Previous Up Next

Chapter 5  Communications inter-processus classiques

On a vu jusqu’ici comment manipuler des processus et les faire communiquer avec l’extérieur par l’intermédiaire de fichiers. Le reste de ce cours est consacré au problème de faire communiquer entre eux des processus s’exécutant en parallèle, pour leur permettre de coopérer.

5.1  Les tuyaux

Les fichiers normaux ne fournissent pas un moyen satisfaisant de communication entre processus parallèles. Exemple: dans une situation écrivain/lecteur (un processus écrit des informations, l’autre les lit), si on utilise un fichier comme médium, le lecteur peut constater que le fichier ne grossit plus (read renvoie zéro), mais il ne peut pas savoir si c’est dû au fait que le processus écrivain a terminé, ou bien si l’écrivain est simplement en train de calculer la prochaine information. De plus, le fichier garde trace de toutes les informations transmises, ce qui pose des problèmes, en particulier de place disque.

Les tuyaux (parfois également appelés tubes) fournissent un mécanisme adapté à ce style de communication. Un tuyau se présente sous la forme de deux descripteurs de fichiers. L’un, ouvert en écriture, représente l’entrée du tuyau. L’autre, ouvert en lecture, représente la sortie du tuyau. On crée un tuyau par l’appel système pipe:

     
   val pipe : unit -> file_descr * file_descr

Un appel à pipe retourne une paire (fd_in, fd_out). Le premier résultat fd_in est un descripteur ouvert en lecture sur la sortie du tuyau; le deuxième résultat fd_out est un descripteur ouvert en écriture sur l’entrée du tuyau. Le tuyau proprement dit est un objet interne au noyau, accessible uniquement via ces deux descripteurs. En particulier, le tuyau créé n’a pas de nom dans le système de fichiers.

Un tuyau se comporte comme un tampon géré en file d’attente (first-in, first-out): ce qu’on lit sur la sortie du tuyau, c’est ce qu’on a écrit sur l’entrée, dans le même ordre. Les écritures (write sur le descripteur d’entrée) remplissent le tuyau, et lorsqu’il est plein, bloquent en attendant qu’un autre processus vide le tuyau en lisant depuis l’autre extrémité; ce processus est répété plusieurs fois, si nécessaire, jusqu’à ce que toutes les données fournies à write aient été transmises. Les lectures (read sur le descripteur de sortie) vident le tuyau. Si le tuyau est entièrement vide, la lecture bloque jusqu’à ce qu’un octet au moins soit écrit dedans. Les lectures retournent dès qu’il y a quelque chose dans le tuyau, sans attendre que le nombre d’octets demandés à read soit atteint.

Les tuyaux ne présentent donc aucun intérêt si c’est le même processus qui écrit et qui lit dedans. (Ce processus risque fort de se bloquer à tout jamais sur une écriture trop grosse, ou sur une lecture dans un tuyau vide.) Ce sont donc généralement des processus différents qui écrivent et qui lisent dans un tuyau. Comme le tuyau n’est pas nommé, il faut que ces processus aient été créés par fork à partir du processus qui a alloué le tuyau. En effet, les descripteurs sur les deux extrémités du tuyau, comme tous les descripteurs, sont dupliqués au moment du fork, et font donc référence au même tuyau dans le processus père et dans le processus fils.

Exemple:

le fragment de code ci-dessous est typique.

     
   let (fd_infd_out) = pipe() in
   match fork() with
     0 ->
       close fd_in;
       ... write fd_out buffer1 offset1 count1 ...
   | k ->
       close fd_out;
       ... read fd_in buffer2 offset2 count2 ...

Après le fork, il y a deux descripteurs ouverts sur l’entrée du tuyau (un dans le père, un dans le fils), et de même pour la sortie.

Dans cet exemple, on a choisi de faire du fils l’écrivain, et du père le lecteur. Le fils ferme donc son descripteur fd_in sur la sortie du tuyau (pour économiser les descripteurs, et pour éviter certaines erreurs de programmation). Cela laisse le descripteur fd_in du père inchangé, car les descripteurs sont alloués dans la mémoire du processus et, après le fork, la mémoire du fils et celle du père sont disjointes. Le tuyau, alloué dans la mémoire système, continue à exister puisqu’il y a encore le descripteur fd_in du père ouvert en lecture sur sa sortie. Le père ferme de même son descripteur sur l’entrée du tuyau. La situation est donc la suivante:

Les données que le fils écrit sur fd_out arrivent donc bien jusqu’au descripteur fd_in du père.

Lorsqu’on a fermé tous les descripteurs sur l’entrée d’un tuyau, read sur la sortie du tuyau renvoie zéro: fin de fichier. Lorsqu’on a fermé tous les descripteurs sur la sortie d’un tuyau, write sur l’entrée du tuyau provoque la mort du processus qui fait write. Plus précisément: le noyau envoie un signal SIGPIPE au processus qui fait write, et le comportement par défaut de ce signal est de tuer le processus (voir la partie “signaux” ci-dessous), ou si le comportement du signal SIGPIPE à été modifié alors l’appel système write échoue avec une erreur EPIPE.

