Corso di Laurea in Informatica Applicata – La Spezia
27 Giugno 2006 Sistemi Operativi 
Prova Scritta 

Esercizio 1.
Cosa sono i semafori? A cosa servono?  Descrivere il loro funzionamento.

Esercizio 2.
Scrivere in pseudo-C (o in altro pseudo-linguaggio) un algoritmo che risolve il problema dei cinque filosofi a cena.

Esercizio 3.
a)	Che differenza c’e’ tra deadlock (stallo) e starvation (morte per fame)? 
b)	Per andare in starvation, un processo deve essere gia’ in stallo? (se la risposta   e’ si dare un esempio, altrimenti motivare la risposta)
c)	Come puo’ essere evitata la starvation?

Esercizio 4.
Descrivere il problema dell’inversione di priorita’ nello scheduling di Windows 2000.

Esercizio 5.
Cinque lavori batch, indicati con le lettere A, B, C, D, E, arrivano al calcolatore in ordine, ma approssimativamente allo stesso istante. I processi hanno un tempo stimato di 8, 10, 2, 4, 8 minuti, rispettivamente, mentre le loro priorita’ (determinate esternamente) sono 2, 4, 5, 1, 3 (5 rappresenta la massima priorita’). Per ognuno dei seguenti algoritmi di schedulazione, determinare il tempo di turnaround (completamento).  Si ignori l’overhead dovuto al cambio di contesto.
a)	 Round Robin (2min)
b)	 Schedulazione a priorita’
c)	 FCFS
d)	 SJF
Nel caso (a) si assuma che il sistema sia multiprogrammato. Negli altri casi si assuma che venga mandato in esecuzione solo un lavoro alla volta fino al suo completamento.

Esercizio 6.
Facendo riferimento ad un ambiente di gestione memoria virtuale con  paginazione su richiesta, si consideri un processo caratterizzato dalla seguente stringa di riferimenti a pagina:
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
a)	 Si illustri il comportamento dell’algoritmo LRU (Least Recently Used) nel caso che al processo siano assegnate 4 pagine fisicche. 
b)	 Si calcoli il numero dei page-fault, supponendo un regime iniziale di paginazione pura.
c)	 Come supporto alla trasformazione degli indirizzi viene usata una tabella di registri associativa (TLB). L’accesso alla memoria centrale richiede 200 ns, la ricerca nella tabella associativa richiede 20 ns. Si calcoli il tempo medio di accesso ai dati, supponendo una hit ratio del 75%.

Esercizio 7.
Si descriva l’algoritmo di sostituzione di pagine di Unix.

Esercizio 8.
I file system possono usare diverse strategie per tenere traccia di quali blocchi compongono un certo file. Se ne descrivano due.

Esercizio 9
Che differenza c’e’ tra hard link e symbolic link ?

Esercizio 10.
a)	 Cos’e’ l’interleaving (interallacciamento) nei dischi?
b)	 In quali casi si usa l’interleaving singolo e quando si usa l’interleaving doppio ?
c)	 Per quali altre componenti del computer puo’ essere usato?