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. 12.3 SEMAFORY 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) ? - | -