Prove scritte 2019
Jump to navigation
Jump to search
Esame 18/06/2019
Esercizio c.1 (da controllare)
monitor pg{
int waitingReader = 0;
int waitingWriter = 0;
condition ok2write;
condition ok2read;
T datobuf;
entry put (T dato) {
if (waitingReader > 0)
datobuf = dato;
while (waitingReader > 0)
ok2read.signal();
else if (waitingWriter >= 0)
waitingWriter++;
ok2write.wait();
waitingWriter--;
datobuf = dato;
}
entry T get (void) {
if (waitingReader > 0 || waitingWriter == 0)
waitingReader++;
ok2read.wait();
waitingReader--;
else if (waitingWriter > 0)
ok2write.signal();
return datobuf;
}
}
Esercizio c.1 (da controllare)
monitor taon {
condition ok2w, ok2r;
int nw, nr = 0;
T buf;
entry void put (T dato){
nw++;
if( nw != 1 || nr == 0)
ok2w.wait();
buf = dato;
for (i=0, i++, i < nr)
ok2r.signal();
nw--;
}
entry T get(){
nr++;
if(nw==0)
ok2r.wait();
ok2w.signal();
T dato = buf;
nr --;
return dato;
}
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)
- 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.
- 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.
- 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.
- 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 18/05/2019
Esercizio c.1 (da controllare)
- Controllato dall'utente Lusvelt in data 26/08/2020 (sbagliato, dal testo si evince che se manca anche solo un componente bisogna mettersi in attesa finchè non arrivi, per poi prendere anche gli altri).
- ...
Il sorgente seguente può essere eseguito scaricando in una stessa directory il package pysm del prof. Davoli.
#!/usr/bin/env python3
import threading
from array import array
from pysm.monitor import condition, entry, monitor
class storage(monitor):
ELEMS = 16
"""
Implementazione che permette l'avanzamento degli operai in presenza di
altri operai in attesa.
"""
def __init__(self):
monitor.__init__(self)
self._v = array('L', self.ELEMS * [0])
self._c = tuple(condition(self) for i in self._v)
# self._requests[i] = [l1, l2, ..., ln] se per l'attrezzo i ci sono in
# attesa n processi che richiedono ciascuno l1, l2, ..., ln unita'
self._requests = {i: list() for i in range(self.ELEMS)}
@entry
def add(self, components):
if len(components) != self.ELEMS:
raise ValueError("components must contain exactly ELEMS elements")
for i, c in enumerate(components):
self._v[i] += c
# Finche' per il componente i ci sono richieste in sospeso che
# possono essere soddisfatte, svegliamo il processo in attesa, che
# proseguira' col richiedere i componenti successivi
while self._requests[i] and self._requests[i][0] <= self._v[i]:
self._c[i].signal()
@entry
def get(self, components):
if len(components) != self.ELEMS:
raise ValueError("components must contain exactly ELEMS elements")
for i in range(len(components)):
if components[i] <= self._v[i]:
self._v[i] -= components[i]
else:
components[i] -= self._v[i]
self._v[i] = 0
self._requests[i].append(components[i])
self._c[i].wait()
self._v[i] -= components[i]
self._requests[i].pop(0)
def request(m, q):
"""
Funzione processo che simula la richiesta di un operaio.
"""
name = threading.current_thread().name
print("[%s] Requesting %s" % (name, q))
m.get(q)
print("[%s] Done requesting" % (name))
def supply(m, s):
"""
Funzione processo che simula il rifornimento di un magazziniere.
"""
name = threading.current_thread().name
print("[%s] Supplying %s" % (name, s))
m.add(s)
print("[%s] Done supplying" % (name))
def main():
m = storage()
requests = [
threading.Thread(name='req1', target=request, args=(m, [4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
threading.Thread(name='req2', target=request, args=(m, [0, 0, 2, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
threading.Thread(name='req3', target=request, args=(m, [4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
threading.Thread(name='req4', target=request, args=(m, [4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
threading.Thread(name='req5', target=request, args=(m, [4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
]
supplies = [
threading.Thread(name='supply1', target=supply, args=(m, [4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
threading.Thread(name='supply2', target=supply, args=(m, [4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
threading.Thread(name='supply3', target=supply, args=(m, [4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
threading.Thread(name='supply4', target=supply, args=(m, [4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
threading.Thread(name='supply5', target=supply, args=(m, [0, 0, 2, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
]
for t in requests + supplies:
t.daemon = True
t.start()
for t in requests + supplies:
t.join()
return 0
if __name__ == "__main__":
exit(main())
Esercizio c.2 (da controllare)
unsigned procs_in = 0;
semaphore mutex = new binary_semaphore(1);
queue<semaphore> semaphores = new queue<>();
sau_enter () {
mutex.P();
procs_in++;
mutex.V();
}
sau_exit () {
mutex.P();
procs_in--;
if (procs_in > 0) {
semaphore s = new semaphore(0);
semaphores.enqueue(s);
mutex.V();
s.P();
} else {
while (!sempahores.empty())
semaphores.dequeue().V();
mutex.V();
}
}
Esercizio g.1 (da controllare)
Domanda a)
Poiché lo scheduler è non-preemptive, una volta assegnata la CPU ad un dato processo, questi non viene cambiato finché non ha terminato. Visto il vincolo nel testo della consegna, una volta concluso il processo corrente si hanno solo due scelte: selezionare il più recente processo A o il più recente processo B.
Nuovi processi A partono ogni 6ms, nuovi processi B ogni 8ms; gli intervalli di tempo in cui partono sia processi A sia processi B sono multipli di mcm(6, 8) ms = 24ms: cioè ai tempi 0ms, 24ms, 48ms, 72ms, ..., parte sia un processo A sia un processo B.
In ognuno di questi intervalli di 24ms, si susseguono sia processi A sia processi B. I processi A sono 24ms / 6ms = 4, i processi B 24ms / 8ms = 3; i primi richiedono 4 * 3ms = 12ms, i secondi 3 * 4ms = 12ms. È possibile dimostrare induttivamente che ad ogni nuovo intervallo di 24ms, i processi di quello precedente sono stati tutti svolti e che quelli correnti saranno terminati entro 24ms (infatti ad ogni 24ms, è un po' come se le condizioni iniziali venissero ristabilite). Pertanto è possibile eseguire entrambi i processi senza portare a starvation.
Domanda b)
Ragionamento analogo al punto precedente, con alcune differenze date dalle permutazioni in cui certi processi vengono schedulati.
Domanda c)
Per definizione, uno scheudler round-robin garantisce possibilità di esecuzione a tutti i processi, pertanto è possibile. La figura mostra un intervallamento di scheduling secondo criterio RR che evidenzia come sia possibile completare tutti i processi entro i 24ms.
Esercizio g.2 (da controllare)
- Basso, perché vengono generate molte page trap. Così facendo i processi direttamente interessati devono attendere il caricamento delle pagine di memoria ed essere posti in attesa, riducendo l'utilizzazione della CPU.
- Sì, ad esempio il MBR (Master Boot Record) e l'area di swap. Il MBR contiene meta-informazioni sul disco stesso e non è adatto a contenere informazioni concrete, mentre l'area di swap può essere considerata un'estensione della memoria centrale del calcolatore.
- Flessibile, perché se intendo riconfigurare alcuni parametri del sistema non occorre ricompilare il kernel, ma solamente riscrivere/riconfigurare e rilanciare il programma che si fa carico del servizio in questione; affidabile, in quanto i servizi di sistema sono realizzati tramite processi a livello utente, e un loro crash non si ripercuote sull'intero sistema; meno efficiente (di un kernel monolitico) in quanto i vari servizi comunicano con il kernel non tramite chiamate di sistema, ma un vero e proprio servizio di message passing tra processi, che aggiunge overhead.
- Come voci di una directory che puntano allo stesso inode (laddove il file system sia basato su inode) o più in generale allo stesso FCB (File Control Block). Per determinare se un dato FCB non è più linkato da nessuna voce (entry) si utilizza un contatore che rappresenta il numero corrente di riferimenti; quando questo diventa 0, il FCB può essere eliminato dal file system.
Esame 14/02/2019
Esercizio c.1 (possibile soluzione corretta)
# Original authors: Mattia Guazzaloca & Paolo Marzolo
#
# Contributors:
#
class monobinarysem(monitor):
def __init__(self, val):
self.iszero = condition(self)
self.val = val
@entry
def monoP(self):
if self.val == 0:
self.iszero.wait()
self.val -= 1
@entry
def monoV(self):
if self.val == 0:
self.val += 1
self.iszero.signal()
Esercizio c.2 (soluzione corretta)
# Original author: Renzo Davoli (durante la lezione)
#
# Contributors:
#
def pssend(message, destination):
asend((self(),message),destination)
while(1):
snd, message = arecv(ANY)
if(message == ACK):
break
datastruct.add(snd, message)
def psreceive(sender):
dummy = Message(null)
asend(self(),dummy) //self is my id
while(1):
snd, message = arecv(ANY)
if(message == dummy):
break
datastruct.add(snd, message)
if (datastruct.match(sender)):
src, msg = datastruct.get(sender)
asend((self(),ACK), src)
return msg
else:
return None
Esame 28/05/2019
Esercizio c.1 (da controllare)
monitor storage:
[16] int vector
[16] condition ok2get
[16] bool available = { 1, ..., 1 }
entry get([16] int components):
for (i from 0 to 15):
while ((components[i] > vector[i]) || !available[i]):
if (available[i]):
available[i] = false
ok2get[i].wait()
vector[i] -= components[i]
available[i] = true
ok2get[i].signal()
entry add([16] int components):
for (i from 0 to 15):
vector[i] += components[i]
available[i] = true
ok2get[i].signal()
Esercizio c.1 (da controllare)
monitor storage{
int stored[16]
int components[16]
condition ok2make[16]
boolean required[16] //false
void add(components){
stored += components;
for(i=0; i< 16; i ++){
if(required[i] == true)
ok2make(i).signal();
}
}
void get(components){
for(i = 0; i< 16; i++){
if (stored[i] >= components[i])
stored[i] -= components[i]
else
required[i] = true
ok2make(i).wait();
required[i] = false
i—;
}
}
Esame 15/07/2019
Esercizio c.1
- Verifica del 18/05/2020 dell'utente Acsor. Ritengo sia: corretto
- Verifica del ... dell'utente ... . Ritengo sia: ...
- ...
Una semplice realizzazione in Python dello pseudocodice seguente è disponibile qui.
# Original authors: Mattia Guazzaloca, Paolo Marzolo
#
# Contributors: utente Acsor
monitor pair_buffer:
int nw, nr;
queue buffer;
condition same_number;
pair_buffer():
nw = nr = 0
buffer = queue()
same_number = condition()
@entry
put(T x):
nw++;
buffer.enqueue(x);
if nw != nr:
same_number.wait();
same_number.signal();
nw--;
@entry
T get(void):
nr++;
if nw != nr:
same_number.wait();
else:
same_number.signal();
T val = buffer.dequeue();
same_number.signal();
nr--;
return val;
Esame 13/09/2019
Testo: 2019.09.13.tot.pdf
Esercizio c.1
Controllato dal professor Davoli durante la lezione del 19/05/2020.
# Original author: Andrea R.
monitor mbuf:
waiting = 0
queue<pair<T, int>> q # (dato, molteplicità)
condition ok2add # q.length() < MAXELEM
condition ok2get # q.length() > 0
entry void add(T data, int n):
if q.length() >= MAXELEM:
ok2add.wait()
q.enqueue({data, n})
if waiting >= q.front().second:
ok2get.signal()
entry T get():
waiting++ # vuole ricevere
if q.empty() or waiting < q.front().second: # cortocircuitato
ok2get.wait()
x = q.front().first
q.front().second--
waiting-- # riceve
if q.front().second > 0: # cascata
ok2get.signal()
else: # ultimo che riceve
q.dequeue()
ok2add.signal()
return x