Sistemi Operativi e Laboratorio, Prova del 6/6/2019

Nome: __________________ Cognome: _________________ Matricola:___________ fila:__ posto: __ corso:___ aula: ______

Esercizio 1 (4 punti) Un sistema operativo simile a UNIX gestisce la memoria con paginazione a domanda mediante il processo PageDaemon (con parametri Lotsfree e MinFree), che applica l’algoritmo di sostituzione Second Chance. Ad ogni intervento, il processo PageDaemon si comporta nel modo seguente:

• se NumeroDiBlocchiLiberi ≥ MinFree e NumeroDiBlocchiLiberi < LotsFree, applica ripetutamente l’algoritmo Second Chance sui blocchi che contengono pagine caricate in memoria, e ogni volta scarica la pagina da questo selezionata come vittima, finchè NumeroDiBlocchiLiberi = Lotsfree + 2;

• se NumeroDiBlocchiLiberi < MinFree esegue lo swapout di uno o più processi, finché diviene NumeroDiBlocchiLiberi ≥ Lotsfree. Per lo swapout dei processi si segue l’ordine alfabetico.

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, utilizzato da Second Chance). Al tempo t (quando sono presenti i processi A, B, C, D , la Core Map ha la configurazione mostrata in tabella (non sono mostrati i blocchi assegnati al sistema operativo) e il viene attivato il processo il PageDaemon.

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

Pag 0 5 10 12 7 0 1 0 2 9 6 3 1 2 6 2 7 3 7 11 2

Rif 1 0 0 1 1 0 1 0 0 1 1 1 1 1 1 1 1 0 1 1 0

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

Core Map al tempo t

Si chiede quali sono le pagine scaricate dal processo PageDaemon e la configurazione della CoreMap nelle seguenti ipotesi (alternative): a) PageDaemon ha parametri Lotsfree= 5 e MinFree= 3 e il puntatore dell’algoritmo di SecondChance è posizionato sul blocco 7; b) PageDaemon ha parametri Lotsfree= 7 e MinFree= 3 e il puntatore dell’algoritmo di SecondChance è posizionato sul blocco 14. Soluzione Ipotesi a) Si ha NumeroDiBlocchiLiberi = MinFree e NumeroDiBlocchiLiberi < LotsFree e pertanto PageDaemon applica ripetutamente l’algoritmo Second Chance per scaricare 4 pagine.

• Vengono scaricate le pagine B-0; C-2; B-3; A-2.

• La configurazione finale della CoreMap è la seguente:

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

Pag 0 5 10 12 7 0 1 9 6 3 1 2 6 2 7 7 11

Rif 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0

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

Ipotesi b) Si ha NumeroDiBlocchiLiberi = MinFree e NumeroDiBlocchiLiberi < LotsFree e pertanto PageDaemon applica ripetutamente l’algoritmo Second Chance per scaricare 6 pagine.

• Vengono scaricate le pagine B-3, A-2, C-5, C-10, A-0, B-0.

• La configurazione finale della CoreMap è la seguente:

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

Pag 0 12 7 1 2 9 6 3 1 2 6 2 7 7 11

Rif 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0

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

Sistemi Operativi e Laboratorio, Prova del 6/6/2019 Soluzione Ipotesi a)

• Vengono scaricate le pagine: _______________________________________________________

• La configurazione finale della CoreMap è la seguente:

Proc

Pag

Rif

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

Ipotesi b)

• Vengono scaricate le pagine: _______________________________________________________

• La configurazione finale della CoreMap è la seguente:

Proc

Pag

Rif

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

Esercizio 2 (5 punti)

Spiegare la differenza tra algoritmi di sostituzione locali e globali. Dire poi in quale di queste due classi rientra l’algoritmo del working set motivando la risposta. (max. 5 righe):

______________________________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

Si consideri un sistema che gestisce la memoria con paginazione a domanda, applicando una politica di controllo dinamico del Working Set. Per ogni processo sono definiti i seguenti dati:

• l’intero MaxBlocchi: massimo numero di blocchi disponibili per il caricamento del Working Set, che viene ridefinito periodicamente dal demone WorkingSetManager;

