Quelques éléments fondamentaux des systèmes répartis

Michel RIVEILL

Projet IMAG-INRIA Sirac
655, avenue de l’Europe
38330 Montbonnot
Email : Michel.Riveill@univ-savoie.fr

1. CONSTRUCTION D’UN ETAT GLOBAL

Un système réparti est organisé comme un ensemble de processus qui s’exécutent sur des sites reliés par un réseau de communication et qui communique par envoie de messages. Sur chaque site, il est possible de définir un état local, qui est modifié par l’exécution des processus du site. Nous appelons événement un changement local d’état sur un site ou bien l’envoi ou la réception d’un message par un processus. Une horloge unique permet de donner une date à chacun des événements. En revanche, les processus de deux sites différents peuvent avoir des informations différentes sur l’état du système et sur l’ordre des événements qui s’y produisent. En effet, l’état d’un site distant ne peut être connu que par des informations véhiculées par les messages, dont les délais de transmission peuvent varier. Les méthodes pour réaliser l’ordonnancement des événement sont examinées dans les sections qui suivent, ainsi que leur application à la conception d’algorithmes répartis

1.1. Précédence causale

Pour définir l’état d’un système réparti, il faut d’abord pouvoir ordonner les événements. Tout schéma global de datation doit pouvoir respecter l’ordre local sur chaque site, et doit être tel que la date d’émission d’un message soit antérieure à sa date de réception (principe de causalité). Une relation d’ordre entre les événements, vérifiant ces conditions, a été définie comme suit par [Lamport 78]. Soit a et b deux événements. On dit que a précède directement b si et seulement si l’une des deux conditions suivantes est vraie : · a et b se sont produit sur le même site, et a est antérieur à b sur ce site, · a est l’envoi d’un message m depuis un site, et b la réception de ce message m sur un autre site. La relation précède (notée —>) est la fermeture transitive de la relation précède directement. Cette relation dite de précédence causale est un ordre partiel ; elle traduit une dépendance potentielle : pour que a puisse être cause de b, il est nécessaire que a —> b. Deux événements sont dits concurrent (ou causalement indépendant) si aucun des deux ne précède causalement l’autre, et ne peut donc influer sur lui. On écrit : a // b <=> non (a -> b) et non (b -> a).

1.2. Ordonnancement par estampille

Une méthode pratique pour ordonner les événements dans un système réparti, est d’utiliser la relation de précédence causale. Su chaque site Si est créé un compteur Hi à valeurs entières (horloge logique), initialisé à 0, qui sert à dater les événements sur ce site. A chaque événement e arrivant sur Si la valeur Hi est incrémentée de 1 et la date de e, notée Hi(e), est par définition la nouvelle valeur de Hi. Pour garantir la précédence causale, tout message m émis par Si porte une estampille E(m) qui est sa date d’émission, et le site Sj qui reçoit m exécute : Hj := max(Hj, E(m))+1. La relation ainsi définie n’est pas un ordre strict : en effet, des événements causalement indépendants, arrivant sur des sites différents peuvent avoir la même date. Pour obtenir un ordre strict, il suffit de définir un ordre arbitraire entre les sites. Si a et b sont des événements arrivant respectivement sur les sites Si et Sj, on peut définit comme suit une relation d’ordre total strict, notée => : a => b si et seulement si H(a) < Hj(b) ou (Hi(a) = Hj(b) et i<j). Un événement est maintenant daté par le couple (numéro de site, estampille).

1.3. Ordonnancement par horloges vectorielles

La relation d’ordre => définie par les estampilles ne suffit pas pour établir une relation de causalité entre deux événements. On peut simplement dire que l’ordre total défini par la relation => est compatible avec l’ordre partiel de précédence causale -> : si a => b, ou bien a -> b ou bien a et b sont causalement indépendants (aucun événement ne peut être la cause de l’autre). L’ordre total introduit par les estampilles "efface" artificiellement la précédence causale. Il est néanmoins utiles de pouvoir déterminer la dépendance ou l’indépendance causale entre deux événements :
  • Mise au points de programme répartis. La dépendance entre deux événements est une notion centrale pour la recherche des causes potentielles d’une erreur.
  • Placement d’une application répartie. La mesure du degré d’indépendance des calculs est nécessaire pour évaluer les gains liés à la mise en œuvre d’un calcul sur différents processeurs.
  • Réalisation efficace d’algorithme ne nécessitant par un ordre total.
Le mécanisme des horloges vectorielles [Fidge 88, Mattern 88] a été introduit pour caractériser la dépendance causale. Soit n le nombre de site. Sur chaque site Si, i = 1, …, n, on définit une horloge vectorielle comme un vecteur Vi[1..n] initialisé à 0. Lorsqu’un événement se produit sur le site Si, on exécute Vi[i] := Vi[i] + 1. Chaque message m porte comme estampille Vm l’horloge vectorielle Vi du site émetteur. A la réception d’un message (m, Vm), le site récepteur, soit Si exécute : Vi[j] := max (Vi[j], Vm[j]) pour j = 1, …, m Appelons passé d’un événement a l’ensemble constitué de a lui-même et des événements qui précèdent causalement a. Grâce à leur construction, les horloges vectorielles peuvent être interprétées comme suit : si un événement a est daté par le vecteur Va, alors :
  • Va[j] = nombre d’événement du passé de a sur le site Sj,
  • S Va[j] = nombre total d’événements du passé de a.
