Algoritm för prioriteringsplanering: Förebyggande, icke-förebyggande EXEMPEL

Typer av prioriteringsplanering

Prioritetsschemaläggning uppdelad 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 denna typ av schemaläggningsmetod har CPU:n allokerats till en specifik process. Processen som håller CPU:n upptagen kommer att släppa CPU:n 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.

Egenskaper för prioriteringsplanering

• En CPU-algoritm som schemalägger processer baserat på prioritet.
• Den användes 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å.
• Lägre siffran, högre är prioritet.
• I den här typen av schemaläggningsalgoritm, om en nyare process anländer, som har högre prioritet än den för närvarande pågående processen, är den för närvarande pågående processen förebyggd.

Exempel på prioriteringsplanering

Överväg att följa fem processer P1 till P5. Varje process har sin unika prioritet, sprängtid 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 tid=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 tidpunkt=1 kommer ingen ny process. Utförandet 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 kommer ingen ny process så du kan fortsätta med P1. P2-processen fortfarande i kö.

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

Steg 5) Klockan = 5 kommer ingen ny process, så vi fortsätter med P2.

Steg 6) Klockan=6 kommer P3. P3 har högre prioritet (1) jämfört med att P2 har prioritet (2). P2 är förebyggd, och P3 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) Kl tid 7 kommer ingen ny process, så vi fortsätter med P3. P2 står i väntekö.

Steg 8) Klockan = 8 kommer ingen ny process, så vi kan fortsätta med P3.

Steg 9) Klockan = 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) Klockan=12 kommer P5. P3 har högre prioritet, så det fortsätter att köras.

Steg 13) Vid tidpunkten=13 slutför P3 exekveringen. Vi har P2,P4,P5 i redo kö. P2 och P5 har samma prioritet. Ankomsttiden för P2 är före P5. Så P2 börjar köras.

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 exekvering.

Steg 15) Vid tiden =15 fortsätter P5 exekveringen.

Steg 16) Vid tid = 16 är P5 avslutad med sin exekvering. P4 är den enda processen kvar. Det börjar köras.

Steg 17) Vid tiden =20 har P5 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 = o - o = o
P2 =4 - o + 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ördelar/fördelar med att använda prioritetsschemaläggningsmetoden:

• Enkel att använda schemaläggningsmetod
• Processer exekveras utifrån prioritet så hög prioritet behöver inte vänta länge vilket sparar tid
• Denna metod ger 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 nackdelar/nackdelar med prioriteringsschemalä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.

Sammanfattning

• Prioritetsschemaläggning är en metod för schemaläggning av processer som är baserad på prioritet. I den här algoritmen väljer schemaläggaren de uppgifter som ska fungera enligt prioritet.
• I Priority Preemptive Scheduling tilldelas uppgifterna oftast med sina prioriteringar.
• I Priority Non-preemptive scheduling-metoden har CPU:n allokerats till en specifik process.
• Processer exekveras utifrån prioritet så hög prioritet behöver inte vänta länge vilket sparar tid
• 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.