Exercices

Exercices

Les philosophes débloqués

Pour résoudre l'éventuel blocage des philosophes orientaux, il suffit de limiter à quatre l'accès simultané à la table. Implantez cette solution. On rajoute un compteur indiquant le nombre de philosophes présents ainsi que deux fonctions, entrer et sortir, chargées respectivement de limiter les entrées et signaler les sorties.


#
 
 let entrer, sortir =
   let n = ref 0 in
   let m = Mutex.create() in
   let c = Condition.create() in
   let loc_entrer () = 
     Mutex.lock m ;
     while not (!n < 4) do Condition.wait c m done ; 
     incr n ;
     if !n > 1 then Printf.printf "%d philosophes sont a table\n" !n
     else Printf.printf "%d philosophe est a table\n" !n ;
     flush stdout;
     Mutex.unlock m
   in
   let loc_sortir () =
     Mutex.lock m ;
     decr n ;
     Mutex.unlock m ;
     Condition.broadcast c
   in
   loc_entrer, loc_sortir ;;
val entrer : unit -> unit = <fun>
val sortir : unit -> unit = <fun>

Il suffit alors d'appeler ces fonctions en début et en fin de boucle d'un philosophe.


# let philosophe i =
   let ii = (i+1) mod 4 in
   while true do
     Printf.printf "Le philosophe (%d) se pointe\n" i ;
     entrer () ;
     mediter 3. ;
     Mutex.lock b.(i);
     Printf.printf 
 "Le philosophe (%d) prend sa baguette gauche et medite encore un peu\n" i;
     mediter 0.2; Mutex.lock b.(ii) ;
     Printf.printf "Le philosophe (%d) prend sa baguette droite\n" i ;
     manger 0.5 ;
     Mutex.unlock b.(i) ;
     Printf.printf 
 "Le philosophe (%d) rend sa baguette gauche et commence deja a mediter\n" i;
     mediter 0.15 ; 
     Mutex.unlock b.(ii) ;
     Printf.printf "Le philosophe (%d) rend sa baguette droite\n" i ;
     sortir () ; 
     Printf.printf "Le philosophe (%d) se tire\n" i ;
   done ;;
val philosophe : int -> unit = <fun>

Attention, cette solution supprime les inter-blocages, mais pas les famines. Pour résoudre ce dernier problème, on peut soit se fier au hasard en introduisant un délai d'attente en aprés la sortie d'un philosophe, soit gérer explicitement une file d'attente.

La poste en fait plus

Nous proposons l'amendement suivant au bureau de poste décrit à la page ?? : certains clients impatients peuvent partir avant que leur numéro ne soit appelé.

Ajouter à la classe distrib une méthode attendre (de type int -> unit) qui met en attente l'appelant tant que le dernier numéro distribué est inférieur ou égal au paramètre de la méthode (il faut modifier prendre de façon à ce qu'elle émette un signal).


# class distrib () =
   object
     val mutable n = 0
     val m = Mutex.create ()
     val c = Condition.create ()
 
     method attendre nc =
       Mutex.lock m ;
       while (n <= nc) do Condition.wait c m done ;
       Mutex.unlock m
 
     method prendre () =
       Mutex.lock m ;
       n <- n+1 ;
      let nn = n in
      Condition.broadcast c ;
      Mutex.unlock m ;
      nn
   end ;;
class distrib :
  unit ->
  object
    val c : Condition.t
    val m : Mutex.t
    val mutable n : int
    method attendre : int -> unit
    method prendre : unit -> int
  end

Modifier la méthode attendre_arrivee de la classe guichet de façon à ce qu'elle retourne le booléen true si le client attendu s'est présenté et false si le client ne s'est pas présenté au bout d'un certain temps. On rajoute une méthode privée reveil chargée de réveiller le guichetier en attente au bout d'un temps donné.


#
   method private reveil t =
    let dt = delai_attente_appel /. 10.0 in
      while (Unix.gettimeofday() < t) do Thread.delay dt done;
      Condition.signal c
 
   method attendre_arrivee () =
    let t = Unix.gettimeofday() +. delai_attente_appel in
    let r = Thread.create self#reveil t in
      Mutex.lock m;
      while libre && (Unix.gettimeofday() < t) do 
        Condition.wait c m 
      done;
      (try Thread.kill r with _ -> ());
      let b = not libre in (Mutex.unlock m; b)

Modifier la classe affich en lui passant en paramètre un distributeur de numéros et en :

ajoutant une méthode attendre_jusqu'a qui renvoie true si le numéro attendu a été appelé pendant un délai d'attente donné en paramètre et false sinon ; La modification de la méthode appel a pour but de garantir à la fois que ne sont appelés que des numéros effectivement distribués et que lorsqu'un numéro d'appel est affiché, il existe bien un guichet qui attend ce numéro.


# class affich (d:distrib) =
   object
     val mutable nc = 0
     val m = Mutex.create ()
     val c = Condition.create ()
 
    method attendre n =
      Mutex.lock m ;
      while nc < n do Condition.wait c m done ;
      Mutex.unlock m 
 
    method attendre_jusqu'a n t =
      Mutex.lock m ;
      while (nc < n) && (Unix.gettimeofday() < t) do Condition.wait c m done ;
      let b = not (nc < n) in
      Mutex.unlock m ;
      b
 
    method appel (g:guichet) =
      Mutex.lock m ;
      d#attendre nc ;
      nc <- nc+1 ; 
      g#set_nc nc ;
      Condition.broadcast c ;
      Mutex.unlock m 
 
   end ;;
class affich :
  distrib ->
  object
    val c : Condition.t
    val m : Mutex.t
    val mutable nc : int
    method appel : guichet -> unit
    method attendre : int -> unit
    method attendre_jusqu'a : int -> float -> bool
  end

