Esercizio - Grafi di precedenza e ordine di stampa con i semafori (eserciziario, esercizi 19, 52, 60, 91 e 114)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD). Esercizi in cui i semafori servono a imporre un ordine di esecuzione tra processi (grafo di precedenza). 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 91. Aggiungere semafori (specificandone l'inizializzazione) al codice seguente per ottenere l'output 1 2 3 4 5 6. $P_1$ scrive "line 1", "line 2"; $P_2$ scrive "line 3", "line 4"; $P_3$ scrive "line 5", "line 6". Esiste una sola istanza di ciascun processo.
• Esercizio 114. Dati i processi $P_0$, $P_1$, $P_2$ (ciascuno stampa "Processo Pi"), sincronizzarli con semafori in modo che l'ordine sia $P_2$, $P_1$, $P_0$. Si possono usare due soli semafori.
• Esercizio 52. Con 4 semafori realizzare il grafo di precedenza $P_1 \to P_2$, $P_1 \to P_3$, $P_2 \to P_4$, $P_3 \to P_4$, $P_4 \to P_1$ (ciclico): all'istante iniziale può essere eseguito solo $P_1$. Prima inizializzare i semafori, poi scrivere le funzioni che gestiscono i processi ciclici (ognuno while(1) { ...; SC di Pi; ... }).
• Esercizio 60. Semafori e processi: init(S1, 1); init(S2, 0); con $P_1$: while(1) { wait(S1); SC P1; signal(S2); }, $P_2$: while(1) { wait(S2); SC P2; signal(S2); }, $P_3$: while(1) { wait(S2); SC P3; signal(S1); }. Quale ordine di esecuzione è possibile?
• Esercizio 19. Giulio e Giovanni lavorano in un bar specializzato in panini e cocktail abbinati. Giulio prepara un panino mentre, contemporaneamente, Giovanni realizza il cocktail più adatto. Quando entrambi hanno terminato, servono sia il panino sia la bevanda a un cliente. Queste azioni si ripetono per tutto il giorno. Si noti che Giulio non può servire un panino finché Giovanni non ha finito di preparare il cocktail e viceversa. Descrivere i due processi con semafori.

Esercizio 91

Si impone l'ordine $P_1 \to P_2 \to P_3$: ogni processo aspetta che il precedente abbia finito. Due semafori, go2 e go3, entrambi inizializzati a 0 (il processo parte solo dopo un V del predecessore):

sem go2 = 0, go3 = 0;

process P1 {                    process P2 {                    process P3 {
    write("line 1");                P(go2);                         P(go3);
    write("line 2");                write("line 3");                write("line 5");
    V(go2);                         write("line 4");                write("line 6");
}                                   V(go3);                     }
                                }

Output garantito: 1 2 3 4 5 6. $P_1$ non ha bisogno di aspettare nessuno; $P_2$ è bloccato su go2 (0) finché $P_1$ non ha scritto le sue due righe; $P_3$ su go3 finché $P_2$ non ha finito.

Esercizio 114

Ordine richiesto $P_2 \to P_1 \to P_0$ con due semafori Sem_P_0 = 0 e Sem_P_1 = 0: il processo $P_2$ può stampare subito e sveglia $P_1$; $P_1$ aspetta $P_2$, stampa e sveglia $P_0$; $P_0$ aspetta $P_1$.

P0:                       P1:                       P2:
    P(Sem_P_0);               P(Sem_P_1);               print "Processo P2";
    print "Processo P0";      print "Processo P1";      V(Sem_P_1);
                              V(Sem_P_0);

Esercizio 52: grafo ciclico con quattro semafori

Un semaforo per ogni processo che "abilita" quel processo: S1 = 1 (solo $P_1$ può partire), S2 = S3 = S4 = 0. Ogni processo, quando ha finito la sua sezione critica, abilita i successori:

init(S1, 1); init(S2, 0); init(S3, 0); init(S4, 0);

P1:  while (1) { wait(S1); SC di P1; signal(S2); signal(S3); }
P2:  while (1) { wait(S2); SC di P2; signal(S4); }
P3:  while (1) { wait(S3); SC di P3; signal(S4); }
P4:  while (1) { wait(S4); wait(S4); SC di P4; signal(S1); }

$P_4$ ha due predecessori ($P_2$ e $P_3$), quindi deve fare due wait(S4) (un signal da ciascuno). Con una sola wait(S4) partirebbe dopo che uno solo dei due ha finito: è l'errore tipico (e quello della "soluzione errata" mostrata dal corso, in cui i signal e le wait non corrispondono al grafo). Ordine ottenuto per ogni giro: $P_1$, poi $P_2$ e $P_3$ in qualunque ordine, poi $P_4$: sequenze 1 2 3 4 ... oppure 1 3 2 4 .... Verificato enumerando tutti gli intrecci con due giri: le uniche sequenze possibili sono 12341234, 12341324, 13241234, 13241324.

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>

#define GIRI 3

static sem_t S1, S2, S3, S4;

static void *p1(void *arg)
{
    (void)arg;
    for (int i = 0; i < GIRI; i++) {
        sem_wait(&S1);
        printf("P1\n");
        sem_post(&S2);
        sem_post(&S3);
    }
    return NULL;
}

static void *p2(void *arg)
{
    (void)arg;
    for (int i = 0; i < GIRI; i++) {
        sem_wait(&S2);
        printf("P2\n");
        sem_post(&S4);
    }
    return NULL;
}

static void *p3(void *arg)
{
    (void)arg;
    for (int i = 0; i < GIRI; i++) {
        sem_wait(&S3);
        printf("P3\n");
        sem_post(&S4);
    }
    return NULL;
}

static void *p4(void *arg)
{
    (void)arg;
    for (int i = 0; i < GIRI; i++) {
        sem_wait(&S4);                    /* aspetta P2... */
        sem_wait(&S4);                    /* ...e P3 */
        printf("P4\n");
        sem_post(&S1);
    }
    return NULL;
}

int main(void)
{
    pthread_t t[4];
    sem_init(&S1, 0, 1);
    sem_init(&S2, 0, 0);
    sem_init(&S3, 0, 0);
    sem_init(&S4, 0, 0);
    pthread_create(&t[0], NULL, p1, NULL);
    pthread_create(&t[1], NULL, p2, NULL);
    pthread_create(&t[2], NULL, p3, NULL);
    pthread_create(&t[3], NULL, p4, NULL);
    for (int i = 0; i < 4; i++)
        pthread_join(t[i], NULL);
    return 0;
}

Esercizio 60: quali ordini sono possibili

$S_1 = 1$, $S_2 = 0$. Si ragiona sui "gettoni":

• $S_1$ ha un gettone: solo $P_1$ può partire. Dopo la sua sezione critica fa signal(S2) e crea il gettone $S_2$.
• Il gettone $S_2$ può essere preso sia da $P_2$ sia da $P_3$: chi lo prende per primo va. Se è $P_2$, dopo la sua sezione critica rimette il gettone (signal(S2)): $P_2$ può quindi ripetersi quante volte vuole, e $P_3$ può non essere mai scelto (starvation).
• Se il gettone lo prende $P_3$, dopo la sezione critica fa signal(S1): $P_1$ riparte.

Quindi gli ordini possibili sono: $P_1\ (P_2)^k\ P_3$, ripetuto, con $k \ge 0$ per ogni giro; per esempio 1 3 1 3 ..., 1 2 3 1 2 2 3 ..., o anche 1 2 2 2 2 ... per sempre. Verificato enumerando tutte le sequenze di sezioni critiche fino a lunghezza 6: sono esattamente quelle in cui un $P_3$ chiude ogni giro, con zero o più $P_2$ tra $P_1$ e $P_3$ (e il solo prefisso senza $P_3$ finale).

Esercizio 19: Giulio e Giovanni (rendez-vous)

I due devono finire la propria preparazione prima di consegnare, e nessuno può cominciare il giro successivo prima che l'altro abbia finito. È un rendez-vous con due semafori, first = 0 e second = 0:

Giulio:                                       Giovanni:
  while (true) {                                while (true) {
      prepara il panino;                            realizza il cocktail;
      wait(first);                                  signal(first);
      signal(second);                               wait(second);
      consegna il panino;                           consegna il cocktail;
  }                                             }

Passo per passo: Giovanni, finito il cocktail, fa signal(first); Giulio, finito il panino, aspetta first (cioè che il cocktail sia pronto) e, appena lo ottiene, fa signal(second); Giovanni aspetta second (cioè che anche il panino sia pronto). Solo dopo entrambi consegnano. Se Giovanni è più veloce aspetta Giulio su second; se Giulio è più veloce aspetta Giovanni su first.

Domande d'esame

Perché in 52 $P_4$ ha due wait(S4)? Traccia. Ha due predecessori ($P_2$ e $P_3$): ognuno fa un signal(S4). Con una sola wait $P_4$ partirebbe quando uno solo ha finito, violando il grafo di precedenza.