Systèmes d’Exploitation & Programmation Concurrente

public int k=1;

Processus PA

int main ()

{ int i;

1. i=k;

2. i=i+1;

3. k=i;

4. printf("PA avec k=%d\n",k);

Processus PB

int main ()

{ int j;

1. j=k;

2. j=j+4;

3. k=j;

4. printf("PB avec k =%d\n",k);

...

}

...

}

1) Rappelez (en général) quand peut-on avoir des résultats corrects d’exécution concurrente

(entrelacée) de deux processus?

Les résultats corrects de PA//PB sont compris dans soit les résultats de PA ;PB

ou PB ;PA c’est-à-dire PA avec k=2, PB avec k=6 (2,6) ou encore PB avec k=5, PA

avec k=6 (5,6). Cq. k=6

0,75

2/4

2) Les résultats suivants sont-ils possibles ? corrects ? Justifiez vos réponses ?

R1

R2

R3

PA avec k=2

PB avec k =2

PA avec k =2

PB avec k=6

PA avec k =5

PB avec k=2

R1 (2,2) possible et non correcte :

o Exécution de PA1 ; PA2 ; PA3 ; PA4 ; PB1 ; PB2 ; PB3 ; PB4

o (2,2) différent des (2,6) et (5,6).

R2 (2,6) possible et correcte car équivalente à PA ;PB

R3 (5,2) non possible et non correcte

0,25

0,25

0,25

o car k est incrémentée et donc la 2ème valeur est supérieure ou

égale !!!

3) En donnez, dans chaque cas, un entrelacement d’exécution des deux processus qui génère une

réponse, qui soit

a) possible et correcte.

PB ;PA  (5,6) possible et correcte

0,5

b) possible et non correcte.

(5, 5) c-à-d PA1 ;PA2 ;PA3 ; PB1 ;PB2 ;PB3 ;PB4 ; PA4. (6,6) c-à-d

PB1 ;PB2 ;PB3 ; PA1 ;PA2 ;PA3 ;PA4 ; PB4

0,5

4) Afin de garantir tout le temps des résultats corrects, dire que peut-on proposer ? Modifiez le

code des processus PA et PB et précisez vos variables partagées (avec initialisation) ?

public int k=1;

public semaphore Mutex=1 ;

0,5

Processus PA

Processus PB

int main ()

{ int i;

int main ()

{ int j;

0,5 (P et V)

P(Mutex);

i=k;

i=i+1;

k=i;

printf("PA avec k=%d\n",k);

0,5 (P et V)

P(Mutex);

j=k;

j=j+4;

k=j;

printf("PB avec k =%d\n",k);

V(Mutex);

...

}

V(Mutex);

...

}

3/4

Remarque : SC contient un read sur k (i=k), un write sur k (k=i) et enfin un

read sur k (printf(…k) ;). En cq. V(Mutex) doit être après printf pour ne pas

avoir (6,6) qui est différent des deux résultats corrects (2,6) et (5,6) !!

Exercice 3 : Ordonnancement (6 points --1+1,5(+0 ,75 en plus)+2,5 (+0,25 en plus) +1)

On considère l’ensemble des processus suivants :

Processus

Date d'arrivée

Temps estimé –TE Priorité

P1

P2

P3

P4

7h00

7h00

7h03

7h10

10mn

15mn

8mn

18mn

2

3

4

5

1) Les algorithmes d’ordonnancement basés sur des priorités peuvent-ils engendrer le problème de

famine des processus à faible priorité ?. Comment peut-on éviter ce problème ?

Par ordonnancement pour avoir périodiquement une équité

1

2) On suppose qu’on utilise un algorithme d’ordonnancement basé sur la priorité (la plus grande

valeur signifie la plus haute priorité).

Donnez le diagramme de Gantt pour l’ordonnancement priorité (statique) avec préemption. En déduire le temps de

réponse de chaque processus et le temps de réponse moyen.

0—P2—3—P3—10—P4—28—P3—29—P2—41—P1—51

1,5 (0,25/transition)

Tps de réponse –TR TR(P1)=51mn ; TR(P2)=41mn ; TR(P3)=26mn ;

TR(P4)=18mn

TRmoyen = (51+41+26+18)/4 = 40mn

0,75

3) On souhaite maintenant que la priorité des processus soit dynamique au cours du temps. Ainsi,

pour calculer la priorité d’un processus, on utilise la formule suivante :

Priorité = (T_Att+TE_Restant) /TE

Où

 T_Att correspond au temps d’attente d’un processus depuis sa dernière exécution.

 TE_Restant = TE – Temps d’exécution courant.

Avec les hypothèses suivantes :

 Au démarrage, les priorités des processus sont égales à leurs priorités statiques initiales

(indiquées dans le tableau).

4/4

 Les priorités sont recalculées à chaque 5mn. Pour les autres temps, on prend la priorité

précédente.

 Lors des calculs des priorités, on arrondira comme suit :

