CPU-planning Algorithms in Operasystemen

Soorten CPU-planning

Hier zijn twee soorten planningsmethoden:

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.

Wanneer is planning preventief of niet-preventief?

Om te bepalen of planning preventief of niet-preventief is, houdt u rekening met deze vier parameters:

1. Een proces schakelt over van de lopende naar de wachtende toestand.
2. Specifieke processen schakelen van de actieve status naar de gereedstatus.
3. Specifieke processen schakelen van de wachtstatus naar de gereedstatus.
4. Het proces heeft de uitvoering ervan voltooid en beëindigd.

Alleen voorwaarde 1 en 4 zijn van toepassing, de planning wordt niet-preëmptief genoemd.

Alle andere planningen zijn preventief.

Belangrijke CPU-planningsterminologieën

• Bursttijd/uitvoeringstijd: Het is de tijd die het proces nodig heeft om de uitvoering te voltooien. Het wordt ook wel looptijd genoemd.
• Aankomsttijd: wanneer een proces de gereedheidsstatus bereikt
• Eindtijd: wanneer het proces is voltooid en een systeem wordt verlaten
• Multiprogrammering: Een aantal programma's die tegelijkertijd in het geheugen aanwezig kunnen zijn.
• Banen: Het is een soort programma zonder enige vorm van gebruikersinteractie.
• Gebruiker: Het is een soort programma met gebruikersinteractie.
• Werkwijze: Het is de referentie die wordt gebruikt voor zowel de taak als de gebruiker.
• CPU/IO burst-cyclus: Karakteriseert procesuitvoering, waarbij wordt afgewisseld tussen CPU- en I/O-activiteit. CPU-tijden zijn meestal korter dan de tijd van I/O.

CPU-planningscriteria

Een CPU-planningalgoritme probeert het volgende te maximaliseren en minimaliseren:

Maximaliseren

CPU-gebruik:CPU-gebruik is de belangrijkste taak waarbij het besturingssysteem ervoor moet zorgen dat de CPU zo druk mogelijk blijft. Het kan variëren van 0 tot 100 procent. Voor het RTOS kan het echter variëren van 40 procent voor het low-level en 90 procent voor het high-level systeem.

Doorvoer: Het aantal processen dat de uitvoering per tijdseenheid voltooit, is de zogenaamde Throughput. Dus wanneer de CPU bezig is met het uitvoeren van het proces, wordt er op dat moment gewerkt, en het werk dat per tijdseenheid wordt voltooid, wordt Throughput genoemd.

Verkleinen

Wachttijd: Wachttijd is de hoeveelheid tijd die een specifiek proces in de wachtrij moet wachten.

Reactietijd: Het is de hoeveelheid tijd waarin het verzoek is ingediend totdat het eerste antwoord is gegenereerd.

Doorlooptijd: Doorlooptijd is de hoeveelheid tijd die nodig is om een ​​specifiek proces uit te voeren. Het is de berekening van de totale tijd die is besteed aan het wachten om in het geheugen te komen, het wachten in de wachtrij en het uitvoeren op de CPU. De periode tussen het moment van indiening van het proces en de voltooiingstijd is de doorlooptijd.

Interval Timer

Timeronderbreking is een methode die nauw verwant is aan preemption. Wanneer een bepaald proces de CPU-toewijzing krijgt, kan een timer op een gespecificeerd interval worden ingesteld. Zowel timeronderbreking als voorrang dwingen een proces om de CPU terug te sturen voordat de CPU-burst voltooid is.

De meeste multi-geprogrammeerde besturingssystemen gebruiken een soort timer om te voorkomen dat een proces het systeem voor altijd vastzet.

Wat is Dispatcher?

Het is een module die controle over de CPU voor het proces biedt. De Dispatcher moet snel zijn, zodat deze op elke contextschakelaar kan worden uitgevoerd. Dispatchlatentie is de hoeveelheid tijd die de CPU-planner nodig heeft om het ene proces te stoppen en het andere te starten.

Functies uitgevoerd door Dispatcher:

• Context wisselen
• Overschakelen naar gebruikersmodus
• Verplaatsen naar de juiste locatie in het nieuw geladen programma.

Soorten CPU-planningsalgoritme

