Esame di Sistemi Operativi 1 : 21 Gennaio 2005
Esame completo: rispondere a tutte le domande
I Compitino: domande 1-5
II Compitino: domande 6-10 (*)
(*) Chi ha fatto laboratorio 03-04 puo' non rispondere alla domanda 10

Punteggio

1
 2
 3
 4
 5
 6
 7
 8
 9
 10
 Totale
Scritto completo
 3
 3
 3
 4
 4
 4
 3
 3
 3
 4
 34
I Compitino




8
 6
 6
 6
 8
 34
II Compitino
 6
 6
 6
 8
 8




34

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

Sol: vedi lucidi

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

Sol: vedi lucidi

Domanda 3
Discutere la differenza fra process table e user area in un sistema Unix

Sol: vedi lucidi

Domanda 4
Considerate i seguenti  processi

Risorse condivise
  semaphore S=1;
  int x=0;
Processo P1
{
while (true) do
 begin
  down(S);
  x:=x+1;
  up(S);
end  
}
 Processo P2
{
 while (true) do
 begin
    down(S);
    write(x);
    x:=x+1;
    up(S);
 end  
}

supponete che i processi vengano eseguiti concorrentemente sulla stessa CPU.
  1. Quali sono le regioni critiche in questo programma?

  2. Vale la proprieta' di mutua esclusione? E la proprieta' di progresso?

  3. Descrivere il comportamento e i possibili output del programma concorrente.

Sol:

  1. Le sezioni critiche sono: x:=x+1 per P1 e   write(x); x:=x+1; per P2

  2. Mutua esclusione (accesso alla s.c. protetto da S in P1 e P2)
    Progresso non vale: P2 puo aspettare indefinitamente mentre P1 accede alla sua s.c.
    (non c'e' alternanza stretta)

  3. Vi sono 3 tipi di comportamenti: 
    1. P1 entra ed esce dalla s.c. P2 aspetta (nessun output)
    2. P2 entra ed esce dalle s.c. P1 aspetta (P2 continua a stampare lo stesso valore di x)
    3. P1 e P2 entrano in interleaving nella s.c.

      L'insieme degli output si puo caratterizzare tramite la sequenza generica di numeri naturali

      < n1-m1  n2-m2 ..... ni-mi ..... >

      dove ni-mi = sequenza ni (ni)+1 (ni)+2 ... mi,  mi < n(i+1), i>=0

Domanda 5
8 processi richiedono contemporaneamente (cioe' arrivano tutti al tempo 0) di poter utilizzare la CPU.
La lunghezza dei CPU-burst  e le priorità sono dati nella seguente tabella (supponiamo che numeri bassi
corrispondano a priorità alte e viceversa):

  P1 P2 P3 P4 P5 P6
 P7
 P8
CPU burst 5
 4
 3 2 6 7
 10
 8
Priorità 3
 5 2 1 4 6
 7
 8

Disegnare il diagramma di Gantt e calcolare il tempo di completamento di ogni processo per ciascuna
delle seguenti politiche di scheduling della CPU:

  1.  FIFO (supponendo che i processi siano stati inseriti in coda in ordine crescente di indice) 
  2.  Shortest Job First 
  3. Priorità 
  4.  Round Robin (con quanto di tempo q = 2 e trascurando il tempo di context switch)
Sol: applica definizioni viste a lezione
Domanda 6
Descrivere l'algoritmo di aging (basato sull'uso di array di bit) utilizzato per il  rimpiazzamento delle pagine.

Sol: ogni pagina ha ref bit + array bit di lunghezza fissata,
        ad ogni interrupt di clock: right-shift di 1 pos ed inderimento ref-bit nel bit + significativo dell'array   
        selezione vittima: pagina con valore memorizzato nell'array (in binario) minore

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

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

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.

Sol: costruendo tabella come visto a lezione => 15 page fault

Domanda 8
Si supponga che, durante la fase della fsck che verifica la consistenza dei blocchi vengano prodotti i seguenti vettori:

indice di blocco:                  0    1    2    3    4    5    6    7    8    9   10  11  12  13  14  15  16  

vettore blocchi liberi:          0    1    1    1    1    1    0     1    0    1    0    0    0    1    0    5    3  

vettore blocchi occupati:     0    2    0    0    0    1    1     1    0    1    0    0    0    3    0    1    1   

spiegare quali sono le azioni (passo per passo) intraprese dalla fsck per ripristinare uno stato consistente del file system.

Sol: vedi esempi lucidi

Domanda 9
Considerate un disco con capacita' 2 GB e blocchi da 4 KB.

Supponendo di utilizzare solo multipli di 2, quanti byte servono per gli indirizzi di blocco?

Sia N il numero di byte degli indirizzi di blocchi calcolato nella domanda 1.
Calcolare la dimensione della FAT.

Quanti blocchi occupa la FAT se memorizzata su disco?

Sol: Num blocchi: 2Gb/4Kb ==> 2^19 quindi servono 19 bit ==> 4 byte per indirizzi di blocco
       DimFat= 2^19 *4 byte
       Blocchi Fat= DimFat/4Kb

Domanda 10
A cosa serve, cosa fa e come si configura il processo init in Linux?

Sol: Completa fase di boot (mount e check f.s., creazione demoni, ...), controlla processi getty,
       eredita processi orfani, smonta f.s. e interrompe servizi durante shutdown
        Init si configura tramite /etc/inittab dove si specifica runlevel e relativi servizi attivabili