Sistemi Operativi - User contributions [en]

Prove scritte 2017

2023-01-18T10:52:57Z

Gio: /* Soluzione proposta 2 (da controllare) */

== Esame 11/09/2017 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2017.09.11.tot.pdf 2017.09.11.tot.pdf]
=== Esercizio c.1 ===
<syntaxhighlight lang="c">
monitor crossing

ok2dir[4]; //NESW
bool busy = false;

pe entra(int dir)
if (busy)
ok2dir[dir].wait();
busy = true;

pe esci(int dir)
busy = false;
ok2dir[(dir + 1) % 4].signal();
if (!busy)
ok2dir[(dir + 2) % 4].signal();
if (!busy)
ok2dir[(dir + 3) % 4].signal();
if (!busy)
ok2dir[(dir + 4) % 4].signal(); //dir

//alternativa più compatta
pe esci(int dir)
busy = false;
for (i = 0; i < 4; i++)
if (!busy)
ok2dir[(dir + i + 1) % 4].signal();

</syntaxhighlight>
 

==== Soluzione proposta 2 ====
Soluzione proposta da Libera e corretta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]

<syntaxhighlight lang=C>

const int N_DIRECTION = 4;

// assumo N = 0, E = 1, S = 2, W = 3, oppure shiftati ciclicamente, è equivalente

monitor crossing {
bool free; //l'incrocio è libero?
int num_waiting[N_DIRECTION];
condition okToCross[N_DIRECTION]; //free == True

crossing() {
free = True; //parto con l'incrocio libero
for (int i = 0; i < N_DIRECTION; i++) {
num_waiting[i] = 0;
}
}

procedure entry enter(int direction) {
if(!free) { //se l'incrocio non è libero
num_waiting[direction]++;
okToCross[direction].wait(); //aspetto nella mia direzione
num_waiting[direction]--;
}
//ora sono sicurə che sia libero
free = False; //quindi lo dichiaro occupato
}

procedure entry exit(int direction) {
//non devo aspettare niente per liberare l'incrocio
free = True; //lo dichiaro libero

for (int i = 0; i < N_DIRECTION; i++) {
int curr_dir = (direction + i + 1) % N_DIRECTION;
if (num_waiting[curr_dir] > 0) {
okToCross[curr_dir].signal();
break; // l'onere di risvegliare gli altri è stato passato al nuovo processo risvegliato, quindi esco.
}
}
}
}

</syntaxhighlight>

=== Esercizio c.2 (da controllare) ===
<syntaxhighlight lang="c">
// server[] = array contenente il PID di tutti i server

#define BROADCAST server[0]

server[0]
{
while(true)
{
<msg, sender> = arecv(*); // ricevo il messaggio
if (sender == BROADCAST)
print(msg); // se il messaggio l'ho ricevuto da me stesso allora lo stampo
else
asend(*, <msg, getpid()>); // se il messaggio l'ho ricevuto da un client o da un altro server lo inoltro a tutti i server (compreso me stesso)
}
}

server[x] // x = 1...N-1
{
while(true)
{
<msg, sender> = arecv(*); // ricevo il messaggio
if (sender == BROADCAST)
print(msg); // se il messaggio l'ho ricevuto dal server[0] allora lo stampo
else
asend(BROADCAST, <msg, getpid()>) // se il messaggio l'ho ricevuto da un client lo inoltro al server[0]
}
}
</syntaxhighlight>
 

==== Soluzione proposta 2 ====

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]
Soluzione corretta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Gio Flecart friend]

<syntaxhighlight lang=C>
process server_0 {

while (true) {
<msg, sender> = arecv(ANY);
for (int i = 1 ; i < N; i++) {
asend(<msg, 0>, server[i]);
while(true){
msg = arecv(server[i]); // così so che tutti abbiano stampato.
if(msg==ACK)
break
asend(msg,server[0]);
}
}
print(msg);
}
}

process server_[i=1 to N - 1] {
while (true) {
<msg, sender> = arecv(ANY);
if (sender == 0) {
print(msg);
asend(ACK, server[0]);
} else {
asend(<msg, i>, server[0]);
}
}
}

</syntaxhighlight>

== Esame 17/07/2017 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2017.07.17.tot.pdf 2017.07.17.tot.pdf]
=== Esercizio c.1 ===
<syntaxhighlight lang="c">
monitor conf {
condition finished;
condition ready2present[max];
bool arrived[max] = false;
bool giachiamato[max] = false;

entry chiama(chiamato){
if(arrived[chiamato] == true)
ready2present[chiamato].signal;
finished.wait;
return true;
else
giachiamato[chiamato]= true
return false;
}

entry arrivato(nome){
if(giachiamato[nome] == true)
return false;

arrived[nome] = true;
ok2present[nome].wait;
return true;
}

entry finepresentazione(nome){
finished.signal;
}
}

</syntaxhighlight>

=== Esercizio c.2 (da controllare) ===
<syntaxhighlight lang="c">
si, è possibile:

Implementare asend e arecv date bsend e brecv

asend(pid_t, msg_type msg){
bsend (<pid_t dst, msg>);
}

arecv(*){
pid_t act = getpid(); \\ act = proprio pid
do{
<dst, msg> = brecv(*);
}while (dst =! act)
return msg;
}

</syntaxhighlight>
 

== Esame 19/06/2017 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2017.06.19.tot.pdf 2017.06.19.tot.pdf]
=== Esercizio c.1 (da controllare)===
<syntaxhighlight lang="c">
#define NATLETI n

condition ok2lancia[NATLETI];
condition ok2giudice;

int counter[NATLETI];
int ultimo_tiro;
float registro[NATLETI][3];

Procedure entry: boolean pronto(int i)
{
if(!(i == 0 && counter[i] == 0)) // se è il primo lancio non devo metterlo in wait
ok2lancia[i].wait()
if(counter[i] < 3)
return true;
else
return false;
}

Procedure entry: void lanciato (int i)
{
counter[i]++;
ultimo_tiro = i;
ok2giudice.signal();
}

Procedure entry: int lanciofatto()
{
ok2giudice.wait()
if(ultimo_tiro == NATLETI-1 && counter[0] == 3)
return -1; // devo invalidare la condizione per uscire dal while, quindi se nessuno deve più lanciare ritorno -1
else
return ultimo_tiro;
}

Procedure entry: void registraechiama(int i, float m)
{
registro[i][counter[i]-1] = m; // il secondo indice indica l'iesimo lancio -1 (perchè iniziamo a contare da zero)
if(i == NATLETI-1) // se ha appena tirato l'ultimo atleta non posso dare il via a NATLETI (perchè non esiste), quindi faccio ricominciare il giro
ok2lancia[0].signal();
else
ok2lancia[i+1].signal();
}

Procedure entry: int classifica()
{
int best[NATLETI];
for(int i = 0; i < NATLETI; i++)
{
for(int j = 0; j < 3; j++)
{
if(registro[i][j] > best[i])
best[i] = registro[i][j];
}
}
best.sort_in_descending_order(); // supponiamo nel nostro pseudolinguaggio esista una funzione di ordinamento qualunque
return best;
}
</syntaxhighlight>
 

== Esame 29/05/2017 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2017.05.29.tot.pdf 2017.05.29.tot.pdf]
=== Esercizio c.1 ===
<syntaxhighlight lang="c">
condition okpartita
condition ok2chiama
condition ok2punteggio
condition ok2run[2][MAX]
int numpronti
int punteggio[2]
boolean partita=false
boolean partitafinita=false
chiamati = []
contabandiera[2]
int winner

entry nuovapartita():
{
punteggio[A] = punteggio[B] = 0;
numpronti = 0;
partita=true;
okpartita.signal()
chiamati = [];
}
entry chiama(l):
{
if (numpronti<2*MAX)
{
ok2chiama.wait();
}
chiamati = l;
contabandiera[A] = contabandiera[B] = 0
winner = -1;
for (s in n)
{
ok2run[A][s].signal();
ok2run[B][s].signal()
}
ok2punteggio.wait();
punteggio[winner++]
if (max(punteggio) == 10)
{
partitafinita = true;
for (s in A,B)
{
for (n in range(MAX))
{
ok2run[s][n].signal();
}
}
}
return punteggio;
}
entry pronto(s, n):
{
if (partitafinita) return 1;
if (!partita)
{
okpartita.wait();
}
numpronti++;
if (numpronti>=2*MAX)
{
ok2chiama.signal();
}
if (!(n in chiamati))
{
ok2run[s][n].wait();
}
numpronti--;
return 0 if partita else 1;
}
allabandiera(s, n):
{
contabandiera[s]++;
if (winner == -1 && contabandiera[s] == len(chiamati))
{
winner = s;
}
if (contabandiera[A] == len(chiamati) && contabandiera[B] == len(chiamati))
{
ok2punteggio.signal();
}
}

casi da discutere:
se arrivano studenti a pronto prima che il prof dichiara nuovapartita succedono guai.
</syntaxhighlight>

Prove scritte 2017

2023-01-18T10:52:04Z

Gio: /* Soluzione proposta 2 (da controllare) */

== Esame 11/09/2017 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2017.09.11.tot.pdf 2017.09.11.tot.pdf]
=== Esercizio c.1 ===
<syntaxhighlight lang="c">
monitor crossing

ok2dir[4]; //NESW
bool busy = false;

pe entra(int dir)
if (busy)
ok2dir[dir].wait();
busy = true;

pe esci(int dir)
busy = false;
ok2dir[(dir + 1) % 4].signal();
if (!busy)
ok2dir[(dir + 2) % 4].signal();
if (!busy)
ok2dir[(dir + 3) % 4].signal();
if (!busy)
ok2dir[(dir + 4) % 4].signal(); //dir

//alternativa più compatta
pe esci(int dir)
busy = false;
for (i = 0; i < 4; i++)
if (!busy)
ok2dir[(dir + i + 1) % 4].signal();

</syntaxhighlight>
 

==== Soluzione proposta 2 ====
Soluzione proposta da Libera e corretta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]

<syntaxhighlight lang=C>

const int N_DIRECTION = 4;

// assumo N = 0, E = 1, S = 2, W = 3, oppure shiftati ciclicamente, è equivalente

monitor crossing {
bool free; //l'incrocio è libero?
int num_waiting[N_DIRECTION];
condition okToCross[N_DIRECTION]; //free == True

crossing() {
free = True; //parto con l'incrocio libero
for (int i = 0; i < N_DIRECTION; i++) {
num_waiting[i] = 0;
}
}

procedure entry enter(int direction) {
if(!free) { //se l'incrocio non è libero
num_waiting[direction]++;
okToCross[direction].wait(); //aspetto nella mia direzione
num_waiting[direction]--;
}
//ora sono sicurə che sia libero
free = False; //quindi lo dichiaro occupato
}

procedure entry exit(int direction) {
//non devo aspettare niente per liberare l'incrocio
free = True; //lo dichiaro libero

for (int i = 0; i < N_DIRECTION; i++) {
int curr_dir = (direction + i + 1) % N_DIRECTION;
if (num_waiting[curr_dir] > 0) {
okToCross[curr_dir].signal();
break; // l'onere di risvegliare gli altri è stato passato al nuovo processo risvegliato, quindi esco.
}
}
}
}

</syntaxhighlight>

=== Esercizio c.2 (da controllare) ===
<syntaxhighlight lang="c">
// server[] = array contenente il PID di tutti i server

#define BROADCAST server[0]

server[0]
{
while(true)
{
<msg, sender> = arecv(*); // ricevo il messaggio
if (sender == BROADCAST)
print(msg); // se il messaggio l'ho ricevuto da me stesso allora lo stampo
else
asend(*, <msg, getpid()>); // se il messaggio l'ho ricevuto da un client o da un altro server lo inoltro a tutti i server (compreso me stesso)
}
}

server[x] // x = 1...N-1
{
while(true)
{
<msg, sender> = arecv(*); // ricevo il messaggio
if (sender == BROADCAST)
print(msg); // se il messaggio l'ho ricevuto dal server[0] allora lo stampo
else
asend(BROADCAST, <msg, getpid()>) // se il messaggio l'ho ricevuto da un client lo inoltro al server[0]
}
}
</syntaxhighlight>
 

==== Soluzione proposta 2 (da controllare) ====
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]
<syntaxhighlight lang=C>
process server_0 {

while (true) {
<msg, sender> = arecv(ANY);
for (int i = 1 ; i < N; i++) {
asend(<msg, 0>, server[i]);
while(true){
msg = arecv(server[i]); // così so che tutti abbiano stampato.
if(msg==ACK)
break
asend(msg,server[0]);
}
}
print(msg);
}
}

process server_[i=1 to N - 1] {
while (true) {
<msg, sender> = arecv(ANY);
if (sender == 0) {
print(msg);
asend(ACK, server[0]);
} else {
asend(<msg, i>, server[0]);
}
}
}

</syntaxhighlight>

== Esame 17/07/2017 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2017.07.17.tot.pdf 2017.07.17.tot.pdf]
=== Esercizio c.1 ===
<syntaxhighlight lang="c">
monitor conf {
condition finished;
condition ready2present[max];
bool arrived[max] = false;
bool giachiamato[max] = false;

entry chiama(chiamato){
if(arrived[chiamato] == true)
ready2present[chiamato].signal;
finished.wait;
return true;
else
giachiamato[chiamato]= true
return false;
}

entry arrivato(nome){
if(giachiamato[nome] == true)
return false;

arrived[nome] = true;
ok2present[nome].wait;
return true;
}

entry finepresentazione(nome){
finished.signal;
}
}

</syntaxhighlight>

=== Esercizio c.2 (da controllare) ===
<syntaxhighlight lang="c">
si, è possibile:

Implementare asend e arecv date bsend e brecv

asend(pid_t, msg_type msg){
bsend (<pid_t dst, msg>);
}

arecv(*){
pid_t act = getpid(); \\ act = proprio pid
do{
<dst, msg> = brecv(*);
}while (dst =! act)
return msg;
}

</syntaxhighlight>
 

== Esame 19/06/2017 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2017.06.19.tot.pdf 2017.06.19.tot.pdf]
=== Esercizio c.1 (da controllare)===
<syntaxhighlight lang="c">
#define NATLETI n

condition ok2lancia[NATLETI];
condition ok2giudice;

int counter[NATLETI];
int ultimo_tiro;
float registro[NATLETI][3];

Procedure entry: boolean pronto(int i)
{
if(!(i == 0 && counter[i] == 0)) // se è il primo lancio non devo metterlo in wait
ok2lancia[i].wait()
if(counter[i] < 3)
return true;
else
return false;
}

Procedure entry: void lanciato (int i)
{
counter[i]++;
ultimo_tiro = i;
ok2giudice.signal();
}

Procedure entry: int lanciofatto()
{
ok2giudice.wait()
if(ultimo_tiro == NATLETI-1 && counter[0] == 3)
return -1; // devo invalidare la condizione per uscire dal while, quindi se nessuno deve più lanciare ritorno -1
else
return ultimo_tiro;
}

Procedure entry: void registraechiama(int i, float m)
{
registro[i][counter[i]-1] = m; // il secondo indice indica l'iesimo lancio -1 (perchè iniziamo a contare da zero)
if(i == NATLETI-1) // se ha appena tirato l'ultimo atleta non posso dare il via a NATLETI (perchè non esiste), quindi faccio ricominciare il giro
ok2lancia[0].signal();
else
ok2lancia[i+1].signal();
}

Procedure entry: int classifica()
{
int best[NATLETI];
for(int i = 0; i < NATLETI; i++)
{
for(int j = 0; j < 3; j++)
{
if(registro[i][j] > best[i])
best[i] = registro[i][j];
}
}
best.sort_in_descending_order(); // supponiamo nel nostro pseudolinguaggio esista una funzione di ordinamento qualunque
return best;
}
</syntaxhighlight>
 

== Esame 29/05/2017 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2017.05.29.tot.pdf 2017.05.29.tot.pdf]
=== Esercizio c.1 ===
<syntaxhighlight lang="c">
condition okpartita
condition ok2chiama
condition ok2punteggio
condition ok2run[2][MAX]
int numpronti
int punteggio[2]
boolean partita=false
boolean partitafinita=false
chiamati = []
contabandiera[2]
int winner

entry nuovapartita():
{
punteggio[A] = punteggio[B] = 0;
numpronti = 0;
partita=true;
okpartita.signal()
chiamati = [];
}
entry chiama(l):
{
if (numpronti<2*MAX)
{
ok2chiama.wait();
}
chiamati = l;
contabandiera[A] = contabandiera[B] = 0
winner = -1;
for (s in n)
{
ok2run[A][s].signal();
ok2run[B][s].signal()
}
ok2punteggio.wait();
punteggio[winner++]
if (max(punteggio) == 10)
{
partitafinita = true;
for (s in A,B)
{
for (n in range(MAX))
{
ok2run[s][n].signal();
}
}
}
return punteggio;
}
entry pronto(s, n):
{
if (partitafinita) return 1;
if (!partita)
{
okpartita.wait();
}
numpronti++;
if (numpronti>=2*MAX)
{
ok2chiama.signal();
}
if (!(n in chiamati))
{
ok2run[s][n].wait();
}
numpronti--;
return 0 if partita else 1;
}
allabandiera(s, n):
{
contabandiera[s]++;
if (winner == -1 && contabandiera[s] == len(chiamati))
{
winner = s;
}
if (contabandiera[A] == len(chiamati) && contabandiera[B] == len(chiamati))
{
ok2punteggio.signal();
}
}

casi da discutere:
se arrivano studenti a pronto prima che il prof dichiara nuovapartita succedono guai.
</syntaxhighlight>

Prove scritte 2018

2023-01-18T10:39:24Z

Gio: /* Esercizio c.2 (ERRATO) */

