Esame di Sistemi Operativi 1 : 9 settembre 2004 Domanda 1

Domanda 1
Descrivere significato e possibili modi d'uso (anche con esempi) dell'istruzione Test & Set?

Domanda 2
Descrivere in pseudo-codice l'algoritmo del fornaio.

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

Domanda 4
Descrivere l'algoritmo di aging utilizzato per il  rimpiazzamento delle pagine.

Domanda 5
Descrivere e spiegare il significato dei seguenti attributi di file:

 -r-xr-x--x    john   students   844255   Jan 8 9:01   aabb

Qual e' l'effetto del comando "chmod 711 aabb"?

Esercizio 1
Considerate i seguenti  processi

Risorse condivise
  semaphore  S=2, T=0;
  int x=0;
Processo P1
{
    down(&T);
    x:=5;
   up(&S);
   x:=6;
  
}
 Processo P2
{
   down(&S);
   x:=1;
   up(&T);
   down(&S);
   x:=10;
  write(x);
  
}

supponete che i processi vengano eseguiti concorrentemente sulla stessa CPU.

  1. Determinare tutti i possibili output di tale programma concorrente.

  2. Cosa succede se inizialmente i semafori hanno valore S=1 e T=0?

  3. Considerate sempre l'inizializzazione S=1 e T=0.
    Inserire una sola nuova chiamata down su  S o T ed in uno tra P1 e P2 in modo da ottenere
    come unico possibile output il valore 10
Soluzione

 1. Con  S=2 e T=0 l'insieme dei possibili risultati e'  {5, 6, 10 }

2. Con S=1 e T=0 otteniamo invece {6, 10 }

3. Ponendo down(&T) prima di x:=6 in P1 forziamo l'output a 10.

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

9

P2

3

17

P3

7

10

P4

11

9

P5

15

6

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(completamento) dei processi.

Soluzione 

P1

P2

P1

P3

P2

P4

P1

P5

P3

P2

P4

P5

P3

P2

P4

P2

0-4

4-8

8-12

12-16

16-20

20-24

24-25

25-29

29-33

33-37

37-41

41-43

43-45

45-49

49-50

50-51

Nota: Quando arriva P3 P1 e' gia in coda! Quindi allo scadere del II quanto viene schedulato di nuovo
P1 (la strategia di base  e' sempre FIFO) e cosi via....
  1. Tempo di attesa=Tempo di completamento-Tempo di esecuzione
    Media tempo di attesa dei processi: ((25-0-9)+(51-3-17)+(45-7-10)+(50-11-9)+(43-15-6) = 127/5

  2. Tempo di completamento= Istante di completamento - Tempo di arrivo
    Valore medio del tempo di turnaround dei processi: (25+(51-3)+(45-7)+(50-11)+(43-15))/5 = 178/5
Esercizio 3
Considerare la seguente stringa di riferimenti di un processo alla memoria in un sistema con memoria virtuale

7 6 10 8 3 1 4 5 4 3 6 7 8 9 10 11 8  9 2 4 

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:

  7      6   10    8    3  1     4   5   4   3   6   7   8   9   10   11     8    9   2     4 

   7    6   10    8    3   1     4   5   4   3   6   7   8   9   10   11     8    9    2    4
         7     6   10   8   3     1   4   5   4   3   6   7   8     9   10   11    8    9    2
                7    6   10  8     3   1    1  5   4   3   6   7     8     9   10   11   8    9
                      7    6   10   8   3   3    1  5   4   3   6     7     8     9   10  11    8   
                            7    6   10  8   8    8   1  5   4   3     6     7     7    7   10  11 

Esercizio 4
Data una memoria partizionata in maniera fissa come segue:
Partizione
 Dimensione
0 200K
1
 500K
2
 300K
3
 600K

e dato che il sistema operativo deve allocare quattro processi P1 di 212K, P2 di 417K, P3 di 112K e P4 di 427K
(in quest'ordine),  scrivere in quale partizione  il sistema alloca ciascun processo se viene usato l'algoritmo:
  1. First Fit
  2. Best Fit
  3. Worst Fit
(se il processo non puo' essere allocato, segnare "X" come partizione).

Soluzione
Nota: le partizioni sono fisse: non si possono mettere due processi nella stessa partizione!
  1. First fit: P1:1, P2: 3, P3:0, P4:X
  2. Best fit:  P1:2, P2: 1, P3:0, P4:3
  3. Worst fit: P1:3, P2:1, P3:2, P4:X

Esercizio 5
Considerare un file system dove la dimensione di un blocco logico e' 2KB e con indirizzi di blocchi a 16 bit.
  1. Determinare la dimensione massima di un file in caso di
    1. allocazione concatenata
    2. allocazione indicizzata con due livelli di blocco indice

  2. Determinare il numero di blocchi effettivamente assegnati ad un file di 200KB per i due tipi di allocazione.
Soluzione
Indirizzi a 16 bit --> 216 blocchi fisici
  1. Dim. massima
    1. Allocazione concatenata: ogni blocco ha 2KB-2B=2046 Byte di spazio dati quindi il file piu grande ha dimensione 216 * 2046 Byte
    2. Allocazione indicizzata: ogni blocco puo contenere 2048/2=1024 puntatori, quindi con due livelli: (1024)2*2 K (senza considerare spazio per la tabella)

  2. Numero blocchi
    1.  Dim file/Spazio in un blocco = 200 KB/2046 = 101 blocchi
    2.  100 blocchi