Testi e soluzioni compitino novembre 2003


Domande (A)

D1) Descrivere il funzionamento della funzione di sistema fork di Unix

Risposta
Vedi lucidi: creazione di processi, relazione padre-figlio, gestione spazio di indirizzamento e risorse, copy-on-write, ecc.

D2) Descrivere l'algoritmo di Peterson (in pseudo codice).

Risposta
Vedi lucidi

Domande (B)

D1) Descrivere il meccanismo dual mode (User/Kernel) e la gestione dei livelli di contesto in Unix.


Risposta:
Vedi ludici: processi user e kernel, ciclo di vita di un processo, gestione livelli di contesto in caso di interrupt

D2) Descrivere una soluzione al problema dei lettori-scrittori tramite semafori.

Risposta:
vedi lucidi

Esercizio 1 (A)

Considerate i seguenti due processi

Risorse condivise
  semaphore  S=1;
  semaphore  T=0;
  int x=0;
  int y=K;
Processo P1
{
 while (y>0) do
  {
    down(&S); 
    x:=x+1;
    write(x);
    if (x=y) then up(&T)
    else up(&S);
  }

}

 Processo P2
{
while (true)
  {
    down(&T); 
    y:=x-1;
    x:=0;
    up(&S);   
  }
}

supponete che P1 e P2 vengano eseguiti concorrentemente dalla stessa CPU.

E1.1)
Vale la proprieta' di mutua esclusione rispetto alla variabili x? E rispetto a y?


Soluzione:

Le regioni critiche per P1 sono
per P2
La prop. di mutua esclusione vale per la variabile x ma non vale per la variabile y.

La parte di codice racchiusa tra down e up in P1 e P2 protegge infatti ogni accesso
(lettura e scrittura) alla variabile x. Per definizione di P1 e P2 solo uno dei
processi puo accedere alla regione critica per x (P1 e P2 si alternano).

La variabile y invece e' parzialmente protetta dai semafori: la condizione (y>0)
e' potenzialmente  soggetta a race-conditions (cioe' dopo aver passato il test in P1,
la variabile potrebbe assumere un valore =0 a causa dell'intervento di P2).

 
E1.2)
Descrivere le possibili sequenze di output per K>1 motivando brevemente la risposta.

Soluzione:

Quando eseguito su K fissato e > 1 il programma concorrente P1 | P2 da origine a
due possibili sequenze di output:

S1=  1 2 ... K   1 2 ... K-1 .... 1 2   1
S2=  1 2 ... K   1 2 ... K-1 .... 1 2   1   1

P1 infatti sblocca P2 solo quando x raggiunge il valore di y.
al che P2  decrementa y azzera x e passa il controllo a x.

Notate tuttavia che quando x=y=1, P1 ha stampato 1 e ha passato il controllo
a P2 (cioe' ha eseguito up(T) ma non ha ancora controllato (y>0))
ci sono due possibili esecuzioni (causate dalla race-condition su y):

a. viene eseguito prima P2 (che mette y a 0) e poi P1 che esce perche (y>0)=falso
   Questa sequenza corrisponde a S1

oppure

b. viene eseguito prima P1 che passa il test (y>0), e si blocca su S.
   A questo punto P2 pone y=0 e x=0 e sblocca P1.
   P1 stampa ancora 1, esegue up(S) e poi esce dal ciclo (y>0)=falso, lasciando
   P2 in deadlock per sempre.
   Questa sequenza corrisponde a S2


E1.3)
Supponete ora di modificare l'inizializzazione dei semafori come segue:
   
      semaphore  S=0;
      semaphore  T=1;

Descrivere le possibili sequenze di output per K>1 motivando brevemente la risposta.

Soluzione:

Nuovamente ci sono due possibili sequenze

S1'= vuota
S2'= 1

Infatti P2 pone y=-1, risveglia P1 e poi va in attesa su T.
P1 potrebbe non essere ancora entrato nel ciclo quindi trova (y>0)=falso
ed esce: sequenza S1'.

Se invece P1 era gia in attesa su S: stampa 1 e poi trova (y>0)=falso ed esce:
sequenza S2'.


Esercizio 1 (B)

Considerate i seguenti due processi

Risorse condivise
  semaphore  S=0;
  semaphore  T=1;
  int x=K;
  int y=K;
Processo P1
{
 while (y>0) do
  {
    down(&S); 
    x:=x+1;
    write(x);
    if (x=y) then up(&T)
    else up(&S);
  }

}

 Processo P2
{
while (true)
  {
    down(&T);      
    y:=x-1;         
    x:=0;           
    up(&S);       
  }
}

supponete che P1 e P2 vengano eseguiti concorrentemente dalla stessa CPU.

E1.1)
Descrivere le possibili sequenze di output per K>1 motivando brevemente la risposta.


Soluzione:

Quando eseguito su K fissato e > 1 il programma concorrente P1 | P2 da origine a
due possibili sequenze di output:

