Précédent Index Suivant

Exemple : bureau de Poste

Nous présentons, pour finir ce chapitre, un exemple un peu plus complet de programme concurrent : la modélisation d'une file d'attente commune aux divers guichets d'un bureau de poste.

Comme souvent en programmation concurrente les problèmes sont posés métaphoriquement, mais remplacez les guichets du bureau de poste par un ensemble d'imprimantes et vous avez la solution d'un vrai problème d'informatique.

Voici la politique de gestion de service que nous proposons, elle n'a rien d'originale mais a fait ses preuves : chaque client prend en arrivant un numéro d'attente ; lorsqu'un guichetier a fini de servir un client, il appelle un numéro. Lorsque son numéro est appelé, le client se rend au guichet correspondant.

Organisation du développement
Nous distinguerons dans notre développement les ressources et les agents. Les premières sont : le distributeur de numéros d'attente, l'afficheur d'appel et les guichets. Les seconds sont : les guichetiers et les clients. Les ressources sont modélisées par des objets. Les agents le sont par des fonctions exécutées par un processus léger.

Les ressources sont les données partagées par les différents agents du système. L'encapsulation de leurs données et actions dans un objet permet de centraliser, pour chacune, la gestion des mécanismes d'exclusion mutuelle. Lorsqu'un agent désire modifier ou consulter l'état d'un objet, il n'a pas à connaître ni à gérer lui-même les verrous, ce qui permet de simplifier l'organisation de l'accès aux données sensibles et d'éviter des oublis lors du codage des agents.

Le matériel

Le distributeur
Le distributeur de numéros d'attente comprend deux champs de données : un compteur et un verrou. La seule méthode offerte par le distributeur est la prise d'un nouveau numéro.

# class distrib () =
object
val mutable n = 0
val m = Mutex.create()
method prendre () = let r = Mutex.lock m ; n <- n+1 ; n
in Mutex.unlock m ; r
end ;;
class distrib :
unit ->
object val m : Mutex.t val mutable n : int method prendre : unit -> int end
Le verrou interdit que deux clients prennent en même temps un numéro. Notez la façon dont on utilise une variable intermédiaire (r) pour garantir que le numéro calculé dans la section critique est bien celui retourné par l'appel à la méthode.

L'afficheur
L'afficheur des numéros appelés contient trois champs de données : un entier (le numéro appelé) ; un verrou et une variable de condition. Les deux méthodes sont : consultation du numéro appelé (attendre) et modification (appel).

# class affich () =
object
val mutable nc = 0
val m = Mutex.create()
val c = Condition.create()

method attendre n =
Mutex.lock m;
while n > nc do Condition.wait c m done;
Mutex.unlock m;

method appel () =
let r = Mutex.lock m ;
nc <- nc+1 ;
nc
in Condition.broadcast c ;
Mutex.unlock m ;
r
end ;;
La variable de condition est utilisée pour mettre les clients en sommeil sur l'attente de leur numéro. Ils sont tous réveillés lorsque la méthode appel est invoquée. L'accès en lecture ou écriture du numéro appelé est protégé par un même verrou.

Le guichet
Le guichet comprend cinq champs de données : un numéro de guichet fixe (variable ng) ; le numéro du client attendu (variable nc) ; un booléen (variable libre) ; un verrou et une variable de condition. Il offre huit méthodes, dont deux privées : deux méthodes d'accès simple (méthodes get_ng et get_nc) ; un groupe de trois méthodes simulant l'attente du guichetier entre deux clients (méthode privée attendre et méthodes publiques attendre_arrivee, attendre_depart) ; un groupe de trois méthodes simulant l'occupation du guichet (méthode privée set_libre et méthodes arriver, partir).

# class guichet (i:int) =
object(self)
val ng = i
val mutable nc = 0
val mutable libre = true
val m = Mutex.create()
val c = Condition.create()

method get_ng = ng
method get_nc = nc

