Difference between revisions of "ProvaTeorica 2012.07.16"

From Sistemi Operativi
Jump to navigation Jump to search
 
(10 intermediate revisions by 5 users not shown)
Line 1: Line 1:
 
[http://www.cs.unibo.it/~renzo/so/compiti/2012-07-16.tot.pdf Link Testo]
 
[http://www.cs.unibo.it/~renzo/so/compiti/2012-07-16.tot.pdf Link Testo]
−
<h2>Esercizio C.2</h2>
+
 
 +
<h2>Esercizio C.1</h2>
  
 
Mia Soluzione:
 
Mia Soluzione:
Line 53: Line 54:
 
monitor limcol {
 
monitor limcol {
 
condition oktoenter
 
condition oktoenter
 +
condition oktoexit
 
int running[2] // numero di processi rossi [0] e blu [1] in esecuzione
 
int running[2] // numero di processi rossi [0] e blu [1] in esecuzione
−
queue waiting // coda dei colori dei processi in attesa
+
queue waiting /* coda delle coppie (colore,azione) dei processi in attesa di entrare (azione==1)
 +
o uscire (azione==-1) */
 
 
−
/* restituisce true se aggiungendo un processo del colore passato viene rispettato il 75%
+
/* restituisce true se aggiungendo o rimuovendo (in base a i) un processo del colore passato
−
dei processi di un colore */
+
viene rispettato il 75% dei processi di un colore */
−
bool morethan75p(colore) {  
+
bool morethan75p(colore, int i) {  
−
return (running[colore]+1>=running[1-colore]*3 || (running[colore]+1)*3<=running[1-colore])
+
return (running[colore]+i>=running[1-colore]*3 || (running[colore]+i)*3<=running[1-colore])
 
}
 
}
 
 
−
// risveglia un processo del colore passato se è possibile farlo
+
// risveglia il processo in testa alla coda waiting se è possibile farlo
 
void checkwakeup() {
 
void checkwakeup() {
 
if (waiting.empty() == false) {
 
if (waiting.empty() == false) {
−
colore=waiting.head() // head resituisce l'elemento in testa senza rimuoverlo
+
colore,azione = waiting.head() // head resituisce l'elemento in testa senza rimuoverlo
−
if (morethan75p(colore)) {  
+
if (morethan75p(colore,azione)) {
 
waiting.dequeue()
 
waiting.dequeue()
−
oktoenter.signal()
+
if (azione == 1)
 +
oktoenter.signal()
 +
else
 +
oktoexit.signal()
 
}
 
}
 
}
 
}
 
}
 
}
−
+
 
procedure entry enter(colore) {
 
procedure entry enter(colore) {
−
if (morethan75p(colore)==false) {
+
if (morethan75p(colore,1)==false) {
−
waiting.enqueue(colore)
+
waiting.enqueue(colore,1)
 
oktoenter.wait()
 
oktoenter.wait()
 
}
 
}
Line 81: Line 87:
 
checkwakeup()
 
checkwakeup()
 
}
 
}
−
+
 
procedure entry exit(colore) {
 
procedure entry exit(colore) {
 +
if (morethan75p(colore,-1)==false) {
 +
waiting.enqueue(colore,-1)
 +
oktoexit.wait()
 +
}
 
running[colore]--
 
running[colore]--
 
checkwakeup()
 
checkwakeup()
 
}
 
}
 
}
 
}
−
 
−
/* la politica FIFO impedisce che si verifichi starvation, perché nel caso pessimo un processo
 
−
che vuole entrare dovrà attendere fino a che tutti quelli in esecuzione terminino */
 
 
</syntaxhighlight>
 
</syntaxhighlight>
 
Daniele Cortesi
 
Daniele Cortesi
Line 184: Line 191:
 
oktoenter[1-color].signal();
 
oktoenter[1-color].signal();
 
}
 
}
−
}
+
}
−
 
  
 
