Difference between revisions of "ProvaTeorica 2012.05.24"

From Sistemi Operativi
Jump to navigation Jump to search
 
(19 intermediate revisions by 6 users not shown)
Line 1: Line 1:
 
<h1>http://www.cs.unibo.it/~renzo/so/compiti/2012-05-24.tot.pdf</h1>
 
<h1>http://www.cs.unibo.it/~renzo/so/compiti/2012-05-24.tot.pdf</h1>
  
 +
<syntaxhighlight lang="C">
 +
monitor santuario
 +
{
 +
#define ANDATA 0
 +
#define RITORNO 1
 +
condition oktoenterponte, oktoexitponte ;
 +
int waiting, crossing, medita ;
 +
 +
procedure entry enterponte(ANDATA)
 +
  {
 +
 +
if ( crssing(ritorno) > = 0 || crossing(ANDATA) > maxSantuario || waiting (RITORNO)>0 )    # per evitare deadlock
 +
    # deve essere maxSantuario >= maxPonte
 +
waiting (ANDATA)++ ;     # crossing(ANDATA) >= maxSantuario
 +
oktoenterponte(ANDATA).wait();
 +
waiting(ANDATA)-- ;
 +
crossing(ANDATA)++ ;
 +
  }
 +
 +
procedure entry exitponte(ANDATA)        # Entra nel santuario
 +
  {
 +
    if ( medita == maxSantuario )
 +
oktoexitponte(ANDATA).wait() ;
 +
crossing(ANDATA)--;
 +
medita++ ;
 +
if (waiting(RITORNO) > 0 ) && (crossing(ANDATA)==0)
 +
oktoenterponte(RITORNO).signal();
 +
oktoenterponte(ANDATA).signal();
 +
  }
 +
 +
rocedure entry enterponte(RITORNO)      # Esci dal santuario
 +
  {
 +
    if (crossing(ANDATA)>0 || crossing(RTORNO) >= maxPonte)
 +
    wiiting(RITORNO)++;
 +
oktoenterponte(RITORNO).wait();
 +
waiting(RITORNO)--;
 +
medita--;
 +
crossing(RITORNO)++;
 +
  }
 +
 
 +
procedure entry exitponte(RITORNO)
 +
  {
 +
crossing(RITORNO)--;
 +
if (waiting(RITORNO)>0)
 +
oktoexitponte(RITORNO).signal()
 +
oktoenterponte(ANDATA).signal() ;
 +
  }
 +
}
  
 +
/* Correggetemi se sbaglio.
  
<syntaxhighlight lang="C">
+
  STARVATION : non l'ho individuata.  
/*
+
            Io penso che se al santuario recitassero tutti il rosario e confessassero molti peccati, allora si.  
  * URL: http://www.cs.unibo.it/~renzo/so/compiti/2012-05-24.tot.pdf
+
  DEADLOCK : se la portata del ponte era piu' grande della portata del santuario si aveva deadlock.
  * author: Tommaso Ognibene
+
          L'ho eliminato mettendo in wait se crossing(ANDATA) > maxSantuario
 
*/
 
*/
 +
save
 +
</syntaxhighlight>
  
 +
<syntaxhighlight lang="C">
 
monitor santuario
 
monitor santuario
 
