Do spisu treści tematu 3

3.3.1 Szeregowanie procesów

     
Spis treści

• Wprowadzenie
• Struktury i zmienne
• Algorytm szeregowania
• Implementacja
• Szeregowanie a wieloprocesorowość
• FSQ, czyli "Frequently Scheduled Questions"
• Bibliografia
       

---

Wprowadzenie

Autor ninejszego opracowania staje przed trudnym zadaniem. W Projekcie Linux, zeszłoroczej pracy starszych kolegów, rozdział Sposoby szeregowania procesów dosyć obszernie wyjaśnia mechanizm szeregowania procesów w Linuxie. Na szczęście nie wyczerpuje całkowicie tematu, a także zawiera klika błędów i nieścisłości. Dlatego autor starał się nie powtarzać już opisanych rzeczy, a raczej wyjaśnić kwestie mogące budzić wątpliwości oraz opisać szczegóły implementacji odsyłając do komentarzy w kodzie jądra Linuxa.

Opis powstał przede wszystkim na bazie analizy źródeł jądra Linuxa w wersji 2.0.32. W części dotyczącej szeregowania procesów, w stosunku do wersji 2.0.0 (opisanej we wspomnianym rozdziale Projektu Linux), dokonano niewielu zmian - poprawiono klika drobnych błędów.

Zacznijmy od wyjaśnienia kilku kluczowych pojęć, struktur i zmiennych związanych z szeregowaniem procesów.

Struktury i zmienne

Tablica task[]  (tablica procesów)

Jądro Linuxa, podobnie jak i jądra innych systemów unixopodobnych, informacje o procesach utrzymuje w statycznej tablicy: Jest zdefiniowana w kernel/sched.c (plik ten zawiera większość funkcji i zmiennych związanych z szeregowaniem procesów). Rozmiar tablicy określony jest przez stałą NR_TASKS, której wartość standardowo równa się 512. System nakłada pewne ograniczenia na maksymalną liczbę procesów dla użytkowników oraz dba o to, aby pozostały wolne miejsca w tablicy dla procesów nadzorcy systemu. Szczegóły zapewne można znaleźć w części poświęconej funkcji fork(). Z punktu widzenia modułu szeregującego procesy, ważniejsza jest kolejka procesów gotowych.
   

Zmienna init_task  (proces idle i kolejka procesów gotowych)

Zmienna ta ma dwojakie znaczenie. Po pierwsze, zawiera informacje o procesie o identyfikatorze równym 0. Jest to specjalny proces, pierwszy jaki powstaje w systemie. Tworzony jest w "sztuczny" sposób, bez udziału fork(). Opis procesu 0 w Projekcie Linux mija się w kilku kwestiach z prawdą. Fakty dotyczące tego procesu są następujące:

• Nosi nazwę swapper (łatwo się o tym przekonać używając kombinacji CTRL-Scroll lock w konsoli), która może sugerować, że jest to tzw. proces wymiany. Wbrew nazwie w Linuxie nie ma on żadnego związku z pamięcią wirtualną - realizuje on algorytm "nudzenia" się procesora, opisany poniżej. Nie jest to również proces tzw. proces init (proces init to jedyny bezpośredni potomek tego procesu, o pid równym zawsze 1 - kod jego znajduje się poza jądrem w pliku /sbin/init). Aby uniknąć nieporozumień proces ten będzie nazywany procesem idle.
      
• Inicjalizowany jest wartościami zdefiniowanymi w makrodefinicji INIT_TASK.
      
• Nie jest żadnym pseudoprocesem - na samym początku dokonuje inicjalizacji wielu struktur systemowych, następnie tworzy proces init za pomocą funkcji clone(), po czym wykonuje nieskończoną pętlę (patrz algorytm idle).
      
• Cały czas znajduje się w stanie TASK_RUNNING (ale i tak wartość pola state dla tego procesu nigdy nie jest używana).
       
• Nigdy nie ginie, jego struktura znajduje się w zerowym elemencie tablicy procesów.
     
• Ma najniższy priorytet w systemie - zostanie wybrany wtedy i tylko wtedy gdy nie ma innych procesów gotowych.

Po drugie, zmienna init_task jest początkiem (i jednocześnie końcem) dwukierunkowej listy cyklicznej, w której znajdują się procesy gotowe do wykonania. Dalej lista ta będzie nazywana kolejką procesów gotowych.
   

