CPU-planning

Een CPU-scheduler kiest het gereedstaande proces of de gereedstaande thread die als volgende op een CPU draait. De regel die de scheduler volgt, is het beleid. De dispatcher voert de keuze uit door de uitvoering naar de geselecteerde taak te wisselen. Ander beleid kan hetzelfde wisselmechanisme gebruiken.

Volg de toestandsveranderingen

Een draaiende taak heeft een CPU. Een gereedstaande taak kan draaien maar wacht op een beurt. Een geblokkeerde taak wacht op een gebeurtenis, zoals de voltooiing van een schijfleesbewerking. Alleen gereedstaande taken komen voor selectie in aanmerking.

Stel dat een editor een schijfleesbewerking start terwijl een compiler gereedstaat. De editor gaat van de toestand in uitvoering naar de geblokkeerde toestand, zodat de compiler kan draaien. Wanneer de leesbewerking eindigt, maakt een interrupt de editor weer gereed. De editor draait niet noodzakelijk onmiddellijk: het beleid moet kiezen tussen de editor en ander gereedstaand werk.

Planningsbeslissingen vinden plaats wanneer een taak blokkeert, eindigt, gereed wordt of wordt onderbroken en terugkeert naar de gereedtoestand. Ook vrijwillig de CPU-beurt afstaan geeft de CPU vrij. Preëmptie betekent dat de CPU wordt afgenomen van een taak die had kunnen blijven draaien; de taak behoudt haar opgeslagen toestand en kan later verdergaan.

Met een timerinterrupt kan de kernel een tijdschijf afdwingen, zelfs als een programma blijft herhalen zonder de beurt af te staan. Voltooide I/O kan ook preëmptie veroorzaken doordat een taak met meer voorrang gereed wordt. Linux, Windows en macOS gebruiken planning met preëmptie.

Werk komt in bursts

Programma's wisselen CPU-bursts, waarin ze rekenen, af met perioden waarin ze op I/O wachten. Een CPU-gebonden programma zoals een encoder heeft lange CPU-bursts. Een I/O-gebonden programma zoals een editor rekent vaak kort en wacht dan. Door een editor na een toetsaanslag snel te bedienen, kan die sneller reageren zonder veel totale CPU-tijd te krijgen.

De dispatcher slaat de toestand van de oude taak op, herstelt de registers van de gekozen taak en hervat de instructiestroom ervan in de gebruikersmodus. Dispatchlatentie is de tijd die nodig is om de uitvoering over te dragen. Wisselen verstoort ook caches en de adresvertaalbuffer, of TLB, die adresvertalingen in de cache bewaart. De volgende taak moet die mogelijk opnieuw vullen, dus de tijd voor het opslaan van registers is slechts een deel van de kosten.

Drie tijdschalen voor planning

De langetermijnscheduler laat ingediende taken toe en bepaalt hoeveel er in het systeem zijn. De middellangetermijnscheduler kan volledige processen opschorten door ze uit het geheugen te wisselen en later terug te plaatsen. De kortetermijnscheduler kiest de volgende gereedstaande taak en handelt vaak. Systemen voor algemeen gebruik vertrouwen vooral op deze laatste rol; batchsystemen en clusters kunnen ook de toelating expliciet regelen.

Begin een beleidsvergelijking met eenvoudige taken die alleen de CPU gebruiken en waarvan de lengtes bekend zijn. Varieer dan één kenmerk: ongelijke lengtes laten de vertragingen van FIFO zien, latere aankomsten laten de grenzen van planning zonder preëmptie zien, I/O biedt mogelijkheden om werk te laten overlappen en onbekende lengtes vereisen voorspelling of terugkoppeling.

Een planning laat zien wanneer taken draaien. Een maatstaf vertelt je welk deel van die planning van belang is. Noteer voor elke taak de aankomst, eerste uitvoering en voltooiing voordat je gemiddelden berekent.

Onderscheid de drie tijden

Doorlooptijd meet het hele interval van aankomst tot voltooiing. Responstijd meet de vertraging tot de eerste uitvoering. Wachttijd telt elk interval op waarin de taak gereed is maar niet draait.

Voor een taak die alleen de CPU gebruikt, is de doorlooptijd gelijk aan de wachttijd plus de CPU-uitvoeringstijd. Bij I/O maakt de geblokkeerde tijd ook deel uit van de doorlooptijd, dus als je alleen de CPU-tijd aftrekt, tel je te veel wachttijd. Hier wordt responstijd gedefinieerd met de eerste uitvoering; een dienst voor gebruikers kan daarnaast de tijd tot de eerste uitvoer meten.

Werk een FIFO-tijdlijn uit

A komt aan op 0 ms en heeft 8 ms CPU-tijd nodig. B komt aan op 1 ms en heeft 4 ms nodig. C komt aan op 2 ms en heeft 2 ms nodig. Zonder wisselkosten geeft FIFO:

• A: 0–8 ms.
• B: 8–12 ms.
• C: 12–14 ms.

De gemiddelde doorlooptijd is $\frac{8+11+12}{3}=\frac{31}{3}\approx \mathrm{10,33}$ ms. De gemiddelde respons- en wachttijd zijn beide $\frac{0+7+10}{3}=\frac{17}{3}\approx \mathrm{5,67}$ ms. Ze zijn gelijk omdat elke taak eenmaal zonder onderbreking draait. Bij preëmptie kan een taak na haar eerste beurt opnieuw wachten, zodat de wachttijd groter kan zijn dan de responstijd.

Meet de hele werklast

Doorvoer telt voltooide taken per eenheid verstreken tijd. De planning voltooit drie taken in 14 ms, ongeveer 214,29 taken/s. De CPU-bezettingsgraad is de tijd dat de CPU bezig is gedeeld door de verstreken tijd; die is hier 100% omdat de CPU nooit niets doet. Vermeld het meetinterval: als je na voltooiing een periode toevoegt waarin de CPU niets doet, veranderen beide cijfers.

Een hoge bezettingsgraad kan nog steeds samengaan met lange wachttijden. Die hoeft ook niet te betekenen dat alle tijd waarin de CPU bezig is nuttig toepassingswerk is: werkelijke metingen kunnen wisselingen en ander kernelwerk meetellen als bezette tijd. Vermeld of een overheadberekening bezette tijd of nuttig werk meet.

Kies wat je optimaliseert

Bij batchwerk is de gemiddelde doorlooptijd vaak van belang. Bij interactief werk telt een snelle respons. Gedeelde diensten hebben zowel eerlijke toegang als doorvoer nodig. Uithongering betekent dat een taak die in aanmerking komt onbeperkt wacht, dus een goed gemiddelde alleen toont geen eerlijke behandeling aan.

Bekijk afzonderlijke vertragingen en de staart van de verdeling. Een responstijd op het 99e percentiel beschrijft de vertraging waar ongeveer 99% van de waarnemingen op of onder valt; enkele ernstige vertragingen kunnen in een laag gemiddelde verdwijnen. Trek altijd het eigen aankomsttijdstip van de taak af en tel haar uitvoeringsintervallen als bediening, nooit als wachttijd.

FIFO, ook FCFS genoemd, voert gereedstaande taken in aankomstvolgorde uit. Het werkt zonder preëmptie: een latere aankomst kan een draaiende CPU-burst niet onderbreken. In voorbeelden met alleen CPU-gebruik draait elke gekozen taak tot voltooiing.

