CPU-planningsalgoritmen in besturingssystemen

Wat is CPU-planning?

CPU-planning is een proces om te bepalen welk proces de CPU zal bezitten voor uitvoering terwijl een ander proces in de wacht staat. De belangrijkste taak van CPU-planning is ervoor te zorgen dat wanneer de CPU inactief blijft, het besturingssysteem ten minste een van de processen selecteert die beschikbaar zijn in de gereedstaande wachtrij voor uitvoering. Het selectieproces wordt uitgevoerd door de CPU-planner. Het selecteert een van de processen in het geheugen die klaar zijn voor uitvoering.

In deze zelfstudie over CPU-planning leert u:

Typen CPU-planning

Hier zijn twee soorten planningsmethoden:

Preventieve planning

In Preemptive Scheduling worden de taken meestal toegewezen met hun prioriteiten. Soms is het belangrijk om een ​​taak met een hogere prioriteit uit te voeren voor een andere taak met een lagere prioriteit, zelfs als de taak met een lagere prioriteit nog loopt. De taak met een lagere prioriteit houdt enige tijd stand en wordt hervat wanneer de taak met een 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 het geen speciale hardware nodig heeft (bijvoorbeeld een timer) zoals preventieve planning.

Wanneer is planning preventief of niet-preventief?

Houd rekening met deze vier parameters om te bepalen of planning preventief of niet-preventief is:

  1. Een proces schakelt van de actieve naar de wachtstatus.
  2. Specifiek proces schakelt over van de actieve status naar de gereedstatus.
  3. Specifiek proces schakelt over van de wachtstatus naar de gereedstatus.
  4. Proces voltooide de uitvoering en beëindigd.

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

Alle andere planningen zijn preventief.

Belangrijke terminologieën voor CPU-planning

  • Burst-tijd/uitvoeringstijd: Het is een tijd die het proces nodig heeft om de uitvoering te voltooien. Het wordt ook wel looptijd genoemd.
  • Aankomsttijd: wanneer een proces in een gereedstatus komt
  • Eindtijd: wanneer het proces is voltooid en een systeem verlaat
  • 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.
  • Proces: Het is de referentie die zowel voor de job als voor de gebruiker wordt gebruikt.
  • CPU/IO burst-cyclus: Kenmerkend voor procesuitvoering, die wisselt tussen CPU- en I/O-activiteit. CPU-tijden zijn meestal korter dan de tijd van I/O.

CPU-planningscriteria

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

Maximaliseren:

CPU-gebruik: CPU-gebruik is de belangrijkste taak waarin het besturingssysteem ervoor moet zorgen dat de CPU zo druk mogelijk blijft. Het kan variëren van 0 tot 100 procent. Voor de RTOS kan dit echter variëren van 40 procent voor het systeem op laag niveau en 90 procent voor het systeem op hoog niveau.

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

Minimaliseren:

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

Reactietijd: Het is een hoeveelheid tijd waarin het verzoek is ingediend totdat de eerste reactie is geproduceerd.

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

Intervaltimer

Timeronderbreking is een methode die nauw verwant is aan voorkoop. Wanneer een bepaald proces de CPU-toewijzing krijgt, kan een timer worden ingesteld op een gespecificeerd interval. Zowel timeronderbreking als preëmptie dwingen een proces om de CPU te retourneren voordat de CPU-burst is voltooid.

Het grootste deel van het meervoudig geprogrammeerde besturingssysteem gebruikt een of andere vorm van een timer om te voorkomen dat een proces het systeem voor altijd vastlegt.

Wat is Dispatcher?

Het is een module die controle over de CPU aan het proces geeft. De Dispatcher moet snel zijn, zodat hij op elke context-switch kan draaien. Verzendlatentie 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.

Typen CPU-planningsalgoritme

Er zijn hoofdzakelijk zes soorten algoritmen voor procesplanning:

  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

Planningsalgoritmen



Wie het eerst komt, het eerst maalt

First Come First Serve is de volledige vorm van FCFS. Het is het gemakkelijkste en meest eenvoudige algoritme voor CPU-planning. In dit type algoritme krijgt het proces dat de CPU aanvraagt ​​eerst de CPU-toewijzing. Deze planningsmethode kan worden beheerd met een FIFO-wachtrij.

Als het proces de wachtrij binnenkomt, wordt zijn PCB (Process Control Block) gekoppeld aan de staart van de wachtrij. Dus wanneer de CPU vrij komt, moet deze aan het begin van de wachtrij aan het proces worden toegewezen.

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 Kortste resterende tijd. Het is ook bekend als SJF preventieve planning. Bij deze methode wordt het proces toegewezen aan de taak die het dichtst bij zijn voltooiing is. 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 waar de benodigde CPU-tijd onbekend is.
  • Associeer met elk proces als de lengte van de volgende CPU-burst. Dus dat besturingssysteem gebruikt deze lengtes, wat helpt om het proces met de kortst mogelijke tijd te plannen.

