2018 - 2019

Semafoare

Capitolul 4

2018 - 2019

Procese

• Algoritmii pentru sectiuni critice fac apel exclusiv la instructiunile

procesorului gazda.

• Semafoarele definesc o abstractie de programare la un nivel deasupra

instructiunilor masina, de regula la nivelul SO.

• Intr-un sistem multiprocesor sau multitasking mai multe procese pot

partaja resursele aceluiasi procesor.

• Un sistem contine o multime de procese, dintre care:

– Un proces in executie (engl. running)

– Mai multe procese gata de executie (engl. ready)

• O componenta a SO numita planificator (engl. scheduler) realizeaza

periodic realocarea procesorului unui nou proces gata de executie.

• Abstractizand modul de functionare a planificatorului, rezulta ca in

principiu este posibila orice intretesere a proceselor gata de executie.

2018 - 2019

Stari ale proceselor

• Fiecare proces p are alocata o stare 𝑝. 𝑠𝑡𝑎𝑡𝑒 din multimea starilor posibile: *𝑖𝑛𝑎𝑐𝑡𝑖𝑣𝑒, 𝑟𝑒𝑎𝑑𝑦, 𝑟𝑢𝑛𝑛𝑖𝑛𝑔, 𝑏𝑙𝑜𝑐𝑘𝑒𝑑, 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑒𝑑+.

– Initial, dupa creare, procesul se afla in starea inactive

– Apoi procesul este activat si devine gata de executie in starea ready

– Din ready procesul poate trece in executie in starea running

– Din running procesul poate reveni in ready, se poate termina si trece in completed sau poate inceta executia trecand in blocked.

– Din blocked procesul poate reveni in ready.

inactive ready running completed

blocked

2018 - 2019

Definirea semafoarelor

• Un semafor 𝑆 este o structura de date cu doua campuri:

– 𝑆. 𝑉 de tip numar natural

– 𝑆. 𝐿 de tip multime de procese

• Initial semaforul primeste o valoare 𝑘 ≥ 0 pentru campul 𝑆. 𝑉

si multimea vida ∅ pentru campul 𝑆. 𝐿, adica:

semaphore 𝑆 ← (𝑘, ∅)

• Pentru un semafor 𝑆 pot fi definite doua operatii atomice:

wait(𝑆)

signal(𝑆)

• Numele date de Dijkstra pentru wait si signal sunt 𝑃 si 𝑉. Ele

reprezinta initialele cuvintelor in limba olandeza:

𝑃 = passering (trecere), 𝑉 = vrijgave (eliberare)

2018 - 2019

Operatia wait

wait(𝑆):

if 𝑆. 𝑉 > 0

𝑆. 𝑉 ← 𝑆. 𝑉 – 1

else

𝑆. 𝐿 ← 𝑆. 𝐿 ∪ * 𝑝 +

𝑝. 𝑠𝑡𝑎𝑡𝑒 ← 𝑏𝑙𝑜𝑐𝑘𝑒𝑑

• Daca 𝑆. 𝑉 > 0 atunci se decrementeaza 𝑆. 𝑉 si procesul curent p

poate continua executia.

• Daca 𝑆. 𝑉 = 0 atunci procesul curent 𝑝 este adaugat la

multimea 𝑆. 𝐿 si 𝑝 trece in starea blocked. Se spune ca 𝑝 devine

blocat la semaforul 𝑆.

2018 - 2019

Operatia signal

signal(𝑆):

if 𝑆. 𝐿 = ∅

𝑆. 𝑉 ← 𝑆. 𝑉 + 1

else

fie un proces arbitrar 𝑞 ∈ 𝑆. 𝐿

𝑆. 𝐿 ← 𝑆. 𝐿 ∖ * 𝑞 +

𝑞. 𝑠𝑡𝑎𝑡𝑒 ← 𝑟𝑒𝑎𝑑𝑦

• Daca 𝑆. 𝐿 = ∅ atunci se incrementeaza 𝑆. 𝑉.

• Daca 𝑆. 𝐿 ≠ ∅ atunci se alege un proces arbitrar 𝑞 ∈ 𝑆. 𝐿 si se

deblocheaza fiind trecut in starea ready.

• Starea procesului 𝑝 ce executa operatia nu se schimba.

2018 - 2019

Semafoare generale si binare

