Sistemi Operativi - User contributions [en]

Prove scritte 2022

2024-01-21T09:55:52Z

Barba: /* Proposta di soluzione 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>

== Esercizio c2 ==

[[ 20220906c2 ]] proposte di soluzione

= Prova 2022/07/20 =

== Esercizio c1 ==

in un porto con una sola banchina utilizzabile occorre caricare cereali sulle navi. I camion portano i cereali al porto. Una sola nave alla volta può essere attraccata al molo, un solo camion alla volta scarica i cereali nella nave.
Il codice eseguito da ogni nave è:
nave[i] process:
porto.attracca(capacità)
porto.salpa()
...naviga verso la destinazione

Il codice di ogni camion è:
camion[j] process:
while (1):
quantità = carica_cereali()
porto.scarica(quantità)

I camion fanno la spola dai depositi alla nave. La nave arriva vuota e può salpare solo se è stata completamente riempita (la somma delle quantità scaricate dai camion raggiunge la capacità indicata come parametro della funzione attracca). Se un camion può scaricare solo parzialmente il suo carico rimane in porto e aspetta di completare l'operazione con la prossima nave che attraccherà al molo.
Scrivere il monitor porto.

=== Soluzione proposta 1 (da controllare) ===
Proposta da [[User: SpookyWiki |SpookyWiki]] ([[User talk:SpookyWiki|talk]]) 14:56, 13 May 2023 (CEST)

<syntaxhighlight lang=C>

// in questa versione, se il remainingSpace è -1 vuol dire che nessuna
//barca è attraccata
monitor porto{

int remainingSpace; // -1 -> non ci sono barche attraccate
bool camionSlotBusy;
condition waiting4slot; //il camion attende di essere preso in carico
condition waiting4dock; //la barca attende il molo
condition waiting4load; //il la barca attende i camion
condition waiting4boat; //i camion attendono una barca

porto {
remainingSpace = -1;
camionSlotBusy = false;
}

procedure entry void attracca(int capacità){
if( remainingSpace >=0 )
wait4dock.wait();
remainingSpace = capacità;
waiting4slot.signal();
}

procedure entry void salpa(){
if( remainingSpace > 0 )
wait4load.wait();
waiting4dock.signal();
}

procedure entry void scarica(quantità){
if( camionSlotBusy )
waiting4slot.wait()
//se non posso scaricare il carico
if( remainingSpace <= 0)
waiting4boat.wait()

int remainingLoad = quantità;

while (remainingLoad > 0){
//il camion si svuota e se ne deve andare
if( remainingSpace >= remainingLoad ) {
remainingSpace -= remainingLoad;
remainingLoad = 0;
if ( remainingSpace == 0)
wait4load.signal();
//il camion non si svuota del tutto e deve rimanere
} else {
remainingLoad -= remainingSpace;
remainingSpace = 0;
waiting4load.signal();
waiting4boat.wait();
}
}
waiting4slot.singal();

}

}
</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>

=== Soluzione proposta 2 (da controllare) ===
Proposta da [[User: SpookyWiki |SpookyWiki]] ([[User talk:SpookyWiki|talk]]) 18:06, 22 May 2023 (CEST)

<syntaxhighlight lang=C>
monitor delay {
Map<pid_t, int tickleft> tickmap;
pid_t last;
int blocked;
int quit;
condition wait4ticks;

delay() {
last = null;
blocked = 0;
quit = 0;
}

procedure entry int wait_tick(int nticks) {
blocked++;
if( nticks > 0 ) { // se un proc entra con nticks = 0 esce direttamente
pid_t mypid = getpid();
tickmap.add(mypid, nticks);
last = mypid
while ( tickmap[mypid].tickleft > 0) {
waiting4ticks.wait()
tickmap[mypid].tickleft --
if( last != mypid )
waiting4ticks.signal();
}
map.remove(mypid);
if( last == mypid )
last = tickleft.getLast(); //se la map è vuota, assumo ritorni null
}
quit++;
return blocked;
}

procedure entry void tick() {
waiting4ticks.signal();
blocked -= quitted;
quit = 0;
}
}
</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>

=== Soluzione proposta 2 (da controllare) ===
Proposta da [[User: SpookyWiki |SpookyWiki]] ([[User talk:SpookyWiki|talk]]) 18:42, 22 May 2023 (CEST)

<syntaxhighlight lang=C>
Map<<pid_t dest, pid_t mitt>, List<int> msgs> db;

void asend(msg_t msg, pid_t dest) { //dobbiamo salvarci l'ordine
pid_t mypid = getpid();
int progressivo;
if (db[<dest, mypid>] == null) {
db.add(<dest, mypid>);
db[<dest, mypid>].msgs.add(0)
progressivo = 0;
} else {
progressivo = db[<dest, mypid>].msgs.getLast() +1;
db[<dest, mypid>].msgs.add(progressivo);
}
nfasend(<msg, progressivo>, dest);
}

msg_t arecv(pid_t sender) {
pid_t mypid = getpid();
int progressivo = db[<mypid, sender>].msgs[0];
msg, prog = nfarecv(sender);
while ( prog != progressivo) {
nfasend(<msg, progressivo>, mypid);
msg, prog = nfarecv(sender);
}
db[<mypid, sender>].msgs.remove(0);
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>

== Esercizio c2 ==

Dato un servizio di message passing asincrono implementare un servizio di message passing sincrono
con selezione ordinata che ha la seguente interfaccia:

void snsend(msgtype msg, pid_t dest);
msgtype snrecv(pid_t sender, int n);

La funzione snrecv deve restituire l'n-mo messaggio proveniente dal mittente specificato (che può essere any). Se n ==
0 restituisce l'ultimo messaggio. Esempi:
m = snrecv(tizio, 1): restituisce il primo messaggio da tizio (attende se non ve ne sono)
m = snrecv(ANY, 42): restituisce il 42-mo messaggio da chiunque (attende se ci sono meno di 42 messaggi in attesa di
essere ricevuti)
m = snrecv(caio, 0): restituisce l'ultimo messaggio ricevuto da Caio (attende se non ci sono messaggi pendenti da Caio)
m = snrecv(ANY, 0): restituisce l'ultimo messaggio ricevuto, indipendentemente dal mittente.

=== Proposta di soluzione 1 (da controllare)===
* Proposta da [[User:Barba|zBarba]] ([[User talk:Barba|talk]]) 10:54, 21 January 2024 (CET)

<syntaxhighlight lang="C">
// int db.count(pid_t sender): conta quanti messaggi inviati da sender sono presenti nel db. Se sender == ANY allora li conta tutti
// msg_t db.extract(pid_t sender,int n): ritorna l'n-mo mesaggio del db inviato da sender. Se sender == ANY allora ritorna l'n-mo elemento

void snsend(msgtype msg, pid_t dest){
asend(<msg, getpid()>, dest)
do{
<m, snd> = arecv(dest)
db.add(<m, snd>)
}while(m != ACK)
db.extract(dest, db.count(dest))
}

msgtype snrecv(pid_t sender, int n){
if(n == 0){
n = db.count(sender)
}

while(db.count(sender) < n){
<m, snd> = arecv(sender)
db.add(<m, snd>)
}
<m, snd> = db.extract(sender, n)
asend(<ACK, getpid()>, snd)
return m
}
</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)
* Errore, ssend in questo caso non è sincrono, bisognerebbe uscire con l'ack dal receiver [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 22:56, 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:gio|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

2024-01-21T09:54:03Z

Barba: /* Prova 2022/02/14 */

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