Définissons une relation d’ordre partiel entre horloges vectorielles :
  • V <=W <=> qq j, V[j] <=W[j]
  • V < W <=> V <= W et V<> W
  • V // W <=> non (V <= W) et non (V <= W)
La relation d’ordre partiel entre horloges vectorielles reflète la relation de précédence causale et peut être exprimé comme suit. Soit deux événements a et b, datés respectivement par les vecteurs Va et Vb. Alors :
  • a -> b <=> Va < Vb
  • a et b causalement indépendants <=> Va // Vb

1.4. Algorithmes répartis pour les systèmes

Par rapport aux algorithmes centralisés habituels, les algorithmes répartis [Raynal 85, Raynal 87] sont caractérisé par l’absence d’état global, par les contraintes dues au système de communication (séquencement des messages, etc.), et enfin par l’importance du traitement des défaillances, dont la probabilité ne peut être négligée. Une étude générale des algorithmes répartis dépasse le cadre de cette note et nous décrivons dans cette section quelques algorithmes importants.

1.4.1. Exclusion mutuelle par estampilles

L’algorithme d’exclusion mutuelle présenté ici [Ricart 81] est une application directe de l’ordonnancement des événements par estampilles. Il est caractéristique d’une classe d’algorithmes qui mettent en œuvre une « file d’attente répartie », dont il existe une représentation partielle sur chaque site. Cette file est ordonnée globalement par l’heure logique des demandes d’entrée. Le principe de l’algorithme est le suivant : un processus qui doit entrer en section critique transmet une demande d’autorisation d’entrée à tous les autres processus, et attend leur accord. Un processus ne peut entrer en section critique que lorsqu’il a reçu une réponse de tous les autres. Un processus pj qui reçoit une demande de la part d’un processus pi réagit comme suit.
  1. Si pj n’est pas en section critique et n’a pas demandé à y entrer, il donne immédiatement son accord à pi.
  2. Si pj a lui-même demandé à entrer en section critique, il ne donne son accord que si la demande de pi est antérieure (au sens de l’ordre global défini par les horloges logiques) à sa propre demande ; sinon, il diffère sa réponse, et enregistre la demande de pi dans une liste d’attente.
  3. Si pj est en section critique, il diffère sa réponse à pi jusqu'à la fin de sa section critique ; à la fin de cette section critique, il transmet son accord à toutes les demandes en attente dans sa liste.
L’entrée d’un processus en section critique nécessite 2(n-1) messages. En l’absence de pannes de sites ou du système de communication, cet algorithme réalise l’exclusion mutuelle, sans interblocage ni privation.

1.4.2. Election

Le problème de l’élection consiste à choisir un processus et un seul parmi plusieurs. L’identité du processus élu est indifférente : les propriétés requises sont l’existence et l’unicité. Le problème de l’élection se pose souvent, dans la pratique, lorsqu’il faut réagir à une défaillance. Si plusieurs processus détectent la défaillance, l’un d’entre eux (et un seul) doit prendre les mesures appropriées. Citons deux exemples classique de l’élection : · Système de type « maître-esclaves ». Une organisation où un processus « maître » unique contrôle le travail de plusieurs processus « esclaves » est courante, notamment pour la gestion d’information en copies multiples ou pour la réalisation de serveurs constitués de plusieurs sites coopérants. La défaillance d’un esclave est traitée par le maître ; lors de la défaillance du maître, un esclave et un seul doit se substituer à lui. L’algorithme d’élection est applicable pour la désignation d’un nouveau maître. · Détection de la perte d’une information, qui doit être reconstituée. L’élection sert à déterminer le processus chargé de cette tâche. Le traitement de la perte d’un jeton circulant en est un exemple typique, qui sert de base à la présentation de ce qui suit. Je jeton circulant de manière continue sur l’anneau, chaque site peut détecter sa perte au moyen d’une horloge de garde ; le choix du délai de garde nécessite de connaître une limite supérieure de la durée d’un tour du jeton. Il faut alors éviter que plusieurs sites, ayant détecté la perte, ne régénèrent chacun un jeton. Comme le choix de l’élu est arbitraire, on choisit par convention, le processus restant de plus grand numéro. L’algorithme que nous décrivons maintenant [Chang 79], procède par filtrage : chaque processus initiateur de l’élection transmet sur l’anneau un message de candidature portant son numéro. Un processus qui reçoit un tel message l’arrête s’il port un numéro inférieur au sien propre, et devient lui-même candidat ; dans le cas contraire, il retransmet le message. Seul le message du processus de plus grand numéro fait donc un tour complet et revient à son émetteur, qui est alors le seul élu. Cet algorithme d’élection permet de choisir le processus qui régénère le jeton en cas de perte.

1.4.3. Terminaison