Bekijk het konvooi-effect

A, B en C komen tegelijk aan. A heeft 60 ms nodig; B en C hebben elk 6 ms nodig. Met A vooraan voert FIFO A 0–60, B 60–66 en C 66–72 uit. De doorlooptijden zijn 60, 66 en 72 ms, gemiddeld 66 ms. De kleine taken wachten het grootste deel van hun bestaan achter A. Dit is het konvooi-effect.

Kortste taak eerst (SJF) kiest de kortste volgende CPU-burst uit de gereedstaande taken en onderbreekt die niet. Met dezelfde aankomsten voert het B 0–6, C 6–12 en daarna A 12–72 uit. De gemiddelde doorlooptijd wordt $\frac{6+12+72}{3}=30$ ms. Het totale CPU-werk blijft 72 ms; de verbetering komt doordat korte taken eerder eindigen.

Waarom helpt dit? Als een lange burst direct vóór een korte burst draait, wachten beide taken op al het eerdere werk. Als je alleen deze twee omwisselt, verkort je de vertraging van de korte taak met de lengte van de lange burst, terwijl je de vertraging van de lange taak alleen met de lengte van de korte burst verlengt. Door zulke wisselingen te herhalen, komen de bursts in oplopende volgorde. Als alle taken tegelijk aankomen en hun lengtes bekend zijn, minimaliseert SJF de gemiddelde doorloop- en wachttijd; in dit geval zonder preëmptie en met alleen CPU-gebruik is de responstijd tot de eerste uitvoering ook gelijk aan de wachttijd.

Beperk de keuze tot gereedstaande taken

Nu komt A aan op 0 ms, terwijl B en C op 10 ms aankomen. Op 0 ms is A de enige keuze. SJF zonder preëmptie voert A 0–60, B 60–66 en C 66–72 uit. De doorlooptijden zijn 60, 56 en 62 ms, gemiddeld ongeveer 59,33 ms. SJF kan niet handelen op basis van een toekomstige taak of een al gestarte burst onderbreken.

FIFO voorkomt uithongering wanneer taken die ervoor staan de CPU uiteindelijk vrijgeven. Bij SJF kan een lange wachtende taak uithongeren als er kort werk blijft aankomen.

Voorspel een burst

De volgende CPU-burst is meestal onbekend. Een exponentieel gemiddelde combineert de laatst gemeten burst met de vorige voorspelling:

Hier is $t_n$ de gemeten burst, ${\tau }_n$ de vorige voorspelling en $\alpha$ een gewicht tussen 0 en 1. Als je begint met 10 ms en $\alpha =\mathrm{0,5}$ gebruikt, geeft een gemeten 6 ms een voorspelling van 8 ms. Een daaropvolgende 4 ms geeft 6 ms; nog eens 6 ms laat de voorspelling op 6 ms. Bij gewicht nul hebben metingen geen effect; bij gewicht één telt alleen de nieuwste meting. De voorspelde grootheid is de CPU-burstlengte, niet de grootte van het programmabestand of het aantal regels code.

Kortste resterende uitvoeringstijd eerst (STCF), ook SRTF genoemd, is SJF met preëmptie. Vergelijk bij een aankomst of voltooiing hoeveel CPU-tijd elke gereedstaande taak nog nodig heeft. Een nieuwkomer onderbreekt de huidige taak wanneer die minder tijd nodig heeft dan de huidige taak nog nodig heeft.

Vergelijk de resterende tijd

A heeft 60 ms nodig en komt aan op 0 ms. B en C hebben elk 6 ms nodig en komen aan op 10 ms. A draait 10 ms en heeft nog 50 ms nodig. Op 10 ms wint B omdat 6 ms minder is dan 50 ms; C heeft dezelfde lengte, dus beslissen eerst de aankomstvolgorde en daarna de naam.

De tijdlijn is A 0–10, B 10–16, C 16–22, A 22–72. De doorlooptijden zijn A 72 ms, B 6 ms en C 12 ms, gemiddeld 30 ms. De responstijden zijn 0, 0 en 6 ms, gemiddeld 2 ms. SJF zonder preëmptie geeft bij deze aankomsten een gemiddelde doorlooptijd van ongeveer 59,33 ms en een gemiddelde responstijd van 35,33 ms.

Trek altijd de al ontvangen uitvoeringstijd af. Een nieuwe burst van 12 ms vergelijken met de oorspronkelijke 60 ms van A zou onjuist zijn als A nog maar 5 ms nodig had. STCF zou A eerst voltooien. Bij bekende lengtes voor taken met alleen CPU-gebruik en zonder wisselkosten minimaliseert STCF de gemiddelde doorlooptijd bij willekeurige aankomsten. Lange taken kunnen nog steeds uithongeren bij een aanhoudende stroom korter werk.

Wanneer alle taken met alleen CPU-gebruik tegelijk aankomen, geven SJF en STCF dezelfde volgorde. De draaiende kortste taak wordt alleen maar korter, dus vormt geen wachtende taak een reden om die te onderbreken.

Gebruik de geblokkeerde tijd van een andere taak

Een geblokkeerde taak kan de CPU niet gebruiken. Haar I/O-wachttijd biedt de gelegenheid om ander gereedstaand werk uit te voeren, zelfs bij beleid zonder preëmptie. Preëmptie wordt weer van belang wanneer voltooide I/O een korte burst gereedmaakt terwijl een andere taak draait.

Neem A met vijf CPU-bursts van 10 ms en een schijfleesbewerking van 10 ms na elk van de eerste vier bursts. B heeft één CPU-burst van 50 ms nodig. Beide komen aan op 0 ms. Als de CPU niets doet tijdens de leesbewerkingen van A en B uitstelt totdat A eindigt, voltooit A op 90 ms en B op 140 ms.

Behandel elke terugkerende burst van A als kort gereedstaand werk:

• A draait van 0–10; de leesbewerking duurt van 10–20 terwijl B draait.
• A keert terug voor 20–30; B heeft nog 40 ms nodig, dus de 10 ms van A wint.
• B draait van 30–40 tijdens de volgende leesbewerking. De afwisseling herhaalt zich.
• De laatste burst van A draait van 80–90; B voltooit zijn laatste 10 ms van 90–100.

A eindigt nog steeds op 90 ms, maar B eindigt op 100 ms. De CPU voert 100 ms werk uit in 100 ms verstreken tijd. Schijfactiviteit en CPU-activiteit overlappen; de CPU voert A niet uit terwijl A geblokkeerd is. Een apparaatinterrupt maakt A gereed wanneer elke leesbewerking eindigt, waarna STCF de nieuwe burst vergelijkt met het resterende werk van B.

Round-robinplanning (RR) houdt een FIFO-gereedwachtrij bij en geeft de voorste taak maximaal één tijdkwantum, of tijdschijf. Een taak die eindigt of blokkeert, verlaat de CPU eerder. Een taak die nog gereed is wanneer haar tijdschijf afloopt, gaat naar achteren.

Volg de beurten voordat je tijden berekent

A, B en C komen aan op 0 ms en hebben elk 9 ms nodig. Met een tijdkwantum van 3 ms voert RR uit:

