Nouveau sujet Répondre Imprimer Syndication RSS 2.0

Algorithme de Dekker

garantissant l'exclusion mutuelle de 3 processus
Photo de Thomas

Ancien
  • Age : 28 ans
  • Messages : 1381
Message édité 1 fois, dernière édition par Thomas, 09 Janvier 2008, 15:57     Lien vers ce message 09 Janvier 2008, 15:54
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.


10 sortes de gens sur terre : ceux qui savent compter en binaire et ceux qui ne savent pas...

Ma page Web
Photo de Thomas

Ancien
  • Age : 28 ans
  • Messages : 1381
Message édité 4 fois, dernière édition par Thomas, 09 Janvier 2008, 15:56     Lien vers ce message 09 Janvier 2008, 15:54
grrr mauvaise manip


10 sortes de gens sur terre : ceux qui savent compter en binaire et ceux qui ne savent pas...

Ma page Web
Crateo (Erasmus guy)
  Lien vers ce message 10 Janvier 2008, 10:51
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 ^^.

Ancien
  • Age : 28 ans
  • Messages : 376
  Lien vers ce message 10 Janvier 2008, 10:59

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

Ancien
  • Messages : 13
  Lien vers ce message 10 Janvier 2008, 11:44
"Vous n'êtes pas autorisé à accéder à cette page"



Aucun idee? : P
Photo de Gilles

Assistant
  • Age : 27 ans
  • Messages : 1707
  Lien vers ce message 10 Janvier 2008, 11:46
"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:
Fichier joint
Télécharger
Fichier téléchargé 684 fois (nom du fichier: Examens - SDO.zip ; taille: 5.091 MO, date d'upload: 30 Aout 2007, 19:12)
Divers énoncés de 2002, 2003, 2004, 2005 et 2007
Hors ligne Mat
Photo de Mat

Ancien
  • Age : 29 ans
  • Messages : 982
  Lien vers ce message 11 Janvier 2008, 11:34
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
while (turn == 1) {}

et
while (turn == 2) {}

Me (re)trompe-je ?


«Saying that Java is nice because it works on all OS's is like saying that anal sex is nice because it works on all genders.»
Photo de Patrick!

Ancien
  • Age : 27 ans
  • Messages : 245
Message édité 4 fois, dernière édition par Patrick!, 11 Janvier 2008, 15:18     Lien vers ce message 11 Janvier 2008, 15:05
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
while (turn == 1) {}

et
while (turn == 2) {}

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 :D)
Photo de Gilles

Assistant
  • Age : 27 ans
  • Messages : 1707
  Lien vers ce message 11 Janvier 2008, 19:43
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é.

Citation (xeon)
turn permet de faire """"""""dormir""""""" le processus tant que ce n'est pas a son tour d'entrer dans la section critique
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.
Photo de Gilles

Assistant
  • Age : 27 ans
  • Messages : 1707
  Lien vers ce message 11 Janvier 2008, 19:54
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?
Photo de Patrick!

Ancien
  • Age : 27 ans
  • Messages : 245
  Lien vers ce message 11 Janvier 2008, 21:34
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
Photo de Gilles

Assistant
  • Age : 27 ans
  • Messages : 1707
Message édité 1 fois, dernière édition par Gilles, 11 Janvier 2008, 22:15     Lien vers ce message 11 Janvier 2008, 22:12
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...
Photo de fifi

Assistant
  • Messages : 320
Message édité 2 fois, dernière édition par fifi, 12 Janvier 2008, 8:54     Lien vers ce message 12 Janvier 2008, 8:52
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.


"Every really large and significant program has just one more bug." -- Gerald M. Weinberg.
"Je suis toujours d'accord avec ce que Gilles ou Geddons disent."
  • Messages : 38
Message édité 3 fois, dernière édition par Arnaud, 14 Janvier 2008, 9:57     Lien vers ce message 14 Janvier 2008, 9:55
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é?
Visiteur
  Lien vers ce message 30 Novembre 2010, 16:10
:oups:est ce j'ai de pose des question sur l'algorithme de dekker svp
Répondre


.