Isolation des systèmes temps réel

Les systèmes à criticité mixte (Mixted Criticality Systems en anglais ou MCS) désigne des systèmes temps réel sur lesquels des applications avec des niveaux de criticité différents cohabitent et peuvent échanger des ressources sans qu'il soit nécessaire de prévoir les cas particuliers[1]. À chaque processus est associé un niveau de criticité qui correspond à un palier d'importance prédéfini dans le système. Un système à criticité mixte a au moins deux niveaux de criticité distincts. Ces groupes de criticité assurent un niveau de confiance hétérogène permettant d'éviter la propagation des erreurs. À chaque processus est attribué un niveau de criticité qui correspond un niveau de confiance que ce processus se doit de respecter : plus le niveau de criticité de ce processus sera élevé, plus cela signifie que la confiance que l'on attribue à ce processus est forte et plus il doit être isolé des autres processus et moins il doit avoir de chance d'être corrompu par les erreurs des autres processus. Un processus dans un système à criticité mixte se distingue des autres systèmes par des paramètres spécifiques tels que le temps d'exécution pire-cas (Worst Case Execution Time en anglais ou WCET), une deadline, une période et un niveau de criticité. Le WCET, la période et la deadline dépendent du niveau de criticité de la tâche. Un niveau de criticité élevé entraîne une majoration importante du WCET pour une application[2].

Les systèmes à criticité mixte doivent apporter un certain nombre de garanties quant à la capacité qu'ils ont à exécuter en harmonie sans que les tâches critiques ne dépassent leur échéance. D'après Burns et Davis, cela implique de trouver un compromis entre le partitionnement des ressources pour assurer un certain niveau de sécurité des tâches et le partage des ressources de manière efficace pour assurer la sûreté du système. Une bonne gestion des ressources implique également d'apporter au système des solutions d'accès déterministe aux ressources.

La problématique principale des systèmes à criticité mixte réside dans le bon équilibre entre partitionnement et partage des ressources. La gestion des ressources partagées est cruciale pour assurer des performances suffisantes pour accueillir des tâches temps réel. L'allocation de ces ressources est notamment un des points critiques à aborder dans un système temps réel. Par exemple, le temps d'accès à la mémoire partagée peut varier selon que la page à laquelle la tâche souhaite accéder n'a pas été utilisée depuis longtemps par le processus propriétaire de la page[3]. Le partitionnement des ressources est une problématique importante dans les systèmes à criticité mixte. La répartition du temps d'utilisation du processeur, par exemple, peut permettre de réduire l'impact d'une attaque par déni de service (Denial of Service en anglais) visant à utiliser la totalité du temps de calcul du processeur ou encore en ayant une utilisation intensive des ressources partagées[4].

Pour respecter ces garanties, les systèmes à criticité mixte se doivent de pouvoir accéder aux ressources sans qu'une tâche ne puisse interférer avec le temps d'exécution des autres tâches. Le temps d'exécution d'une tâche étant intimement lié au délai d'accès aux ressources comme la mémoire ou le cache, il est important de disposer de mécanisme permettant de rendre déterministe le délai lié d'accès à une ressource[5].

Un processus est isolé temporellement s'il s'exécute indépendamment de la charge de travail des autres processus ; son temps d'exécution n'est pas influencé par l'exécution d'autres processus sur le système[6] - [7].

L'exécution de fonctionnalités critiques doit être protégée des interférences générées par des processus non critiques. Une première approche consiste à partager le temps du processeur entre les tâches de manière la plus proche de l'optimale possible. Le calcul du worst-case execution time (WCET) est une borne haute utilisée pour répartir le temps de calcul du processeur entre les tâches. Il s'agit d'une garantie de temps de réponse pour les applications en cours d'exécution[8]. Le modèle courant utilisé dans les systèmes à criticité mixte pour assurer l'isolation temporelle est basé sur ces caractéristiques : les tâches T_i sont définies par une période défini par l'intervalle de temps qui sépare deux activations de la tâche, une limite D_i, le temps d'exécution C_i et un niveau de criticité L_i[9].

