Diner des philosophes

par manianis Ven 28 Déc - 17:14

Je suis en trains de travailler sur les systèmes RTOS.

Voilà un problème que je n'arrives pas à résoudre.

The dining philosophers problem is summarized as five philosophers
sitting at a table doing one of two things - eating or thinking. While
eating, they are not thinking, and while thinking, they are not eating.
The five philosophers sit at a circular table with a large bowl of
spaghetti in the center. A fork is placed in between each philosopher,
and as such, each philosopher has one fork to his or her left and one
fork to his or her right. As spaghetti is difficult to serve and eat
with a single fork, it is assumed that a philosopher must eat with two
forks. The philosopher can only use the fork on his or her immediate
left or right.

par manianis Ven 28 Déc - 17:17

La solution (Naïve) que j'ai ~~trouvé~~ est la suivante :
1/ Thinking
2/ Hungry
3/ getRFork
4/ getLFork
5/ Eating
6/ releaseLFork
7/ releaseRFork

Cette solution présente l'inconvénient que lorsque les cinq philosophes s'approprient au même instant de leur fourchette qui est à droite on est dans une situation de DeadLock

par lamia Ven 28 Déc - 18:20

Pour résoudre ce problème on a besoin d'utiliser les sémaphores.
Voilà comment on peut le résoudre:

Processus: ph(i),i=1...5 : on modélise un seul philosophe car ils ont tous le même comportement: soit penser(section restante) soit manger(section critique).

Ressource partagée: 2 fourchettes (gauche et droite)

Code:: ph(i) repeter penser(); ESC(i);//Entrée à la section critique manger(); SSC(i) ;//Sortie de la section critique jusqu'à fin//fin des processus

Initialisation:

etat: tableau partagé qui donne les etats d'un processus (manger , penser, a faim)
S: sémaphore binaire d'exclusion mutuelle sur l'utilisation du tableau etat.

S_i: S_i=0,sémaphore de synchronisation pour bloquer les philosophes qui ont faim et qui n'ont pas de fourchettes.

Code:: ESC(i) debut P(S); etat(i)←"a faim"; si (etat(i-1)<>"manger" et etat(i+1) <>"manger") etat(i)="manger"; V(S[sub]i[/sub]) ; Fin si V(S) ; P(S[sub]i[/sub]) ; Fin.

Code:: SSC(i) Debut P(S) ; Etat(i) ← "penser" ; Si (etat(i-1) = "a faim" et etat(i-2)<> "manger") V(S[sub]i-1[/sub]) ; Etat(i-1)= "manger" ; Fin si Si (etat(i+1) = "a faim" et etat(i+2)<> "manger") V(S[sub]i+1[/sub]) ; Etat(i+1)= "manger" ; Fin si V(S) ; fin

(les deux opérations :

P(proberen)-->test

V(vertrogen)-->increment)

par methodiX Ven 28 Déc - 18:52

La question est quoi exactement?
A ce qu'il parait: Comment modéliser la situation courante pour qu'il n'y aura pas de deadlock? Expliquez svp!

par lamia Ven 28 Déc - 18:59

Si on suppose que tous les philosophes ont eu faim au meme temps, chacun prend la fourchette qui est à sa droite. Ainsi toutes les fourchettes sont prises. Alors s'ils veulent prendre celle de gauche, personne ne trouvera une disponible. D'où le blocage(deadlock). Le philosophe ne peut que manger ou penser, tant qu'il n'a pas mangé il ne peut rien faire, donc personne ne libera une fourchette. C'est ca le probléme dans ce que manianis a proposé.

par lamia Ven 28 Déc - 19:45

Avant tout je voudrais bien expliquer les opérartions P et V
Pour l'implementation d'un sémaphore on dispose de deux opérations principales : P:proberen(to test) et V(Verhogen)
(to increment)
un sémaphore s est une variable entiére non négative qui ne peut etre modifié ou tester que par ces deux opérations qui
sont indivisibles.

