Compitino S.O. 1 Novembre 2004
Domanda 1 -
Punti 6
Descrivere le strutture dati utilizzate da Unix per la gestione
dei processi e descrivere il ciclo di vita "tipico" di un
processo in tale sistema operativo.
Soluzione:
Vedi
lucidi.
Domanda 2 - Punti 6
Considerate la funzione Shift con segnatura Shift(rif
N: numero binario, val B: bit) : bit definita come segue
- Shif
calcola atomicamente lo shift a destra di N
(spostamento di tutti i bit di una posizione verso destra),
inserendo poi B nel bit più significativo.
- Restituisce come
risultato il bit eliminato tramite lo shift
(cioe' il bit meno significativo del
vecchio valore di N).
Es: Se N=1010
allora Shift(N,1) pone
N=1101 e restituisce 0
Si puo utilizzare questa funzione per
risolvere il problema della sezione critica in modo simile alla
funzione
Test&Set?
(Mostrare il codice della soluzione oppure spiegare perche' non si puo
usare).
Soluzione:
Si puo usare Shift esattamente
come l'operazione Test&Set utilizzzando una variabile lock di
1 solo bit. Lo schema di soluzione del problema della sezione critica
e' mostrato di seguito.
Ris. condivise
var lock: bit =0
Process Pi
var vp bit;
Entry:
repeat {
vp:=Shift(lock,1);
} until vp==0;
< Critical section >
Exit: lock:=0
Domanda 3 - Punti 8
Considerate il seguente programma concorrente dove i semafori sono
implementati tramite ciclo di busy-waiting e assumono solo valori
>=0.
Var semaphore S=M=1 T=0
int x=0
Processo A
{
while (true) do
begin
down(S);
down(M);
x:=x+1;
up(M);
up(T);
end
} |
Processo B
{
while (true) do
begin
down(T);
down(M);
write(x);
x:=x+1;
up(M);
up(S);
end
} |
3.1)
Quali sono le sezioni critiche in questo
programma?
3.2)
Vale la proprieta' di mutua esclusione
dalla sezione critica?
3.3)
Descrivere
i possibili output di tale
programma.
3.4)
Cosa cambia rispetto alle risposte alle domande 3.1. 3.2 e 3.3 se i semafori
sono inizializzati
come segue S=M=T=1
Soluzione:
3.1) Le sezioni critiche sono x:=x+1
per A e write(x);x:=x+1; per B
3.2) Si, il semaforo M sequenzializza gli accesi alle 2 sezioni
critiche.
3.3) Con S=1 e T=0 forziamo l'alternanza stretta tra P1 e P2 (P1 poi P2
poi P1 ecc)
Otteniamo come possibile ouput solo la
sequenza (infinita) dei numeri dispari:
Ouput = { <1,3,5,....>
}
3.4) Non cambia la risposta per 3.1 e 3,2, mentre cambia l'ouput.
Siccome alla fine del corpo del while
il processo A deve aspettare la segnalazione di B
e viceversa alla fine del corpo
del while il processo B deve aspettare la segnalazione di A
non e' possibile eseguire ripetutamente
uno solo dei due processi.
Quindi alla fine dell'esecuzione
del corpo del while sia di A che di B la variabile x aumentera' sempre
di 2.
Tuttavia l'ordine di esecuzione delle
due sezioni critiche e' arbitrario e quindi quando x=2*k possiamo
- incrementare x di 1, stampare e poi
incrementare di nuovo x di 1 --> stampiamo 2*k+1
oppure
- stampare x, e poi incrementare di
nuovo x di 1 e po di nuovi di 1 --> stampiamo 2*k
Quindi l'insieme (infinito) di
possibili ouput e':
Ouput = { <n_0, n_1,n_2, ...... >
| per ogni k>=0 n_k
= 2*k oppure 2*k+1 }
Esempio di possibili ouput:
Numeri pari (ordine crescente):
<0,2,4,...>
Numeri dispari (ordine crescente):
<1,3,5,....>
Sequenze miste (ordine crescente):
<0,2,5,6,8,11,,...> <1,2,4,7,....>
Nota:
I numeri naturali (ordine crescente) non fanno parte dell'insieme
Output.
Domanda 4 - Punti 4
In un sistema time sharing un processo viene eseguito per 10 volte con
i seguenti tempi di esecuzione per ogni CPU burst
t1
|
t2
|
t3
|
t4
|
t5
|
t6
|
t7
|
t8
|
t9
|
t10
|
20
|
4
|
10
|
3
|
12
|
1
|
9
|
6
|
7
|
8
|
Calcolare la stima dei prossimi valori
di esecuzione per ogni singolo CPU burst utilizzando la media
esponenziale (vista a lezione nel contesto delle
approssimazioni di SJF) prendendo come parametri:
Stima iniziale = 4
Coefficiente alpha = 0.5
Soluzione:
La formula e' definita come segue: Tempo-stimato
per next-time-burst = (Ultimo-time-burst + ultima stima )*0,5
Quindi otteniamo la seguente tabella
st2
|
st3
|
st4
|
st5
|
st6
|
st7
|
st8
|
st9
|
st10
|
st11
|
12 |
8
|
9
|
6
|
9
|
5
|
7
|
6,5
|
6,75
|
7,375
|
Domanda 5 - Punti 8
Considerate il seguente workload
Job
|
Burst
time
|
Tempo
arrivo
|
Priorita
|
A
|
7
|
0
|
1
|
B
|
5
|
1
|
1
|
C
|
8
|
5
|
2
|
D |
2
|
6
|
2
|
E
|
5
|
7
|
2
|
F
|
4
|
8
|
0
|
G
|
6
|
9
|
0
|
H
|
2
|
10
|
1
|
Supponete di utilizzare una strategia di scheduling con
multi code di priorita' dove:
Per la coda a priorita' 2 (piu' alta') si utilizza Round Robin con
quanto=4
"
" 1 si utilizza SRTF (SJF con
preemption)
"
" 0 utilizza FCFS
Lo scheduler viene attivato alla: scadenza di un quanto (prior. 2),
all'ingresso di un processo (prior.1) alla terminazione di un
processo (tutte le priorita)
5.1) Scrivere il Gantt Chart relativo
all'allocazione dei processi alla CPU.
5.2) Calcolare il tempo di completamento di ogni processo
Soluzione:
5.1) Sequenza
A(0-1) B(1-5)
C(5-9) D(9-11) E(11-15)
C(15-19) E(19-20)
B(20-21) H(21-23) A(23-29)
F(29-33) G(33-39)
5.2)
Job
|
Tempo
completamento
|
A
|
29
|
B
|
20
|
C
|
14
|
D |
5
|
E
|
13
|
F
|
25
|
G
|
30
|
H
|
13
|