Prioritetsplanleggingsalgoritme: Preemptiv, ikke-preemptiv

Hva er prioritert planlegging?

Prioritetsplanlegging er en metode for å planlegge prosesser som er basert på prioritering. I denne algoritmen velger planleggeren oppgavene som skal fungere i henhold til prioritet.

Prosessene med høyere prioritet bør utføres først, mens jobber med lik prioritering utføres på rundkjørings- eller FCFS-basis. Prioritet avhenger av minnekrav, tidskrav osv.

Typer prioritert planlegging

Prioritert planlegging er delt inn i to hovedtyper:

Forebyggende planlegging

I Preemptive Scheduling er oppgavene stort sett tildelt deres prioriteringer. Noen ganger er det viktig å kjøre en oppgave med høyere prioritet før en annen lavere prioritet oppgave, selv om den lavere prioriterte oppgaven fortsatt kjører. Den lavere prioriterte oppgaven varer i en stund og fortsetter når den høyere prioriterte oppgaven er ferdig.

Ikke-forebyggende planlegging

I denne typen planleggingsmetode er CPU-en allokert til en spesifikk prosess. Prosessen som holder CPU-en opptatt, frigjør CPU-en enten ved å bytte kontekst eller avslutte. Det er den eneste metoden som kan brukes for ulike maskinvareplattformer. Det er fordi den ikke trenger spesiell maskinvare (for eksempel en timer) slik som preemptiv planlegging.

Kjennetegn ved prioriteringsplanlegging

• En CPU-algoritme som planlegger prosesser basert på prioritet.
• Det er brukt i Operasystemer for å utføre batch-prosesser.
• Hvis to jobber med samme prioritet er KLAR, fungerer det på en FØRSTEMANN TIL MØLLA basis.
• Ved prioriteringsplanlegging tildeles et nummer til hver prosess som angir prioritetsnivået.
• Jo lavere tallet er, desto høyere er prioriteten.
• I denne typen planleggingsalgoritme, hvis en nyere prosess ankommer som har høyere prioritet enn den prosessen som kjører for øyeblikket, blir den prosessen som kjører foregrepet.

Eksempel på prioritert planlegging

Tenk på de følgende fem prosessene P1 til P5. Hver prosess har sin unike prioritet, burst-tid og ankomsttid.

Prosess	Prioritet	Sprengtid	Ankomsttid
P1	1	4	0
P2	2	3	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

Trinn 0) Ved tid = 0 ankommer prosess P1 og P2. P1 har høyere prioritet enn P2. Utførelsen begynner med prosess P1, som har burst-tid 4.

Trinn 1) Ved tid = 1, ankommer ingen ny prosess. Utførelsen fortsetter med P1.

Trinn 2) Ved tidspunkt 2 kommer ingen ny prosess, så du kan fortsette med P1. P2 står i ventekø.

Trinn 3) Ved tidspunkt 3 ankommer ingen ny prosess, så du kan fortsette med P1. P2-prosessen står fortsatt i ventekøen.

Trinn 4) På tid 4 har P1 avsluttet sin utførelse. P2 starter utførelse.

Trinn 5) Ved tid = 5 ankommer ingen ny prosess, så vi fortsetter med P2.

Trinn 6) Ved tid = 6 ankommer P3. P3 har høyere prioritet (1) sammenlignet med P2 som har prioritet (2). P2 blir foregrepet, og P3 begynner sin utførelse.

Prosess	Prioritet	Sprengtid	Ankomsttid
P1	1	4	0
P2	2	1 av 3 venter	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

Trinn 7) Ved tidspunkt 7 ankommer ingen ny prosess, så vi fortsetter med P3. P2 står i ventekøen.

Trinn 8) Ved tid = 8 ankommer ingen ny prosess, så vi kan fortsette med P3.

Trinn 9) Ved tid = 9 kommer ingen ny prosess, så vi kan fortsette med P3.

Trinn 10) Ved tidsintervall 10 kommer ingen ny prosess, så vi fortsetter med P3.

Trinn 11) Ved tid = 11 ankommer P4 med prioritet 4. P3 har høyere prioritet, så den fortsetter utførelsen.

Prosess	Prioritet	Sprengtid	Ankomsttid
P1	1	4	0
P2	2	1 av 3 venter	0
P3	1	2 av 7 venter	6
P4	3	4	11
P5	2	2	12

Trinn 12) Ved tid = 12 ankommer P5. P3 har høyere prioritet, så den fortsetter utførelsen.

Trinn 13) Ved tid = 13 fullfører P3 utførelsen. Vi har P2, P4 og P5 i klarkøen. P2 og P5 har lik prioritet. Ankomsttiden til P2 er før P5, så P2 starter utførelsen.

Prosess	Prioritet	Sprengtid	Ankomsttid
P1	1	4	0
P2	2	1 av 3 venter	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

Trinn 14) Ved tid = 14 er P2-prosessen ferdig med utførelse. P4 og P5 er i ventetilstand. P5 har høyest prioritet og starter utførelse.

Trinn 15) Ved tid = 15 fortsetter P5 utførelsen.

Trinn 16) Ved tid = 16 er P5 ferdig med utførelse. P4 er den eneste prosessen som er igjen. Den starter utførelse.

Trinn 17) Ved tidspunktet = 20 har P4 fullført utførelsen, og ingen prosess er igjen.

Trinn 18) La oss beregne den gjennomsnittlige ventetiden for eksemplet ovenfor.

Ventetid = starttidspunkt – ankomsttid + ventetid for neste utbrudd

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

Fordeler med prioritert planlegging

Her er fordelene/profesjonene ved å bruke prioritert planleggingsmetoden:

• Enkel å bruke planleggingsmetode.
• Prosesser utføres på grunnlag av prioritet, slik at høy prioritet ikke trenger å vente lenge, noe som sparer tid.
• Denne metoden gir en god mekanisme der den relative betydningen av hver prosess kan defineres presist.
• Egnet for applikasjoner med varierende tids- og ressursbehov.

Ulemper med prioritert planlegging

Her er ulempene/ulempene med prioritert planlegging:

• Hvis systemet til slutt krasjer, går alle lavprioriterte prosesser tapt.
• Hvis prosesser med høy prioritet tar mye CPU-tid, kan de lavere prioriterte prosessene sulte og vil bli utsatt på ubestemt tid.
• Denne planleggingsalgoritmen kan la noen lavprioriterte prosesser vente på ubestemt tid.
• En prosess vil bli blokkert når den er klar til å kjøre, men må vente på CPU fordi en annen prosess kjører for øyeblikket.
• Hvis en ny prosess med høyere prioritet fortsetter å komme i klarkøen, kan det hende at prosessen som er i ventetilstand må vente i lang tid.

Spørsmål og svar