• Un semafor care poate lua o valoare reprezentand un numar

natural arbitrar pentru campul 𝑆. 𝑉 se numeste semafor general

sau semafor numarator (engl. counting semaphore)

• Un semafor care poate lua doar una dintre valorile 0 sau 1

pentru campul 𝑆. 𝑉 se numeste semafor binar. Operatia wait(𝑆)

nu se schimba pentru un semafor binar. In schimb, pentru

operatia signal(𝑆), instructiunea de incrementare a campului

𝑆. 𝑉 se inlocuieste cu 𝑆. 𝑉 ← 1, iar semaforul poate fi initializat

doar cu (0, ∅) sau (1, ∅).

• Un semafor binar se mai numeste uneori si mutex (dar uneori si

zavoarele folosite in monitoare se numesc mutex, asa ca pot

exista confuzii cu acest termen).

2018 - 2019

Sectiunea critica cu semafoare pentru 2 procese

binary semaphore S (1,)

p q

loop forever p1: sectiune non-critica p2: wait(S) p3: sectiune critica p4: signal(S)

loop forever q1: sectiune non-critica q2: wait(S) q3: sectiune critica q4: signal(S)

Sectiunea critica cu semafoare pentru 2 procese

Sursa: M.Ben-Ari, 2006

• Un proces p care doreste sa intre in SC executa wait(S). Daca S.V = 1 atunci S.V

devine 0 si p intra in SC. La iesire p executa signal(S) si S.V redevine 1.

• Daca un proces q incearca sa intre in SC in timp ce p este acolo, deoarece S.V = 0, se

va bloca si S va deveni (0,{q}). Cand p iese din SC, el executa signal(S). In urma

“alegerii arbirare” din {q}, este ales q, acesta fiind deblocat, putand continua in SC.

2018 - 2019

Diagrama de stari

• Daca q este blocked in q1 atunci singurul proces care va putea avansa este p. Rezultatul este ca q isi va putea continua executia din q2. Situatia este similara pentru p.

• Nu exista nici o stare (p2,q2), deci excluderea mutuala este verificata.

• Nu exista o stare in care procesele sunt blocked, deci nu avem interblocaj.

• Daca p executa wait atunci el va progresa direct sau prin intermediul starii blocked intr-o stare in care poate executa signal, deci nu avem infometare.

Sursa: M.Ben-Ari, 2006

In diagrama se elimina liniile

SNC si SC din ambele

procese. Liniile ramase se

redenumesc p1, p2 si q1, q2.

2018 - 2019

Invarianti pentru semafoare

• Teorema: Fie S un semafor, k 0 valoarea initiala a lui S.V, #signal(S)

numarul de apeluri ale functiei signal(S) si #wait(S) numarul de apeluri

ale functiei wait(S). Atunci sunt valabili urmatorii doi invarianti:

S.V 0 (Inv1)

S.V = k + #signal(S) – #wait(S) (Inv2)

• Demonstratie:

– Initial S.V = k, k 0 si #signal(S) = #wait(S) = 0 deci Inv1 si Inv2 sunt verificati.

– wait(S) eventual descreste S.V cand S.V > 0, iar signal(S) eventual creste S.V, deci

Inv1 este adevarat in mod trivial.

– Daca se executa wait(S) si S.V este decrementat atunci #wait(S) este incrementat.

– Daca se executa signal(S) si S.V este incrementat atunci #signal(S) este incrementat.

– Daca signal(S) deblocheaza un proces q, atunci procesul q termina executia unui

wait(S), astfel ca S.V ramane neschimbat, iar #wait(S) si #signal(S) sunt

imcrementate cu 1.

– Daca wait(S) blocheaza procesul curent atunci S.V, #wait(S) si #signal(S) nu se

schimba.

2018 - 2019

Excluderea mutuala in sectiunea critica cu semafoare

• Teorema: Implementarea sectiunii critice cu semafoare este

corecta: asigura excluderea mutuala, lipsa interblocajului si

lipsa infometarii.

• Demonstratie:

• Daca #cs e numarul de procese din sectiunea critica atunci

avem invariantul:

#cs + S.V = 1 (Inv3)

• Prin inductie din structura programului rezulta ca:

#cs = #wait(S) – #signal(S)

• Combinand acest invariant cu Inv2 pentru k = 1 rezulta Inv3.

