Difference between revisions of "ProvaTeorica 2014.01.22"

From Sistemi Operativi
Jump to navigation Jump to search
 
(21 intermediate revisions by 5 users not shown)
Line 1: Line 1:
−
 
+
<h1>[http://www.cs.unibo.it/~renzo/so/compiti/2014.01.22.tot.pdf Testo del compito]</h1>
  
 
<syntaxhighlight lang="C">
 
<syntaxhighlight lang="C">
Line 9: Line 9:
  
 
monitor bridge {
 
monitor bridge {
−
condition oktomove; /*si muove solo se il ponte è libero o non ci sono auto che vengono nel senso opposto */
+
condition oktomove; /* auto attraversa il ponte */
 
int turn=0; /*indica il senso delle auto */
 
int turn=0; /*indica il senso delle auto */
 
int est=0,ovest=0;      /*contatori delle auto da est e da ovest */
 
int est=0,ovest=0;      /*contatori delle auto da est e da ovest */
Line 20: Line 20:
 
if(turn == 2 || est >=N || !empty(q))   
 
if(turn == 2 || est >=N || !empty(q))   
 
{
 
{
−
q=equeue("E"); /*inserisco nella coda dei sensi*/
+
q=enqueue("E"); /*inserisco nella coda dei sensi*/
 
oktomove.wait();  /*aspetta*/
 
oktomove.wait();  /*aspetta*/
 
 
Line 31: Line 31:
 
if(turn ==1 || ovest >=N || !empty(q))
 
if(turn ==1 || ovest >=N || !empty(q))
 
{
 
{
−
        q=equeue("O"); /*inserisco nella coda dei sensi*/
+
        q=enqueue("O"); /*inserisco nella coda dei sensi*/
 
oktomove.wait(); /*aspetta*/
 
oktomove.wait(); /*aspetta*/
 
 
Line 46: Line 46:
 
{
 
{
 
est--;
 
est--;
−
r=tail(q);
+
r=head(q);                         /* leggo la prossima auto che aspetta di entrare */
−
if(est == 0 || r == "E")
+
if(est == 0 || r == "E")     /*nessuna auto in transito nel ponte o il prossimo va nella stessa direzione*/
 
{
 
{
 
est--;
 
est--;
Line 59: Line 59:
 
oktomove.signal(); /*segnale*/
 
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*/
 +
        }
 +
        }
 +
}
 +
 +
}
 +
</syntaxhighlight>
 +
 +
------
 +
 +
<syntaxhighlight lang="C">
 +
/*
 +
* 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
 
else
 
{
 
{
−
ovest--;
+
/* Se - il numero di veicoli sul ponte ha raggiunto il massimo; oppure
−
if(ovest == 0) /*nessuna auto in transito nel ponte */
+
      - 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')
 
{
 
{
−
turn = 0; /*avanti un altro */
+
  /* 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();
 
}
 
}
−
if(!empty(q))
+
// [Case 2] L'ultimo ad attraversare andava in direzione Est
 +
else
 
{
 
{
−
q.dequeue();
+
  /* Se esiste, attivo il veicolo che per primo si era messo
−
oktomove.signal(); /*segnale*/
+
              in attesa per la direzione opposta */
 +
  if (waitingW > 0)
 +
okW.signal();
 +
  else
 +
okE.signal();
 +
}
 
}
 
}
 
}
 
}
 
}
 
}
 +
</syntaxhighlight>
 +
 +
La Mia soluzione:
 +
<syntaxhighlight lang="C">
 +
/*
 +
* 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();
 +
}
 +
}
 +
       
 +
}
 +
}
 +
</syntaxhighlight>
 +
 +
== Esercizio g.1==
 +
 +
<syntaxhighlight lang="C">
 +
"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...
 +
 +
 +
</syntaxhighlight >
 +
 +
==Esercizio c.2==
 +
 +
<syntaxhighlight lang="C">
 +
 +
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);
 +
*/
 +
</syntaxhighlight>

Latest revision as of 16:24, 16 June 2017

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);
*/
Retrieved from "https://so.v2.cs.unibo.it/wiki/index.php?title=ProvaTeorica_2014.01.22&oldid=1941"