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

Esercizio g.1 (da controllare)

Possiamo notare subito che il sistema ha due processori ed un dispositivo di I/O. A e B partono insieme al tempo 0.
C parte tra il tempo 0 ed il tempo 2 (non possiamo sapere di preciso quando perchè entrambe le CPU sono occupate).
D parte tra il tempo 0 ed il tempo 3.
A questo punto possiamo supporre che tutti e 4 i processi partano in sequenza (A, B, C, D) nello stesso momento, e ognuno prende la prima CPU libera che trova.
A lavora per 3ms, poi scade il time slice.
Nel frattempo B lavora per 2ms, poi richiede I/O per 4ms.
La CPU su cui lavora B quindi si libera, e si manda in esecuzione il processo C.
Scaduto il time slice per A, si da il controllo ad un nuovo processo. B è occupato con I/O, C sta già lavorando, quindi è il turno di D.
C lavora per 3ms, poi richiede I/O per 3ms, che però è occupato da B, quindi si mette in coda per utilizzarlo.
La CPU su cui lavorava C si libera ed il controllo torna ad A, che doveva lavorare ancora per 2ms prima di chiedere il controllo di I/O, quindi lavora e si mette in coda dietro a C.
Tornando a D, questo lavora per 3ms prima che scada il time slice. Anche B ha finito il lavoro e ha bisogno di una CPU.
In questo momento sia D che B sono nella coda dei processi in stato ready, ma dal diagramma possiamo notare che il controllo torna a D.
La CPU ha scelto a caso un processo tra i due, perchè arrivati a questo punto possiamo supporre che lo scheduler sia Round-Robin.
B prende possesso della prima CPU che si libera, ovvero quella occupata da A, poi lavora per 2ms e termina il suo lavoro.
Nel momento in cui B termina il lavoro, scade anche il time slice per D, e C termina di usare I/O.
Abbiamo due processi (C e D) in coda ready. Ma abbiamo anche due CPU libere, perchè A è in coda per I/O e ci entra appena C finisce di usarlo.
Lo scheduler sceglie di mandare C sul primo processore e D sul secondo.
A nel frattempo, lavora per 4ms con I/O.
C lavora per 3ms, poi termina il suo lavoro.
D lavora per 3ms, poi scade il time slice. Ci sono due processori liberi, quindi D riparte subito in esecuzione.
D doveva lavorare ancora per 1ms prima di aver bisogno di I/O, quindi finisce e si mette in coda.
Ma nello stesso momento A termina di usare I/O, si prende un processore libero e lavora per i suoi ultimi 2ms.
D lavora per 1ms con I/O, poi prende il secondo processore libero e lavora per 1ms prima di terminare il suo lavoro.

Il time slice è di 3ms, lo scheduler è di tipo Round-Robin.
Il dispositivo di I/O è FIFO. L'ordine con cui partono i processi è quello alfabetico.

A(){
    compute_a1(); // 5ms
    io_a(); // 4ms
    compute_a2(); // 2ms
}

B(){
    compute_b(); // 2ms
    io_b(); // 4ms
    compute_b(); // 2ms
}

C(){
    compute_c(); // 3ms
    io_c(); // 3ms
    compute_c(); // 3ms
}

D(){
    compute_d1(); // 10ms
    io_d(); // 1ms
    compute_d2(); // 1ms
}

Lo scheduler potrebbe anche essere a priorità:
Priorità B < priorità D < priorità C
Priorità A = ?
B fatto partire prima di C e D.

Esercizio g.2 (da controllare)

a) Nei sistemi embedded o in computer ad uso specifico in cui sono richiesti tempi di risposta molto rapidi. La memoria virtuale può generare ritardi imprevedibili e può richiedere un supporto hardware per la traduzione da indirizzi virtuali ad indirizzi fisici. Ma in sistemi embedded non sempre c'è spazio fisico per implementare questi supporti hardware.
b) Perchè ad esempio sulle chiavette USB quasi mai abbiamo il problema di dover utilizzare file di dimensione maggiore ai 4GB. Non utilizza il journaling, che richiede molteplici scritture per ogni azione ed in dispositivi portatili può ridurre di molto la durata. Non supporta i permessi sui file, e questo è un vantaggio per le chiavette USB, pensate per trasferire dati tra PC diversi.
c) Serve ad aumentare le performance, rendere il sistema resiliente alla perdita di uno o più dischi e poterli rimpiazzare senza interrompere il servizio. RAID serve per tutelarsi dai problemi hardware, non sostituisce i backup in quanto ci permette solo di proseguire il lavoro, non ci permette di recuperare file cancellati o bloccati da ransomware.
d) Per dimostrare questo occorre una variante del grafo di Holt, detto grafo Wait-For, che si costruisce eliminando i nodi di tipo risorsa e collassando gli archi appropriati, per cui il grafo di Holt contiene un ciclo se e solo se il grafo Wait-For contiene un ciclo e pertanto si ha l'attesa circolare (deadlock).

Esame 21/06/2018

Esercizio c.1 (da controllare)

/* Monitor tmon */

define MAX n;
define TERRAFERMA 1;
define ISOLA 2;

semaphore ok2unload;
semaphore ok2load;
semaphore ok2ship;
semaphore mutex(1); // la rampa è zona critica --> mutua esclusione

stack ferry;
int current_port = 0;

Procedure entry: al_porto(int location)
{
    current_port = location; // traghetto arriva a destinazione
    ok2unload.signal(); // da il via per far sbarcare le macchine
    ok2ship.wait(); // si ferma
    current_port = 0; // traghetto sta viaggiando tra i due porti
}

Procedure entry: imbarca(int location)
{
    mutex.wait(); // prende possesso della rampa
    ferry.push(1); // sale sul traghetto
    mutex.signal(); // libera la rampa
}

Procedure entry: imbarcato(int location)
{
    if(ferry.lenght() == MAX) // se il traghetto è pieno da il via per farlo salpare
    {
        ok2load.wait();
        ok2ship.signal();
    }
}

Procedure entry: sbarca(int location)
{
    mutex.wait(); // prende possesso della rampa
    ferry.pop(); // scende dal traghetto
    mutex.signal(); // libera la rampa
}

Procedure entry: sbarcato(int location)
{
    if(ferry.lenght() == 0) // se il traghetto è vuoto da il via per far imbarcare le macchine
    {
        ok2unload.wait();
        ok2load.signal();
    }
}

Esercizio c.2 (da controllare)

#define N n // limite operazioni
semaphore mutex(1); // sezione critica

class unsigned_semaphore()
{
    unsigned int value;
    semaphore plus;
    semaphore minus;
    
    P()
    {
        mutex.P();
        if(value < N)
        {
            if (value >= 0)
            {
                plus.P();
            }
            else
            {
                minus.V();
            }
            value--;
        }
        mutex.V();
    }

    V()
    {
        mutex.P();
        if(value > -N)
        {
            if (value <= 0)
            {
                minus.P();
            } 
            else
            {
                plus.V();
            }
            value++;
        }
        mutex.V();        
    }
}

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