Home

TD 11 Le serpent qui danse

Le but de ce TD est de manipuler des threads et de gérer les problèmes de synchronisation entre eux.

Des serpents se déplacent sur un tore (quand un serpent traverse un bord, il se retrouve de l'autre côté). La tête est représentée par un triangle et donne la direction dans laquelle se dirige le serpent. Pour pouvoir avancer d'un pas, il faut que la case devant eux soit libre. Ils changent de direction aléatoirement. Dans l'exemple ci-dessus, les quatre serpents du bas sont dans une situation de dead-lock, les trois autres bougent. Le but du jeu est de piloter chaque serpent par un thread différent.

Pour ne pas perdre de temps sur l'interface graphique, partir du programme suivant :

• Nid est la classe construisant la fenetre et contient principalement un objet de type Grille.
• Grille est la classe qui représente le terrain où évoluent les serpents. C'est principalement cette classe que vous aurez à modifier.
• Serpent dérive de la classe Thread et sert à gérer les déplacements du serpent.
• Point est une classe très simple pour stocker un point de coordonnées entières.
• ToutNid.java regroupe toutes ces classes en un seul fichier. Vous pouvez soit travailler sur ce fichier, soit sur les quatre ci-dessus.

• la taille des serpents,
• le nombre de serpents,
• la probabilité (entre 0.0 et 1.0) de changer de direction au prochain pas.

machin@radius$ java Nid 15

Exercice 1.

Le but ici est de lancer plusieurs serpents

Exercice 1.1 Plusieurs serpents

Modifier la classe Grille pour lancer plusieurs serpents au lieu d'un seul. On pourra utiliser la variable nbSerpents du constructeur Grille() pour déterminer le nombre de serpents à lancer. (Le deuxième argument de Nid.main est passé à cette variable pour l'instant inutilisée.) Les threads associés pourront être stockés dans un tableau. Testez ensuite ce que cela donne sans synchronisation.

Exercice 1.2 Synchronisation entre les serpents

Il faut gérer les conflits entre serpents :

• Au plus un seul serpent doit pouvoir réserver une case (cela est fait par la fonction Grille.reserve()).
• Lorsqu'une case n'est pas libre, un serpent qui veut la réserver doit attendre qu'elle se libère. Pendant ce temps là, il doit laisser la main aux autres serpents.

Points à vérifier :

• qu'un serpent n'en traverse pas un autre,
• qu'il n'y a pas de serpent bloqué sans personne devant lui,
• qu'un serpent bloqué par un autre est débloqué lorsque l'autre est parti,
• que le bouton quitter marche même avec beaucoup de serpents.

Rappels techniques :

• synchronized sert à rendre une suite d'instructions atomique (elles sont toutes effectuées d'un bloc par un thread). On l'utilise soit sur toutes les instructions d'une méthode, soit sur une suite d'instructions avec la syntaxe synchronized (objet) { ... }.
• Un thread qui exécute une partie atomique reçoit un verrou de réservation sur l'objet associé. La méthode wait () de cet objet permet de redonner le verrou et de passer la main aux autres threads et d'attendre à nouveau le verrou.
• La méthode notifyAll() de cet objet permet de réveiller les threads en attente du verrou, l'un d'eux l'obtiendra alors.

Exercice 1.3 Synchronisation entre un serpent et l'affichage

Il faut gérer les conflits entre un serpent et l'affichage : si un serpent avance pendant que le thread de l'affichage est en train de le redessiner, il peut laisser un morceau derrière lui ou se retrouver tronqué...

Une solution.

Exercice 2. Gestion des serpents

Les serpents vont maintenant être gérés dynamiquement.

Exercice 2.1 Stockage des serpents

Plutôt qu'un simple tableau, définir une classe Sac pour stocker les serpents. Cette classe utilisera son propre tableau pour stocker les serpents :

• le sac a une contenance limitée (la taille fixe du tableau, par exemple CONTENANCE = 30),
• on peut ajouter un serpent dans le sac s'il n'est pas plein,
• on peut obtenir le nombre de serpents dans le sac,
• on peut obtenir le serpent d'index i,
• on peut retirer le serpent d'index i du sac.

Exercice 2.2 Les serpents bloqués

Pour retirer les serpents bloqués, plusieurs juges interviennent. Chaque juge est géré par un thread différent. De temps à autre un juge examine deux serpents du sac et élimine du terrain celui qui a parcouru le moins de distance. Le dernier serpent en course a gagné le jeu du serpent qui danse. Quand le nombre de serpent devient petit par rapport au nombre de juges, les juges doivent terminer pour ne pas surcharger inutilement la machine. Il faut cependant qu'il reste au moins un juge tant qu'il y a plus de deux serpents en course.

Il faut bien sûr gérer les conflits d'accès aux serpents du sac.

Exercice 2.3 Les joueurs de serpent

Les serpents sont introduits dans le jeu par des joueurs. Chaque joueur a sa couleur de serpent et est géré par un thread différent. Il essaye, à intervalle de temps fixe, d'introduire un nouveau serpent de longueur quelconque l. Il doit pour cela réussir à réserver l cases alignées horizontalement avant de pouvoir introduire son serpent sur le terrain. Si l'une des cases est prise, il a échoué et devra recommencer la réservation de zéro. Pour éviter les conflits entre joueurs, l'intervalle de temps entre deux essais pour un joueur donné doit être assez long par rapport au nombre de joueurs. Pour éviter d'avoir des joueurs synchrones, on pourra ajouter une durée aléatoire de moyenne fixe à cet intervalle. Chaque fois qu'un serpent est retiré, le propriétaire marque un score égal au produit de la longueur du serpent par la distance parcourue par celui-ci. Au bout du temps réglementaire, la partie s'arrête et le joueur qui a le plus de points a gagné. Essayez de trouver des stratégies de choix de longueur des serpents gagnantes.

Il faut bien sûr gérer les conflits entre joueurs, juges et serpents.

Sondage

Voici les réponses au sondage précédent.

Merci de remplir le sondage ci-dessous et de cliquer sur "Terminer" quand vous avez fini.