1/35
PB153
OPERAČNÍ SYSTÉMY
A JEJICH ROZHRANÍ
Synchronizace procesů
12
2/35
 Synchronizace běhu procesů
● jeden proces čeká na událost z druhého procesu
 Komunikace mezi procesy
● komunikace – způsob synchronizace, koordinace různých aktivit
● může dojít k uváznutí
● každý proces čeká na zprávu od nějakého jiného procesu
● může dojít ke stárnutí
● dva procesy si opakovaně posílají zprávy zatímco třetí proces čeká na
zprávu nekonečně dlouho
 Sdílení prostředků
● procesy používají a modifikují sdílená data
● operace zápisu musí být vzájemně výlučné
● operace zápisu musí být vzájemně výlučné s operacemi čtení
● operace čtení mohou být realizovány souběžně
● pro zabezpečení integrity dat se používají kritické sekce
PARALELNÍ BĚH PROCESŮ
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
3/35
 Paralelní přístup ke sdíleným údajům může být
příčinou nekonzistence dat
 Udržování konzistence dat vyžaduje používání
mechanismů, které zajistí patřičné provádění
spolupracujících procesů
 Problém komunikace procesů v úloze typu
Producent-Konzument přes vyrovnávací paměť
s omezenou kapacitou
NEKONZISTENCE
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
4/35
 Sdílená data