= Esame 19/09/2018 =
[http://www.cs.unibo.it/~renzo/so/compiti/2018.09.19.tot.pdf Testo dell'esame].

=== Esercizio c.2 (da controllare) ===

* Controllato dall'utente ? in data ?
* ...

Nello pseudocodice seguente, il termine this fa riferimento al processo corrente, mentre ANY ad uno qualunque.

<syntaxhighlight lang="c">
stack<message> messages;

void lifo_send(string m, process dest) {
do {
asend(m, dest);
} while (areceive(dest).text != "ACK");
}

message lifo_receive(process source) {
if (source != ANY) {
message m = areceive(source);

asend("ACK", source);

return m;
} else {
message m;

asend("END", this);
m = areceive(ANY);

while (m.text != "END" || m.sender != this) {
messages.push(m);
asend("ACK", m.sender);

m = areceive(ANY);
}

/* Bisogna tenere conto dei casi in cui lifo_receive() viene invocata quando nessun
* messaggio è stato ancora spedito da altri processi. In tal caso si attende il
* il primo e lo si restituisce.
*/
if (messages.empty()) {
m = areceive(ANY);
asend("ACK", m.sender);

return m;
} else {
return messages.pop();
}
}
}
</syntaxhighlight>

= Esame 17/07/2018 =
[http://www.cs.unibo.it/~renzo/so/compiti/2018.07.17.tot.pdf 2018.07.17.tot.pdf]
== Esercizio c.1 ==
A Bruxelles c'è un locale chiamato Delirium Café. Alla vigilia del FOSDEM tutti gli anni gli sviluppatori europei di
software libero si ritrovano a bere birra (il locale è nel guinnes dei primati con più di duemila tipi di birra). Il prossimo appuntamento è
fissato per il 1 febbraio 2019 ore 20. Numerosi sono i tipi di birra alla spina. I baristi (tanti) prendono gli ordini (es. mezza pinta, 1 o 2
pinte) e riempiono i bicchieri. Quando un fusto e' vuoto avvertono i magazzinieri che prendono un nuovo fusto che contiene più di
cento pinte e lo sostituiscono, a questo punto il barista può completare il riempimento del bicchiere.
La vita di un barista del Delirium è:
while True:
(type, quantity) = get_order()
delirium.pour(type, quantity)
La vita di un Magazziniere è:
while True:
type = delirium.isempty()
capacity = change_keg(type)
delirium.loaded(type, capacity)

Attenzione: se il fusto (keg) è quasi vuoto il barista dovrà riempire parzialmente il bicchiere, occorrerà attivare il magazziniere che
cambierà il fusto e poi il barista riempirà il bicchiere fino alla quantità richiesta dal cliente. Mentre un barista sta attendendo il
cambiamento di un fusto altri baristi potrebbero ricevere ordini per lo stesso tipo di birra: gestire opportunamente questo caso.
Scrivere il monitor Delirium.

=== Proposta di soluzione 1 ===
* ERRORE: Secondo me c'è un leggero errore nella parte di load, nel caso in cui la nuova pinta non riesca a soddisfare completamente la richiesta ossia quando vale availableBeer[t] <= requests[t].head(), allora non lo risveglio nemmeno, invece dovrei risvegliare il pour, fargli versare quanto può, e richiedere una altra pinta, perché questo era un requisito del problema. [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 12:00, 15 January 2023 (CET)

<syntaxhighlight lang="c">
/* Monitor Delirum: */

// Condition: Ok2Load;
// Condition: Ok2Pour[]; // Un elemento per Type
int availableBeer[]; // Un elemento per Type
Queue requests[]; // Un elemento per Type
Queue pendingRequests;

Procedure entry: void Pour(Type t, Quantity c)
{
if (c > availableBeer[t]) // Richiesta maggiore della birra disponibile
{
c -= availableBeer[t];
availableBeer[t] = 0;
requests[t].Enqueue(c);
if (requests[t].Length == 1) // Risveglio un magazziniere solo se è la prima richiesta di questo tipo di birra
{
pendingRequests.Enqueue(t);
Ok2Load().Signal();
}
Ok2Pour[t].Wait();
requests[t].Dequeue(); // Quando ho ottenuto la birra che voglio, elimino la mia richiesta
}
availableBeer[t] -= c;
}

Procedure entry: Type isEmpty()
{
if (pendingRequests.Length == 0)
{
Ok2Load.Wait();
}
return pendingRequests.Dequeue();
}

Procedure entry: Loaded(Type t, Capacity c)
{
availableBeer[t] += c;
while (requests[t].Length > 0 && availableBeer[t] > requests[t].head())
{
Ok2Pour[t].Signal();
}

if (requests[t].Length > 0) // serve per evitare che a causa di un magazziniere lento si accodino cosi tante richieste che mentre si sta caricando si svuota subito il fusto
{
pendingRequests.Enqueue(t);
Ok2Load.Signal();
}
}
</syntaxhighlight>

=== Proposta di soluzione 2 ===
* Proposto da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 13:41, 15 January 2023 (CET)
<syntaxhighlight lang="C">
extern int MAX_TYPE;
class Delirium {
int keg[MAX_TYPE]; // qnty fusto attuale
int orders[MAX_TYPE]; // qnty richiesta
bool worked[MAX_TYPE]; // 1 se magazziniere sta lavorando su questo.

condition type_wait[MAX_TYPE];
int num_wait[MAX_TYPE];

queue<int> empty_type;
condition is_empty;

entry pour(type, quantity) {
while (keg[type] < quantity) {
quantity -= keg[type];
keg[type] = 0;
if (!empty_type.find(type) && !worked[type]) {
empty_type.enqueue(type);
is_empty.signal();
}

num_wait[type]++;
type_wait[type].wait();
num_wait[type]--;
}
keg[type] -= quantity;
quantity = 0; // questo è inutile, ma concettualmente è corretto, l'ordine è completato.
}

entry loaded(type, capacity) {
keg[type] += capacity;
worked[type] = false;

for (int i = num_wait[type]; i > 0; i--) {
type_wait[type].signal();
}
}

// si suppone che un singolo tipo di fusto è lavorabile da un solo magazziniere alla volta.
// worked impedisce di avere nella coda un fusto su cuisi sta già lavorando.
entry isempty() {
if (empty_type.size() <= 0) {
is_emtpy.wait();
}
int type = emtpy_type.dequeue();
worked[type] = true;
return type;
}
}
</syntaxhighlight>

== Esercizio c.2 ==

=== Proposta di soluzione 1 ===
* Visto e corretto dall'utente [[User:Acsor|Acsor]] in data 23/08/2020
* Visto e corretto dall'utente ? in data ?
* Visto, ritenuto corretto [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 09:27, 15 January 2023 (CET)

<syntaxhighlight lang="c">
class LIFOBuffer {
stack<T> s;
semaphore mutex(1); // mutua esclusione
semaphore ok2consume(0);

void push (T value) {
mutex.P();
s.push(value);
// (1)
mutex.V()

ok2consume.V() // Curiosità: che succede se spostiamo quest'istruzione in (1)? Edit: funziona lo stesso, solo che aggiorni il valore del semaforo prima di uscire dalla mutex.
}

T pop () {
T value;

ok2consume.P();
mutex.P();
value = s.pop();
mutex.V();

return value;
}
}
</syntaxhighlight>

=== Proposta di soluzione 2 ===
Proposto da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 09:27, 15 January 2023 (CET)

<syntaxhighlight lang="C">
class lifobuf {
semaphore mutex(1);
stack<int> values; // empty initialized
stack<semaphore> waiting;

push(int value) {
mutex.P();
values.push(value);
if (waiting.size() > 0) {
semaphore s = waiting.pop();
s.V();
return;
}

mutex.V();
}

pop() {
int ret_val;
mutex.P();
if (values.size() <= 0) {
semaphore s = new semaphore(0);
waiting.push(s);
mutex.V();
s.P();
free(s);
}

ret_val = values.pop();
mutex.V();

return ret_val;
}
}
</syntaxhighlight>

== Esercizio g.1 ==
Possiamo notare subito che il sistema ha due processori ed un dispositivo di I/O.
'''A''' e '''B''' partono insieme al tempo 0. 
'''C''' parte tra il tempo 0 ed il tempo 2 (non possiamo sapere di preciso quando perchè entrambe le CPU sono occupate). 
'''D''' parte tra il tempo 0 ed il tempo 3. 
A questo punto possiamo supporre che tutti e 4 i processi partano in sequenza ('''A''', '''B''', '''C''', '''D''') nello stesso momento, e ognuno prende la prima CPU libera che trova. 
'''A''' lavora per 3ms, poi scade il time slice. 
Nel frattempo '''B''' lavora per 2ms, poi richiede I/O per 4ms. 
La CPU su cui lavora '''B''' quindi si libera, e si manda in esecuzione il processo '''C'''. 
Scaduto il time slice per '''A''', si da il controllo ad un nuovo processo. '''B''' è occupato con I/O, '''C''' sta già lavorando, quindi è il turno di '''D'''. 
'''C''' lavora per 3ms, poi richiede I/O per 3ms, che però è occupato da '''B''', quindi si mette in coda per utilizzarlo. 
La CPU su cui lavorava '''C''' si libera ed il controllo torna ad '''A''', che doveva lavorare ancora per 2ms prima di chiedere il controllo di I/O, quindi lavora e si mette in coda dietro a '''C'''. 
Tornando a '''D''', questo lavora per 3ms prima che scada il time slice. Anche '''B''' ha finito il lavoro e ha bisogno di una CPU. 
In questo momento sia '''D''' che '''B''' sono nella coda dei processi in stato ready, ma dal diagramma possiamo notare che il controllo torna a '''D'''. 
La CPU ha scelto a caso un processo tra i due, perchè arrivati a questo punto possiamo supporre che lo scheduler sia Round-Robin. 
'''B''' prende possesso della prima CPU che si libera, ovvero quella occupata da '''A''', poi lavora per 2ms e termina il suo lavoro. 
Nel momento in cui '''B''' termina il lavoro, scade anche il time slice per '''D''', e '''C''' termina di usare I/O. 
Abbiamo due processi ('''C''' e '''D''') in coda ready. Ma abbiamo anche due CPU libere, perchè '''A''' è in coda per I/O e ci entra appena '''C''' finisce di usarlo. 
Lo scheduler sceglie di mandare '''C''' sul primo processore e '''D''' sul secondo. 
'''A''' nel frattempo, lavora per 4ms con I/O. 
'''C''' lavora per 3ms, poi termina il suo lavoro. 
'''D''' lavora per 3ms, poi scade il time slice. Ci sono due processori liberi, quindi '''D''' riparte subito in esecuzione. 
'''D''' doveva lavorare ancora per 1ms prima di aver bisogno di I/O, quindi finisce e si mette in coda. 
Ma nello stesso momento '''A''' termina di usare I/O, si prende un processore libero e lavora per i suoi ultimi 2ms. 
'''D''' lavora per 1ms con I/O, poi prende il secondo processore libero e lavora per 1ms prima di terminare il suo lavoro. 

Il time slice è di 3ms, lo scheduler è di tipo Round-Robin. 
Il dispositivo di I/O è FIFO. L'ordine con cui partono i processi è quello alfabetico.

<syntaxhighlight lang="c">
A(){
compute_a1(); // 5ms
io_a(); // 4ms
compute_a2(); // 2ms
}

B(){
compute_b(); // 2ms
io_b(); // 4ms
compute_b(); // 2ms
}

C(){
compute_c(); // 3ms
io_c(); // 3ms
compute_c(); // 3ms
}

D(){
compute_d1(); // 10ms
io_d(); // 1ms
compute_d2(); // 1ms
}
</syntaxhighlight>
Lo scheduler potrebbe anche essere a priorità: 
Priorità '''B''' < priorità '''D''' < priorità '''C''' 
Priorità '''A''' = ? 
'''B''' fatto partire prima di '''C''' e '''D'''.
 

== Esercizio g.2 (da controllare) ==
# In sistemi dove dispositivi di archiviazione o supporti hardware per la memoria virtuale (e dunque per la paginazione, spesso utilizzata per realizzare il supporto di memoria virtuale) non sono presenti (es. sistemi embedded). ''(In sistemi real-time la memoria virtuale è praticabile? Annotare.)''
# Perchè ad esempio sulle chiavette USB quasi mai abbiamo il problema di dover utilizzare file di dimensione maggiore ai 4GB. Non utilizza il journaling, che richiede molteplici scritture per ogni azione ed in dispositivi portatili può ridurre di molto la durata. Non supporta i permessi sui file, e questo è un vantaggio per le chiavette USB, pensate per trasferire dati tra PC diversi.
# Per fornire parallelismo e ridondanza. Non è necessario fare backup dei dati sul disco, nel senso di mantenere una copia identica di dati già memorizzati altrove, in quanto diversi sistemi di codici permettono il rilevamento e/o la correzione di errori.
# Se in un grafo di Holt multirisorsa esiste un ciclo tra più processi e risorse, ciò non significa che allo stesso tempo non siano coinvolti processi con archi esclusivamente entranti. Ogni processo appartenente a questa categoria non è in attesa di risorse, e può dunque procedere con i suoi calcoli; quando avrà terminato rilascerà le risorse precedentemente allocategli, eventualmente sbloccando uno dei processi coinvolti nel ciclo.

= Esame 21/06/2018 =
[http://www.cs.unibo.it/~renzo/so/compiti/2018.06.21.tot.pdf 2018.06.21.tot.pdf]
=== Esercizio c.1 (sbagliato) ===
<syntaxhighlight lang="c">
/* Monitor tmon */

define MAX n;
define TERRAFERMA 1;
define ISOLA 2;

semaphore ok2unload;
semaphore ok2load;
semaphore ok2ship;
semaphore mutex(1); // la rampa è zona critica --> mutua esclusione

stack ferry;
int current_port = 0;

Procedure entry: al_porto(int location)
{
current_port = location; // traghetto arriva a destinazione
ok2unload.signal(); // da il via per far sbarcare le macchine
ok2ship.wait(); // si ferma
current_port = 0; // traghetto sta viaggiando tra i due porti
}

Procedure entry: imbarca(int location)
{
mutex.wait(); // prende possesso della rampa
ferry.push(1); // sale sul traghetto
mutex.signal(); // libera la rampa
}

Procedure entry: imbarcato(int location)
{
if(ferry.lenght() == MAX) // se il traghetto è pieno da il via per farlo salpare
{
ok2load.wait();
ok2ship.signal();
}
}

Procedure entry: sbarca(int location)
{
mutex.wait(); // prende possesso della rampa
ferry.pop(); // scende dal traghetto
mutex.signal(); // libera la rampa
}

Procedure entry: sbarcato(int location)
{
if(ferry.lenght() == 0) // se il traghetto è vuoto da il via per far imbarcare le macchine
{
ok2unload.wait();
ok2load.signal();
}
}

</syntaxhighlight>
 

=== Esercizio c.1 ===
<syntaxhighlight lang="c">
/* Monitor tmon */

#define MAX n
#define NONE 0
#define TERRAFERMA 1
#define ISOLA 2

condition ok2unload;
condition ok2load[2];
condition ok2ship;
condition empty;

int onboard = 0;
int onramp = 0;
int current_port = NONE;

Procedure entry: al_porto(int location)
{
//arrivando
current_port = location;
ok2unload.signal();
if (onboard > 0)
empty.wait()
ok2load[location].signal()
if (onboard < MAX)
ok2ship.wait()
//partendo
current_port = NONE;
}

Procedure entry: imbarca(int location)
{
if (current_port != location || onramp > 0 || onboard >= MAX)
ok2load[location].wait()
onramp = 1;
}

Procedure entry: imbarcato(int location)
{
onramp = 0; onboard++;
if (onboard < MAX)
ok2load[location].signal();
else
ok2ship.signal();
}

Procedure entry: sbarca(int location)
{
if (current_port != location || onramp > 0)
ok2unload.wait()
onramp = 1;
}

Procedure entry: sbarcato(int location)
{
onramp = 0; onboard--;
if (onboard == 0)
empty.signal();
else
ok2unload.signal();
}
</syntaxhighlight>
 

=== Esercizio c.2 (sbagliato) ===
<syntaxhighlight lang="c">

#define N n // limite operazioni
semaphore mutex(1); // sezione critica

class lim_semaphore()
{
int value;
semaphore plus;
semaphore minus;

P()
{
mutex.P();
if(value < N)
{
if (value >= 0)
{
plus.P();
}
else
{
minus.V();
}
value--;
}
mutex.V();
}

V()
{
mutex.P();
if(value > -N)
{
if (value <= 0)
{
minus.P();
}
else
{
plus.V();
}
value++;
}
mutex.V();
}
}
</syntaxhighlight>
 

=== Esercizio c.2 ===
==== Soluzione "furba e facile" ====
* Visto dall'utente [[User:Acsor|Acsor]] ([[User talk:Acsor|talk]]) in data 18:53, 9 September 2020 (CEST). Ritengo sia: corretto (perché l'ho fatto pressappoco uguale). (Ritengo anche che possedere strumenti di analisi formale per verificare la correttezza di codice simile sarebbe di grande ausilio.)

<syntaxhighlight lang="java">
class bounded_semaphore {
semaphore plus;
semaphore minus;
int value; // serve per significato

bounded_semaphore (int initval, unsigned maxval) {
value = initval;
plus = new semaphore(maxval + initval);
minus = new semaphore(maxval - initval);
}

void P() {
plus.P();
value--;
minus.V();
}

void V() {
minus.P();
value++;
plus.V();
}
}
</syntaxhighlight>

==== Soluzione "schiacciasassi" ====

<syntaxhighlight lang="java">
class bounded_semaphore {
semaphore mutex;
queue<semaphore> okmin, okmax;
int value;
unsigned maxval;

bounded_semaphore (int initval, unsigned maxval) {
value = initval;
this.maxval = maxval;
}

void P() {
mutex.P();

if (value <= -maxval) {
s=semaphore(0);
okmin.enqueue(s);
mutex.V();
s.P();
} else if (okmax.length() > 0) {
s = okmax.dequeue()
s.V();
mutex.V();
} else {
value--;
mutex.V();
}
}

void V() {
mutex.P();

if (value >= -maxval) {
s=semaphore(0);
okmax.enqueue(s);
mutex.V();
s.P();
} else if (okmin.length() > 0) {
s = okmin.dequeue()
s.V();
mutex.V();
} else {
value++;
mutex.V();
}
}
}
</syntaxhighlight>

=== Esercizio g.1 ===
* Controllato dall'utente [[User:Acsor|Acsor]] ([[User talk:Acsor|talk]]), 23:17, 9 September 2020 (CEST). Ritengo sia: corretto

<nowiki>
IC = 10,10,10 // Capitale iniziale
COH = 4,4,4 // Saldo in cassa

MAX ATT RES AVAIL
P1 | 6,6,6 | 1,1,1 | 5,5,5 | 4,4,4
P2 | 6,6,6 | 1,1,1 | 5,5,5 | 5,5,5
P3 | 9,9,9 | 4,4,4 | 5,5,5 | 6,6,6
</nowiki>

Minimizzato

<nowiki>
IC = 4,4,4
COH = 1,1,1

MAX ATT RES
P1 | 3,3,3 | 1,1,1 | 2,2,2
P2 | 3,3,3 | 1,1,1 | 2,2,2
P3 | 3,3,3 | 1,1,1 | 2,2,2
</nowiki>

=== Esercizio g.2 (da controllare) ===

* Visto e rimaneggiato in data 19:40, 10 September 2020 (CEST) dall'utente [[User:Acsor|Acsor]] ([[User talk:Acsor|talk]])

<hr>

# Il calcolo del working set serve a determinare il numero di processi che possono essere mantenuti attivi sulla base del limite della memoria principale, più precisamente del suo numero di frame. Può essere svolto ad ogni page fault, ossia quando un processo tra quelli attivi richiede una pagina non presente in memoria, o prima di avviare un nuovo processo.
# La lunghezza massima di un file che può essere memorizzato su un file system di tipo FAT viene calcolata moltiplicando il massimo numero di cluster (dimensione dell'unità di allocazione) identificabili per la loro dimensione. Il massimo numero di cluster identificabili dipende da quanti bit sono allocati per numerarli, e per questa distinzione esistono varie versioni di FAT (FAT12, FAT16, FAT32).
## FAT32 memorizza la dimensione dei file in un intero unsigned da 32bit, e non può quindi gestire un file di dimensione superiore ai 2^32 bit = ~4GB.
## FAT16, allocando 16bit per identificare i cluster, può contarne al massimo 2^16 (65536). Prendendo quindi, ad esempio, un file system FAT16 con cluster da 32KB, possiamo avere file grandi al massimo 32KB*65536 = ~2GB.
## FAT12 di conseguenza può numerare al massimo 2^12 (4096) cluster, ma dato che il numero dei settori del disco viene memorizzato in un intero signed a 16bit, la massima dimensione del disco è 2^15 = 32MB. Ovviamente, non si può memorizzare un file di grandezza superiore alla dimensione dell'unità di memorizzazione stessa, e quindi anche i file in FAT12 possono avere dimensione massima di 32MB.
# Entrambi condividono l'intento di infettare host con codice malevolo, ma differiscono fondamentalmente nella modalità: i virus infettano programmi già esistenti mediante un ''virus dropper'', mentre i worm diffondono copie di se stessi, solitamente attraverso la rete.
# In vari casi sulla base della natura del sistema. Innanzitutto, in sistemi batch ciò avviene se non sono stati inseriti più processi per un certo lasso di tempo. In sistemi general-purpose (es. per PC o dispositivi mobili) tale condizione è verificabile se tutti i processi sono in attesa su una coda che non è quella dello scheduler (ad. es. di un semaforo o di una periferica di I/O); casi concreti sono pertanto il deadlock (di tutti i processi del sistema) o attesa generale di I/O. Infine sempre in sistemi general-purpose tale condizione può manifestarsi, stavolta in condizioni patologiche, se ogni processo è assegnato ad una propria CPU/core, lasciando pertanto la coda d'attesa vuota.

= Esame 28/05/2018 =
[http://www.cs.unibo.it/~renzo/so/compiti/2018.05.28.tot.pdf 2018.05.28.tot.pdf]
=== Esercizio c.1 ===
<syntaxhighlight lang="c">
Stack<int> entriesStack;

int vid[MAX];
condition ok2esci[MAX]
int in = 0;
int out = -1;

Procedure-entry: entra(int id) {
if (in >= MAX)
ok2entra.wait()
vid[in++] = id;
if (in < MAX)
ok2entra.signal()
else
out = MAX - 1;
}

Procedure-entry: esci(int id) {
int i;
for (i = 0; i < in; i++)
if (vid[i] == id)
break; //cerco l'indice di id nel vettore vid

if (i != out)
ok2esci[i].wait();

if (out > 0) {
out--;
ok2esci[out].signal();
} else {
out--;
in = 0;
ok2entra.signal();
}
}
</syntaxhighlight>
 

=== Esercizio c.1 (da controllare) ===
<syntaxhighlight lang="c">
Monitor riempisvuota {
Int MAXPROCESSI;
Stack s;
condition ok2enter;
condition ok2exit;

p.e void entra(getPid()){
if( s.size() >= MAXPROCESSI)
ok2enter.wait();
s.insert(getPid());
if(s.size() > MAXPROCESSI)
ok2exit.signal()
}

p.e void esci(getPid()){
if(s.size() > MAXPROCESSI && s.top == getPid()) {
s.pop();
ok2entra.signal()
}
else
ok2exit.wait();
}
</syntaxhighlight>
 
=== Esercizio c.2 (ERRATO) ===

* Soluzione proposta è errata, non puoi riceve in modo greedy e printare subito il carattere [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 11:33, 18 January 2023 (CET)

<syntaxhighlight lang="c">
proc[x]: x='a',...,'z'
while True:
//c sarà il carattere stampato dal processo precedente
(c, string) = arecv(*)
if(string == wait){
//mi metto in attesa di ricevere l'ACK da proc[x]
m=arecv(x);
}
if (c == NONE){
//significa che sei il primo a ricevere quella stringa
print(x);
if (len(string) > 1){
//mando la wait a tutti, il primo che riceve qualcosa da stampare manda una wait a tutti
asend(wait,*);
int l = len(string);
int i = 1;
while(l != 0){
asend(proc[string[i]], (x, string[i...]));
//si mette in attesa di ricevere l'ACK dal processo dell'ultima lettera della parola
m=areceive(proc[string[i]]);
//rimando la wait al processo per ribloccarlo
asend(wait, proc[string[i]])
l--;
i++;
}
//dopo aver finito la stampa della stringa sblocco tutti i processi
asend(ACK, *);
}
}else{
print(x);
asend(ACK, x);
//ricomincia il ciclo while, si rimette in attesa e il 'gestore gli rimanda la wait'
}
</syntaxhighlight>
 

=== Esercizio c.2 ===
[[User:Flecart|Flecart friend]] ([[User talk:Flecart|talk]]) cedo la proprità intellettuale di questa soluzione a flecart

<syntaxhighlight lang="c">
process [x]: x='a'..'z'
if(x=='a'){
asend(<NULL,NULL>,'b');
asend(<NULL,NULL>,'b');
}
While True:
<c,string>=arecv(x-1+26%26);
if(string==NULL):
<c,string>=arecv(*);
if(string!=NULL):
<c,string>=arecv(x-1+26%26);

if(string!=NULL):
if(string[0]==x):
print(string[0]);
if(string.len()>1):
aasend(<NULL,string[1:]>,(x+1)%26);
else:
aasend(<NULL,NULL>,(x+1)%26);
aasend(<NULL,NULL>,(x+1)%26);
else:
aasend(<NULL,string>,(x+1)%26);
else:
aasend(<NULL,NULL>,(x+1)%26);
aasend(<NULL,NULL>,(x+1)%26);

</syntaxhighlight>

=== Proposta c2 ===
* Proposto [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 11:31, 18 January 2023 (CET)

<syntaxhighlight lang="C">
proc[a]:
bool occupied = false;
queue<string> s;

while True {
(c, string) = arecv(*);

if (c == NONE) {
if (occupied) {
s.enqueue(string);
} else {
if (string.len() < 1)
continue;

occupied = true;
asend(string[0], (MIDDLE, string));
}
} else if (c == END) {
if (s.size() > 0) {
string ss = s.dequeue();
asend(string[0], (MIDLLE, string));
} else {
occupied = false;
}
} else {
print(x);
if (len(string) > 1)
asend(proc[string[0]], (MIDDLE, string[1:]));
else:
asend(proc[a], (END, ""));
}
}

proc[x]: x = 'b', ... 'z';
while True {
(c, string) = arecv(*);
if (c == NONE) {
asend(proc['a'], (NONE, string));
} else { // potrà essere solo MIDDLE
print(x);
if (len(string) > 1)
asend(proc[string[0]], (MIDDLE, string[1:]));
else:
asend(proc[a], (END, ""));
}
}
</syntaxhighlight>

= Esame 12/02/2018 =
[http://www.cs.unibo.it/~renzo/so/compiti/2018.02.12.tot.pdf 2018.02.12.tot.pdf]

=== Esercizio c.1 (da controllare) ===
<syntaxhighlight lang="c">

monitor bridge:

int ncar
bool boat_on_0
bool boat_on_1 // per semplicità, quando nel codice si trova boat_on_(direction) oppure isBoat(direction)(),
// si valuta il valore booleano di direction e lo si applica sotto forma di stringa al simbolo
// ad esso adiacente
bool is_raised
queue waiting_mean // i valori possibili sono: boat0, boat1 oppure car
condition ok2go

entry car_enter(direction):
if is_raised || ncar == MAXCAR:
waiting_mean.enqueue(car)
ok2go.wait()
is_raised = false
++ncar

entry car_exit(direction):
--ncar
if (waiting_mean.top().isBoat() && ncar == 0) || waiting_mean.top().isCar(): // isBoat ritorna true se l'oggetto su cui
waiting_mean.dequeue() // è invocata è boat0 oppure boat1
ok2go.signal()

entry boat_enter(direction):
if !is_raised || boat_on_(direction):
waiting_mean.enqueue(boat)
ok2go.wait()
if waiting_mean.top().isBoat(!direction)():
waiting_mean.dequeue()
ok2go.signal()
is_raised = true
boat_on_(direction) = true

entry boat_exit(direction):
boat_on_(direction) = false
if !boat_on_(!direction):
waiting_mean.dequeue()
ok2go.signal()

</syntaxhighlight>

 

=== Esercizio c.1 ===
<syntaxhighlight lang="c">
monitor bridge {
int carsOnBridge = 0;
int shipping[2] = {0, 0}; //navi da entrambe le direzioni
int status = NONE; //UP DOWN NONE
int last2pass = 0; //ultimo che ha passato il ponte
int waitingC = 0; //coda delle macchine che aspettano
int waitingS[2] = {0,0}; //navi che stanno aspettando

condition ok2ship[2]
condition ok2drive

entry car_enter(int direction){
if(carsOnBridge >= MAX || status == UP || waitingS[0] + waitingS[1] > 0 ){
waitingC++;ok2drive.wait;waitingC--;}
status = DOWN;
carsOnBridge++
if (carsOnBridge < MAX)
ok2drive.signal(); //vanno tutte le MAX car che stanno aspettando
}
entry car_exit(int direction){
carsOnBridge--
if (waitingS[0] + waitingS[1] == 0)
ok2drive.signal();
if(carsOnBridge == 0){
ok2ship[0].signal(); ok2ship[1].signal();
}
if(carsOnBridge + waitingS[0] + waitingS[1] == 0)
status = NONE
}

entry ship_enter(int direction){
if (bridge = DOWN || shipping[direction] != 0 || waitingC > 0)
{
waitingS[i]++; ok2ship[i].wait(); waitingS[i]--;
}
isBridgeUp = false;
shipping[i] = 1;

entry ship_exit(int direction){
shipping[i] = 0;
if (waitingC == 0)
ok2ship[i].signal()
else if(shipping[1-i] == 0)
ok2drive.signal();
if(carsOnBridge + waitingS[0] + waitingS[1] == 0)
status = NONE
}
</syntaxhighlight>

=== Esercizio c.1 (da controllare) ===
<syntaxhighlight lang="c">
monitor bridge {

UP=0;
DOWN=1;
bridgeis = DOWN;

bool carAreExiting = false;

condition ok2drive;
condition ok2barca[2];

waitingCar = 0;
carOnBridge = 0;

boatWaiting[2] = {0,0};
boatIsPassing[2] = {false,false}

entry car_enter(direction) {

if (bridgeis == DOWN)
if(carOnBridge == MAXCAR)
waitingCar++;
ok2drive.wait();
waitingCar--;
else if (carAreExiting)
waitingCar++;
ok2drive.wait();
waitingCar--;
else
if (boatIsPassing[0] || boatIsPassing[1])
waitingCar++;
ok2drive.wait();
waitingCar--;
bridgeis = DOWN;

carOnBridge++;
carAreExiting = false;
if(carOnBridge < MAXCAR && !carAreExiting)
ok2drive.signal();

}

entry car_exit(direction) {

carOnBridge--;
carAreExiting = true;

if(carOnBridge == 0)
carAreExiting = false;
if(boatWaiting[0] > 0)
bridgeis = UP;
ok2barca[0].signal();
else if (boatWaiting[1] > 0)
bridgeis = UP;
ok2barca[1].signal();
else
ok2drive.signal();
}

entry boat_enter(direction) {

if (bridgeis == UP)
| if (boatIsPassing[direction] == true)
| | boatWaiting[direction]++;
| | ok2barca.wait();
| | boatWaiting[direction]--;
else
| if (carOnBridge > 0)
| | boatWaiting[direction]++;
| | ok2barca.wait();
| | boatWaiting[direction]--;
| | bridgeis = UP;

boatIsPassing[direction] = true;

if(boatIsPassing[1-direction] == false && boatWaiting[1-direction] > 0)
ok2barca[1-direction].signal();

}

entry boat_exit(direction) {

boatIsPassing[direction] = false;

if (boatIsPassing[1-direction] == false)
if (waitingCar > 0)
bridgeis = DOWN;
ok2drive.signal();
else
if (waitingCar == 0)
ok2barca[direction].signal();

}
</syntaxhighlight>

=== Esercizio c.1 (sbagliato) ===
<syntaxhighlight lang="c">
monitor bridge
condition ok2passCar;
condition ok2passBoat;
condition ok2up;
condition ok2down;
int carOnBridge[2] = 0; //2 sensi di marcia
int boatUnderBridge[2] = 0;
boolean bridge_down = false; //vuol dire che il ponte parte alzato, true ponte abbassato

procedure entry car_enter(direction){
if(bridge_down && carOnBridge[direction] < MAXCAR){
carOnBridge[direction]++;
ok2passCar.signal();
}else if (bridge_down && boatUnderBridge[0] == 0 && boatUnderBridge[1] == 0){
//se non ci sono navi in transito e arriva una macchina abbassa ponte
ok2down.signal();
ok2passCar.signal();
ok2passBoat.wait();
}else{
ok2passCar.wait();
}
}

procedure entry car_exit(direction){
carOnBridge[direction]--;
if(carOnBridge[0] == 0 && carOnBridge[1] == 0){
bridge_down = false;
ok2up.signal();
}else{
ok2up.wait();
}
}

procedure entry boat_enter(direction){
if(!bridge_down && boatUnderBridge[direction] < 1){
boatUnderBridge[direction]++;
ok2passBoat.signal();
}else if(!bridge_down && carOnBridge[0] == 0 && carOnBridge[1] == 0){
ok2up.signal();
ok2passBoat.signal();
ok2passCar.wait();
}else {
ok2passBoat.wait();
}
}

procedure entry boat_exit(direction){
boatUnderBridge[direction]--;
if(boatUnderBridge[0] == 0 && boatUnderBridge[1] == 0){
bridge_down = true;
ok2down.signal();
}else{
ok2down.wait();
}
}
</syntaxhighlight>

=== Esercizio c.1 2o (sbagliato) ===
<syntaxhighlight lang="c">
#define car 1
#define ship 2
#define fromDX 1
#define fromSX 0

monitor bridge {
int carsOnBridge = 0;
int shippingDX = 0; //nave che sta passando dal lato destro
int shippingSX = 0; //nave che sta passando dal lato sinistro
bool isBridgeUp = false;
int last2pass = 0; //ultimo che ha passato il ponte
int waitingS = 0; //navi che stanno aspettando
int waitingC = 0 ; //auto che stanno aspettando

condition ok2ship
condition ok2drive

entry car_enter(int direction){
//un auto si ferma se il numero di auto sul ponte è massimo
//e se l'ultima a passare è stata un auto mentre ci sono navi in attesa
if(carsOnBridge == MAX || isBridgeUp || (last2pass==car && waitingS > 0) ){
waitingC++;
ok2drive.wait;
}
carsOnBridge++;
waitingC--;
}

entry car_exit(int direction){
carsOnBridge--;
last2pass = car;
if(carsOnBridge == 0 && waitingS>0){
isBrigdeUp = true;
ok2ship.signal;
}
}

entry ship_enter(int direction){
//se la barca viene da destra
if(direction == fromDX){
//si ferma anche quando c'è una nave che sta già attraversando nella sua stessa direzione
if (isBridgeup == false || shippingDX || (last2pass==ship && waitingC > 0) ){
waitingS++;
ok2ship.wait;
}
if (waitingS > 0)
waitingS--;
shippingDX = 1;
}
//se la barca viene da sinistra
else if(direction == fromSX){
if (isBridgeup == false || shippingSX || ( (last2pass==ship && waitingC > 0))){
waitingS++;
ok2ship.wait;
}
if (waitingS > 0)
waitingS--;
shippingSX = 1;

}
}

entry ship_exit(int direction){
if(direction == fromDX)
shippingDX = 0;
else if (direction == fromSX)
shippingSX = 0;
last2pass = ship;
if(shippingDX == 0 && shippingSX == 0 && waitingC)
isBrigdeUp == false;
ok2drive.signal;
else if(shippingDX == 0 && shippingSX == 0 && waitingS > 0)
ok2ship.signal;
}
}
</syntaxhighlight>

=== Esercizio c.2 (sbagliato) ===

# (Ri)Controllato dall'utente [[User:Acsor|Acsor]] ([[User talk:Acsor|talk]]) in data 26/08/2020

<syntaxhighlight lang="python">
list printed_msg; # questa è una variabile condivisa che ai fini dell'esercizio non si può utilizzare (message passing)

process server[i]:
while true:
<msg, pid> = arecv(*)

if printed_msg.length == 0 or <msg, pid> is not in printed_msg:
printed_msg.append(<msg,id>)
print(msg)
</syntaxhighlight>

=== Esercizio c.2 (da controllare) ===
Nello svolgimento seguente, receiver incapsula l'ambiente privato del processo; _peers rappresenta il vettore di processi "fratelli" ai quali può essere chiesto di stampare un messaggio, mentre _printed contiene l'hash di tutti i messaggi stampati dal processo locale. Si suppone che istanze della classe receiver possano essere passate come parametro ad areceive() ed asend() (non implementate).

<syntaxhighlight lang="python">
class receiver:
def __init__(self, peers):
"""
:param peers: list of processes this process communicates with.
"""
self._peers = tuple(peers)
self._printed = list()

def run(self):
while True:
process, message = areceive(ANY)

if process in self._peers:
self._reply_query(process, message)
else:
self._print(process, message)

def _print(self, sender, message):
h = hash(message.text)

if h not in self._printed and not self._printed_from_peers(message):
self._printed.append(h)
print(message.text)

def _reply_query(self, sender, h):
"""
Invoked when the current process receive a "query" from a peer process.
`h` contains the hash of a message which may or may have not been
sent from this process; if it was sent, the reply is `Yes`, otherwise `No`.
"""
reply = "Yes" if int(h) in self._printed else "No"
asend(sender, reply)

def _printed_from_peers(self, message):
"""
:return: `True` if this message has already been printed from any of the
peer processes, `False` otherwise.
"""
h = hash(message)

for p in self._peers:
asend(p, str(h))

for p in self._peers:
_, reply = areceive(p)

if reply.text == "Yes":
return True
else if reply.text != "No":
# If the response is neither "Yes" nor "No", then we have got a query
self._reply_query(p, reply)

return False
</syntaxhighlight>

=== Esercizio g.1 (da controllare) ===
Sulla base dei valori in entrata, è possibile costruire le matrici Allocation (q.tà di risorse allocate per processo e per tipo), Need (q.tà di risorse che ogni processo potrebbe ancora chiedere) e il vettore Available (num. di risorse correntemente disponibili).

{| class="wikitable" style="float: left"
! colspan=3 | Allocation
|-
! !! A !! B
|-
| p1 || 4 || 5
|-
| p2 || 3 || 3
|-
| p3 || 2 || 4
|}

{| class="wikitable" style="float: left; margin-left: 1em"
! colspan=3 | Need
|-
! !! A !! B
|-
| p1 || 6 || 8
|-
| p2 || 6 || 3
|-
| p3 || 6 || 8
|}

{| class="wikitable" style="float: left; margin-left: 1em"
! colspan=2 | Available
|-
! A !! B
|-
| x || y
|}

 

Nel caso delle risorse di tipo A, deve aversi x >= 6 in quanto un processo dovrà essere selezionato come primo nella permutazione dell'algoritmo del banchiere multivaluta, e tutti quelli correnti hanno lo stesso valore Need(i)(1); per ciò che riguarda le risorse di tipo B, possiamo ragionare per esaustione

* Se il primo processo della permutazione è p1, allora y >= 8 (con questo valore posso soddisfare la richiesta di p1 e in seguito tutte le altre)
* Se il primo processo della permutazione è p2, allora y >= 5: con questo valore è possibile soddisfare la richiesta di p2; una volta che esso avrà finito, restituirà 3 unità della risorsa B, che permetteranno di soddisfare sia le richieste di A sia quelle di C
* Se il primo processo della permutazione è p3, allora y >= 8 (ragionamento analogo come per p1)

Volendo scegliere il minimo, y >= 5, ed in conclusione (x, y) >= (6, 5).

''Svolgimento basato in parte sull'approccio di Operating System Concepts di Silberschatz. et al, 9th edition, cap. 7.''

=== Esercizio g.2 (da controllare) ===
# Può accadere che il sistema torni in uno stato di safety o che invece porti a deadlock. Diversamente uno stato di safety non può portare direttamente ad uno stato di deadlock, ma solo ad uno di non-safety.
# Selezionare uno o più tra i processi attivi e sospenderli, salvando il loro stato su memoria secondaria operando delle operazioni di swap-out, finché l'insieme dei frame nella memoria centrale non è in grado di soddisfare tutti i processi rimasti attivi.
# La scelta è determinata perlopiù dal fattore costo. Con un sistema RAID 1 è possibile ripristinare un disco guasto molto brevemente, in quanto le operazioni coinvolte prevedono una semplice ricopiatura dal disco di backup; con un sistema RAID 5 il ripristino del disco guasto deve coinvolgere tutti i dischi dell'intero array, e ciò può richiedere anche ore per dischi di grandi dimensioni. D'altra parte RAID 1 è più costoso (con n dischi, posso memorizzare tanta informazione quanto potrei con n / 2 dischi) rispetto a RAID 5 dove, tra gli n dischi, complessivamente soltanto uno è destinato alle informazioni di ridondanza.
# ''Completare.''

Prove scritte 2019

2023-01-17T16:09:27Z

Gio: /* Esercizio c2 */

== Esame 18/06/2019 ==
[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">
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;

}

}
</source>
 

=== Esercizio c.1 (da controllare) ===
<source lang="c">
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;
}
</source>
 

=== Esercizio c.2 ===
**non è l'esercizio corretto**
<source lang="c">
/* 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;
}
</source>
 
Soluzione:
<source lang="c">
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
</source>
 

=== Esercizio g.1 (sbagliato) ===
<nowiki>
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|
</nowiki>
 

=== Esercizio g.1 ===
<nowiki>
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
</nowiki>
 

=== 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 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2019.05.18.tot.pdf 2019.05.18.tot.pdf]

=== Esercizio c.1 (da controllare) ===

* Controllato dall'utente ? in data ?
* ...

Il sorgente seguente può essere eseguito scaricando in una stessa directory il package [[Tool per semafori e monitor|pysm]] del prof. Davoli.

<source lang="python">
#!/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())
</source>

=== Esercizio c.2 (da controllare) ===
<source lang="c">
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();
}
}

</source>

=== 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.

[[File:Epson 25082020151034.jpg]]

=== 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 ==
[https://www.cs.unibo.it/~renzo/so/compiti/2019.02.14.tot.pdf Testo d'esame].

=== Esercizio c.1 (da controllare) ===

* Controllato dall'utente [[User:Acsor|Acsor]] ([[User talk:Acsor|talk]]) in data 16:03, 2 September 2020 (CEST). Ritengo sia: corretto
* Controllato dall'utente ? in data ?

<source lang="python">
# 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()
</source>

=== Esercizio c.2 (controllato) ===

<source lang="python">
# 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
</source>

== Esame 28/05/2019 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2019.05.18.tot.pdf 2019.05.18.tot.pdf]

=== Esercizio c.1 (da controllare) ===
<source lang="c">

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()

</source>

 

=== Esercizio c.1 (da controllare) ===
<source lang="c">
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—;

}
}
</source>

== Esame 15/07/2019 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2019.07.15.tot.pdf 2019.07.15.tot.pdf]
=== Esercizio c.1 ===

# Verifica del 18/05/2020 dell'utente [[User:Acsor|Acsor]]. Ritengo sia: corretto
# Ritenuta corretta [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 15:30, 17 January 2023 (CET)

Una semplice realizzazione in Python dello pseudocodice seguente è disponibile [https://github.com/pollomarzo/rdso1920/tree/master/2019exams/samepc qui].

<source lang="python">
# 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;
</source>

=== 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; [http://www.treccani.it/magazine/lingua_italiana/domande_e_risposte/grammatica/grammatica_030.html 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: [https://www.cs.unibo.it/~renzo/so/compiti/2019.09.13.tot.pdf 2019.09.13.tot.pdf].

=== Esercizio c.1 (controllato) ===
* Controllato dal professor Davoli durante la lezione del 19/05/2020.
* Controllato dall'utente [[User:Acsor|Acsor]] ([[User talk:Acsor|talk]]) in data 19:13, 1 September 2020 (CEST).
* Controllato [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 16:09, 17 January 2023 (CET)

<source lang="python">
# 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
</source>

=== Esercizio c.2 ===

* Controllato da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 16:12, 17 January 2023 (CET)
* Controllato dall'utente ? in data ?
* ...

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

<source lang="c">
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();
}
</source>

=== 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.
<source lang="C">

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();
}

</source>

=== 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.)

[[File:2019-09-13-g1.jpg | 768px]]

=== 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 ===
* Proposta [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 14:25, 17 January 2023 (CET)
<syntaxhighlight lang="C">
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();
}
}

}
</syntaxhighlight>

== Esercizio c2 ==
* Soluzione proposta [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 14:38, 17 January 2023 (CET)
<syntaxhighlight lang="C">
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);
}
}
</syntaxhighlight>

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 [[User:Flecart|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

<syntaxhighlight lang="C">
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());
}
}
}

</syntaxhighlight>

Prove scritte 2022

2023-01-16T21:34:09Z

Gio: /* Soluzione proposta 1 (da controllare) */

= Prova 2022/09/06 =

== Esercizio c1 ==

Esercizio c.1: I bit di un numero intero rappresentano condizioni di un sistema. Se lo stato attuale è 6 (0110) vuole dire
che attualmente sono vere le condizioni 2 (0010) e 4 (0100).
Scrivere un monitor bitcond che fornisca le seguenti procedure entry:
void set(int bit2set); accende nello stato attuale i bit di bit2set
void unset(int bit2unset) spegne nello stato attuale i bit di bit2unset
void statuswait(int bit2wait) attende che lo stato attuale soddisfi tutti le condizioni indicate in bit2wait (cioè
che tutti i bit in bit2wait siano accesi nello stato attuale).
Le richieste statuswait devono essere servite in ordine FIFO (cioè un processo anche se sono presenti tutte le
condizioni necessarie deve attendere se un processo che ha chiamato statuswait prima è in attesa).
Lo stato iniziale è zero (nessuna risorsa disponibile)

=== Soluzione proposta 1 ===
<syntaxhighlight lang=C>

class bitcond{
int bitmap;
int lastBitmask;
int has=0;

condition waiting;
condition c;

void set(int i){
bitmap|=i;
if(bitmap&lastBitmask == bitmap) c.signal();
}
void unset(int i){
bitmap&=~i;
}
void statuswait(int i){
has++;
if(has>1){
waiting.wait();
}

if(!(bitmap&i==i)){
lastBitmask=i;
c.wait();
}

waiting.signal();
has--;
}
bitcond(){
bitmap = 0;
}
}

</syntaxhighlight>

=== Soluzione proposta 2 ===
Proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 12:06, 14 January 2023 (CET)
<syntaxhighlight lang=C>

const int int_size = 32;

class monitor {
int value;
condition bitset[int_size];

int numstatuswaiting;
condition waiting;

monitor() {
value = 0;
}

/// guarda se il bit n-significativo è settato in from
bool nbit(int from, int n) {
return (from & (1 << n)) != 0
}

void entry set(int bit2set) {
value |= bit2set;

for (int i = 0; i < 32; i++) {
if (nbit(value, i))
bitset[i].signal();
}
}

void entry statuswait(int bit2wait) {
// in questo modo solamente un singolo processo è dentro ad aspettare
// che tutte le condizioni siano rispettate
if (numstatuswaiting > 0)
waiting.wait();

numstatuswaiting++;
int i = 0;
while(i < 32) {
if (nbit(bit2wait, i) && !nbit(value, i)) {
bitset[i].wait();

// ricomincia a guardare tutti i bit da zero, perché
// nel frattempo potrebbero essere cambiati.
// -1 così con l'istruzione successiva diventa 0
i = -1;
}
i++;
}

numstatuswaiting--;
waiting.signal();
}
}

</syntaxhighlight>

=== Soluzione proposta 3 ===
Proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 12:07, 14 January 2023 (CET)
questa è la soluzione più brutta, ma dovrebbe andare.
<syntaxhighlight lang=C>

const int int_size = 32;

class monitor {
int value;
condition status;

int numstatuswaiting;
condition waiting;

monitor() {
value = 0;
}

/// guarda se il bit n-significativo è settato in from
bool nbit(int from, int n) {
return (from & (1 << n)) != 0
}

void entry set(int bit2set) {
value |= bit2set;
status.signal();
}

void entry unset(int bit2unset) {
value = (value & ~bit2unset);
}

void entry statuswait(int bit2wait) {
// in questo modo solamente un singolo processo è dentro ad aspettare
// che tutte le condizioni siano rispettate
if (numstatuswaiting > 0)
waiting.wait();

numstatuswaiting++;
while(true) {
if ((value & bit2wait) == bit2wait)
break;
else
status.wait();
}
numstatuswaiting--;
waiting.signal();
}
}
</syntaxhighlight>

= Prova 2022/06/21 =

== Esercizio c1 ==
Scrivere il monitor collocamento:
void cercolavoro(char *nome, char *skill)
void char *assumo(char * skill)
Quando un processo chiama la cercolavoro si mette in attesa di una richiesta di lavoro e rimane bloccato nel monitor
fino a che non è stato assunto. Nella cercolavoro viene indicato il nome dell'aspirante lavoratore la sua capacità (skill).
Un datore di lavoro con necessità di personale chiama la assumo specificando la capacità richiesta. Se c'è in attesa
almeno un aspirante lavoratore con quella specifica capacità (uguale valore di skill), il datore di lavoro riceve il nome del
nuovo dipendente ed entrambi i processi escono dal monitor. Nel caso non ci siano richieste compatibili il datore di
lavoro si blocca nel monitor attendendo un lavoratore con la capacità cercata. Quando arriva il lavoratore che soddisfa
le richieste si sbloccano entrambi i processi lavoratore e datore di lavoro. La assumo restituisce in ogni caso il nome del
dipendente da assumere.

=== Soluzione proposta ===

Soluzione proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 12:08, 14 January 2023 (CET)

ci potrebbe essere un errore in quanto non è specificato il comportamento della struttura dati in alcune situazioni

<syntaxhighlight lang=C>

class collocamento{

set<char *, condition> richieste; // chi assume cerca questa skill
set<char *, char *, condition> ricerche; // nome e skill di chi cerca

char *last_nome;

collocamento {
last_nome = NULL;
richieste = set();
ricerche = set();
}

void cercolavoro(char *nome, char *skill) {
datore = richieste.find(skill); // cerca valutando la prima come chiave
if (datore != NULL) {
<skill, cond> = datore;
richieste.remove(datore);
last_nome = nome;
cond.signal();
} else {
condition c = new condition();
ricerche.insert(nome, skill, c);
c.wait();
free(c);
}
}

void char *assumo(char * skill){
lavoratore = ricerche.find2(skill); // cerca valutando la seconda come chiave.
if (lavoratore != NULL) {
<nome, skill, cond> = lavoratore;
ricerche.remove(lavoratore);
cond.signal();
last_nome = nome;
} else {
condition c = new condition();
richieste.insert(skill, c);
c.wait();
free(c);
}

return last_nome;
}

}// class collocamento
</syntaxhighlight>

=== Soluzione proposta ===

Soluzione proposta da [[User:Flecart|Flecart Frend]], regalo la proprietà intellettuale di questa soluzione a flecart.

<syntaxhighlight lang=C>
class workdisptcher{

// la multi map può storare più di un valore per una chiave
// quando viene richiesta una particolare chiave da in maniera LIFO
// il risultato
// es:
// multi_map<char *,int> lavoratori;
// lavoratori.insert("prova",2);
// lavoratori.insert("prova",1);
// lavoratori.get("prova") == 2
// lavoratori.remove("prova")
// lavoratori.get("prova") == 1
multi_map<char *,(char*,cond)> lavoratori;
multi_map<char *,cond> posti_aperti;
char* buffer_name;
void cercolavoro(char *nome, char *skill){
if(posti_aperti.find(skill)){
auto entry =posti_aperti.get(skill);
posti_aperti.remove(entry);
buffer_name=name;
entry.1.signal();
}else{
cond c= new cond();
lavoratori.insert(skill,(nome,c)) ;
c.wait();
free(c);
}
}
void char *assumo(char * skill){
if(lavoratori.find(skill)){
auto entry =lavoratori.get(skill);
posti_aperti.remove(entry);
auto [nome,cnd] = entry.1;
cond.signal();
return nome;
}else{
cond c= new cond();
posti_aperti.insert(skill,c) ;
c.wait();
free(c);
return buffer_name;
}

}

}

</syntaxhighlight>

== Esercizio c2 ==
Un servizio viene fornito in modalità client-server usando message passing asincrono.
Al fine di aumentare l'efficienza si decide di usare molti server e un processo dispatcher in grado di distribuire le
richieste agli N server. Quando un processo server è libero riceve dal dispatcher la prossima richiesta da elaborare:
codice di ogni client (tanti!): .....
asend(<getpid(), request>, dispatcher)
result = arecv(dispatcher)

server process[i], i = 0, ..., N-1:
request = arecv(dispatcher)
result = compute(request)
asend(<getpid(), result>, dispatcher)
Scrivere il processo dispatcher. (il dispatcher conosce i pid di tutti i server).

=== Soluzione proposta (sbagliata) ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]

Questo esercizio è stato corretto tempo fa in classe dal professore, **non è completamente corretto** se si vuole provare a correggerlo alla fine dell'esercizio c'è scritto cos'è sbagliato.

<syntaxhighlight lang=C>

extern int N;
process dispatcher() {
// indice che tiene conto a quale server dover mandare
// per semplicità supponiamo che i server abbiano PID
// da 0 a N - 1
int i = 0;

// mappa server a pid del processo che lo ha richiesto.
// chiave: pid del server
// value: queue richiesta dispatchata al server in chiave
map<int, queue<int>> mapper;
while (true) {
res = arecv(ANY);

// in questa parte l'importante è sapere
// se la richiesta proviene dal server o da un altro
// processo, ho assunto che la disambiguazione
// fosse immediata, un altro modo per checkare questo
// è vedere se il PID del messaggio rientri fra quelli
// noti al dispatcher.
if (<pid, request> = res) {
mapper[i].enqueue(pid);
asend(request, i /*il i-esimo server*/);
i++;
i %= N;
} else if (<pid, response> = res) {
requester_pid = mapper[pid].dequeue();
asend(response, requester_pid);
}
}
}
</syntaxhighlight>

l'es è sbagliato perchè dovrei mandare ai server liberi, non a round-robin [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 15:52, 14 January 2023 (CET)

=== Soluzione proposta 2 ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Gio Giovanni Spadaccini]

<syntaxhighlight lang=C>
dispatcher{
queue<<pid,request>> work;
queue<pid> freeserver;
map<pid,pid> map_server_to_client;
while(true){
<pid,message>=arecv(ANY);
if pid in servers{
client=map_server_to_client.get(pid);
map_client_to_server.remove(pid);
freeserver.push(pid);
asend(<message>,client);
}else{
work.push(<pid,message>);
}
while !freeserver.empty() and !work.emtpy(){
server_pid = freeserver.pop();
<client,msg> = work.pop();
map_server_to_client.insert(server,client);
asend(msg,server_pid);
}
}
}
</syntaxhighlight>

= Prova 2022/06/01 =

== Esercizio c1 ==

Scrivere il monitor delay che fornisce due procedure entry:
int wait_tick(int nticks)
void tick(void)
La procedure entry tick è pensata per essere richiamata periodicamente (es. ogni secondo o ora o giorno) da un
processo.
Quando un processo chiama la wait_tick deve attendere un numero di chiamate della tick pari al parametro nticks.
Per esempio se un processo chiama wait_tick(2) deve fermarsi e verrà riattivato alla seconda successiva chiamata di
tick.
La funzione wait_tick ha come valore di ritorno il numero di processi che erano bloccati al momento della tick che ha
sbloccato il chiamante.
Esempio: P chiama wait_tick(2) e si blocca. Q chiama wait_tick(3) e si blocca. T chiama tick() non succede nulla. R
chiama wait_tick(2) e si blocca. T chiama tick(), viene sbloccata la wait_tick di P e il valore ritornato è 3. T chiama
tick(), vengono sbloccate le wait_tick di Q e R e il valore ritornato per entrambi i processi è 2

=== Soluzione proprosta 1 (da controllare) ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]

<syntaxhighlight lang=C>

class MonitorDelay {
int curr_time;
int waiting_num;

// min heap con il tempo di sblocco dei processi e la condizione su cui è fermato
// il tempo di sblocco minore è messo in cima alla heap
// la sintassi con pair è ispirata alla std::pair di c++
heap<pair<int, condition>> waiting;

void init() {
curr_time = 0;
waiting = heap<pair<int, condition>>();
}

int entry wait_tick(int nticks) {
if (nticks <= 0) {
return waiting.size();
} else {
condition c = new condition();
waiting.insert(make_pair(nticks + curr_time, c));
c.wait();
free(c);
}
return waiting_num;
}

void entry tick(void) {
waiting_num = waiting.size();
curr_time++;

while (waiting.head().first <= curr_time) {
condition c = waiting.head().second;
waiting.deleteHead();
c.signal();
}
}
}
</syntaxhighlight>

== Esercizio c2 ==

=== Consegna ===

Esercizio c.2: Un servizio di message passing asincrono non fifo (nfasend/nfarecv) consegna in tempo finito tutti i
messaggi spediti ma non è garantito che i messaggi vengano ricevuti nell'ordine nel quale sono stati spediti.
void nfasend(msg_t msg, pid_t dest)
msg_t nfarecv(pid_t sender)
Dato un servizio di message passing asincrono non fifo scrivere una libreria che implementi il servizio di message
passing asincrono fifo:
void asend(msg_t msg, pid_t dest)
msg_t arecv(pid_t sender)
Nota: sia il servizio dato (non fifo) sia quello da implementare (fifo) consentono la ricezione solo da mittente specificato
(non supportano ANY/*).

=== Soluzione proposta 1 ===

<syntaxhighlight lang="C">

void nfasend(msg_t msg, pid_t dest);
msg_t nfarecv(pid_t sender);

// array di grandezza di massimi numero di processi, inizializzato a 0
// utilizzato per contare il numero di messaggi inviati a un certo processo.
int num_sender[MAX_PROC];

//RICORDA che ogni sender ha il suo num_sender[...]

void asend(msg_t msg, pid_t dest) {
src = getpid();
nfasend(<msg, num_send[dest]>, dest);
num_sender[dest]++;
}

// molto simile a num_sender, ma è utilizzato per contare il numero di messaggi ricevuti, in ordine.
int num_receiver[MAX_PROC];
// array heap ordinato sul int (per ogni heap in cima c'è il messaggio col minimo int).
min_heap<msg, int> messages[MAX_PROC];

//RICORDA che ogni receiver ha il suo proprio num_receiver[...] e messages[...]

msg_t arecv(pid_t sender) {
p = getpid();

if (messages[sender].size() > 0 && messages[sender].top() == num_receiver[sender]) {
(msg, num_mess) = messages[sender].removeTop();
num_receiver[sender]++;
return msg;
}

(msg, num_mess) = nfarecv(sender);

while (num_mess != num_receiver[sender]) {
messages[sender].insert(msg, num_mess);
(msg, num_mess) = nfarecv(sender);
}

num_receiver[sender]++;
return msg;
}

</syntaxhighlight>

= Prova 2022/02/14 =

== Esercizio c1 ==
Scrivere il monitor semdata che implementi un semaforo con dato. Questa astrazione prevede due operazioni:

datatype dP(void);
void dV(datatype data);

Non è previsto assegmento di valore iniziale nel costruttore, l'invariante è lo stesso dei semafori (con init = 0): ndP <=
ndV (dove ndP e ndV rappresentano rispettivamente il numero di operazioni dP e dV completate. I dati passati come
parametro alla dV devono essere memorizzati in ordine LIFO. L'operazione nP restituisce il valore più recente fra quelli
memorizzati (e lo cancella dalla struttura dati).

=== Proposta di soluzione 1 ===
* Proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 12:06, 16 January 2023 (CET)

<syntaxhighlight lang="C">

class semdata {

stack<datatype> pila;
condition p_waiting;

semdata() {
pila = stack();
}

datatype dp(void) {
if (pila.len() <= 0) {
p_waiting.wait();
}

return pila.pop();
}

void dV(datatype data) {
pila.push(data);
p_waiting.signal();
}

}
</syntaxhighlight>

= Prova 2022/01/17 =

== Esercizio c1 ==

Scrivere il monitor multibuf che implementi un buffer limitato (MAX elementi) di oggetti di tipo T che
implementi le seguenti procedure entry:
void add(int n, T objexts[]);
void get(int n, T objects[]);
La funzione add deve aggiungere al buffer gli n oggetti passati col parametro objects. La funzione get deve predere
dal buffer in modalità FIFO i primi n elementi presenti nel buffer e copiarli negli elementi del vettore objects.
Entrambe le funzioni devono attendere che vi siano le condizioni per poter essere completate: che ci siano n elementi
liberi per la add, che ci siano n elementi nel buffer per la get. Non sono ammesse esecuzioni parziali: mentre attendono
le rispettive condizioni nessun elemento può essere aggiunto o rimosso dal buffer.
La definizione del problema C.1 presenta casi di possibile deadlock?

=== Soluzione proposta 1 ===

* Proposta [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 12:41, 16 January 2023 (CET)

Una situazione di deadlock è quando un add non ha abbastanza per inserire, e get non ha abbastanza da prendere. Se non utilizzo la coda come ho fatto così
rischio starvation.

<syntaxhighlight lang="C">
class multibuf {

T buffer[MAX];
int i, j;
int free;
queue<int,cond> add_queue;

queue<int,cond> get_queue;

multibuf {
i = j = 0;
free = MAX;
}

void add(int n, T objects[]) {
if (add_queue.size() > 0 || free < n) {
condition c = new condition();
add_queue.enqueue(n, c);
c.wait();
free(c);
}

for (int k = j; k != (j + n) % MAX; k = (k + 1) % MAX) {
int other_idx = (k - i) < 0 ? k + MAX - i : k - i;
buffer[k] = objects[other_idx];
}
free -= n;
j = (j + n) % MAX;

while (get_queue.size() > 0 && get_queue.front() <= MAX - free) {
n, cond = get_queue.dequeue();
cond.signal();
}
}

void get(int n, T objects[]) {
if (get_queue.size() > 0 || MAX - free < n) {
condition c = new condition();
get_queue.enqueue(n, c);
c.wait();
free(c);
}

for (int k = i; k != (i + n) % MAX; k = (k + 1) % MAX) {
int other_idx = (k - i) < 0 ? k + MAX - i : k - i;
objects[other_idx] = buffer[k];
}
free += n;
i = (i + n) % MAX;

while (add_queue.size() > 0 && add_queue.front() <= free) {
n, cond = add_queue.dequeue();
cond.signal();
}
}

} // multibuf
</syntaxhighlight>

== Esercizio c2 ==
Un servizio di message passing sincrono senza selezione del mittente prevede una API con due funzioni:
sasend(msg_t msg, pid dest);
msg_t sarecv(void);
La funzione sarecv restituisce il primo messaggio ricevuto da qualsiasi mittente ed è bloccante se non ci sono
messaggi pendenti. la funzione sasend si blocca fino a quando il messaggio msg non viene ricevuto dal processo dest.
Dato quindi un servizio di message passing sincrono senza selezione del mittente implementare un servizio di
message passing sincrono (standard, quello definito nel corso) senza fare uso di processi server.

=== Soluzione proposta 1 (da controllare) ===
* proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 18:25, 16 January 2023 (CET)
<syntaxhighlight lang="C">

ssend(msg_t msg, pid dest) {
sasend(<msg, getpid()>, dest);
}

// variabili interne di srecv
queue<msg_t> msgs[MAX_PROC];

// suppongo non ci sia il caso in cui sender = ANY.
// nel caso ci fosse la necessità, si dovrebbe creare una altra struttura di dati
// che ordini globalmente il messaggio che sia arrivato prima.
msg_t srecv(pid sender) {
if (msgs[sender].len() > 0) {
return msgs[sender].dequeue();
}

while (true) {
<msg, pid> = sarecv();
if (pid == sender) {
return msgs[pid].dequeue();
} else {
msgs[pid].enqueue(msg);
}
}
}

</syntaxhighlight>

=== Soluzione proposta 2 (da controllare) ===

proposta da [[User:Flecart|Flecart Friend]] cedo la proprità intellettuale di questa soluzione a flecart

<syntaxhighlight lang="C">
// mem è condivisa tra ssend e srecv di ogni processo
// essendo che un processo può solo mandare o ricevere alla volta
// non abbiamo bisogno di cs

// inizializzati tutti a NULL
msg_t mem[MAXPID];
// in mem ci basta un messaggio per PID perchè un pid può aver mandato al
// massimo un messaggio essendo che sono bloccanti la send e la recive

void ssend(msg_t msg, pid dest) {
sasend(<getpid(),msg>,dest);
while(true){
<form_c,msg>=sarecv();
// dovrebbe essere ovvio che se è from c allora il msg dovrebbe essere un
// ack perchè se c avesse mandato un messaggio diverso vorrebbe dire che
// sta facendo una send e se i due processi si fanno una send allora c'è
// deadhlock
if(from_c == dest && msg == ACK){
break;
}else{
mem[from_c]=msg;
}
}
}

msg_t srecv(pid from) {
if(mem[from]!=NULL){
t=mem[from];
mem[from]=NULL;
ssend(ACK,from);
return t;
}
while(true){
<form_c,msg>=sarecv();
if(from_c==from){
ssend(ACK,from);
return msg;
}else{
mem[from_c].push(msg);
}
}
}

</syntaxhighlight>

Prove scritte 2022

2023-01-16T21:32:59Z

Gio: /* Esercizio c2 */

= Prova 2022/09/06 =

== Esercizio c1 ==

Esercizio c.1: I bit di un numero intero rappresentano condizioni di un sistema. Se lo stato attuale è 6 (0110) vuole dire
che attualmente sono vere le condizioni 2 (0010) e 4 (0100).
Scrivere un monitor bitcond che fornisca le seguenti procedure entry:
void set(int bit2set); accende nello stato attuale i bit di bit2set
void unset(int bit2unset) spegne nello stato attuale i bit di bit2unset
void statuswait(int bit2wait) attende che lo stato attuale soddisfi tutti le condizioni indicate in bit2wait (cioè
che tutti i bit in bit2wait siano accesi nello stato attuale).
Le richieste statuswait devono essere servite in ordine FIFO (cioè un processo anche se sono presenti tutte le
condizioni necessarie deve attendere se un processo che ha chiamato statuswait prima è in attesa).
Lo stato iniziale è zero (nessuna risorsa disponibile)

=== Soluzione proposta 1 ===
<syntaxhighlight lang=C>

class bitcond{
int bitmap;
int lastBitmask;
int has=0;

condition waiting;
condition c;

void set(int i){
bitmap|=i;
if(bitmap&lastBitmask == bitmap) c.signal();
}
void unset(int i){
bitmap&=~i;
}
void statuswait(int i){
has++;
if(has>1){
waiting.wait();
}

if(!(bitmap&i==i)){
lastBitmask=i;
c.wait();
}

waiting.signal();
has--;
}
bitcond(){
bitmap = 0;
}
}

</syntaxhighlight>

=== Soluzione proposta 2 ===
Proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 12:06, 14 January 2023 (CET)
<syntaxhighlight lang=C>

const int int_size = 32;

class monitor {
int value;
condition bitset[int_size];

int numstatuswaiting;
condition waiting;

monitor() {
value = 0;
}

/// guarda se il bit n-significativo è settato in from
bool nbit(int from, int n) {
return (from & (1 << n)) != 0
}

void entry set(int bit2set) {
value |= bit2set;

for (int i = 0; i < 32; i++) {
if (nbit(value, i))
bitset[i].signal();
}
}

void entry statuswait(int bit2wait) {
// in questo modo solamente un singolo processo è dentro ad aspettare
// che tutte le condizioni siano rispettate
if (numstatuswaiting > 0)
waiting.wait();

numstatuswaiting++;
int i = 0;
while(i < 32) {
if (nbit(bit2wait, i) && !nbit(value, i)) {
bitset[i].wait();

// ricomincia a guardare tutti i bit da zero, perché
// nel frattempo potrebbero essere cambiati.
// -1 così con l'istruzione successiva diventa 0
i = -1;
}
i++;
}

numstatuswaiting--;
waiting.signal();
}
}

</syntaxhighlight>

=== Soluzione proposta 3 ===
Proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 12:07, 14 January 2023 (CET)
questa è la soluzione più brutta, ma dovrebbe andare.
<syntaxhighlight lang=C>

const int int_size = 32;

class monitor {
int value;
condition status;

int numstatuswaiting;
condition waiting;

monitor() {
value = 0;
}

/// guarda se il bit n-significativo è settato in from
bool nbit(int from, int n) {
return (from & (1 << n)) != 0
}

void entry set(int bit2set) {
value |= bit2set;
status.signal();
}

void entry unset(int bit2unset) {
value = (value & ~bit2unset);
}

void entry statuswait(int bit2wait) {
// in questo modo solamente un singolo processo è dentro ad aspettare
// che tutte le condizioni siano rispettate
if (numstatuswaiting > 0)
waiting.wait();

numstatuswaiting++;
while(true) {
if ((value & bit2wait) == bit2wait)
break;
else
status.wait();
}
numstatuswaiting--;
waiting.signal();
}
}
</syntaxhighlight>

= Prova 2022/06/21 =

== Esercizio c1 ==
Scrivere il monitor collocamento:
void cercolavoro(char *nome, char *skill)
void char *assumo(char * skill)
Quando un processo chiama la cercolavoro si mette in attesa di una richiesta di lavoro e rimane bloccato nel monitor
fino a che non è stato assunto. Nella cercolavoro viene indicato il nome dell'aspirante lavoratore la sua capacità (skill).
Un datore di lavoro con necessità di personale chiama la assumo specificando la capacità richiesta. Se c'è in attesa
almeno un aspirante lavoratore con quella specifica capacità (uguale valore di skill), il datore di lavoro riceve il nome del
nuovo dipendente ed entrambi i processi escono dal monitor. Nel caso non ci siano richieste compatibili il datore di
lavoro si blocca nel monitor attendendo un lavoratore con la capacità cercata. Quando arriva il lavoratore che soddisfa
le richieste si sbloccano entrambi i processi lavoratore e datore di lavoro. La assumo restituisce in ogni caso il nome del
dipendente da assumere.

=== Soluzione proposta ===

Soluzione proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 12:08, 14 January 2023 (CET)

ci potrebbe essere un errore in quanto non è specificato il comportamento della struttura dati in alcune situazioni

<syntaxhighlight lang=C>

class collocamento{

set<char *, condition> richieste; // chi assume cerca questa skill
set<char *, char *, condition> ricerche; // nome e skill di chi cerca

char *last_nome;

collocamento {
last_nome = NULL;
richieste = set();
ricerche = set();
}

void cercolavoro(char *nome, char *skill) {
datore = richieste.find(skill); // cerca valutando la prima come chiave
if (datore != NULL) {
<skill, cond> = datore;
richieste.remove(datore);
last_nome = nome;
cond.signal();
} else {
condition c = new condition();
ricerche.insert(nome, skill, c);
c.wait();
free(c);
}
}

void char *assumo(char * skill){
lavoratore = ricerche.find2(skill); // cerca valutando la seconda come chiave.
if (lavoratore != NULL) {
<nome, skill, cond> = lavoratore;
ricerche.remove(lavoratore);
cond.signal();
last_nome = nome;
} else {
condition c = new condition();
richieste.insert(skill, c);
c.wait();
free(c);
}

return last_nome;
}

}// class collocamento
</syntaxhighlight>

=== Soluzione proposta ===

Soluzione proposta da [[User:Flecart|Flecart Frend]], regalo la proprietà intellettuale di questa soluzione a flecart.

<syntaxhighlight lang=C>
class workdisptcher{

// la multi map può storare più di un valore per una chiave
// quando viene richiesta una particolare chiave da in maniera LIFO
// il risultato
// es:
// multi_map<char *,int> lavoratori;
// lavoratori.insert("prova",2);
// lavoratori.insert("prova",1);
// lavoratori.get("prova") == 2
// lavoratori.remove("prova")
// lavoratori.get("prova") == 1
multi_map<char *,(char*,cond)> lavoratori;
multi_map<char *,cond> posti_aperti;
char* buffer_name;
void cercolavoro(char *nome, char *skill){
if(posti_aperti.find(skill)){
auto entry =posti_aperti.get(skill);
posti_aperti.remove(entry);
buffer_name=name;
entry.1.signal();
}else{
cond c= new cond();
lavoratori.insert(skill,(nome,c)) ;
c.wait();
free(c);
}
}
void char *assumo(char * skill){
if(lavoratori.find(skill)){
auto entry =lavoratori.get(skill);
posti_aperti.remove(entry);
auto [nome,cnd] = entry.1;
cond.signal();
return nome;
}else{
cond c= new cond();
posti_aperti.insert(skill,c) ;
c.wait();
free(c);
return buffer_name;
}

}

}

</syntaxhighlight>

== Esercizio c2 ==
Un servizio viene fornito in modalità client-server usando message passing asincrono.
Al fine di aumentare l'efficienza si decide di usare molti server e un processo dispatcher in grado di distribuire le
richieste agli N server. Quando un processo server è libero riceve dal dispatcher la prossima richiesta da elaborare:
codice di ogni client (tanti!): .....
asend(<getpid(), request>, dispatcher)
result = arecv(dispatcher)

server process[i], i = 0, ..., N-1:
request = arecv(dispatcher)
result = compute(request)
asend(<getpid(), result>, dispatcher)
Scrivere il processo dispatcher. (il dispatcher conosce i pid di tutti i server).

=== Soluzione proposta (sbagliata) ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]

Questo esercizio è stato corretto tempo fa in classe dal professore, **non è completamente corretto** se si vuole provare a correggerlo alla fine dell'esercizio c'è scritto cos'è sbagliato.

<syntaxhighlight lang=C>

extern int N;
process dispatcher() {
// indice che tiene conto a quale server dover mandare
// per semplicità supponiamo che i server abbiano PID
// da 0 a N - 1
int i = 0;

// mappa server a pid del processo che lo ha richiesto.
// chiave: pid del server
// value: queue richiesta dispatchata al server in chiave
map<int, queue<int>> mapper;
while (true) {
res = arecv(ANY);

// in questa parte l'importante è sapere
// se la richiesta proviene dal server o da un altro
// processo, ho assunto che la disambiguazione
// fosse immediata, un altro modo per checkare questo
// è vedere se il PID del messaggio rientri fra quelli
// noti al dispatcher.
if (<pid, request> = res) {
mapper[i].enqueue(pid);
asend(request, i /*il i-esimo server*/);
i++;
i %= N;
} else if (<pid, response> = res) {
requester_pid = mapper[pid].dequeue();
asend(response, requester_pid);
}
}
}
</syntaxhighlight>

l'es è sbagliato perchè dovrei mandare ai server liberi, non a round-robin [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 15:52, 14 January 2023 (CET)

=== Soluzione proposta 2 ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Gio Giovanni Spadaccini]

<syntaxhighlight lang=C>
dispatcher{
queue<<pid,request>> work;
queue<pid> freeserver;
map<pid,pid> map_server_to_client;
while(true){
<pid,message>=arecv(ANY);
if pid in servers{
client=map_server_to_client.get(pid);
map_client_to_server.remove(pid);
freeserver.push(pid);
asend(<message>,client);
}else{
work.push(<pid,message>);
}
while !freeserver.empty() and !work.emtpy(){
server_pid = freeserver.pop();
<client,msg> = work.pop();
map_server_to_client.insert(server,client);
asend(msg,server_pid);
}
}
}
</syntaxhighlight>

= Prova 2022/06/01 =

== Esercizio c1 ==

Scrivere il monitor delay che fornisce due procedure entry:
int wait_tick(int nticks)
void tick(void)
La procedure entry tick è pensata per essere richiamata periodicamente (es. ogni secondo o ora o giorno) da un
processo.
Quando un processo chiama la wait_tick deve attendere un numero di chiamate della tick pari al parametro nticks.
Per esempio se un processo chiama wait_tick(2) deve fermarsi e verrà riattivato alla seconda successiva chiamata di
tick.
La funzione wait_tick ha come valore di ritorno il numero di processi che erano bloccati al momento della tick che ha
sbloccato il chiamante.
Esempio: P chiama wait_tick(2) e si blocca. Q chiama wait_tick(3) e si blocca. T chiama tick() non succede nulla. R
chiama wait_tick(2) e si blocca. T chiama tick(), viene sbloccata la wait_tick di P e il valore ritornato è 3. T chiama
tick(), vengono sbloccate le wait_tick di Q e R e il valore ritornato per entrambi i processi è 2

=== Soluzione proprosta 1 (da controllare) ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]

<syntaxhighlight lang=C>

class MonitorDelay {
int curr_time;
int waiting_num;

// min heap con il tempo di sblocco dei processi e la condizione su cui è fermato
// il tempo di sblocco minore è messo in cima alla heap
// la sintassi con pair è ispirata alla std::pair di c++
heap<pair<int, condition>> waiting;

void init() {
curr_time = 0;
waiting = heap<pair<int, condition>>();
}

int entry wait_tick(int nticks) {
if (nticks <= 0) {
return waiting.size();
} else {
condition c = new condition();
waiting.insert(make_pair(nticks + curr_time, c));
c.wait();
free(c);
}
return waiting_num;
}

void entry tick(void) {
waiting_num = waiting.size();
curr_time++;

while (waiting.head().first <= curr_time) {
condition c = waiting.head().second;
waiting.deleteHead();
c.signal();
}
}
}
</syntaxhighlight>

== Esercizio c2 ==

=== Consegna ===

Esercizio c.2: Un servizio di message passing asincrono non fifo (nfasend/nfarecv) consegna in tempo finito tutti i
messaggi spediti ma non è garantito che i messaggi vengano ricevuti nell'ordine nel quale sono stati spediti.
void nfasend(msg_t msg, pid_t dest)
msg_t nfarecv(pid_t sender)
Dato un servizio di message passing asincrono non fifo scrivere una libreria che implementi il servizio di message
passing asincrono fifo:
void asend(msg_t msg, pid_t dest)
msg_t arecv(pid_t sender)
Nota: sia il servizio dato (non fifo) sia quello da implementare (fifo) consentono la ricezione solo da mittente specificato
(non supportano ANY/*).

=== Soluzione proposta 1 ===

<syntaxhighlight lang="C">

void nfasend(msg_t msg, pid_t dest);
msg_t nfarecv(pid_t sender);

// array di grandezza di massimi numero di processi, inizializzato a 0
// utilizzato per contare il numero di messaggi inviati a un certo processo.
int num_sender[MAX_PROC];

//RICORDA che ogni sender ha il suo num_sender[...]

void asend(msg_t msg, pid_t dest) {
src = getpid();
nfasend(<msg, num_send[dest]>, dest);
num_sender[dest]++;
}

// molto simile a num_sender, ma è utilizzato per contare il numero di messaggi ricevuti, in ordine.
int num_receiver[MAX_PROC];
// array heap ordinato sul int (per ogni heap in cima c'è il messaggio col minimo int).
min_heap<msg, int> messages[MAX_PROC];

//RICORDA che ogni receiver ha il suo proprio num_receiver[...] e messages[...]

msg_t arecv(pid_t sender) {
p = getpid();

if (messages[sender].size() > 0 && messages[sender].top() == num_receiver[sender]) {
(msg, num_mess) = messages[sender].removeTop();
num_receiver[sender]++;
return msg;
}

(msg, num_mess) = nfarecv(sender);

while (num_mess != num_receiver[sender]) {
messages[sender].insert(msg, num_mess);
(msg, num_mess) = nfarecv(sender);
}

num_receiver[sender]++;
return msg;
}

</syntaxhighlight>

= Prova 2022/02/14 =

== Esercizio c1 ==
Scrivere il monitor semdata che implementi un semaforo con dato. Questa astrazione prevede due operazioni:

datatype dP(void);
void dV(datatype data);

Non è previsto assegmento di valore iniziale nel costruttore, l'invariante è lo stesso dei semafori (con init = 0): ndP <=
ndV (dove ndP e ndV rappresentano rispettivamente il numero di operazioni dP e dV completate. I dati passati come
parametro alla dV devono essere memorizzati in ordine LIFO. L'operazione nP restituisce il valore più recente fra quelli
memorizzati (e lo cancella dalla struttura dati).

=== Proposta di soluzione 1 ===
* Proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 12:06, 16 January 2023 (CET)

<syntaxhighlight lang="C">

class semdata {

stack<datatype> pila;
condition p_waiting;

semdata() {
pila = stack();
}

datatype dp(void) {
if (pila.len() <= 0) {
p_waiting.wait();
}

return pila.pop();
}

void dV(datatype data) {
pila.push(data);
p_waiting.signal();
}

}
</syntaxhighlight>

= Prova 2022/01/17 =

== Esercizio c1 ==

Scrivere il monitor multibuf che implementi un buffer limitato (MAX elementi) di oggetti di tipo T che
implementi le seguenti procedure entry:
void add(int n, T objexts[]);
void get(int n, T objects[]);
La funzione add deve aggiungere al buffer gli n oggetti passati col parametro objects. La funzione get deve predere
dal buffer in modalità FIFO i primi n elementi presenti nel buffer e copiarli negli elementi del vettore objects.
Entrambe le funzioni devono attendere che vi siano le condizioni per poter essere completate: che ci siano n elementi
liberi per la add, che ci siano n elementi nel buffer per la get. Non sono ammesse esecuzioni parziali: mentre attendono
le rispettive condizioni nessun elemento può essere aggiunto o rimosso dal buffer.
La definizione del problema C.1 presenta casi di possibile deadlock?

=== Soluzione proposta 1 ===

* Proposta [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 12:41, 16 January 2023 (CET)

Una situazione di deadlock è quando un add non ha abbastanza per inserire, e get non ha abbastanza da prendere. Se non utilizzo la coda come ho fatto così
rischio starvation.

<syntaxhighlight lang="C">
class multibuf {

T buffer[MAX];
int i, j;
int free;
queue<int,cond> add_queue;

queue<int,cond> get_queue;

multibuf {
i = j = 0;
free = MAX;
}

void add(int n, T objects[]) {
if (add_queue.size() > 0 || free < n) {
condition c = new condition();
add_queue.enqueue(n, c);
c.wait();
free(c);
}

for (int k = j; k != (j + n) % MAX; k = (k + 1) % MAX) {
int other_idx = (k - i) < 0 ? k + MAX - i : k - i;
buffer[k] = objects[other_idx];
}
free -= n;
j = (j + n) % MAX;

while (get_queue.size() > 0 && get_queue.front() <= MAX - free) {
n, cond = get_queue.dequeue();
cond.signal();
}
}

void get(int n, T objects[]) {
if (get_queue.size() > 0 || MAX - free < n) {
condition c = new condition();
get_queue.enqueue(n, c);
c.wait();
free(c);
}

for (int k = i; k != (i + n) % MAX; k = (k + 1) % MAX) {
int other_idx = (k - i) < 0 ? k + MAX - i : k - i;
objects[other_idx] = buffer[k];
}
free += n;
i = (i + n) % MAX;

while (add_queue.size() > 0 && add_queue.front() <= free) {
n, cond = add_queue.dequeue();
cond.signal();
}
}

} // multibuf
</syntaxhighlight>

== Esercizio c2 ==
Un servizio di message passing sincrono senza selezione del mittente prevede una API con due funzioni:
sasend(msg_t msg, pid dest);
msg_t sarecv(void);
La funzione sarecv restituisce il primo messaggio ricevuto da qualsiasi mittente ed è bloccante se non ci sono
messaggi pendenti. la funzione sasend si blocca fino a quando il messaggio msg non viene ricevuto dal processo dest.
Dato quindi un servizio di message passing sincrono senza selezione del mittente implementare un servizio di
message passing sincrono (standard, quello definito nel corso) senza fare uso di processi server.

=== Soluzione proposta 1 (da controllare) ===
* proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 18:25, 16 January 2023 (CET)
<syntaxhighlight lang="C">

ssend(msg_t msg, pid dest) {
sasend(<msg, getpid()>, dest);
}

// variabili interne di srecv
queue<msg_t> msgs[MAX_PROC];

// suppongo non ci sia il caso in cui sender = ANY.
// nel caso ci fosse la necessità, si dovrebbe creare una altra struttura di dati
// che ordini globalmente il messaggio che sia arrivato prima.
msg_t srecv(pid sender) {
if (msgs[sender].len() > 0) {
return msgs[sender].dequeue();
}

while (true) {
<msg, pid> = sarecv();
if (pid == sender) {
return msgs[pid].dequeue();
} else {
msgs[pid].enqueue(msg);
}
}
}

</syntaxhighlight>

=== Soluzione proposta 1 (da controllare) ===

proposta da [[User:Flecart|Flecart Friend]] cedo la proprità intellettuale di questa soluzione a flecart

<syntaxhighlight lang="C">
// mem è condivisa tra ssend e srecv di ogni processo
// essendo che un processo può solo mandare o ricevere alla volta
// non abbiamo bisogno di cs

// inizializzati tutti a NULL
msg_t mem[MAXPID];
// in mem ci basta un messaggio per PID perchè un pid può aver mandato al
// massimo un messaggio essendo che sono bloccanti la send e la recive

void ssend(msg_t msg, pid dest) {
sasend(<getpid(),msg>,dest);
while(true){
<form_c,msg>=sarecv();
// dovrebbe essere ovvio che se è from c allora il msg dovrebbe essere un
// ack perchè se c avesse mandato un messaggio diverso vorrebbe dire che
// sta facendo una send e se i due processi si fanno una send allora c'è
// deadhlock
if(from_c == dest && msg == ACK){
break;
}else{
mem[from_c]=msg;
}
}
}

msg_t srecv(pid from) {
if(mem[from]==NULL){
ssend(ACK,from);
return mem.pop();
}
while(true){
<form_c,msg>=sarecv();
if(from_c==from){
ssend(ACK,from);
return msg;
}else{
mem[from_c].push(msg);
}
}
}

</syntaxhighlight>

Prove scritte 2022

2023-01-16T17:35:28Z

Gio: /* Soluzione proposta 1 */

Prove scritte 2021

2023-01-16T16:45:24Z

Gio: /* Soluzione proposta 1 */

= Prova 21/07/2021=

== Es C1 (da correggere) ==

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart friend],regalo a flecart la proprietà intellettuale di questa soluzione

<syntaxhighlight lang=C>

class node{
node parent;
sq sq1;
cond c;
}

class BinTree{
vector<node> base;
void create(int N){
base=new vector<node>(2^N);
for(int i=0;i<2^N;i++)
base[i]=new node(null,0,new cond);
for(int i=1;i<=N;i++){
for(int j=0;j<2^(N-i);j++){
get(j,i-1).parent=get(j+i,i-1).parent=new node(null,0,new cond);
}
}
}
node get(int i,int level){
return get(base[i],level);
}
node get(node n,int level){
if(level==0){
return node;
}
return get(node.parent,level-1);
}
}

class Torneo{
BinTree bin(N);
int forma[2^N];
bool win;

bool gioca(int i,int turno,int forma){
forma[i]=forma;
if null==bin.get(i,turno).sq1{
bin.get(i,turno).sq1=i;
bin.get(i,turno).c.wait();
return !win;
}else{
sq1= bin.get(i,turno).sq1;
if(forma[sq1]==forma[i]){
win=random();
}else{
win=forma[sq1]<forma[i];
}
bin.get(i,turno).signal();
}
return win;
}
}
</syntaxhighlight>

= Prova 2021/09/15 =

== Esercizio C1 ==

=== Consegna ===
Esercizio c.1: Scrivere il monitor alrv (at least rendez-vous) che fornisce una sola procedure entry:
procedure entry void at_least(int n)
Quando un processo chiama la funzione at_least vuol dire che vuole sincronizzarsi con un insieme di almeno n
processi (incluso il chiamante).
Esempi:
Se un processo chiama at_least(1) non si blocca.
Se il processo p chiama at_least(2) si blocca, se poi il processo q chiama at_least(2) oppure at_least(1) si
sbloccano sia p sia q (la richiesta di p è soddisfatta, ne aspettava almeno 2, p e q)
Se il processo p chiama at_least(2) si blocca, se poi il processo q chiama at_least(3) si blocca anch'esso perché
sebbene la richiesta di p possa essere soddisfatta, q non può ancora sbloccarsi: ci sono solo 2 processi in attesa mentre
q ne vuole 3. Un terzo processo che chiami at_least(x) con x=1,2,3 li sblocca tutti.
Hint: sia w[k ] il numero dei processi in attesa di essere in almeno k (quelli che hanno chiamato at_least(k) e non
hanno completato l'esecuzione della funzione). Sia s[n]=∑
k=1
n
w[k ] (rappresenta il numero di processi soddisfacibili:
e.g. se ci sono 4 processi in attesa, potrebbero essere soddisfatte le richieste dei processi che ne aspettano almeno 2,
almeno 3 o almeno 4). Preso, se esiste, il massimo indice m tale che s[m]≥m tutti i processi in attesa di essere in n,
per n≤m possono essere sbloccati.

=== 1. Soluzione proposta ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]

<syntaxhighlight lang=C>

extern int MAX; // il massimo numero di attesa
monitor alrv {
int w[MAX];
int s[MAX];
condition c[MAX];

init() {
for (int i = 0; i < MAX; i++) {
w[i] = s[i] = 0;
}
}

procedure entry void at_least(int n) {
if (n >= MAX || n <= 0) raise error;

int i;
for (i = n; i < MAX; i++) s[i]++;

for (i = MAX - 1; i > 0; i--) {
if (s[i] >= i) break;
}

if (i > 0) {
for (int j = 0; j <= i; j++) {
while (w[j] > 0) {
c[j].signal();
w[j]--;
}
}

s[0] = 0;
for (int i = 1; i < MAX; i++) {
s[i] = w[i] + s[i - 1];
}
} else {
w[n]++;
c[n].wait();
}
}
}
</syntaxhighlight>
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart friend],regalo a flecart la proprietà intellettuale di questa soluzione

<syntaxhighlight lang=C>

class Monitor{

min_heap<(int,cond)> h;

void at_least(int n){
int sum=0;
int max_to_sblock= -INF;
cond c = new cond(n);
h.push((n,c));
// la heap viene visitata in maniera crescente
for(auto f=h.begin_iter();null!=f.next();f++) {
sum++;
if(f.0<=sum){
max_to_sblock =f.0;
}
}
for(auto f=h.begin_iter();null!=f.next();f++) {
if(f.0<=max_to_sblock){
f.1.signal();
h.remove(c);
}
}
if(n>max_to_sblock){
c.wait();
}
free(c)
}
}

</syntaxhighlight>

= Prova 2021/06/23 =

== Esercizio C1 ==

=== Consegna ===
Esercizio c.1: Scrivere il monitor delayvalue con una sola procedure entry:
int delay(int value);
Il monitor deve sospendere i primi NDELAY processi che chiamano la delay. Le successive chiamate di delay
devono mantenere costante il numero di processi sospesi, ogni successiva chiamata devo riattivare il primo
processo in attesa prima di sospendersi, la delay ritorna il valore passato come parametro dal processo che
ne ha riattivato l'esecuzione. e.g. se NDELAY è 2:
P1: delay(44) -> P1 si sospende
P2: delay(40) -> P2 si sospende
P3: delay(42) -> P1 si riattiva e ritorna 42, P3 si sospende
P4: delay(22) -> P2 si riattiva e ritorna 22, P4 si sospende

=== Soluzione proposta 1 ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]

<syntaxhighlight lang=C>

// variabile definita altrove.
extern int NDELAY;

class Monitor {
Queue<condition> stopped;
int curr_value;
Monitor {
stopped = Queue<condition>();
curr_value = 0;
}

int delay(int value) {
curr_value = value;
if (stopped.size() == NDELAY) {
condition first = stopped.dequeue();
first.signal();
}
condition c = new condition();
stopped.enqueue(c);
c.wait();

return curr_value;
}
}

</syntaxhighlight>

=== Soluzione proposta 2 ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart friend], regalo la proprietà intellettuale a flecart.

<syntaxhighlight lang=C>

monitor dalayvalue{

#define NDELAY 22
int blocked=0;
int lastvalue=0;
cond c;

int dalay(int value){
lastvalue=value;
if(blocked<NDELAY){
blocked++;
c.wait();
}else if(blocked==NDELAY){
c.signal();
c.wait();
}
return lastvalue;
}
}

</syntaxhighlight>

== Esercizio c2 ==

=== Consegna ===

Esercizio c.2: Implementare usando semafori ordinari (fair, fifo) un servizio di semafori a priorità lifo che
fornisca le seguenti primitive:
void PLP(int prio);
void PLV()
PLP e PLV si devono comportare rispettivamente come P e V. Quando la PLV deve riattivare un processo
sceglie fra quelli in attesa quello a priorità massima, nel caso siano presenti più processi a priorità massima
sceglie quello in attesa da meno tempo.

=== Soluzione proposta 1 ===

Esercizio c2 da Flecart.

controllato:
* [[User:Gio|Gio]] ([[User talk:Gio|talk]]) 17:45, 16 January 2023 (CET)

<syntaxhighlight lang="c">

Stack<semaphore> stack[MAX_PRIORITY];
int num_V = 0;
semaphore mutex(1);

void PLP(int prio) {
mutex.P();
if (num_V > 0) {
num_V--;
mutex.V();
return;
}

semaphore sem = semaphore(0);
stack[prio].push(sem);
mutex.V();
sem.P();

mutex.V();
}

void PLV() {
mutex.P();

for (int i = MAX_PRIORITY - 1; i >= 0; i--) {
if (stack[i].size() > 0) {
sem = stack[i].pop();
sem.V();
return;
}
}

num_V++;

mutex.V();
}

</syntaxhighlight>

= Prova 2021/05/26 =

== Consegna c1 ==

Esercizio c.1: Un buffer sincrono strampalato (bss) ha due procedure entry:
void put(T value)
list of T get(void)
La entry put viene utilizzata per aggiungere un elemento e la entry get per leggere tutti quelli disponibili.
Se più processi chiamano la put quando nessun processo è in attesa per una get, rimangono tutti bloccati.
Quando successivamente un processo chiama la get riceve la lista di tutti gli elementi inseriti con le put e
tutti i processi vengono sbloccati.
Se il buffer è vuoto tutti i processi che chiamano la get rimangono bloccati. quando un processo chiama
successivamente la put tutti i processi in attesa per la get si sbloccano e ricevono lo stesso valore di ritorno:
una lista contenente il solo valore passato come parametro alla put.

=== Soluzione proposta 1 ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]
<syntaxhighlight lang="C">
int num = 0; // se è positiva rappresenta numero di gets che aspettano, se negativa, numero di puts
semaphore semput(0);
semaphore semget(0);
semaphore mutex(1);
list<T> global_list;

