2. PROCESE ŞI FIRE DE EXECUŢIE

2.1. Procese

2.2. Fire de execuţie

2.3. Comunicarea dintre procese (InterProcess Communication – IPC)

2.4. Probleme clasice de comunicare interprocese

2.5. Planificarea proceselor

222..333...222.. EEExxxcccllluuudddeeerrreee mmmuuutttuuuaaalllăăă cccuuu aaaşşşttteeeppptttaaarrreee aaaccctttiiivvvăăă . . Aşteptare activă : testarea continuă a unei variabile până când aceasta ia o anumită valoare

2.3.2.1. Dezactivarea întreruperilor Dezactivarea întreruperilor nu este acceptată ca soluţie a excluderii mutuale deoarece:

a) există pericolul ca un proces utilizator să nu reactiveze întreruperile b) nu este utilă într-un mediu multiprocesor

2.3.2.2. Variabilă de zăvorâre (lock variable) Utilizarea unei variabile partajate, iniţializată cu 0. Dacă un proces doreşte să intre în SC, mai întâi verifică valoarea variabilei de zăvorâre. Dacă aceasta are valoarea 0, procesul îi asignează valoarea 1 şi intră în SC. Dacă valoarea variabilei este 1, procesul aşteaptă ca ea să devină 0. Soluţie ne-viabilă, deoarece se poate ajunge la o situaţie similară celei din exemplul cu coada de printare.

2

2.3.2.3. Alternarea strictă a proceselor Procesul 0 Procesul 1 while (TRUE) { while (turn != 0) /* loop */ ; critical_region(); turn = 1; noncritical_region(); }

while (TRUE) { while (turn != 1) /* loop */ ; critical_region(); turn = 0; noncritical_region(); }

Variabila turn, iniţializată cu 0, indică dacă un proces poate intra în SC. Este garantată excluderea mutuală? Pare soluţia optimă? Dacă procesul 1 este mai lent decât procesul 0:

- procesul 0 a ieşit din secţiunea necritică mai repede decât procesul 1, turn = 1, - procesul 1 este în secţiunea necritică, iar - procesul 0 aşteaptă în bucla while din faţa SC, fiind blocat de procesul 1 aflat în afara SC.

Această implementare nu satisface condiţia C3 (un proces aflat înafara SC nu poate bloca alte procese). 3

2.3.2.4. Soluţia lui Peterson Elimină constrângerea ca procesele să intre alternativ în SC.

#define FALSE 0 #define TRUE 1 #define N 2 /* number of processes */ int turn; /* whose turn is it? */ int interested[N]; /* all values initially 0 (FALSE) */ void enter_region(int process) { /* process is 0 or 1 */ int other; /* number of the other process */ other = 1 – process; /* the oposite of process */ interested[process] = TRUE; /* show that you are interested */ turn = process; /* set flag */ while (turn == process && interested[other] == TRUE) ; /* null statement */ } void leave_region(int process) /* process: who is leaving */ { interested[process] = FALSE; /* indicate departure from Crit. Region */ }

4

2.3.2.5. Instrucţiunea TSL (Test and Set Lock) TSL REGISTER, LOCK

citeşte conţinutul locaţiei de memorie LOCK în registrul REGISTER şi stochează valoarea 1 la adresa LOCK – instrucţiunea este implementată hardware pt. a fi indivizibilă.

enter_region: TSL REGISTER, LOCK | copy lock to register and set lock to 1 CMP REGISTER, #0 | was lock 0? JNE enter_region | if it was non zero, lock was set by | another process, so loop RET | return to caller, critical region entered leave_region: MOVE LOCK, #0 | store a 0 in lock RET | return to caller, critical region left

Utilizarea instrucţiunii TSL pentru obţinerea excluderii mutuale ...

5

222..333...333.. PPPrrriiimmmiiitttiiivvveeellleee sssllleeeeeeppp şşşiii wwwaaakkkeeeuuuppp . . Soluţia lui Peterson şi instrucţiunea TSL garantează excluderea mutuală Aşteptarea activă - inconveniente:

- consumă degeaba timpi procesor - poate avea efecte nedorite, de ex. În cazul proceselor cu priorităţi diferite

Primitivele sleep şi wakeup:

- elimină posibila aşteptare activă înainte de intrarea într-o SC sleep – apel de sistem care are ca efect blocarea procesului apelant wakeup – apel de sistem care acceptă, ca parametru, procesul ce trebuie deblocat Problema producător-consumator (problema buffer-ului finit):