5.2  Exemple complet: le crible d’Ératosthène parallèle

L’exemple qui suit est un grand classique de la programmation par processus communicants. Le but du programme est d’énumérer les nombres premiers et de les afficher au fur et à mesure. L’idée est la suivante: initialement, on connecte un processus qui énumère les entiers à partir de 2 sur sa sortie avec un processus “filtre”. Le processus filtre commence par lire un entier p sur son entrée, et l’affiche à l’écran.

Le premier processus filtre lit donc p=2. Ensuite, il crée un nouveau processus filtre, connecté à sa sortie, et il se met à filtrer les multiples de p depuis son entrée; tous les nombres lus qui ne sont pas multiples de p sont réémis sur sa sortie.

Le processus suivant lit donc p=3, l’affiche, et se met à filtrer les multiples de 3. Et ainsi de suite.

Cet algorithme n’est pas directement implémentable en Unix, parce qu’il crée trop de processus (le nombre d’entiers premiers déjà trouvés, plus un). La plupart des systèmes Unix limitent le nombre de processus à quelques dizaines. De plus, dix processus actifs simultanément suffisent à effondrer la plupart des machines mono-processeurs, en raison des coûts élevés de commutation de contextes pour passer d’un processus à un autre. Dans l’implémentation qui suit, chaque processus attend d’avoir lu un certain nombre d’entiers premiers p1, …, pk sur son entrée avant de se transformer en filtre à éliminer les multiples de p1, …, pk. En pratique, k = 1000 ralentit raisonnablement la création de nouveaux processus.

On commence par le processus qui produit les nombres entiers de 2 à k.

     
   open Unix;;
   
   let input_int = input_binary_int
   let output_int = output_binary_int
   
   let generate k output =
     let rec gen m =
       output_int output m;
       if m < k then gen (m+1)
     in gen 2;;

Pour communiquer les entiers en la sortie d’un générateur et l’entrée du filtre suivant on peut utiliser les fonctions suivantes:

     

La fonction output_binary_int est une fonction de la bibliothèque standard qui écrit la représentation d’un entier (sous forme de quatre octets) sur un out_channel. L’entier peut ensuite être relu par la fonction input_binary_int. L’intérêt d’employer ici la bibliothèque standard est double: premièrement, il n’y a pas à faire soi-même les fonctions de conversion entiers/chaînes de quatre caractères (la représentation n’est pas spécifiée, mais il est garanti que pour une version du langage, elle est indépendante de la machine); deuxièmement, on fait beaucoup moins d’appels système, car les entrées/sorties sont temporisées, d’où de meilleures performances. Les deux fonctions ci-dessous construisent un in_channel ou un out_channel qui temporise les lectures ou les écritures sur le descripteur Unix donné en argument:

     
   val in_channel_of_descr  : file_descr -> in_channel
   val out_channel_of_descr : file_descr -> out_channel

Ces fonctions permettent de faire des entrées/sorties temporisées sur des descripteurs obtenus indirectement ou autrement que par une ouverture de fichier. Leur utilisation n’a pas pour but de mélanger les entrées/sorties temporisés avec des entrées sorties non temporisées, ce qui est possible mais très délicat et fortement déconseillé, en particulier pour les lectures. Il est également possible mais très risqué de construire plusieurs in_channel (par exemple) sur le même descripteur de fichier.

On passe maintenant au processus filtre. Il utilise la fonction auxiliaire read_first_primes. L’appel read_first_primes input n lit n nombres sur input (un in_channel), en éliminant les multiples des nombres déjà lus. On affiche ces n nombres au fur et à mesure de leur construction, et on en renvoie la liste.

     
   let print_prime n = print_int nprint_newline()
   
   let read_first_primes input count =
     let rec read_primes first_primes count =
       if count <= 0 then
         first_primes
       else
         let n = input_int input in
         if List.exists (fun m -> n mod m = 0) first_primes then
           read_primes first_primes count
         else begin
           print_prime n;
           read_primes (n :: first_primes) (count - 1)
         end in
     read_primes [] count;;

Voici la fonction filtre proprement dite.

     
   let rec filter input =
     try
       let first_primes = read_first_primes input 1000 in
       let (fd_infd_out) = pipe() in
       match fork() with
         0 ->
           close fd_out;
           filter (in_channel_of_descr fd_in)
       | p ->
           close fd_in;
           let output = out_channel_of_descr fd_out in
           while true do
             let n = input_int input in
             if List.exists (fun m -> n mod m = 0) first_primes then ()
             else output_int output n
           done
     with End_of_file -> ();;

Le filtre commence par appeler read_first_primes pour lire les 1000 premiers nombres premiers sur son entrée (le paramètre input, de type in_channel). Ensuite, on crée un tuyau et on clone le processus par fork. Le processus fils se met à filtrer de même ce qui sort du tuyau. Le processus père lit des nombres sur son entrée, et les envoie dans le tuyau s’ils ne sont pas multiples d’un des 1000 nombres premiers lus initialement.

