Szeregowanie procesów w Linuksie

Łukasz Bieniasz-Krzywiec

Dobromiła Górczyńska

Jakub Łącki

Plan

• Wstęp
• Scheduler w jądrze 2.4
• Scheduler O(1)
• Afera Schedulerowa
• RSDL
• CFS
• Porównanie Schedulerów
• Testowanie Schedulerów
• Tendencje Rozwojowe
• Podsumowanie

Wstęp

Co to jest scheduler?

• scheduler to algorytm
• dane są procesy gotowe do wykonania
• scheduler wybiera ten, który będzie się wykonywać
• wyróżniamy:
  • cooperative multitasking - proces sam oddaje procesor
  • preemptive multitasking - system wywłaszcza proces

Wstęp

Jak powiedzieć 'scheduler'?

• po angielsku: [skedżjuler]
  
• po polsku:
  • planista?

Polityka zarządzania procesami

• zbiór reguł
• oparta na technice dzielenia czasu
• oparta na priorytetach procesów
• priorytety dynamiczne
• klasyfikacje procesów
• zorientowane na wejście-wyjście i zorientowane obliczeniowo
• interaktywne, procesy czasu rzeczywistego i procesy wsadowe
• faworyzowanie procesów zorientowanych na wejście-wyjście
• możliwość zmiany priorytetu przez użytkownika

Wywłaszczanie procesora

• procesowi zabierany jest procesor gdy
• skończy mu się przydzielony mu kwant czasu
• pojawi się proces o wyższym priorytecie dynamicznym
• wywłaszczanie tylko w trybie użytkownika

Długość kwantu czasu

• za krótka: za duży narzut na przełączanie procesów
• za długa: zmniejsza reaktywność systemu
• kompromis: kwant długi z zachowaniem reaktywności

Scheduler w jądrze 2.4 - ogólnie

• 1400 linii kodu
• prosty algorytm, choć skomplikowana funkcja schedule()
• przepisany od nowa dla jądra 2.4
• podstawowe struktury danych
• schedule_data
• runqueue - połączona lista wszystkich procesów

Epoki

• czas procesora podzielony na epoki
• na początku epoki każdy proces ma swój kwant czasu
• koniec epoki - wykorzystanie wszystkich kwantów czasu
• przeliczenie nowych kwantów

Priorytety procesów

• podstawowy kwant czasu każdego procesu
• możliwość zmiany kwantu przez użytkownika
• wzięcie pod uwagę priorytetów wszystkich procesów przez schedulera
• rodzaje priorytetów
• statyczny - dla procesów czasu rzeczywistego
• dynamiczny - dla zwykłych procesów

Struktury danych schedulera cz. 1

• Pola deskryptora procesu związane z działaniem schedulera:
• need_resched - czy wywołać funkcję schedule()
• policy - klasa procesu:
• SCHED_FIFO
• SCHED_RR
• SCHED_OTHER

Struktury danych schedulera cz. 2

• rt_priority - priorytet statyczny
• counter - ilość przerwań pochodzących od zegara pozostałych do wyczerpania kwantu czasu
• nice
• cpus_allowed - bit specyfikujący, na jakich procesorach dany proces może działać
• cpus_runnable - bit specyfikujący, który procesor wykonuje dany proces, jeśli w ogóle jakiś
• processor - indeks procesora, który wykonuje dany proces

Struktury danych procesora

• tablica aligned_data rozmiaru NR_CPUS zawierająca struktury typu schedule_data
• struktury schedule_data zawierajš dwa pola
• curr - wskaźnik do deskryptora bieżącego procesu
• last_schedule - czas ostatniej zmiany procesu

Funkcja schedule()

• znajduje proces na liście runqueue i przydziela mu procesor
• jest wywoływana bezpośrednio lub leniwie

Funkcja schedule() - Wyw. bezpośrednie

• następuje kiedy bieżący proces musi być zablokowany z powodu niedostępności zasobu
• co się dzieje:
• proces bieżący jest dodawany do odpowiedniej kolejki wait queue
• stan bieżącego procesu zmieniany na TASK_INTERRUPTIBLE lub TASK_UNINTERRUPTIBLE
• wywoływana jest funkcja schedule()
• sprawdzenie, czy zasób jest dostępny, jeśli nie, powrót do punktu 2
• kiedy zasób jest dostępny, bieżący proces jets usuwany z kolejki wait queue