Deoarece conform Inv1 avem S.V 0 rezulta ca #cs 1, deci

excluderea mutuala este satisfacuta.

2018 - 2019

Lipsa infometarii si interblocajului in sectiunea

critica cu semafoare pentru 2 procese

• Daca am avea interblocaj, inseamna ca cele doua procese p si q

ar trebui sa fie blocate in urma executiei apelului wait(S), adica

S.V = 0.

• Deci nici unul dintre cele doua procese nu se afla in SC, adica

#cs = 0. Rezulta ca #cs + S.V = 0, contradictie cu Inv3.

• Daca unul dintre procese, fie el p, ar fi infometat, atunci el va fi

blocat indefinit la semaforul S ce va avea valoarea (0,S.L) cu p

S.L. Conform Inv3, ar rezulta ca #cs = 1 – S.V = 1 – 0 = 1.

Deci obligatoriu celalalt proces q se afla indefinit in SC. Dar in

acest fel se contrazice presupunerea de progres a lui q in SC.

2018 - 2019

Sectiunea critica cu semafoare pentru N procese

• Algoritmii pentru sectiunea critica cu N procese pentru un N arbitrar

raman identici cu cazul N = 2.

• Se verifica excluderea mutuala si lipsa interblocajului.

• Nu se verifica lipsa infometarii.

# p q r S

1 p1: wait(S) q1: wait(S) r1: wait(S) (1,)

2 p2: signal(S) q1: wait(S) r1: wait(S) (0,)

3 p2: signal(S) q1: blocked r1: wait(S) (0,{q})

4 p2: signal(S) q1: blocked r1: blocked (0,{q,r})

5 p1: wait(S) q1: blocked r2: signal(S) (0,{q})

6 p1: blocked q1: blocked r2: signal(S) (0,{p,q})

7 p2: signal(S) q1: blocked r1: wait(S) (0,{q})

Liniile 3 si 7 se repeta, p si r “coopereaza” sa-l infometeze pe q.

2018 - 2019

Asigurarea lipsei infometarii in sectiunea critica cu

semafoare

• Infometarea apare deoarece S.L este o multime din care selectia

procesului pentru deblocare se face in mod arbitrar.

• Daca S.L se implementeaza ca o coada, atunci lipsa infometarii

este asigurata. Fiecarui element din coada ii va veni la un

moment dat randul pentru deblocare.

• Observatie: daca se initializeaza S.V = k > 0 atunci cel mult k

procese se vor afla la un moment dat in SC.

• Tema: sa se verifice ca situatia de infometare nu poate sa apara

daca S.L functioneaza ca o coada.

2018 - 2019

Ordinea executiei cu semafoare

• Se considera un algoritm de calcul in care doua sarcini T1 si T2 pot fi realizate independent, iar apoi o a treia operatie T va combina rezultatele operatiilor T1 si T2.

• In mod tipic acest sablon de calcul apare in algoritmii divide et impera, cum ar fi sortarea prin interclasare.

• Impunerea ordinii corecte de executie, adica T sa astepte dupa ce T1 si T2 se termina, se poate realiza cu doua semafoare binare S1 si S2.

Ordinea operatiilor cu semafoare

binary semaphore S1 (0,), S2 (0,)

p q r

p1: executa operatia T1 p2: signal(S1)

q1: executa operatia T2 q2: signal(S2)

r1: wait(S1) r2: wait(S2) r3: executa operatia T

2018 - 2019

Semafoare slabe si semafoare tari

• Semafoarele prezentate se numesc si semafoare slabe (engl. weak

semaphores), Motivul este ca nu asigura lipsa infometarii datorita alegerii

arbitrare a procesului care va fi deblocat.

• Se pot defini semafoare tari (engl. strong semaphores) implementand pe

S.L utilizand o coada cu urmatoarele operatii: – enqueue(Q,x): depune un element x in coada Q si intoarce o noua coada Q‟

– dequeue(Q): elimina un element x din coada Q si intoarce (x, Q‟) unde Q‟ este coada

rezultata prin eliminarea lui x din Q.

wait(S):

if S.V > 0

S.V S.V – 1

else

S.L enqueue(S.L, p)

p.state blocked

signal(S):

if S.L =

S.V S.V + 1

else

(q, S.L) dequeue(S.L)

q.state ready

2018 - 2019

