Esercizio - Lettori e scrittori, che cosa succede togliendo una istruzione (eserciziario, esercizi 14, 46 e 107)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizi 14, 46 e 107; slide di esercizi sul problema lettori-scrittori). 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 14. Soluzione dei lettori-scrittori con variabili condivise semaphore mutex = 1, db = 1; int rc = 0;:

Process reader {                         Process writer {
  while (1) {                              while (1) {
    wait(mutex);                             wait(db);          // (-0-)
    rc = rc + 1;                             // scrittura del file
    if (rc == 1) wait(db);   // (-2-)        signal(db);        // (-1-)
    signal(mutex);                         }
    // lettura del file                  }
    wait(mutex);
    rc = rc - 1;
    if (rc == 0) signal(db); // (-3-)
    signal(mutex);
    // usa i dati letti
  }
}

Che cosa accade se: (1) si eliminano gli statement (-0-) e (-1-); (2) si elimina (-2-); (3) si elimina (-3-)?

Esercizio 46. Nel problema lettori/scrittori può esserci attesa indefinita: se mentre un lettore è nella sezione critica ne continuano ad arrivare altri, gli scrittori devono aspettare l'uscita dell'ultimo lettore (rilascio di db). Risolvere il problema in modo che possa causare attesa indefinita (starvation) ma non stallo (deadlock).

Esercizio 107. La soluzione seguente dei lettori-scrittori contiene errori e mancanze; si corregga con il minor numero possibile di modifiche.

void Lettore(void) {                     void Scrittore(void) {
  while (true) {                           while (true) {
    P(mutex);                                // prepara il dato da scrivere
    numeroLettori--;                         P(db);
    if (numeroLettori == 1) P(db);           // scrivi il dato
    V(mutex);                                P(db);
    // leggi il dato                       }
    numeroLettori--;                     }
    if (numeroLettori == 0) P(db);
    // usa il dato letto
  }
}

Esercizio 14

Lo schema giusto: db assicura l'accesso esclusivo al file agli scrittori e ai lettori come gruppo (il primo lettore prende db, l'ultimo lo rilascia); mutex protegge il contatore rc.

1. Senza (-0-) e (-1-) gli scrittori non prendono mai db: scrivono quando vogliono. Sono possibili corse critiche (interferenze) tra lettori e scrittori e tra più scrittori (due scrittori scrivono insieme sullo stesso file).
2. Senza (-2-) il primo lettore non prende db: lo scrittore può prendere db e scrivere mentre i lettori leggono (i lettori accedono al file mentre uno scrittore lo sta modificando).
3. Senza (-3-) l'ultimo lettore non rilascia db, che resta a 0 dopo che il primo lettore l'ha preso: gli scrittori rimangono bloccati per sempre su wait(db) (starvation totale), e anche i lettori successivi non sono più fermati.

Esercizio 46

La soluzione è proprio lo schema dell'esercizio 14 completo (quello in cui i lettori hanno priorità):

semaphore mutex = 1, db = 1;  int rc = 0;

Lettore() {                         Scrittore() {
    wait(mutex);                        wait(db);
    rc++;                               ScritturaDB();
    if (rc == 1) wait(db);              signal(db);
    signal(mutex);                  }
    LetturaDB();
    wait(mutex);
    rc--;
    if (rc == 0) signal(db);
    signal(mutex);
}

Perché non c'è deadlock: l'unica attesa mentre si tiene un altro semaforo è quella del primo lettore, che aspetta db tenendo mutex. Ma lo scrittore che possiede db non chiede mai mutex: finisce e rilascia db, e il lettore prosegue. Non si chiude nessun ciclo di attese. Perché c'è starvation possibile: finché c'è almeno un lettore dentro e ne arrivano di nuovi, rc non torna a 0 e signal(db) non viene eseguita: gli scrittori aspettano indefinitamente.

Esercizio 107

Errori e mancanze, da correggere con il minimo di modifiche:

Il codice corretto (le parti cambiate sono quelle della tabella):

void Lettore(void) {                     void Scrittore(void) {
  while (true) {                           while (true) {
    P(mutex);                                // prepara il dato da scrivere
    numeroLettori++;                         P(db);
    if (numeroLettori == 1) P(db);           // scrivi il dato
    V(mutex);                                V(db);
    // leggi il dato                       }
    P(mutex);                            }
    numeroLettori--;
    if (numeroLettori == 0) V(db);
    V(mutex);
    // usa il dato letto
  }
}

È proprio la soluzione standard con mutex = 1, db = 1, numeroLettori = 0. Si noti che if (numeroLettori == 1) del testo è già giusto (il primo lettore prende db), a patto di incrementare prima.

Domande d'esame

Perché db deve essere un semaforo binario e non un mutex? Traccia. Il primo lettore prende db e l'ultimo (un altro thread) lo rilascia: un mutex deve essere rilasciato dal proprietario.