48 - fituska - Interakce mezi procesy a typické problémy paralelismu (synchronizační a komunikační mechanismy)

Question 1

Základní pojmy

Answer 1

• Interakci můžeme rozdělit na kooperaci (je potřeba synchronizace) nebo soupeření (je potřeba vzájemné vyloučení).
  ● soupeření - soutěží o zdroje (problém vzájemného vyloučení - mutual exclusion)
  ● kooperace - každý řeší část problému

● nekonečný ​buffer - producent může pořád vyrábět, konzument musí čekat, pokud není nic k dispozici
● omezený ​buffer - oba musí někdy čekat

Kritická sekce KS je část programu, ve které dochází k přístupu ke sdíleným prostředkům, obvykle maximálně jeden proces se může v daném čase nacházet v kritické sekci, aby bylo dodrženo integrity hodnot.

Obvykle řešíme tak, že každé sdílené proměnné přidělíme vlastní prostředek vzájemného vyloučení (semafor, monitor).

Monitor je abstraktní struktura schopna vzájemného vyloučení (mutex = mutual exclusion), kdy na sdílenou proměnnou je dán zámek při přístupu nějakým programem.
Synchronizace je pak zaručeno zavedením podmínky, která musí být splněna, aby mohl (jiný) proces vstoupit do KS, jinak je zařazen do fronty čekání.

Typické problémy paralelismu procesů jsou problém večeřících filozofů či producent- konzument.

Vzájemné vyloučení
● pouze jeden proces se může nacházet v kritické sekci (KS) v daném okamžiku
● proces, který čeká v nekritické sekci nesmí omezovat ostatní procesy
● nesmí docházet k deadlocku nebo hladovění
● když je KS volná, každý proces, který požádá o vstup musí být hned puštěn dovnitř
● proces je v KS pouze po konečný časový interval

Question 2

Vzájemné vyloučení - HW, SW

Answer 2

SW

• ​bez podpory programovacího jazyka nebo OS / OS NEBO
• programovací jazyk​poskytují podporu

HW -​speciální strojové instrukce
○ proces běží, dokud nezavolá službu OS nebo není přerušen
○ můžeme zakázat přerušení a tím zajistit vzájemné vyloučení (tím ale omezíme možnost procesoru prokládat jednotlivé procesy a tím se může snížit rychlost provádění.)
○ nebo můžeme použít speciální atomické instrukce - TestAndSet / Swap

Předpoklady o PC architektuře
● jedno čtení z paměti je atomické
● jeden zápis do paměti je atomický
● souběžné čtení/zápisy budou v nějakém pořadí proloženy

Problémy paralelismu
● vzájemné vyloučení
● čekání, i když je KS volná
● hladovění
● deadlock

Question 3

Softwarové vyloučení bez podpory OS - Dekkrův algoritmus (Dekker’s)

Answer 3

předpokládáme

• čtení/zápis jedné hodnoty je atomické (nemusí platit při používání stránkování)
• současné čtení/zápis budou provedeny v náhodném pořadí za sebou

Algoritmus: nastavíme flag, poud je nastavený flag jiného procesu a právě je jeho turn, zrušíme flag, počkáme než skončí jeho turn, nastavíme zase náš flag a zkoušíme znovu
po provedené KS zrušíme náš flag a předáme turn druhému procesu

shared var flag: array [0..1] of boolean; //flagy žádosti o vstup do kritické sekce
turn: 0..1; // označení aktuálního kola

repeat
flag[i] := true; // proces žádá o vstup do kritické sekce (nastaví flag žádosti)
while flag[j] do // proces ověřuje dokud o vstup žádá i druhý proces
if turn=j then // Pokud je právě kolo druhého procesu …
flag[i] := false; // … proces se vzdá své žádosti o krit. sekci…
while turn=j do skip; // … a čeká dokud neskončí kolo druhého procesu
flag[i] := true; // Poté znovu nastaví svoji žádost o krit. sekci
endif
endwhile // Proces vstupuje do krit. sekce pokud druhý proces flag nenastavil

turn := j; // Proces nastaví kolo na druhý proces
flag[i] := false;

until false;

Question 4

Softwarové vyloučení bez podpory OS - Petersonův algoritmus (Peterson’s algorithm)

Answer 4

předpokládáme

• čtení/zápis jedné hodnoty je atomické (nemusí platit při používání stránkování)
• současné čtení/zápis budou provedeny v náhodném pořadí za sebou

Algoritmus: nastavíme flag, předáme turn druhému procesu, pokud druhý proces žádá o kritickou sekci - čekáme, potom KS, a zrušení flagu - prostě předáme řízení a čekáme až přijde řada

shared var flag: array [0..1] of boolean; //flagy žádosti o vstup do kritické sekce
turn: 0..1; // označení aktuálního kola

