Planificateurs de tâches

Question

J'ai eu une discussion intéressante avec certains collègues sur les meilleures stratégies de planification pour les tâches en temps réel, mais tout le monde n'avait pas une bonne compréhension des stratégies de planification courantes ou utiles.

Pour votre réponse, veuillez choisir une stratégie et l'examiner en détail, plutôt que de donner quelques informations sur plusieurs stratégies.Si vous avez quelque chose à ajouter à la description de quelqu'un d'autre et qu'elle est courte, ajoutez un commentaire plutôt qu'une nouvelle réponse (si elle est longue ou utile, ou simplement une bien meilleure description, veuillez utiliser une réponse)

• Quelle est la stratégie - décrivez le cas général (en supposant que les gens savent ce qu'est une file d'attente de tâches, les sémaphores, les verrous et d'autres principes fondamentaux du système d'exploitation en dehors du planificateur lui-même)
• Pour quoi cette stratégie est-elle optimisée (latence des tâches, efficacité, temps réel, gigue, partage de ressources, etc.)
• Est-ce en temps réel, ou peut-il être réalisé en temps réel

Stratégies actuelles :

• Préemptif basé sur les priorités
• Horloge la plus lente et la plus faible consommation

-Adam

Answer 1

Comme décrit dans un article intitulé Planification des tâches en temps réel pour les systèmes embarqués économes en énergie, Swaminathan et Chakrabarty décrivent les défis de la planification des tâches en temps réel dans les appareils (embarqués) à faible consommation avec plusieurs vitesses de processeur et profils de consommation d'énergie disponibles.L'algorithme de planification qu'ils décrivent (et qui s'avère seulement environ 1 % pire qu'une solution optimale lors des tests) propose une manière intéressante de planifier les tâches qu'ils appellent l'heuristique LEDF.

Extrait du journal :

La première échéance de faible énergie est d'abord l'heuristique, ou simplement le LEDF, est une extension de l'algorithme le plus connu de la date limite (EDF).Le fonctionnement de LEDF est le suivant:LEDF maintient une liste de toutes les tâches publiées, appelées «Liste Ready».Lorsque les tâches sont libérées, la tâche avec la date limite la plus proche est choisie pour être exécutée.Un chèque est effectué pour voir si la date limite de tâche peut être respectée en l'exécutant à la tension inférieure (vitesse).Si la date limite peut être respectée, LEDF attribue la tension inférieure à la tâche et la tâche commence à exécuter.Pendant l'exécution de la tâche, d'autres tâches peuvent entrer dans le système.Ces tâches sont supposées être placées automatiquement sur la «liste des prêts».LEDF sélectionne à nouveau la tâche avec la date limite la plus proche à exécuter.Tant qu'il y a des tâches qui attendent d'être exécutées, LeDF ne garde pas le ralenti du processeur.Ce processus est répété jusqu'à ce que toutes les tâches soient prévues.

Et en pseudo-code :

Repeat forever {
    if tasks are waiting to be scheduled {
        Sort deadlines in ascending order
        Schedule task with earliest deadline
        Check if deadline can be met at lower speed (voltage)
        If deadline can be met,
            schedule task to execute at lower voltage (speed)
        If deadline cannot be met,
            check if deadline can be met at higher speed (voltage)
        If deadline can be met,
            schedule task to execute at higher voltage (speed)
        If deadline cannot be met,
            task cannot be scheduled: run the exception handler!
    }
}

Il semble que la planification en temps réel soit un problème intéressant et en constante évolution à mesure que les petits appareils à faible consommation deviennent de plus en plus omniprésents.Je pense que c'est un domaine dans lequel nous verrons de nombreuses recherches plus approfondies et j'ai hâte de me tenir au courant !

Answer 2

Un schéma de planification en temps réel courant consiste à utiliser le multitâche préemptif basé sur les priorités.
Chaque tâche se voit attribuer un niveau de priorité différent.
La tâche la plus prioritaire dans la file d'attente prête sera la tâche en cours d'exécution.Il fonctionnera jusqu'à ce qu'il abandonne le processeur (c'est-à-direretards, attentes sur un sémaphore, etc...) ou une tâche de priorité plus élevée devient prête à être exécutée.

L'avantage de ce système est que le concepteur du système a un contrôle total sur les tâches qui seront exécutées avec quelle priorité.L'algorithme de planification est également simple et doit être déterministe.

D’un autre côté, les tâches de faible priorité peuvent manquer de CPU.Cela indiquerait un problème de conception.