Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion