‹#›/35
PB153
OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
Synchronizace procesů
08

‹#›/35

lSynchronizace běhu procesů
●jeden proces čeká na událost z druhého procesu
lKomunikace 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
lSdí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Í

‹#›/35

lParalelní přístup ke sdíleným údajům může být příčinou nekonzistence dat
lUdržování konzistence dat vyžaduje používání mechanismů, které zajistí patřičné provádění
spolupracujících procesů
lProblé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Í

‹#›/35

lSdílená data
●#define BUFFER_SIZE 10
●typedef struct {
● . . .
●} item;
●item buffer[BUFFER_SIZE];
●int in = 0;
●int out = 0;
●int counter = 0;
●
l
PRODUCENT-KONZUMENT (1)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

lProducent
l
l item nextProduced;
l while (1) {
l while (counter == BUFFER_SIZE)
l ; /* do nothing */
l buffer[in] = nextProduced;
l in = (in + 1) % BUFFER_SIZE;
l counter++;
l }
l
PRODUCENT-KONZUMENT (2)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

lKonzument
l
l item nextConsumed;
l while (1) {
l while (counter == 0)
l ; /* do nothing */
l nextConsumed = buffer[out];
l out = (out + 1) % BUFFER_SIZE;
l counter--;
l }
PRODUCENT-KONZUMENT (3)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

lAtomická operace je taková operace, která vždy proběhne bez přerušení
lNásledující příkazy musí být atomické
●counter++;
●counter--;
lcount++ v assembleru může vypadat
●register1 = counter
●register1 = register1 + 1
●counter = register1
lcount-- v assembleru může vypadat
●register2 = counter
●register2 = register2 – 1
●counter = register2
PRODUCENT-KONZUMENT (4)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

lProtože takto implementované operace count++ a count-- nejsou atomické, můžeme se dostat do
problémů s konzistencí
lNechť 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)
lVýsledná hodnota proměnné counter bude buďto 4 nebo 6, zatímco správný výsledek má být 5.
l
PRODUCENT-KONZUMENT (5)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

ANIMACE: PRODUCENT-KONZUMENT (5)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

lRace 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í
lOchrana procesů před negativními dopady race condition
●je potřeba procesy synchronizovat
RACE CONDITION
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

lN procesů soupeří o právo používat
jistá sdílená data
lV 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
lProblé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Í

‹#›/35

lPodmí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
lPodmí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
lPodmí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Í

‹#›/35

lMáme pouze 2 procesy, P0 a P1
lGenerická struktura procesu Pi
l    do {
l
l
l
l } while (1);
lProcesy mohou za účelem dosažení synchronizace svých akcí sdílet společné proměnné
lČ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

‹#›/35

lSoftwarová řešení
●algoritmy, jejichž správnost se nespoléhá na žádné další předpoklady
●s aktivním čekáním „busy waiting“
lHardwarová řešení
●vyžadují speciální instrukce procesoru
●s aktivním čekáním
lŘ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Í

‹#›/35

lSdílené proměnné
●int turn;
počátečně turn = 0
●turn = i Þ Pi může vstoupit do KS
lProces Pi
l do {
l while (turn != i) ;
l critical section
l turn = j;
l reminder section
l } while (1);
lSplňuje vzájemné vyloučení, ale ne trvalost postupu
l
ALGORITMUS 1
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

lSdílené proměnné
●boolean flag[2];
počátečně flag [0] = flag [1] = false.
●flag [i] = true Þ Pi může vstoupit do své KS
lProcess Pi
l do {
l flag[i] := true;
while (flag[j]) ; critical section
l flag [i] = false;
l remainder section
l } while (1);
lSplňuje vzájemné vyloučení, ale ne trvalost postupu
l
ALGORITMUS 2
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

lKombinuje sdílené proměnné algoritmů 1 a 2
lProces Pi
l do {
l flag [i]:= true;
turn = j;
while (flag [j] and turn == j) ;
l critical section
l flag [i] = false;
l remainder section
l } while (1);
lJsou splněny všechny tři podmínky správnosti řešení problému kritické sekce
ALGORITMUS 3 (PETERSONŮV)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

lSpeciální instrukce strojového jazyka
●test_and_set, exchange / swap, …
lStále zachována idea používání „busy waiting“
lTest_and_set
●testování a modifikace hodnoty proměnné – atomicky
l     boolean TestAndSet (boolean &target) {
                           boolean rv = target;
                           target = true;
                           return rv;
                  }
lSwap
●Atomická výměna dvou proměnných
●Void Swap (boolean &ra, boolean &rb] {
                   boolean temp = a;
                  a = b;
                   b = temp;
             }
SYNCHRONIZAČNÍ HARDWARE
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

lSdílená data (inicializováno na false):
l            boolean lock:
lProces Pi
l do {
l while (TestAndSet(lock)) ;
l critical section
l lock = false;
l remainder section
l }
VYUŽITÍ TESTANDSET
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

