Prove svolte e soluzioni proposte

Questa pagina serve a raccogliere prove d'esame svolte (che possono essere utili alla preparazione) e soluzioni proposte a tali prove da sottoporre a peer-review.

Esame 19/09/2018

Esercizio c.1 (sbagliato)

// Condition: MAX
// Condition: ok2load
// Condition: ok2unload
// Condition: ok2move

int airport_codes = [BLQ, CDG, BRX, LGW, FCO, ...]
struct luggage {
    int dstcode;
    int owner;
};
luggage cart[MAX];
int loaded = 0;

Procedure entry: void cartat(int code)
{
    if(code == 0)
    {
        ok2unload.wait();
        ok2load.signal();
    }
    else
    {
        ok2load.wait();
        ok2unload.signal();
    }
}

Procedure entry: void load(int dstcode, int owner)
{
    ok2move.wait();
    if(loaded < MAX)
    {
        luggage l;
        l.dstcode = dstcode;
        l.owner = owner;
        cart.push(l);
        loaded++;
    }
    else ok2move.signal();
}

Procedure entry: int unload(int dstcode)
{
    ok2move.wait();
    int i;
    for(i=0; i<loaded; i++)
    {
        if(cart[i].dstcode == dstcode)
        {
            int owner = cart[i].owner;
            cart[i].remove();
            loaded--;
            return owner;
        }
    }
    else ok2move.signal();
}

Esercizio c.1

monitor dispatch
condition go_cart;
condition ok2station; // quando la stazione può caricare
current_station = None
// dizionario con chiave destinazione
luggages = {}

def countl(luggages):
    n=0
    for d in luggages:
        n += len(luggages[d]);

p.e. cartat(code):
    current_station = code // carrello arriva alla stazione
    if (code == BLQ || len(luggages[code]) > 0):
        ok2station[code].signal()
        go_cart.wait()
    current_station = None // il carrello sta viaggiando tra le stazioni

p.e. load(dst, owner):
    if (current_station != BLQ || countl(luggages) >= MAX):
        ok2station(BLQ).wait()
    luggages[dst].append(owner)
    if (countl(luggages) >= MAX)
        go_cart.signal()
    
p.e. unload(dst):
    if (current_station != dst || len(luggages[dst]) == 0)
    // lunghezza lista dei bagagli con questa destinazione
        ok2station(dst).wait()
    owner = luggages[dst].pop()
    if len(luggages[dst]) == 0)
        go_cart.signal()
    return owner

Esercizio c.2

/* MP sincrono dato quello asincrono */

void ssend(obj msg, process q)
{
    asend(msg, q);
    ack = areceive(q);
}

obj sreceive(process p)
{
    obj msg = areceive(p);
    asend(ack, p);
    return msg;
}

Soluzione:

dati asend/arecv devo implementare lssend lsrecv

lssend(dst, msg):
    asend(dst, (MSG, myid(), msg))
    arecv(dst)