Struktura task_struct

Jest to struktura związana z każdym z istniejących w systemie procesów. Pola wykorzystywane przez kod modułu szeregowania to:

• volatile long state - określa stan procesu. I tu uwaga: to, że pole state zawiera określoną wartość nie musi koniecznie oznaczać, że proces już znajduje się w danym stanie, ale że może się w takim stanie dopiero znaleźć. W Linuxie zdefiniowane są następujące stany:
  
  TASK_RUNNING - proces się wykonuje bądź jest gotowy do wykonania
  
  TASK_INTERRUPTIBLE - proces jest lub może zostać uśpiony w stanie przerywalnym, czyli że zostanie wznowiony po nadejściu sygnału lub po upływie czasu budzenia. Ostatnie oznacza, że proces może zostać uśpiony na pewien zadany czas (możliwość często używana przez sterowniki urządzeń).
  
  TASK_UNINTERRUPTIBLE - proces jest lub zostanie uśpiony w stanie nieprzerywalnym (np. w oczekiwaniu na i-węzeł). Proces taki może zostać wznowiony jedynie na skutek wywołania funkcji wake_up() - ściślej jego stan zostanie zmieniony na TASK_RUNNING.
  
  TASK_ZOMBIE - proces wykonał funkcję exit(). Zostanie usunięty z tablicy procesów.
  
  TASK_STOPPED - proces jest lub zostanie wstrzymany. Może zostać wznowiony jedynie na skutek otrzymania sygnału SIGCONT.
  
  TASK_SWAPPING - nie jest wykorzystywany - żaden z procesów nie znajdzie się w tym stanie (ciekawostka: nie wiadomo czemu jest sprawdzany w funkcji count_active_tasks()).
  
  Stany procesów opisano w Projekcie Linux. Nie wspomina się tam jednak, że to właśnie moduł szeregowania (i tylko on) odpowiedzialny jest za faktyczne usunięcie procesu z kolejki procesów gotowych. Szczegóły w opisie algorytmu poniżej.
  
  Zwracam uwagę na użycie volatile - pole state często odczytywane jest przy włączonych przerwaniach, w wyniku których może dojść do jego modyfikacji (przypominam, że volatile zmusza kompilator do bezpośredniego sięgania do komórki pamięci przy każdym odwołaniu).
    
• long priority - wartość kwantu czasu (w tyknięciach) jaki proces otrzymuje jednorazowo na działanie. Dopuszczalne wartości zamykają się w przedziale [1, 2*DEF_PRIORITY] (dla Intela DEF_PRIORITY = 20). Wyższa wartość oznacza wyższy priorytet. Opis w Projekcie Linux podaje nieprawdę, że jest odwrotnie, oraz że priority może mieć wartość 0. Wartość priority w Linuxie jest odwzorowaniem tzw. wartości nice procesu. Może być modyfikowana i odczytywana funkcjami nice(), setpriority() oraz getpriority().
    
• long counter - czas jaki pozostał procesowi na działanie, czyli nim system spróbuje go wywłaszczyć (patrz niżej). Nazywany również dynamicznym priorytetem. Czas jest wyrażony w tyknięciach zegara. Dla Intela 1 tyknięcie równa się 10 milisekundom. Możliwe wartości counter należą do przedziału [0, 4*DEF_PRIORITY) - czyli w przypadku Intela: 0 <= counter < 80. Dlaczego? Odpowiedź poniżej.
    
• unsigned long timeout - "godzina" (wyrażona w systemowych jednostkach, patrz jiffies), o której proces zostanie obudzony i wstawiony do kolejki procesów gotowych. Odpowiedzialna za uśpienie procesu jest funkcja schedule().
    
• unsigned long policy - określa tryb szeregowania dla procesu. Dostępne tryby to: SCHED_OTHED, SCHED_RR, SCHED_FIFO.
    
• unsigned long rt_priority - priorytet realtime procesu. Dla procesów szeregowanych standardową metodą SCHED_OTHER wynosi 0, w pozostałych trybach musi być w przedzale [1,99]. Wyższa wartość - wyższy priorytet.
       
• struct task_struct *next_run, *prev_run - dowiązania do następnego i poprzedniego procesu w kolejce procesów gotowych.

Struktura zawiera jeszcze kilka pól związanych z czasem i tzw. zegarami interwałowymi, które są opisane tutaj.
    

Zmienna current