Response Time Analysis (RTA) est une méthode consistant à évaluer le temps de réponse pour déterminer le temps d'exécution d'une tâche et ainsi prévenir le dépassement de temps alloué pour ce processus. L'intérêt est d'approcher la valeur optimale d'utilisation des ressources. Dans l'article écrit par Baruah une première possibilité (pour l'implémentation de RTA) est de ranger les tâches par niveau de criticité puis d'utiliser l'algorithme de Audsley sur chaque niveau de criticité pour assigner les priorités aux tâches en les ordonnant de la plus basse à la plus haute. Le test d'ordonnancement des tâches se fait en parcourant par ordre croissant de priorité le niveau de criticité basse puis le niveau de criticité haute. L'approche de Vestal prend en compte deux types de criticité : haute et basse. Les tâches peuvent être interrompues pendant leur traitement quel que soit leur niveau de criticité et toutes les tâches doivent être exécutées comme si elles avaient le plus haut niveau de criticité. Elle se distingue de la méthode précédente dans l'article de Baruah parce qu'elle ne définit pas les priorités par deadline monotonic. En effet Vestal a démontré que le "deadline monotonic prority assignment" n'était pas optimal pour les tâches qui ont plus d'un WCET (Worst Case Execution Time)[10] - [11].

D'autres méthodes existent, comme le Slack Scheduling qui consiste à utiliser le temps non utilisé par les tâches critiques pour les tâches non critiques[12]. Least Slack Time First (LST) est une implémentation pour laquelle un slack time court privilégie une tâche en augmentant sa priorité.

${\displaystyle \Delta {u}=\sum _{i\mathop {=} 1}^{n}{\frac {e_{i}}{D_{i}}}\leqslant 1}$

Cette équation mesure le taux d'utilisation du processeur.

D_i représente la limite de temps relative pour cette tâche, e_i le temps d'exécution alloué à la tâche pour chaque période. u représente la somme du rapport entre e_i et D_i pour chaque tâche, il s'agit d'un coefficient.

Les tâches suivantes devraient s'exécuter de manière optimale : sans que le processeur soit dans une situation où il n'ait rien à exécuter. On voit que ${\displaystyle \Delta {u}=1}$, il n'y a pas de temps mort[13].

Il est également possible de faire coexister des applications critiques et non critiques en transformant la période des tâches (Period Transformation). Le principe est de diviser les tâches critiques, ainsi la période et le temps d'exécution de ces sous tâches est inférieure ce qui augmente leur priorité d'exécution par rapport aux tâches non critiques. La contrepartie de cette solution est l'accroissement du temps d'exécution d'ordonnancement dû à l'augmentation du nombre de tâches[14].

La programmation orientée objet offre la possibilité d'attribuer une contrainte à une suite d'instructions. Si l'une des instructions ne se respecte pas la contrainte, un événement, aussi appelé exception, vient interrompre l'exécution normale du programme. Appliquée aux systèmes temps réel, une exception générée après un temps donné est un moyen efficace d'isoler temporellement les processus en les empêchant de dépasser le temps qui leur a été attribué[15]. Les méthodes utilisant des délais est courant dans les systèmes tolérants aux pannes : l'expiration de ce délai met en évidence une anomalie dans l'exécution du processus. Une fois l'anomalie détectée, il devient possible de la gérer par l'arrêt du processus, par exemple[16] - [17].

Dans le contexte d'une plateforme multi-cœurs d'autres pistes ont été abordées comme l'exécution exclusive des tâches critiques sur les cœurs disponibles pendant un intervalle de temps avant que les applications non critiques puissent prendre la main[18]. AMC (Analyzable Memory Controller) s'appuie sur une segmentation en deux groupes d'applications distinctes : critiques et non critiques. En l'absence de nécessité d'exécuter des tâches critiques alors les tâches non critiques peuvent être prises en considération, à l'inverse se sont toujours les tâches critiques qui ont la main[19].

Le cache partagé étant une des ressources les plus sollicitées, le temps d'accès à celle-ci peut être très variable même lorsque chaque cœur possède sa partition dédiée de cache. Cette ressource pouvant faire varier le temps d'exécution pire-cas d'une tâche (Worst Case Execution Time en anglais ou WCET), rendre plus prévisible le temps d'accès à celle-ci permettrait donc d'améliorer le temps d'exécution pire-cas d'une tâche[20] - [21].

Les appels mémoire intensifs par les applications sur des architectures multi-cœurs peuvent entraîner une augmentation linéaire du temps pour le temps d'exécution pire-cas (Worst Case Execution Time en anglais ou WCET) en fonction du nombre de cœurs gérés par le système. Pendant une période où les transactions mémoire sont importantes il est possible d'adopter un ordonnancement dit "memory-centric". L'implémentation est effectuée par l'isolation dans un premier temps : Time Division Multiple Access (TDMA) qui consiste à partager le temps d'accès avec une marge importante (coarse-grained) pour permettre en même temps l'exécution et les accès mémoire et pour diminuer le temps de réponse des applications. Dans un second temps l'ordonnancement par cœur privilégie l'accès aux tâches qui effectuent des opérations mémoires intensives. L'avantage lié à l'utilisation de l'isolation temporelle TDMA est de rendre l'ordonnancement prédictible. L'isolation au niveau de chaque cœur peut être vu comme s'il faisait partie d'une architecture "single-core"[22].

Les systèmes temps réel ne disposent pas de mécanismes de protections en général. Les besoins de l'industrie évoluent, il devient difficile de concilier sécurité et performance en voulant intégrer de plus en plus de fonctionnalités sur des systèmes non protégés. L'utilisation d'un système d'exploitation intégrant ces protections n'est pas envisageable dans l'état pour une utilisation temps réel du fait de la difficulté de prédiction du temps de réponse. Il est possible de séparer les fonctionnalités temps réel des autres en les exécutant sur des processeurs dédiés mais cela entraîne une hausse des coûts d'intégration. Une solution proposée est d'utiliser un système avec ordonnancement complètement préemptif : avec la possibilité de changer de tâche pour un processeur à n'importe quel moment (même pendant l'exécution d'une tâche en cours sur ce processeur). Il est également possible d'interrompre l'exécution du code du kernel pendant l'ordonnancement. Seules certaines sections critiques ne peuvent être interrompues en général pour modifier des structures de données. Cette implémentation a l'avantage de permettre d'obtenir de très bon résultats au niveau de la latence pendant les interruptions. Cependant la difficulté réside dans l'implémentation d'un tel système où les interruptions peuvent produire des résultats inattendus ou des crashs si le système présente des défauts. Il faut également prendre en considération la difficulté à analyser le comportement dans un contexte concurrent et la reproduction des bugs[23].

L'ordonnancement hiérarchique est très utilisé dans les systèmes temps réel. Un hyperviseur attribue une part du temps de calcul à chaque machine virtuelle. Cette ordonnanceur est aussi appelé ordonnanceur global. À l'intérieur de chaque machine virtuelle, un ordonnanceur local gère les tâches[24]. L'utilisation de ce type d'ordonnancement provoque néanmoins une perte conséquente de performance provenant de l'utilisation d'un hyperviseur[25]. Cette méthode permet d'assurer l'isolation temporelle des applications car le temps d'utilisation du processeur est décidé par l'ordonnanceur de l'hyperviseur qui divise la totalité du temps d'utilisation du processeur entre les machines virtuelles[26].

Sur des architectures matérielles dont les composants se basent sur un temps aléatoire (time-randomised), on calcule le pWCET (Probabilistic Worst Case Execution Time). On peut l'obtenir en définissant une fonction qui dérive du taux d'échec maximum associé à un niveau de criticité. La distribution couverte par le pWCET définit des estimations du WCET pour les différents niveaux de criticité d'une même tâche[27].

Schéma de mémoire partagée

Quand on aborde le transfert de données entre applications de niveau de criticité différents, on est confronté à l'incertitude quant à la fiabilité des données provenant d'une tâche non critique à destination d'une tâche critique, à moins que le composant critique dispose d'un mécanisme lui permettant de détecter les incohérences éventuelles. Dans le cas d'un transfert de données d'une tâche critique vers une tâche non critique, il faut également prévoir un blocage ou retard éventuel dû à l'activité du processus non critique (utilisation d'un sémaphore…)[28].