void put(T value) {
//< await(num > 0) --> global_list.add(value) >
mutex.P();
if (num <= 0) {
num--;
mutex.V();
semput.P();
num++;
}
global_list.add(value);

if (num < 0)
semput.V();
else
semget.V();

return;
}

list of T get() {
list<T> local_list;

mutex.P();
if (num >= 0) {
num++;
mutex.V();
semget.P();
num--;
} else {
semput.V();
semget.P();
}

local_list = global_list; // fa deep copy

if (num > 0) {
semget.V();
} else {
global_list = list<T>();
mutex.V();
}

return local_list;
}
</syntaxhighlight>

=== Soluzione proposta 2 ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Gio Gio]
<syntaxhighlight lang="C">

class bss{
int waiting_put=0;
int waiting_get=0;
cond cw,cg;
queue<T> q;

void put(T value){
q.push(T);
if(waiting_get>0){
cg.signal()
}else{
waiting_put++;
cw.wait();
waiting_put--;
}
}

list<T> get(){
if(waiting_put>0){
while(waiting_put>0){
cw.signal();
}
}else{
waiting_get++;
cg.wait();
waiting_get--;
}
list<T> p= q.tolist();
if(waiting_get>0){
cg.signal();
}
q.removeAll();
return p;
}
}
</syntaxhighlight>

