Synchronizace procesů

Synchronizace procesu˚ ´ s Vojnar Tomaˇ

[email protected]

Vysoke´ uˇcen´ı technicke´ v Brneˇ Fakulta informaˇcn´ıch technologi´ı ˇ Boˇzetechova 2, 612 66 BRNO 11. dubna 2011

´ Operaˇcn´ı systemy

Synchronizace procesu˚

ˇ ˇ – Soucasn y´ pˇr´ıstup nekolika paraleln´ıch procesu˚ ke sd´ılenym ´ zdrojum ˚ (sd´ılena´ data, sd´ılena´ I/O ´ k nekonzistenc´ım zpracovavan´ ´ zaˇr´ızen´ı) muˇ ych dat. ˚ ze vest

ˇ ´ – Casov eˇ zavisl a´ chyba (neboli race condition): chyba vznikaj´ıc´ı pˇri pˇr´ıstupu ke sd´ıleným zdrojum ˚ ´ ´ en´ ˇ ı jednotlivých paraleln´ıch výpoˇctu˚ v systemu, ´ kvuli poˇrad´ı provad tj. kvuli ˚ ruzn ˚ emu ˚ jejich ruzn ˚ e´ relativn´ı rychlosti.

ˇ ı konzistence dat vyˇzaduje mechanismy synchronizace procesu˚ zajiˇst’uj´ıc´ı spravn ´ e´ poˇrad´ı – Zajiˇsten´ ´ en´ ˇ ı spolupracuj´ıc´ıch procesu. provad ˚


Synchronizace 1

ˇ ˇ ´ bufferu (napˇr. – Pˇr´ıklad: Mejme promennou N, ktera´ obsahuje poˇcet poloˇzek ve sd´ılenem ´ uvaˇzujme proveden´ı nasleduj´ ıc´ıch operac´ı:

konzument: N--

||

producent: N++

´ ı kontextu muˇ ´ – Na strojove´ urovni a pˇri pˇrep´ınan´ ıc´ımu: ´ ˚ ze doj´ıt k nasleduj´

producent: producent: konzument: konzument: producent: konzument:

N==5) a

race condition - chyba záleží na pořadí prováděn příkazů

register1 = N (register1 == 5) register1 = register1 + 1 (register1 == 6) register2 = N (register2 == 5) register2 = register2 - 1 (register2 == 4) N = register1 (N == 6) N = register2 (N == 4 !!!!!)

´ e´ hodnoty 5! – Výsledkem muˇ ˚ ze být 4, 5, nebo 6 nam´ısto jedine´ spravn


Synchronizace 2

Kriticke´ sekce ´ ˇ z´ıc´ıch o pˇr´ıstup ke sd´ıleným zdrojum. – Mame n procesu˚ souteˇ Kaˇzdý proces je ˇr´ızen urˇcitým programem. ˚

na p. dv a pr oc es y m an ip ul ují sx zá ro ve

– Sd´ılenymi ´ kritickymi ´ sekcemi daných procesu˚ rozum´ıme ty useky jejich ˇr´ıd´ıc´ıch programu˚ ´ ´ en´ ˇ ı jedn´ım procesem vyluˇcuje souˇcasne´ provad ´ en´ ˇ ı pˇristupuj´ıc´ı ke sd´ıleným zdrojum, jejichˇz provad ˚ ´ ˇ libovolneho z techto usek u˚ ostatn´ımi procesy. ´ ´ ´ – Je moˇzný výskyt v´ıce sad sd´ılených kritických sekc´ı, ktere´ navzajem sd´ılene´ nejsou (napˇr. pˇri praci ˇ ymi). s ruzn´ ˚ ymi sd´ılenými promenn´ ˇ s´ım pˇr´ıpadem pak je situace, kdy sd´ılene´ kriticke´ sekce nejsou vzajemn ´ – Obecnejˇ eˇ zcela vylouˇceny, ´ et ˇ nejvýsˇ e urˇcitý poˇcet. ale muˇ ˚ ze se jich souˇcasneˇ provad ´ kriticke´ sekce – pro sd´ılene´ kriticke´ sekce je zapotˇreb´ı zajistit: – Problem ´ ´ e´ vylouˇcen´ı (mutual exclusion): nanejvýsˇ jeden (obecneˇ k) proces(u) • Vzajemn ˚ je v danem okamˇziku v KS.

• Dostupnost KS: ´ proces nemuˇ – Je-li KS volna, ˚ ze neomezeneˇ cˇ ekat na pˇr´ıstup do n´ı. – Je zapotˇreb´ı se vyhnout: ´ ∗ uvaznut´ ı, ´ ıa ∗ blokovan´ ´ ∗ starnut´ ı. ´ Operaˇcn´ı systemy

Synchronizace 3

´ ´ ı, starnut´ ´ Uvaznut´ ı, blokovan´ ı

proces 1 vlastní zdroj A, eká na zdroj B, proces 2 vlastní zdroj B, eká na zdroj A, zacyklení , nedokají se