Dans un système multicœur, les ressources partagées telles que le cache peuvent représenter un goulot d'étranglement. Certaines tâches peuvent influer sur l'exécution des autres tâches en accédant de manière répétée aux ressources partagées ce qui empêcherait les autres tâches d'y accéder efficacement sauf si un système d'isolation entre les cœurs est mis en place[29].

Il est possible d'éviter les situations de blocage en se servant du concept de sections critiques. L'objectif d'une section critique est de limiter l'accès à une ressource. Cette limitation peut prendre plusieurs formes, il est possible de passer par une limitation de l'accès aux ressources de certains cœurs pour une période donnée lorsqu'une application critique a besoin d'accéder de manière intensive à des ressources[30] - [31]. Il est également possible de gérer cette section critique comme les bases de données gèrent les transactions, on appelle cette méthode de gestion de sections critiques : mémoire transactionnelle. Pour initialiser une transaction, il faut préciser une portion de mémoire sur laquelle on souhaite réaliser les instructions de la section critique ainsi qu'une limite de temps pour réaliser la transaction. Une fois qu'une transaction est initialisée, des lectures et écritures peuvent être réalisés sur la mémoire. À la fin de la section critique, il sera alors possible d'appliquer les changements qui auront été effectué pendant la transaction. Si la transaction a dépassé le temps qui a été précisé lors de l'initialisation, celle-ci est annulé[32].

