Który algorytm planowania jest używany w systemie Linux?

Niedawno w wywiadzie zapytano mnie o algorytm planowania używany przez system operacyjny Linux. Jaki algorytm jest używany, dlaczego?

Jaki algorytm jest wykorzystywany w systemach operacyjnych czasu rzeczywistego i dlaczego?

Obecny harmonogram zadań systemu Linux nosi nazwę Całkowicie uczciwy harmonogram (CFS). Więcej informacji można znaleźć na stronie http://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt . Projekt jest dość złożony i moim zdaniem nie nadaje się do RTOS.

Częstą techniką w systemach czasu rzeczywistego jest harmonogramowanie monotoniczne, ponieważ ma silne gwarancje, jeśli pewne założenia zostaną spełnione (np. Statyczne priorytety zadań oraz ustalony czas i szybkość wykonania). Istnieje wiele innych algorytmów i przeprowadzono wiele badań. Więc w zasadzie chodzi o właściwości, których potrzebujesz, o tym, co wiesz o swoim zadaniu i co zostało naprawione.

Nie jestem do końca pewien, czy bierzesz pod uwagę planowanie we / wy jądra. Jeśli nie jesteś: Zignoruj ​​tę odpowiedź.

Wikipedia stwierdza, że CFG (całkowicie Fair Queuing) jest domyślny od Kernela 2.6.18.

W moim openSUSE (z jądrem 2.6.37) mogę przełączać się między CFG, NOOP i Deadline .

Algorytm Round Robin jest zwykle używany w środowiskach dzielenia czasu.

Algorytm wykorzystywany przez program planujący Linuksa jest złożonym schematem z kombinacją wyprzedzającego priorytetu i stronniczego podziału czasu. Przypisuje kwant dłuższy czas do zadań o wyższym priorytecie i krótszy kwant do zadań o niższym priorytecie.

Identyfikuje każdy proces jako proces w czasie rzeczywistym lub normalny (inny) proces. Zadaniom w czasie rzeczywistym są przypisywane priorytety statyczne w zakresie [0,99], gdzie niższa liczba oznacza wyższy priorytet.

Wszystkie inne zadania mają dynamiczne priorytety w zakresie [100,139], oparte na interaktywności zadania, które są oparte na ich miłych wartościach plus lub minus wartość 5. Zadania bardziej interaktywne zwykle mają dłuższy czas snu i dlatego są bardziej prawdopodobne wprowadzać korekty bliższe wartości -5, ponieważ harmonogram preferuje zadania interaktywne. (Interaktywność zadania zależy od tego, jak długo spał w oczekiwaniu na operacje wejścia / wyjścia.) Interaktywność zadania określa, czy wartość 5 zostanie dodana, czy odjęta od wartości miłej. Rezultatem takich dostosowań będą wyższe priorytety dla tych zadań. I odwrotnie, zadania o krótszych czasach uśpienia są często bardziej związane z procesorem, a zatem ich priorytety zostaną obniżone.

Jądro utrzymuje listę wszystkich możliwych do uruchomienia zadań w strukturze danych typu runqueue. Kolejka zawiera dwie tablice priorytetów: aktywne i wygasłe. Aktywna tablica zawiera wszystkie zadania z pozostałym czasem w swoich przedziałach czasowych, a wygasła tablica zawiera wszystkie zadania, które wygasły. Każda z tych tablic priorytetów zawiera listę zadań indeksowanych według priorytetów. Program planujący wybiera zadanie o najwyższym priorytecie z aktywnej tablicy do wykonania na CPU. Gdy wszystkie zadania wyczerpią swoje przedziały czasowe (tzn. Tablica aktywna jest pusta), wymieniane są dwie tablice priorytetów: tablica wygasła staje się tablicą aktywną i odwrotnie.

Dynamiczny priorytet zadania jest ponownie obliczany, gdy zadanie wyczerpało kwant czasowy i ma zostać przeniesione do tablicy, która wygasła. Tak więc, gdy dwie tablice są wymieniane, wszystkie zadania w nowej aktywnej tablicy mają przypisane nowe priorytety i odpowiednie przedziały czasowe. (Uwaga: jest to fragment książki „System System Concepts” (wydanie 9) Abrahama Silberschatza i innych. Szczegółowe informacje można znaleźć w rozdziale 5.6.3 tej książki)

To jest odpowiedź na twoje kolejne pytanie. Systemy czasu rzeczywistego (RTS) są dwojakiego rodzaju: twardy i miękki. Algorytm planowania procesora dla twardego RTS jest algorytmem zapobiegawczym opartym na priorytetach, a dla miękkiego RTS nie ma pierwszeństwa.