´ – Uvaznut´ ım (deadlockem) pˇri pˇr´ıstupu ke sd´ıleným zdrojum ˚ rozum´ıme situaci, kdy kaˇzdý ze skupiny ˇ ı zdroje s výluˇcným (omezeným) pˇr´ıstupem vlastnen´ ˇ ym procesu˚ je pozastaven a cˇ eka´ na uvolnen´ ˇ ym procesem z dane´ skupiny. [[ Obecnejˇ ˇ s´ı pojet´ı uvaznut´ ´ ´ ]] nejak´ ı – viz dale. ´ a´ ´ ım (blocking) pˇri pˇr´ıstupu do kriticke´ sekce rozum´ıme situaci, kdy proces, jenˇz zˇ ad – Blokovan´ ´ y proces se nenachaz´ ´ ı o vstup do kriticke´ sekce, mus´ı cˇ ekat, pˇrestoˇze je kriticka´ sekce volna´ (tj. zˇ adn´ ´ e´ sd´ılene´ kriticke´ sekci) a ani o zˇ adnou ´ v n´ı ani v zˇ adn z dane´ mnoˇziny sd´ılených kritických sekc´ı ´ y dalˇs´ı proces neˇzad ´ a. ´ zˇ adn´ ´ z hladoven´ ˇ ım, starvation) – rozum´ıme situaci, kdy proces cˇ eka´ na podm´ınku, ktera´ ´ – Starnut´ ım (teˇ ˇ ı vstupu do kriticke´ sekce. nemus´ı nastat. V pˇr´ıpadeˇ kriticke´ sekce je touto podm´ınkou umoˇznen´ ´ ´ ı zvlaˇ ´ stn´ımi pˇr´ıpady starnut´ ´ – Pˇri striktn´ı interprepatci jsou uvaznut´ ı i blokovan´ ı.

´ ˇ z´ı, ale ´ stn´ım pˇr´ıpadem starnut´ ı je take´ tzv. livelock, kdy vˇsechny procesy z urˇcite´ mnoˇziny beˇ – Zvlaˇ ´ ej´ ˇ ı jen omezený usek ´ ´ opakovaneˇ zˇ adaj´ ´ ı o urˇcitý sd´ılený zdroj, který vlastn´ı provad kodu, ve kterem ´ ˇ ´ eˇ zˇ ad ´ a. ´ nekter´ y z procesu˚ dane´ skupiny, pˇriˇcemˇz ten ho nemuˇ ˚ ze uvolnit, aniˇz by z´ıskal zdroj, o který aktualn ˇ – data race: dva pˇr´ıstupy k teˇ ´ ze promenn ˇ e´ ze dvou procesu˚ bez synchronizace, alesponˇ [[ Doplnek ´ ´ stn´ı pˇr´ıpad chybej´ ˇ ıc´ıho vzajemn ´ ´ jeden pˇr´ıstup je pˇritom pro zapis (zvlaˇ eho vylouˇcen´ı). ]]


Synchronizace 4

Petersonuv ˚ algoritmus

´ – Moˇzne´ ˇreˇsen´ı problemu KS pro dva procesy:

bool flag[2] = { false, false }; int turn = 0;

// shared array // shared variable

// process i (i==0 or i==1): do { //... flag[i] = true; turn = 1-i;

přihlásím svůj zájem o KS a nastavím druhému procesu prioritu pro vstup do KS

while (flag[1-i] && turn != i) ; // critical section flag[i] = false; // remainder section } while (1);

// busy waiting

ˇ ı Petersonova algoritmu pro n procesu˚ a dalˇs´ı algoritmy. – Existuje zobecnen´ ´ Operaˇcn´ı systemy

Synchronizace 5

Bakery algoritmus L. Lamporta ´ – Vzajemn e´ vylouˇcen´ı pro n procesu: ˚ ˇ s´ı neˇz cˇ ´ısla pˇridelen ˇ a´ jiˇz • Pˇred vstupem do KS proces z´ıska´ “l´ıstek”, jehoˇz cˇ ´ıselna´ hodnota je vetˇ cˇ ekaj´ıc´ım procesum. ˚

• Drˇzitel nejmenˇs´ıho cˇ ´ısla a s nejmenˇs´ım PID muˇ ˚ ze vstoupit do KS (v´ıce procesu˚ muˇ ˚ ze l´ıstek z´ıskat ˇ souˇcasne!). ˇ ısla pˇridelovan ˇ • C´ a´ procesum ˚ mohou teoreticky neomezeneˇ rust. ˚ pí zn ak to ho , že pr oc es zí sk áv á lís te k

bool flag[N] = {false}; // shared array int ticket[N] = { 0 }; // shared array int j, max=0; // local (non-shared) variables

ho dn ot a pí st up ov éh o lís tk u, 0 = ne m á zá je m


projde všechny lístky a spoítá maximální hodnotu, kterou použije pro svj lístek

// process i while (1) { // ... before the critical section flag[i] = true; // finding the max ticket for (j = 0; j < N; j++) { if (ticket[j] > max) max = ticket[j]; } ticket[i] = max + 1; // take a new ticket

Synchronizace 6

ˇ an´ ´ ı Bakery algoritmus – pokracov

ko ne c ge ne rov ání sv éh o pís tup ov éh o líst ku

flag[i] = false; // give priority to processes with smaller tickets // (or equal tickets and smaller PID) for (j = 0; j < N; j++) { while (flag[j]); if (ticket[j] > 0 && (ticket[j] < ticket[i] || (ticket[j] == ticket[i] && j 0); } } // the critical section ticket[i] = 0; // the remainder section

proces i iteruje pes procesy, pokud si proces poítá lístek, eká, pokud má proces zájem o KS, zjistí hodnotu jeho lístku, pokud má stejnou hodnotu, oví jeho PID, až proces projde pes všechny ostatní, má jistotu, že je na ad

} – Pozor na moˇznost pˇreteˇcen´ı u cˇ ´ısel l´ıstku! ˚


