Prioriterad schemaläggningsalgoritm: Preemptiv, icke-preemptiv

Vad är prioriteringsplanering?

Prioritetsschemaläggning är en metod för att schemalägga processer som är baserad på prioritet. I den här algoritmen väljer schemaläggaren de uppgifter som ska fungera enligt prioritet.

Processerna med högre prioritet bör utföras först, medan jobb med lika prioritet utförs på rundgångs- eller FCFS-basis. Prioriteten beror på minneskrav, tidskrav etc.

Typer av prioriteringsplanering

Prioriterad schemaläggning är indelad i två huvudtyper:

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 den här typen av schemaläggningsmetod har processorn allokerats till en specifik process. Processen som håller processorn upptagen frigör 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 vid preemptiv schemaläggning.

Egenskaper för prioriteringsplanering

• En CPU-algoritm som schemalägger processer baserat på prioritet.
• Det används i Operasystem för att utföra batchprocesser.
• Om två jobb med samma prioritet är REDO fungerar det på en FÖRST TILL KVARN basis.
• I prioriteringsschemaläggning tilldelas ett nummer till varje process som anger dess prioritetsnivå.
• Ju lägre siffra, desto högre prioritet.
• I den här typen av schemaläggningsalgoritm, om en nyare process anländer som har högre prioritet än den process som för närvarande körs, så föregrips den process som för närvarande körs.

Exempel på prioriteringsplanering

Betrakta följande fem processer P1 till P5. Varje process har sin unika prioritet, bursttid och ankomsttid.

Behandla	Budget	Sprängtid	Ankomst tid
P1	1	4	0
P2	2	3	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

Steg 0) Vid tidpunkten 0 anländer process P1 och P2. P1 har högre prioritet än P2. Exekveringen börjar med process P1, som har bursttid 4.

Steg 1) Vid tidpunkten 1 anländer ingen ny process. Exekveringen fortsätter med P1.

Steg 2) Vid tidpunkt 2 kommer ingen ny process, så du kan fortsätta med P1. P2 står i väntekö.

Steg 3) Vid tidpunkt 3 anländer ingen ny process, så du kan fortsätta med P1. P2-processen står fortfarande i väntekön.

Steg 4) Vid tidpunkt 4 har P1 avslutat sin exekvering. P2 börjar köras.

Steg 5) Vid tidpunkt = 5 anländer ingen ny process, så vi fortsätter med P2.

Steg 6) Vid tidpunkten 6 anländer P3. P3 har högre prioritet (1) jämfört med P2 som har prioritet (2). P2 förbehålls och P3 påbörjar sin exekvering.

Behandla	Budget	Sprängtid	Ankomst tid
P1	1	4	0
P2	2	1 av 3 väntande	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

Steg 7) Vid tidpunkt 7 anländer ingen ny process, så vi fortsätter med P3. P2 står i väntekön.

Steg 8) Vid tidpunkten = 8 anländer ingen ny process, så vi kan fortsätta med P3.

Steg 9) Vid tidpunkten = 9 kommer ingen ny process, så vi kan fortsätta med P3.

Steg 10) Vid tidsintervall 10 kommer ingen ny process, så vi fortsätter med P3.

Steg 11) Vid tidpunkten 11 anländer P4 med prioritet 4. P3 har högre prioritet, så den fortsätter sin exekvering.

Behandla	Budget	Sprängtid	Ankomst tid
P1	1	4	0
P2	2	1 av 3 väntande	0
P3	1	2 av 7 väntande	6
P4	3	4	11
P5	2	2	12

Steg 12) Vid tidpunkten 12 anländer P5. P3 har högre prioritet, så den fortsätter körningen.

Steg 13) Vid tidpunkten 13 slutför P3 exekveringen. Vi har P2, P4 och P5 i redokön. P2 och P5 har samma prioritet. P2:s ankomsttid är före P5, så P2 börjar exekveringen.

Behandla	Budget	Sprängtid	Ankomst tid
P1	1	4	0
P2	2	1 av 3 väntande	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

Steg 14) Vid tidpunkten 14 har P2-processen avslutat sin exekvering. P4 och P5 är i vänteläge. P5 har högsta prioritet och startar exekveringen.

Steg 15) Vid tidpunkten 15 fortsätter P5 körningen.

Steg 16) Vid tidpunkten 16 är P5 klar med sin exekvering. P4 är den enda processen som återstår. Den startar exekveringen.

Steg 17) Vid tidpunkten 20 har P4 slutfört exekveringen och ingen process finns kvar.

Steg 18) Låt oss beräkna den genomsnittliga väntetiden för exemplet ovan.

Väntetid = starttid – ankomsttid + väntetid för nästa skur

P1 = 0 - 0 = 0
P2 = 4 - 0 + 7 = 11
P3 = 6 - 6 = 0
P4 = 16 - 11 = 5
Average Waiting time = (0 + 11 + 0 + 5 + 2)/5 = 18/5 = 3.6

Fördelar med prioriterad schemaläggning

Här är fördelarna/fördelarna med att använda prioriterad schemaläggningsmetod:

• Lättanvänd schemaläggningsmetod.
• Processer exekveras baserat på prioritet, så hög prioritet behöver inte vänta länge, vilket sparar tid.
• Denna metod erbjuder en bra mekanism där den relativa betydelsen av varje process kan definieras exakt.
• Lämplig för applikationer med varierande tids- och resurskrav.

Nackdelar med prioriteringsschemaläggning

Här är nackdelarna/nackdelarna med prioriterad schemaläggning:

• Om systemet så småningom kraschar går alla lågprioriterade processer förlorade.
• Om högprioriterade processer tar mycket CPU-tid, kan de lägre prioriterade processerna svälta och kommer att skjutas upp på obestämd tid.
• Denna schemaläggningsalgoritm kan låta vissa lågprioriterade processer vänta på obestämd tid.
• En process kommer att blockeras när den är redo att köras men måste vänta på CPU:n eftersom någon annan process körs just nu.
• Om en ny process med högre prioritet fortsätter att komma i klarkön, kan processen som är i vänteläge behöva vänta under en lång tid.

Vanliga frågor