Prove scritte 2014

Esame 24/09/2014

Testo d'esame.

Esercizio c.1 (da controllare)

La soluzione proposta fa uso della libreria pysm.

from pysm import condition, entry, monitor


class VariableBoundedBuffer(monitor):
    def __init__(self, size):
        monitor.__init__(self)
        self._q = list()
        self._max_elem = size
        self._can_write, self._can_read = condition(self) for i in range(2)

    @entry
    def write(self, x):
        if self._max_elem <= len(self._q):
            self._can_write.wait()

        self._q.append(x)
        self._can_read.signal()

    @entry
    def read(self):
        if not self._q:
            self._can_read.wait()

        retval = self._q.pop(0)

        if len(self._q) < self._max_elem:
            self._can_write.signal()

        return retval

    @entry
    def resize(self, size):
        if size < 0:
            raise ValueError("Invalid size argument:", size)

        diff = size - self._max_elem
        self._max_elem = size

        # Poiché non è possibile trovare le due code d'attesa contemporaneamente
        # non vuote e poiché non è possibile ricevere nuove richieste nel
        # frattempo, ciclare su una signal() è sicuro
        while diff > 0:
            self._can_write.signal()
            diff -= 1

Esercizio c.2 (da controllare)

class process:
    def __init__(self):
        self._stack = list()

    def lsend(dest, m):
        """
        Any process is allowed to send itself messages in a LIFO order, except
        for the empty message `""`.
        """
        if (dest == self and m == ""):
            raise ValueError('Cannot self-send the empty message ""')

        self.asend(dest, m)

    def lrecv():
        self.asend(self, "")
        m = self.arecv(process.ANY)

        # When we exit out of the loop, m.sender == self and m.text == ""
        while m.sender != self or m.text != "":
            self._stack.append(m)
            m = self.arecv(process.ANY)

        if not self._stack:
            return self.arecv(process.ANY)
        else:
            return self._stack.pop()

Esercizio g.1 (da controllare)

                                                0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
      | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
      ---------------------------------------------------------------------------------
CPU   |P1 |P1 |P1 |P1 |   |P2 |P2 |P2 |P2 |P1 |P1 |P1 |P1 |P2 |P2 |P1 |P2 |P2 |P3 |P3 |
IO    |   |   |   |   |P1 |P1 |   |   |   |P2 |P2 |   |   |P1 |P1 |   |   |   |P2 |P2 |
SPAWN |P1 |   |   |   |   |P2 |   |   |   |   |P3 |   |   |   |   |   |   |   |   |   |


      | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
      | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
      ---------------------------------------------------------------------------------
CPU   |P2 |P3 |P3 |   |   |P3 |P3 |P3 |P3 |   |   |P3 |   |   |   |   |   |   |   |   |
IO    |   |   |   |P3 |P3 |   |   |   |   |P3 |P3 |   |   |   |   |   |   |   |   |   |
SPAWN |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
 

Esercizio c.2 (da controllare)

1. No, non è richiesto. È sufficiente che il controller del dispositivo sia in grado di comunicare con la CPU sul bus e di segnalare il completamente di una delle sue operazioni al momento opportuno. (Il supporto DMA è utile se si vuole affidare la copiatura di grandi quantità di dati dalla memoria secondaria a quella primaria ai controller delle periferiche, e non alla CPU.)
2. Un timer di sistema dotato di interrupt, in grado di notificare il sistema alle scadenze del quanto di tempo.
3. Nessuno, infatti semplicità di realizzazione e basse richieste hardware compaiono tra i suoi principali vantaggi.

Esame 16/07/2014

2014.07.16.tot.pdf

Esercizio c.1 (da controllare)

/* 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 (da controllare)

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 (da controllare)

    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

Esame 03/06/2014

2014.06.03.tot.pdf

Esercizio c.1 (da controllare)

monitor sabelev
{
    #define N n //numero dei piani

    condition ok2enter[N][2]; //piano di partenza e direzione
    condition ok2exit[N]; //piano di arrivo

    procedure entry: void atfloor(int floor, int direction)
    {
        ok2exit[floor].signal(); //da il via al primo del piano che deve uscire
        ok2enter[floor][direction].signal(); //da il via al primo del piano che deve entrare e deve andare in questa direzione
    }

    procedure entry: void enter(int from, int to)
    {
        int direction;
        if(to > from) //controllo sulla direzione
            direction = 0;
        else
            direction = 1;

        ok2enter[from][direction].wait(); //mi fermo in attesa che arrivi l'ascensore
        ok2enter[from][direction].signal(); //quando arriva l'ascensore do il via a quello in attesa dopo di me
        ok2exit[to].wait(); //mi fermo dentro all'ascensore in attesa di uscire
    }

    procedure entry: void exit(int from, int to)
    {
        ok2exit[to].signal(); //do il via ad un altro che deve uscire a questo piano come me
    }

}

Esame 21/02/2014

2014.02.21.tot.pdf

Esercizio c.1 (da controllare)

monitor bbwl
{
    #define MAXELEM n

    condition ok2read;
    condition ok2write;
    condition ok2log;

    queue q1;
    queue q2;

    procedure entry: void write(eltype elem)
    {
        if (q1.size() >= MAXELEM)
            ok2write.wait();
        q1.enqueue(elem);
        ok2log.signal();
    }

    procedure entry: eltype read()
    {
        if (q2.size == 0)
            ok2read.wait();
        eltype elem = q2.dequeue();
        ok2write.signal();
        return elem;
    }

    procedure entry: eltype log()
    {
        if (q1.size() == 0)
            ok2log.wait();
        eltype elem = q1.dequeue();
        q2.enqueue(elem);
        ok2read.signal()
        return elem;
    }
}