Prove scritte 2017
Esame 11/09/2017
Esercizio c.1
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();
Soluzione proposta 2
Soluzione proposta da LLibera e corretta da Flecart
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.
}
}
}
}
Esercizio c.2 (da controllare)
// 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]
}
}
Soluzione proposta 2
Soluzione proposta da Flecart Soluzione corretta da Flecart friend
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]);
}
}
}
Esame 17/07/2017
Esercizio c.1
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;
}
}
Esercizio c.2 (da controllare)
controllata da LiberaL 14:26, 26 May 2023 (CEST) l'implementazione fornita gestisce solo il caso di arecv(ANY) e non arecv(mittente)
si, è possibile:
Implementare asend e arecv date bsend e brecv
asend(pid_t dst, msg_type msg){
bsend (<dst, msg>);
}
arecv(*){
do {
<dst, msg> = brecv(*);
} while (dst != getpid())
return msg;
}
propongo (13:04, 27 May 2023 (CEST)) quindi questa implementazione con gestione arecv da mittente specificato (sempre da controllare)
//il messaggio mandato è la tripla <destinatario, mittente, messaggio>
asend(pid_t dst, msg_type msg){
bsend (<dst, getpid(), msg>);
}
Queue of <pid_t, msg_type> db; //nota: salvo qui solo se il messaggio è per me quindi dest non mi serve sarebbe sempre == getpid()
arecv(pid_t sender) {
//devo controllare se nella coda ho già ricevuto il messaggio da quel mittente, ovvero mentre aspettavo un messaggio da qualcun'altro
//db.get(sender) cerca una tripla il cui mittente è sender
//se trova il messaggio lo rimuove anche dal db.
//db.get(ANY) ritorna (ed elimina da db) il primo che trova (FIFO), e if(db.isEmpty()) return NULL;
if( ( <mit, msg> = db.get(sender) ) != NULL ) //se lo trova
return msg;
bool message_for_me;
do {
<dst, mit, msg> = brecv(*); //ricevo
message_for_me = (dst == getpid()); //il messaggio è per me?
if( message_for_me ) {
if ( mit == sender || sender == ANY ) //se devo ritornare il messaggio
break; //esci dal while
else //se devo salvarlo (sender specificato e messaggio per me)
//devo mettere in db i messaggi di altri mittenti, ricevuti quando ne aspettavo uno da un mittente specificato
db.add(<mit, msg>);
}
} while (!message_for_me)
return msg;
}
Esame 19/06/2017
Esercizio c.1 (da controllare)
- Mi sembra che ci sia un errore per il giodice, potrebbe succedere in un caso che il wait non si risvegli mai Flecart (talk) 15:38, 19 January 2023 (CET)
#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;
}
Esame 29/05/2017
Esercizio c.1
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.