Télécharger le fichier original (Mémoire de fin d’études)

Sûreté de fonctionnement

La sûreté de fonctionnement d’un système informatique est la caractéristique qui permet d’assurer à ses utilisateurs une confiance avérée dans le service qui leur est délivré [02]. Ce dernier est aperçu par ses utilisateurs à travers son comportement. L’utilisateur est un autre système (humain ou physique) qui agit réciproquement avec le système considéré [03]. Quant à la sûreté de fonctionnement, elle peut être présentée autour de trois notions telles que décrites dans la figure 1.1 extraite de [01] à savoir : ses attributs, ses entraves et ses moyens.

Attributs de la sûreté de fonctionnement

Les attributs de la sûreté de fonctionnement se définissent à travers les différentes propriétés que doit vérifier le système.
Ils permettent d’évaluer la qualité du service délivré par le système. Ces attributs sont au nombre de six et sont définis dans [02] comme suit :
 disponibilité : c’est la qualité exigée par la majorité des systèmes sûrs de fonctionnement, ça consiste en la période pendant laquelle le système est disponible pour son utilisation. (en éloignant les temps de défaillance et de réparation);
 fiabilité: cet attribut sert à évaluer la continuité du service c’est-à-dire le taux en temps de fonctionnement durant lequel le système ne subit aucune défaillance ou aucune faute;
 sécurité-innocuité : semblables à la fiabilité mais par rapport aux conséquences graves engendrées par les fautes ;
 confidentialité : cet attribut évalue l’aptitude du système à fonctionner malgré les fautes volontaires et illégalement introduites;
 intégrité : l’intégrité d’un système détermine sa capacité à assurer des modifications approuvées des données;
 maintenabilité : cette qualité décrit la flexibilité et la souplesse du système face à des modifications apportées en vue de sa maintenance.
L’importance des attributs diffère selon l’application et l’environnement auquel est destiné le système informatique en question. La disponibilité, l’intégrité sont d’une façon générale exigées bien évidement a des degrés variables selon l’application .Par contre, la fiabilité, la sécurité-innocuité, la confidentialité peuvent être ou non requis. Dans le pilotage de fusée par exemple les applications sont critiques c’est pourquoi une grande importance doit être donnée à tous les attributs de la sûreté de fonctionnement alors qu’une importance est donnée à la maintenance et la fiabilité concernant les applications parallèles à longue durée d’exécution.

Difficultés de la sûreté de fonctionnement

Dans les difficultés de la sûreté de fonctionnement, on différencie trois types : les fautes, les erreurs et les défaillances.
 Fautes : une faute ou panne est caractérisée par sa nature, son origine et son étendue temporelle [04]. La nature d’une faute précise la manière dont elle a été provoquée : intentionnellement ou accidentellement. La cause de l’apparition d’une faute est révélée par son origine. L’étendue temporelle caractérise la persistance ou la durée d’une faute (temporaire ou permanente).
 Erreurs : une erreur est la conséquence d’une faute. L’emploi d’un état erroné par le système, engendre tout de suite la survenance d’une défaillance [05]. [06], les erreurs ont été classées selon leur type comme suit :
–Premièrement : le service ne convient pas, en valeur, à celui spécifié.
–Deuxièmement : le service n’est pas délivré dans l’intervalle de temps spécifié.
De multiples catégories ont été définies dans [06]. Le service rendu est toujours en avance ou toujours en retard ou encore arbitrairement en avance ou en retard.
On considère aussi comme un type d’erreur si jamais le système néglige ou oublie de rendre le service. On appelle un arrêt (crash) le fait que le système ne délivre plus de services..
 Défaillances : appelé défaillance : l’inaptitude d’un élément du système à garantir le service spécifié par l’utilisateur (son comportement n’est pas conforme à sa spécification).
Cette dernière est nettement marquée par son domaine, sa compréhension et sa perception, par les utilisateurs et ses répercussions sur l’environnement [04].
Fautes, erreurs et défaillances sont liées par des relations de causalité illustrées sur la figure 2.1.
Figure1.2: La chaîne fondamentale des entraves
Une faute activée cause une erreur, qui peut se répandre dans un composant ou d’un composant à un autre jusqu’à produire une défaillance. Il est très important de noter que la défaillance d’un composant peut entraîner une faute permanente ou temporaire dans le système qui le contient, par contre la défaillance d’un système cause une faute permanente ou temporaire pour les systèmes avec lesquels il interagit.

Moyens d’assurer la sûreté de fonctionnement

