Difference between revisions of "Prove scritte 2019"
Jump to navigation
Jump to search
| Line 1: | Line 1: | ||
| − | + | = Esame 18/06/2019 = | |
[http://www.cs.unibo.it/~renzo/so/compiti/2019.06.18.tot.pdf 2019.06.18.tot.pdf] | [http://www.cs.unibo.it/~renzo/so/compiti/2019.06.18.tot.pdf 2019.06.18.tot.pdf] | ||
| − | + | == Esercizio c.1 (da controllare) == | |
<source lang="c"> | <source lang="c"> | ||
monitor pg{ | monitor pg{ | ||
| Line 43: | Line 43: | ||
<br> | <br> | ||
| − | + | == Esercizio c.1 (da controllare) == | |
<source lang="c"> | <source lang="c"> | ||
monitor taon { | monitor taon { | ||
| Line 72: | Line 72: | ||
<br> | <br> | ||
| − | + | == Esercizio c.2 == | |
**non è l'esercizio corretto** | **non è l'esercizio corretto** | ||
<source lang="c"> | <source lang="c"> | ||
| Line 113: | Line 113: | ||
<br> | <br> | ||
| − | + | == Esercizio g.1 (sbagliato) == | |
<nowiki> | <nowiki> | ||
x = long_compute()/short_compute() | x = long_compute()/short_compute() | ||
| Line 126: | Line 126: | ||
<br> | <br> | ||
| − | + | == Esercizio g.1 == | |
<nowiki> | <nowiki> | ||
P1(start=0): 5ms CPU, 5ms IO, 5ms CPU, 5ms IO, 2ms CPU | P1(start=0): 5ms CPU, 5ms IO, 5ms CPU, 5ms IO, 2ms CPU | ||
| Line 145: | Line 145: | ||
| − | + | == 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. | # 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. | # 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. | ||
Revision as of 23:10, 25 March 2023
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
- non è l'esercizio corretto**
/* 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 ? in data ?
- ...
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
def __init__(self):
"""
Implementazione che permette l'avanzamento degli operai in presenza di
altri operai in attesa.
"""
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 (da controllare)
- Controllato dall'utente Acsor (talk) in data 16:03, 2 September 2020 (CEST). Ritengo sia: corretto
- Controllato dall'utente ? in data ?
# Original authors: Mattia Guazzaloca, Paolo Marzolo
#
# Contributors: utente Acsor
class monobinarysem(monitor):
def __init__(self, val):
monitor.__init__(self)
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 (controllato)
# 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
Esercizio g.1
In un sistema monoprocessore mostrare un caso nel quale l'algoritmo di scheduling FIFO e quello Round Robin producano la stessa sequenza di esecuzione (per evitare casi banali si richiede che siano presenti almeno 3 processi e ognuno faccia almeno due operazioni di I/O).
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
- Ritenuta corretta Flecart (talk) 15:30, 17 January 2023 (CET)
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;
Esercizio c.2 (da controllare)
Viene ritornata x stessa, in un numero di iterazioni pari a length(x). Il calcolo viene svolto tramite message passing tra processi client e processo server; quest'ultimo opera una sorta di iterazione inoltrando a se stesso il messaggio spedito da un client finché x != "".
Se più processi chiamano la funzione dilemma() allo stesso tempo, ciò non causa disagi nel calcolo del risultato finale. Infatti l'identificatore del processo cliente destinatario è memorizzato in pid, e protratto fino alla chiamata in cui x == "". Inoltre la presenza di molteplici richieste non causa sovrapposizione, posto che asend() memorizzi il contenuto di messaggi in sospeso in una coda FIFO.
Esame 13/09/2019
Testo: 2019.09.13.tot.pdf.
Esercizio c.1 (controllato)
- Controllato dal professor Davoli durante la lezione del 19/05/2020.
- Controllato dall'utente Acsor (talk) in data 19:13, 1 September 2020 (CEST).
- Controllato Flecart (talk) 16:09, 17 January 2023 (CET)
# 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
Esercizio c.2
Il programma è composto da due processi, ognuno dei quali stampa all'infinito il proprio identificatore. Perché sia possibile stampare è però necessario attendere il proprio turno, condizione gestita dal monitor bohm: esso possiede due stati (0 o 1) ed è possibile entrarvi quando l'id del processo invocante e il valore dello stato corrispondono; la procedura post() di bohm setta lo stato al valore complementare e sveglia il processo in attesa sulla coda di condizione corrispondente (al nuovo stato).
È possibile implementare il meccanismo di sincronizzazione con semafori tramite il codice seguente
binary_sempahore[2] sem = {new binary_semaphore(1), new binary_semaphore(0)};
void pre (int n) {
sem[n].P();
}
void post (int n) {
sem[1 - n].V();
}
Esercizio c.2 (da controllare)
L'output dei due processi è printare in modo alterno 0, 1, 0, 1.... Non rispetta condizione di minimalità di istruzioni e variabili, quindi non sarebbe la soluzione migliore.
int state = 0;
semaphore turn(0);
semaphore mutex(1);
void pre(int n) {
mutex.P();
if (state != n) {
mutex.V();
turn.P();
} else {
mutex.V();
}
}
void post(int n) {
mutex.P();
state = 1 - state;
turn.V();
mutex.V();
}
Esercizio g.1 (da controllare)
- Controllato dall'utente ? in data ?
- ...
Date le variabili del problema x, y ed m, bisogna avere x < m, x < y e che il tempo di arrivo dei processi P1, P2 e P3 durante lo scheduling RR sia P1, P2 e P3. Per ulteriori informazioni vedere lo svolgimento in figura. (Nota: non è specificata la relazione tra y ed m né sono considerati i casi x = m e x = y.)
Esercizio g.2 (da controllare)
- Le opzioni per comunicare con le periferiche di IO sono solitamente due: polling (sondaggio) e interrupt. Mediante il polling il sistema verifica costantemente lo stato dei dispositivi di IO prendendo azione quando esso cambia, con gli interrupt sono i dispositivi stessi a notificare il cambiamento del loro stato. Poiché fare polling significa eseguire ciclicamente delle istruzioni che svolgano il controllo, ricevere degli interrupt è più efficiente perché nello stesso tempo è possibile svolgere altro lavoro utile.
- Da svolgere.
- Quando bisogna svolgere un'operazione di swap-in (caricamento di una pagina dalla memoria secondaria a quella primaria) e di swap-out (inversa alla precedente). L'algoritmo di rimpiazzamento è invocato durante un'operazione di swap-in che vede la memoria centrale completamente occupata: in tal caso sarà necessario individuare una pagina da spostare in memoria secondaria.
- Vantaggi: dimensioni del file eseguibile finale ridotte, in quanto non è richiesto mantenere all'interno dello stesso una copia delle procedure di cui ci si serve; risparmio in memoria centrale: per un dato simbolo appartenente ad una data libreria, è possibile riservare un solo spazio in memoria condiviso da più processi che ne hanno bisogno. Svantaggi: versionamento, ovvero l'installazione di versioni più aggiornate della stessa libreria in conflitto con quelle meno recenti: tale problema è risolto mediante la definizione precisa di numeri di versione delle librerie e la specificazione delle dipendenze (rispetto ad un dato numero di versione).
Esame 2019/01/15
Esercizio c1
Soluzione proposta 1
monitor wsem {
condition cond;
queue<int> waiting;
wsem(value) {
this->value = value;
}
P(int w) {
if (w > value || waiting.size() > 0) {
waiting.enqueue(w);
cond.wait();
}
value -= w;
}
V(int w) {
value += w;
while (waiting.size() > 0 && waiting.front() <= value) {
waiting.dequeue();
cond.signal();
}
}
}
Esercizio c2
ms_send(pid dest, msg_t msg) {
asend(dest, <msg, getpid()>);
ack = arecv(dest);
}
ms_recv(int n, pid *senders, msg_t *msgs) {
pid_t sender_pid[n];
for (int i = 0; i < n; i++) {
msgs[i], sender_pid[i] = arecv(senders[i]);
}
for (int i = 0; i < n; i++) {
asend(senders_pid[i], ACK);
}
}
Esempi di deadlock:
- Due processi A, B si aspettano messaggi l'un l'altro. (entrambi chiamano recv sull'altro), questo è un deadlock comune anche al message passing sincrono.
- L'esempio di sopra si può estendere in un caso più generale quando sia A un ms_recv ed esiste un processo all'interno di senders che stia aspettando un messaggio da A.
- Altro deadlock che può capitare è quando uno stesso processo è presente più volte all'interno di senders, in questo caso ricevo solo una volta, è impossibile che riesca a ricevere una altra volta.
- Per esempio basterebbe avere come input un (ANY, 1), e ricevere il primo messaggio da 1, e, nonostante soddisfi le specifiche, si avrebbe un deadlock.
- Soluzione proposta Flecart Friend cedo, la proprietà intellettuale di questa soluzione a flecart.
Doveri avere risolto gli ultimi due casi di deadlock descritti sopra con questo codice
void ms_send(pid dest, msg_t msg){
asend(<getpid(),msg>,dest);
while(true){
<pid,msg>=arecv(dest);
if(msg==ACK){
break;
}
}
}
ms_recv(int n, pid *senders, msg_t *msgs){
msg_t cached[MAXPID];
queue<int> any;
for(int i=0;i<MAXPID;i++){
cached[i]=NULL;
}
for(int i=0;i<n;i++){
if(senders[i]==ANY)any.push(i);
else left++;
}
while(left>0 && any.size()>0){
<pid,msg>=arecv(ANY);
//diamo priorità a quelli non any
for(int i=0;i<n;i++){
if(senders[i]==ANY)continue;
if(msgs[i]==NULL and senders[i]==pid){
msgs[i]=msg;
asend(<getpid(),ACK>,sender);
left--;
msg=NULL;
break;//break for
}
}
if(msg!=NULL){
//aggiungiamo agli any
if(any.size()>0){
current_index=q.pop();
msgs[current_index]=msg;
asend(<getpid(),ACK>,sender);
}else{
//se no mettiamo in cached
cached[pid]=msg;
}
}
}
for(int i=0;i<MAXPID;i++){
if(cached[i]!=NULL){
asend(<i,cached[i]>,getpid());
}
}
}