ProvaTeorica 2014.01.22

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);
*/