== esercizio c2 ==

Dato un servizio di message passing asincrono implementare un servizio di message passing
asincrono a selezione di mittenti (samp) senza fare uso di processi server.
Il servizio samp ha due primitive:
sasend(message , destination)
sarecv(senders)
dove senders è un insieme.
la sarecv restituisce il primo messaggio che uno dei processi in senders ha spedito al processo ricevente
usando la sasend (o spedito da qualsiasi processo se senders è vuoto).

=== Soluzione proposta 1 ===

Soluzione proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 15:29, 15 January 2023 (CET)
<syntaxhighlight lang="C">
sasend(message, destination) {
pid t = getpid();
asend(<message, t>, destination);
}

// variabile privata di sarecv
queue all_messages[MAX_PROC];

// stora tutti i messaggi ricevuti, lo utilizziamo come queue per tutti, con
// anche la possibilità di rimuovere in un punto a scelta.
vector<<messages, pid>> msg;
sarecv(senders) {
if (senders.len() == 0) {
if (msg.len() == 0) {
<message, sender> = arecv(ANY);
return message;
} else {
<message, sender> = msg.pop_back();
return message;
}
} else {
do {
for (idx in senders) {
if (all_messages[idx].size() > 0) {
message = all_messages[idx].dequeue();
// rimuove il singolo messaggio dal vector, non tutti quelli uguali.
msg.remove(<message, idx>);
return message;
}
}

<message, sender> = arecv(ANY);
msg.push_back(<message, sender>);
all_messages[sender].enqueue(<message>);
} while(true);
}
}
</syntaxhighlight>

