CPU-schemaläggning Algorithms in Operating Systems

Typer av CPU-schemaläggning

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

Förebyggande schemaläggning

I förebyggande schemaläggning tilldelas uppgifterna oftast med sina prioriteringar. Ibland är det viktigt att köra en uppgift med högre prioritet före en annan lägre prioriterad uppgift, även om den lägre prioriterade uppgiften fortfarande körs. Uppgiften med lägre prioritet håller i sig en tid och återupptas när den högre prioriterade uppgiften slutförs.

Icke-förebyggande schemaläggning

I denna typ av schemaläggningsmetod har CPU:n allokerats till en specifik process. Processen som håller processorn upptagen kommer att släppa processorn antingen genom att byta kontext eller avsluta. Det är den enda metoden som kan användas för olika hårdvaruplattformar. Det beror på att den inte behöver speciell hårdvara (till exempel en timer) som förebyggande schemaläggning.

När schemaläggning är förebyggande eller icke-förebyggande?

För att avgöra om schemaläggning är förebyggande eller icke-förebyggande, överväg dessa fyra parametrar:

1. En process växlar från pågående till vänteläge.
2. Specifik process växlar från driftläge till redoläge.
3. Specifik process växlar från vänteläge till redoläge.
4. Processen avslutade sin exekvering och avslutades.

Endast villkor 1 och 4 gäller, schemaläggningen kallas icke-förebyggande.

All annan schemaläggning är förebyggande.

Viktiga CPU-schemaläggningsterminologier

• Burst Time/Execution Time: Det är en tid som krävs av processen för att slutföra exekvering. Det kallas också löptid.
• Ankomst tid: när en process går in i ett klart tillstånd
• Sluttid: när processen är klar och avslutas från ett system
• Multiprogrammering: Ett antal program som kan finnas i minnet samtidigt.
• Jobb: Det är en typ av program utan någon form av användarinteraktion.
• Användare: Det är ett slags program som har användarinteraktion.
• Process: Det är referensen som används för både jobb och användare.
• CPU/IO-burstcykel: Karakteriserar processexekvering, som växlar mellan CPU- och I/O-aktivitet. CPU-tider är vanligtvis kortare än tiden för I/O.

CPU-schemaläggningskriterier

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

Maximera

CPU-användning:CPU-användning är den huvudsakliga uppgiften där operativsystemet måste se till att CPU förblir så upptagen som möjligt. Det kan variera från 0 till 100 procent. Men för RTOS kan det variera från 40 procent för lågnivå och 90 procent för högnivåsystem.

genomströmning: Antalet processer som avslutar sin exekvering per tidsenhet är känd genomströmning. Så när processorn är upptagen med att köra processen, vid den tidpunkten, utförs arbetet, och arbetet som slutförts per tidsenhet kallas för genomströmning.

Minimera

Väntetid: Väntetid är ett belopp som specifik process behöver vänta i klarkön.

Respons tid: Det är en tidsperiod under vilken begäran lämnades in tills det första svaret tas fram.

Vändtid: Handläggningstid är en tid för att utföra en specifik process. Det är beräkningen av den totala tiden som spenderas på att vänta på att komma in i minnet, vänta i kön och köra på CPU:n. Perioden mellan tidpunkten för inlämning av processen till färdigställandetiden ä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 av det multiprogrammerade operativsystemet använder någon form av en timer för att förhindra en process från att binda upp systemet för alltid.

Vad är Dispatcher?

Det är en modul som ger kontroll över processorn till processen. Dispatchern ska vara snabb så att den kan köras på alla sammanhangsväxlar. Utskickslatens är den tid som krävs av CPU-schemaläggaren för att stoppa en process och starta en annan.

Funktioner som utförs av Dispatcher:

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

Typer av CPU-schemaläggningsalgoritm

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

Först till kvarn

Först till kvarn gäller är den fullständiga formen av FCFS. Det är den enklaste och enklaste CPU-schemaläggningsalgoritmen. I denna typ av algoritm får processen som begär CPU:n CPU-allokeringen först. Denna schemaläggningsmetod kan hanteras med en FIFO-kö.

När processen går in i den färdiga kön, länkas dess PCB (Process Control Block) med köns bakre del. Så när CPU blir ledig bör den tilldelas processen i början av kön.

Egenskaper för FCFS-metoden

• Den erbjuder en icke-förebyggande och 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 Kortaste återstående tid. Det är också känt som SJF förebyggande schemaläggning. I den här metoden kommer processen att allokeras till uppgiften, som ligger närmast dess slutförande. Den här metoden förhindrar en nyare redo-tillståndsprocess från att hålla slutförandet av en äldre process.

Egenskaper för SRT-schemaläggningsmetoden