• l’intero PagineResidenti, uguale al numero di pagine attualmente caricate in memoria e variabile nel tempo;

• la tabella delle pagine di ogni processo, con campi Blocco, R (bit di pagina riferita) e TUR (tempo di ultimo riferimento). In particolare, il valore di R è quello usuale (0 se la pagina non è stata riferita, 1 altrimenti). Invece il valore di TUR viene aggiornato al tempo attuale ogni volta che l’algoritmo di sostituzione trova il bit R della pagina a 1 e lo resetta.

Quando un processo avanza, per ogni pagina riferita:

• se il riferimento non determina un Page Fault la pagina viene marcata come riferita;

• se il riferimento determina Page Fault, la pagina riferita viene caricata nel blocco libero individuato dal primo elemento della lista dei blocchi liberi in memoria (che si suppone sempre non vuota), viene aggiornata conseguentemente la tabella delle pagine (inizializzando il valore di TUR al tempo attuale e ponendo R=1) e viene incrementata la variabile PagineResidenti;

Il demone WorkingSetManager, che interviene periodicamente, esegue le seguenti operazioni per ogni processo: Fase 1) per ogni pagina residente in memoria, se R= 1 assegna TUR= tempo attuale e pone R=0. Fase 2) per ogni processo:

• se PagineResidenti>MaxBlocchi:

• scarica dalla memoria principale PagineResidenti – MaxBlocchi, selezionandole in ordine crescente del valore di TUR;

Sistemi Operativi e Laboratorio, Prova del 6/6/2019 • se per l’ultima pagina scaricata si ha TUR > tempo_attuale – 20, incrementa MaxBlocchi;

• se invece PagineResidenti< MaxBlocchi, decrementa MaxBlocchi. Al tempo T1=25, subito dopo un intervento di WorkingSetManager, per il processo P si ha MaxBlocchi = 6 e la tabella delle pagine ha la seguente configurazione:

Pagina Blocco R TUR

0 - - -

1 - - -

2 - - -

3 20 0 19

4 - - -

5 - - -

6 - - -

7 10 0 14

8 - - -

9 - - -

10 8 0 24

11 6 0 2

12 15 0 7

Inoltre, sempre al tempo T1, la lista dei blocchi liberi in memoria sia: → 50 → 51 → 52 → 53 → 54 → …., Tra il tempo T1 e il tempo T2=35 avanza il processo P, poi al tempo T2 viene eseguito nuovamente il demone WorkingSetManager. Si chiede di mostrare il valore di PagineResidenti, di MaxBlocchi e la tabella delle pagine del processo P al tempo T2=35 prima dell’esecuzione del WorkingSetManager; al termine della prima fase di esecuzione del WorkingSetManager (al tempo T3=36) e al termine dell’esecuzione del WorkingSetManager (al tempo T4=37), nelle seguenti ipotesi (da considerare in alternativa):

1) Durante la sua esecuzione il processo P riferisce nell’ordine le seguenti pagine: 8 (26), 10(27), 0(28), 3(29), 8(30), 11(31), 0(32), 11(33), 3(34), 2(35) (nota: tra parentesi è indicato l’istante di riferimento).

T2: Tabella delle Pagine T3: Tabella delle Pagine T4: Tabella delle Pagine

Pagina Blocco R TUR Pagina Blocco R TUR Pagina Blocco R TUR

0 0 0

1 1 1

2 2 2

3 3 3

4 4 4

5 5 5

6 6 6

7 7 7

8 8 8

9 9 9

10 10 10

11 11 11

12 12 12

Pagine Residenti= ______________; Pagine Residenti= ______________; Pagine Residenti= ______________; MaxBlocchi=__________________; MaxBlocchi=__________________; MaxBlocchi=__________________;

2) Durante la sua esecuzione il processo P riferisce nell’ordine le seguenti pagine: 11(26), 2(27), 0(28), 2(29), 11(30), 6(31), 0(32), 2(33), 9(34), 5(35) (nota: tra parentesi è indicato l’istante di riferimento).