Prove scritte 2021

2023-01-16T16:45:01Z

Gio: /* Soluzione proposta 1 */

= Prova 21/07/2021=

== Es C1 (da correggere) ==

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart friend],regalo a flecart la proprietà intellettuale di questa soluzione

<syntaxhighlight lang=C>

class node{
node parent;
sq sq1;
cond c;
}

class BinTree{
vector<node> base;
void create(int N){
base=new vector<node>(2^N);
for(int i=0;i<2^N;i++)
base[i]=new node(null,0,new cond);
for(int i=1;i<=N;i++){
for(int j=0;j<2^(N-i);j++){
get(j,i-1).parent=get(j+i,i-1).parent=new node(null,0,new cond);
}
}
}
node get(int i,int level){
return get(base[i],level);
}
node get(node n,int level){
if(level==0){
return node;
}
return get(node.parent,level-1);
}
}

class Torneo{
BinTree bin(N);
int forma[2^N];
bool win;

bool gioca(int i,int turno,int forma){
forma[i]=forma;
if null==bin.get(i,turno).sq1{
bin.get(i,turno).sq1=i;
bin.get(i,turno).c.wait();
return !win;
}else{
sq1= bin.get(i,turno).sq1;
if(forma[sq1]==forma[i]){
win=random();
}else{
win=forma[sq1]<forma[i];
}
bin.get(i,turno).signal();
}
return win;
}
}
</syntaxhighlight>

= Prova 2021/09/15 =

== Esercizio C1 ==

=== Consegna ===
Esercizio c.1: Scrivere il monitor alrv (at least rendez-vous) che fornisce una sola procedure entry:
procedure entry void at_least(int n)
Quando un processo chiama la funzione at_least vuol dire che vuole sincronizzarsi con un insieme di almeno n
processi (incluso il chiamante).
Esempi:
Se un processo chiama at_least(1) non si blocca.
Se il processo p chiama at_least(2) si blocca, se poi il processo q chiama at_least(2) oppure at_least(1) si
sbloccano sia p sia q (la richiesta di p è soddisfatta, ne aspettava almeno 2, p e q)
Se il processo p chiama at_least(2) si blocca, se poi il processo q chiama at_least(3) si blocca anch'esso perché
sebbene la richiesta di p possa essere soddisfatta, q non può ancora sbloccarsi: ci sono solo 2 processi in attesa mentre
q ne vuole 3. Un terzo processo che chiami at_least(x) con x=1,2,3 li sblocca tutti.
Hint: sia w[k ] il numero dei processi in attesa di essere in almeno k (quelli che hanno chiamato at_least(k) e non
hanno completato l'esecuzione della funzione). Sia s[n]=∑
k=1
n
w[k ] (rappresenta il numero di processi soddisfacibili:
e.g. se ci sono 4 processi in attesa, potrebbero essere soddisfatte le richieste dei processi che ne aspettano almeno 2,
almeno 3 o almeno 4). Preso, se esiste, il massimo indice m tale che s[m]≥m tutti i processi in attesa di essere in n,
per n≤m possono essere sbloccati.

=== 1. Soluzione proposta ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]

<syntaxhighlight lang=C>

extern int MAX; // il massimo numero di attesa
monitor alrv {
int w[MAX];
int s[MAX];
condition c[MAX];

init() {
for (int i = 0; i < MAX; i++) {
w[i] = s[i] = 0;
}
}

procedure entry void at_least(int n) {
if (n >= MAX || n <= 0) raise error;

int i;
for (i = n; i < MAX; i++) s[i]++;

for (i = MAX - 1; i > 0; i--) {
if (s[i] >= i) break;
}

if (i > 0) {
for (int j = 0; j <= i; j++) {
while (w[j] > 0) {
c[j].signal();
w[j]--;
}
}

s[0] = 0;
for (int i = 1; i < MAX; i++) {
s[i] = w[i] + s[i - 1];
}
} else {
w[n]++;
c[n].wait();
}
}
}
</syntaxhighlight>
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart friend],regalo a flecart la proprietà intellettuale di questa soluzione

<syntaxhighlight lang=C>

class Monitor{

min_heap<(int,cond)> h;

void at_least(int n){
int sum=0;
int max_to_sblock= -INF;
cond c = new cond(n);
h.push((n,c));
// la heap viene visitata in maniera crescente
for(auto f=h.begin_iter();null!=f.next();f++) {
sum++;
if(f.0<=sum){
max_to_sblock =f.0;
}
}
for(auto f=h.begin_iter();null!=f.next();f++) {
if(f.0<=max_to_sblock){
f.1.signal();
h.remove(c);
}
}
if(n>max_to_sblock){
c.wait();
}
free(c)
}
}

</syntaxhighlight>

= Prova 2021/06/23 =

== Esercizio C1 ==

=== Consegna ===
Esercizio c.1: Scrivere il monitor delayvalue con una sola procedure entry:
int delay(int value);
Il monitor deve sospendere i primi NDELAY processi che chiamano la delay. Le successive chiamate di delay
devono mantenere costante il numero di processi sospesi, ogni successiva chiamata devo riattivare il primo
processo in attesa prima di sospendersi, la delay ritorna il valore passato come parametro dal processo che
ne ha riattivato l'esecuzione. e.g. se NDELAY è 2:
P1: delay(44) -> P1 si sospende
P2: delay(40) -> P2 si sospende
P3: delay(42) -> P1 si riattiva e ritorna 42, P3 si sospende
P4: delay(22) -> P2 si riattiva e ritorna 22, P4 si sospende

=== Soluzione proposta 1 ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]

<syntaxhighlight lang=C>

// variabile definita altrove.
extern int NDELAY;

class Monitor {
Queue<condition> stopped;
int curr_value;
Monitor {
stopped = Queue<condition>();
curr_value = 0;
}

int delay(int value) {
curr_value = value;
if (stopped.size() == NDELAY) {
condition first = stopped.dequeue();
first.signal();
}
condition c = new condition();
stopped.enqueue(c);
c.wait();

return curr_value;
}
}

</syntaxhighlight>

=== Soluzione proposta 2 ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart friend], regalo la proprietà intellettuale a flecart.

<syntaxhighlight lang=C>

monitor dalayvalue{

#define NDELAY 22
int blocked=0;
int lastvalue=0;
cond c;

int dalay(int value){
lastvalue=value;
if(blocked<NDELAY){
blocked++;
c.wait();
}else if(blocked==NDELAY){
c.signal();
c.wait();
}
return lastvalue;
}
}

</syntaxhighlight>

== Esercizio c2 ==

=== Consegna ===

Esercizio c.2: Implementare usando semafori ordinari (fair, fifo) un servizio di semafori a priorità lifo che
fornisca le seguenti primitive:
void PLP(int prio);
void PLV()
PLP e PLV si devono comportare rispettivamente come P e V. Quando la PLV deve riattivare un processo
sceglie fra quelli in attesa quello a priorità massima, nel caso siano presenti più processi a priorità massima
sceglie quello in attesa da meno tempo.

=== Soluzione proposta 1 ===

Esercizio c2 da Flecart.

controllato:
-[[User:Gio|Gio]] ([[User talk:Gio|talk]]) 17:45, 16 January 2023 (CET)

<syntaxhighlight lang="c">

Stack<semaphore> stack[MAX_PRIORITY];
int num_V = 0;
semaphore mutex(1);

void PLP(int prio) {
mutex.P();
if (num_V > 0) {
num_V--;
mutex.V();
return;
}

semaphore sem = semaphore(0);
stack[prio].push(sem);
mutex.V();
sem.P();

mutex.V();
}

void PLV() {
mutex.P();

for (int i = MAX_PRIORITY - 1; i >= 0; i--) {
if (stack[i].size() > 0) {
sem = stack[i].pop();
sem.V();
return;
}
}

num_V++;

mutex.V();
}

</syntaxhighlight>

= Prova 2021/05/26 =

== Consegna c1 ==

Esercizio c.1: Un buffer sincrono strampalato (bss) ha due procedure entry:
void put(T value)
list of T get(void)
La entry put viene utilizzata per aggiungere un elemento e la entry get per leggere tutti quelli disponibili.
Se più processi chiamano la put quando nessun processo è in attesa per una get, rimangono tutti bloccati.
Quando successivamente un processo chiama la get riceve la lista di tutti gli elementi inseriti con le put e
tutti i processi vengono sbloccati.
Se il buffer è vuoto tutti i processi che chiamano la get rimangono bloccati. quando un processo chiama
successivamente la put tutti i processi in attesa per la get si sbloccano e ricevono lo stesso valore di ritorno:
una lista contenente il solo valore passato come parametro alla put.

=== Soluzione proposta 1 ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]
<syntaxhighlight lang="C">
int num = 0; // se è positiva rappresenta numero di gets che aspettano, se negativa, numero di puts
semaphore semput(0);
semaphore semget(0);
semaphore mutex(1);
list<T> global_list;

void put(T value) {
//< await(num > 0) --> global_list.add(value) >
mutex.P();
if (num <= 0) {
num--;
mutex.V();
semput.P();
num++;
}
global_list.add(value);

if (num < 0)
semput.V();
else
semget.V();

return;
}

list of T get() {
list<T> local_list;

mutex.P();
if (num >= 0) {
num++;
mutex.V();
semget.P();
num--;
} else {
semput.V();
semget.P();
}

local_list = global_list; // fa deep copy

if (num > 0) {
semget.V();
} else {
global_list = list<T>();
mutex.V();
}

return local_list;
}
</syntaxhighlight>

=== Soluzione proposta 2 ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Gio Gio]
<syntaxhighlight lang="C">

class bss{
int waiting_put=0;
int waiting_get=0;
cond cw,cg;
queue<T> q;

void put(T value){
q.push(T);
if(waiting_get>0){
cg.signal()
}else{
waiting_put++;
cw.wait();
waiting_put--;
}
}

list<T> get(){
if(waiting_put>0){
while(waiting_put>0){
cw.signal();
}
}else{
waiting_get++;
cg.wait();
waiting_get--;
}
list<T> p= q.tolist();
if(waiting_get>0){
cg.signal();
}
q.removeAll();
return p;
}
}
</syntaxhighlight>

== esercizio c2 ==

Dato un servizio di message passing asincrono implementare un servizio di message passing
asincrono a selezione di mittenti (samp) senza fare uso di processi server.
Il servizio samp ha due primitive:
sasend(message , destination)
sarecv(senders)
dove senders è un insieme.
la sarecv restituisce il primo messaggio che uno dei processi in senders ha spedito al processo ricevente
usando la sasend (o spedito da qualsiasi processo se senders è vuoto).

=== Soluzione proposta 1 ===

Soluzione proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 15:29, 15 January 2023 (CET)
<syntaxhighlight lang="C">
sasend(message, destination) {
pid t = getpid();
asend(<message, t>, destination);
}

// variabile privata di sarecv
queue all_messages[MAX_PROC];

// stora tutti i messaggi ricevuti, lo utilizziamo come queue per tutti, con
// anche la possibilità di rimuovere in un punto a scelta.
vector<<messages, pid>> msg;
sarecv(senders) {
if (senders.len() == 0) {
if (msg.len() == 0) {
<message, sender> = arecv(ANY);
return message;
} else {
<message, sender> = msg.pop_back();
return message;
}
} else {
do {
for (idx in senders) {
if (all_messages[idx].size() > 0) {
message = all_messages[idx].dequeue();
// rimuove il singolo messaggio dal vector, non tutti quelli uguali.
msg.remove(<message, idx>);
return message;
}
}

<message, sender> = arecv(ANY);
msg.push_back(<message, sender>);
all_messages[sender].enqueue(<message>);
} while(true);
}
}
</syntaxhighlight>

Prove scritte 2021

2023-01-16T16:27:41Z

Gio: /* Esercizio C1 */

= Prova 21/07/2021=

== Es C1 (da correggere) ==

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart friend],regalo a flecart la proprietà intellettuale di questa soluzione

<syntaxhighlight lang=C>

class node{
node parent;
sq sq1;
cond c;
}

class BinTree{
vector<node> base;
void create(int N){
base=new vector<node>(2^N);
for(int i=0;i<2^N;i++)
base[i]=new node(null,0,new cond);
for(int i=1;i<=N;i++){
for(int j=0;j<2^(N-i);j++){
get(j,i-1).parent=get(j+i,i-1).parent=new node(null,0,new cond);
}
}
}
node get(int i,int level){
return get(base[i],level);
}
node get(node n,int level){
if(level==0){
return node;
}
return get(node.parent,level-1);
}
}