/*
 
/*
Line 193: Line 199:
 
</syntaxhighlight>
 
</syntaxhighlight>
 
Pir@t@
 
Pir@t@
 +
 +
 +
 +
<syntaxhighlight lang="C">
 +
#DEFINE BLUE 0
 +
#DEFINE RED 1
 +
monitor limcol{
 +
condition ok;
 +
int numcolor[2];
 +
Queue q;
 +
int i=1;
 +
procedure entry enter(color){
 +
if((numcolor[color] + 1 < float((tot+1)*(75/100))  &&
 +
  numcolor[color] + 1 >= float((tot+1)*(25/100))) ||
 +
  !q.empty() )
 +
{
 +
q.enqueue(color);
 +
ok.wait();
 +
i++;
 +
if(!q.empty()){
 +
          if(numcolor[q.head()] + i >= float((tot+i)*(75/100)) ||
 +
  numcolor[q.head()] + i < float((tot+i)*(25/100)))  )
 +
{
 +
q.dequeue();
 +
ok.signal();
 +
}
 +
i=1;
 +
}
 +
}
 +
numcolor[color]++;
 +
tot++;
 +
}
 +
procedure entry exit(color){
 +
numcolor[color]--;
 +
tot--;
 +
if( numcolor[q.head()] + 1 >= float((tot+1)*(75/100))  ||
 +
    numcolor[q.head()] + 1 < float((tot+1)*(25/100)) )
 +
  {
 +
q.dequeue();
 +
ok.signal();
 +
}
 +
}
 +
</syntaxhighlight>
 +
Alessandro
 +
 +
 +
<syntaxhighlight lang="C">
 +
#define LIMIT 0.75
 +
#define RED 0
 +
#define BLUE 1
 +
 +
monitor limcol{
 +
double procNum; // numero processi all'interno del semaforo
 +
double pColourNum[2]; // numero di processi rossi [0] o blu [1]
 +
condition okToEnter;
 +
condition okToLeave;
 +
 +
procedure entry enter(colour)
 +
{ // Se ci sono processi nel semaforo && il numero dei processi del colore attuale è inferiore
 +
                // al 75% && il numero dei processi dell'altro colore è inferiore al 75% sul totale+1, wait
 +
if(procNum != 0 && (pColourNum[1-colour]/procNum+1) < LIMIT && (pColourNum[colour]/procNum) < LIMIT)
 +
{
 +
okToEnter.wait();
 +
}
 +
 +
else
 +
{
 +
procNum++;
 +
pColourNum[colour]++;
 +
 +
// Se qualcuno è in attesa di uscire e adesso le percentuali lo permettono, signal
 +
if((pColourNum[colour]/procNum-1) >= LIMIT)
 +
{
 +
okToLeave.signal();
 +
}
 +
 +
// Se qualcuno è in attesa di entrare e adesso le percentuali lo permettono, signal
 +
if((pColourNum[colour]/procNum+1) >= LIMIT)
 +
{
 +
okToEnter.signal();
 +
}
 +
}
 +
}
 +
 +
 +
procedure entry exit(colour)
 +
{
 +
// Se il numero di processi del colore attuale è inferiore al 75% sul totale+1, wait
 +
if((pColourNum[colour]/procNum-1) < LIMIT)
 +
{
 +
okToLeave.wait();
 +
}
 +
 +
else
 +
{
 +
procNum--;
 +
pColourNum[colour]--;
 +
 +
// Se qualcuno dell'altro colore è in attesa di uscire e adesso le percentuali lo permettono, signal
 +
                        if((pColourNum[1-colour]/procNum-1) >= LIMIT)
 +
                        {
 +
                                okToLeave.signal();
 +
                        }
 +
 +
}
 +
}
 +
 +
limcol
 +
{
 +
procNum = 0;
 +
pColourNum[0] = 0;
 +
pColourNum[1] = 0;
 +
}
 +
}
 +
</syntaxhighlight>
 +
Mirko
 +
 +
<syntaxhighlight lang="C">
 +
#DEFINE RED 0
 +
#DEFINE BLUE 1
 +
 +
int is_ok(int n_red,int n_blue); /*funzione is_ok: restituisce 1 se la configurazione passata in input è accettabile*/
 +
 +
 +
