CPU-schemaläggning Algorithms in Operating Systems

Vad är CPU-schemaläggning?

CPU-schemaläggning är en process för att avgöra vilken process som ska äga processorn för körning medan en annan process är pausad. Huvuduppgiften för CPU-schemaläggning är att se till att närhelst processorn förblir inaktiv, väljer operativsystemet minst en av de processer som är tillgängliga i redokön för körning. Urvalsprocessen utförs av CPU-schemaläggaren, som väljer en av processerna i minnet som är redo för körning.

Typer av CPU-schemaläggning

Här finns två typer av schemaläggningsmetoder:

Förebyggande schemaläggning

Vid preemptiv schemaläggning tilldelas uppgifterna oftast med sina prioriteter. Ibland är det viktigt att köra en uppgift med högre prioritet före en annan uppgift med lägre prioritet, även om uppgiften med lägre prioritet fortfarande körs. Uppgiften med lägre prioritet väntar ett tag och återupptas när uppgiften med högre prioritet har avslutat sin körning.

Icke-förebyggande schemaläggning

I den här typen av schemaläggningsmetod allokeras processorn till en specifik process. Processen som håller processorn sysselsatt frigör processorn antingen genom att byta kontext eller avsluta. Det är den enda metoden som kan användas över olika hårdvaruplattformar, eftersom den inte behöver speciell hårdvara (till exempel en timer) som preemptiv schemaläggning.

När är schemaläggning preemptiv eller icke-preemptiv?

För att avgöra om schemaläggning är preemptiv eller icke-preemptiv, beakta dessa fyra parametrar:

1. En process växlar från pågående till vänteläge.
2. En specifik process växlar från körtillstånd till klartillstånd.
3. En specifik process växlar från vänteläge till klartillstånd.
4. En process avslutar sin exekvering och avslutas.

Om endast villkor 1 och 4 gäller kallas schemaläggningen icke-preemptiv. Alla andra schemaläggningssituationer är preemptiva.

Viktiga termer för CPU-schemaläggning

• Burst Time/Execution Time: Den tid som krävs för en process att slutföra exekveringen. Detta kallas även körtid.
• Ankomst tid: Den tidpunkt då en process går in i klartillstånd.
• Sluttid: Den tidpunkt då en process slutförs och lämnar systemet.
• Multiprogrammering: Ett antal program som kan finnas i minnet samtidigt.
• Jobb: En typ av program utan någon form av användarinteraktion.
• Användare: En typ av program som har användarinteraktion.
• Process: Referensen som används för både ett jobb och en användare.
• CPU/IO-burstcykel: Karaktäriserar processkörning, som växlar mellan CPU- och I/O-aktivitet. CPU-tider är vanligtvis kortare än I/O-tider.

CPU-schemaläggningskriterier

En CPU-schemaläggningsalgoritm försöker maximera och minimera följande:

Maximera

CPU-användning: CPU-utnyttjandegraden är den huvudsakliga uppgiften där operativsystemet behöver se till att processorn förblir så upptagen som möjligt. Den kan variera från 0 till 100 procent. För en RTOS kan den dock variera från 40 procent för ett lågnivåsystem till 90 procent för ett högnivåsystem.

genomströmning: Antalet processer som slutför sin exekvering per tidsenhet kallas genomströmning. Så när processorn är upptagen med att exekvera en process utförs arbete, och det arbete som slutförs per tidsenhet kallas genomströmning.

Minimera

Väntetid: Väntetiden är den tid en specifik process måste vänta i klarkön.

Respons tid: Det är den tid som går från det att förfrågan skickades in tills det första svaret produceras.

Vändtid: Handläggningstiden är den tid det tar att köra en specifik process. Det är den totala tiden det tar att vänta på att komma in i minnet, vänta i kön och köra på processorn. Perioden mellan tidpunkten för processens inlämning och slutförandetid är handläggningstiden.

Intervalltimer

Timeravbrott är en metod som är nära relaterad till preemption. När en viss process får CPU-allokeringen kan en timer ställas in på ett specificerat intervall. Både timeravbrott och preemption tvingar en process att returnera CPU:n innan dess CPU-skur är klar.

De flesta flerprogrammerade operativsystem använder någon form av timer för att förhindra att en process binder upp systemet för alltid.

Vad är Dispatcher?

Dispatchern är en modul som ger kontroll över processens processor. Dispatchern bör vara snabb så att den kan köras på varje kontextväxel. Dispatch-latens är den tid som behövs för CPU-schemaläggaren för att stoppa en process och starta en annan.

Funktioner som utförs av trafikledaren:

• Kontextväxling.
• Växlar till användarläge.
• Flytta till rätt plats i det nyligen laddade programmet.

Typer av CPU-schemaläggning Algorithms

Det finns huvudsakligen sex typer av processschemaläggningsalgoritmer:

1. Först till kvarn gäller (FCFS)
2. Shortest-Job-First (SJF) Schemaläggning
3. Kortaste återstående tid
4. Prioritetsschemaläggning
5. Runda Robin Schemaläggning
6. Schemaläggning av köer på flera nivåer

Schemaläggning Algorithms

Först till kvarn

FCFS står för Först till kvarnDet är den enklaste och enklaste CPU-schemaläggningsalgoritmen. I den här typen av algoritm får den process som begär CPU:n CPU-allokeringen först. Denna schemaläggningsmetod kan hanteras med en FIFO-kö.

När en process går in i redo-kön länkas dess PCB (processkontrollblock) till köns slut. Så när processorn blir ledig bör den tilldelas processen i början av kön.

Egenskaper hos FCFS-metoden

• Det är en icke-förebyggande schemaläggningsalgoritm.
• Jobb utförs alltid enligt först till kvarn-principen.
• Det är lätt att implementera och använda.
• Denna metod har dock dålig prestanda och den allmänna väntetiden är ganska lång.

Kortaste återstående tid

Den fullständiga formen av SRT är Shortest Remaining Time. Det är även känt som SJF preemptive scheduling. Med den här metoden allokeras processen till den uppgift som är närmast slutförd. Denna metod förhindrar att en nyare färdigprocess försenar slutförandet av en äldre process.

Egenskaper hos SRT-schemaläggningsmetoden

• Denna metod tillämpas oftast i batchmiljöer där korta jobb behöver prioriteras.
• Detta är inte en idealisk metod att implementera i ett delat system där den erforderliga CPU-tiden är okänd.
• Varje process är associerad med längden på sin nästa CPU-burst, så operativsystemet använder dessa längder för att schemalägga processen med kortast möjliga tid.

Prioritetsbaserad schemaläggning

Prioritetsschemaläggning är en metod för att schemalägga processer baserat på prioritet. I den här metoden väljer schemaläggaren de uppgifter att arbeta med enligt deras prioritet.

Prioritetsschemaläggning hjälper också operativsystemet att involvera prioritetstilldelningar. Processer med högre prioritet utförs först, medan jobb med samma prioritet utförs på en round-robin- eller FCFS-basis. Prioritet kan bestämmas baserat på minneskrav, tidskrav och andra faktorer.

Round-Robin Schemaläggning

Round robin är en av de äldsta och enklaste schemaläggningsalgoritmerna. Namnet på denna algoritm kommer från round-robin-principen, där varje person får en lika stor andel av något i tur och ordning. Den används mestadels för schemaläggning i multitasking-system. Denna metod hjälper till att uppnå svältfri exekvering av processer.

Kännetecken för Round-Robin-schemaläggning

• Round robin är en hybridmodell som är klockdriven.
• Tidsintervallet som tilldelas för en specifik uppgift att bearbetas bör vara minimalt. Det kan dock variera för olika processer.
• Det fungerar som ett tidsdelningssystem som svarar på varje process inom en specifik tidsgräns.

Kortaste jobbet först

SJF (Shortest Job First) är en schemaläggningsalgoritm där processen med kortast exekveringstid väljs för nästa exekvering. Denna schemaläggningsmetod kan vara preemptiv eller icke-preemptiv. Den minskar avsevärt den genomsnittliga väntetiden för andra processer som väntar på exekvering.

Egenskaper för SJF Schemaläggning

• Varje jobb är kopplat till en tidsenhet att slutföra.
• I den här metoden, när processorn är tillgänglig, körs nästa process eller jobb med kortast slutförandetid först.
• Det implementeras med en icke-förebyggande policy.
• Den här algoritmen är användbar för batchbearbetning, där det inte är avgörande att vänta på att jobb ska slutföras.
• Det förbättrar jobbresultatet genom att först utföra kortare jobb, vilka oftast har en kortare handläggningstid.

Schemaläggning av köer på flera nivåer

Denna algoritm delar upp den färdiga kön i flera separata köer. I den här metoden tilldelas processer till en kö baserat på en specifik egenskap hos processen, såsom processprioritet, minnesstorlek och så vidare.

Detta är dock inte en oberoende schemaläggningsalgoritm, eftersom den behöver använda andra typer av algoritmer för att schemalägga jobben.

Egenskaper för schemaläggning av köer på flera nivåer

• Flera köer bör underhållas för processer med delade egenskaper.
• Varje kö kan ha sin egen separata schemaläggningsalgoritm.
• Prioriteter tilldelas varje kö.

Syftet med en schemaläggningsalgoritm

Här är anledningarna till att använda en schemaläggningsalgoritm:

• CPU:n använder schemaläggning för att förbättra sin effektivitet.
• Det hjälper dig att fördela resurser mellan konkurrerande processer.
• Maximal utnyttjande av CPU:n kan uppnås med multiprogrammering.
• De processer som ska köras hålls i redo-kön.

Vanliga frågor