Le problème de la terminaison est celui de la détection de la fin d’un calcul réparti. Plusieurs processus coopèrent à la réalisation d’un tâche commune et communiquent par messages. La réception d’un message par un processus peut déclencher une nouvelle phase de calcul. Pour détecter la terminaison, il ne suffit pas d’observer que l’ensemble des processus sont au repos ou passifs : des processus ont pu, avant de s’arrêter, émettre des messages qui provoqueront la reprise de l’activité. La terminaison ne peut donc être garantie que si tous les processus sont arrêtés et qu’il n’y a plus de message en transit. On peut noter que le problème de la terminaison se rapproche de celui de l’interblocage, en ce sens qu’il s’agit, dans les deux cas, de propriétés stables : un ensemble de processus interbloqués ou un ensemble de processus coopérants terminés sont dans un état qui n’évoluera plus au cours du temps. Il y a néanmoins des différences importantes : en particulier, l’ensemble des processus dont on veut détecter la terminaison est donné initialement, alors que l’ensemble des processus qui risquent un interblocage n’est généralement pas connu a priori. Nous présentons un algorithme de détection e terminaison utilisant un jeton [Misra 83]. Soit un ensemble de sites organisés en anneau virtuel, avec un processus par site. L’anneau est le seul moyen de communication entre les sites et on suppose que les messages ne peuvent se doubler sur l’anneau. Si chacun des sites a été visité deux fois de suite par le jeton et qu’il est resté passif entre les deux passages, on peut affirmer que la terminaison est détectée. En effet, les messages qui pouvaient être en transit vers un site lors de la première visite du jeton lui sont nécessairement parvenus lors de la seconde visite, et il ne peut plus y en avoir en transit, puisque les autres sites ont été observés passifs et que les messages ne peuvent se doubler. La terminaison, si elle se produit, est ainsi détectée en deux tous de jeton au plus. Pour vérifier qu’un processus est resté inactif entre deux passages du jeton, on associe à chaque site une couleur (blanc ou noir). Le site qui possède le jeton ne le renvoie que lorsque le processus du site est passif ; le site est alors mis à blanc. Si le processus devient actif, le site est mis à noir. Lorsqu’un site blanc reçoit le jeton, on peut donc affirmer que le processus est resté passif en permanence depuis le dernier passage. Le jeton est muni d’un compteur qui enregistre le nombre total de sites trouvés blancs ; ce compteur est remis à zéro si un site est trouvé noir. La terminaison est détectée lorsque la valeur du compteur est égale au nombre total de sites.

1.4.4. Contrôle des accès concurrents et traitements des interblocages

Le principe du contrôle des accès concurrents consiste à ordonnancer les actions des processus concurrents, de telle sorte que le résultat de leur exécution soit équivalent à celui d’une exécution séquentielle (propriété de sérialisation). Il y a conflit d’accès lorsque deux processus veulent exécuter des actions incompatible sur le même objet (par exemple lire et écrire). L’apparition d’un conflit crée une relation de dépendance (notée <<). Cette relation tient compte des caractéristiques du conflit et de l’ordre chronologique. Les relations de dépendances peuvent être représentées globalement à l’aide d’un graphe des dépendances dans lequel les noeuds représentent les processus et les arcs les dépendances engendrées par les conflits d’accès. Un cycle dans le graphe de dépendance est le signe d’une exécution non sérialisable et d’un interblocage entre les différents processus mis en cause dans le cycle. On classe généralement les techniques de contrôle des accès concurrents en deux groupes selon que le contrôle de dépendance a lieu à chaque conflit (méthodes de contrôle continue), ou bien lorsqu’il est reporté à la terminaison du processus (méthodes de certification). Dans la suite de cette note, nous ne nous intéressons uniquement au premier groupe, dans lequel on distingue deux classes de techniques :
1.4.4.1. Respect de l’ordre de verrouillage et méthode de détection-guérison des interblocage.
La relation de dépendance est définie uniquement par l’ordre chronologique des opérations sur l’objet partagé. Pour traduire cette dépendance en terme d’exécution séquentielle, on force le processus à l’origine du conflit à attendre la libération de l’objet verrouillé par le processus concurrent. Dans cette méthode, le graphe des dépendances représente aussi le graphe des attentes entre processus. A chaque conflit un arc est ajouté dans le graphe des attentes. Les interblocages sont détectés par recherche de cycle dans le graphe des attentes. Si un cycle est détecté, un des processus impliqué dans celui-ci doit être annulé (mécanisme transactionnel) et repris ultérieurement. Le choix du processus à annuler est réalisé selon un des critères suivants : celui qui a provoqué l’interblocage, celui qui a verrouillé le moins de ressources, le processus le plus récent. La construction du graphe et la détection des cycles peut être centralisée, chaque processus envoyant alors à un site privilégié chaque conflit ; mais aussi réparties, chaque site, échangeant périodiquement avec ses voisins des sous-graphes pour reconstituer les cycles potentiels.
1.4.4.2. Ordonnancement par estampille et méthodes de prévention des interblocages.
Le principe des techniques d’ordonnancement par estampillage consiste, lorsqu’il y a conflit, à forcer les processus à s’exécuter selon un ordre de sérialisation préétabli. On utilise les estampille pour générer la relation d’ordre. En cas de conflit le système vérifie que les accès concurrents sont effectués dans l’ordre préétabli entre les processus à l’aide de l’estampillage. Si c’est le cas, l’action est acceptée ; dans le cas contraire, le processus doit être annulée (mécanisme transactionnel) et repris. Il est a noté que cette méthode empêche la construction de cycles dans le graphe des attentes. 1.4.5. Diffusion fiable La diffusion est un mécanisme de communication dans lequel un processus émetteur envoie un message m à un ensemble de processus récepteurs. Dans les applications, on demande généralement que la diffusion soit fiable : tous les destinataires du message qui ne sont pas en panne doivent le recevoir ; ou bien, en cas de panne non récupérable de l’émetteur pendant la diffusion, aucun ne doit le recevoir. Un protocole de diffusion fiable doit résister aux pannes du système de communication et des sites. Un mécanisme de diffusion est dit fiable, s’il possède les qualités suivantes :
  1. validité : si un processus correct diffuse un message m, tous le processus destinataires corrects délivrent le message m ;
  2. accord : si un processus destinataire correct délivre un message m, tous les destinataires corrects délivrent le message m ;
  3. intégrité : un message m n’est délivré par un destinataire correct que si un processus a effectivement diffusé m.