Synchronizace 7

Vyuˇzit´ı hardware pro synchronizaci ˇ neˇz specializovane´ algoritmy bez HW podpory. – Pouˇz´ıva´ se cˇ asteji

– Atomicka´ instrukce typu TestAndSet (napˇr.

LOCK BTS):

bool TestAndSet(bool &target) { bool rv = target; zamkne KS a vrátí původní stav KS target = true; return rv; } – Vyuˇzit´ı TestAndSet pro synchronizaci na KS:

bool lock = false; // ... while (TestAndSet(lock)) ; // critical section lock = false; // ...


Synchronizace 8

– Atomicka´ instrukce typu Swap (napˇr.

LOCK XCHG):

void Swap(bool &a, bool &b) { bool temp = a; zamění obsah dvou míst v paměti a = b; b = temp; } – Vyuˇzit´ı Swap pro synchronizaci na KS:

// ... bool key = true; while (key == true) Swap(lock,key); // critical section lock = false; // ...


sdí len á pro mn ná

bool lock = false;

dokud bude KS zamčená, key bude true (záměna true za true), proces tedy bude čekat na odemčení

Synchronizace 9

´ ´ – Uvedena´ ˇreˇsen´ı vzajemn eho vylouˇcen´ı zaloˇzena´ na specializovaných instrukc´ıch zahrnuj´ı moˇznost ˇ an´ ´ ı, proto se take´ tato ˇreˇsen´ı cˇ asto oznaˇcuj´ı jako tzv. spinlock. aktivn´ıho cek while(...)

aby nemohlo dojít k přepnutí kontextu