== Esercizio c2 ==

[[ 20220906c2 ]] proposte di soluzione

= Prova 2022/07/20 =

== Esercizio c1 ==

in un porto con una sola banchina utilizzabile occorre caricare cereali sulle navi. I camion portano i cereali al porto. Una sola nave alla volta può essere attraccata al molo, un solo camion alla volta scarica i cereali nella nave.
Il codice eseguito da ogni nave è:
nave[i] process:
porto.attracca(capacità)
porto.salpa()
...naviga verso la destinazione

Il codice di ogni camion è:
camion[j] process:
while (1):
quantità = carica_cereali()
porto.scarica(quantità)

I camion fanno la spola dai depositi alla nave. La nave arriva vuota e può salpare solo se è stata completamente riempita (la somma delle quantità scaricate dai camion raggiunge la capacità indicata come parametro della funzione attracca). Se un camion può scaricare solo parzialmente il suo carico rimane in porto e aspetta di completare l'operazione con la prossima nave che attraccherà al molo.
Scrivere il monitor porto.

=== Soluzione proposta 1 (da controllare) ===
Proposta da [[User: SpookyWiki |SpookyWiki]] ([[User talk:SpookyWiki|talk]]) 14:56, 13 May 2023 (CEST)

<syntaxhighlight lang=C>

