EsempioEsame.md



Esami Sistemi Operativi 2

Esempio Esame
Domanda 1:
Si calcoli il valore del sector interleaving per un disco caratterizzato da una
velocità rotazionale di 4200 RPM e 1600 settori per traccia, e un tempo di
trasferimento di un settore in memoria (incluso il tempo di controllo dell'ECC)
di 60 microsecondi.
Nella risposta occorre mostrare anche i passaggi intermedi che portano al
risultato finale.
Risposta:
 $T_r \text{ (Tempo singola rotazione)} = \frac{60s}{4200 RPM} = 0,014s$ 

 $T_s \text{ (Tempo settore sotto la testina)} = \frac{T_r}{\text{num settori}} = \frac{0,014s}{1600} = 8.928 \mu s$ 

 $\text{Sector Leaving} = \frac{\text{Tempo trasferimento}}{T_s} = 6,72 \approx 7 \text{ settori}$ 

Domanda 2:
Si consideri la cache di un file system che utilizza la tecnica di hashing per
velocizzare il reperimento dei blocchi in essa presenti, la politica LRU per il
rimpiazzamento dei blocchi, e abbia una capacità pari a 15 blocchi.
Si ipotizzi inoltre che tale cache preveda l'uso di 9 "slot" per la tabella di hash
(indirizzati da 0 a 8) e che la funzione di hashing utilizzata
sia h(B) = B mod 9 dove B è
l'indirizzo del blocco da memorizzare nella cache.
Supponendo che la cache sia inizialmente vuota, si riporti
il contenuto della lista LRU,
e delle liste corrispondenti agli slot n. 0, 1 e 6 nelle seguenti situazioni (ogni
situazione parte dallo stato della cache della situazione precedente):


dopo l'accesso ai blocchi aventi i seguenti indirizzi
(l'ordine di accesso ai blocchi è
da sinistra a destra):
[226, 402, 280, 66, 246, 250, 435, 235, 27, 478, 112, 444, 269,
419, 430];


dopo l'accesso al blocco avente indirizzo: 478;


dopo l'accesso al blocco avente indirizzo: 411.


Per ogni punto (1), (2) e (3), si riportino le seguenti informazioni:


la lista corrispondente allo slot numero k
(per ogni slot k richiesto dall'esercizio);
usare la notazione: Hashtable[k]: [b1, b2, ...]


lista LRU; usare la notazione: LRU list: [b1, b2, ...]


elementi LRU e MRU; usare la notazione: LRU: b1, MRU: b2
dove b1, b2, ... sono indirizzi di blocchi. Si usi [ ] per indicare la lista vuota.


L'assenza delle suddette informazioni o l'uso di una notazione diversa da quella
indicata equivale a subire una penalizzazione nel punteggio.
Risposta:
Domanda 3:
Si consideri un file system inizialmente composto dai file [0, 1, 2, 3] e si supponga
che si effettuino le seguenti modifiche:


Giorno
File modificati/aggiunti


0
[4, 5, 6, 7]


1
[1, 8, 9, 10]


2
[11, 12, 13]


3
[]


4
[14, 15]


5
[16, 17, 18, 19]


6
[0, 6, 9, 20]


7
[8]


Supponendo:


di effettuare il backup ogni giorno,


di eseguire il backup totale ogni 6
giorni a partire dal giorno 0 (cioè, il giorno 0,
poi il giorno 6, ...),


che ogni backup totale contenga tutti
i file presenti inizialmente nel sistema o
aggiunti successivamente dal giorno 0 sino al giorno della sua esecuzione, e


che tutte le modifiche/aggiunte mostrate nello scenario sopra riportato
avvengano prima di effettuare un backup,


svolgere i seguenti punti:


Mostrare il contenuto dei BACKUP
DIFFERENZIALI effettuati nei giorni [3, 4, 7] dello
scenario sopra riportato.


Elencare i backup usati per il ripristino dei file fino al giorno
4 (incluso) nella
situazione del punto 1.


Supponendo che il backup al giorno 2 diventi
inutilizzabile, è possibile effettuare il
ripristino del punto 2? Motivare la risposta.


Mostrare il contenuto dei BACKUP INCREMENTALI
effettuati nei giorni [3, 4, 7] dello
scenario sopra riportato.


Elencare i backup usati per il ripristino dei
file fino al giorno 4 (incluso) nella
situazione del punto 4.


Supponendo che il backup al giorno 2 diventi inutilizzabile,
è possibile effettuare il
ripristino del punto 5? Motivare la risposta.


Per i punti 1 e 4, si usi la seguente notazione:
Giorno X: [file1, file2, ...], cioè il
backup al giorno X contiene i file file1, file2, ...
Per i punti 2 e 5, si usi la seguente notazione:
[giornoX, giornoY, ...], dove l'ordine
del ripristino è da sinistra verso destra
(cioè, il ripristino del backup al giornoX viene
effettuato prima di quello al giornoY).
L'assenza delle suddette informazioni o l'uso di una notazione diversa da quella
indicata equivale a subire una penalizzazione nel punteggio.
Risposta:
Domanda 4:
Si consideri un sistema RAID livello 5 costituito da 7 dischi identici (inizialmente
vuoti) e con blocchi (strip) da 1 byte, e si supponga di
effettuare, una dopo l'altra, le
operazioni di seguito indicate dove,
per ciascuna operazione, il controller RAID riceve i
comandi di lettura/scrittura come un'unica richiesta.
Nel formulare le risposte, si
numerino a partire da 0 sia i dischi sia le strip (non farlo equivale a subire una
penalizzazione nel punteggio).

Si riporti il contenuto dei dischi n. 4, 5, 6 dopo aver
scritto la seguente sequenza di
byte: b[0]=11001110, b[1]=00101100, b[2]=01111011, b[3]=00100100, b[4]=01100000,
b[5]=10110100, b[6]=01000110, b[7]=10010011, b[8]=00110101, b[9]=10100011,
b[10]=10111111, b[11]=01011101.
Si indichino i vari byte con la notazione "b[i]"
(con i=0,1,...,11) e non con la sequenza
di bit corrispondente, tranne per gli eventuali byte di
parità che invece devono essere
calcolati e indicati esplicitamente
(non farlo equivale a subire una penalizzazione nel
punteggio).
si riporti il numero di READ, indicando quante di queste sono effettuate in
parallelo, quando si effettua la lettura dei byte b[1], b[2], b[3], b[8].
si dica quale metodo per il calcolo della parità
(additiva o sottrattiva) risulti essere
più efficiente (o se è indifferente), giustificando la risposta,
quando si modifica il byte
b[1] da 00101100 a 10100011, b[3] da 00100100 a 11011011, b[5] da 10110100 a
01001011

Risposta:
Punto 1:
Parity Stripe 0:
b[0] 11001110 
 $\bigoplus$ 


b[1] 00101100  $\bigoplus$ 


b[2] 01111011  $\bigoplus$ 


b[3] 00100100 \bigoplus


b[4] 01100000 \bigoplus


b[5] 10110100 =
01101001


Disco 0
Disco 1
Disco 2
Disco 3
Disco 4
Disco 5
Disco 6


11001110
00101100
01111011
00100100
01100000
10110100
01101001


Parity Stripe 1:
b[6]= 01000110 
\bigoplus


b[7]= 10010011 \bigoplus


b[8]= 00110101 \bigoplus


b[9]= 10100011 \bigoplus


b[10]=10111111 \bigoplus


b[11]=01011101 =
10100001


Disco 0
Disco 1
Disco 2
Disco 3
Disco 4
Disco 5
Disco 6


11001110
00101100
01111011
00100100
01100000
10110100
01101001


01000110
10010011
00110101
10100011
10111111
10100001
01011101


Punto 2:
2 read necessarie.
La prima read in parallelo per i byte b[0] b[1] e b[2],
la seconda per b[8].
Non si possono effettuare tutte in una singola read perché il contenuto
di b[8] è nello stesso disco di b[2].
Punto 3:
b[1]
00101100 -> 10100011
Sottrattiva:
old b[1] 
\bigoplus


new b[1] \bigoplus


parity stripe 0 =
00101100 
\bigoplus


10100011 \bigoplus


01101001 =
11100110
In questo modo otteniamo la nuova strip di parità.
Conviene utilizzare la parity sottrattiva perché le modifiche sono "small write",
ovvero modifiche di poche strip.
La stessa cosa è valida per b[3] e b[5] perché sono tutti
cambiamenti che sono al di sotto del punto di crossover.
La parity addittiva avrebbe fatto la lettura di tutte le strip vecchie della stripe.
Quindi in questo caso di b[0], b[2], e b[4]. Per un totale di 5 letture
e 2 scritture, ovvero la strip da modificare e la strip di parità.
Invece la parity sottrattiva usa solo due letture e due scritture per ognuna delle
strip da modificare.
Domanda 6:
Si consideri uno schema di indirizzamento CHS in cui sono utilizzati 8 bit per il
numero di cilindri, 6 bit per il numero di testine,
e 10 bit per il numero di settori per
traccia.
Si converta l'indirizzo LBA 11400145 in notazione CHS (C,H,S).
Mostrare i calcoli (non farlo equivale a subire una penalizzazione nel punteggio).
Risposta:
Per prima cosa trasforiamo il numero di bit in numero totale di
cilindri, testine e settori.
N_C = 2^{8} =256

N_H = 2^{6} =64

N_S = 2^{10} =1024

Ora possiamo effettuare la conversione da LBA a CHS.
c = LBA / (N_H \times N_S) \rightarrow 11400145 / (64 \times 1024) = 173

h = (LBA / N_S) \mod N_H \rightarrow (11400145 / 1024) \mod 64 = 60

s = (LBA \mod N_S)+1 \rightarrow (11400145 \mod 1024)+1 = 978