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 :
-
Appeler un numéro.
- Attendre l'arrivée du client porteur du numéro appelé.
- 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 :
-
Prendre un numéro d'attente.
- Attendre que son numéro soit appelé.
- 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.