Systèmes temps réel et aux algorithmes d’ordonnancement

INTRODUCTION
1. Introduction générale
2. Introduction aux systèmes temps réel et aux algorithmes d’ordonnancement
2.1 Introduction
2.2 Définitions
2.2.1 Système réactif
2.2.2 Exemples de système réactif
2.2.3 Système temps réel
2.2.4 Temps réel souple et temps réel strict
2.2.5 Système distribué et système embarqué
2.3 Modélisation des systèmes temps réel
2.3.1 Tâche
2.3.2 Niveau logiciel
2.3.3 Niveau matériel
2.3.4 Caractéristique temporelle
2.3.5 Contrainte matérielle
2.4 Problématique de distribution et d’ordonnancement temps réel
2.4.1 Description du problème
2.4.2 Présentation du problème
2.4.3 Classification des algorithmes d’ordonnancement temps réel
2.5 Algorithme de distribution et d’ordonnancement de SYNDEX
2.6 Conclusion
3. Fiabilité des systèmes
3.1 Introduction
3.2 Terminologie
3.2.1 Sûreté de fonctionnement
3.2.2 Moyen de la sûreté de fonctionnement
3.2.3 Fiabilité
3.2.4 Faute, Erreur, Défaillance
3.2.5 Taux de défaillance
3.3 Modèles pour le calcul de la fiabilité
3.3.1 Modèles combinatoires
3.3.2 Modèles basés sur la chaine de Markov
3.3.3 Modèles basés sur les réseaux de Pétri
3.3.4 Modèles basés sur les algorithmes d’ordonnancement
3.4 Techniques d’évaluation de la fiabilité
3.4.1 Arbre de défaillance
3.4.2 Bloc de diagramme de la fiabilité BDF
3.4.3 Représentation BDD
3.4.4 Ensemble de coupe minimal et le chemin plus court
3.4.5 Algorithme directe
3.5 Conclusion
4. Etat de l’art
4.1 Introduction
4.2 Problème d’optimisation bi-critères
4.3 Classification des algorithmes bi-critères
4.3.1 Agrégation de deux critères a un seul
4.3.1.1 Principe
4.3.2.2 Présentation de quelques algorithmes
4.3.2 Transformation d’un critère à une contrainte
4.3.2.1 Principe
4.3.2.2 Présentation de quelques algorithmes
4.3.3 Hiérarchisation des critères
4.3.2.1 Principe
4.3.2.2 Présentation de quelques algorithmes
4.4 Discussion
4.5 Conclusion
5. Algorithme d’ordonnancement bi-critères : temps réel et fiabilité
5.1 Problème d’ordonnancement et d’optimisation bi-critères
5.1.1 Modèle de faute
5.1.2 Formalisation du problème
5.1.3 Premier critère : Minimisation de la langueur
5.1.4 Deuxième critère : Maximisation de fiabilité
5.2 Heuristique d’ordonnancement et d’optimisation bi-critère
5.2.1 Importance du coût statique
5.2.3 Fonction de SYNDEX
5.2.3 Fonction de compromise
5.2.4 Présentation de l’algorithme de l’heuristique
5.3 BSA
5.4 Génération aléatoire de graphes d’architectures et d’algorithmes
5.3 Etude comparative
5.4 Simulation
5.5 Conclusion
Conclusion et perspectives
Bibliographie

Modèles pour le calcul de la fiabilité

Le calcul de la fiabilité d’un système nécessite la définition d’un modèle de fiabilité. Le choix d’un tel modèle de fiabilité a un effet direct sur le niveau de confiance de ce calcul. Ce modèle doit définir les paramètres de performance des composants logiciels et/ou matériels du système (tels que les taux de défaillance), le niveau et le type de la redondance si elle existe, ainsi que les hypothèses de défaillance. Il existe dans la littérature plusieurs modèles de fiabilité. Les modèles les plus utilisés sont : les modèles combinatoires [1], les modèles basés sur les chaînes de Markov [14], les modèles basés sur les réseaux de Petri et les modèles basés sur la théorie de l’ordonnancement [28]. Nous les présentons dans les paragraphes suivants.

Modèles combinatoires

