Difference between revisions of "Prove scritte 2017"
Jump to navigation
Jump to search
(Created page with "== 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 === <source lang="c"> monitor crossing ok2dir[4]; ...") |
|||
(33 intermediate revisions by 3 users not shown) | |||
Line 2: | Line 2: | ||
[http://www.cs.unibo.it/~renzo/so/compiti/2017.09.11.tot.pdf 2017.09.11.tot.pdf] | [http://www.cs.unibo.it/~renzo/so/compiti/2017.09.11.tot.pdf 2017.09.11.tot.pdf] | ||
=== Esercizio c.1 === | === Esercizio c.1 === | ||
− | < | + | <syntaxhighlight lang="c"> |
monitor crossing | monitor crossing | ||
Line 31: | Line 31: | ||
ok2dir[(dir + i + 1) % 4].signal(); | ok2dir[(dir + i + 1) % 4].signal(); | ||
− | </ | + | </syntaxhighlight> |
<br> | <br> | ||
+ | |||
+ | ==== Soluzione proposta 2 ==== | ||
+ | Soluzione proposta da [https://t.me/LLibera LLibera] 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) === | === Esercizio c.2 (da controllare) === | ||
− | < | + | <syntaxhighlight lang="c"> |
// server[] = array contenente il PID di tutti i server | // server[] = array contenente il PID di tutti i server | ||
Line 63: | Line 110: | ||
} | } | ||
} | } | ||
− | </ | + | </syntaxhighlight> |
<br> | <br> | ||
+ | |||
+ | ==== 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 == | == Esame 17/07/2017 == | ||
[http://www.cs.unibo.it/~renzo/so/compiti/2017.07.17.tot.pdf 2017.07.17.tot.pdf] | [http://www.cs.unibo.it/~renzo/so/compiti/2017.07.17.tot.pdf 2017.07.17.tot.pdf] | ||
=== Esercizio c.1 === | === Esercizio c.1 === | ||
− | < | + | <syntaxhighlight lang="c"> |
monitor conf { | monitor conf { | ||
condition finished; | condition finished; | ||
Line 102: | Line 186: | ||
− | </ | + | </syntaxhighlight> |
=== Esercizio c.2 (da controllare) === | === Esercizio c.2 (da controllare) === | ||
− | < | + | controllata da [[User:LiberaL|LiberaL]] 14:26, 26 May 2023 (CEST) l'implementazione fornita gestisce solo il caso di arecv(ANY) e non arecv(mittente) |
+ | <syntaxhighlight lang="c"> | ||
si, è possibile: | si, è possibile: | ||
Implementare asend e arecv date bsend e brecv | Implementare asend e arecv date bsend e brecv | ||
− | asend(pid_t, msg_type msg){ | + | asend(pid_t dst, msg_type msg){ |
− | bsend (< | + | bsend (<dst, msg>); |
} | } | ||
arecv(*){ | arecv(*){ | ||
− | + | do { | |
− | do{ | ||
<dst, msg> = brecv(*); | <dst, msg> = brecv(*); | ||
− | }while (dst = | + | } while (dst != getpid()) |
return msg; | return msg; | ||
} | } | ||
+ | </syntaxhighlight> | ||
+ | <br> | ||
+ | propongo ([[User:LiberaL|LiberaL]] 06:04, 29 May 2023 (CEST)) quindi questa implementazione con gestione arecv da mittente specificato (sempre da controllare) | ||
+ | <syntaxhighlight lang="c"> | ||
+ | //il messaggio mandato è la tripla <destinatario, mittente, messaggio> | ||
+ | |||
+ | asend(pid_t dst, msg_type msg){ | ||
+ | bsend (<dst, getpid(), msg>); | ||
+ | } | ||
+ | |||
+ | myDictionaryQueue of <pid_t, msg_type> db; //nota: salvo qui solo se il messaggio è per me, quindi dest non mi serve | ||
+ | |||
+ | 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; | ||
− | </ | + | do { |
+ | <dst, mit, msg> = brecv(*); //ricevo | ||
+ | if( dst == getpid() ) { //il messaggio è per me? | ||
+ | if ( mit == sender || sender == ANY ) //se devo ritornare il messaggio | ||
+ | return msg; //esci dal while | ||
+ | //se devo salvarlo (sender specificato e messaggio per me) | ||
+ | //metto in db i messaggi di altri mittenti, ricevuti quando ne aspettavo uno da un mittente specificato | ||
+ | db.add(<mit, msg>); | ||
+ | } | ||
+ | } while ( true ) //devo uscire solo con il return | ||
+ | } | ||
+ | </syntaxhighlight> | ||
<br> | <br> | ||
Line 129: | Line 244: | ||
[http://www.cs.unibo.it/~renzo/so/compiti/2017.06.19.tot.pdf 2017.06.19.tot.pdf] | [http://www.cs.unibo.it/~renzo/so/compiti/2017.06.19.tot.pdf 2017.06.19.tot.pdf] | ||
=== Esercizio c.1 (da controllare)=== | === 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 [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 15:38, 19 January 2023 (CET) | ||
+ | |||
+ | <syntaxhighlight lang="c"> | ||
#define NATLETI n | #define NATLETI n | ||
Line 188: | Line 306: | ||
return best; | return best; | ||
} | } | ||
− | </ | + | </syntaxhighlight> |
<br> | <br> | ||
Line 194: | Line 312: | ||
[http://www.cs.unibo.it/~renzo/so/compiti/2017.05.29.tot.pdf 2017.05.29.tot.pdf] | [http://www.cs.unibo.it/~renzo/so/compiti/2017.05.29.tot.pdf 2017.05.29.tot.pdf] | ||
=== Esercizio c.1 === | === Esercizio c.1 === | ||
− | < | + | <syntaxhighlight lang="c"> |
condition okpartita | condition okpartita | ||
condition ok2chiama | condition ok2chiama | ||
Line 278: | Line 396: | ||
casi da discutere: | casi da discutere: | ||
se arrivano studenti a pronto prima che il prof dichiara nuovapartita succedono guai. | se arrivano studenti a pronto prima che il prof dichiara nuovapartita succedono guai. | ||
− | </ | + | </syntaxhighlight> |
Latest revision as of 05:05, 29 May 2023
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 (LiberaL 06:04, 29 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>);
}
myDictionaryQueue of <pid_t, msg_type> db; //nota: salvo qui solo se il messaggio è per me, quindi dest non mi serve
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;
do {
<dst, mit, msg> = brecv(*); //ricevo
if( dst == getpid() ) { //il messaggio è per me?
if ( mit == sender || sender == ANY ) //se devo ritornare il messaggio
return msg; //esci dal while
//se devo salvarlo (sender specificato e messaggio per me)
//metto in db i messaggi di altri mittenti, ricevuti quando ne aspettavo uno da un mittente specificato
db.add(<mit, msg>);
}
} while ( true ) //devo uscire solo con il return
}
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.