ESERCIZIO Segmentazione 1 In un sistema che gestisce la...

22
ESERCIZIO Segmentazione 1 In un sistema che gestisce la memoria con spazio logico suddiviso in segmento codice e segmento dati (comprensivo della pila) e caricamento in partizioni variabili con rilocazione dinamica, i registri base e limite del segmento codice hanno a un certo istante i valori B 1 = 12.000 e L 1 = 28.000, mentre i registri base e limite del segmento dati hanno i valori B 2 = 45.000 e L 2 = 25.000. Supponendo che il processo in esecuzione estragga istruzioni dagli indirizzi logici 7.000, 30.000 e 25.000, che riferiscono dati con indirizzi logici 47.000, 40.000 e 20.000, dire se ognuno dei precedenti indirizzi logici è legittimo e, in caso affermativo, calcolare il corrispondente indirizzo fisico. SOLUZIONE Istruzioni: Indirizzo logico Legittimo? Indirizzo fisico 1. 7.000 SI 19000 2. 30.000 NO 3. 25.000 SI 37000 Dati: 1. 47.000 NO 2. 40.000 NO 3. 20.000 SI 65000

Transcript of ESERCIZIO Segmentazione 1 In un sistema che gestisce la...

ESERCIZIO Segmentazione 1In un sistema che gestisce la memoria con spazio logico suddiviso in segmento codice e segmento dati(comprensivo della pila) e caricamento in partizioni variabili con rilocazione dinamica, i registri base elimite del segmento codice hanno a un certo istante i valori B1= 12.000 e L1= 28.000, mentre i registri basee limite del segmento dati hanno i valori B2= 45.000 e L2= 25.000.Supponendo che il processo in esecuzione estragga istruzioni dagli indirizzi logici 7.000, 30.000 e 25.000,che riferiscono dati con indirizzi logici 47.000, 40.000 e 20.000, dire se ognuno dei precedenti indirizzilogici è legittimo e, in caso affermativo, calcolare il corrispondente indirizzo fisico.

SOLUZIONEIstruzioni:

Indirizzo logico Legittimo? Indirizzo fisico

1. 7.000 SI 19000

2. 30.000 NO

3. 25.000 SI 37000

Dati:

1. 47.000 NO

2. 40.000 NO

3. 20.000 SI 65000

ESERCIZIO Segmentazione 2

In un sistema che gestisce la memoria con segmentazione a domanda, l’indirizzo logico è di 28 bit, dei qualii primi 6 bit codificano l’indice di segmento e i restanti 22 bit definiscono l’offset. Ogni elemento dellatabella dei segmenti è formato da 7 byte, dei quali 1 byte contiene indicatori utili al gestore della memoria, 3byte contengono il valore base, e i restanti 3 byte contengono il valore limite.Si chiede:

1. Il massimo numero di segmenti di un processo;2. La massima dimensione di un segmento (in byte);3. La massima dimensione della tabella dei segmenti (in byte);4. Il massimo valore possibile per l’indirizzo di origine di un segmento;

SOLUZIONE1. Massimo numero di segmenti di un processo: 26 segmenti = 64 segmenti2. Massima dimensione di un segmento (in byte): 222 byte = 4 Mbyte3. Massima dimensione della tabella dei segmenti (in byte): 64*7= 448 byte4. Massimo valore possibile per l’indirizzo di origine di un segmento: 224-1

ESERCIZIO Tabelle delle pagine 1Si consideri un sistema dove gli indirizzi logici hanno la lunghezza di 32 bit e le pagine logiche e fisichehanno ampiezza di 4 kByte. Per la gestione della memoria con paginazione dinamica si utilizzano tabelledelle pagine a 2 livelli. La tabella di primo livello comprende 210 elementi.Gli elementi di ogni tabella di primo o secondo livello occupano 4 byte, di cui 1 è riservato agli indicatori(pagina caricata, riferita, modificata, ecc.) mentre i rimanenti individuano un indice di blocco fisico.Si chiede:

1. la lunghezza del campo offset, in numero di bit;2. la lunghezza delle tabelle di secondo livello (numero di elementi);3. lo spazio occupato in memoria da ogni tabella di secondo livello (numero di byte);4. la massima dimensione della memoria fisica (numero di blocchi e di byte, espressi come potenze di

2).

SOLUZIONE1. lunghezza del campo offset : 12 bit

2. lunghezza (numero di elementi) di ogni tabella di secondo livello: 210 elementi

3. spazio occupato in memoria da ogni tabella di secondo livello (numero di byte) : 212 byte

4. massima dimensione della memoria fisica : 224 blocchi 2 24 * 212 = 236 byte (gli indici dei blocchi

di memoria fisica sono codificati con 3 byte)

ESERCIZIO Tabella delle pagine 2Un sistema gestisce la memoria con paginazione e usa indirizzi logici di 32 bit, blocchi di memoria di 1kbyte e tabelle delle pagine a due livelli. La tabella delle pagine di 1° livello (o directory) e quelle di 2°livello hanno uguale dimensione. Ogni elemento della tabella di primo livello e di quelle di secondo livellocontiene l’indice di un blocco di memoria e 2 bit di controllo.La memoria fisica ha una capacità di 4 Gbyte (= 232 byte)Domande:

1. Nell’indirizzo logico, quanti bit sono riservati all’offset nella tabella di 1° livello, quanti all’offsetnella tabella di 2° livello e quanti all’offset nella pagina logica?

2. Quanti bit sono necessari per codificare un indice di blocco e quanti bit contiene ogni elemento deitabella di primo o di secondo livello?

3. Quanti byte e quanti blocchi di memoria occupa ogni tabella?

SOLUZIONEIl numero di blocchi fisici è 222 .

1. Offset in Tab 1° livello (numero di bit): 11 bit

Offset in Tab 2° livello (numero di bit): 11 bit

Offset in pagina logica (numero di bit): 10 bit

2. Bit necessari per codificare un indice di blocco: 22 bit

Lunghezza in bit di ogni elemento di tabella: 24 bit (22 bit per l’indice di blocco + 2 bit di controllo)

3. Numero di byte occupati da ogni tabella:

Numero di blocchi occupati da ogni tabella: 211 elementi di 3 byte 6 * 2 10 byte 6 blocchi

ESERCIZIO Tabella delle pagine 3Si consideri un sistema che gestisce la memoria con paginazione dinamica con le seguenti caratteristiche:

· indirizzi logici di 32 bit e ampiezza dello spazio logico di ogni processo pari a 232 byte;· pagine logiche e blocchi fisici di 1 KByte;· tabelle delle pagine a due livelli; la tabella di primo livello comprende 210 elementi; · tutti gli elementi della tabella di primo e di secondo livello hanno lunghezza pari a 32 bit, di cui 10

sono indicatori e i restanti 22 codificano l’indice di un blocco fisico;In questo sistema è presente il processo P, che ha allocato nello spazio virtuale due aree di memoria:

Area 1: 2 Mbyte a partire dalla locazione 100* 1024 Area 2: 4 Mbyte a partire dalla locazione 4096* 1024

Si chiede:1. La lunghezza, in numero di bit, delle componenti dell’indirizzo logico che indirizzano,

rispettivamente, la tabella di primo livello, di secondo livello, e l’offset;2. Lo spazio occupato in memoria dalla tabella di primo livello e da ogni tabella di secondo livello (in

byte);3. La massima dimensione della memoria fisica (numero di blocchi e di byte, espressi come potenze di

2);4. Lo spazio indirizzabile da una tabella di secondo livello;5. Quali elementi della tabella di primo livello sono usati per indirizzare l’Area 1;6. Quali elementi della tabella/ delle tabelle di secondo livello sono usate per indirizzare l’Area 1;7. Quali elementi della tabella di primo livello sono usati per indirizzare l’Area 2;8. Quali elementi della tabella/ delle tabelle di secondo livello sono usate per indirizzare l’Area 2;

Soluzione1. Lunghezza del campo che indirizza la tabella di 1° livello: 10 bit2. Lunghezza del campo che indirizza la tabella di 2° livello: 12 bit 3. Lunghezza del campo offset: 10 bit 4. Spazio occupato in memoria dalla tabella di 1° livello: 4 kByte5. Spazio occupato in memoria dalla tabella di 2° livello: 16 kByte6. Massima dimensione della memoria fisica: 222 blocchi = 222+10 Bytes7. Spazio indirizzabile da una tabella di 2° livello: 212+10 Bytes = 4 MBytes8. L’Area 1 occupa le locazioni comprese tra 100*1024 e (100+2048) *1024 – 1, quindi tra 100 Kbyte

(estremo incluso) e 2Mbyte+100Kbyte (estremo escluso). Si tratta di locazioni comprese nei primi4Mbyte della memoria virtuale, che sono indirizzabili dalla prima tabella di secondo livello. Quindil’Area 1 è indirizzata dall’elemento 0 della tabella di primo livello.

9. Ogni elemento di una tabella di 2° livello indirizza 1 Kbyte, quindi l’Area 1 è indirizzata daglielementi della 1° tabella di secondo livello compresi tra: 100 e 100+2048-1

10. L’Area 2 occupa le locazioni comprese tra 4096* 1024 e (4096+4096) *1024 – 1, quindi tra 4 MByte(estremo incluso)e 8MByte (estremo escluso). Si tratta di locazioni comprese nei secondi 4Mbytedella memoria virtuale, che sono indirizzabili dalla seconda tabella di secondo livello. Quindi l’Area2 è indirizzata dall’elemento 1 della tabella di primo livello.

11. Ogni elemento di una tabella di 2° livello indirizza 1 Kbyte, quindi l’Area 2 è indirizzata daglielementi della 1° tabella di secondo livello compresi tra 0 e 4096- 1. In altri termini, per indirizzarel’Area 2 si utilizzano tutti gli elementi della tabella di secondo livello di indice 1.

ESERCIZIO Tabella delle pagine 4

Si consideri un sistema dove gli indirizzi logici hanno la lunghezza di 32 bit e le pagine logiche e i blocchifisici hanno ampiezza di 2 kByte.Per la gestione della memoria con paginazione a domanda si utilizzanotabelle delle pagine a 3 livelli. Le tabelle di primo, secondo o terzo livello hanno tutte uguale lunghezza.Per ogni tabella, gli elementioccupano 3 byte e riservano 4 bit agli indicatori (bit di presenza, riferimento, modifica e protezione inscrittura). I rimanenti bit codificano un indice di blocco fisico. Si chiede:

5. la lunghezza del campo offset, in numero di bit;6. la lunghezza delle tabelle di secondo livello (numero di elementi);7. lo spazio occupato in memoria da ogni tabella di secondo livello (numero di byte);8. la massima estensione della memoria fisica (numero di blocchi e di byte, espressi come potenze di

2).

SOLUZIONE5. lunghezza del campo offset : 11 bit

6. lunghezza, in numero di elementi, di ogni tabella di primo, secondo o terzo livello: 27 elementi

7. spazio occupato da ogni tabella di primo, secondo o terzo livello, in numero di byte : 3* 2 7 = 384

byte

8. massima estensione della memoria fisica : 220 blocchi 2 20 * 211 = 231 byte 2 Gbyte.

ESERCIZIO Segmentazione paginata

In un sistema che gestisce la memoria con segmentazione paginata, l’indirizzo logico è di 32 bit, dei quali iprimi 6 bit codificano l’indice di segmento e i restanti 26 bit definiscono l’offset all’interno del segmento. I26 bit dell’offset codificano l’indice di pagina con 14 bit e l’offset all’interno della pagina con i restanti 12bit.Si chiede:

il massimo numero di segmenti di un processo, la dimensione di una pagina (in byte); la massima dimensione di un segmento (in numero di pagine); la massima dimensione della tabella delle pagine (in numero di descrittori).

SOLUZIONE5. Massimo numero di segmenti di un processo: 26 segmenti = 64 segmenti6. Dimensione di una pagina: 212= 4KB7. Massima dimensione di un segmento : 214= 16K pagine

Massimo numero di descrittori nella tabella delle pagine: 214= 16K

Esercizio Segmentazione paginata 2

Si consideri un sistema che gestisce la memoria con segmentazione, con spazio logico suddiviso in segmentocodice, segmento dati e pila (rispettivamente individuati dagli indici 0, 1, 2) e caricamento in partizionivariabili con rilocazione dinamica. A un certo istante i registri base e limite del segmento codice, dati e pilahanno rispettivamente i valori B0= 7.400 e L0= 38.019, B1= 20.100 e L1= 8.022 e B2= 75.000 e L2=13.250.Supponendo che il processo in esecuzione riferisca i seguenti indirizzi logici, formati da coppie contenentil’indice di segmento e l’offset,

1. <0, 7.401>, 2. <2, 13.000>, 3. <3, 1.500>, 4. <1, 20.300>,

si chiede se ognuno dei precedenti indirizzi logici è legittimo e, in caso affermativo, di qual è ilcorrispondente indirizzo fisico.

SoluzioneIndirizzo logico Legittimo? Indirizzo fisico

4. <0, 7.401>, SI 14.8015. <2, 13.000>, SI 88.0006. <3, 1.500>, NO7. <1, 20.300>, NO

ESERCIZIO Page daemon

Un sistema operativo simile a UNIX, che gestisce la memoria con paginazione a domanda, utilizza il processoPageDaemon, con parametri lotsfree= 5 e minfree=2, e l’algoritmo di sostituzione Second Chance. Glielementi della CoreMap hanno i campi Proc (processo a cui è assegnato il blocco; il campo è vuoto se ilblocco è libero); Pag (pagina del processo caricata nel blocco), Rif (bit di pagina riferita utilizzato da SecondChance). Al tempo t sono presenti i processi A, B, C, D e la Core Map ha la configurazione mostrata infigura, con il puntatore dell’algoritmo di sostituzione posizionato sul blocco 11. I primi 6 blocchi dellamemoria fisica sono riservati al sistema operativo e sono ignorati dall’algoritmo di sostituzione.

Proc C A B A B C D D D B A B C CPag 0 1 0 2 6 3 1 2 6 2 7 3 7 2Rif 0 1 0 0 1 1 0 1 0 0 1 0 1 0Blocco 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Core Map al tempo t

Il PageDaemon interviene al tempo t e successivamente ogni 10 msec. Ad ogni intervento, PageDaemonavanza per 1 msec occupando in modo esclusivo il processore e scarica fino a 3 pagine o, in alternativa, se ilnumero di pagine libere è minore di minfree, esegue lo swapout di un processo.La selezione dei processi candidati allo swapout avviene in ordine alfabetico. In caso di errori di pagina, iblocchi liberi vengono assegnati in ordine crescente di indice. Considerare la seguente evoluzione del sistema:1. Dal tempo t al tempo t+1 avanza il processo PageDaemon;2. Dal tempo t+1 al tempo t+10 avanzano i processi B e C, che riferiscono nell’ordine le pagine B0,

B1, B6, C2, C0, C4, B2, B5 3. Dal tempo t+10 al tempo t+11 avanza il processo PageDaemon;4. Dal tempo t+11 al tempo t+20 avanzano i processi D e B, che riferiscono nell’ordine le pagine D3,

D6, D2, D1, B0, B2, B3, B0;5. Dal tempo t+20 al tempo t+21 avanza il processo PageDaemon.

Mostrare la configurazione della CoreMap ai tempi 1, 10, 11, 20 e 21

