Le nom le dit : ceci n'est qu'un bref, pas une description exhaustive des sujets couverts.
Ce petit document se base sur :
Ce qui suit décrit très brièvement quelques sujets importants pour la question plus générale de la gestion des ressources réparties. C'est une question vaste qui mériterait un cours à elle seule; conséquemment, chacun de ces sujets n'est que survolé par la présente. N'hésitez pas à pousser plus loin votre étude.
L'algorithme du banquier est l'un des algorithmes les plus connus pour gérer des ressources réparties tout en évitant les Deadlocks. Cet algorithme nous vient de Dijkstra en 1965[1]. L'idée générale est de passer par un médiateur (le système d'exploitation) pour obtenir des ressources, mais de faire en sorte que le service de la demande soit remis à plus tard si le médiateur détermine que la desservir immédiatement pourrait provoquer un Deadlock. Son intérêt est surtout historique.
L'idée va comme suit :
Il est sous-entendu ici que le tiers conserve aussi la trace de toutes les ressources ayant été allouées pour chaque client potentiel, car évaluer le pire cas de demande possible dépend de ce savoir – si un client possède trois ressources et n'en demandera jamais plus de cinq, alors le pire cas possible pour ce client est de deux.
C'est un algorithme conservateur, manifestement. Bien qu'il fonctionne bien en théorie, cet algorithme exige que le tiers connaisse d'avance le pire cas de demande de chaque client – en pratique, on ne le sait que rarement. Il peut être généralisé de manière à couvrir le pire cas par type de ressource (il suffit alors d'avoir plusieurs banquiers).
Pour en savoir plus, voir http://en.wikipedia.org/wiki/Banker%27s_algorithm
Par Deadlock, on entend une situation où deux processus, et , se bloquent mutuellement de manière inextricable pour eux. Le cas le plus simple implique deux ressources et de manière telle que possède et bloque en attente de alors que possède et bloque en attente de . Cela dit, des situations bien plus complexes sont possibles, et le nombre de processus participant dans un cycle de Deadlocks peut être arbitrairement grand.
Par Livelock, on entend une situation où deux processus, et , se bloquent mutuellement de manière inextricable pour eux, mais sans cesser de s'exécuter. Dans un Livelock simple, veut la ressource et possède la ressource , alors que veut la ressource et possède la ressource . Constatant qu'il n'est pas en mesure d'accomplir sa tâche, chacun relâche « sa » ressource puis la reprend et s'essaie à nouveau. Il est alors possible que les deux se butent à la même situation encore et encore... Un Livelock survient si cette situation perdure ad vitam aeternam.
Quelques trucs pour éviter les interblocages, en pratique :
Dans les deux cas, une part de discipline de programmation est requise, mais cette discipline peut être renforcée par les langages et les outils. Par exemple, certains éléments de C++ 11 formalisent l'obtention ordonnancée des ressources (on peut par exemple demander avec la fonction std::lock() un groupe de mutex, et cette fonction fait en sorte que la demande se fasse toujours selon un ordre imposé par le programme).
Qui dit traitement réparti et systèmes réparti dit aussi répartition des ressources. L'un des cas les plus étudiés est, sans surprises, celui des systèmes de fichiers répartis. Ce bref survol s'intéresse aux caractéristiques souhaitées de tels systèmes de fichiers. Le cas particulier de NFS, bien connu, est survolé un tout petit plus en détail un peu plus bas.
Un système de fichiers réparti, pour être pertinent, doit offrir un certain nombre de caractéristiques. Ce qui suit liste quelques-unes des principales caractéristiques souhaitées d'un tel système.
On souhaite qu'un système de fichiers réparti soit transparent, à plusieurs niveaux :
On souhaite qu'un système de fichiers réparti soit échelonnable (néologisme personnel pour Scalable). En effet, il faut pouvoir y ajouter des clients, des médias d'entreposage, des fichiers et des dossiers en fonction des besoins.
On souhaite que plusieurs clients puissent réaliser des mises à jour concurrentes au contenu et à la structure du système de fichiers (chose que NFS permet plus ou moins, d'ailleurs).
On souhaite aussi d'un système de fichiers réparti :
Typiquement, un système de fichiers réparti reposera sur les systèmes de fichiers des plateformes sous-jacentes et assurera le volet réparti par une interface de plus haut niveau.
Le système de fichiers réparti NFS est un cas particulier bien connu. Ce qui suit donne un exemple sous forme d'une vue aérienne et sans prétention des traits caractéristiques de ce système, à titre informatif. Voir comment ce système résout ses problèmes et rencontre les exigences attendues d'un système de fichiers réparti donne des pistes pour penser nos propres systèmes.
Comme bien des systèmes de fichiers répartis, NFS est en fait un métasystème de fichiers. Il est implémenté selon une approche RPC. L'implémentation originale fut réalisée chez Sun Microsystems mais ses interfaces sont du domaine public depuis 1989.
Comme tout métasystème de fichiers, NFS offre une gamme d.'opérations peu importe la plateforme sous-jacente. Ces opérations incluent :
Depuis sa version 3, NFS est en fait un système client/ serveur avec serveurs sans états, sauf pour une tenue à jour de la liste des clients. Il utilise des proxy côté client (avec possibilité de cache locale) alors que le serveur réalise des opérations idempotentes.
Lorsqu'un client soumet ds requêtes, il est responsable de les numéroter de manière unique avec croissance monotone. Ceci permet de détecter les requêtes manquantes ou hors-séquence.
Le serveur étant sans états, il ne peut pas implémenter une cache des écritures. Conséquemment, chaque appel RPC menant à une écriture est synchrone au sens faible du terme (l'écriture a lieu sur le système de fichiers avant que l'appel de fonction ne soit complété). Pour que les performances demeurent acceptables, NFS a recours à des mémoires non-volatiles et à des disques en mémoire (RAM Disks). Il reste que, sans grandes surprises, NFS montre de meilleures performances en lecture qu'en écriture, surtout si plusieurs petites écritures doivent être réalisées.
Au sens de NFS, chaque écriture est atomique pour un serveur donné. Le protocole que NFS utilise pour véhiculer les données est RPC/XDR alors qu'il a recours à son propre protocole (le protocole NFS) pour les opérations.
|
De manière générale, NFS est intégré à bas niveau avec le système d'exploitation, particulièrement les variantes de Linux ou de Unix. NFS tend à maintenir une correspondance directe, 1:1 avec le modèle Unix pour la plupart des opérations, mais le fait qu'un serveur NFS soit sans état influence la signature de ses services. Dns l'esquisse proposée à droite, remarquez le descripteur de fichiers, fd, passé à toutes les fonctions sans exception. Ce descripteur doit être riche, et ne peut se limiter à un int car le serveur ne peut retenir à quelle ressource est associé chaque descripteur. Le client porte seul cette responsabilité. |
fd = open(...); fd = creat(...); stat = close(fd); n = read(fd, ...); n = write(fd, ...); pos = lseek(fd, ...); stat = unlink(fd, ...); |
[1]Note historique sympathique : le texte original de Dijkstra se nommait, dans sa version anglaise, An algorithm for the prevention of the deadly embrace. J'ai eu vent que certains utilisent en français le terme « Étreinte fatale » comme traduction pour Deadlock. C'est charmant et, manifestement, pas fou du tout.
