Brain Fuck Scheduler

Brain Fuck Scheduler
Utvecklare	Con Kolivas
Slutlig utgåva	0,512 / 3 oktober 2016 ; för 6 år sedan
Skrivet i	C
Operativ system	Linux
Licens	GNU GPL
Hemsida	kärna .kolivas .org

Placeringen av processplanerare i en förenklad struktur av Linux-kärnan

The Brain Fuck Scheduler ( BFS ) är en processplanerare designad för Linux-kärnan i augusti 2009 som ett alternativ till Completely Fair Scheduler (CFS) och O(1)-schemaläggaren . BFS skapades av en erfaren kärnprogrammerare Con Kolivas .

Målet med BFS, jämfört med andra schemaläggare, är att förse en schemaläggare med en enklare algoritm , som inte kräver justering av heuristik eller inställningsparametrar för att skräddarsy prestanda till en specifik typ av beräkningsarbetsbelastning . Kolivas hävdade att dessa avstämbara parametrar var svåra för den genomsnittliga användaren att förstå, särskilt när det gäller interaktioner av flera parametrar med varandra, och hävdade att användningen av sådana inställningsparametrar ofta kan resultera i förbättrad prestanda i en specifik riktad typ av beräkning, till priset av sämre prestanda i det allmänna fallet. BFS har rapporterats förbättra lyhördheten på stationära Linux-datorer med färre än 16 kärnor .

Kort efter introduktionen skapade den nya schemaläggaren rubriker inom Linux-communityt och dök upp på Slashdot , med recensioner i Linux Magazine och Linux Pro Magazine . Även om det har varit olika recensioner av förbättrad prestanda och lyhördhet, hade Con Kolivas inte för avsikt att BFS skulle integreras i huvudlinjekärnan.

Teoretisk design och effektivitet

2009 introducerades BFS och hade ursprungligen använt en dubbellänkad listdatastruktur , men datastrukturen behandlas som en kö . Uppgiftsinsättning är $O(1)$ . Uppgiftssökning för nästa uppgift att utföra är $O(n)$ i värsta fall. Den använder en enda global körkö som alla processorer använder. Uppgifter med högre schemaläggningsprioriteringar utförs först. Uppgifterna ordnas (eller distribueras) och väljs baserat på den virtuella deadline-formeln i alla policyer förutom realtids- och isokronprioritetsklasserna.

Utförandebeteendet är fortfarande en viktad variant av Round-Robin Scheduler, särskilt när uppgifter har samma prioritet under den isokrona policyn. Det användarinställbara round robin-intervallet ( tidssnitt ) är 6 millisekunder som standard, vilket valdes som det minimala jitter strax under detekterbart av människor. Kolivas hävdade att allt under 6 ms var meningslöst och allt över 300 ms för round robin timeslice är fruktlöst när det gäller genomströmning. Denna viktiga inställning kan skräddarsy round robin-schemaläggaren som en avvägning mellan genomströmning och latens. Alla uppgifter får samma tidssegment med undantag för realtids-FIFO som antas ha en oändlig tidsdel.

Kolivas förklarade att anledningen till att han valde att gå med den dubbellänkade listan mono-runqueue än multi-runqueue (round robin) prioritetsmatrisen per CPU som användes i hans RDSL-schemaläggare var för att underlätta rättvisa bland scenariot med flera CPU och ta bort komplexitet som varje runqueue i ett multi-runqueue-scenario var tvungen att upprätthålla sina egna latenser och [uppgifts] rättvisa. Han hävdade att deterministiska latenser garanterades med BFS i hans senare iteration av MuQSS. Han upptäckte också möjliga problem med låskonflikter (relaterat till ändring, borttagning, skapande av uppgiftsnoddata) med ökande CPU:er och overhead för $O(\log n)$ nästa uppgift för exekveringssökning. MuQSS försökte lösa dessa problem.

Kolivas ändrade senare designen till en överhoppningslista i v0.480-versionen av BFS 2016. Den här gången förändrade detta effektiviteten hos schemaläggaren. Han noterade $O(\log n)$ uppgiftsinfogning, $O(1)$ uppgiftssökning; $O(k)$ , med $k\leq 16$ , för borttagning av uppgift.

Virtuell deadline

Den virtuella deadline-formeln är en framtida deadline-tid som är den skalade round robin-tidsdelen baserat på den fina nivån som kompenseras av den aktuella tiden (i niffy-enheter eller nanosekund- jiffies , en intern kärntidsräknare). Den virtuella deadline föreslår bara beställningen men garanterar inte att en uppgift kommer att köras exakt på det framtida schemalagda niffy.