SOLUZIONE

(Modificare incrementalmente la configurazione iniziale della CoreMap, aggiornando anche la posizione del puntatore)

Proc C A B A B C D D B A B C CPag 0 1 0 2 6 3 2 6 2 7 3 7 2Rif 0 1 0 0 0 0 1 0 0 1 0 1 0Blocco 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Core Map al tempo t+1 (scaricata 1 pagina)

Proc C A B A B B C C D B D B A B C CPag 0 1 0 2 1 6 3 4 2 5 6 2 7 3 7 2Rif 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1Blocco

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Core Map al tempo t+10 (2 blocchi liberi)

Proc C A B B B C C D B B A C CPag 0 1 0 1 6 3 4 2 5 2 7 7 2Rif 0 0 0 1 1 0 1 0 0 0 0 0 0Blocco

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Core Map al tempo t+11 (scaricate 3 pagine)

Proc C A B D B B C C D B D B A D B CPag 0 1 0 3 1 6 3 4 2 5 6 2 7 1 3 7Rif 0 0 1 1 1 1 0 1 1 0 1 1 0 1 1 0Blocco 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Core Map al tempo t+20 (1 blocco libero)

Proc C B D B B C C D B D B D B CPag 0 0 3 1 6 3 4 2 5 6 2 1 3 7Rif 0 1 1 1 1 0 1 1 0 1 1 1 1 0Blocco 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Core Map al tempo t+21 (scaricato il processo A: il numero di pagine libere rimane < lotsfree, ma PagerDaemon ha il vincolo di

scaricare un solo processo in ogni intervento) )

ESERCIZIO Page daemon bis

Un sistema operativo simile a UNIX, che gestisce la memoria con paginazione a domanda, utilizza il processoPageDaemon, con parametri lotsfree= 10 e minfree=4, e l’algoritmo di sostituzione Second Chance. Perl’eventuale swapout, i processi sono considerati in ordine alfabetico. Notare che non si considera il parametrodesfree.Gli elementi della CoreMap hanno i campi Proc (processo a cui è assegnato il blocco), Pag (pagina delprocesso caricata nel blocco) e Rif (bit di uso, utilizzato da Second Chance); questi campi sono vuoti se ilblocco è libero. I blocchi di indici 0, 1, 2, 3, 4, e 5 sono riservati al sistema operativo e sono ignorati dalPageDaemon. Il PageDaemon interviene al tempo t sono quando sono presenti i processi A, B, C, D, E e rimane inesecuzione per tutto il tempo necessario ad applicare la sua politica, utilizzando in modo esclusivo ilprocessore (in altri termini, nessuno dei processi avanza in questo intervallo di tempo.Considerando le ipotesi a), b), c) d) per la configurazione della CoreMap e per la posizione del puntatore altempo t, definire per ciascuna ipotesi la configurazione della CoreMap e la posizione del puntatore al terminedell’intervento del PageDaemon (riempire solo le caselle modificate). Inoltre elencare, con formato (proc,pag), le pagine eventualmente scaricate o i processi eventualmente scaricati.

SOLUZIONEIpotesi a)S.O.

S.O.

S.O.

S.O.

S.O.

S.O.

A21

A30

B21

B41

A50

C31

C51

C00

D11

A01

B50

B11

C71

C91

C81

E01

D81

A90

A71

E10

E21

B91

C60

B111

C40

B121

E31

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

17

18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

Configurazione della CoreMap e posizione del puntatore al tempo t(per esempio: il blocco 20 è assegnato alla pagina 5 del processo B, con bit di uso 0,e il puntatore è posizionato sul blocco 12)

S.O.

S.O.

S.O.

S.O.

S.O.

S.O.

C30

C50

D10

A00

B10

C70

C90

C80

E00

D80

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

17

18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

Configurazione della CoreMap e posizione del puntatore al termine dell’intervento di PageDaemonPagine scaricate: (C, 0), (B, 5), (A, 9) Processi scaricati: Ipotesi b)

S.O.

S.O.

S.O.

S.O.

S.O.

S.O.

A21

B21

B41

A50

C31

C51

C00

D11

A01

B50

B11

C91

C81

E01

D81

A71

E10

E21

B91

C60

B111

C40

B121

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

17

18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

Configurazione della CoreMap e posizione del puntatore al tempo t

S.O.

S.O.

S.O.

S.O.

S.O.

S.O.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

17

18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

Configurazione della CoreMap e posizione del puntatore al termine dell’intervento di PageDaemonPagine scaricate: Processi scaricati: Ipotesi c)

S.O.

S.O.

S.O.

S.O.

S.O.

S.O.

A21

A30

B21

B41

A50

C31

C51

C00

D11

D31

A01

B50

B11

C71

C91

C81

E01

D81

A90

A71

E10

E21

D51

B91

C60

B111

C40

B121

E31

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

17

18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

Configurazione della CoreMap e posizione del puntatore al tempo t

S.O.

S.O.

S.O.

S.O.

S.O.

S.O.

A20

B20

B40

E20

D50

B90

B110

B120

E30

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

17

18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

Configurazione della CoreMap e posizione del puntatore al termine dell’intervento di PageDaemonPagine scaricate: (E, 1), (C, 6), (C, 4), (A, 3), (A, 5) Processi scaricati: Ipotesi d)

