-

Compito di Sistemi Operativi, Prof. Mancini - 30 settembre 1999

1. (punti: -1,4)

Dati due processi concorrenti Pi e Pj:

 

(a)    se A e B sono dei comandi eseguiti rispettivamente da Pi e Pj , è sempre possibile stabilire una relazione di precedenza fra A e B;

(b)   solo con i meccanismi di sincronizzazione i due processi possono imporre il vincolo che l’azione A di Pi preceda l’azione  di Pj , o viceversa;

(c)    se A e B sono due comandi eseguiti rispettivamente da Pi e Pj , è generalmente impossibile stabilire una relazione di precedenza fra A e B;

(d)   con i meccanismi di sincronizzazione i due processi non possono imporre il vincolo che l’azione A di Pi preceda l’azione di B di Pj , o viceversa;

(e)    nel modello concorrente Pi e Pj procedono indipendentemente e senza il pieno controllo delle proprie velocità di avanzamento;

(f)     nel modello concorrente Pi e Pj procedono indipendentemente e con il pieno controllo delle proprie velocità di avanzamento;

(g)    nessuna delle affermazioni precedenti è corretta.

 

2. (punti: -1.5,4)

 

Assumendo in ogni caso un comportamento bloccante per la primitiva receive:

 

(a)    i modelli di consumazione si dicono sincroni, se la send ha un comportamento bloccante;

(b)   i modelli di comunicazione si dicono sincroni, se la send non ha un comportamento bloccante;

(c)    la forma di comunicazione chiamata “rendez-vous” richiede un comportamento non bloccante della send;

(d)   la forma di comunicazione chiamata “rendez-vous” richiede un comportamento bloccante della send;

(e)    la forma di comunicazione chiamata “rendez-vous esteso” richiede un comportamento non bloccante della send;

(f)     la forma di comunicazione chiamata “rendez-vous esteso” richiede un comportamento bloccante della send;

(g)    nessuna delle affermazioni precedenti è corretta.

 

3. (punti: -1,4)

La seguente porzione di codice contenente una chiamata alla primitiva  fork di Unix genera un processo figlio Pi:

if ($pid = fork) {

codice-A

     } else if (defined $pid) {

            codice-B

     } else {

            codice-C

     }

     codice-D

 

(a)      Il processo Pi esegue sicuramente il codice-A e potrebbe eseguire il codice-D;

(b)     Il processo Pi esegue sicuramente il codice-A e non esegue mai il codice-D;

(c)      Il processo Pi esegue sicuramente il codice-B e potrebbe eseguire il codice-D;

(d)     Il processo Pi esegue sicuramente il codice-B e non esegue mai il codice-D;

(e)      Il processo Pi esegue sicuramente il codice-C e potrebbe eseguire il codice-D;

(f)       Il processo Pi esegue sicuramente il codice-C e non esegue mai il codice-D;

(g)      nessuna delle affermazioni precedenti è corretta.

 

4. (punti: -1,4)

Si assuma che in un sistema Unix Si e Sk siano due sistemi di archiviazione ospitati sui dispositivi fisici diversi e che Sk venga montato sul direttorio Dik di Si:

(a)      se il direttorio Dik è vuoto, allora Dik viene rimosso;

(b)     se il direttorio Dik è vuoto, allora il monitoraggio di Sk e Si fallisce;

(c)      se il direttorio Dik non è vuoto, allora tutti i suoi discendenti (archivi e direttori) diventato inaccessibili ed in Dik sono visibili solo gli archivi che in realtà sono definiti nel direttorio radice Sk;

(d)     se il direttorio Dik non è vuoto, allora tutti i suoi discendenti (archivi e direttori) vengono rimossi ed in Dik sono visibili solo gli archivi che in realtà sono definiti nel direttorio radice Sk;

(e)      se il montaggio ha successo, rimane a carico dell’utente specificare esplicitamente quale dei sistemi di archiviazione intende di volta in volta utilizzare;

(f)       se il montaggio non ha successo, non è a carico dell’utente specificare esplicitamente quale dei sistemi di archiviazione intende di volta in volta utilizzare;

(g)      nessuna delle affermazioni precedenti è corretta.

 

5. (punti: 6)

Illustrare in al più 60 parole la struttura dati MappaDescrittoriDiArchivio, o I-node bitmap, ed il suo utilizzo.

 

6. (punti: 6)

Considerare un insieme di cinque processi P1, P2, P3 , P4, P5 con i seguenti tempi di arrivo e tempi di esecuzione in millisecondi:

 

Processo