• Eerste ronde: A 0–3, B 3–6, C 6–9.
• Tweede ronde: A 9–12, B 12–15, C 15–18.
• Laatste ronde: A 18–21, B 21–24, C 24–27.

De eerste uitvoeringen zijn op 0, 3 en 6 ms, dus de gemiddelde responstijd is 3 ms. De voltooiingen zijn op 21, 24 en 27 ms, dus de gemiddelde doorlooptijd is 24 ms. FIFO geeft een gemiddelde responstijd van 9 ms en een gemiddelde doorlooptijd van 18 ms. Hier laat RR iedereen snel beginnen, maar stelt het de eerste voltooide taak uit tot 21 ms.

RR verdeelt CPU-toegang terwijl taken concurreren; het maakt de voltooiingstijden niet gelijk. Een korte taak kan in haar eerste beurt eindigen. Met een vaste groep van $n$ gereedstaande taken en tijdkwantum $q$ is de wachttijd tussen beurten maximaal $(n-1)q$ zonder wisselkosten. Voortdurende aankomsten, andere prioriteitsklassen en beperkingen op welke CPU's taken mogen gebruiken, veranderen de omstandigheden van die grens.

Verwerk aankomsten op de grens van een tijdschijf

Gebruik de aankomstvolgorde en bij gelijke aankomsttijden de alfabetische volgorde. Een taak die precies aankomt wanneer een tijdschijf afloopt, komt vóór de onderbroken taak in de wachtrij. Als A aankomt op 0 ms en 8 ms nodig heeft, B op 1 ms en 4 ms nodig heeft en C op 2 ms en 2 ms nodig heeft, geeft een tijdkwantum van 2 ms A 0–2, B 2–4, C 4–6, A 6–8, B 8–10, A 10–14.

Het laatste interval van A bevat twee opeenvolgende beurten zonder concurrent. De responstijden zijn 0, 1 en 2 ms; de doorlooptijden zijn 14, 9 en 4 ms. De gemiddelden zijn 1 ms en 9 ms. Wanneer een geblokkeerde taak bij eenvoudige RR terugkeert, sluit die aan voor een nieuwe beurt; de taak reserveert geen ongebruikte CPU-tijd terwijl ze geblokkeerd is.

Zorg dat het tijdkwantum zijn kosten waard is

Een zeer groot tijdkwantum laat RR zich als FIFO gedragen voor bursts die korter zijn dan dat kwantum. Een zeer klein tijdkwantum veroorzaakt veel overdrachten en herhaalde verstoring van caches. In een eenvoudige implementatie op basis van een timer is het tijdkwantum een geheel aantal timerperioden.

Bij wisselkosten $s$ na elke nuttige tijdschijf met lengte $q$ is het geschatte overheadaandeel $\frac{s}{q+s}$. Een wisseling van 0,1 ms kost ongeveer 9,1% bij een tijdschijf van 1 ms, maar ongeveer 0,99% bij een tijdschijf van 10 ms. Langere tijdschijven amortiseren wisselkosten door die over meer nuttig werk te spreiden.

Een veelgebruikte vuistregel voor de grootte is dat de meeste bursts, bijvoorbeeld ongeveer 80%, binnen één tijdschijf eindigen. De juiste keuze hangt af van gemeten burstlengtes en de responsvertragingen die de werklast kan verdragen. Tel wisselingen tussen taken afzonderlijk van timergebeurtenissen die simpelweg dezelfde enige gereedstaande taak laten doorgaan.

Een prioriteitsscheduler voert de gereedstaande taak met de hoogste prioriteit uit. Taken met gelijke prioriteit kunnen FIFO of round-robinplanning volgen. In een versie met preëmptie krijgt een nieuw gereedstaande taak met hogere prioriteit onmiddellijk de CPU; in een versie zonder preëmptie wacht die totdat de huidige taak de CPU vrijgeeft.

Lees de richting van de schaal

Prioriteitsgetallen hebben geen universele richting. Gebruik in de voorbeelden uit dit leerboek kleinere getallen voor hogere prioriteit. Linux-nice-waarden volgen die richting, maar Windows-prioriteitsniveaus en Linux-realtimeprioriteiten gebruiken grotere getallen voor hogere prioriteit.

A, B en C komen aan op 0 ms met bursts van 4, 3 en 5 ms en prioriteiten 2, 1 en 3. Prioriteitsplanning zonder preëmptie voert B 0–3, A 3–7 en C 7–12 uit. Hun wachttijden zijn 0, 3 en 7 ms, gemiddeld ongeveer 3,33 ms; hun doorlooptijden zijn 3, 7 en 12 ms, gemiddeld ongeveer 7,33 ms.

Een interne prioriteit komt voort uit gemeten gedrag, zoals CPU-gebruik of wachten op I/O. SJF leidt de rangorde af uit de voorspelde burstlengte. Een externe prioriteit komt van een persoon, zoals een beheerder die een back-up als minder urgent aanmerkt. Geen van beide keuzes verzekert dat werk met lage prioriteit tijd krijgt bij een voortdurende toevoer van werk met hogere prioriteit.

Verhoog de prioriteit tijdens het wachten

Geleidelijke prioriteitsverhoging verhoogt de prioriteit van een wachtende taak geleidelijk. Als de rang elke 100 ms met één verbetert, bereikt een taak die begint met prioriteit 20 na 2 s wachten in de gereedtoestand de hoogste prioriteit 0. Door de hogere rang concurreert de taak met werk dat voorrang krijgt; regels voor gelijke prioriteit bepalen de beurten van taken met dezelfde rang.

Uithongering is gebrek aan voortgang doordat steeds ander werk wordt gekozen. Geleidelijke prioriteitsverhoging pakt dit aan door de rang in de loop van de tijd te veranderen. Dit dient een ander doel dan het voorspellen van de burstlengte: een lang wachtende lange taak kan een beurt verdienen, ook al blijft haar burst lang.

Volg de afhankelijkheid bij prioriteitsinversie

Een taak H met hoge prioriteit kan geblokkeerd zijn op een vergrendeling die wordt vastgehouden door taak L met lage prioriteit. Een taak M met gemiddelde prioriteit kan L onderbreken. Nu kan H niet verder, ook al heeft M een lagere prioriteit dan H: L moet eerst draaien om de vergrendeling vrij te geven. Dit is prioriteitsinversie.

Bij prioriteitsovererving erft L tijdelijk de prioriteit van H zolang L de vergrendeling vasthoudt die H nodig heeft. M kan L niet langer van de CPU houden. L draait, geeft de vergrendeling vrij en verliest de overgeërfde prioriteit; H wordt gereed en kan draaien.

De eigen prioriteit van H verhogen geeft de vergrendeling waarop H wacht niet vrij: H blijft geblokkeerd. Het gaat erom de thread te laten draaien die aan de afhankelijkheid kan voldoen. In 1997 kreeg Mars Pathfinder te maken met een probleem van prioriteitsinversie dat werd aangepakt door prioriteitsovererving in te schakelen.

Een feedbackwachtrij met meerdere niveaus (MLFQ) combineert prioriteiten met round-robinplanning. Het doel is de bediening van korte taken te benaderen en interactief werk snel te laten reageren zonder dat de toekomstige uitvoeringstijd van elke taak bekend is. Recent CPU-gebruik levert de terugkoppeling.

