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)
/* 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
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
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;
}
}