ProvaTeorica 2014.01.22
Jump to navigation
Jump to search
Testo del compito
URL: http://www.cs.unibo.it/~renzo/so/compiti/2014.01.22.tot.pdf
@author: Alessandro
monitor bridge {
condition oktomove; /* auto attraversa il ponte */
int turn=0; /*indica il senso delle auto */
int est=0,ovest=0; /*contatori delle auto da est e da ovest */
Queue q; /*coda delle senso delle macchine in attesa */
procedure entry enter (char EoW)
{
if(EoW == "E") /* viene da est */
{
if(turn == 2 || est >=N || !empty(q))
{
q=enqueue("E"); /*inserisco nella coda dei sensi*/
oktomove.wait(); /*aspetta*/
}
turn = 1; /*impongo il senso delle auto in circolo nel ponte */
est++;
}
else /* viene da ovest */
{
if(turn ==1 || ovest >=N || !empty(q))
{
q=enqueue("O"); /*inserisco nella coda dei sensi*/
oktomove.wait(); /*aspetta*/
}
turn = 2; /*impongo il senso delle auto in circolo nel ponte */
ovest++;
}
}
procedure entry exit(char EoW)
{
char r;
if(EoW == "O")
{
est--;
r=head(q); /* leggo la prossima auto che aspetta di entrare */
if(est == 0 || r == "E") /*nessuna auto in transito nel ponte o il prossimo va nella stessa direzione*/
{
est--;
if(est == 0) /*nessuna auto in transito nel ponte */
{
turn = 0; /*avanti un altro */
}
if(!empty(q))
{
q.dequeue();
oktomove.signal(); /*segnale*/
}
}
else
{
ovest--;
r=head(q); /* leggo la prossima auto che aspetta di entrare */
if(ovest == 0 || r == "O") /*nessuna auto in transito nel ponte o il prossimo va nella stessa direzione*/
{
turn = 0; /*avanti un altro */
}
if(!empty(q))
{
q.dequeue();
oktomove.signal(); /*segnale*/
}
}
}
}
/*
* URL: http://www.cs.unibo.it/~renzo/so/compiti/2014.01.22.tot.pdf
* author: Tommaso Ognibene
*/
monitor bridge
{
condition okE; // attraversare in direzione Est
condition okW; // attraversare in direzione Ovest
int n = 0; // numero di veicoli sul ponte
int waitingE = 0; // numero di veicoli che attendono di attraversare in direzione Est
int waitingW = 0; // numero di veicoli che attendono di attraversare in direzione Ovest
bool toE = true; // direzione di attraversamento
procedure entry enter(Vehicle vehicle)
{
// [Case 1] Il veicolo vuole attraversare in direzione Ovest
if (vehicle.To == 'W')
{
/* Se - il numero di veicoli sul ponte ha raggiunto il massimo; oppure
- qualcuno sta attraversando in direzione opposta; oppure
- qualcuno sta attendendo di attraversare in direzione opposta */
if (n == N || (toE && n > 0) || (!toE && waitingE > 0))
{
// Mi fermo e attendo di essere sbloccato
waitingW++;
okW.wait();
waitingW--;
}
toE = false;
n++;
/* Se possibile, sblocco eventuali altri veicoli in attesa per la stessa direzione.
* Questo non crea starvation in quanto sono sicuramente un numero limitato. */
if (n < N && waitingE == 0)
okW.signal();
}
// [Case 2] Il veicolo vuole attraversare in direzione Est
else
{
/* Se - il numero di veicoli sul ponte ha raggiunto il massimo; oppure
- qualcuno sta attraversando in direzione opposta; oppure
- qualcuno sta attendendo di attraversare in direzione opposta */
if (n == N || (!toE && n > 0) || (toE && waitingW > 0))
{
// Mi fermo e attendo di essere sbloccato
waitingE++;
okE.wait();
waitingE--;
}
toE = true;
n++;
/* Se possibile, sblocco eventuali altri veicoli in attesa per la stessa direzione.
* Questo non crea starvation in quanto sono sicuramente un numero limitato. */
if (n < N && waitingW == 0)
okE.signal();
}
}
procedure entry exit(Vehicle vehicle)
{
n--;
/* Se nessuno sta attraversando il ponte */
if (n == 0)
{
// [Case 1] L'ultimo ad attraversare andava in direzione Ovest
if (vehicle.To == 'W')
{
/* Se esiste, attivo il veicolo che per primo si era messo
in attesa per la direzione opposta */
if (waitingE > 0)
okE.signal();
else
okW.signal();
}
// [Case 2] L'ultimo ad attraversare andava in direzione Est
else
{
/* Se esiste, attivo il veicolo che per primo si era messo
in attesa per la direzione opposta */
if (waitingW > 0)
okW.signal();
else
okE.signal();
}
}
}
}
La Mia soluzione:
/*
* author: Midolo
*/
Monitor Ponte {
#define O 0
#define E 1
condition oktocross[2];
int countwaiting[2], crossing;
bridge.enter(dir){
if(crossing != 0 || countwaiting[1-dir] != 0){
countwaiting[dir]++;
oktocross[dir].wait();
countwaiting[dir]--;
}
crossing++;
if(crossing < N){
oktocross[dir].signal();
}
}
bridge.exit(dir){
crossing--;
if(crossing == 0){
if(countwaiting[dir] != 0){
oktocross[dir].signal();
}else{
oktocross[1-dir].signal();
}
}
}
}
Esercizio g.1
"Punto a"
123456789123456789123456789...
111111111111111111111111111
22222222222222222222222222 MIN e MAXNUM (infiniti page fault)
3456789993456789993456789
"Punto b"
123453453453453453453453453...
111111111111111111111111111
22222222222222222222222222 MIN e MAXNUM (page fault ad ogni accesso)
3453453453453453453453453
== Esercizio g.1 ==
a)
1234123124123124123...
111111111111111111 ...
22222222222222222 ...
3444333444333444 ...
b)
12343434343...
11144444444...
1222222222...
333333333...
Esercizio c.2
message database=Queue():
message msgxchange(pid_t pid, message msg)
{
message ris;
asendx(pid,msg);
ris=database.Search(pid,getpid());
if (ris!=NULL)
return ris;
do
{
ris=arecvx();
if (ris.sender!=pid)
database.Add(ris)
}
while (ris.sender!=pid);
return ris;
}
/*
Sì, può provocare deadlock. Es:
A: msgxchange(B,msg);
B: msgxchange(C,msg);
C: msgxchange(A,msg);
*/