Esame di Sistemi Operativi 1 : 14 Gennaio 2004

Punteggio

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

Tipo A


Domanda 1
Definire le proprieta' di mutua esclusione, progresso e bounded waiting.
Mostrare  un'esempio di programma concorrente per il quale vale progresso ma non vale
bounded waiting.

Soluzione
Mutua esclusione: se il processo Pi sta eseguendo la
sua sezione critica, allora nessun altro processo può eseguire la
propria sezione critica.

Progresso: se nessun processo è nella sezione critica e
esiste un processo che desidera entrare nella propria sezione
critica, allora l'esecuzione di tale processo non può essere
posposta indefinitamente.

Attesa limitata (bounded waiting): se un processo P ha richiesto di entrare
nella propria sezione critica, allora il numero di volte che si
concede agli altri processi di accedere alla propria sezione critica
prima del processo P deve essere limitato.

In un programma in cui la scelta del processo è fatta in modo casuale dall'insieme dei processi
in attesa (ad es. utilizzando numeri random) vale progresso ma non bounded waiting (un processo 
potrebbe soffrire di starvation).


Domanda 2
Descrivere la differenza fondamentale tra una trap e un'interruzione.

Soluzione

Le trap e le interruzioni sono alla base del funzionamento dual-mode di un sistema operativo.
Una trap è generata da una chiamata software al sistema operativo e permette di passare da esecuzione 
a livello utente ad esecuzione a livello kernel. 

Un'interruzione è causata invece da un dispositivo hardware e provoca il passaggio a modalità kernel 
per la gestione di eventi quali la terminazione di operazioni di I/O.


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

Soluzione

Il doppio accesso alla memoria si riduce con una cache dedicata per
le entry delle page tables: \emph{registri associativi} detti anche
Il translation look-aside buffer (TLB) è un insieme di registri associativi 
utilizzati per memorizzare le entry della page table utilizzate più frequentemente.
Il virtual page number A viene confrontato con tutte le entry
contemporaneamente. Se A è nel TLB (TLB hit), si usa il numero del frame 
nel TLB. Altrimenti, la MMU esegue un normale lookup nelle page table in memoria,
e sostituisce una entry della TLB con quella appena trovata. 
Il S.O. viene informato solo nel caso di un page fault 
(...protezioni, validità, ...).

Variante software: I TLB miss vengono gestiti direttamente dal S.O.
nel caso di una TLB miss, la MMU manda un interrupt al
processore (TLB fault), si attiva una apposita routine del S.O., che gestisce le page table
e la TLB esplicitamente. 


Domanda 4
Descrivere l'algoritmo del clock a due lancette utilizzato dal demone delle pagine di Unix.

Soluzione

Pagedaemon utilizza una politica di rimpiazzamento  globale
(non si guarda il processo a cui appartiene la pagina) e una
variante dell'algoritmo dell'orologio: l'orologio (CLOCK) a 2 lancette.
L'algoritmo usa due puntatori (lancette) per scorrere
la lista delle pagine allocate nella  core map
Fino a che NFL < lotsfree si eseguono i seguenti passi:
La prima lancetta azzera il reference bit della pagina a cui punta
correntemente; La seconda sceglie la pagina vittima: se trova r=0 (i.e. la pagina non è stata usata nel periodo trascorso
tra il passaggio delle due lancette): Se dirty-bit=1 il frame viene salvato su disco
il frame viene aggiunto alla free-list poi si fanno avanzare i due puntatori.

La distanza tra i puntatori (handspread) viene decisa al boot, per liberare frame 
abbastanza rapidamente. Se le lancette sono vicine: solo le pagine realmente usate rimarranno in memoria
Se le lancette sono distanti 359 gradi = algoritmo dell'orologio (la seconda passa dopo un giro)