Le programme principal se réduit à connecter par un tuyau le générateur d’entiers avec un premier processus filtre (crible  k énumère les nombres premiers plus petits que k. Si k est omis (ou n’est pas un entier) il prend la valeur par défaut max_int).

     
   let crible () =
     let len = try int_of_string Sys.argv.(1) with _ -> max_int in
     let (fd_infd_out) = pipe () in
     match fork() with
       0 ->
         close fd_out;
         filter (in_channel_of_descr fd_in)
     | p ->
         close fd_in;
         generate len (out_channel_of_descr fd_out);;
   
   handle_unix_error crible ();;

Ici, nous n’avons pas attendu que les fils terminent pour terminer le programme. Les processus pères sont des générateurs pour leurs fils. Lorsque k est donné, le père va s’arrêter en premier, et fermer le descripteur sur le tuyau lui permettant de communiquer avec son fils. Lorsqu’il termine, OCaml vide les tampons sur les descripteurs ouverts en écriture, donc le processus fils peut lire les dernières données fournies par le père. Il s’arrête à son tour, etc. Les fils deviennent donc orphelins et sont temporairement rattachés au processus 1 avant de terminer à leur tour.

Lorsque k n’est pas fourni, tous les processus continuent indéfiniment (jusqu’à ce que l’un ou plusieurs soient tués). La mort d’un processus entraîne la terminaison d’un de ses fils comme dans le cas précédent et la fermeture en lecture du tuyau qui le relie à son père. Cela provoquera la terminaison de son père à la prochaine écriture sur le tuyau (le père recevra un signal SIGPIPE, dont l’action par défaut est la terminaison du processus).

Exercice 12   Comment faut-il modifier le programme pour que le père attende la terminaison de ses fils?
(Voir le corrigé)
Exercice 13   À chaque nombre premier trouvé, la fonction print_prime exécute l’expression print_newline() qui effectue un appel système pour vider de tampon de la sortie standard, ce qui limite artificiellement la vitesse d’exécution. En fait print_newline() exécute print_char '\n' suivi de flush Pervasives.stdout. Que peut-il se passer si on exécute simplement print_char '\n'? Que faire alors?
(Voir le corrigé)

5.3  Les tuyaux nommés

Certaines variantes d’Unix (System V, SunOS, Ultrix, Linux) fournissent la possibilité de créer des tuyaux associés à un nom dans le système de fichiers. Ces tuyaux nommés (aussi appelés fifo) permettent la communication entre des processus sans liens de famille particuliers (au contraire des tuyaux normaux, qui limitent la communication au créateur du tuyau et à ses descendants).

L’appel permettant de créer un tuyau nommé est:

     
   val mkfifo : string -> int -> unit

Le premier argument est le nom du tuyau; le deuxième, les droits d’accès voulus.

On ouvre un tuyau nommé par l’appel système openfile, comme pour un fichier normal. Lectures et écritures sur un tuyau nommé ont la même sémantique que sur un tuyau simple. Cependant l’ouverture d’un tuyau nommé en lecture seule ou en écriture seule est bloquante jusqu’à ce que ce tuyau soit ouvert par un autre processus en écriture ou en lecture, respectivement (ce qui peut déjà être le cas et il n’y a pas à attendre), à moins que l’ouverture soit faite avec le drapeau O_NONBLOCK. Dans ce denier cas les lectures ou écritures effectués sur le tuyau ne seront pas non plus bloquantes. On peut changer ce drapeau une fois le tuyau ouvert avec la fonction clear_nonblock et rendre les lectures ou les écritures suivantes sur le tuyau bloquantes (ou non bloquantes avec set_nonblock).

     
   val set_nonblock : file_descr -> unit
   val clear_nonblock : file_descr -> unit

5.4  Redirections de descripteurs

Avec ce qu’on a vu jusqu’ici, on ne sait toujours pas connecter par un tuyau des processus via leurs entrées et sorties standard, comme le fait le shell pour exécuter des commandes de la forme cmd1 | cmd2. En effet, les descripteurs sur les extrémités d’un tuyau qu’on obtient avec pipe (ou avec openfile sur un tuyau nommé) sont de “nouveaux” descripteurs, distincts des descripteurs stdin, stdout et stderr.

Pour ce genre de problèmes, Unix fournit un appel système, dup2 (lire: “DUPlicate a descriptor TO another descriptor”), qui permet de rediriger un descripteur vers un autre. Ceci est rendu possible par le fait qu’il y a un niveau d’indirection entre un descripteur de fichier (un objet de type file_descr) et l’objet du noyau, qu’on appelle une file table entry, qui contient effectivement le pointeur vers le fichier ou le tuyau associé, et la position courante de lecture/écriture.

     
   dup2 : file_descr -> file_descr -> unit