Au cours des 50 dernières années, de nombreux moyens ont été mis au point pour la sûreté de fonctionnement, Ces moyens peuvent être regroupés en quatre grandes catégories [2]:
 La prévention des fautes : elle interdit la présence des fautes dans le système, en se basant sur des règles de développement (modélisation, utilisation de langage fortement typé, preuve formelle, etc.) ;
 L’élimination des fautes : tient énormément à atténuer la présence des fautes que ça soit en nombre ou degré de gravité ou de sévérité de la faute. Ce moyen ne peut être réalisé que pendant la phase de développement d’un système par vérification, diagnostic et correction, ou bien pendant sa phase opérationnelle par le biais de la maintenance;
 La prévision des fautes cherche à estimer de façon qualitative et quantitative la survenance et les conséquences des fautes. C’est par le biais de la détection d’erreurs et le rétablissement du système qu’on peut la mettre en œuvre;
 La tolérance aux fautes vise à préserver le service malgré l’occurrence de fautes (essaie de cacher ou d’occulter la présence des fautes et permet de continuer à fournir le service demandé malgré leur apparition).
La section suivante va présenter les différentes approches pour réaliser la tolérance aux fautes. Ces méthodes peuvent être groupées de différentes façons.
1. Prévention des fautes et éliminations des fautes peuvent êtres considérées comme constituant « d’évitement des fautes. On cherche à concevoir un système sujet a moins de fautes possible. Il est de même pour la prévention des fautes.
2. Prévention des fautes et tolérance aux fautes peuvent se regrouper sous le concept « d’acceptation des fautes ; partant du principe qu’il ya toujours des fautes inévitables. Seulement il est préférable d’évaluer leur influence sur le système dans le but de diminuer le degré de gravité des défaillances qu’elles peuvent causer ,(si possible jusqu’à suppression totale des défaillances) , on remarque que ses deux méthodes sont complémentaires pour comprendre ou concevoir un système sur de fonctionnement [38].

Tolérance aux fautes

Dans le présent mémoire, nous visons spécialement et plus particulièrement la tolérance aux fautes qu’on considère comme un moyen de la sûreté de fonctionnement et qui a pour but de maintenir un service correct délivré par le système en dépit de l’occurrence ou présence de fautes. La tolérance aux fautes ne peut être mise en œuvre que s’il y a détection d’erreur et rétablissement du système. La figure 1.3 liste les techniques de tolérance aux fautes [38].
Figure 1.3: Techniques de tolérance aux fautes

Détection d’erreur

La détection d’erreur est basée sur une redondance qui peut prendre plusieurs formes : redondance au niveau information ou composant, redondance temporelle ou algorithmique. Les formes de détection d’erreur les plus couramment utilisées sont les suivantes :
 Les codes détecteurs d’erreur ils visent en particulier les erreurs induites par les fautes physiques. La détection est basée sur une redondance dans la représentation de l’information [07].
 La méthode de duplication et comparaison le cout matériel de cette méthode est très important mais malgré ca, elle reste un moyen de détection très utilisé vu sa simplicité de mise en œuvre. Au minimum, deux unités redondantes et obligatoirement indépendantes face aux fautes que l’on souhaite tolérées sont utilisées dans cette méthode.
Typiquement, il existe une redondance des composants matériels concernant les fautes physiques, et diversification pour des fautes de conception [4].
 Le contrôle temporel et d’exécution par “chien de garde” (watch dog) est l’outil le plus couramment utilisé pour la détection d’erreur en ligne, il est particulièrement utilisé pour déceler la défaillance d’un périphérique en assurant que son temps de réponse n’excède pas une valeur seuil ou bien pour contrôler régulièrement l’activité d’une unité centrale. Aussi, se contrôle ce définit par faible cout économique [4].
 Le contrôle de vraisemblance il cherche à détecter des erreurs en valeur aberrantes pour le système. Sa mise en œuvre peut se faire par du matériel de détection, par exemple des adresses mémoires erronées, ou bien par un logiciel de vérification de la conformité des entrées, des sorties ou des variables internes du système par rapport à des invariants [04].

Rétablissement du système

Le rétablissement du système peut être assuré par deux méthodes complémentaires :
Le traitement d’erreur qui vise l’élimination des erreurs, si possible avant la survenance d’une défaillance.
Le traitement de faute qui sert à éviter l’activation à nouveau de la faute à l’origine de l’erreur.

Traitement d’erreur