En d’autres termes, la diffusion fiable garantit qu’un message diffusé parvient à tous ses destinataires en état de le recevoir, ou à aucun. Cette propriété est essentielle pour le maintient d’information cohérentes. Un protocole de diffusion fiable peut imposer des contraintes plus fortes :
  • maintien de l’ordre causal : si diffuser (m) -> diffuser (m’), alors un destinataire correct ne peut pas délivrer m’ s’il n’a pas au préalable délivré m. Cette propriété garantit que la diffusion préserve la relation de causalité mais ne donne aucun garantie pour la livraison de messages non liés par la relation de causalité.
  • maintien de l’ordre total : si deux processus p et q délivrent chacun les messages m et m’, alors p délivre m avant m’ si et seulement si q délivre m avant m’.
Le protocole ABCAST (pour Atomic Broadcast) [Birman 87] résiste aux défaillances des sites et assure un ordre de réception uniforme par ordonnancement global des messages. Cet ordonnancement est réalisé au moyen d’estampilles. Un site qui reçoit un message, à destination d’un processus de ce site, le met dans une file d’attente locale au site et le marque comme « en attente ». Il renvoie à l’émetteur un accusé de réception estampillé par la date de réception du message. Lorsque l’émetteur a reçu tous les accusés de réception pour un message, il affecte a ce message une estampille définitive qui est la plus grande estampille des accusés de réception du message. Cette estampille est rediffusée à tous les sites destinataires. Chaque destinataire affecte définitivement cette estampille au message correspondant en attente, marque celui-ci comme « prêt » et réordonne la file dans l’ordre croissant des estampilles. Si le message de tête est dans l’état « prêt », il est sorti de la file et délivré à ses destinataires sur le site. Cette méthode garantit que deux messages sont dans le même ordre dans toutes les files où ils se trouvent. Ce protocole utilise une validation à « deux phases » et nécessite 3n messages pour une diffusion vers n sites, en l’absence de pannes. En cas de panne de l’émetteur avant la fin de la rediffusion des estampilles, un des destinataires, soit p, (déterminé par élection) reprend le protocole et le mène jusqu'à terme. A cet effet, le processus p détermine l’état des messages marqués « en attente » dans sa file. Pour chacun de ces message, il interroge les autres processus. Si un processus possède le message dans l’état « prêt », p transmet à tous les processus la valeur correspondante de l’estampille (qui est alors définitive). Sinon, p rediffuse le message, comme s’il n’avait jamais été transmis. Notons que ce protocole de reprise nécessite de conserver les messages dans la file après leur remise à leur destinataire, et de les détruire ultérieurement par ramassage de miettes.

2. DESIGNATION

Dans un système informatique, le nom d’un objet est une information qui remplit deux fonctions : désigner l’objet, c’est à dire le distinguer des autres objets du systèmes ; servir de voie d’accès à un objet pour permettre son utilisation dans le système.

2.1. Nom et liaison