Först skapas en uppslagstabell för prio-förhållanden. Den bygger på en rekursiv sekvens. Den ökar med 10 % för varje trevlig nivå. Det följer ett paraboliskt mönster om det är grafiskt, och de snyggade uppgifterna fördelas som en rörlig kvadratfunktion från 0 till 39 (motsvarande från högsta till lägsta trevliga prioritet) som domän och 128 till 5089 som intervall. Den rörliga delen kommer från t i den virtuella deadline-formeln som Kolivas antydde.

g(0) = 128 g(i) = INT( g(i-1)*11/10 )

Index	Täljare
0	128
1	140
2	154
3	169
4	185
5	203
6	223
7	245
8	269
9	295
10	324
11	356
12	391
13	430
14	473
15	520
16	572
17	629
18	691
19	760
20	836
21	919
22	1010
23	1111
24	1222
25	1344
26	1478
27	1625
28	1787
29	1965
30	2161
31	2377
32	2614
33	2875
34	3162
35	3478
36	3825
37	4207
38	4627
39	5089

Uppgiftens nice -to-index mappningsfunktion f(n) mappas från nice −20...19 till index 0...39 för att användas som indata till prio ratio lookup-tabellen. Denna mappningsfunktion är TASK_USER_PRIO() i sched.h i kärnhuvudet. Den interna kärnimplementeringen skiljer sig något med intervallet mellan 100 och 140 statisk prioritet men användarna kommer att se det som -20...19 trevligt.

Trevlig	Index
−20	0
−19	1
−18	2
−17	3
−16	4
−15	5
−14	6
−13	7
−12	8
−11	9
−10	10
−9	11
−8	12
−7	13
−6	14
−5	15
−4	16
−3	17
−2	18
−1	19
0	20
1	21
2	22
3	23
4	24
5	25
6	26
7	27
8	28
9	29
10	30
11	31
12	32
13	33
14	34
15	35
16	36
17	37
18	38
19	39

Den virtuella deadline är baserad på denna exakta formel:

T = 6 N = 1<<20 d(n,t) = t + g(f(n)) * T * (N/128)

Alternativt

{\mathtt {d(n,t)={\frac {g(f(n))}{128} }*T*N+t}}

där d(n,t) är den virtuella deadline i u64 heltal nanosekunder som en funktion av nice n och t som är den aktuella tiden i niffies, g(i) är prio ratio-tabelluppslagningen som en funktion av index, f(n) ) är uppgiftens nice-to-index mappningsfunktion, T är round robin-tidssnittet i millisekunder, N är en konstant på 1 millisekund i termer av nanosekunder som en latensreducerande approximation av omvandlingsfaktorn på $\mathrm {\frac {10^{9}ns}{10^{3}ms}}$ men Kolivas använder en bas 2 konstant N med ungefär den skalan. Mindre värden på d betyder att den virtuella deadline är tidigare motsvarande negativa fina värden. Större värden på d indikerar att den virtuella deadline skjuts tillbaka senare motsvarande positiva fina värden. Den använder denna formel närhelst tidsintervallet löper ut.

128 i bas 2 motsvarar 100 i bas 10 och möjligen en "pseudo 100". 115 i bas 2 motsvarar 90 i bas 10. Kolivas använder 128 för "snabba skift ", som i division är höger skift bas 2.

Trevlig	Virtuell deadline i tidsintervall i förhållande till t	Virtuell deadline i exakta sekunder i förhållande till t
−20	1.0	0,006
−19	1,09	0,006562
−18	1.2	0,007219
−17	1.3	0,007922
−16	1.4	0,008672
−15	1.5	0,009516
−14	1.7	0,010453
−13	1.9	0,011484
−12	2.1	0,012609
−11	2.3	0,013828
−10	2.5	0,015187
−9	2.7	0,016688
−8	3.0	0,018328
−7	3.3	0,020156
−6	3.6	0,022172
−5	4.0	0,024375
−4	4.4	0,026812
−3	4.9	0,029484
−2	5.3	0,032391
−1	5.9	0,035625
0	6.5	0,039188
1	7.1	0,043078
2	7.8	0,047344
3	8.6	0,052078
4	9.5	0,057281
5	10.5	0,063000
6	11.5	0,069281
7	12.6	0,076172
8	13.9	0,083766
9	15.3	0,092109
10	16.8	0,101297
11	18.5	0,111422
12	20.4	0,122531
13	22.4	0,134766
14	24.7	0,148219
15	27.1	0,163031
16	29,8	0,179297
17	32,8	0,197203
18	36.1	0,216891
19	39,7	0,238547

