Foglio di esercizi 30/10/2006

 

Esercizio 1

Considerate il seguente programma concorrente:

tex2html_wrap_inline470: array [0..1] of { true, false }. Initialized to false.
tex2html_wrap_inline472: 0..1. Initialized to 0.
 

 

E’ una soluzione corretta al problema della sezione critica?

Soluzione:

No. La seguente sequenza di esecuzione porta ad una violazione della mutua esclusione:

P1 assegna true a flag[1], entra nel ciclo piu’ esterno (turn=0), non entra nello spin-lock interno (flag[0]=/=true) e poi viene interrotto dallo scheduler (che inizia ad eseguire S2)

P2 assegna true a flag[0], trova turn=/=1 e quindi entra in sezione critica dove viene interrotto.

P1 assegna 1 a turn e  torna alla condizione del ciclo piu esterno, trova turn=/= 0 ed entra in sezione critica.

A questo punto i due processi sono entrambi in sezione critica.

Inoltre si potrebbe verificare anche starvation:

P0 entra in sezione critica, poi P1 si blocca sullo spin-lock while flag[0] do skip, P0 esce e rientra in sezione critica un numero arbitrario di volte.

Esercizio 2
Sia data la procedura swap così definita:

 

proc swap(var x,var y)
  var aux;
  atomic(

      aux := y;
      y   := x;
      x   := aux;
  )


che scambia il contenuto di x e y in modo "atomico" cioe' senza possibili interferenze
con altri processi.

 

E' possibile utilizzare questa funzione per assicurare la  proprieta' di mutua esclusione da una sezione critica?

Soluzione

 

Possiamo usare swap in modo simile alla procedura TSL (test-and-set-lock):

 

var occ: boolean:=false;

 

Process Pi {

var aux: boolean;

 

repeat

                        aux :=true ;

                        swap(occ,aux) ;

until aux=false ;

 

critical section;

 

occ:=false;

}

 

 

Esercizio 3

Supponete di voler risolvere il problema della sezione critica per 4 processi utilizzando l’algoritmo di Peterson per 2 processi. Le variabili condivise e i costrutti a disposizione per invocare l’algoritmo di Peterson sono:

turn: intero, flag[i] (=true se il processo i e’ interessato ad entrare),
entry_code(turn,flag[i]) ed exit_code(turn,flag[i]) eseguito dal processo i.

Inserite il codice mancante per risolvere il problema della sezione critica per 4 processi.

tex2html_wrap564    // shared variables

tex2html_wrap566 tex2html_wrap568 tex2html_wrap570 tex2html_wrap572

 

 

 

Soluzione:

Possiamo organizzare la competizione tra i 4 processi utilizzano un albero binario, cioe’ con semifinali tra coppie di processi e finale tra i vincenti.

Utilizziamo tre coppie di variabili: semifinali: (turnX, flagX), (turnY, turnY), finale: (turnZ,flagZ)

Il codice dei processi e’ definito come segue:

tex2html_wrap838 tex2html_wrap840 tex2html_wrap842 tex2html_wrap844


Esercizio 4
Considerate il seguente programma concorrente

Variabili condivise

      semaphor s1:=0, s2:=0;

process P1 {       
            up(s1);  
            down(s2);  
            print “P” 
            down(s2);
            print “R”
            up(s1);
}

process P2 {
            up(s2);
            down(s1);
            print “A”;
            up(s2);
            down(s1);
            print “I”;
}

 

 

Descrivere il comportamento e i possibili output dell’esecuzione parallela di P1 e P2.

 

Soluzione:

Inizialmente uno qualsiasi tra P1 e P2 puo’ essere selezionato per l’esecuzione della prima esecuzione.

Il processo P1 deve attendere l’esecuzione di up(s2) da parte di P2 e viceversa P2 attende

l’esecuzione di up(s1).

L’esecuzione delle prime due stampe “R” in P1  e “A” P2 puo’  avvenire in qualsiasi ordine.

Dopo aver stampato “R” P1 attende che P2 esegua up(s2) e quindi segnala sul semaforo s1

sul quale attende P2. Solo dopo la segnalazione su s1 P2 puo stampare “I”.

I possibili output sono quindi due: la stringa “PARI” e la stringa “APRI”.

 

 

Esercizio 5

Utilizzare i semafori per forzare l’esecuzione sequenziale delle istruzioni di 3 processi concorrenti P1, P2 e P3.

 

Soluzione:

Utilizziamo 2 semafori condivisi, s1 ed s2, entrambi inizializzati a zero.

P1 esegue up(s1) come ultima istruzione.

P2 esegue down(s1) come prima istruzione e up(s2) come ultima istruzione.

P3 esegue down(s2) come prima istruzione.

 

 

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

 

Variabili condivise

   semaphore mutex=1, db=1

   int rc=0 ;

 

Process reader {

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();

}

}

 

Process writer {

 

                while (TRUE)

                {

                  Think_Up_Data();

      down(db);                    (-0-)

      write_data_base();

      up(db);                        (-1-)

     }

}

 

 

 

Dire cosa accade se:

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

2.        si elimina lo statement (-2-)

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