Pas de wachtrijregels toe

Elke gereedstaande taak behoort tot één prioriteitswachtrij. De basisversie met gebruiksregistratie volgt vier regels:

1. Kies de wachtrij met de hoogste prioriteit die gereedstaand werk bevat.
2. Wissel binnen die wachtrij taken met gelijke prioriteit af volgens round-robinplanning.
3. Plaats een nieuwe taak in de bovenste wachtrij.
4. Verlaag de prioriteit van een taak wanneer die haar CPU-tijdbudget op het huidige niveau verbruikt, waarbij het gebruik over alle beurten en I/O-onderbrekingen wordt meegeteld.

Een tijdkwantum begrenst één beurt. Een budget begrenst de totale bediening op een prioriteitsniveau. Een niveau kan meerdere tijdkwanta toestaan voordat de prioriteit daalt. Op het laagste niveau blijft de taak bij een verlaging in de onderste wachtrij.

Zo krijgt een nieuwe taak een kans om snel te eindigen. Een taak die herhaaldelijk CPU-tijd verbruikt, laat zien dat ze langer nodig heeft en zakt. Een korte burst die blokkeert, verbruikt weinig budget, zodat interactieve taken doorgaans langer hoog blijven.

Volg een lange taak en een nieuwkomer

Gebruik wachtrijen Q2, Q1 en Q0, met Q2 als hoogste, tijdkwanta van 10 ms en budgetten van 10 ms op elk niveau, en geen verhoging tijdens dit voorbeeld. A heeft 200 ms nodig en komt aan op 0 ms. De taak draait in Q2 van 0–10, in Q1 van 10–20 en daarna in Q0.

Op 100 ms heeft A 100 ms CPU-tijd gekregen. B komt aan en heeft 20 ms nodig. B komt in Q2 en onderbreekt A, en draait vervolgens van 100–110 in Q2. B heeft het budget van dat niveau verbruikt en zakt naar Q1. Q1 heeft voorrang op Q0 van A, dus B draait van 110–120 en eindigt. A gaat verder op 120 en voltooit de resterende 100 ms op 220 ms. De doorlooptijd van B is 20 ms, ondanks de aankomst na een veel langere taak.

Houd het resterende werk van A bij terwijl B draait: dat blijft 100 ms. De verstreken tijd loopt door tijdens de bediening van B, maar A krijgt dan geen CPU-tijd.

Onderscheid wachten van CPU-verbruik

Een editor die 1 ms draait en op invoer wacht, gebruikt een budget van 10 ms over tien van zulke bursts. Geblokkeerde tijd gaat niet van het CPU-budget af. Bij strikte registratie tellen die korte bursts nog steeds op, zodat de editor uiteindelijk zakt, tenzij een prioriteitsverhoging de editor eerst terugplaatst.

Een vroege MLFQ-regel verlaagde alleen de prioriteit van taken die een volledig ononderbroken tijdkwantum gebruikten. Een taak die vlak vóór het aflopen de beurt afstond, behield haar prioriteit. Die regel liet interactief werk snel reageren, maar maakte ook opzettelijke manipulatie mogelijk. Door cumulatief CPU-gebruik te tellen, sluit je die achterdeur.

Lagere wachtrijen draaien wanneer alle hogere wachtrijen geen gereedstaand werk hebben. Een geblokkeerde taak met hogere prioriteit verhindert niet dat taken met lagere prioriteit de CPU gebruiken. Bij aanhoudende vraag met hoge prioriteit heeft lager geplaatst werk een extra mechanisme tegen uithongering nodig, in de vorm van periodieke verhogingen.

Terugkoppeling zorgt voor een nuttige scheiding, maar het vroegere gedrag van een taak hoeft niet haar huidige behoeften te blijven weerspiegelen. Een lange berekening kan later interactief worden. Ondertussen kan een taak in de onderste wachtrij onbeperkt wachten als de hogere wachtrijen druk blijven.

Beoordeel elke taak periodiek opnieuw

Een prioriteitsverhoging brengt na een periode $S$ alle taken terug naar de bovenste wachtrij. Daardoor kunnen wachtende taken de bovenste wachtrij delen en kan de scheduler veranderd gedrag opnieuw leren. Een verhoogde CPU-gebonden taak verbruikt later haar budget en zakt weer.

Neem de vroege MLFQ-regels: twee interactieve taken staan altijd de beurt af vóór het einde van een volledige tijdschijf van 10 ms en houden samen Q2 bezig. Een CPU-gebonden taak wacht in Q0. Zonder verhogingen krijgt die geen uitvoeringstijd. In een herhalende planning waarin een verhoging elke 100 ms de taak één beurt van 10 ms op het hoogste niveau geeft voordat ze zakt en werk met hogere prioriteit de rest vult, krijgt ze 10% van de CPU. Dat percentage komt uit dit voorbeeld; een verhoging kent geen algemeen vast aandeel toe.

Een lang interval tussen verhogingen laat taken lang wachten tussen kansen om te draaien. Een zeer kort interval plaatst CPU-gebonden werk steeds opnieuw bovenaan en verzwakt het voordeel van interactief werk. Ontwerpen hebben perioden van ongeveer één seconde gebruikt, maar de periode is een keuze die je afstemt op het gedrag van de werklast en de responsdoelen.

Registreer gebruik over meerdere beurten

Een afzonderlijk probleem is manipulatie. Volgens de vroege regel voor volledige tijdschijven kan een programma 9 ms draaien, 1 ms I/O aanvragen en dat herhalen. Het gebruikt nooit een volledige tijdschijf van 10 ms achter elkaar en behoudt daardoor de hoogste prioriteit, terwijl het bijna alle beschikbare CPU-tijd verbruikt.

Bij een cumulatief budget van 10 ms verbruikt de eerste burst 9 ms en blijft 1 ms over. Na de I/O put één extra milliseconde het budget uit en daalt de prioriteit van de taak tijdens haar tweede burst. Een I/O-verzoek verandert de toestand; het wist de al ontvangen uitvoeringstijd niet. De registratieregel voorkomt deze tactiek ook zonder verhoging.

Stel de niveaus af

Kies het aantal wachtrijen, het tijdkwantum van elke wachtrij, het budget van elk niveau en het interval tussen verhogingen. Bovenste wachtrijen gebruiken meestal korte tijdkwanta, bijvoorbeeld 10 ms, om interactieve taken snel af te wisselen. Lagere wachtrijen kunnen veel langere tijdkwanta gebruiken, soms honderden milliseconden, om wisselingen tijdens aanhoudend rekenwerk te verminderen.

Het budget kan onafhankelijk van het tijdkwantum groeien. Een niveau met een tijdkwantum van 5 ms en een budget van 15 ms kan drie volledige beurten toestaan voordat de prioriteit daalt. Een groter budget stelt de indeling als langlopende taak uit; een groter tijdkwantum verlengt een afzonderlijke beurt.

Het tijdsverdelingsontwerp van Solaris illustreert tabelgestuurde terugkoppeling: de klassieke instelbare tabel heeft 60 prioriteitsniveaus, met tijdkwanta van ongeveer 20 ms bij hoge prioriteit tot enkele honderden milliseconden bij lage prioriteit. Klassieke BSD-ontwerpen berekenden de prioriteit daarentegen uit recent CPU-gebruik dat in de loop van de tijd afneemt. Bij beide verliest oud CPU-gebruik invloed, zodat het verre verleden van een thread de behandeling niet blijvend bepaalt.