Wskazuje na task_struct bieżącego procesu. W rzeczywistości jest to makrodefinicja zwracająca wskaźnik na task_struct bieżącego procesu na "bieżącym" procesorze (wskazuje na odpowiedni element tablicy current_set[], która zawiera wskaźniki na bieżące procesy dla każdego z procesorów systemu. O tym jak wygląda szeregowanie na architekturach wieloprocesorowych można przeczytać poniżej).
    

Zmienna need_resched

Flaga wskazująca czy ma być wywołane schedule(). Istnienie takiej zmiennej podyktowane jest niemożnością wywołania funkcji schedule() bezpośrednio z procedury obsługi przerwania sprzętowego (wynika to z choćby z implementacji, a także z tego, że wybór procesu może trwać za długo, aby działo się to w procedurze obsługi przerwania).
    

Zmienna jiffies

Jest to licznik czasu systemowego. Standardowo zwiększany o 1 jest co 10ms (wartość standardowa dla Linuxa/i386, dla Linuxa/AXP jest to 1ms).

Algorytm szeregowania

Dostępne tryby szeregowania oraz działanie algorytmu zostały bardzo dobrze (i zgodnie z prawdą) opisane w Projekcie Linux. Trudno właściwie tu coś dodać - algorytm szeregowania zaimplementowany w Linuxie jest rzeczywiście bardzo prosty.

Najważniejsze jego cechy to:

• Zapewnia, że proces nie zostanie zagłodzony - odnosi się to do standardowego trybu szeregowania (SCHED_OTHER). W przypadku trybów SCHED_RR oraz SCHED_FIFO jeśli jest choć jeden gotowy proces realtime nigdy nie zostanie wznowiony proces o niższym priorytecie, w szczególności żaden z procesów szergowanych standardowo.
       
• Jest mało wytrzymały na duże obciążenie systemu, co objawia się spowolnieniem reakcji systemu. Każdy kto kompilował jądro i próbował coś pisać, prawdopodobnie odczuł, że system się zatyka. Wynika to z stąd, iż Linuxowy scheduler nie przewiduje obniżenia priorytetu zachłannego procesu wykonującego dużo obliczeń (tzw. compute-bound task). Procesy interaktywne (tzw. transput-bound tasks) miałyby dzięki temu większe szanse otrzymać procesor.
  

Schemat algorytmu

schedule()
{
   if (czekają wolne procedury obsługi przerwań)
      wykonaj je;

   wywołaj listę funkcji w kolejce tq_scheduler;

   if (bieżący proces szeregowany jest w SCHED_RR i wykorzystał swój kwant czasu)    
      przydziel mu nowy kwant i przesuń na koniec kolejki procesów gotowych;

   if (bieżący ma zostać uśpiony, ale może odbierać sygnały)
      if (otrzymał nieblokowany sygnał || minął jego czas budzenia)
         zmień jego stan na gotowy;
      else
         usuń go z kolejki procesów gotowych;

   for (każdy proces z kolejki procesów gotowych)
      wybierz proces o najwyższym priorytecie (wartości goodness);

   if (najwyższy priorytet = 0)
     for (każdy proces)
        zmodyfikuj jego wartość counter (dynamiczny priorytet);
   else
      if (brak procesu do wykonania)
         wybierz proces idle;

   if (wybrany został inny proces niż bieżący)
   {
      ustaw ewentualny czas budzenia dla bieżącego procesu;
      wznów działanie wybranego procesu;
   }
 
   if (wznowiony proces miał ustawiony budzik i obudził się przed czasem)
       wyłącz budzik;
}

Szczegółowe wyjaśnienie znajduje się w komentarzach funkcji schedule(), która realizuje wyżej opisany algorytm.

Wartość goodness

Określa na ile "dobry" jest dany proces, aby przydzielić mu procesor. Im większa wartość tym lepsza. Równa się odpowiednio:

• 1000+rt_priority: gdy proces szeregowany jest w jednym z trybów realtime
• counter: gdy proces szeregowany jest standardowo
• counter+1: jw, gdy proces jest procesem bieżącym
  

Algorytm idle

Proces 0 wykonuje nieskończoną pętlę, tzw. idle-loop. Implementacja pętli jest zależna od architektury. W przypadku Intela, początkowo wykonuje aktywne czekanie. Jeśli przez określony czas (HARD_IDLE_TIMEOUT tyknięć zegara) nie pojawi się żądanie przeszeregowania procesów (flaga need_resched)zatrzymuje działanie procesora. Opóźnienie ma na celu uniknięcie sytuacji, kiedy natychmiast po zatrzymaniu procesora trzeba go ponownie uruchomić.