monitor limcol
 +
{
 +
int number[2]; /*number[i] contiene il numero di processi del colore i nella sezione limcol*/
 +
condition oktoenter[2],oktoexit[2];
 +
procedure entry enter(int colour)
 +
{
 +
if (!is_ok(number[colour]+1,number[!colour]))
 +
oktoenter[colour].wait();
 +
number[colour]++;
 +
if (is_ok(number[colour]+1,number[!colour]))
 +
oktoenter[colour].signal();
 +
if (is_ok(number[colour],number[!colour]+1))
 +
oktoenter[!colour].signal();
 +
if (is_ok(number[colour]-1,number[!colour]))
 +
oktoexit[colour].signal();
 +
if (is_ok(number[colour],number[!colour]-1))
 +
oktoexit[!colour].signal();
 +
}
 +
 +
}
 +
procedure entry exit(int colour)
 +
{
 +
if (!is_ok(number[colour]-1,number[!colour]))
 +
oktoexit[colour].wait();
 +
number[colour]--;
 +
if (is_ok(number[colour]+1,number[!colour]))
 +
oktoenter[colour].signal();
 +
if (is_ok(number[colour],number[!colour]+1))
 +
oktoenter[!colour].signal();
 +
if (is_ok(number[colour]-1,number[!colour]))
 +
oktoexit[colour].signal();
 +
if (is_ok(number[colour],number[!colour]-1))
 +
oktoexit[!colour].signal();
 +
}
 +
}
 +
</syntaxhighlight>
 +
Stefano
 +
 +
==Esercizio c.2==
 +
Per quali indici n le funzioni foo possono essere utilizzate al posto della test&set?
 +
 +
Risposta: per n = 5
 +
 +
Nella Test&Set x prende il valore di y, quindi y deve essere = booln(x,y)
 +
Andiamo a vedere per quali valori y è uguale a booln(x,y)
 +
{| border="1" class="wikitable"
 +
|-
 +
! x || y || bool0 || bool1 || bool2 || bool3 || bool4 || bool5 || bool6 || bool7 || bool8 || bool9 || bool10 || bool11 || bool12 || bool13 || bool14 || bool15
 +
|-
 +
| 0 || '''0''' || '''0''' || '''0''' || '''0''' || '''0''' || '''0''' || '''0''' || '''0''' || '''0''' || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1
 +
|-
 +
| 0 || '''1''' || 0 || 0 || 0 || 0 || '''1''' || '''1''' || '''1''' || '''1''' || 0 || 0 || 0 || 0 || '''1''' || '''1''' || '''1''' || '''1'''
 +
|-
 +
| 1 || '''0''' || '''0''' || '''0''' || 1 || 1 || '''0''' || '''0''' || 1 || 1 || '''0''' || '''0''' || 1 || 1 || '''0''' || '''0''' || 1 || 1
 +
|-
 +
| 1 || '''1''' || 0 || '''1''' || 0 || '''1''' || 0 || '''1''' || 0 || '''1''' || 0 || '''1''' || 0 || '''1''' || 0 || '''1''' || 0 || '''1'''
 +
|-
 +
|}
 +
 +
In bold sono indicati i valori per cui y = booln(x,y)
 +
L'unico caso in cui i valori sono evidenziati in ogni riga è per bool5.
 +
 +
Giulia (non sono molto sicura della soluzione, ma questo è il ragionamento che mi è sembrato più corretto)
 +
 +
