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

        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)

• Controllato in data 11:30, 12 September 2020 (CEST) dall'utente Acsor (talk). Ritengo sia: corretto (perché svolto in maniera pressappoco identica al mio)

monitor BoundedBuffer {
	queue<T> q;

	// Condition: oktoread: q.length > MIN
	// Condition: oktowrite: q.length < MAX
	condition oktoread, oktowrite;

        BoundedBuffer () {
            q = new queue<>();
            oktoread = new condition(this);
            oktowrite = new condition(this);
        }

	procedure entry T read() {
		if (q.length <= MIN) // Controllo
			oktoread.wait();

		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 (T elem) {
		if (q.length() >= MAX) // Controllo
			oktowrite.wait()

		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

Testo d'esame.

Esercizio c.1 (da controllare)

Questo svolgimento è basato sulla libreria pysm ricavabile da Tool per semafori e monitor.

#!/usr/bin/env python3
import threading

from enum import auto, Enum
from pysm.monitor import condition, entry, monitor
from random import randint


class Direction(Enum):
    UP = auto()
    DOWN = auto()

    @classmethod
    def from_int(cls, x):
        """
        :return: `UP` if `x > 0`, `DOWN` if `x < 0` or raise an error otherwise.
        """
        if x > 0:
            return cls.UP
        elif x < 0:
            return cls.DOWN
        else:
            raise ValueError("Unaccepted value 0")


class Elevator(monitor):
    def __init__(self, floors):
        """
        :param floors: number of floors.
        """
        monitor.__init__(self)

        # Total floors number and current floor, respectively
        self.floors, self._floor = floors, None
        # self._queue[f][dir] = condition queue associated with floor f and direction dir
        self._queue = {
            f: {d: condition(self) for d in Direction} for f in range(floors)
        }
        # self._exits[f] = k if k processes are to exit at floor f
        self._exits = {f: 0 for f in range(floors)}
        # Can the elevator close its door?
        self._can_close = condition(self)

    @entry
    def at_floor(self, floor, direction):
        self._floor = floor
        self._queue[floor][direction].signal()

        if self._exits[floor] > 0:
            self._can_close.wait()

    @entry
    def user_enter(self, _from, to):
        direction = Direction.from_int(to - _from)

        self._queue[_from][direction].wait()
        self._queue[_from][direction].signal()

        self._exits[to] += 1

    @entry
    def user_exit(self, _from, to):
        direction = Direction.from_int(to - _from)

        if self._floor != to:
            self._queue[to][direction].wait()
            self._queue[to][direction].signal()

        self._exits[to] -= 1

        if self._exits[to] == 0:
            self._can_close.signal()


def elevator(e: Elevator):
    name = threading.current_thread().name

    while True:
        for i in range(e.floors):
            print("[%s] Going to floor %d" % (name, i))
            e.at_floor(i, Direction.UP)

        for i in range(e.floors - 1, -1, -1):
            print("[%s] Going to floor %d" % (name, i))
            e.at_floor(i, Direction.DOWN)


def user(e: Elevator):
    name = threading.current_thread().name

    while True:
        _from, to = randint(0, e.floors - 1), randint(0, e.floors - 1)

        if _from != to:
            print("[%s] Entering from %d to %d" % (name, _from, to))
            e.user_enter(_from, to)
            print("[%s] Exiting from %d to %d" % (name, _from, to))
            e.user_exit(_from, to)


def main():
    try:
        e = Elevator(6)
        threads = [
            threading.Thread(name='elevator', target=elevator, args=(e, )),
            threading.Thread(name='user0', target=user, args=(e, )),
            threading.Thread(name='user1', target=user, args=(e, )),
            threading.Thread(name='user2', target=user, args=(e, )),
            threading.Thread(name='user3', target=user, args=(e, )),
        ]

        for t in threads:
            t.daemon = True
            t.start()

        for t in threads:
            t.join()
    except KeyboardInterrupt:
        print("Bye")

    return 0


if __name__ == "__main__":
    exit(main())

Esercizio c.1 (sbagliato)

• Stato: sbagliato. Non viene garantita la seguente proprietà, specificata dalla consegna: Quando l'ascensore arriva ad un piano non puo' ripartire se non sono scese tutte le persone che volevano giungere a quel piano. Infatti se ci sono uno o più utenti in attesa di uscire ad un dato piano x, allora atfloor(x, dir) sbloccherà un solo utente dalla sua chiamata a enter() senza che questi (e, assieme a lui, altri utenti in attesa di scendere) invochi exit(). Acsor (talk) 17:19, 12 September 2020 (CEST)

// numero dei piani
#define N n

monitor sabelev {
    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 = to > from ? 0: 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;
    }
}