#define BUFFER_SIZE 10
typedef struct {
. . .
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
int counter = 0;
PRODUCENT-KONZUMENT (1)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
5/35
 Producent
item nextProduced;
while (1) {
while (counter == BUFFER_SIZE)
; /* do nothing */
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
counter++;
}
PRODUCENT-KONZUMENT (2)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
6/35
 Konzument
item nextConsumed;
while (1) {
while (counter == 0)
; /* do nothing */
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter--;
}
PRODUCENT-KONZUMENT (3)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
7/35
 Atomická operace je taková operace, která vždy proběhne bez
přerušení
 Následující příkazy musí být atomické
● counter++;
● counter--;
 count++ v assembleru může vypadat
● register1 = counter
● register1 = register1 + 1
● counter = register1
 count-- v assembleru může vypadat
● register2 = counter
● register2 = register2 – 1
● counter = register2
PRODUCENT-KONZUMENT (4)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
8/35
 Protože takto implementované operace count++ a
count-- nejsou atomické, můžeme se dostat do
problémů s konzistencí
 Nechť je hodnota counter nastavena na 5. Může
nastat:
● producer: register1 = counter (register1 = 5)
● producer: register1 = register1 + 1 (register1 = 6)
● consumer: register2 = counter (register2 = 5)
● consumer: register2 = register2 – 1 (register2 = 4)
● producer: counter = register1 (counter = 6)
● consumer: counter = register2 (counter = 4)
 Výsledná hodnota proměnné counter bude buďto 4
nebo 6, zatímco správný výsledek má být 5.
PRODUCENT-KONZUMENT (5)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
9/35
ANIMACE: PRODUCENT-KONZUMENT (5)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
10/35
 Race condition (podmínka soupeření):
● více procesů současně přistupuje ke sdíleným zdrojům
a manipulují s nimi
● konečnou hodnotu zdroje určuje poslední z procesů,
který zdroj po manipulaci opustí
 Ochrana procesů před negativními dopady race
condition
● je potřeba procesy synchronizovat
RACE CONDITION
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
11/35
 N procesů soupeří o právo používat
jistá sdílená data
 V každém procesu se nachází segment kódu
programu nazývaný kritická sekce, ve kterém
proces přistupuje ke sdíleným zdrojům
 Problém:
● je potřeba zajistit, že v kritické sekci, sdružené s jistým
zdrojem, se bude nacházet nejvýše jeden proces
PROBLÉM KRITICKÉ SEKCE
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
12/35
 Podmínka vzájemného vyloučení (mutual exclusion), podmínka
bezpečnosti, „safety“
● jestliže proces P1 provádí svoji kritickou sekci, žádný jiný proces nemůže
provádět svoji kritickou sekci sdruženou se stejným zdrojem
 Podmínka trvalosti postupu (progress), podmínka živosti, „liveliness“
● jestliže žádný proces neprovádí svoji sekci sdruženou s jistým zdrojem a
existuje alespoň jeden proces, který si přeje vstoupit do kritické sekce
sdružené s tímto zdroje, pak výběr procesu, který do takové kritické sekce
vstoupí, se nesmí odkládat nekonečně dlouho
 Podmínka konečnosti doby čekání (bounded waiting), podmínka
spravedlivosti, „fairness“
● musí existovat horní mez počtu, kolikrát může být povolen vstup do
kritické sekce sdružené s jistým zdrojem jiným procesům než procesu,
který vydal žádost o vstup do kritické sekce sdružené s tímto zdrojem, po
vydání takové žádosti a před tím, než je takový požadavek uspokojen
● předpokládáme, že každý proces běží nenulovou rychlostí
● o relativní rychlosti procesů nic nevíme
PODMÍNKY ŘEŠENÍ PROBLÉMU KRITICKÉ SEKCE
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
13/35
 Máme pouze 2 procesy, P0 a P1
 Generická struktura procesu Pi
do {
} while (1);
 Procesy mohou za účelem dosažení synchronizace svých akcí
sdílet společné proměnné
 Činné čekání na splnění podmínky v „entry section“ – „busy
waiting“
POČÁTEČNÍ NÁVRHY ŘEŠENÍ
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
entry section
critical section
exit section
reminder section
14/35
 Softwarová řešení
● algoritmy, jejichž správnost se nespoléhá na žádné
další předpoklady
● s aktivním čekáním „busy waiting“
 Hardwarová řešení
● vyžadují speciální instrukce procesoru
● s aktivním čekáním
 Řešení zprostředkované operačním systémem
● potřebné funkce a datové struktury poskytuje OS
● s pasivním čekáním
● podpora v programovacím systému/jazyku
● semafory, monitory, zasílání zpráv
ŘEŠENÍ PROBLÉMU KS
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
15/35
 Nedostatek softwarového řešení
● procesy, které žádají o vstup do svých KS to dělají
metodou „busy waiting“
● po nezanedbatelnou dobu spotřebovávají čas procesoru
 Speciální instrukce
● výhody
● vhodné i pro multiprocesory (na rozdíl od prostého
maskování/povolení přerušení)
● nevýhody
● opět „busy waiting“
● možnost stárnutí – náhodnost řešení konfliktu
● možnost uváznutí v prioritním prostředí (proces v KS nedostává
čas CPU)
SITUACE BEZ PODPORY OS
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
16/35
 Synchronizační nástroj, který lze implementovat i bez
„busy waiting“
● proces je (operačním systémem) „uspán“ a „probuzen“
● tj. řešení na úrovni OS
 Definice
Semaphore S : integer
 Lze ho zpřístupnit pouze pomocí dvou atomických
operací
wait (S): signal(S):
while S ≤ 0 do no-op; S ++;
S --;
SEMAFORY
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
17/35
 Sdílená data:
semaphore mutex; // počátečně mutex = 1
 Proces Pi:
do {
wait(mutex);
critical section
signal(mutex);
remainder section
} while (1);
KRITICKÁ SEKCE
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
18/35
 Má se provést akce B v Pj pouze po té, co se provede
akce A v Pi
 Použije se semafor flag inicializovaný na 0
 Program:
Pi Pj
 
A wait(flag)
signal(flag) B
. .
SYNCHRONIZACE SEMAFOREM
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
19/35
 Uváznutí
● dva nebo více procesů neomezeně dlouho čekají na událost, kterou
může generovat pouze jeden z čekajících procesů
● Nechť S a Q jsou dva semafory inicializované na 1
P0 P1
wait(S); wait(Q);
wait(Q); wait(S);
 
signal(S); signal(Q);
signal(Q) signal(S);
 Stárnutí
● neomezené blokování, proces nemusí být odstraněný z fonty na
semafor nikdy (předbíhání vyššími prioritami, …)
UVÁZNUTÍ A STÁRNUTÍ
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
20/35
 Obecný semafor S
● celočíselná hodnota z neomezovaného intervalu
 Binární semafor
● celočíselná hodnota z intervalu <0,1>
 Implementovatelnost
● binární semafor lze snadněji implementovat
● obecný semafor lze implementovat semaforem
binárním
DVA TYPY SEMAFORŮ
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
21/35
Výukovou pomůcku zpracovalo
Servisní středisko pro e-learning na MU
http://is.muni.cz/stech/
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