Un nom n’a pas de signification absolue : il doit être interprété dans un contexte de désignation, qui définit l’ensemble des noms valides et les règles d’interprétation de ces noms. Par exemple, dans Unix, un même fichier peut être désigné par au moins quatre noms différents : par un nom symbolique, par un numéro attribué lors de son ouverture, par l’adresse d’un descripteur en mémoire, par l’adresse d’un descripteur sur disque. Les règles d’interprétation des noms spécifie la procédure qui, à partir d’un nom, permet d’atteindre l’objet désigné. Cette procédure comporte souvent plusieurs étapes : l’objet est atteint à partir du nom à travers une suite d’objets intermédiaires, ou relais, qui constitue ce que l’on appelle une chaîne d’accès. En pratique la fonction de désignation associe un nom symbolique (en général une chaîne de caractères) et un nom interne interprétable par les couche basse du système ou directement par le matériel. Ce nom interne est souvent une adresse, ou encore un identificateur unique à partir duquel le système peut retrouver l’adresse par association statique ou dynamique à un nom de niveau inférieur. La liaison est l’action de constitution de la chaîne d’accès. La liaison peut être statique ou dynamique. Dans le premier cas la correspondance entre nom symbolique et adresse est fixé une fois pour toutes, soit lors de l’écriture du programme, soit dans une phase de chargement et édition de lien, préalable à l’exécution. Dans le second cas, la liaison est réalisée au moment de l’exécution soit lors du premier accès, soit à chaque accès. Une méthode générale pour réaliser la liaison dynamique repose sur l’indirection à travers un descripteur dont le nom est connu statiquement et dont le contenu est modifiable. Il est souvent utile de restreindre l’ensemble des noms utilisables à un instant donné par un processus, notamment pour des raisons de protection ou d’efficacité. La notion d’environnement permet d’y parvenir. Un environnement définit un sous-ensemble d’un espace de noms et les règles d’interprétation des noms dans ce sous ensemble. Cette notion s’applique aussi bien aux noms internes qu’aux noms symboliques. Dans un environnement donné, un objet peut être désigné par un nom local qui n’est interprétable que dans cet environnement. Les notions ci-dessus s’appliquent à tous systèmes informatiques. Dans un systèmes répartis apparaissent les aspects spécifiques suivant : · l’espace des noms a une grande taille ; · l’espace des noms évolue dynamiquement, non seulement par création de nouvelles entités, mais par l’adjonction permanente de nouveaux composants ou système, ou par la réorganisation de sa structure interne ; · la recherche de l’indépendance entre entités logique et localisation physique (transparence) conduit à utiliser fréquemment la liaison dynamique entre noms et objets ; · des sous-ensemble importants du réseau peuvent ne pas être accessibles à un instant donné, par suite de pannes ou de déconnexions. Ce la ne doit pas compromettre la réalisation de la désignation dans le reste du système.

2.2. Serveur de nom

2.2.1. Désignation interne

Un nom interne est une information qui désigne une entité dans un système réparti, et qui est destinée à l’usage interne du système. Selon l’organisation du système, les noms internes peuvent désigner des entités différents. Les entités auxquelles on associe le plus couramment des noms internes sont : · les machines sur un réseau ; · les unités d’information : fichiers, segments, ou « objets » selon l’organisation du système ; · les portes servant à la communication. Une porte est essentiellement une file de messages qui permet la communication indirecte entre deux processus. Une porte est souvent associée à un service : un processus demande le service en envoyant un message à cette porte. La notion de porte permet de dissocier l’interface d’un service de son mode de réalisation et de sa localisation physique (une porte pouvant migrer d’un site à un autre en conservant le même nom). Les propriétés requises d’un nom interne sont les suivantes : · il doit désigner un objet de manière unique : deux objets distincts ne doivent pas avoir le même nom ; en revanche un même objet peut être désigné par plusieurs noms ; · il doit permettre de retrouver de manière efficace l’objet désigné ; L’unicité est en général obtenue en concaténant l’identification unique de la machine sur laquelle l’objet désigné a été créé et une identification unique locale à cette machine (par exemple la valeur d’un compteur ou d’une horloge absolue). Pour retrouver un objet à partir de son nom interne, une solution possible est d’inclure dans le nom de l’objet une information sur sa localisation physique. L’inconvénient de cette solution est qu’un objet qui se déplace doit changer de nom, ce qui est contraire au principe de transparence. Si cet événement est très peu fréquent, on peut tolérer les inconvénients qui en résultent : ainsi, une adresse Internet permet d’atteindre une machine en identifiant le réseau sur lequel elle se trouve, mais doit être modifiée si une machine est déplacée d’un réseau à un autre. Pour des objets plus mobiles, il est néanmoins souhaitable de maintenir invariants les noms internes (car ils peuvent être copiés, et il est peu envisageable de conserver des liens inverses vers toutes les copies d’un nom). En conséquence, si la localisation physique d’un objet figure dans le nom interne, elle n’a qu’une valeur d’identification si l’objet peut migrer. Les méthodes utilisées pour retrouver un objet dépendent entre autres de la fréquence de la migration.
  • Si la migration est peu fréquente, l’objet est le plus souvent encore sur son site d’origine. Lorsqu’un objet migre, le système place sur son site d’origine un lien de poursuite indiquant son nouveau site.
  • Si la migration est fréquente, la méthode ci-dessus est coûteuse car les liens de poursuite sont nombreux. Dans ce cas, il faut utiliser des méthodes pour accélérer la recherche, comme l’entretien d’un cache qui associe sur chaque site les noms et les localisations, pour éviter de répéter une recherche longue en cas d’accès rapprochés. En dernier ressort, on doit recourir à une méthode de diffusion, mais une telle recherche doit rester l’exception étant donné son coût élevé.

2.2.2. Désignation symbolique

