Esercizio
Sia data la procedura swap così definita:

proc swap(var x,var y)
var aux;
begin-atomic
 aux := y;
 y   := x;
 x   := aux;
end-atomic

che scambia il contenuto di x e y in modo "atomico" cioe' senza possibili interferenze
dello scheduler.

E' possibile utilizzare questa funzione al posto, ad. es. della test&set, per assicurare la
proprieta' di mutua esclusione da una sezione critica?


Esercizio
Considerate il seguente programma concorrente


semaphor s1:=0;
semaphor s2:=0;


P: process {       
  up(s1);  
  down(s2);  
  print P 
  down(s2);
  print R
  up(s1);
}

Q: process {
  up(s2);
  down(s1);
  print A;
  up(s2);
  down(s1);
  print I;
}

 

Descrivere il comportamento e i possibili output dell’esecuzione parallela di P e Q.

 

Esercizio
Si consideri il problema dei lettori e scrittori, con riferimento alla soluzione proposta nel testo e riportata di seguito:

 

semaphore mutex=1;

semaphore db=1;

int rc=0;

 

void reader (void) {

while (TRUE) {

            down(&mutex);                                     

            rc=rc+1;

            if (rc==1) down(&db) endif;    (-2-)

up(&mutex);                                                                                                                                                 

            read_DataBase();

            down(&mutex);                     

            rc=rc-1;

            if (rc==0) up(&db);        (-3-)

up(&mutex);                                                                                                                                                   

            use_data_read();

}

}

void writer(void) {

                while (TRUE) {

                               Think_Up_Data();

                down(&db);                    (-0-)

                write_data_base();

                up(&db);                        (-1-)

}

}

 

Dire cosa accade se:

a)      si eliminano gli statement (-0-) e (-1-)

b)       b) si elimina lo statement (-2-)

c) si elimina lo statement (-3-)


Soluzione:

a)              si possono avere corse critiche (interferenze) fra i lettori e gli scrittori e fra più scrittori

b)                 i lettori possono accedere al database mentre uno scrittore lo sta modificando

c)              gli scrittori possono rimanere bloccati per sempre in attesa su db

 

 

Esercizio

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

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.

<!--[if !supportEmptyParas]-->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
Considerate i seguenti  processi

Risorse condivise
  semaphore  S=1, T=1, U=0;
  int x=0;

 

Processo P1
{
      down(&S);
       if (x=0) then up(&T)
                    else up(&U);
       x:=3;
     write(x);
}

Processo P2
{
    down(&T);
    x:=1;
    up(&S);   
}

Processo P3
{
    down(&U); 
    x:=10;
    up(&S);
}


supponete che i processi vengano eseguiti concorrentemente sulla stessa CPU.

<!--[if !supportEmptyParas]-->

  1. In questo programma possono verificarsi race conditions per la variabile x? (Motivare la risposta)
  2. Quali output vengono prodotti da tale programma concorrente? (Motivare la risposta)
  3. Cosa succede se inseriamo l'istruzione down(&S) nel processo P1 subito prima dell'istruzione write(x)?
          ...
               x:=3;
          down(&S);
         write(x);
          ...

Soluzione

·  Si, la variabile x non 'e protetta adeguatamente. Ad esempio, P1 e P2 possono accedere ad x simultaneamente.

·  In generale: P1 e P2 lavorano in concorrenza (race conditions su x).
P3 puo partire solo dopo P2 e solo se P3 pone x=1;
Quando attivi P1 e P3 lavorano in concorrenza (race conditions su x).
Vi sono quindi vari interleaving:

  1. Viene eseguito prima tutto P1: stampa 3
  2. Viene eseguito P1 fino a x:=3, poi P2 pone x a 1, e quindi P2 stampa 1
  3. Viene eseguito prima P2, poi P1 che trova x>0, sveglia P3, P3 pero' e' l'ultimo a modificare x: stampa 3
  4. Viene eseguito prima P2, poi P1 che trova x>0, sveglia P3, si blocca dopo aver modificato x, poi viene mandato in esecuzione P3, e poi si torna a P1: stampa 10

·  Cosi' facendo inseriamo un punto di sincronizzazione in P1: write(x) verra' eseguita solo se P2 o P3 hanno prima eseguito una up.
Tuttavia rimangono le race conditions tra i tre assegnamenti.
Quindi i possibili output rimangono sempre 1, 3 e 10.

 

 

Esercizio
Considerate i seguenti  processi

 

Risorse condivise
  semaphore  S=1, M=1;
  int x=10;