lSdílená data (inicializováno na false):
l                    boolean lock;
l                    boolean waiting[n];
lProces Pi
l     do {
l key = true;
l while (key == true)
l Swap(lock,key);
l critical section
l lock = false;
l remainder section
l }
VYUŽITÍ SWAP
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

lNedostatek 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
lSpeciá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Í

‹#›/35

lSynchronizač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
lDefinice
l            Semaphore S : integer
lLze ho zpřístupnit pouze pomocí dvou atomických operací
l    wait (S):                                   signal(S):
l      while S ≤ 0 do no-op;                  S ++;
l      S --;
SEMAFORY
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

lSdílená data:
l    semaphore mutex;     // počátečně mutex = 1
lProces Pi:
l   do {
l         wait(mutex);
l                critical section
l         signal(mutex);
l                remainder section
l    } while (1);
KRITICKÁ SEKCE
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

lMá se provést akce B v Pj pouze po té, co se provede akce A v Pi
lPoužije se semafor flag inicializovaný na 0
lProgram:
l Pi Pj
l M M
l A      wait(flag)
l signal(flag) B
l    .                 .
SYNCHRONIZACE SEMAFOREM
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

lUvá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
l    P0    P1
l wait(S); wait(Q);
l wait(Q); wait(S);
l     M     M
l signal(S); signal(Q);
l signal(Q) signal(S);
lStá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Í

‹#›/35

lObecný semafor S
●celočíselná hodnota z neomezovaného intervalu
lBinární semafor
●celočíselná hodnota z intervalu <0,1>
lImplementovatelnost
●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Í

‹#›/35

lSemafory jsou mocný nástroj pro dosažení vzájemného vyloučení a koordinaci procesů
lOperace wait(S) a signal (S) jsou prováděny více procesy a jejich účinek nemusí být vždy
explicitně zřejmý
●semafor s explicitním ovládáním wait/signal je nástroj nízké úrovně
lChybné použití semaforu v jednom procesu hroutí souhru všech spolupracujících procesů
lPatologické případy použití semaforů:
l     wait(x)          wait(x)
l       KS                            KS
l     wait(x)                                 signal(y)
PROBLÉMY SE SEMAFORY
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

lKonstrukt programovacího jazyka vysoké úrovně
lSdílená proměnná v typu T, je deklarována jako:
l                    v: shared T
lProměnná v je dostupná pouze v příkazu
l                region v when B do S
l     kde B je booleovský výraz
lPo dobu, po kterou se provádí příkaz S, je proměnná v pro jiné procesy nedostupná
lOblasti referující stejnou sídlenou proměnnou se v čase vzájemně vylučují
KRITICKÉ OBLASTI
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

lKdyž se proces pokusí provést příkaz region, vyhodnotí se Booleovský výraz B
lJe-li B pravdivý, příkaz S se provede
lJe-li B nepravdivý, provedení příkazu S se oddálí do doby až bude B pravdivý a v oblasti (region)
spojené s V se nenachází žádný proces
KRITICKÉ OBLASTI (2)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

lSynchronizační nástroj vysoké úrovně
lUmožňuje bezpečné sdílení abstraktního datového typu souběžnými procesy
lProvádění P1, P2, … se implicitně vzájemně vylučují
MONITORY
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
monitor monitor-name
{
   shared variable declarations
   procedure body P1 (…) {
   . . .
   }
   procedure body P2 (…) {
   . . .
   }
   procedure body Pn (…) {
   . . .
   }
   {
   initialization code
   }
}

‹#›/35

lIPC (InterProcess Communication)
●signály (asynchronní události)
●roury ( ls|pr|lpr )
●zprávy (messages)
●semafory (semaphores)
●sdílená paměť (shared memory)
PŘÍKLAD: LINUX (1)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/35

lSemafory podle SYS V IPC, volání jádra
●semget
●semctl
●semop
PŘÍKLAD: LINUX (2)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
array of semaphores
sem_queue
sem_undo
semid_ds
ipc
times
sem_base
sem_pending
sem_pending_last
undo
sem_nsems
proc_next
id_next
semid
semadj
next
prev
sleeper
undo
pid
status
sma
sops
nsops

‹#›/35

PŘÍKLAD: WIN32 (1)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
win_ipc_list

‹#›/35

lSemafory (obecné semafory), volání jádra
●CreateSemaphore
●OpenSemaphore
●ReleaseSemaphore
●Wait
●SignalObjectAndWait
●WaitForSingleObject
●WaitForSingleObjectEx
●WaitForMultipleObjects
●WaitForMultipleObjectsEx
●MsgWaitForMultipleObjects
●MsgWaitForMultipleObjectsEx
PŘÍKLAD: WIN32 (2)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/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Í