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.
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_in, fd_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.
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 n; print_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_in, fd_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_in, fd_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).
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?
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).
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_WRONLY; O_TRUNC; O_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_in, fd_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.
sh, à savoir:
>> 2> 2>> 2>1 << |
É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.
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_in, fd_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 (pid, WEXITED 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.)
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.(i) ready_fds then begin let n = read inputs.(i) buffer 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.(i) buffer 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.
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 fd, value buf, value vofs, value vlen) { CAMLparam4(fd, buf, vofs, vlen); long ofs, len; int numbytes, ret; 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(buf, ofs), numbytes); enter_blocking_section(); ret = write(Int_val(fd), iobuf, numbytes); 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 offset) len in if n < len then really_write fd buffer (offset + n) (len - n);; |