Compitino S.O. 1 Novembre 2004

Domanda 1   - Punti 6

Descrivere il funzionamento del meccanismo di protezione dual mode dei processi Unix spiegando (anche con esempi) a cosa servono i livelli di contesto.

Soluzione:
Vedi lucidi.(dual mode: kernel/user)

Domanda 2 - Punti 6

Spiegare in cosa consiste il problema dei produttori e consumatori.
Scrivere il codice di una soluzione del problema con i monitor.

Soluzione:
Vedi lucidi (soluzione con i monitor non con altre primitive di sincronizzazione)

Domanda 3 - Punti 8

Considerate il seguente programma concorrente dove i semafori sonoimplementati 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);
     x:=x+2;
    write(x);
    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 x:=x+2; write(x); 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 multpli di 3 e maggiori di 0
     
      Ouput = {  <3,6,9,....>  }

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.
       Alla fine dell'esecuzione del corpo del while sia di A che di B la variabile x aumentera' sempre di 3.
       Tuttavia l'ordine di esecuzione delle due sezioni critiche e' arbitrario e quindi quando x=3*k possiamo
       - incrementare x di 2, stampare e poi incrementare di nuovo x di 1  --> stampiamo 3*k+2
       oppure
       - incrementare x di 1, poi di nuovo di 2 e poi stampare  --> stampiamo 3*(k+1)
       Quindi l'insieme (infinito) di possibili ouput e':
               
                Ouput = {  <n_0, n_1,n_2, ...... >  |  per ogni k>=0  n_k =  2+3*k oppure 3*(k+1)  }
      
       Esempio di possibili ouput:
        <3,6,9,...>
        <2,5,8,11,....>
        <3,6,8,11,14,15,...>

Domanda 4 - Punti 6

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
4
 20
 3
 10
 1
 12
 6
 9
 8
 7

Calcolare la stima dei prossimi valori di esecuzione per ogni singolo CPU burst utilizzando la media esponenziale (vista a lezione nel contesto delle approssimazioni a SJF) prendendo come parametri:

Stima iniziale    = 16
Coefficiente     alpha   = 0.5
st2
 st3
 st4
 st5
 st6
 st7
 st8
 st9
 st10
 st11
10 15
 9
 9,5
 5,25
 8.625
 7.31
 8,15
 8,078
 7,53


Domanda 5 - Punti 8

Considerate il seguente workload
Job
 Burst time
 Tempo arrivo
 Priorita
A
 7
 0
 1
B
 7
 1
 1
C
 4
 5
 2
D 8
 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 in un sistema con scheduling con multi code di priorita' dove:

5.2) Calcolare il tempo di completamento di ogni processo.

Soluzione:

5.1) Sequenza

A(0-5)   C(5-9)    D(9-13)   E(13-17)   D(17-21)   E(21-22)    A(22-24)  H(24-26) B(26-33)   F(33-37)   G(37-43)

5.2)
Job
 Tempo completamento
A
 24
B
 32
C 4
D 15
E 15
F 29
G
 34
H
 16