Punteggio

 D1
 D2
 D3
 E1
 E2
 E3
 Totale
Punti
 6
 5
 5
 6
 5
 5
 32


Testo e soluzioni

  1. TIPO A (working set, ecc)
  2. TIPO B (tlb ecc)


TIPO A

Domanda 1
Descrivere l'algoritmo di base per la  sostituzione di pagine basato sul Working Set.

Soluzione:
Working set=insieme delle pagine utilizzate correntemente da un processo.
Il s.o. mantiene un'approsimazione del working set di ogni singolo processo in memoria.
Si seleziona una pagina al di fuori del working set.
Ad esempio, si associa il tempo di ultimo uso, e fissato un paramentro di anzianita' di seleziona
una pagina con eta' maggiore del parametro.
Possibili implementazioni: WS con tempo di ultimo utilizzo (...), WSClock (...).

Domanda 2
Come sono organizzati i frame liberi della memoria principale in Windows 2000?

Soluzione:
Sono organizzati in 4 liste: pagine modificate, in attesa, libere, azzerate.
Il gestore e i demoni spostano le pagine da una lista all'altra:
Dopo un page fault la pagina rimpiazzata va in una tra le liste modificata/in attesa
ecc ....


Domanda 3
A cosa serve, come e' organizzata, e come viene usata la tabella dei file aperti di in Unix?

Soluzione:
Unix tiene traccia dei file aperti sia localmente (tabella dei file associati ad un processo)
sia globalmente (tabella dei descrittori dei file aperti).
La prima tabella contiene dei puntatori alle entry della seconda.
Operazioni quali "open" restituiscono un puntatore ad una entry della tabella dei file "locale".
La seconda tabella mantiene informazioni quali la posizione nel file e il puntatore all'inode del file.
In tal modo padre e figlio possono condividere ad. es la posizione corrente nel file dopo una fork.
Un processo scorrelato  da essi otterra' invece una nuova entry (e quindi un nuovo cursore nel file).


Esercizio 1
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 2
Dato un file system FAT con blocchi di 3KB  e il seguente frammento di FAT,
dire in quali blocchi fisici sono collocati i seguenti byte:
  1. byte 6758 del file "pippo" che inizia al blocco 8
  2. byte 4097 del file "pluto" che inizia al blocco 3
  3. byte 2044 del file "paperino" che inizia al blocco 4

Frammento FAT :

Entry
 Contenuto
0
 7
1
 2
2
 11
3
 5
4
 3
5
 20
6
 13
7
 1
8
 0

Soluzione
  1. Dim. blocco = 3*1024= 3072 bytes. Il byte 6758 di pippo si trova nel terzo blocco (6758/3072 =2.1).
    Percorrendo la FAT: I blocco: 8, II blocco: 0, III blocco: 7.
    Quindi l'indirizzo fisico del blocco e' 7

  2. Il byte 4097 di pluto si trova nel secondo blocco, quindi nel blocco fisico 5.

  3. Il byte 2044 del file "paperino" si trova nel primo blocco, quindi nel blocco fisico 4.
Esercizio 3
In una organizzazione dell'allocazione dei file simile a quella adottata in UNIX vi sono 13 puntatori nel
descrittore di file  (mantenuto in memoria durante l'accesso al file) di cui Se la dimensione di un blocco è 1KB, e un puntatore occupa 4 bytes:
  1.  Qual è la dim. massima di un file per il quale non sono necessari accessi aggiuntivi per accedere a qualunque blocco?

  2.  Qual è la dim. massima di un file?

  3. Quanti accessi aggiuntivi sono necessari per accedere al byte alla posizione 1000K?
Soluzione
Un blocco puo' contenere (dim. blocco/dim.puntatore=) 1024/4=256 puntatori a blocchi.
  1. La dim. massima di un file con blocchi accessibili solo tramite puntatori diretti e' 10*1KB=10 KB.

  2. La dim. massima di un file indirizzabile e' 10 KB+512 KB+2562 KB= 66058 KB.

  3. 1000K> 522KB. Quindi il 1000000-esimo byte di un file si trova in un blocco accessibile tramite puntatore doppiamente indiretto:
    occorrono quindi 2 accessi aggiuntivi (uno alla tabella esterna e uno a quella interna).
TIPO B

Domanda 1
Descrivere il meccanismo di gestione degli accessi alla pagine logiche in un sistema con paginazione munito di TLB.

Soluzione:
La TLB (translation lookaside buffer) e' un dispositivo hardware che permette di mappare indirizzi logici in indirizzi fisici senza
passare attraverso la tabella delle pagine (memoria associativa).
In una MMU con TLB quando occorre risolvere un riferimento ad un indirizzo logico, si cerca prima
l'indirizzo di pagina logica all'interno della TLB, si controllano i bit di validita' e protezione, e se in caso di successo
si recupera l'indirizzo fisico della pagina.
In caso di operazione non lecita (ad es. scrittura su pagina di sola lettura) viene generato un errore di protezione.
Se la pagina invece non 'e presente (o non e' valida) allora si esgue una ricerca la tabella delle pagine, e si sostitusisce
un'elemento della TLB con le informazioni sulla pagina recuperate dalla tabella o attraverso la gestione di un page fault.

