Esame di Sistemi Operativi 1: 18 gennaio 2006


Punteggio Punteggio

 

D1

D2

D3

D4

D5

D6

E1

E2

E3

Totale

Punti

4

4

4

3

3

3

5

3

3

32


Risposte alle domande di teoria: vedi materiale corso/libro


Domanda 1
Spiegare il funzionamento dei monitor e descrivere una possibile implementazione dei
semafori attraverso i monitor.

 

Domanda 2
Descrivere in pseudo codice l’algoritmo del banchiere e spiegare a cosa serve.

Domanda 3
Descrivere il funzionamento (struttura e risoluzione indirizzi, eventuale supporto hardware)

della paginazione su richiesta. .

Trascurando il tempo di overhead per la gestione di un page,

calcolare il tempo effettivo di accesso (EAT)  per un sistema con paginazione a richiesta,

con una frequenza di page fault 1/1000000,  tempo di accesso alla memoria di 20ns e

overhead di  swap+restart di 5ms per ogni page fault.

Risposta II domanda:
freq-pf=10^-6

tlb=tempo look up TLB
EAT = (20+tlb) *(1-freq-pf)  + (tlb+0.5+2*20) * freq-pf


Domanda 4
Descrivere il funzionamento dell’allocazione concatenata e dell’allocazione indicizzata
per i blocchi di un file su disco.

 

Domanda 5
Calcolare la dimensione minima di una FAT necessaria per indirizzare un disco di capacità
160 GB con blocchi da 4KB.

Considerate ora i seguenti due file:
A di dimensione 14000 Byte

B di dimensione  6000  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).


Risposta:
Numero blocchi= 160G/4K = 40M
Dim. inidrizzi= 4 byte
Dim. minima FAT = 40M * 4 =160 MB


A= 4 blocchi  es. A 0  --->   0(1) 1(2) 2(3) 3(-)
B= 2 blocchi  es.  A 100 --->   100(101) ... 101(-)


Domanda 6

A cosa serve il servizio Syslog e quali sue caratteristiche si possono configurare in un sistema Linux?


Esercizio 1
Considerate i seguenti  processi

Risorse condivise
  semaphore  M=2;
  int x=20;

Processo P1
{

 begin
    down(&M);
    x:=x+5;
    up(&M);  
 end
}

Processo P2
{

begin
    down(&M);
    x:=x+5;
    up(&M);  
 end
 }

Processo P3
{

begin
    down(&M);
    x:=x+5;
    up(&M);  
 end
 }


supponete che i processi vengano eseguiti concorrentemente sulla stessa CPU. 

  1. Individuate le regioni critiche nel codice di P1, P2 e P3..
    Vale la mutua esclusione?
  2. Determinare il valore di x alla fine di ogni possibile esecuzione del programma.

  3. Notate che P1, P2 e P3 sono tutte copie di uno stesso processo P.
    Cosa cambia nella risposta 2 se M fosse inizializzato ad un valore K>=0 ed
    avessimo N>=1 copie di P eseguite in parallelo.

Risposte:
  1. Sezione critica: sssegnamento x:=x+5 per tutti e tre i processi.
    Race condition: Poiche' l'assegnamento non e' un'operazione atomica ed il semaforo M e' inizialissato a 2, possono verificarsi race condition su x (es. 2 processi eseguono l'assegnamento simultaneamente)

  2. Ogni processo esegue al piu' una sola volta l'assegnamento x:=x+5
    Tuttavia se 2 processi sono nella sezione critica, l'incremento di  x da parte di un processo
    potrebbe essere sovrascritto dall'incremento dell'altro processo (quindi invece di incrementare il valore di 10 si incrementa solo di 5).
    Inoltre se 2 processi sono in sezione critica uno potrebbe eseguire l'assegnamento e poi lasciare la sezione critica e quindi il terzo potrebbe a sua volta entrare in sezione critica, eseguire l'assegnamento
    e poi passare il controllo al primo processo che sovrascrive i due assegnamenti.
    Quindi x alla fine assume il valore 25, 30 o35.

  3. Se K=0 il sistema va in deadlock (quindi il programma non termina).
    Se invece K>=1 (cioe' al piu' K processi simultaneamente nella sezione critica),
    a causa delle possibili race condition i K assegnamenti dei processi che sono in sezione critica potrebbero avere l'effetto di incrementare x di 5 oppure 10 oppure ... 5K.
    Notiamo anche che quando un processo esce dalla sezione critica puo' essere rimpiazzato da un'altro (all'interno dei K  eseguiti in concorrenza).
    Quindi x alla fine dell'esecuzione assume un valore nell'intervallo 20+5 ,..., 20+5*N



Esercizio 2
Considerare un insieme di cinque processi P1, P2, P3, P4  con i seguenti tempi di arrivo e tempi di
esecuzione.

Processo

Tempo di arrivo

CPU Burst

P1

0

7

P2

3

2

P3

4

13

P4

6

9


Assegnare questo insieme di processi ad un processore in base alla politica SRTF.
Calcolare il valor medio del tempo di attesa ed il valor medio del tempo
di turnaround (completamento) dei processi.


Soluzione:


P1(0-3) P2(3-5) P1(5-9) P4(9-18)  P3(18-31)

Comp:  9, 2, 27, 12
Attesa: 2, 0,  14, 3


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

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

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


Soluzione: 12 page fault  come da tabella seguente


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