si E(2X)=2E(X) alors E(X) sinon E(X) +1 où E est la fonction partie entière.

 En cas d’égalité des priorités, on choisit le processus qui attend depuis le plus longtemps.

a) Donnez le diagramme de Gantt de l’ordonnancement préemptif des processus par priorité

dynamique en précisant l'évolution des priorités des différents processus. En déduire le temps

de réponse de chaque processus et le temps de réponse moyen.

2,75 (1,25 tableau (80,125+0,25) + 1,5 DGantt (13 transitions 0,115)

process Tcpu

P1

p2

P3

P4

10

15

8

18

Prio

init

2

3

4

5

t=5

t=10

t=15

t=20

t=25

t=30

t=35

t=40

t=45

2

1

1

--

1

1

1

5

1

2

2

1

2

0

3

1

2

1

0

1

---

1

1

2

1

1

0

0

2

1

0

--

0

0-P2-3-P3-5-P1-10-P4-15-P2-20-P3-25-P1-30-P4-35-P2-40-P3-41-P4-45-P2-47-P4-51

b) Ce procédé permet-il de résoudre le problème de famine? Expliquer

Exercice 4. Synchronisation du problème H2O (6 points –1,5+2+1+1,5)

On souhaite pratiquer les problèmes de synchronisation, vu en cours, dans la chimie. Comme exemple

classique, on prend une molécule d’eau, qui est formée de 2 atomes d’hydrogènes (H2) et un atome

d’oxygène (O). On souhaite écrire du code qui profite d’une synchronisation interprocessus à base de

sémaphores pour le problème de construction de molécules d’eau (H2O). La solution à proposer

doit modéliser la récupération en même temps de deux atomes H (H2) et un atome O afin de créer

une molécule H2O.

1) Identifiez et donnez les différents processus en synchronisation ? A quel(s) type(s) de problème(s)

de synchronisation appartient-il ? expliquez brièvement.

1,5

H  |

H

|  H20

O  |

Problème de Producteurs/consommateur et RDV :

5/4

 Solution 1 : 3 classes de processus dont 1 classe Hydrogene, 1 classe

Oxygène et une 3ème classe H2O. En d’autres termes, 3 producteurs

(H2+0) et un consommateur (H2O) et RDV entre 3 processus H H et O

 Solution 2 : 2 classes de processus dont 1 classe Hydrogene, 1 classe

OxyReady avec combinaison H2O. En d’autres termes, 2 producteurs H et

H et un consommateur O et RDV entre 2 H

2) En indication, on propose d’utiliser (au moins) les variables globales suivantes :

Semaphore Hyd, Oxy; //obligatoires

//Hyd sert à marquer la présence d’un atome H

// Oxy sert à marquer la présence d’un atome O

a) Donnez les valeurs initiales de ces variables ? justifiez.

Semaphore Hyd=Oxy= 0 ; //Sémaphore de blocage pr RDV et P/C 0,5

b) Ecrire les différents codes C correspondant à la formation des molécules d’eau.

Hydrogene()

{

While (True) {

0,75

V(Oxy) ; //Producteur de H

P(Hyd); //RDV avec un 2nd H

}

}

OxyReady()

{

While (True) {

0,75

P(Oxy); //Cons. de H

P(Oxy); //Cons. du 2nd H

makeWater(); //H2O

V(Hyd);

V(Hyd);

}

}

3) Dérouler l’exécution du scénario suivant : deux H arrivent l’un après l’autre puis deux O arrivent

en même temps (c-à-d H1(1) ; H2 (2); O1(3) ; O2(3); … avec Xi(t) signifie l’atome X (dans {H,

O}) de numéro i, arrivé au temps t) ? Conclure ?.

This is dangerous, since it may lead to starvation. If two H’s arrive, then the

value of the Oxy semaphore will be 2. If two O’s arrive, then they can each

decrement Oxy, before either can decrement it twice. So no water is made, even

1

though enough atoms have arrived!!

4) Afin d’éviter le problème de famine modifiez la solution proposée par le rajout d’un autre

sémaphore en précisant son initialisation.

6/4

The fix is to put a lock acquire before the first line in OxyReady, and a lock

release after the two V(Hyd)’s. This way, only one oxygen looks for waiting H’s

at a time -- if there aren’t enough H’s for the first oxygen, there won’t be enough

for any of the later oxygens either.

Semaphore Hyd=Oxy= 0 ; //Sémaphore de blocage pr RDV et P/C

Semaphore Mutex = 1 ; //Exclusion mutuelle sur attente de 2 H

0,5

Hydrogene()

{

While (True) {

V(Oxy) ; //Producteur de H

P(Hyd); //RDV avec un 2nd H

}

}

OxyReady()

{

While (True) {

P(Mutex) ;

1

P(Oxy); //Cons. de H

P(Oxy); //Cons. du 2nd H

makeWater(); //H2O

V(Hyd);

V(Hyd);

V(Mutex) ;

}

}

7/4

8/4