Généralement, ces modèles utilisent la théorie des graphes pour représenter graphiquement (par un graphe orienté) toutes les combinaisons d’événements élémentaires qui peuvent causer la défaillance d’un système. À chaque nœud son prédécesseur du graphe, qui représente un événement élémentaire, est associé un ensemble de paramètres de performance, telle que la probabilité de son apparition. La fiabilité de ce système est calculée à partir d’une analyse quantitative de chaque graphe. Les deux modèles les plus fréquemment utilisés sont le diagramme de blocs et l’arbre de fautes. Par exemple, l’arbre de fautes est constitué de plusieurs niveaux, où chaque nœud d’un niveau supérieur représente une combinaison de deux ou plusieurs événements liés aux nœuds de niveau inférieur. Les feuilles de l’arbre représentent les événements élémentaires qui peuvent causer la défaillance d’un système et la racine de l’arbre représente l’événement de défaillance du système. Donc, la probabilité que le système défaille est la probabilité d’atteindre la racine de l’arbre à partir de ses feuilles. Les modèles combinatoires sont faciles à comprendre, mais il n’est pas facile de représenter le comportement non indépendant des événements, au sens probabiliste.

Modèles basés sur la chaine de Markov

Les chaînes de Markov permettent de modéliser le comportement dynamique d’un système par un graphe d’états, qui représente tous les états du système et les transitions possibles entre ces états. Les transitions sont pondérées par des probabilités suivant des lois exponentielles.
Le calcul de la fiabilité d’un système peut être effectué grâce à des méthodes de résolution numérique ou par simulation. À la différence des modèles combinatoires les chaînes de Markov permettent la modélisation des événements non indépendants et aussi des événements de réparation des composants du système. Cependant, l’espace d’état peut grossir exponentiellement avec le nombre de composants d’un système, d’où des problèmes algorithmiques pour calculer la fiabilité.

Modèles basés sur les réseaux de pétri

Le comportement dynamique d’un système est ici représenté par un ensemble d’états, de jetons et de transitions. À la différence des modèles combinatoires, les transitions peuvent être associées à n’importe quel type de loi probabiliste. Les réseaux de Petri peuvent être utilisés pour générer des chaînes de Markov. En plus, ils peuvent être utilisés facilement pour représenter les caractéristiques des systèmes concurrents, telles que la synchronisation et le partage des ressources, et aussi pour valider des propriétés d’un système, telle que l’absence de blocage. Le calcul de la fiabilité est basé sur la simulation. Le but de la simulation est d’appliquer à un système un ensemble de tests aléatoires, et d’utiliser ensuite les résultats de ces tests pour calculer la fiabilité de ce système. Cependant, la précision de ce calcul dépend du choix de l’ensemble de tests et augmente avec la durée de la simulation. Or la procédure de production des tests introduit toujours un biais, qui est difficile à mesurer.

Modèles basés sur les algorithmes d’ordonnancement

Il existe plusieurs travaux qui montrent que l’utilisation de la théorie de l’ordonnancement pour la conception des systèmes peut améliorer la fiabilité de ces systèmes, c’est pourquoi, nous nous sommes attachés à ce modèle. Dans ce modèle, un taux de défaillance est associé à chaque composant matériel et le calcul de la fiabilité est basé sur une fonction d’évaluation (Fiab) qui permet d’évaluer la probabilité du bon fonctionnement du système (ou de l’allocation résultante d’un algorithme de distribution/ordonnancement). La fiabilité d’un système dépend donc de l’allocation des composants logiciels de l’algorithme sur les composants matériels de l’architecture.

Bloc-diagramme de Fiabilité

Un BDF est un graphe orienté (N, E), dont chaque sommet de N est un bloc représentant un composant du système et chaque arc de E est un lien de causalité (dépendance) entre deux blocs. Dans tout BDF, deux blocs particuliers sont identifiés: ceux sont sa source S et sa destination D. Un BDF représente un système et il est utilisé pour calculer la fiabilité : un BDF est opérationnel si et seulement si, il existe au moins un chemin opérationnel de S à D.

Un chemin est opérationnel si et seulement si, tous les blocs de ce chemin sont opérationnels. La probabilité qu’un bloc soit opérationnel est sa fiabilité. Par construction, la probabilité qu’un BDF soit opérationnel est donc égale à la fiabilité du système qu’il représente. Quand le BDF est construit, on distingue trois types de système : série, parallèle ou série parallèle.

Télécharger le rapport complet