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
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