Algorithme de Dekker

Salut à tous,

Dans l'examen de Aout 2004 à livre fermé, il est demandé d'implémenter en C une version modifiée de l'algorithme de Dekker afin de garantir l'exclusion mutuelle de 3 processus.

j'ai une solution, mais j'aimerais votre avis.  Ce n'est peut-etre pas juste...

int C1 = 1;
int C2 = 1;
int C3 = 1;
int turn = 1;

/* P1 */
while (true) {
/* section non critique */
C1 = 0;
while (C2 == 0 || C3 == 0) {
C1 = 1;
while (turn == 2 || turn == 3) { };
C1 = 0;
}
/* section CRITIQUE */
turn = 2;
C1 = 1;
}

/* P2 */
while (true) {
/* section non critique */
C2 = 0;
while (C1 == 0 || C3 == 0) {
C2 = 1;
while (turn == 1 || turn == 3) { };
C2 = 0;
}
/* section CRITIQUE */
turn = 3;
C2 = 1;
}

/* P3 */
while (true) {
/* section non critique */
C3 = 0;
while (C2 == 0 || C1 == 0) {
C3 = 1;
while (turn == 2 || turn == 1) { };
C3 = 0;
}
/* section CRITIQUE */
turn = 1;
C3 = 1;
}


Désolé pour l'indentation mais si je la met, ca fait :
    /* section CRITIQUE */
au lieu des espaces.

grrr mauvaise manip

Hi, sorry for explaining this in english. Your solution is correct, from my point of view. The only one improvement that i see if to write "while (turn != 1)" instead of "while (turn==2 || turn ==3)" (One comparison instead two), but it is a minor modification : P.

The problems are the same that in original dekker, but there are a new one. You can´t pass control from P1 to P3 without executing P2, so if there are any problem with one process, all the rest are blocked. To ensure that we will "wake up" a process we could make something like this:

int C1 = 1;
int C2 = 1;
int C3 = 1;
int W1 = 0;
int W2 = 0;
int W3 = 0;
int turn = 1;

/* P1 */
while (true) {
/* section non critique */
C1 = 0;
while (C2 == 0 || C3 == 0) {
C1 = 1;
while (turn != 1) { W1 = 1;};
C1 = 0;
}
/* section CRITIQUE */
if (W2 == 1)
turn = 2;
else if (W3 == 1)
turn = 3;
C1 = 1;
W1 = 0;
}


/* P2 */
while (true) {
/* section non critique */
C2 = 0;
while (C1 == 0 || C3 == 0) {
C2 = 1;
while (turn != 2) { W2 = 1;};
C2 = 0;
}
/* section CRITIQUE */
if (W3 == 1)
turn = 3;
else if (W1 == 1)
turn = 1;
C2 = 1;
W2 = 0;
}

/* P3 */
while (true) {
/* section non critique */
C3 = 0;
while (C1 == 0 || C2 == 0) {
C3 = 1;
while (turn != 3) { W3 = 1;};
C3 = 0;
}
/* section CRITIQUE */
if (W1 == 1)
turn = 1;
else if (W2 == 1)
turn = 2;
C3 = 1;
W3 = 0;
}



The W variables indicate that the process is in the turn checking loop
I put in bold the modifications. Please, give me your opinion about this version. I hope to have been helpful.

PD: Could you tell me where can i get the exams of other years to have an idea about the kind of questions that i can expect? Or just tell me about that : P. I´m a little nervous with that ^^.

Here is exams :
http://www.scinfo.be/index.php?p=topic&t_id=1905
but you must be correctly logged (" s'enregistrer ") to access at this part of forum

"Vous n'êtes pas autorisé à accéder à cette page"



Aucun idee? : P

Tu dois être identifié (Profil > Matricule ULg) pour avoir accès aux tuyaux.

Utilise ce lien:

Petite question juste pour être sûr: avec l'algo de Dekker, les processus vont toujours dans la section crituqe à tour de rôle, c'est-à-dire que c'est impossible qu'un même processus y aille deux fois de suite: me trompe-je?

D'ailleurs, c'est à ça que sert la variable turn et les boucles

et

Me (re)trompe-je ?

c1 & c2 permettent de savoir quelle processus va executer la section critique, turn permet de faire """"""""dormir""""""" le processus tant que ce n'est pas a son tour d'entrer dans la section critique. les processus vont bien être exécuté chacun leur tour, c'est le groupe des variables c1 c2 et turn qui le permet


en rapport avec le message de crateo111 (je vais répondre en francais), tu dis qu'on ne sais passer de P1 à P3, ce qui est exacte, et qui s'il y a un probleme (sous entendu dans P2), on est bloquer. tu donnes donc une solution pour passer de P1 à P3, mais je me demande si cela sert vraiment a quelque chose :
- S'il y a un probleme dans P2, rien ne ns dit qu'on ne va pas rester bloquer dedans
- pour moi cela va chercher un peu loin

(nb : j'ai peut être rien compris, si c'est le cas, heu ben )

Je ne suis pas d'accord avec vous. Pourquoi ne peut on pas passer de P1 à P3 avec le code de Thomas?

