Les robots de l'aube
Comme nous l'avions promis dans la dernière application de la
troisième partie (page ??), nous reprenons le
problème des robots pour le traiter dans un cadre distribué où le
monde est un serveur et où chaque robot est un processus indépendant
pouvant s'exécuter depuis une machine distante.
Cette application est un bon résumé des possibilités du langage
Objective CAML puisque nous allons y exploiter et mélanger la plupart de
ses traits. Outre le modèle distribué qui nous est imposé par
l'exercice, nous avons recours à la concurrence pour réaliser le
serveur de sorte que les multiples connexions soient traitées
indépendamment tout en s'appuyant sur une unique représentation mémoire
du << monde >>. L'accès et la modification de l'état des cases du monde
devront en conséquence être protégés par des sections critiques.
Afin de réutiliser au maximum le code qui a déjà été réalisé pour les
robots d'une part, et les architectures client-serveur d'autre
part, nous employons de façon conjointe foncteurs et héritage de
classes.
Cette application est assez minimaliste, mais nous verrons que son
architecture se prête particulièrement bien à des extensions dans de
multiples directions.
Monde-Serveur
Nous prenons une représentation du monde similaire à celle que nous
avions développée dans la partie III. Le monde est une grille de taille
finie et chaque case de cette grille ne peut être occupée que par un seul
robot. Un robot est connu par son nom et par sa position, le monde est
déterminé par sa taille et par les robots qui y séjournent. Ces
différentes informations sont représentées par les types suivants :
# type position = { x:int ; y:int } ;;
# type robot_info = { name : string ; mutable pos : position }
type world_info = { length : int ; width : int ;
mutable robots : robot_info list } ;;
Le monde aura à servir deux sortes de clients :
-
des clients passifs qui se contentent d'épier les
déplacements des différents robots. Ils nous serviront pour réaliser
les clients chargés des affichages. Nous les appellerons des
espions.
- des clients actifs, susceptibles de demander au serveur
de les déplacer et donc de modifier son état.
Ces deux catégories de clients et leur comportement vont déterminer
l'ensemble des messages qu'échangeront serveur et clients.
Un client en se connectant se déclare passif (Spy) ou actif
(Enter). Un espion reçoit en réponse à sa connexion l'état
global du monde. Ensuite, il est tenu informé de tous les changements.
Par contre, il ne peut pas soumettre de requête. Un robot qui se
connecte doit donner ses caractéristiques (son nom et sa position
initiale souhaitée), le monde lui confirme alors son arrivée. Ensuite,
il pourra demander des informations : sa propre position
(GetPos) ou la liste des robots qui l'entourent
(Look). Il peut aussi solliciter le monde pour se déplacer.
Le protocole de requêtes du monde des robots distribués est représenté
par le type suivant :
# type query =
| Spy (* requêtes de déclaration initiale *)
| Enter of robot_info
| Move of position (* requêtes des robots *)
| GetPos
| Look of int
| World of world_info (* messages délivrés par le monde *)
| Pos of robot_info
| Exit of robot_info ;;
De ce protocole, et avec les foncteurs de la << boîte à outils
distribuée >> du chapitre précédent, on tire immédiatement le serveur
générique.
# module Pquery = Make_Protocole (struct type t = query end ) ;;
# module Squery = Server (Pquery) ;;
Il ne nous reste plus qu'à préciser le comportement du serveur en
implantant la méthode treat et en y incorporant les données
qui, d'une part, représentent le monde et, d'autre part, permettent la
gestion des connexions.
Plus précisément, le serveur possède une variable world
(de type world_info) qui est protégée par le verrou
sem (de type Mutex.t). Il possède aussi une
variable spies qui est une liste de files de messages à
envoyer aux observateurs, à raison d'une file par espion. Pour
réveiller les processus chargés de l'envoi de ces messages, le serveur
dispose aussi d'un signal (de type Condition.t).
Nous donnons une fonction auxiliaire dist de
calcul de distance entre deux positions :
# let dist p q = max (abs (p.x-q.x)) (abs (p.y-q.y)) ;;
val dist : position -> position -> int = <fun>
La fonction critical encapsule dans une section critique un
calcul de valeur :
# let critical m f a =
Mutex.lock m ; let r = f a in Mutex.unlock m ; r ;;
val critical : Mutex.t -> ('a -> 'b) -> 'a -> 'b = <fun>
Voici la définition de la classe server implantant le
monde-serveur. Elle est longue, mais nous en donnons ci-après une
explication synthétique.
# class server l w n np =
object (self)
inherit [query] Squery.server n np
val world = { length=l ; width=w ; robots=[] }
val sem = Mutex.create ()
val mutable spies = []
val signal = Condition.create ()
method lock = Mutex.lock sem
method unlock = Mutex.unlock sem
method legal_pos p = p.x>=0 && p.x<l && p.y>=0 && p.y<w
method free_pos p =
let is_not_here r = r.pos.x<>p.x || r.pos.y<>p.y
in critical sem (List.for_all is_not_here) world.robots
method legal_move r p =
let dist1 p = (dist r.pos p) <= 1
in (critical sem dist1 p) && self#legal_pos p && self#free_pos p
method queueing_message mes =
List.iter (Queue.add mes) spies ;
Condition.broadcast signal
method trace_loop s q =
let foo = Mutex.create () in
let f () =
try
spies <- q :: spies ;
self#send s (World world) ;
while true do
while Queue.length q = 0 do Condition.wait signal foo done ;
self#send s (Queue.take q)
done
with _ -> spies <- List.filter ((!=) q) spies ;
Unix.close s
in ignore (Thread.create f ())
method remove_robot r =
self#lock ;
world.robots <- List.filter ((<>) r) world.robots ;
self#queueing_message (Exit {r with name=r.name}) ;
self#unlock
method try_move_robot r p =
if self#legal_move r p
then begin
self#lock ;
r.pos <- p ;
self#queueing_message (Pos {r with name=r.name}) ;
self#unlock
end
method treat_robot s r =
let f () =
try
world.robots <- r :: world.robots ;
self#send s (Pos r) ;
self#queueing_message (Pos r) ;
while true do
Thread.delay 0.5 ;
match self#receive s with
Move p -> self#try_move_robot r p
| GetPos -> self#send s (Pos r)
| Look d ->
self#lock ;
let dist p = max (abs (p.x-r.pos.x)) (abs (p.y-r.pos.y)) in
let l = List.filter (fun x -> (dist x.pos)<=d) world.robots
in self#send s (World { world with robots = l }) ;
self#unlock
| _ -> ()
done
with _ -> self#unlock ;
self#remove_robot r ;
Unix.close s
in ignore (Thread.create f ())
method treat s =
match self#receive s with
Spy -> self#trace_loop s (Queue.create ())
| Enter r ->
( if not (self#legal_pos r.pos && self#free_pos r.pos) then
let i = ref 0 and j = ref 0 in
( try
for x=0 to l do
for y=0 to w do
let p = { x=x ; y=y }
in if self#legal_pos p && self#free_pos p
then ( i:=x ; j:=y; failwith "treat" )
done done ;
Unix.close s
with Failure "treat" -> r.pos <- { x= !i ; y= !j } )) ;
self#treat_robot s r
| _ -> Unix.close s
end ;;
class server :
int ->
int ->
int ->
int ->
object
val nb_pending : int
val port_num : int
val sem : Mutex.t
val signal : Condition.t
val sock : Unix.file_descr
val mutable spies : Pquery.t Queue.t list
val world : world_info
method free_pos : position -> bool
method legal_move : robot_info -> position -> bool
method legal_pos : position -> bool
method lock : unit
method queueing_message : Pquery.t -> unit
method receive : Unix.file_descr -> Pquery.t
method remove_robot : robot_info -> unit
method send : Unix.file_descr -> Pquery.t -> unit
method start : unit
method trace_loop : Unix.file_descr -> Pquery.t Queue.t -> unit
method treat : Unix.file_descr -> unit
method treat_robot : Unix.file_descr -> robot_info -> unit
method try_move_robot : robot_info -> position -> unit
method unlock : unit
end
La méthode treat s'emploie dès le départ à distinguer la nature
du client. Suivant qu'il est actif ou passif, c'est un traitement
particulier qui est appelé : trace_loop pour un observateur,
treat_robot pour un robot. Dans le second cas, on vérifie que
la position initiale proposée par le client est compatible avec l'état
du monde, sinon on tâche de lui trouver une position initiale valide.
Le reste du code peut se partager en quatre catégories :
-
Les méthodes générales : ce sont celles que nous avions
pour les mondes généraux de la partie III. Principalement, il s'agit de
vérifier qu'un déplacement est légal pour un robot donné.
- La gestion des observateurs : chaque observateur est
associé à une socket par laquelle lui sont envoyées les données, à une
queue contenant tous les messages qui ne lui ont pas encore été
envoyés et à un processus. La méthode trace_loop est une
boucle sans fin qui vide la queue des messages en les émettant et qui
s'endort quand elle est vide. Le remplissage est effectué sur toutes
les files d'attente par la méthode queueing_message. Notons
qu'après avoir ajouté un message, le signal de réveil est envoyé à
tous les processus.
- La gestion des robots : là encore, chaque robot est
associé à un processus qui lui est dédié. La méthode
treat_robot est une boucle sans fin : elle attend la
réception d'une requête, la traite et y répond s'il y a lieu. Puis
elle se remet en attente de la prochaine requête. Notons que ce sont
les méthodes gérant le robot qui font les appels à la méthode
queueing_message quand une modification de l'état du monde a
eu lieu. Si la connexion avec le robot est perdue, c'est à dire si
une exception est levée pendant la réception des requêtes, le robot
est considéré comme se retirant et son départ est signalé aux
observateurs.
- Les méthodes héritées : ce sont celles du serveur
générique obtenu par application du foncteur Server au
protocole de notre application.
Client-Observateur
Le foncteur Client nous donne les fonctions génériques
de connexion avec un serveur selon le protocole particulier qui nous
occupe ici.
# module Cquery = Client (Pquery) ;;
module Cquery :
sig
module Com :
sig
val send : Unix.file_descr -> Pquery.t -> unit
val receive : Unix.file_descr -> Pquery.t
end
val connect : string -> int -> Unix.file_descr
val emit_simple : string -> int -> Pquery.t -> unit
val emit_answer : string -> int -> Pquery.t -> Pquery.t
end
Le comportement de l'espion est simple : il se connecte au serveur et
affiche les informations que celui-ci lui transmet. L'espion dispose
de trois fonctions d'affichage que nous donnons ci-dessous :
# let display_robot r =
Printf.printf "Le robot %s se trouve en (%d,%d)\n" r.name r.pos.x r.pos.y ;
flush stdout ;;
val display_robot : robot_info -> unit = <fun>
# let display_exit r = Printf.printf "Le robot %s se retire\n" r.name ;
flush stdout ;;
val display_exit : robot_info -> unit = <fun>
# let display_world w =
Printf.printf "Le monde est un damier de %d par %d \n" w.length w.width ;
List.iter display_robot w.robots ;
flush stdout ;;
val display_world : world_info -> unit = <fun>
La fonction principale du client-espion est :
# let trace_client name port =
let sock = Cquery.connect name port
in Cquery.Com.send sock Spy ;
( match Cquery.Com.receive sock with
World w -> display_world w
| _ -> failwith "le serveur ne suit pas le protocole" ) ;
while true do
match Cquery.Com.receive sock with
Pos r -> display_robot r
| Exit r -> display_exit r
|_ -> failwith "le serveur ne suit pas le protocole"
done ;;
val trace_client : string -> int -> unit = <fun>
Il y a deux façons de procéder pour réaliser un affichage
graphique. La première est simple mais peu économique : puisqu'en
début de connexion le serveur envoie la totalité de l'information, on
peut se contenter d'ouvrir une nouvelle connexion à intervalles
réguliers, d'afficher le monde dans sa globalité et de refermer la
connexion. L'autre possibilité consiste à utiliser les informations
envoyées par le serveur pour maintenir une copie de l'état du
monde. Il est alors aisé de n'afficher que les modifications d'état au
fil de la réception des messages. C'est cette seconde solution que
nous avons mise en oeuvre.
Client-Robot
Tels que nous les avions définis dans le précédent chapitre (cf. page
??), les robots suivaient la signature suivante.
# module type ROBOT =
sig
class robot : int -> int ->
object
val mutable i : int
val mutable j : int
method get_pos : int * int
method next_pos : unit -> int * int
method set_pos : int * int -> unit
end
end ;;
La partie que nous souhaitons conserver des différentes classes
est celle qui justement variait d'un type de robot à l'autre et qui
définissait son comportement : la méthode next_pos.
De plus nous avons besoin d'une méthode pour connecter le robot à un
monde (start) et d'une boucle alternant calcul d'une nouvelle
position et communication avec le serveur pour soumettre la position
choisie.
Nous définissons un foncteur qui partant d'une classe implantant un
robot virtuel, c'est-à-dire respectant la signature ROBOT,
crée, par héritage, une nouvelle classe contenant les méthodes propres à
faire du robot un client autonome.
# module RobotClient (R : ROBOT) =
struct
class robot robname x y hostname port =
object (self)
inherit R.robot x y as super
val mutable socket = Unix.stderr
val mutable rob = { name=robname ; pos={x=x;y=y} }
method private adjust_pos r =
rob.pos <- r.pos ; i <- r.pos.x ; j <- r.pos.y
method get_pos =
Cquery.Com.send socket GetPos ;
match Cquery.Com.receive socket with
Pos r -> self#adjust_pos r ; super#get_pos
| _ -> failwith "le serveur ne respecte pas le protocole"
method set_pos =
failwith "la méthode set_pos ne doit pas être utilisée"
method start =
socket <- Cquery.connect hostname port ;
Cquery.Com.send socket (Enter rob) ;
match Cquery.Com.receive socket with
Pos r -> self#adjust_pos r ; self#run
| _ -> failwith "le serveur ne respecte pas le protocole"
method run =
while true do
let (x,y) = self#next_pos ()
in Cquery.Com.send socket (Move {x=x;y=y}) ;
ignore (self#get_pos)
done
end
end ;;
module RobotClient :
functor(R : ROBOT) ->
sig
class robot :
string ->
int ->
int ->
string ->
int ->
object
val mutable i : int
val mutable j : int
val mutable rob : robot_info
val mutable socket : Unix.file_descr
method private adjust_pos : robot_info -> unit
method get_pos : int * int
method next_pos : unit -> int * int
method run : unit
method set_pos : int * int -> unit
method start : unit
end
end
Remarquons que la méthode get_pos a été redéfinie comme une
interrogation auprès du serveur car les variables d'instance
i et j ne sont pas fiables puisqu'elles peuvent être
modifiées sans l'accord du monde. Pour les mêmes raisons, l'emploi de
set_pos a été invalidé de sorte que son appel
déclenche systématiquement une exception. Ce traitement peut
apparaître brutal, mais il y a fort à parier que si cette méthode est
utilisée par next_pos alors un décalage entre la position
réelle (celle connue par le serveur) et la position supposée (celle
connue par le client) apparaîtra.
Nous utilisons le foncteur RobotClient pour créer les
différentes classes correspondant aux différents robots.
# module Fix = RobotClient (struct class robot = fix_robot end) ;;
# module Crazy = RobotClient (struct class robot = crazy_robot end) ;;
# module Obstinate = RobotClient (struct class robot = obstinate_robot end) ;;
Le petit programme suivant permet de lancer depuis une ligne de
commande, le serveur ou les différents clients. Chacun d'eux est
identifié par l'argument passé au programme.
# let port = 1200 in
if Array.length Sys.argv >=2 then
match Sys.argv.(1) with
"1" -> let s = new server 25 30 port 10 in s#start
| "2" -> trace_client "localhost" port
| "3" -> let o = new Fix.robot "fixe" 10 10 "localhost" port in o#start
| "4" -> let o = new Crazy.robot "fou" 10 10 "localhost" port in o#start
| "5" -> let o = new Obstinate.robot "obstine" 10 10 "localhost" port
in o#start
| _ -> () ;;
Pour en faire plus
Le monde des robots a l'imagination fertile. Avec les éléments déjà
donnés ici, on peut facilement réaliser un << robot intelligent >> qui
soit à la fois robot et espion. Cela permettrait de faire coopérer les
différents habitants du monde. On peut alors étendre l'application pour
obtenir un petit jeu d'action comme << poules-renards-vipères >>
dans lequel les renards chassent les poules, les vipères chassent les
renards et les poules mangent les vipères.