Arwa écrit sur les problèmes de programmation et de codage, notamment sur la planification des algorithmes dans les systèmes d’exploitation en temps réel.
Les algorithmes de planification sont des méthodes utilisées dans les systèmes d’exploitation pour répartir les ressources entre les processus de manière planifiée.
Photo par Antonio Batinić sur Pexels
Les algorithmes de planification sont des méthodes utilisées dans les systèmes d’exploitation pour répartir les ressources entre les processus de manière planifiée. Le but de ces algorithmes est de minimiser la pénurie de ressources en veillant à ce que chaque processus obtienne le temps CPU requis.
Cet article explique un exemple d’algorithme d’ordonnancement utilisé dans les systèmes d’exploitation en temps réel et l’ordonnancement au plus tôt (EDF).
Qu’est-ce que la programmation EDF ?
Le premier délai en premier (EDF) est un algorithme d’ordonnancement prioritaire dynamique optimal principalement utilisé dans les systèmes d’exploitation en temps réel. Elle peut être décrite à travers les points suivants :
- Axé sur la priorité: Chaque processus se voit attribuer une priorité et le planificateur sélectionne le processus à exécuter en fonction de celle-ci. Par conséquent, le processus avec la priorité la plus élevée est exécuté en premier. Dans le cas d’EDF, la priorité est fixée en fonction du délai absolu de chaque processus.
- Dynamique: les priorités sont calculées et peuvent changer pendant l’exécution des processus ; contrairement à l’ordonnancement statique, dans lequel les priorités sont déjà attribuées avant que les processus ne soient exécutés.
- S’exécute en mode préemptif: Cela signifie que les tranches de temps du CPU peuvent être divisées pour un processus. En d’autres termes, il n’est pas nécessaire que le même processus conserve la ressource qui lui est donnée tout au long de son cycle de vie. Au lieu de cela, il peut être interrompu par un autre processus si cet autre processus a une priorité plus élevée. EDF fonctionne également sur des monoprocesseurs non préemptifs, mais il n’autorise pas de temps d’inactivité inséré.
Comment fonctionne EDF
Chaque processus a un délai absolu qui lui est assigné et le planificateur exécute les processus en fonction de ces délais. Le processus dont l’échéance est la plus proche se voit attribuer la priorité la plus élevée. Les priorités sont attribuées et modifiées dynamiquement.
Pour s’assurer qu’un ensemble de processus est ordonnancé à l’aide d’EDF, la formule suivante est utilisée :
où U est l’utilisation du processeur, Ci est le temps d’exécution et Ti est la période de chaque processus.
EDF peut garantir le respect de tous les délais dès lors que leur utilisation est inférieure ou égale à 100 %.
Avantages et limites
EDF présente certains avantages par rapport aux algorithmes d’ordonnancement à priorité fixe. Par exemple, il a moins de changements de contexte, moins de temps d’inactivité (le processeur peut être pleinement utilisé) et il peut planifier tous les ensembles de processus que les algorithmes à priorité fixe peuvent, tandis que les processus programmables EDF ne sont pas tous programmables avec des algorithmes à priorité fixe.
Cependant, il existe quelques limitations. Par exemple, il est moins prévisible en raison des priorités variables des tâches, ce qui peut affecter le système lorsqu’il est surchargé. Il est également moins contrôlable en termes de priorités et d’exécution. De plus, EDF a des frais généraux élevés et est difficile à mettre en œuvre dans le matériel.
Faites défiler pour continuer
Exemple 1
Considérez les trois processus suivants :
Étape 1
Premièrement, nous allons vérifier si les processus sont planifiables en calculant l’utilisation :
U = C1/P1 + C2/P2 + C3/P3 = (3/20) + (2/5) + (2/10) = 0,75 = 75 %
U = 75 < 100 %, ce qui indique que les processus sont planifiables.
Étape 2
Nous prenons le plus petit commun multiple des périodes des processus pour savoir de combien d’unités nous avons besoin pour exécuter les trois processus :
Lcm(20, 5, 10) = 20
Nous avons besoin de 20 unités au maximum pour exécuter les processus.
Étape 3
Comme la période de P1 = 10, nous lui donnons 20/10 = 2 tranches de temps, chacune d’une longueur de 10 unités. De même, avec P2, nous obtenons 20/5 = 4 tranches de temps, chacune d’une longueur de 5 unités, et P3 recevra 20/20 = 1 tranche de temps d’une longueur de 20 unités. Les séparateurs sont marqués en vert et illustrés dans la figure ci-dessous :
Étape 4
Le processus dont l’échéance est la plus proche reçoit la priorité d’exécution. Lorsque son temps d’exécution est terminé pour cette tranche de temps, le processus suivant avec l’échéance la plus proche s’exécutera. Dans ce cas, les délais sont égaux aux périodes. ceci est illustré ci-dessous :
Exemple 2
Dans cet exemple, chacun des processus de l’exemple précédent se voit attribuer une échéance qui n’est pas égale à sa période. Nous divisons le temps accordé à chaque processus comme dans l’exemple précédent. Cependant, dans ce cas, nous marquons le délai comme suit (les délais sont marqués en noir) :
Comme nous pouvons le voir sur la figure ci-dessous, chaque processus doit terminer son exécution pour chaque tranche de temps avant le délai imparti. Par exemple, P2 doit s’exécuter deux fois avant d’atteindre un temps de 4 sur sa première tranche de temps, 9 sur sa seconde, et ainsi de suite.
Ce contenu est exact et fidèle au meilleur de la connaissance de l’auteur et ne vise pas à remplacer les conseils formels et individualisés d’un professionnel qualifié.
