Gestione della memoria

 

Domanda

 

Esercizio 1  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

  1. best fit
  2. first fit
  3. 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 2 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:

  1. causato da C, e il gestore della memoria utilizza l’algoritmo di sostituzione LRU
  2. causato da B, e il gestore utilizza l’algoritmo di sostituzione LRU
  3. causato da C, e il gestore utilizza l’algoritmo di sostituzione Working Set con parametro di anzianità 8
  4. causato da B, e il gestore utilizza l’algoritmo di sostituzione Working Set con parametro di anzianità 8

 

Soluzione

  1. Page fault causato da C con LRU: viene selezionata la pagina 2 (allocata al processo A)
  2. Page fault causato da B con LRU: viene selezionata la pagina 2 (allocata al processo A)
  3. Page fault causato da C con WS: viene selezionata la pagina 5 (allocata al processo C)
  4. Page fault causato da B con WS: sono fuori dal working set sia la pagina 1 che la 8 (allocate entrambe al processo B).
  5. L’algoritmo di sostituzione ne seleziona una delle due in base all’ordine con il quale le analizza.

 

 

File System

 

Domanda

 

Esercizio 3.

Calcolare la dim. (in byte) della FAT per un disco da 512MB con blocchi da 16 KB e indirizzi dei blocchi a 16 bit.

Quanti blocchi occuperebbe la FAT se memorizzata su disco?

Quanti accessi alla FAT occorrono per recuperare l’indirizzo fisico del blocco nel quale si trova il byte 125384 di un certo file del file system in questione?

 

Nota:  16K=24*210=214     512M=29 * 220=229

 

Soluzione  La dimensione del disco è di’ 229 byte e quindi di 229/214= 215 blocchi di 214 byte.

Il campo di indirizzamento della FAT (16 bit=2 byte) consente di indirizzare tutti i blocchi.

La dimensione della FAT è di  215*2 = 216 byte. Se risiede su disco occupa 216/214= 4 blocchi.

Supponendo che i blocchi dell’archivio siano numerati a partire da 0, il byte 125384 si trova nel blocco 7.

Quindi occorre accedere 7 volte alla FAT per poter recuperare l’indirizzo fisico associato a tale byte.

 

 

Esercizio 4. Si supponga che, durante la fase della fsck che verifica la consistenza dei blocchi vengano prodotti i seguenti vettori:

 

indice di blocco:                  0    1    2    3    4    5    6    7    8    9   10  11  12  13  14  15  16  17

vettore blocchi liberi:      1    1    1    1    0    0    0    1    1    1    0    0    0    0    0    2    2    1

vettore blocchi occupati:                1    2    1    1    0    0    1    1    1    0    0    0    0    0    0    1    1    2

 

spiegare quali sono le azioni intraprese dalla fsck per ripristinare uno stato consistente del file system.

 

Soluzione:

La fsck intraprende un insieme di azioni volte ad avere ogni blocco presente con un solo 1 in una delle due tabelle

1.        blocchi 0,1,2,3,7,8,15,16,17 : sono presenti sia nella lista dei blocchi liberi che nell’i-node di qualche file. La fsck gli elimina dalla lista libera e la ricostruisce, risultato

indice di blocco:                  0    1    2    3    4    5    6    7    8    9   10  11  12  13  14  15  16  17

vettore blocchi liberi:      0    0    0    0    0    0    0    0    0    1    0    0    0    0    0    0    0    0

vettore blocchi occupati:                1    2    1    1    0    0    1    1    1    0    0    0    0    0    0    1    1    2

 

2. blocchi 4,5,10,11,12,13,14 : non sono presenti in nessuna delle due tabelle, la fsck assume siano liberi e li inserisce nella lista dei blocchi liberi, risultato

indice di blocco:                  0    1    2    3    4    5    6    7    8    9   10  11  12  13  14  15  16  17

vettore blocchi liberi:      0    0    0    0    1    1    0    0    0    1    1    1    1    1    1    0    0    0

vettore blocchi occupati:                1    2    1    1    0    0    1    1    1    0    0    0    0    0    0    1    1    2

 

3. blocchi : 1,17 : sono presenti come blocchi dati di due file distinti, la fsck crea due copie diverse per ognuno (usando due blocchi liberi, ad esempio il 4 ed il 5)
e corregge i corrispondenti i-node. Inoltre avverte l’utente di possibili inconsistenze sui dati stampando un messaggio di errore. Risultato finale :

indice di blocco:                  0    1    2    3    4    5    6    7    8    9   10  11  12  13  14  15  16  17

vettore blocchi liberi:      0    0    0    0    0    0    0    0    0    1    1    1    1    1    1    0    0    0

vettore blocchi occupati:                1    1    1    1    1    1    1    1    1    0    0    0    0    0    0    1    1    1

 

 

Processi

 

Esercizio 5. Si consideri il problema dei filosofi a cena, con riferimento alla soluzione proposta nel testo e riportata di seguito:

 

#define N 5

#define LEFT (i+N-1)%N

#define RIGHT (i+1)%N

#define THINKING 0

#define HUNGRY 1

#define EATING 2

int state[N];

semaphore mutex=1;

semaphore s[N];

 

void pilosopher (int i) {

                while (TRUE) {

                                think();

                                takeForks(i);

                                eat();

                                putForks(i);

}

}

void takeForks (int i) {

                down(&mutex);

                state[i] = HUNGRY ;

test(i);

up(&mutex);

down(&s[i]);                     (-3-)

}

void putForks (int i) {

                down(&mutex);

                state[i] = THINKING ;        (-1-)

test(LEFT);

test(RIGHT);                     (-2-)

up(&mutex);

}

void test (int i) {

                if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING ) {

                                state[i] = EATING;

                up(&s[i]);

}

 }

 

 

 

Discutere cosa accade si invertiamo i due statement (-1-) e (-2-). E cosa accade se eliminiamo (-3-) ?

 

Soluzione:

·         Se si invertono le righe (-1-) e (-2-), i filosofi che rilasciano le bacchette non potranno riattivare eventuali altri filosofi adiacenti che vorrebbero mangiare.
Infatti al momento della chiamata della procedura test, il filosofo mantiene lo stato EATING. In questo modo i filosofi in attesa di mangiare non
verranno mai riattivati dai filosofi che terminano di mangiare, e resteranno perciò bloccati.

·         Se si elimina la riga (-3-) dal codice dei filosofi a cena ci potrebbero essere dei filosofi che mangiano anche senza aver ottenuto le bacchette.