Jak Linux naprawdę daje procesowi CPU

Runnable nie znaczy running

Jeżeli proces lub wątek ma pracę do wykonania i nie czeka na I/O, lock ani timer, może być w stanie runnable.

W dużym uproszczeniu:

runnable -> running

running oznacza, że task aktualnie wykonuje instrukcje na CPU.

runnable oznacza:

jest gotowy do wykonania,
ale może jeszcze czekać na procesor

To rozróżnienie jest istotne.

Na jednym logicznym CPU w danej chwili może wykonywać się tylko jeden task.

Jeżeli mamy:

CPU 0

task A - running
task B - runnable
task C - runnable

to B i C są gotowe do pracy, ale muszą czekać, aż scheduler przydzieli im CPU.

Scheduler wybiera kolejny task

Linux utrzymuje dla CPU struktury schedulera zawierające taski gotowe do wykonania.

Uproszczony obraz:

CPU 0

running:
    A

runnable:
    B
    C
    D

Po pewnym czasie scheduler może zdecydować:

A -> B

Stan zmienia się wtedy mniej więcej tak:

A: running  -> runnable
B: runnable -> running

Następuje context switch i CPU zaczyna wykonywać kod procesu B.

Później może zostać wybrany C, ponownie A itd.

A -> B -> C -> A -> D -> ...

W ten sposób wiele procesów może współdzielić jeden procesor.

CPU time

Jeżeli proces wykonywał się przez 10 ms, zużył około 10 ms CPU time.

To niezależne od tego, ile czasu minęło zegarowo.

Przykład:

0 ms      proces staje się runnable
0-20 ms   czeka na CPU
20-30 ms  wykonuje się
30 ms     kończy pracę

Wall-clock time:

30 ms

CPU time:

10 ms

Pozostałe 20 ms proces był gotowy do wykonania, ale nie dostał procesora.

To bardzo ważne rozróżnienie:

wall-clock time != CPU time

CPU time mierzy czas rzeczywistego wykonywania kodu na procesorze.

Co się dzieje, gdy procesów jest więcej niż CPU

Załóżmy jeden logiczny CPU i dwa procesy:

A
B

Oba są CPU-bound i cały czas mają pracę.

Każdy z nich chciałby wykonywać się bez przerwy.

Nie jest to możliwe, bo dostępny jest tylko jeden CPU.

Scheduler musi więc dzielić czas procesora:

time ------------------------------------------------>

CPU:
| A | B | A | B | A | B | A | B |

Każdy proces przez część czasu jest running, a przez część runnable.

W dłuższym okresie mogą otrzymać mniej więcej po połowie CPU time.

Jeżeli obserwujemy okres jednej sekundy:

A CPU time ≈ 500 ms
B CPU time ≈ 500 ms

To nie znaczy, że każdy dostał „połowę fizycznego rdzenia”.

Dostali naprzemiennie czas wykonania na tym samym logicznym CPU.

A jeśli mamy kilka CPU?

Na maszynie wieloprocesorowej kilka tasków może wykonywać się równolegle.

Przykład:

CPU 0 -> task A
CPU 1 -> task B
CPU 2 -> task C
CPU 3 -> task D

Jeżeli pojawi się piąty runnable task:

task E

nie może wykonywać się równolegle z pozostałą czwórką.

Musi poczekać, aż scheduler udostępni mu któryś CPU.

Czyli przy czterech logicznych CPU:

4 runnable tasks  -> wszystkie mogą być running
5 runnable tasks  -> co najmniej jeden musi czekać
20 runnable tasks -> większość będzie w danej chwili czekać

Sam fakt, że proces jest runnable, nie gwarantuje natychmiastowego wykonania.

Thready są schedulerowane osobno

Scheduler nie patrzy wyłącznie na proces jako całość.

W praktyce schedulowane są taski, więc wielowątkowy proces może wykonywać kilka wątków jednocześnie.

Proces:

app
├── thread A
├── thread B
├── thread C
└── thread D

Na czterech CPU możemy mieć:

CPU 0 -> thread A
CPU 1 -> thread B
CPU 2 -> thread C
CPU 3 -> thread D

Taki proces może w ciągu jednej sekundy zużyć około:

4 CPU-seconds

bo cztery jego wątki wykonywały się równolegle przez sekundę.

Dlatego wartość typu:

400% CPU

dla procesu wielowątkowego nie jest niczym dziwnym w narzędziach, które przyjmują 100% jako pełne wykorzystanie jednego logicznego CPU.

Scheduler nie „uruchamia procesu raz”

Proces nie dostaje CPU raz na zawsze.

Scheduler podejmuje decyzje stale.

Typowy CPU-bound task może wyglądać tak:

running
   |
   v
runnable
   |
   v
running
   |
   v
runnable
   |
   v
running

Task jest wielokrotnie zdejmowany z CPU i ponownie na niego wpuszczany.

Z punktu widzenia aplikacji wykonywanie wygląda ciągle.

Z punktu widzenia kernela jest to seria fragmentów CPU time rozdzielanych pomiędzy wiele tasków.

Najważniejszy model mentalny

Mechanizm można sprowadzić do:

task ma pracę
    |
    v
runnable
    |
    v
scheduler wybiera task
    |
    v
running
    |
    v
task zużywa CPU time

Jeżeli dostępnych CPU jest więcej niż runnable tasków, task zwykle może zostać wykonany szybko.

Jeżeli runnable tasków jest więcej niż dostępnego CPU, część z nich musi czekać.

I to jest fundament całej dalszej rozmowy o CPU:

proces nie posiada procesora

proces dostaje od schedulera odcinki czasu,
w których może wykonywać instrukcje

Dopiero na tym mechanizmie budowane są wszystkie wyższe warstwy kontroli CPU.