T2: Tabella delle Pagine T3: Tabella delle Pagine T4: Tabella delle Pagine Pagina Blocco R TUR Pagina Blocco R TUR Pagina Blocco R TUR

0 0 0

1 1 1

2 2 2

3 3 3

4 4 4

5 5 5

Sistemi Operativi e Laboratorio, Prova del 6/6/2019 6 6 6

7 7 7

8 8 8

9 9 9

10 10 10

11 11 11

12 12 12

Pagine Residenti= ______________; Pagine Residenti= ______________; Pagine Residenti= ______________; MaxBlocchi=__________________; MaxBlocchi=__________________; MaxBlocchi=__________________; Soluzione

1) il processo P e riferisce le pagine: 8 (26), 10(27), 0(28), 3(29), 8(30), 11(31), 0(32), 11(33), 3(34), 2(35) T2=35: Tabella delle Pagine T3: Tabella delle Pagine T4: Tabella delle Pagine

Pagina Blocco R TUR Pagina Blocco R TUR Pagina Blocco R TUR

0 51 1 28 0 51 0 36 0 51 0 36

1 - - - 1 - - - 1 - - -

2 52 1 35 2 52 0 36 2 52 0 36

3 20 1 19 3 20 0 36 3 20 0 36

4 - - - 4 - - - 4 - - -

5 - - - 5 - - - 5 - - -

6 - - - 6 - - - 6 - - -

7 10 0 14 7 10 0 14 7

8 50 1 26 8 50 0 36 8 50 0 36

9 - - - 9 - - - 9 - - -

10 8 1 24 10 8 0 36 10 8 0 36

11 6 1 2 11 6 0 36 11 6 0 36

12 15 0 7 12 15 0 7 12

Pagine Residenti= 8; MaxBlocchi=6; Pagine Residenti= 8; MaxBlocchi=6; Pagine Residenti=6; MaxBlocchi=6

2) il processo P e riferisce le pagine: 11(26), 2(27), 0(28), 2(29), 11(30), 6(31), 0(32), 2(33), 9(34), 5(35) T2=35: Tabella delle Pagine T3: Tabella delle Pagine T4: Tabella delle Pagine

Pagina Blocco R TUR Pagina Blocco R TUR Pagina Blocco R TUR

0 51 1 28 0 51 0 36 0 51 0 36

1 - - - 1 - - - 1 - - -

2 50 1 27 2 50 0 36 2 50 0 36

3 20 0 19 3 20 0 19 3 - - -

4 - - - 4 - - - 4 - - -

5 54 1 35 5 54 0 36 5 54 0 36

6 52 1 31 6 52 0 36 6 52 0 36

7 10 0 14 7 10 0 14 7 - - -

8 - - - 8 - - - 8 - - -

9 53 1 34 9 53 0 36 9 53 0 36

10 8 0 24 10 8 0 24 10 - - -

11 6 1 2 11 6 0 36 11 6 0 36

12 15 0 7 12 15 0 7 12 - - -

Pagine Residenti= 10; MaxBlocchi=6; Pagine Residenti= 10; MaxBlocchi=6; Pagine Residenti=6; MaxBlocchi=7

Sistemi Operativi e Laboratorio, Prova del 6/6/2019 Esercizio 3 (5 punti) Spiegare (in al max. 5 righe) i vantaggi gli svantaggi di un file system FAT rispetto ad FFS ed NTFS.

_____________________________________________________________________________________

_____________________________________________________________________________________

_____________________________________________________________________________________

_____________________________________________________________________________________

