Esercizio - Semafori POSIX, thread e processi (laboratorio 5)

Testo (laboratorio 5 del corso di Sistemi Operativi, Ing. Informatica UniPD). Semafori POSIX (<semaphore.h>, gcc ... -lpthread):

• Task 1 (posix-sem.c): due thread $A$ e $B$ con sezione critica protetta da un semaforo binario; $A$ parte subito e $B$ dopo 2 s. Qual è l'output? E senza semaforo (commentare sem_wait e sem_post)?
• Task 2 (multisem.c): reader, sorter e writer, tre thread in ciclo, con tre semafori, che devono eseguire sempre nell'ordine reader, sorter, writer, reader, sorter, writer... Il programma contiene errori nell'inizializzazione e nell'uso dei semafori: correggerlo (multisem_new.c).
• Task 3 (countsem.c): due produttori ($A$ ogni 3 s, $B$ ogni 1 s) e un consumatore con due semafori contatori; il consumatore stampa solo dopo che due produttori hanno stampato. L'output è quello atteso? Cosa succede inizializzando i semafori in modo diverso?
• Task 4 (dal laboratorio 4): multithreads.c (scrittore e due lettori sulla variabile book) con i semafori invece del mutex; salvare multithreads_sem.c.
• Task 5 (procsem.c): sincronizzazione tra processi con semafori con nome: il padre è consumatore, un figlio (creato con fork) è produttore. Controllare l'output; interrompere con Ctrl-C e rilanciare: perché non funziona più?
• Task 6: modificare procsem.c aggiungendo un secondo figlio produttore $B$; il padre stampa "This is the CONSUMER parent" solo dopo che sia $A$ sia $B$ hanno stampato (in qualsiasi ordine). Salvare procsem_new.c.

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 →.

I semafori POSIX

Un semaforo POSIX è un intero non negativo: sem_post lo incrementa, sem_wait lo decrementa e blocca se vale 0. Due tipi:

Task 1: posix-sem.c

Linea temporale (il thread $A$ parte a $t = 0$, $B$ a $t = 2$; la sezione critica dura 4 s, la sezione di coda 2 s):

Le due sezioni critiche (0-4 e 4-8) non si sovrappongono. Senza semaforo (commentando sem_wait/sem_post) $B$ entra a $t = 2$ mentre $A$ è ancora dentro: le due sezioni critiche si sovrappongono tra 2 e 4 s, e le righe Entered / Exiting dei due thread si mescolano: viola la mutua esclusione.

Un difetto del codice del corso: la funzione thread è dichiarata void* ma non restituisce nulla (manca return NULL; alla fine): comportamento indefinito (-Wreturn-type). Si corregge con return NULL;.

Task 2: multisem.c con errori

Il programma originale: sem1 inizializzato a 1, sem2 e sem3 a 0; il reader non aspetta nulla: stampa, dorme e fa sem_post(&sem1); il sorter aspetta sem1, stampa, sem_post(&sem2); il writer aspetta due semafori, sem1 e sem2, stampa, sem_post(&sem3).

Errori:

1. il reader non fa mai wait: gira libero e continua a incrementare sem1 senza limite, quindi non rispetta alcun ordine;
2. sem1 è inizializzato a 1: il sorter può partire subito, prima del reader;
3. il writer aspetta sem1, lo stesso semaforo del sorter: i due thread si contendono i permessi di sem1 e l'ordine non è garantito; l'attesa su sem1 per il writer è sbagliata;
4. sem3 è incrementato ma nessuno lo aspetta: il ciclo non si chiude.

Correzione (soluzione del corso): una catena circolare in cui ogni thread aspetta il semaforo del predecessore e segnala quello del successore: reader aspetta sem3 (inizializzato a 1, così il reader parte per primo), sorter aspetta sem1, writer aspetta sem2.

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

#define GIRI 3

static sem_t sem1, sem2, sem3;

static void *reader_run(void *arg)
{
    (void)arg;
    for (int i = 0; i < GIRI; i++) {
        sem_wait(&sem3);                       /* aspetta il writer del giro precedente */
        printf("This is reader.\n");
        usleep(1000);
        sem_post(&sem1);                       /* tocca al sorter */
    }
    return NULL;
}

static void *sorter_run(void *arg)
{
    (void)arg;
    for (int i = 0; i < GIRI; i++) {
        sem_wait(&sem1);
        printf("This is sorter.\n");
        usleep(1000);
        sem_post(&sem2);                       /* tocca al writer */
    }
    return NULL;
}

static void *writer_run(void *arg)
{
    (void)arg;
    for (int i = 0; i < GIRI; i++) {
        sem_wait(&sem2);
        printf("This is writer.\n\n");
        usleep(1000);
        sem_post(&sem3);                       /* il reader puo' ripartire */
    }
    return NULL;
}

int main(void)
{
    pthread_t reader, sorter, writer;
    sem_init(&sem1, 0, 0);
    sem_init(&sem2, 0, 0);
    sem_init(&sem3, 0, 1);                     /* l'unico a 1: parte il reader */
    pthread_create(&reader, NULL, reader_run, NULL);
    pthread_create(&sorter, NULL, sorter_run, NULL);
    pthread_create(&writer, NULL, writer_run, NULL);
    pthread_join(reader, NULL);
    pthread_join(sorter, NULL);
    pthread_join(writer, NULL);
    sem_destroy(&sem1);
    sem_destroy(&sem2);
    sem_destroy(&sem3);
    return 0;
}

