Algoritme voor prioriteitsplanning: preventief, niet-preventief VOORBEELD
Nathaniel Brooks
Wat is prioriteitsplanning?
Prioriteitsplanning is een methode voor het plannen van processen die is gebaseerd op prioriteit. In dit algoritme selecteert de planner de taken die volgens de prioriteit moeten worden uitgevoerd.
De processen met een hogere prioriteit moeten eerst worden uitgevoerd, terwijl taken met gelijke prioriteiten worden uitgevoerd op basis van round-robin of FCFS. Prioriteit hangt af van geheugenvereisten, tijdvereisten, enz.
Soorten prioriteitsplanning
Prioriteitsplanning onderverdeeld in twee hoofdtypen:
Preventieve planning
Bij Preemptive Scheduling worden de taken meestal toegewezen met hun prioriteiten. Soms is het belangrijk om een taak met een hogere prioriteit uit te voeren vóór een andere taak met een lagere prioriteit, zelfs als de taak met een lagere prioriteit nog steeds actief is. De taak met lagere prioriteit blijft enige tijd bestaan en wordt hervat wanneer de taak met hogere prioriteit is uitgevoerd.
Niet-preventieve planning
Bij dit type planningsmethode is de CPU toegewezen aan een specifiek proces. Het proces dat de CPU bezig houdt, zal de CPU vrijgeven door van context te wisselen of te beëindigen. Het is de enige methode die voor verschillende hardwareplatforms kan worden gebruikt. Dat komt omdat er geen speciale hardware voor nodig is (bijvoorbeeld een timer), zoals preventieve planning.
Kenmerken van prioriteitsplanning
- Een CPU-algoritme dat processen plant op basis van prioriteit.
- Het werd gebruikt Operasystemen voor het uitvoeren van batchprocessen.
- Als twee taken met dezelfde prioriteit KLAAR zijn, werkt het op a WIE HET EERST KOMT HET EERST MAALT basis.
- Bij prioriteitsplanning wordt aan elk proces een nummer toegewezen dat het prioriteitsniveau ervan aangeeft.
- Lager het getal, hoger is de prioriteit.
- Als er bij dit type planningsalgoritme een nieuwer proces binnenkomt, dat een hogere prioriteit heeft dan het momenteel lopende proces, wordt het momenteel lopende proces voorrang gegeven.
Voorbeeld van prioriteitsplanning
Overweeg de volgende vijf processen P1 tot P5. Elk proces heeft zijn eigen prioriteit, bursttijd en aankomsttijd.
| Proces | Prioriteit | Burst-tijd | Aankomsttijd |
|---|---|---|---|
| P1 | 1 | 4 | 0 |
| P2 | 2 | 3 | 0 |
| P3 | 1 | 7 | 6 |
| P4 | 3 | 4 | 11 |
| P5 | 2 | 2 | 12 |
Stap 0) Op tijdstip=0 arriveren proces P1 en P2. P1 heeft een hogere prioriteit dan P2. De uitvoering begint met proces P1, dat burst-tijd 4 heeft.
Stap 1) Op tijdstip=1 arriveert er geen nieuw proces. De uitvoering gaat verder met P1.
Stap 2) Op tijdstip 2 komt er geen nieuw proces binnen, dus u kunt doorgaan met P1. P2 staat in de wachtrij.
Stap 3) Op tijdstip 3 komt er geen nieuw proces binnen, dus u kunt doorgaan met P1. P2-proces staat nog steeds in de wachtrij.
Stap 4) Op tijdstip 4 is P1 klaar met de uitvoering. P2 start de uitvoering.
Stap 5) Op tijdstip= 5 arriveert er geen nieuw proces, dus gaan we verder met P2.
Stap 6) Op tijdstip=6 arriveert P3. P3 heeft een hogere prioriteit (1) vergeleken met P2 met prioriteit (2). Er wordt beslag gelegd op P2 en P3 begint met de uitvoering ervan.
| Proces | Prioriteit | Burst-tijd | Aankomsttijd |
|---|---|---|---|
| P1 | 1 | 4 | 0 |
| P2 | 2 | 1 op 3 in behandeling | 0 |
| P3 | 1 | 7 | 6 |
| P4 | 3 | 4 | 11 |
| P5 | 2 | 2 | 12 |
Stap 7) Op tijd 7 komt er geen nieuw proces aan, dus gaan we verder met P3. P2 staat in de wachtrij.
Stap 8) Op tijdstip = 8 arriveert er geen nieuw proces, dus we kunnen doorgaan met P3.
Stap 9) Op tijdstip = 9 komt er geen nieuw proces, dus we kunnen doorgaan met P3.
Stap 10) Op tijdsinterval 10 komt er geen nieuw proces, dus gaan we verder met P3
Stap 11) Op tijdstip=11 arriveert P4 met prioriteit 4. P3 heeft een hogere prioriteit en gaat dus door met de uitvoering.
| Proces | Prioriteit | Burst-tijd | Aankomsttijd |
|---|---|---|---|
| P1 | 1 | 4 | 0 |
| P2 | 2 | 1 op 3 in behandeling | 0 |
| P3 | 1 | 2 op 7 in behandeling | 6 |
| P4 | 3 | 4 | 11 |
| P5 | 2 | 2 | 12 |
Stap 12) Op tijdstip=12 arriveert P5. P3 heeft een hogere prioriteit en gaat dus door met de uitvoering.
Stap 13) Op tijdstip=13 voltooit P3 de uitvoering. We hebben P2,P4,P5 in gereedstaande wachtrij. P2 en P5 hebben dezelfde prioriteit. Aankomsttijd van P2 ligt vóór P5. Dus P2 begint met de uitvoering.
| Proces | Prioriteit | Burst-tijd | Aankomsttijd |
|---|---|---|---|
| P1 | 1 | 4 | 0 |
| P2 | 2 | 1 op 3 in behandeling | 0 |
| P3 | 1 | 7 | 6 |
| P4 | 3 | 4 | 11 |
| P5 | 2 | 2 | 12 |
Stap 14) Op tijdstip =14 is het P2-proces voltooid. P4 en P5 bevinden zich in de wachtstatus. P5 heeft de hoogste prioriteit en begint met de uitvoering.
Stap 15) Op tijdstip =15 gaat P5 door met de uitvoering.
Stap 16) Op tijdstip = 16 is P5 klaar met de uitvoering ervan. P4 is het enige overgebleven proces. Het begint met de uitvoering.
Stap 17) Op tijdstip =20 is P5 voltooid en is er geen proces meer over.
Stap 18) Laten we de gemiddelde wachttijd voor het bovenstaande voorbeeld berekenen.
Wachttijd = starttijd – aankomsttijd + wachttijd voor de volgende burst
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
Voordelen van prioriteitsplanning
Hier volgen de voordelen/voordelen van het gebruik van de prioriteitsplanningsmethode:
- Eenvoudig te gebruiken planningsmethode
- Processen worden uitgevoerd op basis van prioriteit, zodat hoge prioriteit niet lang hoeft te wachten, wat tijd bespaart
- Deze methode biedt een goed mechanisme waarmee het relatieve belang van elk proces nauwkeurig kan worden gedefinieerd.
- Geschikt voor toepassingen met wisselende tijd- en resourcevereisten.
Nadelen van prioriteitsplanning
Hier volgen de nadelen/nadelen van prioriteitsplanning
- Als het systeem uiteindelijk crasht, gaan alle processen met lage prioriteit verloren.
- Als processen met een hoge prioriteit veel CPU-tijd in beslag nemen, kunnen de processen met een lagere prioriteit verhongeren en voor onbepaalde tijd worden uitgesteld.
- Dit planningsalgoritme kan sommige processen met lage prioriteit voor onbepaalde tijd laten wachten.
- Een proces wordt geblokkeerd wanneer het klaar is om te worden uitgevoerd, maar moet wachten op de CPU omdat er momenteel een ander proces actief is.
- Als er een nieuw proces met een hogere prioriteit in de wachtrij blijft staan, moet het proces dat zich in de wachtstatus bevindt mogelijk een lange tijd wachten.
Samenvatting
- Prioriteitsplanning is een methode voor het plannen van processen die is gebaseerd op prioriteit. In dit algoritme selecteert de planner de taken die volgens de prioriteit moeten worden uitgevoerd.
- Bij Priority Preemptive Scheduling worden de taken meestal toegewezen met hun prioriteiten.
- Bij de Priority Non-preemptive planningsmethode is de CPU toegewezen aan een specifiek proces.
- Processen worden uitgevoerd op basis van prioriteit, zodat hoge prioriteit niet lang hoeft te wachten, wat tijd bespaart
- Als processen met een hoge prioriteit veel CPU-tijd in beslag nemen, kunnen de processen met een lagere prioriteit verhongeren en voor onbepaalde tijd worden uitgesteld.
