Dépôt facultatif, mais avant le jeudi 11 mars, 18h00.
Cette page sera éventuellement mise à jour avec des indications
supplémentaires.
(Dernière mise à jour le 4 janvier 2006)
Sujet
La commande Unix.gethostbyname permet de trouver l'adresse IP d'une
machine en fonction de son nom. Cette résolution peut utiliser différentes
stratégies, mais en général, la recherche s'effectue d'abord dans un fichier
d'association adresse/nom de la machine locale (/etc/hosts) puis, en
interrogeant une machine de référence (Domain Name Server) qui a
son tour peut en appeler d'autres, etc. de façon transparente. Ce n'est
donc pas un appel système, mais une fonction de bibliothèque complexe. Par
conséquent, la commande peut ne pas retourner immédiatement, voir même
prendre un temps significatif, parfois bien plus long que la connexion à la
machine elle-même une fois son adresse résolue.
Un client WEB du type de wget peut donc se retrouver bloqué, non
pas parce que la page n'est pas disponible sur la machine désirée,
mais parce l'adresse de la machine n'est pas encore résolue.
On peut donc avoir intérêt à séparer la résolution des adresses et de
la récupération des pages proprement dite afin de gérer indépendemment
ces deux tâches.
Le but de ce DM est d'implémenter une bibliothèque permettant de résoudre les
noms de machines efficacement. Pour cela, on diminue la latence en lançant
des requêtes en parallèle en utilisant des coprocessus et en maintenant un
cache de réponses.
La bibliothèque aura l'interface dns.mli suivante:
moduletype S = sigexception Try_againval resolve : string -> Unix.host_entryval try_resolve : string -> Unix.host_entry endmodule Make (P : sigval resolve : string -> Unix.host_entryval max_active_threads : int end) : S
La partie significative de cette bibliothèque est l'interface S,
expliqué ci-après, et l'essentiel du travail consiste à implémenter une
structure ayant cette interface.
Toutefois, la bibliothèque sera fournie sous forme d'un foncteur Make
permettant de la paramétrer par une structure P. La structure P
regroupe une fonction primitive de résolution de noms
P.resolve (typiquement
gethostbyname) et une variable P.max_active_threads qui
impose une limite sur le nombre maximum de coprocessus que l'on
s'autorise à utiliser en même temps pour traiter les requêtes en
parallèle (typiquement de l'ordre de la dizaine) : c'est
essentiellement le facteur par lequel la latence des requêtes pourra
être divisée.
Pour utiliser votre bibliothèque, il suffira donc d'appliquer le foncteur
Dns.Make de la façon suivante:
module D = Dns.Make (structlet resolve = Unix.gethostbynamelet max_active_threads = 13 end ) ;;
Décrivons maintenant l'interface S. La fonction S.resolve
a la même interface que la fonction P.resolve (et aussi
Unix.gethostbyname) et une sémantique équivalente : elle bloque
jusqu'à l'obtention d'une réponse. Toutefois, les réponses peuvent
être fournies plus rapidement si elles sont déjà présentes dans le
cache. Pour pouvoir vraiment bénéficier des avantage d'un telle
bibliothèque, il faudra également pouvoir lancer des requêtes en
parallèle, donc avant d'en avoir réellement besoin. Pour cela, on
utilisera une variante P.try_resolve qui retourne toujours
immédiatement avec une réponse analogue à P.resolve (soit une
vraie réponse, soit l'exception Not_found) ou lève l'exception
Try_again si aucune réponse n'est disponible immédiatement. De
plus, dans ce dernier, la requête est programmée de telle façon que la
réponse soit éventuellement disponible lors d'une prochaine requête
(si un délai suffisemment long s'est écoulé).
Lors d'une demande de résolution de nom, les fonctions de résolution
resolve et try_resolve commencent par vérifier dans un cache que le
résultat n'est pas déjà disponible ou s'il n'est pas déjà en train d'être
résolu. On pourra utiliser pour implanter le cache, une table d'association
Map ou une table de hache Hastbl qui stocke le résultat de la
résolution ou à des informations associées à la requête en cours
Le comportement des fonctions est ensuite le suivant:
si le résultat est déjà dans le cache, il suffit de le
retourner ;
si une requête est déjà en cours :
si l'appel est non-bloquant (try_resolve) la fonction
lève l'exception Try_again ;
si l'appel est bloquant (resolve), les informations
stockées dans le cache doivent permettre d'attendre
jusqu'à ce que la réponse soit disponible et de la retourner le
moment venu ;
sinon, on commence par placer dans le cache les informations
indiquant qu'une requête est en cours, puis :
si l'appel est bloquant le coprocessus courant se charge de
faire la résolution, de mettre à jour le cache et de réveiller les
éventuels coprocessus en attente;
si l'appel est non-bloquant, le coprocessus se contente de
placer le nom à résoudre et les informations relative à la
résolution dans une file d'attente pour que la requête soit traitée par
une piscine de coprocessus.
(Une astuce qu'on pourra utiliser pour simplifier éventuellement la gestion
du cache consiste à mettre l'information sur le calcul en cours où la réponse
du calcul dans une référence.)
La piscine de coprocessus est gérée par un coprocessus «gestionnnaire» qui
lance de nouveaux coprocessus «travailleurs» pour traiter les requêtes tant
qu'il y a des requêtes et que leur nombre de «travailleurs» est inférieur à
la variable max_active_threads.
Un coprocessus «travailleur» effectue alors la résolution d'une requête (il
pourra être plus simple de lui fournir une requête initiale), met à jour le
cache avec le résultat et réveille les éventuels coprocessus en attente du
résultat. Puis le coprocessus prend une nouvelle requête dans la file
d'attente et la traite de la même façon ou se termine s'il n'y a plus
requête en attente.
Bien sûr, l'ensemble des opérations sur les structures de données
seront protégées contre les accès concurrents. On essayera également
de minimiser les zones de code protégées pour favoriser la concurrence
et de limiter les réveils de coprocessus afin d'éviter les
changements de contexte inutiles.
Afin de simplifier l'implantation de cette bibliothèque, on ne se
préoccupera pas de la gestion des signaux qui pourraient être reçus
pendant l'utilisation de la bibliothèque.
Pour tester votre bibliothèque nous vous proposons quelques tests
regroupés dans un fichier tests.ml que vous
pourrez passer avant de soumettre votre DM. Ces tests sont fournis à titre
d'exemple. Vous pouvez les modifier à votre besoin, en ajouter d'autres,
etc.
Ceux-ci utilisent un module
Gethostbyname qui
simule une fonction de résolution de noms
avec l'interface suivante:
moduletype S = sigval addr_number : intval total : float refval gethostbyname : string -> Unix.host_entryval check : unit -> unitval reset : unit -> unit endmodule Make(P: sig val addr_number : int val not_found : int end) : S
La fonction de résolution de noms du module résout des noms qui sont
des entiers sous forme des chaînes de caractères. Ces noms sont
compris entre 0 et addr_number - 1. Pour chaque adresse un
délai est fixé aléatoirement lors de l'instanciation du module. La
fonction utilise ce délai pour simuler un temps de résolution.
La variable total contient la somme des temps de résolutions pour
tous les noms et la fonction check permet de vérifier que chaque
adresse a été résolue une et une seule fois (reset remet ce nombre à
0 pour toutes les adresses).
Le foncteur Make permet de fixer le nombre d'adresses qu'il est
possible résoudre et not_found permet de fixer une proportion
(1 / not_found)
d'adresses qui lèveront une exception Not_found lors de la
résolution.
Le premier test effectué lance des coprocessus qui effectuent des
résolutions de noms bloquantes en concurrence. On vérifie à la fin que
chaque adresse n'a été résolue qu'une seule fois. Un deuxième test évalue
l'influence du nombre maximum de coprocessus utilisés pour la résolution de
noms sur la durée totale de résolution d'un ensemble
d'adresses. Statistiquement, celle-ci devrait être proportionnelle au nombre
maximum de coprocessus utilisés. Cela suppose que le temps de lattence est
prépondérant sur le temps de calcul et ne sera donc plus valable si les
temps de latence deviennent trop faibles. Du fait que nous mesurons des
temps réels, nous observons dès temps des temps de calculs légérement
supérieurs à ce valeur théorique. Toutefois, sur une machine peut chargée,
le temps réel devrait rester proche du temps théorique. Une alarme permet
de terminer les tests qui bloquent trop longtemps (1.3 * G.total), ce qui
peut correspondre à une situation d'interblockage. On pourra facilement
ajuster ce paramètre ou le retirer. Un dernier test vérifie que les
coprocessus qui effectue un appel bloquants sont utilisés pour faire la
résolution de nom.
Les quelques tests décrits ne sont certainement pas exhaustifs. De plus, du
fait du non-déterminisme de l'ordonnancement des coprocessus, ils peuvent
s'avérer non reproductibles.
Vous pourrez compléter ces tests en instrumentant votre code pour qu'il
force des changements de contexte (Thread.yield) au moment des
manipulations de mutex et de condition. Vous aurez ainsi plus de chance de
mettre en évidence des problèmes de synchronisation.
Vous pourrez aussi être amenés à instrumenter votre code à des fins de
deboggage en traçant les prises et relaches de verrous, notemment dans le
cas où vous auriez des situations d'interblocage: indiquer alors à chaque
opération de synchronization le coprocessus qui l'exécute et l'opération
effectuée, ce qui vous donnera une trave d'exécution de votre programme.
Il y a trois situations typiques que vous risquez de rencontrer:
Le programme bloque: vous n'avez peut-être pas bien organisé la
prise/relache de verrous.
Certaines adresses ne sont pas calculées ou calculées plusieurs fois:
vous avez sans doute mal géré l'accès au cache ou sa mise à jour du cache.
Le programme tourne, mais l'augmentation du nombre de coprocessus ne réduit
pas la latence: vous avez peut-être introduit trop de synchronisation avec
pour résultat une séquentialisation des résolutions qui annule l'effet de la
piscine de copocessus.
Procédure de dépôt
Le fichier dns.ml devra respecter l'interface
dns.mli.
Se placer dans le répertoire de dépôt:
cd /users/profs/info/INF552
Invoquer la commande de dépôt:
./deposer-DM2 <chemin>/dns.ml
où <chemin> est un chemin absolu qui mène à votre fichier.
Vous pouvez vérifier le dépôt:
./deposer-DM2
Vous pouvez redéposer plusieurs fois, chaque dépôt effaçant le précédent.