Esame di Sistemi Operativi 1 : 22 Aprile 2004

Punteggio

D1
D2
D3
D4
D5
E1
E2
E3
E4
Totale
Punti
4
3
3
3
3
6
4
3
3
32

Domanda 1

Definire le proprieta' di progresso e attesa limitata.
Mostrare  un'esempio di programma concorrente per il quale vale
la proprieta' di attesa limitata ma non vale progresso.

Vedi lucidi

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

Vedi lucidi (ogni processo prende un ticket (Max+1), entra il processo con ticket piu basso ....)

Domanda 3

Descrivere lo schema di risoluzione degli indirizzi logici utilizzato nella paginazione.

Vedi lucidi (<pag.logica,offset> ---> Tabella pagine --> <pag.fisica,offset>)

Domanda 4
Spiegare a cosa serve e come funziona la segmentazione con paginazione.

Vedi lucidi (segmenti paginati, indirizzi =<segmento,pag.logica,offset>, ecc)

Domanda 5

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

Vedi lucidi (Seq. di K bit, shift a destra ed ins. del ref bit, selezione pagina con valore seq. minore..)
Nota: alg. utilizzato per il rimpiazzamento delle pagine non per lo swap di processi.


Esercizio 1
Considerate i seguenti  processi
Risorse condivise
  semaphore  S=1, T=0, U=0, V=1
  int x;
Processo P1
{
      down
(&S);
       read(x);
       if (x=0) then
           up(&T);
         down
(&U);
       else
           up(&T);
         down(&V);
       endif;
     write(x);
}
Processo P2
{
    down(&T);
    x:=100;
    up(&U);
    up(&V);  
}

supponete che i processi vengano eseguiti concorrentemente sulla stessa CPU.
  1. Al variare dell'input, quali possibili output vengono prodotti
    durante l'esecuzione contemporanea di P1 e P2 in CPU?
     
  2. Al variare dell'input, quali sono i possibili output  se i
    valori iniziali dei semafori sono invece S=1, T=0, U=1,V=1 ?

  3. Quali valori iniziali dei semafori occorrono per ottenere un'unico possibile ouput
    indipendentemente dall'input e dalla schedulazione dei processi?

Soluzione
Sia K il valore in input
  1. Se K=0, stampa 100. Se K=\=0 stampa 100 oppure K.

  2. Stampa K oppure 100.

  3. Con S=1,T=0,U=0,V=0 otteniamo come unico output possibile 100.

Esercizio 2
Cinque processi, P1, P2, P3, P4 e P5 richiedono contemporaneamente di poter utilizzare la CPU.
La lunghezza dei CPU-burst  e le priorità sono dati nella seguente tabella (numeri bassi = priorità alte):

  P1 P2 P3 P4 P5
CPU burst 4 6 8 4 2
Priorità 5 4 3 2 1

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)
Soluzione
  1. Sequenza: P1, P2, P3, P4, P5
  2. Sequenza: P5,P1,P4,P2,P3
  3. Sequenza: P5,P4,P3,P2,P1
  4. Sequenza: P1,P2, P3, P4, P5,P1,P2,P3,P4,P2,P3,P3

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.

  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

Considerate un disco con capacita' 1024 MB e blocchi da 8 KB.

- Quanti byte servono per gli indirizzi di blocco? (1,2 o 4?)

Sia N il numero di byte degli indirizzi di blocchi calcolato nella domanda 1.

- Calcolare la dimensione (in byte) della FAT.

- Quanti blocchi occupa la FAT se memorizzata su disco?

- Qual'e' il contenuto della FAT relativamente ad un file "pippo"
  i cui dati sono memorizzati (in sequenza) nei blocchi  3, 6, 0 e 10?

Soluzione
Ricordiamo che 1KB=1024 byte = 210byte ;   1 MB=220 byte.
  1. Servono 4 byte:    Cap. disco/dim. blocco = 230/213=217 blocchi indirizzabili con 4 byte

  2. Dimensione FAT: 217* 4 byte = 219 byte  = 512 KB

  3. La FAT occupa 64 blocchi (512KB/8KB)

  4. FAT: 0 (10) .... 3(6) .... 6(0) .... 10 (-) .....
Esercizio 5

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.

Soluzione

1)   (0,0) --> (1,0)

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

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


2) (C,K) --> (0,K) se C,K>0

vettore blocchi liberi:          1   0    1    1    1    0    0    0      1   0    1    1    1    0    1    0   0 

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

3) (0,K) --> (0,1) + K-1 copie se K>0

vettore blocchi liberi:           0    0     0   0    1     0     0    0     1   0    1    1    1     0    1    0   0 

vettore blocchi occupati:      1    1    1    1    0    1     1    1    0    1    0    0    0    1    0    1    1