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
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
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