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 P_i 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₁ chiama p(3, 10) che porta sem=1 e restituisce 0
• P₁ chiama p(4, 20) che porta sem=0 e restituisce 0
• P₁ chiama p(4, 30) e si blocca
• P₂ chiama p(7, 15) e si blocca
• P₃ chiama v(14) che sblocca il processo P₂, in quanto 7 > 4. La funzione p() restituisce a P₂ il valore 14 e la funzione v() restituisce a P₃ il valore 15
• P₃ chiama v(35) che sblocca il processo P₁. La funzione p() restituisce a P₁ il valore 35 e la funzione v() restituisce a P₃ il valore 30
• P₃ chiama v(16) che porta sem=1 e restituisce 0

soluzione_es1.c

#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 C_i 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:

• C₁ chiama bConsume() e si blocca
• C₂ chiama bConsume() e si blocca
• P chiama bProduce(21) che sblocca i processi C₁ e C₂ bloccati su bConsume(). La funzione bConsume() restituirà a entrambi i processi il valore 21
• P chiama bProduce(12) e si blocca
• C₂ chiama bConsume() che sblocca il processo P e restituisce a C₂ il valore 12
• C₁ chiama la funzione bConsume() e si blocca

soluzione_es2.c

int 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 P_i 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:

• P₁ chiama val(3) e si blocca
• P₂ chiama val(5) e si blocca
• M chiama mul(2) che sblocca i processi P₁ e P₂ bloccati su val(). Le due funzioni val() restituiranno rispettivamente ai processi chiamanti, P₁ e P₂, i valori 3*2=6 e 5*2=10
• M chiama mul(3) e si blocca
• P₂ chiama val(4) che sblocca il processo M e restituisce immediatamente a P₂ il valore 4*3=12

soluzione_es3.c

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 P_i 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 P_i, 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:

• P₁ chiama wait(3,2) e si blocca
• P₂ chiama wait(3,4) e si blocca
• P₃ chiama wait(5,2) e restituisce immediatamente -1, in quanto il numero totale di processi bloccati è 2 che non è inferiore al valore max_proc=2
• P₃ chiama wait(5,3) e si blocca
• P₄ chiama sblock(3,6) che sblocca i processi P₁ e P₂ i quali restituiscono entrambi il valore 6. La funzione sblock restituisce, invece, il valore 2
• P₁ chiama sblock(2,7) la quale restituisce immediatamente il valore -1 perché non sblocca nessun processo

soluzione_es4.c

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