Prova teorica 2014.06.03

Testo: [1]

Esercizio c.1

Soluzione di G.C.

int wait_enter[N][2] = {0,0,0,0,0,0,0,0,0,...,0}
int wait_exit[N] = {0,0,0, ... , 0}

int n = 0;

monitor sabelev{
	
	int current_floor = NULL;
	int current_dir = NULL;
	condition ok2enter[N][2], ok2exit[N];
	procedure entry atfloor(floor, dir){
		current_floor = floor;
		current_dir = dir;
		if (wait_enter[floor][dir]>0){
			ok2enter[floor][dir].signal();
		}
		if (wait_exit[floor]>0){
			ok2exit[floor].signal();
		}
		//elevator is moving from floor to floor+1 (or -1)
		current_floor = NULL;
	}
	procedure entry enter(from, to){
		int dir = from>to ? down : up;
		if (current_floor != from) || (current_dir != dir){
			wait_enter[from][dir]++;
			ok2enter[from][dir].wait();
			wait_enter[from][dir]--;
		}
		//process enter in the elevator
		n++;
		//wakes up the processes that are in this floor and going in its direction
		if (wait_enter[from][dir]>0){
			ok2enter[from][dir].signal();
		}
	}
	procedure entry exit(from,to){
		if (current_floor != to){
			wait_exit[to]++;
			ok2exit[to].wait();
			wait_exit[to]--;
		}
		//exit from the elevator
		n--;
		//wakes up the processes that have to exit on this floor
		if (wait_exit[to]>0){
			ok2exit[to].signal();
		}
	}
}

Esercizio c.2

Siano dati 4 processi:

prchar=”IATL”
Process i: i=range(4)
while True:
 sync(i)
 print(prchar[i])

Scrivere la funzione sync in modo che in un sistema di processi a memoria privata, usando message passing asincrono, l'unico output possibile sia la stringa di lunghezza infinita: “ITALIAITALIAITALIA....”

Soluzione di S.G

Solo il processo 2 (lettera T) permette di iniziare la sincronizzazione dei processi.

Oltre al processo 2 anche il processo 1 (lettera A) permette di riavviare la sequenza.

Nella descrizione di seguito chiameremo T il processo incaricato a stampare tale lettera, e cosi anche per gli altri.

def sync(i):
	if i == 0:			# Processo 0 (processo I)
		mittente = recv(*)			# Aspetto un messaggio da T, L o A
		if mittente == 2 or mittente == 1:	# Se il mittente è il processo T o A (avvio o riavvio sequenza)
			send(2, 0)			# Invio un messaggio al processo T
		
		elif mittente == 3:	# Se il mittente è il processo L
			send(1, 0)	# Invio un messaggio al processo A
	
	elif i == 1:		# Processo 1 (processo A)
		mittente = recv(*)	# Aspetto un messaggio dal processo T o I
		if mittente == 0:	# Se il mittente è il processo I
			send(0, 1)	# Invio un messaggio al processo I (riavvio la sequenza)
		elif mittente == 2:	# Se il mittente è il processo T
			send(3, 1)	# Invio un messaggio al processo L
	
	elif i == 2:		# Processo 2 (processo T)
		send (0, 2)		# Invio un messaggio al processo I (Avvia la sequenza)
		mittente = recv(0)	# Aspetto un messaggio dal processo I
		if mittente == 0:	# Se il mittente è il processo I
			send(1, 2)	# Invio un messaggio al processo A
	
	elif i == 3:		# Processo 3 (processo L)
		mittente = recv(1)	# Aspetto un messaggio dal processo A
		if mittente == 1:	# Se il mittente è il processo A
			send(0, 3)	# Invio un messaggio al processo I

Una volta avviato T invierà un messaggio a I e si bloccherà in attesa di I.

Il processo I in attesa riceverà un messaggio da T, allora sbloccherà T e stamperà I.

A questo punto il processo T invierà un messaggio ad A, e stamperà T.

A aspetterà messaggi da più mittenti, in questo caso riceverà un messaggio da T, invierà un messaggio ad L e stamperà A.

L aspetterà il messaggio da A che appena ricevuto invierà un messaggio ad I, e stamperà L.

Il processo I in attesa, riceverà un messaggio da L sbloccandosi invierà un messaggio ad A e stamperà I.

A ancora una volta in attesa, riceverà un messaggio da I, risponderà ad I e stamperà A.

I riceverà un messaggio da A, e riavvierà la sequenza. S.G (talk) 10:35, 4 December 2016 (CET)

Soluzione di FedericoB

Penso che la soluzione di S.G. sia sbagliata in quanto appena si fa una send un processo bloccato su una receive viene sbloccato. Quindi per esempio verrà stampato T prima di I. L'idea è di sbloccare T alla seconda chiamata di sync(0). Per sapere il numero della chiamata si può utilizzare un contatore statico, che mantiene il suo valore tra le chiamate di funzione e viene inizializzata a 0.

sync(i)
	if i==0: #processo "I"
		if (count=1):
			send(2)
			recv(3)
		elif: (count=2)
			send(1)
			recv(1)
			count = 0
	elif i==1: #processo "A"
		if (count==0)
			recv(2)
		elif (count=1):
			send(3)
			recv(0)
		elif: (count=2)
			send(0)
			recv(2)
			count=0
	elif i==2: #processo "T"
		if (count==0)
			recv(0)
		elif (count=1):
			send(1)
			recv(0)
			count=0
	elif i==3: #processo "L"
		if (count==0)
			recv(1)
		elif (count=1):
			send(0)
			recv(1)
			count=0
	count++

Sequenzialemente le chiamate sono in quest'ordine

sync(0) non fa nulla
print(I)
sync(0) count=1 manda messaggio a T e si bloccherà in attesa di un messaggio da L
sync(2) count=0 aspetta messaggio da I
print(T)
sync(2) count = 1 manda messaggio a A e setto count=0
sync(1) count = 0 aspetta messaggio da T
print(A)
sync(1) count = 1 manda messaggio a L e aspetto un messaggio da I
sync(3) count=0 aspetta messaggio da A
print(L)
sync(3) count = 1 manda messaggio a I e setto count=0
print(I) #si sblocca per il messaggio da L
sync(0) count=2 mando un messaggio ad A e mi blocco in attesa di un messaggio da A quando lo ricevo metto count=0
print(A)
sync(1) count=2 mando messaggio a I e aspetto messaggio da T e quando mi arriverà imposto count=0

Ma in realtà è tutto in parallelo quindi:

Processo "I"	Processo "A"	Processo "T"	Processo "L"
sync(0) non fa nulla print(I) sync(0) count=1 manda messaggio a T e si bloccherà in attesa di un messaggio da L print(I) #si sblocca per il messaggio da L sync(0) count=2 mando un messaggio ad A e mi blocco in attesa di un messaggio da A quando lo ricevo metto count=0	sync(1) count = 0 aspetta messaggio da T print(A) sync(1) count = 1 manda messaggio a L e aspetto un messaggio da I print(A) sync(1) count=2 mando messaggio a I e aspetto messaggio da T e quando mi arriverà imposto count=0	sync(2) count=0 aspetta messaggio da I print(T) sync(2) count = 1 manda messaggio a A e setto count=0	sync(3) count=0 aspetta messaggio da A print(L) sync(3) count = 1 manda messaggio a I e setto count=0