S.O.

S.O.

S.O.

S.O.

S.O.

S.O.

A21

A30

B21

B41

A50

D21

C31

C51

C00

D11

D30

A01

D50

B50

B11

C71

C91

C81

E01

D81

A90

E81

A71

E10

E21

E90

B91

C60

B111

C40

B121

E31

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

17

18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

Configurazione della CoreMap e posizione del puntatore al tempo t

S.O.

S.O.

S.O.

S.O.

S.O.

S.O.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

17

18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

Configurazione della CoreMap e posizione del puntatore al termine dell’intervento di PageDaemonPagine scaricate: Processi scaricati: A, B

Esercizio second chanceUn sistema operativo simile a UNIX, che gestisce la memoria con paginazione a domanda, utilizza il processoPageDaemon, con parametri lotsfree= 7 e minfree=3, e l’algoritmo di sostituzione Second Chance. Glielementi della CoreMap hanno i campi Proc (processo a cui è assegnato il blocco; il campo è vuoto se ilblocco è libero); Pag (pagina del processo caricata nel blocco), Rif (bit di pagina riferita utilizzato da SecondChance). Al tempo t sono presenti i processi A, B, C, D e la Core Map ha la configurazione mostrata infigura, con il puntatore dell’algoritmo di sostituzione posizionato sul blocco 11. I primi 2 blocchi dellamemoria fisica sono riservati al sistema operativo e sono ignorati dall’algoritmo di sostituzione.

↓Proc A D A C D D C A A C B B A C B D B APag 2 6 4 0 4 9 3 5 6 4 2 3 8 10 5 11 7 10Rif 1 1 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1Blocco 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Core Map al tempo t

PageDaemon interviene al tempo t e successivamente ogni 10 msec. Ad ogni intervento, PageDaemon avanzaper 1 msec occupando in modo esclusivo il processore e scarica fino a 4 pagine (per arrivare a lotsfree paginelibere) se il numero di pagine libere è almeno minfree. Se invece il numero di pagine libere è minore diminfree, allora esegue lo swapout di uno o più processi fino ad arrivare ad almeno lotsfree pagine libere.La selezione dei processi candidati allo swapout avviene in ordine di dimensione (per primi i processi piùgrandi). In caso di errori di pagina, i blocchi liberi vengono assegnati in ordine crescente di indice. Considerare la seguente evoluzione del sistema (i tempi sono espressi in millisecondi): Dal tempo t al tempo t+1 avanza il processo PageDaemon; Dal tempo t+1 al tempo t+10 i processi A, B, C e D riferiscono nell’ordine le pagine: A10, C3, C0,

C10, C2, C6, B3, B2, D10, D11, C9 Dal tempo t+10 al tempo t+11 avanza il processo PageDaemon; Dal tempo t+11 al tempo t+20 i processi A, B, C e D riferiscono nell’ordine le pagine: A2, A5, A9,

A11, A4, B0, B5, B6, B7, D6, D10 Dal tempo t+20 al tempo t+21 avanza il processo PageDaemon.

Mostrare la configurazione della CoreMap ai tempi 1, 10, 11, 20 e 21

Soluzione (Modificare incrementalmente la configurazione iniziale della CoreMap, aggiornando anche la posizione del puntatore)

↓Proc A D A C - D C A A C - B - C B D B APag 2 6 4 0 - 9 3 5 6 4 - 3 - 10 5 11 7 10Rif 0 0 0 0 - 1 1 0 0 0 - 0 - 0 0 0 0 0Blocco 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Core Map al tempo t+1 Pagine scaricate: B2, A8, D4

↓Proc A D A C C C D C A A C B D B C C B D B APag 2 6 4 0 2 6 9 3 5 6 4 2 10 3 9 10 5 11 7 10Rif 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1Blocco 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Core Map al tempo t+10

↓Proc A D A - - - D - A A - B D B - - B D B APag 2 6 4 - - - 9 - 5 6 - 2 10 3 - - 5 11 7 10Rif 0 0 0 - - - 1 - 0 0 - 1 1 1 - - 0 1 0 1Blocco 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Core Map al tempo t+11Pagine scaricate: C0, C2, C6, C3, C4, C9, C10 (intero processo C)

↓Proc A D A A A B D B A A B D B B D B APag 2 6 4 9 11 0 9 6 5 6 2 10 3 5 11 7 10Rif 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1Blocco 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Core Map al tempo t+20

↓Proc A D A A A B D B A - - D B B D B APag 2 6 4 9 11 0 9 6 5 - - 10 3 5 11 7 10Rif 0 0 0 0 0 0 0 0 0 - - 0 0 0 0 0 0Blocco 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Core Map al tempo t+21Pagine scaricate: A6, B2

Esercizio LRU locale e working set In un sistema che gestisce la memoria con paginazione, sono presenti i processi A, B e C. Lo stato dioccupazione della memoria al tempo 11 è descritto dalla seguente Core Map, dove per ogni blocco sispecifica il processo a cui appartiene la pagina caricata e l’indice della pagina medesima. Ad esempio, nelblocco 11 è caricata la pagina 6 del processo B.