Uscita: reader, sorter, writer ripetuti per 3 giri, sempre in quest'ordine: un solo semaforo vale 1 (token) e passa da un thread al successivo. (Il corso usa while(1) e sleep(1); qui i giri sono finiti per poter terminare.)

Task 3: countsem.c

Con csem = 2 e psem = 0: i due produttori fanno sem_wait(csem) (hanno 2 permessi: possono stampare entrambi), sem_post(psem); il consumatore aspetta due psem, stampa, e restituisce due permessi csem. Output atteso, a coppie: due righe di produttori (A-B, B-A, A-A o B-B: il produttore B, più veloce, può stampare anche due volte di fila se $A$ dorme), poi This is consumer. Con valori diversi:

Task 4: scrittore e lettori con i semafori

Lo schema dei lettori-scrittori (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 →): rw_mutex = 1 (accesso al libro), mutex = 1 (contatore dei lettori), read_count = 0. Il primo lettore prende rw_mutex, l'ultimo lo rilascia; lo scrittore lo prende per scrivere. Un semaforo binario (non un mutex) perché lo rilascia un thread diverso da quello che l'ha preso. Il codice completo è lettori_scrittori.c nella nota di teoria; qui basta sostituire il dato con book.

Task 5: semafori con nome tra processi

procsem.c: due semafori con nome, /psem (iniziale 0) e /csem (iniziale 1). Il figlio (produttore) fa sem_wait(csem), stampa This is the PRODUCER child, dorme 2 s, sem_post(psem), exit(0); il padre (consumatore) fa sem_wait(psem), stampa This is the CONSUMER parent, sem_post(csem), wait(NULL), sem_close e sem_unlink di entrambi.

Output: prima This is the PRODUCER child, poi (dopo 2 s) This is the CONSUMER parent.

Ctrl-C e rilancio. I semafori con nome vivono nel sistema (in /dev/shm), non nel processo: se il programma viene interrotto prima di sem_unlink restano là con il valore che avevano. Al lancio successivo sem_open(..., O_CREAT, 0666, valore) trova il semaforo esistente e ignora il valore iniziale: se /csem era rimasto a 0 il figlio si blocca per sempre. Si rimedia a mano con rm /dev/shm/sem.psem /dev/shm/sem.csem (nei file compaiono con il prefisso sem.), oppure facendo sem_unlink all'inizio del programma.

Task 6: due produttori

Il padre deve aspettare due produttori: psem si incrementa due volte (una per produttore) e il padre fa sem_wait(psem) due volte. csem iniziale 2 (due produttori possono lavorare).

#include <fcntl.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/wait.h>
#include <unistd.h>

static void produttore(sem_t *psem, sem_t *csem, char nome)
{
    sem_wait(csem);
    printf("This is the PRODUCER child %c\n", nome);
    fflush(stdout);
    sleep(2);
    sem_post(psem);
    exit(0);                                 /* il figlio termina qui */
}

int main(void)
{
    sem_unlink("/psem");                     /* elimina eventuali residui di esecuzioni interrotte */
    sem_unlink("/csem");
    sem_t *psem = sem_open("/psem", O_CREAT, 0666, 0);
    sem_t *csem = sem_open("/csem", O_CREAT, 0666, 2);
    if (psem == SEM_FAILED || csem == SEM_FAILED) {
        perror("sem_open");
        return 1;
    }

    if (fork() == 0)
        produttore(psem, csem, 'A');         /* primo figlio */
    if (fork() == 0)
        produttore(psem, csem, 'B');         /* secondo figlio */

    sem_wait(psem);                          /* aspetta il primo produttore... */
    sem_wait(psem);                          /* ...e il secondo */
    printf("This is the CONSUMER parent\n");
    sem_post(csem);
    sem_post(csem);

    wait(NULL);                              /* raccoglie entrambi i figli */
    wait(NULL);

    sem_close(psem);
    sem_close(csem);
    sem_unlink("/psem");
    sem_unlink("/csem");
    return 0;
}

Output: le due righe dei produttori (in qualunque ordine, quasi insieme perché csem = 2), poi dopo 2 s la riga del consumatore.

Errore nella soluzione del corso (procsem_new.c): il padre chiama wait(NULL) una sola volta pur avendo due figli: il secondo figlio resta zombie fino all'uscita del padre (e fa sem_post(csem) una sola volta invece di due, cosa innocua perché il programma termina). Qui si raccolgono entrambi i figli e si rimettono i due permessi.

Tutti i programmi sono compilati con zig cc -Wall -Wextra -Wpedantic per Linux senza avvisi (il posix-sem.c del corso ha l'avviso -Wreturn-type); non sono eseguiti qui (binari Linux).

Domande d'esame

Perché dopo un Ctrl-C il programma con semafori con nome può non funzionare più al lancio successivo? Traccia. I semafori con nome persistono nel sistema (/dev/shm) finché non si fa sem_unlink; sem_open con O_CREAT su un semaforo esistente ignora il valore iniziale, che resta quello sbagliato lasciato dall'esecuzione interrotta.