Salta al contenuto
Note per Studenti Esercizio - Incrocio con il vigile e autobus con due porte (eserciziario, esercizi 75 e 79)

Esercizio - Incrocio con il vigile e autobus con due porte (eserciziario, esercizi 75 e 79)

In questa pagina 3

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizi 75 e 79). 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 75. Utilizzare due semafori (bus inizializzato a 30 e door inizializzato a 2) per gestire il problema seguente: ogni bus ha capacità di 30 passeggeri e ha due porte; gestire il fatto che non ci possono essere più di 30 passeggeri e che i passeggeri non devono scontrarsi quando entrano o escono dal bus.

Esercizio 79. Un incrocio di due grandi viali (uno in direzione Nord-Sud, l'altro Est-Ovest) è regolato da un vigile. Il vigile lascia passare le macchine su uno dei due viali (in ambedue i sensi) per un tempo TT, poi blocca il transito da quel viale, attende che l'incrocio si liberi dagli automezzi che lo avevano già impegnato, e quindi dà via libera ai mezzi in attesa sull'altro viale, lasciandoli transitare per un tempo TT, e così via indefinitamente. I due viali sono così ampi che nell'incrocio non c'è mai ingorgo. Fornire il pseudo-codice dei processi auto_NS e auto_EW e della procedura vigile, considerando che all'avvio l'incrocio sia già assegnato alle macchine sulla direttrice Nord-Sud.

Esercizio 75: autobus

Due risorse: posti (30) e porte (2). Il semaforo bus conta i posti liberi: chi sale ne prende uno e lo tiene fino a quando scende. Il semaforo door conta le porte libere: chi attraversa una porta ne occupa una per il tempo del passaggio.

getting_on():                getting_off():
    P(&bus);                     P(&door);
    P(&door);                    walk_out();
    walk_in();                   V(&door);
    V(&door);                    V(&bus);

Perché l'ordine: all'ingresso prima il posto (bus), poi la porta, così nessuno occupa una porta per aspettare un posto (bloccherebbe quelli che scendono e liberano posti: sarebbe un deadlock). All'uscita il posto si rilascia dopo aver liberato la porta (o prima: è indifferente), ma la porta si prende senza tenere altro.

autobus.cc
#include <pthread.h>
#include <semaphore.h>
#include <stdatomic.h>
#include <stdio.h>
#include <unistd.h>

#define POSTI 30
#define PORTE 2
#define PASSEGGERI 40

static sem_t bus, door;
static atomic_int a_bordo, alle_porte;
static atomic_int errori;

static void passa_porta(void)
{
    if (atomic_fetch_add(&alle_porte, 1) + 1 > PORTE)
        atomic_fetch_add(&errori, 1);          /* due passeggeri si scontrerebbero */
    usleep(200);
    atomic_fetch_sub(&alle_porte, 1);
}

static void *passeggero(void *arg)
{
    (void)arg;
    sem_wait(&bus);                            /* un posto */
    sem_wait(&door);                           /* una porta */
    passa_porta();
    sem_post(&door);
    if (atomic_fetch_add(&a_bordo, 1) + 1 > POSTI)
        atomic_fetch_add(&errori, 1);          /* piu' di 30 a bordo */

    usleep(2000);                              /* il viaggio */

    atomic_fetch_sub(&a_bordo, 1);
    sem_wait(&door);
    passa_porta();
    sem_post(&door);
    sem_post(&bus);                            /* libera il posto */
    return NULL;
}

int main(void)
{
    pthread_t t[PASSEGGERI];
    sem_init(&bus, 0, POSTI);
    sem_init(&door, 0, PORTE);
    for (int i = 0; i < PASSEGGERI; i++)
        pthread_create(&t[i], NULL, passeggero, NULL);
    for (int i = 0; i < PASSEGGERI; i++)
        pthread_join(t[i], NULL);
    printf("errori rilevati: %d (attesi 0)\n", atomic_load(&errori));
    return 0;
}

(Per semplicità un passeggero conta come "a bordo" subito dopo aver passato la porta; il programma verifica che a bordo non ci siano mai più di 30 persone e che alle porte non ne passino più di 2 alla volta. Compilato senza avvisi, non eseguito qui.)

Esercizio 79: incrocio e vigile

Variabili del corso: int n = 0 (macchine che stanno impegnando l'incrocio) e semafori NS = 1 (via libera Nord-Sud), EW = 0 (via libera Est-Ovest), mutexNS = 1, mutexEW = 1, incrocio = 1, conta = 1.

auto_NS():                                   vigile():
    int mn;                                      while (1) {
    wait(mutexNS);                                   sleep(T);
    wait(NS);                                        wait(NS);          // chiude il viale NS
    signal(mutexNS);                                 wait(incrocio);    // aspetta che l'incrocio si liberi
    wait(conta);                                     signal(incrocio);
    mn = ++n;                                        signal(EW);        // apre il viale EW
    signal(conta);
    if (mn == 1) wait(incrocio);                     sleep(T);
    signal(NS);                                      wait(EW);          // chiude il viale EW
    passa_incrocio();                                wait(incrocio);
    wait(conta);                                     signal(incrocio);
    mn = --n;                                        signal(NS);        // apre il viale NS
    signal(conta);                               }
    if (mn == 0) signal(incrocio);

auto_EW() è identica con mutexEW e EW al posto di mutexNS e NS. Come funziona:

  • Il cancello del viale (NS o EW): un'auto lo passa (wait, poi signal subito dopo essersi registrata); il vigile lo chiude con wait e lo apre con signal. mutexNS fa sì che una sola macchina alla volta si metta in attesa del cancello, così il vigile al più aspetta una macchina ferma lì e non una coda lunga (nota del corso: curare questo aspetto, perché il vigile non deve aspettare molte macchine già in coda).
  • Registrare il passaggio: n conta le macchine nell'incrocio (protetto da conta); la prima prende il semaforo incrocio e l'ultima lo rilascia: lo stesso schema dell'interruttore dei lettori. Mentre un'auto è tra il cancello e il wait(incrocio) tiene il cancello, quindi il vigile non può chiuderlo prima che l'auto sia registrata.
  • Il vigile: dopo TT chiude un viale (wait(NS)), poi wait(incrocio); signal(incrocio) serve solo ad aspettare che l'incrocio sia vuoto (lo prende solo quando l'ultima macchina l'ha rilasciato), poi apre l'altro viale.
  • Inizializzazione: NS = 1, EW = 0: all'avvio l'incrocio è assegnato al viale Nord-Sud, come richiesto.

Programma C (con un controllo che non ci siano mai insieme auto delle due direzioni nell'incrocio):

incrocio.cc
#include <pthread.h>
#include <semaphore.h>
#include <stdatomic.h>
#include <stdio.h>
#include <unistd.h>

#define AUTO 12                        /* per direzione */

static sem_t NS, EW, mutexNS, mutexEW, incrocio, conta;
static int n;                          /* macchine nell'incrocio */
static atomic_int dentro[2];           /* 0 = NS, 1 = EW, solo per il controllo */
static atomic_int errori, finite, fine;

static void auto_dir(int d)
{
    sem_t *gate = d ? &EW : &NS;
    sem_t *mutexd = d ? &mutexEW : &mutexNS;

    sem_wait(mutexd);
    sem_wait(gate);                    /* aspetta la via libera */
    sem_post(mutexd);
    sem_wait(&conta);
    int mn = ++n;
    sem_post(&conta);
    if (mn == 1)
        sem_wait(&incrocio);           /* la prima prende l'incrocio */
    sem_post(gate);                    /* ora il vigile puo' chiudere il viale */

    atomic_fetch_add(&dentro[d], 1);
    if (atomic_load(&dentro[1 - d]) != 0)
        atomic_fetch_add(&errori, 1);  /* auto di direzioni diverse insieme: errore */
    usleep(300);                       /* passa_incrocio() */
    atomic_fetch_sub(&dentro[d], 1);

    sem_wait(&conta);
    mn = --n;
    sem_post(&conta);
    if (mn == 0)
        sem_post(&incrocio);           /* l'ultima libera l'incrocio */
    atomic_fetch_add(&finite, 1);
}

static void *auto_run(void *arg)
{
    auto_dir((int)(long)arg);
    return NULL;
}

static void *vigile(void *arg)
{
    (void)arg;
    while (!atomic_load(&fine)) {
        usleep(1000);                  /* T */
        sem_wait(&NS);                 /* chiude NS */
        sem_wait(&incrocio);
        sem_post(&incrocio);           /* incrocio libero */
        sem_post(&EW);                 /* apre EW */
        usleep(1000);
        sem_wait(&EW);                 /* chiude EW */
        sem_wait(&incrocio);
        sem_post(&incrocio);
        sem_post(&NS);                 /* apre NS */
    }
    return NULL;
}

int main(void)
{
    pthread_t v, a[2 * AUTO];
    sem_init(&NS, 0, 1);               /* all'avvio via libera per Nord-Sud */
    sem_init(&EW, 0, 0);
    sem_init(&mutexNS, 0, 1);
    sem_init(&mutexEW, 0, 1);
    sem_init(&incrocio, 0, 1);
    sem_init(&conta, 0, 1);
    pthread_create(&v, NULL, vigile, NULL);
    for (long i = 0; i < 2 * AUTO; i++)
        pthread_create(&a[i], NULL, auto_run, (void *)(i % 2));
    for (int i = 0; i < 2 * AUTO; i++)
        pthread_join(a[i], NULL);
    atomic_store(&fine, 1);
    pthread_join(v, NULL);
    printf("auto passate: %d, errori: %d (atteso 0)\n", atomic_load(&finite), atomic_load(&errori));
    return 0;
}

(Il vigile termina dopo il suo ultimo ciclo, lasciando aperto un viale; compilato senza avvisi, non eseguito qui.)

Domande d'esame

All'autobus, perché non si può fare prima P(door) e poi P(bus)? Traccia. Chi entrerebbe tenendo una porta mentre aspetta un posto bloccherebbe le uscite: i passeggeri a bordo non potrebbero scendere, quindi i posti non si libererebbero mai (attesa circolare porte/posti). L'ordine posto, poi porta lo evita.

Versione ripasso

Teoria collegata