Proc A A A C A B A C B C B B C A B A B C C

Pag 4 5 8 0 1 8 2 5 6 3 4 5 9 10 10 11 3 7 2

Blocco

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

A un certo tempo le tabelle delle pagine dei tre processi sono le seguenti, dove il campo Rif contiene il tempovirtuale (locale al processo) al quale è avvenuto l’ultimo riferimento alla pagina.

Pagina Blocco Rif Pagina Blocco Rif Pagina Blocco Rif0 0 0 6 01 7 10 1 12 9 11 2 2 23 23 3 19 6 3 12 34 1 17 4 13 8 45 2 14 5 14 13 5 10 56 6 11 12 67 7 7 21 128 4 16 8 8 15 89 9 9 15 8

10 16 18 10 17 18 1011 18 20 11 11

Processo A Processo B Processo C

Per la gestione della memoria si utilizza un algoritmo di sostituzione LRU locale con controllo del workingset. Il working set assegnato ai tre processi (inteso come numero di blocchi a disposizione del processo,anche se momentaneamente non occupati) ha dimensione 7. Al verificarsi di un errore di pagina, la paginariferita viene caricata in un blocco disponibile se il numero di blocchi occupati dal processo è minore dellimite assegnato al suo working set; in caso contrario si applica l’algoritmo di sostituzione. I blocchidisponibili vengono assegnati in ordine crescente di indice.Si chiede come si modificano la Core Map e le Tabelle delle pagine se, a partire dal tempo considerati, siverificano le seguenti sequenze di riferimenti alla memoria (considerare le due alternative):

4. Alternativa 1: - ai tempi 21, 22, 23 e 24 il processo A riferisce le pagine 2, 3, 7, 8; - quindi ai tempi 13, 14, 15 e 16 il processo C riferisce le pagine 0, 1, 4, 5

5. Alternativa 2: - ai tempi 13, 14, 15 e 16 il processo C riferisce le pagine 9, 7, 6, 5; - quindi ai tempi 19, 20, 21 e 22 il processo B riferisce le pagine 10, 11, 6, 7

Soluzione

6. Alternativa 1: - ai tempi 21, 22, 23 e 24 il processo A riferisce le pagine 2, 3, 7, 8; - quindi ai tempi 13, 14, 15 e 16 il processo C riferisce le pagine 0, 1, 4, 5

Proc A A C A A C C B A C B C B B C A B A B C

Pag 3 4 1 7 8 4 0 8 2 5 6 3 4 5 9 10 10 11 7 7

Blocco

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Pagina Blocco Rif Pagina Blocco Rif Pagina Blocco Rif0 0 0 6 131 1 1 2 142 9 21 2 23 0 22 3 19 6 3 12 34 1 17 4 13 8 4 5 155 5 14 13 5 10 166 6 11 12 67 3 23 7 7 21 128 4 24 8 8 15 89 9 9 15 8

10 16 18 10 17 18 1011 18 20 11 11

Processo A Processo B Processo C

7. Alternativa 2: - ai tempi 13, 14, 15 e 16 il processo C riferisce le pagine 9, 7, 6, 5; - quindi ai tempi 19, 20, 21 e 22 il processo B riferisce le pagine 10, 11, 6, 7

Proc C A A B A B C A B A C B C B B C A B A B C C

Pag 6 4 5 11 8 7 0 1 8 2 5 6 3 4 5 9 10 10 11 7 7 2

Blocco

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Pagina Blocco Rif Pagina Blocco Rif Pagina Blocco Rif0 0 0 6 01 7 10 1 12 9 11 2 2 23 23 3 3 3 12 34 1 17 4 13 8 45 2 14 5 14 13 5 10 166 6 11 21 6 0 157 7 5 22 7 21 148 4 16 8 8 15 89 9 9 15 13

10 16 18 10 17 19 1011 18 20 11 3 20 11

Processo A Processo B Processo C

Esercizio Paginazione a domandaUn sistema operativo simile a UNIX, che gestisce la memoria con paginazione a domanda, utilizza ilprocesso PageDaemon, con parametri lotsfree= 6 e minfree=2, e l’algoritmo di sostituzione Second Chanceglobale. Gli elementi della CoreMap hanno i campi Proc (processo a cui è assegnato il blocco; il campo èvuoto se il blocco è libero); Pag (pagina del processo caricata nel blocco), Rif (bit di pagina riferita utilizzatoda Second Chance). Al tempo t sono presenti i processi A, B, C, D e la Core Map ha la configurazionemostrata in figura, con il puntatore dell’algoritmo di sostituzione posizionato sul blocco 6.

Proc A C C A B C D B D B B C B B A D A D DPag 11 0 9 8 1 3 1 0 6 2 6 7 3 7 9 2 1 7 8Rif 1 0 1 0 1 1 0 0 0 0 1 0 1 1 1 1 1 1 0Blocco 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Core Map al tempo t