_____________________________________________________________________________________ In un file system simile a UNIX i blocchi del disco hanno ampiezza di 1 Kbyte e i puntatori ai blocchi sono a 32 bit. Gli i-node contengono, oltre agli altri attributi, 5 puntatori diretti e 3 puntatori indiretti (indiretto singolo, doppio e triplo). Il primo blocco del disco ha indice 0. Si consideri il file corrispondente all’i-node 22, lungo 12.000 bytes, e allocato sulla sequenza di blocchi contigui da 2.000 a 2.011. Il blocco indice di primo livello collegato dal puntatore indiretto singolo dell’i-node è il 4.000. Il file è aperto in lettura/scrittura ed è individuato dal file descriptor fd, l’ultimo byte letto dal file è il 8.999, per cui la posizione dell’I/O pointer per la prossima operazione sul file è il byte 9.000. In questo stato viene effettuata un’operazione di scrittura: write(fd, &buf, 6.000) con cui si scrivono 6.000 caratteri (ciascuno di un byte) sul file a partire dalla posizione 9.000. Si suppone che l’operazione termini con successo. Nell’ipotesi che, al momento nel quale venga richiesta l’operazione di scrittura, i blocchi liberi nel disco siano (nell’ordine): 1000, 1001, 1002, 1003, 1004, 1005, 1006, … e che i blocchi vengano allocati ai file attingendo a questa lista in ordine crescente, si chiede:

1. Quanti (e quali) blocchi logici contiene il file dopo la scrittura e a quali blocchi fisici corrispondono 2. Quali blocchi del disco sono stati modificati dall’operazione di scrittura 3. Quale è il contenuto dell’i-node del file dopo l’operazione di scrittura 4. Quali è il contenuto del blocco 4.000 (blocco indice di primo livello) 5. Quanti byte del file sono contenuti nell’ultimo blocco fisico allocato al file

Soluzione

1. Dopo la scrittura il file ha dimensione 15.000 bytes, quindi contiene 15.000 div 1024 +1 = 15 blocchi logici numerati da 0 a 14. I blocchi logici sono allocati rispettivamente sui blocchi fisici da 2.000 a 2.011 e da 1.000 a 1.002.

2. Dato che la scrittura inizia a partire dal blocco logico 9.000 div 1024 = 8, i blocchi logici modificati dall’operazione di scrittura sono quelli da 8 a 14, corrispondenti ai blocchi fisici: 2008, 2009, 2010, 2011, 1000, 1001, 1002. In aggiunta è modificato anche il blocco indice 4000.

3. L’i-nodo del file è:

Puntatore 0 1 2 3 4 5 6 7

Valore del puntatore 2000 2001 2002 2003 2004 4000 - -

4. Il file ha bisogno di un solo blocco indice, il 4.000, che contiene:

Indice di elemento nel blocco Valore del puntatore

0 2005

1 2006

2 2007

3 2008

4 2009

5 2010

6 2011

Sistemi Operativi e Laboratorio, Prova del 6/6/2019 7 1000

8 1001

9 1002

10 -

5. L’ultimo blocco dati (il 1002), contiene ((15000) mod 1024) byte = 664 byte

Soluzione 1. Dopo la scrittura il file contiene i blocchi logici da_____________ a _____________

corrispondenti ai blocchi fisici: ___________________________________________

2. I blocchi fisici modificati dall’operazione di scrittura sono: _____________________________ ________________________________________________________________________

3. L’i-nodo del file è:

Puntatore 0 1 2 3 4 5 6 7

Valore del puntatore

4. Il contenuto del blocco 4.000 è:

Indice di elemento nel blocco

Valore del puntatore Indice di elemento nel blocco

Valore del puntatore

0 10

1 11

2 12

3 13

4 14

5 15

6 16

7 17

8 18

9 19 …

5. L’ultimo blocco dati contiene __________________________________ byte

Esercizio 4 (3 punti)

Spiegare la differenza tra thread I/O bound e CPU-Bound (max. 5 righe):

______________________________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

In un sistema ad un dato istante di tempo t termina il processo in esecuzione mentre nella coda pronti sono presenti i processi A, B,C,D,E, con durate residue di esecuzione mostrate nella tabella.

Processo Tempo di arrivo Durata

A t-5 23

B t-4 41

C t-3 12

Sistemi Operativi e Laboratorio, Prova del 6/6/2019 D t-2 15

E t-1 20

