Esame di Sistemi Operativi 1 : Giugno  2004

Punteggio

 

D1

D2

D3

D4

D5

E1

E2

E3

E4

E5

Totale

Punti

5

3

2

3

3

6

3

2

3

2

32


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

Domanda 2
Si definiscano le seguenti  nozioni:   Regione critica, Mutua esclusione, Starvation  
 
Domanda 3
Descrivere le differenze tra sistemi operativi monolitici, a strati (layered),  e a microkernel. 

Domanda 4
Descrivere struttura ed organizzazione delle tabelle di memoria utilizzate per la gestione dei file in Unix.

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

(Per risposte doimande orali: vedi lucidi e libro di testo)

Esercizio 1
Considerate i seguenti  processi:

 

Risorse condivise
  semaphore  S, T, U;
  int x=100;

 

Processo P1
{
   down(&S);
    if (x=0)
      then 
           up(&T)
       else      
           up(&U)

     endif;
      down(&S);

      write(x);
}

Processo P2
{
    down(&T);
    x:=x-1;
    up(&S);   
}

Processo P3
{
    down(&U); 
    x:=x+1;
    up(&S);
}

 

supponete che i processi vengano eseguiti concorrentemente sulla stessa CPU.
Qual’è l’output di tale programma se i semafori sono inizializzati come segue:
 
  1. S=1 T=0 U=0
  2. S=0 T=1 U=1
  3. S=1 T=1 U=1


Soluzione
  1. P1 risveglia P3 che incrementa x e poi risveglia P1 che stampa 101
  2. P1 e P2 accedono in contemporanea a x: dopo la loroi esecuzione x puo essere 99, 100 o 101 valori che vengono stampati da P1
  3. Come in 2.

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

P6

CPU burst

6

4

8

2

4

6

Priorità

1

2

3

4

5

6

Disegnare il diagramma di Gantt e calcolare il tempo di completamento di ogni processo
per ciascuna  delle seguenti politiche di scheduling della CPU:
  1. Shortest Job First 
  2. Con Priorità 
  3. Round Robin (con quanto di tempo q = 2 e trascurando il tempo di context switch)

Soluzione (assumendo che si ordini irispetto agli indici  in caso di ambiguita):
SJF: P4 P2 P5 P1 P6 P3
Prior.: P1 P2 P3 P4 P5 P6
RR: P1 P2 P3 P4 P5 P6 P1 P2 P3 P5 P6 P1 P3 P6 P3 (ognuno per 2 unita)



Esercizio 3
Considerare la seguente stringa di riferimenti di un processo alla memoria in un sistema
con memoria virtuale

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

 

Illustrare il comportamento dell’algoritmo LRU di sostituzione delle pagine per una
memoria fisica di 4 blocchi.
Calcolare il numero di page fault che si verificano.


Soluzione: 17 page fault


Esercizio 4
Calcolare la dimensione minima di una FAT necessaria per
indirizzare un disco di capacità 5096 MB con blocchi da 4KB.
Considerate ora i seguenti due file:

  1. A di dimensione 13000 byte
  2. B di dimensione  7500 byte
 
Mostrate un esempio di come vengono memorizzati gli indirizzi dei blocchi
dei file A e B in una FAT per un disco con le caratteristiche viste sopra
(scegliete indirizzi di blocco a piacere per i due file).


Soluzione:

N. blocchi= 5096 MB/4KB=1304576  indirizzabili con 3 byte
Fat= 1304576 * 3= 3913728 byte


A occupa 4 blocchi  (ad es. 0 1 2 3), B 2 blocchi (ad es. 4 5)
quindi se A

FAT: 0(1) 1(2) 2(3) 3(*) 4(5) 5(*) ....


Esercizio 5
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, 12 ,0, 1 )

dove in ogni tupla  (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 delle pagine esistenti.
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 = 14; periodo del working set =6;
la lancetta punta inizialmete a P1.

Soluzione:
Viene selzionat ala pagina P4 (non in ws e bit a zero).
Nuova lista:

(P1, 10, 0,  0) --> (P2,  9, 0, 0) --> (P3, 5, 0, 0/1*) --> (P6,14,1, 0 ) --> (P5, 12 ,0, 1 )


*=dipende dal tempo di  risposta della scrittura su disco