In questa sezione verranno presentati una serie di esercizi svolti di programmazione concorrente utilizzando uno pseudo linguaggio simile al C. Le funzioni P()
e V()
hanno le stesso comportamento delle funzioni POSIX sem_wait()
e sem_post()
, rispettivamente. Si ipotizzi che sia possibile definire ed inizializzare un semaforo con uno pseudo-statement del tipo: sem_t <nome_semaforo> = <valore_iniziale>;
. Le variabili con nome m
(m
, m1
, m2
) rappresentano dei semafori utilizzati come dei mutex.
Nello svolgimento di tutti gli esercizi si ipotizzi che i thread che realizzano il programma concorrente siano stati già creati. Ad un programma completo occorrerebbe aggiungere alle soluzioni qui riportate la la funzione pthread_create() per la creazione dei thread.
Un numero imprecisato di processi Pi possono chiamare le funzioni int p(int prio, int value_p)
e int v(int value_v)
. Esse dovranno simulare, a partire dai semafori ordinari (su cui è supposto un accodamento FIFO), il comportamento di semafori che accodano in base alla priorità prio
argomento della funzione p()
(0 < = prio < = 9
, prio=9
è la massima priorità).
Il comportamento delle due funzioni è di seguito descritto:
int p(int prio, int value_p)
: quando il valore del semaforo è un numero maggiore di 0 la funzione decrementa di un'unità tale valore e restituisce 0. Nel caso in cui il semaforo sia uguale a 0 la funzione è bloccante. Quando sbloccata da v()
, p()
dovrà restituire al chiamante il valore value_v
passato come argomento alla funzione v()
.int v(int value_v)
: se eseguita quando non vi è nessun processo bloccato su p()
, la funzione incrementa di un'unità il valore del semaforo e restituisce il valore 0. Nel caso in cui esista almeno un processo bloccato su p()
, la funzione dovrà liberare il processo bloccato con maggior priorità e restituire il valore value_p
passato come argomento alla funzione p()
. Nel caso di più processi bloccati con la stessa priorità la scelta del processo da sbloccare è libera.
Il semaforo ha valore iniziale 2
.
Si realizzino le funzioni int p(int prio, int value_p)
e int v(int value_v)
.
Esempio:
p(3, 10)
che porta sem=1
e restituisce 0
p(4, 20)
che porta sem=0
e restituisce 0
p(4, 30)
e si bloccap(7, 15)
e si bloccav(14)
che sblocca il processo P2, in quanto 7 > 4
. La funzione p()
restituisce a P2 il valore 14
e la funzione v()
restituisce a P3 il valore 15
v(35)
che sblocca il processo P1. La funzione p()
restituisce a P1 il valore 35
e la funzione v()
restituisce a P3 il valore 30
v(16)
che porta sem=1
e restituisce 0
#define NPRIO 10 sem_t wait[NPRIO]={0,0....}; int nBlockedPrio[NPRIO]={0,0,...}; int nBlocked=0; int pass = 0; int sem=2; sem_t sync=0; int p(int prio, int value_p){ int ret; P(m); if(sem==0){ nBlocked++; nBlockedPrio[prio]++; V(m); P(wait[prio]); ret=pass; pass=value_p; V(sync); return ret; }else{ sem--; V(m); return 0; } } int v(int value_v){ int ret; P(m); if(nBlocked){ for(i=NPRIO-1; i>=0; i--){ if (nBlockedPrio[i]){ nBlockedPrio[i]--; nBlocked--; pass = value_v; V(wait[i]); P(sync); ret=pass; V(m); return ret; } } }else{ sem++; V(m); return 0; } }
Un numero imprecisato di processi Ci possono chiamare la funzione int bConsume()
e un processo P può chiamare la funzione void bProduce(int value)
.
Il comportamento delle due funzioni è di seguito definito:
int bConsume()
è bloccante nell'attesa che venga chiamata dal processo P la funzione bProduce(int value)
. La funzione bProduce(int value)
, quando chiamata, sbloccherà tutti i processi bloccati su int bConsume()
, la quale dovrà restituire ad ogni processo sbloccato il valore value
passato come argomento alla funzione bProduce(int value)
.bProduce(int value)
, nel caso ci siano dei processi bloccati su int bConsume()
, dovrà sbloccarli passando ad essi il valore value
. Nel caso nessun processo sia bloccato sulla funzione int bConsume()
, essa dovrà essere bloccante nell'attesa che un processo esegua int bConsume()
. Una volta sbloccata, la funzione bProduce(int value)
dovrà passare il valore value
alla funzione int bConsume()
la quale, non bloccandosi, lo restituirà al processo chiamante.
Si realizzino le funzioni int bConsume()
e bProduce(int value)
.
Esempio:
bConsume()
e si bloccabConsume()
e si bloccabProduce(21)
che sblocca i processi C1 e C2 bloccati su bConsume()
. La funzione bConsume()
restituirà a entrambi i processi il valore 21bProduce(12)
e si bloccabConsume()
che sblocca il processo P e restituisce a C2 il valore 12bConsume()
e si bloccaint pBlocked=0, cBlocked=0, pass; sem_t pWait=0, cWait=0; sem_t m=1, m2=1; void bProduce(int value){ int localCBlocked, c; P(m); if(cBlocked==0){ pBlocked++; V(m); P(cWait); } localCBlocked = cBlocked; pass = value; for(c=0; c<localCBlocked; c++) V(pWait); } int bConsume() { int ret; P(m); cBlocked++; if(pBlocked){ pBlocked--; V(cWait); }else{ V(m); } P(pWait); P(m2); cBlocked--; ret = pass; if(cBlocked==0) V(m); V(m2); }
Un numero imprecisato di processi Pi possono chiamare la funzione int val(int v)
e un processo M può chiamare la funzione void mul(int m)
.
Il comportamento delle due funzioni è di seguito definito:
int val(int v)
è bloccante nell'attesa che venga chiamata dal processo M la funzione void mul(int m)
. Quando la funzione void mul(int m)
è chiamata dal processo M, essa dovrà sbloccare tutti i processo P bloccati fino a quell'istante su int val(int v)
. Ad ogni processo P la funzione int val(int v)
dovrà restituire il valore v
moltiplicato per il valore m
.void mul(int m)
, oltre al comportamento descritto nel precedente punto, nel caso in cui non ci sia nessun processo bloccato su int val(int v)
, essa dovrà essere bloccante nell'attesa che un processo di tipo P chiami la funzione int val(int v)
. Quando tale evento accade il processo M dovrà essere sboccato e la funzione int val(int v)
, chiamata dal processo P, dovrà restituire immediatamente il valore v*m
.
Si realizzino le funzioni int val(int v)
e void mul(int m)
.
Esempio:
val(3)
e si bloccaval(5)
e si bloccamul(2)
che sblocca i processi P1 e P2 bloccati su val()
. Le due funzioni val()
restituiranno rispettivamente ai processi chiamanti, P1 e P2, i valori 3*2=6
e 5*2=10
mul(3)
e si bloccaval(4)
che sblocca il processo M e restituisce immediatamente a P2 il valore 4*3=12
sem_t m1=1, m2=1, sync=0, syncMul=0; int n=0, s=0, mean=0, meanBlock=0; int sum(int x){ int ret; P(m1); if(meanBlock){ s=x; V(syncMul); ret = mean; P(sync); V(m1); return ret; }else{ s += x; n++; V(m1); P(sync); ret = mean; P(m2) n--; if(n==0) V(m1); V(m2); return ret; } } mul(int m){ int c; P(m1); if(n>0){ mean = s*m; for (c=0; c<n;c++){ V(sync); } }else{ meanBlock+=1; V(m1); P(syncMul); mean = s*m; V(sync); } }
Un numero imprecisato di processi Pi possono chiamare le funzioni int wait(int w_prio, int max_proc)
e int sblock(int s_prio, int value)
. I parametri w_prio
e s_prio
possono assumere valori compresi tra 0 e 9.
Il comportamento delle due funzioni è di seguito definito:
int wait(int w_prio, int max_proc)
è bloccante se il numero totale di processi da essa bloccati fino all'istante della sua chiamata è inferiore a max_proc
, alternativamente restituisce il valore -1. Se i processi bloccati su wait
vengono sbloccati dalla funzione sblock
, la funzione wait
deve restituire il valore value
passato come argomento alla funzione sblock
.int sblock(int s_prio, int value)
sblocca tutti i processi bloccati dalla funzione wait
con valore w_prio
uguale a s_prio
. La funzione wait
dovrà restituire a tutti i processi sbloccati il valore value
. La funzione sblock
restituisce il numero di processi sbloccati, -1 nel caso in cui nessun processo sia sbloccato.
Si presti particolare attenzione al fatto che il valore value
sia restituito correttamente a tutti i processi sbloccati e che i processi Pi, che eseguono la funzione wait
dopo una funzione sblock
, siano correttamente bloccati dalla funzione wait
.
Si realizzino le funzioni int wait(int w_prio, int max_proc)
e int sblock(int s_prio, int value)
.
Esempio:
wait(3,2)
e si bloccawait(3,4)
e si bloccawait(5,2)
e restituisce immediatamente -1, in quanto il numero totale di processi bloccati è 2 che non è inferiore al valore max_proc=2
wait(5,3)
e si bloccasblock(3,6)
che sblocca i processi P1 e P2 i quali restituiscono entrambi il valore 6. La funzione sblock
restituisce, invece, il valore 2sblock(2,7)
la quale restituisce immediatamente il valore -1 perché non sblocca nessun processo#define N_CLASSES 10 int value_pass; int nwait = 0; int nwait_prio[N_CLASSES] = {0,0,...}; sem_t sync[N_CLASSES] = {0,0,...}; sem_t mutex = 1, mutex2 = 1; int wait(int w_prio, int max_proc){ int res; P(mutex); if (nwait >= max_proc){ V(mutex); return -1; }else{ nwait_prio[w_prio]++; nwait++; V(mutex); P(sync[w_prio]); P(mutex2); res = value_pass; nwait--; nwait_prio[w_prio]--; if (nwait_prio[w_prio]==0) V(mutex); V(mutex2); return res; } } int sblock(int s_prio, int value){ int c, res; P(mutex); if (nwait_prio[s_prio] > 0){ res = nwait_prio[s_prio]; value_pass = value; for(c=0; c<res; c++){ V(sync[w_prio]); } }else{ res = 0; V(mutex); } return res; }