Analysis and scheduling of hierarchical virtualized systems composed of hard real-time applications
Analyse et ordonnancement d’un système hiérarchique virtualisé composé d’applications temps réel strictes
Résumé
In the context of smart cities, the concept of autonomous vehicle is gaining importance in the objective of carrying out surveillance missions for the protection of infrastructures. In this context, unmanned aerial vehicles (drones) embed several applications (control command, communication and video) of different criticality with often heterogeneous associated certification constraints. The instrumentation and control application with the highest level of criticality must be certified at the highest level of requirement. When multiple applications of different criticality run on the same hardware platform, the most critical application contagiously imposes certification on the less critical applications to the same level of requirement as that of the most critical application. This is not always possible given the complexity of the applications and can lead to a certification cost which can be significant. One solution to this problem is to use a virtualization system based on a certified hypervisor, providing spatial and temporal isolation of applications. Each application then runs in a dedicated virtual machine (VM). The activation of VMs is managed by the hypervisor in charge of this isolation.From a scheduling point of view, this forms a two-level hierarchical system. VMs are scheduled by the hypervisor at the first level, the tasks of each VM are scheduled at the second level by a specific scheduling algorithm. We consider in this thesis a fixed priority scheduling at the second level.Our work fits into the context of the CEOS surveillance drone project. In this project, the goal is to create an autonomous surveillance drone for non-military purposes. This is a FUI project with various partners such as INRIA, Enedis, EDF, Sysgo, Alerion, Thalès, Caen airport. This drone is defined for three use cases: (i) monitoring power lines in the EDF network, (ii) monitoring water pipes in the mountains for ENEDIS and (iii) monitoring fences in the Caen airport.For the CEOS project, a type 1 hypervisor developed by the Sysgo company (PikeOs) was chosen. PikeOs is certified DAL-A for various avionics standards such as ARINC 653 and MILS. It is thanks to its certifications that this hypervisor was chosen. One of its peculiarities is that it is possible to master the level 1 scheduling of VMs. For level 1, the scheduling of virtual machines using a scheduling table must be determined beforehand, no algorithm is imposed. Regarding the tasks executed by the VMs, their scheduling is determined by the real-time operating system associated with the virtual machine. It is also possible to introduce tasks directly into PikeOS which will then be scheduled by a fixed priority scheduling.The freedom to choose an algorithm for first-level scheduling involves several questions: How to schedule VMs so that all tasks in their VM meet their deadlines? Under the conditions of predetermined scheduling for virtual machines, which scheduling would give a good success ratio for the scheduling of tasks ?
Dans le contexte des villes intelligentes, le concept de véhicule autonome prend de l’importance dans l’objectif de mener à bien de missions de surveillance pour la protection des infrastructures. Dans ce contexte, les véhicules aériens sans pilote (drones) embarquent plusieurs applications (contrôle commande, communication et vidéo) de criticité différente avec des contraintes de certification associées souvent hétérogènes. L'application de contrôle-commande ayant le niveau de criticité le plus élevé doit être certifiée au plus haut niveau d’exigence. Lorsque plusieurs applications de criticité différente s’exécutent sur la même plate-forme matérielle, l’application la plus critique impose par contagion aux applications les moins critiques une certification du même niveau d’exigence que celui de l’application la plus critique. Ce qui n’est pas toujours possible compte tenu de la complexité des applications et peut conduire à un coût de certification qui peut être important. Une solution à ce problème consiste à utiliser un système de virtualisation basé sur un hyperviseur certifié, assurant une isolation spatiale et temporelle des applications. Chaque application s’exécute alors dans une machine virtuelle (VM) dédiée. L'activation des VMs est gérée par l'hyperviseur en charge de cette isolation.D’un point de vue ordonnancement, cela forme un système hiérarchique à deux niveaux. Les VMs sont ordonnancées par l'hyperviseur au premier niveau, les tâches de chaque VM sont ordonnancées au second niveau par un algorithme d’ordonnancement spécifique. Nous considérons dans cette thèse un ordonnancement à priorité fixe au second niveau.Nos travaux s’intègrent dans le contexte du projet de drone de surveillance CEOS. Dans ce projet, le but est de créer un drone autonome de surveillance à but non militaire. Il s’agit d’un projet FUI avec différents partenaires tels que l’INRIA, Enedis, EDF, Sysgo, Alerion, Thalès, l’aéroport de Caen. Ce drone est défini pour trois cas d’usage : (i) la surveillance des lignes électriques dans le réseau EDF, (ii) la surveillance de conduites d’eau dans les montagnes pour ENEDIS et (iii) la surveillance de clôtures dans l’aéroport de Caen.Pour le projet CEOS, un hyperviseur de type 1 développé par la société Sysgo (PikeOs) a été choisi. PikeOs est certifié DAL-A pour divers standards avioniques tels que ARINC 653 et MILS. C’est grâce à ses certifications que cet hyperviseur a été choisi. Une de ses particularités est qu’il est possible de maîtriser l’ordonnancement de niveau 1 des VMs. Pour le niveau 1, l’ordonnancement des machines virtuelles à l’aide d’une table d’ordonnancement doit être déterminé au préalable, aucun algorithme n’est imposé. Concernant les tâches exécutées par les VMs, leur ordonnancement est déterminé par le système d’exploitation temps réel associé à la machine virtuelle. Il est également possible d’introduire des tâches directement dans PikeOS qui seront alors ordonnancées par un ordonnancement à priorité fixe. La liberté du choix d’algorithme pour l’ordonnancement de premier niveau implique plusieurs questions : comment ordonnancer les machines virtuelles pour permettre aux tâches de respecter leurs échéances ? Dans les conditions d’un ordonnancement déterminé à l’avance pour les machines virtuelles, quel ordonnancement donnerait un bon taux de succès pour les tâches ?
Origine : Version validée par le jury (STAR)