Esercizio - Conteggio dei valori finali con una variabile condivisa (eserciziario, esercizi 96 e 112)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizi 96 e 112). Teoria: Sincronizzazione - sezione critica, race condition e mutexQuando più processi o thread accedono agli stessi dati e il risultato dipende dall'ordine degli accessi si ha una race condition (esempio: counter++ e counter-- sono tre istruzioni macchina ciascuna, e interleaving diversi danno 4, 5 o 6 partendo da 5); il problema della sezione critica chiede un protocollo (entry section, sezione critica, exit section, remainder section) che garantisca mutua esclusione, progresso e attesa limitata; disabilitare gli interrupt non scala sui multiprocessori, l'alternanza stretta con turn viola il progresso, la soluzione di Peterson (flag[2] e turn) soddisfa i tre requisiti ma può fallire su hardware moderno per il riordino delle istruzioni, per cui servono barriere di memoria; l'hardware offre test_and_set e compare_and_swap (atomiche) e variabili atomiche; il mutex lock (acquire/release, in POSIX pthread_mutex_t) è lo strumento di alto livello, con attesa attiva se è uno spinlock oppure con sospensione del thread se è un mutex di sistema; bloccare due volte lo stesso mutex senza sbloccarlo causa deadlock.Sincronizzazione - sezione critica, race condition e mutex →.

Esercizio 96. Pseudo-codice:

const int n = 20;
int conta;

void incrementa() {
    int i;
    for (i = 0; i < n; ++i) {
        int t;
        t = conta;
        conta = t + 1;
    }
}

void main() {
    conta = 0;
    parbegin(incrementa, incrementa);   /* due processi concorrenti */
    write(conta);
}

parbegin avvia due processi concorrenti che incrementano iterativamente una variabile condivisa; la velocità relativa dei due processi non è prevedibile. (1) Quali sono i valori minimo e massimo che il risultato può assumere e perché? (2) Quali sono se vengono avviati $M$ processi invece di 2?

Esercizio 112. Due thread eseguiti in concorrenza con memoria condivisa:

Thread A:                         Thread B:
for (i = 0; i < 5; i++)           for (j = 0; j < 5; j++)
    x = x + 1;                        x = x + 2;

$x$ è inizializzata a 0. Si suppone che x = x + 2 nel thread $B$ sia atomica (come una funzione atomicIncr2(x)); questo non vale per x = x + 1 del thread $A$. Quali sono i possibili valori finali di $x$?

Esercizio 96

Ogni iterazione fa t = conta; (lettura) e conta = t + 1; (scrittura): se due processi si intrecciano, uno può scrivere un valore basato su una lettura vecchia e cancellare gli incrementi dell'altro (aggiornamento perso, Sincronizzazione - sezione critica, race condition e mutexQuando più processi o thread accedono agli stessi dati e il risultato dipende dall'ordine degli accessi si ha una race condition (esempio: counter++ e counter-- sono tre istruzioni macchina ciascuna, e interleaving diversi danno 4, 5 o 6 partendo da 5); il problema della sezione critica chiede un protocollo (entry section, sezione critica, exit section, remainder section) che garantisca mutua esclusione, progresso e attesa limitata; disabilitare gli interrupt non scala sui multiprocessori, l'alternanza stretta con turn viola il progresso, la soluzione di Peterson (flag[2] e turn) soddisfa i tre requisiti ma può fallire su hardware moderno per il riordino delle istruzioni, per cui servono barriere di memoria; l'hardware offre test_and_set e compare_and_swap (atomiche) e variabili atomiche; il mutex lock (acquire/release, in POSIX pthread_mutex_t) è lo strumento di alto livello, con attesa attiva se è uno spinlock oppure con sospensione del thread se è un mutex di sistema; bloccare due volte lo stesso mutex senza sbloccarlo causa deadlock.Sincronizzazione - sezione critica, race condition e mutex →).

Massimo: $20 \cdot M$ (con $M = 2$: 40). Si ottiene quando nessun incremento va perso, per esempio quando i processi si eseguono uno dopo l'altro: ogni incremento viene contato.

Minimo: 2, anche per $M$ processi qualsiasi con almeno 2 (non 20: la soluzione del corso riporta 20, ma è un errore: scrive che il minimo corrisponde a "una interruzione a ogni iterazione e sarà ovviamente pari a 20", e per $M$ processi indica 20 come minimo e $20M$ come massimo. Il minimo reale è 2). Costruzione per due processi $P$ e $Q$ con $n = 20$:

1. $P$ legge conta (0) in t e si ferma;
2. $Q$ esegue $19$ iterazioni complete: conta vale 19;
3. $P$ scrive conta = 0 + 1 = 1 (cancella 19 incrementi); poi $P$ si ferma;
4. $Q$ legge conta (1) per la sua ultima iterazione e si ferma;
5. $P$ esegue le sue 19 iterazioni rimaste: conta vale 20;
6. $Q$ scrive conta = 1 + 1 = 2. Ora $Q$ ha finito (20 iterazioni) e $P$ pure: risultato 2.

Perché non si può scendere sotto 2: ogni scrittura scrive $t + 1 \ge 1$ (con $t \ge 0$), quindi dopo la prima scrittura conta vale sempre almeno 1. Il processo che termina per ultimo termina con la sua ventesima scrittura, che è l'ultima di tutte; la sua ventesima lettura avviene dopo la sua diciannovesima scrittura, quindi legge un valore $\ge 1$ e scrive $\ge 2$. La verifica esaustiva (enumerazione di tutti gli intrecci) conferma: per due processi con $n = 20$ il risultato minimo è 2 e il massimo 40; per $M = 3$ processi con $n = 5$ minimo 2 e massimo 15 (stessa legge: minimo 2, massimo $nM$).

Esercizio 112

Il thread $B$ aggiunge 2 in modo indivisibile, 5 volte: contributo totale 10. Il thread $A$ fa 5 volte x = x + 1, ognuna composta da lettura e scrittura. Le sole interferenze possibili: $A$ legge $x$, poi $B$ esegue $k$ delle sue somme (atomiche) e infine $A$ scrive (letto $+ 1$): le $k$ somme di $B$ avvenute nella finestra tra la lettura e la scrittura di $A$ vengono cancellate.

Quindi $x_{\text{finale}} = 5 + 10 - 2k$, dove $k$ è il numero totale di somme di $B$ cancellate (0 $\le k \le 5$):

Valori possibili: 5, 7, 9, 11, 13, 15. Esempi: 15 se i thread non si intrecciano; 5 se $A$ legge 0, $B$ fa tutte e 5 le somme ($x = 10$) e poi $A$ scrive 1 (i 5 incrementi di $B$ sono cancellati), seguono 4 incrementi di $A$. Valori pari o maggiori di 15 sono impossibili. Verificato enumerando tutti gli intrecci: l'insieme dei valori è esattamente $\{5, 7, 9, 11, 13, 15\}$, come nel corso.

Domande d'esame

Con 2 processi che incrementano 20 volte una variabile condivisa senza mutua esclusione, qual è il valore minimo? Traccia. 2 (non 20): un processo legge 0 presto, l'altro fa 19 giri, il primo scrive 1, poi il secondo legge 1 e il primo fa i suoi 19 giri, infine il secondo scrive 2.