Semafoare busy-wait • Un semafor busy-wait nu contine componenta S.L iar S.V este identic cu S.

wait(S):

await S > 0

S S – 1

signal(S):

S S + 1

# p q S

1 p1: wait(S) q1: wait(S) 1

2 p2: signal(S) q1: wait(S) 0

3 p2: signal(S) q1: wait(S) 0

4 p1: wait(S) q1: wait(S) 1

• Un semafor busy-wait nu garanteaza lipsa infometarii in problema sectiunii critice nici pentru cazul a 2 procese. In scenariul de mai jos q este infometat, linia 4 este identica cu linia 1.

• q e selectat indefinit (echitabil), dar exact cand S = 0, a.i. nu va progresa.

2018 - 2019

Semafoare cu valori negative

• Unii autori permit ca un semafor sa aiba valoarea S.V negativa. Aceasta valoare se poate folosi pentru a determina, de exemplu, numarul de elemente aflate in multimea S.L, dupa cum se va vedea mai jos

wait(S):

S.V S.V – 1

if S.V < 0

S.L S.L { p }

p.state blocked

signal(S):

S.V S.V + 1

if S.V 0

fie un proces arbitrar q S.L

S.L S.L { q }

q.state ready

• Tema: Sa se demonstreze ca aceste definitii ale operatiilor cu semafoare verifica invariantii urmatori:

(S.V 0) (|S.L| = – S.V)

(S.V 0) (|S.L| = 0)

S.V = k + #signal – #wait – |S.L|

2018 - 2019

Semafoare in platforma Java

• Platforma Java contine o implementare a semafoarelor in

pachetul de concurenta java.util.concurrent prin clasa

Semaphore.

• Operatiile P si V (wait si signal) se numesc acquire si release.

• Operatia acquire poate genera o exceptie InterruptedException.

• Primul parametru al constructorului ce defineste valoarea

initiala a semaforului este un numar natural ce se numeste

numar de permise.

• Constructorul clasei contine un parametru suplimentar boolean

utilizat pentru a indica daca semaforul este sau nu echitabil. Un

semafor echitabil corespunde definitiei de semafor tare.

2018 - 2019

Clasa Semaphore in Java public class Semaphore {

public Semaphore(long permits);

public Semaphore(long permits, boolean fair);

public void acquire( ) throws InterruptedException;

public void acquireUninterruptibly( );

public void acquire(long permits) throws InterruptedException;

public void acquireUninterruptibly(long permits);

public boolean tryAcquire( );

public boolean tryAcquire(long timeout, TimeUnit unit);

public boolean tryAcquire(long permits);

public boolean tryAcquire(long permits, long timeout, TimeUnit unit);

public void release(long permits);

public void release( );

public long availablePermits( );

}

P

V

2018 - 2019

Numarare concurenta cu semafoare I import java.util.concurrent.Semaphore;

public class CountSem extends Thread {

static volatile int n = 0;

static Semaphore s = new Semaphore(1);

public int getN() {

return n;

}

public void run() {

int temp;

for (int i=0; i<10000000; i++) {

try {

s.acquire();

temp = n;

n = temp+1;

}

catch (InterruptedException e) {}

finally { s.release(); }

}

}

}

2018 - 2019

Numarare concurenta cu semafoare II

import java.io.*;

public class MainCountSem {

public static void main(String[] args) {

CountSem p = new CountSem();

CountSem q = new CountSem();

p.start();

q.start();

try {

p.join();

q.join();;

}

catch (InterruptedException e) {}

System.out.println("Final counter: "+p.getN());

}

}

2018 - 2019

Alte mecansime Java pentru sincronizare

• Pe langa clasa Semaphore, Java include alte doua clase utile pentru sincronizarea firelor de executie.

• Clasa CountDownLatch

• Clasa CyclicBarrier

• Clasa CountDownLatch permite ca unul sau mai multe fire sa astepte pana cand o multime de operatii ale altor fire sunt terminate.

• Tema: Cum se poate implementa functionalitatea clasei CountDownLatch folosind semafoare?

• Clasa CyclicBarrier permite firelor dintr-o multime de fire sa astepte pana cand fiecare dintre ele ajunge intr-un punct comun de bariera. Obiectul poate fi refolosit odata ce firele in asteptare au fost eliberate sa continue.

CyclicBarrier

2018 - 2019