• Denna metod tillämpas mestadels i batchmiljöer där korta jobb krävs för att prioriteras.
• Detta är inte en idealisk metod för att implementera det i ett delat system där den nödvändiga CPU-tiden är okänd.
• Associera med varje process som längden på nästa CPU-skur. Så det operativsystemet använder dessa längder, vilket hjälper till 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 som ska fungera enligt prioritet.

Prioritetsschemaläggning hjälper också OS att involvera prioriterade uppdrag. Processerna med högre prioritet bör utföras först, medan jobb med lika prioritet utförs på rundgång eller FCFS-basis. Prioritet kan bestämmas utifrån minneskrav, tidskrav etc.

Round-Robin Schemaläggning

Round robin är den äldsta, enklaste schemaläggningsalgoritmen. Namnet på denna algoritm kommer från round-robin-principen, där varje person får en lika stor del av något i sin tur. Det används mest för att schemalägga algoritmer i multitasking. Denna algoritmmetod hjälper till att köra processer utan svält.

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

• Round robin är en hybridmodell som är klockdriven
• Tidsintervallet bör vara minimum, vilket tilldelas för en specifik uppgift som ska bearbetas. Det kan dock variera för olika processer.
• Det är ett realtidssystem som svarar på händelsen inom en viss tidsgräns.

Kortaste jobbet först

SJF är en fullständig form av (Kortaste jobbet först) är en schemaläggningsalgoritm där processen med den kortaste exekveringstiden ska väljas för exekvering härnäst. Denna schemaläggningsmetod kan vara förebyggande eller icke-förebyggande. Det minskar avsevärt den genomsnittliga väntetiden för andra processer som väntar på exekvering.

Egenskaper för SJF Schemaläggning

• Det är kopplat till varje jobb som en tidsenhet att slutföra.
• I den här metoden, när processorn är tillgänglig, kommer nästa process eller jobb med den kortaste slutförandetiden att utföras först.
• Den genomförs med icke-förebyggande policy.
• Denna algoritmmetod är användbar för bearbetning av batchtyp, där det inte är avgörande att vänta på att jobb ska slutföras.
• Det förbättrar arbetsresultatet genom att erbjuda kortare jobb, som bör utföras först, som oftast har en kortare handläggningstid.

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

Denna algoritm separerar den färdiga kön i olika separata köer. I denna metod tilldelas processer till en kö baserat på en specifik egenskap hos processen, som processprioritet, minnesstorlek, etc.

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

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

• Flera köer bör upprätthållas för processer med vissa egenskaper.
• Varje kö kan ha sina separata schemaläggningsalgoritmer.
• Prioriteringar ges för 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.
• Maximalt utnyttjande av CPU kan erhållas med multiprogrammering.
• Processerna som ska exekveras står i klarkö.

Sammanfattning

• CPU-schemaläggning är en process för att bestämma vilken process som kommer att äga CPU för exekvering medan en annan process är pausad.
• I förebyggande schemaläggning tilldelas uppgifterna oftast med sina prioriteringar.
• I den icke-förebyggande schemaläggningsmetoden har CPU:n allokerats till en specifik process.
• Bursttiden är den tid som krävs för att processen ska slutföra exekvering. Det kallas också löptid.
• CPU-användning är den huvudsakliga uppgiften där operativsystemet behöver för att säkerställa att CPU:n förblir så upptagen som möjligt.
• Antalet processer som avslutar sin exekvering per tidsenhet är känd genomströmning.
• Väntetid är en summa som en specifik process behöver vänta i klarkön.
• Det är den tid under vilken begäran skickades in tills det första svaret produceras.
• Handläggningstid är hur lång tid det tar att utföra en specifik process.
• Timeravbrott är en metod som är nära relaterad till preemption.
• En dispatcher är en modul som ger kontroll över processorn till processen.
• Sex typer av processschemaläggningsalgoritmer är: Först till kvarn (FCFS), 2) Kortaste jobb-först (SJF) Schemaläggning, 3) Kortaste återstående tid, 4) Prioritetsschemaläggning, 5) Round Robin-schemaläggning, 6) Schemaläggning för flera nivåer. .
• I Först till kvarn-metoden, processen som begär CPU:n får CPU-allokeringen först.
• På den kortaste återstående tiden kommer processen att tilldelas den uppgift som ligger närmast dess slutförande.
• I Prioritetsschemaläggning väljer schemaläggaren de uppgifter som ska fungera enligt prioritet.
• Round robin schemaläggning arbetar efter principen att varje person får lika stor del av något i sin tur.
• I det kortaste jobbet först, bör den kortaste körningstiden väljas för körning nästa.
• Schemaläggningsmetoden med flera nivåer separerar den färdiga kön i olika separata köer. I den här metoden tilldelas processer till en kö baserat på en specifik egenskap.
• CPU:n använder schemaläggning för att förbättra sin effektivitet.