Les stratégies d'ordonnancement constituent un créneau de recherche actif. Quelques pistes contemporaines d'exploration suivent.
Dans Soft Real-Time on Multiprocessors: Are Analysis-Based Schedulers Really Worth It? se trouve une étude de la pertinence d'un ordonnanceur analytique (avec tests d'ordonnançabilité et tout le tralala) pour un ensemble de tâches TR au sens usuel du terme. Les auteurs font le constat que :
Sachant cela, vaut-il la peine de passer à un ordonnanceur TR avec ses mécanismes analytiques pour un STR usuel?
Les auteurs utilisent une application de flux vidéo avec un ordonnanceur EDF (un G-EDF, en fait, fruit dune thèse de 2014 : http://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=1000&context=eng_etds) et un ordonnanceur équitable de Linux (le CFS : http://en.wikipedia.org/wiki/Completely_Fair_Scheduler) à titre comparatif, pour faire le constat qu'en situation de charge élevée du système, l'ordonnanceur EDF présente des caractéristiques avantageuses, donc peut être pertinent selon le contexte.
Dans An O(m) Analysis Technique for Supporting Real-Time Self-Suspending Task Systems, les auteurs proposent une approche pour faire en sorte que les pertes de temps d'utilisation des coeurs d'un ordinateur dûs à une suspension d'exécution fortuite (non-volontaire) soit d'une complexité linéaire en fonction du nombre de coeurs disponibles. Leur domaine d'application est les STR où se trouvent principalement des tâches TR usuelles et des tâches sporadiques.
Dans LLF Schedulability Analysis on Multiprocessor Platforms, les auteurs proposent une stratégie d'ordonnancement qu'ils nomment LLF, pour Least Laxity First, et avec laquelle les tâches qui ont le moins de « laxité » se font attribuer la plus haute priorité. Cette stratégie est utilisée (et mène à un ordonnancement optimal) sur des systèmes monoprocesseurs, mais les auteurs examinent ici ses caractéristiques sur systèmes multiprocesseurs.
La « laxité » d'une tâche y est définie comme l'urgence de la réaliser, ou plus formellement :
« [the] laxity of a task at any time is defined as remaining time to deadline minus the amount of remaining execution »
En général, la « laxité » d'une tâche se définit informellement par le Slack Time, ou temps qui resterait à la période d'une tâche après son exécution d'une tâche si elle démarrait immédiatement.
Dans Tardiness Bounds under Global EDF Scheduling on a Multiprocessor, l'auteur fait le constat que pour qu'un algoirithme d'ordonnancement tel qu'EDF puisse être appliqué à un STR strict, il faut parfois être si pessimiste qu'on en vient à sacrifier 50% du temps d'exécution disponible, mais montre comment, en relaxant certaines règles, on peut tirer mieux profit de ces algorithmes dans un STR au sens usuel du terme.
Son analyse repose sur la Tardiness des tâches, ce qui est informellement le temps de complétion de la tâche moins son échéance. Cette valeur peut être positive ou négative, surtout si la tâche n'est pas TR au sens strict.
Dans CPU Scheduling and Memory Management for Interactive Real-Time Applications, les auteurs examinent la question de l'ordonnancement des tâches sur les processeurs d'un ordinateur multicoeurs. On parle d'une étude assez importante des paramètres (incluant les Page Faults, qui constituent un facteur difficile à évaluer à l'interne mais susceptible d'avoir un impact prononcé sur le temps d'exécution) qui contribuent à la capacité d'un STR sur le plan global de rencontrer ses contraintes en fonction de la répartition des tâches et de la charge de traitement sur les coeurs mis à sa disposition, et de l'exposition d'algorithmes pour évaluer l'état de la situation en continu.
Parmi les algorithmes explorés, on trouve :
Dans Techniques for Multiprocessor Global Schedulability Analysis, l'auteur examine les tests d'ordonnançabilité connus pour la répartition de tâches sporadiques sur plusieurs processeurs et note que ces tests sont mal adaptés aux ordinateurs contemporains, alors qu'un ordonnancement partitionné, plus « manuel », tend à donner de meilleurs résultats. Il définit un STR comme :
« [...] a finite collection of independent recurring tasks, each of which generates a potentially infinite sequence of jobs. Every job is characterized by an arrival time, an execution requirement, and a deadline, and it is required that a job complete execution between its arrival time and its deadline »
Il met par la suite de l'avant un test qui montre des caractéristiques d'exécution intéressantes et dont il détaille les avantages.
Dans Qilin: Exploiting Parallelism on Heterogeneous Multiprocessors with Adaptive Mapping, les auteurs discutent de mise en correspondance entre threads et processeurs dans un ordinateur aux unités de traitement hétérogènes (CPU, GPU, unités SIMD, etc.) avec une approche dynamique qu'ils qualifient d'adaptative.
Leur approche repose sur une bibliothèque qui compile dynamiquement (un peu comme le fait .NET) certaines fonctions de manière à ce que le code généré corresponde aux unités de traitement qui seront exploitées. Une part d'entraînement est impliqué pour tirer profit de leur outil.
L'article CPU-Assisted GPGPU on Fused CPU-GPU Architectures discute de l'utilisation du CPU pour gérer l'exécution de tâches sur une puce intégrant à la fois CPU et GPU. Leur approche profite de la fréquence d'horloge du CPU, typiquement plus élevée, pour prendre des décisions qui maximisent le débit des diverses unités de traitement.
Dans Transparent CPU-GPU Collaboration for Data-Parallel Kernels on Heterogeneous Systems, les auteurs proposent leur approche pour réduire les copies de données vers et du GPU, ce qui importe du fait qu'il s'agit d'un point de sérialisation coûteux dans les systèmes parallèles.
D'ailleurs, Data Transfer Matters for GPU Computing s'intéresse spécifiquement au coût de ces transferts et à la latence qui en découle, visant à en arriver (le plus possible) à une approche de type Zero-Copy. L'approche Zero-Copy domine aussi l'article Zero-copy I/O processing for low-latency GPU computing, qui explique comment faire correspondre l'adresse d'un appareil et de l'autre pour que les accès soient direct (nous avons vu, dans le cours, comment y arriver en C++), de manière à opérer convenablement avec un système de fusion nucléaire (un Tokamak).
Dans Automatic CPU-GPU Communication Management and Optimization, les auteurs décrivent leur bibliothèque pour automatiser les échanges entre CPU et GPU et expliquent comment ils réalisent cette mise en correspondance.
L'article Dynamic Load Balancing on Single- and Multi-GPU Systems s'intéresse au problème du balancement des charges de traitement sur un système à plusieurs GPU. Reconnaissant la difficulté de cette tâche pour des humains, l'article propose un mécanisme automatisé pour arriver à cette fin.
De même, PTask: Operating System Abstractions To Manage GPUs as Compute Devices (présentation : http://www.mimuw.edu.pl/~iwanicki/courses/ds/2012/presentations/ds-presentation-11-wed-12-ptask.pdf) propose une approche pour pallier le manque d'abstraction au niveau du système d'exploitation pour abstraire les GPU de manière à les traiter comme des périphériques « normaux ».
Dans TimeGraph: GPU Scheduling for Real-Time Multi-Tasking Environments, les auteurs proposent une architecture pour alimenter un GPU de travail tout en cherchant à respecter les échéances des tâches à traiter.
On commence à voir de l'exploration de STR sur téléphones intelligents, en particulier sur plateforme Android.
L'article Real-Time Android: Deterministic Ease of Use examine ce qu'il faut apporter comme ajustement à un système Android pour un faire un SETR, ou pour y exécuter des STR de manière fiable. Les auteurs suggèrent entre autres de conserver Android tel quel pour l'essentiel, mais de remplacer le noyau par un noyau de Linux TR.
Une caractéristique de plusieurs STR sur Linux est le recours à de la mémoire partagée entre processus, pour faciliter une communication directe entre les entités qui en ont besoin. Android offre un mécanisme atypique de mémoire partagée en comparaison avec ce que l'on trouve sur un système Linux plus classique, soit ashmem (Asynchronous Shared Memory), ce qui demande aux applications d'adapter leurs pratiques, ou à tout le moins d'ajuster le code client pour profiter de cette API.
L'article Evaluating Android OS for Embedded Real-Time Systems examine aussi l'applicabilité d'Android en tant que SETR. Les subtilités du moteur de collecte d'ordures de Dalvik, la JVM propre à Android, y sont examinées. L'article met de l'avant que les changements de contexte sur Android sont pris en charge par le noyau de Linux qui sous-tend l'ensemble du système, ce qui permet d'avoir recours à un noyau TR et aux ordonnanceurs qui lui sont spécifiques.
Par défaut, le noyau livré avec Android ne prend pas en charge la dualité inversion de priorités / héritage de priorités. Outre changer de noyau, les auteurs suggèrent aussi la possibilité de passer par un hyperviseur TR, mais indiquent que cela coupe essentiellement l'accès des processus aux services spécifiques à Android.
Dans Scheduling Jobs with Unknown Duration in Clouds, les auteurs s'intéressent à la maximisation du débit des tâches qui sont soumises à un centre de traitement dans un contexte infonuagique, sur la base d'heuristiques stochastiques où chaque tâche est modélisée comme une variable aléatoire à partir de ses paramètres d'exécution.
L'Internet of Things, ou IoT, où la connectivité sera essentiellement totale entre une multitude d'appareils de tailles et de formats variés, est l'une des promesses que nous fait aujourd'hui l'industrie. Son impact serait global, touchant la conduite automatique de véhicules à moteurs, la gestion de l'épicerie et des dates de péremption, la localisation automatique des individus, et j'en passe.
Le rapport Time-Aware Applications, Computers, and Communication Systems (TAACCS) du NIST, par Marc Weiss et al., met de l'avant l'importance de composants TR stricts dans le contexte de cette révolution, et insiste sur le fait que l'évolution matérielle contemporaine nous a donné de meilleurs comportements en moyenne, mais tend à réduire notre capacité de tirer des mesures précises du comportement de nos programmes. Il émet des recommandations à l'effet de corriger le tir et de remettre entre les mais des programmeuses et des programmeurs des outils leur permettant un contrôle plus fin des considérations associées au passage du temps.
Ce rapport souligne l'existence de trois types de signaux pour mesurer le temps qui passe, soit :
Les modalités de mesure qui impliquent un transfert d'information sont évidemment plus complexes que celles qui n'en dépendent pas, du fait de l'implication de plus d'un homologue. Le transfert d'information demande de tenir compte de la latence de transfert, comme le font par exemple :
Le rapport s'intéresse aussi aux métriques de vitesse d'exécution, incluant la question des délais (latence) et du Jitter (variations de latence). §3.4 met particulièrement en relief l'opposition entre l'amélioration des « performances » moyennes, entre autres dû au fait que presque tous les ordinateurs aujourd'hui sont munis de plus d'un coeur, mais aussi dû à la présence de Caches et d'unités d'exécution spéculative, et la capacité que nous avons de mesurer ce que nous faisons avec précision.
Voilà!
