CPU-planlægningsalgoritmer i operativsystemer

Indholdsfortegnelse:

Anonim

Hvad er CPU-planlægning?

CPU-planlægning er en proces til at bestemme, hvilken proces der vil eje CPU til udførelse, mens en anden proces er i venteposition. Hovedopgaven med CPU-planlægning er at sikre, at når CPU'en forbliver inaktiv, skal OS i det mindste vælge en af ​​de tilgængelige processer i den klare kø til udførelse. Udvælgelsesprocessen udføres af CPU-planlæggeren. Det vælger en af ​​de processer i hukommelsen, der er klar til udførelse.

I denne CPU-planlægningsvejledning lærer du:

  • Hvad er CPU-planlægning?
  • Typer af CPU-planlægning
  • Vigtige CPU-planlægningsterminologier
  • Kriterier for CPU-planlægning
  • Interval timer
  • Hvad er Dispatcher?
  • Typer af CPU-planlægningsalgoritme
  • Først til mølle
  • Korteste resterende tid
  • Prioriteret planlægning
  • Round-Robin planlægning
  • Korteste job først
  • Planlægning af køer på flere niveauer
  • Formålet med en planlægningsalgoritme

Typer af CPU-planlægning

Her er to slags planlægningsmetoder:

Forebyggende planlægning

I præventiv planlægning tildeles opgaverne for det meste med deres prioriteter. Nogle gange er det vigtigt at køre en opgave med en højere prioritet før en anden opgave med lavere prioritet, selvom opgaven med lavere prioritet stadig kører. Opgaven med lavere prioritet holder i nogen tid og genoptages, når opgaven med højere prioritet er færdig med udførelsen.

Ikke-forebyggende planlægning

I denne type planlægningsmetode er CPU'en allokeret til en bestemt proces. Processen, der holder CPU'en optaget, frigiver CPU'en enten ved at skifte kontekst eller afslutte. Det er den eneste metode, der kan bruges til forskellige hardwareplatforme. Det skyldes, at det ikke har brug for særlig hardware (for eksempel en timer) som forebyggende planlægning.

Når planlægning er forebyggende eller ikke-forebyggende?

For at afgøre, om planlægning er forebyggende eller ikke-forebyggende, skal du overveje disse fire parametre:

  1. En proces skifter fra kører til ventetilstand.
  2. Specifik proces skifter fra kørende tilstand til klar tilstand.
  3. Specifik proces skifter fra ventetilstand til klar tilstand.
  4. Processen afsluttede sin udførelse og blev afsluttet.

Kun betingelser 1 og 4 gælder, planlægningen kaldes ikke-forebyggende.

Al anden planlægning er forebyggende.

Vigtige CPU-planlægningsterminologier

  • Bursttid / udførelsestid: Det er en tid, der kræves af processen for at fuldføre udførelsen. Det kaldes også kørselstid.
  • Ankomsttid: når en proces går i klar tilstand
  • Afslutningstid: når processen er færdig og afslutter et system
  • Multiprogrammering: Et antal programmer, der kan være til stede i hukommelsen på samme tid.
  • Job: Det er en type program uden nogen form for brugerinteraktion.
  • Bruger: Det er en slags program, der har brugerinteraktion.
  • Process: Det er den reference, der bruges til både job og bruger.
  • CPU / IO burst-cyklus: Karakteriserer procesudførelse, der veksler mellem CPU- og I / O-aktivitet. CPU-tider er normalt kortere end tiden for I / O.

Kriterier for CPU-planlægning

En algoritme til CPU-planlægning forsøger at maksimere og minimere følgende:

Maksimer:

CPU-udnyttelse: CPU-udnyttelse er den vigtigste opgave, hvor operativsystemet skal sikre, at CPU forbliver så travlt som muligt. Det kan variere fra 0 til 100 procent. For RTOS kan det dog være fra 40 procent for lavt niveau og 90 procent for højniveausystemet.

Gennemløb: Antallet af processer, der afslutter deres udførelse pr. Tidsenhed, er kendt Gennemløb. Så når CPU'en er optaget af at udføre processen, på det tidspunkt udføres der arbejde, og arbejdet afsluttet pr. Tidsenhed kaldes gennemløb.

Minimer:

Ventetid: Ventetid er et beløb, som den specifikke proces skal vente i den klare kø.