Domanda 2
Descrivere l'algoritmo del clock a due lancette utilizzato dal demone delle pagine di Unix.

Soluzione:
L'alg. del clock a 2 lancette utilizza due puntatori per selezionare la pagina da rimpiazzare.
Il primo puntatore esegue una prima passata sulla lista (circolare) delle pagine e modifica i bit
(se Rif=1... ) il secondo puntatore seleziona la pagina (...).
A seconda della 'distanza' tra le due lancette di ottengono diverse strategia (...)


Domanda 3
Descrivere le caratteristiche principali e confrontare tra loro (con un occhio di riguardo alla capacita' di indirizzamento)
i file system FAT-12, FAT-16 e FAT-32 e un file system basato su i-node stile Unix.

Soluzione:
I file system FAT-12, FAT-16 e FAT-32 utilizzano la FAT (mem. all'inizio di un disco) per tenere traccia dei blocchi fisici associati ad un file.
La FAT e' una tabella indicizzata sul numero di blocco fisico. Il contenuto di una entry rappresenta il blocco seguente di un determinato file
(cioe' una FAT rappresenta un'insieme di liste concatenate).
La differenza tra i vari FS FAT sta nel numero di bit utilizzati per l'indirizzamento del disco (risp. 12, 16, 28).
La capacita' dipende dalla dimensione dei blocchi:
-- FAT-12 da  2MB (blocchi da 0.5KB) a 16 MB (blocchi da 4KB)
-- FAT-16 da  128MB (blocchi da 2KB) a 2048 MB (blocchi da 32KB)
-- FAT-32 da  1TB (blocchi da 4KB) a 2TB (blocchi da 324KB)

In Unix gli indirizzi di blocco sono mantenuti dentro un'inode (insieme as altre info sul file):
10 indirizzi diretti, 1 singolo indiretto, 1 doppio indiretto.
La capacita' dipende dalla dim. dei blocchi e dei puntatori: con blocchi da 4KB e puntatori da 4byte ~ 4TB


Esercizio 1
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 2
Dato un file system FAT con blocchi di 2KB  e il seguente frammento di FAT,
dire in quali blocchi fisici sono collocati i seguenti byte:
  1. byte 6758 del file "pippo" che inizia al blocco 4
  2. byte 4096 del file "pluto" che inizia al blocco 3
  3. byte 2044 del file "paperino" che inizia al blocco 5

Frammento FAT :

Entry
 Contenuto
0
 10
1
 2
2
 0
3
 6
4
 1
5
 8
6
 7
7
 11
8
 12

Soluzione
  1. Dim. blocco = 2*1024= 2048 bytes. Il byte 6758 di pippo si trova nel quarto blocco
    Percorrendo la FAT: I blocco: 4, II blocco: 1, III blocco: 2, IV blocco: 0
    Quindi l'indirizzo fisico del blocco e' 0

  2. Il byte 4096 di pluto si trova nel secondo (terzo) blocco se si parte da 1 (0), quindi nel blocco fisico 6 (7).

  3. Il byte 2044 del file "paperino" si trova nel primo blocco, quindi nel blocco fisico 5.

Esercizio 3
In una organizzazione dell'allocazione dei file simile a quella adottata in UNIX vi sono 14 puntatori nel descrittore di file
(mantenuto in memoria durante l'accesso al file) di cui Se la dimensione di un blocco è 1KB, e un puntatore occupa 4 bytes:
  1.  Qual è la dimensione massima di un file per il quale non sono necessari accessi aggiuntivi per accedere a qualunque blocco?

  2.  Qual è la dimensione massima di un file?

  3. Quanti accessi aggiuntivi sono necessari per accedere al byte alla posizione 300K?

Soluzione
Un blocco puo' contenere (dim. blocco/dim.puntatore=) 1024/4=256 puntatori a blocchi.
  1. La dim. massima di un file con blocchi accessibili solo tramite puntatori diretti e' 12*1KB=12 KB.

  2. La dim. massima di un file indirizzabile e' 12 KB+256 KB+2562 KB=65804 KB

  3. Il 300000-esimo byte di un file si trova in un blocco accessibile tramite puntatore doppiamente indiretto:
    occorrono quindi 2 accessi aggiuntivi (uno alla tabella esterna e uno a quella interna).