Prova Teorica 16-07-2014

scrivere il monitor mMbb che realizzi un meccanismo di un minmax bounded buffer.
Dopo le prime MIN operazioni di scrittura, un minmax bounded buffer deve sempre avere almeno MIN elementi e mai piu' di MAX
elementi (e' quindi limitato sia nell'ampiezza massima, sia nell'ampiezza minima).
Le funzioni (procedure entry) read e write del minmax bounded buffer hanno gli stessi argomenti e valori di ritorno di quelle del producer/consumer o del bounded buffer ordinario.

Soluzione di Stefano Zaniboni

/*esercizio 1*/

monitor mMbb{
	object[] buffer; //spazio di memorizzazione
	
	final int MAXELEM; // numero massimo di elementi che ci possono essere nel buffer
	final int MINELEM; //numero minimo di elementi --> numero di scritture minime
	
	condition okW; // dove mi fermo se non posso scrivere
	condition okR; // dove mi fermo se non posso leggere

	int count; // elementi presenti nel buffer
	int front;   // contatore al elemento prodotto
	int rear;   // contatore al elemento consumato	
	

	mMbb(){
		 buffer = new Object[MAXELEM];
    	count = rear = front = 0;
	}


	procedure entry object read(){
		if ((count < MINELEM))  //se il buffer e' pieno oppure non ci sono min elem chiamo la wait
    		     okR.wait();
  		eltype val = buffer[rear]; // assegno al val l'elemento che ho letto e poi aggiorno rear
		rear = ((rear + 1) % (MAXELEM -1 ));  // aggiorno rear;
		count--; // decremento count per dire che ho consumato un elemento
  		okW.signal(); // qui faccio signal sui produttori che adesso possono scrivere
  		return retval;
	}
	procedure entry void write(int val){
		if (count == buffer.length) //se il buffer e' pieno mi fermo
    		      okW.wait();
  		buffer[front] = val; //scrivo elemento
  		count++; //aggiorno i prodotti disponibili
  		front = ((front+1)%(MAXELEM - 1)); // aggiorno il contatore front a puntare nella prossima posizione

  		okR.signal();
	}

}

Esercizio c.2

 Facendo uso di semafori scrivere la funzione rendezvous che consenta ai processi di sincronizzarsi secondo le seguenti specifiche:
– Ogni processo indica come parametro della funzione rendezvous con quanti altri processi vuole sincronizzarsi.
– M processi che chiamano la rendezvous con parametro N rimangono bloccati se M<N.
– Quando l'N-mo processo richiama la rendezvous specificando N come parametro, lui e gli N-1 sospesi devono proseguire nelle propria esecuzione

// ------------------------- SOLUZIONE DI MV -------------------------

void rendezvous(int N)
{
	struct S { Semaphore sem; int N; int M };
	
	static List<struct S> L = new List<struct S>();
	static Semaphore mutex = new Semaphore(1);
	
	if(N <= 1)	// se N==1 significa che non vuole sincronizzarsi
		return;	// se N<1 non ha senso => esce dalla funzione
	
	bool trovato = false;
	mutex.P();	// prende la mutua esclusione per evitare incoerenze
	// scorre la lista in cerca di un semaforo per N
	for(List<struct S> el = L.head(); !L.last(el) && !trovato; el = L.next(el) )
		if(el.content.N == N)	// se esiste
		{
			trovato = true;
			if(el.content.M == N-1)	// se è l'N-esimo processo
			{
				while(el.content.M)	// sblocca tutti gli altri
				{
					el.content.sem.V();
					el.content.M--;
				}
				mutex.V();
			}
			else		// altrimenti si mette in attesa
			{
				el.content.M++;
				mutex.V();
				el.content.sem.P();
			}
			break;
		}
	
	if(!trovato)	// se non esiste lo crea
	{
		// NB: ho ancora la mutua esclusione
		struct S s;
		s.N = N;
		s.M = 1;
		s.sem = new Semaphore(0);
		L.insert_tail(S)	// inserisce nella lista (in coda)
		
		mutex.V():
		// si mette in attesa sul semaforo appena creato (NB: N!=1)
		L.tail().content.sem.P();
	}
}

/* NOTA: gli elementi della lista non vengono deallocati una volta liberato
	il semaforo; questo perchè è ancora possibile una race condition (rara)
	nel caso in cui un processo P1 stia per inserirsi su un semaforo già esistente
	(ha appena fatto mutex.V() ) e un altro P2 riesca ad entrare nel ciclo e
	liberare tutti => P2 effettua una V in più e P1 esce subito dalla P
*/