juin
2011
Un étudiant qui se spécialise en anthropologie et accessoirement en informatique s’est embarqué dans un projet de recherche pour voir s’il était possible d’enseigner les interblocages aux babouins d’Afrique. Il repère un profond canyon et y jette une corde au travers, de sorte que les babouins puissent le traverser à bout de bras. Plusieurs babouins peuvent traverser en même temps, pourvu qu’ils aillent tous dans la même direction. Si des babouins qui se dirigent vers l’est et d’autres vers l’ouest se trouvent sur la corde au même moment, cela conduit à un interblocage(les babouins sont bloqués au point de rencontre sur la corde) : en effet, ils n’ont pas la possibilité de passer les uns par-dessus les autres alors qu’ils sont suspendus au-dessus du canyon. Si un babouin souhaite traverser le canyon, il doit vérifier qu’aucun autre babouin ne traverse en sens inverse.
1. Au moyen de sémaphores, écrivez un programme pour éviter l’interblocage. Ne traitez pas le cas d’un groupe infini de babouins se déplaçant d’un côté et interdisant tout passage à ceux qui se déplacent vers l’autre côté.
2. Reprenez la question précédente, mais en évitant la privation de ressources (famine). Lorsqu’un babouin qui souhaite traverser le canyon vers l’est arrive à la corde et trouve un babouin qui traverse vers l’ouest, il attend jusqu’à ce que la corde soit vide, mais aucun babouin se déplaçant vers l’ouest n’est autorisé à démarrer jusqu’à ce qu’au moins un babouin ait traversé dans l’autre sens.