==Esercizio g.1==
 +
{| border="1" class="wikitable"
 +
|-
 +
! Reference String
 +
| 1 || 2 || 3 || 4 || 5 || 6 || 4 || 5 || 6 || 3 || 2 || 1 || 3 || 2 || 1 || 6 || 5 || 4 || 6 || 5 || 4 || 1 || 2 || 3
 +
|-
 +
! Page Frame 1
 +
| 1 || 1 || 1 || 4 || 4 || 4 ||  ||  ||  || 3 || 3 || 3 ||  ||  ||  || 6 || 6 || 6 ||  ||  ||  || 1 || 1 || 1
 +
|-
 +
! Page Frame 2
 +
|  || 2 || 2 || 2 || 5 || 5 ||  ||  ||  || 5 || 2 || 2 ||  ||  ||  || 2 || 5 || 5 ||  ||  ||  || 5 || 2 || 2
 +
|-
 +
! Page Frame 3
 +
|  ||  || 3 || 3 || 3 || 6 ||  ||  ||  || 6 || 6 || 1 ||  ||  ||  || 1 || 1 || 4 ||  ||  ||  || 4 || 4 || 3
 +
|}
 +
                       
 +
The above Reference String is both FIFO, LRU and MIN compliant.
 +
 +
-TomOgn

Latest revision as of 23:34, 30 March 2014

Link Testo

Esercizio C.1

Mia Soluzione: 

#define RED 0
#define BLUE 1
//restituisce 1 se c'e piu del 75% blue o 75% di red
//restituisce 0 se non c'e una maggiornza
int media(color){
	int mediared;
	int localinto =  into;
	if (color != NULL){
		localinto[color]++;
	}
	mediared = ((100*localinto[0])/(localinto[0]+localinto[1]));
	if(mediared >=75 || mediared < 25){
		return 1;//75% di rossi o di blue
	}else{
		return 0;// non c'e maggioranza		
	}
}

monitor limcol{

	conditon oktoenter[2];
	int into[2];

	enter(color){
		if(media(color) != 1){// attendo perche' non c'e una maggioranza
			oktoenter[color].wait();
		}
		into[color]++;
	}

	exit(color){
		into[color]--;
		if(media(1-color) == 1){
			oktoenter[1-color].signal();
		}else if(media(color) == 1){
			oktoenter[color].signal();
		}
	}
}

- Midolo 


#define ROSSO 0
#define BLU 1

monitor limcol {
	condition oktoenter
	condition oktoexit
	int running[2] // numero di processi rossi [0] e blu [1] in esecuzione
	queue waiting /* coda delle coppie (colore,azione) dei processi in attesa di entrare (azione==1)
			 o uscire (azione==-1) */
	
	/* restituisce true se aggiungendo o rimuovendo (in base a i) un processo del colore passato
	viene rispettato il 75% dei processi di un colore */
	bool morethan75p(colore, int i) { 
		return (running[colore]+i>=running[1-colore]*3 || (running[colore]+i)*3<=running[1-colore])
	}
	
	// risveglia il processo in testa alla coda waiting se è possibile farlo
	void checkwakeup() {
		if (waiting.empty() == false) {
			colore,azione = waiting.head() // head resituisce l'elemento in testa senza rimuoverlo
			if (morethan75p(colore,azione)) {
				waiting.dequeue()
				if (azione == 1)
					oktoenter.signal()
				else
					oktoexit.signal()
			}
		}
	}
 
	procedure entry enter(colore) {
		if (morethan75p(colore,1)==false) {
			waiting.enqueue(colore,1)
			oktoenter.wait()
		}
		running[colore]++
		checkwakeup()
	}
 
	procedure entry exit(colore) {
		if (morethan75p(colore,-1)==false) {
			waiting.enqueue(colore,-1)
			oktoexit.wait()
		}
		running[colore]--
		checkwakeup()
	}
}

Daniele Cortesi 


define RED 0
define BLUE 1
int majorcolor = -1
int numproc[2] = 0,0
cond oktoenter[2]  //bastavano due condizioni.
cond oktoexit[2]