l'implementation de P(s) est:
[s=n(nb d'exemplaires de la ressouce partagée)
si s>0 alors s=s-1
sinon bloquer le processus(attente dans la file d'attente)]

l'implementation de V(s) est:
[s=s+1
appel systeme pour reveiller le processus en file d'attente.]

(mais le contenu de ces 2 opérations ne peut pas etre modifié)

par lamia Ven 28 Déc - 19:47

Alors dans ce que j'ai proposé:

le tableau etat est la ressouce partagée: on dispose un seul exemplaire de la ressource partagée
(chaque case du tableau est l'etat du philosophe)

alors un seul processus peut utiliser ce tableau au meme instant en fesant appel à P.
si il a terminé avec ce tableau, il le libére pourqu'un autre processus peut l'utiliser en fesant appel à V.

Un philosophe qui pense ne cause pas de probleme.

Mais quand il a faim il doit changer son etat, donc il accede au tableau etat, et il bloque son utilisation(pour ne pas avoir du conflit en cas d'utilisation simultanée)
il change son etat en "a faim"
il verifie si ses voisins de gauche est de droite sont entrain de manger ou non.
si c'est bon il change son etat en "manger", et appel de V(Si)(reservation: Les fouchettes ne soient que pour lui)
il debloque l'utilisation du tableau
appel de P(Si)(liberation des fourchettes)

Alors il a les 2 fourchettes
Il mange

Quand il a terminer de manger , il doit modifier son etat
il bloque l'utilisation du tableau
il modifie son état en "penser"
il verifie si son voisin de droite a faim et le voisin de droite de ce dernier n'est pas entrain de manger, il lui reserve les fourchettes et lui change son etat en "manger"
et de meme pour sont voisin de gauche
il débloque l'utilisation du tableau.

(j'espere que ce que j'ai expliqué est plus ou moins clair scratch

)

par manianis Sam 29 Déc - 11:42

Non, lamia je ne suis pas d'accord avec votre implémentation de SSC(i). Un philsophe n'a pas le droit de changer l'état de ses voisins.

Code:: [color=black][font=Verdana]SSC(i) Debut P(S) ; Etat(i) ← "penser" ; Si (etat(i-1) = "a faim" et etat(i-2)<> "manger") V(S[sub]i-1[/sub]) ; Etat(i-1)= "manger" ; Fin si Si (etat(i+1) = "a faim" et etat(i+2)<> "manger") V(S[sub]i+1[/sub]) ; Etat(i+1)= "manger" ; Fin si V(S) ; fin[/font][/color]

Dans ce problème d'aprés la littérature il y'a beaucoup de problèmes qui peuvent être résolus de plusieurs manières :

1er Cas : Considérons que les fourchettes sont les ressources critiques.
Cela mène à la solution que j'ai donné un peu en haut qui a l'inconvénient de deadlock au cas où les philosophes prenne tous la même fourchette au même instant.

Une solution à ce problème est que les philsophes de rang pair prennent la fourchette à leur droite et que les philosophes de rang impair prennent la fourchette à leur gauche. Cette solution est critiquée par la littérature dans le sens où le cinquième philosophe a plus de privilèges que les autres (une des fourchettes est toujours disponible donc dès que son voisin baisse ses fourchettes il commence à manger).

par manianis Sam 29 Déc - 11:58

2ème cas : Les états des voisins sont rangés dans un tableau considéré comme étant une ressource critique (solution proposée par Lamia)
Chaque philosophe n'a le droit de manger que si il a faim et qu'il possède les deux fourchettes.

POur plus de détails et de solutions consultez :
http://www.cs.utk.edu/%7Eplank/plank/classes/cs560/560/notes/Dphil/lecture.html

par lamia Sam 29 Déc - 13:36

Supposons qu'on est dans la situation:
ph1: pense
ph2:mange
ph3:pense
ph4:pense
ph4:pense

ph2 mange toujours
ph3 a faim
il teste sur la disponibilité des fouchettes, il trouve qu'une fourchette est libre et l'autre non , le test ne se fait qu'une seule fois

ph2 termine de manger et pose les fourchettes

toutes les fourchettes sont libres, ph3 a faim, et ne fait rien ===> Problème

par manianis Sam 29 Déc - 13:47

lamia a écrit:
ph2 mange toujours
ph3 a faim
il teste sur la disponibilité des fouchettes, il trouve qu'une fourchette est libre et l'autre non , le test ne se fait qu'une seule fois

ph2 termine de manger et pose les fourchettes

Dans ce cas ph3 doit se bloquer en attendant que ph2 se rassassie. Dés que ph2 termine ph3 commencera aussitôt à manger c'est le rôle de sémaphores en fin de compte d'éveiller ph3, Non ?

par manianis Sam 29 Déc - 13:55

C'est la tâche du Système d'exploitation,
1/ ph2 prend le verrou
2/ ph3 essaie de prendre le verrou --> il est mis en attente
3/ ph2 mange
4/ ph2 lève le verrou
5/ ph3 s'en approprie...
6/ ...

par lamia Sam 29 Déc - 14:19

manianis a écrit:C'est la tâche du Système d'exploitation,
1/ ph2 prend le verrou
2/ ph3 essaie de prendre le verrou --> il est mis en attente
3/ ph2 mange
4/ ph2 lève le verrou
5/ ph3 s'en approprie...
6/ ...

bein je suis pas trés bonne en ce qui concerne le fonctionnement du systeme d'exploitation.
Mais je sais que le programmeur doit faire appel à l'instruction qui lève le verrou.

...
2/quand ph3 est mis en attente, il est bloqué car il n'as pas de fourchettes ( à l'aide de l'instruction p(S_i), sachant que Si est initialisé à 0, alors il sera bloqué)
...
4/ ph2 léve le verrou -> ph3 peut manger, mais il ne fait pas la vérification de la disponibilité de la fourchette doite et la fourchette gauche(il ne refait pas le test donc il ne change pas son etat en "manger" et son etat reste à "a faim")

supposons qu'à ce niveau ph4 a faim, il teste, il trouve que son voisin ph3 a faim et ne fais rien donc, et ph5 entrain de penser, donc c'est bon , il a les deux fourchettes, alors que c'est faux car ph3 est entain de manger confused

Donc ph2 doit changer l'etat de ph3.

par manianis Sam 29 Déc - 14:55

Non lamia.

4/ ph2 lève le verrou (sur les deux fourchettes)
5/ ph3 s'approprie du verrou (les fourchettes ne seront pas disponible pour les autres)

par lamia Sam 29 Déc - 14:59

manianis a écrit:Non lamia.

4/ ph2 lève le verrou (sur les deux fourchettes)
5/ ph3 s'approprie du verrou (les fourchettes ne seront pas disponible pour les autres)

Mais selon ma solution, le sémaphore n'est pas sur les fourchettes(comme dans votre solution) mais plutot sur le tableau des etats des philosophes, si c'etait le cas ce que vous dites est vrai Smile

par manianis Sam 29 Déc - 15:05

Oui, c'est correct Lamia.

Votre solution est plus correcte que ma solution.

Mais, votre implémentation pour SSC est incorrecte car ce n'est pas au philosophe (qui mange) de changer l'état de ses voisins (qui attendent qu'il termine).

Ce qui ne me plait pas c'est le code suivant :

Code:: ... Etat(i-1)= "manger" ; ... Etat(i+1)= "manger" ;

car c'est le philosophe qui décide s'il va manger ou non.

par lamia Sam 29 Déc - 15:08

Mais si son etat est "a faim", donc il veut manger, il a déjà décidé s'il va manger ou non, il n'attend que les fourchettes, il ne va pas annuler sa décision, non?

par manianis Sam 29 Déc - 18:04

Je vous propose une implémentation de la solution naive en Python :

http://manianis.sitesled.com/Diner_Philosophes.zip (~ 3 Ko)

par manianis Sam 29 Déc - 18:05

lamia a écrit:Mais si son etat est "a faim", donc il veut manger, il a déjà décidé s'il va manger ou non, il n'attend que les fourchettes, il ne va pas annuler sa décision, non?

Oui c'est çà. Je testerai votre solution et je vous ferai part de mes remarques inchallah.

par lamia Sam 29 Déc - 18:14

manianis a écrit:Je vous propose une implémentation de la solution naive en Python :

ftp://manianis.sitesled.com/Diner_Philosophes.zip (~ 3 Ko)

Faut un mot de passe ou je sais pas quoi, meme en voulant l'ouvrir en session anonyme, ca marche pas. Comment faire?

manianis a écrit:Oui c'est çà. Je testerai votre solution et je vous ferai part de mes remarques inchallah.

Ok

par manianis Sam 29 Déc - 18:43

Excusez-moi. C'est http://... et non ftp.

http://manianis.sitesled.com/Diner_Philosophes.zip

par ArLi Jeu 24 Jan - 21:37

manianis a écrit:
lamia a écrit:
ph2 mange toujours
ph3 a faim
il teste sur la disponibilité des fouchettes, il trouve qu'une fourchette est libre et l'autre non , le test ne se fait qu'une seule fois

ph2 termine de manger et pose les fourchettes

Dans ce cas ph3 doit se bloquer en attendant que ph2 se rassassie. Dés que ph2 termine ph3 commencera aussitôt à manger c'est le rôle de sémaphores en fin de compte d'éveiller ph3, Non ?

par ArLi Jeu 24 Jan - 21:42

lamia a écrit:Pour résoudre ce problème on a besoin d'utiliser les sémaphores.
Voilà comment on peut le résoudre:

Processus: ph(i),i=1...5 : on modélise un seul philosophe car ils ont tous le même comportement: soit penser(section restante) soit manger(section critique).

Ressource partagée: 2 fourchettes (gauche et droite)

Code:
ph(i) repeter penser(); ESC(i);//Entrée à la section critique manger(); SSC(i) ;//Sortie de la section critique jusqu'à fin//fin des processus

Initialisation:

etat: tableau partagé qui donne les etats d'un processus (manger , penser, a faim)
S: sémaphore binaire d'exclusion mutuelle sur l'utilisation du tableau etat.

S_i: S_i=0,sémaphore de synchronisation pour bloquer les philosophes qui ont faim et qui n'ont pas de fourchettes.

Code:
ESC(i) debut P(S); etat(i)←"a faim"; si (etat(i-1)<>"manger" et etat(i+1) <>"manger") etat(i)="manger"; V(S[sub]i[/sub]) ; Fin si V(S) ; P(S[sub]i[/sub]) ; Fin.

Code:
SSC(i) Debut P(S) ; Etat(i) ← "penser" ; Si (etat(i-1) = "a faim" et etat(i-2)<> "manger") V(S[sub]i-1[/sub]) ; Etat(i-1)= "manger" ; Fin si Si (etat(i+1) = "a faim" et etat(i+2)<> "manger") V(S[sub]i+1[/sub]) ; Etat(i+1)= "manger" ; Fin si V(S) ; fin

(les deux opérations :

P(proberen)-->test

V(vertrogen)-->increment)

par Contenu sponsorisé

Diner des philosophes

Diner des philosophes

Re: Diner des philosophes

Re: Diner des philosophes

Re: Diner des philosophes

Re: Diner des philosophes

Re: Diner des philosophes

Re: Diner des philosophes

Re: Diner des philosophes

Re: Diner des philosophes

Re: Diner des philosophes

Re: Diner des philosophes

Re: Diner des philosophes

Re: Diner des philosophes

Re: Diner des philosophes

Re: Diner des philosophes

Re: Diner des philosophes

Re: Diner des philosophes

Re: Diner des philosophes

Re: Diner des philosophes

Re: Diner des philosophes

Re: Diner des philosophes

Est-il pas utile d'utiliser des variables de conditions ( Moniteurs ) ?? :)

Que signifie V(S[sub]i[/sub]) ; et P(S[sub]i[/sub]) ; ??

Re: Diner des philosophes