Planlægning (computing) - Scheduling (computing)

I computeren er planlægning handlingen med at tildele ressourcer til at udføre opgaver . De ressourcer kan være processorer , netværksforbindelser eller udvidelseskort . De opgaver kan være tråde , processer eller data flow .

Planlægningsaktiviteten udføres af en proces kaldet scheduler . Planlægningsprogrammer er ofte designet til at holde alle computerressourcer optaget (som ved belastningsbalancering ), give flere brugere mulighed for at dele systemressourcer effektivt eller for at opnå en målkvalitet i servicen .

Planlægning er grundlæggende for selve beregningen og en iboende del af eksekveringsmodellen for et computersystem; begrebet planlægning gør det muligt at have computer multitasking med en enkelt central processor (CPU).

Mål

En planlægger kan sigte mod et eller flere mål, for eksempel:

• maksimering af gennemstrømning (den samlede mængde arbejde udført pr. tidsenhed);
• minimering af ventetid (tiden fra arbejdet bliver klar, indtil det første punkt begynder udførelsen);
• minimering af latenstid eller responstid (tiden fra arbejdet bliver klar, indtil det er færdigt i tilfælde af batchaktivitet, eller indtil systemet reagerer og afleverer det første output til brugeren i tilfælde af interaktiv aktivitet);
• maksimere fairness (lige CPU -tid til hver proces eller mere generelt passende tidspunkter i henhold til prioriteten og arbejdsbyrden for hver proces).

I praksis er disse mål ofte i konflikt (f.eks. Gennemstrømning versus forsinkelse), og derfor vil en planlægger implementere et passende kompromis. Præference måles ved en af ​​ovennævnte bekymringer afhængigt af brugerens behov og mål.

I realtidsmiljøer , såsom integrerede systemer til automatisk styring i industrien (f.eks. Robotteknologi ), skal planlæggeren også sikre, at processer kan overholde deadlines ; dette er afgørende for at holde systemet stabilt. Planlagte opgaver kan også distribueres til eksterne enheder på tværs af et netværk og administreres gennem en administrativ backend.

Typer af operativsystemplanlæggere

Planlæggeren er et operativsystemmodul, der vælger de næste job, der skal optages i systemet, og den næste proces, der skal køres. Operativsystemer kan indeholde op til tre forskellige planlæggertyper: en langsigtet planlægger (også kendt som en optagelsesplanlægger eller planlægger på højt niveau), en planlægger på mellemlang eller mellemlang sigt og en kortfristet planlægger . Navnene antyder den relative frekvens, hvormed deres funktioner udføres.

Procesplanlægger

Procesplanlæggeren er en del af operativsystemet, der bestemmer, hvilken proces der kører på et bestemt tidspunkt. Det har normalt evnen til at sætte en igangværende proces på pause, flytte den bag på løbekøen og starte en ny proces; sådan en planlægger er kendt som en præventiv planlægger , ellers er den en kooperativ planlægger .

Vi skelner mellem "langsigtet planlægning", "planlægning på mellemlangt sigt" og "korttidsplanlægning" baseret på, hvor ofte beslutninger skal træffes.

Langsigtet planlægning

Den langsigtede planlægger eller optagelsesplanlægger beslutter, hvilke job eller processer der skal optages i den klare kø (i hovedhukommelsen); det vil sige, når der gøres et forsøg på at udføre et program, er dets optagelse i sættet af aktuelt udførte processer enten godkendt eller forsinket af den langsigtede planlægger. Denne planlægger dikterer således, hvilke processer der skal køres på et system, og graden af ​​samtidighed, der skal understøttes på én gang-om mange eller få processer skal udføres samtidigt, og hvordan opdelingen mellem I/O-intensiv og CPU -intensive processer skal håndteres. Den langsigtede planlægger er ansvarlig for at kontrollere graden af ​​multiprogrammering.