Planning op basis van evenredige aandelen beoogt CPU-tijd te verdelen volgens toegekende aandelen. Bij loterijplanning heeft elke uitvoerbare taak tickets. Een willekeurig winnend ticket kiest de taak voor de volgende even lange tijdschijf. De winkans van een taak is haar aantal tickets gedeeld door alle tickets van uitvoerbare taken.

Zoek een winnend ticket

A heeft 100 tickets, B 50 en C 250. Nummer de 400 tickets van 0 tot en met 399. A heeft 0–99, B heeft 100–149 en C heeft 150–399. Een trekking van 300 kiest C.

Een implementatie met een lijst trekt een getal en telt de aantallen tickets op. De lopende totalen zijn 100 na A, 150 na B en 400 na C. Stop bij het eerste totaal dat strikt groter is dan het getrokken getal. Met “groter dan of gelijk aan” zouden tickets op de grens verkeerd worden toegewezen: trekking 100 hoort bij B. Door houders van meer tickets vooraan te plaatsen, wordt deze zoekactie in de lijst gemiddeld korter.

Onderscheid verwachting van garantie

Als A 75 tickets heeft en B 25, is het verwachte aandeel van A 75%. Bij 100 onafhankelijke trekkingen met gelijke tijdschijven waarbij beide uitvoerbaar zijn, verwacht A 75 keer te winnen. De standaardafwijking is:

$\sqrt{100\times \mathrm{0,75}\times \mathrm{0,25}}\approx \mathrm{4,33}$ tijdschijven.

Een resultaat van ongeveer 71–79 overwinningen ligt binnen ongeveer één standaardafwijking van het gemiddelde; het is geen gegarandeerd bereik. Korte reeksen kunnen aanzienlijk afwijken van de beoogde verhouding 3:1. Naarmate het waarnemingsvenster groeit, wordt de relatieve willekeurige variatie kleiner. Loterijplanning biedt kansmatige eerlijkheid, geen exacte verdeling over een eindig venster of begrensde wachttijd tot de volgende beurt.

Voor twee taken met evenveel tickets en gelijke CPU-behoeften deelt de maat voor oneerlijkheid U het vroegere voltooiingstijdstip door het latere. De verhouding bereikt 1 wanneer ze tegelijk eindigen en is kleiner wanneer één veel eerder eindigt. Deze voltooiingsverhouding varieert vooral sterk bij korte taken die met loterijplanning worden gepland.

Verdeel tickets over gebruikers en afhankelijkheden

Met een lokaal ticketsysteem kan een gebruiker een toegewezen globale aanspraak lokaal verdelen. Gebruiker X heeft 200 globale tickets en wijst 300 lokale tickets toe aan X1 en 100 aan X2. Van de 400 lokale tickets heeft X1 driekwart, wat 150 globale tickets geeft; X2 krijgt er 50. Gebruiker Y heeft 100 globale tickets voor Y1. Het totaal is 300, dus X1 ontvangt naar verwachting 50%, X2 ongeveer 16,67% en Y1 ongeveer 33,33% van de betwiste CPU-tijd.

Ticketoverdracht leent de tickets van een client tijdelijk uit aan een server die werk voor de client doet en geeft ze terug wanneer het verzoek is voltooid. Dit volgt de werkafhankelijkheid. Met ticketinflatie kunnen samenwerkende taken hun eigen aantallen tickets verhogen om meer uitvoeringstijd te vragen. Dit vereist vertrouwen of grenzen: onbeperkte inflatie laat een hebzuchtige taak de aandelen van alle anderen verwateren.

Loterijplanning heeft tickettotalen nodig, maar geen registratie van hoeveel uitvoeringstijd elke taak voorligt. Een nieuwe taak draagt eenvoudig haar tickets bij aan de verzameling uitvoerbare taken. De toewijzing van tickets blijft een beleidskeuze; de willekeurige trekking dwingt die keuze in verwachting af. De tickets van een geblokkeerde taak dingen niet mee naar een tijdschijf die de taak niet kan gebruiken.

Strideplanning zet ticketaandelen om in een deterministische reeks. Elke uitvoerbare taak heeft een stapgrootte, berekend als een grote constante gedeeld door haar tickets, en een voortgangswaarde die haar gewogen voortgang bijhoudt. Kies de laagste voortgangswaarde, voer die taak één even lange tijdschijf uit en tel dan haar stapgrootte bij haar voortgangswaarde op.

Bereken de stapgroottes

A heeft 50 tickets, B 25 en C 100. Met constante 1.000 zijn hun stapgroottes 20, 40 en 10. Meer tickets leveren een kleinere stapgrootte op. De voortgangswaarde van een bevoordeelde taak stijgt langzaam, zodat die vaker het minimum wordt.

Begin alle voortgangswaarden bij nul en gebruik bij gelijke waarden de alfabetische volgorde. Houd de tuple in de vaste volgorde A, B, C:

Alleen de voortgangswaarde van de geselecteerde taak verandert. In zeven tijdschijven krijgt A twee beurten, B één en C vier: precies de verhouding 50:25:100. Bij de gezamenlijke voortgangswaarde 40 heeft elk dezelfde hoeveelheid gewogen uitvoeringstijd doorlopen. Tussen zulke gelijke standen hoeven aandelen over korte perioden niet exact te zijn.

Houd werkelijke uitvoering en virtuele voortgang gescheiden

De voortgangswaarde is een ordeningswaarde, geen verstreken tijd of aantal tickets. Door de grote stapgrootte van B wacht die taak terwijl A en C de voortgangswaarde inhalen. B krijgt nog steeds het beoogde aandeel van een zevende over deze herhalende cyclus. Het aantal tickets bij de voortgangswaarde optellen zou het ontwerp omkeren: de taak met de meeste tickets zou de grootste sprong maken en minder vaak worden gekozen.

De constante bepaalt de schaal van de stapgroottes, niet de beoogde ticketverhoudingen. Implementaties met gehele getallen hebben voldoende precisie nodig om te voorkomen dat afronding die verhoudingen vertekent. Vergelijkingen en updates moeten dezelfde schaal gebruiken.

Plaats een nieuwkomer verstandig

Stel dat bestaande taken voortgangswaarden rond 4.000 hebben. Een nieuwe taak die bij nul begint, zou herhaaldelijk winnen tijdens het inhalen, zelfs met weinig tickets. Initialiseer haar voortgangswaarde ten opzichte van de huidige systeemvoortgang, bijvoorbeeld op de huidige minimale voortgangswaarde, zodat ze geen uitvoeringstijd verzamelt voor de periode vóór haar aankomst.

De virtuele uitvoeringstijd van Linux gebruikt het verwante idee om gewogen voortgang toe te rekenen voor werkelijk ontvangen CPU-tijd. In beide ontwerpen laat een grotere aanspraak die voortgang langzamer groeien, zodat de taak blijft meedingen naar latere uitvoeringstijd.