class Torneo{
BinTree bin(N);
int forma[2^N];
bool win;

bool gioca(int i,int turno,int forma){
forma[i]=forma;
if null==bin.get(i,turno).sq1{
bin.get(i,turno).sq1=i;
bin.get(i,turno).c.wait();
return !win;
}else{
sq1= bin.get(i,turno).sq1;
if(forma[sq1]==forma[i]){
win=random();
}else{
win=forma[sq1]<forma[i];
}
bin.get(i,turno).signal();
}
return win;
}
}
</syntaxhighlight>

= Prova 2021/09/15 =

== Esercizio C1 ==

=== Consegna ===
Esercizio c.1: Scrivere il monitor alrv (at least rendez-vous) che fornisce una sola procedure entry:
procedure entry void at_least(int n)
Quando un processo chiama la funzione at_least vuol dire che vuole sincronizzarsi con un insieme di almeno n
processi (incluso il chiamante).
Esempi:
Se un processo chiama at_least(1) non si blocca.
Se il processo p chiama at_least(2) si blocca, se poi il processo q chiama at_least(2) oppure at_least(1) si
sbloccano sia p sia q (la richiesta di p è soddisfatta, ne aspettava almeno 2, p e q)
Se il processo p chiama at_least(2) si blocca, se poi il processo q chiama at_least(3) si blocca anch'esso perché
sebbene la richiesta di p possa essere soddisfatta, q non può ancora sbloccarsi: ci sono solo 2 processi in attesa mentre
q ne vuole 3. Un terzo processo che chiami at_least(x) con x=1,2,3 li sblocca tutti.
Hint: sia w[k ] il numero dei processi in attesa di essere in almeno k (quelli che hanno chiamato at_least(k) e non
hanno completato l'esecuzione della funzione). Sia s[n]=∑
k=1
n
w[k ] (rappresenta il numero di processi soddisfacibili:
e.g. se ci sono 4 processi in attesa, potrebbero essere soddisfatte le richieste dei processi che ne aspettano almeno 2,
almeno 3 o almeno 4). Preso, se esiste, il massimo indice m tale che s[m]≥m tutti i processi in attesa di essere in n,
per n≤m possono essere sbloccati.

=== 1. Soluzione proposta ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]

<syntaxhighlight lang=C>

extern int MAX; // il massimo numero di attesa
monitor alrv {
int w[MAX];
int s[MAX];
condition c[MAX];

init() {
for (int i = 0; i < MAX; i++) {
w[i] = s[i] = 0;
}
}

procedure entry void at_least(int n) {
if (n >= MAX || n <= 0) raise error;

int i;
for (i = n; i < MAX; i++) s[i]++;

for (i = MAX - 1; i > 0; i--) {
if (s[i] >= i) break;
}

if (i > 0) {
for (int j = 0; j <= i; j++) {
while (w[j] > 0) {
c[j].signal();
w[j]--;
}
}

s[0] = 0;
for (int i = 1; i < MAX; i++) {
s[i] = w[i] + s[i - 1];
}
} else {
w[n]++;
c[n].wait();
}
}
}
</syntaxhighlight>
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart friend],regalo a flecart la proprietà intellettuale di questa soluzione

<syntaxhighlight lang=C>

class Monitor{

min_heap<(int,cond)> h;

void at_least(int n){
int sum=0;
int max_to_sblock= -INF;
cond c = new cond(n);
h.push((n,c));
// la heap viene visitata in maniera crescente
for(auto f=h.begin_iter();null!=f.next();f++) {
sum++;
if(f.0<=sum){
max_to_sblock =f.0;
}
}
for(auto f=h.begin_iter();null!=f.next();f++) {
if(f.0<=max_to_sblock){
f.1.signal();
h.remove(c);
}
}
if(n>max_to_sblock){
c.wait();
}
free(c)
}
}

</syntaxhighlight>

= Prova 2021/06/23 =

== Esercizio C1 ==

=== Consegna ===
Esercizio c.1: Scrivere il monitor delayvalue con una sola procedure entry:
int delay(int value);
Il monitor deve sospendere i primi NDELAY processi che chiamano la delay. Le successive chiamate di delay
devono mantenere costante il numero di processi sospesi, ogni successiva chiamata devo riattivare il primo
processo in attesa prima di sospendersi, la delay ritorna il valore passato come parametro dal processo che
ne ha riattivato l'esecuzione. e.g. se NDELAY è 2:
P1: delay(44) -> P1 si sospende
P2: delay(40) -> P2 si sospende
P3: delay(42) -> P1 si riattiva e ritorna 42, P3 si sospende
P4: delay(22) -> P2 si riattiva e ritorna 22, P4 si sospende

=== Soluzione proposta 1 ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]

<syntaxhighlight lang=C>

// variabile definita altrove.
extern int NDELAY;

class Monitor {
Queue<condition> stopped;
int curr_value;
Monitor {
stopped = Queue<condition>();
curr_value = 0;
}

int delay(int value) {
curr_value = value;
if (stopped.size() == NDELAY) {
condition first = stopped.dequeue();
first.signal();
}
condition c = new condition();
stopped.enqueue(c);
c.wait();

return curr_value;
}
}

</syntaxhighlight>

=== Soluzione proposta 2 ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart friend], regalo la proprietà intellettuale a flecart.

<syntaxhighlight lang=C>

monitor dalayvalue{

#define NDELAY 22
int blocked=0;
int lastvalue=0;
cond c;

int dalay(int value){
lastvalue=value;
if(blocked<NDELAY){
blocked++;
c.wait();
}else if(blocked==NDELAY){
c.signal();
c.wait();
}
return lastvalue;
}
}

</syntaxhighlight>

== Esercizio c2 ==

=== Consegna ===

Esercizio c.2: Implementare usando semafori ordinari (fair, fifo) un servizio di semafori a priorità lifo che
fornisca le seguenti primitive:
void PLP(int prio);
void PLV()
PLP e PLV si devono comportare rispettivamente come P e V. Quando la PLV deve riattivare un processo
sceglie fra quelli in attesa quello a priorità massima, nel caso siano presenti più processi a priorità massima
sceglie quello in attesa da meno tempo.

=== Soluzione proposta 1 ===

Esercizio c2 (da controllare) da Flecart.

<syntaxhighlight lang="c">

Stack<semaphore> stack[MAX_PRIORITY];
int num_V = 0;
semaphore mutex(1);

void PLP(int prio) {
mutex.P();
if (num_V > 0) {
num_V--;
mutex.V();
return;
}

semaphore sem = semaphore(0);
stack[prio].push(sem);
mutex.V();
sem.P();

mutex.V();
}

void PLV() {
mutex.P();

for (int i = MAX_PRIORITY - 1; i >= 0; i--) {
if (stack[i].size() > 0) {
sem = stack[i].pop();
sem.V();
return;
}
}

num_V++;

mutex.V();
}

</syntaxhighlight>

= Prova 2021/05/26 =

== Consegna c1 ==

Esercizio c.1: Un buffer sincrono strampalato (bss) ha due procedure entry:
void put(T value)
list of T get(void)
La entry put viene utilizzata per aggiungere un elemento e la entry get per leggere tutti quelli disponibili.
Se più processi chiamano la put quando nessun processo è in attesa per una get, rimangono tutti bloccati.
Quando successivamente un processo chiama la get riceve la lista di tutti gli elementi inseriti con le put e
tutti i processi vengono sbloccati.
Se il buffer è vuoto tutti i processi che chiamano la get rimangono bloccati. quando un processo chiama
successivamente la put tutti i processi in attesa per la get si sbloccano e ricevono lo stesso valore di ritorno:
una lista contenente il solo valore passato come parametro alla put.

=== Soluzione proposta 1 ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]
<syntaxhighlight lang="C">
int num = 0; // se è positiva rappresenta numero di gets che aspettano, se negativa, numero di puts
semaphore semput(0);
semaphore semget(0);
semaphore mutex(1);
list<T> global_list;

void put(T value) {
//< await(num > 0) --> global_list.add(value) >
mutex.P();
if (num <= 0) {
num--;
mutex.V();
semput.P();
num++;
}
global_list.add(value);

if (num < 0)
semput.V();
else
semget.V();

return;
}

list of T get() {
list<T> local_list;

mutex.P();
if (num >= 0) {
num++;
mutex.V();
semget.P();
num--;
} else {
semput.V();
semget.P();
}

local_list = global_list; // fa deep copy

if (num > 0) {
semget.V();
} else {
global_list = list<T>();
mutex.V();
}

return local_list;
}
</syntaxhighlight>

=== Soluzione proposta 2 ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Gio Gio]
<syntaxhighlight lang="C">

class bss{
int waiting_put=0;
int waiting_get=0;
cond cw,cg;
queue<T> q;

void put(T value){
q.push(T);
if(waiting_get>0){
cg.signal()
}else{
waiting_put++;
cw.wait();
waiting_put--;
}
}

list<T> get(){
if(waiting_put>0){
while(waiting_put>0){
cw.signal();
}
}else{
waiting_get++;
cg.wait();
waiting_get--;
}
list<T> p= q.tolist();
if(waiting_get>0){
cg.signal();
}
q.removeAll();
return p;
}
}
</syntaxhighlight>

== esercizio c2 ==

Dato un servizio di message passing asincrono implementare un servizio di message passing
asincrono a selezione di mittenti (samp) senza fare uso di processi server.
Il servizio samp ha due primitive:
sasend(message , destination)
sarecv(senders)
dove senders è un insieme.
la sarecv restituisce il primo messaggio che uno dei processi in senders ha spedito al processo ricevente
usando la sasend (o spedito da qualsiasi processo se senders è vuoto).

=== Soluzione proposta 1 ===

Soluzione proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 15:29, 15 January 2023 (CET)
<syntaxhighlight lang="C">
sasend(message, destination) {
pid t = getpid();
asend(<message, t>, destination);
}

// variabile privata di sarecv
queue all_messages[MAX_PROC];

// stora tutti i messaggi ricevuti, lo utilizziamo come queue per tutti, con
// anche la possibilità di rimuovere in un punto a scelta.
vector<<messages, pid>> msg;
sarecv(senders) {
if (senders.len() == 0) {
if (msg.len() == 0) {
<message, sender> = arecv(ANY);
return message;
} else {
<message, sender> = msg.pop_back();
return message;
}
} else {
do {
for (idx in senders) {
if (all_messages[idx].size() > 0) {
message = all_messages[idx].dequeue();
// rimuove il singolo messaggio dal vector, non tutti quelli uguali.
msg.remove(<message, idx>);
return message;
}
}

<message, sender> = arecv(ANY);
msg.push_back(<message, sender>);
all_messages[sender].enqueue(<message>);
} while(true);
}
}
</syntaxhighlight>

Prove scritte 2021

2023-01-16T16:27:15Z

Gio: /* Esercizio C1 */

= Prova 21/07/2021=

== Es C1 (da correggere) ==

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart friend],regalo a flecart la proprietà intellettuale di questa soluzione

<syntaxhighlight lang=C>

class node{
node parent;
sq sq1;
cond c;
}

class BinTree{
vector<node> base;
void create(int N){
base=new vector<node>(2^N);
for(int i=0;i<2^N;i++)
base[i]=new node(null,0,new cond);
for(int i=1;i<=N;i++){
for(int j=0;j<2^(N-i);j++){
get(j,i-1).parent=get(j+i,i-1).parent=new node(null,0,new cond);
}
}
}
node get(int i,int level){
return get(base[i],level);
}
node get(node n,int level){
if(level==0){
return node;
}
return get(node.parent,level-1);
}
}

class Torneo{
BinTree bin(N);
int forma[2^N];
bool win;

bool gioca(int i,int turno,int forma){
forma[i]=forma;
if null==bin.get(i,turno).sq1{
bin.get(i,turno).sq1=i;
bin.get(i,turno).c.wait();
return !win;
}else{
sq1= bin.get(i,turno).sq1;
if(forma[sq1]==forma[i]){
win=random();
}else{
win=forma[sq1]<forma[i];
}
bin.get(i,turno).signal();
}
return win;
}
}
</syntaxhighlight>

= Prova 2021/09/15 =

== Esercizio C1 ==

=== Consegna ===
Esercizio c.1: Scrivere il monitor alrv (at least rendez-vous) che fornisce una sola procedure entry:
procedure entry void at_least(int n)
Quando un processo chiama la funzione at_least vuol dire che vuole sincronizzarsi con un insieme di almeno n
processi (incluso il chiamante).
Esempi:
Se un processo chiama at_least(1) non si blocca.
Se il processo p chiama at_least(2) si blocca, se poi il processo q chiama at_least(2) oppure at_least(1) si
sbloccano sia p sia q (la richiesta di p è soddisfatta, ne aspettava almeno 2, p e q)
Se il processo p chiama at_least(2) si blocca, se poi il processo q chiama at_least(3) si blocca anch'esso perché
sebbene la richiesta di p possa essere soddisfatta, q non può ancora sbloccarsi: ci sono solo 2 processi in attesa mentre
q ne vuole 3. Un terzo processo che chiami at_least(x) con x=1,2,3 li sblocca tutti.
Hint: sia w[k ] il numero dei processi in attesa di essere in almeno k (quelli che hanno chiamato at_least(k) e non
hanno completato l'esecuzione della funzione). Sia s[n]=∑
k=1
n
w[k ] (rappresenta il numero di processi soddisfacibili:
e.g. se ci sono 4 processi in attesa, potrebbero essere soddisfatte le richieste dei processi che ne aspettano almeno 2,
almeno 3 o almeno 4). Preso, se esiste, il massimo indice m tale che s[m]≥m tutti i processi in attesa di essere in n,
per n≤m possono essere sbloccati.

=== 1. Soluzione proposta ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]

<syntaxhighlight lang=C>

extern int MAX; // il massimo numero di attesa
monitor alrv {
int w[MAX];
int s[MAX];
condition c[MAX];

init() {
for (int i = 0; i < MAX; i++) {
w[i] = s[i] = 0;
}
}

procedure entry void at_least(int n) {
if (n >= MAX || n <= 0) raise error;

int i;
for (i = n; i < MAX; i++) s[i]++;

for (i = MAX - 1; i > 0; i--) {
if (s[i] >= i) break;
}

if (i > 0) {
for (int j = 0; j <= i; j++) {
while (w[j] > 0) {
c[j].signal();
w[j]--;
}
}

s[0] = 0;
for (int i = 1; i < MAX; i++) {
s[i] = w[i] + s[i - 1];
}
} else {
w[n]++;
c[n].wait();
}
}
}
</syntaxhighlight>
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart friend],regalo a flecart la proprietà intellettuale di questa soluzione

<syntaxhighlight lang=C>

class Monitor{

min_heap<(int,cond)> h;

void at_least(int n){
int sum=0;
int max_to_sblock= -INF;
cond c = new cond(n);
h.push((n,c));
// la heap viene visitata in maniera crescente
for(auto f=h.begin_iter();null!=f.next();f++) {
sum++;
if(f.0<=sum){
max_to_sblock =f.0;
}
}
for(auto f=h.begin_iter();null!=f.next();f++) {
if(f.0<=max_to_sblock){
f.1.signal();
h.remove(c);
}
}
if(n>max_to_sblock){
c.wait();
}
free(c)
}
}

</syntaxhighlight>

= Prova 2021/06/23 =

== Esercizio C1 ==

=== Consegna ===
Esercizio c.1: Scrivere il monitor delayvalue con una sola procedure entry:
int delay(int value);
Il monitor deve sospendere i primi NDELAY processi che chiamano la delay. Le successive chiamate di delay
devono mantenere costante il numero di processi sospesi, ogni successiva chiamata devo riattivare il primo
processo in attesa prima di sospendersi, la delay ritorna il valore passato come parametro dal processo che
ne ha riattivato l'esecuzione. e.g. se NDELAY è 2:
P1: delay(44) -> P1 si sospende
P2: delay(40) -> P2 si sospende
P3: delay(42) -> P1 si riattiva e ritorna 42, P3 si sospende
P4: delay(22) -> P2 si riattiva e ritorna 22, P4 si sospende

=== Soluzione proposta 1 ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart], da controllare

<syntaxhighlight lang=C>

// variabile definita altrove.
extern int NDELAY;

class Monitor {
Queue<condition> stopped;
int curr_value;
Monitor {
stopped = Queue<condition>();
curr_value = 0;
}

int delay(int value) {
curr_value = value;
if (stopped.size() == NDELAY) {
condition first = stopped.dequeue();
first.signal();
}
condition c = new condition();
stopped.enqueue(c);
c.wait();

return curr_value;
}
}

</syntaxhighlight>

=== Soluzione proposta 1 ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart friend], regalo la proprietà intellettuale a flecart.

<syntaxhighlight lang=C>

monitor dalayvalue{

#define NDELAY 22
int blocked=0;
int lastvalue=0;
cond c;

int dalay(int value){
lastvalue=value;
if(blocked<NDELAY){
blocked++;
c.wait();
}else if(blocked==NDELAY){
c.signal();
c.wait();
}
return lastvalue;
}
}

</syntaxhighlight>

== Esercizio c2 ==

=== Consegna ===

Esercizio c.2: Implementare usando semafori ordinari (fair, fifo) un servizio di semafori a priorità lifo che
fornisca le seguenti primitive:
void PLP(int prio);
void PLV()
PLP e PLV si devono comportare rispettivamente come P e V. Quando la PLV deve riattivare un processo
sceglie fra quelli in attesa quello a priorità massima, nel caso siano presenti più processi a priorità massima
sceglie quello in attesa da meno tempo.

=== Soluzione proposta 1 ===

Esercizio c2 (da controllare) da Flecart.

<syntaxhighlight lang="c">

Stack<semaphore> stack[MAX_PRIORITY];
int num_V = 0;
semaphore mutex(1);

void PLP(int prio) {
mutex.P();
if (num_V > 0) {
num_V--;
mutex.V();
return;
}

semaphore sem = semaphore(0);
stack[prio].push(sem);
mutex.V();
sem.P();

mutex.V();
}

void PLV() {
mutex.P();

for (int i = MAX_PRIORITY - 1; i >= 0; i--) {
if (stack[i].size() > 0) {
sem = stack[i].pop();
sem.V();
return;
}
}

num_V++;

mutex.V();
}

</syntaxhighlight>

= Prova 2021/05/26 =

== Consegna c1 ==

Esercizio c.1: Un buffer sincrono strampalato (bss) ha due procedure entry:
void put(T value)
list of T get(void)
La entry put viene utilizzata per aggiungere un elemento e la entry get per leggere tutti quelli disponibili.
Se più processi chiamano la put quando nessun processo è in attesa per una get, rimangono tutti bloccati.
Quando successivamente un processo chiama la get riceve la lista di tutti gli elementi inseriti con le put e
tutti i processi vengono sbloccati.
Se il buffer è vuoto tutti i processi che chiamano la get rimangono bloccati. quando un processo chiama
successivamente la put tutti i processi in attesa per la get si sbloccano e ricevono lo stesso valore di ritorno:
una lista contenente il solo valore passato come parametro alla put.

=== Soluzione proposta 1 ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]
<syntaxhighlight lang="C">
int num = 0; // se è positiva rappresenta numero di gets che aspettano, se negativa, numero di puts
semaphore semput(0);
semaphore semget(0);
semaphore mutex(1);
list<T> global_list;

void put(T value) {
//< await(num > 0) --> global_list.add(value) >
mutex.P();
if (num <= 0) {
num--;
mutex.V();
semput.P();
num++;
}
global_list.add(value);

if (num < 0)
semput.V();
else
semget.V();

return;
}

list of T get() {
list<T> local_list;

mutex.P();
if (num >= 0) {
num++;
mutex.V();
semget.P();
num--;
} else {
semput.V();
semget.P();
}

local_list = global_list; // fa deep copy

if (num > 0) {
semget.V();
} else {
global_list = list<T>();
mutex.V();
}

return local_list;
}
</syntaxhighlight>

=== Soluzione proposta 2 ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Gio Gio]
<syntaxhighlight lang="C">

class bss{
int waiting_put=0;
int waiting_get=0;
cond cw,cg;
queue<T> q;

void put(T value){
q.push(T);
if(waiting_get>0){
cg.signal()
}else{
waiting_put++;
cw.wait();
waiting_put--;
}
}

list<T> get(){
if(waiting_put>0){
while(waiting_put>0){
cw.signal();
}
}else{
waiting_get++;
cg.wait();
waiting_get--;
}
list<T> p= q.tolist();
if(waiting_get>0){
cg.signal();
}
q.removeAll();
return p;
}
}
</syntaxhighlight>

== esercizio c2 ==

Dato un servizio di message passing asincrono implementare un servizio di message passing
asincrono a selezione di mittenti (samp) senza fare uso di processi server.
Il servizio samp ha due primitive:
sasend(message , destination)
sarecv(senders)
dove senders è un insieme.
la sarecv restituisce il primo messaggio che uno dei processi in senders ha spedito al processo ricevente
usando la sasend (o spedito da qualsiasi processo se senders è vuoto).

=== Soluzione proposta 1 ===

Soluzione proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 15:29, 15 January 2023 (CET)
<syntaxhighlight lang="C">
sasend(message, destination) {
pid t = getpid();
asend(<message, t>, destination);
}

// variabile privata di sarecv
queue all_messages[MAX_PROC];

// stora tutti i messaggi ricevuti, lo utilizziamo come queue per tutti, con
// anche la possibilità di rimuovere in un punto a scelta.
vector<<messages, pid>> msg;
sarecv(senders) {
if (senders.len() == 0) {
if (msg.len() == 0) {
<message, sender> = arecv(ANY);
return message;
} else {
<message, sender> = msg.pop_back();
return message;
}
} else {
do {
for (idx in senders) {
if (all_messages[idx].size() > 0) {
message = all_messages[idx].dequeue();
// rimuove il singolo messaggio dal vector, non tutti quelli uguali.
msg.remove(<message, idx>);
return message;
}
}

<message, sender> = arecv(ANY);
msg.push_back(<message, sender>);
all_messages[sender].enqueue(<message>);
} while(true);
}
}
</syntaxhighlight>

Prove scritte 2020

2023-01-16T13:43:03Z

Gio: /* Prova 2020/01/15 */

= Prova 2020/01/15 =

== esercizio c1 ==

=== Soluzione proposta 1 ===
<syntaxhighlight lang="C">
class TS{

int v=0;
queue<(unsigned int,cond)> pq;
usinged int timer;

void V(){
if(pq.empty()){
v++;
}else{
pq.pop().signal();
}
}
bool P(unsigned int timeout){
if(v == 0){
cond c = new condition();
pq.push((timeout+timer,));
c.wait();
free(c);
if timer== timeout+timer{
return true;
}
}else{
v--;
}
return false;
}

void tick(){
timer++;
for [i,c] in pq.iter(){
if( i <= timer) {
c.signal();
// la nostra stuttura dati supporta la rimozione durante lo scorrimento
// per esempio può essere una lista
pq.remove(c);
}
}
}
}

</syntaxhighlight>

=== Soluzione proposta 2 ===

<syntaxhighlight lang="C">

int value;
boolean ret_val;
int time;
min_heap<int, condition> heap; // ordinato sul tempo minore.
vector<condition> queue; // vector utilizzato come queue, con rimozione anche nel mezzo.

monitor {
value = 0;
time = 0;
}

void V(void) {
if (heap.size() > 0) {
condition c = queue.pop_back(); // remove and return
heap.remove(c); // rimuovi l'unico elemento con c.
ret_val = true;
c.signal();
} else {
value++;
}
}

boolean P(unsigned int timeout) {
if (value > 0) {
value--;
return true;
} else {
int next_time = timeout + time;
condition c = new condition();
heap.insert(<next_time, c>);
queue.push_back(c);
c.wait();
free(c);

return ret_val;
}
}

void tick(void) {
ret_val = false;
time++;
while (heap.size() > 0 && heap.top().0 <= time) {
condition c = heap.top().1;
heap.deleteTop();
queue.remove(c);
c.signal();
}
}

</syntaxhighlight>

== esercizio c2 ==

=== Soluzione proposta 1 (da controllare)===

[[User:Gio|Gio]] ([[User talk:Gio|talk]]) 14:43, 16 January 2023 (CET)

<syntaxhighlight lang="C">

void multisend(pid_t destination,T msg,int times){
for(int i=0;i<n;i++){
asend(<n-i,getpid(),msg>,destination);
ack=arecv(destination)
}
}
T multirecv(pid_t sender){
int i;
if(sender==ANY){
//assegna il pid preso da a recv a sender
<i, sender, msg>=arecv(ANY);
}else{
<i, sender, msg>=arecv(sender);
}
asend(ack,sender);
i--;
while(i>0)
<j, sender, msg>=arecv(sender);
asend(ack,sender);
i--;
assert(i==j);
}
return msg;
}
</syntaxhighlight>

= Prova 2020/02/20 =

== esercizio c2 ==

Sol : x alla seconda

Prove scritte 2019

2023-01-16T13:10:55Z

Gio: /* Esercizio c.2 */

== Esame 18/06/2019 ==
[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">
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;

}

}
</source>
 

=== Esercizio c.1 (da controllare) ===
<source lang="c">
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;
}
</source>
 

