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

Soluzioni proposte da: Mattia Biondi (da controllare)

Esercizio c.1

// 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.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 proposta:

stack s;

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

obj sreceive(process p)
{
    obj msg;
    while(msg = areceive(p))
    {
        s.push(msg);
    }
    asend(ack, p);
    return s.pop();
}

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();
    }
}

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