Assumendo che tutti i processi avanzino senza mai sospendersi fino alla loro terminazione e che i tempi di esecuzione dello scheduler e della commutazione di contesto siano trascurabili, calcolare il tempo di permanenza nel sistema di ogni processo (definito come differenza tra il tempo di completamento dell’esecuzione e il tempo di arrivo nel sistema,) e il tempo medio di permanenza dei processi, con le seguenti politiche di scheduling 1. Politica round robin con quanto di tempo di 10 ms e con i processi in coda pronti nell’ordine A, B, C, D, E. 2. Politica SJF (Shortest Job First). Soluzione

1. Politica round robin:

processo in esecuzione

Inizio quanto di tempo (t+…)

Fine quanto di tempo (t+…)

Tempo residuo di esecuzione

A 0 10 13

B 10 20 31

C 20 30 2

D 30 40 5

E 40 50 10

A 50 60 3

B 60 70 21

C 70 72 Terminato al tempo 72

D 72 77 Terminato al tempo 77

E 77 87 Terminato al tempo 87

A 87 90 Terminato al tempo 90

B 90 111 Terminato al tempo 111

Pertanto:

PROCESSO TEMPO DI ARRIVO

TERMINA ESECUZIONE

TEMPO DI PERMANENZA NEL SISTEMA

A t-5 t+90 95

B t-4 t+111 115

C t-3 t+72 75

D t-2 t+77 79

E t-1 t+87 88

Tempo medio di permanenza: (95+115+75+79+88)/5=90,4 msec 2. Politica SJF:

PROCESSO TEMPO DI ARRIVO INIZIA ESECUZIONE

TERMINA ESECUZIONE

TEMPO DI PERMANENZA NEL SISTEMA

C t-3 t+0 t+12 15

D t-2 t+12 t+12+15= t+27 29

E t-1 t+27 t+27+20= t+47 48

A t-5 t+47 t+47+23= t+70 75

B t-4 t+70 t+70+41= t+111 115

Tempo medio di permanenza: (15+29+48+75+115)/5=56,4 msec Soluzione

1. Politica round robin:

PROCESSO TEMPO DI ARRIVO

TERMINA ESECUZIONE

TEMPO DI PERMANENZA NEL SISTEMA

Sistemi Operativi e Laboratorio, Prova del 6/6/2019 A 0

B 0

C 0

D 0

E 0

Tempo medio di permanenza: _________________________ msec 2. Politica SJF:

PROCESSO TEMPO DI ARRIVO INIZIA ESECUZIONE

TERMINA ESECUZIONE

TEMPO DI PERMANENZA NEL SISTEMA

C 0

D 0

E 0

A 0

B 0

Tempo medio di permanenza: _________________________ msec

Esercizio 5 (5 punti)

In un file system NTFS con blocchi di dimensione 2KB e puntatori a 32 bit, la lista dei blocchi liberi per l’allocazione contiene i blocchi: 1000, 1001, 1002, 1003, 5000, 5001, 5002, ….

Nel file system è presente il file LITTLE di dimensione 9.000 bytes, che è allocato sui blocchi: 900, 901, 902, 950, 951 e che è già aperto dal file system con file descriptor fd. Si considerino i seguenti casi (in alternativa):

1. sul file viene eseguita l’operazione: write(fd, &buf, 8000) a partire dalla fine del file (quindi dal byte 9.000)

2. sul file viene eseguita l’operazione: write(fd, &buf, 13.000) a partire dall’inizio del file (quindi dal byte 0)

3. sul file viene eseguita l’operazione: write(fd, &buf, 4096) a partire dal byte 8192

dire per ogni caso quali run occupa il file e quanti bytes sono contenuti nell’ultimo blocco allocato al file.

caso Run del file Bytes allocati nell’ultimo blocco del file

1)

2)

3)

Inoltre nel file system è anche allocato il file VERYLITTLE che contiene solo la stringa “almost empty”. Discutere il contenuto dell’MFT record che lo descrive (max. 5 righe)

__________________________________________________________________________________

__________________________________________________________________________________

__________________________________________________________________________________

Sistemi Operativi e Laboratorio, Prova del 6/6/2019 __________________________________________________________________________________

__________________________________________________________________________________

Soluzione

Caso Run del file Bytes allocati nell’ultimo blocco del file

1) <900,3>, <950,2>, <1000,4> 616