Prévenir des situations où la latence entre le moment où un cœur demande l'accès à une ressource et le moment où il y accède effectivement est possible. Des systèmes de gestion de banques de ressources ont été proposés à cet égard pour fluidifier l'accès à la DRAM (Dynamic Random Access Memory) dans les systèmes multicœurs. Une banque correspond à un ensemble de ressources que l'utilisateur définit. Cela permet à l'utilisateur d'attribuer des ressources auxquelles un cœur aura accès et évitera ainsi que tous les cœurs du processeurs essaient d'accéder en même temps à la même ressource[33] - [1].

Les priorités fixes par Response Time Analysis (RTA) peuvent être utilisées pour compiler des ordonnancements. Ces computed schedules sont établis par niveaux de criticité à l'aide d'une table (Time Triggered Table) et permettent de déterminer les sauts effectués entre les niveaux de criticité ce qui est utile dans le cas de ressources partagées comme la mémoire pour éviter l'incertitude[34].

Cette méthode consiste à allouer des pages de mémoire partagées de manière statique. Chaque tâche temps réel spécifie le nombre de pages dont elle a besoin. Une fois réservées, ces pages ne seront utilisables que par la tâche à laquelle elles sont attribuées et ne peuvent pas être remplacées par les pages d'une autre tâche. Cela permet d'accéder aux pages de mémoire avec un temps d'accès constant, sans que les autres applications puissent influer sur ce temps, ce qui en fait une méthode efficace pour rendre efficace pour rendre déterministe l'accès à la mémoire partagée et isoler temporellement les tâches entre elles[35].

Pour assurer la sécurité d'un système, la propriété la plus importante à respecter est l'isolation mémoire[36]. L'isolation mémoire (ou isolation spatiale) consiste à contrôler l'accès aux ressources. On entend par ressources : mémoire, buffers, i/o ports, registres[37]. Concilier isolation mémoire et performances sur un système temps réel est un véritable défi. On peut utiliser la MMU, ou Memory Management Unit, un composant matériel destiné à gérer dynamiquement la mémoire à travers l'allocation de plages (pages) d'adresses physiques mappées sur des plages d'adresses virtuelles. Cette solution de gestion de l'isolation est largement utilisée mais elle n'est pas adaptée aux systèmes temps réel pour lesquels la perte de performances est perceptible[38]. Ainsi, certains systèmes temps réel sont dépourvus de mécanismes de protection mémoire pour réduire le temps d'exécution[39]. Le système devient alors dépendant des applications exécutées ce qui entraîne des problèmes de sécurité[40] - [38]. L'isolation mémoire peut se matérialiser de différentes manières, il y a plusieurs niveaux de granularité. On peut décider d'isoler seulement le système des applications ou bien d'aller plus loin en isolant également les applications entre elles[41].

Dans certains systèmes temps réel, on introduit la notion de mémoire partagée distribuée (Distributed Shared Memory en anglais ou DSM) dont l'optique est de faciliter le développement des applications distribuées en partageant les variables entre les nœuds[42]. Cela évite de devoir réécrire une partie de l'application pour partager les données à travers l'envoi de messages. La plupart des implémentations de DSM sont basées sur les pages mémoires ce qui rend le temps de réponse difficile à prévoir dans un système distribué. De plus, cette implémentation est basée sur la MMU qui est absente pour certains microcontrôleurs. Il est possible d'optimiser le temps d'exécution d'une solution d'isolation mémoire à base de MMU en utilisant des niveaux de tailles de pages différents et en passant les niveaux de tables de pages intermédiaires qui ne sont plus utilisés[43]. Pour unifier les accès mémoire entre matériel hétérogène une solution à base d'espaces de données appelée Tailor Made Dataspaces (TSS) propose une représentation unique des ressources pour simplifier les méthodes d'accès qui sont mappées en mémoire (mapped I/O methods)[44].

Schéma d'hyperviseur

L'hypervision permet d'assurer l'isolation et apporte un système de privilèges. Cependant la complexité et la taille du code de ces systèmes est accrue. D'autres approches pour l'hypervision existent comme TrustZone Based Real-Time Kernel Protection (TZ-RKP), il s'agit de l'implémentation d'un environnement isolé et dédié aux services de sécurité du système. L'avantage de cette solution est de permettre l'isolation de ces outils de sécurité par rapport au kernel[45]. L'hypervision permet également l'isolation des machines virtuelles et protège des comportements malveillants des applications[46].