Funkcja schedule() - Wyw. leniwe

• pole need_resched procesu current ustawiane jest na 1
• gwarancja wywołania funkcji schedule() w najbliższej przyszłości
• następuje np. w następujących przypadkach:
• po zużyciu kwantu czasu, wołana przez funkcję update_process_time()
• budzony proces ma wyższy priorytet niż obecny, wołana przez reschedule_idle() (zazwyczaj wywoływana przez funkcję wake_up_process())
• następują wywołania systemowe sched_setscheduler() lub sched_yield()

Przed przełączeniem procesów cz.1

• cel funkcji schedule():
• wybrać następny proces, któremu przydzielony zostanie procesor
• ustawić zmienną lokalną next na deskryptor wybranego procesu
• inicjalizacja paru zmiennych lokalnych:

• 	prev = current;
  	this_cpu = prev->processor;
  	sched_data = & aligned_data[this_cpu];
  

• sprawdzenie blokad
• zdezaktywowanie przerwań lokalnych i założenie spin locka na runqueue

Przed przełączeniem procesów cz. 2

• sprawdzanie, czy proces prev jest procesem czasu rzeczywistego z polityką Round Robin, któremu wygasł kwant
• jeśli tak, danie prev nowego kwantu i wsadzenie go na koniec runqueue
• sprawdzanie stanu procesu prev
• TASK_INTERRUPTIBLE i ma niezablokowane sygnały -> jego stan ustawiany jest na TASK_RUNNING
• nie jest TASK_RUNNING -> jest usuwany z runqueue
• ustawienie pola need_resched procesu current na 0

Przed przełączeniem procesów cz. 3

• wybranie procesu któremu przydzielony zostanie procesor
• przeglądanie listy runqueue
• uwzględnienie tylko procesów:
• gotowych do działania na bieżącym procesorze
• nie wykonujących się jeszcze na innym procesorze
• przypisanie na next deskryptora wybranego procesu
• gdy zajdzie potrzeba, zaczęcie nowej epoki
• uaktualnienie zmiennej procesora aligned_data
• zapisanie indeksu procesora w deskryptorze procesu
• zdjęcie spin locka z listy runqueue
• uaktywnienie przerwań lokalnych

Przed przełączeniem procesów cz. 4

• jeśli wybrany proces jest tym samym co prev, schedule() kończy działanie
• w przeciwnym przypadku przełączenie procesów:
• oznaczenie czasu w odpowiedniej strukturze
• odpowiednie zarządzenie przestrzenią adresową nowego procesu
• next jest normalnym procesem -> zastąpienie
• next jest wątkiem jądra -> zwolnienie
• wywołanie funkcji switch_to() - przełączenie procesów prev i next

Strategia wybierania najlepszego procesu

• sedno algorytmu przydzielania procesora - wybranie najlepszego procesu
• funkcja goodness()
• waga wyliczana w zależności od tego, czy:
• proces jest poprzednio działającym procesem: waga -1
• proces jest zwykłym procesem, który wykorzystał swój kwant czasu: waga 0
• proces jest zwykłym procesem, który nie wykorzystał swojego kwantu czasu: waga [2,77]
• proces jest procesem czasu rzeczywistego: waga ponad 1000
• w wieloprocesorowych systemach specjalny bonus służący do tego, żeby nie przełączać procesu między procesorami

Działanie na systemie wieloprocesorowym

• wymiana informacji między procesami
• funkcja reschedule_idle() - sprawdzenie procesu prev po przełączeniu procesów przez inne procesory

Efektywność działania schedulera

• hackerzy jądra uwielbiają wprowadzać własne poprawki i eksperymentować
• dla każdej strategii zarządzania procesami istnieje zestaw danych, który wykaże jej miernotę
• algorytm dobry i całkiem wydajny dla pojedynczej maszyny, na której działa kilkadziesiąt procesów na raz

Wady algorytmu cz. 1