modifiant la méthode appel pour qu'elle prenne en paramètre un guichet et mette à jour le champ nc de ce guichet (il faut rajouter une méthode de mise à jour dans la classe guichet).

Modifier la fonction guichetier pour tenir compte des attentes infructueuses.


# type bureau = { d: distrib; a: affich; gs: guichet array }
val delai_service : float = 4
val delai_arrivee : float = 2
val delai_guichet : float = 0.5
val delai_attente_client : float = 0.7

 let guichetier ((a : affich), (g : guichet)) =
   while true do
     a#appel g ;
     Printf.printf"Guichet %d appelle %d\n" g#get_ng g#get_nc ;
     if g#attendre_arrivee () then g#attendre_depart ()
     else
       begin
         Printf.printf"Guichet %d n'attend plus %d\n" g#get_ng g#get_nc ;
         flush stdout
       end ;
     Thread.delay (Random.float delai_guichet)
   done ;;
val guichetier : affich * guichet -> unit = <fun>

Écrire une fonction client_impatient qui simule le comportement d'un client impatient.


# val chercher_guichet : 'a -> < get_nc : 'a; .. > array -> int = <fun>

 let client_impatient b =
   let n = b.d#prendre() in
   let t = Unix.gettimeofday() +. (Random.float delai_attente_client) in
   Printf.printf "Arrivee client impatient %d\n" n; flush stdout;
   if b.a#attendre_jusqu'a n t 
   then
     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 
   else
     Printf.printf "Le client %d, las d'attendre, s'en va\n" n
   flush stdout ;;  
Characters 518-531:
This function is applied to too many arguments

Producteurs et consommateurs d'objet

Cet exercice reprend l'algorithme des producteurs-consommateurs avec la variante suivante : le magasin de stockage est de taille finie (i.e. un tableau plutôt qu'une liste gérée en FIFO). De plus, nous proposons d'en faire une implantation utilisant, à l'instar du bureau de poste, les objets pour modéliser les ressources.

Définir une classe produit de signature :


# class produit (s:string) =
 object
   val nom = s
   method nom = nom
 end ;;
class produit : string -> object val nom : string method nom : string end


class produit : string -> 
  object
    val nom : string 
    method nom : string 
  end

Définir une classe magasin telle que :


# class magasin n =
   object(self)
     val mutable taille = n;
     val mutable np = 0
     val mutable buffer = ([||] : produit array)
     val mutable ip = 0  (* Indice producteur *)
     val mutable ic = 0  (* Indice consommateur *)
 
     val m = Mutex.create ()
     val c = Condition.create ()
  
     initializer buffer<-Array.create n (new produit "empty")
 
     method display1 () =
       let i = ip mod taille in
       Printf.printf "Ajout (%d)%s\n" i ((buffer.(i))#nom)
 
     method deposer p =
       Mutex.lock m ;
       while (ip-ic+1 > Array.length(buffer)) do Condition.wait c m done ;
       buffer.(ip mod taille) <- p ;
       self#display1() ;
       ip <- ip+1 ;
       Mutex.unlock m ;
       Condition.signal c
 
     method display2 () =
       let i = ic mod taille in 
       Printf.printf "Retrait (%d)%s\n" i ((buffer.(i))#nom)
 
     method prendre () =
       Mutex.lock m ;
       while(ip == ic) do Condition.wait c m done ;
       self#display2() ;
       let r = buffer.(ic mod taille) in
       ic<- ic+1 ; 
       Mutex.unlock m ;
       Condition.signal c ;
       r
   end ;;
class magasin :
  int ->
  object
    val mutable buffer : produit array
    val c : Condition.t
    val mutable ic : int
    val mutable ip : int
    val m : Mutex.t
    val mutable np : int
    val mutable taille : int
    method deposer : produit -> unit
    method display1 : unit -> unit
    method display2 : unit -> unit
    method prendre : unit -> produit
  end


class magasin : int ->
  object
    val mutable buffer : produit array
    val c : Condition.t
    val mutable ic : int
    val mutable ip : int
    val m : Mutex.t
    val mutable np : int
    val taille : int
    method deposer : produit -> unit
    method prendre : unit -> produit
  end

Les indices ic et ip sont manipulés respectivement par les producteurs et les consommateurs. L'indice ic donne l'indice du dernier produit pris et ip celui du dernier produit stocké. Le compteur np donne le nombre de produits en stock. L'exclusion mutuelle et la mise en attente des producteurs et des consommateurs seront gérées par les méthodes de cette classe.

Définir une fonction consommateur : magasin -> string -> unit.


# let consommateur mag na =
   while true do
     let p = mag#prendre() in
     Printf.printf "Le consommateur %s prend le produit %s\n" na p#nom ;
     flush stdout ;
     Thread.delay(Random.float(3.0))
   done ;;
val consommateur :
  < prendre : unit -> < nom : string; .. >; .. > -> string -> unit = <fun>

Définir une fonction creer_produit de type string -> produit. Le nom donné à un produit sera composé de la chaîne passée en argument concaténée à un numéro de produit incrémenté à chaque appel de la fonction.
Utiliser cette fonction pour définir producteur : magasin -> string -> unit.


# let producteur =
   let num = ref 0 in
   let creer_produit () =
     let p = new produit("lessive-"^(string_of_int !num)) in
     incr num ; 
     p
   in
   function mag -> function nm ->
     while true do
       let p = creer_produit () in
       mag#deposer(p) ;
       Printf.printf"Production de %s\n" p#nom ;
       flush stdout ;
       Thread.delay (Random.float (1.0))
      done ;;
val producteur : < deposer : produit -> '_a; _.. > -> '_b -> unit = <fun>