2) <900,3>, <950,2>, <1000,2> 712

3) <900,3>, <950,2>, <1000,1> 2048

Nel caso del file VERYLITTLE, l’intero file è memorizzato direttamente nel MFT record:

metadati… Nomefile , “VERYLITTLE”

Contenuto, “almost empty”

NULL…

Esercizio 6 (5 punti)

Discutere i vantaggi della tecnica della segmentazione rispetto a meccanismi di allocazione con partizioni variabili e di traduzione degli indirizzi con una coppia di registri base/limite (max. 5 righe)

__________________________________________________________________________________

__________________________________________________________________________________

__________________________________________________________________________________

__________________________________________________________________________________

__________________________________________________________________________________ Si consideri un sistema che gestisce la memoria con paginazione e tabelle delle pagine a due livelli. Gli indirizzi logici hanno lunghezza di 32 bit e l’indirizzo logico è così ripartito: indice primo livello 13 bit; indice secondo livello 8 bit, offset 11 bit. Ogni elemento di una tabella di primo o di secondo livello contiene un indice di pagina fisica formato da 20 bit più 12 bit contenenti indicatori per il gestore della memoria e attributi di protezione della pagina. Si chiede:

1. la dimensione delle pagine logiche e dei blocchi fisici; 2. il numero di elementi contenuti in una tabella di primo e di secondo livello 3. la dimensione in byte di una tabella di primo e di secondo livello; 4. la massima dimensione della memoria fisica, espressa in numero di blocchi e in numero di byte. 5. quanto è grande (in bytes) lo spazio di memoria virtuale di un processo mappato da una tabella di secondo

livello 6. la tabella di secondo livello necessaria per tradurre l’indirizzo logico 1.672.000 (supponendo che la MMU

nella sua cache non abbia le informazioni necessarie per tradurre questi indirizzi). 7. quali tabelle di secondo livello sono necessarie per mappare un’area di memoria virtuale di 1MB che inizia

all’indirizzo: 3.000.000 Soluzione

1. dimensione delle pagine logiche: ____________________________ dimensione dei blocchi fisici: ____________________________

Sistemi Operativi e Laboratorio, Prova del 6/6/2019 2. numero di elementi in una tabella di primo livello: ____________________________

numero di elementi in una tabella di secondo livello: ____________________________ 3. dimensione in byte di una tabella di primo livello: ____________________________

dimensione in byte di una tabella di secondo livello: ____________________________ 4. la massima dimensione della memoria fisica: ____________blocchi, quindi

____________________________ bytes 5. spazio di memoria virtuale di un processo mappato da una tabella di secondo livello:

____________________________ 6. tabella di secondo livello necessaria per tradurre l’indirizzo logico 1.672.000:

____________________________ 7. tabelle di secondo livello necessarie per mappare un’area di memoria virtuale di 1MB che inizia all’indirizzo

3.000.000: ______________________________ Soluzione

1. dimensione delle pagine logiche: 2 KB; dimensione dei blocchi fisici: 2 KB;

2. numero di elementi in una tabella di primo livello: 8 K = 8192 elementi; numero di elementi in una tabella di secondo livello: 256 elementi;

3. dimensione in byte di una tabella di primo livello: 32 KB; dimensione in byte di una tabella di secondo livello: 1 KB;

4. la massima dimensione della memoria fisica: 220 blocchi, quindi 220*211=231 bytes = 2 GB 5. spazio di memoria virtuale di un processo mappato da una tabella di secondo livello: 211*28= 512 KB 6. la tabella di secondo livello necessaria per tradurre l’indirizzo logico 1.672.000 è data da 1.672.000 div 2^19

= 3 7. tabelle di secondo livello necessarie per mappare un’area di memoria virtuale di 1MB che inizia all’indirizzo

3.000.000: la prima di tali tabelle è la 3.000.000 div 2^19 = 5, quindi, dato che ogni tabella mappa ½ MB, servono: 5,6,7, che contengono rispettivamente 145.728 Bytes, 524.288 bytes e 378.560 bytes.