• jedna kolejka procesów runqueue dla wszystkich procesorów w systemie SMP
• proces może dostać którykolwiek z procesorów
• jeden spinlock na kolejkę runqueue
• kiedy jeden procesor zablokuje kolejkę, pozostałe muszą czekać
• mniejsza efektywność działania
• nieskalowalny
• źle się zachowuje w przypadku dużej ilości procesów
• urządzenia wejścia-wyjścia muszą dłużej czekać na reakcję

Wady algorytmu cz. 2

• kwant czasu jest zbyt duży w przypadku dużego obciążenia procesorów
• strategia preferowania procesów zorientowanych na wejście-wyjście nie jest optymalna
• nie obsługiwał wywłaszczania
• mogło się zdarzyć, że proces o wyższym priorytecie czeka, aż proces o niższym priorytecie skończy działanie

Scheduler w jądrze 2.6 - ogólnie

• stworzony przez Ingo Molnara
• działa w czasie O(1) - nazywany schedulerem O(1)
• jedna z motywacji Ingo do stworzenia nowego schedulera: wirtualna maszyna Javy (powoduje wykonywanie wielu wątków)

Zalety schedulera O(1)

• skalowalny, dobrze sobie radzi z dużą ilością procesów i zadań
• zapobiega niepotrzebnemu przeskakiwaniu procesów pomiędzy procesorami
• sprzyja zachowaniu procesów zorientowanych na wejście/wyjście na jednym procesorze

Podstawowe struktury danych

• tablica priorytetów
• zawiera bitmapę do efektywnego znajdowania procesu o najwyższym priorytecie
• tablica list procesów o danym priorytecie
• proces, który chce dostać procesor, dołącza się na koniec odpowiedniej listy
• struktura runqueue
• zawiera dwie tablice priorytetów (active i expired)
• zamienia active z expired, gdy active jest pusta
• wybór procesu o najwyższym priorytecie w czasie stałym

Wsparcie dla SMP

• jedna struktura runqueue na procesor
• jedna blokada na strukturę runqueue
• efektywne działanie wielu procesorów
• zawiera dwie tablice priorytetow (active i expired)
• zamienia active z expired, gdy active jest pusta
• wybór procesu o najwyższym priorytecie w czasie stałym

Wywłaszczanie procesora

• scheduler O(1) zapewnia, że żaden proces o niższym priorytecie nie będzie działał, kiedy gotowy do wykonania jest proces o wyższym priorytecie

Dynamiczne wyznaczanie priorytetów

• zapobiega sytuacji zawłaszczania procesora przez jeden proces
• nagradzanie i karanie procesów przez przyznawanie bonusów
• nagradzanie procesów zorientowanych na wejście/wyjście
• karanie procesów zorientowanych obliczeniowo
• rodzaj procesu określany na podstawie stosunku czasu działania do czasu spania
• dynamiczne priorytety zmieniane tylko na procesach zwykłych (użytkownika)

Zbalansowanie przeciążenia proc. w SMP

• funkcjonalność odciążania jednych procesorów przez inne
• co 200 ms procesor sprawdza, czy obciążenia procesorów są zbalansowane
• jeśli nie, zaczyna przerzucanie zadań
• niestety, dane procesu muszą być przerzucane do cache'u nowego procesora

Najciekawsze funkcje schedulera O(1)

• schedule - glowna funkcja schedulera
• load_balance - sprawdza, czy zachodzi nierównomierne obciążenie procesorów
• jeśli zachodzi, próbuje przerzucić procesy
• effective_prio - zwraca efektywny priorytet procesu (z doliczonymi bonusami)
• recalc_task_prio - oblicza bonus dla procesu
• source_load - oblicza obciążenie procesora, z którego można przerzucić proces
• target_load - oblicza obciążenie procesora, na który być może proces zostanie przerzucony
• migration_thread - wysokopriorytetowy wątek, który przerzuca zadania między procesorami

Podsumowanie

• poprawienie wykorzystania procesora z jednoczesnym poprawieniem reaktywności
• wprowadzenie wywłaszczania
• wsparcie dla architektur wieloprocesorowych

AFERA SCHEDULEROWA

W połowie kwietnia 2007 wybuchła afera schedulerowa:

• Con Kolivas tworzy innowacyjnego RSDLa
• Linus zapowiada włączenie RSDLa do mainstream
• Con ulega wypadkowi i trafia do szpitala na 6 tygodni
• Ingo Molnar tworzy CFSa w 63 (sic!) godziny robocze
• pierwsze wersje CFSa przegrywaja z RSDL we wszystkich płaszczyznach
• mimo to Linus skłania się ku wynalazkowi Ingo...

