Marco Lapegna » 24.Esercitazione 6: La memoria virtuale

Esercizio 1

Con riferimento ad un ambiente di gestione della memoria virtuale con paginazione su richiesta, si consideri un processo caratterizzato dalla seguente stringa di riferimenti

1 0 3 5 6 9 1 19 15 18 9 15 1 3 5 1 9 19 3

Si illustri il comportamento degli algoritmi FIFO e LRU nel caso siano assegnati al processo 5 frame. Si calcoli il numero di page faults

Soluzione FIFO

Soluzione LRU

Esercizio 2

Supponiamo che il sistema di paginazione usato dal S.O. assegni 3 frame da 512B a ciascun processo e si consideri il seguente programma

…

#define N 512

int A[N], C[N];

int i,j;

…

for(i=1; i<=2; i++)

for(j=0; j<N/2; j++)

A[i*j] = A[2*i] + C[2*j];

…

Esercizio 2

• si determini la stringa dei riferimenti alle pagine della memoria supponendo che un intero si rappresentato con 2B
• si determini la tabella delle pagine, al termine dell’esecuzione della procedura, nel caso che l’algoritmo di avvicendamento sia (i) FIFO, (ii) LRU

Soluzione

Gli array A e C occupano 1024B ciascuno, suddivisi in 2 pagine da 512B come segue:

• A[0..255] alla pagina 0,
• A[256..511] alla pagina 1
• C[0..255] alla pagina 2,
• C[256..511] alla pagina 3

Soluzione

soluzione

Esercizio 3

Nei due casi precedenti:

• FIFO = 5 page fault
• LRU = 4 page fault

qual’e’ il tempo di accesso effettivo della paginazione su richiesta se il tempo medio di servizio e’

• 25 millisecondi (25*10-3 sec) in caso di page fault
• 100 microsecondi (100*10-6 sec) in caso di pagina presente in memoria?

Soluzione

• Complessivamente l’istruzione A[i*j] = A[2*i] + C[2*j] viene eseguita 512 volte
• Ogni volta vengono fatti 3 accessi
• Totale di 1536 riferimenti in memoria.

• EAT = (1 – p) x t[accesso alla memoria] + p x t[page fault]

Soluzione

FIFO → p=5/1536 = 0.0032

EAT = 0.9968 x 100*10-6 + 0.0032 x 25000*10-6 = 179.68 *10-6 sec

LRU → p=4/1536 = 0.0026

EAT = 0.9974 x 100*10-6 + 0.0026 x 25000*10-6 = 164.74 *10-6 sec

Esercizio 4

Considerare la seguente successione di riferimenti di pagine:

1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 3, 2, 7, 6, 3, 2, 1, 2, 3, 6.

E si supponga che l’accesso alle pagine 1, 2 , 3 sia sempre in scrittura.

Esercizio 4

• Determinare il tempo di accesso effettivo della paginazione su richiesta per LRU con 5 blocchi, se:
• il tempo medio di servizio di un page fault senza salvataggio della pagina avvicendata é di 80 millisecondi (80*10^-3 sec),
• il tempo medio di servizio di un page fault con salvataggio della pagina avvicendata è di 140 millisecondi (140*10^-3 sec)
• il tempo di accesso alla memoria è di 80 microsecondi (80*10^-6 sec),

soluzione

soluzione

• 1 page fault con salvataggio della pagina sostituita
• 7 page fault senza salvataggio della pagina sostituita
• 12 accessi diretti senza page fault

• EAT = (12/20 * 80 + 7/20 * 80000 + 1/20 * 140000 ) *10-6 sec = 35.048 msec

Clock algorithm

Implementazione mediante un bit di accesso. (bit=1 se referenziata)

Si scorrono le pagine presenti nella lista:

Se bit=1 :

• Si pone il bit di riferimento a 0.
• Si lascia la pagina in memoria.
• Si rimpiazza la pagina successiva (in ordine di clock), in base alle stesse regole.

Se bit=0

• Si rimpiazza la pagina

Esercizio 5

Data la seguente sequenza di riferimenti di pagine

1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 3, 2, 7, 6, 3, 2, 1, 2, 3, 4

Determinare quanti page fault avvengono utilizzando il clock algorithm con 5 frame e lancetta dell’orologio posizionata sul primo elemento

soluzione

Soluzione (note)

• (0) all’inizio clock = 1
• (1) pag 1 e 2 bit=1 → si portano bit=0 e si avvicenda pagina 3 → clock =4
• (2) clock = 5
• (3) clock = 1
• (4) pag 1, 2, 6, 3 bit=1 → si portano bit=0 e si avvicenda pagina 7 → clock =1

Esercizio 6: Working set

Il working set di un processo W(t, w), e’ l’insieme delle pagine referenziate dal processo nell’intervallo di tempo [t – w , t ]
Si studi l’andamento dell’algoritmo basato su working set W(t,w) con w=5 per la seguente stringa di riferimento alle pagine di memoria e si determini la minima e la massima dimensione del w.s.

1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 5, 6, 4, 5, 6, 4, 5, 6

Esercizio 6 / soluzione

Esercizio 7

Determinare il numero di p.f. per l’algoritmo del working set con w=5 per le seguenti stringhe di riferimenti

S1

1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 5, 6, 4, 5, 6, 4, 5, 6

S2

1, 4, 1, 3, 2, 6, 1, 2, 3, 5, 4, 2, 3, 2, 4, 6, 5, 6, 1, 5, 3

Si osservi: In entrambi casi

4 riferimenti alle pagine 1, 2 e 3

3 riferimenti alle pagine 4, 5 e 6

Soluzione stringa s1

Soluzione stringa s2

Esercizio 8

Supponiamo che il sistema di paginazione utilizzato dal sistema operativo assegni 3 frame (blocchi di memoria) da 512B a ciascun processo e che l’algoritmo di sostituzione delle pagine sia LRU.

Prendiamo in considerazione il seguente programma:

…

#define N 512

int a[N];

int i;

…

for (i=0; i < N/2; i++)

a[i] = a[2*i] + a[N-i-1];

…

Esercizio 8

Si risponda ai seguenti quesiti:

• se la dimensione di un intero è 4B, qual è il numero di page faults ?
• In tal caso, se il tempo medio di servizio di un page fault é di 25 millisecondi (25*10-3 sec) ed il tempo di accesso alla memoria di 100 microsecondi (100*10-6 sec), qual è il tempo di accesso medio della paginazione su richiesta?

soluzione

Soluzione

Soluzione

Esercizio 9

In un s.o. con paginazione su richiesta occorrono:

• 8 msec in caso di p.f. senza salvataggio della pagina avvicendata
• 20 msec in caso di p.f. con salvataggio della pagina avvicendata
• 100 nsec in caso di pagina presente in memoria

Supponendo che il 70% delle volte e’ necessario salvare la pagina avvicendata, determinare il massimo valore del p.f. rate p per ottenere un EAT al piu’ di 200 nsec

soluzione