L’appel dup2 fd1 fd2 a pour effet de faire pointer le descripteur fd2 vers la même file table entry que celle pointée par fd1. Après exécution de cet appel, fd2 est donc un duplicata de fd1: les deux descripteurs font référence au même fichier ou tuyau, à la même position de lecture/écriture.

Exemple:

redirection de l’entrée standard.

     
   let fd = openfile "foo" [O_RDONLY] 0 in
   dup2 fd stdin;
   close fd;
   execvp "bar" [|"bar"|]

Après le dup2, le descripteur stdin fait référence au fichier foo. Toute lecture sur stdin va donc lire depuis le fichier foo. (Et aussi toute lecture depuis fd; mais on ne va plus utiliser fd par la suite, et c’est pourquoi on le ferme immédiatement.) De plus, cet état de choses est préservé par execvp. Et donc, le programme bar va s’exécuter avec son entrée standard reliée au fichier foo. C’est ainsi que le shell exécute des commandes de la forme bar < foo.

Exemple:

redirection de la sortie standard.

     
   let fd = openfile "foo" [O_WRONLYO_TRUNCO_CREAT] 0o666 in
   dup2 fd stdout;
   close fd;
   execvp "bar" [|"bar"|]

Après le dup2, le descripteur stdout fait référence au fichier foo. Toute écriture sur stdout va donc écrire sur le fichier foo. Le programme bar va donc s’exécuter avec sa sortie standard reliée au fichier foo. C’est ainsi que le shell exécute des commandes de la forme bar > foo.

Exemple:

relier l’entrée d’un programme à la sortie d’un autre.

     
   let (fd_infd_out) = pipe() in
   match fork() with
     0 -> dup2 fd_in stdin;
          close fd_out;
          close fd_in;
          execvp "cmd2" [|"cmd2"|]
   | _ -> dup2 fd_out stdout;
          close fd_out;
          close fd_in;
          execvp "cmd1" [|"cmd1"|]

Le programme cmd2 est exécuté avec son entrée standard reliée à la sortie du tuyau. En parallèle, le programme cmd1 est exécuté avec sa sortie standard reliée à l’entrée du tuyau. Et donc, tout ce que cmd1 écrit sur sa sortie standard est lu par cmd2 sur son entrée standard.

Que se passe-t-il si cmd1 termine avant cmd2? Au moment du exit dans cmd1, les descripteurs ouverts par cmd1 sont fermés. Il n’y a donc plus de descripteur ouvert sur l’entrée du tuyau. Lorsque cmd2 aura vidé les données en attente dans le tuyau, la prochaine lecture renverra une fin de fichier; cmd2 fait alors ce qu’il est censé faire quand il atteint la fin de son entrée standard — par exemple, terminer. Exemple de cette situation:

     
   cat foo bar gee | grep buz

D’un autre côté, si cmd2 termine avant cmd1, le dernier descripteur sur la sortie du tuyau est prématurément fermé, et donc cdm1 va recevoir un signal (qui, par défaut, termine le processus) la prochaine fois qu’il essaye d’écrire sur sa sortie standard. Exemple de cette situation:

     
   grep buz gee | more

et on quitte more avant la fin en appuyant sur q. À ce moment là, grep est prématurément arrêté, sans qu’il aille jusqu’à la fin du fichier gee.

Exercice 14   Comment implémenter quelques-unes des autres redirections du shell sh, à savoir:
     
   >>      2>      2>>     2>1     <<
(Voir le corrigé)

Échanger deux descripteurs est plus délicat: la séquence dup2 fd1 fd2; dup2 fd2 fd1 à laquelle on pourrait penser naïvement ne convient pas. En effet, la seconde opération de redirection n’a aucun effet, puisqu’après la premier les deux descripteurs fd1 et fd2 pointent déjà vers la même file table entry. L’ancienne valeur de fd2 a été perdue. Comme pour intervertir le contenu de deux références, il faut utiliser une variable auxiliaire pour sauvegarde l’une des deux valeurs. Ici, il faut sauvegarder l’un des deux descripteurs, en le recopiant avec l’appel système dup.

     
   val dup : file_descr -> file_descr

L’appel dup fd retourne un nouveau descripteur qui pointe vers la même file table entry que fd. Par exemple, on peut maintenant échanger stdout et stderr par le code suivant:

     
   let tmp = dup stdout in
   dup2 stderr stdout;
   dup2 tmp stderr;
   close tmp;;

Ne pas oublier de refermer le descripteur temporaire tmp, devenu inutile, afin d’éviter une fuite de mémoire.

5.5  Exemple complet: composer N commandes

On va construire une commande compose, telle que

compose cmd1 cmd2 … cmdn

se comporte comme la commande shell

