Prova Teorica 2011.05.13

Esercizio 1

Scrivere un monitor reqq che gestisca Ncode di richieste.
I richiedenti chiamano la funzione che ha la seguente signature:
answer_t reqq.query(request_t request, int type);
Query deve fermare il processo richiedente fino a completamento della richiesta da parte di un gestore. Il valore di ritorno
e' la risposta del gestore.
Ci sono N gestori, uno per ogni tipo di richiesta, che si comportano come segue:
multiq_handler: process[i, i=0,..,N-1] {
  request_t req;
  int type;
  while (1) {
    req=reqq.getquery(i, &type);
    reqq.reply(i,handle(req, type));
  }
}
Normalmente le richieste vengono assegnate al gestore del tipo corrispondente (i==type), se non vi sono richieste di tale
tipo elabora una richiesta del tipo con la piu' lunga coda di richieste pendenti. Quando un gestore termina l'elaborazione
(funzione handle, da non implementare!) invia il risultato tramite la reply. Il valore passato alla reply deve essere restituito
al richiedente come valore di ritorno della funzione query. Se non vi sono richieste disponibili i gestori si fermano
attendendo nuove richieste.

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

monitor reqq
{
	queue Q[N];	// array di N code
	answer_t A[N];	// variabili per salvare temporaneamente le risposte dei gestori
	condition notempy[N];	// ci si fermano i gestori se la risp. coda è vuota
	condition done[N];	// ci si fermano i processi in attesa della risposta
	int n_req[N];	// num. di richieste per ogni coda
	
	answer_t query(request_t request, int type)
	{
		Q[type].enqueue(request);
		n_req[type]++;
		notempy.signal();
		done.wait();
		return A[type];
	}
	
	request_t getrequest(int i, int* type)
	{
		*type = i;
		if(n_req[N] == 0)
			notempy.wait();
		return Q[i].dequeue();
	}
	
	void reply(int type, answer_t answer)
	{
		A[type] = answer;
		done.signal();
	}
}

Ho provato a risolverlo pur non avendo ben capito una frase ("se non vi sono richieste di tale tipo elabora una richiesta del tipo con la piu' lunga coda di richieste pendenti"). Se notate errori avvisatemi!

// ------------------------------- SOLUZIONE DI Maldus ----------------------------------------
monitor reqq{
	request_t queue Q[N];	
	condition[] done = new condition[N];	
	condition notempty;	// una sola condizione per controllare quando la coda delle richieste è vuota;
	answer_t A[N];
	int longest;

	reqq(){
		longest = 0 ;
	}

	procedure entry answer_t query( request_t request, int type){
		Q[type].enqueue(request);
		if( Q[type].lenght() > Q[longest].lenght() ) longest = type;
		notempty.signal();
		done[type].wait();
		return A[type];
	}

	procedure entry request_t getquery( int i, int* type){
		if( Q[i].empty() ){
			if( longest == 0 ) notempty.wait();
			i = longest;
		}
		*type = i ;
		return Q[i].dequeue();
	}

	procedure entry void reply( int type, answer_t answer){
		A[type] = answer;
		done.signal();
	}

Interpreto la frase "se non vi sono richieste di tale tipo elabora una richiesta del tipo con la piu' lunga coda di richieste pendenti" considerando appunto il tipo per il quale ci sono più richieste ( se quello specificato invece non ne ha) nella funzione getquery: in quest'ottica ho pensato che la condizione notempty dovesse essere singola, perchè se un gestore può gestire anche una richiesta diversa dal tipo specificato, non importa quale richiesta viene aggiunta. Per il resto è praticamente identico alla soluzione di MV.

Esercizio 2

Facendo uso di semafori ordinari implementare le funzioni lifocs_enter e lifocs_exit che realizzino una critical section LIFO.
I processi per usare la critical section LIFO usano il seguente protocollo:
lifocs_enter()
.... codice critico
lifocs_exit()
quando un processo rilascia la sezione critica e ci sono processi in attesa di entrare, deve venir assegnata la sezione critica al processo che ha fatto l'ultima richiesta (in ordine di tempo).

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

// la cosa più semplice che mi è venuta in mente è di allocare dinamicamente uno stack di semafori
shared Stack<Semaphore> S = new Stack<Semaphore>();
shared Semaphore mutex = new Semaphore(1);
shared int n_proc = 0;

lifocs_enter()
{
	mutex.P();
	if(n_proc++ == 0)
	{
		mutex.V();
	}
	else
	{
		Semaphore sem = new Semaphore(0);
		S.push(sem);
		mutex.V();
		sem.P();
	}
}

lifocs_exit()
{
	Semaphore sem;
	mutex.P();
	if(--n_proc == 0)
	{
		mutex.V();
	}
	else
	{
		sem = S.pop();
		mutex.V();
		sem.V();
		free(sem);
	}
}

Nota di Maldus: se nella funzione lifocs_exit rilascio la mutua esclusione prima di chiamare la V() sul semaforo che era in cima secondo me c'è il pericolo che tra le due istruzioni si inserisca un'altra lifocs_exit che invece arrivi fino in fondo, svegliando così il penultimo processo piuttosto che l'ultimo sulla pila. La soluzione è fare passaggio del testimone: la lifocs_exit non rilascia la mutua esclusione, lasciando l'onere di farlo alla lifocs_enter, immediatamente dopo la chiamata a sem.P()

Esercizio 3

Un servizio di message passing a canale prevede che ogni spedizione e ricezione di un messaggio faccia riferimento a “canale” e non ad un processo.
L'interfaccia e' la seguente:
  n=channel_join_create(id); /* crea un canale con l'id specificato se non esiste, altrimenti incrementa il numero dei processi che stanno usando il canale, restituisce il numero di processi che condividono il canale. l'operazione e' atomica */
  channel_send(id,msg); /* spedisce in modo asincrono un messaggio sul canale id */
  msg=channel_receive(id); /* riceve un messaggio sul canale specificato, se piu' processi si fermano in attesa di un messaggio dallo stesso canale, ogni messaggio viene recapitato al processo che per primo ha richiesto la channel_receive */
  channel_leave_delete(id); /* decrementa il numero dei processi utilizzatori del canale, il canale viene cancellato
quando non ha piu' utilizzatori. L'operazione e' atomica. */
Implementare un supporto per sezioni critiche che faccia uso del message passing a canale. (le funzioni da implementare sono csenter, csexit).

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

const int ID = 1;	// si utilizza un unico canale

void cs_enter()
{
	// se c'è almeno un altro processo si mette in attesa di un messaggio di via libera, altrimenti semplicemente crea il canale
	if(channel_join_create(ID) > 1)
		channel_receive(ID);
}

void cs_exit()
{
	// libera il primo processo in attesa di receive sul canale
	// (si suppone che un messaggio spedito su un canale vuoto venga semplicemente perduto)
	channel_send(ID,"go");
	channel_leave_delete(ID);
}