Con Kolivas - bohater [1/2]

• hackowanie kernela to jego hobby
• na co dzień anestezjolog w Melbourne
• skupił się na poprawie wydajności linuxa na desktopach
• dlatego zyskał rzesze fanów
• jego niektóre łatki zostały włączone do mainstream
• nauczył się programować w 2002 roku!

Con Kolivas - bohater [2/2]

• benchmark Contest - poprawa schedulera I/O
• zbiór łatek na O(1)
• planista stopniowy (SD) - odrzucony "z braku dowodów"
• PlugSched - idea wymiennego planisty wyszła od Cona - odrzucony
• RSDL
• hałaśliwy użytkownik (sched_yield)
• choroba & CFS
• koniec przygody z rozwijaniem jądra

Scheduler SD

Główne cechy schedulera SD:

• SD - Staircase Deadline scheduler
• celem SD jest poprawia interaktywności
• zapewnia także sprawiedliwość

SD - realizacja

Podstawowa zasada działania:

• dwie kolejki procesów: active i expired
• wybieramy do wykonania proces o najwyższym priorytecie
• procesowi, który wykorzysta swój przydział czasu spada dynamiczny priorytet
• dostaje nowy przydział czasu
• całość działa w czasie O(1)

SD - przykład

Procesy "spadają po schodach"

SD - przykład

Procesy "spadają po schodach"

SD - przykład

Procesy "spadają po schodach"

SD - przykład

Procesy "spadają po schodach"

SD - przykład

Procesy "spadają po schodach"

SD - przykład

Procesy "spadają po schodach"

SD - przykład

Procesy "spadają po schodach"

SD - przykład

Skąd wiadomo jak spadają procesy?

Stąd:

nice -20 0000000000000000000000000000000000000000
nice -10 1000100010001000100010001000100010010000
nice   0 1010101010101010101010101010101010101010
nice   5 1011010110110101101101011011010110110110
nice  10 1110111011101110111011101110111011101110
nice  15 1111111011111110111111101111111011111110
nice  19 1111111111111111111111111111111111111110

Przydział czasu

• Przydział czasu zależy od wartości nice procesu:

      unsigned int rr = rr_interval;
      if (nice < -6) {
  	rr *= nice * nice;
  	rr /= 40;
      } else if (nice > 0)
  	rr = rr / 2 ? : 1;
  

• rr_interval można modyfikować przez /proc/sys/kernel/rr_interval, domyślnie 8ms

SD - procesy interaktywne

SD nie ma herurystyk do obsługi procesów interaktywnych

• proces, który się budzi (prawdopodobnie) nie wykorzystał jeszcze swojego czasu w danej epoce
• inne procesy mogły już "spaść po schodach"
• obudzony proces zostanie wykonany jako jeden z pierwszych
• brak heurystyk pozwala na prostą analizę zachowania schedulera

Nowości w kernelu 2.6.23

• podział schedulera na moduły
  • za każdą klasę procesów może odpowiadać inny algorytm szeregowania
• obecnie trzy algorytmy:
  • prosty scheduler dla procesów SCHED_FIFO i SCHED_RR
  • CFS do obsługi SCHED_NORMAL i SCHED_BATCH
  • "prawie jak scheduler" dla SCHED_IDLE

Podział schedulera na moduły (1)

Jak napisać własny scheduler?

• Zadanie zmienia stan:
  • void (*enqueue_task) (struct rq *rq, struct task_struct *p);
  • void (*dequeue_task) (struct rq *rq, struct task_struct *p);
• Prośba o odsunięcie zadania w czasie:
  • void (*requeue_task) (struct rq *rq, struct task_struct *p);
• Inicjalizacja i aktualizacja danych zadania:
  • void (*task_new) (struct rq *rq, struct task_struct *p);
  • void (*task_init) (struct rq *rq, struct task_struct *p);
  • void (*task_tick) (struct rq *rq, struct task_struct *p);

Podział schedulera na moduły (2)

Jak napisać własny scheduler?

• Sprawdzanie, czy aktualny proces należy wywłaszczyć:
  • void (*check_preempt_curr) (struct rq *rq, struct task_struct *p);