Op prioriteit 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 werken.

Prioriteitsplanning helpt het besturingssysteem ook om prioriteitstoewijzingen te betrekken. 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 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 meestal gebruikt voor het plannen van algoritmen bij multitasking. Deze algoritmemethode helpt bij het hongervrij uitvoeren van processen.

Kenmerken van Round-Robin-planning

  • Round robin is een hybride model dat wordt aangedreven door een klok
  • De tijdschijf moet minimaal zijn, die is toegewezen aan een specifieke taak die moet worden verwerkt. Het kan echter variëren voor verschillende processen.
  • Het is een realtime systeem dat binnen een bepaalde tijdslimiet op de gebeurtenis reageert.

Kortste baan eerst

SJF is een volledige vorm van (Kortste taak eerst) is een planningsalgoritme waarin het proces met de kortste uitvoeringstijd als volgende moet worden geselecteerd voor uitvoering. 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 is gekoppeld aan elke taak 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 doorlooptijd als eerste uitgevoerd.
  • Het wordt uitgevoerd met niet-preventief beleid.
  • Deze algoritmemethode is handig voor batchverwerking, waarbij wachten op het voltooien van taken niet essentieel is.
  • Het verbetert de joboutput door kortere jobs aan te bieden, die eerst uitgevoerd moeten worden, die meestal een kortere doorlooptijd hebben.

Wachtrijen op meerdere niveaus plannen

Dit algoritme verdeelt de klaar-wachtrij in verschillende afzonderlijke wachtrijen. Bij deze methode worden processen toegewezen aan een wachtrij 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 het besturingssysteem, omdat het andere soorten algoritmen moet gebruiken om de taken te plannen.

Kenmerkend voor het plannen van wachtrijen op meerdere niveaus:

  • Er moeten meerdere wachtrijen worden bijgehouden voor processen met bepaalde kenmerken.
  • Elke wachtrij kan zijn eigen planningsalgoritmen hebben.
  • Voor elke wachtrij wordt een prioriteit 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 middelen toe te wijzen aan concurrerende processen.
  • Het maximale CPU-gebruik kan worden bereikt met multi-programmering.
  • De uit te voeren processen staan ​​in de wachtrij.

Samenvatting:

  • CPU-planning is een proces om te bepalen welk proces de CPU zal bezitten voor uitvoering terwijl een ander proces in de wacht staat.
  • In Preemptive Scheduling worden de taken meestal toegewezen met hun prioriteiten.
  • In de niet-preventieve planningsmethode is de CPU toegewezen aan een specifiek proces.
  • Burst-tijd is een tijd die nodig is voor het proces om de uitvoering te voltooien. Het wordt ook wel looptijd genoemd.
  • CPU-gebruik is de belangrijkste taak waarin het besturingssysteem ervoor moet zorgen dat de CPU zo druk mogelijk blijft
  • Het aantal processen dat hun uitvoering per tijdseenheid voltooit, is de bekende doorvoer.
  • Wachttijd is een hoeveelheid die een specifiek proces moet wachten in de wachtrij.
  • Het is een hoeveelheid tijd waarin het verzoek is ingediend totdat de eerste reactie is geproduceerd.
  • Doorlooptijd is een hoeveelheid tijd om een ​​specifiek proces uit te voeren.
  • Timeronderbreking is een methode die nauw verwant is aan preëmptie,
  • Een dispatcher is een module die de controle over de CPU aan het proces geeft.
  • Zes soorten procesplanningsalgoritmen zijn:
  • First Come First Serve (FCFS), 2) Shortest-Job-First (SJF)-planning 3) Kortste resterende tijd 4) Prioriteitsplanning 5) Round Robin-planning 6) Multilevel-wachtrijplanning
  • Bij de First Come First Serve-methode krijgt het proces dat de CPU aanvraagt ​​eerst de CPU-toewijzing.
  • In de kortst resterende tijd zal het proces worden toegewezen aan de taak die het dichtst bij zijn voltooiing is.
  • In Prioriteitsplanning selecteert de planner de taken die volgens de prioriteit moeten werken.
  • In deze Round Robin-planning werkt het principe, waarbij elke persoon op zijn beurt een gelijk deel van iets krijgt
  • In Kortste taak eerst moet de kortste uitvoeringstijd worden geselecteerd voor uitvoering daarna
  • Bij planning op meerdere niveaus scheidt de methode de klaar-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.