Esercizio 7 (3 punti) Un disco RAID di livello 4 è composto da 5 dischi fisici, numerati da 0 a 4. Le strip corrispondono a blocchi. Il disco di indice 4 è ridondante e il suo blocco di indice i contiene la parità dei blocchi di indice i dei dischi non ridondanti, cioè dei dischi 0, 1, 2 e 3. Al tempo T il controller del RAID tenta di leggere la strip 100 sul disco 0, ma il comando fallisce perché la strip viene rilevata come danneggiata. Discutere come il controller può intervenire per mascherare il guasto (max 5 righe):

__________________________________________________________________________________

__________________________________________________________________________________

__________________________________________________________________________________

__________________________________________________________________________________

__________________________________________________________________________________ Una volta riparato il disco guasto, la stripe 100, contenente i blocchi di indice 100 di tutti i dischi fisici ha il contenuto mostrati in tabella (nella quale non è mostrato il contenuto del disco 4 ridondante).

Disco 0 0 0 1 0 1 0 0 1

Disco 1 1 1 0 0 1 1 0 1

Disco 2 1 0 0 1 1 0 0 0

Disco 3 1 0 1 0 1 1 0 1

Disco 4

Sistemi Operativi e Laboratorio, Prova del 6/6/2019 Dopo la riparazione del disco, al tempo T1 arriva un comando di scrittura nella strip 100 del disco 0 del valore: 0 1 0 1 0 1 1 0. Si chiede:

1) Quale è il contenuto della strip 100 del disco ridondante dopo la riparazione del guasto e prima del tempo T1 2) Quali sono i dischi fisici sui quali si deve operare per eseguire la scrittura richiesta al tempo T1 e di quali

operazioni si tratta; 3) Quali di queste operazioni sono eseguibili in parallelo e quali vanno eseguite sequenzialmente? 4) Il contenuto della strip 100 dei dischi che vengono che vengono modificati.

Soluzione 1) Contenuto della strip 100 del disco ridondante 4 dopo la riparazione del guasto e prima del tempo T1:

Disco 4

2) Si devono eseguire le seguenti operazioni (indicarle secondo l’ordine nel quale vengono eseguite):

1 disco/i: _______operazione: _______________ per quale motivo: ________________________________ 2 disco/i: _______operazione: _______________ per quale motivo: ________________________________ 3 disco/i: _______operazione: _______________ per quale motivo: ________________________________ 4 disco/i: _______operazione: _______________ per quale motivo: ________________________________ 5 disco/i: _______operazione: _______________ per quale motivo: ________________________________ 6 disco/i: _______operazione: _______________ per quale motivo: ________________________________

3) Sono eseguibili in parallelo le operazioni: _____________________________________ _______________________________________________________________________ Vanno eseguite sequenzialmente le operazioni: _________________________________ _______________________________________________________________________

4) Queste operazioni modificano la strip 100 dei dischi _________________ e i nuovi contenuti sono i seguenti:

Disco 0

Disco 1

Disco 2

Disco 3

Disco 4

Soluzione

1) Contenuto della strip 100 del disco ridondante 4 dopo la riparazione del guasto e prima del tempo T1:

Disco 4 1 1 0 1 0 0 0 1

2) Si devono eseguire le seguenti operazioni:

1 lettura del vecchio valore sulla strip 100 del dischi 0 (per il ricalcolcolo della parità) 2 lettura del vecchio valore sulla strip 100 del dischi 4 (per il ricalcolcolo della parità) 3 scrittura sulla strip 100 del disco 0 (per modificare il contenuto)

4 scrittura sulla strip 100 del disco 4 (per modificare la parità ) 3) Sono eseguibili in parallelo le due operazioni di lettura [1,2], poi, in seguito, sono eseguibili in parallelo le

due operazioni di scrittura [3,4] 4) Queste operazioni modificano la strip 100 dei dischi 0 e 4 e i nuovi contenuti sono i seguenti:

Disco 0 0 1 0 1 0 1 1 0

Disco 1 1 1 0 0 1 1 0 1

Disco 2 1 0 0 1 1 0 0 0

Disco 3 1 0 1 0 1 1 0 1

