Helt rättvis schemaläggare

Helt rättvis schemaläggare
Originalförfattare Ingo Molnár
Utvecklare Linux-kärnutvecklare
Skrivet i C
Operativ system Linux kärna
Typ processschemaläggare
Licens GPL-2.0
Hemsida kernel .org
Placering av "Completely Fair Scheduler" (en processplanerare) i en förenklad struktur av Linux-kärnan.

Completely Fair Scheduler ( CFS ) är en processplanerare som slogs samman till 2.6.23 (oktober 2007) utgåvan av Linuxkärnan och är standardschemaläggaren för uppgifterna i klassen SCHED_NORMAL ( dvs. uppgifter som inte har någon realtid utförandebegränsningar). Den hanterar CPU- resursallokering för exekvering av processer och syftar till att maximera den totala CPU-användningen samtidigt som den maximerar interaktiv prestanda.

I motsats till den tidigare O(1)-schemaläggaren som användes i äldre Linux 2.6-kärnor, som upprätthöll och bytte körköer av aktiva och utgångna uppgifter, baseras CFS-schemaläggaren på körningsköer per CPU, vars noder är tidsordnade schemaläggbara enheter som hålls sorterade efter rödsvarta träd . CFS gör bort den gamla uppfattningen om fasta tidssegment per prioritet och i stället syftar den till att ge en rättvis del av CPU-tiden till uppgifter (eller, bättre, schemalagda enheter).

Algoritm

En uppgift (dvs. en synonym för tråd) är den minimala enhet som Linux kan schemalägga. Men det kan också hantera grupper av trådar, hela flertrådade processer och till och med alla processer för en given användare. Denna design leder till konceptet med schemaläggningsbara enheter, där uppgifter grupperas och hanteras av schemaläggaren som helhet. För att denna design ska fungera, bäddar varje task_struct -uppgiftsbeskrivning in ett fält av typen sched_entity som representerar uppsättningen av entiteter som uppgiften tillhör.

Varje kör-kö per CPU av typen cfs_rq sorterar sched_entity -strukturer på ett tidsordnat sätt i ett röd-svart träd (eller 'rbtree' i Linux-språk), där noden längst till vänster är upptagen av den entitet som har fått minst segment av körningstid (som sparas i vruntime -fältet för entiteten). Noderna indexeras av processorns " exekveringstid " i nanosekunder.

En " maximal exekveringstid " beräknas också för varje process för att representera den tid processen skulle ha förväntat sig att köra på en "ideal processor". Detta är den tid som processen har väntat på att köras, dividerat med det totala antalet processer.

När schemaläggaren anropas för att köra en ny process:

  1. Noden längst till vänster i schemaläggningsträdet väljs (eftersom den kommer att ha den lägsta förbrukade exekveringstiden ) och skickas för exekvering.
  2. Om processen helt enkelt slutför exekveringen tas den bort från systemet och schemaläggningsträdet.
  3. Om processen når sin maximala exekveringstid eller på annat sätt stoppas (frivilligt eller via avbrott) återinförs den i schemaläggningsträdet baserat på dess nyligen förbrukade exekveringstid .
  4. Den nya noden längst till vänster kommer sedan att väljas från trädet och upprepa iterationen.

Om processen ägnar mycket av sin tid åt att sova, är dess värde för spenderad tid lågt och den får automatiskt prioritetsökningen när den äntligen behöver den. Sådana uppgifter får därför inte mindre processortid än de uppgifter som ständigt körs.

Komplexiteten hos algoritmen som infogar noder i cfs_rq -körkön för CFS-schemaläggaren är O( log N), där N är det totala antalet enheter. Att välja nästa enhet att köra görs i konstant tid eftersom noden längst till vänster alltid cachelagras.

Historia

Con Kolivas arbete med schemaläggning, framför allt hans implementering av " rättvis schemaläggning " som heter Rotating Staircase Deadline , inspirerade Ingo Molnár att utveckla sin CFS, som en ersättning för den tidigare O(1)-schemaläggaren , vilket krediterade Kolivas i hans tillkännagivande. CFS är en implementering av en välstuderad, klassisk schemaläggningsalgoritm som kallas viktad rättvis kö . Ursprungligen uppfanns för paketnätverk , fair queuing hade tidigare tillämpats på CPU-schemaläggning under namnet stride scheduling . CFS är den första implementeringen av en schemaläggare för rättvis köprocess som ofta används i ett generellt operativsystem.

Linux-kärnan fick en patch för CFS i november 2010 för 2.6.38-kärnan som har gjort schemaläggaren "rättvisare" för användning på stationära datorer och arbetsstationer. Utvecklad av Mike Galbraith med hjälp av idéer som föreslagits av Linus Torvalds , implementerar patchen en funktion som kallas autogruppering som avsevärt ökar interaktiva skrivbordsprestanda. Algoritmen placerar överordnade processer i samma uppgiftsgrupp som underordnade processer. (Uppgiftsgrupper är knutna till sessioner skapade via setsid() -systemanropet.) Detta löste problemet med långsamma interaktiva svarstider på multi-core och multi-CPU ( SMP ) system när de utförde andra uppgifter som använder många CPU-intensiva trådar i dessa uppgifter. En enkel förklaring är att, med denna patch installerad, kan man fortfarande titta på en video, läsa e-post och utföra andra typiska skrivbordsaktiviteter utan problem eller hacking medan man till exempel kompilerar Linux-kärnan eller kodar video .

2016 patchades Linux-schemaläggaren för bättre multicore-prestanda, baserat på förslagen som beskrivs i tidningen "The Linux Scheduler: A Decade of Wasted Cores".

Se även

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Completely_Fair_Scheduler&oldid=1084595711 "