Il PageDaemon interviene al tempo t e successivamente ogni 10 msec. Ad ogni intervento, PageDaemonavanza per 1 msec occupando in modo esclusivo il processore e scarica pagine occupate fino a che il numerodi pagine libere è pari a lotsfree+2 o, in alternativa, se il numero di pagine libere è minore di minfree, eseguelo swap out di alcuni processi.Per semplicità, la selezione dei processi candidati allo swap out avviene in ordine di dimensione (per primi iprocessi che occupano più blocchi), e i processi vengono scaricati finché in memoria ci sono almenolotsfree+2 blocchi liberi. Il PageDaemon esegue anche lo swap in dei processi (sempre in ordine didimensione), dei quali vengono caricate in memoria le sole pagine riferite al momento dello swap out. Loswap in avviene quando il numero di blocchi liberi è pari al numero di pagine del processo da caricare piùlotsfree+2. In caso di errori di pagina, i blocchi liberi vengono assegnati in ordine crescente di indice. Considerare la seguente evoluzione del sistema:1. Dal tempo t al tempo t+1 avanza il processo PageDaemon;2. Dal tempo t+1 al tempo t+10 avanzano i processi A, B e C, che riferiscono nell’ordine le pagine A7,B6, A9, A8, C1, C9, C5, C8, D0, D1, C9, D83. Dal tempo t+10 al tempo t+11 avanza il processo PageDaemon;4. Dal tempo t+11 al tempo t+20 avanzano i processi B, C e D, che riferiscono nell’ordine le pagineA10, A9, B9, B2, B3, B1, D7, D2, C9, C0, B65. Dal tempo t+20 al tempo t+21 avanza il processo PageDaemon.

Mostrare la configurazione della CoreMap ai tempi 1, 10, 11, 20 e 21

Soluzione

Proc A C C A B C B B B A D A D DPag 11 0 9 8 1 3 6 3 7 9 2 1 7 8Rif 1 0 1 0 0 0 0 1 1 1 1 1 1 0Blocco 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Core Map al tempo t+1Scaricate le pagine: D1, B0, D6, B2, C7

Proc A C A C A C B C C C D D B B B A D A D DPag 11 0 7 9 8 1 1 3 5 8 0 1 6 3 7 9 2 1 7 8Rif 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1Blocco 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Core Map al tempo t+10Caricate le pagine: A7, C1, C5, C8, D0, D1

Proc A A C A C C C D D B D A D DPag 11 7 9 8 1 5 8 0 1 6 2 1 7 8Rif 0 0 0 0 0 0 0 0 0 0 0 0 0 0Blocco 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Core Map al tempo t+11Scaricate le pagine: C0, B1, C3, B3, B7, A9

Proc A A A C A C A B C C D D B B B B C D A D DPag 11 10 7 9 8 1 9 9 5 8 0 1 2 6 3 1 0 2 1 7 8Rif 0 1 0 1 0 0 1 1 0 0 0 0 1 1 1 1 1 1 0 1 0Blocco 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Core Map al tempo t+20Caricate le pagine: A10, A9, B9, B2, B3, B1, C0

Proc C C C C D D C D D DPag 9 1 5 8 0 1 0 2 7 8Rif 0 0 0 0 0 0 1 0 0 0Blocco 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Core Map al tempo t+21Swapout dei processi A e uno tra B, C e D (ad esempio B)

Esercizio LRU globaleIn un sistema che gestisce la memoria con paginazione, sono presenti i processi A, B e C. Lo stato dioccupazione della memoria al tempo 10 è descritto dalla seguente tabella, dove per ogni blocco si specificanell’ordine: il processo a cui appartiene la pagina caricata, l’indice della pagina e il tempo al quale èavvenuto l’ultimo riferimento alla pagina stessa. Ad esempio, nel blocco 11 è caricata la pagina 6 delprocesso B, il cui ultimo riferimento è avvenuto al tempo 5.

SO SO SO SO SO SO B,311

A,12

B,010

C,13

B,65

C,78

A,412

C,36

A,59

C,57

B,41

A,74

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Per la gestione della memoria si utilizza un algoritmo di sostituzione LRU globale. Si considerino le seguenti sequenze di eventi (da considerare in alternativa):

a) Il processo A riferisce la pagina 3 al tempo 13, la pagina 6 al tempo 14 e la pagina 4 al tempo 15; b) Il processo A riferisce la pagina 8 al tempo 13, la pagina 9 al tempo 14 e la pagina 10 al tempo 15; c) Il processo B riferisce la pagina 4 al tempo 13, la pagina 7 al tempo 14 e la pagina 8 al tempo 15;

Dire quali pagine vengono scaricate dalla memoria e caricate in memoria ai tempi t= 13, t=14 e t=15:

Soluzione

t= Pagina scaricata Pagina caricata ... Nel blocco

(a)13 - A3 1014 B4 A6 1715 - -

(b)13 - A8 1014 B4 A9 1715 A1 A10 7

(c)13 - -14 - B7 1015 A1 B8 7

Esercizio Working set Un sistema simile a Windows gestisce la memoria con paginazione a domanda mediante un Working SetManager. A un certo tempo, lo stato di occupazione della memoria (senza considerare i blocchi riservati alsistema operativo) è quello descritto nella seguente Core Map, i cui elementi hanno valore nullo se il bloccoè libero, o altrimenti identificano il processo e la pagina a cui il blocco è assegnato.

B,6 A,4

A,2

B,4 C,2 A,8

C,5 B,1 C,6 B,2 C,7 B,5 A,7