=== Esercizio c.2 ===
**non è l'esercizio corretto**
<source lang="c">
/* 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;
}
</source>
 
Soluzione:
<source lang="c">
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
</source>
 

=== Esercizio g.1 (sbagliato) ===
<nowiki>
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|
</nowiki>
 

=== Esercizio g.1 ===
<nowiki>
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
</nowiki>
 

=== 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 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2019.05.18.tot.pdf 2019.05.18.tot.pdf]

=== Esercizio c.1 (da controllare) ===

* Controllato dall'utente ? in data ?
* ...

Il sorgente seguente può essere eseguito scaricando in una stessa directory il package [[Tool per semafori e monitor|pysm]] del prof. Davoli.

<source lang="python">
#!/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())
</source>

=== Esercizio c.2 (da controllare) ===
<source lang="c">
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();
}
}

</source>

=== 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.

[[File:Epson 25082020151034.jpg]]

=== 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 ==
[https://www.cs.unibo.it/~renzo/so/compiti/2019.02.14.tot.pdf Testo d'esame].

=== Esercizio c.1 (da controllare) ===

* Controllato dall'utente [[User:Acsor|Acsor]] ([[User talk:Acsor|talk]]) in data 16:03, 2 September 2020 (CEST). Ritengo sia: corretto
* Controllato dall'utente ? in data ?

<source lang="python">
# 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()
</source>

=== Esercizio c.2 (controllato) ===

<source lang="python">
# 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
</source>

== Esame 28/05/2019 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2019.05.18.tot.pdf 2019.05.18.tot.pdf]

=== Esercizio c.1 (da controllare) ===
<source lang="c">

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()

</source>

 

=== Esercizio c.1 (da controllare) ===
<source lang="c">
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—;

}
}
</source>

== Esame 15/07/2019 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2019.07.15.tot.pdf 2019.07.15.tot.pdf]
=== Esercizio c.1 ===

# Verifica del 18/05/2020 dell'utente [[User:Acsor|Acsor]]. Ritengo sia: corretto
# Verifica del ... dell'utente ... . Ritengo sia: ...
# ...

Una semplice realizzazione in Python dello pseudocodice seguente è disponibile [https://github.com/pollomarzo/rdso1920/tree/master/2019exams/samepc qui].

<source lang="python">
# 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;
</source>

=== 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; [http://www.treccani.it/magazine/lingua_italiana/domande_e_risposte/grammatica/grammatica_030.html 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: [https://www.cs.unibo.it/~renzo/so/compiti/2019.09.13.tot.pdf 2019.09.13.tot.pdf].

=== Esercizio c.1 (controllato) ===
* Controllato dal professor Davoli durante la lezione del 19/05/2020.
* Controllato dall'utente [[User:Acsor|Acsor]] ([[User talk:Acsor|talk]]) in data 19:13, 1 September 2020 (CEST).

<source lang="python">
# 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
</source>

=== Esercizio c.2 (da controllare) ===

* Controllato dall'utente ? in data ?
* ...

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

<source lang="c">
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();
}
</source>

=== 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.)

[[File:2019-09-13-g1.jpg | 768px]]

=== 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).

Prove scritte 2022

2023-01-15T10:49:36Z

Gio: /* Soluzione proposta (da controllare) */

= Prova 2022/09/06 =

== Esercizio c1 ==

Esercizio c.1: I bit di un numero intero rappresentano condizioni di un sistema. Se lo stato attuale è 6 (0110) vuole dire
che attualmente sono vere le condizioni 2 (0010) e 4 (0100).
Scrivere un monitor bitcond che fornisca le seguenti procedure entry:
void set(int bit2set); accende nello stato attuale i bit di bit2set
void unset(int bit2unset) spegne nello stato attuale i bit di bit2unset
void statuswait(int bit2wait) attende che lo stato attuale soddisfi tutti le condizioni indicate in bit2wait (cioè
che tutti i bit in bit2wait siano accesi nello stato attuale).
Le richieste statuswait devono essere servite in ordine FIFO (cioè un processo anche se sono presenti tutte le
condizioni necessarie deve attendere se un processo che ha chiamato statuswait prima è in attesa).
Lo stato iniziale è zero (nessuna risorsa disponibile)

=== Soluzione proposta 1 ===
<syntaxhighlight lang=C>

class bitcond{
int bitmap;
int lastBitmask;
int has=0;

condition waiting;
condition c;

void set(int i){
bitmap|=i;
if(bitmap&lastBitmask == bitmap) c.signal();
}
void unset(int i){
bitmap&=~i;
}
void statuswait(int i){
has++;
if(has>1){
waiting.wait();
}

if(!(bitmap&i==i)){
lastBitmask=i;
c.wait();
}

waiting.signal();
has--;
}
bitcond(){
bitmap = 0;
}
}

</syntaxhighlight>

=== Soluzione proposta 2 ===
Proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 12:06, 14 January 2023 (CET)
<syntaxhighlight lang=C>

const int int_size = 32;

class monitor {
int value;
condition bitset[int_size];

int numstatuswaiting;
condition waiting;

monitor() {
value = 0;
}

/// guarda se il bit n-significativo è settato in from
bool nbit(int from, int n) {
return (from & (1 << n)) != 0
}

void entry set(int bit2set) {
value |= bit2set;

for (int i = 0; i < 32; i++) {
if (nbit(value, i))
bitset[i].signal();
}
}

void entry statuswait(int bit2wait) {
// in questo modo solamente un singolo processo è dentro ad aspettare
// che tutte le condizioni siano rispettate
if (numstatuswaiting > 0)
waiting.wait();

numstatuswaiting++;
int i = 0;
while(i < 32) {
if (nbit(bit2wait, i) && !nbit(value, i)) {
bitset[i].wait();

// ricomincia a guardare tutti i bit da zero, perché
// nel frattempo potrebbero essere cambiati.
// -1 così con l'istruzione successiva diventa 0
i = -1;
}
i++;
}

numstatuswaiting--;
waiting.signal();
}
}

</syntaxhighlight>

=== Soluzione proposta 3 ===
Proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 12:07, 14 January 2023 (CET)
questa è la soluzione più brutta, ma dovrebbe andare.
<syntaxhighlight lang=C>

const int int_size = 32;

class monitor {
int value;
condition status;

int numstatuswaiting;
condition waiting;

monitor() {
value = 0;
}

/// guarda se il bit n-significativo è settato in from
bool nbit(int from, int n) {
return (from & (1 << n)) != 0
}

void entry set(int bit2set) {
value |= bit2set;
status.signal();
}

void entry unset(int bit2unset) {
value = (value & ~bit2unset);
}

void entry statuswait(int bit2wait) {
// in questo modo solamente un singolo processo è dentro ad aspettare
// che tutte le condizioni siano rispettate
if (numstatuswaiting > 0)
waiting.wait();

numstatuswaiting++;
while(true) {
if ((value & bit2wait) == bit2wait)
break;
else
status.wait();
}
numstatuswaiting--;
waiting.signal();
}
}
</syntaxhighlight>

= Prova 2022/06/21 =

== Esercizio c1 ==
Scrivere il monitor collocamento:
void cercolavoro(char *nome, char *skill)
void char *assumo(char * skill)
Quando un processo chiama la cercolavoro si mette in attesa di una richiesta di lavoro e rimane bloccato nel monitor
fino a che non è stato assunto. Nella cercolavoro viene indicato il nome dell'aspirante lavoratore la sua capacità (skill).
Un datore di lavoro con necessità di personale chiama la assumo specificando la capacità richiesta. Se c'è in attesa
almeno un aspirante lavoratore con quella specifica capacità (uguale valore di skill), il datore di lavoro riceve il nome del
nuovo dipendente ed entrambi i processi escono dal monitor. Nel caso non ci siano richieste compatibili il datore di
lavoro si blocca nel monitor attendendo un lavoratore con la capacità cercata. Quando arriva il lavoratore che soddisfa
le richieste si sbloccano entrambi i processi lavoratore e datore di lavoro. La assumo restituisce in ogni caso il nome del
dipendente da assumere.

=== Soluzione proposta ===

Soluzione proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 12:08, 14 January 2023 (CET)

ci potrebbe essere un errore in quanto non è specificato il comportamento della struttura dati in alcune situazioni

<syntaxhighlight lang=C>

class collocamento{

set<char *, condition> richieste; // chi assume cerca questa skill
set<char *, char *, condition> ricerche; // nome e skill di chi cerca

char *last_nome;

collocamento {
last_nome = NULL;
richieste = set();
ricerche = set();
}

void cercolavoro(char *nome, char *skill) {
datore = richieste.find(skill); // cerca valutando la prima come chiave
if (datore != NULL) {
<skill, cond> = datore;
richieste.remove(datore);
last_nome = nome;
cond.signal();
} else {
condition c = new condition();
ricerche.insert(nome, skill, c);
c.wait();
free(c);
}
}

void char *assumo(char * skill){
lavoratore = ricerche.find2(skill); // cerca valutando la seconda come chiave.
if (lavoratore != NULL) {
<nome, skill, cond> = lavoratore;
ricerche.remove(lavoratore);
cond.signal();
last_nome = nome;
} else {
condition c = new condition();
richieste.insert(skill, c);
c.wait();
free(c);
}

return last_nome;
}

}// class collocamento
</syntaxhighlight>

=== Soluzione proposta ===

Soluzione proposta da [[User:Flecart|Flecart Frend]], regalo la proprietà intellettuale di questa soluzione a flecart.

<syntaxhighlight lang=C>
class workdisptcher{

// la multi map può storare più di un valore per una chiave
// quando viene richiesta una particolare chiave da in maniera LIFO
// il risultato
// es:
// multi_map<char *,int> lavoratori;
// lavoratori.insert("prova",2);
// lavoratori.insert("prova",1);
// lavoratori.get("prova") == 2
// lavoratori.remove("prova")
// lavoratori.get("prova") == 1
multi_map<char *,(char*,cond)> lavoratori;
multi_map<char *,cond> posti_aperti;
char* buffer_name;
void cercolavoro(char *nome, char *skill){
if(posti_aperti.find(skill)){
auto entry =posti_aperti.get(skill);
posti_aperti.remove(entry);
buffer_name=name;
entry.1.signal();
}else{
cond c= new cond();
lavoratori.insert(skill,(nome,c)) ;
c.wait();
free(c);
}
}
void char *assumo(char * skill){
if(lavoratori.find(skill)){
auto entry =lavoratori.get(skill);
posti_aperti.remove(entry);
auto [nome,cnd] = entry.1;
cond.signal();
return nome;
}else{
cond c= new cond();
posti_aperti.insert(skill,c) ;
c.wait();
free(c);
return buffer_name;
}

}

}

</syntaxhighlight>

== Esercizio c2 ==
Un servizio viene fornito in modalità client-server usando message passing asincrono.
Al fine di aumentare l'efficienza si decide di usare molti server e un processo dispatcher in grado di distribuire le
richieste agli N server. Quando un processo server è libero riceve dal dispatcher la prossima richiesta da elaborare:
codice di ogni client (tanti!): .....
asend(<getpid(), request>, dispatcher)
result = arecv(dispatcher)

server process[i], i = 0, ..., N-1:
request = arecv(dispatcher)
result = compute(request)
asend(<getpid(), result>, dispatcher)
Scrivere il processo dispatcher. (il dispatcher conosce i pid di tutti i server).

=== Soluzione proposta (sbagliata) ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]

Questo esercizio è stato corretto tempo fa in classe dal professore, **non è completamente corretto** se si vuole provare a correggerlo alla fine dell'esercizio c'è scritto cos'è sbagliato.

<syntaxhighlight lang=C>

extern int N;
process dispatcher() {
// indice che tiene conto a quale server dover mandare
// per semplicità supponiamo che i server abbiano PID
// da 0 a N - 1
int i = 0;

// mappa server a pid del processo che lo ha richiesto.
// chiave: pid del server
// value: queue richiesta dispatchata al server in chiave
map<int, queue<int>> mapper;
while (true) {
res = arecv(ANY);

// in questa parte l'importante è sapere
// se la richiesta proviene dal server o da un altro
// processo, ho assunto che la disambiguazione
// fosse immediata, un altro modo per checkare questo
// è vedere se il PID del messaggio rientri fra quelli
// noti al dispatcher.
if (<pid, request> = res) {
mapper[i].enqueue(pid);
asend(request, i /*il i-esimo server*/);
i++;
i %= N;
} else if (<pid, response> = res) {
requester_pid = mapper[pid].dequeue();
asend(response, requester_pid);
}
}
}
</syntaxhighlight>

l'es è sbagliato perchè dovrei mandare ai server liberi, non a round-robin [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 15:52, 14 January 2023 (CET)

=== Soluzione proposta 2 ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart frend] che cede a flecart la proprietà intellettuale di questa soluzione

<syntaxhighlight lang=C>
dispatcher{
queue<<pid,request>> work;
queue<pid> freeserver;
map<pid,pid> map_server_to_client;
while(true){
<pid,message>=arecv(ANY);
if pid in servers{
client=map_server_to_client.get(pid);
map_client_to_server.remove(pid);
freeserver.push(pid);
asend(<message>,client);
}else{
work.push(<pid,message>);
}
while !freeserver.empty() and !work.emtpy(){
server_pid = freeserver.pop();
<client,msg> = work.pop();
map_server_to_client.insert(server,client);
asend(msg,server_pid);
}
}
}
</syntaxhighlight>

= Prova 2022/06/01 =

== Esercizio c1 ==

Scrivere il monitor delay che fornisce due procedure entry:
int wait_tick(int nticks)
void tick(void)
La procedure entry tick è pensata per essere richiamata periodicamente (es. ogni secondo o ora o giorno) da un
processo.
Quando un processo chiama la wait_tick deve attendere un numero di chiamate della tick pari al parametro nticks.
Per esempio se un processo chiama wait_tick(2) deve fermarsi e verrà riattivato alla seconda successiva chiamata di
tick.
La funzione wait_tick ha come valore di ritorno il numero di processi che erano bloccati al momento della tick che ha
sbloccato il chiamante.
Esempio: P chiama wait_tick(2) e si blocca. Q chiama wait_tick(3) e si blocca. T chiama tick() non succede nulla. R
chiama wait_tick(2) e si blocca. T chiama tick(), viene sbloccata la wait_tick di P e il valore ritornato è 3. T chiama
tick(), vengono sbloccate le wait_tick di Q e R e il valore ritornato per entrambi i processi è 2

=== Soluzione proprosta 1 (da controllare) ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]

<syntaxhighlight lang=C>

class MonitorDelay {
int curr_time;
int waiting_num;

// min heap con il tempo di sblocco dei processi e la condizione su cui è fermato
// il tempo di sblocco minore è messo in cima alla heap
// la sintassi con pair è ispirata alla std::pair di c++
heap<pair<int, condition>> waiting;

void init() {
curr_time = 0;
waiting = heap<pair<int, condition>>();
}

int entry wait_tick(int nticks) {
if (nticks <= 0) {
return waiting.size();
} else {
condition c = new condition();
waiting.insert(make_pair(nticks + curr_time, c));
c.wait();
free(c);
}
return waiting_num;
}

void entry tick(void) {
waiting_num = waiting.size();
curr_time++;

while (waiting.head().first <= curr_time) {
condition c = waiting.head().second;
waiting.deleteHead();
c.signal();
}
}
}
</syntaxhighlight>

== Esercizio c2 ==

=== Consegna ===

Esercizio c.2: Un servizio di message passing asincrono non fifo (nfasend/nfarecv) consegna in tempo finito tutti i
messaggi spediti ma non è garantito che i messaggi vengano ricevuti nell'ordine nel quale sono stati spediti.
void nfasend(msg_t msg, pid_t dest)
msg_t nfarecv(pid_t sender)
Dato un servizio di message passing asincrono non fifo scrivere una libreria che implementi il servizio di message
passing asincrono fifo:
void asend(msg_t msg, pid_t dest)
msg_t arecv(pid_t sender)
Nota: sia il servizio dato (non fifo) sia quello da implementare (fifo) consentono la ricezione solo da mittente specificato
(non supportano ANY/*).

=== Soluzione proposta 1 ===

<syntaxhighlight lang="C">

void nfasend(msg_t msg, pid_t dest);
msg_t nfarecv(pid_t sender);

// array di grandezza di massimi numero di processi, inizializzato a 0
// utilizzato per contare il numero di messaggi inviati a un certo processo.
int num_sender[MAX_PROC];

//RICORDA che ogni sender ha il suo num_sender[...]

void asend(msg_t msg, pid_t dest) {
src = getpid();
nfasend(<msg, num_send[dest]>, dest);
num_sender[dest]++;
}

// molto simile a num_sender, ma è utilizzato per contare il numero di messaggi ricevuti, in ordine.
int num_receiver[MAX_PROC];
// array heap ordinato sul int (per ogni heap in cima c'è il messaggio col minimo int).
min_heap<msg, int> messages[MAX_PROC];

//RICORDA che ogni receiver ha il suo proprio num_receiver[...] e messages[...]

msg_t arecv(pid_t sender) {
p = getpid();

if (messages[sender].size() > 0 && messages[sender].top() == num_receiver[sender]) {
(msg, num_mess) = messages[sender].removeTop();
num_receiver[sender]++;
return msg;
}

(msg, num_mess) = nfarecv(sender);

while (num_mess != num_receiver[sender]) {
messages[sender].insert(msg, num_mess);
(msg, num_mess) = nfarecv(sender);
}

num_receiver[sender]++;
return msg;
}

</syntaxhighlight>

User talk:Gio

2023-01-14T20:07:45Z

Gio:

Pls don't talk to me.

User talk:Gio

2023-01-14T20:07:27Z

Gio: Pls, don't talk to me

Prove scritte 2021

2023-01-14T16:20:16Z

Gio: /* Es C1 (da correggere) */

= Prova 21/07/2021=

== Es C1 (da correggere) ==

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart friend],regalo a flecart la proprietà intellettuale di questa soluzione

<syntaxhighlight lang=C>

class node{
node parent;
sq sq1;
cond c;
}

class BinTree{
vector<node> base;
void create(int N){
base=new vector<node>(2^N);
for(int i=0;i<2^N;i++)
base[i]=new node(null,0,new cond);
for(int i=1;i<=N;i++){
for(int j=0;j<2^(N-i);j++){
get(j,i-1).parent=get(j+i,i-1).parent=new node(null,0,new cond);
}
}
}
node get(int i,int level){
return get(base[i],level);
}
node get(node n,int level){
if(level==0){
return node;
}
return get(node.parent,level-1);
}
}

class Torneo{
BinTree bin(N);
int forma[2^N];
bool win;

bool gioca(int i,int turno,int forma){
forma[i]=forma;
if null==bin.get(i,turno).sq1{
bin.get(i,turno).sq1=i;
bin.get(i,turno).c.wait();
return !win;
}else{
sq1= bin.get(i,turno).sq1;
if(forma[sq1]==forma[i]){
win=random();
}else{
win=forma[sq1]<forma[i];
}
bin.get(i,turno).signal();
}
return win;
}
}
</syntaxhighlight>

= Prova 2021/09/15 =

== Esercizio C1 ==

=== Consegna ===
Esercizio c.1: Scrivere il monitor alrv (at least rendez-vous) che fornisce una sola procedure entry:
procedure entry void at_least(int n)
Quando un processo chiama la funzione at_least vuol dire che vuole sincronizzarsi con un insieme di almeno n
processi (incluso il chiamante).
Esempi:
Se un processo chiama at_least(1) non si blocca.
Se il processo p chiama at_least(2) si blocca, se poi il processo q chiama at_least(2) oppure at_least(1) si
sbloccano sia p sia q (la richiesta di p è soddisfatta, ne aspettava almeno 2, p e q)
Se il processo p chiama at_least(2) si blocca, se poi il processo q chiama at_least(3) si blocca anch'esso perché
sebbene la richiesta di p possa essere soddisfatta, q non può ancora sbloccarsi: ci sono solo 2 processi in attesa mentre
q ne vuole 3. Un terzo processo che chiami at_least(x) con x=1,2,3 li sblocca tutti.
Hint: sia w[k ] il numero dei processi in attesa di essere in almeno k (quelli che hanno chiamato at_least(k) e non
hanno completato l'esecuzione della funzione). Sia s[n]=∑
k=1
n
w[k ] (rappresenta il numero di processi soddisfacibili:
e.g. se ci sono 4 processi in attesa, potrebbero essere soddisfatte le richieste dei processi che ne aspettano almeno 2,
almeno 3 o almeno 4). Preso, se esiste, il massimo indice m tale che s[m]≥m tutti i processi in attesa di essere in n,
per n≤m possono essere sbloccati.

=== 1. Soluzione proposta ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]

<syntaxhighlight lang=C>

extern int MAX; // il massimo numero di attesa
monitor alrv {
int w[MAX];
int s[MAX];
condition c[MAX];

init() {
for (int i = 0; i < MAX; i++) {
w[i] = s[i] = 0;
}
}

procedure entry void at_least(int n) {
if (n >= MAX || n <= 0) raise error;

int i;
for (i = n; i < MAX; i++) s[i]++;

for (i = MAX - 1; i > 0; i--) {
if (s[i] >= i) break;
}

if (i > 0) {
for (int j = 0; j <= i; j++) {
while (w[j] > 0) {
c[j].signal();
w[j]--;
}
}

s[0] = 0;
for (int i = 1; i < MAX; i++) {
s[i] = w[i] + s[i - 1];
}
} else {
w[n]++;
c[n].wait();
}
}
}
</syntaxhighlight>
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart friend],regalo a flecart la proprietà intellettuale di questa soluzione

<syntaxhighlight lang=C>

class Monitor{

min_heap<(int,cond)> h;

void at_least(int n){
int sum=0;
int max_to_sblock= -INF;
cond c = new cond(n);
h.push((n,c));
// la heap viene visitata in maniera crescente
for(auto f=h.begin_iter();null!=f.next();f++) {
sum++;
if(f.0<=sum){
max_to_sblock =f.0;
}
}
for(auto f=h.begin_iter();null!=f.next();f++) {
if(f.0<=max_to_sblock){
f.1.signal();
h.remove(c);
}
}
if(n>max_to_sblock){
c.wait();
}
free(c)
}
}

</syntaxhighlight>

= Prova 2021/06/23 =

== Esercizio C1 ==

=== Consegna ===
Esercizio c.1: Scrivere il monitor delayvalue con una sola procedure entry:
int delay(int value);
Il monitor deve sospendere i primi NDELAY processi che chiamano la delay. Le successive chiamate di delay
devono mantenere costante il numero di processi sospesi, ogni successiva chiamata devo riattivare il primo
processo in attesa prima di sospendersi, la delay ritorna il valore passato come parametro dal processo che
ne ha riattivato l'esecuzione. e.g. se NDELAY è 2:
P1: delay(44) -> P1 si sospende
P2: delay(40) -> P2 si sospende
P3: delay(42) -> P1 si riattiva e ritorna 42, P3 si sospende
P4: delay(22) -> P2 si riattiva e ritorna 22, P4 si sospende

=== Soluzione proposta 1 ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart], da controllare

<syntaxhighlight lang=C>

// variabile definita altrove.
extern int NDELAY;

class Monitor {
Queue<condition> stopped;
int curr_value;
Monitor {
stopped = Queue<condition>();
curr_value = 0;
}

int delay(int value) {
curr_value = value;
if (stopped.size() == NDELAY) {
condition first = stopped.dequeue();
first.signal();
}
condition c = new condition();
stopped.enqueue(c);
c.wait();

return curr_value;
}
}

</syntaxhighlight>

== Esercizio c2 ==

=== Consegna ===

Esercizio c.2: Implementare usando semafori ordinari (fair, fifo) un servizio di semafori a priorità lifo che
fornisca le seguenti primitive:
void PLP(int prio);
void PLV()
PLP e PLV si devono comportare rispettivamente come P e V. Quando la PLV deve riattivare un processo
sceglie fra quelli in attesa quello a priorità massima, nel caso siano presenti più processi a priorità massima
sceglie quello in attesa da meno tempo.

=== Soluzione proposta 1 ===

Esercizio c2 (da controllare) da Flecart.

<syntaxhighlight lang="c">

Stack<semaphore> stack[MAX_PRIORITY];
int num_V = 0;
semaphore mutex(1);

void PLP(int prio) {
mutex.P();
if (num_V > 0) {
num_V--;
mutex.V();
return;
}

semaphore sem = semaphore(0);
stack[prio].push(sem);
mutex.V();
sem.P();

mutex.V();
}

void PLV() {
mutex.P();

for (int i = MAX_PRIORITY - 1; i >= 0; i--) {
if (stack[i].size() > 0) {
sem = stack[i].pop();
sem.V();
return;
}
}

num_V++;

mutex.V();
}

</syntaxhighlight>

= Prova 2021/05/26 =

== Consegna c1 ==

Esercizio c.1: Un buffer sincrono strampalato (bss) ha due procedure entry:
void put(T value)
list of T get(void)
La entry put viene utilizzata per aggiungere un elemento e la entry get per leggere tutti quelli disponibili.
Se più processi chiamano la put quando nessun processo è in attesa per una get, rimangono tutti bloccati.
Quando successivamente un processo chiama la get riceve la lista di tutti gli elementi inseriti con le put e
tutti i processi vengono sbloccati.
Se il buffer è vuoto tutti i processi che chiamano la get rimangono bloccati. quando un processo chiama
successivamente la put tutti i processi in attesa per la get si sbloccano e ricevono lo stesso valore di ritorno:
una lista contenente il solo valore passato come parametro alla put.

=== Soluzione proposta 1 ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]
<syntaxhighlight lang="C">
int num = 0; // se è positiva rappresenta numero di gets che aspettano, se negativa, numero di puts
semaphore semput(0);
semaphore semget(0);
semaphore mutex(1);
list<T> global_list;

void put(T value) {
//< await(num > 0) --> global_list.add(value) >
mutex.P();
if (num <= 0) {
num--;
mutex.V();
semput.P();
num++;
}
global_list.add(value);

if (num < 0)
semput.V();
else
semget.V();

return;
}

list of T get() {
list<T> local_list;

mutex.P();
if (num >= 0) {
num++;
mutex.V();
semget.P();
num--;
} else {
semput.V();
semget.P();
}

local_list = global_list; // fa deep copy

if (num > 0) {
semget.V();
} else {
global_list = list<T>();
mutex.V();
}

return local_list;
}
</syntaxhighlight>

=== Soluzione proposta 2 ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Gio Gio]
<syntaxhighlight lang="C">

