Vers une mémoire transactionnelle temps réel

Notion de tâche temps réel

   Dans la littérature, le terme tâche se réfère à une suite cohérente d’opérations afin d’exécuter un programme. Ce terme est souvent préféré au terme processus pour signifier la périodicité ou la cyclicité d’exécution. Le terme processus est attaché quant à lui, plutôt au sens de l’unicité de la demande d’exécution. Au moment de son exécution, l’entité tâche est composée d’un ensemble de travaux. Dans un environnement multicœur, ces travaux peuvent être attribués aux différents cœurs en parallèle, mais en règle générale, le parallélisme au sein même d’un travail n’est pas admis. Outre les contraintes de temps que nous allons définir par la suite, les tâches peuvent avoir d’autres contraintes à respecter parmi lesquelles (Silly-Chetto 1993) :
– les contraintes de ressources. Les ressources partagées autres que les processeurs ne sont pas forcément disponibles au moment de l’activation des tâches, et leur accès doit être protégé de manière à assurer leur cohérence (ex : variables partagées en mémoire).
– les contraintes de synchronisation qui imposent un certain ordre d’exécution formulé par des relations de précédence. Lorsqu’aucune relation de précédence n’est appliquée à une tâche, celle-ci est dite indépendante.
– les contraintes d’exécution. Deux modes sont considérés : préemptif et non-préemptif. Une tâche est dite préemptible, si elle peut être interrompue à un instant quelconque et être reprise ultérieurement. Dans le cas non-préemptif, la tâche s’exécute complètement de manière ininterrompue à partir du moment où elle obtient le processeur.
– les contraintes de placement qui portent sur l’identité du (ou des) processeur(s) d’un système multicœur sur lequel une tâche est autorisée à s’exécuter. Dans la suite de ce chapitre, nous discuterons plus précisément de ces contraintes de placement

Types d’ordonnancements

Ordonnancement hors-ligne / en-ligne Quelle que soit la plateforme considérée (monocœur/multicœur), lorsque l’ordonnancement est établi avant le lancement des tâches et que leur comportement est bien connu pour l’ensemble de leurs actions, alors l’ordonnancement est dit hors-ligne. L’ordonnancement est en revanche dit en-ligne si la décision d’ordonnancement est prise pendant l’exécution.
Ordonnancement préemptif / non-préemptif Dans un ordonnancement préemptif, l’exécution d’un travail peut être interrompue à un instant arbitraire puis reprise à un instant ultérieur. L’ordonnancement non-préemptif quant à lui, garantit à tout travail l’exclusivité du processeur durant toute sa durée d’exécution.
Ordonnancement à priorités fixes Un algorithme d’ordonnancement à priorité fixe au niveau des tâches, attribue des priorités statiques aux tâches. Ces priorités sont directement héritées par les travaux de ces tâches. Tous les travaux d’une même tâche auront toujours la même priorité. Parmi les algorithmes d’ordonnancement à priorité fixe, citons RM (Rate Monotonic) (Liu et Layland 1973) et DM (Deadline Monotonic) (Audsley 1990).
Ordonnancement à dynamicité restreinte Ces algorithmes d’ordonnancement sont à priorité fixe au niveau des travaux. Ils permettent, lors de l’exécution des tâches, d’avoir des priorités différentes entre les différents travaux d’une tâche. Pendant la vie d’un travail donné, sa priorité reste cependant identique. L’algorithme d’ordonnancement EDF (Earliest Deadline First) (Dertouzos 1974) fait  partie de cette catégorie.
Ordonnancement à priorités dynamiques Les algorithmes à priorité dynamique ne mettent aucune restriction sur les priorités assignées aux travaux. À chaque instant, la priorité d’un travail est recalculée. L’algorithme LLF (Least Laxity First) (Mok et Dertouzos 1978) est un exemple d’ordonnancement à priorités dynamiques.

Protocoles bloquants

   Ces protocoles reposent sur la technique des verrous. Les protocoles que nous présentons ici supposent une réentrance binaire, autrement dit, une seule tâche peut accéder en même temps à une ressource partagée. Les sections de code en exclusion mutuelle sont qualifiées de sections critiques.
