Je développe un planificateur pour un système intégré. Ce planificateur appellera chaque processus tous les x millisecondes; Cette fois peut être configuré séparément pour chaque processus, bien sûr.
Tout est codé et appelle chaque processus comme il le devrait; Le problème que je suis confronté est la suivante:
Imaginez que je fixe 4 processus à appeler toutes les 10, 5 et 30 millisecondes respectivement: p> L'appel résultant au fil du temps sera le suivant: p> A |
A B A B |
C C C C C C C | processes being called
D |
----------------------------------
0 5 10 15 20 25 30 35... ms
4 Réponses :
Il n'y a pas de solution parfaite pour cela, ils entreront en collision de temps en temps. Je suggérerais d'ajouter une valeur aléatoire minuscule (0,01-0,0,1 ms) à la longueur du cycle, de sorte qu'à long terme, ils seront vraiment appelés rarement à la fois.
Alternativement, si vous avez la granularité de planificateur de 5 ms, le premier thread est toujours appelé à x + 1 ms, seconde sur x + 2, etc., de sorte qu'il soit toujours garanti 1 ms de course ininterrompue (si vous avez 10 threads, alors Soyez x + 0,5, x + 1, x + 1,5). Mais cela pourrait devenir assez délicat à mettre en œuvre.
La granularité du planificateur est de 1 ms. Ce qui précède était juste un exemple pour montrer le problème facilement.
Dommage que le planificateur n'a pas de granularité infinie; Ensuite, vous pourriez simplement ajouter SQRT (2) à la période du premier processus, SQRT (3) à la seconde, SQRT (5) au troisième ... :)
Ce type de problème concerne directement le domaine des algorithmes de programmation et de planification en temps réel. J'ai pris une classe sur ce sujet au collège, et si je me souviens bien, Schedule de taux monotonique est le genre d'algorithme que vous recherchez.
L'idée est que vous attribuez des priorités à des emplois inversement proportionnels à leur période, c'est-à-dire la période la plus petite, plus la priorité est élevée. Mais cela fonctionne mieux si vous pouvez interrompre vos emplois et les reprendre plus tard.
Il y a d'autres alternatives, cependant, comme EDF (Date limite la plus tôt en premier) , mais ces sont des algorithmes de planification dynamiques (c.-à-d. Les priorités sont attribuées pendant l'exécution).
Étant donné un ensemble d'intervalles, vous pouvez trouver le temps à laquelle les temps de début coïncideraient (n'ayant pas offsets) en trouvant le multiple le moins commun comme mentionné Jason dans un commentaire à votre message. Vous pouvez trouver le LCM en faisant la factorisation principale des intervalles pour un ensemble de tâches.
Il semble que le Le plus grand diviseur commun (ou le plus grand facteur commun GCF) pourrait être le nombre le plus utile à calculer. Ce numéro vous donnera un intervalle à laquelle les répétitions seront . Dans votre exemple, le GCF est 5. Avec un GCF de 5, il est possible d'ajouter un décalage initial de 1, 2, 3, etc. à chaque tâche pour éviter de se chevaucher des heures de début. Ainsi, avec un GCF de 5, vous pouvez avoir jusqu'à 5 tâches qui ont des temps de départ qui ne se chevauchèrent jamais. Avec un GCF de 20, vous pourriez avoir jusqu'à 20 tâches prévues sans aucune période de début de chevauchement. Si deux (ou plus) tâches sont relativement amorces (GCF = 1), un chevauchement se produira certainement, peu importe ce que vous utilisez pour ces tâches si les intervalles ne changent jamais.
Et si j'ai des processus multiples de 5 mélangés à 7? Exemple: a = 5, b = 7, c = 20
Le GCF de 5 et 7 est 1 (ils sont relativement prêts). Compte tenu des heures de début entier, il est impossible de planifier ces deux tâches de manière à répéter toutes les 5 et 7 fois et non en collision. En ne sachant pas plus sur les contraintes du problème, ma pensée est qu'il serait préférable de prendre le GCF des tâches restantes (5 dans ce cas) et de planifier ces tâches de manière à ne jamais entrer en collision. Puis planifiez la tâche B avec un décalage de 0 et vous aurez au maximum 2 tâches qui commencent simultanément. Si vous pouvez utiliser des compensations non entières, une tâche B a un décalage de .5ms.
La solution facile consiste à modifier le calendrier dans lequel vous appelez les sous-programmes. C'est à dire. Au lieu de 5, 10, 15 et 30 ms, pouvez-vous vivre selon E.G. avec 5, 15, 15 et 30? Ensuite, vous pouvez utiliser le modèle suivant: (A = 5 MS PROC, B, C = 15 MS PROC, D = 30 MS PROC):
AAAAAAAAAAAAAAAAAAAA ... B B B B B B B ... C C C C C C C ... D D D ...
Les intervalles que j'ai écrites n'étaient qu'un exemple. Je ne sais pas quels intervalles le planificateur fera face. L'idée est que le planificateur lui-même est capable d'ajuster le délai pour minifier les collisions. Évidemment, si les temps sont toujours statiques, je peux les ajuster manuellement, mais je ne sais pas quels intervalles vont être utilisés.
L'intervalle entre les collisions entre deux processus sera la LCM de leurs intervalles. Vous aurez donc des collisions minimales lorsque tous vos intervalles sont relativement amorces les uns aux autres.