Esercizio - Buffer limitato con semafori e messaggi lunghi (eserciziario, esercizi 11 e 45)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizi 11 e 45).

Esercizio 11. Due processi $P$ e $Q$ comunicano tramite un buffer di capacità un messaggio. $P$ invia messaggi che sono stringhe di al più 80 caratteri; $Q$ estrae i caratteri uno alla volta. Definire i dati condivisi e scrivere le procedure invio(x, y) (con x array di 80 caratteri e y la dimensione di x) e ricezione(ch), usando semafori.

Esercizio 45. I thread $A$ (produttore) e $B$ (consumatore) si scambiano messaggi attraverso un buffer di 10 celle, ciascuna capace di un messaggio, con i semafori mutex (valore iniziale 1), CelleLibere (10) e MessaggiGiacenti (0). A meno delle operazioni di sincronizzazione e mutua esclusione (necessarie perché insert e remove_item non sono indivisibili), i frammenti sono i due cicli produce/insert e remove/consume. Completarli con le operazioni sui semafori.

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 11

Il buffer contiene un solo messaggio, ma $Q$ lo consuma carattere per carattere. Stato condiviso: il messaggio buf_msg[80], la sua lunghezza dim_msg e l'indice index del prossimo carattere da leggere. Due semafori:

• pieno (iniziale 1): "il buffer è libero, $P$ può scrivere" (il nome indica "puoi riempire");
• vuoto (iniziale 0): "nel buffer c'è qualcosa da leggere".

invio aspetta che il buffer sia libero, copia il messaggio, azzera l'indice e segnala che c'è da leggere. ricezione aspetta, prende il carattere in posizione index, avanza l'indice; se ha letto l'ultimo carattere libera il buffer (pieno), altrimenti segnala a se stesso (vuoto) che c'è ancora da leggere:

invio(x, y):                         ricezione(ch):
    wait(pieno);                         wait(vuoto);
    buf_msg = x; dim_msg = y;            ch = buf_msg[index];
    index = 1;                           index = index + 1;
    signal(vuoto);                       if (index > dim_msg) signal(pieno);
                                         else                 signal(vuoto);

Il signal(vuoto) nell'else serve per far proseguire la lettura dei caratteri successivi (con un solo consumatore sarebbe possibile anche un ciclo, ma con più consumatori ogni carattere è letto da chi per primo passa wait(vuoto)).

Il codice C (indici da 0, con i due thread e una sequenza di messaggi):

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

#define MAXLEN 80

static char buf_msg[MAXLEN];
static int dim_msg;
static int index_;                       /* prossimo carattere da leggere */
static sem_t pieno;                      /* iniziale 1: buffer libero, P puo' scrivere */
static sem_t vuoto;                      /* iniziale 0: c'e' qualcosa da leggere */

static void invio(const char *x, int y)
{
    sem_wait(&pieno);                    /* aspetta che il messaggio precedente sia stato letto tutto */
    memcpy(buf_msg, x, (size_t)y);
    dim_msg = y;
    index_ = 0;
    sem_post(&vuoto);
}

static char ricezione(void)
{
    sem_wait(&vuoto);
    char ch = buf_msg[index_++];
    if (index_ >= dim_msg)
        sem_post(&pieno);                /* ultimo carattere: libera il buffer */
    else
        sem_post(&vuoto);                /* ce ne sono altri: sveglia la prossima ricezione */
    return ch;
}

static const char *messaggi[] = {"ciao", "sistemi operativi", "fine"};
#define NMSG 3

static void *produttore(void *arg)
{
    (void)arg;
    for (int i = 0; i < NMSG; i++)
        invio(messaggi[i], (int)strlen(messaggi[i]));
    return NULL;
}

static void *consumatore(void *arg)
{
    (void)arg;
    for (int i = 0; i < NMSG; i++) {
        int n = (int)strlen(messaggi[i]);       /* il consumatore conosce le lunghezze */
        for (int k = 0; k < n; k++)
            putchar(ricezione());
        putchar('\n');
    }
    return NULL;
}

int main(void)
{
    pthread_t p, c;
    sem_init(&pieno, 0, 1);
    sem_init(&vuoto, 0, 0);
    pthread_create(&p, NULL, produttore, NULL);
    pthread_create(&c, NULL, consumatore, NULL);
    pthread_join(p, NULL);
    pthread_join(c, NULL);
    return 0;
}

Stampa le tre stringhe, una per riga, anche se il produttore è più veloce: invio del messaggio successivo si blocca su pieno finché l'ultimo carattere del precedente non è stato letto. (Il programma è stato compilato senza avvisi; la logica è la stessa del corso con indici da 0.)

Esercizio 45

Il produttore deve aspettare una cella libera e usare il buffer in mutua esclusione; il consumatore deve aspettare un messaggio e anch'esso usare il buffer in mutua esclusione:

A (produttore):                          B (consumatore):
while (true) {                           while (true) {
    item = produce_item();                   P(&MessaggiGiacenti);
    P(&CelleLibere);                         P(&mutex);
    P(&mutex);                               item = remove_item();
    insert(item);                            V(&mutex);
    V(&mutex);                               V(&CelleLibere);
    V(&MessaggiGiacenti);                    consume(item);
}                                        }

L'ordine delle $P$ è importante. Se il produttore facesse P(mutex) prima di P(CelleLibere) e il buffer fosse pieno, terrebbe mutex mentre dorme su CelleLibere; il consumatore, per liberare una cella, deve prendere mutex: nessuno avanza (deadlock). Lo stesso per il consumatore con MessaggiGiacenti. Si noti che produce_item e consume sono fuori dalla sezione critica (non serve proteggerli e tenere il mutex durante calcoli lunghi rallenterebbe tutto).

Il programma completo è nella nota di 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 →, prod_cons_sem.c).

Domande d'esame

Quali valori iniziali dei tre semafori e perché? Traccia. mutex = 1 (nessuno nel buffer); CelleLibere = 10 (il buffer parte vuoto: tutte le celle sono libere); MessaggiGiacenti = 0 (nessun messaggio da consumare). La somma CelleLibere + MessaggiGiacenti resta 10 fuori dalle operazioni in corso.