CPU-planlægning Algorithms in Operating Systemer

Hvad er CPU-planlægning?

CPU-planlægning er en proces til at bestemme, hvilken proces der skal eje CPU'en til udførelse, mens en anden proces er sat på hold. Hovedopgaven ved CPU-planlægning er at sikre, at når CPU'en forbliver inaktiv, vælger operativsystemet mindst én af de processer, der er tilgængelige i klarkøen til udførelse. Udvælgelsesprocessen udføres af CPU-planlæggeren, som vælger en af ​​de processer i hukommelsen, der er klar til udførelse.

Typer af CPU-planlægning

Her er to typer planlægningsmetoder:

Forebyggende planlægning

I præemptiv 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 et stykke tid og genoptages, når opgaven med højere prioritet afslutter sin udførelse.

Ikke-forebyggende planlægning

I denne type planlægningsmetode allokeres CPU'en til en specifik proces. Den proces, der holder CPU'en beskæftiget, frigiver CPU'en enten ved at skifte kontekst eller afslutte. Det er den eneste metode, der kan bruges på tværs af forskellige hardwareplatforme, fordi den ikke kræver speciel hardware (f.eks. en timer) som præemptiv planlægning.

Hvornår er planlægning præemptiv eller ikke-præemptiv?

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

1. En proces skifter fra kørende til ventetilstand.
2. En specifik proces skifter fra kørende tilstand til klartilstand.
3. En specifik proces skifter fra ventetilstand til klartilstand.
4. En proces afslutter sin udførelse og afsluttes.

Hvis kun betingelse 1 og 4 gælder, kaldes planlægningen ikke-præemptiv. Alle andre planlægningssituationer er præemptive.

Vigtige CPU-planlægningsterminologier

• Burst-tid/udførelsestid: Den tid, det tager for en proces at fuldføre udførelsen. Dette kaldes også kørselstid.
• Ankomsttid: Det tidspunkt, hvor en proces går i klartilstand.
• Sluttid: Det tidspunkt, hvor en proces fuldføres og forlader systemet.
• Multiprogrammering: Et antal programmer, der kan være til stede i hukommelsen på samme tid.
• Jobs: En type program uden nogen form for brugerinteraktion.
• Bruger: En type program, der har brugerinteraktion.
• Proces: Den reference, der bruges til både et job og en bruger.
• CPU/IO burst cyklus: Karakteriserer procesudførelse, som veksler mellem CPU- og I/O-aktivitet. CPU-tider er normalt kortere end I/O-tider.

CPU-planlægningskriterier

En CPU-planlægningsalgoritme forsøger at maksimere og minimere følgende:

Maksimer

CPU-udnyttelse: CPU-udnyttelse er den primære opgave, hvor operativsystemet skal sørge for, at CPU'en forbliver så travl som muligt. Den kan variere fra 0 til 100 procent. For en RTOS kan den dog variere fra 40 procent for et lavniveausystem til 90 procent for et højniveausystem.

gennemløb: Antallet af processer, der afslutter deres udførelse pr. tidsenhed, kaldes gennemløb. Så når CPU'en er travlt optaget af at udføre en proces, udføres der arbejde, og det udførte arbejde pr. tidsenhed kaldes gennemløb.

Minimer

Ventetid: Ventetid er den tid, en specifik proces skal vente i klarkøen.

Responstid: Det er den tid, der går fra anmodningen blev indsendt, til det første svar er givet.

Vendetid: Udførelsestiden er den tid, det tager at udføre en specifik proces. Det er den samlede tid, der bruges på at vente på at blive indlæst i hukommelsen, vente i køen og udføre processen på CPU'en. Perioden mellem tidspunktet for processens afsendelse og færdiggørelsestidspunktet er udførelsestiden.

Intervaltimer

Timerafbrydelse er en metode, der er tæt forbundet med forkøbsret. Når en bestemt proces får CPU-allokeringen, kan en timer indstilles til et specificeret interval. Både timerafbrydelse og præemption tvinger en proces til at returnere CPU'en, før dens CPU-burst er færdig.

De fleste multiprogrammerede operativsystemer bruger en form for timer til at forhindre en proces i at binde systemet for evigt.

Hvad er Dispatcher?

Dispatcheren er et modul, der giver kontrol over CPU'en til processen. Dispatcheren skal være hurtig, så den kan køre på alle kontekstskift. Dispatch-latens er den tid, som CPU-scheduleren bruger til at stoppe en proces og starte en anden.

Funktioner udført af dispatcheren:

• Kontekstskift.
• Skifter til brugertilstand.
• Flytning til den korrekte placering i det nyligt indlæste program.

Typer af CPU-planlægning Algorithms

