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 gia' 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 la differenza fondamentale tra una trap e un'interruzione.

Sol: vedi lucidi

Domanda 2
Scrivere in pseudo codice l'algoritmo di Peterson.

Sol: vedi lucidi

Domanda 3
Descrivere almeno due diversi modi per implementare un sistema di supporto per  threads.

Sol: vedi lucidi (ad es. threads implementati nel kernel o nello spazio user....)

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);
    up(S);
 end  
}

supponete che i processi vengano eseguiti concorrentemente sulla stessa CPU.
  1. Quali sono le sezioni 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) 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

      < n1^k1  n2^k2 ..... ni^ki ..... >

      dove ni^ki = ni ripetuto ki volte e  ni < ni+1 per 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 3
 7
 2 4 8 10
 5
 6
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 = 3 e trascurando il tempo di context switch)
Sol: applica definizioni viste a lezione
Domanda 6
Descrivere il meccanismo di gestione degli accessi alla pagine logiche in un sistema
con paginazione munito di TLB.

Sol: vedi lucidi (TLB=memoria associativa che contiene mappa pag. logica-fisica + diritti accesso, bit validita',...)

Domanda 7
Descrivere la struttura della Master File Table (MFT) del file system NTFS.

Sol: Sequenza di record che contiene meta dati di un volume NTFS; primi 16 record per volume, rimanenti per file/directory,
       struttura record per file: attributi + allocazione blocchi in run ecc

 
Domanda 8
Un sistema e' composta da 7 processi P1,...,P7 e da 6 risorse condivise R1,...,R6 ciascuna di tipo diverso.
La situazione del sistema e' la seguente:

Si determini, usando il grafo di allocazione delle risorse, se il sistema e' in deadlock (stallo), e in caso affermativo
quali sono i processi e le risorse coinvolti.

Sol:  il grafo di allocazione (vedi lucidi) si trova un ciclo che coinvolge P4, P5, P7, R3, R4,R5

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

Se la dimensione di un blocco è 2Kbyte, e un puntatore occupa 4 byte:
  1.  Qual è la dimensione massima di un file indirizzabile in questo file system?
  2.  Qual è la dimensione massima di un file indirizzabile con i primi 9 puntatori?
  3.  Quanti accessi a disco sono necessari per accedere al byte alla posizione 450.000 di un file?

Sol: N puntatori in 1 blocco: 2K/4=512
  1. Max File= (8 + 512 + 512^2)*2KB
  2. Max File 9 punt = (8 + 512)*2KB
  3. Servono 2 accessi (indice del primo indiretto + blocco dati)

Domanda 10
Descrivere almeno 5 diverse directory del primo livello del file system di Linux.

Sol: vedi lucidi