138 lines
6.2 KiB
Markdown
138 lines
6.2 KiB
Markdown
Problème des philosophes
|
|
========================
|
|
|
|
Énoncé
|
|
------
|
|
|
|
N philosophes sont autour d'une table. Il y a une assiette par philosophe,
|
|
et *une* fourchette entre chaque assiette. Pour manger, un philosophe
|
|
doit utiliser les deux fourchettes adjacentes à son assiette (et celles-là
|
|
seulement).
|
|
|
|
Un philosophe peut être dans l'état :
|
|
|
|
- penseur : il n'utilise pas de fourchettes ;
|
|
- mangeur : il utilise les deux fourchettes adjacentes ; aucun de ses
|
|
voisins ne peut manger ;
|
|
- demandeur : il souhaite manger mais ne dispose pas des deux fourchettes.
|
|
|
|
Visuellement les états mangeur/demandeur/penseur sont représentés par un
|
|
rond noir (ou rouge en cas de possible problème)/un rond blanc/rien.
|
|
|
|
Code fourni
|
|
-----------
|
|
- `StrategiePhilo.java` : interface de la synchronisation entre philosophes.
|
|
- `PhiloSem.java` : une implantation de cette interface.
|
|
- `ProcessusPhilosophe.java` : code d'un philosophe.
|
|
- `Main.java` : programme principal.
|
|
Définit aussi les `PhiloDroite(i)`, `PhiloGauche(i)`, `FourchetteGauche(i)`,
|
|
`FourchetteDroite(i)`.
|
|
- `EtatFourchette.java` : définition des constantes pour fourchette placée
|
|
sur la table, l'assiette gauche, l'assiette droite.
|
|
- `EtatPhilosophe.java` : définition des constantes pour philosophe penseur,
|
|
demandeur ou mangeur.
|
|
- `IHM*.java` : interface utilisateur.
|
|
- `Synchro/Simulateur.java` : le simulateur de temps.
|
|
|
|
- Compilation:
|
|
`javac *.java Synchro/*.java`
|
|
|
|
- Exécution:
|
|
`java Main`
|
|
`java Main PhiloSem 10`
|
|
(classe implantant l'interface StrategiePhilo) (nb de philosophes)
|
|
|
|
Le bouton d'aide de la fenêtre affichée par l'application en présente
|
|
les fonctionnalités.
|
|
|
|
La classe Semaphore
|
|
--------------------
|
|
La plateforme Java fournit la classe `java.util.concurrent.Semaphore` qui propose
|
|
une implantation des sémaphores généraux, avec notamment :
|
|
|
|
- un constructeur prenant un paramètre entier, correspondant à la valeur initiale
|
|
du sémaphore. Un second paramètre *optionnel* booléen, qui permet de préciser si
|
|
le sémaphore créé est FIFO. Par défaut, les sémaphores de
|
|
la classe `java.util.concurrent.Semaphore` ne sont pas FIFO.
|
|
Par exemple : `s=new Semaphore(5,true)` crée un sémaphore FIFO de valeur initiale 5.
|
|
|
|
- une méthode `acquire()`, qui correspond à l'opération `P()`
|
|
- une méthode `release()`, qui correspond à l'opération `V()`
|
|
|
|
Cette classe fournit en outre différentes méthodes destinées
|
|
à faciliter l'écriture des programmes (au risque d'altérer la clarté et la sûreté
|
|
de la conception). Il est ainsi possible d'effectuer des `P()`non bloquants (`tryAcquire()`),
|
|
de demander à augmenter ou diminuer la valeur du sémaphore de plusieurs unités en
|
|
une seule opération (`acquire(k)`, `release(j)`), de consulter et modifier
|
|
la valeur du sémaphore, le nombre de processus en attente sur le sémaphore, et
|
|
d'autres choses bien pires encore, qu'il est possible d'utiliser,
|
|
mais avec recul, précaution et modération...
|
|
|
|
À faire
|
|
-------
|
|
|
|
### Première approche : les fourchettes sont des ressources critiques
|
|
=> associer un sémaphore à chacune des fourchettes
|
|
|
|
- Implanter une version de base, où tous les philosophes commencent par prendre leur
|
|
fourchette de droite avant de prendre leur fourchette de gauche.
|
|
- Mettre en évidence la situation d'interblocage pouvant se produire avec cette version.
|
|
Un moyen simple pour cela est d'introduire une temporisation suffisante entre les prises
|
|
de fourchette.
|
|
- Implanter (en utilisant des sémaphores) différentes adaptations de cette version de base
|
|
afin d'éviter les interblocages. Justifier en quoi chaque adaptation évite les interblocages.
|
|
|
|
### Seconde approche : contrôler la progression d'un philosophe en fonction de l'état de ses voisins.
|
|
=> introduire explicitement la notion d'état des philosophes, et associer un sémaphore
|
|
« privé » à chaque philosophe :un philosophe peut manger si aucun de ses voisins ne mange,
|
|
il doit attendre sinon. Les principales difficultés sont :
|
|
|
|
- d'assurer la cohérence des tests sur l'état des philosophes : le (dé)blocage d'un
|
|
philosophe doit être effectué de manière simultanée (atomique) à l'évaluation de
|
|
l'état qui motive la décision de (dé)blocage;
|
|
- la gestion du déblocage d'un philosophe qui ne pouvait pas manger précédemment et qui
|
|
peut le faire suite aux changements d'états d'un ou de ses deux voisins.
|
|
|
|
Cette solution est optimale en termes de degré de parallélisme, dans
|
|
le sens où un philosophe qui demande et dont les voisins ne mangent pas peut
|
|
manger directement. Evaluer ce degré de parallélisme, en fonction du nombre
|
|
de philosophes, et le comparer avec celui de la solution 1.
|
|
|
|
#### Equité
|
|
Montrer (en exhibant un scénario avec 4 ou 5 philosophes) que cette solution « optimale »
|
|
peut conduire à la famine d'un philosophe.
|
|
|
|
Imaginer une solution gérant une priorité entre les philosophes permettant de résoudre ce
|
|
problème. Etudier
|
|
|
|
- le degré de parallélisme dans le pire des cas. Comparer avec la solution optimale.
|
|
- l'attente maximum pour un philosophe demandeur
|
|
(en termes nombre de philosophes servis avant le philosophe demandeur)
|
|
- les limites éventuelles de la solution proposée.
|
|
|
|
Indications
|
|
-----------
|
|
|
|
- `PhiloSem.java` est la seule classe à modifier. Le constructeur de cette classe prend
|
|
un paramètre correspondant au nombre de philosophes lancés. Les variables d'état ou
|
|
les sémaphores utilisés par les méthodes de cette classes seront (déclarés comme) des
|
|
attributs de cette classe.
|
|
|
|
- Il est possible de contrôler la progression des philosophes pas à pas, en mettant
|
|
la simulation en pause, puis en cliquant sur les philosophes (voir l'aide de la fenêtre),
|
|
ce qui peut être très utile pour mettre en évidence des scénarios conduisant à des
|
|
situations pathologiques (famine, erreur...)
|
|
|
|
- Utiliser `Main.java` pour les numéros (`Main.FourchetteGauche` /
|
|
`Main.FourchetteDroite` / `Main.PhiloGauche` / `Main.PhiloDroite`).
|
|
|
|
- (Optionnel) Pour pour poser la fourchette n°f sur l'assiette à *sa* droite, à *sa*
|
|
gauche ou sur la table, utiliser
|
|
|
|
IHMPhilo.poser (f, EtatFourchette.AssietteDroite);
|
|
IHMPhilo.poser (f, EtatFourchette.AssietteGauche);
|
|
IHMPhilo.poser (f, EtatFourchette.Table);
|
|
|
|
|
|
|