- două procese partajează un buffer de dimensiune finită - un proces (producătorul) depune informaţii în buffer - celălalt proces (consumatorul) extrage informaţii din buffer

6

#define N 100 /* number of slots in the buffer */ int count = 0; /* number of items in the buffer */ void producer(void) { int item; while (TRUE) { /* repeat forever */ item = produce_item(); /* generate next item */ if (count == N) sleep(); /* if buffer is full, go to sleep */ insert_item(item); /* put item in buffer */ count = count + 1; /*increment count of items in the buffer */ if (count == 1) wakeup(consumer); /* was buf. empty and the cons. sleeping? */ } } void consumer(void) { int item while (TRUE) { /* repeat forever */ if (count == 0) sleep(); /* if buffer is empty, go to sleep */ item = remove_item(); /* take item out of buffer */ count = count - 1; /* decrement count of items in the buffer */ if (count == N-1) wakeup(producer); /* was buf. full and the prod. sleeping? */ consume_item(item); /* print item … */ } }

7

Deficienţele acestei soluţii:

a) nu împiedică accesarea simultană a bufferului de către cele două procese; b) există posibilitatea ca ambele procese să se blocheze, datorită faptului că un semnal de

deblocare trimis de un proces (prin wakeup) se poate pierde –> exemplu ? Ce fenomen apare ? Este accesul la variabila “count” restricţionat ?

Se poate introduce o nouă variabilă (wakeup_waiting_bit): - Atunci când un semnal de wakeup este transmis unui proces care nu este în sleep, acest bit

este setat (i se atribuie valoarea 1). - La momentul la care procesul respectiv va dori să intre în sleep, va verifica valoarea bitului. - Dacă acesta are valoarea 1, procesul nu va mai intra în sleep (deoarece primise un semnal

de wakeup anterior) şi va reseta bitul.

8

222..333...444.. SSSeeemmmaaafffoooaaarrreee . . Semafor (1965, Dijkstra) – o variabilă întreagă ce indică numărul de semnale de deblocare salvate Operaţii:

down decrementează un semafor doar dacă valoarea lui este strict mai mare decât 0 dacă semaforul are valoarea 0, atunci procesul se blochează (intră în sleep)

up incrementează valoarea unui semafor dacă unul sau mai multe procese sunt blocate pe respectivul semafor (nu au putut continua o operaţie down anterioară pe semafor cu valoarea 0), se va debloca unul dintre ele, pentru a-şi încheia operaţia down operaţia up nu poate bloca un proces

Operaţiile iniţiate asupra unui semafor sunt indivizibile

Problema producător-consumator rezolvată cu ajutorul a trei semafoare: semaforul full numără poziţiile ocupate din buffer semaforul empty contorizează poziţiile libere din buffer semaforul mutex ce împiedică accesul simultan la buffer (excluderea mutuală)

Iniţial: full = 0, empty = N (dimensiunea bufferului) şi mutex=1 9

#define N 100 /* number of slots in the buffer*/ typedef int semaphore; /* semaphores are a special kind of int */ semaphore mutex = 1; /* controls access to critical region */ semaphore empty = N; /* counts empty buffer slots */ semaphore full = 0; /* counts full buffer slots */ void producer(void) { int item; while (TRUE) { /* infinite loop */ item = produce_item(); /* generate something to put in buffer */ down(&empty); /* decrement empty count */ down(&mutex); /* enter critical region */ insert_item(item); /* put new item in buffer – Crit. Sect.*/ up(&mutex); /* leave critical region */ up(&full); /* increment count of full slots */ } } void consumer(void) { int item; while (TRUE) { /* infinite loop */ down(&full); /* decrement full count */ down(&mutex); /* enter critical region */ item = remove_item(); /* take item from buffer – Crit. Sect.*/ up(&mutex); /* leave critical region */ up(&empty); /* increment count of empty slots */ consume_item(item); /* do something with the item */ } }

10

a) empty = 0; full = N; mutex = 1 şi se execută producer( ) Procesul producer se va bloca pe instrucţiunea down(&empty) deoarece empty = 0. Deblocarea procesului va avea loc abia după ce procesul consumer va executa instrucţiunea

up(&empty). Producer Consumer

down(&empty); blocare empty = 0 down(&empty); /* empty = 0 */ down(&mutex); /* mutex = 0*/ insert_item(item); /* Crit. Sect.*/ up(&mutex); /* mutex = 1 */ up(&full); /* full = N */