Il suffit par exemple de penser au scénario suivant :
- P1 possède la main, il fait une itération de sa boucle principale (`while(true)`). À la fin de la boucle, on a donc turn = 2; C1 = 1; C2 = 1; C3 = 1.
- P1 perd la main et elle est donné à P3. Comme les deux autres processus n'ont pas encore l'intention d'entrer en section critique (C1 = 1; C2 = 1), la condition de la boucle externe de la section non critique est sautée et P3 rentre en section critique.

On est donc passé de P1 à P3 sans passer par P2. Quel est le problème?

Personnelement, je vois les choses ainsi:

Les variables Ci indiquent si un processus a l'intention d'entrer en section critique. Si un processus i a l'intention d'entrer en section critique, alors Ci = 0, sinon Ci = 1. Cela étant, un processus ne peut pas entrer en section critique si d'autres processus ont aussi l'intention d'y entrer, ou si un autre s'y trouve déjà. C'est donc la raison d'être de la première boucle de la section non-critique. Elle permet à un processus de temporairement renoncer à l'exclusion mutuelle avant de réessayer.

Maintenant, si on ne s'en tient qu'aux variables Ci, alors un deadlock est possible en cas de symétrie parfaite des instructions. Pour pallier ce problème, on introduit une variable Turn qui permet de rompre la symétrie.

Considérons le cas de deux processus. On débute avec C1, C2, Turn = 1. En cas de symétrie parfaite des instructions, les deux processus vont aboutir aux boucles internes `while (Turn == 2)` (resp. `while (Turn == 1)`). Comme on a Turn 1, le premier processus va passer outre cette boucle tandis que le second va s'y retrouver piéger. Par ailleurs, comme juste avant le processus 2 a retiré son intention d'entrer en section critique (C2 = 1), le premier peut quitter la boucle externe et entrer en section critique. Bref, la variable Turn a avant tout pour effet de briser la symétrie.

Il est aussi indispensable de noter, contrairement à ce que disait Mat et Xeon, que cette variable n'induit PAS une alternance stricte entre les processus. En effet, lorsqu'un processus a terminé une itération, aucune contrainte ne l'empêche d'aussitôt réentrer en section critique s'il conserve la main. Le fonctionnement correct de l'algorithme dépend donc du fait que chaque processus finit toujours par progresser à un moment ou un autre, condition dépendante du gestionnaire de processus qui est supposé garantir l'équité.

Malgré les guillemets, je ne peux pas m'empêcher de rebondir la dessus Les processus ne sont pas endormis, ils sont en attente active. Lorsqu'un processus a la main et qu'il est piégé dans une boucle `while (Turn != i)`, des cycles CPUs sont inutilement bouffés à vérifier sans cesse la condition (qui ne peut évidemment pas changer tant que ce processus garde la main), ce qui est d'ailleurs bien laid.

Hmm après réflexion, je vois ce que vous vouliez dire à propos du passage de P1 à P2 à P3.

Si P1 est en section critique, que P2 et P3 sont en train de boucler en attendant leur tour, alors lorsque P1 aura terminé c'est inévitablement P2 qui sera débloqué.

Est-ce que c'est un problème? Il faut bien en choisir un. Si on suppose que les process ne vont pas planter et que le gestionnaire est équitable, c'est une solution équitable. Non?

ca me parait juste aussi

Le mieux en fait je pense, niveau équité, ce serait que P1 modifie Turn de façon à débloquer le process qui est resté le plus longtemps dans la boucle.

C'est pas trop compliqué à implémenter, il suffit d'utiliser une queue. Lorsqu'un process i entre dans la boucle interne, il ajoute son identifiant i à la queue. Ensuite, lorsqu'un process sort de la section critique, il fait qqch du genre Turn := queue.dequeue(). Le seul problème qui me vient à l'esprit, c'est qu'il faudrait aussi gérer le cas où la queue est vide. Dans ce cas, on peut imaginer de ne pas modifier Turn ou de le modifier pour un id aléatoire.

Edit: Mais hmppff, il faudrait que la queue soit synchronisée, donc on tourne en rond...

Si on généralise un peu les codes donnés plus haut, on doit arriver à quelque chose comme ça :

/*Cannevas de base.
Remplacer la section critique selon les cas.
Remplacer 'iD' par l'identifiant du processus.*/

while(TRUE) {
/* Section Non Critique */;

//Protocole d'accès (Début).
flagProcess[iD] = CRITICAL_SECTION;

while (isAnybodyElseInCriticalSection(iD, flagProcess) == TRUE) {
flagProcess[iD] = NO_CRITICAL_SECTION;
while (Turn != iD){};
flagProcess[iD] = CRITICAL_SECTION;
};
//Protocole d'accès (Fin).

/* Section Critique */;

//Protocole de fin (Début).
Turn = ((iD + 1) % PROCESS_NBR);
flagProcess[iD] = NO_CRITICAL_SECTION;
//Protocole de fin (Fin).
}

Il faut, bien sûr, avoir déclaré les variables et les constantes adéquates auparavant.

Dans le diagramme page 19, la "légère" modification se situe-t-elle bien au trn==1 dans le processus 1 et trn==2 dans le processus 2?

Si oui, alors cet algorithme correspond, à quelques changements de noms de variables prêt, à la version présente sur wikipedia (en anglais).

Cette ligne de code supplémentaire semblerait éviter toute "famine". Est-ce en rapport direct avec l'hypothèse d'équité?

est ce j'ai de pose des question sur l'algorithme de dekker svp