ProvaTeorica 2012.07.16

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