cmd1 ∣ cmd2 ∣ ⋯ ∣ cmdn.
     
   open Sys;;
   open Unix;;
   
   let compose () =
     let n = Array.length Sys.argv - 1 in
     for i = 1 to n - 1 do
       let (fd_infd_out) = pipe() in
       match fork() with
         0 ->
           dup2 fd_out stdout;
           close fd_out;
           close fd_in;
           execv "/bin/sh" [| "/bin/sh""-c"Sys.argv.(i) |]
       | _ ->
           dup2 fd_in stdin;
           close fd_out;
           close fd_in
     done;
     match fork() with
       0 ->
         execv "/bin/sh" [|"/bin/sh""-c"Sys.argv.(n) |]
     | _ ->
         let rec wait_for_children retcode =
           try
             match wait() with
               (pidWEXITED n) -> wait_for_children (retcode lor n)
             | (pid_)         -> wait_for_children 127
           with
               Unix_error(ECHILD__) -> retcode in
         exit (wait_for_children 0)
   ;;
   handle_unix_error compose ();;

L’essentiel du travail est fait par la boucle for des lignes 6–18. Pour chaque commande sauf la dernière, on crée un nouveau tuyau, puis un nouveau processus. Le nouveau processus (le fils) relie l’entrée du tuyau à sa sortie standard, et exécute la commande. Il hérite l’entrée standard du processus père au moment du fork. Le processus principal (le père) relie la sortie du tuyau à son entrée standard, et continue la boucle. Supposons (hypothèse de récurrence) que, au début du ième tour de boucle, la situation soit la suivante:

(Les carrés représentent des processus, avec leur entrée standard à gauche et leur sortie standard à droite. Les deux ellipses représentent l’entrée standard et la sortie standard initiales du processus compose.) Après pipe et fork, la situation est la suivante:

Le père appelle dup2; on obtient:

Le fils appelle dup2 puis exec; on obtient:

Tout est prêt pour le prochain tour de boucle.

L’exécution de la dernière commande est faite en dehors de la boucle, parce qu’il n’y a pas besoin de créer un nouveau tuyau: le processus compose a déjà la bonne entrée standard (la sortie de l’avant-dernière commande) et la bonne sortie standard (celle fournie initialement à la commande compose); il suffit donc de faire fork et exec du côté du processus fils. Le processus père se met alors à attendre que les fils terminent: on fait wait de manière répétée jusqu’à ce que l’erreur ECHILD (plus de fils à attendre) se déclenche. On combine entre eux les codes de retour des processus fils par un “ou” bit-à-bit (opérateur lor) pour fabriquer un code de retour raisonnable pour compose: zéro si tous les fils ont renvoyé zéro, non nul sinon.

Remarque: si les exécutions des commandes cmdi passent par l’intermédiaire de /bin/sh, c’est pour le cas où l’on fait par exemple

     
   compose "grep foo" "wc -l"

L’appel à /bin/sh assure le découpage de chaque commande complexe en mots. (On aurait pu le faire soi-même comme dans l’exemple du mini shell, mais c’est pénible.)

5.6  Multiplexage d’entrées-sorties

Dans les exemples qu’on a vus jusqu’ici, les processus communiquent de façon “linéaire”. En particulier, un processus lit des données en provenance d’au plus un autre processus. Les situations où un processus doit lire des données en provenance de plusieurs processus posent des problèmes supplémentaires, comme on va le voir maintenant.

On considère l’exemple d’un émulateur de terminal multi-fenêtres sur un micro-ordinateur. C’est-à-dire, on a un micro-ordinateur relié à une machine Unix par une liaison série, et on cherche à faire émuler par le micro-ordinateur plusieurs terminaux, affichant chacun dans une fenêtre différente sur l’écran du micro, et reliés à des processus différents sur la machine Unix. Par exemple, une fenêtre peut être reliée à un shell, et une autre à un éditeur de textes. Les sorties du shell s’affichent sur la première fenêtre, les sorties de l’éditeur, sur la seconde; les caractères entrés au clavier du micro sont envoyés sur l’entrée standard du shell si la première fenêtre est active, ou sur l’entrée standard de l’éditeur si la seconde est active.

Comme il n’y a qu’une liaison physique entre le micro et la machine Unix, il va falloir multiplexer les liaisons virtuelles fenêtre/processus, c’est-à-dire entrelacer les transmissions de données. Voici le protocole qu’on va utiliser. Transitent sur la liaison série des paquets de la forme suivante:

Voici comment les choses se passent du côté de la machine Unix. Les processus utilisateur (shell, éditeur, etc.) vont être reliés par des tuyaux à un ou plusieurs processus auxiliaires, qui lisent et écrivent sur la liaison série, et effectuent le multiplexage et le démultiplexage. La liaison série se présente sous la forme d’un fichier spécial (/dev/ttya, par exemple), sur lequel on fait read et write pour recevoir ou envoyer des octets au micro-ordinateur.

Le démultiplexage (transmission dans le sens micro vers processus) ne pose pas de difficultés. Il suffit d’avoir un processus qui lit des paquets depuis la liaison série, puis écrit les données lues sur le tuyau relié à l’entrée standard du processus utilisateur destinataire.