Tempo di arrivo

Tempo di esecuzione

P1

0

10

P2

14

18

P3

6

9

P4

10

9

P5

2

5

 

Assegnare questo insieme di processi ad un processore in base alla politica Round Robin considerando un quanto di tempo di 4 millisecondi.

 

Calcolare il valor medio del tempo di attesa ed il valor medio del tempo di turnaround dei processi.

 

7. Considerare la seguente stringa di riferimenti di un processo alla memoria in un sistema con memoria virtuale

 

S=2 4 6 8 3 1 6 4 5 4 3 8 5 9 7 0 3 1 7 8

 

(a)  (punti: 3)

 

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.

 

(b)  (punti: 3)

 

Illustrare il comportamento dell’algoritmo Second Chance di sostituzione delle pagine per una memoria fisica di 5 blocchi. Calcolare il numero di page fault che si verificano.

 

8. (punti: 9)

Utilizzare un tipo di dato Monitor per realizzare il meccanismo della  chiave con copia multipla. Una chiave multipla è una struttura dati su cui sono definite due operazioni: lock e unlock. Una operazione di lock consente ad un processo P di impossessarsi di una chiave K: qualunque altro processo tenti di eseguire una lock su K viene messo in attesa fino a quando P la non rilascia con una unlock. A questo punto K viene assegnata ad uno soltanto dei processi eventualmente in attesa su di essa, o altrimenti lasciata libera per una nuova lock. Un processo può acquisire più copie di una chiave già in suo possesso: un processo P che esegua una lock su una chiave in suo possesso può proseguire senza bloccarsi; ma per rilasciare la chiave dovrà fare tante unlock su K quante sono le lock che vi ha eseguito.

9. (punti: 9)

Realizzare un programma Perl efficiente che riceva in ingresso un array di interi (positivi e negativi) e che calcoli il massimo fra le sue somme di tutti gli intervalli di interi consecutivi. Valutare la complessità in tempo e spazio del programma.

Esempio: (-3,2,1,-1,2,-5); Massimo=4
 
 

Risultati della prova

1. b,c,e
2. a,d,e
3. c
4. c,f

5.

La MappaDescrittoriDiArchivio è un vettore di dimensione pari al numero degli i-node; ogni elemento di questo vettore è un bit che indica se l’i-node corrispondente è assegnato ad un archivio o meno.

6.

a)  

P1

P5

P1

P3

P5

P4

P1

P2

P3

P4

P2

P3

P4

P2

0-4

4-8

8-12

12-16

16-17

17-21

21-23

23-27

27-31

31-35

35-39

39-40

40-41

41-51

b) media tempo di attesa dei processi: 89/5
c) valore medio del tempo di turnaround dei processi: 140/5

7.

a: Algoritmo LRU (pag. 469 del Maestrini):

 

 

 

 LRU

2

4

6

8

3

1

6

4

5

4

3

8

5

9

7

0

3

1

7

8

0

2

2

2

2

2

1

1

1

1

1

1

8

8

8

8

8

3

3

3

3

1

 

4

4

4

4

4

4

4

4

4

4

4

4

4

7

7

7

7

7

7

2

 

 

6

6

6

6

6

6

6

6

6

6

6

9

9

9

9

9

9

8

3

 

 

 

8

8

8

8

8

5

5

5

5

5

5

5

5

5

1

1

1

4

 

 

 

 

3

3

3

3

3

3

3

3

3

3

3

0

0

0

0

0

 

p

p

p

p

p

p

 

 

p

 

 

 
p

 

p

p

p

p

p

 

p

Numero di page fault: 5+9

b: Algoritmo Second Chance: (pag. 473 del Maestrini)

 TURNOMS=4

 

TurnoMS

 

SC 

2

4

6

8

3

1

6

4

5

4

3

8

5

9

7

0

3

1

7

8

0

21

21

21

21

21

11

11

11

11

11

11

10

10

10

71

71

71

70

71

71

1

 

41

41

41

41

40

40

41

40

41

41

40

40

40

40

01

01

00

00

00

2

 

 

61

61

61

60

61

61

60

60

60

81

81

81

81

81

80

11

11

11

3

 

 

 

81

81

80

80

80

51

51

51

51

51

50

50

50

31

31

31

30

4

 

 

 

 

31

30

30

30

30

30

31

30

30

91

91

91

91

90

90

81

 

p

p

p

p

p

p

 

 

p

 

 

 
p

 

p

p

p

p

p

 

p

Numero page fault: 5+9

 

8.

- 30 settembre 1999 -