// in questa versione, se il remainingSpace è -1 vuol dire che nessuna
//barca è attraccata
monitor porto{

int remainingSpace; // -1 -> non ci sono barche attraccate
bool camionSlotBusy;
condition waiting4slot; //il camion attende di essere preso in carico
condition waiting4dock; //la barca attende il molo
condition waiting4load; //il la barca attende i camion
condition waiting4boat; //i camion attendono una barca

porto {
remainingSpace = -1;
camionSlotBusy = false;
}

procedure entry void attracca(int capacità){
if( remainingSpace >=0 )
wait4dock.wait();
remainingSpace = capacità;
waiting4slot.signal();
}

procedure entry void salpa(){
if( remainingSpace > 0 )
wait4load.wait();
waiting4dock.signal();
}

procedure entry void scarica(quantità){
if( camionSlotBusy )
waiting4slot.wait()
//se non posso scaricare il carico
if( remainingSpace <= 0)
waiting4boat.wait()

int remainingLoad = quantità;

while (remainingLoad > 0){
//il camion si svuota e se ne deve andare
if( remainingSpace >= remainingLoad ) {
remainingSpace -= remainingLoad;
remainingLoad = 0;
if ( remainingSpace == 0)
wait4load.signal();
//il camion non si svuota del tutto e deve rimanere
} else {
remainingLoad -= remainingSpace;
remainingSpace = 0;
waiting4load.signal();
waiting4boat.wait();
}
}
waiting4slot.singal();

}

}
</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>

=== Soluzione proposta 2 (da controllare) ===
Proposta da [[User: SpookyWiki |SpookyWiki]] ([[User talk:SpookyWiki|talk]]) 18:06, 22 May 2023 (CEST)

<syntaxhighlight lang=C>
monitor delay {
Map<pid_t, int tickleft> tickmap;
pid_t last;
int blocked;
int quit;
condition wait4ticks;

delay() {
last = null;
blocked = 0;
quit = 0;
}

procedure entry int wait_tick(int nticks) {
blocked++;
if( nticks > 0 ) { // se un proc entra con nticks = 0 esce direttamente
pid_t mypid = getpid();
tickmap.add(mypid, nticks);
last = mypid
while ( tickmap[mypid].tickleft > 0) {
waiting4ticks.wait()
tickmap[mypid].tickleft --
if( last != mypid )
waiting4ticks.signal();
}
map.remove(mypid);
if( last == mypid )
last = tickleft.getLast(); //se la map è vuota, assumo ritorni null
}
quit++;
return blocked;
}

procedure entry void tick() {
waiting4ticks.signal();
blocked -= quitted;
quit = 0;
}
}
</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>

=== Soluzione proposta 2 (da controllare) ===
Proposta da [[User: SpookyWiki |SpookyWiki]] ([[User talk:SpookyWiki|talk]]) 18:42, 22 May 2023 (CEST)

<syntaxhighlight lang=C>
Map<<pid_t dest, pid_t mitt>, List<int> msgs> db;

void asend(msg_t msg, pid_t dest) { //dobbiamo salvarci l'ordine
pid_t mypid = getpid();
int progressivo;
if (db[<dest, mypid>] == null) {
db.add(<dest, mypid>);
db[<dest, mypid>].msgs.add(0)
progressivo = 0;
} else {
progressivo = db[<dest, mypid>].msgs.getLast() +1;
db[<dest, mypid>].msgs.add(progressivo);
}
nfasend(<msg, progressivo>, dest);
}