method private attendre f =
Mutex.lock m ;
while f () do Condition.wait c m done ;
Mutex.unlock m

method attendre_arrivee n = nc <- n ; self#attendre (fun () -> libre)
method attendre_depart () = self#attendre (fun () -> not libre)

method private set_libre b =
Mutex.lock m ;
libre <- b ;
Condition.signal c ;
Mutex.unlock m
method arriver () = self#set_libre false
method partir () = self#set_libre true

end ;;


Un bureau de poste
On regroupe ces trois ressources dans un enregistrement :

# type bureau = { d : distrib ; a : affich ;  gs : guichet array } ;;



Clients et guichetiers

Le comportement de l'ensemble du système dépendra des trois paramètres suivants :

# let delai_service = 1.7 ;;
# let delai_arrivee = 1.7 ;;
# let delai_guichet = 0.5 ;;


Ils représentent chacun la valeur maximale du paramètre dont la valeur effective sera tirée au hasard dans la limite des bornes fixées. Le premier paramètre modélise le temps de service d'un client ; le deuxième le délai d'arrivée des clients dans le bureau de poste ; le dernier le temps que met un guichetier pour appeler un nouveau client après que le dernier soit parti.

Le guichetier
Le travail d'un guichetier consiste à boucler indéfiniment sur la séquence suivante :
  1. Appeler un numéro.
  2. Attendre l'arrivée du client porteur du numéro appelé.
  3. Attendre le départ du client occupant son guichet.
En rajoutant quelques affichages, nous obtenons la fonction :

# let guichetier ((a:affich), (g:guichet)) =
while true do
let n = a#appel ()
in Printf.printf"Guichet %d appelle %d\n" g#get_ng n ;
g#attendre_arrivee n ;
g#attendre_depart () ;
Thread.delay (Random.float delai_guichet)
done ;;
val guichetier : affich * guichet -> unit = <fun>


Le client
Un client exécute la séquence suivante :
  1. Prendre un numéro d'attente.
  2. Attendre que son numéro soit appelé.
  3. Se rendre au guichet ayant appelé son numéro pour se faire servir.
La seule activité un peu complexe du client est de chercher le guichet où il est attendu.

On se donne, pour ce, la fonction auxiliaire :

# let chercher_guichet n gs =
let i = ref 0 in while gs.(!i)#get_nc <> n do incr i done ; !i ;;
val chercher_guichet : 'a -> < get_nc : 'a; .. > array -> int = <fun>


En rajoutant quelques affichages, la fonction principale du client est :

# let client b =
let n = b.d#prendre()
in Printf.printf "Arrivée client %d\n" n ; flush stdout ;
b.a#attendre n ;
let ig = chercher_guichet n b.gs
in b.gs.(ig)#arriver () ;
Printf.printf "Le client %d occupe le guichet %d\n" n ig ;
flush stdout ;
Thread.delay (Random.float delai_service) ;
b.gs.(ig)#partir () ;
Printf.printf "Le client %d s'en va\n" n ; flush stdout ;;
val client : bureau -> unit = <fun>


L'ensemble

Le programme principal de l'application crée un bureau de poste et ses guichetiers (chaque guichetier est un processus) puis lance un processus chargé d'engendrer indéfiniment des clients (chaque client est aussi un processus).

# let main () =
let b =
{ d = new distrib();
a = new affich();
gs = (let gs0 = Array.create 5 (new guichet 0) in
for i=0 to 4 do gs0.(i) <- new guichet i done;
gs0)
}
in for i=0 to 4 do ignore (Thread.create guichetier (b.a, b.gs.(i))) done ;
let creer_clients b = while true do
ignore (Thread.create client b) ;
Thread.delay (Random.float delai_arrivee)
done
in ignore (Thread.create creer_clients b) ;
Thread.sleep () ;;
val main : unit -> unit = <fun>
La dernière instruction endort le processus associé au programme afin de passer tout de suite la main aux autres processus actifs de l'application.






Précédent Index Suivant