Generelt kan de fleste processer beskrives som enten I/O-bundet eller CPU-bundet . En I/O-bundet proces er en, der bruger mere af sin tid på at lave I/O, end den bruger på at lave beregninger. En CPU-bundet proces derimod genererer I/O-anmodninger sjældent og bruger mere af sin tid til at lave beregninger. Det er vigtigt, at en langsigtet planlægger vælger en god procesblanding af I/O-bundne og CPU-bundne processer. Hvis alle processer er I/O-bundne, vil den klare kø næsten altid være tom, og den kortsigtede planlægger har lidt at gøre. På den anden side, hvis alle processer er CPU-bundne, vil I/O-ventekøen næsten altid være tom, enheder vil gå ubrugt, og igen vil systemet være ubalanceret. Systemet med den bedste ydelse vil således have en kombination af CPU-bundne og I/O-bundne processer. I moderne operativsystemer bruges dette til at sikre, at realtidsprocesser får nok CPU-tid til at afslutte deres opgaver.

Langsigtet planlægning er også vigtig i store systemer, såsom batchbehandlingssystemer , computerklynger , supercomputere og renderfarme . For eksempel i parallelle systemer , coscheduling af interagerende processer er ofte nødvendigt for at forhindre dem i at blokere på grund venter på hinanden. I disse tilfælde bruges software til specialjob - planlægger typisk til at hjælpe disse funktioner ud over enhver underliggende adgangsplanlægningsstøtte i operativsystemet.

Nogle operativsystemer tillader kun tilføjelse af nye opgaver, hvis det er sikkert, at alle tidsfrister i realtid stadig kan overholdes. Den specifikke heuristiske algoritme, der bruges af et operativsystem til at acceptere eller afvise nye opgaver, er adgangskontrolmekanismen .

Planlægning på mellemlang sigt

Den mellemfristede planlægger fjerner midlertidigt processer fra hovedhukommelsen og placerer dem i sekundær hukommelse (f.eks. Et harddiskdrev ) eller omvendt, som almindeligvis kaldes "bytte ud" eller "bytte ind" (også forkert som " personsøgning out "eller" paging in "). Den mellemfristede planlægger kan beslutte at skifte en proces ud, som ikke har været aktiv i et stykke tid, eller en proces, der har lav prioritet, eller en proces, der ofte fejler sider , eller en proces, der fylder meget hukommelse for at frigøre hovedhukommelse til andre processer, bytte processen tilbage senere, når mere hukommelse er tilgængelig, eller når processen er blevet blokeret og ikke længere venter på en ressource. [Stallings, 396] [Stallings, 370]

I mange systemer i dag (dem, der understøtter kortlægning af virtuelt adresserum til andet sekundært lager end swapfilen), kan den mellemfristede planlægger faktisk udføre rollen som den langsigtede planlægger ved at behandle binære filer som "udskiftede processer" på deres udførelse. På denne måde, når et segment af binæret er påkrævet, kan det byttes ind på forespørgsel eller "doven ladet", [Stallings, 394] også kaldet demand paging .

Kortsigtet planlægning

Den kortsigtede planlægger (også kendt som CPU-planlæggeren ) beslutter, hvilken af ​​de klare processer i hukommelsen, der skal udføres (tildelt en CPU) efter et urafbrydelse , et I/O-afbrydelse, et opkald til operativsystemet eller en anden form af signal . Således tager den kortsigtede planlægger planlægningsbeslutninger meget oftere end de langsigtede eller midtvejsplanlæggere-en planlægningsbeslutning skal som minimum træffes efter hver tidsskive, og disse er meget korte. Denne planlægger kan være præventiv og indebære, at den er i stand til med magt at fjerne processer fra en CPU, når den beslutter at allokere denne CPU til en anden proces eller ikke-præventiv (også kendt som "frivillig" eller "kooperativ"), hvor hvis planlæggeren ikke er i stand til at "tvinge" processer fra CPU'en.

En præventiv planlægger er afhængig af en programmerbar intervaltimer, som påkalder en afbrydelseshandler, der kører i kernetilstand og implementerer planlægningsfunktionen.

Afsender

En anden komponent, der er involveret i CPU-planlægningsfunktionen, er afsenderen, som er modulet, der giver kontrol over CPU'en til den proces, der vælges af den kortsigtede planlægger. Det modtager kontrol i kernetilstand som følge af et afbrydelse eller systemopkald. Afsenderens funktioner involverer følgende:

• Kontekstkontakter , hvor afsenderen gemmer tilstanden (også kendt som kontekst ) for den proces eller tråd, der tidligere kørte; afsenderen indlæser derefter den første eller tidligere gemte tilstand for den nye proces.
• Skift til brugertilstand.
• Springe til den korrekte placering i brugerprogrammet for at genstarte det program, der er angivet ved dets nye tilstand.

Afsenderen skal være så hurtig som muligt, da den påberåbes under hver procesafbryder. Under kontekstkontakterne er processoren praktisk talt inaktiv i en brøkdel af tiden, og derfor bør unødvendige kontekstskift undgås. Den tid, det tager for afsenderen at stoppe en proces og starte en anden, kaldes afsendelsesforsinkelsen .

Planlægning af discipliner

En planlægningsdisciplin (også kaldet planlægningspolitik eller planlægningsalgoritme ) er en algoritme, der bruges til at distribuere ressourcer mellem parter, der samtidigt og asynkront anmoder om dem. Planlægningsdiscipliner bruges i routere (til at håndtere pakketrafik) såvel som i operativsystemer (til at dele CPU -tid mellem både tråde og processer ), diskdrev ( I/O -planlægning ), printere ( printspooler ), de fleste integrerede systemer osv. .

Hovedformålene med planlægningsalgoritmer er at minimere ressource sult og at sikre retfærdighed blandt de parter, der udnytter ressourcerne. Planlægning omhandler problemet med at beslutte, hvilken af ​​de udestående anmodninger, der skal tildeles ressourcer. Der er mange forskellige planlægningsalgoritmer. I dette afsnit introducerer vi flere af dem.

I pakkekoblede computernetværk og anden statistisk multiplexering bruges forestillingen om en planlægningsalgoritme som et alternativ til først-til-mølle- kø i datapakker.

De enkleste planlægningsalgoritmer med bedste indsats er round-robin , fair queuing (en max-min fair scheduling algoritme), proportionel-fair planlægning og maksimal gennemstrømning . Hvis differentieret eller garanteret servicekvalitet tilbydes, i modsætning til kommunikation med bedste indsats, kan vægtet fair kø bruges.

I avancerede pakkeradio-trådløse netværk såsom HSDPA (High-Speed ​​Downlink Packet Access) 3.5G- cellesystem kan kanalafhængig planlægning bruges til at udnytte information om kanalstatus . Hvis kanalforholdene er gunstige, kan gennemstrømningen og systemets spektrale effektivitet øges. I endnu mere avancerede systemer som LTE kombineres planlægningen ved kanalafhængig pakke-for-pakke dynamisk kanaltildeling eller ved at tildele OFDMA- multibærere eller andre frekvensdomæneudligningskomponenter til de brugere, der bedst kan udnytte dem.

Først til mølle får først malet

Først ind, først ud ( FIFO ), også kendt som først til mølle (FCFS), er den enkleste planlægningsalgoritme. FIFO køer ganske enkelt processer i den rækkefølge, de ankommer i den klare kø. Dette bruges almindeligvis til en opgavekø , f.eks. som illustreret i dette afsnit.

• Da kontekstskift kun forekommer ved procesafslutning, og der ikke kræves nogen reorganisering af proceskøen, er planlægning af omkostninger minimal.
• Gennemstrømning kan være lav, fordi lange processer kan holde CPU'en, hvilket får de korte processer til at vente længe (kendt som konvojeffekten).
• Ingen sult, fordi hver proces får mulighed for at blive udført efter en bestemt tid.
• Vendetid , ventetid og svartid afhænger af rækkefølgen af ​​deres ankomst og kan være høj af de samme årsager ovenfor.
• Der sker ingen prioritering, og derfor har dette system problemer med at overholde procesfrister.
• Den manglende prioritering betyder, at så længe hver proces til sidst er fuldført, er der ingen sult. I et miljø, hvor nogle processer muligvis ikke gennemføres, kan der være sult.
• Det er baseret på kø.

Prioriteret planlægning