Clasa CountDownLatch

• Clasa CountDownLatch permite ca unul sau mai multe fire sa astepte pana cand o multime de operatii ale altor fire sunt terminate.

• Numarul acestor operatii este fix si se specifica in constructorul obiectului CountDownLatch. public class CountDownLatch {

public CountDownLatch(int count);

public void await( ) throws InterruptedException;

public boolean await(long timeout, TimeUnit unit)

throws InterruptedException;

public void countDown( );

public long getCount( );

}

• Un fir care asteapta executa metoda await. Daca contorul este strict pozitiv, firul intra in asteptare. El va fi eliberat cand contorul devine zero.

• Incheierea unei operatii este semnalizata prin decrementarea contorului folosind countDown.

2018 - 2019

Exemplu de folosire CountDownLatch

• Se considera un program concurent in care exista urmatoarele categorii de fire:

• Fire semnalizatoare, in numar de 𝑚. Fiecare semnalizeaza indeplinirea unui eveniment de 𝑘 ori. Deci in total sunt semnalizate 𝑝 = 𝑚 × 𝑘 evenimente.

• Fire ascultatoare, in numar de 𝑛. Fiecare dintre aceste fire asteapta indeplinirea conditiei ca evenimentul sa fie semnalizat de 𝑝 ori, dupa care continua.

• Pentru implementare se foloseste un obiect CountDownLatch care este initializat cu 𝑝 pentru valoarea contorului.

• Fiecare fir semnalizator decrementeaza contorul pentru semnalizarea evenimentului folosind metoda countDown.

• Fiecare fir ascultator asteapta ca valoarea contorului sa devina zero folosind metoda await.

2018 - 2019

Implementarea firelor ascultatoare

class Waiter implements Runnable {

CountDownLatch latch = null;

int idx;

public Waiter(CountDownLatch latch, int i) {

this.latch = latch;

idx = i;

}

public void run() {

try {

latch.await();

} catch (InterruptedException e) {

e.printStackTrace();

}

System.out.println("Waiter "+idx+" released");

}

}

Asteapta indeplinirea conditiei

2018 - 2019

Implementarea firelor semnalizatoare class Decrementer implements Runnable {

int counter, idx;

CountDownLatch latch = null;

public Decrementer(CountDownLatch latch,int i,int counter) {

this.latch = latch;

this.counter = counter;

idx = i;

}

public void run() {

try {

for (int i = 1; i <= counter; i++) {

Thread.sleep(1000);

latch.countDown();

System.out.println("Decrementer "+idx+": Step "+i);

}

} catch (InterruptedException e) {

e.printStackTrace();

}

}

}

Semnalizarea evenimentului

2018 - 2019

Program de test CountDownLatch – structuri de date

• Se creaza firele folosind Runnable. Atunci avem doua tipuri de

obiecte “executabile”: • waiters si decrementers, vectori de obiecte ce implementeaza Runnable

• waiter_threads si decrementer_threads, vectori de fire

public class Main {

private static Waiter[] waiters;

private static Decrementer[] decrementers;

private static CountDownLatch latch;

private static Thread[] decrementer_threads;

private static Thread[] waiter_threads;

private static int counter = 15; // Valoarea p

private static int n_waiters = 20; // Valoarea n

private static int n_decrementers = 3; // Valoarea m. k = p/m = 5

// Codul functiei main ...

}

2018 - 2019

Program de test CountDownLatch – functia main public static void main(String args[]) {

latch = new CountDownLatch(counter);

// Creare waiters si decrementers

decrementers = new Decrementer[n_decrementers];

decrementer_threads = new Thread[n_decrementers];

waiters = new Waiter[n_waiters];

waiter_threads = new Thread[n_waiters];

for (int i=0; i < n_decrementers; i++) {

decrementers[i] = new Decrementer(latch,i+1,counter / n_decrementers);

decrementer_threads[i] = new Thread(decrementers[i]);

}

for (int i=0; i < n_waiters; i++) {

waiters[i] = new Waiter(latch,i+1);

waiter_threads[i] = new Thread(waiters[i]);

}

// Pornire fire

for (int i=0; i < n_waiters; i++) {

waiter_threads[i].start();

}

for (int i=0; i < n_decrementers; i++) {

decrementer_threads[i].start();

}

// Asteapta terminarea firelor folosind join ... tema !!!

}