Le multiplexage (transmission dans le sens processus vers micro) est plus délicat. Essayons l’approche symétrique du démultiplexage: un processus lit successivement sur les tuyaux reliés aux sorties standard des processus utilisateur, puis met les données lues sous forme de paquets (en ajoutant le numéro de la fenêtre destinataire et la taille du bloc de données lu) et les écrit sur la liaison série.

Cette approche ne marche pas, car les lectures sur tuyaux sont bloquantes. Par exemple, si on décide de lire sur la sortie du shell, mais que le shell n’affiche rien pendant ce temps, le processus multiplexeur reste bloqué; et si pendant ce temps l’éditeur affiche des caractères, ces caractères ne seront pas transmis au micro-ordinateur. Il n’y a aucun moyen de savoir à l’avance quels sont les tuyaux sur lesquels il y a effectivement des données en attente d’affichage. (En algorithmique parallèle, cette situation où un processus se voit refuser indéfiniment l’accès à une ressource partagée est connue sous le nom de “situation de famine”.)

Essayons une deuxième approche: à chaque processus utilisateur est associé un processus “répéteur”, qui lit la sortie standard du processus utilisateur par l’intermédiaire d’un tuyau, la met sous forme de paquet, et écrit directement le paquet sur la liaison série. (Chaque processus répéteur a ouvert /dev/ttya en écriture.)

Les situations de blocage ne sont plus à craindre, puisque chaque processus utilisateur a sa sortie retransmise indépendamment des autres processus utilisateur. En revanche, le protocole n’est pas forcément respecté. Deux répéteurs peuvent en effet écrire deux paquets au même instant (ou presque). Or, le noyau Unix ne garantit pas que les écritures sont atomiques, c’est-à-dire effectuées en une seule opération ininterruptible. Le noyau peut très bien transmettre à /dev/ttya une partie du paquet écrit par le premier répéteur, puis le paquet écrit par le second répéteur, puis le reste du premier paquet. Ceci va plonger le démultiplexeur qui est à l’autre bout de la liaison dans la plus extrême confusion: il va prendre le deuxième paquet pour une partie des données du premier paquet, puis il va essayer d’interpréter le reste des données du premier paquet comme un en-tête de paquet.

Pour éviter cette situation, il faut que les processus répéteurs se synchronisent pour assurer que, à tout instant, au plus un répéteur est en train d’écrire sur la liaison série. (En algorithmique parallèle, on dit qu’il faut assurer l’exclusion mutuelle entre les processus qui accèdent à la ressource partagée.) On peut le faire avec les moyens qu’on a vu jusqu’ici: les répéteurs créent un fichier donné (le “verrou”) avec l’option O_EXCL de openfile avant d’écrire un paquet, et le détruisent après avoir écrit le paquet. Cette méthode n’est pas très efficace, en raison du coût de création et de destruction du fichier verrou.

Une troisième approche consiste à reprendre la première approche (un seul processus multiplexeur), en mettant en mode “non bloquant” les descripteurs ouverts sur les tuyaux reliés aux sorties standard des processus utilisateur. (Le passage en mode “non bloquant” se fait par une des options de l’appel système fcntl, qu’on ne décrira pas dans ce cours.) En mode “non bloquant”, les opérations de lecture sur un tuyau vide ne bloquent pas, mais retournent immédiatement avec une erreur. Il suffit d’ignorer cette erreur et de passer à la lecture sur le prochain processus utilisateur. Cette approche empêche la famine et ne pose pas de problèmes d’exclusion mutuelle, mais se révèle très inefficace. En effet, le processus multiplexeur fait ce qu’on appelle de l’attente active: il consomme du temps de calcul même s’il n’y a rien à faire — par exemple, si les processus utilisateur n’envoient rien sur leur sortie pendant un certain temps. Bien entendu, on peut diminuer la fréquence des tentatives de lecture en introduisant par exemple des appels sleep dans la boucle de lecture; mais il est très difficile de trouver la bonne fréquence: celle qui charge suffisamment peu la machine lorsqu’il n’y a rien à retransmettre, mais qui n’introduit pas de délai perceptible dans la transmission lorsqu’il y a beaucoup à retransmettre.

On le voit, il y a là un problème sérieux. Pour le résoudre, les concepteurs de BSD Unix ont introduit un nouvel appel système, select, qui se trouve maintenant sur la plupart des variantes d’Unix. L’appel select permet à un processus de se mettre en attente (passive) d’un ou plusieurs événements d’entrée-sortie. Les événements possibles sont:

     
   val select :
       file_descr list -> file_descr list -> file_descr list ->
         float -> file_descr list * file_descr list * file_descr list

Les trois premiers arguments sont des ensembles de descripteurs (représentés par des listes): le premier argument est l’ensemble des descripteurs à surveiller en lecture; le deuxième argument est l’ensemble des descripteurs à surveiller en écriture; le troisième argument est l’ensemble des descripteurs à surveiller en exception. Le quatrième argument est un délai maximal d’attente, exprimé en secondes. S’il est positif ou nul, l’appel select va rendre la main au bout de ce temps, même si aucun événement ne s’est produit. S’il est strictement négatif, l’appel select attend indéfiniment qu’un des événements demandés se produise.