Patrz opis funkcji sys_idle(), hard_idle().

Implementacja

Większość funkcji związanych z szeregowaniem znajduje się w pliku kernel/sched.c. Część w kernel/sys.c, include/linux/sched.h, include/asm-i386/system.h, arch/i386/kernel/process.c, arch/i386/kernel/entry.S. Poniżej mały przewodnik po funkcjach.

Najważniejsze z nich to: schedule(), goodness(), update_process_times().

Funkcje pomocnicze: add_to_runqueue(), del_from_runqueue(), move_last_runqueue(), wake_up_process(), process_timeout().

Makrodefinicja dokonująca przełączenia kontekstu (w asemblerze, zależna od architektury): switch_to().

Funkcja inicjalizująca scheduler: sched_init()

Funkcje umożliwiające modyfikację i sprawdzenie parametrów szeregowania:

sys_sched_setscheduler(), sys_sched_getscheduler(), sys_sched_setparam(), sys_nice(), sys_setpriority(), sys_getpriority()

Inne funkcje związane z szeregowaniem:

sys_sched_get_priority_max(), sys_sched_get_priority_min(), sys_sched_rr_get_interval(), sys_sched_yield().

W pliku kernel/sched.c, oprócz funkcji związanych ze schedulerem i czasem, znajduje się też kilka innych: show_state() oraz rodzina funkcji sys_getXid().

Procedura powrotu z trybu jądra, gdzie m.in. może dojść do wywołania schedule() to: ret_from_sys_call.

Szeregowanie a wieloprocesorowość

W jądrze SMP Linuxa (SMP - Symmetric MultiProcessor), które wykorzystuje wieloprocesorowość niektórych platform, różnice dotyczące algorytmu szeregowania procesów są minimalne. Fakty są następujące:

• Prostotę implementacji wsparcia wieloprocesorowości w Linuxie zapewnia pojedyncza blokada jądra. Blokada ta polega na tym, że tylko jeden procesor może przejść do trybu jądra. Jest to tzw. Coarse Grained Locking.
      
• W architekturach opartych na procesorach Intela wszelkie standardowe przerwania, w szczególności przerwanie zegarowe, docierają tylko do procesora o numerze 0 (tzw. bootcpu). Może to być powodem problemów, gdyż może prowadzić do zablokowania systemu, np. w sytuacji gdy procesor inny niż bootcpu znajduje się w trybie jądra, a bootcpu otrzyma przerwanie (dokładnie to opisano w komentarzu do funkcji allow_interrupts()).
     
• Do komunikacji między procesorami służą tzw. przerwania IPI (Interprocessor Interrupt). Dla Intela jest to przerwanie IRQ13, przy czym dla komunikacji zwiazanej z szeregowaniem zarezerwowano przerwanie IRQ16.
       
• Każdy z procesorów sam, gdy wejdzie do jądra, może wykonać schedule().
            
• Jeden z procesorów dokonuje odliczania czasu zużytego przez procesy na wszystkich procesorach (na Intelu jest to bootcpu, gdyż tylko on jest przerywany). W razie potrzeby, korzystając z IPI powiadamia inny procesor, o konieczności przeszeregowania procesu (normalnie wystarczy ustawienie flagi need_resched). Wtedy taki procesor otrzyma przerwanie i zawiesi się w oczekiwaniu na zdjęcie blokady z jądra. Gdy uda mu się przejąć jądro, będzie mógł sam wywołać schedule().
          
• Każdy z procesorów, wykonując schedule(), może wybrać proces sam dla siebie - nie może zmusić innego procesorora do wykonywania jakiegoś procesu.
   

W strukturze task_struct dodano następujące pola:

• int processor - zawiera numer procesora, przez który proces właśnie w danej chwili jest wykonywany, wpp wypadku równa się stałej NO_PROC_ID (równej 0xFF).

• int last_processor - numer procesora, na którym proces ostatnio działał dany proces.
      