Svartid: Det er et tidsrum, hvor anmodningen blev indsendt, indtil det første svar er produceret.

Turnaround Time: Turnaround time er en mængde tid til at udføre en bestemt proces. Det er beregningen af ​​den samlede tid brugt på at vente på at komme ind i hukommelsen, vente i køen og udføre på CPU'en. Perioden mellem tidspunktet for aflevering af processen til afslutningstiden er omløbstiden.

Interval timer

Timer-afbrydelse er en metode, der er tæt knyttet til præemption. Når en bestemt proces får CPU-tildelingen, kan en timer indstilles til et bestemt interval. Både timerafbrydelse og præemption tvinger en proces til at returnere CPU'en, før dens CPU burst er afsluttet.

Det meste af det flerprogrammerede operativsystem bruger en eller anden form for en timer til at forhindre en proces i at binde systemet for evigt.

Hvad er Dispatcher?

Det er et modul, der giver kontrol over CPU'en til processen. Dispatcheren skal være hurtig, så den kan køre på alle kontekstomskiftere. Forsendelsesforsinkelse er den tid, der kræves af CPU-planlæggeren til at stoppe en proces og starte en anden.

Funktioner udført af Dispatcher:

  • Kontekstskift
  • Skift til brugertilstand
  • Flytning til den rigtige placering i det nyindlæste program.

Typer af CPU-planlægningsalgoritme

Der er hovedsageligt seks typer procesplanlægningsalgoritmer

  1. First Come First Serve (FCFS)
  2. Planlægning af korteste job-første (SJF)
  3. Korteste resterende tid
  4. Prioriteret planlægning
  5. Runde Robin Planlægning
  6. Planlægning af kø til flere niveauer
Planlægning af algoritmer

Først til mølle

First Come First Serve er den fulde form for FCFS. Det er den nemmeste og mest enkle algoritme til CPU-planlægning. I denne type algoritme får processen, der anmoder om CPU, først CPU-tildelingen. Denne planlægningsmetode kan styres med en FIFO-kø.

Når processen går ind i den klare kø, er dens PCB (Process Control Block) forbundet med køens hale. Så når CPU bliver gratis, skal den tildeles processen i begyndelsen af ​​køen.

Karakteristik af FCFS-metoden:

  • Det tilbyder ikke-forebyggende og forebyggende planlægningsalgoritme.
  • Job udføres altid efter først til mølle-princippet
  • Det er let at implementere og bruge.
  • Denne metode har dog dårlig ydelse, og den generelle ventetid er ret høj.

Korteste resterende tid

Den fulde form for SRT er korteste resterende tid. Det er også kendt som SJF forebyggende planlægning. I denne metode tildeles processen til opgaven, som er tættest på dens afslutning. Denne metode forhindrer en nyere klar tilstandsproces i at afslutte færdiggørelsen af ​​en ældre proces.

Karakteristika for SRT planlægningsmetode:

  • Denne metode anvendes for det meste i batchmiljøer, hvor korte job skal foretrækkes.
  • Dette er ikke en ideel metode til at implementere det i et delt system, hvor den krævede CPU-tid er ukendt.
  • Associer med hver proces, når længden af ​​den næste CPU-burst. Så operativsystemet bruger disse længder, hvilket hjælper med at planlægge processen med den kortest mulige tid.

Prioriteret planlægning

Prioritetsplanlægning er en metode til planlægning af processer baseret på prioritet. I denne metode vælger planlæggeren de opgaver, der skal fungere i henhold til prioriteten.

Prioritetsplanlægning hjælper også OS med at involvere prioritetsopgaver. Processerne med højere prioritet skal udføres først, mens job med lige prioriteter udføres på en round-robin eller FCFS-basis. Prioritet kan afgøres ud fra hukommelseskrav, tidskrav osv.

Round-Robin planlægning

Round robin er den ældste, enkleste planlægningsalgoritme. Navnet på denne algoritme kommer fra round-robin-princippet, hvor hver person får en lige stor andel af noget igen. Det bruges mest til planlægning af algoritmer i multitasking. Denne algoritmemetode hjælper med sultfri udførelse af processer.