De eerlijke schedulers van Linux houden gewogen CPU-tijd bij. De Completely Fair Scheduler (CFS), geïntroduceerd in Linux 2.6.23 in 2007, koos de uitvoerbare taak met de kleinste virtuele uitvoeringstijd. Linux begon die selectieregel in 6.6 in 2023 te vervangen door EEVDF.

Verdeel uitvoeringstijd naar gewicht

Een nice-waarde loopt van −20, met de meeste voorrang, tot +19, met de minste voorrang. Nice 0 heeft gewicht 1024. Elke stap naar een grotere nice-waarde verlaagt het gewicht met een factor van ongeveer 1,25. Voorbeeldgewichten zijn 3121 bij nice −5, 820 bij nice 1, 335 bij nice 5, 110 bij nice 10 en 15 bij nice 19.

Nice 0 tegenover nice 1 geeft $\frac{1024}{1024+820}\approx \mathrm{0,555}$, ongeveer 55,5% tegenover 44,5%. Aandelen hangen ongeveer af van het verschil tussen nice-waarden: $3121\mathrm{/}1024$ en $335\mathrm{/}110$ zijn beide ongeveer 3,05. Nice +19 krijgt in dit eenvoudige model met twee taken nog steeds ongeveer 1,4% wanneer het concurreert met nice 0.

Klassieke CFS verdeelt een beoogde planningslatentie naar gewicht:

Voor gewichten 1024, 1024 en 335 is het totaal 2383. Een beoogde periode van 48 ms geeft ongeveer 20,63 ms aan elk van de zwaardere taken en 6,75 ms aan de lichtere. Dit zijn illustratieve parameters, geen universele standaardwaarden van de kernel. Met vier gelijke taken geeft 48 ms elk 12 ms. Met tien zou 4,8 ms per taak onder een illustratieve minimale granulariteit van 6 ms vallen, dus moet de periode groeien.

Reken virtuele voortgang toe

CFS verhoogt de virtuele uitvoeringstijd van een draaiende taak met:

Een taak met gewicht 1024 krijgt één virtuele milliseconde per werkelijke milliseconde. Een taak met gewicht 335 krijgt er ongeveer 3,06. Door lichtere taken sneller voortgang toe te rekenen, moeten ze eerder wachten terwijl zwaardere taken meer werkelijke uitvoeringstijd krijgen.

Klassieke CFS ordent uitvoerbare taken in de wachtrij in een rood-zwartboom op virtuele uitvoeringstijd. Invoegen en verwijderen kosten logaritmische tijd; een in de cache bewaarde pointer naar de meest linkse knoop maakt het vinden van het minimum mogelijk in constante tijd. Geblokkeerde taken verlaten deze boom van uitvoerbare taken. De plaatsing bij ontwaken beperkt de mate waarin eerder slapen een onbeperkte aanspraak op inhaaltijd kan worden.

Kies met EEVDF uit taken die in aanmerking komen

Earliest Eligible Virtual Deadline First behoudt gewichten en registratie van virtuele uitvoeringstijd. Een taak heeft een positieve achterstand wanneer ze nog uitvoeringstijd tegoed heeft en een negatieve achterstand wanneer ze meer dan haar aanspraak heeft gekregen. Taken met een niet-negatieve achterstand komen in aanmerking. EEVDF kiest de taak die in aanmerking komt en de vroegste virtuele deadline heeft.

De deadline combineert de virtuele start van een verzoek met de aangevraagde uitvoeringsduur, omgerekend naar virtuele tijd. Het is een waarde voor de uitvoeringsvolgorde, geen beloofd voltooiingstijdstip op de klok. Een kortere aangevraagde tijdschijf kan een taak die in aanmerking komt een vroegere deadline geven en de latentie verbeteren zonder haar gewichtsaandeel op lange termijn te verhogen. Huidige Linux-versies ondersteunen aanvragen voor tijdschijven via sched_setattr().

Meerdere CPU's helpen alleen wanneer er parallel werk is. Eén thread draait op één logische CPU tegelijk; meerdere threads of onafhankelijke programma's kunnen samen meerdere CPU's gebruiken. Een scheduler moet kiezen welke taak draait en waar die draait.

Deel de verantwoordelijkheid voor planning

Bij symmetrische multiprocessing (SMP) voeren CPU's kernelcode uit en nemen ze zelf planningsbeslissingen. Bij asymmetrische multiprocessing coördineert één hoofdprocessor de planning terwijl andere toegewezen werk uitvoeren. Centrale besturing is eenvoudiger, maar de hoofdprocessor kan een knelpunt worden. Systemen voor algemeen gebruik gebruiken SMP.

Gelijktijdige beslissingen vereisen coördinatie. Als twee CPU's taken uit een gedeelde gereedwachtrij verwijderen, moeten de wijzigingen worden gesynchroniseerd zodat geen vermelding verloren gaat en dezelfde taak uit de wachtrij niet twee keer wordt gekozen. Meer CPU's kunnen de concurrentie om die gedeelde structuur vergroten.

Behoud nuttige cache-inhoud

Processorkernen hebben kleine snelle caches, meestal eigen L1- en L2-caches en een grotere L3-cache die meerdere kernen delen. Temporele lokaliteit betekent dat recent gebruikte gegevens opnieuw worden gebruikt. Ruimtelijke lokaliteit betekent dat nabijgelegen gegevens worden gebruikt, zoals opeenvolgende array-elementen.

Een sorterende thread op kern 0 vult de caches en TLB van die kern. Als de thread daar na een korte preëmptie wordt hervat, kunnen veel benodigde vermeldingen nog aanwezig zijn. Op kern 3 moet de thread mogelijk dezelfde gegevens opnieuw ophalen uit een gedeelde cache of het geheugen. Cacheaffiniteit is de neiging van de scheduler om een thread dicht bij de recent gebruikte CPU te houden. Het precieze voordeel hangt af van wat in de cache blijft en van de topologie van gedeelde caches.

Onderscheid coherentie van synchronisatie

Cachecoherentie voorkomt dat kernen onbeperkt tegenstrijdige gecachte kopieën van één geheugenlocatie gebruiken. Busverkeer afluisteren is één mogelijke implementatie: caches observeren verkeer en maken kopieën ongeldig of werken die bij wanneer een andere kern schrijft. Grotere systemen kunnen andere coherentiemechanismen gebruiken.

Coherentie maakt van meerdere instructies geen enkele atomaire bewerking. Als twee CPU's allebei een wachtrijlengte lezen, vermeldingen wijzigen en de lengte terugschrijven, laten coherente afzonderlijke lees- en schrijfbewerkingen nog steeds schadelijke vervlechtingen toe. De scheduler heeft vergrendelingen of een andere synchronisatiemethode nodig voor de hele wijziging. De gedeelde cacheregel van een vergrendeling kan zelf tussen kernen bewegen terwijl die erom concurreren.

Lees de hardware-indeling

Intel noemt zijn SMT-implementatie Hyper-Threading. Twee drukke threads op logische CPU's van dezelfde kern concurreren om de bronnen van die kern; twee logische CPU's zijn niet gelijk aan twee onafhankelijke fysieke kernen. Een NUMA-migratie kan berekeningen ook verder van het gebruikte geheugen brengen, zelfs wanneer het opwarmen van de cache kort duurt.