Un espace des noms qui est un ensemble d’identificateurs sans structure interne est dit « plat ». Cette absence de structure présente deux inconvénients importants lorsque la taille de l’espace est importante : la recherche implique d’explorer tout l’espace ; les risques de conflit restreignent le libre choix des noms. C’est pourquoi l’espace des noms symboliques a généralement une structure hiérarchique, qui réduit ces inconvénients. Un exemple usuel, dans un système dans un système centralisé, est le mode de désignation des fichiers au moyen d’une arborescence de catalogues. Dans un système réparti, il est également très courant de trouver une structure arborescente de l’espace des noms. Le problème de l’évolution d’un tel espace est important dans un système réparti où la composition et l’organisation du système peuvent être modifiés. Deux cas fréquents d’évolution sont la combinaison d’espaces pré-existants pour former un nouvel espace unique, et la réorganisation interne. Le problème de la combinaison d’espaces de noms existants se pose lorsque l’on souhaite réunir plusieurs machines ou sous-système dont chacun a déjà son propre espace de noms, par exemple pour des fichiers ou des usagers. On souhaite ne pas modifier le mode de désignation des fichiers locaux sur une machine donnée. Nous supposons que chaque machine utilise localement une organisation arborescente de l’espace des noms. Deux méthodes sont couramment utilisées :
  • création d’une super-racine virtuelle. Les espaces de noms existants sont regroupés sous une « super-racine », dont les filles sont les racines des espaces de noms locaux. Chacune de ces racines doit elle-même recevoir un nom pour la distinguer des autres. On construit ainsi un environnement universel, tout en préservant l’usage antérieur des environnements locaux.
  • montage logique. On crée un lien entre une entrée dans un catalogue et une arborescence sur une machine distante. On peut ainsi construire un nouvel espace de noms global, qui englobe les espaces initiaux, mais qui n’est plus une arborescence. La structure de cet espace peut devenir complexe si des règles simplificatrices ne sont pas établies pour le montage. Une règle courante consiste à monter partout le catalogue complet d’une machine sous le nom symbolique attribué à cette machine, ce qui permet à un usager de retrouver le même environnement sur tous les sites.

2.2.3. Serveur de désignation

La correspondance entre noms symboliques et noms internes est souvent réalisée, dans les systèmes répartis, par un service spécialisé appelé service de désignation. Ce service est mis en œuvre par un ensemble de serveur de noms (name servers). Un serveur de noms est un composant important d’un système réparti. Le service qu’il fournit doit répondre aux exigences suivantes :
  • disponibilité, car le bon fonctionnement du serveur de noms conditionne l’accès des utilisateurs aux autres services du système,
  • efficacité, car le serveur de noms est consulté souvent,
  • capacité d’évolution, pour permettre l’adjonction, la suppression ou le déplacement de composants du système.
Notons qu’au moins un serveur de noms doit être connu directement par un nom interne ou une adresse, défini statiquement ou mis à jour par l’administration du système, et communiqué à tout client lors de sa connexion au système. La disponibilité du service de désignation est obtenue par redondance. Deux méthodes sont utilisées :
  1. plusieurs serveurs indépendants peuvent chacun assurer la totalité du service, et leur liste est connue à priori de tout utilisateur du système. En cas de défaillance d’un serveur, les clients s’adressent au serveur suivant de la liste.
  2. plusieurs serveurs coopèrent à la réalisation du service. L’organisation doit permettre de continuer à assurer le service en cas de défaillance d’un ou plusieurs serveurs. Par exemple, on peut distribuer les noms entre les serveurs de manière que les objets les plus importants soient accessibles via au moins deux serveurs distincts.

2.3. Localisation des ressources

Un objet que l’on veut accéder peut se trouver sur n’importe quel site ou même migrer entre plusieurs sites. Pour pouvoir accéder à cet objet, il faut d’abord pouvoir le localiser à partir de l’information disponible : un identificateur global unique que nous appellerons Oid (qui est généralement construit à l’aide d’une estampille). Si l’objet ne migre pas, la localisation de l’objet comporte la recherche de l’adresse réseau de son site de résidence que l’on peut retrouver grâce à l’estampille constitué de la référence du site de création et d’un numéro de génération sur ce site. Si l’objet peut migrer, il devient nécessaire d’utiliser une des heuristiques suivantes : · recherche sur le site de création. On fait l’hypothèse que l’objet n’a pas migré et on le recherche sur son site de création. Si l’objet a migré, le service de localisation installe sur ce site un lien de poursuite indiquant le site détenteur de l’objet. En cas de migration fréquente de l’objet, il devient nécessaire de raccourcir les liens de poursuite afin de désigner la localisation d’un objet avec le minimum d’indirection. · recherche dans un cache de localisation. Sur chaque site, le service de localisation entretient un cache contenant la dernière localisation connue pour les objets récemment accédés. En cas d’échec dans la consultation des caches, il peut être nécessaire de diffuser d’abord partiellement et de manière non fiable, puis éventuellement à tous le sites de manière fiable le signal de recherche.

3. COMMUNICATION

3.1. Envoie de message

