Esercizio - Valori finali di x e y con semafori e processi concorrenti (eserciziario, esercizi 99 e 110)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizi 99 e 110). 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 99. Tre processi $A$, $B$, $C$ si sincronizzano con i semafori Sem1, Sem2, Sem3 (inizializzati a 0) e operano sulle variabili condivise $x$, $y$, $z$ inizializzate a $x = 1$, $y = 2$, $z = 1$:

Process A {                  Process B {                  Process C {
    P(Sem1);                     P(Sem2);                     V(Sem2);
    z = (x - z) * y;             x = x + y;                   P(Sem3);
    x = x + z + y;               z = x - z;                   x = x / y;
    V(Sem3);                     y = (y - z) + x;             y = 2*z + x;
    P(Sem1);                     Print(y);                    V(Sem1);
    x = x + y;                   V(Sem1);                     z = x + z;
    Print(x);                }                                Print(z);
}                                                         }

Con quale ordine i processi stampano i valori? Qual è il valore finale delle tre variabili?

Esercizio 110. Due processi condividono la variabile $x$ ($= 1$ inizialmente); $P$ = wait, $V$ = signal; SemA e SemC sono inizializzati a 0, SemB e Mutex a 1.

P1:                          P2:
 1: P(SemA)                   8: P(SemB)
 2: P(Mutex)                  9: P(Mutex)
 3: if (x < 0) x = x + 1     10: x = x - 2
 4: V(Mutex)                 11: V(Mutex)
 5: V(SemC)                  12: V(SemA)
 6: P(SemA)                  13: P(SemC)
 7: print(x)                 14: P(Mutex)
                             15: x = x - 1
                             16: V(Mutex)
                             17: print(x)

I due processi sono eseguiti in modo concorrente. Si elenchino i possibili ordini di esecuzione delle istruzioni (per esempio 1 8 2 10 ...) motivando la risposta.

Esercizio 99

Chi parte e chi aspetta. $B$ attende Sem2, che solo $C$ incrementa con la sua prima istruzione: quindi $C$ parte per primo, poi $B$. $A$ attende Sem1, incrementato solo da $B$ (alla fine) e da $C$ (dopo P(Sem3)). $C$ attende Sem3, incrementato da $A$. Quindi il primo V(Sem1) viene necessariamente da $B$ (quello di $C$ è dopo P(Sem3), che richiede il V(Sem3) di $A$, che richiede un V(Sem1)): l'ordine delle fasi è $C_1 \to B \to A_1 \to C_2 \to \{A_2, C_3\}$.

Calcolo passo-passo ($x = 1, y = 2, z = 1$):

Da qui in poi $A$ (seconda parte) e $C$ (ultime due istruzioni) sono concorrenti:

• $A$: P(Sem1) passa, x = x + y = 3 + 9 = 12, Print(x) stampa 12;
• $C$: z = x + z: se $C$ lo esegue prima dell'aggiornamento di $x$ di $A$, $z = 3 + 3 = 6$; se dopo, $z = 12 + 3 = 15$; Print(z) stampa 6 oppure 15.

Risposte. Il processo $B$ stampa $y = 3$ per primo. Non si può dire chi stampa per secondo e per terzo tra $A$ ($x = 12$) e $C$ ($z = 6$ oppure $15$). Stato finale: $x = 12$, $y = 9$, $z = 6$ oppure $15$ (a seconda di quale processo avanza per primo tra $A$ e $C$). L'enumerazione di tutti gli intrecci conferma le quattro combinazioni: output $\{3, 12, 6\}$ o $\{3, 12, 15\}$ con $A$ e $C$ in entrambi gli ordini.

Errore nella soluzione del corso. La slide scrive "il risultato finale sarà $x = 12$ e $y = 3$": ma $y$ vale 9 alla fine (l'istruzione y = 2z + x di $C$ lo porta a 9 e nessuno lo cambia più; nella stessa slide il passo è annotato = 9). Il valore corretto è $y = 9$.

Esercizio 110

Si ragiona sui semafori:

• P1 istruzione 1 attende SemA (0): si sblocca solo con V(SemA) di P2 (istruzione 12);
• P2 può iniziare subito: SemB = 1, Mutex = 1.

Sequenza forzata. P2 esegue 8, 9, 10, 11, 12 (nessuno lo interrompe in modo significativo: P1 è bloccato su 1 finché non c'è 12). Dopo 12 P1 può proseguire e P2 va a 13, che attende SemC (0), incrementato solo da P1 all'istruzione 5. Quindi: P1 esegue 1, 2, 3, 4, 5 (per x: dopo 10 vale $-1$, x < 0 è vero, quindi 3 porta $x$ a 0); poi P2 completa 13, 14, 15, 16, 17 ($x = -1$, stampa $-1$).

Ordine completo. $8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 13, 14, 15, 16, 17$, con le istruzioni di P1 1 .. 5 che possono anche iniziare ("1" bloccato) prima di 8 (cioè P1 esegue P(SemA) e resta fermo): quello che conta è il momento in cui l'istruzione 1 termina, che è dopo 12. Il corso elenca "8:12 oppure 1 8:12 ... dopo 12 può esserci 2 oppure 13 ... in 13 sicuro P2 si blocca", cioè più "ordini" che differiscono solo per il momento in cui si comincia a tentare l'istruzione bloccata; nell'ordine di completamento l'ordine è unico.

Lo stallo finale. Dopo 17 P2 termina; P1 è alla istruzione 6, P(SemA): SemA vale 0 (c'è stato un solo V(SemA), all'istruzione 12, già consumato dall'istruzione 1) e nessun processo lo incrementerà più: P1 resta bloccato per sempre e non stampa mai (istruzione 7). Il corso non lo segnala; con i valori dati il sistema finisce in deadlock (parziale: termina P2, resta bloccato P1). Output: solo P2 stampa $x = -1$. Verificato enumerando tutti gli intrecci: l'unica traccia completa è quella indicata, e termina sempre con P1 bloccato su 6.

Domande d'esame

In 99, perché $y = 9$ alla fine e non 3? Traccia. $y$ è modificato da $B$ (porta a 3) e poi da $C$ con y = 2z + x $= 2\cdot3 + 3 = 9$; dopo non viene più cambiato. Il valore 3 è quello stampato da $B$, non il finale.