• Pytanie o zadanie, które ma zostać wykonane:
  • struct task_struct * (*pick_next_task) (struct rq *rq);
  • void (*put_prev_task) (struct rq *rq, struct task_struct *p);

CFS - założenia

• zasada działania oparta na prostej idei
• symulujemy zachowanie 'idealnego' procesora
• na takim komputerze każdy proces cały czas otrzymuje 1/<ilość_działających_procesów> dostępnego czasu procesora

CFS - realizacja

Symulację przeprowadzamy w następujący sposób:

• trzymamy procesy w drzewie czerwono - czarnym
• dla każdego procesu kluczem jest 'ile muszę się wykonywać, żebym miał tyle czasu co reszta'
zawsze wybieramy ten, który ma 'największy dług'

CFS - szczegóły (1)

Problem:

klucze wszystkich elementów w drzewie zmieniają się w czasie

Rozwiązanie:

• dodajmy do systemu wirtualny (statystyczny) proces
• cfs_rq -> fair_clock - ile czasu procesora od startu systemu dostałby wirtualny proces
• p -> wait_runtime - o ile mniej czasu od procesu wirtualnego dostał proces p
• klucz sortowania w drzewie to cfs_rq -> fair_clock - p -> wait_runtime

CFS - szczegóły (2)

Obsługa priotytetów

• im wyższy priotytet, tym większą wagę ma proces
• im większa waga, tym szybciej rośnie p -> wait_runtime procesu
• im większy priorytet procesu, tym trudniej go wywłaszczyć
• spójrzmy w kod...

CFS - szczegóły (3)

Ile czasu może wykonywać się proces?

static long sched_granularity(struct cfs_rq *cfs_rq)
{
    unsigned int gran = sysctl_sched_latency;
    unsigned int nr = cfs_rq->nr_running;
    if (nr > 1) { 
	gran = gran/nr - gran/nr/nr;
	gran = max(gran, sysctl_sched_min_granularity);
    }
    return gran;
}

Que? Skąd się bierze '- gran/nr/nr'?

CFS - szczegóły (4)

Obliczanie granularności

klucz_przedA + gran = klucz_przedB
klucz_poB + gran = klucz_poA
klucz_poA = klucz_przedA
klucz_poB = klucz_przedB - d + d/nr
opoznienie = d * nr

CFS - szczegóły (5)

Co z procesami interaktywnymi?

• proces, który spał, powiększa swój dług o czas snu
• ale o nie więcej niż 2*sysctl_sched_runtime_limit
• trzeba też komuś odjąć trochę czasu

CFS - szczegóły (6)

Kiedy proces zostaje wywłaszczony?

    s64 __delta = curr->fair_key - se->fair_key;
    unsigned long ideal_runtime, delta_exec;
    
    ideal_runtime = max(sysctl_sched_latency / cfs_rq->nr_running,
	(unsigned long)sysctl_sched_min_granularity);

    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
    if (delta_exec > ideal_runtime)
	granularity = 0;

    if (__delta > niced_granularity(curr, granularity))
	resched_task(rq_of(cfs_rq)->curr);

Porównanie schedulerów cz. 1

• podstawowe struktury danych:
• scheduler 2.4: runqueue - lista wszystkich procesów
• scheduler O(1): runqueue - dwie tablice list procesów (active i expired)
• scheduler RSDL: runqueue - dwie tablice list procesów (active i expired)
• scheduler CFS: runqueue - drzewo czerwono-czarne
• czas szeregowania procesów
• scheduler 2.4: O(n)
• scheduler O(1): zagadka...
• scheduler RSDL: O(1)
• scheduler CFS: O(log n)

Porównanie schedulerów cz. 2

• zmiana priorytetów dynamicznych:
• scheduler 2.4: liczenie wagi procesu w zależności od:
• typu: proces zwykły, czy czasu rzeczywistego
• wykorzystania kwantu czasu
• scheduler O(1): bonusy przyznawane w zależności od interaktywności procesu
• scheduler RSDL: tymczasowe zmniejszanie priorytetu o stablicowane wartości
• brak heurystyk dla procesów interaktywnych
• scheduler CFS: bonusy przyznawane w zależności od interaktywności procesu