On appelle voie de communication un dispositif pouvant être utilisé pour la transmission d’information entre deux ou plusieurs entités (organes physiques, programmes, processus, usagers, etc.). Dans les systèmes informatiques répartis, les voies de communication, comme les systèmes eux-mêmes, sont généralement organisées comme une hiérarchie de couches. Chacune de ces couches réalise un niveau d’abstraction particulier, en permettant la communication entre des entités définies à ce niveau. L’opération élémentaire de communication est définie comme la transmission d’une information, appelée message, d’un émetteur vers un (ou plusieurs) récepteur(s). Les primitives de base d’un système de communication sont : envoyer (message, destinataire) recevoir (message, émetteur) Les systèmes de communication se distingue par le mode de désignation de l’émetteur et du destinataire, la synchronisation assurée par les primitives d’émission et de réception, la forme des messages, leur mode d’acheminement, le degré de fiabilité de la transmission, la nature et la performance des voies, etc. Outre ces primitives de base, les systèmes de communication fournissent d’autres fonctions, parmi lesquelles on peut citer :
  • l’établissement ou la coupure d’une liaison permanente entre deux partenaires (cette liaison, ou circuit virtuel, permet ensuite de transmettre un flot de messages sans avoir à désigner explicitement le destinataire) ;
  • le transcodage de l’information (pour assurer la confidentialité ou l’adaptation à des organes physiques particuliers).

3.2. Appel de procédure à distance

L’appel de procédure à distance [Birrel 84] est un mécanisme qui permet à un processus p, implanté sur un site C, d’exécuter une procédure P sur un site distant S, avec un effet globalement identique à celui qui serait obtenu par l’exécution locale de P sur C. Son intérêt est d’étendre à un système réparti une construction dont la sémantique est bien connue. Sa réalisation repose sur l’utilisation d’un processus s (ou serveur), qui exécute la procédure P sur le site S. Le processus client p reste bloqué pendant l’exécution de P et il est réactivé au retour de P. Le principe de transparence s’applique : aussi bien pour le processus client que pour le processus serveur, tout se passe comme si l’appel était local. On introduit à cet effet deux procédures, appelées talons (stub). Le talon client, sur le site appelant, fournit au processus client une interface identique à celle de la procédure appelée ; de même, le talon serveur, sur le site appelé, réalise pour le processus serveur une interface identique à celle d’un appel local . Chacun des talons, liés au programme du processus client ou serveur sur le site correspondant, fonctionne aussi comme un représentant de l’autre processus (client ou serveur) sur ce site. En l’absence de défaillances, les fonctions du talon client, exécuté par le processus appelant, sont : · mettre les paramètres d’appel sous une forme permettant leur transport sur le réseau vers le site appelé ; c’est la fonction d’emballage (marshalling) ; · envoyer vers le site appelé un message contenant l’identité de la procédure appelée et les paramètres ; · provoquer le blocage du processus client, en attendant la réponse du site appelé ; lorsque la réponse arrive, le processus client est réveillé ; il poursuit son exécution dans le talon client pour exécuter les étapes suivantes ;
  • extraire du message de réponse les résultats, s’il y en a, et les transposer dans leur forme interne : c’est la fonction de déballage (unmarshalling) ;
  • exécuter le retour de procédure, avec transmission des résultats ; tout se passe alors, pour le processus client, comme pour le retour d’un appel de procédure local
Sur le site appelé, le processus serveur appel le talon serveur et exécute les fonctions suivantes :
  • à partir du message reçu du client, déterminer la procédure appelée et déballer les paramètre ;
  • exécuter la procédure appelée en lui passant les paramètre (il s’agit d’un appel local).
Au retour de cet appel, l’exécution se poursuit dans le talon serveur, pour exécuter les étapes suivantes ; · préparer le message de retour vers le site appelant, en emballant les éventuels résultats ;
  • envoyer le message de retour au site appelant ;
  • terminer l’exécution : soit par autodestruction si le processus serveur a été créé à la demande, soit par blocage, s’il s’agit d’un serveur pris dans un pool.
La réalisation de programmes d’emballage et de déballage nécessite que soit défini un format standard pour la représentation des paramètres. Comme les processus appelant et appelé s’exécutent dans des espaces d’adressage différents, ces paramètres ne peuvent être transmis que par valeur. En cas de défaillance, l’appel de procédure à distance doit respecter un comportement spécifié. Les spécifications diffèrent selon les garanties à respecter sur le nombre d’exécutions de la procédure appelée après une défaillance du serveur ou du système de communication, suivi d’une tentative de reprise. L’exécution « au moins une fois » est acceptable si la procédure est idempotente (i.e. si l’effet de deux appels successifs est identique à celui d’un appel). L’exécution « au plus une fois » est le cas le plus fréquent. L’exécution « exactement une fois » nécessite des mécanismes évolués pour la détection des erreurs et la redondance du serveur. Les programmeurs d’applications réparties disposent d’outils pour réaliser l’appel de procédure à distance sans avoir à connaître le détail des mécanismes décrit ci-dessus. Ces outils repose sur une spécification des interfaces dans un langage approprié, qui définit pour chaque procédure susceptible d’être appelée à distance une interface qui comporte le nom de la procédure et, pour chaque paramètre, son type et son sens de transmission (argument ou résultat). Un langage de spécification d’interfaces commun à plusieurs langages de programmation permet la communication entre des programmes écrits dans ces différents langages. Il existe des générateurs (ou compilateurs) de talons qui, à partir de la spécification d’interfaces de procédures destinées à être appelées à distance, produisent les talons client et serveur nécessaires. Un compilateur de talons engendre les procédures d’emballage et de déballage, en fonction de la description des paramètres, et réalise la liaison pour l’appel de procédure à distance en identifiant la procédure appelée.

3.3. Modèle client-serveur

