The responsibility for running processes and threads includes deciding when to run which process or thread, called scheduling. Scheduling accommodates various requirements such as responsiveness, throughput, efficiency:
Responsiveness requires that a process reacts to asynchronous events within reasonable time. The asynchronous events may be, for example, a user input, where a prompt reaction is required to maintain interactivity, or a network request, where a prompt reaction is required to maintain quality of service.
Predictability requires that the operating system can provide guarantees on the behavior of scheduling.
Turnaround requires that scheduling minimizes the duration of each task.
Throughput requires that scheduling maximizes the number of completed tasks.
Efficiency requires that scheduling maximizes the resource utilization.
Fairness requires that the operating system can provide guarantees on the equal treatment of tasks with the same scheduling parameters.
Many of the requirements can conflict with each other. Imagine a set of short tasks and a single long task that, for sake of simplicity, do not contend for other resources than the processor. A scheduler that aims for turnaround would execute the short tasks first, thus keeping the average duration of each task low. A scheduler that aims for throughput would execute the tasks one by one in an arbitary order, thus keeping the overhead of context switching low. A scheduler that aims for fairness would execute the tasks in parallel in a round robin order, thus keeping the share of processor time used by each task roughly balanced.
When resolving the conflicts between the individual scheduling requirements, it helps to consider classes of applications:
An interactive application spends most of its time waiting for input. When the input does arrive, the application must react quickly. It is often stressed that a user of an interactive application will consider the application slow when a reaction to an input does not happen within about 150 ms. Fluctuations in reaction time are also perceived negatively.
A batch application spends most of its time executing internal computations in order to deliver an external output. In order to benefit from various forms of caching that happen within the hardware and the operating system, a batch application must execute uninterrupted for some time.
A realtime application must meet specific deadlines and therefore must execute long enough and often enough to be able to do so.
When faced with the conflict between the individual scheduling requirements, the operating system would therefore lean towards responsiveness for interactive applications, efficiency for batch applications, predicability for realtime applications.
Na stavovém diagramu je pak zjevně vidět, co je úlohou plánování. Je to rozhodnout, kdy a který proces přepnout ze stavu "ready to run" do stavu "running" a zpět. Pokud není žádný proces ve stavu "ready to run", spouští se umělý idle process alias zahaleč.
HLT
References.
James Dabrowski, Ethan Munson: Is 100 Milliseconds Too Fast ?
Také cyklické plánování, FIFO, prostě spouštět procesy jeden po druhém. Otázkou je délka kvanta v poměru k režii přepnutí kontextu, příliš krátké kvantum snižuje efektivitu, příliš dlouhé kvantum zhoršuje responsiveness.
Processes are assigned static priorities, the process with the highest priority is scheduled. Either constant quantum is used or shorter quantum is coupled with higher priority and vice versa.
Confusion can arise when comparing priorities, for numerically lower priority values are often used to meant semantically higher priorities. In this text, the semantic meaning of priorities is used.
Processes are assigned initial priorities, actual priorities are calculated from the initial priorities and the times recently spent executing, the process with the highest actual priority is scheduled.
Pokus o dobrou podporu dávek, spouští se ta co trvá nejkratší dobu, tím se dosáhne průměrně nejkratšího času do ukončení dávky, protože pokud čeká více dávek, jejich časy ukončení se postupně přičítají, a tak je dobře začít od nejkratších časů. Toto se dá zčásti použít i na interaktivní procesy, v situaci kdy více uživatelů na více terminálech čeká na odezvu, spustí se ten proces, kterému bude doručení odezvy trvat nejméně dlouho, tím se dosáhne minimální average response time. Nepříjemné je, že vyžaduje vizionářství, řeší se třeba statisticky.
Také guaranteed share scheduling, procesům se zaručuje jejich procento ze strojového času, buď každému zvlášť nebo po skupinách nebo třeba po uživatelích
Procesy mají deadlines do kdy musí něco udělat, plánuje se vždy proces s nejbližší deadline. Deadlines se zpravidla rozdělují do hard realtime deadlines , ty jsou krátké a nesmí se prošvihnout, soft realtime deadlines , ty jsou krátké a občas se prošvihnout můžou dokud bude možné zaručit nějaký statistický limit prošvihnutí, timesharing deadlines , ty v podstatě nemají pevný časový limit ale měly by se do někdy stát, batch deadlines , ty mají limity v hodinách a obvykle s nimi nebývají problémy.
Nejprve starší scheduler z UNIXu, dynamické priority, nepreemptivní kernel. Priorita je číslo 0-127, nižší číslo vyšší priorita, default 50. Každý proces má current priority 0-127, pro kernel rezervováno 0-49, user priority 0-127, processor usage counter 0-127 a nice factor 0-39, ovlivněný příkazem nice. Current priority v aplikaci je rovna user priority, v kernelu se nastaví podle toho, na co proces čeká, například po čekání na disk se nastaví na 20, čímž se zaručí, že proces po ukončení čekání rychle vypadne z kernelu. Processor usage count se inkrementuje při každém kvantu spotřebovaném procesem, zmenšuje se podle magické formule jednou za čas, třeba na polovinu každou vteřinu, nebo podle load average aby při zatíženém procesoru processor usage count neklesal moc rychle. Load je průměrný počet spustitelných procesů v systému za nějaký čas. User priority se pak vypočítá jako default priority + processor usage counter / 4 + nice factor * 2.
Nevýhody. První, does not scale well. Pokud běží hodně procesů, roste režie na přepočítávání priorit. Další, neumí nic garantovat, zejména ne response time nebo processor share. A závěrem, aplikace mohou priority ovlivňovat pouze přes nice factor, který nenabízí zrovna moc advanced control.
Podobný je System V Release 4 scheduler. Ten má jako jádro scheduleru fronty ready to run" procesů podle priority 0-160 a rutinu pro plánování, která klasicky vybere proces nejvyšší priority, round robin na stejné prioritě. Každý proces patří do nějaké třídy priorit, která má na starosti všecha rozhodnutí ohledně přidělění priority a délky kvanta. By default jsou k dispozici tři třídy priorit, timesharing, system a realtime:
Timesharing. Používá priority 0-59, procesu se zvyšuje priorita pokaždé když na něco čeká nebo když dlouho trvá než spotřebuje své kvantum, priorita se snižuje pokaždé když proces spotřebuje své kvantum. Přesný způsob změny priority se určuje podle tabulky, jako příklad proces priority 40 spadne po spotřebování kvanta na 30, po ukončení čekání nebo pokud proces nespotřebuje kvantum do 5 vteřin, priorita naopak vyleze na 50 (čekající proces dostane priority 59, změna v normální prioritě se objeví po návratu do user mode). K výsledku se ještě přidává nice value, tím je priorita v user mode určena jednak systémem počítanou prioritou a dvak nice value. Podle systémem počítané priority se udržuje také délka kvanta, nižší priority mají delší kvantum (protože se čeká, že tak často nepoběží, a tak když už se dostanou na řadu, tak ať něco udělají).
System. Používá priority 60-99 pro procesy běžící v kernelu. Tato třída je interní systémová, nečeká se že by do ní hrabali useři, běží v ní třeba page daemon. Proces, který při volání kernelu obdrží kritické resources, dostane dočasně také priority 60-99.
Realtime. Používá priority 100-159, priorita procesu a přidělované kvantum se nastavuje syscallem priocntl a od okamžiku nastavení se nemění. Bordel je v tom, že realtime priority může být větší než system priority, tedy občas by bylo potřeba přerušit kernel. To se ale normálně nedělá, protože preemptivní kernel by byl složitý, procesy se přepínají nejčastěji při opouštění kernel mode, kdy se zkontroluje flag "runrun" indikující nutnost přepnout kontext. Jako řešení se k flagu "runrun" přidá ještě flag "kprunrun" indikující nutnost přenout kontext uvnitř kernelu, a definují se body, kdy je i v kernelu bezpečné přepnout kontext. V těchto bodech se pak testuje "kprunrun". Výsledkem je zkrácení prodlev před rozběhnutím "ready to run" realtime procesů.
Také se počítá s tím, že člověk si bude moci přidávat vlastní třídy priorit. Každá třída implementuje 7 obslužných rutin, jsou to CL_TICK volaná z clock interrupt handleru, CL_FORK a CL_FORKRET pro inicializaci nového procesu, CL_ENTERCLASS a CL_EXITCLASS pro obsluhu situací, kdy proces vstoupí do třídy nebo ji opustí, CL_SLEEP volaná když proces udělá sleep, CL_WAKEUP volaná když proces opustí sleep. Přidání vlastní třídy znamená napsat těchto 7 rutin a přeložit kernel.
Výhoda popsaného scheduleru spočívá jednak v tom, že nikdy nepřepočítává žádné velké seznamy priorit, dvak v tom, že umí podporovat realtime procesy. Pravděpodobně nejznámějším systémem s tímto schedulerem je Solaris, ten má několik drobných změn. Solaris 7 nabízí uživatelům timesharing, interactive a realtime classes, podobně jak bylo popsáno výše, až na to že kernel je mostly preemptive, což zlepšuje responsiveness realtime procesů.
Solaris 7 má příkaz "dispadmin", kterým se dají vypsat tabulky se scheduling parametry. Parametry pro timesharing procesy jsou ve formě tabulky s délkou kvanta (200ms pro prioritu 0, 20ms pro prioritu 59), priority po vypršení kvanta (vždy o 10 menší), priority po sleepu (50 + priority/10 pro většinu priorit), maximální délka starvation (1 vteřina pro všechny priority) a priorita při překročení této délky (50 + priority/10 pro většinu priorit). Parametry pro interactive procesy jsou stejné jako pro timesharing procesy. Parametry pro realtime procesy jsou ve formě tabulky s délkou kvanta (1 sekunda pro prioritu 0, 100ms pro prioritu 59). Admin může tyto tabulky měnit.
Třídy interactive a timesharing sdílejí tutéž tabulku parametrů, což by naznačovalo, že sdílejí i tentýž plánovací algoritmus, ale nemusí to být pravda. Letmá měření žádný rozdíl neukázala, takže je možné, že TS a IA třídy existují kvůli větší flexibilitě (každé zvlášt se dá nastavit rozsah user priorit) a by default jsou opravdu stejné.
Jako zajímavost, Solaris 7 nabízí ještě volání, které umožnuje lightweight procesu požádat kernel, aby mu dočasně neodebral procesor. To se hodí třeba při implementaci spinlocků v user mode. Detaily viz manpage schedctl_init.
In the 2.4.X series of Linux kernels, the scheduler decided what process to run based on a proprietary metric called goodness value, simply by picking the process with the highest goodness value. The scheduler distinguished time sharing and realtime scheduling policies and used different goodness value calculation depending on the policy used by each process.
Under the realtime scheduling policy, each process has a priority value ranging from 1 (low) to 99 (high). The goodness value was calculated as 1000 plus the process priority. This calculation made the scheduler select the realtime process with the highest priority ahead of any other realtime or time sharing process. Depending on whether the scheduling policy was SCHED_RR or SCHED_FIFO, the scheduler either assigned the process a quantum or let the process run with no quantum limit. Naturally, this only made any difference when there were more realtime processes with the same priority.
Under the time sharing scheduling policy, each process has a nice value ranging from -20 (high) to 19 (low). The goodness value was equal to the quantum left to the process in the current scheduling cycle, with the entire range of nice values roughly corresponding to quanta from 210 ms for nice -20 to 10 ms for nice 19. When all processes consumed their quanta, a new scheduling cycle was started and new quanta were assigned to the processes.
Windows uses a priority based scheduler. The priority is an integer from 0 to 31, higher numbers denoting higher priorities. The range of 1-15 is intended for standard applications, 16-31 for realtime applications, memory management worker threads use priorities 28 and 29. The priorities are not assigned to threads directly. Instead, the integer priority is calculated from the combination of one of seven relative thread priorities and one of four process priority classes:
| Idle | Normal | High | Realtime | |
|---|---|---|---|---|
| Idle | 1 | 1 | 1 | 16 |
| Lowest | 2 | 6 | 11 | 22 |
| Below Normal | 3 | 7 | 12 | 23 |
| Normal | 4 | 8 | 13 | 24 |
| Above Normal | 5 | 9 | 14 | 25 |
| Highest | 6 | 10 | 15 | 26 |
| Time Critical | 15 | 15 | 15 | 31 |
The priorities are further adjusted. Threads of the Idle, Normal and High priority class processes receive a priority boost on end of waiting inside kernel and certain other events, and a priority drop after consuming the entire allocated quantum. Threads of the Normal priority class processes receive a priority boost after their window is focused. Similar adjustment is used for process affinity and priority inheritance.
The scheduler always runs the thread with the highest priority. Multiple threads with the same priority are run in a round robin fashion. The time quanta are fixed at around 120 ms in server class Windows versions, and variable from around 20 ms for background processes to around 60 ms for foreground processes in desktop class Windows versions.
Administrative privileges are required to set priorities from the realtime range. To avoid the need for administrative privileges for running multimedia applications, which could benefit from realtime priorities, Windows Vista introduces the Multimedia Class Scheduler Service. Processes can register their threads with the service under classes such as Audio or Games, and the service takes care of boosting the priority of the registered threads based on predefined registry settings.
Operační systém Nemesis, Cambridge University 1994-1998, cílem je podpora Quality of Service pro distributed multimedia applications. V Nemesis se plánují domény, kernel přidělí CPU doméně pomocí activation, což není nic jiného než upcall rutiny specifikované v příslušném domain control bloku. Výjimku tvoří situace, kdy byla doméně odebrána CPU dříve, než ta indikovala připravenost na další activation, v takovém případě se pokračuje v místě odebrání CPU. Krom stavu ready to run může doména ještě čekat na event, což není nic jiného než asynchronně doručovaná zpráva obsahující jeden integer.
Každá doména si řekne o processor share, který chce, ve formě čísel slice a period, obě v nějakých timer ticích. Systém pak zaručuje, že v každé periodě dostane aplikace nejméně slice tiků, s podmínkou, že suma všech slice / period v systému je menší než 1 (jinak by nebylo dostatek CPU času na uspokojení všech domén).
Interní je scheduler založen na earliest deadline first algoritmu. Udržuje se fronta domén, které ještě nebyly v dané periodě uspokojeny, seřazná podle času konce této periody, a fronta domén, které již uspokojeny byly, seřazená podle času začátku nové periody. Scheduler vždy spustí první doménu ve frontě neuspokojených domén, pokud je tato fronta prázdná, pak náhodnou doménu ve frontě uspokojených domén. Následující scheduler action se naplánuje na čas nejbližší deadline nebo do konce slice, whichever comes sooner.
Mimochodem, původní popis algoritmu nezmiňoval scheduler action při vyčerpání slice, což se pak projevovalo jednak v anomáliích při rozjezdu algoritmu, dvak v neřízeném rozdělování přebytečného času procesoru. Divné.
Příklad, tři procesy A B C, A chce share 1 per 2, B chce share 1 per 5, C chce share 2 per 10. Tabulka, řádky čas, sloupce zbývající slices a period deadlines pro A B C.Jako detaily, předpokládá se stabilní běh systému a nulová režie scheduleru. Další drobnost, domain si může říci, zda chce nebo nechce dostávat přebytečný čas procesoru. Mezi ty domény, které ho chtějí dostávat, se přebytečný čas procesoru rozděluje náhodně, s kvantem nějakých 100 us, nic lepšího zatím nevymysleli a prý to stačí.
Jeden detail, co dělat s doménami, které čekaly na event? Prostě se nacpou zpátky do fronty neuspokojených domén jako kdyby se nově zařazovaly, přinejhorším tím budou spotřebovávat přebytečný čas procesoru. Pro domény, kterým stačí jen malé procento času procesoru, ale potřebují reagovat rychle, se dá zadat ještě latency hint, ten se použije pro výpočet deadline místo periody v případě, že doména čekala déle než svou periodu. Použití pro interrupt handling.
Interrupt handling je neobvyklý, zato však odstraňuje jeden ze základních problémů dosud zmíněných schedulerů, totiž že část aktivit spojená s devices je v podstatě plánovaná signály od hardware a nikoliv operačním systémem. Když přijde interrupt, jeho handler v kernelu jej pouze zamaskuje a pošle event doméně zodpovědné za jeho obsluhu. Předpokládá se, že tato doména čeká na event, scheduler jí tedy v souladu s jejími parametry naplánuje, doména obslouží device a znovu povolí interrupt. Pokud pak systém nestíhá, není ucpaný interrupty, ale prostě vyřídí to co stíhá a zbytek interruptů ignoruje. Drivery mohou instalovat handlery v kernelu.
Téma nestíhání serverů a driverů je ještě o něco hlubší. Nad kernel schedulerem totiž má běžet ještě Quality of Service monitor aplikace, který umí detekovat situace, kdy server nebo driver nestíhá odpovídat na dotazy. Processor share serveru se udržuje dostatečně vysoký na to, aby stíhal odpovídat, to je vždy možné protože s rostoucím share se blíží extrém, kdy server sežere veškerý čas procesoru a nepoběží driver, který mu dodává data jež ho zatěžují. Processor share driveru se udržuje dostatečně vysoký na zpracování příchozích dat, nejvýše však takový, aby se kvůli němu nemusel snižovat processor share serveru. A tím je vystaráno, počítač dělá co stihne, nadbytečný traffic prostě ignoruje a nezahltí se.
Ještě drobný detail o tom, proč se domény aktivují tak divně od stejného místa. Počítá se s tím, že každá doména bude mít v sobě něco jako user threads, aktivace domény pak spustí user scheduler, který si skočí na který thread uzná za vhodné. Systém nabízí doménám možnost specifikovat, kam se má při preempci uložit kontext procesoru, předpokládá se, že každá doména bude zvlášť ukládat kontexty jednotlivých threadů.
Plánování začne být ještě o něco zajímavější v multiprocesorových systémech. Některé problémy už byly naznačené, totiž multiprocesorové plánování by nemělo být pouhým rozšířením singleprocesorového, které má jednu ready frontu a z ní posílá procesy na všechny procesory. Proč vlastně ?
Důvod spočívá v tom, jak vypadá multiprocesorový hardware. I u velmi těsně vázaného systému mají procesory lokální informace nasbírané za běhu procesu, jako třeba cache překladu adres, memory cache, branch prediction a podobně. Z toho je snadno vidět, že výkonu systému prospěje, pokud scheduler bude plánovat tytéž procesy, případně thready téhož procesu, na stále stejné procesory. Tomu se někdy říká processor affinity.
Již zmíněnými příklady byly Solaris, Linux, a Windows NT, které na multiprocesorovém hardware zohledňují processor affinity a mírně se snaží plánovat stejné procesy na stejné procesory. Další by byl třeba Mach.
Samozřejmě zůstávají další problémy, jeden z nich je například sdílení ready fronty. Čím více procesů sdílí libovolný prostředek, tím více na něm budou čekat, a ready frontu sdílí každý procesor a kernel do ní hrabe každou chvíli. Drobným vylepšením je například definování local a global ready front s rozlišením, kdy se bude sahat do které. Toto rozlišení může být různé, například realtime procesy v globální frontě a ostatní v lokálních, nebo dynamické přesouvání mezi globální a lokální frontou podle zatížení procesoru.
Ještě zajímavější je scheduling na loosely coupled hardware, kde se například nesdílí paměť. Tam se už musí zohledňovat i cena migrace procesu, cena vzdáleného přístupu k prostředkům a podobně, ale to teď necháme.
Mach plánuje na úrovni threadů. Základní princip plánování je stále stejný, priority a zohlednění CPU usage, zaměřme se na multiprocessor support.
Za prvé, Mach nemá cross processor scheduler events. Co to je napovídá název — pokud se na některém procesoru objeví událost, která povolí běh threadu s prioritou vyšší než je priorita nějakého jiného threadu na jiném procesoru, tento druhý thread se nepřeruší, ale poklidně doběhne své kvantum, než se scheduler dostane ke slovu.
Za druhé, Mach zavádí processor sets, množiny procesorů určených k vykonávání threadů. Každý thread má přidělen jeden processor set, na kterém je plánován, processor sets definuje a přiděluje admin. Tak je možné vyhradit například rychlé procesory na realtime úlohy, či procesory se speciálním hardware na úlohy, které jej využijí. Procesory sice mohou patřit pouze do jednoho setu, ale za běhu systému mohou mezi sety cestovat.
Handoff scheduling.
The early 2.6 series of kernels uses a scheduler that provides constant time scheduling complexity with support for process preemption and multiple processors.
The scheduler keeps a separate pair of an active and an expired queue for each processor and priority, the active queue being for processes whose quantum has not yet expired, the expired queue being for processes whose quantum has already expired. For priorities from 1 to 140, this makes 280 queues per processor. The scheduler finds first non empty queue pair, switches the active and expired queues when the active queue is empty, and schedules the first process from the active queue. The length of the quantum is calculated linearly from the priority, with higher quanta for lower priority.
An interactivity metric is kept for all processes as a ratio of the time spent calculating to the time spent waiting for input or output. Processes with the priority range between 100 and 140, which is reserved for user processes, get their priority adjusted so that processes that calculate a lot are penalized and processes that wait for input or output a lot are rewarded. Processes that wait for input or output a lot are never moved from the active to the expired queue.
An extra kernel thread redistributes processes between processors.
References.
Rohit Agarwal: Process Scheduler For Kernel 2.6.x
The late 2.6 series of kernels distinguish Completely Fair Scheduler (CFS) and Real Time (RT) classes, handled by separate scheduler modules with separate per processor run queue structures.
The scheduler calls the put_prev_task function of the appropriate module to put a previously scheduled process among other runnable processes, and the pick_next_task function of the highest priority module to pick the next scheduled process from other runnable processes.
The per processor structure of the RT class scheduler contains an array of queues, one for each process priority.
The pick_next_task function picks the process with the highest priority.
The quantum is set to 100 ms for the SCHED_RR scheduling policy and to infinity for the SCHED_FIFO scheduling policy.
The per processor structure of the CFS class scheduler contains a tree of processes, indexed by a virtual time consumed by each process.
The pick_next_task function achieves fairness by picking the process with the least consumed time, maintaining overall balance in the consumed times.
Rather than setting a fixed quantum, the scheduler is configured to rotate all ready processes within a given time period and calculates the quantum from this time period and the number of ready processes.
The virtual time consumed by each process is weighted by the nice value. A difference of one nice point translates into a difference of 10% processor time. After the quantum expires, the consumed time is adjusted accordingly. Processes that become ready are assigned the minimum of the virtual consumed times, unless they become ready after a short sleep, in which case their virtual consumed time is preserved.
An extra kernel thread redistributes processes between processors.
Multiple advanced features control the scheduler behavior on groups of processes. The groups can be defined using the control group mechanism, which is exported through a virtual filesystem. There can be multiple control group hierarchies exported through multiple virtual filesystems. Each hierarchy is associated with a particular controller, the scheduler being one. Individual groups are created as directories in the virtual filesystem. Group membership and controller parameters are set through files.
> tree -d /sys/fs/cgroup /sys/fs/cgroup |-- blkio |-- cpu | `-- system | |-- acpid.service | |-- chronyd.service | |-- crond.service | |-- dbus.service | |-- httpd.service | |-- mdmonitor.service ... | |-- sshd.service | |-- udev.service | `-- upower.service |-- devices |-- memory ...
Each scheduler control group can define its processor share in the cpu.shares tunable.
The shares are dimensionless numbers that express processor usage relative to other control groups.
Processor usage can also be regulated in absolute rather than relative terms.
The cpu.cfs_period_us and cpu.cfs_quota_us tunables set the maximum processor usage per period for the CFS scheduler, the cpu.rt_period_us and cpu.rt_runtime_us tunables provide similar feature for the RT scheduler.
The processors in a multiprocessor system can be grouped using the cpuset control groups. Each cpuset control group contains a subset of processors of its parent, the top level group has all processors. Assignment of processes to processors can be restricted by placing them in a particular cpuset. Load balancing within a cpuset can be disabled entirely or adjusted so that immediate load balancing is limited. Immediate load balancing takes place when there are no ready processes available to a particular processor.