Parametryzacja planisty CFS

Jakub Nogły

Wstęp

Od jądra Linuxa 2.6.23 planista O(1) został zastąpiony przez CFS (Completely Fair Scheduler). Przedstawię schemat działania CFS a następnie omówię możliwości zmiany konfiguracji planisty CFS.

Scheduling

Każdy nowoczesny system operacyjny dzieli kwanty czasu pracy procesora pomiędzy procesy i wątki (w Linuxie task) zgodnie z określonym algorytmem i priorytetami. Jest to możliwe ponieważ system co kwant czasu generuje przerwanie i to pozwala planiście na wykonanie swojej pracy, czyli dokonania wyboru następnego zadania (task) do wykonania. Częstotliwość zegara jest ustalana jednorazowo, w czasie konfiguracji. W przypadku jądra 2.4 częstotliwość ta była ustawiona na 100Hz. W sytuacji jąder 2.6 mamy do wyboru pomiędzy 100, 250, 300 lub 1000Hz. Oczywiście większa częstotliwość zegara oznacza szybszą obsługę przerwań i w konsekwencji lepszą interaktywność kosztem zwiększenia obciążenia systemu. Jeżeli system nie ma za dużo pracy do wykonania, mianowicie nie ma procesów w kolejce do wykonywania, obsługa setek przerwań na sekundę jest stratą czasu i energii procesora. W jądrze 2.6.21 ten problem został rozwiązany poprzez implementacje dynamicznych tyknięć zegara. Kiedy system jest bezczynny, pewne przerwania są ignorowane. W ten sposób można uzyskać częstotliwość do 6 przerwań zegarowych na sekundę (są to przerwania pochodzące od sprzętu). Co więcej w od jądra 2.6.16 został wprowadzony zegar wysokiej rozdzielczości (high resolution timer) pozwalający mierzyć czas z dokładnością do nanosekund. Dzięki tej technologii planista może pracować z większą dokładnością.

Przedstawię tylko pobieżny schemat działania planisty CFS, szczegóły działania były omawiane na wykładzie. 1. Timer generuje przerwanie i planista wybiera zadanie, które (zgodnie z konfiguracją):

ma najmniejszy wirtualny czas wykonania
właśnie zmieniło status z waiting na running.

Następnie liczony jest czas na jaki zadanie otrzyma procesor (time_slice) zgodnie z równaniem:


		time_slice = period * task_load / cfs_rq_load;

gdzie time_slice jest to czas jaki zostanie przydzielony danemu zadaniu, period jest to czas epoki (zależy od liczby zadań w kolejce oraz konfiguracji), task_load waga zadania, zależy od priorytetu, cfs_rq_load waga wczystkich zadań z klasy fair. Jeżeli używany zegar wysokiej rozdzielczości to time_slice jest obliczany z dokładnością do 1ns. Następnie planista zmienia kontekst.
2. Zadanie otrzymuje procesor.
3. Przychodzi następne przerwanie zegarowe. Planista sprawdza stan aktualnego zadania i podejmuje decyzje o wywłaszczeniu. Zadanie może zostać pozbawione procesora gdy:

Zużyło cały time_slice
Istnieje zadanie z mniejszym wirtualnym czasem wykonania.
W systemie jest nowo stworzone zadanie.
Jest zadanie, które zostało obudzone.

Jeżeli trzeba to:
(a) Planista aktualizuje wirtualny czas wykonania zgodnie z rzeczywistym czasem wykonania i obciążeniem
(b) Planista dodaje zadanie do drzewa czerwono czarnego. Gdzie zadania są posortowane po current_vruntime - min_vruntime, gdzie current_vruntime jest to czas aktualnego zadania, a min_vruntime jest to minimalny czas zadania w drzewie.

Parametry planisty CFS

CFS posiada wiele parametrów które mogą być modyfikowane w celu dopasowania działania do aktualnych potrzeb. Parametry są dostępne przez system plików proc. Wszystkie niżej wymienione parametry znajdują się w /proc/sys/kernel w pliku z taką samą nazwą jaką parametr.
Aby dowiedzieć się o wartość parametru można uzyć jednej z dwóch komend: (przykład dla sched_latency_ns)

# cat /proc/sys/kernel/sched_latency_ns
# sysctl sched_latency_ns

Analogicznie w przypadku edycji:

# echo VALUE > /procs/sys/kernel/sched_latency_ns
# sysctl -w sched_latency_ns=VALUE

sched_latency_ns - czas trwania epoki w ns, (20ms domyślnie)
sched_min_granuality - na podstawie tej zmiennej wyliczany jest period mianowicie


		period = max(nr_running * sched_min_granuality, sched_latency_ns);

gdzie nr_running to aktulna ilość zadań w kolejce. Domyślna wartość to 4ms. Oznacza, to że długość trwania, epoki zostaje wydłużona, gdy liczba zadań przekracza 5, przy standardowych ustawieniach.