Schemaläggningspolicyer

BFS använder schemaläggningsprinciper för att bestämma hur mycket av CPU-uppgifterna som får använda. BFS använder 4 schemaläggningsnivåer (kallade schemaläggningspolicyer eller schemaläggningsklasser) ordnade från bäst till sämst som bestämmer hur uppgifter väljs med de överst som körs först.

Varje uppgift har ett speciellt värde som kallas a prio. I v0.462-utgåvan (används i -ck 4.0 kernel patchset) finns det totalt 103 "prioritetsköer" (aka prio) eller tillåtna värden som den kan ta. Ingen egentlig speciell datastruktur användes som prioritetskö utan endast den dubbellänkade listrunkön i sig. Det lägre prio-värdet betyder att det är viktigare och exekveras först.

Realtidspolicy

Realtidspolicyn utformades för realtidsuppgifter . Denna policy innebär att de pågående uppgifterna inte kan avbrytas (dvs. förebyggas) av den lägre prioriterade uppgiften eller de lägre prioriterade policynivåerna. Prioritetsklasser som schemaläggaren betraktar under realtidspolicyn är de som är markerade SCHED_RR och SCHED_FIFO. Schemaläggaren behandlar round robin i realtid (SCHED_RR) och FIFO i realtid (SCHED_FIFO) på olika sätt.

Designen lade ut de första 100 statiska prioritetsköerna.

Uppgiften som kommer att väljas för exekvering är baserad på uppgiftstillgänglighet för det lägsta värdet av prio av de 100 köerna och FIFO-schemaläggning.

På gafflar kommer processprioriteten att degraderas till normal policy.

Vid oprivilegierad användning (dvs. icke-rootanvändare) av sched_setscheduler anropad med en begäran om realtidspolicyklass, kommer schemaläggaren att degradera uppgiften till Isochronous policy.

Isokron politik

Isochronous-policyn utformades för prestanda i nästan realtid för icke- rootanvändare .

Designen lade ut 1 prioritetskö som som standard kördes som pseudo-realtidsuppgifter, men som kan ställas in som en grad av realtid.

Policyns beteende kan tillåta att en uppgift kan degraderas till normal policy när den överskrider en inställbar resurshanteringsprocent (70 % som standard) på 5 sekunder skalat till antalet online-CPU:er och timerupplösningen plus 1 bock. Formeln ändrades i MuQSS på grund av multi-runqueue-designen. De exakta formlerna är:

{\mathtt {T_{BFS}=((5*F*n)+1)*R}}

{\mathtt {T_{MuQSS}=(5*F)*R}}

där T är det totala antalet isokrona markeringar, F är timerfrekvensen, n är antalet online-CPU:er, R är den inställbara resurshanteringsprocenten inte i decimal utan som ett heltal. Timerfrekvensen är inställd på 250 som standard och kan redigeras i kärnan, men vanligtvis inställd på 100 Hz för servrar och 1000 Hz för interaktiva skrivbord. 250 är det balanserade värdet. Att sätta R till 100 gjorde att uppgifter beter sig som realtid och 0 gjorde att det inte blev pseudo-realtid och allt i mitten var pseudo-realtid.

Uppgiften som hade en tidigast virtuell deadline valdes för exekvering, men när flera isokrona uppgifter finns schemalägger de som round robin vilket gör att uppgifterna kan köra det inställbara round robin-värdet (med 6 ms som standard) efter varandra i en mässa lika chans utan hänsyn till den fina nivån.

Detta beteende hos den isokrona policyn är unikt för endast BFS och MuQSS och kanske inte implementeras i andra CPU-schemaläggare.

Normal policy

Den normala policyn har utformats för regelbunden användning och är standardpolicyn. Nyskapade uppgifter är vanligtvis markerade som normala.

Designen lade ut en prioriterad kö och uppgifterna väljs att utföras först baserat på den tidigaste virtuella deadline.

Inaktiv prioritetspolicy

Inaktiv-prioriteten har utformats för bakgrundsprocesser som distribuerade program och omkodare så att förgrundsprocesser eller de ovanför denna schemaläggningspolicy kan köras oavbrutet.

Designen lade ut 1 prioritetskö och uppgifter kan flyttas upp till normal policy automatiskt för att förhindra obestämd resurshållning .