Processo P1
{
    down(&M);
    x:=x+1;
    up(&M);  

   down(&M);
   write(x);
    up(&M);

   up(&S);

}

Processo P2
{
    down(&S);
 
    down(&M);
    x:=x-1;
    up(&M);
 
    down(&M);
   write(x);
    up(&M);
}


supponete che i processi vengano eseguiti concorrentemente sulla stessa CPU.

  1. Individuate le regioni critiche nel codice di P1 e P2.
    Si possono verificare race conditions per la variabile condivisa x?
  2. Determinare tutti i possibili output di tale programma concorrente (P1 in parallelo con P2).
  3. Supponiamo di inizializzare il semaforo  S a 0 invece che a 1.
    Determinare tutti i possibili output del programma (P1 in parallelo con P2) modificato.


Soluzione

  1. Regioni critiche:
    1. R1: x:=x+1;
    2. R2: write(x);
    3. R3: x:=x-1,
    4. R4: write(x) 
  2. Le regioni critiche sono protette da semafori per cui non vi sono race conditions su x.
  3. Il semaforo S non influisce sul flusso di esecuzione e quindi l'output dipende dall'ordine di esecuzione
    di R1-R2 e R3-R4:
    1. Prima R1,R3 (in qualsiasi ordine) e poi R2,R4 (in qualsiasi ordine)--> stampa: 10 10
    2. R1 R2 R3 R4 --> stampa: 11 10
    3. R3 R4 R1 R2 --> stampa:  9  10
  4. Il semaforo forza l'ordine di esecuzione P1 -> P2 e quindi ci sara' un solo output: 11 10

 

Esercizio
Considerate i seguenti  processi

Risorse condivise
  semaphore  S=0, M=1;
  int x=10;

Processo P1
{
    down(&M);
    x:=x+1;
    up(&M);  

   down(&M);
   write(x);
    up(&M);

   up(&S);

}

Processo P2
{
    down(&S);
 
    down(&M);
    x:=x-1;
    up(&M);
 
    down(&M);
   write(x);
    up(&M);
}


supponete che i processi vengano eseguiti concorrentemente sulla stessa CPU.

 

  1. Individuate le regioni critiche nel codice di P1 e P2.
    Si possono verificare race conditions per la variabile condivisa x?
  2. Determinare tutti i possibili output di tale programma concorrente (P1 in parallelo con P2).
  3. Supponiamo di inizializzare il semaforo S a 1 invece che a 0.
    Determinare tutti i possibili output del programma (P1 in parallelo con P2) modificato.


Soluzione

  1. Regioni critiche:
    1. R1: x:=x+1;
    2. R2: write(x);
    3. R3: x:=x-1,
    4. R4: write(x)

          Le regioni critiche sono protette da semafori per cui non vi sono race conditions su x

  1. Il semaforo forza l'ordine di esecuzione P1 -> P2 e quindi ci sara' un solo output: 11 10
  2. Il semaforo S non influisce sul flusso di esecuzione e quindi l'output dipende dall'ordine di esecuzione
    di R1-R2 e R3-R4:
    1. Prima R1,R3 (in qualsiasi ordine) e poi R2,R4 (in qualsiasi ordine)--> stampa: 10 10
    2. R1 R2 R3 R4 --> stampa: 11 10
    3. R3 R4 R1 R2 --> stampa:  9  10

Esercizio
Considerate i seguenti  processi

Risorse condivise
  semaphore  S=1, T=0, U=0, V=1
  int x;

Processo P1
{
      down(&S);
       read(x);
       if (x=0) then
           up(&T);
         down(&U);
       else
           up(&T);
         down(&V);
       endif;
     write(x);
}

Processo P2
{
    down(&T);
    x:=100;
    up(&U);
    up(&V);  
}


supponete che i processi vengano eseguiti concorrentemente sulla stessa CPU.

  1. Al variare dell'input, quali possibili output vengono prodotti
    durante l'esecuzione contemporanea di P1 e P2 in CPU?
     
  2. Al variare dell'input, quali sono i possibili output  se i
    valori iniziali dei semafori sono invece S=1, T=0, U=1,V=1 ?
  3. Quali valori iniziali dei semafori occorrono per ottenere un'unico possibile ouput
    indipendentemente dall'input e dalla schedulazione dei processi?


Soluzione
Sia K il valore in input

  1. Se K=0, stampa 100. Se K=\=0 stampa 100 oppure K.
  2. Stampa K oppure 100.
  3. Con S=1,T=0,U=0,V=0 otteniamo come unico output possibile 100.