lsrecv(snd):
    asend(myid(), (TAG, myid(), NULL))    // mi mando un messaggio che riesco a riconoscere
    while True:
        (T, s, m) =  arecv(ANY)           // continua a ricevere finchè non ricevi il mio messaggio
        if (T != TAG) data.push(s, m)
        else break
    while (((s,m) = data.pop(snd) == NULL):   // c'è il messaggio di src definito?
        (T, s, m) =  arecv(ANY)
        data.push(s, m)
    asend(s, (ACK, myid(), NULL)
    return m

Esercizio g.1 (sbagliato)

x = long_compute()/short_compute()
X = io()

   0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 8 8 8
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
P1 |x|x|x|x|x|X|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|x|x|-|-|-|-|-|-|x|x|x|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|X|x|-|-|-|-|-|-|x|-|-|
P2         |-|-|x|x|x|-|-|-|-|-|-|x|x|-|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|X|x|-|-|-|-|-|-|x|x|x|-|-|-|-|-|-|x|-|-|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|X|x|-|-|-|x|-|-|
P3               |-|-|x|x|x|-|-|-|-|-|-|x|x|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|X|x|-|-|-|-|-|-|x|x|x|-|-|-|-|-|-|x|-|-|-|-|-|-|-|-|X|X|X|-|-|-|X|X|x|x|
 

Esercizio g.1

P1(start=0): 5ms CPU, 5ms IO, 5ms CPU, 5ms IO, 2ms CPU
P2(start=4): 5ms CPU, 5ms IO, 5ms CPU, 5ms IO, 2ms CPU
P3(start=7): 5ms CPU, 5ms IO, 5ms CPU, 5ms IO, 2ms CPU

 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 
P|1 1 1|1 1|2 2 2|3 3 3|2 2|1 1 1|3 3|1 1|2 2 2*3 3 3|2 2|3 3|1 1|-|2 2|- - -|3 3|
I          |1 1 1 1 1|     |2 2 2 2 2|3 3 3 3 3|1 1 1 1 1|2 2 2 2 2|3 3 3 3 3|

r - - - - 2 - - 3 2 2 2 1 1 3 3 3 1 1 2 2 - - - 2 2 2 3 3 1 1
                      1 3 3

* 3 ha finito input output e 2 è ancora in esecuzione quindi c'è da scegliere
 

Esercizio g.2 (da controllare)

a) Può richiedere supporto hardware. Se implementato con contatori o stack questi devono essere aggiornati ad ogni riferimento alla memoria. L'intero sistema viene appesantito e rallentato.
b) Il journaling si assicura che i dati sul filesystem siano consistenti, ma non aggiornati. Assicura la coerenza dei dati, ma non la perdita dei file se il filesystem si danneggia.
c) Si dice che un programma A ha lo stesso potere espressivo di un programma B quando è possibile esprimere ogni programma scritto con B mediante A. Per implementare MP sincrono dato quello asincrono basta aggiungere una libreria. Per implementare MP asincrono dato quello sincrono bisogna aggiungere un processo server.
d) In questi casi tutte le istruzioni vengono eseguite con la massima autorità, con problemi di sicurezza nel caso un utente estraneo prenda il controllo del sistema o rischio di commettere gravi errori semplicemente sbagliando a digitare un comando.

Esame 17/07/2018

Esercizio c.1

/* Monitor Delirum: */

// Condition: Ok2Load;
// Condition: Ok2Pour[]; // Un elemento per Type
int availableBeer[]; // Un elemento per Type 
Queue requests[]; // Un elemento per Type
Queue pendingRequests;

Procedure entry: void Pour(Type t, Quantity c)
{
    if (c > availableBeer[t]) // Richiesta maggiore della birra disponibile
    {
        c -= availableBeer[t];
        availableBeer[t] = 0;              
        requests[t].Enqueue(c);
        if (requests[t].Length == 1) // Risveglio un magazziniere solo se è la prima richiesta di questo tipo di birra
        {
            pendingRequests.Enqueue(t);
            Ok2Load().Signal();
        }
        Ok2Pour[t].Wait();
        requests[t].Dequeue(); // Quando ho ottenuto la birra che voglio, elimino la mia richiesta
    }
    availableBeer[t] -= c;
}

Procedure entry: Type isEmpty()
{
    if (pendingRequests.Length == 0)
    {
        Ok2Load.Wait();
    }
    return pendingRequests.Dequeue();
}

Procedure entry: Loaded(Type t, Capacity c)
{
    availableBeer[t] += c;
    while (requests[t].Length > 0 && availableBeer[t] > requests[t].head())
    {
        Ok2Pour[t].Signal();
    }

    if (requests[t].Length > 0) // serve per evitare che a causa di un magazziniere lento si accodino cosi tante richieste che mentre si sta caricando si svuota subito il fusto
    {
        pendingRequests.Enqueue(t);
        Ok2Load.Signal();
    }
}

Esercizio c.2 (da controllare)

stack s;
semaphore mutex(1); // mutua esclusione
semaphore ok2consume(0);

Procedure entry: void push(int value)
{
    mutex.P();
    s.push(value)
    mutex.V()
    ok2consume.V()
}

Procedure entry: int pop()
{
    int value;
    ok2consume.P();
    mutex.P();
    value = s.pop();
    mutex.V();
    return value;
}

Esame 29/05/2017

Esercizio c.1

condition okpartita
condition ok2chiama
condition ok2punteggio
condition ok2run[2][MAX]
int numpronti
int punteggio[2]
boolean partita=false
boolean partitafinita=false
chiamati = []
contabandiera[2]
int winner