2018 - 2019

Clasa CyclicBarrier

• Clasa CyclicBarrier permite firelor dintr-o multime de fire sa astepte pana cand fiecare dintre ele ajunge intr-un punct comun de bariera. Obiectul poate fi refolosit odata ce firele in asteptare au fost eliberate sa continue – bariera ciclica.

• Numarul firelor ce folosesc bariera este fix si se specifica in constructor. public class CyclicBarrier {

public CyclicBarrier(int parties);

public CyclicBarrier(int parties, Runnable barrierAction);

public int await( ) throws

InterruptedException, BrokenBarrierException;

public int await(long timeout, TimeUnit unit) throws

InterruptedException, BrokenBarrierException, TimeoutException;

public void reset( );

public boolean isBroken( );

public int getParties( );

public int getNumberWaiting( );

}

• Fiecare fir care foloseste bariera, asteapta la bariera prin executia metodei await.

• Cand toate firele au executat await, bariera este “eliberata”, putand fi refolosita.

• Bariera poate specifica o actiune Runnable ce se va executa automat la eliberare.

2018 - 2019

Teme

• Tema 1:

• Cum se poate implementa clasa CyclicBarrier folosind clasa

CountDownLatch ?

• Cum se poate implementa clasa CountDownLatch folosind clasa

Semaphore ?

• Tema 2: Se considera un vector 𝑣 de 𝑛 = 100000 de numere. Sa se

determine cel mai mare numar din 𝑣 folosind 𝑚 = 10 fire. Fiecare fir

𝑖 ∈ *1,2, … , 𝑚+ determina cel mai mare numar 𝑤𝑖 dintr-un subvector de

𝑝 = 𝑛/𝑚 elemente consecutive ale vectorului 𝑣 astfel: firul 1 pentru

subvectorul 𝑣1, 𝑣2, … , 𝑣𝑝 , firul 2 pentru subvectorul 𝑣𝑝+1, 𝑣𝑝+2, … , 𝑣2𝑝 ,

..., firul 𝑚 pentru subvectorul 𝑣 𝑚−1 𝑝+1, 𝑣 𝑚−1 𝑝+2, … 𝑣𝑛. Se va folosi o

bariera pentru sincronizarea celor 𝑚 fire. Rezultatul se va determina

calculand ulterior minimul vectorului 𝑤. Se observa ca aceasta metoda are

potentialul de a reduce timpul de executie al algoritmului de la 𝑂(𝑛) la

𝑂(𝑛

𝑚+ 𝑚). De ce?

2018 - 2019

Semafoare POSIX I

• Initializarea unui semafor: int sem_init(sem_t *sem, int pshared, unsigned int value);

sem = pointer catre un obiectul semafor de initializat

pshared = flag ce indica daca semaforul este/nu este paratajat de procese concurente.

value = valoarea initiala a semaforului

• Inchiderea unui semafor: int sem_destroy(sem_t *sem);

sem = pointer catre un obiectul semafor de inchis

2018 - 2019

Semafoare POSIX II

• Asteptarea la un semafor: int sem_wait(sem_t *sem);

Daca valoarea semaforului este negativa, procesul apelant se blocheaza; unul dintre procesele blocate va fi “trezit” cand un alt proces executa sem_post. Implementeaza operatia P.

• Incrementarea valorii unui semafor: int sem_post(sem_t *sem);

Incrementeaza valoarea unui semafor si „trezeste‟ un proces blocat ce asteapta la semafor, daca exista un astfel de proces.

Implementeaza operatia V.

2018 - 2019

Exemplu cu semafoare POSIX I #include <pthread.h>

#include <semaphore.h>

#define NUM_THREADS 20

int shared ;

sem_t binary_sem ; // Used like a mutex.

int thread_id[NUM_THREADS];

void *thread_function(void *arg) {

int i = *((int *)arg);

int t;

// Delay before accessing the shared resource

for (t=0;t<50000*i;t++) {}

sem_wait(&binary_sem) ; // Decrements semaphore count.

// Use shared resource.

printf("Incrementing by thread %d\n",i);

t = shared;

shared = t+1;

sem_post(&binary_sem) ; // Increments semaphore count.

}

2018 - 2019

