Quel algorithme de planification est utilisé sous Linux?

Récemment dans une interview, j'ai été interrogé sur l'algorithme de planification utilisé par le système d'exploitation Linux. Quel est l'algorithme utilisé pourquoi?

De plus, quel algorithme est utilisé dans les systèmes d'exploitation en temps réel et pourquoi?

Le planificateur de tâches Linux actuel s'appelle Completely Fair Scheduler (CFS). Vous devriez jeter un œil à http://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt pour plus de détails. Le design est assez complexe et à mon avis ne convient pas pour RTOS.

L'ordonnancement monotone est une technique courante dans les systèmes en temps réel, car elle a de fortes garanties si certaines hypothèses se vérifient (par exemple, les priorités de tâche statiques et le temps et le taux d'exécution fixes). Il existe de nombreux autres algorithmes et de nombreuses recherches ont été menées. Il s'agit donc essentiellement des propriétés dont vous avez besoin et de ce que vous savez sur votre tâche et de ce qui est fixe.

Je ne suis pas sûr de savoir si vous envisagez la planification des E / S du noyau. Dans le cas où vous n'êtes pas: Ignorez cette réponse.

Wikipédia déclare que le CFG (complètement Fair Queuing) est par défaut depuis le noyau 2.6.18.

Sur mon openSUSE (exécutant le noyau 2.6.37), je peux basculer entre CFG, NOOP et Deadline .

L'algorithme Round Robin est généralement utilisé dans les environnements de partage de temps.

L'algorithme utilisé par le planificateur Linux est un schéma complexe avec une combinaison de priorité préemptive et de découpage temporel biaisé. Il attribue un quantum de temps plus long aux tâches de priorité plus élevée et un quantum de temps plus court aux tâches de priorité plus faible.

Il identifie chaque processus soit comme un processus en temps réel soit comme un processus normal (autre). Les tâches en temps réel se voient attribuer des priorités statiques dans la plage [0,99], où un nombre inférieur indique une priorité plus élevée.

Toutes les autres tâches ont des priorités dynamiques dans la plage [100,139], basées sur l'interactivité d'une tâche qui sont basées sur leurs belles valeurs plus ou moins la valeur 5. Les tâches qui sont plus interactives ont généralement des temps de sommeil plus longs et sont donc plus susceptibles de ont des ajustements plus proches de -5, car le planificateur favorise les tâches interactives. (L'interactivité d'une tâche est déterminée par la durée de sommeil pendant qu'elle attend les E / S.) L'interactivité d'une tâche détermine si la valeur 5 sera ajoutée ou soustraite de la valeur de Nice. Le résultat de ces ajustements sera une priorité plus élevée pour ces tâches. Inversement, les tâches avec des temps de sommeil plus courts sont souvent plus liées au processeur et verront donc leurs priorités réduites.

Le noyau conserve une liste de toutes les tâches exécutables dans une structure de données runqueue. Une file d'attente d'exécution contient deux tableaux prioritaires: actif et expiré. Le tableau actif contient toutes les tâches avec du temps restant dans leurs tranches de temps, et le tableau expiré contient toutes les tâches expirées. Chacun de ces tableaux de priorités contient une liste de tâches indexées en fonction de la priorité. Le planificateur choisit la tâche avec la priorité la plus élevée dans le tableau actif pour exécution sur la CPU. Lorsque toutes les tâches ont épuisé leurs tranches de temps (c'est-à-dire que le tableau actif est vide), les deux tableaux de priorité sont échangés: le tableau expiré devient le tableau actif, et vice versa.

La priorité dynamique d'une tâche est recalculée lorsque la tâche a épuisé son temps quantique et doit être déplacée vers le tableau expiré. Ainsi, lorsque les deux tableaux sont échangés, toutes les tâches du nouveau tableau actif ont reçu de nouvelles priorités et des tranches de temps correspondantes. (Remarque: Ceci est un extrait du livre sur les concepts de système d'exploitation (9e édition) par Abraham Silberschatz, et al. Pour plus de détails, veuillez vous référer à la section 5.6.3 de ce livre)

Ceci est une réponse à votre autre question. Les systèmes en temps réel (RTS) sont de deux types, durs et mous. L'algorithme de planification du processeur pour le RTS dur est un algorithme préemptif basé sur la priorité et celui pour le RTS doux est une priorité non préemptive.