down(&full); /* full = N-1 */ down(&mutex); /* mutex = 0 */ item = remove_item(); /* Crit. Sect.*/ up(&mutex); /* mutex = 1 */ up(&empty); /* empty = 1*/ consume_item(item);

deblocare

11

b) empty = N; full = 0; mutex = 1 şi se execută consumer( )

Producer Consumer down(&empty); /* empty = N-1 */ down(&mutex); /* mutex = 0*/ insert_item(item); /* Crit. Sect.*/ up(&mutex); /* mutex = 1 */ up(&full); /* full = 1 */

down(&full); blocare full = 0 down(&full); /* full = 0 */ down(&mutex); /* mutex = 0 */ item = remove_item(); /* Crit. Sect.*/ up(&mutex); /* mutex = 1 */ up(&empty); /* empty = N*/ consume_item(item);

deblocare

12

c) empty != 0; full != 0; mutex = 1 şi cele două procese încearcă să intre simultan în SC

Producer Consumer down(&empty); down(&mutex); /* mutex = 0*/ insert_item(item); /* Crit. Sect.*/ up(&mutex); /* mutex = 1 */ up(&full);

down(&full); down(&mutex); blocare mutex = 0 down(&mutex); /* mutex = 0 */ item = remove_item(); /* Crit. Sect.*/ up(&mutex); /* mutex = 1 */ up(&empty); consume_item(item);

schimbare context

deblocare

full nu permite consumatorului să extragă informaţii din buffer dacă acesta este gol, empty nu permite producătorului să introducă informaţii în buffer dacă el este plin, iar mutex nu permite celor două procese să acceseze simultan bufferul (excludere mutuală)

13

2.3.5. Mutex-uri Mutex: semafor binar utilizat de două sau mai multe procese pentru a asigura intrarea în SC doar a unuia dintre ele, la un moment dat.

mutex == 1 (locked): un proces a intrat în SC mutex == 0 (unlocked): nici un proces nu este în SC

Operaţii: mutex_lock şi mutex_unlock (cu scopul de a intra în SC). mutex_lock: un proces încearcă să câştige mutex-ul, 0 1 mutex_unock: pentru deblocarea mutex-ului, 1 0

Dacă fiecare proces execută o operaţie mutex_lock chiar înainte de a intra în SC şi o operaţie mutex_unlock imediat după părăsirea SC, excluderea mutuală este garantată.

mutex_lock: TSL REGISTER,MUTEX | copy mutex to register and set mutex to 1 CMP REGISTER,#O | was mutex zero? JZE ok | if it was zero, mutex was unlocked, so return CALL thread_yield | mutex is busy; schedule another thread JMP mutex_lock | try again later ok: RET | return to caller; critical region entered mutex_unlock: MOVE MUTEX,#0 | store a 0 in mutex RET | return to caller

14

2.3.6. Monitoare Monitor (Hoare, 1974; Hansen, 1975) este un pachet de proceduri, variabile şi structuri de date: Procesele pot apela procedurile unui monitor, dar nu pot accesa variabile şi structurile de

date interne ale monitorului. Doar un singur proces poate fi activ în monitor, la un moment dat (se poate executa doar o

singură procedură din monitor). Excluderea mutuală a mai multor procese: plasarea tuturor secţiunilor critice într-un monitor Variabile condiţie, cu operaţiile wait şi signal

- Când o procedură din monitor nu poate continua ea va executa un wait pe o variabilă condiţie.

- Această acţiune blochează procesul apelant şi permite altui proces să intre în monitor. - Acest alt proces poate debloca primul proces executând signal pe variabila condiţie

aşteptată de acesta. - Al doilea proces trebuie apoi să părăsească monitorul, pentru a permite procesului deblocat

să-şi continue execuţia în monitor. - Variabilele condiţie nu acumulează semnale pentru a fi prelucrate ulterior. - Dacă o variabilă condiţie este utilizată într-un apel signal şi nu există nici un proces care să

aştepte acest semnal, atunci semnalul este pierdut. - Un apel wait trebuie să preceadă un apel signal.

Structura de tip monitor trebuie să fie suportată de limbajul de programare (Java). 15

monitor ProducerConsumer condition full, empty; integer count; procedure insert(item: integer); begin if count = N then wait(full); insert _item(item); count := count + 1; if count = 1 then signal(empty) end; function remove: integer; begin if count = 0 then wait(empty); remove = remove_item; count := count - 1; if count = N - 1 then signal(full) end; count := 0; end monitor;

procedure producer; begin while true do begin item = produce _item; ProducerConsumer.insert(item) end end; procedure consumer; begin while true do begin item = ProducerConsumer.remove; consume_item(item) end end;