´ ych, – Lze uˇz´ıt na kratk ´ neblokuj´ıc´ıch kritickych ´ sekc´ıch bez preempce (alesponˇ bez preempce na ´ procesoru: proto býva´ vlastn´ı pouˇzit´ı atomicke´ instrukce uzavˇreno mezi zakaz/povolen´ ´ pouˇzitem ı pˇreruˇsen´ı). ´ ˇ ’oveho ´ ˇ ı konzistence cache – Opakovaný zapis pamet m´ısta je problematický z hlediska zajiˇsten´ ´ ˇ zuje sd´ılenou pamet ˇ ’ovou sbernici) ˇ v multiprocesorových systemech (zateˇ – ˇreˇsen´ım je pˇri aktivn´ım ˇ an´ ´ ı pouze c´ ˇ ıst: cek

// ... while (TestAndSet(lock)) while (lock) ; // ... ´ ˇ ı moˇznost starnut´ ´ – Uvedena´ ˇreˇsen´ı nevylucuj´ ı: býva´ tolerovano, ale existuj´ı ˇreˇsen´ı s frontou ´ odstranuj´ ˇ ı. cˇ ekaj´ıc´ıch procesu, ˚ ktere´ tento problem


Synchronizace 10

Semafory ´ ´ ı. – Synchronizaˇcn´ı nastroj nevyˇzaduj´ıc´ı aktivn´ı cˇ ekan´ ˇ ˇ zakladn´ ´ – Jedna´ se typicky o celoˇc´ıselnou promennou pˇr´ıstupnou dvemi ımi atomickými operacemi:

• lock (take´ P cˇ i down), • unlock (take´ V cˇ i up) ´ muˇ ˇ ych operac´ı, napˇr. (dale ˚ ze být k dispozici napˇr. inicializace apod., pˇr´ıpadneˇ ruzn ˚ e´ varianty zm´ınen´ ´ ı atp.). neblokuj´ıc´ı zamknut´ı, pokus o zamknut´ı s horn´ı mez´ı na dobu cˇ ekan´

´ ˇ e´ S odpov´ıdaj´ıc´ı semaforu: celoˇc´ıselne´ promenn – Semantika ˇ ych semaforu, • S > 0 – odemknuto (hodnota S > 1 se uˇz´ıva´ u zobecnen´ ˚ jeˇz mohou propustit do kriticke´ sekce v´ıce neˇz jeden proces), ´ a´ poˇcet procesu˚ cˇ ekaj´ıc´ıch na semaforu). • S ≤ 0 – uzamknuto (je-li S < 0, hodnota |S| udav ˇ ´ – Nekdy se zaporn e´ hodnoty neuˇz´ıvaj´ı a semafor se zastav´ı na nule.


Synchronizace 11

– Vyuˇzit´ı semaforu˚ pro synchronizaci na KS:

semaphore mutex; // shared semaphore init(mutex,1); // initially mutex = 1 // ... lock(mutex); // critical section unlock(mutex); // ...

´ ı implementace semaforu: – Konceptualn´

typedef struct { int value; process_queue *queue; } semaphore;


Synchronizace 12

lock(S) { S.value--; if (S.value < 0) { zjistí výslednou hodnotu semaforu, pokud je kladná, může proces vstoupit do KS // remove the process calling lock(S) from the ready queue C = get(ready_queue); // add the process calling lock(S) to S.queue append(S.queue, C); // switch context, the current process has to wait to get // back to the ready queue je hodnota záporná, proces přidá sám sebe do čekací fronty a přepne kontext (proces je switch(); pokud pozastaven, spustí se jiný proces } } unlock(S) { S.value++; if (S.value <= 0) { pokud je hodnota záporná, někdo čeká // get and remove the first waiting process from S.queue P = get(S.queue); vybere první proces z čekací fronty a zařadí ho do fronty procesů připravených běžet // enable further execution of P by adding it into // the ready queue append(ready_queue, P); } } ´ Operaˇcn´ı systemy

Synchronizace 13

´ en´ ˇ ı lock a unlock mus´ı být atomicke. ´ Jejich telo ˇ pˇredstavuje rovneˇ ˇ z kritickou sekci!!! – Provad ˇ sen´ı atomicity lock a unlock: – Reˇ ´ • zakaz pˇreruˇsen´ı, ´ ´ ım (spinlock) • vzajemn e´ vylouˇcen´ı s vyuˇzit´ım atomických instrukc´ı a aktivn´ım cˇ ekan´ ´ u; – pouˇz´ıva´ se u multiprocesorových system ˚ ´ ı pouze na vstup do lock/unlock, ne na dokonˇcen´ı dlouhe´ uˇzivatelske´ KS. – cˇ ekan´

´ – Pouˇz´ıvaj´ı se take: ´ ´ ˇ • read-write zamky – pro cˇ ten´ı lze zamknout v´ıcenasobn e, ´ ´ ˇ • reentrantn´ı zamky – proces muˇ zamknout opakovane, ˚ ze stejný zamek ´ ı semafory, ktere´ mohou být odemknuty pouze temi ˇ procesy, ktere´ ja zamkly • mutexy – binarn´ ˇ (umoˇznuje optimalizovanou implementaci).


Synchronizace 14

´ ı: – POSIX: Semafory dostupne´ prostˇrednictv´ım volan´

semget - získání semaforu (vytvoření množiny semaforů, zpřístupnění) semop - operace nad semafory semctl - inicializace, zrušení

semget, semop, semctl, ˇ s´ı (viz man sem_overview): sem_open, sem_init, sem_post, novejˇ sem_wait, sem_getvalue, sem_close, sem_unlink, sem_destroy, ´ pthread_mutex_lock, pthread_mutex_unlock, ... POSIXova´ vlakna:

• starˇs´ı rozhran´ı (System V): • •

– Linux: futexes – fast user-space locks: ˇ zna´ celoˇc´ıselna´ promenn ˇ a´ ve sd´ılene´ pameti ˇ s atomickou • pouˇz´ıva´ se beˇ ´ reˇzimu na urovni inkrementac´ı/dekrementac´ı v uˇzivatelskem assembleru, ´ ´ • pˇri detekci konfliktu se vola´ pro ˇreˇsen´ı konfliktu jadro – sluˇzba

futex (hlavn´ı operace

FUTEX WAIT a FUTEX WAKE), ´ poˇctu konfliktu˚ se zcela obejde reˇzie spojena´ s volan´ ´ ım • rychlost vyplýva´ z toho, zˇ e pˇri malem ´ sluˇzeb jadra.


Synchronizace 15

Monitory ˇ ych synchronizaˇcn´ıch prostˇredku. – Jeden z vysokourov ´ nov´ ˚ Zapouzdˇruje data, ma´ definovane´ ´ et ˇ nejakou ˇ ´ en´ ˇ ymi daty: operace, jen jeden proces muˇ operaci nad chran ˚ ze provad

monitor monitor-name { shared variable declarations

s daty se neoperuje přímo, ale prostřednictvím monitoru, který automaticky zajišťuje, že na ním v dané chvíli pracuje pouze jeden proces

procedure body P1 (...) { ... } procedure body P2 (...) { ... } { initialization code } }


Synchronizace 16

´ ı uvnitˇr monitoru jsou k dispozici tzv. podm´ınky (conditions), nad kterými je – Pro moˇznost cˇ ekan´ předá monitor jinému procesu ´ et ˇ operace: moˇzne´ provad

• wait() a ´ neˇceka-li ´ nikdo, jedna´ se • signal(), resp. notify() – pokraˇcuje pˇr´ıjemce/odes´ılatel signalu; ´ o prazdnou operaci.

– Implementace moˇzna´ pomoc´ı semaforu. ˚ – Monitory jsou v urˇcite´ podobeˇ pouˇzity v Javeˇ (viz kl´ıcˇ ove´ slovo synchronized). Pro POSIXova´ ´ vlakna jsou k dispozici podm´ınky pthread cond t a souvisej´ıc´ı funkce pthread cond wait/ signal/ broadcast. ´ Operaˇcn´ı systemy

Synchronizace 17

ˇ ˇ ı problemy ´ Nekter e´ klasicke´ synchronizacn´

´ ˇ ’ s kapacitou omezenou na N – Komunikace producenta a konzumenta pˇres vyrovnavac´ ı pamet poloˇzek: – Synchronizaˇcn´ı prostˇredky:

semaphore full, empty, mutex; // Initialization: init(full,0); init(empty,N); init(mutex,1);


full - počet položek v bufferu empty - počet volných míst v bufferu mutex - přístup do KS

Synchronizace 18

– Producent:

do { ... // produce an item I ... lock(empty); je k dispozici volné místo? lock(mutex); ... // add I to buffer zápis do KS ... unlock(mutex); unlock(full); oznámí konzumentovi, že zapsal do bufferu } while (1);


– Konzument:

do { lock(full) nachází se něco v bufferu? lock(mutex); ... // remove I from buffer ... čtení z KS unlock(mutex); unlock(empty); v bufferu je volné místo, producent může zapsat ... // consume I ... } while (1);

Synchronizace 19

´ cten ´ ru˚ muˇ ˇ ˇ ´ ru˚ a p´ısaˇru: – Problem aˇ ˚ libovolný poˇcet cˇ tenaˇ p´ısˇ e, nikdo dalˇs´ı ˚ ze cˇ ´ıst; pokud ale nekdo ´ ani cˇ ´ıst. nesm´ı psat

– Synchronizaˇcn´ı prostˇredky:

int readcount; semaphore mutex, wrt;

readcount - počet čtenářů mutex - přístup k readcount wrt - vyloučení písařů navzájem, vyloučení čtenářů a písařů

// Initialization: readcount=0; init(mutex,1); init(wrt,1);


Synchronizace 20

ˇ ´ r: aˇ – Cten

– P´ısaˇr:

do { ... lock(wrt); vyloučení ostatních ... // writing is performed ... unlock(wrt); pustí ostatní ... } while (1);

ˇ ı” p´ısaˇru: – Hroz´ı “vyhladoven´ ˚ pˇridat dalˇs´ı semafor.


do { lock(mutex); readcount++; if (readcount == 1) lock(wrt); první čtenář zamyká před písaři unlock(mutex); ... // reading is performed ... lock(mutex); readcount--; if (readcount == 0) unlock(wrt); poslední čtenář odemkne unlock(mutex); písařům ... } while (1); pokud bude v KS vždy aspoň jeden čtenář, písař se nedostane na řadu přidáme semafor, který signalizuje, že písař čeká, čtenář se úplně na začátku pokusí zamknout zájem písaře, pokud se mu to nepovede, znamená to, že před ním již čeká písař a musí proto čekat. v případě, že se zámek povede, zase jej odemkne. písař Synchronizace 21 zámek odemyká po vstupu do KS

´ veceˇ ˇ r´ıc´ıch filozofu: – Problem ˚


Synchronizace 22

ˇ sen´ı (s moˇznost´ı uvaznut´ ´ – Reˇ ı):

semaphore chopstick[5]; // Initialization: for (int i=0; i<5; i++) init(chopstick[i],1); // Philospher i: do { lock(chopstick[i]) zamkne obě své hůlky lock(chopstick[(i+1) % 5]) ... // eat ... unlock(chopstick[i]); obě hůlky uvolní unlock(chopstick[(i+1) % 5]); ... uváznutí - každý filozof zaráz uchopí levou hůlku a bude se dožadovat pravé hůlky // think řešení: - např. semafory SYSV (umožňuje zamknout dva semafory zaráz) ... - jeden proces bude asymetrický, například první proces bude zamykat nejdříve } while (1); pravou hůlku ´ ˇ z´ıskavat ´ – Lepˇs´ı ˇreˇsen´ı: z´ıskavat obeˇ hulky souˇcasne, hulky asymetricky, ... ˚ ˚ ´ Operaˇcn´ı systemy

Synchronizace 23

´ ı synchronizacn´ ˇ ıch problem ´ u˚ Modelovan´ ´ u˚ je moˇzne´ pouˇz´ıt napˇr. Petriho s´ıteˇ (a ˇradu dalˇs´ıch – K popisu a analýze synchronizaˇcn´ıch problem formalismu). ˚ – P/T Petriho s´ıt’ ma´ charakter bipartitn´ıho grafu: dva typy uzlu˚ (m´ısta a pˇrechody), hrany propojuj´ı ruzn ˚ e´ typy uzlu˚ (nelze propojit m´ısto s m´ıstem): ˇ ych. M´ısta – reprezentuj´ı moˇzne´ stavy procesu˚ a promenn´ Pˇrechody – reprezentuj´ı moˇzne´ akce. ˇ ych. Znaˇcen´ı s´ıteˇ (teˇcky v m´ıstech) – stavy procesu˚ a promenn´ Proveden´ı pˇrechodu (pˇresuv znaˇcek ze vˇsech vstupn´ıch do vˇsech výstupn´ıch m´ıst) – reprezentuje ˇ e´ akce. je proveditelný, pokud má v každém vsutpním místě alespoň jednu značku proveden´ı nejak


Synchronizace 24

´ ´ – Pˇr´ıklad: model vzajemn eho vylouˇcen´ı na kriticke´ sekci

P(mutex)

mutex

critical section V(mutex)


Synchronizace 25

´ Uvaznut´ ı (deadlock) ´ – Uvaznut´ ım (deadlockem) pˇri pˇr´ıstupu ke sd´ılenym ´ zdrojum ˚ rozum´ıme situaci, kdy kaˇzdý ze ˇ ı zdroje s výluˇcným (omezeným) pˇr´ıstupem skupiny procesu˚ je pozastaven a cˇ eka´ na uvolnen´ ˇ ym nejak´ ˇ ym procesem z dane´ skupiny. vlastnen´ P1

P2

dva sdílené zdroje (např. paměť a I/O), první proces zamyká nejprve paměť, poté I/O, druhý proces zamyká I/O a pak paměť. může nastat situace, že první proces zamkne paměť, druhý zároveň zamkne I/O a oba čekají na odemknutí druhého zdroje - uváznutí

a

b

c

d

ˇ s´ı definice, ktera´ poˇc´ıta´ i s moˇznost´ı uvaznut´ ´ ´ ı – Obecnejˇ ı bez sd´ılených postˇredku˚ (napˇr. pˇri zas´ılan´ ´ ´ ´ zprav): Uvaznut´ ım rozum´ıme situaci, kdy kaˇzdý ze skupiny procesu˚ je pozastaven a cˇ eka´ na udalost, ˇ ktera´ by ovˇsem mohla nastat pouze, pokud by mohl pokraˇcovat nekter´ y z procesu˚ z dane´ mnoˇziny. ´ Operaˇcn´ı systemy

Synchronizace 26

ˇ ıc´ı podm´ınky uvaznut´ ´ – Nutne´ a postacuj´ ı pˇri pˇr´ıstupu ke sd´ılenym ´ zdrojum ˚ (Coffmanovy podm´ınky): (co se musí stát, aby vzniklo uváznutí) ´ ´ ı prostˇredku, 1. vzajemn e´ vylouˇcen´ı pˇri pouˇz´ıvan´ ˚ ´ ı na dalˇs´ı, 2. vlastnictv´ı alesponˇ jednoho zdroje, pozastaven´ı a cˇ ekan´ 3. prostˇredky vrac´ı proces, který je vlastn´ı, a to po dokonˇcen´ı jejich vyuˇzit´ı,

prostředky nemohou být odebrány

´ 4. cyklicka´ zavislost na sebe cˇ ekaj´ıc´ıch procesu. ˚ ´ ı cyklen´ım v cˇ ekac´ı smyˇcce.) (Pozor: Nesouvis´ı nijak s pojmem aktivn´ıho cˇ ekan´

ˇ sen´ ˇ ı: – Re ´ • prevence uvaznut´ ı, ´ ı se uvaznut´ ´ • vyhýban´ ı,

• detekce a zotaven´ı, ˇ ren´ı, zˇ e uvaznut´ ´ • (oveˇ ı nemuˇ ˚ ze nastat).


Synchronizace 27

´ Prevence uvaznut´ ı

ˇ ´ – Zruˇs´ıme platnost nekter e´ z nutných podm´ınek uvaznut´ ı: při práci s proměnnými v paměti použijeme atomické instrukce a nebude potřeba zamykání

ˇ ı (skuteˇcneˇ 1. Nepouˇz´ıvat sd´ılene´ prostˇredky nebo uˇz´ıvat sd´ılene´ prostˇredky, ktere´ umoˇznuj´ ´ souˇcasný) sd´ılený pˇr´ıstup a u kterých tedy nen´ı nutne´ vzajemn e´ vylouˇcen´ı procesu. ˚ ´ ´ e´ nevlastn´ı. 2. Proces muˇ o prostˇredky pouze pokud zˇ adn ˚ ze zˇ adat ´ a´ o prostˇredky, ktere´ nemuˇ ´ eˇ z´ıskat, je pozastaven, vˇsechny 3. Pokud proces poˇzad ˚ ze momentaln ´ a cˇ eka´ se, aˇz mu mohou být vˇsechny potˇrebne´ prostˇredky pˇrideleny. ˇ prostˇredky jsou mu odebrany ´ a je moˇzne´ je z´ıskavat ´ 4. Prostˇredky jsou oˇc´ıslovany pouze od nejniˇzsˇ ´ıch cˇ ´ısel k vyˇssˇ ´ım.


Synchronizace 28

´ ı se uvaznut´ ´ Vyhyb ´ an´ ı

– Procesy pˇredem deklaruj´ı urˇcite´ informace o zpusobu, jakým budou vyuˇz´ıvat zdroje: ˚ ´ ı pocet ˇ souˇcasneˇ poˇzadovaných zdroju˚ jednotlivých v nejjednoduˇssˇ ´ım pˇr´ıpadeˇ se jedna´ o maximaln´ typu. ˚

´ e´ informace o moˇzných poˇzadavc´ıch jednotlivých procesu˚ a o aktualn´ ´ ım stavu – Pˇredem znam ˇ an´ ´ ı se vyuˇzij´ı k rozhodovan´ ´ ı o tom, ktere´ poˇzadavky mohou být uspokojeny (a ktere´ mus´ı pˇridelov ´ poˇckat) tak, aby nevznikla cyklicka´ zavislost na sebe cˇ ekaj´ıc´ıch procesu. ˚ pokud hrozí, že po přidělení zdroje určitému procesu nastane uváznutí, systém požadavek na zdroje odmítne


Synchronizace 29

´ ı se uvaznut´ ´ – Existuje ˇrada algoritmu˚ pro vyhýban´ ı: ´ ´ • napˇr. algoritmus zaloˇzený na grafu alokace zdroju˚ pro systemy s jednou instanc´ı kaˇzdeho zdroje – ´ r´ıme graf vztahu, ˇ (Ri ⇒ Pj ), kdo o který zdroj zˇ ad ´ a´ cˇ i muˇ vytvaˇ ˚ který zdroj je kým vlastnen ˚ ze ˇ ´ ´ pouze tehdy, pokud nehroz´ı vznik cyklicke´ zavislosti poˇzadat (Pi ⇒ / → R j ); zdroj je pˇridelen cˇ ekaj´ıc´ıch procesu, ˚ coˇz by se projevilo cyklem v grafu), zdroj

R1

R1

P2 může žádat o R1

P1 vlastní R1

proces

P1

P2

P1

P2

P2 žádá o R2

R2

R2

"splníme" požadavky, tedy modelujeme situaci, kdy je procesu přidělen požadovaný zdroj, pokud vzniká cyklus, nastává uváznutí - přidělení zdroje není povoleno

´ ruv ´ s v´ıce instancemi zdroju. • tzv. bankeˇ ˚ algoritmus pro praci ˚


Synchronizace 30

´ Detekce uvaznut´ ı a zotaven´ı

´ – Uvaznut´ ı muˇ ˚ ze vzniknout; periodicky se pˇritom detekuje, zda k tomu nedoˇslo, a pokud ano, provede se zotaven´ı. ´ ı pro systemy ´ ´ ´ – Detekce uvaznut´ ı: graf cˇ ekan´ s jednou instanc´ı kaˇzdeho zdroje (který proces cˇ eka´ na ˇ ı zdroje kterým procesem: cyklus implikuje deadlock), ... uvolnen´ ´ – Zotaven´ı z uvaznut´ ı: ˇ • ukonˇcen´ı vˇsech nebo nekter´ ych zablokovaných procesu, ˚ ´ ı zdroju˚ nekter´ ˇ ˇ umoˇznen´ ˇ ı pokraˇcovat (pˇr´ıpadneˇ • odebran´ ym procesum, jejich pozastaven´ı a pozdeji ˚ jejich restart).

možnost nekonzistence zdrojů

V obou pˇr´ıpadech anulace nedokonˇcených operac´ı (rollback ), nebo nutnost akceptace moˇzných nekonzistenc´ı.


Synchronizace 31

´ ˇ ı procesu˚ (starvation) Starnut´ ı/hladoven´ ˇ ı zdroju), – Procesy cˇ ekaj´ı na podm´ınku (napˇr. pˇridelen´ ˚ u n´ızˇ nen´ı zaruˇceno, zˇ e nastane (napˇr. proto, ´ pˇredb´ıhany ´ jinými procesy). zˇ e pˇr´ısluˇsne´ procesy mohou být neustale

2

a

b

2


Synchronizace 32

´ ı verifikace Formaln´ ´ ´ – Pokud nen´ı pouˇzit mechanismus prevence, obchazen´ ı cˇ i detekce a zotaven´ı se z uvaznut´ ı (ˇci jiných ´ ˇ rit, zˇ e system ´ je navrˇzen tak, zˇ e zˇ adn ´ e´ neˇzadouc´ ´ ´ ı neˇzadouc´ ıch vlastnost´ı), je vhodne´ oveˇ ı chovan´ nehroz´ı. ´ ı neˇzadouc´ ´ ´ ı system ´ u˚ (mj. uvaznut´ ´ ´ – Moˇznosti odhalovan´ ıho chovan´ ı cˇ i starnut´ ı) zahrnuj´ı: ´ ´ ´ • inspekce systemu (nejlepe nezavislou osobou), ˇ ´ ı, dynamicka´ analýza, (pˇr´ıp. i samo-oprava za behu: self-healing), • simulace, testovan´ ´ ı verifikace, • formaln´

• nebo kombinace vˇsech uvedených pˇr´ıstupu. ˚ ´ ı) umoˇznuje ˇ ´ ´ ı verifikace (na rozd´ıl od simulace a testovan´ – Formaln´ nejen vyhledavat chyby, ale take´ ´ ´ ´ ´ ´ zˇ e zˇ adn ´ e´ chyby nezustaly dokazat spravnost systemu s ohledem na zadana´ kriteria (coˇz znamena, ˚ bez povˇsimnut´ı).


Synchronizace 33

´ ı verifikace: – Proces formaln´ model systému ´ pˇr´ımo se systemem), ´ • vytvoˇren´ı modelu (lze pˇreskoˇcit pˇri praci

ˇ rit (nekter ˇ • specifikace vlastnosti, kterou chceme oveˇ e´ vlastnosti mohou být genericke´ – napˇr. absence deadlocku, null pointer exceptions apod.), ´ kontrola, zda model splnuje ˇ • (automaticka) specifikaci.

´ ´ ı verifikaci zahrnuj´ı: – Zakladn´ ı pˇr´ıstupy k formaln´

• model checking • theorem proving • static analysis


Synchronizace 34

– Theorem proving: splňuje systém danou podmínku?

• Vyuˇz´ıva´ (typicky) poloautomatický dokazovac´ı prostˇredek (PVS, Isabel,Coq,ACL/2,...). ´ • Vyˇzaduje experta, který urˇcuje, jak se ma´ dukaz vest. ˚ – Model checking: generuje a prohledává všechny možné stavy procesu

• Vyuˇz´ıva´ obvykle automatický prostˇredek (Spin, SMV, Slam/SDV, Blast, JPF, ...). ´ ´ ı a prohledav ´ an´ ´ ı stavoveho prostoru. • Vyuˇz´ıva´ typicky generovan´ ´ stavove´ exploze, kdy velikost stavoveho ´ • Hlavn´ı nevýhodou je problem prostoru roste ´ eˇ s velikost´ı modelu, pˇr´ıpadneˇ prace ´ s neomezeným poˇctem stavu. exponencialn ˚ – Static analysis: ˇ ren´ı pˇr´ısluˇsných vlastnost´ı na zaklad ´ ´ • Snaha o oveˇ eˇ popisu modelu cˇ i systemu, aniˇz by se tento ´ el ˇ a prochazel ´ ´ ı jen na urˇcite´ abstraktn´ı urovni). provad se stavový prostor (pˇr´ıpadneˇ se provad´ ´

• Ruzn ˚ e´ podoby: dataflow analysis, constraint analysis, type analysis, abstract interpretation.


Synchronizace 35

Verifikace na FIT – VeriFIT ˇ ´ ´ – Rada temat sahaj´ıc´ıch od teoretickeho vyzkumu ´ (teorie jazyku˚ a automatu˚ a jej´ı vyuˇzit´ı, Petriho ˇ ...), pˇres pokrocil ˇ e´ algoritmy a datove´ struktury potˇrebne´ pro efektivn´ı implementaci s´ıte, ´ e´ pˇr´ıpadove´ studie: verifikaˇcn´ıch metod po realn ´ ı verifikace parametrických a nekoneˇcneˇ stavových system ´ u˚ (napˇr. programy s • formaln´ dynamickými datovými strukturami: seznamy, stromy, ...) pomoc´ı automatu, ˚ logik, ... – partneˇri LIAFA (Paˇr´ızˇ ), Verimag (Grenoble), Uppsala University, ... ´ ı verifikace Java programu˚ (ve spolupraci ´ s Universitou v Milan ´ e), ˇ • formaln´ ´ ı verifikace v OS, ... • formaln´ ´ ı, dynamicka´ analýza a sebe-opravovan´ ´ ı paraleln´ıch programu˚ (Java, C) – EU projekt • testovan´ Shadows (partneˇri: IBM Haifa Research Laboratories, ...)

– Jedna z hlavn´ıch aplikac´ı v oboru Matematicke´ metody v IT na FIT. ´ ˇ ıkovou praci, ´ ´ ´ – Zajemci o moˇznou rocn´ diplomovou praci, ... jsou v´ıtani!


Synchronizace 36

Synchronizace procesů

Recommend Documents