Esercizio - Output ed ordine di esecuzione con i semafori (eserciziario, esercizi 6, 7 e 8)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizi 6, 7 e 8). Teoria: Semafori, monitor e problemi classici di sincronizzazioneUn semaforo è un intero accessibile solo con due operazioni atomiche, wait (P: aspetta finché S > 0 e decrementa) e signal (V, in POSIX sem_post: incrementa); il semaforo contatore ha valori illimitati, quello binario vale 0 o 1; con valore iniziale 1 realizza la mutua esclusione, con valore iniziale 0 impone un ordine di esecuzione (S1 prima di S2); senza attesa attiva ogni semaforo ha una coda di processi sospesi (sleep e wakeup); i semafori si usano male con facilità (ordine sbagliato, omissioni); il monitor è un tipo di dato astratto in cui un solo processo alla volta è attivo e le variabili condizione x.wait()/x.signal() sospendono e risvegliano (in POSIX mutex più pthread_cond_t); le anomalie di liveness sono deadlock, starvation e inversione di priorità; i problemi classici sono produttore-consumatore a buffer limitato (mutex, vuote = n, piene = 0; l'ordine delle wait è importante), lettori-scrittori (rw_mutex, mutex, read_count; i lettori possono far morire di fame gli scrittori) e filosofi a cena (la soluzione ingenua con un semaforo per bacchetta va in deadlock; si evita limitando a n-1 filosofi, rompendo la simmetria o ordinando le risorse), con soluzioni in C (POSIX) e in Go (canali e sync).Semafori, monitor e problemi classici di sincronizzazione →.

Esercizio 6. Risorse condivise: semafori $S, T, U$ e int x = 100.

Processo P1:                 Processo P2:        Processo P3:
  wait(S);                     wait(T);            wait(U);
  if (x == 0)                  x := x - 1;         x := x + 1;
      signal(T);               signal(S);          signal(S);
  else
      signal(U);
  wait(S);
  write(x);

I tre processi girano concorrentemente sulla stessa CPU. Qual è l'output con $S=1$, $T=0$, $U=0$? Se invece i semafori fossero inizializzati a $S=0$, $T=1$, $U=1$, si può avere una race condition?

Esercizio 7. Semafori $s1 = s2 = 0$.

process P1 {                 process P2 {
    signal(s1);                  signal(s2);
    wait(s2);                    wait(s1);
    print "P";                   print "A";
    wait(s2);                    signal(s2);
    print "R";                   wait(s1);
    signal(s1);                  print "I";
}                            }

Descrivere il comportamento e i possibili output dell'esecuzione parallela di $P_1$ e $P_2$.

Esercizio 8. Semafori $M, S, T, U$ e int x = 0.

Processo P1:          Processo P2:          Processo P3:
  while (1) {           while (1) {           wait(U);
    wait(S);              wait(T);            while (1) {
    wait(M);              wait(M);              wait(M);
    x = x + 1;            write(x);             x = 0;
    signal(M);            signal(M);            signal(M);
    signal(T);            signal(S);          }
  }                     }

Qual è l'output se i semafori sono inizializzati (1) $M=1, S=1, T=0, U=0$; (2) $M=1, S=0, T=1, U=0$; (3) $M=1, S=1, T=0, U=1$? Qual è il ruolo del semaforo $M$?

Esercizio 6

Con $S=1, T=0, U=0$:

$P_2$ resta bloccato per sempre su wait(T) ($T$ non viene mai incrementato). Output: 101. $P_1$ "risveglia" $P_3$, che incrementa $x$ e a sua volta "risveglia" $P_1$.

Con $S=0, T=1, U=1$. $P_1$ si blocca subito su wait(S). Invece $P_2$ (per $T=1$) e $P_3$ (per $U=1$) possono entrambi avanzare: modificano $x$ senza nessun semaforo comune che li escluda a vicenda ($T$ e $U$ sono semafori diversi e sono entrambi "aperti"). Quindi sì, c'è una race condition su $x$: x = x - 1 e x = x + 1 sono sequenze lettura-modifica-scrittura intrecciabili, e il risultato può essere 99, 100 o 101 (aggiornamento perso). Chi segnala per primo $S$ (uno dei due) sveglia $P_1$, che stampa un valore che dipende dall'intreccio; il secondo signal(S) lascia $S$ a 1 e il secondo wait(S) di $P_1$ passa senza aspettare che l'altro processo abbia finito.

Esercizio 7

Traccia (le due sequenze iniziali sono concorrenti):

1. $P_1$ esegue signal(s1) ($s1 = 1$); $P_2$ esegue signal(s2) ($s2 = 1$), in qualunque ordine.
2. $P_1$ fa wait(s2): passa ($s2 = 0$); $P_2$ fa wait(s1): passa ($s1 = 0$).
3. $P_1$ stampa P, $P_2$ stampa A: l'ordine tra queste due è libero.
4. $P_1$ fa il secondo wait(s2): $s2 = 0$, si blocca; $P_2$ fa signal(s2), dopo aver stampato A. Ora $P_1$ passa e stampa R.
5. $P_1$ esegue signal(s1); solo allora $P_2$ passa il secondo wait(s1) e stampa I.

Perciò R viene dopo A e dopo P, e I viene dopo R: gli unici output possibili sono PARI e APRI. Enumerando tutti gli intrecci possibili con un programma (stato dei semafori e posizione di ogni processo) si trovano esattamente queste due stringhe e nessun deadlock.

Esercizio 8

Il semaforo $M$ è un mutex (valore 1): protegge l'accesso alla variabile condivisa $x$ da parte dei tre processi. $S$ e $T$ fanno alternare $P_1$ e $P_2$ (un incremento, una stampa, un incremento...): $P_1$ aspetta $S$ e segnala $T$; $P_2$ aspetta $T$ e segnala $S$; $U$ abilita l'azzeramento di $P_3$.

1. $M=1, S=1, T=0, U=0$. $P_1$ parte: $x = 1$, signal(T); $P_2$ stampa 1, signal(S); $P_1$: $x = 2$; ... $P_3$ è bloccato per sempre su wait(U). Output: 1 2 3 4 ... (sequenza infinita dei naturali da 1).
2. $M=1, S=0, T=1, U=0$. Parte $P_2$: stampa $x = 0$, signal(S); poi $P_1$ incrementa a 1 e segnala $T$; $P_2$ stampa 1. Output: 0 1 2 3 ....
3. $M=1, S=1, T=0, U=1$. $P_3$ può girare: quando riesce a prendere $M$ azzera $x$ ($x = 0$), quindi la sequenza viene azzerata in momenti non deterministici: l'output è del tipo $(0)\ 1\ 2\ \dots\ n_1\ (0)\ 1\ 2\ \dots\ n_2 \dots$ con $n_i \ge 0$ (se $n_i = 0$ la sotto-sequenza è vuota). Esempi: 0 0 0 ... (azzera sempre prima di ogni stampa), 1 1 1 ..., 0 1 2 0 1 2 3 .... Il mutex $M$ garantisce solo che gli accessi a $x$ non si sovrappongano, non l'ordine.

Domande d'esame

Perché in 6 con $S=0, T=1, U=1$ c'è una race condition e con $S=1, T=0, U=0$ no? Traccia. Nel secondo caso solo $P_1$ e poi $P_3$ toccano $x$, uno dopo l'altro (i semafori impongono l'ordine); nel primo $P_2$ e $P_3$ sono entrambi abilitati e nessun semaforo comune ne protegge l'accesso.