PIP (Priority Inheritance Protocol) Ce protocole a été proposé (Sha et al. 1990) pour résoudre le problème d’interblocage entre tâches ainsi que le phénomène d’inversion de priorité. Le principe consiste à rehausser la priorité de la tâche obtenant la ressource critique, à celle de la tâche qu’elle bloque en attente de la même ressource. Il s’agit donc d’attribuer à la tâche τi entrant en section critique, une priorité Pr(τi) = Max{Pr(τ1), Pr(τ2), Pr(τ3), …, Pr(τn)}, sous condition que les tâches τ1, τ2, τ3, …τn aient une priorité supérieure à celle de τi et attendent toutes la ressource détenue par τi . La priorité de τi est rétablie au moment de la libération de la ressource qu’elle a occupée. De cette manière, aucune tâche de priorité inférieure ne pourra préempter la tâche τi durant son exécution en section critique.
PCP (Priority Ceiling Protocol) Ce protocole (Sha et al. 1990) prévient les situations d’interblocages. Il définit une nouvelle notion : la priorité plafond (PP) d’une ressource, qui est une valeur maximum des priorités des tâches qui l’utilisent, en posant la condition suivante : une tâche τi ne peut entrer en section critique que si la priorité de la ressource qu’elle demande, est strictement supérieure à la priorité plafond des ressources en cours d’utilisation (hormis celles de τi). En section critique, la tâche devra hériter de la priorité de la tâche la plus prioritaire qu’elle bloque. Ceci sous-entend que le protocole à priorité plafond résout également le problème d’inversion de priorité. De plus, contrairement au protocole PIP, le temps de blocage est réduit à une seule section critique. Des versions multiprocesseurs (M-PCP) et distribuées (D-PCP) sont proposées par Rajkumar (1991). Pour le M-PCP, l’auteur a considéré une plateforme multiprocesseur avec un ordonnancement à priorités statiques et partitionné. L’adaptation du M-PCP à l’ordonnancement P-EDF est quant à lui proposé par López et al. (2004).
SRP (Stack Resources Protocol) Tout comme le protocole PCP, SRP se base également sur la notion de priorité plafond (Baker 1991). Cependant, à la différence du PCP, le protocole SRP satisfait immédiatement chaque requête du travail ji demandant une ressource. Sous SRP, le blocage est effectué uniquement lors du réveil du travail ji, et son exécution n’est entamée que lorsque sa priorité devient plus grande que la priorité plafond du système. Ainsi, les travaux sont bloqués au plus une seule fois, et il n’y a aucun besoin d’utiliser l’héritage de priorité. La version multiprocesseur M-SRP pour la politique P-EDF a été proposée par López et al. (2004) et Gai et al. (2003). Ces derniers auteurs ont discuté son implémentation étant donnée la nature expérimentale de leur travail. Les résultats de ce travail ont montré que M-SRP offre de meilleures performances que M-PCP.
FMLP (Flexible Multiprocessor Locking Protocol) Ce protocole a été spécialement conçu pour les systèmes multiprocesseurs (Block et al. 2007). Il prend en effet en compte les approches partitionnée et globale. L’unité de blocage dans FMLP est un groupe de ressources. Chaque groupe contient soit seulement de longues ressources ou seulement de courtes ressources, et chacun de ces groupes est protégé par un verrou qui est soit un spinlock (pour les courtes ressources), soit un sémaphore (pour les longues ressources). Deux ressources R1 et R2 sont du même groupe si et seulement s’il existe un travail ji qui lance une requête pour détenir R1 et R2, et que ces deux ressources sont toutes les deux de même type (longues/courtes). Le protocole FMLP permet ainsi l’utilisation des ressources d’une manière imbriquée. En outre, il a été démontré dans (Block et al. 2007) que FMLP évite l’interblocage et offre de meilleures performances que le protocole
M-SRP (Gai et al. 2003). Stratégie par Supertâches Moir et Ramamurthy (1999) ont observé que la migration sous Pfair peut poser problème lors de la gestion de ressources partagées. En effet, une tâche qui communique par exemple avec un périphérique externe pourrait avoir besoin de s’exécuter sur un processeur particulier et ne pas migrer. Pour supporter la non-migration des tâches, les auteurs ont proposé l’utilisation de la notion de supertâche (supertasking). Dans leur approche, une supertâche Sk remplace l’ensemble des tâches qui sont affectées au processeur k ∈ M et partageant les mêmes ressources. Avec ce concept,pour τi 6∈ Sk , le pire temps requis pour obtenir la ressource détenue par le groupe Sk est Maxτj∈Sτ {Bj} (au lieu de ∑τj∈Sτ Bj), où Bj est le temps deblocage causé par la tâche τj.Selon Pfair, chaque surpertâche est dotée d’un ratio d’utilisation du processeur défini comme suit :u(Sk) = ∑ τ∈Sk u k (τ) (1.4) Les tâches partageant les mêmes ressources sont donc groupées puis ordonnancées comme une seule tâche. Le principal problème qui apparaît lors de l’ordonnancement avec cette approche est celui de la faisabilité du système. Deux approches sont alors données dans la littérature. La première consiste à gérer les supertâches comme étant des classes spéciales lors de l’utilisation d’une approche globale. Cependant, la réservation du traitement particulier aux supertâches réduit considérablement les performances du système. Une approche alternative a été proposée dans Holman et Anderson (2001) pour le Pfair. Cette approche consiste à affecter un ratio d’utilisation du processeur suffisamment grand à une supertâche de manière à ce qu’elle ne manque pas son échéance. Au sein du groupe d’une supertâche, une autre politique d’ordonnancement (que le Pfair) peut être appliquée, et on parle alors d’un ordonnancement hiérarchique. Pour les tâches appartenant au même groupe, l’algorithme EDF est recommandé pour son optimalité à ordonnancer des sous-ensembles de tâches.