Domanda 5
Descrivere le caratteristiche principali e confrontare tra loro (con un occhio di
riguardo alla capacita' di indirizzamento) i file system FAT-12, FAT-16 e FAT-32 e
un file system basato su i-node stile Unix.


Soluzione:
I file system FAT-12, FAT-16 e FAT-32 utilizzano la FAT (mem. all'inizio di un disco) per tenere traccia dei blocchi fisici associati ad un file.
La FAT e' una tabella indicizzata sul numero di blocco fisico. Il contenuto di una entry rappresenta il blocco seguente di un determinato file
(cioe' una FAT rappresenta un'insieme di liste concatenate).
La differenza tra i vari FS FAT sta nel numero di bit utilizzati per l'indirizzamento del disco (risp. 12, 16, 28).
La capacita' dipende dalla dimensione dei blocchi:
-- FAT-12 da  2MB (blocchi da 0.5KB) a 16 MB (blocchi da 4KB)
-- FAT-16 da  128MB (blocchi da 2KB) a 2048 MB (blocchi da 32KB)
-- FAT-32 da  1TB (blocchi da 4KB) a 2TB (blocchi da 324KB)

In Unix gli indirizzi di blocco sono mantenuti dentro un'inode (insieme as altre info sul file):
10 indirizzi diretti, 1 singolo indiretto, 1 doppio indiretto.
La capacita' dipende dalla dim. dei blocchi e dei puntatori: con blocchi da 4KB e puntatori da 4byte ~ 4TB


Esercizio 1
Considerate i seguenti  processi

Risorse condivise
  semaphore  S=1, T=1, U=0;
  int x=0;
Processo P1
{
      down(&S);
       if (x=0) then up(&T)
                    else up(&U);
       x:=3;
     write(x);
}
 Processo P2
{
    down(&T);
    x:=1;
    up(&S);   
}
 Processo P3
{
    down(&U); 
    x:=10;
    up(&S);
}

supponete che i processi vengano eseguiti concorrentemente sulla stessa CPU.

  1. In questo programma possono verificarsi race conditions per la variabile x? (Motivare la risposta)

  2. Quali output vengono prodotti da tale programma concorrente? (Motivare la risposta)

  3. Cosa succede se inseriamo l'istruzione down(&S) nel processo P1 subito prima dell'istruzione write(x)?
          ...
           x:=3;
          down(&S);
         write(x);
          ...
Soluzione

  • Si, la variabile x non 'e protetta adeguatamente. Ad esempio, P1 e P2 possono accedere ad x simultaneamente.
  • In generale: P1 e P2 lavorano in concorrenza (race conditions su x).
    P3 puo partire solo dopo P2 e solo se P3 pone x=1;
    Quando attivi P1 e P3 lavorano in concorrenza (race conditions su x).
    Vi sono quindi vari interleaving:
    1. Viene eseguito prima tutto P1: stampa 3
    2. Viene eseguito P1 fino a x:=3, poi P2 pone x a 1, e quindi P2 stampa 1
    3. Viene eseguito prima P2, poi P1 che trova x>0, sveglia P3, P3 pero' e' l'ultimo a modificare x: stampa 3
    4. Viene eseguito prima P2, poi P1 che trova x>0, sveglia P3, si blocca dopo aver modificato x, poi viene mandato in esecuzione P3, e poi si torna a P1: stampa 10
  • Cosi' facendo inseriamo un punto di sincronizzazione in P1: write(x) verra' eseguita solo se P2 o P3 hanno prima eseguito una up.
    Tuttavia rimangono le race conditions tra i tre assegnamenti.
    Quindi i possibili output rimangono sempre 1, 3 e 10.


    • 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 (supponiamo che numeri bassi
    corrispondano a priorità alte e viceversa):

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

    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. FIFO
      Gantt chart:
      P1 (0-10), P2 (10-16), P3 (16-18), P4 (18-22), P5 (22-30)  

      Tempi di completamento:
      P1: 10,
      P2: 16,
      P3: 18,
      P4:22,
      P5: 30

    2. SJF
      Gantt chart:
      P3 (0-2), P4 (2-6), P2 (6-12), P5 (12-20), P1 (20-30)

      Tempi di completamento:
      P1: 30,
      P2: 12,
      P3: 2,
      P4:6,
      P5: 20

    3. Priorità
      Gantt chart:
      P4 (0-4), P3 (4-6), P1 (6-16), P5 (16-24), P2 (24-30)  

      Tempi di completamento:
      P1: 16,
      P2: 30,
      P3: 6,
      P4:4,
      P5: 20

    4. Round Robin
      Gantt chart:
      P1 (0-2), P2 (2-4), P3 (4-6), P4 (6-8), P5 (8-10),P1 (10-12), P2 (12-14), P4 (14-16),
      P5 (16-18),P1 (18-20), P2 (20-22), P5 (22-24),P1(24-26),P5(26-28),P1(28-30)

      Tempi di completamento:
      P1: 30,
      P2: 22,
      P3: 6,
      P4:16,
      P5: 28
    Esercizio 3
    Considerate la seguente lista circolare associata alle pagine utilizzate dal processo A:

      (P1, 10, 1,  0) --> (P2,  9, 0, 0) --> (P3, 5, 0, 1) --> (P4, 7 ,0, 0 ) --> (P5, 11 ,0, 1 )  ->  puntatore all'indietro a P1                                                                                   
         
    dove in (N,T,R,M): N=Numero della pagina; T=Tempo di ultimo uso; R=Reference bit;  M=Modified bit.
    Supponete che il processo A abbia bisogno di caricare la pagina P6 e che occorra rimpiazzare una esistente.

    Determinare la pagina selezionata per il rimpiazzamento e la nuova lista delle pagine ottenuta utilizzando
    l'algoritmo WSClock  con le seguenti assunzioni: contatore del tempo virtuale di CPU del processo A = 12;
    periodo del working set =4; la lancetta punta inizialmete a P1.

    Soluzione:
    Viene selezionata la pagina P4 (P1 e P2 sono nel ws, P3 ha il bit M a 1).
    La nuova lista e'

    (P1, 10, 0,  0) --> (P2,  9, 0, 0) --> (P3, 5, 0, 0*) --> (P6, 12 ,1, 0 ) --> (P5, 11 ,0, 1 )
                                                                                                |
    0*= se supponiamo che la copia su disco vada a buon fine.


    Esercizio 4
    Dato un file system FAT con blocchi di 2KB  e il seguente frammento di FAT,
    dire in quali blocchi fisici sono collocati i seguenti byte:

    1. byte 6758 del file "pippo" che inizia al blocco 4
    2. byte 4097 del file "pluto" che inizia al blocco 3
    3. byte 2044 del file "paperino" che inizia al blocco 5

    Frammento FAT :

    Entry
    		 Contenuto
    0
    		 10
    1
    		 2
    2
    		 0
    3
    		 6
    4
    		 1
    5
    		 8
    6
    		 7
    7
    		 11
    8
    		 12
     

    Soluzione

    1. Dim. blocco = 2*1024= 2048 bytes. Il byte 6758 di pippo si trova nel quarto blocco
      Percorrendo la FAT: I blocco: 4, II blocco: 1, III blocco: 2, IV blocco: 0
      Quindi l'indirizzo fisico del blocco e' 0

    2. Il byte 4096 di pluto si trova nel secondo (terzo) blocco se si parte da 1 (0), quindi nel blocco fisico 6 (7).

    3. Il byte 2044 del file "paperino" si trova nel primo blocco, quindi nel blocco fisico 5.


    Esercizio 5
    In una organizzazione dell'allocazione dei file simile a quella adottata in UNIX vi sono 14 puntatori nel descrittore di file
    (mantenuto in memoria durante l'accesso al file) di cui

    Se la dimensione di un blocco è 1Kb, e un puntatore occupa 4 bytes:
    1.  Qual è la dimensione massima di un file per il quale non sono necessari accessi aggiuntivi per accedere a qualunque blocco?
    2.  Qual è la dimensione massima di un file?
    3. Quanti accessi aggiuntivi sono necessari per accedere al byte alla posizione 300K?
    Soluzione
    Un blocco puo' contenere (dim. blocco/dim.puntatore=) 1024/4=256 puntatori a blocchi.
    1. La dim. massima di un file con blocchi accessibili solo tramite puntatori diretti e' 12*1KB=12 KB.

    2. La dim. massima di un file indirizzabile e' 12 KB+256 KB+2562 KB=65804 KB

    3. Il 300000-esimo byte di un file si trova in un blocco accessibile tramite puntatore doppiamente indiretto:
      occorrono quindi 2 accessi aggiuntivi (uno alla tabella esterna e uno a quella interna).

     


    Tipo B

    Esame di Sistemi Operativi 1 -  14 Gennaio 2004


    Punteggio

    		 D1
    		 D2
    		 D3
    		 D4
    		 E1
    		 E2
    		 E3
    		 E4
    		 E5
    		 Totale
    Punti
    		 5
    		 3
    		 4
    		 4
    		 6
    		 4
    		 2
    		 2
    		 2
    		 32

    Domanda 1
    Descrivere in pseudo codice una soluzione al problema del produttore-consumatore con i monitor.

    Soluzioni
    Vedi lucidi


    Domanda 2
    Cos'è  un semaforo?
    Dare una definizione delle operazioni up e down (anche chiamate P e V oppure wait e signal), e
    spiegare come queste possano essere implementate (in particolare come si possa garantire la loro atomicità).

    Soluzioni
    Un meccanismo di sincronizzazione per processi concorrenti implementato attraverso una variabile intera modificata
    atomicamente (...funzionamento, implementazione con code di processi, ecc).


    Domanda 3
    Descrivere l'algoritmo di base per la  sostituzione di pagine basato sul Working Set.

    Soluzione:
    Working set=insieme delle pagine utilizzate correntemente da un processo.
    Il s.o. mantiene un'approsimazione del working set di ogni singolo processo in memoria.
    Si seleziona una pagina al di fuori del working set.
    Ad esempio, si associa il tempo di ultimo uso, e fissato un paramentro di anzianita' di seleziona
    una pagina con eta' maggiore del parametro.
    Possibili implementazioni: WS con tempo di ultimo utilizzo (...), WSClock (...).


    Domanda 4
    Come sono organizzati i frame liberi della memoria principale in Windows 2000?

    Soluzione:
    Sono organizzati in 4 liste: pagine modificate, in attesa, libere, azzerate.
    Il gestore e i demoni spostano le pagine da una lista all'altra:
    Dopo un page fault la pagina rimpiazzata va in una tra le liste modificata/in attesa
    ecc ....

    Domanda 5
    A cosa serve, come e' organizzata, e come viene usata la tabella dei file aperti di in Unix?

    Soluzione:
    Unix tiene traccia dei file aperti sia localmente (tabella dei file associati ad un processo)
    sia globalmente (tabella dei descrittori dei file aperti).
    La prima tabella contiene dei puntatori alle entry della seconda.
    Operazioni quali "open" restituiscono un puntatore ad una entry della tabella dei file "locale".
    La seconda tabella mantiene informazioni quali la posizione nel file e il puntatore all'inode del file.
    In tal modo padre e figlio possono condividere ad. es la posizione corrente nel file dopo una fork.
    Un processo scorrelato  da essi otterra' invece una nuova entry (e quindi un nuovo cursore nel file).

    Esercizio 1
    Considerate i seguenti  processi

    Risorse condivise
      semaphore  S=1, T=1, U=0;
      int x=0;
    Processo P1
    {
          down(&S);
           if (x=0) then up(&T)
                        else up(&U);
           x:=3;
         write(x);
    }
    		 Processo P2
    {
        down(&T);
        x:=1;
        up(&S);   
    }
    		 Processo P3
    {
        down(&U); 
        x:=10;
        up(&S);
    }

    supponete che i processi vengano eseguiti concorrentemente sulla stessa CPU.

    1. In questo programma possono verificarsi race conditions per la variabile x? (Motivare la risposta)

    2. Quali output vengono prodotti da tale programma concorrente? (Motivare la risposta)

    3. Cosa succede se inseriamo l'istruzione down(&S) nel processo P1 subito prima dell'istruzione write(x)?
            ...
             x:=3;
            down(&S);
           write(x);
            ...
    Soluzione

  • Si, la variabile x non 'e protetta adeguatamente. Ad esempio, P1 e P2 possono accedere ad x simultaneamente.

  • In generale: P1 e P2 lavorano in concorrenza (race conditions su x).
    P3 puo partire solo dopo P2 e solo se P3 pone x=1;
    Quando attivi P1 e P3 lavorano in concorrenza (race conditions su x).
    Vi sono quindi vari interleaving:
    1. Viene eseguito prima tutto P1: stampa 3
    2. Viene eseguito P1 fino a x:=3, poi P2 pone x a 1, e quindi P2 stampa 1
    3. Viene eseguito prima P2, poi P1 che trova x>0, sveglia P3, P3 pero' e' l'ultimo a modificare x: stampa 3
    4. Viene eseguito prima P2, poi P1 che trova x>0, sveglia P3, si blocca dopo aver modificato x, poi viene mandato in esecuzione P3, e poi si torna a P1: stampa 10
  • Cosi' facendo inseriamo un punto di sincronizzazione in P1: write(x) verra' eseguita solo se P2 o P3 hanno prima eseguito una up.
    Tuttavia rimangono le race conditions tra i tre assegnamenti.
    Quindi i possibili output rimangono sempre 1, 3 e 10.


    • Esercizio 2

    Considerate i seguenti Job:

    Job
    		 Burst time
    		 Tempo di arrivo
    A
    		 2
    		 0
    B
    		 6
    		 1
    C
    		 5
    		 4
    D 3
    		 7


    Calcolare il tempo di esecuzione necessario a completare ogni job in ognuno dei seguenti casi:
    1. scheduler SJF  con preemption

    2. scheduler round robin con quanto di 2 unita' (e coda per i processi in attesa/nuovi processi)

    Soluzione
    1. SJF cn preemption
      Gantt chart
      A (0-2) B (2-7) D (8-11) C (11-16)

      Tempi compl:
      A=2
      B=7
      C=12
      D=4
    2. RR
      Gantt chart
      A(0-2) B(2-4) C(4-6)  B(6-8) C(8-10) D(10-12) B (12-14) C(14-15) D(15-16)

      Tempi compl:
      A=2
      B=13
      C=11
      D=12
    Esercizio 3
    Considerare la seguente stringa di riferimenti alla memoria di un processo in un sistema con memoria virtuale

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

    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
    Rif.
    		 10
    		 6
    		 2
    		 4
    		 6
    		 8
    		 3
    		 1
    		 4
    		 5
    		 11
    		 8
    		 7
    		 6
    		 10
    		 9
    		 7
    		 8
    		 11
    		 2
    1
    		 10
    		 10
    		 10
    		 10
    		 10
    		 10
    		 3
    		 3
    		 3
    		 3
    		 3
    		 8
    		 8
    		 8
    		 8
    		 8
    		 8
    		 8
    		 8
    		 8
    2
    		6
    		 6
    		 6
    		 6
    		 6
    		 6
    		 6
    		 6
    		 5
    		 5
    		 5
    		 5
    		 5
    		 10
    		 10
    		 10
    		 10
    		 10
    		 2
    3

    		2
    		 2
    		 2
    		 2
    		 2
    		 1
    		 1
    		 1
    		 1
    		 1
    		 7
    		 7
    		 7
    		 7
    		 7
    		 7
    		 7
    		 7
    4


    		4
    		 4
    		 4
    		 4
    		 4
    		 4
    		 4
    		 4
    		 4
    		 4
    		 6
    		 6
    		 6
    		 6
    		 6
    		 11
    		 11
    5




    		8
    		 8
    		 8
    		 8
    		 8
    		 11
    		 11
    		 11
    		 11
    		 11
    		 9
    		 9
    		 9
    		 9
    		 9
    Page Fault
    		 *
    		 *
    		 *
    		 *
    		*
    		 *
    		 *
    		*
    		 *
    		 *
    		 *
    		 *
    		 *
    		 *

    		*
    		 *

    In neretto:     pagina selezionata
    Numero di page fault:     16

     

    Esercizio 4
    Dato un file system FAT con blocchi di 3KB  e il seguente frammento di FAT,
    dire in quali blocchi fisici sono collocati i seguenti byte:

    1. byte 6758 del file "pippo" che inizia al blocco 8
    2. byte 4096 del file "pluto" che inizia al blocco 3
    3. byte 2044 del file "paperino" che inizia al blocco 4

    Frammento FAT :

    Entry
    		 Contenuto
    0
    		 7
    1
    		 2
    2
    		 11
    3
    		 5
    4
    		 3
    5
    		 20
    6
    		 13
    7
    		 1
    8
    		 0
     

    Soluzione

    1. Dim. blocco = 3*1024= 3072 bytes. Il byte 6758 di pippo si trova nel terzo blocco (6758/3072 =2.1).
      Percorrendo la FAT: I blocco: 8, II blocco: 0, III blocco: 7.
      Quindi l'indirizzo fisico del blocco e' 7

    2. Il byte 4097 di pluto si trova nel secondo blocco, quindi nel blocco fisico 5.

    3. Il byte 2044 del file "paperino" si trova nel primo blocco, quindi nel blocco fisico 4.

    Esercizio 5
    In una organizzazione dell'allocazione dei file simile a quella adottata in UNIX vi sono 13 puntatori nel
    descrittore di file  (mantenuto in memoria durante l'accesso al file) di cui

    Se la dimensione di un blocco è 1Kb, e un puntatore occupa 2 bytes:
    1.  Qual è la dim. massima di un file per il quale non sono necessari accessi aggiuntivi  per accedere
      a qualunque blocco?

    2.  Qual è la dim. massima di un file?

    3. Quanti accessi aggiuntivi sono necessari per accedere al byte alla posizione 2000K?
    Soluzione
    Un blocco puo' contenere (dim. blocco/dim.puntatore=) 1024/2=512 puntatori a blocchi.
    1. La dim. massima di un file con blocchi accessibili solo tramite puntatori diretti e' 10*1KB=10 KB.

    2. La dim. massima di un file indirizzabile e' 10 KB+1024 KB+5122 KB= 263178 KB.

    3. 2000K> 1034KB. Quindi il 2000000-esimo byte di un file si trova in un blocco accessibile tramite puntatore doppiamente indiretto:
      occorrono quindi 2 accessi aggiuntivi (uno alla tabella esterna e uno a quella interna).