Exclusion mutuelle de groupe basée sur le modèle client-serveur
Modèle Client-Serveur
Définition La notion de client-serveur est fondamentale pour comprendre le fonctionnement des systèmes d’exploitation modernes. Bien qu’elle relève, en toute rigueur, d’un cours sur les communications, il est difficile de ne pas l’aborder indépendamment tant elle intervient aujourd’hui dans le fonctionnement des ordinateurs même en mode non connecté, sans aucune liaison à un réseau. Pour comprendre le schéma du modèle client-serveur on se limitera à imaginer deux processus qui s’exécutent sur une ou deux machines différentes. Ces processus peuvent communiquer entre eux au travers d’interfaces logiciels spécifiques que l’on appelle ports ou Exclusion mutuelle de groupe basée sur le modèle client-serveur Exclusion mutuelle de groupe basée sur le modèle client-serveur sockets. Ces interfaces sont analogues aux structures employées dans les ordres de lecture et d’écriture et mises en oeuvre par une déclaration d’ouverture de fichier fopen en langage C. La différence fondamentale est que ces deux interfaces de communication ne résident pas nécessairement sur la même machine et peuvent se trouver sur deux ordinateurs différents à des milliers de kilomètres. La façon dont la liaison est établie entre ces deux interfaces n’entre pas dans notre propos. Cela relève d’un cours sur les communications. En toute rigueur on peut imaginer un mécanisme client-serveur qui fonctionnerait en employant un autre moyen de communication que les sockets. Des pipes, par exemple, pourraient convenir. La seule restriction serait alors que le client et le serveur ne pourraient résider que sur la même machine, ce qui est trop restrictif pour la généralité de ce mécanisme.
Modèle client-serveur
Le modèle de base pour la structuration des systèmes répartis 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ées 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. 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, imprimer_catalogue, etc.). Lorsque le serveur peut servir plusieurs clients, il est intéressant de l’organiser comme une famille de processus coopérant pour permettre l’exécution concurrente de plusieurs requêtes 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 : while True do 1.133 Begin 1.134 receive(client, message) 1.135 extract(message, service_id, < params >) 1.136 p ← create_processus(client, service_id, < params >) 1.137 End Processus exécutant 1.138 processus p 1.139 Begin 1.140 Do 1.141 service [service_id] (, results) 1.142 Send (client, results) 1.143 EndDo 1.144 exit 1.145 autodestruction 1.146 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éparti sur plusieurs sites, pour augmenter sa disponibilité ou ses performances. 4.2 Préliminaires Le problème de l’exclusion mutuelle de groupe a été introduit par Joung [Jou01a] sous le nom du problème des philosophes parlant d’une même voix. Dans [Jou01a] un autre type d’exclusion mutuelle appelée exclusion mutuelle de groupe (GME) est présenté. Dans le problème de GME, chaque accès à une section critique est associé à un groupe. Les sections critiques qui appartiennent à un même groupe peuvent être exécutées simultanément. Cependant les sections critiques de groupes différents doivent être exécutées dans un ordre séquentiel avec le principe de l’exclusion mutuelle. Un exemple pour le problème GME, décrit dans [Jou98], est le CD-ROM juke-box partagé par plusieurs processus comme on l’a vu dans le chapitre consacré à l’état de l »art. Tout nombre de processus peut simultanément accéder au CD-ROM en cours d’utilisation, mais les processus désirant accéder à un autre 71 Exclusion mutuelle de groupe basée sur le modèle client-serveur CD-ROM doivent attendre. Dans ce cas les sessions sont les CD-ROM dans le juke-box. Joung [Jou01b] a introduit le concept de m-groupes système de quorums. Plusieurs solutions pour le problème GME ont été proposées sans partage de mémoire et d’horloge globale, où les processus communiquent en échangeant des messages. J. Beauquier et al. [BCDP03] ont présenté de nouvelles solutions pour GME : deux solutions basées sur l’arbre couvrant statique (static spanning tree). Dans [AM05] la notion de sorrogate-quorum a été utilisé pour résoudre le problème GME, et requiert une complexité basse en terme de messages, un délai de synchronisation minimum faible et un degré de concurrence élevé. La compléxité en messages est O( q) par demande d’accès en section critique, où q est la taille maximale d’un quorum. Le degré maximum de concurrence est n, ce qui implique qu’il est possible pour tous les processus appartenant au même groupe d’exécuter leurs sections critiques simultanément. Dans ce chapitre, nous proposons une nouvelle solution distribuée pour le problème GME basée sur le chemin inverse (reverse path). Le problème est de concevoir une solution pour les algorithmes distribués de GME satisfaisant les propriétés suivantes : • Exclusion mutuelle (Surêté) : A tout moment, deux sessions de différents groupes ne peuvent être ouvertes simultanément. • Absence de blocage (Vivacité) : Une session désirant être ouverte le sera au bout d’un temps fini. • Entrée concurrente (Efficacité) : Si un groupe g de processus demande une session et aucun autre groupe de processus n’est intéressé par une session différente, alors les processus du groupe g peuvent accéder en section critique de façon concurrente [Jou98, KM01, Had01].
Exclusion mutuelle distribuée
Modèle de système distribué
Un système distribué est organisé comme un ensemble de processus ou noeuds qui s’exécutent sur des sites reliés par un réseau de communication et qui communiquent par envoi de message. Sur chaque site, il est possible de définir un état local, qui est modifié par l’exécution des processus du site. Les messages font un temps fini mais arbitraire pour atteindre les processus qui les reçoivent. L’ordre des messages à travers les liens de communication fiable du réseau sont FIFO. L’algorithme présenté dans ce chapitre partage dans sa conception certaines conditions pour l’environnement du système distribué. A chaque processus dans le système distribué, il lui est associé une identification unique d’un entier naturel. Il y a exactement un seul processus en demande d’exécution sur chaque noeud. Les processus compétissent pour une seule ressource. A tout moment, chaque processus initie au plus une
Algorithme proposé
Notre contribution a été ici de proposer une solution distribuée pour l’exclusion mutuelle de groupe basée sur le modèle client-serveur. Nous avons utilisé les mêmes principes pour résoudre le problème de l’exclusion mutuelle de groupe dans un système distribué. Un processus peut plusieurs fois entrer en section critique, tandis qu’une seule session peut être ouverte à la fois. La racine de l’arbre (leader) contrôle un ou plusieurs sessions, le jeton est contrôlé par la racine. Quand les processus désirent entrer en section critique de manière concurrente, la sélection ne peut être retardée indéfiniment. Un processus demandant à entrer en section critique ne peut être empêché par un autre au bout d’un délai fini. Avec un graphe connecté, nous construisons un arbre couvrant. Chaque noeud y appartient à l’arbre couvrant (spanning tree). L’arbre couvrant est utilisé afin de minimiser le nombre de messages échangé, et élimine les messages dupliqués. Initialement, un jeton est associé à un noeud. Quand un noeud x demande à entrer en section critique, deux cas sont possibles : 1. Le noeud x a le jeton, dans ce cas, il entre immédiatement en section critique, sans envoyer un message de requête. 2. Le noeud x ne possède pas le jeton, il envoie une requête à son successeur dans l’arbre couvrant, et attend le jeton. Quand un noeud y reçoit un message requête envoyé par un noeud x, plusieurs cas sont possibles : 1. Le noeud y possède le jeton et ne l’utilise pas, alors dans ce cas il l’envoie immédiatement au noeud x. 2. Le noeud y est en section critique alors dans ce cas il garde le message dans sa file d’attente. 3. Dans les autres cas, le noeud y envoie la requête à ses successeurs dans l’arbre couvrant sauf le noeud pour lequel il a reçu la demande.
Télécharger le document complet
