Exemple avec blocages : Dîner des philosophes
La programmation concurrente en Java et LTSA
Ce lab traite le problème de la programmation concurrente et les problèmes d'interblocage qui peuvent se produire lors d'accès concurrents à des ressources partagées.
Le problème des cinq philosophes: il y a 5 philosophes assis autour
d'une table, sur laquelle il y a exactement 5 plats et 5 baguettes. Un
philosophe peut être dans deux états: soit il mange, soit il pense.
Lorsqu'il pense, un philosophe n'a pas besoin de baguettes
mais une fois qu'il a faim, il doit se procurer les deux baguettes qui se
trouvent à ses côtés (à sa droite et à sa gauche). Une fois qu'il a fini de
manger il doit reposer les baguettes et continuer à penser. Le tout continue dans un cycle infini.
La baguette est une ressource partagée puisqu'elle peut
être utilisée par le philosophe à sa gauche ou à sa droite. Les classes données ici représentent un programme Java (sauf que le code de la classe Chopstick n'est pas donné), incluant les
fonctions nécessaires pour montrer graphiquement le déroulement du dîner des
philosophes. Les philosophes et les baguettes sont numérotées de 0 à 4, commençant
par le rouge et en suivant le sens de l'horloge. Les couleurs utilisées sont :
0- rouge 1- bleu 2- vert 3- jaune 4- blanc. Lorsqu'un philosophe pense, sa couleur est noire.
Les baguettes ont une couleur noire lorsqu'ils
sont libres ou ont la couleur du philosophe qui l'utilise.
Philosopher 4 pense Philosopher 3 fini de penser Philosopher 3 a faim Philosopher 3 veut la baguette de gauche Philosopher 3 prend la baguette de gauche Philosopher 3 veut la baguette de droite Philosopher 0 fini de penser Philosopher 0 a faim Philosopher 0 veut la baguette de gauche Philosopher 0 prend la baguette de gauche Philosopher 0 veut la baguette de droite Philosopher 0 prend la baguette de droite Philosopher 0 mange Philosopher 1 fini de penser Philosopher 1 a faim Philosopher 1 veut la baguette de gauche Philosopher 2 fini de manger Philosopher 2 libère la baguette de gauche Philosopher 3 prend la baguette de droite Philosopher 3 mange Philosopher 2 libère la baguette de droite Philosopher 2 pense Philosopher 1 prend la baguette de gauche Philosopher 1 veut la baguette de gauche |
 |
Les fonctions de la classe GraphicTable dont vous aurez besoin sont décrites comme suit:
- GraphicTable() : Constructeur de la classe; n'a pas besoin de paramètres, simplement pour initialiser l'interface graphique.
- isHungry(int) : Permet d'indiquer que le philosophe donné comme paramètre a faim. Ceci permet de colorer le plat en utilisant la couleur correspondante.
- isThinking(int) : Permet d'indiquer que le philosophe donné comme paramètre pense. Ceci rend la couleur de son plat noir.
- takeChopstick(int, int) : Permet d'indiquer que le philosophe spécifié par le premier paramètre prend la baguette spécifiée par le deuxième paramètre. Ceci colorie la baguette de la même couleur que le philosophe.
- releaseChopstick(int, int) : Permet d'indiquer que le philosophe spécifié dans le premier paramètre libère la baguette spécifiée par le deuxième paramètre. Ceci colorie la baguette en noir.
Exercice 1
Le lab consiste à implémenter le problème des cinq philosophes ( chacun sera un Thread en Java ) partageant les cinq baguettes selon le schéma expliqué précédemment. Les cinq baguettes sont des ressources partagées et leur réservation doit être implémentée en utilisant le wait() et notify() de Java. C'est à vous d'écrire le corps des méthodes de la classe Chopstick.
Notez que la classe Philosopher contient trois constantes qui déterminent le temps de penser, le temps entre la prise de la première et deuxième baguette, et le temps de manger. Vous pouvez changer ces constantes pour obtenir différentes séquences d'exécution pour le système de 5 philosophes.
Exécutez le programme avec un temps de penser égale à zéro. Vous allez probablement constater un interblocage. En effet, durant l'exécution de votre programme vous pouvez observer un interblocage, dû à la détention partielle des ressources. Ceci peut se produire, par exemple, dans le cas où chaque philosophe a pris la baguette à sa gauche et attend celle à sa droite, qui ne sera jamais libérée. L'exemple suivant illustre cette situation:
Philosopher 0 a faim Philosopher 0 veut la baguette de gauche Philosopher 0 prend la baguette de gauche Philosopher 1 a faim Philosopher 1 veut la baguette de gauche Philosopher 1 prend la baguette de gauche Philosopher 2 a faim Philosopher 2 veut la baguette de gauche Philosopher 2 prend la baguette de gauche Philosopher 3 a faim Philosopher 3 veut la baguette de gauche Philosopher 3 prend la baguette de gauche Philosopher 4 a faim Philosopher 4 veut la baguette de gauche Philosopher 4 prend la baguette de gauche Philosopher 0 veut la baguette de droite Philosopher 1 veut la baguette de droite Philosopher 2 veut la baguette de droite Philosopher 3 veut la baguette de droite Philosopher 4 veut la baguette de droite |
 |
Est-ce que vous avez rencontré un tel interblocage aussi quand vous avez utilisé des temps de penser plus grands ? - Expliquez vous observations. Quelle est la probabilité de rencontrer un tel interblocage ? - De quoi est-ce que cela dépend ? - Expliquer, svp.
Exercice 2
L'expérience avec l'exercice 1 montre qu'il est très rare que le blocage possible se présente effectivement quand les vitesses d'exécution des différents philosophes sont arbitraires. C'est pourquoi il est très difficile, en général, de trouver de tels problèmes en exécutant des tests sur le programme donné.
Maintenant, regardons comment l'outil LTSA pourrait aider à trouver des blocages potentiels. Pour chacun des différents modèles de diners de philosophes (voir ci-dessous), essayez de comprendre la spécification du système et exécutez la commande Check Safety pour détecter des blocages potentiels.
- Decrivez vos observations et expliquez les résultats obtenus en quelques mots.
- Expliquez pourquoi LTSA trouve tous les blocages potentiels, tandis qu'ils sont difficiles à trouver par des tests.
Note: Vous pourriez augmenter le nombre de philosophes dans le système pour déterminer la complexité des systèmes qui peuvent être analysés par l'outil LTSA. Notez qu'il existent des outils plus puissants avec des fonctions similaires, par exemple SPIN.
- Considérez les systèmes de philosophes au diner suivants:
- philosophers - standard version.lts
- philosophers - standard version - taking left or right.lts
- philosophers - abstract version.lts
- philosophers - standard version - with counting active philosophers.lts
Exercice 3
Vous devriez modifier le programme de l'Exercise 1 pour explorer les situations suivantes:
- On peut éviter l'interblocage en limitant le nombre de philosophes qui tentent de manger en même temps. Ceci peut être facilement implémenté en utilisant un sémaphore compteur pour limiter à quatre le nombre de philosophes qui tentent de manger simultanément. De cette façon, au moins un philosophe sera capable de manger et celui-ci libéra ses baguettes une fois terminé, permettant au prochain de manger. - Suggestion: Écrivez la classe SemTable qui limite le nombre de philosophes qui mangent simultanément et adaptez vos classes précédentes pour éviter les interblocages. Observer le comportement du système. - Est-ce que votre solution est telle que les philosophes sont servis d'une façon équitable ? - Expliquez.
- Une approche générale pour éviter les blocages quand plusieurs processus se partagent plusieurs ressources est la réservation de ressources en deux phases. Pensez comment on pourrait introduire un ordre linéaire parmi les baguettes pour appliquer cet approche au philosophes. Si le temps le permet, implantez cet approche de réservation.
- Quand un philosophe attend une deuxième baguette pendant un certain temps, il devrait relâcher la première. Est-ce que ce comportement évite le blocage ? - Théoriquement, qu'en pensez-vous ? - En programmant cet approche, est-ce que vous trouvez un problème ? - Et si on introduisait un temps d'attente aléatoire ?
- Autre approche: les philosophes impairs commencent par la baguette à gauche, les autres à droite. Ca marche ??
Pour chaque situation, discutez si le blocage est évité. Implantez chaque situation en modifiant le programme de l'exercice 1, et observez son comportement.