Er zijn hoofdzakelijk zes soorten procesplanning algoritmen

1. Wie het eerst komt, het eerst maalt (FCFS)
2. Shortest-Job-First (SJF) planning
3. Kortste resterende tijd
4. Prioriteitsplanning
5. Round Robin-planning
6. Wachtrijplanning op meerdere niveaus

Wie het eerst komt, het eerst maalt

Wie het eerst komt, het eerst maalt, is de volledige vorm van FCFS. Het is het gemakkelijkste en meest eenvoudige CPU-planningsalgoritme. Bij dit type algoritme krijgt het proces dat om de CPU vraagt ​​als eerste de CPU-toewijzing. Deze planningsmethode kan worden beheerd met een FIFO-wachtrij.

Wanneer het proces de gereedstaande wachtrij binnengaat, wordt de PCB (Process Control Block) gekoppeld aan de staart van de wachtrij. Dus wanneer de CPU vrijkomt, moet deze worden toegewezen aan het proces aan het begin van de wachtrij.

Kenmerken van de FCFS-methode

• Het biedt een niet-preventief en preventief planningsalgoritme.
• Taken worden altijd uitgevoerd op basis van wie het eerst komt, het eerst maalt
• Het is gemakkelijk te implementeren en te gebruiken.
• Deze methode presteert echter slecht en de algemene wachttijd is vrij hoog.

Kortste resterende tijd

De volledige vorm van SRT is de kortste resterende tijd. Het is ook bekend als preventieve planning van SJF. Bij deze methode wordt het proces toegewezen aan de taak die het dichtst bij de voltooiing ervan ligt. Deze methode voorkomt dat een nieuwer gereed statusproces de voltooiing van een ouder proces tegenhoudt.

Kenmerken van de SRT-planningsmethode

• Deze methode wordt vooral toegepast in batchomgevingen waar korte opdrachten de voorkeur moeten krijgen.
• Dit is geen ideale methode om het te implementeren in een gedeeld systeem waarbij de vereiste CPU-tijd onbekend is.
• Koppel aan elk proces de lengte van de volgende CPU-burst. Zodat het besturingssysteem deze lengtes gebruikt, wat helpt om het proces zo kort mogelijk te plannen.

Op prioriteiten gebaseerde planning

Prioriteitsplanning is een methode om processen te plannen op basis van prioriteit. Bij deze methode selecteert de planner de taken die volgens de prioriteit moeten worden uitgevoerd.

Prioriteitsplanning helpt het besturingssysteem ook bij het betrekken van prioriteitstoewijzingen. De processen met hogere prioriteit moeten als eerste worden uitgevoerd, terwijl taken met gelijke prioriteiten op round-robin- of FCFS-basis worden uitgevoerd. Prioriteit kan worden bepaald op basis van geheugenvereisten, tijdvereisten, enz.

Round-Robin-planning

Round robin is het oudste, eenvoudigste planningsalgoritme. De naam van dit algoritme komt van het round-robin-principe, waarbij elke persoon op zijn beurt een gelijk deel van iets krijgt. Het wordt vooral gebruikt voor planningsalgoritmen bij multitasking. Deze algoritmemethode helpt bij het uitvoeren van processen zonder honger.

Kenmerken van Round-Robin-planning

• Round Robin is een hybride model dat klokgestuurd is
• Het tijdsdeel moet minimaal zijn, wat wordt toegewezen aan een specifieke taak die moet worden verwerkt. Het kan echter variëren voor verschillende processen.
• Het is een real-time systeem dat binnen een bepaalde tijdslimiet op de gebeurtenis reageert.

Kortste baan eerst

SJF is een volledige vorm van (Kortste taak eerst) en is een planningsalgoritme waarin het proces met de kortste uitvoeringstijd moet worden geselecteerd om vervolgens te worden uitgevoerd. Deze planningsmethode kan preventief of niet-preventief zijn. Het vermindert de gemiddelde wachttijd voor andere processen die wachten op uitvoering aanzienlijk.

Kenmerken van SJF-planning

