Prova Teorica 2009.09.18
Jump to navigation
Jump to search
TESTO COMPITO
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 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | ||
| 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | |||
| 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | ||||
| 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 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, sulla quale puo' essere applicato LRU. | |||||||||||||||||||||||||||
| 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. | |||||||||||||||||||||||||||