Trois techniques sont utilisées pour le traitement d’erreur, il s’agit de : la reprise, la poursuite et la compensation [1].
 La reprise : est la technique la plus couramment utilisée. Elle consiste à sauvegarder périodiquement l’état du système pour le ramener dans un état antérieur à l’occurrence de l’erreur. Cet état sauvegardé est appelé point de reprise. Les principaux inconvénients de la reprise sont la taille des sauvegardes, la difficulté d’effectuer des sauvegardes cohérentes, et le surcoût temporel nécessaire à leur établissement.
 La poursuite : cette technique consiste à mettre en place un nouvel état ne contenant pas d’erreur qui permet au système de continuer à fonctionner de façon admissible éventuellement en mode dégradé. La mise du système dans un état sûr, par exemple en l’arrêtant est une forme limite de celle technique.
 La compensation : Cette technique exige que l’état du système contienne suffisamment de redondance, pour permettre, malgré les erreurs qui pourraient l’affecter, sa transformation en un état dépourvu d’erreur . Cette compensation peut intervenir immédiatement suite à une détection d’erreur ou exécutée systématiquement (masquage d’erreur).

Traitement de faute

Ce traitement comprend quatre phases successives : Le diagnostic, la passivation, la reconfiguration et la réinitialisation [10].
• La 1ere phase : le diagnostic de faute : qui sert à identifier la localisation et le type de faute responsable de l’état erroné du système [10].
• La 2eme phase : la passivation : elle est destinée à remplir l’objectif principal de traitement de faute en empêchant une nouvelle activation des fautes. Elle s’opère en excluant la participation du composant erroné de la délivrance du service par des moyens physiques ou logiciels.
• La 3eme phase : la reconfiguration [38] : intervient lorsque le système est incapable de délivrer le même service qu’auparavant. Cette phase vise à compenser l’isolement du composant défaillant, soit par basculement des composants – redondant, soit en réattribuant ses tâches à d’autres composants.
• La 4eme phase : la réinitialisation : cette phase consiste à vérifier et mettre a jour la nouvelle configuration du système [10]. .

Tolérance aux fautes dans les systèmes répartis

Un système distribué est connu par le nombre important de composants. Une faute d’un seul des composants peut mener à la défaillance de tout le système. Ainsi, la défaillance du système est inévitable même si chaque composant présente une probabilité de faute très faible. La fiabilité des systèmes distribués est tributaire de l’occurrence des fautes et l’aptitude à leur faire face [08].
La tolérance aux fautes apparaît comme un élément indispensable aux systèmes répartis. Elle est impérativement actionnée par l’utilisateur d’un mécanisme de redondance [02] .Cette redondance peut être spatiale, (duplication de composants), temporelle, (traitement multiple) ou bien informationnelle, (c.à.d. redondance des données, codes, signatures) [09] .Pour répondre à ce besoin, plusieurs techniques ont été conçues. Ces techniques peuvent être séparées en deux classes : les techniques basées sur la duplication et les techniques basées sur une mémoire stable.

Redondance spatiale et temporelle : réplication

La tolérance aux fautes par réplication consiste à utiliser des copies multiples d’un même composant ou processus sur des processeurs différents. Cette approche par duplication rend possible le traitement des pannes en les masquant. C’est-à-dire le groupe de processus doit être géré de façon à donner l’illusion d’un seul processus logique qui continue à fournir un service correct, malgré la défaillance d’un sous ensemble des membres du groupe. On distingue généralement trois stratégies : la réplication passive, active et semi-active [01].
 Duplication active : une seule copie (la copie primaire) reçoit les requêtes et effectue toutes les opérations. Pour assurer la cohérence, la copie primaire diffuse son état interne régulièrement aux copies secondaires. Cet état sert de point de reprise en cas de défaillance En cas de défaillance de la copie primaire, une des copies secondaires est élue pour prendre sa place.
 Duplication passive : cette réplication se caractérise par la correspondance (symétrie) du comportement des copies d’un composant duplique ou toutes les copies jouent un rôle identique : traitement de tous les messages réceptionnés, mise a jour de son état interne de façon indépendante et production des messages de sortie. Cette stratégie écourte l’utilisation des points de reprise onéreux .Par conséquent, elle nécessite un système de diffusion atomique et exige, pour garantir la cohérence [08], que l’exécution des requêtes soit déterministe.
 Duplication semi-active : c’est une solution hybride entre la réplication active et la réplication passive. Cette stratégie ressemble à la réplication active dans le sens où toutes les copies réceptionnent les messages d’entrée et peuvent aussi les traiter. Cependant, elle se rapproche de la réplication passive son traitement asymétrique ou une copie privilégiée assure la responsabilité de certaines dispositions ( par exemple ,l’acceptation des messages ,ou la préemption du traitement en cours). Appelée la meneuse, cette copie privilégiée peut dicter ses décisions aux autres copies dénommées par le terme des suiveuses sans les consulter. Ainsi, la meneuse peut endosser seule la responsabilité de transmettre les messages de sortie [1].
