Prova Teorica 2009.09.18

CONCORRENZA

Esercizio 1

Operation

Urgent Stack

c[0]

c[1]

…

c[N-2]

c[N-1]

n[0]

n[1]

…

n[N-2]

n[N-1]

tot

initialization

nil

nil

nil

…

nil

nil

0

0

…

0

0

p[0]: bar(0)

p[0]

1

0

p[1]: bar(1)

p[1]

1

0

…

…

…

…

p[N-2]: bar(N-2)

p[N-2]

1

0

p[N-1]: bar(N-1)

p[N-1]

1

1

p[0]: bar(0)

p[N-1], p[0]

nil

p[1]: bar(1)

p[N-1], p[0], p[1]

nil

…

p[N-1], p[0], p[1], …

…

p[N-2]: bar(N-2)

p[N-1], p[0], p[1], …, p[N-3]

nil

0

…

…

…

p[1]: bar(1)

p[N-1], p[0]

0

p[0]: bar(0)

p[N-1]

0

p[N-1]: bar(N-1)

nill

0

Descrizione:

I processi si disattivano fino a quando tutti gli elementi dell'array <n> assumono valore maggiore di 0.

Il processo che ha assegnato l'ultimo valore riattiva il processo con indice successivo (in modo circolare), e cosi' via a cascata.

Viene popolato e consumato l'urgent stack.

Progressivamente i valori contenuti nell'array risultano diminuiti di 1.

Non necessariamente tornano a 0.

Esercizio 2

Queue recvdigest()
{
	Queue buffer;
	asend(BookMark, getpid());
	message = arecv(*);
	if (message == BookMark)
		buffer.enqueue(arecv(*));
	else
	{
		do
		{
			buffer.enqueue(message);
			message = arecv(*);
		} until (message == BookMark)		
	}
	return buffer;
}

GENERALE

Esercizio 1

Reference String	1	2	3	4	5	1	2	3	4	5	1	2	3	1	2	3	2	3	4	2	3	4	1	2	3	4	5
Least Recently Used policy:
frame 1	1	1	1	4	4	4	2	2	2	5	5	5	3	3	3	3	3	3	3	3	3	3	3	2	2	2	5
frame 2		2	2	2	5	5	4	3	3	3	1	1	1	1	1	1	1	1	4	4	4	4	4	4	3	3	3
frame 3			3	3	3	1	5	5	4	4	4	2	2	2	2	2	2	2	2	2	2	2	1	1	1	4	4
Working Set:
Working Set Window	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	2	2	2	2	1	1	1	1
		2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	3	3	3	3	2	2	2	2
			3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	4	4	4	4	3	3	3	3
				4	4	4	4	4	4	4	4	4	4	4	5									4	4	4	4
					5	5	5	5	5	5	5	5	5	5
Osservazioni:
Ambedue i meccanismi si fondano sul fenomeno denominato principle of locality.
Il meccanismo del WS e' orientato ad ottimizzare la CPU utilization, evitando il cosidetto trashing. Non costituisce un algoritmo di page replacement.
Tuttavia, puo' essere utilmente impiegato nell'ambito dell'algoritmo LRU, in quanto definisce una window di riferimenti da mantenere in memoria.
Il problema precipuo dell'algoritmo LRU e' giustappunto il metodo di memorizzazione della serie storica delle pagine accedute.
Nella fattispecie, data una reference string contenente una permutazione di 5 riferimenti, e dato un WS con window size pari a 5, tutte le pagine rimpiazzate si ritrovano nel WS.