16

2.3.7. Comunicarea interprocese prin transmitere de mesaje Transmiterea de mesaje (message passing) utilizează apelurile de sistem send şi receive send(destination, &message); - trimite un mesaj la destinaţia dată (un proces) receive(source, &message); - primeşte un mesaj de la sursa specificată (un proces); dacă nu este disponibil nici un mesaj, destinatarul este blocat până la sosirea mesajului. Realizează o comunicare directă între două procese. Fiecare proces trebuie să cunoască numele celuilalt proces pentru a putea comunica. Problema producător-consumator:

(i) toate mesajele au aceeaşi dimensiune (ii) mesajele trimise şi nerecepţionate sunt păstrate într-un buffer de către SO

Numărul total de mesaje utilizate este N. Iniţial consumatorul trimite N mesaje vide producătorului. Când producătorul are de trimis informaţii, preia un mesaj vid, îl completează şi-l expediază consumatorului. Numărul total de mesaje din sistem rămâne constant în timp, mesajele putând fi stocate într-o zonă de memorie de dimensiune cunoscută.

17

#define N 100 /* number of slots in the buffer */ void producer(void) { int item; message m; /* message buffer */ while (TRUE) { item = produce_item(); /* generate something to put in buffer */ receive(consumer, &m); /* wait for an empty message to arrive */ build_message(&m, item); /* construct a message to send */ send(consumer, &m); /* send item to consumer */ } } void consumer(void) { int item, i; message m; for (i = 0; i < N; i++) send(producer, &m); /* send N empties */ while (TRUE) { receive(producer, &m); /* get message containing item */ item = extract_item(&m); /* extract item from message */ send(producer, &m); /* send back empty reply */ consume_item(item); /* do something with the item */ } }

18

În cazul unei comunicări indirecte, mesajele sunt trimise la / extrase dintr-o cutie poştală (eng. mailbox). O cutie poştală poate fi privită ca fiind un obiect în care procesele plasează mesaje şi din care pot fi extrase mesaje. Operarea cutiei poştale se face cu ajutorul primitivelor send şi receive, în care destinatarul şi sursa reprezintă cutia poştală. Comunicarea de tip rendezvous utilizează aceleaşi primitive send şi receive, care operează, însă, sincron. Procesul care expediază un mesaj (send) este blocat până când destinatarul preia mesajul. Procesul care primeşte mesajul (receive) este blocat până când un alt proces îi trimite un mesaj.

19

22..44.. PPrroobblleemmee ccllaassiiccee ddee ccoommuunniiccaarree iinntteerrpprroocceessee

2.4.1. Cina celor 5 filozofi (The Dining Philosophers)

2.4.2. Problema frizerului (The Sleeping Barber Problem)

2.4.3. Cititor şi scriitor (The Readers and Writers Problem)

20

2.4.1. Cina celor 5 filozofi (The Dining Philosophers) 1965, Djikstra Soluţia incorectă a problemei celor 5 filozofi

#define N 5 /* number of philosophers */ void philosopher(int i) /* i: philosopher number */ { while (TRUE) { I think(); /* philosopher is thinking */ take_stick(i); /* take left stick */ take_stick((i+1) % N); /* take right stick; % is modulo operator */ eat(); /* yum-yum, rice */ put_stick(i); /* put left stick back on the table */ put_stick((i+1) % N); /* put right stick back on the table */ } }

Ph4

Ph3 Ph2

Ph1

S4

S3

S2

S1 S0

Ph0

Dacă fiecare filozof ia băţul din stânga sa, nici unul dintre ei nu va putea lua şi băţul din dreapta ajungându-se în deadlock.

21

O soluţie: utilizarea unui semafor binar, mutex, iniţializat cu 1.

- înainte de a executa take_stick(i), fiecare proces execută down(& mutex), urmând a executa up(& mutex) după ce a eliberat al doilea băţ.

- dezavantajul acestei soluţii: la orice moment de timp, un singur filozof poate mânca Soluţia următoare elimină deadlock-ul şi asigură paralelismul maxim pentru un număr arbitrar de filozofi. LEFT şi RIGHT definesc vecinii din stânga şi din dreapta filozofului i. Vectorul state conţine stările celor N filozofi (THINKING, HUNGRY sau EATING). S este un vector de semafoare şi fiecare semafor corespunde un filozof. Un filozof poate începe să mănânce doar dacă nici unul din vecini nu mănâncă deja (stările lor sunt diferite de EATING).

