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 :

Aucune précaution de synchronisation n'a été incluse dans ce programme, c'est pourquoi il ne lance qu'un seul serpent. Le mécanisme de réservation pour l'avance du serpent est seulement ébauché (fonctions Grille.reserve() et Grille.libere()) : pour avancer, le serpent attend que la case devant lui se libère, la réserve et libère alors la case de bout queue. La fonction Nid.main prend trois arguments éventuels : Par exemple, vous pouvez tester le programme en lançant 
machin@radius$ java Nid 15
pour voir évoluer un serpent de longueur 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 :

Points à vérifier :

Rappels techniques :

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 :

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.


Exercice 1

Difficulté :
Intérêt :
Ce que vous avez fait :
Commentaire :

Exercice 2

Difficulté :
Intérêt :
Ce que vous avez fait :
Commentaire :


Sujet proposé par Laurent Viennot Last modified: Tue Jan 7 16:45:19 CET 2003