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

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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);
l
ALGORITMUS 3 (PETERSONŮV)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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Í

‹#›/34

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
   }
}

‹#›/34

lSynchronizace
●signály (asynchronní události)
●wait
●semafory (semaphores)
●mutexy v pthreads
lKomunikace
●nepojmenované roury ( ls|pr|lpr ) fce popen/pclose, …
●pojmenované roury (mkfifo)
●zprávy (messages, message queues)
●sdílená paměť (shared memory)
PŘÍKLAD: LINUX
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/34

LINUX: Signály dle POSIX
10-05

‹#›/34

LINUX: Signály
l1) SIGHUP 2) SIGINT 3) SIGQUIT 4) SIGILL
l5) SIGTRAP 6) SIGABRT 7) SIGEMT 8) SIGFPE
l9) SIGKILL 10) SIGBUS 11) SIGSEGV 12) SIGSYS
l13) SIGPIPE 14) SIGALRM 15) SIGTERM 16) SIGURG
l17) SIGSTOP 18) SIGTSTP 19) SIGCONT 20) SIGCHLD
l21) SIGTTIN 22) SIGTTOU 23) SIGIO 24) SIGXCPU
l25) SIGXFSZ 26) SIGVTALRM 27) SIGPROF 28) SIGWINCH
l29) SIGINFO 30) SIGUSR1 31) SIGUSR2

‹#›/34

LINUX: posílání signálů

‹#›/34

LINUX: real-time signály

‹#›/34

LINUX: Semafory
lPOSIX
●#include <semaphore.h>
●klasické semafory dle POSIXu
lSystem V
●#include <sys/sem.h>
●modernější verze

‹#›/34

LINUX: POSIX semafory
lint sem_init ((sem_t *sem, int pshared, unsigned int value));
●Nepojmenovaný semafor
lsem_t *sem_open (char *name, int oflag, [mode_t mode, int init_value]);
●Pojmenovaný semafor
lint sem_wait ((sem_t *sem));
lint sem_post ((sem_t *sem));
lint sem_close (sem_t *sem);
lint sem_unlink(char *name);
lint sem_getvalue (sem_t *sem, int *val);

‹#›/34

lVolání jádra:
●semget
●semctl
●semop
LINUX: Semafory dle System V
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

‹#›/34

LINUX: Mutexy v pthreads
02-30

‹#›/34

LINUX: Mutexy v pthreads
02-31

‹#›/34

LINUX: Zprávy
lKapacita zpráv
●Administrátor může změnit defaultní hodnoty
●Max msgs:  10 /queue
●Max Msg Size: 8192
●Max # of Queues: 256
lVirtuální message queue file system (mqueue)
●Může být připojen pro zobrazení (a manipulaci) se zprávami
●mkdir /dev/mqueue
●mount –t mqueue none /dev/mqueue
l

‹#›/34

Linux: sdílená paměť
Proces 1
Proces 2
Proces 3

‹#›/34

Linux: sdílená paměť
Proces 1
Proces 2
Proces 3

‹#›/34

LINUX: sdílená paměť
l#include <sys/ipc.h>  + #include<sys/shm.h>
lint shmget (key_t, int size, int shmflg);
lvoid * shmat (shmid, shmaddr, shmflg);
lint shmctl (shmid, cmd, struct shmid_ds *buf);
●cmd:
●IPC_STAT – return status information about the shared memory in buf.
●IPC_SET – modify the shared memory based on parameters in buf (can only change UID and mode bits)
●IPC_RMID – Remove (deallocate) the shared memory segment specified in shmid.
●IPC_LOCK – lock the shared memory segment in memory (don’t swap out).
●IPC_UNLOCK – release the lock on shared memory

‹#›/34

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

‹#›/34

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

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