Le modèle de base pour la structuration des systèmes réparties met en jeu un processus client, qui demande l’exécution d’un service, et un processus serveur, qui réalise ce service. Client et serveur sont localisés sur deux machines reliés par un réseau de communication. Le modèle client serveur garantit la protection mutuelle du client et du serveur par la séparation de leurs espaces d’adressage. Il permet également de localiser dans un serveur une fonction partagée par plusieurs clients. Le schéma classique d’organisation d’un serveur est celui d’un processus cyclique : while true do begin receive (client, message) ; extract (message, service_id, <params>) ; case service_id of ... id : begin do_service [id] (<params>, results) ; send (client, results) ; end ... end end Nous avons supposé que le serveur peut exécuter plusieurs types de services, identifiés par un nom service-id différent (par exemple, pour un serveur de fichier : lire_fichier, écrire_fichier, impimer_catalogue, etc.). Lorsque le serveur peut servir plusieurs clients, il est intéressant de l’organiser comme une famille de processus coopérants pour permettre l’exécution concurrente de plusieurs requête et exploiter ainsi un multi-processus ou des entrées-sorties simultanées. Le schéma classique comporte un processus cyclique, le veilleur (deamon), qui attend les demandes des clients. Lorsqu’une demande arrive, le veilleur active un processus exécutant qui réalise le travail demandé. Les exécutants peuvent être créés à l’avance et constituer un pool fixe, ou être créés à la demande par le veilleur. Ce dernier schéma est illustré ci après :
  
-- processus veilleur
while true do
    begin
      receive (client, message); extract (message, service-id, <params>); p := create_processus (client, service_id, <params>);
    end ;
 
-- processus exécutant
processus p :
    begin
      do_service [service_id] (<params>, results); send (client, results) ; exit ; -- autodestruction
    end

Notons qu’il n’y a pas identité entre la notion de serveur et la notion de site. Plusieurs serveurs peuvent coexister sur un même site. Un serveur peut être répartis sur plusieurs sites, pour augmenter sa disponibilité ou ses performance.

3.4. Protocole de groupes

4. TOLERANCE AUX FAUTES

4.1. Duplication des données

4.2. Sauvegarde / reprise

4.3. Duplication des services

5. SECURITE ET PROTECTION

5.1. Authentification

5.2. Sécurité (DCE)

6. GESTIONS REPARTIES DES DONNEES

6.1. Gestion répartie de la mémoire

6.2. Gestion répartie des fichiers

6.3. Gestion répartie des objets

7. PLATE-FORMES POUR LA CONSTRUCTION D’APPLICATIONS REPARTIES

7.1. PVM (échange de messages)

7.2. Corba (client serveur)

7.3. Bus de message (Koala)

7.4. Systèmes répartis à objets (Guide)

8. BIBLIOGRAPHIE
[Birman 87] K. P. Birman, T. A. Joseph, Reliable communication in the presence of failure, ACM Transactions on Computers Systems, 5, 1, pp. 47-76, Feb. 1987.
[Birrel 84] A. D. Birrel, B. J. Nelson, Implementing Remote Procedure Call, ACM Transactions on Computer Systems, 2, 1, pp. 39-59, February 1984.
[Chang 79] E. J. Chang, R. Roberts, An improved algorithm for decentralized extrema-finding in circular configurations of processors, Communications of the ACM, 22, 5, pp 281-283, May 1979.
[Fidge 88] C. J. Fidge, Timestamp in message-passing systems taht preserve the partial ordering, Proceedings 11th Australian Conference, February 1988.
[Lamport 78] L. Lamport, Time, Clock and the ordering of events in a distributed system, Communication of the ACM, 21, 7, pp. 125-133, July 1978.
[Mattern 88] F. Mattern, Virtual time and global states in distributed systems, International Conference on Parallel and Distributed Algorithms, North Holland, pp ? 215-226, 1988.
[Misra 83] J. Misra, Detecting termination of distributed computations using markers, Proc. 2nd Symposium on Principles of Distributed Computinng, Montreal, Canada, pp. 290-294, August 1983.
[Raynal 85] M. Raynal, Algorithmes répartis et protocoles, Eyrolles, 1985.
[Raynal 87] M. Raynal, Systèmes répartis et réseaux, Eyrolles, 1987.
[Ricard 81] G . Ricard, A. K. Agrawala, An optimal algorithm for mutual exclusion in computer networks, Communication of the ACM, 24, 1, pp. 9-17, January 1981.

Livres de référence R. Balter, J-P. Banâtre, S. Krakowiak, Construction des systèmes d’exploitation répartis, Collection didactique, INRIA, 1991. A. Coulouris, J. Dollimore, T. Kindberg, Distributed Systems, 2e édition, 642 p., Addison-Wesley, 1994.

Michel RIVEILL

Laboratoire I3S - Bât. ESSI
930 Route des Colles
06903 Sophia Antipolis CEDEX

email : riveill at unice.fr

Généralité

Projet Rainbow

Ressources en lignes

Les rubriques des cours :

 

Rechercher sur ce site avec Google: 

 

dernière mise à jour
le 18 septembre 2003

 

 

Réservation d'Hôtel à Prix Réduits - HotelClub