repeat
flag[i] := true; // Proces žádá o krit. sekci
turn := j; // Proces nastaví kolo na druhý proces
while (flag[j] and turn=j) do skip; // Čeká dokud je kolo druhého procesu a žádá o krit. sekci

flag[i] := false; // Po dokončení krit. sekce proces stáhne žádost o krit sekci

until false;

Question 5

Softwarové vyloučení bez podpory OS - ostatní nástroje

Answer 5

Operátor < await B - > S >

• je původně pouze teoretický operátor, implementovaný ve vyšších programovacích jazycích pro paralelní programování.
• implementace je problémová
• Zajišťuje atomičnost , očekává splnění podmínky B a poté atomicky vykoná sekvenci příkazů S.

Critical Region

• ve vyšších jazycích
• jsou obalení použití semaforů pro přístup ke KS
• klíčové slovo region (označení KS) a označení proměnných shared (všechny přístupy k proměnné vzájemně vyloučené)
• Problém, pokud se zanořují, pak může dojít ke konfliktu.
• Jednoduchá implementace (téměř makro).

Conditional Critical Region

• rozšiřuje koncepci o podmínku
• pokud je stanovena dobře, ke kolizi nedojde
• Implementace je ovšem velmi složitá.

Question 6

Hardwarové vyloučení

Answer 6

Implementované v hardware jako jediná atomická instrukce

Test-and-set - testuješ, když je volno, vrátí 0, takže vstoupíš
   int testAndSet (int * target)
   {
       int value = *target;
       *target = 1;
       return (value);
   }

while(1){
    while (TestAndSet(lock));
    critical section
    lock = false;
    remainder section
}

Swap
   void Swap(int * a, int * b)
   {
       int temp = *a;
       *a = *b;
       *b = temp;
   }

while (1){
    key = true;
    while(key)
         swap(lock,key);
    critical section
    lock = false;
    remainder section
}

Question 7

Softwarové vyloučení na úrovni OS - Semafory

Answer 7

Semafory

• 1965 Dijkstra
• Synchronizační nástroj poskytovaný OS, který nevyžaduje aktivní čekání (busy waiting)
• Semafor S je to proměnná typu integer (celé číslo), ke které (kromě inicializace) může být přistupováno pouze skrze 2 atomické a vzájemně exkluzivní operace P(S) a V(S)
• Aby se předešlo aktivnímu čekání - pokud musí proces čekat, je uložen do fronty blokovaných procesů.
• Ve skutečnosti je tedy semafor struktura, obsahující celočíselnou proměnnou a FIFO frontu blokovaných procesů.

 P(S):
       S.count--;
       if (S.count<0) {
           block this process
           place this process in S.queue
       }
   V(S):
       S.count++;
       if (S.count<=0) {
           remove a process P from S.queue
           place this process P on ready list
       }

S.count musí být inicializováno na nezápornou hodnotu
Když je S.count >= 0 - tak S.count udává počet procesů, které mohou použít P(S) bez toho aniž by byly zablokovány
Když je S.count < 0 - tak absolutní hodnota S.count udává počet procesů, které čekají na semafor
Těla funkcí P(S) a V(S) jsou kritické sekce - 2 procesy nemůžou být současně v obou

Použití

• vzájemné vyloučení - nastavíme S.count na 1
• synchornizace - nastavíme S.count na 0
• • Aby jsme docílili, že P2 se provede po P1
• • P1 nejdřív musí zavolat V(S)
• • Teprve pak bude moc P2 pokračovat (P2 do té doby čekal na volání P(S))

Řešení problému producent-konzument (P/C) - neomezený buffer

• • Použijeme dva semafory:
• • S - pro vzájemné vyloučení pro přístup k bufferu
• • N - pro synchronizaci P/C skrz počet prvků ke konzumaci v bufferu
• • V tomto přístupu si může P produkovat jak se mu zlíbí a nemusí čekat na K zkonzumenta
• • Poznámka: S “zamykají” a “odemykají” oba P i K
• • Poznámka: N je inkrementovaný pouze v P a dekrementovaný pouze v K

Řešení problému producent-konzument (P/C) - omezený buffer

• • Použijeme tři semafory:
• • S - pro vzájemné vyloučení pro přístup k bufferu
• • N - pro synchronizaci P/C skrz počet prvků ke konzumaci v bufferu
• • E - pro synchronizaci P/C skrz počet volných položek v bufferu
• • Binární semafory (ty co jsme probírali do teď jsou zvané counting semaphores) jsou semafory, kde se v S.count používají pouze hodnoty True a False.

Counting semaphores mohou být implementovány pomocí binárních semaforů
Obecně jsou na použití složitější než counting semaphores