S1=  1 2 ... K-1   1 2 ... K-2 .... 1 2   1
S2=  1 2 ... K-1   1 2 ... K-2 .... 1 2   1   1

Infatti P2 inizialmente mette y a K-1 e x a 0 e poi passa il controllo a P1.
P1 sblocca P2 solo quando x raggiunge il valore di y.
al che P2  decrementa y azzera x e passa il controllo a x.

Notate tuttavia che quando x=y=1, P1 ha stampato 1 e ha passato il controllo
a P2 (cioe' ha eseguito up(T) ma non ha ancora controllato (y>0))
ci sono due possibili esecuzioni (causate dalla race-condition su y):

a. viene eseguito prima P2 (che mette y a 0) e poi P1 che esce perche (y>0)=falso
   Questa sequenza corrisponde a S1

oppure

b. viene eseguito prima P1 che passa il test (y>0), e si blocca su S.
   A questo punto P2 pone y=0 e x=0 e sblocca P1.
   P1 stampa ancora 1, esegue up(S) e poi esce dal ciclo (y>0)=falso, lasciando
   P2 in deadlock per sempre.
   Questa sequenza corrisponde a S2

E1.2)
Supponete che le parti di codice racchiuse tra down e up in P1 e P2 rappresentino regioni critiche.
Vale la proprieta' di progesso per il sistema globale composta da P1 e P2?

Soluzione:

La prop. di progesso non vale perche' quando il processo P1 esce dal while e termina le
sue operazioni P2 rimane sospeso sul semaforo T per sempre -> dedalock.


E1.3)
Supponete ora di modificare l'inizializzazione della variabile x come segue:
   
      int x=0;

Descrivere le possibili sequenze di output per K>1 motivando brevemente la risposta.

Soluzione:

Nuovamente ci sono due possibili sequenze

S1'= vuota
S2'= 1

Infatti P2 pone y=-1, risveglia P1 e poi va in attesa su T.
P1 potrebbe non essere ancora entrato nel ciclo quindi trova (y>0)=falso
ed esce: sequenza S1'.

Se invece P1 era gia in attesa su S: stampa 1 e poi trova (y>0)=falso ed esce:
sequenza S2'.


Esercizio 2 (A)

Considerate i seguenti Job:

Job
 Burst time
 Tempo di arrivo
 Prima risposta
A
 7
 0
 4.5
B
 5
 1
 3.5
C
 4
 3
 2.5
D 1
 5
 0.5


E2.1 
Supponete di utilizzare una politica Shortest Job First senza preemption.

Assumete che lo scheduler venga attivato quando un job entra nella coda di attesa e  quando un job completa l'esecuzione in CPU.

Descrivere la sequenza di esecuzione dei job in CPU e calcolare  il tempo di completamento e di risposta di ogni Job.


Soluzione

Lo scheduler non applica preemption e quindi non interrompe mai i processi in esecuzione.

0-1
 1-2
 2-3
 3-4
 4-5
 5-6
 6-7
 7-8
 8-9
 9-10
 10-11
 11-12
 12-13
 13-14
 14-15
 15-16
 16-17
A
 A A A A A A D
 C
 C
 C
 C
 B
 B
 B
 B
 B


Tempi di completamento     
A:        7
B: 17-1= 16
C: 12-3=  9
D: 8-5 =  3

Tempo di risposta

A:          4.5
B: 15.5-1= 14.5
C: 10.5-3=  7.5
D: 7.5-5 =  2.5

E2.2
Considerate ora la seguente politica di scheduling.

Lo scheduler di lungo termine immette job nella coda di attesa nell'ordine di arrivo
(supponiamo che tale operazione abbia costo zero).

Per ogni job J nel sistema lo scheduler di breve termine mantiene due contatori CPU_J e WAIT_J
inizialmente a zero.

Lo scheduler viene risvegliato dal clock ogni 2 secondi (tempo 2,4,6,...) ed inoltre  quando un job completa la sua esecuzione.

In entrambi i casi esegue le seguenti operazioni:
Descrivere la sequenza di esecuzione dei job in CPU  e calcolare il tempo di completamento e
di risposta di ogni Job.



Soluzione

0-1
 1-2
 2-3
 3-4
 4-5
 5-6
 6-7
 7-8
 8-9
 9-10
 10-11
 11-12
 12-13
 13-14
 14-15
 15-16
 16-17
A
 A
 B
 B
 C
 C
 A
 A
 B
 B
 A
A
 B
 A
 C
 C
 D

Wa=0 (*)
Wa=1
Wa=2
Wa=2
Wa=3
Wa=3 Wa=4  /
 /
 /
 /

Ca=1
Ca=1
Ca=1
Ca=2
Ca=2
Ca=3 Ca=3 /
 /
 /
 /

Wb=1
Wb=1
Wb=2
Wb=3
Wb=3
Wb=4 /
 /
 /
 /
 /