Procedura “philosopher” e rulată de fiecare proces.

22

#define N 5 /* number of philosophers */ #define LEFT (i+N-1)%N /* number of i's left neighbor */ #define RIGHT (i+1)%N /* number of i's right neighbor */ #define THINKING 0 /* philosopher is thinking */ #define HUNGRY 1 /* philosopher is trying to get sticks */ #define EATING 2 /* philosopher is eating */ typedef int semaphore; /* semaphores are a special kind of int */ int state[N]; /* array to keep track of everyone's state */ semaphore mutex = 1; /* mutual exclusion for critical regions */ semaphore s[N]; /* one semaphore per philosopher */ void philosopher(int i) /* i: philosopher number, from 0 to N-1 */ { while (TRUE) { /* repeat forever */ think(); /* philosopher is thinking */ take_sticks(i); /* acquire two sticks or block */ eat(); /* yum-yum, rice */ put_sticks(i); /* put both sticks back on table */ } }

23

void take_sticks(int i) /* i: philosopher number, from 0 to N-1 */ { down(&mutex); /* enter critical region */ state[i] = HUNGRY; /* record fact that philosopher i is hungry */ test(i); /* try to acquire 2 sticks */ up(&mutex); /* exit critical region */ down(&s[i]); /* block if sticks were not acquired */ } void put_sticks(i) /* i: philosopher number, from 0 to N-1 */ { down(&mutex); /* enter critical region */ state[i] = THINKING; /* philosopher has finished eating */ test(LEFT); /* see if left neighbor can now eat */ test(RIGHT); /* see if right neighbor can now eat */ up(&mutex); /* exit critical region */ } void test(i) /* i: philosopher number, from 0 to N-1 */ { if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) { state[i] = EATING; up(&s[i]); } }

24

2.4.2. Problema frizerului (The Sleeping Barber Problem)

3 semafoare: - customers: numără clienţii ce aşteaptă să ajungă

pe scaunul frizerului; - barbers: numărul de frizeri disponibili. Poate

avea valoarea 0 şi 1; - mutex: utilizat pentru excludere mutuală. variabila waiting contorizează clienţii în aşteptare (reprezintă o copie a semaforului customers)

25

#define CHAIRS 5 /* # chairs for waiting customers */ typedef int semaphore; /* use your imagination */ semaphore customers = 0; /* # of customers waiting for service */ semaphore barbers = 0; /* # of barbers waiting for customers */ semaphore mutex = 1; /* for mutual exclusion */ int waiting = 0; /* customers are waiting (not being cut) */ void barber(void) { while (TRUE) { down(&customers); /* go to sleep if # of customers is 0 */ down(&mutex); /* acquire access to 'waiting' */ waiting = waiting - 1; /* decrement count of waiting customers */ up(&barbers); /* one barber is now ready to cut hair */ up(&mutex); /* release 'waiting' */ cut_hair(); /* cut hair (outside critical region) */ } } void customer(void) { down(&mutex); /* enter critical region */ if (waiting < CHAIRS) { /* if there are no free chairs, leave */ waiting = waiting + 1; /* increment count of waiting customers */ up(&customers); /* wake up barber if necessary */ up(&mutex); /* release access to 'waiting' */ down(&barbers); /* go to sleep if # of free barbers is 0 */ get_haircut(); /* be seated and be serviced */ } else { up(&mutex); /* shop is full; do not wait */} }

26

27

2.4.3. Cititor şi scriitor (The Readers and Writers Problem) typedef int semaphore; /* use your imagination */ semaphore mutex = 1; /* controls access to 'rc' */. semaphore db = 1; /* controls access to the database */ int rc = 0; /* readers counter = # of processes reading or wanting to */

void reader(void) { while (TRUE) { /* repeat forever */ down(&mutex); /* get exclusive access to 'rc' */ rc = rc + 1; /* one reader more now */ if (rc == 1) down(&db); /* if this is the first reader... */ up(&mutex); /* release exclusive access to 'rc' */ read_data_base(); /* access the data */ down(&mutex); /* get exclusive access to 'rc' */ rc = rc - 1; /* one reader fewer now */ if (rc == 0) up(&db); /* if this is the last reader... */ up(&mutex); /* release exclusive access to 'rc' */ use_data_read(); /* noncritical region */ } }

void writer(void) { while (TRUE) { /* repeat forever */ think_up_data(); /* noncritical region */ down(&db); /* get exclusive access */ write __data_base(); /* update the data */ up(&db); /* release exclusive access */ } }