Struktury danych w nowym schedulerze pozwalają zlikwidować czynnik O(n) z poprzedniej wersji.
Podstawowa struktura danych schedulera. Jest to kolejka wszystkich procesów gotowych przyporządkowanych danemu procesorowi - każdy procesor ma swoją kolejkę runqueue. Kolejka składa się z dwóch tablic priorytetowych, właściwych struktur przechowujących procesy:
struct runqueue {
...
prio_array_t *active; /* wskaźnik tablicy wątków gotowych */
prio_array_t *expired; /* wskażnik tablicy wątków którym skończył się kwant czasu */
prio_array_t arrays[2]; /* właściwe tablice */
...
};
Wszystkie procesy zaczynają na jednej tablicy (*active). W chwili, gdy procesowi skończy się kwant czasu, jest on przerzucany do tablicy *expired. W momencie, gdy w tablicy *active nie ma już procesów, wskaźniki do obu tablic są po prostu zamieniane miejscami. (Warto zauważyć, że procesowi jest wyliczany nowy kwant czasu w trakcie przerzucania z jednej tablicy do drugiej, a nie po przerzuceniu wszystkich - dzięki temu unikamy przestoju pod koniec epoki.)
prio_array_t):
Struktura ta odpowiada za znalezienie pierwszego procesu o najniższym priorytecie w czasie O(1). Jest to tablica list - każda lista w tablicy odpowiada jednemu systemowemu priorytetowi, na liście o numerze x znajdują się tylko procesy o priorytecie x. (Podobnie jak dawniej, w Linuksie 2.6 mamy standardowo 100 priorytetów czasu rzeczywistego (0..99) i 40 priorytetów użytkownika (100..139, odpowiadają wartościom nice -20..19).)
struct prio_array {
unsigned int nr_active; /* liczba aktywnych procesów na prio_array */
unsigned long bitmap[BITMAP_SIZE]; /* bitmapa zajętości list */
struct list_head queue[MAX_PRIO]; /* tablica list - po jednej liście na priorytet */
};
Znalezienie pierwszego procesu o najwyższym priorytecie sprowadza się do znalezienia pierwszego ustawionego bitu w bitmap (za pomocą bardzo zoptymalizowanej funkcji), a potem wzięcia pierwszego procesu z odpowiadającej znalezionemu priorytetowi listy (pierwszy proces z listy na pewno ma jeszcze kwant czasu, bo procesy bez kwantu czasu leżą w drugiej tablicy, *expired). Natomiast "odłożenie" odchodzącego procesu polega na przełożeniu go z początku odpowiadającej mu listy na jej koniec (efektem czego procesy o tym samym priorytecie są szeregowane metodą round-robin). Wszystkie te operacje są wykonywalne w czasie stałym; podobnie dodanie nowego procesu (wstawiamy do jednej z list), przeniesienie procesu do tablicy *expired (proces odchodzący zawsze znajduje się na początku swojej listy).