Porównanie schedulerów cz. 2

• myśl przewodnia algorytmu
• scheduler 2.4: zwiększenie efektywności w porównaniu z poprzednią wersją
• scheduler O(1): poprawienie reaktywności systemu (z jednoczesnym lepszym wykorzystaniem procesora)
• scheduler RSDL: poprawienie reaktywności systemu
• scheduler CFS: sprawiedliwy podział czasu procesora

Plan - Testowanie

Testowanie

• Po co testować?
• Co testować?
• Jak testować?
• Czym testować?
• Prezentacja wyników benchmarków.

Po co testować?

• aby poprawić działanie schedulera
• aby wyłonić najlepszego kandydata na włączenie do mainstream
• aby wykryć błędy
• aby dowiedzieć się jakie są przypadki brzegowe i jak rozwiązać ich kwestie
• aby Linuxa używało się lepiej, wszystkim

Co testować?

• wydajność (performance)
• narzut (overhead)
• skalowalność (scalability)
• sprawiedliwość (fairness)
• interaktywność (interactivity)
• reaktywność (responsiveness)

Jak testować? [1/2]

• find the latest version of the patch
• download it
• if on a slow link, go back to #1
• compile it
• if on a slow cpu, go back to #1
• start testing
• find bug
• go back to #1
• report bug.

Jak testować? [2/2]

• to bardzo trudne zadanie ...
• stare schedulery nie działają deterministycznie
• testy trzeba powtarzać wiele razy, uśredniać wyniki
• działanie schedulera w dużym stopniu zależy od sprzętu
• można symulować obciążenie procesora

Czym testować? [1/2]

Micro-Benchmarki:

• lat_ctx, pipe-test, starve, massive_intr
• za ich pomocą mierzymy głównie:
• narzut schedulera (szybkość przełączania kontekstu)
• skalowalność
• sprawiedliwość
• nie odzwierciedlają rzeczywistości
• są bardzo technicze

Czym testować? [2/2]

Macro-Benchmarki:

• hackbench, contest, interbench
• za ich pomocą mierzymy głównie:
• wydajność
• skalowalność
• interaktywność
• reaktywność
• mają odzwierciedlać rzeczywistości

Używanie:

• muzyka, filmy, gry 3D, X-y, ...

pipe-test

• autor: Ingo Molnar
• źródło: strona domowa Ingo
• mierzy: czas przełączanie kontekstu

pipe-test - Nasze Wyniki

pipe-test - Wyniki z KernelTrap

lat_ctx

• autor: Larry McVoy (1994)
• źródło: pakiet lmbench-2.5
• mierzy: czas przełączania kontekstu, narzut schedulera, także skalowalność

lat_ctx - Nasze Wyniki

lat_ctx - Wyniki z KernelTrap

hackbench

• autor: Open Source Development Labs (2003)
• źródło: strona Open Source Development Labs
• mierzy: wydajność, narzut schedulera, skalowalność
• działanie:

hackbench - Nasze Wyniki

hackbench - Wyniki z KernelTrap

hackbench - Nasze Wyniki

massive_intr

• autor: Satoru Takeuchi
• źródło: http://people.redhat.com/mingo/cfs-scheduler/tools/massive_intr.c
• mierzy: sprawiedliwość
• działanie:
• massive_intr uruchamia n (parametr) procesów, na t sekund
• procesy w pętli kopiują długie stringi
• dla każdego procesu wypisywana jest liczba pętli które wykonał

starve

• autor: Satoru Takeuchi
• źródło: http://people.redhat.com/mingo/cfs-scheduler/tools/massive_intr.c
• mierzy: szybkość przełączania kontekstu, wydajność
• działanie:
• 2 procesy
• pierwszy wysyła do drugiego 1 mln SIGUSR1
• wyniki:
• 2.6.22: 59.418s
• 2.6.22-ck1: 40.900s
• 2.6.22-cfs: 44.222s

Co nas czeka?

• sprawiedliwość!
• rezygnacja z przybliżania i zgadywania, determinizm
• upraszczanie implementacji (Roman Zippel, RFS, RSRFS)
• modularna budowa
• może jednak zintegrowanie PlugScheda?
• może powstaną różne schedulery dla różnych zastosowań
• . . . ? ? ?