msg_t arecv(pid_t sender) {
pid_t mypid = getpid();
int progressivo = db[<mypid, sender>].msgs[0];
msg, prog = nfarecv(sender);
while ( prog != progressivo) {
nfasend(<msg, progressivo>, mypid);
msg, prog = nfarecv(sender);
}
db[<mypid, sender>].msgs.remove(0);
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>

== Esercizio c2 ==

Dato un servizio di message passing asincrono implementare un servizio di message passing sincrono
con selezione ordinata che ha la seguente interfaccia:

void snsend(msgtype msg, pid_t dest);
msgtype snrecv(pid_t sender, int n);

La funzione snrecv deve restituire l'n-mo messaggio proveniente dal mittente specificato (che può essere any). Se n ==
0 restituisce l'ultimo messaggio. Esempi:
m = snrecv(tizio, 1): restituisce il primo messaggio da tizio (attende se non ve ne sono)
m = snrecv(ANY, 42): restituisce il 42-mo messaggio da chiunque (attende se ci sono meno di 42 messaggi in attesa di
essere ricevuti)
m = snrecv(caio, 0): restituisce l'ultimo messaggio ricevuto da Caio (attende se non ci sono messaggi pendenti da Caio)
m = snrecv(ANY, 0): restituisce l'ultimo messaggio ricevuto, indipendentemente dal mittente.

=== Proposta di soluzione 1 (da controllare)===
* Proposta da [[User:Barba|zBarba]] ([[User talk:Barba|talk]]) 10:54, 21 January 2024 (CET)

<syntaxhighlight lang="C">
// int db.count(pid_t sender): conta quanti messaggi inviati da sender sono presenti nel db. Se sender == ANY allora li conta tutti
// msg_t db.extract(pid_t sender,int n): ritorna l'n-mo mesaggio del db inviato da sender. Se sender == ANY allora ritorna l'n-mo elemento

void snsend(msgtype msg, pid_t dest){
asend(<msg, getpid()>, dest)
do{
<m, snd> = arecv(dest)
db.add(<m, snd>)
}while(m != ACK)
db.extract(dest, 0)
}

msgtype snrecv(pid_t sender, int n){
if(n == 0){
n = db.count(sender)
}

while(db.count(sender) < n){
<m, snd> = arecv(sender)
db.add(<m, snd>)
}
<m, snd> = db.extract(sender, n)
asend(<ACK, getpid()>, snd)
return m
}
</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)
* Errore, ssend in questo caso non è sincrono, bisognerebbe uscire con l'ack dal receiver [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 22:56, 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:gio|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 2021

2024-01-20T13:47:35Z