sched_child_runs_first - gdy 1 to proces potomny ma pierwszeństwo przed procesem macierzystym.
sched_compat_yield - gdy 0(domyślnie) to zablokowane jest dobrowolne zrzekanie się procesora (funkcja system_yields()).
sched_wakeup_granuality - o ile nowo obudzone zadanie musi mieć lepszy czas by wywłaszczyć aktualne, domyślnie 5ms.
sched_migration_cost - jeżeli średni czas działania obudzonego procesu i aktywnego jest mniejszy niż zadany parametr to do działania wybierany jest inne zadanie. Domyślna wartość 0,5ms. Żeby ten parametr działał musi być ustawiona zmienna WAKE_OVERLAP

W przypadku gdy wieloprocesorowych systemów planista może rozmieszczać zadania na różnych procesorach, wtedy używana jest zmienna:

sched_migration_cost - koszt migracji pomiędzy procesorami, (0,5ms domyślnie) jest używany do oszacowania, czy kod zadania jest jeszcze w pamięci podręcznej procesora, jeżeli czas działania zadania jest mniejszy niż zadana wartość, planista stara się nie zmieniać procesora.
sched_nr_migrate - maksymalna liczba zadań jaką planista obsługuje w czasie ładowania zrównoważonego.

Planista CFS daja możliwość kontrolowania zadań z klasy "real-time" z dokładnością do mikrosekund

sched_rt_runtime_us - maksymalny czas CPU jaki może użyty przez wszystkie zadania typu real-time. Domyślnie 1s. Po tym czasie zadanie musi czekać sched_rt_period_us czasu żeby byc ponownie wykonywane.
sched_rt_period_us - Planista CFS czeka tyle czasu zanim wykona zadnie ponownie, domyślnie (0.95 s)
sched_features - inne opcje dostrajania

Aktualne ustawienie innych atrybutów można znaleźć w /sys/kernel/debug/sched_features . Po zamontowanie debugfs

 # mount -t debugfs none /sys/kernel/debug

Nazwy z prefiksem NO_ oznaczają, że ta opcja nie jest włączona. Zmian można dokonywać poprzez:


		# echo FEATURE_NAME > sched_features 

		# echo NO_FEATURE_NAME > sched_features

Lista dostępnych opcji:

NEW_FAIR_SLEEPERS - dotyczy zadań pochodzących z kolejki uśpionych. Każde nowo obudzone zadanie otrzymuje wirtualny czas działania równy najmniejszemu czasowi z kolejki zadań. Jeżeli opcja jest ustawiona, to dodatkowo zmniejszamy wirtualny czas o sched_latency_ns. Jednak nowy wirtualny czas nie może być mniejszy niż ten przed uśpieniem.
NORMALIZED_SLEEPER - ma sens tylko w przypadku włączonej powyższej opcji. Oznacza, że sched_latency_ns podlega również normalizacji, zależnej od priorytetu
WAKE_UP_PREEMPT - oznacza, że nowo obudzone zadanie, zastępuje aktualnie wykonujące się. W przypadku wyłączenia tej opcji, zadanie nie może zostać wywłaszczone jeżeli nie wykorzysta całego time_slice. Co więcej, jeżeli opcja jest aktywna i w systemie jest tylko jedno zadanie wtedy planista będzie powstrzymywał się z wywołaniem procedury wyboru następnego zadania do czasu pojawienia się nowego zadania w kolejce.
START_DEBIT - parametr jest jest brany pod uwagę w czasie inicjalizacji wirtualnego czasu wykonania dla nowo tworzonego zadania. Jeżeli jest aktywna wówczas początkowy wirtualny czas działania jest zwiększany o time_slice, jaki otrzymało by zadanie.
SYNC_WAKEUPS - zezwala na synchroniczne budzenie zadań. Gdy włączony to planista obsługuje nowo obudzone przed aktualnym. Opcja WAKE_UP_PREEMPT musi być aktywna.
HRTICK - włącza i wyłącza zegar wysokiej rozdzielczości (high resolution timer)
DOUBLE_TICK - Gdy parametr jest ustawiony wtedy planista sprawdza czy zadanie ma być wywłaszczone przy przerwaniu pochodzącym od zegara wysokiej rozdzielczości oraz również zegara systemowego. W przeciwnym razie sprawdzenie odbywa się tylko po przerwaniu pochodzącemu od zegar wysokiej rozdzielczości (high resolution timer).
ASYM_GRAN - Gdy aktywna to sched_wakeup_granuality_ns jest normalizowana (w ten sam sposób jak wirtualny czas)

Testy

