Esercizio - Deadlock tra due processi con lock incrociati (eserciziario, esercizi 92 e 116)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizi 92 e 116: lo stesso problema in due versioni). Due processi concorrenti condividono tre variabili intere $x = y = z = 0$ e due semafori $lock1 = lock2 = 1$:

process foo {                    process bar {
    z = z + 2;                       P(lock2);
    P(lock1);                        y = y + 1;
    x = x + 2;                       P(lock1);
    P(lock2);                        x = x + 1;
    V(lock1);                        V(lock1);
    y = y + 2;                       V(lock2);
    V(lock2);                        z = z + 1;
}                                }

($P$ = wait, $V$ = signal). Può avvenire deadlock? Come? Quali sono i valori possibili di $(x, y, z)$ in caso di deadlock? Teoria: Deadlock - condizioni, prevenzione, evitamento e rilevamentoUn deadlock (stallo) è una situazione in cui un insieme di processi attende all'infinito risorse possedute da altri processi dello stesso insieme; può verificarsi solo se valgono insieme quattro condizioni (mutua esclusione, hold and wait, assenza di prelazione, attesa circolare); il grafo di allocazione delle risorse (archi di richiesta P->R e di assegnazione R->P) senza cicli esclude lo stallo, con un ciclo lo implica se ogni risorsa ha una sola istanza, e lo rende solo possibile se ha più istanze; si può prevenire (negare una delle quattro condizioni, per esempio ordinare le risorse per negare l'attesa circolare), evitare (stato sicuro: esiste una sequenza sicura; algoritmo del grafo con archi di rivendicazione per istanza singola, algoritmo del banchiere con Available, Max, Allocation, Need = Max - Allocation e complessità O(m n^2) per istanze multiple), rilevare e ripristinare (grafo wait-for per istanza singola, algoritmo di rilevamento per istanze multiple; terminazione dei processi o prelazione delle risorse con scelta della vittima e rollback), oppure ignorare.Deadlock - condizioni, prevenzione, evitamento e rilevamento →, 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 →.

Svolgimento

Il deadlock è possibile. I due processi prendono i due lock in ordine opposto: foo prende $lock1$ e poi $lock2$ (con $lock1$ ancora tenuto), bar prende $lock2$ e poi $lock1$ (con $lock2$ ancora tenuto). Se foo esegue P(lock1) e bar esegue P(lock2) prima che l'altro prenda il secondo, ognuno aspetta il lock tenuto dall'altro: è la situazione dei filosofi simmetrici, un'attesa circolare. Le operazioni $V$ non c'entrano: per trovare il deadlock bisogna guardare le $P$ di semafori diversi in ordine diverso. Naturalmente i processi possono anche non andare in deadlock (se uno prende entrambi i lock prima che l'altro cominci).

Valori in caso di deadlock. Si guarda fino a dove arriva ciascun processo quando entrambi sono bloccati:

• foo è bloccato su P(lock2): ha già eseguito z = z + 2 e x = x + 2 (dopo P(lock1)), ma non ancora y = y + 2;
• bar è bloccato su P(lock1): ha eseguito P(lock2) e y = y + 1, ma non x = x + 1 né z = z + 1.

Quindi $x = 2$ (solo foo), $y = 1$ (solo bar), $z = 2$ (solo foo): $(x, y, z) = (2, 1, 2)$. È l'unico stato di deadlock possibile: finché nessuno dei due ha preso un lock, gli incrementi precedenti sono quelli fissi, e fino al punto del blocco non ci sono corse, quindi il risultato è unico (le istruzioni su variabili diverse non interferiscono). Il corso conferma: "(2,1,2); fino a quel punto non ci sono state corse, quindi il risultato è unico".

Conferma per enumerazione. Enumerando tutti gli intrecci possibili dei 7 passi di foo e dei 7 di bar, 10 sequenze finiscono in deadlock e tutte con $(x,y,z) = (2,1,2)$; gli altri intrecci arrivano alla fine con $(3,3,3)$. Quindi: deadlock con $(2,1,2)$ oppure termine con $(3,3,3)$.

Come eliminare il deadlock. Imporre lo stesso ordine di acquisizione ai due processi (sempre $lock1$ poi $lock2$): nega l'attesa circolare. Per esempio bar diventa P(lock1); P(lock2); y = y + 1; x = x + 1; V(lock2); V(lock1); z = z + 1;.

Domande d'esame

Il deadlock dipende dalla velocità dei processi? Come lo si evita sempre? Traccia. Dipende dall'intreccio: con un ordine di acquisizione opposto può avvenire o no. Si evita con un ordine totale dei lock.