• Het wordt aan elke taak gekoppeld als een tijdseenheid die moet worden voltooid.
• Bij deze methode wordt, wanneer de CPU beschikbaar is, het volgende proces of de volgende taak met de kortste voltooiingstijd als eerste uitgevoerd.
• Het wordt geïmplementeerd met niet-preventief beleid.
• Deze algoritmemethode is handig voor batchverwerking, waarbij wachten tot taken zijn voltooid niet van cruciaal belang is.
• Het verbetert de taakopbrengst door kortere taken aan te bieden, die als eerste moeten worden uitgevoerd en die meestal een kortere doorlooptijd hebben.

Wachtrijplanning op meerdere niveaus

Dit algoritme verdeelt de gereedstaande wachtrij in verschillende afzonderlijke wachtrijen. Bij deze methode worden processen aan een wachtrij toegewezen op basis van een specifieke eigenschap van het proces, zoals de procesprioriteit, de grootte van het geheugen, enz.

Dit is echter geen onafhankelijk algoritme voor het plannen van taken, omdat er andere typen algoritmen nodig zijn om de taken te plannen.

Kenmerkend voor het plannen van wachtrijen op meerdere niveaus

• Voor processen met bepaalde kenmerken moeten meerdere wachtrijen worden onderhouden.
• Elke wachtrij kan zijn eigen planningalgoritmen hebben.
• Voor elke wachtrij worden prioriteiten gegeven.

Het doel van een planningsalgoritme

Hier zijn de redenen voor het gebruik van een planningsalgoritme:

• De CPU gebruikt planning om de efficiëntie te verbeteren.
• Het helpt u bij het toewijzen van middelen aan concurrerende processen.
• Het maximale gebruik van de CPU kan worden verkregen met multiprogrammering.
• De processen die moeten worden uitgevoerd, staan ​​in de wachtrij.

Samenvatting

• CPU-planning is een proces waarbij wordt bepaald welk proces de CPU zal bezitten voor uitvoering terwijl een ander proces in de wacht staat.
• Bij Preemptive Scheduling worden de taken meestal toegewezen met hun prioriteiten.
• Bij de niet-preventieve planningsmethode is de CPU toegewezen aan een specifiek proces.
• De burst-tijd is de tijd die het proces nodig heeft om de uitvoering te voltooien. Het wordt ook wel looptijd genoemd.
• CPU-gebruik is de belangrijkste taak van het besturingssysteem. Het besturingssysteem moet ervoor zorgen dat de CPU zo veel mogelijk wordt gebruikt.
• Het aantal processen dat de uitvoering per tijdseenheid voltooit, is de zogenaamde Throughput.
• Wachttijd is de hoeveelheid tijd die een specifiek proces in de wachtrij moet wachten.
• Het is de hoeveelheid tijd waarin het verzoek is ingediend totdat het eerste antwoord is gegenereerd.
• Doorlooptijd is de hoeveelheid tijd die nodig is om een ​​specifiek proces uit te voeren.
• Timeronderbreking is een methode die nauw verwant is aan preemption.
• Een dispatcher is een module die controle over de CPU aan het proces geeft.
• Zes typen algoritmen voor procesplanning zijn: First Come First Serve (FCFS), 2) Shortest-Job-First (SJF)-planning, 3) Shortest Remaining Time, 4) Priority Scheduling, 5) Round Robin Scheduling, 6) Multilevel Queue Scheduling.
• In het Wie het eerst komt, het eerst maalt, krijgt het proces dat om de CPU vraagt ​​eerst de CPU-toewijzing.
• In de kortste resterende tijd wordt het proces toegewezen aan de taak die het dichtst bij de voltooiing ervan ligt.
• Bij Prioriteitsplanning selecteert de planner de taken die volgens de prioriteit moeten worden uitgevoerd.
• Round robin planning werkt volgens het principe waarbij iedereen op zijn beurt een gelijk deel van iets krijgt.
• Bij Kortste taak eerst moet de kortste uitvoeringstijd worden geselecteerd voor uitvoering daarna.
• De planningsmethode op meerdere niveaus verdeelt de wachtrij in verschillende afzonderlijke wachtrijen. Bij deze methode worden processen toegewezen aan een wachtrij op basis van een specifieke eigenschap.
• De CPU gebruikt planning om de efficiëntie te verbeteren.