Exemplu cu semafoare POSIX II int main () {

pthread_t thread[NUM_THREADS];

int i,t;

// Share by threads. Set semaphore to initial count 1.

sem_init(&binary_sem, 0, 1);

// Start threads here.

for (i = 0; i < NUM_THREADS; i++) {

thread_id[i] = i;

if (pthread_create(&thread[i], NULL, thread_function,

(void *)&thread_id[i]) != 0 ) {

printf("pthread_create() error\n");

return 1;

}

else {

printf("Thread %d created\n",i);

}

}

2018 - 2019

Exemplu cu semafoare POSIX III sem_wait(&binary_sem);

// Use shared resource.

printf("Incremeting by main\n");

t = shared;

shared = t+1;

sem_post(&binary_sem);

// Join with threads here.

for (i = 0; i < NUM_THREADS; i++) {

pthread_join(thread[i], NULL);

}

sem_destroy(&binary_sem);

printf("%d\n",shared);

return 0 ;

}

2018 - 2019

Problema producator - consumator

• Contine doua tipuri de procese:

– Producatori: executa instructiuni ce produc elemente de date, ce urmeaza a fi trimise la procesele consumator.

– Consumatori: dupa receptionarea unui element de date de la procesele producator, executa o instructiune ce consuma elementul respectiv

• Problema producator – consumator apare in numeroase situatii in sistemele de calcul concurente si distribuite:

– Un client Web primeste / trimite date de la / catre nivelul de comunicatie in retea

– Driver-ul unui dispozitiv de intrare transmite date catre sistemul de operare

– Un procesor de texte trimite date catre un driver de imprimanta. Ulterior, driver-ul de imprimanta trimite date catre imprimanta.

– Etc.

2018 - 2019

Zona tampon in problema producator - consumator

• Comunicarea intre producator si consumator poate fi sincrona sau asincrona.

• In comunicarea sincrona, producatorul si consumatorul trebuie sa se coordoneze. Comunicarea nu va avea loc decat atunci cand ambele procese sunt gata sa schimbe un element de date.

• In comunicarea asincrona, schimbul de informatie are loc printr-o zona tampon numita buffer. Tamponul are functiile unei cozi: producatorul depune elemente in spatele cozii, iar consumatorul preia elemente din fata cozii.

• Exista doua probleme ce necesita atentie:

– Consumatorul nu poate prelua un element dintr-un tampon gol

– Producatorul nu poate depune un element intr-un tampon plin

2018 - 2019

Producator – consumator cu semafoare si zona tampon finita

semaphore notEmpty (0,) semaphore notFull (N,) finite queue of dataType buffer empty queue

p q

dataType d loop forever p1: d produce p2: wait(notFull) p3: append(d,buffer) p4: signal(notEmpty)

dataType d loop forever q1: wait(notEmpty) q2: d take(buffer) q3: signal(notFull) q4: consume(d)

Producator – consumator cu zona tampon finita

Sursa: M.Ben-Ari, 2006 • Tema: sa se demonstreze corectitudinea acestui algoritm.

– Nu se extrage un element dintr-un tampon vid

– Nu se depune un element intr-un tampon plin

– Nu exista interblocare

2018 - 2019

Semafoare divizate

• Algoritmul de rezolvare a problemei producator – consumator cu semafoare introduce tehnica semafoarelor divizate (engl. split semaphore).

• El se refera la o tehnica de sincronizare folosind un grup de doua sau mai multe semafoare ce satisfac un invariant:

“suma lor este (cel mult) egala cu o valoare fixa N”

• In cazul problemei producator – consumator, conditia urmatoare este indeplinita la inceputul corpurilor celor doua bucle:

notEmpty.V + notFull.V = N

• Tema: sa se demonstreze ca acest invariant (cu ) este adevarat.

• Daca N = 1 atunci avem un semafor binar cu divizare.

• Observatie: In exluderea mutuala se foloseste un singur semafor binar, iar instructiunile pereche wait si signal se executa intr-un singur proces. Pentru sincronizare in problema producator-consumator, o instructiune wait intr-un proces este imperecheata cu signal in celalalt process.

2018 - 2019

Cina filosofilor

loop forever p1: think p2: preprotocol p3: eat p4: postprotocol

Problema cinei filosofilor

• Un filosof poate apuca furculitele numai una cate una si are nevoie de doua furculite sa poata manca.

• Proprietati de corectitudine:

– Un filosof mananca numai cand are doua furculite