Een thread naar een ongebruikte CPU verplaatsen kan een lange wachtrijvertraging wegnemen. De thread op zijn plaats houden kan lokaliteit behouden. Vergelijk die kosten aan de hand van de werkelijke werklast: affiniteit is een prestatievoorkeur, terwijl een expliciet affiniteitsmasker beperkt welke CPU's überhaupt zijn toegestaan.

Een multiprocessorscheduler heeft een plaats nodig om gereedstaand werk te bewaren. Eén gedeelde wachtrij maakt werk gemakkelijk te vinden. Afzonderlijke wachtrijen per CPU verminderen concurrentie om gedeelde bronnen en behouden de plaatsing, maar kunnen één CPU overbelast laten terwijl een andere niets doet.

Vergelijk wachtrijontwerpen

Bij multiprocessorplanning met één wachtrij halen alle CPU's werk uit één gedeelde wachtrij. Als taken op elke CPU kunnen draaien, vult wachtend werk vanzelf een ongebruikte CPU. Een gedeelde vergrendeling beschermt de wachtrij, zodat een groter aantal CPU's die vergrendeling tot een knelpunt kan maken.

Met vijf round-robintaken A–E op vier CPU's wijst een mogelijke reeks A, B, C, D toe in de eerste ronde; E, A, B, C in de tweede; en D, E, A, B in de derde. A draait op CPU 0, daarna 1 en daarna 2. De machine blijft bezig, maar A wisselt herhaaldelijk van eigen caches. Affiniteitsregels kunnen de meeste plaatsingen behouden en geselecteerde taken verplaatsen om het werk te verdelen.

Merk ongelijke aandelen op

Bij multiprocessorplanning met meerdere wachtrijen plant elke CPU zijn eigen wachtrij. Stel dat CPU 0 A en C heeft en CPU 1 B en D, allemaal CPU-gebonden en lokaal delend volgens round-robinplanning. Aanvankelijk krijgt elke taak een halve CPU. Wanneer C eindigt, krijgt A heel CPU 0, terwijl B en D nog steeds elk de helft van CPU 1 krijgen.

De machine blijft volledig bezet, maar de taken krijgen niet langer gelijke aandelen. Als A ook eindigt, gaat CPU 0 niets doen hoewel B en D gereed zijn. Door één ervan naar CPU 0 te verplaatsen krijgen beide een volledige CPU en wordt eerder ongebruikte capaciteit benut.

Met drie gelijke CPU-gebonden taken en twee CPU's is gelijke uitvoering op lange termijn twee derde van een CPU per taak. Bij een vaste plaatsing staat één taak alleen en delen twee taken een CPU. Door periodiek af te wisselen welke taak alleen staat, kun je de gelijke verdeling benaderen. Niet één thread draait op beide CPU's tegelijk.

Beslis wanneer je migreert

Migratie verplaatst een taak naar de wachtrij van een andere CPU. Werk stelen is een haalstrategie: een CPU met weinig werk bekijkt de wachtrij van een drukkere CPU en neemt werk over. Vaak controleren veroorzaakt synchronisatieverkeer; zelden controleren laat ongelijke belasting voortbestaan. Bij stelen moet ook rekening worden gehouden met toegestane CPU's en geheugenlokaliteit.

Vergelijk de verwachte bespaarde wachttijd met de migratiekosten. Een lange wachtrij op één CPU en een ongebruikte geschikte CPU vormen een sterke reden om te verplaatsen. Een klein tijdelijk verschil tussen wachtrijen kan verdwijnen voordat de kosten van een koude cache zijn terugverdiend.

De O(1)- en CFS-ontwerpen van Linux gebruikten uitvoeringswachtrijen per CPU; Linux verdeelt de belasting over hardwareplanningsdomeinen en houdt rekening met gedeelde kernen en sockets. De alternatieve BF Scheduler gebruikte één wachtrij. Gebruikers kunnen plaatsing beperken met taskset of sched_setaffinity() op Linux en SetThreadAffinityMask() op Windows. Een beperkt affiniteitsmasker kan verklaren waarom een gereedstaande taak een ogenschijnlijk ongebruikte CPU niet gebruikt.

Linux plant threads, die in de kernel taken worden genoemd. Het planningsbeleid, de nice-waarde, groepsinstellingen en CPU-affiniteit van een taak beantwoorden verschillende vragen over wanneer en waar die draait.

Lees eerst het beleid

De normale beleidsvormen hebben statische prioriteit 0. Realtime-FIFO en -RR gebruiken 1–99, waarbij 99 het hoogst is. Een FIFO-taak gaat door totdat die blokkeert, de beurt afstaat of wordt onderbroken door werk met hogere prioriteit. RR voegt beurten toe voor taken met gelijke prioriteit; sched_rr_get_interval() geeft het tijdkwantum. Deze namen beschrijven Linux-beleid: normale eerlijke planning is niet het RR-algoritme met gelijke tijdschijven uit het leerboek.

Verander aandelen en plaatsing

Nice loopt van −20 tot +19, met standaard 0. Grotere waarden verlagen het gewicht in de eerlijke klasse met ongeveer een factor 1,25 per stap. Bij een gebruikelijke start met nice 0 start nice -n 10 make een bouwproces met nice 10; -n is een aanpassing van de overgeërfde nice-waarde. renice -n 5 -p 4321 stelt het doelproces in op nice 5. Een gebruiker kan eigen werk minder voorrang geven; voor het verhogen van de prioriteit is een geschikt privilege of een toegestane brongrens nodig.

taskset -c 0,1 ./app staat toe dat een programma op CPU's 0 en 1 draait. Het maakt geen tweede thread aan en belooft geen exclusief gebruik van een van beide CPU's. ps -o pid,cls,ni,rtprio,comm toont velden die met beleid samenhangen, terwijl top helpt om prioriteit, nice en CPU-verbruik te observeren.

chrt -f 50 ./app kiest FIFO-realtimeprioriteit 50. Gebruik realtime-instellingen alleen in een gecontroleerde omgeving: een drukke thread met hoge prioriteit kan de shell en essentieel systeemwerk vertragen. Standaardlimieten voor realtimebandbreedte reserveren enige tijd voor normaal werk, maar zorgen er niet voor dat elke dergelijke werklast snel reageert. Voorrang verandert de toegang tot CPU-tijd, niet de snelheid van een instructie.

Onderscheid groepsgewicht van quotum

In cgroup v2 loopt cpu.weight van 1 tot 10.000, met standaard 100, en verdeelt het betwiste CPU-capaciteit in de eerlijke klasse over actieve nevengroepen. Gewichten 200 en 100 geven ongeveer twee derde en een derde van één CPU wanneer beide groepen bezig zijn. Als de tweede niets gaat doen, kan de eerste alle beschikbare capaciteit gebruiken.

cpu.max stelt een bandbreedtelimiet in. De waarde “50000 100000” staat 50 ms gezamenlijke CPU-tijd per periode van 100 ms toe, gemiddeld gelijk aan een halve CPU. Meerdere threads kunnen dat budget parallel verbruiken en het eerder in verstreken tijd uitputten. Een begrensde groep kan worden afgeremd, zelfs wanneer er CPU-capaciteit over is.

Plaats de namen in de geschiedenis