Lock-free

   Cette stratégie de gestion des ressources, contrairement au wait-free, est plutôt destinée à établir des contraintes de temps de type souples lors de l’accès aux sections critiques. En effet, le lock-free garantit qu’à chaque instant, l’exécution d’au moins une tâche peut progresser. Autrement dit, il existe des tâches sous cette stratégie qui peuvent manquer leurs échéances faute d’un grand nombre de réitèrements non-bornés lors des conflits d’accès aux sections critiques. Le principal défi auquel est confrontée cette stratégie est la transformation du code séquentiel en lock-free. Cette transformation dite construction universelle (Lamport 1977) représente une classe d’implémentation du lockfree. Il s’agit en général de prendre en compte de nombreuses constructions de structures de données, afin de pouvoir automatiser leur transformation en lock-free par des compilateurs ou environnements dédiés (Turek et al. 1992, Barnes 1993). Un autre défi consiste à trouver des stratégies d’ordonnancement afin de borner le nombre d’interférences entre travaux. Dans (Anderson et al. 1997c) l’interférence concerne un travail manipulant un objet en lock-free et préempté par un autre travail de plus haute priorité mais que ce dernier ne manipulera pas. Ces mêmes auteurs posent une condition simple quant au nombre d’itérations nécessaires pour l’accès aux objets lock-free en le considérant constant. Ceci a permis de déduire des tests d’ordonnançabilité pour les politiques DM et EDF en incluant ces temps de rejoues. Cependant, les conditions posées sont pessimistes, et de plus, elles ne sont applicables que pour des environnements monoprocesseurs. Il existe peu de travaux utilisant à la fois le lock-free comme synchronisation tout en considérant l’environnement multiprocesseur. Dans Holman et Anderson (2006) les auteurs proposent la prise en compte du lock-free dans un environnement multiprocesseur pour l’algorithme d’ordonnancement Pfair pouvant être cependant généralisé, à tout algorithme d’ordonnancement basé sur des quantums de temps. Les auteurs utilisent une structure de données simple avec insertion dans une file. L’accès à cette file utilise une primitive de type CAS. Le temps d’accès est d’abord borné en tenant compte du nombre de tentatives pour accéder à un objet dans la file. A partir de cette borne, la pire durée d’accès à l’objet est ensuite déduite. Cette borne est réduite par la suite en utilisant le concept de supertâche. Sur des architectures multiprocesseurs, la synchronisation par lockfree est préférable pour des structures de données simples comme les files, les piles, les buffers et les listes. Cependant, pour des structures de données plus complexes, les protocoles bloquants offrent de meilleures performances. Cette affirmation est répandue dans la littérature puis a récemment été étayée expérimentalement sur une plateforme réelle multiprocesseur par Brandenburg et al. (2008).