Tidligste deadline først (EDF) eller mindst tid til at gå er en dynamisk planlægningsalgoritme, der bruges i operativsystemer i realtid til at placere processer i en prioritetskø. Når der opstår en planlægningshændelse (en opgave er afsluttet, en ny opgave frigives osv.), Søges der i køen efter den proces, der er nærmest dens deadline, som vil blive den næste, der skal planlægges til udførelse.

Korteste resterende tid først

Ligner det korteste job først (SJF). Med denne strategi arrangerer planlæggeren processer med den mindst anslåede behandlingstid tilbage til at være den næste i køen. Dette kræver avanceret viden eller estimater om den tid, der kræves, før en proces kan gennemføres.

• Hvis der kommer en kortere proces under en anden proces 'eksekvering, afbrydes den aktuelt kørende proces (kendt som præemption), og opdeler denne proces i to separate datablokke. Dette skaber overskydende omkostninger gennem yderligere kontekstskift. Planlæggeren skal også placere hver indgående proces på et bestemt sted i køen og skabe yderligere overhead.
• Denne algoritme er designet til maksimal gennemstrømning i de fleste scenarier.
• Ventetid og responstid stiger, efterhånden som procesens beregningskrav stiger. Da behandlingstid er baseret på ventetid plus behandlingstid, påvirkes længere processer betydeligt af dette. Den samlede ventetid er mindre end FIFO, da ingen proces skal vente på afslutningen af ​​den længste proces.
• Der lægges ikke særlig vægt på deadlines, programmereren kan kun forsøge at gøre processer med deadlines så korte som muligt.
• Sult er mulig, især i et travlt system med mange små processer, der køres.
• For at bruge denne politik bør vi have mindst to processer med forskellig prioritet

Fast prioriteret præventiv planlægning

Operativsystemet tildeler hver proces en fast prioritetsrangering, og planlæggeren arrangerer processerne i klar kø i rækkefølge efter deres prioritet. Lavere prioriterede processer bliver afbrudt af indgående processer med højere prioritet.

• Overhead er ikke minimal, og den er heller ikke signifikant.
• FPPS har ingen særlig fordel med hensyn til gennemstrømning i forhold til FIFO -planlægning.
• Hvis antallet af placeringer er begrænset, kan det karakteriseres som en samling af FIFO -køer, en for hver prioriteret placering. Processer i køer med lavere prioritet vælges kun, når alle køer med højere prioritet er tomme.
• Ventetid og svartid afhænger af procesens prioritet. Højere prioriterede processer har mindre ventetid og svartider.
• Deadlines kan overholdes ved at give processer med deadlines en højere prioritet.
• Sultning af processer med lavere prioritet er mulig med et stort antal højt prioriterede processer, der står i kø til CPU-tid.

Round-robin planlægning

Planlæggeren tildeler en fast tidsenhed pr. Proces og cykler igennem dem. Hvis processen afsluttes inden for denne tidsperiode, afsluttes den, ellers omlægges den efter at have givet alle andre processer en chance.

• RR -planlægning indebærer omfattende omkostninger, især med en lille tidsenhed.
• Balanceret gennemstrømning mellem FCFS/ FIFO og SJF/ SRTF, kortere job udføres hurtigere end i FIFO og længere processer gennemføres hurtigere end i SJF.
• God gennemsnitlig responstid, ventetid er afhængig af antal processer og ikke gennemsnitlig proceslængde.
• På grund af høje ventetider overholdes sjældent deadlines i et rent RR -system.
• Sult kan aldrig forekomme, da der ikke prioriteres. Tidsordningens enhedstildeling er baseret på proces ankomsttid, svarende til FIFO.
• Hvis Time-Slice er stor, bliver det til FCFS /FIFO, eller hvis det er kort, bliver det til SJF /SRTF.

Planlægning af køer på flere niveauer

Dette bruges til situationer, hvor processer let opdeles i forskellige grupper. For eksempel foretages en fælles opdeling mellem forgrundsprocesser (interaktive) og baggrundsprocesser (batch). Disse to typer processer har forskellige svartidskrav og kan derfor have forskellige planlægningsbehov. Det er meget nyttigt til problemer med delt hukommelse .