La tolérance aux fautes par duplication est alors réalisée par masquage d’erreur. La défaillance d’une copie est masquée par le comportement des copies non défaillantes. Le principal désavantage de cette méthode par réplication est qu’elle nécessite de nombreuses ressources : pour tolérer p défaillances, il est nécessaire d’avoir p + 1 composants identiques. Cette méthode n’est donc pas adaptée aux calculs parallèles où la performance (temps de calcul) est souvent le critère prépondérant : les ressources doivent être exploitées en priorité pour le calcul.

Redondance informationnelle : mémoire stable

La mémoire stable n’est qu’une abstraction [11]. Il s’agit d’un support constant de stockage qui a pour rôle d’assurer l’accessibilité aux données et leur protection contre les pannes pouvant affectées le système. En cas de panne, un état correct stocké antérieurement sur la mémoire stable reste accessible et permet au système de revenir à un état antérieur. [09].
Un support de stockage est vu comme une mémoire stable si et seulement si les trois conditions suivantes sont vraies :
1. Accessibilité : il existe à tout moment de l’exécution un chemin permettant d’accéder aux données sauvegardées même en présence des pannes.
2. Protection : les pannes affectant le système ou l’application n’altèrent pas les données.
3. Atomicité : les mises à jour des données sur le support de stockage se font de manière atomique.
Le principe de cette technique est de remplacer l’état d’erreur par un état cohérent en utilisant les informations stockées sur la mémoire stable. Cette approche utilise la redondance d’informations. Ces informations correspondent à la sauvegarde de l’état des processus ou bien à la journalisation d’évènements, et sont stockées sur la mémoire stable.
Le point critique pour réaliser la tolérance aux fautes par mémoire stable est la constitution d’un état correct du système. La constitution d’un tel état introduit un surcoût qui va dépendre des contraintes imposées au système : nombre et types de défaillances à tolérer, reprise globale du système ou uniquement des processus défaillants, etc. [08].
Deux approches ont été proposées dans la littérature pour construire un état global cohérent d’un système réparti [11] :
– A priori : les sauvegardes des différents états des processus coopérants sont coordonnées pour constituer un état global cohérent ;
– A posteriori : les sauvegardes des états des processus sont indépendantes; la reconstitution d’un état global cohérent se fait lors de la reprise.
L’état global d’une application parallèle est composé :
• de l’état local de tous les processus participant au calcul,
• et de l’état de tous les canaux de communication entre les processus.
Les deux sous-sections suivantes présentes les protocoles de reprise basés sur la sauvegarde et les protocoles basés sur la journalisation [8].

Reprise par sauvegarde

Les règles de reprise par sauvegarder assurent la concrétisation des sauvegardes régulières de l’état des processus. L’action de redémarrage nécessite l’utilisation du dernier ensemble de sauvegarde composant un état global cohérent [11].
On distingue généralement trois approches pour la reprise par sauvegarde selon le mode de construction de l’état global cohérent de la reprise :
 Sauvegarde non coordonnée : l’analyse des différences entre les points de sauvegarde au moment de la reprise est assurée par un algorithme pour essayer de délimiter l’ensemble des sauvegardes les plus actuelles composant un état global cohérent. Cette demande génère un surcoût important et une absence de coordination pouvant provoquer un effet domino (réaction en chaîne) .Durant l’élaboration de l’état global cohérent, les dépendances entre les messages peuvent entraîner un retour à l’état initial [01].
 Sauvegarde coordonnée : permet d’assurer que seules des lignes de reprise cohérentes sont créées. Il existe différentes manières de coordonner les processus. La sauvegarde coordonnée bloquante : chaque processus ne peut sauvegarde son état local qu’après que tous les processus sont arrêtés et que les canaux de communication sont vidés. La sauvegarde coordonnée minimale: ne synchronise un processus qu’avec les processus dont il dépend réellement.
 Sauvegarde induite par les communications : c’est un compromis entre les deux approches précédentes Chaque processus peut créer indépendamment des points de reprise locale qui sont complétés par des points de reprise forcés (une sauvegarde qui doit être effectuée pour empêcher l’effet domino).

Reprise par journalisation