De O(1)-scheduler van Linux 2.6.0 gebruikte prioriteitsarrays en terugkoppeling over interactiviteit. CFS verscheen in 2.6.23 in 2007. Linux 6.6 begon in 2023 de overgang naar EEVDF-selectie in de eerlijke klasse. Sinds Linux 6.12 in 2024 ondersteunt sched_ext dynamisch geladen BPF-planningsbeleid op daarvoor geconfigureerde kernels. Als zo'n scheduler faalt of uitvoerbaar werk laat vastlopen, herstelt de kernel de ingebouwde planning.

Windows plant gereedstaande threads op prioriteit van 0 tot en met 31, waarbij grotere getallen hoger zijn. Gereedstaande threads met gelijke prioriteit wisselen elkaar af volgens round-robinplanning. Een nieuw gereedstaande thread met hogere prioriteit onderbreekt een thread met lagere prioriteit zonder te wachten tot het tijdkwantum daarvan eindigt. Prioriteit 0 behoort toe aan de thread die vrije pagina's met nullen vult.

Bepaal de basisprioriteit uit twee instellingen

De basisprioriteit van een thread hangt af van de prioriteitsklasse van het proces en het eigen relatieve threadniveau. Procesklassen zijn inactief, onder normaal, normaal, boven normaal, hoog en realtime. Threadniveaus omvatten inactief, laagste, onder normaal, normaal, boven normaal, hoogste en tijdkritisch.

Tijdkritisch geeft 15 buiten de klasse realtime en 31 daarbinnen. Threadniveau inactief geeft 1 buiten realtime en 16 daarbinnen. Deze grensniveaus zijn bijzondere tabelvermeldingen, dus een vaste waarde bij elke klasse optellen zou verkeerde resultaten geven.

Volg een tijdelijke verhoging

Prioriteiten 1–15 vormen het variabele bereik; 16–31 vormen het realtimebereik. Een thread begint met een dynamische prioriteit gelijk aan de basisprioriteit. Voor threads in het variabele bereik kunnen gebeurtenissen zoals invoer of het einde van een wachtperiode de dynamische prioriteit tijdelijk verhogen. Threads met een realtimebasisprioriteit krijgen zulke verhogingen niet.

Stel dat een thread met basisprioriteit 8 wordt verhoogd naar 14. Als de thread blijft rekenen, daalt de dynamische prioriteit na elk volledig tijdkwantum één niveau: 13 na het eerste, 12 na het tweede en 8 na het zesde. De verhoging verandert de basisprioriteit niet blijvend en neemt niet af tot onder die basis.

Dit is terugkoppeling: recent gedeblokkeerd werk krijgt snel uitvoeringstijd, terwijl aanhoudend CPU-gebruik het tijdelijke voordeel verliest. Windows gebruikt ook tijdelijke verhogingen voor lang wachtende gereedstaande threads om uithongering tegen te gaan. Zo'n verhoging kan een taak met lage rang die een vergrendeling vasthoudt helpen vooruitgang te boeken, maar is een ander mechanisme dan prioriteitsovererving voor een specifieke vergrendeling.

Herken verwante ontwerpen

De tijdsverdelingsklasse van Solaris is een tabelgestuurd MLFQ-ontwerp. ULE van FreeBSD gebruikt uitvoeringswachtrijen per CPU en vergelijkt slaapgedrag met uitvoeringsgedrag om interactieve threads te herkennen. Deze systemen delen het idee om de uitvoering aan te passen aan waargenomen gedrag zonder identieke wachtrijregels te gebruiken.

macOS biedt dienstkwaliteitsklassen (QoS), waaronder gebruikersinteractief, door gebruiker gestart, standaard, hulpprogramma en achtergrond. Die beschrijven de urgentie van werk. Op Apple silicon helpt QoS het systeem om werk over prestatie- en efficiëntiekernen te verdelen. Programma's geven het belang van het werk door; het besturingssysteem kiest de plaatsing volgens het beleid en de beschikbare hardware.

Bestaande schedulers combineren terugkoppeling, prioriteiten, eerlijkheid en affiniteit. Een Windows-klasse realtime heeft sterkere voorrang, maar garandeert geen snellere berekening of volledige correctheid voor realtimegebruik.

Kies het doel van de werklast voordat je een scheduler kiest. Bij een batchwachtrij kan het belangrijk zijn dat veel kleine taken snel worden voltooid. Een editor heeft na invoer snelle bediening nodig. Een gedeelde server heeft een verdedigbare verdeling tussen gebruikers of groepen nodig.

Stem het mechanisme af op het doel

Vergelijk beleid met dezelfde invoer

A komt aan op 0 ms en heeft 8 ms nodig, B op 1 ms en heeft 4 ms nodig, en C op 2 ms en heeft 2 ms nodig. Negeer wisselkosten. FIFO voert A, B, C uit. SJF begint ook met A, maar voert daarna C vóór B uit. STCF voert A 0–1, B 1–2, C 2–4, B 4–7, A 7–14 uit. RR gebruikt een tijdkwantum van 2 ms, waarbij taken die op de grens aankomen vóór de taak met de verlopen tijdschijf in de wachtrij komen.

STCF wint bij deze werklast op beide maatstaven omdat elke nieuw aankomende kortere taak onmiddellijk draait. RR laat taken snel beginnen zonder burstlengtes te kennen. Als even lange taken tegelijk aankomen, kan FIFO een lagere gemiddelde doorlooptijd hebben dan RR. Een rangorde bij één werklast zegt iets over die werklast.

Kies een beoordelingsmethode

Deterministische modellering berekent een vast verloop met de hand. Ze geeft exacte resultaten voor de invoer en maakt beslissingen gemakkelijk te onderzoeken, maar laat vaak dispatch- en cachekosten weg. Wachtrijmodellen beschrijven aankomst- en bedieningspatronen met verdelingen en voorspellen gemiddeld gedrag.

Voor een stabiel systeem in een stationaire toestand verbindt de wet van Little het gemiddelde aantal taken $n$, de aankomstsnelheid $\lambda$ en de gemiddelde verblijftijd $W$:

Bij 14 taken/s en een gemiddelde tijd van 0,5 s in het systeem is het gemiddelde aantal 7 taken. Houd de grens consistent: bij het aantal in de gereedwachtrij hoort de wachttijd in die wachtrij, terwijl bij het aantal in het hele systeem de tijd in het hele systeem hoort. Zet eenheden om voordat je vermenigvuldigt.

Simulatie voert een schedulermodel uit, vaak met een geregistreerde werklast. Daarmee kun je ingewikkelde aankomst- en blokkeringspatronen onderzoeken, maar de conclusies hangen af van het model en de gekozen registraties. Implementatie meet de scheduler in een echt besturingssysteem en omvat de werkelijke overhead; dit kost meer moeite en vereist nog steeds representatieve werklasten en herhaalbare metingen.

Bekijk naast gemiddelden ook doorvoer, bezettingsgraad, individuele vertragingen en vertragingen in de staart, eerlijkheid en energiegebruik. Bij een multiprocessor kan een drukke machine de uitvoeringstijd nog steeds ongelijk verdelen of tijd verspillen aan het opnieuw vullen van caches. Vergelijk beleidsvormen met hetzelfde waarnemingsvenster en dezelfde werklast en varieer vervolgens de werklastkenmerken die voor de beoogde gebruikers van belang zijn.