Arbejdsbesparende planlæggere

En arbejdsbesparende planlægger er en planlægger, der altid forsøger at holde de planlagte ressourcer optaget, hvis der er indsendte job klar til at blive planlagt. I modsætning hertil er en ikke-arbejdsbesparende planlægger en planlægger, der i nogle tilfælde kan efterlade de planlagte ressourcer inaktive på trods af tilstedeværelsen af ​​job, der er klar til at blive planlagt.

Planlægning af optimeringsproblemer

Der er flere planlægningsproblemer, hvor målet er at afgøre, hvilket job der går til hvilken station på hvilket tidspunkt, således at den samlede produktionsperiode minimeres:

• Planlægning af jobbutik  - der er n job og m identiske stationer. Hvert job skal udføres på en enkelt maskine. Dette betragtes normalt som et online problem.
• Planlægning i åben butik  -der er n job og m forskellige stationer. Hvert job skal bruge lidt tid på hver station, i en gratis rækkefølge.
• Flow shop planlægning  - der er n job og m forskellige stationer. Hvert job skal bruge noget tid på hver station i en forudbestemt rækkefølge.

Manuel planlægning

En meget almindelig metode i integrerede systemer er at planlægge job manuelt. Dette kan for eksempel gøres på en tidsmultiplekset måde. Nogle gange er kernen opdelt i tre eller flere dele: Manuel planlægning, præventivt og afbrydelsesniveau. Nøjagtige metoder til planlægning af job er ofte proprietære.

• Ingen ressource sult problemer
• Meget høj forudsigelighed; muliggør implementering af hårde realtidssystemer
• Næsten ingen omkostninger
• Måske er det ikke optimalt for alle applikationer
• Effektiviteten er helt afhængig af implementeringen

Valg af en planlægningsalgoritme

Når man designer et operativsystem, skal en programmør overveje, hvilken planlægningsalgoritme der vil fungere bedst til den brug, systemet kommer til at se. Der er ingen universel "bedste" planlægningsalgoritme, og mange operativsystemer bruger udvidede eller kombinationer af planlægningsalgoritmerne ovenfor.

For eksempel bruger Windows NT /XP /Vista en feedback-kø på flere niveauer , en kombination af forudgående planlægning med fast prioritet, round-robin og først ind, først ud-algoritmer. I dette system kan tråde dynamisk stige eller falde i prioritet afhængigt af, om det allerede er blevet serviceret, eller hvis det har ventet meget. Hvert prioritetsniveau repræsenteres af sin egen kø, med planlægning af round-robin blandt de højt prioriterede tråde og FIFO blandt de med lavere prioritet. I denne forstand er svartiden kort for de fleste tråde, og korte, men kritiske systemtråde bliver afsluttet meget hurtigt. Da tråde kun kan bruge en tidsenhed i round-robin i køen med højeste prioritet, kan sult være et problem for længere højt prioriterede tråde.

Operativsystem proces planlægger implementeringer

Den anvendte algoritme kan være så enkel som round-robin , hvor hver proces får lige lang tid (f.eks. 1 ms, normalt mellem 1 ms og 100 ms) i en cykelliste. Så proces A udføres i 1 ms, derefter proces B, derefter proces C, derefter tilbage til proces A.

Mere avancerede algoritmer tager højde for procesprioritet eller procesens betydning. Dette giver nogle processer mulighed for at bruge mere tid end andre processer. Kernen bruger altid de ressourcer, den har brug for for at sikre, at systemet fungerer korrekt, og det kan siges at have uendelig prioritet. I SMP -systemer anses processoraffinitet for at øge den samlede systemydelse, selvom det kan få en proces til at køre langsommere. Dette forbedrer generelt ydeevnen ved at reducere cache -thrashing .

OS/360 og efterfølgere

IBM OS/360 var tilgængelig med tre forskellige planlæggere. Forskellene var sådan, at varianterne ofte blev betragtet som tre forskellige operativsystemer:

• Muligheden Single Sequential Scheduler , også kendt som det primære kontrolprogram (PCP), gav sekventiel udførelse af en enkelt arbejdsstrøm.
• Muligheden Multiple Sequential Scheduler , kendt som Multiprogramming with a Fixed Number of Tasks (MFT), udførte udførelse af flere samtidige job. Udførelse var styret af en prioritet, der havde en standard for hver stream eller kunne anmodes om separat for hvert job. MFT version II tilføjede delopgaver (tråde), som udføres med en prioritet baseret på forælderjobbet. Hver jobstrøm definerede den maksimale mængde hukommelse, der kunne bruges af ethvert job i denne strøm.
• Muligheden Multiple Priority Schedulers eller Multiprogramming with a Variable Number of Tasks (MVT) indeholdt delopgaver fra starten; hvert job anmodede om prioritet og hukommelse, det krævede før udførelse.

Senere virtuelle lagringsversioner af MVS tilføjede en Workload Manager -funktion til planlæggeren, som planlægger processorressourcer i henhold til et udførligt skema, der er defineret af installationen.

Windows

Meget tidligt MS-DOS og Microsoft Windows-systemer var ikke multitasking, og havde som sådan ikke en planlægger. Windows 3.1x brugte en ikke-præventiv planlægger, hvilket betyder, at den ikke afbrød programmer. Det stolede på, at programmet skulle afslutte eller fortælle operativsystemet, at det ikke havde brug for processoren, så det kunne gå videre til en anden proces. Dette kaldes normalt kooperativ multitasking. Windows 95 introducerede en rudimentær præventiv planlægger; for ældre support valgte imidlertid at lade 16 bit applikationer køre uden forudbetaling.

Windows NT -baserede operativsystemer bruger en feedback -kø på flere niveauer. 32 prioritetsniveauer er defineret, 0 til og med 31, hvor prioriteter 0 til 15 er "normale" prioriteter og prioriteter 16 til 31 er bløde realtidsprioriteter, der kræver privilegier at tildele. 0 er forbeholdt operativsystemet. Brugergrænseflader og API'er arbejder med prioritetsklasser for processen og trådene i processen, som derefter kombineres af systemet til det absolutte prioritetsniveau.

Kernen kan ændre prioritetsniveauet for en tråd afhængigt af dens I/O- og CPU -brug, og om den er interaktiv (dvs. accepterer og reagerer på input fra mennesker), øger prioriteten for interaktive og I/O -afgrænsede processer og sænker den for CPU -bundne processer for at øge lydhørheden for interaktive applikationer. Planlæggeren blev ændret i Windows Vista til at bruge cyklustællerregisteret for moderne processorer til at holde styr på præcis, hvor mange CPU-cyklusser en tråd har udført, frem for bare at bruge en interval-timer afbrydelsesrutine. Vista bruger også en prioritetsplanlægger til I/O -køen, så diskdefragmentatorer og andre sådanne programmer ikke forstyrrer forgrundsoperationer.

Klassisk Mac OS og macOS

Mac OS 9 bruger kooperativ planlægning til tråde, hvor en proces styrer flere kooperative tråde og giver også præventiv planlægning til multiprocessingsopgaver. Kernen planlægger multiprocessering af opgaver ved hjælp af en præventiv planlægningsalgoritme. Alle Process Manager -processer køres inden for en særlig multiprocessingsopgave, kaldet den "blå opgave". Disse processer planlægges kooperativt ved hjælp af en round-robin-planlægningsalgoritme ; en proces giver kontrol over processoren til en anden proces ved eksplicit at kalde en blokeringsfunktion som f.eks WaitNextEvent. Hver proces har sin egen kopi af Thread Manager, der planlægger processens tråde i samarbejde; en tråd giver kontrol over processoren til en anden tråd ved at ringe til YieldToAnyThreadeller YieldToThread.

macOS bruger en feedback-kø på flere niveauer med fire prioritetsbånd til tråde-normal, systemhøj prioritet, kun kernetilstand og realtid. Tråde er planlagt præventivt; macOS understøtter også kooperativt planlagte tråde i implementeringen af ​​Thread Manager i Carbon .

AIX

I AIX Version 4 er der tre mulige værdier for trådplanlægningspolitik:

• Først ind, først ud: Når en tråd med denne politik er planlagt, kører den til afslutning, medmindre den er blokeret, den giver frivilligt kontrol over CPU'en, eller en tråd med højere prioritet kan sendes. Kun tråde med fast prioritet kan have en FIFO-planlægningspolitik.
• Round Robin: Dette ligner AIX Version 3 scheduler round-robin-skemaet baseret på 10 ms tidsskiver. Når en RR -tråd har kontrol i slutningen af ​​tidsskiven, bevæger den sig til halen af ​​køen af ​​afsendelige tråde med dens prioritet. Kun tråde med fast prioritet kan have en Round Robin-planlægningspolitik.
• ANDET: Denne politik er defineret af POSIX1003.4a som implementeringsdefineret. I AIX version 4 er denne politik defineret til at svare til RR, bortset fra at den gælder for tråde med ikke-fast prioritet. Genberegningen af ​​den løbende tråds prioritetsværdi ved hvert urafbrydelse betyder, at en tråd kan miste kontrollen, fordi dens prioritetsværdi er steget over værdien for en anden afsendelig tråd. Dette er AIX version 3 adfærd.

Tråde er primært af interesse for applikationer, der i øjeblikket består af flere asynkrone processer. Disse applikationer kan pålægge systemet en lettere belastning, hvis de konverteres til en flertrådet struktur.

AIX 5 implementerer følgende planlægningspolitikker: FIFO, round robin og en fair round robin. FIFO -politikken har tre forskellige implementeringer: FIFO, FIFO2 og FIFO3. Round robin -politikken hedder SCHED_RR i AIX, og fair round -robin kaldes SCHED_OTHER.

Linux

Linux 2.4

I Linux 2.4 blev der brugt en O (n) -planlægger med en feedback -kø på flere niveauer med prioritetsniveauer fra 0 til 140; 0–99 er reserveret til realtidsopgaver, og 100–140 betragtes som gode opgaveniveauer. For realtidsopgaver var tidskvantet for skifteprocesser cirka 200 ms, og for flotte opgaver cirka 10 ms. Planlæggeren løb gennem kørselskøen for alle færdige processer og lod processerne med den højeste prioritet gå først og køre gennem deres tidsskiver, hvorefter de blev placeret i en udløbet kø. Når den aktive kø er tom, bliver den udløbne kø den aktive kø og omvendt.

Nogle enterprise Linux-distributioner såsom SUSE Linux Enterprise Server erstattede imidlertid denne planlægger med en bagport af O (1) -planlæggeren (som blev vedligeholdt af Alan Cox i sin Linux 2.4-ac Kernel-serie) til Linux 2.4-kernen, der blev brugt af distributionen .

Linux 2.6.0 til Linux 2.6.22

I version 2.6.0 til 2.6.22 brugte kernen en O (1) planlægger udviklet af Ingo Molnar og mange andre kerneudviklere under Linux 2.5 -udviklingen. For mange kerner i tidsramme udviklede Con Kolivas patch -sæt, der forbedrede interaktiviteten med denne planlægger eller endda erstattede den med sine egne planlæggere.

Siden Linux 2.6.23

Con Kolivas 'arbejde, mest markant hans implementering af " fair scheduling " med navnet "Rotating Staircase Deadline", inspirerede Ingo Molnár til at udvikle den fuldstændig fair planlægger som en erstatning for den tidligere O (1) planlægger , hvilket krediterede Kolivas i sin meddelelse. CFS er den første implementering af en fair kø- procesplanlægger, der er meget udbredt i et generelt operativsystem.

The Completely Fair Scheduler (CFS) bruger en velstuderet, klassisk planlægningsalgoritme kaldet fair queuing, der oprindeligt blev opfundet til pakkenetværk . Fair kø var tidligere blevet anvendt til CPU -planlægning under navnet skridtplanlægning . CFS -planlæggeren med rimelig kø har en planlægningskompleksitet på , hvor er antallet af opgaver i runqueue . Valg af en opgave kan udføres på konstant tid, men genindsættelse af en opgave, efter at den er kørt, kræver operationer, fordi kørselskøen er implementeret som et rød -sort træ . ${\ displaystyle O (logN)}$${\ displaystyle N}$${\ displaystyle O (logN)}$