• int lock_depth - lokalny licznik wywołań funkcji systemowych przez dany proces. Licznik ten jest inkrementowany, gdy proces wywołuje funkcję jądra oraz w procedurze obsługi przerwania (także IPI). Jego istnienie związane jest z blokadą jądra. Np. w sytuacji, kiedy dochodzi do przełączenia kontekstu z procesu działającego w trybie jądra na proces w trybie użytkownika, należy zwolnić blokadę jądra. Patrz switch_to().

Pozostałe różnice to:

• Tworzonych jest tyle kopii procesu 0 ile jest procesorów w systemie - każdy z procesorów, bądź ich część może się przecież niezależnie "nudzić". Są to prawdziwe klony - wszystkie mają identyfikator (pid) równy 0. Ma to miejsce w smp_init().
      
• W tablicy current_set[] przechowywane są wskaźniki na procesych wykonywane na poszczególnych procesorach.
      
• Dzięki wspomnianej makrodefinicji current fragmenty kodu, odwołujące się do struktury bieżącego procesu, dla których wieloprocesorowość jest przezroczysta (a takich jest wiekszość), mogły pozostać bez zmian.
            
• Wykonywanie pętli idle musi nastąpić poza jądrem (z uwagi na blokadę). Ale jednocześnie pojawia się problem - co będzie jeśli pojawi się np. jeden nowy proces, a nudzi się kilka procesorów? Jeśli wszystkie z nich będą próbowały wykonać schedule(), wszystkie zostaną zablokowane, po czym po kolei będą wchodzić do jądra, najprawdopodobniej niepotrzebnie, blokując innym dostęp do niego. W tym celu wprowadzono globalną zmienną smp_process_available - jest to licznik gotowych, ale nie wykonywanych w danej chwili procesów. Licznik ten jest modyfikowany w sekcji krytycznej chronionej semaforem binarnym. Semafor ten jest bitem, ustawianym i odczytywanym przy pomocy atomowej instrukcji typu TEST_AND_SET. Procesor, który wejdzie do sekcji krytycznej, sprawdza wartość licznika, jeśli większy od zera, dekrementuje go, po czym wykonuje schedule(), wpp kontynuuje wykonywanie pętli idle. Patrz funkcje sys_idle(), cpu_idle() w wersji SMP.

• Funkcja goodness() stara się zapobiegać migracji procesów między procesorami. Może to się opłacać ze względów sprzętowych (każdy z procesorów może mieć własną pamięć podręczną drugiego poziomu). Realizuje to w ten sposób, że dodaje do zwracanej wartości (jeśli > 0) stałą PROC_CHANGE_PENALTY = 20 w przypadku, gdy proces, dla którego oblicza wartość goodness, poprzednio działał na tym samym procesorze (czyli tym samym, który wykonuje schedule()).
      
• Funkcja add_to_runqueue(), po dodaniu procesu do kolejki procesów gotowych inkrementuje licznik smp_process_available, po czym sprawdza czy któryś z procesorów nie wykonuje pętli idle i jeśli tak, powiadamia go, że pojawił się nowy proces gotowy do wykonania.
     
• Funkcja update_process_times() odlicza czas zużyty przez procesy działające na wszystkich procesorach.   

Realizację wieloprocesorowości w jądrze w wersji 2.1.x, znajdującej się jeszcze w stadium alpha, zaimplementowano od nowa, wprowadzając niezależne blokady dla poszczególnych części jądra (tzw. fine grained locking). Zwiększa to oczywiście wydajność systemu, komplikuje jednak znacznie jego implementację.

FSQ
czyli "Frequently scheduled questions"

W trakcie zajęć z przedmiotu "Systemy operacyjne", jak i podczas naszych "burz mózgów" pojawiało się sporo pytań, które pozostały bez odpowiedzi, bądź też skończyło się na spekulacjach i przypuszczeniach. Pytania i odpowiedzi na nie, znalezione u samych źródeł, zamieszczone są poniżej.

1. Do jakiego przedziału należą wartości pola counter?
   
   Najwyższy możliwy priorytet to 40. Wobec tego, proces taki otrzyma na działanie kwant czasu równy 40 "tyknięciom" zegara (400ms). Załóżmy, że natychmiast, nim licznik counter zostanie mu zmniejszony, odda procesor i na długo zaśnie (np. wywoła funkcję pause()). Następnie, zgodnie z algorytm szeregowania, proces zostanie "postarzany", czyli kolejno będzie przyjmował wartości: 40+20=60, 40+30=70, 40+35=75. Z prostych obliczeń (suma nieskończonego ciągu geometrycznego) wynika, że wartość ta dąży do 80, nigdy jej nie osiągając.
        
