Simulation d’algorithmes d’ordonnancement temps réel

Formation simulation d’algorithmes d’ordonnancement temps reel, tutoriel & guide de travaux pratiques en pdf.

Systèmes temps réels

Les systèmes informatiques temps réels sont aujourd’hui présents dans de nombreux secteurs d’activités comme : − L’industrie de production au travers des systèmes de contrôle de procédé. − L’industrie du transport au travers des systèmes de pilotage embarqués − Les salles de marché au travers du traitement des données boursières en temps réel. − La nouvelle économie au travers du besoin toujours croissant du traitement et l’acheminement de l’information (vidéo, pilotage à distance, réalité virtuelle…).
Ce qui est primordiale de retenir en systèmes informatiques temps réel, c’est la notion de contraintes temporelles dont le respect est aussi important que l’exactitude du résultat. En effet, les dits systèmes doivent délivrer des résultats exacts dans les délais imposés. Pour garantir le respect des limites ou contraintes temporelles, il est nécessaire que : − Les différents services et algorithmes utilisés s’exécutent en temps borné. − Les différents enchaînements possibles des traitements garantissent que chacun des services et algorithmes ne dépassent pas leurs limites temporelles. Pour cela, il est nécessaire de faire appel à la théorie de l’ordonnancement.
L’ordonnancement consiste à organiser dans le temps la réalisation de tâches, compte tenu de contraintes temporelles (délais, contraintes d’enchaînement) et de contraintes portant sur la disponibilité des ressources requises. Il existe plusieurs algorithmes d’ordonnancement dont :

− Rate Monotonic ou encore RM : C’est un algorithme à priorité fixe, utilisé uniquement pour les tâches périodiques. La tâche qui a la priorité la plus forte, est élue pour être exécutée. La priorité est l’inverse de la périodicité : la tâche ayant la période la plus petite, dans un jeu de tâches, est la plus prioritaire. C’est un algorithme optimal dans la classe des algorithmes à priorité fixe, facile à implanter dans un système d’exploitation. Les tâches sont ordonnançables en mode préemptif ou non préemptif.

− Earliest Deadline First ou encore EDF : C’est un algorithme à priorité dynamique, pour les tâches périodiques et apériodiques. Comme RM, les tâches sont ordonnançeables en mode préemptif et non préemptif. C’est également un algorithme optimal, difficile à implanter dans un système d’exploitation. Il est instable en surcharge et est moins déterministe que RM. Pour un jeu de tâches donné, on calcule l’échéance pour chacune d’elle et celle ayant la plus courte échéance est élue.
− Deadline Monotonic ou encore DM : c’est un algorithme à priorité statique. La priorité d’une tâche est inversement proportionnelle à son échéance. Cet algorithme équivaut à R M quand l’échéance est égale à la période (échéance sur requête).
− Least Laxity First ou encore LLF : C’est un algorithme basé sur des priorités dynamiques. La priorité d’une tâche est inversement proportionnelle à sa laxité dynamique. Autrement dit, la tâche de plus haute priorité à l’instant t dispose de la plus petite laxité.

− Ordonnancement POSIX 1003b : C’est une extension temps réel du standard ISO / ANSI POSIX définissant une interface portable de systèmes d’exploitation. C’est un algorithme à priorité fixe, s’exécute uniquement en mode préemptif (RM facile). Les tâches sont élue grâce à une file d’attente par priorité et une politique de gestion de la file parmi: SCHED_FIFO, SCHED_RR et SCHED_OTHERS.