– Excludere mutuala: doi filosofi nu pot detine simultan aceeasi furculita

– Lipsa interblocajului

– Lipsa infometarii

– Comportament eficient in lipsa conflictelor pe furculite

Fil3

furc1

Fil4 Fil2

Fil1 Fil0

furc4

furc0 furc2

furc3

spaghete

2018 - 2019

Cina filosofilor (varianta I)

Filosof i ( i {0,1,2,3,4} )

semaphore array[0..4] fork [1,1,1,1,1]

loop forever p1: think p2: wait(fork[i]) p3: wait(fork[i+1]) p4: eat p5: signal(fork[i]) p6: signal(fork[i+1])

Problema cinei filosofilor – varianta I

• Este posibil sa apara interblocaj, care va conduce si la infometarea tuturor filosofilor. Daca fiecare filosof apuca furculita din stanga fork[i] inainte ca oricare din ei sa apuce furculita din dreapta, atunci toti vor intra in asteptare pentru furculita din dreapta.

• Teorema: Nici o furculita nu va fi detinuta simultan de doi filosofi.

Demonstratie:

• Daca #Fi este numarul de filosofi ce detin furculita i atunci #Fi = #wait(fork[i]) – #signal(fork[i]). Din invariantul semaforului fork[i] rezulta ca fork[i].V = 1 – #Fi de unde #Fi = 1 – fork[i].V. Dar fork[i].V 0 de unde #Fi 1.

2018 - 2019

Cina filosofilor (varianta II)

Filosof i ( i {0,1,2,3,4} )

semaphore array[0..4] fork [1,1,1,1,1] semaphore room 4

loop forever p1: think p2: wait(room) p3: wait(fork[i]) p4: wait(fork[i+1]) p5: eat p6: signal(fork[i]) p7: signal(fork[i+1]) p8: signal(room)

Problema cinei filosofilor – variantele II & III & IV

• Pentru a asigura lipsa infometarii se introduce un semafor room care limiteaza la 4 numarul de filosofi care pot cina la un moment dat.

• Teorema: Acest algoritm asigura lipsa infometarii filosofilor

• Demonstratie:

• Tema !

• Varianta III – este o solutie asimetrica in care primii 4 filosofi sunt identici cu varianta I, iar al 5-lea filosof asteapta intai pentru furculita din dreapta fork[0] si apoi pentru cea din stanga fork[4].

• Varianta IV – filosofii dau cu banul pentru a alege ce furculita asteapta intai.

2018 - 2019

Teme I

• Tema 1: Sa se implementeze problema producator-consumator folosind semafoare.

• Se considera ca avem 𝑝 fire producatoare care impreuna produc 𝑛 litere mari aleatoare astfel incat 𝑝 < 𝑛. Fie 𝑛 = 𝑝𝑞 + 𝑟 unde 𝑞 si 𝑟 reprezinta catul si restul impartirii lui 𝑛 la 𝑝. Fiecare fir producator va produce 𝑞 sau 𝑞 + 1 litere, astfel incat 𝑝 − 𝑟 fire produc cate 𝑞 litere, iar celelalte 𝑟 fire produc cate 𝑞 + 1 litere.

• Cele 𝑛 litere sunt consumate de catre 𝑐 fire consumatoare astfel incat 𝑐 < 𝑛. Fie 𝑛 = 𝑐𝑞′ + 𝑟′ unde 𝑞′ si 𝑟′ reprezinta catul si restul impartirii lui 𝑛 la 𝑐. Fiecare fir consumator va consuma 𝑞′ sau 𝑞′ + 1 litere, astfel incat 𝑐 − 𝑟′ fire consuma cate 𝑞′ litere, iar celelalte 𝑟′ fire consuma cate 𝑞′ + 1 litere.

2018 - 2019

Teme II

• Tema 2: Sa se dezvolte un program concurent in Java care modeleaza fiecare filosof din problema filosofilor folosind cate un fir. Pentru sincronizarea firelor se vor folosi semafoare Java. Se vor consdera toate variantele care evita infometarea:

• Varianta cu limitarea numarului de filosofi care pot manca la un moment dat

• Varianta asimetrica

• Varianta stocastica

• Tema 3: Sa se implementeze semafoarele in Promela. Sa se verifice corectitudinea implementarii sectiunii critice folosind semafoare in Promela.