Prova teorica 2014.07.16

Testo: [1]

Esercizio c.1

/*
 * Esercizio c.1: 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.
 */
#define MIN
#define MAX
#define SIZE // con SIZE >= MAX

monitor mMbb{
	
	generic_type bb[];
	int front, rear, count;
	condition R, W;
	
	void mMbb(void){
		bb = new generic_type[SIZE];
		front = rear = count = 0;
	}
	
	procedure_entry generic_type read(){
		while(count < MIN)	// Controllo che il buffer abbia MIN elementi per poter leggere
			R.wait();
		
		generic_type ret = bb[rear];
		count--;
		rear = (rear + 1) % SIZE;
		W.signal();
		return ret;
	}
	
	procedure_entry write(generic_type c){
		while(count >= MAX)	// Controllo che il buffer non abbia MAX elementi per poter scrivere
			W.wait();
		
		bb[front] = c;
		count++;
		front = (front + 1) % SIZE;
		R.signal();	
	}
	
}

S.G (talk) 17:21, 2 December 2016 (CET)

Non è fifo. Perché? Renzo (talk) 07:43, 3 December 2016 (CET)

Nel caso in cui MIN vale 3 e arrivino tre processi lettori nel seguente ordine, L1, L2, L3, avremmo che la coda di R è la seguente:

R: L1, L2, L3

Ora arriva un processo scrittore S1, viene eseguito liberando un lettore (R.signal) cioè L1. A questo punto L1 riprende la sua esecuzione, riesegue il ciclo e rientra nello stato di attesa. Quindi ora la coda di R è la seguente:

R: L2, L3, L1

Si potrebbe risolvere il problema modificando le funzioni write e read nel seguente modo:

procedure_entry generic_type read(){
		if(count < MIN)	// Controllo che il buffer abbia MIN elementi per poter leggere
			R.wait();
		
		generic_type ret = bb[rear];
		count--;
		rear = (rear + 1) % SIZE;
		if(count < MAX)
			W.signal();
		return ret;
	}
	
	procedure_entry write(generic_type c){
		if(count >= MAX)	// Controllo che il buffer non abbia MAX elementi per poter scrivere
			W.wait();
		
		bb[front] = c;
		count++;
		front = (front + 1) % SIZE;
		if(count > MIN)
			R.signal();	
	}

S.G (talk) 10:37, 3 December 2016 (CET)

Esercizio c.2

/*
 * 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
 */

struct S {
	Semaphore sem;
	int N; // parametro della funzione rendezvous con quanti altri processi vuole sincronizzarsi
	int I; // Contatore dei processi che richiamano rendezvous con paramentro N
}

List<S> listS = new List[]; // Lista di possibili semafori

Semaphore mutex = new Semaphore(1);		// Variabile che consente la mutua esclusione

rendevouz(int n){
	mutex.P();	// Ottengo la mutua esclusione
	
	find = FALSE;
	for(s in listS){	// Cerco il semaforo nella lista
		if(s.N == n){	
			find = TRUE;
			break;
		}
	}
	if(find == FALSE){	// se non è presente nella lista lo creo
		struct S s;
		s.sem = new semaphore(0);
		s.N = n;
		s.I = 0;
		listS.insert(s);
	}
	
	s.I++;
	if(s.I == s.N){		// Quando l'N-mo processo richiama la rendezvous specificando N come parametro
		while(s.I--)	// lui e gli N-1 sospesi devono proseguire nelle propria esecuzione
			s.sem.V();
	}
	else if(s.I < s.N){	// M processi che chiamano la rendezvous con parametro N rimangono bloccati se M<N
		s.sem.P();
	}
	
	mutex.V();	// Rilascio la mutua esclusione
}

Ho qualche dubbio su questa soluzione, riguardo la linea presente l'istruzione s.sem.P(), il processo viene immediatamente bloccato? Se si dovrei rilasciare la mutua esclusione prima quindi? S.G (talk) 16:43, 3 December 2016 (CET)