Prove scritte 2014
Jump to navigation
Jump to search
Esame 24/09/2014
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)
- 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.)
- Un timer di sistema dotato di interrupt, in grado di notificare il sistema alle scadenze del quanto di tempo.
- Nessuno, infatti semplicità di realizzazione e basse richieste hardware compaiono tra i suoi principali vantaggi.
Esame 16/07/2014
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
Esercizio c.1 (da controllare)
Questo svolgimento è basato sulla libreria pysm ricavabile da Tool per semafori e monitor.
from enum import auto, Enum
from pysm import condition, entry, monitor
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.
"""
# 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[k] = v if v users are waiting to get off at floor k
self._exits = {f: 0 for f in range(floors)}
# Is the elevator allowed to close its door?
self._can_close = condition(self)
@entry
def at_floor(self, floor, direction):
self._queue[floor][direction].signal()
while self._exits[floor] > 0:
self._can_close.wait()
@entry
def 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 exit(self, _from, to):
self._exits[to] -= 1
self._can_close.signal()
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
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;
}
}