Disco 4 1 0 1 0 1 1 1 0

Sistemi Operativi e Laboratorio, Prova del 6/6/2019 Nome: _________________ Cognome: ________________ Matricola:_____________ corso:____

MODULO LABORATORIO

Esercizio 1 (4 punti): Realizzare i metodi push e pop di una coda concorrente Q di capacità fissa (N>0) aventi la seguente segnatura:

int push(queue_t* Q, void* p); void* pop(queue_t* Q);

L’implementazione dei due metodi deve essere fatta utilizzando le primitive della libraria POSIX Thread (PThread). Nello specifico:

• il metodo push blocca il thread chiamante se la coda Q è piena; ritorna 0 in caso di inserimento con successo e -1 in caso di errore settando opportunamente errno. Se l’invocazione va a buon fine, il dato puntato dal parametro p viene inserito in fondo alla coda Q.

• il metodo pop blocca il thread chiamante se la coda è vuota; ritorna NULL in caso di errore settando opportunamente errno, altrimenti ritorna il puntatore al dato estratto dalla testa della coda Q.

Definire il tipo queue_t con tutto quanto necessario per implmentare i due metodi push e pop.

void* pop(queue_t *Q) { if (Q==NULL) { …………….; …………….; } ……………………..; while( Q->len == 0 ) { ……………………………….; } data = Q→buffer[Q→head]; Q→head = (Q→head +1) % Q->N; ……………….; ……………….; ……………….; }

typedef struct queue_t {

} queue_t;

int push(queue_t *Q, void *data) { if (Q==NULL || data==NULL) { ……………………; ……………………; } …………………...; while(Q→len >= Q->N) { ……………………………...; } Q→buffer[Q→tail] = data; Q→tail = (Q→tail +1) % Q->N; ……………….; ……………….; ……………….; }

Sistemi Operativi e Laboratorio, Prova del 6/6/2019 Soluzione

** va bene anche if (Q→len == 1) pthread_cond_broadcast(&q→empty);

°° va bene anche if (Q→len == (q→N-1)) pthread_cond_broadcast(&q→full); Esercizio 2 (2 punti): Dato il seguente frammento di codice C, dare l’output del programma coprendo sia i casi di successo che di fallimento delle system calls fork ed execlp. Output: ……………………………………………………………………………………………………………………………………………………………………………………

#include <sys/types.h> #include <sys/wait.h> #include <unistd.h> #include <string.h>

int main() { write(1,"ciao ", strlen("ciao ")); if (fork() == 0) { execlp("echo1", "echo", "mondo", "!", NULL); write(1, "goodbye\n", strlen("goodbye\n")); } wait(NULL); write(1, "bye\n", strlen("bye\n")); return 0; }

int push(queue_t *Q, void *data) { if (Q==NULL || data==NULL) { errno=EINVAL; return -1; } pthread_mutex_lock(&Q→mutex); while( Q→len >= Q->N) pthread_cond_wait(&Q→full, &Q→mutex); Q→buffer[Q→tail] = data; Q→tail = (Q→tail +1) % Q->N; Q→len += 1; pthread_cond_signal(&Q→empty); ** pthread_mutex_unlock(&Q→mutex); return 0; }

void* pop(queue_t *Q) { if (Q==NULL) { errno=EINVAL; return NULL; } pthread_mutex_lock(&Q→mutex); while( Q->len == 0) pthread_cond_wait(&Q→empty, &Q→mutex); void* data = Q→buffer[Q→head]; Q→head = (Q→head +1) % Q->N; Q→len -= 1; pthread_cond_signal(&Q→full); °° pthread_mutex_unlock(&Q→mutex); return data; }

typedef struct queue_t { void **buffer; size_t head, tail, N, len; pthread_mutex_t mutex; pthread_cond_t full, empty; } queue_t;

Sistemi Operativi e Laboratorio, Prova del 6/6/2019 ……………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………… Soluzione Considerendo OK successo e KO fallimento, si ha:

fork OK, execlp OK fork KO fork OK, execlp KO

ciao mondo ! bye

ciao bye ciao goodbay bye bye