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+1	3+1	3	32+2

Risposte alle domande di teoria: vedi materiale corso/libro

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

Domanda 2
Descrivere in pseudo codice l’algoritmo di Peterson e spiegare perché risolve

il problema della regione critica.

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

della paginazione a piu’ livelli.

Calcolare il tempo effettivo di accesso (EAT) per un sistema con paginazione a 2 livelli,

con un hit ratio del 95%, un tempo di look up associativo di 0.5ns, ed un tempo di accesso

alla memoria di 20ns.

Risposta II domanda:
EAT = (20+0.5) * 0.95 + (0.5+3*20) * 0.05

Domanda 4
Descrivere l’algoritmo utilizzato per gestire un dump logico in sistemi Unix.

Domanda 5
Descrivere la struttura della Master File Table (MFT) e il contenuto di un suo record.
Considerate ora un file di nome aabb con 10 blocchi allocati ai seguenti indirizzi fisici

2, 3, 4, 20, 21, 24, 25, 100, 101, 102

In quale formato vengono mantenuti gli indirizzi fisici dei blocchi nel record del file aabb della
MFT?

Risposta II domanda:

Header: 0,10 Ind. blocchi: 2:3, 20:2, 24:2, 100:3

Domanda 6

Descrivere i passi principali della fase di boot in un sistema Linux.

Esercizio 1
Considerate i seguenti processi

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

Processo P1
{

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

Processo P2
{

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

Processo P3
{

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

supponete che i processi vengano eseguiti concorrentemente sulla stessa CPU.

Individuate le regioni critiche nel codice di P1 e P2.
Si possono verificare race conditions per la variabile condivisa x?
Determinare il valore di x alla fine di ogni possibile esecuzione del programma.
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:

Sezione critica: sssegnamento x:=x+1 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)
Ogni processo esegue al piu' una sola volta l'assegnamento x:=x+1
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 2 si incrementa solo di 1). 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 101, 102 o 103.
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 1 oppure 2 oppure ... K. 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 1,...,20+N
(nota se i K assegn. hanno effetto di 1 solo assegnamento si ha N-K+1,
se i K assegn. hanno effetto di K incrementi si ha N, infine se entrano in sequenza tutti i processi in sezione critica un assegnamento potrebbe sovrascrivere tutti gli altri N-1).

Esercizio 2
Considerare un insieme di cinque processi P₁, P₂, P₃, P₄ con i seguenti tempi di arrivo e tempi di
esecuzione.

Processo	Tempo di arrivo	CPU Burst
P₁	0	7
P₂	3	2
P₃	4	13
P₄	6	9

Assegnare questo insieme di processi ad un processore in base alla politica Round Robin considerando un quanto di tempo di 4 unità.

Calcolare il valor medio del tempo di attesa ed il valor medio del tempo
di turnaround (completamento) dei processi.

Soluzione:

P1(0-4) P2(4-6) P1(6-9) P3(9-13) P4(13-17) P3(17-21) P4(21-25) P3(25-29)
P4(29-30) P3(30-31)

Comp: 9, 3, 27, 24
Attesa: 2, 1, 14, 15

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 LRU di sostituzione delle pagine per una memoria fisica di 4 blocchi.
Calcolare il numero di page fault che si verificano.

Soluzione: 18 page fault come da tabella seguente

2
2
2 6
2 6 7
1 6 7
1 8 7
1 8 9

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