Den Brain fuck Scheduler , også skabt af Con Kolivas, er et alternativ til CFS.

FreeBSD

FreeBSD bruger en feedback -kø på flere niveauer med prioriteter fra 0–255. 0–63 er reserveret til afbrydelser, 64–127 til den øverste halvdel af kernen, 128–159 til brugertråde i realtid, 160–223 til tidsdelte brugertråde og 224–255 til inaktive brugertråde. Ligesom Linux bruger den også den aktive køopsætning, men den har også en inaktiv kø.

NetBSD

NetBSD bruger en feedback -kø på flere niveauer med prioriteter fra 0–223. 0-63 er reserveret til tid-delt gevind (standard, SCHED_OTHER politik), 64-95 for bruger tråde, der trådte kerne plads , 96-128 til kernel tråde, 128-191 for bruger realtid gevind (SCHED_FIFO og SCHED_RR politikker) og 192–223 for softwareafbrydelser .

Solaris

Solaris bruger en feedback-kø på flere niveauer med prioriteter på mellem 0 og 169. Prioriteter 0–59 er reserveret til tidsdelte tråde, 60–99 for systemtråde, 100–159 for realtidstråde og 160–169 for afbrydelser med lav prioritet . I modsætning til Linux, når en proces udføres ved hjælp af sin tidskvantum, får den en ny prioritet og sættes tilbage i køen. Solaris 9 introducerede to nye planlægningsklasser, nemlig fast prioritetsklasse og fair share -klasse. Trådene med fast prioritet har samme prioritetsinterval som tidsdelingsklassen, men deres prioriteter justeres ikke dynamisk. Klassen for fair planlægning bruger CPU -delinger til at prioritere tråde til planlægningsbeslutninger. CPU -aktier angiver retten til CPU -ressourcer. De er allokeret til et sæt processer, der samlet kaldes et projekt.

Resumé

Operativ system	Forudbetaling	Algoritme
Amiga OS	Ja	Prioriteret round-robin planlægning
FreeBSD	Ja	Feedback -kø på flere niveauer
Linux -kerne før 2.6.0	Ja	Feedback -kø på flere niveauer
Linux -kerne 2.6.0–2.6.23	Ja	O (1) planlægger
Linux -kerne efter 2.6.23	Ja	Helt fair planlægger
klassisk Mac OS pre-9	Ingen	Kooperativ planlægger
Mac OS 9	Nogle	Forebyggende planlægger til MP -opgaver og kooperativ til processer og tråde
macOS	Ja	Feedback -kø på flere niveauer
NetBSD	Ja	Feedback -kø på flere niveauer
Solaris	Ja	Feedback -kø på flere niveauer
Windows 3.1x	Ingen	Kooperativ planlægger
Windows 95 , 98 , Me	Halvt	Forebyggende planlægger til 32-bit processer og kooperativ til 16-bit processer
Windows NT (inklusive 2000, XP, Vista, 7 og Server)	Ja	Feedback -kø på flere niveauer

Se også

Noter

Referencer

Yderligere læsning

• Operativsystemer: Three Easy Pieces af Remzi H. Arpaci-Dusseau og Andrea C. Arpaci-Dusseau. Arpaci-Dusseau Books, 2014. Relevante kapitler: Planlægning: Introduktion Tilbagemeldingskø på flere niveauer Planlægning af proportionel andel Multiprocessor Planlægning
• Kort diskussion af algoritmer til jobplanlægning
• Forståelse af Linux -kernen: Kapitel 10 Procesplanlægning
• Kerneltrap: Linux kernel scheduler artikler
• AIX CPU -overvågning og tuning
• Josh Aas 'introduktion til Linux 2.6.8.1 CPU -planlæggerimplementering
• Peter Brucker, Sigrid Knust. Kompleksitetsresultater for planlægningsproblemer [3]
• TORSCHE Scheduling Toolbox til Matlab er en værktøjskasse med planlægnings- og grafalgoritmer.
• En undersøgelse om pakkeplanlægning af mobilnetværk
• Klyngestyring i stor skala hos Google med Borg