{
 
{
condition okP;   // andare al santuario
+
Go = 0;               // andare al santuario
condition okS;   // tornare indietro
+
Back = 1;             // tornare indietro
int numP = 0;     // numero di persone sul ponte
+
condition ok[2];     // 2 condizioni
int numS = 0;     // numero di persone nel santuario
+
crossing[2] = {0, 0}; // numero di persone sul ponte
int waitingP = 0; // numero di persone che attendono di andare al santuario
+
visiting = 0;         // numero di persone nel santuario
int waitingS = 0; // numero di persone che attendono di tornare indietro
+
waiting[2] = {0, 0}; // numero di persone in attesa
bool toS = true;  // direzione di attraversamento del ponte
 
  
procedure entry entraponte(bool goingBack)
+
procedure entry entraponte(dir)
 
{
 
{
// [Case 1] La persona vuole tornare indietro
+
/* Mi blocco se:
if (goingBack)
+
      - il numero di persone sul ponte ha raggiunto il massimo; oppure
 +
      - la direzione e' il santuario e il numero di visitatori
 +
                        (compresi quelli che stanno raggiungendo il santuario) ha raggiunto il massimo; oppure
 +
      - qualcuno sta attraversando il ponte in direzione opposta; oppure
 +
      - qualcuno sta attendendo di attraversare nel senso opposto */
 +
if (crossing[dir] == MAXPONTE ||
 +
    (dir == Go && visiting + crossing[dir] == MAXSANTUARIO) ||
 +
    crossing[1 - dir] > 0 ||
 +
    waiting[1 - dir] > 0)
 
{
 
{
/* Se - il numero di persone sul ponte ha raggiunto il massimo; oppure
+
waiting[dir]++;
      - qualcuno sta attraversando il ponte in direzione opposta; oppure
+
ok[dir].wait();
      - qualcuno sta attendendo di attraversare nel senso opposto */
+
waiting[dir]--;
if (numP == MAXPONTE || (toS && numP > 0) || waitingP > 0)
+
}
{
+
crossing[dir]++;
// Mi fermo e attendo di essere sbloccato
+
 
waitingS++;
+
if (dir == Back)
okS.wait();
+
visiting--;
waitingS--;
+
}
 +
 
 +
procedure entry esciponte(dir)
 +
{
 +
crossing[dir]--;
 +
 
 +
if (dir == Go)
 +
visiting++;
 +
 +
// [Case 1] Nessuno sta attraversando il ponte
 +
if (crossing[dir] == 0)
 +
ok[1 - dir].signal();
 +
// [Case 2] Qualcuno sta attraversando il ponte
 +
else
 +
ok[dir].signal();
 +
}
 +
}
 +
</syntaxhighlight>
 +
-TomOgn
 +
 
 +
 
 +
<syntaxhighlight lang="C">
 +
monitor santuario{
 +
#define ANDATA 0
 +
#define RITORNO 1
 +
 +
int waiting[2];
 +
int crossing[2];
 +
condition oktoenter[2];
 +
int count; /* persone dentro al santuario */
 +
 +
procedure entry entraponte(int dir){
 +
if (dir == ANDATA){
 +
if (crossing[1-dir] > 0 || crossing[dir] >= MAXPONTE || cout+crossing[dir] >= MAXSANTUARIO){
 +
waiting[dir]++;
 +
oktoenter[dir].wait();
 +
waiting[dir]--;
 +
}
 +
}
 +
else {
 +
if (crossing[1-dir] > 0 || crossing[dir] >= MAXPONTE){
 +
waiting[dir]++;
 +
oktoenter[dir].wait();
 +
waiting[dir]--;
 
}
 
}
numP++;
 
numS--;
 
 
}
 
}
// [Case 2] La persona vuole andare al santuario
+
crossing[dir]++;
 +
if ((crossing[dir]+count < MAXSANTUARIO) && crossing[dir] < MAXPONTE)
 +
oktoenter[dir].signal();
 +
}
 +
 +
procedure entry esciponte(int dir){
 +
crossing[dir]--;
 +
if (dir == ANDATA){
 +
count++;
 +
if (count+crossing[dir] < MAXSANTUARIO) /* voi che siete in attesa andate sul ponte */
 +
oktoenter[dir].signal();
 +
}
 
else
 
else
{
+
count--;
/* Se - il numero di persone sul ponte ha raggiunto il massimo; oppure
+
      - il numero di persone nel santuario ha raggiunto il massimo; oppure
+
if (crossing[dir] == 0)
      - qualcuno sta attraversando il ponte in direzione opposta; oppure
+
oktoenter[1-dir].signal();
      - qualcuno sta attendendo di attraversare nel senso opposto */
+
}
if (numP == MAXPONTE || numP + numS == MAXSANTUARIO || (!toS && numP > 0) || waitingS > 0)
+
}
{
+
</syntaxhighlight>
// Mi fermo e attendo di essere sbloccato
+
Gabriele & Giulia (se non va colpa di Gabriele)
waitingP++;
+
 
okP.wait();
+
 
waitingP--;
+
 
 +
 
 +
 
 +
<syntaxhighlight lang="C">
 +
 
 +
monitor santuario{
 +
int CurrentDir /* 0 = arriving , 1 = leaving */
 +
int crossing
 +
condition oktoenter
 +
condition oktoleave
 +
//queue enter
 +
//queue ponte
 +
//queue leave
 +
int fidelis /* fedeli nel tempio */
 +
 
 +
procedure entry entraponte(CrossingDir){
 +
if(CrossingDir != CurrentDir){
 +
if(CrossingDir == 0){
 +
//enter.enqueue()
 +
oktoenter.wait()
 +
//enter.dequeue()
 +
}
 +
if(CrossingDir == 1){
 +
//leave.enqueue()
 +
oktoleave.wait()
 +
//leave.dequeue()
 +
}
 +
}
 +
if(CrossingDir == 0){
 +
if(fidelis == MAXSANTUARIO || crossing == MAXPONTE){
 +
//ponte.enqueue()
 +
oktoenter.wait()
 +
//ponte.dequeue()
 +
}
 +
fidelis++
 +
crossing++
 +
}
 +
if(CrossingDir == 1){
 +
if(crossing == MAXPONTE){
 +
//ponte.enqueue()
 +
oktoleave.wait()
 +
//ponte.dequeue()
 
}
 
}
numP++;
+
fidelis--
 +
crossing++
 
}
 
}
 
}
 
}
  
procedure entry esciponte(bool goingBack)
+
precedure entry esciponte(CrossingDir){
{
+
crossing--
numP--;
+
if(crossing == 0){
/* Se la persona ha raggiunto il santuario */
+
if(CrossingDir == 0){
if (!goingBack)
+
if(fidelis < MAXSANTUARIO /*&& !enter.isempty()*/){
numS++;
+
oktoenter.signal()
+
}
/* Se nessuno sta attraversando il ponte */
+
else{
if (numP == 0)
+
CurrentDir = 1 - CurrentDir
{
+
oktoleave.signal()
// [Case 1] L'ultimo ad attraversare tornava indietro
+
}
if (goingBack)
 
{
 
/* Se esiste, attivo la persona che per prima si era messa
 
  in attesa per la direzione opposta */
 
if (waitingP > 0)
 
okP.signal();
 
else
 
okS.signal();
 
 
}
 
}
// [Case 2] L'ultimo ad attraversare andava al santuario
+
else{
else
+
CurrentDir = 1 - CurrentDir
{
+
oktoenter.signal()
/* Se esiste, attivo la persona che per prima si era messa
 
  in attesa per la direzione opposta */
 
if (waitingS > 0)
 
okS.signal();
 
else
 
okP.signal();
 
 
}
 
}
 +
}
 +
 +
}
 +
 +
 +
santuario{
 +
crossing = 0
 +
CurrentDir = 0
 +
fidelis = 0
 +
}
 +
}
 +
</syntaxhighlight>
 +
Fede & Mirko
 +
 +
 +
 +
 +
 +
<syntaxhighlight lang="C">
 +
 +
 +
monitor santuario {
 +
condition okpassa; // vai sul ponte secondo metodo FIFO
 +
int turn=2;        // turno di attraversamento
 +
int visitatori[2];  // contatori andata ritorno
 +
visitatori[0]=0;
 +
visitatori[1]=0;
 +
int fedeli=0;
 +
int i=0;
 +
Queue q;            // coda dei visitatori in attesa
 +
 +
procedure entry entraponte(dir){
 +
/* se il turno è della direzione opposta o
 +
i visitatori in transito sono MAXPONTE o
 +
la coda non è vuota aspetta */
 +
if( (dir==0 && fedeli==MAXSANTUARIO ) || turn==(1-dir) || visitatori[dir]==MAXPONTE || !q.empty()){
 +
q.enqueue(dir);      // inserisci in coda
 +
okpassa.wait();      // aspetta
 +
if( q.head()==dir && (visitatori[dir] + i) < (MAXPONTE - 1) ){  // questa condizione
 +
                        i++;
 +
q.dequeue();   // mi serve per far passare
 +
okpassa.signal();   // MAXPONTE visitatori nella direzione
 +
} // in attesa quando nella direzione opposta
 +
i=0;         // i visitatori in transito erano N         
 +
}
 +
turn=dir;          // setto il turno della direzione
 +
visitatori[dir]++;  //incremento visitatori in transito
 +
if(dir==0){fedeli++;}
 +
if(dir==1){fedeli--;}
 +
}
 +
 +
 +
procedure entry esciponte(dir){
 +
visitatore[dir]--;          //decremento visitatori in transito
 +
/* se il primo visitatore in attesa va nella stessa direzione
 +
di chi è uscito può entrare sul ponte poichè questo
 +
si verifica solo se il visitatore uscito era il numero N
 +
o il visitatore che esce è l'ultimo fa passare il primo in attesa
 +
che sarà sicuramente della direzione opposta */     
 +
primo = (dir == 0 && fedeli < MAXSANTUARIO) && ( q.head()==0 || visitatori[0]==0 ))
 +
secondo = (dir == 1 && (q.head()==0 || visitatori[1]==0 )
 +
 +
      if(primo || secondo){                                             
 +
              if(visitatore[dir]==0){
 +
                turn=2;  // ponte vuoto
 +
                }
 +
q.dequeue();
 +
okpassa.signal();    // causa il passaggio sul ponte
 +
                    //  del primo visitatore in attesa
 +
    // (secondo una politica FIFO)
 +
}
 +
     
 +
}
 +
 +
</syntaxhighlight>
 +
Alessandro
 +
 +
<syntaxhighlight lang="C">
 +
#define ANDARA 0;
 +
#define RITORNO 1;
 +
monitor santuario{
 +
int cross;
 +
condition oktocross[2];
 +
int fidelis;
 +
entraponte(dir){
 +
if( cross != 0 || (dir == 0 && MAXSANTUARIO == fidelis)){
 +
wait[dir]++;
 +
oktocross[dir].wait();
 +
wait[dir]--;
 +
}
 +
cross++;
 +
if(dir == 0){
 +
fidelis++;
 +
if(cross < MAXPONTE && MAXSANTUARIO > fidelis){
 +
oktocross[dir].signal;
 +
}
 +
}else{
 +
fidelis--;
 +
if(cross < MAXPONTE){
 +
oktocross[dir].signal;
 +
}
 +
}
 +
}
 +
esciponte(dir){
 +
cross--;
 +
if(cross == 0 && MAXSANTUARIO == fidelis){
 +
oktocross[RITORNO].signal();
 +
}else if(cross == 0 && wait[1-dir]){
 +
oktocross[1-dir].signal();
 +
}else if(cross == 0){
 +
oktocross[dir].signal();
 
}
 
}
 
}
 
}
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
-Midolo

Latest revision as of 19:05, 1 June 2014

http://www.cs.unibo.it/~renzo/so/compiti/2012-05-24.tot.pdf

monitor santuario
{
#define ANDATA 0
#define RITORNO 1 
condition oktoenterponte, oktoexitponte ;
int waiting, crossing, medita ;

procedure entry enterponte(ANDATA)
  {
		
	if ( crssing(ritorno) > = 0 || crossing(ANDATA) > maxSantuario || waiting (RITORNO)>0 )     # per evitare deadlock
										     # deve essere maxSantuario >= maxPonte														
		waiting (ANDATA)++ ;						     # crossing(ANDATA) >= maxSantuario															
		oktoenterponte(ANDATA).wait();
		waiting(ANDATA)-- ;
	crossing(ANDATA)++ ;
  }

procedure entry exitponte(ANDATA)         # Entra nel santuario
  {
    if ( medita == maxSantuario )
		oktoexitponte(ANDATA).wait() ;
	 crossing(ANDATA)--;
	 medita++ ;
	 if (waiting(RITORNO) > 0 ) && (crossing(ANDATA)==0)
		oktoenterponte(RITORNO).signal();
	 oktoenterponte(ANDATA).signal();
  }

rocedure entry enterponte(RITORNO)       # Esci dal santuario
  {
    if (crossing(ANDATA)>0 || crossing(RTORNO) >= maxPonte)
	    wiiting(RITORNO)++;
		oktoenterponte(RITORNO).wait();
		waiting(RITORNO)--;
	medita--;
	crossing(RITORNO)++;
  }
  
procedure entry exitponte(RITORNO) 
  {
	crossing(RITORNO)--;
	if (waiting(RITORNO)>0) 
		oktoexitponte(RITORNO).signal()
	oktoenterponte(ANDATA).signal() ;
  }
}

/* Correggetemi se sbaglio.

 STARVATION : non l'ho individuata. 
             Io penso che se al santuario recitassero tutti il rosario e confessassero molti peccati, allora si. 
 DEADLOCK : se la portata del ponte era piu' grande della portata del santuario si aveva deadlock. 
           L'ho eliminato mettendo in wait se crossing(ANDATA) > maxSantuario
*/
save
monitor santuario
{
	Go = 0;               // andare al santuario
	Back = 1;             // tornare indietro
	condition ok[2];      // 2 condizioni
	crossing[2] = {0, 0}; // numero di persone sul ponte
	visiting = 0;         // numero di persone nel santuario
	waiting[2] = {0, 0};  // numero di persone in attesa

	procedure entry entraponte(dir)
	{
		/* Mi blocco se: 
		      - il numero di persone sul ponte ha raggiunto il massimo; oppure
		      - la direzione e' il santuario e il numero di visitatori 
                        (compresi quelli che stanno raggiungendo il santuario) ha raggiunto il massimo; oppure
		      - qualcuno sta attraversando il ponte in direzione opposta; oppure
		      - qualcuno sta attendendo di attraversare nel senso opposto */	
		if (crossing[dir] == MAXPONTE || 
		    (dir == Go && visiting + crossing[dir] == MAXSANTUARIO) || 
		    crossing[1 - dir] > 0 || 
		    waiting[1 - dir] > 0)
		{
			waiting[dir]++;
			ok[dir].wait();
			waiting[dir]--;
		}
		crossing[dir]++;

		if (dir == Back)
			visiting--;
	}

	procedure entry esciponte(dir)
	{
		crossing[dir]--;

		if (dir == Go)
			visiting++;
		
		// [Case 1] Nessuno sta attraversando il ponte
		if (crossing[dir] == 0)
			ok[1 - dir].signal();
		// [Case 2] Qualcuno sta attraversando il ponte
		else
			ok[dir].signal();
	}
}

-TomOgn


monitor santuario{
	#define ANDATA 0
	#define RITORNO 1
	
	int waiting[2];
	int crossing[2];
	condition oktoenter[2];
	int count; /* persone dentro al santuario */
	
	procedure entry entraponte(int dir){
		if (dir == ANDATA){
			if (crossing[1-dir] > 0 || crossing[dir] >= MAXPONTE || cout+crossing[dir] >= MAXSANTUARIO){
				waiting[dir]++;
				oktoenter[dir].wait();
				waiting[dir]--;
			}
		}
		else {
			if (crossing[1-dir] > 0 || crossing[dir] >= MAXPONTE){
				waiting[dir]++;
				oktoenter[dir].wait();
				waiting[dir]--;
			}
		}
		crossing[dir]++;
		if ((crossing[dir]+count < MAXSANTUARIO) && crossing[dir] < MAXPONTE)
			oktoenter[dir].signal();
	}
	
	procedure entry esciponte(int dir){
		crossing[dir]--;
		if (dir == ANDATA){
			count++;
			if (count+crossing[dir] < MAXSANTUARIO) /* voi che siete in attesa andate sul ponte */
				oktoenter[dir].signal();
		}
		else
			count--;
		
		if (crossing[dir] == 0)
			oktoenter[1-dir].signal();	
	}
}

Gabriele & Giulia (se non va colpa di Gabriele)



monitor santuario{
	int CurrentDir /* 0 = arriving , 1 = leaving */
	int crossing
	condition oktoenter
	condition oktoleave
	//queue enter
	//queue ponte
	//queue leave
	int fidelis /* fedeli nel tempio */

	procedure entry entraponte(CrossingDir){
		if(CrossingDir != CurrentDir){
			if(CrossingDir == 0){
				//enter.enqueue()
				oktoenter.wait()
				//enter.dequeue()
			}
			if(CrossingDir == 1){
				//leave.enqueue()
				oktoleave.wait()
				//leave.dequeue()
			}
		}
		if(CrossingDir == 0){
			if(fidelis == MAXSANTUARIO || crossing == MAXPONTE){
				//ponte.enqueue()
				oktoenter.wait()
				//ponte.dequeue()
			}
			fidelis++
			crossing++
		}
		if(CrossingDir == 1){
			if(crossing == MAXPONTE){
				//ponte.enqueue()
				oktoleave.wait()
				//ponte.dequeue()
			}
			fidelis--
			crossing++
		}
	}

	precedure entry esciponte(CrossingDir){
		crossing--
		if(crossing == 0){
			if(CrossingDir == 0){
				if(fidelis < MAXSANTUARIO /*&& !enter.isempty()*/){
					oktoenter.signal()
				}
				else{
					CurrentDir = 1 - CurrentDir
					oktoleave.signal()
				}
			}
			else{
				CurrentDir = 1 - CurrentDir
				oktoenter.signal()
			}
		}

	}


	santuario{
		crossing = 0
		CurrentDir = 0
		fidelis = 0
	}
}

Fede & Mirko



monitor santuario {
condition okpassa; // vai sul ponte secondo metodo FIFO
int turn=2;        // turno di attraversamento
int visitatori[2];  // contatori andata ritorno
visitatori[0]=0;
visitatori[1]=0;
int fedeli=0;
int i=0;
Queue q;            // coda dei visitatori in attesa

procedure entry entraponte(dir){
/* se il turno è della direzione opposta o
 i visitatori in transito sono MAXPONTE o
 la coda non è vuota aspetta */
	if( (dir==0 && fedeli==MAXSANTUARIO ) || turn==(1-dir) || visitatori[dir]==MAXPONTE || !q.empty()){
		q.enqueue(dir);      // inserisci in coda
		okpassa.wait();      // aspetta
		if( q.head()==dir && (visitatori[dir] + i) < (MAXPONTE - 1) ){  // questa condizione 
                        i++;
			q.dequeue();		   // mi serve per far passare 
			okpassa.signal();	   // MAXPONTE visitatori nella direzione
			}			// in attesa quando nella direzione opposta 
		i=0;	         		// i visitatori in transito erano N           
		}
turn=dir;           // setto il turno della direzione
visitatori[dir]++;   //incremento visitatori in transito
if(dir==0){fedeli++;}
if(dir==1){fedeli--;}
}


procedure entry esciponte(dir){
visitatore[dir]--;           //decremento visitatori in transito
/* se il primo visitatore in attesa va nella stessa direzione 
di chi è uscito può entrare sul ponte poichè questo
si verifica solo se il visitatore uscito era il numero N 
o il visitatore che esce è l'ultimo fa passare il primo in attesa
che sarà sicuramente della direzione opposta */      
 primo = (dir == 0 && fedeli < MAXSANTUARIO) && ( q.head()==0 || visitatori[0]==0 ))
 secondo = (dir == 1 && (q.head()==0 || visitatori[1]==0 )	

	      if(primo || secondo){                                               
              if(visitatore[dir]==0){
                turn=2;   // ponte vuoto
                }
		q.dequeue();
		okpassa.signal();    // causa il passaggio sul ponte 
                     //  del primo visitatore in attesa
		     //	(secondo una politica FIFO)
		}
		      
}

Alessandro

#define ANDARA 0;
#define RITORNO 1;
monitor santuario{
	int cross;	
	condition oktocross[2];	
	int fidelis;
	entraponte(dir){
		if( cross != 0 || (dir == 0 && MAXSANTUARIO == fidelis)){
			wait[dir]++;
			oktocross[dir].wait();
			wait[dir]--;
		}
		cross++;	
		if(dir == 0){
			fidelis++;
			if(cross < MAXPONTE && MAXSANTUARIO > fidelis){
				oktocross[dir].signal;
			}	
		}else{
			fidelis--;
			if(cross < MAXPONTE){
				oktocross[dir].signal;
			}
		}
	}
	esciponte(dir){
		cross--;
		if(cross == 0 && MAXSANTUARIO == fidelis){
			oktocross[RITORNO].signal();
		}else if(cross == 0 && wait[1-dir]){
			oktocross[1-dir].signal();
		}else if(cross == 0){
			oktocross[dir].signal();
		}
	}
}

-Midolo