L’appel select renvoie un triplet de listes de descripteurs: les descripteurs effectivement prêts en lecture (première composante), en écriture (deuxième composante), ou sur lesquels une condition exceptionnelle s’est produite (troisième composante). Si le délai maximal s’est écoulé sans aucun événement, les trois listes sont vides.

Exemple:

Le fragment de code ci-dessous surveille en lecture les deux descripteurs fd1 et fd2, et reprendre la main au bout de 0,5 secondes.

     
   match select [fd1;fd2] [] [] 0.5 with
     [],[],[] -> (* le délai de 0,5s est écoulé *)
   | fdl,[],[] ->
       if List.mem fd1 fdl then
            (* lire depuis fd1 *);
       if List.mem fd2 fdl then
            (* lire depuis fd2 *)

Exemple:

La fonction multiplex ci-dessous est le coeur du multiplexeur/démultiplexeur pour l’émulateur de terminaux virtuels décrit plus haut. (Pour simplifier, le multiplexeur se contente d’étiqueter les messages en fonction de leur provenance et le démultiplexeur suppose que les messages sont étiquetés en fonction de leur destinataire: on suppose donc soit que chaque émetteur parle à une destinataire de même numéro, soit qu’au milieu de la ligne on établit la correspondance émetteur destinataire en ré-étiquetant les messages.)

