Trzy klasy procesów:
- procesy czasu rzeczywistego: SCHED_RR i SCHED_FIFO,
- zwykłe procesy: SCHED_NORMAL,
- proces idle
Mają bezwzględne pierwszeństwo przed zwykłymi procesami. Każdy proces klasy RT ma priorytet z przedziału 1..99. Wyższa wartość oznacza wyższy priorytet. Procesy o wyższym priorytecie są zawsze wykonywane przed procesami o niższym priorytecie. Różne polityki w klasach SCHED_RR i SCHED_FIFO.
Każdy zwykły proces ma priorytet określony przez nice. Przyjmuje on wartości od -20 do 19.
Działanie algorytmu szeregowania jest podzielone na epoki. Każdy proces ma przypisany pewien kwant czasu, przez który może używać procesor w bieżącej epoce.
Dwie grupy procesów aktywnych - active i expired - zaimplementowane jako wskaźniki do struktur struct prio_array. Proces w stanie TASK_RUNNING znajduje się w grupie active jeśli ma jeszcze jakiś czas do wykorzystania lub w expired jeśli już wykorzystał swój kwant czasu.
Koniec epoki następuje gdy grupa active jest pusta. Jej wykonanie polega na zamianie wskaźników active i expired i zajmuje czas stały.
W danym momencie wykonywany jest proces o najwyższym priorytecie dynamicznym. Najwyższy tzn. mający najniższą wartość. Każdy proces ma priorytet dynamiczny z przedziału 0..139:
0..99 - procesy czasu rzeczywistego, ich priorytety ustalone są przez użytkownika i nie są modyfikowane przez scheduler
100..139 - zwykłe procesy, ich priorytet dynamiczny ustalany jest na podstawie nice, ale jest modyfikowany przez scheduler
Algorytm znajdowania procesu o najniższym priorytecie korzysta z dwóch struktur danych:
Mapa bitowa procesów o danym priorytecie
Zaimplementowana na liczbach całkowitych typu unsigned long.
Tablica list procesów
Dzięki temu znajdowanie procesu o najwyższym priorytecie odbywa się w czasie stałym.
Priorytety dynamiczne obliczane są tak żeby promować procesy interaktywne. Jeśli scheduler uzna że proces jest interaktywny dostaje wyższy priorytet dynamiczny. Szczegóły w dalszej części prezentacji.
Każdy procesor posiada własne listy active i expired. Procesy przydzielone są do procesora na którym się wykonują. Jeśli zachodzi taka potrzeba wyrównywane są ilości procesów przydzielonych poszczególnym procesorom.