Opcje ustawione na moim laptopie (kernel 2.6.32-31 intel Core 2 Duo)


		# cat /sys/kernel/debug/sched_features | sed "s/ /\n/g" 

		FAIR_SLEEPERS 

		GENTLE_FAIR_SLEEPERS 

		NO_NORMALIZED_SLEEPER 

		START_DEBIT 

		WAKEUP_PREEMPT 

		ADAPTIVE_GRAN 

		ASYM_GRAN 

		NO_WAKEUP_SYNC 

		NO_WAKEUP_OVERLAP 

		NO_WAKEUP_RUNNING 

		SYNC_WAKEUPS 

		AFFINE_WAKEUPS 

		SYNC_LESS 

		NO_SYNC_MORE 

		NO_NEXT_BUDDY 

		LAST_BUDDY 

		CACHE_HOT_BUDDY 

		NO_ARCH_POWER 

		NO_HRTICK 

		NO_DOUBLE_TICK 

		LB_BIAS 

		LB_SHARES_UPDATE 

		ASYM_EFF_LOAD 

		OWNER_SPIN 

		NONIRQ_POWER 

		# sysctl -A | grep "sched" | grep -v "domain" 

		kernel.sched_child_runs_first = 0 

		kernel.sched_min_granularity_ns = 2000000 

		kernel.sched_latency_ns = 10000000 

		kernel.sched_wakeup_granularity_ns = 2000000 

		kernel.sched_shares_ratelimit = 500000 

		kernel.sched_shares_thresh = 4 

		kernel.sched_features = 0 

		kernel.sched_migration_cost = 500000 

		kernel.sched_nr_migrate = 32 

		kernel.sched_time_avg = 1000 

		kernel.sched_rt_period_us = 1000000 

		kernel.sched_rt_runtime_us = 950000 

		kernel.sched_compat_yield = 0

Najpierw postanowiłem sprawdzić użyteczność ustawiania jakichkolwiek opcji:


	# echo 0 > /proc/sys/kernel/sched_features 

	# for (( N=0; N < 10; N++ )); do ( while :; do :; done ) & done

Test polegał na uruchomieniu 10 procesów wykonujących nieskończoną pętlę. Okazało się że po 20 sekundach pracy jeden proces najbardziej uprzywilejowany wykonywał się o około 1sekundę dłużej niż najmniej uprzywilejowany.


	# top 

	  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND                                                                                        
 
	32139 kuba      20   0  6288 2256  316 R   24  0.1   0:22.82 bash 

	32135 kuba      20   0  6288 2252  312 R   19  0.1   0:22.83 bash 

	32140 kuba      20   0  6288 2256  316 R   19  0.1   0:23.07 bash 

	32142 kuba      20   0  6288 2256  316 R   19  0.1   0:22.44 bash 

	32136 kuba      20   0  6288 2256  316 R   19  0.1   0:22.30 bash 

	32137 kuba      20   0  6288 2256  316 R   19  0.1   0:22.22 bash 

	32138 kuba      20   0  6288 2256  316 R   19  0.1   0:22.23 bash 

	32141 kuba      20   0  6288 2256  316 R   19  0.1   0:22.89 bash 

	32143 kuba      20   0  6288 2256  316 R   19  0.1   0:22.52 bash 

	32144 kuba      20   0  6288 2256  316 R   19  0.1   0:22.79 bash 

	# killall bash

Przy standardowych ustawieniach.


	# echo 32611451 > /proc/sys/kernel/sched_features 

	# for (( N=0; N < 10; N++ )); do ( while :; do :; done ) & done 

	# top 

	 PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND                                                                                          

	32211 kuba      20   0  6288 2256  316 R   20  0.1   0:22.28 bash 

	32209 kuba      20   0  6288 2252  312 R   19  0.1   0:22.27 bash 

	32213 kuba      20   0  6288 2256  316 R   19  0.1   0:22.27 bash 

	32215 kuba      20   0  6288 2256  316 R   19  0.1   0:22.27 bash 
 
	32217 kuba      20   0  6288 2256  316 R   19  0.1   0:22.27 bash 

	32210 kuba      20   0  6288 2256  316 R   19  0.1   0:22.19 bash  

	32218 kuba      20   0  6288 2256  316 R   19  0.1   0:22.01 bash 

	32214 kuba      20   0  6288 2256  316 R   19  0.1   0:22.01 bash 

	32216 kuba      20   0  6288 2256  316 R   19  0.1   0:21.95 bash 
 
	32212 kuba      20   0  6288 2256  316 R   18  0.1   0:22.18 bash 

	# killall bash

Widzimy bardzo małe odchylenie rzędu 0,3sekundy. Następny test działał następująco. Pierwszy proces uruchamiał N procesów. Każdy wykonywał przez K sekund następującą pętlę (N, K parametry programu) 8milisekund pracuj i 1 milisekundę spij. Po zakończeniu każdy proces wypisywał ile razy udało mu się wykonać pętle.


	# gcc -o intr intr.c -lrt 

	#  ./intr 20 60 > out1 

	# echo 0 > /proc/sys/kernel/sched_features 
 
	#  ./intr 20 60 > out0

Przy standardowych ustawieniach różnica pomiędzy maksymalną a minimalną liczbą wykonany pętli wynosiła 9 obrotów (max 766) Przy wszystkich wyłączonych różnica 33, max 751. Po przeanalizowanie ustawień doszedłem do wniosku, że różnica może być spowodowana wyłączeniem opcji FAIR_SLEEPERS , faktycznie po analogicznych testach z opcją FAIR_SLEEPERS uzyskane wyniki bardzo niewiele odbiegały od tych z wszystkimi opcjami.

Źródła

http://www.fizyka.umk.pl/~jkob/prace-mag/cfs-tuning.pdf
Materiały z wykładu ZSO
Documentation/scheduler/sched-design-CFS.txt
Program intr

Janina Mincer-Daszkiewicz