La fonction multiplex prend un descripteur ouvert sur la liaison série, et deux tableaux de descripteurs de même taille, l’un contenant les tuyaux reliés aux entrées standard des processus utilisateur, l’autre les tuyaux reliés à leurs sorties standard.

     
   open Unix;;
   
   let rec really_read fd buff start length =
     if length <= 0 then () else
       match read fd buff start length with
         0 -> raise End_of_file
       | n -> really_read fd buff (start+n) (length-n);;
   
   let buffer = String.create 258;;
   
   let multiplex channel inputs outputs =
     let input_fds = channel :: Array.to_list inputs in
     try
       while true do
         let (ready_fds__) = select input_fds [] [] (-1.0) in
         for i = 0 to Array.length inputs - 1 do
           if List.mem inputs.(iready_fds then begin
             let n = read inputs.(ibuffer 2 255 in
             buffer.[0] <- char_of_int i;
             buffer.[1] <- char_of_int n;
             ignore (write channel buffer 0 (n+2));
             ()
           end
         done;
         if List.mem channel ready_fds then begin
           really_read channel buffer 0 2;
           let i = int_of_char(buffer.[0])
           and n = int_of_char(buffer.[1]) in
           if n = 0 then
             close outputs.(i)
           else begin
             really_read channel buffer 0 n;
             ignore (write outputs.(ibuffer 0 n);
             ()
           end
         end
       done
     with End_of_file ->
       ()
   ;;

La fonction multiplex commence par construire un ensemble de descripteurs (input_fds) contenant les descripteurs d’entrée (ceux qui sont connectés aux sorties standard des processus utilisateur), plus le descripteur sur la liaison série. À chaque tour de la boucle while true, on appelle select pour surveiller en lecture input_fds. On ne surveille aucun descripteur en écriture ni en exception, et on ne borne pas le temps d’attente. Lorsque select retourne, on teste s’il y a des données en attente sur un des descripteurs d’entrée, ou sur le canal de communication.

S’il y a des données sur une des entrées, on fait read sur cette entrée, on ajoute un en-tête aux données lues, et on écrit le paquet obtenu sur le canal. Si read renvoie zéro, ceci indique que le tuyau correspondant a été fermé. Le programme à l’autre bout de la liaison série va recevoir un paquet contenant zéro octets de données, ce qu’il va interpréter comme “le processus utilisateur numéro tant est mort”; il peut alors fermer la fenêtre correspondante.

S’il y a des données sur le canal, on lit d’abord l’en-tête, ce qui donne le numéro i de la sortie destinataire et le nombre n d’octets à lire; puis on lit les n octets sur le canal, et on les écrit sur la sortie numéro i. Cas particulier: si n vaut 0, on ferme la sortie correspondante. L’idée est que l’émulateur de terminal à l’autre bout de la liaison va envoyer un paquet avec n = 0 pour signifier une fin de fichier sur l’entrée standard du processus correspondant.

On sort de la boucle quand really_read déclenche une exception End_of_file, c’est-à-dire quand la fin de fichier est atteinte sur la liaison série.

5.7  Miscelleaneous: write

La commande Unix.write itère l’appel système write jusqu’à ce que la quantité demandée soit effectivement la quantité transférée. Lorsque le descripteur est un tuyau (ou une prise que l’on verra dans le chapitre suivant), l’écriture est par défaut bloquante. L’appel système write peut donc être interrompu en présence de signaux. L’erreur EINTR est alors remontée vers OCaml, alors qu’une partie des données a déjà pu être transférée par un appel précédent à write. La taille des données transférée est alors perdue, irrémédiablement, ce qui rend Unix.write inutilisable en présence de signaux.

Pour remédier à ce problème, OCaml relève également l’appel système write sous le nom single_write. Nous montrons sur cet exemple comment relever un appel système en OCaml. Il s’agit en fait simplement d’interfacer OCaml avec du code C et on pourra se reporter à la section correspondante du manuel OCaml. Le code suivant est écrit dans un fichier single_write.c.

     
   #include <errno.h>
   #include <string.h>
   #include <caml/mlvalues.h>
   #include <caml/memory.h>
   #include <caml/signals.h>
   #include "unixsupport.h"
   
   CAMLprim value caml_single_write
           (value fdvalue bufvalue vofsvalue vlen) {
     CAMLparam4(fdbufvofsvlen);
     long ofslen;
     int numbytesret;
     char iobuf[UNIX_BUFFER_SIZE];
     ofs = Long_val(vofs)
     len = Long_val(vlen)
     ret = 0;
     if (len > 0) {
       numbytes = len > UNIX_BUFFER_SIZE ? UNIX_BUFFER_SIZE : len;
       memmove (iobuf, &Byte(bufofs), numbytes);
       enter_blocking_section();
       ret = write(Int_val(fd), iobufnumbytes);
       leave_blocking_section();
       if (ret == -1) uerror("single_write"Nothing);
     }
     CAMLreturn (Val_int(ret));
   }

Les deux premières lignes incluent des bibliothèques C standards. Les trois suivantes incluent des bibliothèques C spécifiques à OCaml et installées avec. La bibliothèque "unixsupport.h" qui permet de réutiliser certaines fonctions C d’Unix comme le traitement d’erreur, etc. n’est pas installée par défaut et il faut la récupérer dans les sources de la distribution.

La ligne la plus significative est l’appel à write (ligne 21). Comme celui-ci est bloquant (si le descripteur est un tuyau ou une chaussette), il faut relâcher le verrou OCaml immédiatement avant l’appel et le reprendre après (lignes 20 et 22), afin d’être compatible avec la bibliothèque Thread et de permettre éventuellement à d’autres coprocessus de s’exécuter pendant l’attente (voir le Chapitre 7). OCaml peut donc effectuer un GC pendant l’exécution de l’appel système, ce qui oblige à se prémunir contre un déplacement de la chaîne OCaml buf en la recopiant dans une chaîne C iobuf. Cela a un coût supplémentaire, mais seulement de l’ordre de 10% et non de l’ordre de 50% comme on pourrait s’y attendre, car la gestion de l’appel système et des structures systèmes liés à la copie gardent un coût prépondérant.

La taille de cette chaîne est bornée par UNIX_BUFFER_SIZE, afin d’éviter des à coups inutiles, définie dans unix_support.h. Une erreur pendant l’appel système, signalée par une valeur de retour strictement négative, est propagée vers OCaml par la fonction uerror, définie dans la bibliothèque Unix.

Pour remonter ce code en OCaml, le fichier unix.mli déclare

     
   external unsafe_single_write :
     file_descr -> string -> int -> int -> int = "caml_single_write"

En pratique, on vérifie les arguments avant d’appeler cette fonction.

     
   let single_write fd buf ofs len =
     if ofs < 0 || len < 0 || ofs > String.length buf - len
     then invalid_arg "Unix.write"
     else unsafe_single_write fd buf ofs len

Cette fonction est disponible en OCaml depuis la version 3.08. Autrement, pour utiliser cette fonction dans un programme main.ml, en supposant que l’on ait écrit le code précédant dans des fichiers write.mli et write.ml, il aurait fallu compiler comme suit:

     
   ocamlc -c single_write.c write.ml
   ocamlc -custom -o prog unix.cma single_write.o write.cmo mod1.ml mod2.ml

Il est souvent plus pratique de fabriquer une bibliothèque write.cma réunissant le code C et OCaml:

     
   ocamlc -custom -a -o write.cma single_write.o write.cmo

On peut alors utiliser write.cma simplement comme on utilise unix.cma:

     
   ocamlc -o main.byte unix.cma write.cma main.ml

La fonction single_write reproduit l’appel write aussi fidèlement que possible. La seule différence reste que lorsque la chaîne d’origine est très longue, l’appel est autoritairement découpé en plusieurs appels. L’atomicité de l’appel à write (garantie dans le cas des fichiers réguliers) n’est donc pas préservée pour des écritures très longues. Cette différence est assez marginale, mais il faut en être conscient.

Au dessus de cet appel nous pouvons réimplanter une fonction de plus haut niveau really_write analogue à really_read qui écrit effectivement la quantité demandée.

     
   let rec really_write fd buffer offset len =
     let n = restart_on_EINTR (single_write fd buffer offsetlen in
     if n < len then really_write fd buffer (offset + n) (len - n);;

Previous Up Next