p.e. nuovapartita():
{
    punteggio[A] = punteggio[B] = 0;
    numpronti = 0;
    partita=true;
    okpartita.signal()
    chiamati = [];
}
p.e. chiama(l):
{
    if (numpronti<2*MAX)
    {
        ok2chiama.wait();
    }
    chiamati = l;
    contabandiera[A] = contabandiera[B] = 0
    winner = -1;
    for (s in n)
    {
        ok2run[A][s].signal();
        ok2run[B][s].signal()
    }
    ok2punteggio.wait();
    punteggio[winner++]
    if (max(punteggio) == 10)
    {
        partitafinita = true;
        for (s in A,B)
        {
            for (n in range(MAX))
            {
                ok2run[s][n].signal();
            }
        }
    }
    return punteggio;
}
p.e. pronto(s, n):
{
    if (partitafinita) return 1;
    if (!partita)
    {
        okpartita.wait();
    }
    numpronti++;
    if (numpronti>=2*MAX)
    {
        ok2chiama.signal();
    }
    if (!(n in chiamati))
    {
        ok2run[s][n].wait();
    }
    numpronti--;
    return 0 if partita else 1;
}
allabandiera(s, n):
{
    contabandiera[s]++;
    if (winner == -1 && contabandiera[s] == len(chiamati))
    {
        winner = s;
    }
    if (contabandiera[A] == len(chiamati) && contabandiera[B] == len(chiamati))
    {
        ok2punteggio.signal();
    }
}

Esame 16/07/2014

Esercizio c.1

/* Monitor Bounded Buffer: (non richiesto dall'esercizio) */
queue q;
condition oktoread; // q.length() > 0
condition oktowrite; // q.length() < MAX

procedure entry type read():
    if (q.length() == 0) oktoread.wait(); // controllo
    retval = q.dequeue(); // cambio lo stato
    // abilito coloro che possono essere abilitati dal cambiamento di stato
    oktowrite.signal() 
    return retval;

procedure entry void write(type elem):
    if (q.length() >= MAX) oktowrite.wait(); //controllo
    q.enqueue(elem); // cambio lo stato
    oktoread.signal(); // abilito chi può essere abilitato

/* NOTE:
 * procedure entry ==> dichiarazione di funzioni (senza vedere l'implementazione 
 * dall'esterno)
 */

/* Min-Max Monitor Bounded Buffer: */

Queue Q;

// Condition: OKTOREAD: Q.Length > MIN
// Condition: OKTOWRITE: Q.Length < MAX

procedure entry: Type Read():
{
    if (Q.Length <= MIN) OKTOREAD.Wait(); // Controllo
    retval = Q.Dequeue(); // Cambio di stato
    OKTOWRITE.Signal(); // Abilito chi vuole scrivere
    return retval; // Qui sono sicuro perchè ne ho eliminato uno prima
}

procedure entry: void Write(Type elem):
{
    if (Q.Length >= MAX) OKTOWRITE.Wait() // Controllo
    Q.Enqueue(elem); // Cambio di stato
    if (Q.Length > MIN) OKTOREAD.Signal(); // Abilito chi vuole leggere
}

Esercizio c.2

Semaphore mutex = 1;

struct Elem
{
    Semaphore s;
    int counter;
}

struct Elem V[]; // Vettore a dimensione variabile. I nuovi elementi sono initializzati a s = 0, counter = 0.

void RendezVouz(int n)
{
    mutex.P(); // Blocco, decremento di 1 (il processo si blocca se il semaforo vale 0)
    V[n].counter++;
    if (V[n].counter < n)
    {
        mutex.V(); // Rilascia, incrementa di 1
        V[n].s.P();
    }
    V[n].counter--;
    if (V[n].counter > 0)
        V[n].s.V();
    else
        mutex.V();       
}

Esercizio g.1

    0241302 ==> soluzione corretta
(0)2   2200
(1)3   1111
(2)4   4442
(3)0   0333

    2 3 4 0 1 2 3 4  0  1  2  3 ==> soluzione proposta, non corretta perchè non è la stringa più corta 
2           1 1 1 1  0  0  0  0
3           3 2 2 2  2  1  1  1
4           4 4 3 3  3  3  2  2
0           0 0 0 4  4  4  4  3