L'isolation logicielle (Software Fault Isolation en anglais ou SFI) est une méthode logicielle qui permet de réduire les dégâts que pourrait causer un bug sur les autres applications en cours d'exécution sur le système. Cela consiste à partitionner l'espace mémoire global du système en plusieurs domaines. Un domaine correspond, par exemple, à une application. L'utilisateur doit définir une safe stack généralement située à la fin de l'espace d'adressage global qui est un domaine de confiance[47] : seul ce domaine a accès aux autres domaines. Les instructions machines des binaires sont réécrites puis ces instructions sandboxées sont vérifiées par le domaine de confiance au moment de l'exécution. C'est ce système qui permet de détecter si une fonction tente d'écrire dans un domaine auquel elle n'a pas le droit d'accéder. À défaut de prévenir les bugs dans les applications, cela permet d'éviter que ce bug n'affecte l'ensemble de l'espace mémoire[48] - [4]. D'autres types d'isolations logicielles sont courantes dans les systèmes temps réel. Partitionner le cache partagé en donnant une portion de ce cache à chaque processeur est une technique communément appliquée dans les systèmes temps réel qui permet d'isoler les cœurs entre eux[49].

La MMU, ou Memory Management Unit, est utilisée dans de nombreux systèmes informatiques et dans les systèmes embarqués haut de gamme comme ceux utilisés en avionique. Cependant, pour les systèmes embarqués utilisés par le secteur de l'automobile, d'autres contrôleurs appelés MCU (Micro Control Units) sont utilisés et ne disposent pas de hautes performances et de fonctionnalités avancées. Le MCU dispose d'un MPU (Memory Protection Unit), le principe est le découpage de la mémoire en régions. Un système temps réel disposant d'un MPU doit implémenter des fonctionnalités permettant dé gérer la mémoire statique pour éviter aux développeurs de gérer le stockage du code et des données dans la mémoire[50].

• Narjes Jomaa, David Nowak, Gilles Grimaud et Julien Iguchi-Cartigny, « Formal Proof of Dynamic Memory Isolation Based on MMU », Theoretical Aspects of Software Engineering (TASE),‎ mars 2015, p. 297-300 (DOI 10.1109/TASE.2016.28)
  Vingt-sixièmes Journées Francophones des Langages Applicatifs (JFLA 2015)
• (en) Philip Derrin, Kevin Elphinstone, Gerwin Klein et David Cock, « Running the Manual: An Approach to High-Assurance Microkernel Development », ACM,‎ septembre 2006, p. 60-71 (ISBN 1-59593-489-8, DOI 10.1145/1159842.1159850)
  Haskell '06 Proceedings of the 2006 ACM SIGPLAN workshop on Haskell
• (en) Kevin Elphinstone, Gerwin Klein, Philip Derrin et Timothy Roscoe, « Towards a practical, verified kernel », USENIX,‎ mai 2007
  HOTOS'07 Proceedings of the 11th USENIX workshop on Hot topics in operating systems
• (en) Liang Gu, Alexander Vaynberg, Bryan Ford, Zhong Shao et David Costanzo, « CertiKOS: a certified kernel for secure cloud computing », ACM,‎ juillet 2011 (ISBN 978-1-4503-1179-3, DOI 10.1145/2103799.2103803)
  APSys '11 Proceedings of the Second Asia-Pacific Workshop on Systems
• (en) Heekwon Kang, Dongwoo Kang et Jongmoo Choi, « Cooperative kernel: online memory test platform using inter-kernel context switch and memory isolation », IEEE,‎ mars 2014, p. 1517-1522 (ISBN 9781450324694, DOI 10.1145/2554850.2554972)
  Proceedings of the 29th Annual ACM Symposium on applied computing
• (en) G. Yao, R. Pellizzoni, S. Bak, E. Betti et M. Caccamo, « Memory-centric scheduling for multicore hard real-time systems », Springer US, vol. 48,‎ novembre 2012, p. 681-715 (ISSN 0922-6443, DOI 10.1007/s11241-012-9158-9)
• (en) Silviu S. Craciunas et Christoph M. Kirsch, « The Power of Isolation », IEEE/ACM,‎ décembre 2012, p. 375 - 382 (ISBN 978-1-4673-5165-2, DOI 10.1109/ICCSE.2012.59)
  International Conference on Computational Science and Engineering

• Système d'exploitation temps réel
• Worst Case Execution Time (Temps d'exécution pire-cas)