monitor limcol{
	procedure entry enter(COL){
		if(COL == majorcolor){
			numproc[COL]++
			if(((proc[majorcolor])*100/(numproc[COL] + numproc[1-COL] + 1)) >= 75)
				oktoenter[1-COL].signal()
		}
		else if(COL == 1-majorcolor){
			if((proc[majorcolor]*100/(numproc[COL] + numproc[1-COL] + 1)) < 75)
				oktoenter[COL].wait()
			if(majorcolor == -1)
				majorcolor == COL
			numproc[COL]++
		}
		else{
			numproc[COL]++
			majorcolor = COL
		}
	}

	procedure entry exit(COL){
		if(numproc[COL] + numproc[1-COL] == 1){
			majorcolor = -1
			numproc[COL]--
			oktoenter[1-COL].signal()
		}
		else if(COL == majorcolor){
			if(((proc[majorcolor] - 1)*100/(numproc[COL] + numproc[1-COL] - 1)) < 75){
				oktoexit[COL].wait()
			numproc[COL]--
			}
		}
		else if(COL == 1-majorcolor){
			numproc[COL]--
			if(((proc[majorcolor])*100/(numproc[COL] + numproc[1-COL] - 1)) >= 75)
				oktoexit[1-COL].signal()
		}
	}
}

Fede 


define RED 0
define BLU 1

limcol{
	/*variable*/
	int array[2] = 0,0;
	color major = -1;
	/*condition*/
	condition oktoenter[2];
	condition oktoleave[2];


	procedure entry enter( color ){
		if ( majorcolor == -1 ) 
			majorcolor = color;
		if ( majorcolor == (1-color) && newmajorcolor%(color) < 75% )
			oktoenter[color].wait();
		array[color]++; 
		if ( majorcolor == -1 )            //se un processo si risveglia nel monitor vuoto deve impostare majorcolor
			majorcolor = color;
		if ( newmajorcolor%(1-color) >= 75% )         
			oktoenter[1-color].signal();
					}

	procedure entry exit( color ){
		if ( majorcolor == color && majorcolor_less1%(color) > 75% )
			oktoleave[color].wait();
		array[color]--;
		if ( !colorsempty() )
			if ( majorcolor_less1%(color) >= 75% )
				oktoleave[1-color].signal();
		else{
			majorcolor == -1;
			oktoenter[1-color].signal();
				}
					}	 

/*
newmajorcolor%(color) calcola la nuova % del colore maggiore aggiungendo color
majorcolor_less1%(color) calcola la nuova % del colore maggiore togliendo color
*/

Pir@t@ 


#DEFINE BLUE 0
#DEFINE RED 1
monitor limcol{
condition ok;
int numcolor[2];
Queue q;
int i=1;
procedure entry enter(color){
if((numcolor[color] + 1 < float((tot+1)*(75/100))  &&
   numcolor[color] + 1 >= float((tot+1)*(25/100))) ||
   !q.empty() ) 
	{
	q.enqueue(color);
	ok.wait();
	i++;
	if(!q.empty()){
          if(numcolor[q.head()] + i >= float((tot+i)*(75/100)) ||
	   numcolor[q.head()] + i < float((tot+i)*(25/100)))  )
	{
	q.dequeue();
	ok.signal();
	}
	i=1;
	}
	}
numcolor[color]++;
tot++;
}
procedure entry exit(color){
numcolor[color]--;
tot--;
if( numcolor[q.head()] + 1 >= float((tot+1)*(75/100))  ||
    numcolor[q.head()] + 1 < float((tot+1)*(25/100)) )
  	{
	q.dequeue();
	ok.signal();
	}
}

Alessandro 


#define LIMIT 0.75
#define RED 0
#define BLUE 1

monitor limcol{
	double procNum; // numero processi all'interno del semaforo
	double pColourNum[2]; // numero di processi rossi [0] o blu [1]
	condition okToEnter;
	condition okToLeave;

	procedure entry enter(colour)
	{	// Se ci sono processi nel semaforo && il numero dei processi del colore attuale è inferiore 
                // al 75% && il numero dei processi dell'altro colore è inferiore al 75% sul totale+1, wait
		if(procNum != 0 && (pColourNum[1-colour]/procNum+1) < LIMIT && (pColourNum[colour]/procNum) < LIMIT)
		{
			okToEnter.wait();
		}

		else
		{
			procNum++;
			pColourNum[colour]++;

			// Se qualcuno è in attesa di uscire e adesso le percentuali lo permettono, signal
			if((pColourNum[colour]/procNum-1) >= LIMIT)
			{
				okToLeave.signal();
			}

			// Se qualcuno è in attesa di entrare e adesso le percentuali lo permettono, signal
			if((pColourNum[colour]/procNum+1) >= LIMIT)
			{
				okToEnter.signal();
			}
		}
	}


	procedure entry exit(colour)
	{
		// Se il numero di processi del colore attuale è inferiore al 75% sul totale+1, wait
		if((pColourNum[colour]/procNum-1) < LIMIT)
		{
			okToLeave.wait();
		}

		else
		{
			procNum--;
			pColourNum[colour]--;

			// Se qualcuno dell'altro colore è in attesa di uscire e adesso le percentuali lo permettono, signal
                        if((pColourNum[1-colour]/procNum-1) >= LIMIT)
                        {
                                okToLeave.signal();
                        }

		}
	}

	limcol
	{
		procNum = 0;
		pColourNum[0] = 0;
		pColourNum[1] = 0;
	}
}

Mirko 

#DEFINE RED 0
#DEFINE BLUE 1

int is_ok(int n_red,int n_blue); /*funzione is_ok: restituisce 1 se la configurazione passata in input è accettabile*/


monitor limcol
{
	int number[2]; /*number[i] contiene il numero di processi del colore i nella sezione limcol*/
	condition oktoenter[2],oktoexit[2];
	procedure entry enter(int colour)
	{
		if (!is_ok(number[colour]+1,number[!colour]))
			oktoenter[colour].wait();
		number[colour]++;
		if (is_ok(number[colour]+1,number[!colour]))
			oktoenter[colour].signal();
		if (is_ok(number[colour],number[!colour]+1))
			oktoenter[!colour].signal();
		if (is_ok(number[colour]-1,number[!colour]))
			oktoexit[colour].signal();
		if (is_ok(number[colour],number[!colour]-1))
			oktoexit[!colour].signal();
	}
			
	}
	procedure entry exit(int colour)
	{
		if (!is_ok(number[colour]-1,number[!colour]))
			oktoexit[colour].wait(); 
		number[colour]--;
		if (is_ok(number[colour]+1,number[!colour]))
			oktoenter[colour].signal();
		if (is_ok(number[colour],number[!colour]+1))
			oktoenter[!colour].signal();
		if (is_ok(number[colour]-1,number[!colour]))
			oktoexit[colour].signal();
		if (is_ok(number[colour],number[!colour]-1))
			oktoexit[!colour].signal();
	}	
}

