Problème :

La situation est la suivante :

• cinq philosophes (initialement mais il peut y en avoir beaucoup plus) 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.

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.

Le problème consiste à trouver un ordonnancement des philosophes tel qu’ils puissent tous manger, chacun à leur tour. Cet ordre est imposé par la solution que l’on considère comme celle de Dijkstra avec sémaphores ou Courtois avec des compteurs.

Le corps du processus philosophe peut être le suivant :

Philo(i)
{
    while(true)
    {
        pense( );
        prendre_fourchette( i );
        manger ( );
        poser_fourchette( i );
    }
}

Conséquence, il faut écrire les fonctions prendre_fouchette () et poser_fourchette ().

A. Première solution

On prend un sémaphore par fourchette (un mutex fait aussi l’affaire), chaque sémaphore est initialisé à 1.

sem fourch[ N ] = {1,........1}
prendre_fourchette (int i)
{
    fourch[i].P() ;
    fourch[(i+1)% N].P() ;
}

poser_fourchette (int i)
{
    fourch[i].V() ;
    fourch[(i+1)% N].V() ;
}

Monter que cette solution peut provoquer un interblocage de processus.

B. Deuxième solution

On modifie la solution 1 de sorte que les philosophes ne puissent pas prendre tous en même temps la fourchette de droite.

On introduit pour cela un sémaphore dont le compteur est égal à N-1

Implémenter cette solution.

C. Troisième solution

C’est la même chose que la première solution sauf qu’un philosophe est gaucher et ceci afin d’éviter l’interblocage.

Implémenter cette solution.

D. Quatrième solution 

On se centre ici sur les philosophes. Un sémaphore est attribué à chaque philosophe.

Etat = { PENSE , MANGE , A_FAIM}

Un philosophe qui veut prendre les fourchettes (donc manger) déclare qu’il a faim. Si l’un de ses deux voisins est en train de manger, il ne peut donc pas prendre les deux fourchettes pour l’instant et donc se met en attente. Si les deux philosophes à coté ne mangent pas alors il peut prendre les deux fourchettes et déclarer qu’il mange. Quand le philosophe a fini de manger, il déclare donc qu’il pense et regarde si ses deux voisins qui forcément ne pouvaient pas manger, en ont dès lors l’opportunité. Si c’est le cas il les réveille.

Implémenter cette solution.