2. Co to są "bottom halves" ?
   
   Są tzw. wolne procedury obsługi przerwań. Wykonanie funkcji związanych z niektórymi przerwaniami mogłoby trwać zbyt długo, aby wykonywały się w kontekście przerwania. Dlatego wprowadzono mechanizm "dolnych połówek" obsługi przerwań w celu zminimalizowania czasu spędzanego w przerwaniu - procedura jego obsługi dzielona jest na dwie części, pierwsza robi to co jest niezbędne oraz zaznacza konieczność wykonania drugiej, poza przerwaniem. Służy do tego makro mark_bh(). Funkcje bottom half wywoływane są w do_bottom_half(), które z kolei jest wywoływane przy wyjściu z jądra w ret_from_sys_call oraz w schedule().
   
   Przewidziano 32 funkcje bottom half - umieszczane są w tablicy bh_base[]. Definicje dla poszczególnych przerwań znajdują się w pliku linux/interrupt.h. Tam też znajdują się makra init_bh(), mark_bh(), enable_bh(), disable_bh().
   
   Przykładem wykorzystania opisywanego mechanizmu są funkcje do_timer() oraz timer_bh(), odpowiedzialne za czas systemowy.
          
   
3. Czy w schedule() proces może być wywłaszczony przez inny proces?
   
   Nie. Proces znajdujący się w trybie jądra nie może być wywłaszczony przez inny proces. Chwilowo wywłaszczyć proces w trybie jądra może, oczywiście, przerwanie sprzętowe (które, z kolei może być wywłaszczone przez przerwanie o wyższym priorytecie). Po skończeniu jego obsługi sterowanie wróci do przerwanego procesu. Innymi słowy, jądro jest sekcją krytyczną dla procesów użytkownika.
       
4. Kiedy i gdzie proces jest wywłaszczany?
   
   Wtedy gdy wykorzysta przydzielony mu kwant czasu. Odpowiedzialna za stwierdzenie tego faktu jest funkcja update_process_times(), wykonująca się jako "bottom half" przerwania zegarowego. Jeśli proces wykorzysta swój kwant czasu, ustawiana jest flaga need_resched. Będzie sprawdzona w procedurze powrotu z wywołania systemowego (ta sama procedura wykonywana jest także przy powrocie z procedury obsługi przerwania). Jeśli wywłaszczenie nastąpi poza jądrem - proces zostanie wstrzymany dokładnie tam, gdzie go przerwanie zastało. Jeśli przerwanie wystąpiło w momencie gdy proces przebywa w trybie jądra, to w ret_from_sys_call proces zostanie zmuszony do wejścia do schedule() i zostanie wstrzymany w miejscu wywołania switch_to().
         
   
5. Czemu niektóre funkcje jądra mają w nazwie prefiks sys_?
   
   Są to funkcje dostępne są poza jądrem dla programów użytkownika - widziane są bez prefiksu. Oczywiście, samo dodanie sys_ nie wystarcza aby funkcja była widziana poza jądrem.
          
6. A co zmienna XXX oznacza i gdzie jest zdefiniowana?
   
   W znalezieniu odpowiedzi na tego typu pytania bardzo może pomóc skrypt grepr, bez którego opis ten nie miałby szans powstać.
   

Bibliografia

1. Pliki źródłowe jądra Linuxa 2.0.32
2. Man pages: nice (2), setpriority (2), getpriority (2), sched_setscheduler (2), sched_getscheduler (2), sched_getparam (2), sched_setparam (2), sched_get_priority_max (2), sched_get_priority_min (2), sched_rr_get_interval (2), sched_yield (2), idle (2)
3. Krzysztof Arciszewski, Krzysztof Sobusiak Projekt-Linux, rozdział Sposoby szeregowania procesów
4. David A. Rusling Linux Documentation Project - The Linux Kernel, rozdział Scheduling
5. Michael K. Johnson The Linux Kernel Hacker's Guide, rozdział The Linux scheduler
6. Alan Cox An implementation Of Multiprocessor Linux
7. Markus Kuhn POSIX.1b Compatibility and Real-Time Support
8. Maurice J. Bach Budowa systemu operacyjnego UNIX, wyd. II, WNT 1995
9. Berny Goodheart, James Cox The Magic Garden Explained, PRENTICE HALL 1994