Le principe de la tolérance aux fautes par journalisation est de sauvegarder l’histoire de l’application. Les protocoles par journalisation utilisent à la fois la sauvegarde locale de l’état des processus et la journalisation des évènements déterministes pour permettre la reprise de l’application. Il est alors possible de reprendre l’exécution des processus défaillants (et uniquement des processus défaillants) à partir de leur dernière sauvegarde en rejouant les évènements non déterministes sauvegardés [08].
Deux méthodes principales permettent de réaliser la tolérance aux fautes dans les systèmes répartis (figure 1.4) : la duplication et l’abstraction d’une mémoire stable. Dans les deux cas, la tolérance aux fautes est réalisée par l’emploi d’un mécanisme de redondance.
Figure 1.4 : Les techniques de tolérance aux fautes dans les systèmes répartis [09]

Conclusion

Dans ce chapitre, nous avons présenté en premier lieu d’un point de vue très général, les grands principes de la sûreté de fonctionnement des systèmes informatiques, en détaillant les principales méthodes. Nous avons expliqué aussi que la tolérance aux fautes est un moyen pour assurer la sûreté de fonctionnement d’un système et qu’on utilise toujours la redondance pour l’obtenir.
La dernière partie de ce chapitre a présentée un aperçu de la tolérance aux fautes pour les systèmes distribués. Les techniques de tolérance aux fautes spécifiques aux systèmes distribués sont basées sur la réplication ou sur l’utilisation d’une mémoire stable.

Table des matières

Introduction Générale
Chapitre 1 Tolérance aux fautes
1.1 Introduction
1.2 Sûreté de fonctionnement
1.2.1 Attributs de la sûreté de fonctionnement
1.2.2 Difficultés de la sûreté de fonctionnement
1.2.3 Moyens d’assurer la sûreté de fonctionnement
1.3 Tolérance aux fautes
1.3.1 Détection d’erreur
1.3.2 Rétablissement du système
1.3.2.1 Traitement d’erreur
1.3.2.2 Traitement de faute
1.4 Tolérance aux fautes dans les systèmes répartis
1.4.1 Redondance spatiale et temporelle : réplication
1.4.2 Redondance informationnelle : mémoire stable
1.4.2.1 Reprise par sauvegarde
1.4.2.2 Reprise par journalisation
1.5 Conclusion
Chapitre 2 algorithmes évolutionnaires
2.1 Introduction
2.2 Algorithmes évolutionnaires
2.2.1 Terminologie et notations
2.2.2 Principe général :
2.3 Algorithmes génétiques
2.3.1 Représentation
2.3.2 Evaluation : fitness
2.3.3 Sélection
2.3.4 Croisement
2.3.5 Mutation
2.3.6 Opérateur de remplacement
2.3.7 Critère d’arrêt
2.4 Stratégies d’évolution
2.4.1 Représentation
2.4.2 Evolution
2.4.3 Sélection
2.4.4 Croisement
2.4.5 Mutation
2.4.6 Auto-adaptation
2.5 Programmation génétique
2.6 Programmation Evolutive
2.7 Conclusion
Chapitre 3 Graphes et coloration forte strict
3.1 Introduction
3.2 Initiation aux graphes
3.2.1 Définitions
3.2.2 Différents types de graphes
3.2.3 Les prédécesseurs, successeurs d’un sommet:
3.3 Coloration de graphe
3.3.1 Définition:
3.4 Coloration forte stricte
3.4.1 Coloration forte
3.4.2 Coloration forte stricte
3.4.3 Quelques propriétés
3.5 Algorithme de coloration forte stricte généralisé pour les graphes
3.5.1 L’algorithme
3.5.2 L’explication
3.6 Algorithme de distribution du graphe basée sur la coloration forte stricte
3.6.1 L’initialisation
3.6.2 L’optimisation
3.7 Algorithme évolutionnaire basée sur la coloration forte stricte
3.7.1 Représentation de coloration forte stricte
3.7.2 Opérateur d’initialisation
3.7.3 Opérateur de croisement
3.7.4 Opérateur de Correction
3.8 Conclusion
Chapitre 4 Contributions
4.1 Introduction
4 .2 Distribution de l’algorithme évolutionnaire basée sur la coloration forte stricte
4.2.1 Présentation de l’approche
4.3 Positionnement du problème
4.4 La distribution à la volée
4.4.1 La Génération.
4.4.2 La répartition.
4.4.3 Envoyer et Recevoir des parties.
4.5 Mécanisme tolérant aux pannes
4.6 Intégration de nouvelles machines
4.7 Détection de la terminaison
4.7.1 Les canaux vides.
4.7.2 La collection des informations.
4.8 Mise en oeuvre
4.8.1 Langage Matlab.
4.8.2 Matlab pour les algorithmes évolutionnaires.
4.8.3 Matlab Distributed Computing Server.
4.9 Conclusion
conclusion générale
Références

Télécharger le rapport complet