GLAVA 12. MNOGOPROCESSORNYE SISTEMY
V klassicheskoj postanovke dlya sistemy UNIX predpolagaetsya ispol'zovanie
odnoprocessornoj arhitektury, sostoyashchej iz odnogo CP, pamyati i periferijnyh
ustrojstv. Mnogoprocessornaya arhitektura, naprotiv, vklyuchaet v sebya dva i
bolee CP, sovmestno ispol'zuyushchih obshchuyu pamyat' i periferijnye ustrojstva (Ri-
sunok 12.1), raspolagaya bol'shimi vozmozhnostyami v uvelichenii proizvoditel'-
nosti sistemy, svyazannymi s odnovremennym ispolneniem processov na raznyh
CP. Kazhdyj CP funkcioniruet nezavisimo ot drugih, no vse oni rabotayut s od-
nim i tem zhe yadrom operacionnoj sistemy. Povedenie processov v takoj sisteme
nichem ne otlichaetsya ot povedeniya v odnoprocessornoj sisteme - s sohraneniem
semantiki obrashcheniya k kazhdoj sistemnoj funkcii - no pri etom oni mogut otk-
ryto peremeshchat'sya s odnogo processora na drugoj. Hotya, k sozhaleniyu, eto ne
privodit k snizheniyu zatrat processornogo vremeni, svyazannogo s vypolneniem
processa. Otdel'nye mnogoprocessornye sistemy nazyvayutsya sistemami s prisoe-
dinennymi processorami, poskol'ku v nih periferijnye ustrojstva dostupny ne
dlya vseh processorov. Za isklyucheniem osobo ogovorennyh sluchaev, v nastoyashchej
glave ne provoditsya nikakih razlichij mezhdu sistemami s prisoedinennymi pro-
cessorami i ostal'nymi klassami mnogoprocessornyh sistem.
Parallel'naya rabota neskol'kih processorov v rezhime yadra po vypolneniyu
razlichnyh processov sozdaet ryad problem, svyazannyh s sohraneniem celostnosti
dannyh i reshaemyh blagodarya ispol'zovaniyu sootvetstvuyushchih mehanizmov zashchity.
Nizhe budet pokazano, pochemu klassicheskij variant sistemy UNIX ne mozhet byt'
prinyat v mnogoprocessornyh sistemah bez vneseniya neobhodimyh izmenenij, a
takzhe budut rassmotreny dva varianta, prednaznachennye dlya raboty v ukazannoj
srede.
+-----------+ +-----------+ +-----------+
| Processor | | Processor | | Processor |
| 1 | | 2 | ........... | n |
+-----+-----+ +-----+-----+ +-----+-----+
----------+-------+-------+--------------+------------+-----------
+---+----+ +-----------+-------------+
| Pamyat' | | Periferijnye ustrojstva |
+--------+ +-------------------------+
Risunok 12.1. Mnogoprocessornaya konfiguraciya
12.1 PROBLEMY, SVYAZANNYE S MNOGOPROCESSORNYMI SISTEMAMI
V glave 2 my govorili o tom, chto zashchita celostnosti struktur dannyh yadra
sistemy UNIX obespechivaetsya dvumya sposobami: yadro ne mozhet vygruzit' odin
process i pereklyuchit'sya na kontekst drugogo, esli rabota proizvoditsya v re-
zhime yadra, krome togo, esli pri vypolnenii kriticheskogo uchastka programmy
obrabotchik voznikayushchih preryvanij mozhet povredit' struktury dannyh yadra, vse
voznikayushchie preryvaniya tshchatel'no maskiruyutsya. V mnogoprocessornoj sisteme,
odnako, esli dva i bolee processov vypolnyayutsya odnovremenno v rezhime yadra na
raznyh processorah, narushenie celostnosti yadra mozhet proizojti dazhe nesmotrya
na prinyatie zashchitnyh mer, s drugoj storony, v odnoprocessornoj sisteme vpol-
ne dostatochnyh.
362
+-------------------------------------------------------+
| struct queue { |
| |
| } *bp, *bp1; |
| bp1->forp=bp->forp; |
| bp1->backp=bp; |
| bp->forp=bp1; |
| /* rassmotrite vozmozhnost' pereklyucheniya konteksta v |
| * etom meste */ |
| bp1->forp->backp=bp1; |
+-------------------------------------------------------+
Risunok 12.2. Vklyuchenie bufera v spisok s dvojnymi ukazatelyami
V kachestve primera rassmotrim fragment programmy iz glavy 2 (Risunok
12.2), v kotorom novaya struktura dannyh (ukazatel' bp1) pomeshchaetsya v spisok
posle sushchestvuyushchej struktury (ukazatel' bp). Predpolozhim, chto etot fragment
vypolnyaetsya odnovremenno dvumya processami na raznyh CP, prichem processor A
pytaetsya pomestit' vsled za strukturoj bp strukturu bpA, a processor B -
strukturu bpB. Po povodu sopostavleniya bystrodejstviya processorov ne priho-
ditsya delat' nikakih predpolozhenij: vozmozhen dazhe naihudshij sluchaj, kogda
processor B ispolnyaet 4 komandy yazyka Si, prezhde chem processor A ispolnit
odnu. Pust', naprimer, vypolnenie programmy processorom A priostanavlivaetsya
v svyazi s obrabotkoj preryvaniya. V rezul'tate, dazhe nesmotrya na blokirovku
ostal'nyh preryvanij, celostnost' dannyh budet postavlena pod ugrozu (v gla-
ve 2 etot moment uzhe poyasnyalsya).
YAdro obyazano udostoverit'sya v tom, chto takogo roda narushenie ne smozhet
proizojti. Esli vopros ob opasnosti vozniknoveniya narusheniya celostnosti os-
tavit' otkrytym, kak by redko podobnye narusheniya ni sluchalis', yadro utratit
svoyu neuyazvimost' i ego povedenie stanet nepredskazuemym. Izbezhat' etogo
mozhno tremya sposobami:
1. Ispolnyat' vse kriticheskie operacii na odnom processore, opirayas' na
standartnye metody sohraneniya celostnosti dannyh v odnoprocessornoj sis-
teme;
2. Reglamentirovat' dostup k kriticheskim uchastkam programmy, ispol'zuya ele-
menty blokirovaniya resursov;
3. Ustranit' konkurenciyu za ispol'zovanie struktur dannyh putem sootvetst-
vuyushchej peredelki algoritmov.
Pervye dva sposoba zdes' my rassmotrim podrobnee, tret'emu sposobu budet
posvyashcheno otdel'noe uprazhnenie.
12.2 GLAVNYJ I PODCHINENNYJ PROCESSORY
Sistemu s dvumya processorami, odin iz kotoryh - glavnyj (master) - mozhet
rabotat' v rezhime yadra, a drugoj - podchinennyj (slave) - tol'ko v rezhime za-
dachi, vpervye realizoval na mashinah tipa VAX 11/780 Gobl (sm. [Goble 81]).
|ta sistema, realizovannaya vnachale na dvuh mashinah, poluchila svoe dal'nejshee
razvitie v sistemah s odnim glavnym i neskol'kimi podchinennymi processorami.
Glavnyj processor neset otvetstvennost' za obrabotku vseh obrashchenij k opera-
cionnoj sisteme i vseh preryvanij. Podchinennye processory vedayut vypolneniem
processov v rezhime zadachi i informiruyut glavnyj processor o vseh proizvodi-
myh obrashcheniyah k sistemnym funkciyam.
Vybor processora, na kotorom budet vypolnyat'sya dannyj process, proizvo-
ditsya v sootvetstvii s algoritmom dispetcherizacii (Risunok 12.3). V sootvet-
stvuyushchej zapisi tablicy processov poyavlyaetsya novoe pole, v kotoroe zapisyva-
etsya identifikator vybrannogo processora; predpolozhim dlya prostoty, chto on
pokazyvaet, yavlyaetsya li processor glavnym ili podchinennym. Kogda process
363
proizvodit obrashchenie k sistemnoj funkcii, vypolnyayas' na podchinennom proces-
sore, podchinennoe yadro pereustanavlivaet znachenie polya identifikacii proces-
sora takim obrazom, chtoby ono ukazyvalo na glavnyj processor, i pereklyuchaet
kontekst na drugie processy (Risunok 12.4). Glavnoe yadro zapuskaet na vypol-
nenie process s naivysshim prioritetom sredi teh processov, kotorye dolzhny
vypolnyat'sya na glavnom processore. Kogda vypolnenie sistemnoj funkcii zaver-
shaetsya, pole identifikacii processora perenastraivaetsya obratno, i process
vnov' vozvrashchaetsya na podchinennyj processor.
Esli processy dolzhny vypolnyat'sya na glavnom processore, zhelatel'no, chto-
by glavnyj processor obrabatyval ih kak mozhno skoree i ne zastavlyal ih zhdat'
svoej ocheredi chereschur dolgo. Pohozhaya motivirovka privoditsya v ob®yasnenie
vygruzki processa iz pamyati v odnoprocessornoj sisteme posle vyhoda iz sis-
temnoj funkcii s osvobozhdeniem sootvetstvuyushchih resursov dlya vypolneniya bolee
nasushchnyh schetnyh operacij. Esli v tot moment, kogda podchinennyj processor
delaet zapros na ispolnenie sistemnoj funkcii, glavnyj process vypolnyaetsya v
rezhime zadachi, ego vypolnenie budet prodolzhat'sya do sleduyushchego pereklyucheniya
konteksta. Glavnyj processor reagiroval by gorazdo bystree, esli by podchi-
nennyj processor ustanavlival pri etom global'nyj flag; proveryaya ustanovku
flaga vo vremya obrabotki ocherednogo preryvaniya po tajmeru, glavnyj processor
proizvel by v itoge pereklyuchenie konteksta maksimum cherez odin tajmernyj
tik. S drugoj storony, podchinennyj processor mog by prervat' rabotu glavnogo
i zastavit' ego pereklyuchit' kontekst nemedlenno, no dannaya vozmozhnost' tre-
buet special'noj apparatnoj realizacii.
+------------------------------------------------------------+
| algoritm schedule_process (modificirovannyj) |
| vhodnaya informaciya: otsutstvuet |
| vyhodnaya informaciya: otsutstvuet |
| { |
| vypolnyat' poka (dlya zapuska ne budet vybran odin iz pro-|
| cessov) |
| { |
| esli (rabota vedetsya na glavnom processore) |
| dlya (vseh processov v ocheredi gotovyh k vypolne- |
| niyu) |
| vybrat' process, imeyushchij naivysshij prioritet |
| sredi zagruzhennyh v pamyat'; |
| v protivnom sluchae /* rabota vedetsya na podchinen- |
| * nom processore */ |
| dlya (teh processov v ocheredi, kotorye ne nuzhdayut-|
| sya v glavnom processore) |
| vybrat' process, imeyushchij naivysshij prioritet |
| sredi zagruzhennyh v pamyat'; |
| esli (dlya zapuska ne podhodit ni odin iz processov) |
| ne zagruzhat' mashinu, perehodyashchuyu v sostoyanie pro-|
| stoya; |
| /* iz etogo sostoyaniya mashina vyhodit v rezul'tate|
| * preryvaniya */ |
| } |
| ubrat' vybrannyj process iz ocheredi gotovyh k vypolne- |
| niyu; |
| pereklyuchit'sya na kontekst vybrannogo processa, vozobno- |
| vit' ego vypolnenie; |
| } |
+------------------------------------------------------------+
Risunok 12.3. Algoritm dispetcherizacii
364
+------------------------------------------------------------+
| algoritm syscall /* ispravlennyj algoritm vyzova sistem- |
| * noj funkcii */ |
| vhodnaya informaciya: kod sistemnoj funkcii |
| vyhodnaya informaciya: rezul'tat vypolneniya sistemnoj funkcii|
| { |
| esli (rabota vedetsya na podchinennom processore) |
| { |
| pereustanovit' znachenie polya identifikacii processo-|
| ra v sootvetstvuyushchej zapisi tablicy processov; |
| proizvesti pereklyuchenie konteksta; |
| } |
| vypolnit' obychnyj algoritm realizacii sistemnoj funkcii;|
| perenastroit' znachenie polya identifikacii processora, |
| chtoby ono ukazyvalo na "lyuboj" (podchinennyj); |
| esli (na glavnom processore dolzhny vypolnyat'sya drugie |
| processy) |
| proizvesti pereklyuchenie konteksta; |
| } |
+------------------------------------------------------------+
Risunok 12.4. Algoritm obrabotki obrashcheniya k sistemnoj funkcii
Programma obrabotki preryvanij po tajmeru na podchinennom processore sle-
dit za periodichnost'yu perezapuska processov, ne dopuskaya monopol'nogo is-
pol'zovaniya processora odnoj zadachej. Krome togo, kazhduyu sekundu eta prog-
ramma vyvodit podchinennyj processor iz sostoyaniya bezdejstviya (prostoya). Pod-
chinennyj processor vybiraet dlya vypolneniya process s naivysshim prioritetom
sredi teh processov, kotorye ne nuzhdayutsya v glavnom processore.
Edinstvennym mestom, gde celostnost' struktur dannyh yadra eshche podverga-
etsya opasnosti, yavlyaetsya algoritm dispetcherizacii, poskol'ku on ne predohra-
nyaet ot vybora processa na vypolnenie srazu na dvuh processorah. Naprimer,
esli v konfiguracii imeetsya odin glavnyj processor i dva podchinennyh, ne is-
klyuchena vozmozhnost' togo, chto oba podchinennyh processora vyberut dlya vypol-
neniya v rezhime zadachi odin i tot zhe process. Esli oba processora nachnut vy-
polnyat' ego parallel'no, osushchestvlyaya chtenie i zapis', eto neizbezhno privedet
k iskazheniyu soderzhimogo adresnogo prostranstva processa.
Izbezhat' vozniknoveniya etoj problemy mozhno dvumya sposobami. Vo-pervyh,
glavnyj processor mozhet yavno ukazat', na kakom iz podchinennyh processorov
sleduet vypolnyat' dannyj process. Esli na kazhdyj processor napravlyat' nes-
kol'ko processov, voznikaet neobhodimost' v sbalansirovanii nagruzki (na
odin iz processorov naznachaetsya bol'shoe kolichestvo processov, v to vremya kak
drugie processory prostaivayut). Zadacha raspredeleniya nagruzki mezhdu proces-
sorami lozhitsya na glavnoe yadro. Vo-vtoryh, yadro mozhet prosledit' za tem,
chtoby v kazhdyj moment vremeni v algoritme dispetcherizacii prinimal uchastie
tol'ko odin processor, dlya etogo ispol'zuyutsya mehanizmy, podobnye semaforam.
Podderzhka sistemy UNIX v mnogoprocessornoj konfiguracii mozhet vklyuchat' v
sebya razbienie yadra sistemy na kriticheskie uchastki, parallel'noe vypolnenie
kotoryh na neskol'kih processorah ne dopuskaetsya. Takie sistemy prednaznacha-
lis' dlya raboty na mashinah AT&T 3B20A i IBM 370, dlya razbieniya yadra ispol'-
zovalis' semafory (sm. [Bach 84]). Nizhesleduyushchie rassuzhdeniya pomogayut ponyat'
sut' dannoj osobennosti. Pri blizhajshem rassmotrenii srazu zhe voznikayut dva
voprosa: kak ispol'zovat' semafory i gde opredelit' kriticheskie uchastki.
Kak uzhe govorilos' v glave 2, esli pri vypolnenii kriticheskogo uchastka
programmy process priostanavlivaetsya, dlya zashchity uchastka ot posyagatel'stv so
365
storony drugih processov algoritmy raboty yadra odnoprocessornoj sistemy UNIX
ispol'zuyut blokirovku. Mehanizm ustanovleniya blokirovki:
vypolnyat' poka (blokirovka ustanovlena) /* operaciya proverki */
priostanovit'sya (do snyatiya blokirovki);
ustanovit' blokirovku;
mehanizm snyatiya blokirovki:
snyat' blokirovku;
vyvesti iz sostoyaniya priostanova vse processy, priostanovlennye v re-
zul'tate blokirovki;
Process A/Processor A Process B/Processor B
+---------------------------------------------------------
| +---------------------------+
| | Blokirovka NE ustanovlena |
| - +---------------------------+ -
| - -
| - -
| Proveryaet, ustanovlena Proveryaet, ustanovlena
| li blokirovka li blokirovka
| (net) (net)
t - + - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
| Ustanavlivaet Ustanavlivaet
| blokirovku blokirovku
|
| Ispol'zuet resurs Ispol'zuet resurs
v ^ ^
Vremya | |
+------+ +------+
Opasnost' narusheniya celostnosti
Risunok 12.5. Konkurenciya za ustanovku blokirovki v mnogopro-
cessornyh sistemah
Blokirovki takogo roda ohvatyvayut nekotorye kriticheskie uchastki, no ne
rabotayut v mnogoprocessornyh sistemah, chto vidno iz Risunka 12.5. Predpolo-
zhim, chto blokirovka snyata i chto dva processa na raznyh processorah odnovre-
menno pytayutsya proverit' ee nalichie i ustanovit' ee. V moment t oni obnaru-
zhivayut snyatie blokirovki, ustanavlivayut ee vnov', vstupayut v kriticheskij
uchastok i sozdayut opasnost' narusheniya celostnosti struktur dannyh yadra. V
uslovii odnovremennosti imeetsya otklonenie: mehanizm ne srabotaet, esli pe-
red tem, kak process vypolnyaet operaciyu proverki, ni odin drugoj process ne
vypolnil operaciyu ustanovleniya blokirovki. Esli, naprimer, posle obnaruzheniya
snyatiya blokirovki processor A obrabatyvaet preryvanie i v etot moment pro-
cessor B vypolnyaet proverku i ustanavlivaet blokirovku, po vyhode iz prery-
vaniya processor A tak zhe ustanovit blokirovku. CHtoby predotvratit' voznikno-
venie podobnoj situacii, nuzhno sdelat' tak, chtoby procedura blokirovaniya by-
la nedelimoj: proverku nalichiya blokirovki i ee ustanovku sleduet ob®edinit'
v odnu operaciyu, chtoby v kazhdyj moment vremeni s blokirovkoj imel delo tol'-
ko odin process.
12.3.1 Opredelenie semaforov
Semafor predstavlyaet soboj obrabatyvaemyj yadrom celochislennyj ob®ekt,
dlya kotorogo opredeleny sleduyushchie elementarnye (nedelimye) operacii:
* Inicializaciya semafora, v rezul'tate kotoroj semaforu prisvaivaetsya ne-
otricatel'noe znachenie;
* Operaciya tipa P, umen'shayushchaya znachenie semafora. Esli znachenie semafora
366
opuskaetsya nizhe nulevoj otmetki, vypolnyayushchij operaciyu process priosta-
navlivaet svoyu rabotu;
* Operaciya tipa V, uvelichivayushchaya znachenie semafora. Esli znachenie semafora
v rezul'tate operacii stanovitsya bol'she ili ravno 0, odin iz processov,
priostanovlennyh vo vremya vypolneniya operacii P, vyhodit iz sostoyaniya
priostanova;
* Uslovnaya operaciya tipa P, sokrashchenno CP (conditional P), umen'shayushchaya
znachenie semafora i vozvrashchayushchaya logicheskoe znachenie "istina" v tom slu-
chae, kogda znachenie semafora ostaetsya polozhitel'nym. Esli v rezul'tate
operacii znachenie semafora dolzhno stat' otricatel'nym ili nulevym, nika-
kih dejstvij nad nim ne proizvoditsya i operaciya vozvrashchaet logicheskoe
znachenie "lozh'".
Opredelennye takim obrazom semafory, bezuslovno, nikak ne svyazany s se-
maforami pol'zovatel'skogo urovnya, rassmotrennymi v glave 11.
12.3.2 Realizaciya semaforov
Dijkstra [Dijkstra 65] pokazal, chto semafory mozhno realizovat' bez is-
pol'zovaniya special'nyh mashinnyh instrukcij. Na Risunke 12.6 predstavleny
realizuyushchie semafory funkcii, napisannye na yazyke Si. Funkciya Pprim blokiru-
et semafor po rezul'tatam proverki znachenij, soderzhashchihsya v massive val;
kazhdyj processor v sisteme upravlyaet znacheniem odnogo elementa massiva.
Prezhde chem zablokirovat' semafor, processor proveryaet, ne zablokirovan li
uzhe semafor drugimi processorami (sootvetstvuyushchie im elementy v massive val
togda imeyut znacheniya, ravnye 2), a takzhe ne predprinimayutsya li popytki v
dannyj moment zablokirovat' semafor so storony processorov s bolee nizkim
kodom identifikacii (sootvetstvuyushchie im elementy imeyut znacheniya, ravnye 1).
Esli lyuboe iz uslovij vypolnyaetsya, processor pereustanavlivaet znachenie svo-
ego elementa v 1 i povtoryaet popytku. Kogda funkciya Pprim otkryvaet vneshnij
cikl, peremennaya cikla imeet znachenie, na edinicu prevyshayushchee kod identifi-
kacii togo processora, kotoryj ispol'zoval resurs poslednim, tem samym ga-
rantiruetsya, chto ni odin iz processorov ne mozhet monopol'no zavladet' resur-
som (v kachestve dokazatel'stva soshlemsya na [Dijkstra 65] i [Coffman 73]).
Funkciya Vprim osvobozhdaet semafor i otkryvaet dlya drugih processorov vozmozh-
nost' polucheniya isklyuchitel'nogo dostupa k resursu putem ochistki sootvetstvu-
yushchego tekushchemu processoru elementa v massive val i perenastrojki znacheniya
lastid. CHtoby zashchitit' resurs, sleduet vypolnit' sleduyushchij nabor komand:
Pprim(semafor);
komandy ispol'zovaniya resursa;
Vprim(semafor);
V bol'shinstve mashin imeetsya nabor elementarnyh (nedelimyh) instrukcij,
realizuyushchih operaciyu blokirovaniya bolee deshevymi sredstvami, ibo cikly, vho-
dyashchie v funkciyu Pprim, rabotayut medlenno i snizhayut proizvoditel'nost' siste-
my. Tak, naprimer, v mashinah serii IBM 370 podderzhivaetsya instrukciya compare
and swap (sravnit' i perestavit'), v mashine AT&T 3B20 - instrukciya read and
clear (prochitat' i ochistit'). Pri vypolnenii instrukcii read and clear pro-
cessor schityvaet soderzhimoe yachejki pamyati, ochishchaet ee (sbrasyvaet v 0) i po
rezul'tatam sravneniya pervonachal'nogo soderzhimogo s 0 ustanavlivaet kod za-
versheniya instrukcii. Esli tu zhe instrukciyu nad toj zhe yachejkoj parallel'no
vypolnyaet eshche odin processor, odin iz dvuh processorov prochitaet pervona-
chal'noe soderzhimoe, a drugoj - 0: nedelimost' operacii garantiruetsya appa-
ratnym putem. Takim obrazom, za schet ispol'zovaniya dannoj instrukcii funkciyu
Pprim mozhno bylo by realizovat' menee slozhnymi sredstvami (Risunok 12.7).
Process povtoryaet instrukciyu read and clear v cikle do teh por, poka ne bu-
det schitano znachenie, otlichnoe ot nulya. Nachal'noe znachenie komponenty sema-
fora, svyazannoj s blokirovkoj, dolzhno byt' ravno 1.
367
Kak takovuyu, dannuyu semafornuyu konstrukciyu nel'zya realizovat' v sostave
yadra operacionnoj sistemy, poskol'ku rabotayushchij s nej process ne vyhodit iz
cikla, poka ne dostignet svoej celi. Esli
+------------------------------------------------------------+
| struct semaphore |
| { |
| int val[NUMPROCS]; /* zamok---1 element na kazhdyj pro- |
| /* cessor */ |
| int lastid; /* identifikator processora, polu- |
| /* chivshego semafor poslednim */ |
| }; |
| int procid; /* unikal'nyj identifikator proces- |
| /* sora */ |
| int lastid; /* identifikator processora, polu- |
| /* chivshego semafor poslednim */ |
| |
| INIT(semaphore) |
| struct semaphore semaphore; |
| { |
| int i; |
| for (i = 0; i < NUMPROCS; i++) |
| semaphore.val[i] = 0; |
| } |
| Pprim(semaphore) |
| struct semaphore semaphore; |
| { |
| int i,first; |
| |
| loop: |
| first = lastid; |
| semaphore.val[procid] = 1; |
| /* prodolzhenie na sleduyushchej stranice */ |
+------------------------------------------------------------+
Risunok 12.6. Realizaciya semafornoj blokirovki na Si
semafor ispol'zuetsya dlya blokirovaniya struktury dannyh, process, obnaruzhiv
semafor zablokirovannym, priostanavlivaet svoe vypolnenie, chtoby yadro imelo
vozmozhnost' pereklyuchit'sya na kontekst drugogo processa i vypolnit' druguyu
poleznuyu rabotu. S pomoshch'yu funkcij Pprim i Vprim mozhno realizovat' bolee
slozhnyj nabor semafornyh operacij, sootvetstvuyushchij tomu sostavu, kotoryj op-
redelen v razdele 12.3.1.
Dlya nachala dadim opredelenie semafora kak struktury, sostoyashchej iz polya
blokirovki (upravlyayushchego dostupom k semaforu), znacheniya semafora i ocheredi
processov, priostanovlennyh po semaforu. Pole blokirovki soderzhit informa-
ciyu, otkryvayushchuyu vo vremya vypolneniya operacij tipa P i V dostup k drugim po-
lyam struktury tol'ko odnomu processu. Po zavershenii operacii znachenie polya
sbrasyvaetsya. |to znachenie opredelyaet, razreshen li processu dostup k kriti-
cheskomu uchastku, zashchishchaemomu semaforom. V nachale vypolneniya algoritma opera-
cii P (Risunok 12.8) yadro s pomoshch'yu funkcii Pprim predostavlyaet processu
pravo isklyuchitel'nogo dostupa k semaforu i umen'shaet znachenie semafora. Esli
semafor imeet neotricatel'noe znachenie, tekushchij process poluchaet dostup k
kriticheskomu uchastku. Po zavershenii raboty process sbrasyvaet blokirovku se-
mafora (s pomoshch'yu funkcii Vprim), otkryvaya dostup k semaforu dlya drugih pro-
cessov, i vozvrashchaet priznak uspeshnogo zaversheniya. Esli zhe v rezul'tate
umen'sheniya znachenie semafora stanovitsya otricatel'nym, yadro priostanavlivaet
vypolnenie processa, ispol'zuya algoritm,
368
+------------------------------------------------------------+
| forloop: |
| for (i = first; i < NUMPROCS; i++) |
| { |
| if (i == procid) |
| { |
| semaphore.val[i] = 2; |
| for (i = 1; i < NUMPROCS; i++) |
| if (i != procid && semaphore.val[i] == 2) |
| goto loop; |
| lastid = procid; |
| return; /* uspeshnoe zavershenie, resurs |
| /* mozhno ispol'zovat' |
| */ |
| } |
| else if (semaphore.val[i]) |
| goto loop; |
| } |
| first = 1; |
| goto forloop; |
| } |
| Vprim(semaphore) |
| struct semaphore semaphore; |
| { |
| lastid = (procid + 1) % NUMPROCS; /* na sleduyushchij |
| /* processor */ |
| semaphore.val[procid] = 0; |
| } |
+------------------------------------------------------------+
Risunok 12.6. Realizaciya semafornoj blokirovki na Si (prodolzhenie)
podobnyj algoritmu sleep (glava 6): osnovyvayas' na znachenii prioriteta, yadro
proveryaet postupivshie signaly, vklyuchaet tekushchij process v spisok priostanov-
lennyh processov, v kotorom poslednie predstavleny v poryadke postupleniya, i
vypolnyaet pereklyuchenie konteksta. Operaciya V (Risunok 12.9) poluchaet isklyu-
chitel'nyj dostup k semaforu cherez funkciyu Pprim i uvelichivaet znachenie sema-
fora. Esli ochered' priostanovlennyh po semaforu processov nepusta, yadro vy-
biraet iz nee pervyj process i perevodit ego v sostoyanie "gotovnosti k za-
pusku".
Operacii P i V po svoemu dejstviyu pohozhi na funkcii sleep i wakeup.
Glavnoe razlichie mezhdu nimi sostoit v tom, chto semafor yavlyaetsya strukturoj
dannyh, togda kak ispol'zuemyj funkciyami sleep i wakeup adres predstavlyaet
soboj vsego lish' chislo. Esli nachal'noe znachenie semafora - nulevoe, pri vy-
polnenii operacii P nad semaforom process vsegda priostanavlivaetsya, poetomu
operaciya P mozhet zamenyat' funkciyu sleep. Operaciya V, tem ne menee, vyvodit
iz sostoyaniya priostanova tol'ko odin process, togda kak odnoprocessornaya
funkciya wakeup vozobnovlyaet vse processy, priostanovlennye po adresu, svya-
zannomu s sobytiem.
S tochki zreniya semantiki ispol'zovanie funkcii wakeup oznachaet: dannoe
sistemnoe uslovie bolee ne udovletvoryaetsya, sledovatel'no, vse priostanov-
lennye po usloviyu processy dolzhny vyjti iz sostoyaniya priostanova. Tak, nap-
rimer, processy, priostanovlennye v svyazi s zanyatost'yu bufera, ne dolzhny
dal'she prebyvat' v etom sostoyanii, esli bufer bol'she ne ispol'zuetsya, poeto-
mu oni vozob-
novlyayutsya yadrom. Eshche odin primer: esli neskol'ko processov vyvodyat dannye na
terminal s pomoshch'yu funkcii write, terminal'nyj drajver mozhet perevesti ih v
369
+-------------------------------------------------------+
| struct semaphore { |
| int lock; |
| }; |
| |
| Init(semaphore) |
| struct semaphore semaphore; |
| { |
| semaphore.lock = 1; |
| } |
| |
| Pprim(semaphore) |
| struct semaphore semaphore; |
| { |
| while (read_and_clear(semaphore.lock)) |
| ; |
| } |
| |
| Vprim(semaphore) |
| struct semaphore semaphore; |
| { |
| semaphore.lock = 1; |
| } |
+-------------------------------------------------------+
Risunok 12.7. Operacii nad semaforom, ispol'zuyushchie instrukciyu
read and clear
sostoyanie priostanova v svyazi s nevozmozhnost'yu obrabotki bol'shih ob®emov in-
formacii. Pozzhe, kogda drajver budet gotov k priemu sleduyushchej porcii dannyh,
on vozobnovit vse priostanovlennye im processy. Ispol'zovanie operacij P i V
v teh sluchayah, kogda ustanavlivayushchie blokirovku processy poluchayut dostup k
resursu poocheredno, a vse ostal'nye processy - v poryadke postupleniya zapro-
sov, yavlyaetsya bolee predpochtitel'nym. V sravnenii s odnoprocessornoj proce-
duroj blokirovaniya (sleep-lock) dannaya shema obychno vyigryvaet, tak kak esli
pri nastuplenii sobytiya vse processy vozobnovlyayutsya, bol'shinstvo iz nih mo-
zhet vnov' natknut'sya na blokirovku i snova perejti v sostoyanie priostanova.
S drugoj storony, v teh sluchayah, kogda trebuetsya vyvesti iz sostoyaniya prios-
tanova vse processy odnovremenno, ispol'zovanie operacij P i V predstavlyaet
izvestnuyu slozhnost'.
Esli operaciya vozvrashchaet znachenie semafora, yavlyaetsya li ona ekvivalent-
noj funkcii wakeup ?
while (value(semaphore) < 0)
V(semaphore);
Esli vmeshatel'stva so storony drugih processov net, yadro povtoryaet cikl
do teh por, poka znachenie semafora ne stanet bol'she ili ravno 0, ibo eto oz-
nachaet, chto v sostoyanii priostanova po semaforu net bol'she ni odnogo proces-
sa. Tem ne menee, nel'zya isklyu-
chit' i takuyu vozmozhnost', chto srazu posle togo, kak process A pri testirova-
nii semafora na odnoimennom processore obnaruzhil nulevoe znachenie semafora,
process B na svoem processore vypolnyaet operaciyu P, umen'shaya znachenie sema-
fora do -1 (Risunok 12.10). Process A prodolzhit svoe vypolnenie, dumaya, chto
im vozobnovleny vse priostanovlennye po semaforu processy. Takim obrazom,
cikl vypolneniya operacii ne daet garantii vozobnovleniya vseh priostanovlen-
nyh processov, poskol'ku on ne yavlyaetsya elementarnym.
370
+------------------------------------------------------------+
| algoritm P /* operaciya nad semaforom tipa P */ |
| vhodnaya informaciya: (1) semafor |
| (2) prioritet |
| vyhodnaya informaciya: 0 - v sluchae normal'nogo zaversheniya |
| -1 - v sluchae avarijnogo vyhoda iz |
| sostoyaniya priostanova po signalu, pri-|
| nyatomu v rezhime yadra |
| { |
| Pprim(semaphore.lock); |
| umen'shit' (semaphore.value); |
| esli (semaphore.value >= 0) |
| { |
| Vprim(semaphore.lock); |
| vernut' (0); |
| } |
| /* sleduet perejti v sostoyanie priostanova */ |
| esli (proveryayutsya signaly) |
| { |
| esli (imeetsya signal, preryvayushchij nahozhdenie v sos- |
| toyanii priostanova) |
| { |
| uvelichit' (semaphore.value); |
| esli (signal prinyat v rezhime yadra) |
| { |
| Vprim(semaphore.lock); |
| vernut' (-1); |
| } |
| v protivnom sluchae |
| { |
| Vprim(semaphore.lock); |
| longjmp; |
| } |
| } |
| } |
| postavit' process v konec spiska priostanovlennyh po se-|
| maforu; |
| Vprim(semaphore.lock); |
| vypolnit' pereklyuchenie konteksta; |
| proverit' signaly (sm. vyshe); |
| vernut' (0); |
| } |
+------------------------------------------------------------+
Risunok 12.8. Algoritm vypolneniya operacii P
Rassmotrim eshche odin fenomen, svyazannyj s ispol'zovaniem semaforov v od-
noprocessornoj sisteme. Predpolozhim, chto dva processa, A i B, konkuriruyut za
semafor. Process A obnaruzhivaet, chto semafor svoboden i chto process B prios-
tanovlen; znachenie semafora ravno -1. Kogda s pomoshch'yu operacii V process A
osvobozhdaet semafor, on vyvodit tem samym process B iz sostoyaniya priostanova
i vnov' delaet znachenie semafora nulevym. Teper' predpolozhim, chto process A,
po-prezhnemu vypolnyayas' v rezhime yadra, pytaetsya snova zablokirovat' semafor.
Proizvodya operaciyu P, process priostanovitsya, poskol'ku semafor imeet nule-
voe znachenie, nesmotrya na to, chto resurs poka svoboden. Sisteme pridetsya
"raskoshelit'sya" na dopolnitel'noe pereklyuchenie konteksta. S drugoj storony,
esli by blokirovka byla realizovana na osnove odnoprocessornoj shemy
371
+------------------------------------------------------------+
| algoritm V /* operaciya nad semaforom tipa V */ |
| vhodnaya informaciya: adres semafora |
| vyhodnaya informaciya: otsutstvuet |
| { |
| Pprim(semaphore.lock); |
| uvelichit' (semaphore.value); |
| esli (semaphore.value <= 0) |
| { |
| udalit' iz spiska processov, priostanovlennyh po se-|
| maforu, pervyj po schetu process; |
| perevesti ego v sostoyanie gotovnosti k zapusku; |
| } |
| Vprim(semaphore.lock); |
| } |
+------------------------------------------------------------+
Risunok 12.9. Algoritm vypolneniya operacii V
(sleep-lock), process A poluchil by pravo na povtornoe ispol'zovanie resursa,
poskol'ku za eto vremya ni odin iz processov ne smog by zablokirovat' ego.
Dlya etogo sluchaya shema sleep-lock bolee podhodit, chem shema s ispol'zovaniem
semaforov.
Kogda blokiruyutsya srazu neskol'ko semaforov, ocherednost' blokirovaniya
dolzhna isklyuchat' vozniknovenie tupikovyh situacij. V kachestve primera rass-
motrim dva semafora, A i B, i dva algoritma, trebuyushchih odnovremennoj bloki-
rovki semaforov. Esli by algoritmy ustanavlivali blokirovku na semafory v
obratnom poryadke, kak sleduet iz Risunka 12.11, posledovalo by vozniknovenie
tupikovoj situacii; process A na odnoimennom processore zahvatyvaet semafor
SA, v to vremya kak process B na svoem processore zahvatyvaet semafor SB.
Process A pytaetsya zahvatit' i semafor SB, no v rezul'tate operacii P pere-
hodit v sostoyanie priostanova, poskol'ku znachenie semafora SB ne prevyshaet
0. To zhe samoe proishodit s processom B, kogda poslednij pytaetsya zahvatit'
semafor SA. Ni tot, ni drugoj processy prodolzhat'sya uzhe ne mogut.
Dlya predotvrashcheniya vozniknoveniya podobnyh situacij ispol'zuyutsya sootvet-
stvuyushchie algoritmy obnaruzheniya opasnosti vzaimnoj blokirovki, ustanavlivayu-
shchie nalichie opasnoj situacii i likvidiruyushchie ee. Tem ne menee, ispol'zovanie
takih algoritmov "utyazhelyaet" yadro. Poskol'ku chislo situacij, v kotoryh pro-
cess dolzhen odnovremenno zahvatyvat' neskol'ko semaforov, dovol'no ograniche-
no, legche bylo by realizovat' algoritmy, preduprezhdayushchie vozniknovenie tupi-
kovyh situacij eshche do togo, kak oni budut imet' mesto. Esli, k primeru, ka-
koj-to nabor semaforov vsegda blokiruetsya v odnom i tom zhe poryadke, tupiko-
vaya situaciya nikogda ne vozniknet. No v tom sluchae, kogda zahvata semaforov
v obratnom poryadke izbezhat' ne
udaetsya, operaciya CP predotvratit vozniknovenie tupikovoj situacii (sm. Ri-
sunok 12.12): esli operaciya zavershitsya neudachno, process B osvobodit svoi
resursy, daby izbezhat' vzaimnoj blokirovki, i pozzhe zapustit algoritm na vy-
polnenie povtorno, skoree vsego togda, kogda process A zavershit rabotu s re-
sursom.
CHtoby predupredit' odnovremennoe obrashchenie processov k resursu, program-
ma obrabotki preryvanij, kazalos' by, mogla vospol'zovat'sya semaforom, no
iz-za togo, chto ona ne mozhet priostanavlivat' svoyu rabotu (sm. glavu 6), is-
pol'zovat' operaciyu P v etoj programme nel'zya. Vmesto etogo mozhno ispol'zo-
vat' "ciklicheskuyu blokirovku" (spin lock) i ne perehodit' v sostoyanie prios-
tanova, kak v sleduyushchem primere:
while (! CP(semaphore));
372
Process A/Processor A Process B/Processor B
+-----------------------------------------------------------
| - +------------------------+ -
| - | Znachenie semafora = -1 | -
| - +------------------------+ -
| proveryaet(znachenie sema- -
| fora < 0) ? -
| (da) -
| V(semafor) -
| - -
| - +------------------------+ -
| - | Znachenie semafora = 0 | -
| - +------------------------+ -
| proveryaet(znachenie sema- -
| fora < 0) ? -
| - -
| - P(semafor)
| - Znachenie semafora = -1
| -
| (net)
| NEVERNO !!
v
Vremya
Risunok 12.10. Neudachnoe imitaciya funkcii wakeup pri ispol'-
zovanii operacii V
Operaciya povtoryaetsya v cikle do teh por, poka znachenie semafora ne prevysit
0; programma obrabotki preryvanij ne priostanavlivaetsya i cikl zavershaetsya
tol'ko togda, kogda znachenie semafora stanet polozhitel'nym, posle chego eto
znachenie budet umen'sheno operaciej CP.
CHtoby predotvratit' situaciyu vzaimnoj blokirovki, yadru nuzhno zapretit'
vse preryvaniya, vypolnyayushchie "ciklicheskuyu blokirovku". Inache vypolnenie pro-
cessa, zahvativshego semafor, budet prervano eshche do togo, kak on smozhet osvo-
bodit' semafor; esli programma obrabotki preryvanij popytaetsya zahvatit'
etot semafor, ispol'zuya "ciklicheskuyu blokirovku", yadro zablokiruet samo se-
bya. V kachestve primera obratimsya k Risunku 12.13. V moment vozniknoveniya
Process A/Processor A Process B/Processor B
+-----------------------------------------------------------
| P(semafor SA); -
| - -
| - -
| - -
| - P(semafor SB);
| - -
| - -
| - -
| - P(semafor SA);
| - priostanavlivaetsya
| -
| P(semafor SB);
| priostanavlivaetsya
|
v Vzaimnaya blokirovka !!
Vremya
Risunok 12.11. Vozniknovenie tupikovoj situacii
iz-za smeny ocherednosti blokirovaniya
373
preryvaniya znachenie semafora ne prevyshaet 0, poetomu rezul'tatom vypolneniya
operacii CP vsegda budet "lozh'". Problema reshaetsya putem zapreshcheniya vseh
preryvanij na to vremya, poka semafor zahvachen processom.
12.3.3 Primery algoritmov
V dannom razdele my rassmotrim chetyre algoritma yadra, realizovannyh s
ispol'zovaniem semaforov. Algoritm vydeleniya bufera illyustriruet slozhnuyu
shemu blokirovaniya, na primere algoritma wait pokazana sinhronizaciya vypol-
neniya processov, shema blokirovaniya drajverov realizuet izyashchnyj podhod k re-
sheniyu dannoj problemy, i nakonec, metod resheniya problemy holostoj raboty
processora pokazyvaet, chto nuzhno sdelat', chtoby izbezhat' konkurencii mezhdu
processami.
12.3.3.1 Vydelenie bufera
Obratimsya eshche raz k algoritmu getblk, rassmotrennomu nami v glave 3. Al-
goritm rabotaet s tremya strukturami dannyh: zagolovkom bufera, hesh-ochered'yu
buferov i spiskom svobodnyh buferov. YAdro svyazyvaet semafor so vsemi ekzemp-
lyarami kazhdoj struktury. Drugimi slovami, esli u yadra imeyutsya v rasporyazhenii
200 buferov, zagolovok kazhdogo iz nih vklyuchaet v sebya semafor, ispol'zuemyj
dlya zahvata bufera; kogda process vypolnyaet nad semaforom operaciyu P, drugie
processy, tozhe pozhelavshie zahvatit' bufer, priostanavlivayutsya do teh por,
poka pervyj process ne ispolnit operaciyu V. U kazhdoj hesh-ocheredi buferov
takzhe imeetsya semafor, blokiruyushchij dostup k ocheredi. V odnoprocessornoj sis-
teme blokirovka hesh-oche-
Process A/Processor A Process B/Processor B
+-----------------------------------------------------------
| P(semafor SA); -
| - -
| - P(semafor SB);
| - -
| - -
| - esli (! CP(semafor SA))
| - {
| - V(semafor SB);
| - perezapustit' algo-
| - ritm
| - }
| P(semafor SB);
| priostanavlivaetsya
v
Vremya
Risunok 12.12. Ispol'zovanie operacii P uslovnogo tipa dlya
predotvrashcheniya vzaimnoj blokirovki
redi ne nuzhna, ibo process nikogda ne perehodit v sostoyanie priostanova, os-
tavlyaya ochered' v nesoglasovannom (neuporyadochennom) vide. V mnogoprocessornoj
sisteme, tem ne menee, vozmozhny situacii, kogda s odnoj i toj zhe hesh-oche-
red'yu rabotayut dva processa; v kazhdyj moment vremeni semafor otkryvaet dos-
374
tup k ocheredi tol'ko dlya odnogo processa. Po tem zhe prichinam i spisok svo-
bodnyh buferov nuzhdaetsya v semafore dlya zashchity soderzhashchejsya v nem informacii
ot iskazheniya.
Na Risunke 12.14 pokazana pervaya chast' algoritma getblk, realizovannaya v
mnogoprocessornoj sisteme s ispol'zovaniem semaforov. Prosmatrivaya bufernyj
kesh v poiskah ukazannogo bloka, yadro s pomoshch'yu operacii P zahvatyvaet sema-
for, prinadlezhashchij hesh-ocheredi. Esli nad semaforom uzhe kem-to proizvedena
operaciya dannogo tipa, tekushchij process priostanavlivaetsya do teh por, poka
process, zahvativshij semafor, ne osvobodit ego, vypolniv operaciyu V. Kogda
tekushchij process poluchaet pravo isklyuchitel'nogo kontrolya nad hesh-ochered'yu, on
pristupaet k poisku podhodyashchego bufera. Predpolozhim, chto bufer nahoditsya v
hesh-ocheredi. YAdro (process A) pytaetsya zahvatit' bufer, no esli ono ispol'-
zuet operaciyu P i esli bufer uzhe zahvachen, yadru pridetsya priostanovit' svoyu
rabotu, ostaviv hesh-ochered' zablokirovannoj i ne dopuskaya takim obrazom ob-
rashchenij k nej so storony drugih processov, dazhe esli poslednie vedut poisk
nezahvachennyh buferov. Pust' vmesto etogo process A zahvatyvaet bufer, is-
pol'zuya operaciyu CP; esli operaciya zavershaetsya uspeshno, bufer stanovitsya ot-
krytym dlya processa. Process A zahvatyvaet semafor, prinadlezhashchij spisku
svobodnyh buferov, vypolnyaya operaciyu CP, poskol'ku semafor zahvatyvaetsya na
neprodolzhitel'noe vremya i, sledovatel'no, priostanavlivat' svoyu rabotu, vy-
polnyaya operaciyu P, process prosto ne imeet vozmozhnosti. YAdro ubiraet bufer
iz spiska svobodnyh buferov, snimaet blokirovku so spiska i s hesh-ocheredi i
vozvrashchaet zahvachennyj bufer.
|
| P(semafor);
| (Znachenie semafora teper' ravno 0)
|
| Preryvanie
|
| CP(semafor) zavershaetsya neudachno ---
| semafor zahvachen
|
| Semafor ne osvobozhdaetsya do vyhoda iz preryvaniya.
|
| Vyhod iz preryvaniya bez ego obrabotki nevozmozhen.
|
| Tupikovaya situaciya (vzaimnaya blokirovka)
v
Vremya
Risunok 12.13. Vzaimnaya blokirovka pri vypolnenii programmy
obrabotki preryvaniya
Predpolozhim, chto operaciya CP nad buferom zavershilas' neudachno iz-za to-
go, chto semafor, prinadlezhashchij buferu, okazalsya zahvachennym. Process A osvo-
bozhdaet semafor, svyazannyj s hesh-ochered'yu, i priostanavlivaetsya, pytayas' vy-
polnit' operaciyu P nad semaforom bufera. Operaciya P nad semaforom budet vy-
polnyat'sya, nesmotrya na to, chto operaciya CP uzhe poterpela neudachu. Po zaver-
shenii vypolneniya operacii process A poluchaet vlast' nad buferom. Tak kak v
ostavshejsya chasti algoritma predpolagaetsya, chto bufer i hesh-ochered' zahvache-
ny, process A teper' pytaetsya zahvatit' hesh-ochered' (*). Poskol'ku ochered-
---------------------------------------
(*) Vmesto zahvata hesh-ocheredi v etom meste mozhno bylo by ustanovit' soot-
vetstvuyushchij flag, proveryaemyj dalee pered vypolneniem operacii V, no
chtoby proillyustrirovat' shemu zahvata semaforov v obratnoj posledova-
tel'nosti, v izlozhenii my budem priderzhivat'sya ranee opisannogo varian-
ta.
375
nost' zahvata zdes' (snachala semafor bufera, potom semafor ocheredi) obratna
vysheukazannoj ocherednosti, nad semaforom vypolnyaetsya operaciya CP. Esli po-
pytka zahvata zakanchivaetsya neudachej, imeet mesto obychnaya obrabotka, trebuyu-
shchayasya po hodu zadachi. No esli zahvat udaetsya, yadro ne mozhet byt' uvereno v
+------------------------------------------------------------+
| algoritm getblk /* mnogoprocessornaya versiya */ |
| vhodnaya informaciya: nomer fajlovoj sistemy |
| nomer bloka |
| vyhodnaya informaciya: zahvachennyj bufer, prednaznachennyj dlya|
| obrabotki soderzhimogo bloka |
| { |
| vypolnyat' (poka bufer ne budet obnaruzhen) |
| { |
| P(semafor hesh-ocheredi); |
| esli (blok nahoditsya v hesh-ocheredi) |
| { |
| esli (operaciya CP(semafor bufera) zavershaetsya ne- |
| udachno) /* bufer zanyat */ |
| { |
| V(semafor hesh-ocheredi); |
| P(semafor bufera); /* priostanov do momen-|
| * ta osvobozhdeniya |
| */ |
| esli (operaciya CP(semafor hesh-ocheredi) zaversha-|
| etsya neudachno) |
| { |
| V(semafor bufera); |
| prodolzhit'; /* vyhod v cikl "vypolnyat'" |
| */ |
| } |
| v protivnom sluchae esli (nomer ustrojstva ili |
| nomer bloka izmenilis') |
| { |
| V(semafor bufera); |
| V(semafor hesh-ocheredi); |
| } |
| } |
| vypolnyat' (poka operaciya CP(semafor spiska svobod-|
| nyh buferov) ne zavershitsya uspeshno) |
| ; /* "kol'cevoj cikl" */ |
| pometit' bufer zanyatym; |
| ubrat' bufer iz spiska svobodnyh buferov; |
| V(semafor spiska svobodnyh buferov); |
| V(semafor hesh-ocheredi); |
| vernut' bufer; |
| } |
| v protivnom sluchae /* bufer otsutstvuet v hesh- |
| * ocheredi |
| */ |
| /* zdes' nachinaetsya vypolnenie ostavshejsya chasti algo-|
| * ritma |
| */ |
| } |
| } |
+------------------------------------------------------------+
Risunok 12.14. Vydelenie bufera s ispol'zovaniem semaforov
376
tom, chto zahvachen korrektnyj bufer, poskol'ku soderzhimoe bufera moglo byt'
ranee izmeneno drugim processom, obnaruzhivshim bufer v spiske svobodnyh bufe-
rov i zahvativshim na vremya ego semafor. Process A, ozhidaya osvobozhdeniya sema-
fora, ne imeet ni malejshego predstavleniya o tom, yavlyaetsya li interesuyushchij
ego bufer tem buferom, kotoryj emu nuzhen, i poetomu prezhde vsego on dolzhen
ubedit'sya v pravil'nosti soderzhimogo bufera; esli proverka daet otricatel'-
nyj rezul'tat, algoritm zapuskaetsya snachala. Esli soderzhimoe bufera korrekt-
no, process A zavershaet vypolnenie algoritma.
+------------------------------------------------------------+
| mnogoprocessornaya versiya algoritma wait |
| { |
| dlya (;;) /* cikl */ |
| { |
| perebor vseh processov-potomkov: |
| esli (potomok nahoditsya v sostoyanii "prekrashcheniya |
| sushchestvovaniya") |
| vernut' upravlenie; |
| P(zombie_semaphore); /* nachal'noe znachenie - 0 */|
| } |
| } |
+------------------------------------------------------------+
Risunok 12.15. Mnogoprocessornaya versiya algoritma wait
Ostavshuyusya chast' algoritma mozhno rassmotret' v kachestve uprazhneniya.
Iz glavy 7 my uzhe znaem o tom, chto vo vremya vypolneniya sistemnoj funkcii
wait process priostanavlivaet svoyu rabotu do momenta zaversheniya vypolneniya
svoego potomka. V mnogoprocessornoj sisteme pered processom vstaet zadacha ne
upustit' pri vypolnenii algoritma wait potomka, prekrativshego sushchestvovanie
s pomoshch'yu funkcii exit; esli, naprimer, v to vremya, poka na odnom processore
process-roditel' zapuskaet funkciyu wait, na drugom processore ego potomok
zavershil svoyu rabotu, roditelyu net neobhodimosti priostanavlivat' svoe vy-
polnenie v ozhidanii zaversheniya vtorogo potomka. V kazhdoj zapisi tablicy pro-
cessov imeetsya semafor, imenuemyj zombie_semaphore i imeyushchij v nachale nule-
voe znachenie. |tot semafor ispol'zuetsya pri organizacii vzaimodejstviya
wait/exit (Risunok 12.15). Kogda potomok zavershaet rabotu, on vypolnyaet nad
semaforom svoego roditelya operaciyu V, vyvodya roditelya iz sostoyaniya priosta-
nova, esli tot pereshel v nego vo vremya ispolneniya funkcii wait. Esli potomok
zavershilsya ran'she, chem roditel' zapustil funkciyu wait, etot fakt budet obna-
ruzhen roditelem, kotoryj tut zhe vyjdet iz sostoyaniya ozhidaniya. Esli oba pro-
cessa ispolnyayut funkcii exit i wait parallel'no, no potomok ispolnyaet funk-
ciyu exit uzhe posle togo, kak roditel' proveril ego status, operaciya V, vy-
polnennaya potomkom, vosprepyatstvuet perehodu roditelya v sostoyanie priostano-
va. V hudshem sluchae process-roditel' prosto povtoryaet cikl lishnij raz.
V mnogoprocessornoj realizacii vychislitel'noj sistemy na baze komp'yute-
rov AT&T 3B20 semafory v strukturu zagruzochnogo koda drajverov ne vklyuchayut-
sya, a operacii tipa P i V vypolnyayutsya v tochkah vhoda v kazhdyj drajver (sm.
[Bach 84]). V glave 10 my govorili o tom, chto interfejs, realizuemyj drajve-
rami ustrojstv, harakterizuetsya ochen' nebol'shim chislom tochek vhoda (na prak-
377
tike ih okolo 20). Zashchita drajverov osushchestvlyaetsya na urovne tochek vhoda v
nih:
P(semafor drajvera);
otkryt' (drajver);
V(semafor drajvera);
Esli dlya vseh tochek vhoda v drajver ispol'zovat' odin i tot zhe semafor,
no pri etom dlya raznyh drajverov - raznye semafory, kriticheskij uchastok
programmy drajvera budet ispolnyat'sya processom monopol'no. Semafory mogut
naznachat'sya kak otdel'nomu ustrojstvu, tak i klassam ustrojstv. Tak, napri-
mer, otdel'nyj semafor mozhet byt' svyazan i s otdel'nym fizicheskim terminalom
i so vsemi terminalami srazu. V pervom sluchae bystrodejstvie sistemy vyshe,
ibo processy, obrashchayushchiesya k terminalu, ne zahvatyvayut semafor, imeyushchij ot-
noshenie k drugim terminalam, kak vo vtorom sluchae. Drajvery nekotoryh ust-
rojstv, odnako, podderzhivayut vnutrennyuyu svyaz' s drugimi drajverami; v takih
sluchayah ispol'zovanie odnogo semafora dlya klassa ustrojstv oblegchaet ponima-
nie zadachi. V kachestve al'ternativy v vychislitel'noj sisteme 3B20A predos-
tavlena vozmozhnost' takogo konfigurirovaniya otdel'nyh ustrojstv, pri kotorom
programmy drajvera zapuskayutsya na tochno ukazannyh processorah.
Problemy voznikayut togda, kogda drajver preryvaet rabotu sistemy i ego
semafor zahvachen: programma obrabotki preryvanij ne mozhet byt' vyzvana, tak
kak inache voznikla by ugroza razrusheniya dannyh. S drugoj storony, yadro ne
mozhet ostavit' preryvanie neobrabotannym. Sistema 3B20A vystraivaet preryva-
niya v ochered' i zhdet momenta osvobozhdeniya semafora, kogda vyzov programmy
obrabotki preryvanij ne budet imet' opasnye posledstviya.
12.3.3.4 Fiktivnye processy
Kogda yadro vypolnyaet pereklyuchenie konteksta v odnoprocessornoj sisteme,
ono funkcioniruet v kontekste processa, ustupayushchego upravlenie (sm. glavu
6). Esli v sisteme net processov, gotovyh k zapusku, yadro perehodit v sosto-
yanie prostoya v kontekste processa, vypolnyavshegosya poslednim. Poluchiv prery-
vanie ot tajmera ili drugih periferijnyh ustrojstv, ono obrabatyvaet ego v
kontekste togo zhe processa.
V mnogoprocessornoj sisteme yadro ne mozhet prostaivat' v kontekste pro-
cessa, vypolnyavshegosya poslednim. Posmotrim, chto proizojdet posle togo, kak
process, priostanovivshij svoyu rabotu na processore A, vyjdet iz sostoyaniya
priostanova. Process v celom gotov k zapusku, no on zapuskaetsya ne srazu zhe
po vyhode iz sostoyaniya priostanova, dazhe nesmotrya na to, chto ego kontekst
uzhe nahoditsya v rasporyazhenii processora A. Esli etot process vybiraetsya dlya
zapuska processorom B, poslednij pereklyuchaetsya na ego kontekst i vozobnovlya-
et ego vypolnenie. Kogda v rezul'tate preryvaniya processor A vyjdet iz pros-
toya, on budet prodolzhat' svoyu rabotu v kontekste processa A do teh por, poka
ne proizvedet pereklyuchenie konteksta. Takim obrazom, v techenie korotkogo
promezhutka vremeni s odnim i tem zhe adresnym prostranstvom (v chastnosti, so
stekom yadra) budut vesti rabotu (i, chto ves'ma veroyatno, proizvodit' zapis')
srazu dva processora.
Reshenie etoj problemy sostoit v sozdanii nekotorogo fiktivnogo processa;
kogda processor nahoditsya v sostoyanii prostoya, yadro pereklyuchaetsya na kon-
tekst fiktivnogo processa, delaya etot kontekst tekushchim dlya bezdejstvuyushchego
processora. Kontekst fiktivnogo processa sostoit tol'ko iz steka yadra; etot
process ne yavlyaetsya vypolnimym i ne vybiraetsya dlya zapuska. Poskol'ku kazhdyj
processor prostaivaet v kontekste svoego sobstvennogo fiktivnogo processa,
navredit' drug drugu processory uzhe ne mogut.
378
Pol'zovatel'skij interfejs sistemy Tunis sovmestim s analogichnym inter-
fejsom sistemy UNIX, no yadro etoj sistemy, razrabotannoe na yazyke Concurrent
Euclid, sostoit iz processov, upravlyayushchih kazhdoj chast'yu sistemy. Problema
vzaimnogo isklyucheniya reshaetsya v sisteme Tunis dovol'no prosto, tak kak v
kazhdyj moment vremeni ispolnyaetsya ne bolee odnoj kopii upravlyaemogo yadrom
processa, krome togo, processy rabotayut tol'ko s temi strukturami dannyh,
kotorye im prinadlezhat. Sistemnye processy aktiviziruyutsya zaprosami na vvod,
zashchitu ocheredi zaprosov osushchestvlyaet procedura programmnogo monitora. |ta
procedura usilivaet vzaimnoe isklyuchenie, razreshaya dostup k svoej ispolnyaemoj
chasti v kazhdyj moment vremeni ne bolee, chem odnomu processu. Mehanizm moni-
tora otlichaetsya ot mehanizma semaforov tem, chto, vo-pervyh, blagodarya pos-
lednim usilivaetsya modul'nost' programm (operacii P i V prisutstvuyut na vho-
de v proceduru monitora i na vyhode iz nee), a vo-vtoryh, sgenerirovannyj
kompilyatorom kod uzhe soderzhit elementy sinhronizacii. Holt otmechaet, chto
razrabotka takih sistem oblegchaetsya, esli ispol'zuetsya yazyk, podderzhivayushchij
monitory i vklyuchayushchij ponyatie parallelizma (sm. [Holt 83], str.190). Pri
vsem pri etom vnutrennyaya struktura sistemy Tunis otlichaetsya ot tradicionnoj
realizacii sistemy UNIX radikal'nym obrazom.
12.5 UZKIE MESTA V FUNKCIONIROVANII MNOGOPROCESSORNYH SISTEM
V dannoj glave nami byli rassmotreny dva metoda realizacii mnogoproces-
sornyh versij sistemy UNIX: konfiguraciya, sostoyashchaya iz glavnogo i podchinen-
nogo processorov, v kotoroj tol'ko odin processor (glavnyj) funkcioniruet v
rezhime yadra, i metod, osnovannyj na ispol'zovanii semaforov i dopuskayushchij
odnovremennoe ispolnenie v rezhime yadra vseh imeyushchihsya v sisteme processov.
Oba metoda invariantny k kolichestvu processorov, odnako govorit' o tom, chto
s rostom chisla processorov obshchaya proizvoditel'nost' sistemy uvelichivaetsya s
linejnoj skorost'yu, nel'zya. Poteri proizvoditel'nosti voznikayut, vo-pervyh,
kak sledstvie konkurencii za resursy pamyati, kotoraya vyrazhaetsya v uvelichenii
prodolzhitel'nosti obrashcheniya k pamyati. Vo-vtoryh, v sheme, osnovannoj na is-
pol'zovanii semaforov, k etoj konkurencii dobavlyaetsya sopernichestvo za sema-
fory; processy zachastuyu obnaruzhivayut semafory zahvachennymi, bol'she processov
nahoditsya v ocheredi, dolgoe vremya ozhidaya polucheniya dostupa k semaforam. Per-
vaya shema, osnovannaya na ispol'zovanii glavnogo i podchinennogo processorov,
tozhe ne lishena nedostatkov: po mere uvelicheniya chisla processorov glavnyj
processor stanovitsya uzkim mestom v sisteme, poskol'ku tol'ko on odin mozhet
funkcionirovat' v rezhime yadra. Nesmotrya na to, chto bolee vnimatel'noe tehni-
cheskoe proektirovanie pozvolyaet sokratit' konkurenciyu do razumnogo minimuma
i v nekotoryh sluchayah priblizit' skorost' povysheniya proizvoditel'nosti sis-
temy pri uvelichenii chisla processorov k linejnoj (sm., naprimer, [Beck 85]),
vse postroennye s ispol'zovaniem sovremennoj tehnologii mnogoprocessornye
sistemy imeyut predel, za kotorym rasshirenie sostava processorov ne soprovozh-
daetsya uvelicheniem proizvoditel'nosti sistemy.
1. Reshite problemu funkcionirovaniya mnogoprocessornyh sistem takim obra-
zom, chtoby vse processory v sisteme mogli funkcionirovat' v rezhime yad-
ra, no ne bolee odnogo odnovremenno. Takoe reshenie budet otlichat'sya ot
pervoj iz predlozhennyh v tekste shem, gde tol'ko odin processor (glav-
nyj) prednaznachen dlya realizacii funkcij yadra. Kak dobit'sya togo, chtoby
v rezhime yadra v kazhdyj moment vremeni nahodilsya tol'ko odin processor ?
Kakuyu strategiyu obrabotki preryvanij pri etom mozhno schitat' priemlemoj?
379
2. Ispol'zuya sistemnye funkcii raboty s razdelyaemoj oblast'yu pamyati, pro-
testirujte programmu, realizuyushchuyu semafornuyu blokirovku (Risunok 12.6).
Posledovatel'nosti operacij P-V nad semaforom mogut nezavisimo odin ot
drugogo vypolnyat' neskol'ko processov. Kakim obrazom v programme sledu-
et realizovat' indikaciyu i obrabotku oshibok ?
3. Razrabotajte algoritm vypolneniya operacii CP (uslovnyj tip operacii P),
ispol'zuya tekst algoritma operacii P.
4. Ob®yasnite, zachem v algoritmah operacij P i V (Risunki 12.8 i 12.9) nuzh-
na blokirovka preryvanij. V kakie momenty ee sleduet osushchestvlyat' ?
5. Pochemu pri vypolnenii "ciklicheskoj blokirovki" vmesto stroki:
while (! CP(semafor));
yadro ne mozhet ispol'zovat' operaciyu P bezuslovnogo tipa ? (V kachestve
navodyashchego voprosa: chto proizojdet v tom sluchae, esli process zapustit
operaciyu P i priostanovitsya ?)
6. Obratimsya k algoritmu getblk, privedennomu v glave 3. Opishite realiza-
ciyu algoritma v mnogoprocessornoj sisteme dlya sluchaya, kogda blok otsut-
stvuet v bufernom keshe.
*7. Predpolozhim, chto pri vypolnenii algoritma vydeleniya bufera voznikla
chrezvychajno sil'naya konkurenciya za semafor, prinadlezhashchij spisku svo-
bodnyh buferov. Razrabotajte shemu oslableniya konkurencii za schet raz-
bieniya spiska svobodnyh buferov na dva podspiska.
*8. Predpolozhim, chto u terminal'nogo drajvera imeetsya semafor, znachenie ko-
torogo pri inicializacii sbrasyvaetsya v 0 i po kotoromu processy prios-
tanavlivayut svoyu rabotu v sluchae perepolneniya bufera vyvoda na termi-
nal. Kogda terminal gotov k priemu sleduyushchej porcii dannyh, on vyvodit
iz sostoyaniya ozhidaniya vse processy, priostanovlennye po semaforu. Raz-
rabotajte shemu vozobnovleniya processov, ispol'zuyushchuyu operacii tipa P i
V. V sluchae neobhodimosti vvedite dopolnitel'nye flagi i semafory. Kak
dolzhna vesti sebya shema v tom sluchae, esli processy vyvodyatsya iz sosto-
yaniya ozhidaniya po preryvaniyu, no pri etom tekushchij processor ne imeet
vozmozhnosti blokirovat' preryvaniya na drugih processorah ?
*9. Esli tochki vhoda v drajver zashchishchayutsya semaforami, dolzhno soblyudat'sya
uslovie osvobozhdeniya semafora v sluchae perehoda processa v sostoyanie
priostanova. Kak eto realizuetsya na praktike ? Kakim obrazom dolzhna
proizvodit'sya obrabotka preryvanij, postupayushchih v to vremya, poka sema-
for drajvera zablokirovan ?
10. Obratimsya k sistemnym funkciyam ustanovki i kontrolya sistemnogo vremeni
(glava 8). Raznye processory mogut imet' razlichnuyu taktovuyu chastotu.
Kak v etom sluchae ukazannye funkcii dolzhny rabotat' ?
380
Last-modified: Thu, 12 Feb 1998 07:20:44 GMT