Table des matières

Liste des figures
Liste des tableaux
Introduction
I État de l’art 
1 Les systèmes temps réel multiprocesseur 
1.1 Introduction aux systèmes temps réel
1.1.1 Classification
1.1.2 Les tâches temps réel
1.1.3 Taxonomie des plateformes multiprocesseurs
1.2 Ordonnancement temps réel multiprocesseur
1.2.1 Définitions
1.2.2 Types d’ordonnancements
1.2.3 Types d’approches
1.2.4 Types de migrations
1.2.5 Classification des tests d’ordonnançabilité
1.2.6 Algorithmes d’ordonnancement
1.3 synchronisation en temps réel multiprocesseur
1.3.1 Protocoles bloquants
1.3.2 Protocoles non-bloquants
Conclusion
2 Les systèmes transactionnels 
2.1 Introduction aux systèmes transactionnels
2.1.1 Les transactions
2.1.2 Les contrôleurs de concurrence
2.2 Le transactionnel temps réel
2.2.1 Les protocoles pessimistes
2.2.2 Les protocoles optimistes
Conclusion
3 Les Mémoires Transactionnelles 
3.1 Introduction aux mémoires transactionnelles
3.2 Taxonomie des mémoires transactionnelles
3.2.1 Transactions imbriquées
3.2.2 Granularité des transactions
3.2.3 Faible et forte isolation
3.3 Gestion des conflits
3.3.1 Gestionnaire de contention
3.3.2 Le Helping
3.4 Implémentations des mémoires transactionnelles
3.4.1 Implémentations matérielles (HTM)
3.4.2 Implémentations logicielles (STM)
3.4.3 Implémentations hybrides (HyTM)
3.4.4 Implémentations temps réel
Conclusion
II STM pour les systèmes temps réel soft 
4 Adéquation des STMs existantes aux systèmes temps réel soft 
4.1 Introduction
4.2 Contexte d’évaluation
4.2.1 Plateforme matérielle
4.2.2 Configuration logicielle
4.2.3 Métriques étudiées
4.3 Évaluations expérimentales
4.3.1 Influence de l’OS
4.3.2 Influence des politiques d’ordonnancement
4.3.3 Influence de l’allocateur mémoire
Conclusion
5 Conception d’une STM temps réel (RT-STM) 
5.1 Motivations et objectifs
5.2 La RT-STM
5.2.1 Le modèle transactionnel
5.2.2 La gestion de concurrence
5.2.3 La synchronisation
5.2.4 Règles de résolution de conflits
5.3 Implémentation et évaluation
5.3.1 Implémentation au sein de la OSTM
5.3.2 Évaluation de la RT-STM
Conclusion
6 RT-STM : Protocoles de gestion de concurrence 
6.1 Motivations et objectifs
6.2 Formulation du problème
6.3 Modèle du système
6.4 Protocoles pour la RT-STM
6.4.1 Structures de données
6.4.2 Le protocole mono-écrivain (1W)
6.4.3 Le protocole multi-écrivain (MW)
6.5 Évaluation des protocoles
6.5.1 Contexte d’évaluation
6.5.2 La bande passante du système
6.5.3 La progression globale
6.5.4 Le ratio de temps de rejoue
Conclusion
III Extension aux contraintes firm 
7 RT-STM en environnement firm 
7.1 Motivations et objectif
7.2 Modèles et algorithmes existants
7.2.1 Le modèle de tâche (m,k)-firm
7.2.2 Le modèle transactionnel (mk)-firm
7.3 Modélisation et analyse de la RT-STM firm
7.3.1 Nouveau modèle sous contraintes m-firm
7.3.2 Nouveau modèle sous contraintes de QoS
7.3.3 Analyse du WCET de transactions m-firm
7.4 Extension et évaluation de la RT-STM
7.4.1 Implémentation du modèle m-firm
7.4.2 Évaluation empirique du modèle m-firm
7.4.3 Implémentation de la QoS
Conclusion
Conclusion générale
Bibliographie

Télécharger le rapport complet