Karakteristika ved Round-Robin Scheduling

  • Round robin er en hybridmodel, der er urdrevet
  • Tidsskemaet skal være minimum, hvilket er tildelt til en bestemt opgave, der skal behandles. Det kan dog variere for forskellige processer.
  • Det er et realtidssystem, der reagerer på begivenheden inden for en bestemt tidsfrist.

Korteste job først

SJF er en fuld form for (Korteste job først) er en planlægningsalgoritme, hvor processen med den korteste udførelsestid skal vælges til udførelse næste. Denne planlægningsmetode kan være forebyggende eller ikke-forebyggende. Det reducerer den gennemsnitlige ventetid for andre processer, der afventer udførelse, betydeligt.

Karakteristika ved SJF-planlægning

  • Det er forbundet med hvert job som en tidsenhed, der skal gennemføres.
  • I denne metode, når CPU'en er tilgængelig, udføres den næste proces eller det job med den korteste afslutningstid først.
  • Det gennemføres med ikke-forebyggende politik.
  • Denne algoritmemetode er nyttig til batch-behandling, hvor det ikke er kritisk at vente på, at job er afsluttet.
  • Det forbedrer joboutput ved at tilbyde kortere job, som skal udføres først, som for det meste har en kortere leveringstid.

Planlægning af køer på flere niveauer

Denne algoritme adskiller den klare kø i forskellige separate køer. I denne metode tildeles processer til en kø baseret på en bestemt egenskab ved processen, som procesprioritet, størrelse på hukommelsen osv.

Dette er dog ikke en uafhængig planlægning af OS-algoritme, da den skal bruge andre typer algoritmer for at planlægge jobbet.

Karakteristisk for planlægning af køer på flere niveauer:

  • Der skal opretholdes flere køer til processer med nogle egenskaber.
  • Hver kø kan have sine separate planlægningsalgoritmer.
  • Der prioriteres for hver kø.

Formålet med en planlægningsalgoritme

Her er grundene til at bruge en planlægningsalgoritme:

  • CPU'en bruger planlægning for at forbedre effektiviteten.
  • Det hjælper dig med at fordele ressourcer mellem konkurrerende processer.
  • Den maksimale udnyttelse af CPU kan opnås med multiprogrammering.
  • De processer, der skal udføres, står i kø.

Resumé:

  • CPU-planlægning er en proces til at bestemme, hvilken proces der vil have CPU til udførelse, mens en anden proces er i venteposition.
  • I præventiv planlægning tildeles opgaverne for det meste med deres prioriteter.
  • I den ikke-forebyggende planlægningsmetode er CPU'en allokeret til en bestemt proces.
  • Bursttid er en tid, der kræves for at processen kan gennemføres. Det kaldes også kørselstid.
  • CPU-udnyttelse er den vigtigste opgave, hvor operativsystemet skal sikre, at CPU forbliver så travl som muligt
  • Antallet af processer, der afslutter deres udførelse pr. Tidsenhed, er kendt gennemstrømning.
  • Ventetid er et beløb, som den specifikke proces skal vente i den klare kø.
  • Det er et tidsrum, hvor anmodningen blev indsendt, indtil det første svar er produceret.
  • Vendetid er en tid til at udføre en bestemt proces.
  • Timer-afbrydelse er en metode, der er tæt knyttet til præemption,
  • En afsender er et modul, der giver kontrol over CPU'en til processen.
  • Seks typer procesplanlægningsalgoritmer er:
  • First Come First Serve (FCFS), 2) Korteste job-først (SJF) Planlægning 3) Korteste resterende tid 4) Prioritetsplanlægning 5) Runde Robin Planlægning 6) Flerniveau køplanlægning
  • I metoden First Come First Serve får processen, der anmoder om CPU, CPU-tildelingen først.
  • På den korteste resterende tid tildeles processen til opgaven, som er tættest på dens afslutning.
  • I Prioriteret planlægning vælger planlæggeren de opgaver, der skal fungere i henhold til prioriteten.
  • I denne Round Robin-planlægning fungerer på princip, hvor hver person får en lige stor andel af noget igen
  • I Korteste job skal først den korteste udførelsestid vælges til udførelse derefter
  • I planlægning på flere niveauer adskiller metoden den klare kø i forskellige separate køer. I denne metode tildeles processer til en kø baseret på en bestemt egenskab
  • CPU'en bruger planlægning for at forbedre effektiviteten.