Der er hovedsageligt seks typer procesplanlægningsalgoritmer:

1. Først til mølle (FCFS)
2. Shortest-Job-First (SJF) planlægning
3. Korteste resterende tid
4. Prioritetsplanlægning
5. Runde Robin Planlægning
6. Køplanlægning på flere niveauer

Planlægning Algorithms

Først til mølle

FCFS står for Først til mølleDet er den nemmeste og enkleste CPU-planlægningsalgoritme. I denne type algoritme får den proces, der anmoder om CPU'en, CPU-allokeringen først. Denne planlægningsmetode kan styres med en FIFO-kø.

Når en proces går ind i klarkøen, er dens PCB (proceskontrolblok) forbundet med køens ende. Så når CPU'en bliver ledig, skal den tildeles processen i starten af ​​køen.

Karakteristika for FCFS-metoden

• Det er en ikke-præemptiv planlægningsalgoritme.
• Opgaver udføres altid efter først-til-mølle-princippet.
• Det er nemt at implementere og bruge.
• Denne metode er dog dårlig i ydeevne, og den generelle ventetid er ret høj.

Korteste resterende tid

Den fulde form for SRT er Shortest Remaining Time. Det er også kendt som SJF præemptive scheduling. I denne metode vil processen blive allokeret til den opgave, der er tættest på dens færdiggørelse. Denne metode forhindrer en nyere, klar-til-tilstand-proces i at forsinke færdiggørelsen af ​​en ældre proces.

Karakteristika for SRT-planlægningsmetoden

• Denne metode anvendes mest i batch-miljøer, hvor korte job skal foretrækkes.
• Dette er ikke en ideel metode at implementere i et delt system, hvor den nødvendige CPU-tid er ukendt.
• Hver proces er knyttet til længden af ​​dens næste CPU-burst, så operativsystemet bruger disse længder til at planlægge processen med den kortest mulige tid.

Prioritetsbaseret planlægning

Prioritetsplanlægning er en metode til at planlægge processer baseret på prioritet. I denne metode vælger planlæggeren de opgaver, der skal arbejdes på, i henhold til deres prioritet.

Prioritetsplanlægning hjælper også operativsystemet med at involvere prioritetstildelinger. Processer med højere prioritet udføres først, hvorimod job med samme prioritet udføres på en round-robin- eller FCFS-basis. Prioritet kan bestemmes baseret på hukommelseskrav, tidskrav og andre faktorer.

Round-Robin planlægning

Runde Robin er en af ​​de ældste og enkleste planlægningsalgoritmer. Navnet på denne algoritme stammer fra round-robin-princippet, hvor hver person får en lige stor andel af noget efter tur. Den bruges mest til planlægning i multitasking-systemer. Denne metode hjælper med at opnå en sultfri udførelse af processer.

Karakteristika for Round-Robin-planlægning

• Round robin er en hybridmodel, der er urdrevet.
• Den tidsinddeling, der er tildelt for en specifik opgave, bør være minimal. Den kan dog variere for forskellige processer.
• Det opfører sig som et tidsdelingssystem, der reagerer på hver proces inden for en bestemt tidsgrænse.

Korteste job først

SJF (Shortest Job First) er en planlægningsalgoritme, hvor processen med den korteste udførelsestid vælges til den næste udførelse. Denne planlægningsmetode kan være præemptiv eller ikke-præemptiv. Den reducerer den gennemsnitlige ventetid betydeligt for andre processer, der venter på udførelse.

Karakteristika for SJF-planlægning

• Hvert job er knyttet til en tidsenhed, der skal udføres.
• I denne metode udføres den næste proces eller det næste job med den korteste færdiggørelsestid først, når CPU'en er tilgængelig.
• Det implementeres med en ikke-præemptiv politik.
• Denne algoritme er nyttig til batchbehandling, hvor det ikke er kritisk at vente på, at job fuldføres.
• Det forbedrer joboutputtet ved at udføre kortere job først, som oftest har en kortere ekspeditionstid.

Planlægning af køer på flere niveauer

Denne algoritme opdeler klarkøen i flere separate køer. I denne metode tildeles processer til en kø baseret på en specifik egenskab ved processen, såsom procesprioritet, hukommelsesstørrelse osv.

Dette er dog ikke en uafhængig planlægningsalgoritme, da den skal bruge andre typer algoritmer for at planlægge jobbene.

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

• Der bør vedligeholdes flere køer for processer med fælles egenskaber.
• Hver kø kan have sin egen separate planlægningsalgoritme.
• Prioriteter tildeles til hver kø.

Formålet med en planlægningsalgoritme

Her er grundene til at bruge en planlægningsalgoritme:

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

Ofte Stillede Spørgsmål