CPU-planning Algorithms in Operasystemen

Wat is CPU-planning?

CPU-planning CPU-scheduling is een proces dat bepaalt welk proces de CPU krijgt voor uitvoering terwijl een ander proces in de wachtstand staat. De belangrijkste taak van CPU-scheduling is ervoor te zorgen dat, wanneer de CPU inactief is, het besturingssysteem ten minste één van de beschikbare processen in de wachtrij selecteert voor uitvoering. Het selectieproces wordt uitgevoerd door de CPU-scheduler, die een van de processen in het geheugen selecteert die klaar zijn voor uitvoering.

Soorten CPU-planning

Hieronder volgen twee soorten planningsmethoden:

Preventieve planning

Bij preemptieve scheduling worden taken meestal toegewezen op basis van hun prioriteit. 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 lagere prioriteit nog bezig is. De taak met lagere prioriteit wordt dan enige tijd gewacht en hervat wanneer de taak met hogere prioriteit klaar is.

Niet-preventieve planning

Bij deze planningsmethode wordt de CPU toegewezen aan een specifiek proces. Het proces dat de CPU bezet houdt, geeft de CPU vrij door van context te wisselen of te eindigen. Het is de enige methode die op verschillende hardwareplatformen gebruikt kan worden, omdat er geen speciale hardware (zoals bijvoorbeeld een timer) nodig is, in tegenstelling tot preemptieve scheduling.

Wanneer is planning preemptief of niet-preemptief?

Om te bepalen of de planning preemptief of niet-preemptief is, moet u rekening houden met de volgende vier parameters:

1. Een proces schakelt over van de lopende naar de wachtende toestand.
2. Een specifiek proces schakelt over van de actieve status naar de gereedstatus.
3. Een specifiek proces schakelt over van de wachttoestand naar de gereedtoestand.
4. Een proces voltooit zijn uitvoering en wordt beëindigd.

Als alleen voorwaarden 1 en 4 van toepassing zijn, wordt de planning niet-preëmptief genoemd. Alle andere planningssituaties zijn preëmptief.

Belangrijke terminologieën voor CPU-planning

• Bursttijd/uitvoeringstijd: De tijd die een proces nodig heeft om de uitvoering te voltooien. Dit wordt ook wel looptijd genoemd.
• Aankomsttijd: Het moment waarop een proces de gereed-status bereikt.
• Eindtijd: Het moment waarop een proces is voltooid en het systeem verlaat.
• Multiprogrammering: Een aantal programma's die tegelijkertijd in het geheugen aanwezig kunnen zijn.
• Banen: Een type programma zonder enige vorm van gebruikersinteractie.
• Gebruiker: Een soort programma waarbij de gebruiker interactie heeft.
• Werkwijze: De referentie die zowel voor een functie als voor een gebruiker wordt gebruikt.
• CPU/IO burst-cyclus: Dit kenmerkt de uitvoering van een proces, waarbij CPU- en I/O-activiteit elkaar afwisselen. De CPU-tijden zijn doorgaans korter dan de I/O-tijden.

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 veel mogelijk wordt benut. Dit kan variëren van 0 tot 100 procent. Voor een RTOS kan het echter variëren van 40 procent voor een systeem op laag niveau tot 90 procent voor een systeem op hoog niveau.

Doorvoer: Het aantal processen dat per tijdseenheid zijn uitvoering voltooit, wordt doorvoer genoemd. Dus, wanneer de CPU bezig is met het uitvoeren van een proces, wordt er werk verricht en de hoeveelheid werk die per tijdseenheid wordt voltooid, noemen we doorvoer.

Verkleinen

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

Reactietijd: Het is de tijdsduur vanaf het moment dat het verzoek is ingediend tot het moment dat het eerste antwoord wordt gegeven.

Doorlooptijd: De doorlooptijd is de hoeveelheid tijd die nodig is om een ​​specifiek proces uit te voeren. Het is de totale tijd die wordt besteed aan het laden in het geheugen, wachten in de wachtrij en de uitvoering op de CPU. De periode tussen het moment van het indienen van een proces en het moment van voltooiing 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 besturingssystemen die meerdere programma's tegelijk uitvoeren, gebruiken een timer om te voorkomen dat een proces het systeem permanent blokkeert.

Wat is Dispatcher?

De dispatcher is een module die de controle over de CPU aan het proces geeft. De dispatcher moet snel zijn, zodat deze bij elke contextwissel kan worden uitgevoerd. Dispatchlatentie is de tijd die de CPU-scheduler nodig heeft om een ​​proces te stoppen en een ander te starten.

Functies uitgevoerd door de dispatcher:

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

Soorten CPU-planning Algorithms

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

Scheduling Algorithms

Wie het eerst komt, het eerst maalt