Nästa körda uppgift med Idle-prioritet med andra som finns i samma prioritetspolicy väljs av den tidigaste virtuella deadline.

Förköpsrätt

Preemption kan uppstå när en nyligen klar uppgift med en högre prioritet policy (dvs. högre prio) har en tidigare virtuell deadline än den aktuella uppgiften - som kommer att avschemaläggas och läggas längst bak i kön. Avskedad innebär att dess virtuella deadline uppdateras. Uppgiftens tid fylls på till max round robin quantum när den har använt upp all sin tid. Om schemaläggaren hittade uppgiften vid den högre prio med den tidigaste virtuella deadline, kommer den att köras i stället för den mindre viktiga aktiviteten som körs endast om alla logiska CPU:er (inklusive hypertrådade kärnor/SMT-trådar) är upptagna. Schemaläggaren kommer att fördröja preemption så länge som möjligt om det finns oanvända logiska CPU:er.

Om en uppgift är markerad med tomgångsprioritet kan den inte överhuvudtaget föregripa ens andra inaktiva policymarkerade uppgifter utan använder snarare kooperativ multitasking .

Uppgiftsplacering, flera kärnor

När schemaläggaren upptäcker en vakande uppgift på ett icke-unicore-system, måste den bestämma vilken logisk CPU som ska köras uppgiften. Schemaläggaren gynnar mest de lediga hypertrådade kärnorna (eller lediga SMT- trådar) först på samma CPU som uppgiften kördes på, sedan den andra lediga kärnan i en flerkärnig CPU, sedan de andra CPU:erna på samma NUMA-nod, sedan alla upptagna hypertrådade kärnor / SMT-trådar / logiska CPU:er ska föregås på samma NUMA- nod, sedan den andra (fjärr) NUMA-noden och rankas på en preferenslista. Denna speciella skanning finns för att minimera latensoverhead till följd av migrering av uppgiften.

Förköpsföreläggandet liknar ovanstående stycke. Förhandsordern är hypertrådade kärna/SMT-enheter på samma multicore först, sedan den andra kärnan i multicore, sedan den andra CPU:n på samma NUMA-nod. När den söker efter en uppgift att förebygga i den andra fjärranslutna NUMA-noden, är företrädet bara alla upptagna trådar med lägre till lika prio eller senare virtuell deadline förutsatt att alla logiska CPU:er (inklusive hypertrådade kärna/SMT-trådar) i maskinen är alla upptagen. Schemaläggaren måste söka efter en lämplig uppgift med en policyuppgift med lägre eller kanske lika prioritet (med en senare virtuell deadline om nödvändigt) för att förebygga och undvika logiska CPU:er med en uppgift med en högre prioritet policy som den inte kan föregripa. Lokal preemption har en högre rang än sökning efter en inaktiv NUMA-enhet.

När en uppgift är ofrivillig förebyggd vid den tidpunkt då CPU:n saktas ned som ett resultat av kärnmedierad CPU-frekvensskalning (alias CPU-frekvensregulator), är uppgiften speciellt märkt "klibbig" förutom de som är markerade som realtidspolicy. Markerad som klibbig indikerar att uppgiften fortfarande har outnyttjad tid och att uppgiften är begränsad till samma CPU. Uppgiften kommer att markeras som klibbig närhelst CPU-skalningsregulatorn har skalat CPU:n med en lägre hastighet. Den inaktiva klibbade uppgiften kommer att återgå till att antingen köras i full Ghz-hastighet av en slump eller att schemaläggas för att köras på den bästa lediga CPU som inte är samma CPU som uppgiften kördes på. Det är inte önskvärt att migrera uppgiften till andra platser utan göra den inaktiv istället på grund av ökad latens som orsakas av overhead för att migrera uppgiften till en annan CPU eller NUMA-nod. Denna klibbiga funktion togs bort i den senaste iterationen av BFS (v0.512) motsvarande Kolivas patchset 4.8-ck1 och fanns inte i MuQSS.

schemaverktyg

En privilegierad användare kan ändra prioritetspolicyn för en process med programmet schedtool eller så görs det av ett program själv. Prioritetsklassen kan manipuleras på kodnivå med en syscall som sched_setscheduler endast tillgänglig för root, vilket schedtool använder.

Riktmärken

