comert electronic si securitatea datelor - software.ucv.rosoftware.ucv.ro/~cbadica/scd/cap4.pdf ·...
Post on 31-Aug-2019
20 Views
Preview:
TRANSCRIPT
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.
top related