20210526c1

Consegna

Esercizio c.1: Un buffer sincrono strampalato (bss) ha due procedure entry:

void put(T value)

list of T get(void)

La entry put viene utilizzata per aggiungere un elemento e la entry get per leggere tutti quelli disponibili.

Se più processi chiamano la put quando nessun processo è in attesa per una get, rimangono tutti bloccati.

Quando successivamente un processo chiama la get riceve la lista di tutti gli elementi inseriti con le put e

tutti i processi vengono sbloccati.

Se il buffer è vuoto tutti i processi che chiamano la get rimangono bloccati. quando un processo chiama

successivamente la put tutti i processi in attesa per la get si sbloccano e ricevono lo stesso valore di ritorno:

una lista contenente il solo valore passato come parametro alla put.

1

Questa soluzione è sbagliata perché può succedere questo:

Ho 3 PUT in attesa di un get, arriva la get, le 3 put eseguono tutto e mettono a 0 ng, allora la get pensa che non cisiano puts prima di lei, e si mette ad aspettare che arrivino altre put.

put è bloccato quando non c'è nessun processo che è in attesa di una get.
Se ci sono delle put in attesa e riceve una get, questa get riceve tutte le put.

Get è bloccato quando non c'è nessun put.
Quando arriva un put la get prende il singolo put

Si può vedere come sono fondamentali il numero di get e numero di put in ogni momento.

Sia np il numero di put, e ng il numero di get.

Si può concludere che se np==0 e ng == 0 allora il prossimo processo che chiama get o put
è bloccato. 

se ng == 0 le put sono sempre bloccate.
se np == 0 le get sono sempre bloccate.

allora possiamo decrivere ad alto livello la soluzione

void put(T value) {
    <np++>
    <await ng != 0 -> dai value al primo get che mi sblocca>
    <np-->
}

list of T get() {
    <ng++>
    <await np != 0 -> prendi tutti valori che le put ti danno>
    <ng-->
    return valori che hai trovato nell'await.
}

La parte complessa è la gestione del passaggio di valori fra le get e le put, possiamo risolverlo con 
una coda condivisa, che rappresenta il passaggio dei valori

queue<int> coda, questo parametro sarà la struttura di dati condivisa per passarci i valori tra un processo
all'altro

void put(T value) {
    < np++ >

    <await ng != 0 -> 
        coda.add(value);
        np--;
    >
}


list of T get() {
    queue<int> coda_locale;
    <ng++>
    <await np != 0 -> 
        <await np == 0 -> 
            coda_locale = coda; // prendi la coda globale solo quando tutte le put hanno finito
            coda = empty(coda); // svuota la coda globale.
        >
        ng--;
    >
    
    return coda_locale;
}

Procediamo a tradurre ora tutte le soluzioni con await in soluzioni con semafori validi.

// SOLUZIONE PROPOSTA con paradigma di Andrews, creata con awaits.

semaphore semp(0); // arbitro i puts.
semaphore semgzero(0); // arbitro i gets/
semaphore semgone(0); // arbitro
semaphore mutex(1);
waitinggzero = 0; // chiamata da get, aspetto che il valore sia 0
waitinggone = 0; // chiamaga da get, aspetto che il valore sia 1
waitingp = 0; // aspetto put
list<T> coda; // lista condivisa

void put(T value) {
    mutex.P();
    np++;
    SIGNAL();
    
    mutex.P();
    if (ng == 0) {
        waitingp++;
        mutex.V();
        semp.P();
        waitingp--;
    }
    coda.add(value);
    np--;
    SIGNAL();
}

list of T get() {
    lista<T> lista_locale;

    mutex.P();
    ng++;
    SIGNAL();

    mutex.P();

    // blocca finché non c'è un put
    if (np == 0) {
        waitinggone++;
        mutex.V();
        semgone.P();
        waitinggone--;
    }
    
    // blocca finché i put non hanno aggiunto in coda
    if (np != 0) {
        waitinggzero++;
        mutex.V();
        semgzero.P();
        waitinggzero--;
    }

    lista_locale = coda;
    ng--;
    SIGNAL();

    return lista_locale;
}

void SIGNAL() {
    if (waitinggone > 0 && np != 0)
        semgone.V();
    else if (waitingzero > 0 && np == 0) {
        semgzero.V();
    } else if (waitingp > 0 && ng != 0) {
        semp.V();
    } else {
        mutex.V();
    }
}

2

int num = 0; // se è positiva rappresenta numero di gets che aspettano, se negativa, numero di puts
semaphore semput(0);
semaphore semget(0);
semaphore mutex(1);
list<T> global_list;

void put(T value) {
    //< await(num > 0) --> global_list.add(value) >
    mutex.P();
    if (num <= 0) {
        num--;
        mutex.V();
        semput.P();
        num++;
    }
    global_list.add(value);

    // signal
    if (num < 0)
        semput.V();
    else 
        semget.V();

    return;
}


list<T> get() {
    list<T> local_list;

    mutex.P();
    if (num >= 0) {
        num++;
        mutex.V();
        semget.P();
        num--;
    } else {
        semput.V();
        semget.P();
    }
    
    local_list = global_list; // fa deep copy

    // signal
    if (num > 0) {
        semget.V();
    } else {
        global_list = list<T>(); // put empty list
        mutex.V(); 
    }

    return local_list;
}