Cb=0
Cb=1
Cb=1
Cb=1
Cb=2
Cb=2 /
 /
 /
 /
 /



Wc=1
Wc=1
Wc=2
Wc=3
Wc=4
 Wc=5 Wc=6
/
 /



Cc=0
Cc=1
Cc=1
Cc=1
Cc=1 Cc=1 Cc=1
/
 /





Wd=1
Wd=2
Wd=3
Wd=4 Wd=5
 Wd=6
Wd=7 /





Cd=0
Cd=0
Cd=0
Cd=0 Cd=0 Cd=0

Cd=0 /

Al tempo 0 i contatori sono tutti a 0, A entra e lo scheduler viene attivato al tempo 2.

(*) nella colonna [i,i+1] indica aggiornamento delle variabili al tempo i+1


Tempi di completamento     
A: 14
B: 13-1=12
C: 16-3=13
D: 17-5=12

Tempo di risposta

A: 10.5
B:  9.5
C: 14.5
D: 16.5


Esercizio 2 (B)

Considerate i seguenti Job:

Job
 Burst time
 Tempo di arrivo
 Prima risposta
A
 7
 0
 4.5
B
 5
 1
 3.5
C
 4
 3
 2.5
D 1
 5
 0.5


E2.1
Supponete di utilizzare una politica Shortest Job First con preemption
(chiamata anche Shortest Remaining-Time First).
Assumete che lo scheduler venga attivato quando un job entra nella coda di attesa e
quando un job completa l'esecuzione in CPU.

Descrivere la sequenza di esecuzione dei job in CPU e calcolare
il tempo di completamento e di risposta di ogni Job.

Soluzione

Lo scheduler applica preemption e quindi puo' interrompere processi in esecuzione.

0-1
 1-2
 2-3
 3-4
 4-5
 5-6
 6-7
 7-8
 8-9
 9-10
 10-11
 11-12
 12-13
 13-14
 14-15
 15-16
 16-17
A
 B
 B
 B B
 B
 D
 C
 C
 C
 C
 A
 A
 A
 A
 A
 A

Nota: al tempo 5: b (Running) e D (Ready) hanno Remaining Time uguale a 1 --> non si effettua lo switch

Tempi di completamento     
A:        17
B: 6-1 =   5
C: 11-3=   8
D: 7-5 =   2

Tempo di risposta

A:         14.5
B: 15.5-1=  4.5
C: 10.5-3=  9.5
D: 7.5-5 =  6.5


E2.2
Considerate ora la seguente politica di scheduling.
Lo scheduler di lungo termine immette job nella coda di attesa nell'ordine di arrivo
(supponiamo che tale operazione abbia costo zero).

Per ogni job J nel sistema lo scheduler di breve termine mantiene due contatori CPU_J e WAIT_J
inizialmente a zero.
Lo scheduler viene risvegliato dal clock ogni 2 secondi (2,4,6,..) ed inoltre quando un job completa
la sua esecuzione.

In entrambi i casi esegue le seguenti operazioni:
Descrivere la sequenza di esecuzione dei job in CPU  e calcolare il tempo di completamento e
di risposta di ogni Job.



Soluzione

0-1
 1-2
 2-3
 3-4
 4-5
 5-6
 6-7
 7-8
 8-9
 9-10
 10-11
 11-12
 12-13
 13-14
 14-15
 15-16
 16-17
A
 A
 B
 B
 C
 C
 A
 A
 B
 B
 D 
 C
 A
 A B
 C
 A

Wa=0 (*)
Wa=1
Wa=2
Wa=2
Wa=3 Wa=4 Wa=5
Wa=5
 Wa=6 Wa=7 /

Ca=1
Ca=1
Ca=1
Ca=2
Ca=2 Ca=2 Ca=2
Ca=3
 Ca=3 Ca=3 /

Wb=1
Wb=1
Wb=2
Wb=3
Wb=3 Wb=4 Wb=5
Wb=6
 / / /

Cb=0
Cb=1
Cb=1
Cb=1
Cb=2 Cb=2 Cb=2
Cb=2
 / / /



Wc=1
Wc=1
Wc=2
Wc=3 Wc=4 Wc=4
Wc=5
 Wc=6 / /



Cc=0
Cc=1
Cc=1
Cc=1 Cc=1
 Cc=2
Cc=2
 Cc=2 / /





Wd=1
Wd=2
Wd=3 /
 / /
 / /
 / /





Cd=0
Cd=0
Cd=0 /
 / / / 
 /
 / /

Al tempo 0 i contatori sono tutti a 0, A entra e lo scheduler viene attivato al tempo 2.
(*) se nella colonna i-i+1 indica aggiornamento delle variabili al tempo i+1
/ = completato

Tempi di completamento     
A: 17
B: 14
C: 13
D: 6

Tempo di risposta

A: 12.5
B:  9,5
C: 11,5
D: 10,5