class bss{
int waiting_put=0;
int waiting_get=0;
cond cw,cg;
queue<T> q;

void put(T value){
q.push(T);
if(waiting_get>0){
cg.signal()
}else{
waiting_put++;
cw.wait();
waiting_put--;
}
}

list<T> get(){
if(waiting_put>0){
while(waiting_put>0){
cw.signal();
}
}else{
waiting_get++;
cg.wait();
waiting_get--;
}
list<T> p= q.tolist();
if(waiting_get>0){
cg.signal();
}
q.removeAll();
return p;
}
}
</syntaxhighlight>

== esercizio c2 ==

Dato un servizio di message passing asincrono implementare un servizio di message passing
asincrono a selezione di mittenti (samp) senza fare uso di processi server.
Il servizio samp ha due primitive:
sasend(message , destination)
sarecv(senders)
dove senders è un insieme.
la sarecv restituisce il primo messaggio che uno dei processi in senders ha spedito al processo ricevente
usando la sasend (o spedito da qualsiasi processo se senders è vuoto).

=== Soluzione proposta 1 ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]
<syntaxhighlight lang="C">
sasend(message, destination) {
pid t = getpid();
asend(<message, t>, destination);
}

// variabile privata di sarecv
queue all_messages[MAX_PROC];

// stora tutti i messaggi ricevuti, lo utilizziamo come queue per tutti, con
// anche la possibilità di rimuovere in un punto a scelta.
vector<<messages, pid>> msg;
sarecv(senders) {
if (senders.len() == 0) {
if (msg.len() == 0) {
<message, sender> = arecv(ANY);
return message;
} else {
<message, sender> = msg.pop_back();
return message;
}
} else {
do {
for (idx in senders) {
if (all_messages[idx].size() > 0) {
message = all_messages[idx].dequeue();
// rimuove il singolo messaggio dal vector, non tutti quelli uguali.
msg.remove(<message, idx>);
return message;
}
}

<message, sender> = arecv(ANY);
msg.push_back(<message, sender>);
all_messages[sender].enqueue(<message>);
} while(true);
}
}
</syntaxhighlight>

Prove scritte 2021

2023-01-14T16:19:01Z

Gio: /* Prova 2021/09/15 */

= Prova 21/07/2021=

== Es C1 (da correggere) ==

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart friend],regalo a flecart la proprietà intellettuale di questa soluzione

<syntaxhighlight lang=C>

<class node{
node parent;
sq sq1;
cond c;
}

class BinTree{
vector<node> base;
void create(int N){
base=new vector<node>(2^N);
for(int i=0;i<2^N;i++)
base[i]=new node(null,0,new cond);
for(int i=1;i<=N;i++){
for(int j=0;j<2^(N-i);j++){
get(j,i-1).parent=get(j+i,i-1).parent=new node(null,0,new cond);
}
}
}
node get(int i,int level){
return get(base[i],level);
}
node get(node n,int level){
if(level==0){
return node;
}
return get(node.parent,level-1);
}
}

class Torneo{
BinTree bin(N);
int forma[2^N];
bool win;

bool gioca(int i,int turno,int forma){
forma[i]=forma;
if null==bin.get(i,turno).sq1{
bin.get(i,turno).sq1=i;
bin.get(i,turno).c.wait();
return !win;
}else{
sq1= bin.get(i,turno).sq1;
if(forma[sq1]==forma[i]){
win=random();
}else{
win=forma[sq1]<forma[i];
}
bin.get(i,turno).signal();
}
return win;
}
}
</syntaxhighlight>

= Prova 2021/09/15 =

== Esercizio C1 ==

=== Consegna ===
Esercizio c.1: Scrivere il monitor alrv (at least rendez-vous) che fornisce una sola procedure entry:
procedure entry void at_least(int n)
Quando un processo chiama la funzione at_least vuol dire che vuole sincronizzarsi con un insieme di almeno n
processi (incluso il chiamante).
Esempi:
Se un processo chiama at_least(1) non si blocca.
Se il processo p chiama at_least(2) si blocca, se poi il processo q chiama at_least(2) oppure at_least(1) si
sbloccano sia p sia q (la richiesta di p è soddisfatta, ne aspettava almeno 2, p e q)
Se il processo p chiama at_least(2) si blocca, se poi il processo q chiama at_least(3) si blocca anch'esso perché
sebbene la richiesta di p possa essere soddisfatta, q non può ancora sbloccarsi: ci sono solo 2 processi in attesa mentre
q ne vuole 3. Un terzo processo che chiami at_least(x) con x=1,2,3 li sblocca tutti.
Hint: sia w[k ] il numero dei processi in attesa di essere in almeno k (quelli che hanno chiamato at_least(k) e non
hanno completato l'esecuzione della funzione). Sia s[n]=∑
k=1
n
w[k ] (rappresenta il numero di processi soddisfacibili:
e.g. se ci sono 4 processi in attesa, potrebbero essere soddisfatte le richieste dei processi che ne aspettano almeno 2,
almeno 3 o almeno 4). Preso, se esiste, il massimo indice m tale che s[m]≥m tutti i processi in attesa di essere in n,
per n≤m possono essere sbloccati.

=== 1. Soluzione proposta ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]

<syntaxhighlight lang=C>

extern int MAX; // il massimo numero di attesa
monitor alrv {
int w[MAX];
int s[MAX];
condition c[MAX];

init() {
for (int i = 0; i < MAX; i++) {
w[i] = s[i] = 0;
}
}

procedure entry void at_least(int n) {
if (n >= MAX || n <= 0) raise error;

int i;
for (i = n; i < MAX; i++) s[i]++;

for (i = MAX - 1; i > 0; i--) {
if (s[i] >= i) break;
}

if (i > 0) {
for (int j = 0; j <= i; j++) {
while (w[j] > 0) {
c[j].signal();
w[j]--;
}
}

s[0] = 0;
for (int i = 1; i < MAX; i++) {
s[i] = w[i] + s[i - 1];
}
} else {
w[n]++;
c[n].wait();
}
}
}
</syntaxhighlight>
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart friend],regalo a flecart la proprietà intellettuale di questa soluzione

<syntaxhighlight lang=C>

class Monitor{

min_heap<(int,cond)> h;

void at_least(int n){
int sum=0;
int max_to_sblock= -INF;
cond c = new cond(n);
h.push((n,c));
// la heap viene visitata in maniera crescente
for(auto f=h.begin_iter();null!=f.next();f++) {
sum++;
if(f.0<=sum){
max_to_sblock =f.0;
}
}
for(auto f=h.begin_iter();null!=f.next();f++) {
if(f.0<=max_to_sblock){
f.1.signal();
h.remove(c);
}
}
if(n>max_to_sblock){
c.wait();
}
free(c)
}
}

</syntaxhighlight>

= Prova 2021/06/23 =

== Esercizio C1 ==

=== Consegna ===
Esercizio c.1: Scrivere il monitor delayvalue con una sola procedure entry:
int delay(int value);
Il monitor deve sospendere i primi NDELAY processi che chiamano la delay. Le successive chiamate di delay
devono mantenere costante il numero di processi sospesi, ogni successiva chiamata devo riattivare il primo
processo in attesa prima di sospendersi, la delay ritorna il valore passato come parametro dal processo che
ne ha riattivato l'esecuzione. e.g. se NDELAY è 2:
P1: delay(44) -> P1 si sospende
P2: delay(40) -> P2 si sospende
P3: delay(42) -> P1 si riattiva e ritorna 42, P3 si sospende
P4: delay(22) -> P2 si riattiva e ritorna 22, P4 si sospende

=== Soluzione proposta 1 ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart], da controllare

<syntaxhighlight lang=C>

// variabile definita altrove.
extern int NDELAY;

class Monitor {
Queue<condition> stopped;
int curr_value;
Monitor {
stopped = Queue<condition>();
curr_value = 0;
}

int delay(int value) {
curr_value = value;
if (stopped.size() == NDELAY) {
condition first = stopped.dequeue();
first.signal();
}
condition c = new condition();
stopped.enqueue(c);
c.wait();

return curr_value;
}
}

</syntaxhighlight>

== Esercizio c2 ==

=== Consegna ===

Esercizio c.2: Implementare usando semafori ordinari (fair, fifo) un servizio di semafori a priorità lifo che
fornisca le seguenti primitive:
void PLP(int prio);
void PLV()
PLP e PLV si devono comportare rispettivamente come P e V. Quando la PLV deve riattivare un processo
sceglie fra quelli in attesa quello a priorità massima, nel caso siano presenti più processi a priorità massima
sceglie quello in attesa da meno tempo.

=== Soluzione proposta 1 ===

Esercizio c2 (da controllare) da Flecart.

<syntaxhighlight lang="c">

Stack<semaphore> stack[MAX_PRIORITY];
int num_V = 0;
semaphore mutex(1);

void PLP(int prio) {
mutex.P();
if (num_V > 0) {
num_V--;
mutex.V();
return;
}

semaphore sem = semaphore(0);
stack[prio].push(sem);
mutex.V();
sem.P();

mutex.V();
}

void PLV() {
mutex.P();

for (int i = MAX_PRIORITY - 1; i >= 0; i--) {
if (stack[i].size() > 0) {
sem = stack[i].pop();
sem.V();
return;
}
}

num_V++;

mutex.V();
}

</syntaxhighlight>

= Prova 2021/05/26 =

== Consegna c1 ==

Esercizio c.1: Un buffer sincrono strampalato (bss) ha due procedure entry:
void put(T value)
list of T get(void)
La entry put viene utilizzata per aggiungere un elemento e la entry get per leggere tutti quelli disponibili.
Se più processi chiamano la put quando nessun processo è in attesa per una get, rimangono tutti bloccati.
Quando successivamente un processo chiama la get riceve la lista di tutti gli elementi inseriti con le put e
tutti i processi vengono sbloccati.
Se il buffer è vuoto tutti i processi che chiamano la get rimangono bloccati. quando un processo chiama
successivamente la put tutti i processi in attesa per la get si sbloccano e ricevono lo stesso valore di ritorno:
una lista contenente il solo valore passato come parametro alla put.

=== Soluzione proposta 1 ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]
<syntaxhighlight lang="C">
int num = 0; // se è positiva rappresenta numero di gets che aspettano, se negativa, numero di puts
semaphore semput(0);
semaphore semget(0);
semaphore mutex(1);
list<T> global_list;

void put(T value) {
//< await(num > 0) --> global_list.add(value) >
mutex.P();
if (num <= 0) {
num--;
mutex.V();
semput.P();
num++;
}
global_list.add(value);

if (num < 0)
semput.V();
else
semget.V();

return;
}

list of T get() {
list<T> local_list;

mutex.P();
if (num >= 0) {
num++;
mutex.V();
semget.P();
num--;
} else {
semput.V();
semget.P();
}

local_list = global_list; // fa deep copy

if (num > 0) {
semget.V();
} else {
global_list = list<T>();
mutex.V();
}

return local_list;
}
</syntaxhighlight>

=== Soluzione proposta 2 ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Gio Gio]
<syntaxhighlight lang="C">

class bss{
int waiting_put=0;
int waiting_get=0;
cond cw,cg;
queue<T> q;

void put(T value){
q.push(T);
if(waiting_get>0){
cg.signal()
}else{
waiting_put++;
cw.wait();
waiting_put--;
}
}

list<T> get(){
if(waiting_put>0){
while(waiting_put>0){
cw.signal();
}
}else{
waiting_get++;
cg.wait();
waiting_get--;
}
list<T> p= q.tolist();
if(waiting_get>0){
cg.signal();
}
q.removeAll();
return p;
}
}
</syntaxhighlight>

== esercizio c2 ==

Dato un servizio di message passing asincrono implementare un servizio di message passing
asincrono a selezione di mittenti (samp) senza fare uso di processi server.
Il servizio samp ha due primitive:
sasend(message , destination)
sarecv(senders)
dove senders è un insieme.
la sarecv restituisce il primo messaggio che uno dei processi in senders ha spedito al processo ricevente
usando la sasend (o spedito da qualsiasi processo se senders è vuoto).

=== Soluzione proposta 1 ===

Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]
<syntaxhighlight lang="C">
sasend(message, destination) {
pid t = getpid();
asend(<message, t>, destination);
}

// variabile privata di sarecv
queue all_messages[MAX_PROC];

// stora tutti i messaggi ricevuti, lo utilizziamo come queue per tutti, con
// anche la possibilità di rimuovere in un punto a scelta.
vector<<messages, pid>> msg;
sarecv(senders) {
if (senders.len() == 0) {
if (msg.len() == 0) {
<message, sender> = arecv(ANY);
return message;
} else {
<message, sender> = msg.pop_back();
return message;
}
} else {
do {
for (idx in senders) {
if (all_messages[idx].size() > 0) {
message = all_messages[idx].dequeue();
// rimuove il singolo messaggio dal vector, non tutti quelli uguali.
msg.remove(<message, idx>);
return message;
}
}

<message, sender> = arecv(ANY);
msg.push_back(<message, sender>);
all_messages[sender].enqueue(<message>);
} while(true);
}
}
</syntaxhighlight>

Prove scritte 2022

2023-01-14T15:17:01Z

Gio: /* Soluzione proposta (da controllare) */

Prove scritte 2022

2023-01-14T15:11:32Z

Gio: /* Soluzione proposta (da controllare) */

Prove scritte 2020

2023-01-13T14:26:03Z

Gio: /* esercizio c2 */

= Prova 2020/01/15 =

== esercizio c1 ==

=== Soluzione proposta 1 ===
<syntaxhighlight lang="C">
class TS{

int v=0;
queue<(unsigned int,cond)> pq;
usinged int timer;

void V(){
if(pq.empty()){
v++;
}else{
pq.pop().signal();
}
}
bool P(unsigned int timeout){
if(v == 0){
cond c = new condition();
pq.push((timeout+timer,));
c.wait();
free(c);
if timer== timeout+timer{
return true;
}
}else{
v--;
}
return false;
}

void tick(){
timer++;
for [i,c] in pq.iter(){
if( i <= timer) {
c.signal();
// la nostra stuttura dati supporta la rimozione durante lo scorrimento
// per esempio può essere una lista
pq.remove(c);
}
}
}
}

</syntaxhighlight>

=== Soluzione proposta 2 ===

<syntaxhighlight lang="C">

int value;
boolean ret_val;
int time;
min_heap<int, condition> heap; // ordinato sul tempo minore.
vector<condition> queue; // vector utilizzato come queue, con rimozione anche nel mezzo.

monitor {
value = 0;
time = 0;
}

void V(void) {
if (heap.size() > 0) {
condition c = queue.pop_back(); // remove and return
heap.remove(c); // rimuovi l'unico elemento con c.
ret_val = true;
c.signal();
} else {
value++;
}
}

boolean P(unsigned int timeout) {
if (value > 0) {
value--;
return true;
} else {
int next_time = timeout + time;
condition c = new condition();
heap.insert(<next_time, c>);
queue.push_back(c);
c.wait();
free(c);

return ret_val;
}
}

void tick(void) {
ret_val = false;
time++;
while (heap.size() > 0 && heap.top().0 <= time) {
condition c = heap.top().1;
heap.deleteTop();
queue.remove(c);
c.signal();
}
}

</syntaxhighlight>

== esercizio c2 ==

= Prova 2020/02/20 =

== esercizio c2 ==

Sol : x alla seconda

Prove scritte 2020

2023-01-13T14:24:20Z

Gio: /* esercizio c2 */

= Prova 2020/01/15 =

== esercizio c1 ==

=== Soluzione proposta 1 ===
<syntaxhighlight lang="C">
class TS{

int v=0;
queue<(unsigned int,cond)> pq;
usinged int timer;

void V(){
if(pq.empty()){
v++;
}else{
pq.pop().signal();
}
}
bool P(unsigned int timeout){
if(v == 0){
cond c = new condition();
pq.push((timeout+timer,));
c.wait();
free(c);
if timer== timeout+timer{
return true;
}
}else{
v--;
}
return false;
}

void tick(){
timer++;
for [i,c] in pq.iter(){
if( i <= timer) {
c.signal();
// la nostra stuttura dati supporta la rimozione durante lo scorrimento
// per esempio può essere una lista
pq.remove(c);
}
}
}
}

</syntaxhighlight>

=== Soluzione proposta 2 ===

<syntaxhighlight lang="C">

int value;
boolean ret_val;
int time;
min_heap<int, condition> heap; // ordinato sul tempo minore.
vector<condition> queue; // vector utilizzato come queue, con rimozione anche nel mezzo.

monitor {
value = 0;
time = 0;
}

void V(void) {
if (heap.size() > 0) {
condition c = queue.pop_back(); // remove and return
heap.remove(c); // rimuovi l'unico elemento con c.
ret_val = true;
c.signal();
} else {
value++;
}
}

boolean P(unsigned int timeout) {
if (value > 0) {
value--;
return true;
} else {
int next_time = timeout + time;
condition c = new condition();
heap.insert(<next_time, c>);
queue.push_back(c);
c.wait();
free(c);

return ret_val;
}
}

void tick(void) {
ret_val = false;
time++;
while (heap.size() > 0 && heap.top().0 <= time) {
condition c = heap.top().1;
heap.deleteTop();
queue.remove(c);
c.signal();
}
}

</syntaxhighlight>

== esercizio c2 ==

= Prova 2020/02/20 =

== esercizio c2 ==

<math>x^2</math>

Prove scritte 2020

2023-01-13T14:22:30Z

Gio: /* Prova 2020/01/15 */

Prove scritte 2020

2023-01-13T13:56:22Z

Gio: /* esercizio c1 */

Prove scritte 2021

2023-01-13T11:02:47Z

Gio: /* Prova 2021/05/26 */

= Prova 2021/09/15 =

== Esercizio C1 ==

=== Consegna ===
Esercizio c.1: Scrivere il monitor alrv (at least rendez-vous) che fornisce una sola procedure entry:
procedure entry void at_least(int n)
Quando un processo chiama la funzione at_least vuol dire che vuole sincronizzarsi con un insieme di almeno n
processi (incluso il chiamante).
Esempi:
Se un processo chiama at_least(1) non si blocca.
Se il processo p chiama at_least(2) si blocca, se poi il processo q chiama at_least(2) oppure at_least(1) si
sbloccano sia p sia q (la richiesta di p è soddisfatta, ne aspettava almeno 2, p e q)
Se il processo p chiama at_least(2) si blocca, se poi il processo q chiama at_least(3) si blocca anch'esso perché
sebbene la richiesta di p possa essere soddisfatta, q non può ancora sbloccarsi: ci sono solo 2 processi in attesa mentre
q ne vuole 3. Un terzo processo che chiami at_least(x) con x=1,2,3 li sblocca tutti.
Hint: sia w[k ] il numero dei processi in attesa di essere in almeno k (quelli che hanno chiamato at_least(k) e non
hanno completato l'esecuzione della funzione). Sia s[n]=∑
k=1
n
w[k ] (rappresenta il numero di processi soddisfacibili:
e.g. se ci sono 4 processi in attesa, potrebbero essere soddisfatte le richieste dei processi che ne aspettano almeno 2,
almeno 3 o almeno 4). Preso, se esiste, il massimo indice m tale che s[m]≥m tutti i processi in attesa di essere in n,
per n≤m possono essere sbloccati.

=== 1. Soluzione proposta ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart]

<syntaxhighlight lang=C>

extern int MAX; // il massimo numero di attesa
monitor alrv {
int w[MAX];
int s[MAX];
condition c[MAX];

init() {
for (int i = 0; i < MAX; i++) {
w[i] = s[i] = 0;
}
}

procedure entry void at_least(int n) {
if (n >= MAX || n <= 0) raise error;

int i;
for (i = n; i < MAX; i++) s[i]++;

for (i = MAX - 1; i > 0; i--) {
if (s[i] >= i) break;
}

if (i > 0) {
for (int j = 0; j <= i; j++) {
while (w[j] > 0) {
c[j].signal();
w[j]--;
}
}

s[0] = 0;
for (int i = 1; i < MAX; i++) {
s[i] = w[i] + s[i - 1];
}
} else {
w[n]++;
c[n].wait();
}
}
}
</syntaxhighlight>
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart frend],regalo a flecart la proprietà intellettuale di questa soluzione

<syntaxhighlight lang=C>

class Monitor{

min_heap<(int,cond)> h;

void at_least(int n){
int sum=0;
int max_to_sblock= -INF;
cond c = new cond(n);
h.push((n,c));
// la heap viene visitata in maniera crescente
for(auto f=h.begin_iter();null!=f.next();f++) {
sum++;
if(f.0<=sum){
max_to_sblock =f.0;
}
}
for(auto f=h.begin_iter();null!=f.next();f++) {
if(f.0<=max_to_sblock){
f.1.signal();
h.remove(c);
}
}
if(n>max_to_sblock){
c.wait();
}
free(c)
}
}

</syntaxhighlight>

= Prova 2021/06/23 =

== Esercizio C1 ==

=== Consegna ===
Esercizio c.1: Scrivere il monitor delayvalue con una sola procedure entry:
int delay(int value);
Il monitor deve sospendere i primi NDELAY processi che chiamano la delay. Le successive chiamate di delay
devono mantenere costante il numero di processi sospesi, ogni successiva chiamata devo riattivare il primo
processo in attesa prima di sospendersi, la delay ritorna il valore passato come parametro dal processo che
ne ha riattivato l'esecuzione. e.g. se NDELAY è 2:
P1: delay(44) -> P1 si sospende
P2: delay(40) -> P2 si sospende
P3: delay(42) -> P1 si riattiva e ritorna 42, P3 si sospende
P4: delay(22) -> P2 si riattiva e ritorna 22, P4 si sospende

=== Soluzione proposta 1 ===
Soluzione proposta da [https://so.v2.cs.unibo.it/wiki/index.php/User:Flecart Flecart], da controllare

<syntaxhighlight lang=C>

// variabile definita altrove.
extern int NDELAY;

class Monitor {
Queue<condition> stopped;
int curr_value;
Monitor {
stopped = Queue<condition>();
curr_value = 0;
}

int delay(int value) {
curr_value = value;
if (stopped.size() == NDELAY) {
condition first = stopped.dequeue();
first.signal();
}
condition c = new condition();
stopped.enqueue(c);
c.wait();

return curr_value;
}
}

</syntaxhighlight>

== Esercizio c2 ==

=== Consegna ===

Esercizio c.2: Implementare usando semafori ordinari (fair, fifo) un servizio di semafori a priorità lifo che
fornisca le seguenti primitive:
void PLP(int prio);
void PLV()
PLP e PLV si devono comportare rispettivamente come P e V. Quando la PLV deve riattivare un processo
sceglie fra quelli in attesa quello a priorità massima, nel caso siano presenti più processi a priorità massima
sceglie quello in attesa da meno tempo.

=== Soluzione proposta 1 ===

Esercizio c2 (da controllare) da Flecart.

<source lang="c">

Stack<semaphore> stack[MAX_PRIORITY];
int num_V = 0;
semaphore mutex(1);

void PLP(int prio) {
mutex.P();
if (num_V > 0) {
num_V--;
mutex.V();
return;
}

semaphore sem = semaphore(0);
stack[prio].push(sem);
mutex.V();
sem.P();

mutex.V();
}

void PLV() {
mutex.P();

for (int i = MAX_PRIORITY - 1; i >= 0; i--) {
if (stack[i].size() > 0) {
sem = stack[i].pop();
sem.V();
return;
}
}

num_V++;

mutex.V();
}

</source>

= Prova 2021/05/26 =

== Consegna c1 ==

Esercizio c.1: Un buffer sincrono strampalato (bss) ha due procedure entry:
void put(T value)
list of T get(void)
La entry put viene utilizzata per aggiungere un elemento e la entry get per leggere tutti quelli disponibili.
Se più processi chiamano la put quando nessun processo è in attesa per una get, rimangono tutti bloccati.
Quando successivamente un processo chiama la get riceve la lista di tutti gli elementi inseriti con le put e
tutti i processi vengono sbloccati.
Se il buffer è vuoto tutti i processi che chiamano la get rimangono bloccati. quando un processo chiama
successivamente la put tutti i processi in attesa per la get si sbloccano e ricevono lo stesso valore di ritorno:
una lista contenente il solo valore passato come parametro alla put.

=== Soluzione proposta 1 ===

<syntaxhighlight lang="C">
int num = 0; // se è positiva rappresenta numero di gets che aspettano, se negativa, numero di puts
semaphore semput(0);
semaphore semget(0);
semaphore mutex(1);
list<T> global_list;

void put(T value) {
//< await(num > 0) --> global_list.add(value) >
mutex.P();
if (num <= 0) {
num--;
mutex.V();
semput.P();
num++;
}
global_list.add(value);

if (num < 0)
semput.V();
else
semget.V();

return;
}

list of T get() {
list<T> local_list;

mutex.P();
if (num >= 0) {
num++;
mutex.V();
semget.P();
num--;
} else {
semput.V();
semget.P();
}

local_list = global_list; // fa deep copy

if (num > 0) {
semget.V();
} else {
global_list = list<T>();
mutex.V();
}

return local_list;
}
</syntaxhighlight>

<syntaxhighlight lang="C">

class bss{
int waiting_put=0;
int waiting_get=0;
cond cw,cg;
queue<T> q;

void put(T value){
q.push(T);
if(waiting_get>0){
cg.signal()
}else{
waiting_put++;
cw.wait();
waiting_put--;
}
}

list<T> get(){
if(waiting_put>0){
while(waiting_put>0){
cw.signal();
}
}else{
waiting_get++;
cg.wait();
waiting_get--;
}
list<T> p= q.tolist();
if(waiting_get>0){
cg.signal();
}
q.removeAll();
return p;
}
}
</syntaxhighlight>

Prove scritte 2021

2023-01-13T10:38:32Z

Gio: /* 1. Soluzione proposta */