Esercizio
Si consideri un sistema che utilizza
tabelle delle pagine a due livelli con dimensione delle pagine di 4 KB e
indirizzi a 32 bit suddivisi in tre
campi da rispettivamente 10, 10 e 12 bit (il campo di 12 bit è ovviamente
l’offset). Calcolare la dimensione della tabella delle pagine di un processo
che ha allocato le seguenti aree di memoria logica:
area 1: locazioni da 0 a 1000000
area 2: locazioni da 4200000 a 5200000
Soluzione
Il numero di pagine fisiche indirizzabili è 2^20, quindi un descrittore
di pagina deve contenere almeno 20 bit per l’indirizzo della pagina fisica
(anche se la dimensione effettiva della mem. fisica è inferiore), più alcuni
bit accessori. Dato che non sono forniti ulteriori dettagli, e che comunque è
bene avere
descrittori che occupino un numero intero di byte, supponiamo per
semplicità che un descrittore di pagina occupi 4 byte.
Una tabella delle pagine di primo livello può indirizzare fino a
2^10=1024 tabelle di secondo livello. Dato che gli indirizzi sono di 32 bit = 4
byte,
una tabella di secondo livello occupa 4KB.
Una tabella delle pagine di secondo livello può indirizzare fino a
2^10=1024 pagine di 4KB ciascuna, per un totale di 4MB. Dato un descrittore
occupa 4 byte,
una tabella di secondo livello occupa 4KB.
L’area 1 necessita della prima tabella delle pagine di secondo livello
dato che occupa uno spazio inferiore a 4MB allocato a partire dall’indirizzo 0.
L’area 2 necessita della sola seconda tabella di secondo livello dato
che occupa uno spazio inferiore a 4MB allocato a partire dall’indirizzo
4200000.
Si osservi che la seconda tabella di secondo livello indirizza memoria compresa
tra 4MB e 8MB.
quindi in totale servono 3 tabelle: una di primo livello e due di
secondo livello per un totale di 12 KB
Esercizio
Si consideri un gestore della memoria basato su swapping che utilizza
una bitmap per rappresentare lo stato di allocazione della memoria.
Supponiamo che la bitmap contenga le seguenti informazioni.
0111110001100
Supponiamo ora che al gestore della memoria arrivino le seguenti
richieste in sequenza:
1- deallocazione del processo allocato che occupa le locazioni 1-3
2- allocazione di un nuovo processo di dim. 1
3- allocazione di un nuovo processo di dim. 4
4- allocazione di un nuovo processo di dim. 4
Supponendo che il gestore della memoria utilizzi politiche di
allocazione best fit, dire come si comporta il gestore della memoria e
come varia il contenuto della bitmap.
Soluzione
1) 0000110001100
2) 0000110001110
3) 1111110001110
4) lo spazio libero è frammentato e non c’è posto per un altro processo
di dim. 4. Ci sono due soluzioni: o si compatta la memoria o
si scaricano uno o più processi su disco.
Esercizio
Data
una memoria partizionata in maniera fissa come segue:
|
Partizione |
Dimensione |
|
0 |
200K |
|
1 |
500K |
|
2 |
300K |
|
3 |
600K |
e dato che il sistema operativo deve allocare quattro processi P1 di 212K, P2
di 417K, P3 di 112K e P4 di 427K
(in quest'ordine), scrivere in quale partizione il sistema alloca
ciascun processo se viene usato l'algoritmo:
First Fit
Best Fit
Worst Fit
(se il processo non puo' essere allocato, segnare "X" come
partizione).
Soluzione
Nota: le partizioni sono fisse: non si possono mettere due processi nella
stessa partizione!
First fit: P1:1, P2: 3, P3:0, P4:X
Best fit: P1:2, P2: 1, P3:0, P4:3
Worst fit: P1:3, P2:1, P3:2, P4:X
Esercizio
Si consideri un gestore della memoria basato su swapping che
utilizza una lista per rappresentare lo stato di allocazione della memoria.
Supponiamo che la lista contenga le seguenti informazioni.
(P,0,12)->(H,12,5)->
(P,17,6)->(H,23,15)->(P,38,5)->(H,43,12)-> (P,55,10) -> (H,65,8)
Il simbolo “P” denota una partizione di memoria occupata da un
processo, mentre il simbolo “H” denota una partizione di memoria libera,
il primo numero indica il blocco di partenza, il secondo numero il numero
di blocchi allocati al processo .
Supponiamo ora che al gestore della memoria arrivino in tempi
successivi due richieste di allocazione di memoria per tre processi,
il primo di dimensione 7, il secondo di dimensione 10, il terzo di
dimensione 1.
Dire come si comporta il gestore della memoria nel caso utilizzi la
politica di allocazione
best fit
first fit
worst fit
Mostrare in tutti i casi la lista di allocazione della
memoria risultante.
Soluzione:
Il best fit seleziona per il primo processo l’area (H, 65,8 ) e per il
secondo processo l’area (H,43,12) e
per il terzo processo seleziona l’area (H,72,1) rimasta dopo
l’allocazione dei primi due per cui la lista diventa
(P,0,12)->(H,12,5)->
(P,17,6)->(H,23,15)->(P,38,5)->(P,43,10)-> (H,53,2) -->
(P,55,10) -> (P,65,7)-> (P,72,1)
Il first fit seleziona per il primo processo l’area (H,23,15) e per il
secondo processo l’area (H,43,12) e per il terzo
L’area (H,12,5) per cui la lista diventa
(P,0,12)->(P,12,1)->(H,13,4)->
(P,17,6)->(P,23,7)->(H,30,8)->(P,38,5)->(P,43,10)->(H,53,2)->
(P,55,10) -> (H,65,8)
Il worst fit seleziona per il primo processo l’area (H,23,15) e per il
secondo processo l’area (H,43,12) e per il terzo
l’area (H,30,8) rimasta dopo l’allocazione dei primi due per cui la
lista diventa
(P,0,12)->(H,12,5)->
(P,17,6)->(P,23,7)->(P,30,1)->(H,31,7)->(P,38,5)->(P,43,10)->(H,53,2)->
(P,55,10) -> (H,65,8)
Esercizio
Si consideri un sistema con 8 pagine di mem. fisiche sul quale sono
attivi tre processi A, B e C. Si supponga che all’istante 1000 siano caricate
le pagine:
processo
pag. logica
pag.
fisica
istante di caricamento riferita
A
0
7
500
SI
A
8
6
480
NO
A
5
5
300
SI
B
5
4
970
NO
B
6
0
120
SI
C
2
2
765
NO
C
5
1
900
NO
C
9
3
212
NO
Supponendo che il sistema utilizzi un algoritmo di sostituzione second
chance, dire cosa avviene nei seguenti casi:
second chance GLOBALE, C riferisce la pagina logica 5
second chance GLOBALE, A riferisce la pagina logica 3
Soluzione:
La lista delle pagine per l’algoritmo second chance GLOBALE è
B6(120,SI)->C9(212,NO)->A5(300,SI)
->A8(480,NO)->A0(500,SI)->C2(765,NO)->C5(900,NO)->B5(970,NO)
Quindi le risposte sono:
1.) La pagina C5 è già in memoria (nella pagina fisica 1) e quindi
viene marcata come riferita
2.) La pagina logica A3 non è in memoria, l’algoritmo second chance
esamina B6, siccome è stata riferita, viene inserita in testa alla lista ed
il campo riferita viene resettato, quindi
viene esaminata C9, che viene eliminata, la lista risultante è
A5(300,SI) ->A8(480,NO)->A0(500,SI)->C2(765,NO)->C5(900,NO)->B5(970,NO)
)->B6(120,NO)->A3(1000,SI)
Esercizio
Si consideri un processo attualmente in esecuzione, il cui contenuto
della memoria associativa nella MMU e la tabella delle
pagine siano rispettivamente:
MEM. Associativa:
valido pag.
logica
modificata
protezione
riferita pag. fisica
1
7
SI
RW
SI 7
1
5
NO
R
SI 8
0
4
NO
RW
SI 5
Tab. delle pagine:
pag.
logica pag.
fisica
modificata
protezione
riferita presente/assente
……………………………
4
5
NO
RW
NO SI
5
8
NO
R
SI SI
6
6
SI
RW
NO SI
7
7
SI
RW
NO SI
8
-
NO
RW
NO NO
…………………………..
analizzando ognuno dei seguenti casi in modo INDIPENDENTE DAGLI ALTRI,
dire quali eccezioni vengono sollevate, come si comporta il sistema
e come variano le due tabelle:
1- il processo effettua
uno accesso in scrittura alla pagina logica 5
2- il processo effettua uno accesso in scrittura alla pagina logica 4
3-il processo
effettua uno accesso in lettura alla pagina logica 8
Soluzione
1) il descrittore della pagina 5 è caricato nella mem. associativa,
quindi si traduce l’indirizzo. Siccome l’accesso è in scrittura ma l’accesso
alla pagina
è consentito in sola lettura viene generata un’eccezione che provocherà il
fallimento del processo.
2) il descrittore della pagina 4 non è caricato nella mem. associativa,
quindi viene generata un’eccezione di indirizzo, si accede alla tabella delle
pagine,
si scopre che la pagina 4 è caricata in memoria, quindi si carica il
descrittore della pag. 4 in mem. associativa e si marca la pag. 4
come modificata e riferita nella mem. associativa che quindi diventa:
valido pag.
logica
modificata
protezione
riferita pag. fisica
1
7
SI
RW
SI 7
1
5
NO
R
SI 8
1
4
SI
RW
SI 5
La tabella delle pagine resta invariata.
3) il descrittore della pagina 8 non è caricato nella mem. associativa,
quindi viene generata un’eccezione di indirizzo, si accede alla tabella delle
pagine,
si scopre che la pagina 8 NON è caricata in memoria, quindi si genera un page
fault.
Al termine del page fault verrà aggiornato il descrittore della pagina
8 nella tabella delle pagine e verrà caricato il descrittore nella memoria
associativa.
Esercizio
Considerare
la seguente stringa di riferimenti alla memoria di un processo in un sistema
con memoria virtuale
S = 10 6 2 4 6 8 3 1 4 5 11 8 7 6
10 9 7 8 11 2
Illustrare il comportamento dell'algoritmo LRU di sostituzione delle
pagine per una memoria fisica di 5 blocchi.
Calcolare il numero di page fault che si verificano.
Soluzione
|
Rif. |
10 |
6 |
2 |
4 |
6 |
8 |
3 |
1 |
4 |
5 |
11 |
8 |
7 |
6 |
10 |
9 |
7 |
8 |
11 |
2 |
|
1 |
10 |
10 |
10 |
10 |
10 |
10 |
3 |
3 |
3 |
3 |
3 |
8 |
8 |
8 |
8 |
8 |
8 |
8 |
8 |
8 |
|
2 |
|
6 |
6 |
6 |
6 |
6 |
6 |
6 |
6 |
5 |
5 |
5 |
5 |
5 |
10 |
10 |
10 |
10 |
10 |
2 |
|
3 |
|
|
2 |
2 |
2 |
2 |
2 |
1 |
1 |
1 |
1 |
1 |
7 |
7 |
7 |
7 |
7 |
7 |
7 |
7 |
|
4 |
|
|
|
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
6 |
6 |
6 |
6 |
6 |
11 |
11 |
|
5 |
|
|
|
|
|
8 |
8 |
8 |
8 |
8 |
11 |
11 |
11 |
11 |
11 |
9 |
9 |
9 |
9 |
9 |
|
Page Fault |
* |
* |
* |
* |
|
* |
* |
* |
|
* |
* |
* |
* |
* |
* |
* |
|
|
* |
* |
In neretto: pagina selezionata
Numero di page fault: 16
Esercizio
Considerare la seguente stringa di riferimenti alla memoria di un processo
in un sistema con memoria virtuale
S = 20 18 15 10 6 2 15 18 20 6 10 11 8 6 10 9 7 8 11 2 Illustrare il
comportamento dell'algoritmo LRU di sostituzione delle
pagine per una memoria fisica di 5 blocchi.
Calcolare il numero di page fault che si verificano.
Soluzione
Pagina Riferita
|
|
20 |
18 |
15 |
10 |
6 |
2 |
15 |
18 |
20 |
6 |
10 |
11 |
8 |
6 |
10 |
9 |
7 |
8 |
11 |
2 |
|
0 |
20 |
20 |
20 |
20 |
20 |
2 |
2 |
2 |
2 |
2 |
10 |
10 |
10 |
10 |
10 |
10 |
10 |
10 |
10 |
2 |
|
1 |
|
18 |
18 |
18 |
18 |
18 |
18 |
18 |
18 |
18 |
18 |
18 |
8 |
8 |
8 |
8 |
8 |
8 |
8 |
8 |
|
2 |
|
|
15 |
15 |
15 |
15 |
15 |
15 |
15 |
15 |
15 |
11 |
11 |
11 |
11 |
11 |
7 |
7 |
7 |
7 |
|
3 |
|
|
|
10 |
10 |
10 |
10 |
10 |
20 |
20 |
20 |
20 |
20 |
20 |
20 |
9 |
9 |
9 |
9 |
9 |
|
4 |
|
|
|
|
6 |
6 |
6 |
6 |
6 |
6 |
6 |
6 |
6 |
6 |
6 |
6 |
6 |
6 |
11 |
11 |
5 + 9 = 14 page fault
Esercizio
Considerate la seguente lista circolare associata alle pagine utilizzate dal
processo A:
(P1, 10, 1, 0) --> (P2, 9, 0, 0) --> (P3, 5, 0, 1)
--> (P4, 7 ,0, 0 ) --> (P5, 11 ,0, 1 )
------------------------------------------------------------------------------------
|
dove in ogni tupla (N,T,R,M): N=Numero della pagina; T=Tempo di ultimo
uso; R=Reference bit; M=Modified bit.
Supponete che il processo A abbia bisogno di caricare la pagina P6 e che
occorra rimpiazzare una delle pagine esistenti.
Determinare la pagina selezionata per il rimpiazzamento e la nuova lista delle
pagine ottenuta utilizzando l'algoritmo WSClock
con le seguenti assunzioni:
- contatore del tempo virtuale di CPU del processo A = 12;
- periodo del working set =4;
- la lancetta punta inizialmete a P1.
Soluzione:
Viene selezionata la pagina P4 (P1 e P2 sono nel ws, P3 ha il bit M a 1).
La nuova lista e'
(P1, 10, 0, 0) --> (P2, 9, 0, 0) --> (P3, 5, 0, 0*) --> (P6,
12 ,1, 0 ) --> (P5, 11 ,0, 1 )
|
0*= se supponiamo che la copia su disco vada a buon fine.
Esercizio
Si considerino tre processi (A, B e C), che hanno rispettivamente 3, 3
e 4 pagine logiche caricate in altrettante pagine fisiche della memoria.
Per ogni pagina, l’istante di tempo dell’ultimo riferimento è riassunto
dalla seguente tabella:
Processo
Pagina fisica istante ultimo riferimento
A
0
10
A
2
2
A
4
13
B
1
3
B
9
12
B
8
5
C
7
8
C
3
11
C
6
6
C
5
4
Si supponga inoltre che non siano rimaste pagine libere in memoria.
Dire quale pagina verrebbe rimossa dall’algoritmo di sostituzione se
all’istante 14 avviene un page fault:
causato da C, e il gestore della memoria utilizza l’algoritmo di
sostituzione LRU
causato da B, e il gestore utilizza l’algoritmo di sostituzione LRU
causato da C, e il gestore utilizza l’algoritmo di sostituzione Working
Set con parametro di anzianità 8
causato da B, e il gestore utilizza l’algoritmo di sostituzione Working
Set con parametro di anzianità 8
Soluzione
Page fault causato da C con LRU: viene selezionata la pagina 2
(allocata al processo A)
Page fault causato da B con LRU: viene selezionata la pagina 2
(allocata al processo A)
Page fault causato da C con WS: viene selezionata la pagina 5 (allocata
al processo C)
Page fault causato da B con WS: sono fuori dal working set sia la
pagina 1 che la 8 (allocate entrambe al processo B).
L’algoritmo di sostituzione ne seleziona una delle due in base
all’ordine con il quale le analizza.