Exercices interblocage

ArchMat 10

Exercices

Exercice 1 *

Le dîner des philosophes est un problème présenté par Edsger Dijkstra. La situation est la suivante :

  • cinq philosophes se trouvent autour d’une table ;
  • chacun des philosophes a devant lui un plat de spaghetti ;
  • à gauche de chaque plat de spaghetti se trouve une fourchette.

philosophes philosophes

Un philosophe n’a que trois états possibles :

  • penser pendant un temps indéterminé ;
  • être affamé (pendant un temps déterminé et fini sinon il y a famine) ;
  • manger pendant un temps déterminé et fini.

Des contraintes extérieures s’imposent à cette situation :

  • quand un philosophe a faim, il va se mettre dans l’état « affamé » et attendre que les fourchettes soient libres ;
  • pour manger, un philosophe a besoin de deux fourchettes : celle qui se trouve à gauche de sa propre assiette, et celle qui se trouve à droite (c’est-à-dire les deux fourchettes qui entourent sa propre assiette) ;
  • si un philosophe n’arrive pas à s’emparer d’une fourchette, il reste affamé pendant un temps déterminé, en attendant de renouveler sa tentative.
  1. Rappeler les conditions d’interblocage.
  2. Montrer alors que le dîner des philosophes peut conduire à une situation d’interblocage.

Exercice 2

On dispose des deux programmes suivants. L’instruction ajouter, ajoute immédiatement une lettre à la fin d’un fichier auquel les deux programmes ont accès.

# Programme A1
ajouter("R")
ajouter("V")
# Programme A2
ajouter("B")
ajouter("V")
  • Si l’ordinateur exécute le programme A1 en entier puis le programme A2, le résultat est : RVBV.
  • Si l’ordinateur exécute la première instruction du programme A1, puis tout le programme A2, puis la deuxième instruction du programme A1, on obtient : RBVV.
  1. Sachant que chaque programme n’est appelé qu’une fois, donner, par ordre alphabétique, tous les résultats différents possibles de l’exécution de ces deux programmes.

Dans la suite, on dispose des deux fonctions suivantes, qui communiquent par un partage de ressources symbolisé par des jetons :

  • consommer(“Bleu”) attend qu’un jeton Bleu soit disponible, puis détruit ce jeton.
  • produire(“Bleu”) produit un jeton Bleu et le rend disponible.

Un même jeton ne peut pas être consommé en même temps par deux programmes qui s’exécutent en parallèle. Un programme peut être bloqué indéfiniment s’il cherche à consommer un jeton qui n’est jamais produit par un autre programme.

On dispose des deux programmes suivants:

# Programme B1
consommer("Bleu")
ajouter("A")
ajouter("B")
produire("Bleu")
# Programme B2
consommer("Bleu")
ajouter("C")
produire("Bleu")

Un jeton Bleu est disponible avant le premier appel.

  1. Les deux programmes sont appelés en même temps. Quels sont les résultats possibles que l’on peut obtenir?
  2. Donner par ordre alphabétique les différents résultats possibles des deux programmes ci-dessous, sachant que chacun des deux programmes n’est appelé qu’une fois.
# Programme C1
consommer("Bleu")
ajouter("R")
ajouter("V")
produire("Bleu")
# Programme C2
consommer("Bleu")
ajouter("B")
ajouter("V")
produire("Bleu")
ajouter("C")
  1. Donner par ordre alphabétique les différents résultats possibles des deux nouveaux programmes ci-dessous. Chacun des deux programmes n’est appelé qu’une fois. Au départ, un jeton Bleu et un jeton Rouge sont disponibles.
# Programme D1
consommer("Bleu")
ajouter("R")
ajouter("V")
produire("Bleu")
consommer("Rouge")
ajouter("D")
ajouter("V")
produire("Rouge")
# Programme D2
consommer("Bleu")
ajouter("B")
ajouter("V")
produire("Bleu")
consommer("Rouge")
ajouter("C")
produire("Rouge")