Barba: /* Consegna 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>

== Es G1 ==
=== consegna ===

Sia dato l'algoritmo di rimpiazzamento modulo che data una memoria di NF frame , se avviene un page
fault in corrispondenza dell'i-mo elemento della stringa di riferimenti modulo sceglie come pagina vittima quella che
occupa il frame i % NF.
Es. se NF fosse 3, la prima pagina viene messa nel frame 1 perché 1 % 3 = 1, se l'undicesimo elemento della stringa
causa un page fault, si elimina la pagina nel frame 2 (11 % 3 = 2).
A) Considerare la stringa di riferimenti seguente e mostrare il funzionamento di modulo nei casi NF = 3 e NF = 4:
1 2 3 4 5 3 3 3 1 5
B) modulo è un algoritmo a stack?

=== Soluzione proposta (da controllare) ===
[[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 14:44, 4 May 2023 (CEST)

<pre>
Caso in cui NF=3
allora
1 X X 1
1 2 X 2
1 2 3 3
4 2 3 4
4 5 3 5
4 5 3 3
4 5 3 3
4 5 3 3
1 5 3 1
1 5 3 5

Caso in cui NF=4
1 X X X 1
1 2 X X 2
1 2 3 X 3
1 2 3 4 4
5 2 3 4 5
5 2 3 4 3
5 2 3 4 3
5 2 3 4 3
1 2 3 4 1
5 2 3 4 5

Allora, l'algoritmo non è a stack perché nella penultima accesso al frame ho nel caso NF=3 che
{1, 5, 3}, ma questo non è contenuto in {1, 2, 3, 4}.
</pre>

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

=== 2. Soluzione proposta ===
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>
=== Soluzione proposta 3 (da controllare) ===
Proposta da [[User:SpookyWiki|SpookyWiki]] ([[User talk:SpookyWiki|talk]]) 11:41, 25 May 2023 (CEST)

<syntaxhighlight lang="C">
monitor alrv {
int maxindex;
Map<int, int> waiting4[];
Map<int, condition> ok2go[]

alrv() {
maxindex = 0;
waiting4 = new Map<int, int>();
ok2go = new Map<int, condition>();
}

procedure int check() { //procedura che controlla che i processi in attesa fino n possano essere sbloccati o meno
int sum = 0;
int m = 0;
do {
m++
sum += waiting4[m];
} while(m < maxindex && sum >= m)
return sum >= m ? m : m - 1;
}

procedure entry void at_least(int n) {
if(waiting4[n] == null) {
waiting4.add(n);
waiting4[n]++;
ok2.add(n);
}
if (n > maxindex)
maxindex = n;
int m;
if ((m = check(n)) > 0) {
for(int i = 1; i <= m; i++) {
ok2[i].signal();
waiting4[i] = 0;
}
} else {
ok2go[n].wait();
ok2go[n].signal();
}
}
}
</syntaxhighlight>

== Esercizio C2 ==
Dato un servizio di message passing sincrono scrivere, senza fare uso di processi server, un servizio di
message passing sincrono concatenato che abbia le seguenti primitive:
void chained_send (T msg, list_of_pids dests)
T chained_recv(void)
La funzione chained_send deve fare in modo che tutti i processi indicati nella lista dests ricevano il messaggio. Il
processo che chiama la chained_send si blocca solo fino a quando il primo processo della lista dests non chiama una
chained_recv, il primo si sblocca quando il secondo chiama la chained_recv e così via.
( la funzione chained_recv riceve messaggi provenienti da qualsiasi mittente)

=== Soluzione proposta 1 (da controllare) ===
* proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 18:37, 16 January 2023 (CET)

<syntaxhighlight lang="C">
void chained_send(T msg, list_of_pids dests) {
if (dests.len() < 1) return ERROR;
else if (dests.len() == 1) {
pid head = dests[0];
ssend(<msg, NULL>, head);
} else {
<head, rest> = dests[0], dests[1:];
ssend(<msg, rest>, head);
}
}

T chained_recv(void) {
<msg, rest> = srecv(ANY);
if (rest == NULL) return msg;

if (rest.len() == 1) {
pid head = rest[0];
ssend(<msg, NULL>, head);
} else if (rest.len() > 1) {
<head, rest2> = rest[0], rest[1:];
ssend(<msg, rest2>, head);
}

return msg;
}
</syntaxhighlight>

=== Soluzione proposta 2 (da controllare) ===
Proposta da [[User:SpookyWiki|SpookyWiki]] ([[User talk:SpookyWiki|talk]]) 12:20, 23 May 2023 (CEST)

<syntaxhighlight lang="C">
void chained_send(T msg, list_of_pids dests) {
if ( dests.length() < 1)
return;
pid_t dest = dests.pop(0); //rimuovo e prendo il primo destinatario
ssend(<msg, dests>, dest);
}

T chained_recv(void) {
<msg, dests> == srecv(ANY);
if(dests.length() > 0) { //il messaggio deve essere ancora inviato ad altri
pid_t dest = dests.pop(0);
ssend(<msg, dests>, dest);
}
return msg;
}
</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();
free(c);

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.

* Controllato da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 18:10, 16 January 2023 (CET), corretto se si assume la FIFO interna della condition.

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

=== Soluzione proposta 3 (da controllare) ===
Proposta da [[User:SpookyWiki|SpookyWiki]] ([[User talk:SpookyWiki|talk]]) 12:05, 25 May 2023 (CEST)

Si assume una politica FIFO delle condition, NDELAY non variabile d'ambiente ma parametro passato all'inizializzazione.

<syntaxhighlight lang="C">
monitor delayvalue {
int ndelay;
int in;
int lastvalue;
condition ok2return;

delay(int NDELAY) {
ndelay = NDELAY;
in = 0;
lastvalue = 0;
}

procedure entry int delay(int value) {
if (in >= ndelay) {
lastvalue = value;
ok2return.signal();
} else
in++;
ok2return.wait();
return lastvalue;
}

}
</syntaxhighlight>

== Esercizio c2 ==
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>

=== Soluzione proposta 3 ===

Soluzione proposta da [[User:Barba|zBarba]] ([[User talk:Barba|talk]]) 14:47, 20 January 2024 (CET)
<syntaxhighlight lang="C">
monitor bss:
list<T> buffer
int nget
condition ok2put
condition ok2get

procedure entry void put(T value){
buffer.add(value)
if(nget==0){
ok2put.wait()
ok2put.signal() //cascata di signal
}else if(nget>0){
ok2get.signal()
buffer.clear()
}
}

procedure entry list<T> get(void){
ok2put.signal()
if(buffer.isEmpty()){
nget++
ok2get.wait()
ok2get.signal() //cascata di signal
nget--
}
return buffer
}
</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>

=== Soluzione proposta 2 ===

Soluzione proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 13:05, 7 March 2023 (CET)
dovrebbe essere più semplice della precedente.

<syntaxhighlight lang="C">
sasend(message, destination) {
pid t = getpid();
asend(<message, t>, destination);
}

extern int MAX_PID;

// storerà tutti i messaggi che ricevo che non riesco a utilizzare subito
queue<message> msgs[MAX_PID];
sarecv(senders) {
if (senders == NULL) {
senders = {0, 1, ..., MAX_PID};
}

for (pid_t sender : senders) {
if (msgs[sender].size() > 0) {
message_t msg = msgs[sender].dequeue();
return msg;
}
}

while (True) {
msg, pid = arecv(ANY);
if (pid in senders) {
return msg;
} else {
msgs[pid].enqueue(msg);
}
}
}
</syntaxhighlight>

User:Barba

2024-01-20T13:42:18Z

Barba: Created page with "Marco Reina"

Marco Reina