I en samtida studie jämförde författaren BFS med CFS med hjälp av Linux-kärnan v3.6.2 och flera prestationsbaserade slutpunkter. Syftet med denna studie var att utvärdera Completely Fair Scheduler (CFS) i vanilla Linux-kärnan och BFS i motsvarande kärna patchad med ck1 patchset. Sju olika maskiner användes för att se om skillnader finns och i vilken grad de skalas med hjälp av prestandabaserade mätvärden. Antalet logiska processorer varierade från 1 till 16. Dessa slutpunkter var aldrig faktorer i de primära designmålen för BFS. Resultaten var uppmuntrande.

Kärnor lappade med ck1-patchsetet inklusive BFS överträffade vaniljkärnan med CFS vid nästan alla prestandabaserade riktmärken som testades. Ytterligare studier med en större testuppsättning skulle kunna genomföras, men baserat på den lilla testuppsättningen av 7 utvärderade datorer är dessa ökningar i processköning, effektivitet/hastighet på det hela taget oberoende av CPU-typ (mono, dual, quad, hyperthreaded , etc.), CPU-arkitektur (32-bitars och 64-bitars) och CPU-mångfald (mono eller dubbel sockel).

Dessutom, på flera "moderna" processorer, såsom Intel Core 2 Duo och Core i7 , som representerar vanliga arbetsstationer och bärbara datorer, överträffade BFS konsekvent CFS i vaniljkärnan vid alla riktmärken. Effektivitet och hastighetsökningar var små till måttliga.

Adoption

BFS är standardschemaläggaren för följande Linux-distributioner:

Dessutom har BFS lagts till i en experimentell gren av Googles utvecklingsförråd för Android . Det ingick inte i Froyo-utgåvan efter att blindtestning inte visade en förbättrad användarupplevelse.

MuQSS

BFS har dragits tillbaka till förmån för MuQSS , formellt känd som Multiple Queue Skiplist Scheduler , en omskriven implementering av samma koncept. Den primära författaren övergav arbetet med MuQSS i slutet av augusti 2021.

Teoretisk design och effektivitet

MuQSS använder en dubbelriktad statisk arrayad överhoppningslista på 8 nivåer och uppgifterna ordnas efter statisk prioritet [köer] (med hänvisning till schemaläggningspolicyn) och en virtuell deadline. 8 valdes för att passa arrayen i cacheline. Dubbellänkad datastrukturdesign valdes för att påskynda borttagningen av uppgifter. Att ta bort en uppgift tar bara O(1) med en dubbelhoppningslista jämfört med originaldesignen av William Pugh som tar $O(n)$ i värsta fall.

Uppgiftsinsättning är $O(\log n)$ . Nästa uppgift för exekveringssökning är ${\displaystyle O(k)} ,$ där $k$ är antalet processorer. Nästa uppgift för exekvering är $O(1)$ per runqueue, men schemaläggaren undersöker varannan runqueue för att upprätthålla rättvisa uppgifter mellan CPU:er, för latens eller balansering (för att maximera CPU-användning och cachekoherens på samma NUMA-nod över de som har åtkomst över NUMA-noder), så slutligen $O(k)$ . Det maximala antalet uppgifter den kan hantera är 64 000 uppgifter per runqueue per CPU. Den använder flera uppgiftskörningsköer i vissa konfigurationer en körkö per CPU, medan dess föregångare BFS bara använde en uppgiftskörningskö för alla processorer.

Uppgifterna är ordnade som en gradient i överhoppningslistan på ett sätt så att realtidspolicyprioritet kommer först och inaktiv policyprioritet kommer sist. Normal och inaktiv prioritetspolicy sorteras fortfarande efter virtuell deadline som använder bra värden. Realtids- och isokrona policyuppgifter körs i FIFO- ordning och ignorerar bra värden. Nya uppgifter med samma nyckel placeras i FIFO-ordning, vilket innebär att nya uppgifter placeras i slutet av listan (dvs. översta noden vertikalt), och uppgifter på 0:e nivå eller längst ner får exekvering först före de som ligger närmast topp vertikalt och de som är längst bort från huvudnoden. Nyckeln som används för infogad sortering är antingen den statiska prioriteten eller den virtuella deadline.

Användaren kan välja att dela runqueue mellan multicore eller ha en runqueue per logisk CPU. Spekulationerna med att dela runköers design var att minska latensen med en avvägning av genomströmning.

Ett nytt beteende som introducerades av MuQSS var användningen av timern med hög upplösning för en noggrannhet under millisekunder när tidsintervallen användes, vilket resulterade i omläggning av uppgifter.

Se även

Schemaläggning för rättvis andel

externa länkar

Brain Fuck Scheduler FAQ