FCFS staat voor Wie het eerst komt, het eerst maaltHet is het eenvoudigste en makkelijkste CPU-planningsalgoritme. Bij dit type algoritme krijgt het proces dat de CPU aanvraagt ​​deze als eerste toegewezen. Deze planningsmethode kan worden beheerd met een FIFO-wachtrij.

Zodra een proces in de wachtrij komt, wordt de bijbehorende PCB (Process Control Block) gekoppeld aan het einde van de wachtrij. Wanneer de CPU dus vrijkomt, moet deze worden toegewezen aan het proces aan het begin van de wachtrij.

Kenmerken van de FCFS-methode

• Het is een niet-preëmptief 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 naam van SRT is Shortest Remaining Time. Het wordt ook wel SJF preemptieve scheduling genoemd. Bij deze methode wordt een proces toegewezen aan de taak die het dichtst bij voltooiing is. Deze methode voorkomt dat een nieuwer, gereed proces de voltooiing van een ouder proces vertraagt.

Kenmerken van de SRT-planningsmethode

• Deze methode wordt vooral toegepast in batchomgevingen waar korte taken voorrang moeten krijgen.
• Dit is geen ideale methode om te implementeren in een gedeeld systeem waar de benodigde CPU-tijd onbekend is.
• Aan elk proces is de duur van de volgende CPU-burst gekoppeld, dus het besturingssysteem gebruikt deze duur om het proces zo snel mogelijk in te plannen.

Op prioriteiten gebaseerde planning

Prioriteitsplanning Dit is een methode voor het plannen van processen op basis van prioriteit. Bij deze methode selecteert de planner de taken waaraan gewerkt moet worden op basis van hun prioriteit.

Prioriteitsplanning helpt het besturingssysteem ook bij het toekennen van prioriteiten. Processen met een hogere prioriteit worden eerst uitgevoerd, terwijl taken met een gelijke prioriteit volgens het round-robin- of FCFS-principe worden uitgevoerd. De prioriteit kan worden bepaald op basis van geheugenvereisten, tijdsvereisten en andere factoren.

Round-Robin-planning

ronde robijn Dit is een van de oudste en eenvoudigste planningsalgoritmen. De naam van dit algoritme is afgeleid van het round-robin-principe, waarbij iedereen om de beurt een gelijk deel van iets krijgt. Het wordt vooral gebruikt voor planning in multitasking-systemen. Deze methode helpt bij het voorkomen van uithongering van processen.

Kenmerken van Round-Robin-planning

• Round robin is een hybride model dat klokgestuurd is.
• De tijdsduur die is toegewezen aan de verwerking van een specifieke taak moet minimaal zijn. Deze kan echter variëren afhankelijk van het proces.
• Het werkt als een tijdsdeelsysteem dat op elk proces binnen een bepaalde tijdslimiet reageert.

Kortste baan eerst

SJF (Shortest Job First) is een planningsalgoritme waarbij het proces met de kortste uitvoeringstijd als volgende wordt geselecteerd. Deze planningsmethode kan preemptief of niet-preemptief zijn. Het verkort de gemiddelde wachttijd voor andere processen die op uitvoering wachten aanzienlijk.

Kenmerken van SJF-planning

• Aan elke taak is een tijdseenheid gekoppeld om deze te voltooien.
• Bij deze methode wordt, zodra de CPU beschikbaar is, het proces of de taak met de kortste voltooiingstijd als eerste uitgevoerd.
• Het wordt geïmplementeerd met een niet-preëmptief beleid.
• Dit algoritme is nuttig voor batchverwerking, waarbij het niet cruciaal is om te wachten tot taken zijn voltooid.
• Het verbetert de productiviteit door eerst de kortere taken uit te voeren, die over het algemeen een kortere doorlooptijd hebben.

Wachtrijplanning op meerdere niveaus

Dit algoritme verdeelt de wachtrij met gereedstaande processen in meerdere afzonderlijke wachtrijen. Bij deze methode worden processen aan een wachtrij toegewezen op basis van een specifieke eigenschap van het proces, zoals de procesprioriteit, de geheugengrootte, enzovoort.

Dit is echter geen onafhankelijk planningsalgoritme, omdat het andere algoritmen nodig heeft om de taken in te plannen.

Kenmerken van planning met wachtrijen op meerdere niveaus

• Voor processen met gedeelde kenmerken moeten meerdere wachtrijen worden bijgehouden.
• Elke wachtrij kan een eigen, afzonderlijk planningsalgoritme hebben.
• Aan elke wachtrij worden prioriteiten toegekend.

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 je om middelen te verdelen over concurrerende processen.
• De maximale benutting van de CPU kan worden bereikt met multiprogrammering.
• De processen die uitgevoerd moeten worden, worden in de wachtrij geplaatst.

Veelgestelde vragen