Stefano

Esercizio c.2

Per quali indici n le funzioni foo possono essere utilizzate al posto della test&set?

Risposta: per n = 5

Nella Test&Set x prende il valore di y, quindi y deve essere = booln(x,y) Andiamo a vedere per quali valori y è uguale a booln(x,y)

x y bool0 bool1 bool2 bool3 bool4 bool5 bool6 bool7 bool8 bool9 bool10 bool11 bool12 bool13 bool14 bool15
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

In bold sono indicati i valori per cui y = booln(x,y) L'unico caso in cui i valori sono evidenziati in ogni riga è per bool5.

Giulia (non sono molto sicura della soluzione, ma questo è il ragionamento che mi è sembrato più corretto)

Esercizio g.1

Reference String 1 2 3 4 5 6 4 5 6 3 2 1 3 2 1 6 5 4 6 5 4 1 2 3
Page Frame 1 1 1 1 4 4 4 3 3 3 6 6 6 1 1 1
Page Frame 2 2 2 2 5 5 5 2 2 2 5 5 5 2 2
Page Frame 3 3 3 3 6 6 6 1 1 1 4 4 4 3

The above Reference String is both FIFO, LRU and MIN compliant.

-TomOgn

Retrieved from "https://so.v2.cs.unibo.it/wiki/index.php?title=ProvaTeorica_2012.07.16&oldid=528"