C,9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Nel sistema sono presenti i processi A, B e C, le cui tabelle delle pagine sono le seguenti (il campo TempoRifregistra il tempo virtuale del processo al quale è avvenuto l’ultimo riferimento alla pagina):

Pagina Blocco TempoRif Pagina Blocco TempoRif Pagina Blocco TempoRif0 0 01 1 21 4 12 15 8 2 23 7 2 17 33 3 34 13 9 4 16 5 45 5 26 9 5 20 96 6 10 1 6 22 117 27 5 7 7 25 58 19 4 8 89 9 9 28 6

Processo A - 5 Processo B - 4 Processo C - 6

A ogni processo è assegnato un WorkingSet Ammissibile di 4 pagine. Per ogni pagina riferita da un processoche avanza, si procede nel modo seguente:

Se la pagina è presente in memoria, si scrive il valore attuale del tempo virtuale del processo nelcampo TempoRif della tabella delle pagine.

Se si verifica un PageFault, la pagina riferita viene caricata in un blocco disponibile (anche se il nu-mero di pagine caricate, o insieme residente, supera la dimensione del Working Set Ammissibile), re-gistrando il valore attuale del tempo virtuale del processo nel campo TermpoRif. I blocchi disponibilivengono assegnati in ordine crescente di indice.

Il Working Set Manager viene attivato quando il numero di blocchi disponibili si riduce a 2, e sicomporta nel modo seguente:- considera i soli processi la cui dimensione dell’insieme residente (numero di pagine caricate in

memoria) superi quello del WorkingSet Ammissibile (che è 4 per tutti i processi) e per questiprocessi ordina globalmente le pagine per valori decrescenti del parametro TempoVirtuale-TempoRif, dove TempoVirtuale è il valore attuale del tempo virtuale del processo;

- scarica dalla memoria le pagine secondo questo ordinamento, fino a quando il numero di blocchidisponibili diventa uguale a 8. In caso di parità tra due o più pagine si considera l’ordinealfabetico dei processi.

A partire dal tempo considerato il sistema evolve nel modo seguente: Avanza il processo C, che ai tempi virtuali 12, 13, 14 e 15 riferisce rispettivamente le pagine 1, 2, 0,

e 9 Avanza il processo B, che ai tempi virtuali 10, 11, 12, 13 e 14 riferisce rispettivamente le pagine 6, 5,

0, 6 e 8.

Si chiede la configurazione della CoreMap e delle tabelle delle pagine dei 3 processi al termine dei punti 1 e2. Nei casi nei quali viene eseguito il Working Set Manager indicare anche il tempo virtuale dei processi almomento dell’esecuzione del Working Set Manager, e quante e quali pagine vengono rimosse.

Soluzione1) Configurazione della CoreMap e delle tabelle delle pagine al termine del punto 1:

B,6 C,1 C,0 A,4

A,2

B,4 C,2 A,8

C,5 B,1 C,6 B,2 C,7 B,5 A,7

C,9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Pagina Blocco TempoRif Pagina Blocco TempoRif Pagina Blocco TempoRif0 0 0 12 141 1 21 4 1 11 122 15 8 2 23 7 2 17 133 3 34 13 9 4 16 5 45 5 26 9 5 20 96 6 10 1 6 22 117 27 5 7 7 25 58 19 4 8 89 9 9 28 15

Processo A - 5 Processo B - 4 Processo C - 6

Non è stato eseguito il Working Set Manager

2) Configurazione della CoreMap e delle tabelle delle pagine al termine del punto 2:

B,6 C,1 C,0 A,4

B,0 A,2

B,4 C,2 B,8 A,8

C,5 B,1 C,6 B,2 C,7 B,5 A,7

C,9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Pagina Blocco TempoRif Pagina Blocco TempoRif Pagina Blocco TempoRif0 0 14 12 0 12 141 1 21 4 1 11 122 15 8 2 23 7 2 17 133 3 34 13 9 4 16 5 45 5 26 11 5 20 96 6 10 13 6 22 117 27 5 7 7 25 58 19 4 8 89 9 18 14 9 28 15

Processo A - 5 Processo B - 4 Processo C - 6

Viene quindi eseguito il Working Set Manager che rimuove 6 pagine dei soli processi B e C.Il tempo attuale del processo B è: 15Il tempo attuale del processo C è: 16

TempoVirtuale- TempoRif delle pagine dei processi B e C:6. B0 – 3; B1 – 11; B2 – 8; B4 – 10; B5 – 4; B6 – 2; B9 – 1; 7. C0 – 2; C1 – 4; C2 – 3; C5 – 7; C6 – 5; C7 – 11; C9 – 1;

Vengono quindi rimosse le pagine: B1, C7, B4, B2, C5, C6

B,6 C,1 C,0 A,4

B,0 A,2

C,2 B,8 A,8

B,5 A,7

C,9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Pagina Blocco TempoRif Pagina Blocco TempoRif Pagina Blocco TempoRif0 0 14 12 0 12 141 1 1 11 122 15 8 2 2 17 133 3 34 13 9 4 45 5 26 11 56 6 10 13 67 27 5 7 7

8 19 4 8 89 9 18 14 9 28 15

Processo A - 5 Processo B - 4 Processo C - 6