CPU-planlegging Algorithms in Operating systemer

Hva er CPU-planlegging?

CPU-planlegging er en prosess for å bestemme hvilken prosess som skal eie CPU-en for utførelse mens en annen prosess er satt på vent. Hovedoppgaven med CPU-planlegging er å sørge for at når CPU-en forblir inaktiv, velger operativsystemet minst én av prosessene som er tilgjengelige i klarkøen for utførelse. Utvelgelsesprosessen utføres av CPU-planleggeren, som velger én av prosessene i minnet som er klare for utførelse.

Typer CPU-planlegging

Her er to typer planleggingsmetoder:

Forebyggende planlegging

I preemptiv planlegging tildeles oppgavene stort sett med sine prioriteter. Noen ganger er det viktig å kjøre en oppgave med høyere prioritet før en annen oppgave med lavere prioritet, selv om oppgaven med lavere prioritet fortsatt kjører. Oppgaven med lavere prioritet venter en stund og gjenopptas når oppgaven med høyere prioritet fullfører utførelsen.

Ikke-forebyggende planlegging

I denne typen planleggingsmetode blir CPU-en allokert til en spesifikk prosess. Prosessen som holder CPU-en opptatt, frigjør CPU-en enten ved å bytte kontekst eller avslutte. Det er den eneste metoden som kan brukes på tvers av ulike maskinvareplattformer, fordi den ikke trenger spesiell maskinvare (for eksempel en timer) slik som preemptiv planlegging.

Når er planlegging forebyggende eller ikke-forebyggende?

For å avgjøre om planlegging er preemptiv eller ikke-preemptiv, bør du vurdere disse fire parameterne:

1. En prosess bytter fra kjørende til ventetilstand.
2. En spesifikk prosess bytter fra kjørende tilstand til klar tilstand.
3. En spesifikk prosess går fra ventetilstand til klartilstand.
4. En prosess fullfører utførelsen og avsluttes.

Hvis bare betingelse 1 og 4 gjelder, kalles planleggingen ikke-preemptiv. Alle andre planleggingssituasjoner er preemptive.

Viktige CPU-planleggingsterminologier

• Burst-tid/utførelsestid: Tiden en prosess trenger for å fullføre utførelsen. Dette kalles også kjøretid.
• Ankomsttid: Tidspunktet når en prosess går inn i klartilstand.
• Slutttid: Tidspunktet når en prosess fullføres og forlater systemet.
• Multiprogrammering: Et antall programmer som kan være tilstede i minnet samtidig.
• Arbeidsplasser: En type program uten noen form for brukerinteraksjon.
• Bruker: En type program som har brukerinteraksjon.
• Prosess: Referansen som brukes for både en jobb og en bruker.
• CPU/IO-burst-syklus: Karakteriserer prosessutførelse, som veksler mellom CPU- og I/O-aktivitet. CPU-tider er vanligvis kortere enn I/O-tider.

CPU-planleggingskriterier

En CPU-planleggingsalgoritme prøver å maksimere og minimere følgende:

Maksimer

CPU-bruk: CPU-utnyttelse er hovedoppgaven der operativsystemet må sørge for at CPU-en forblir så opptatt som mulig. Den kan variere fra 0 til 100 prosent. For en RTOS kan den imidlertid variere fra 40 prosent for et lavnivåsystem til 90 prosent for et høynivåsystem.

gjennomløp: Antall prosesser som fullfører utførelsen per tidsenhet kalles gjennomstrømning. Så når CPU-en er opptatt med å utføre en prosess, utføres det arbeid, og arbeidet som fullføres per tidsenhet kalles gjennomstrømning.

Minimer

Ventetid: Ventetid er hvor lenge en bestemt prosess må vente i klarkøen.

Responstid: Det er tiden det tar fra forespørselen ble sendt inn til det første svaret er gitt.

Vendingstid: Behandlingstid er tiden det tar å utføre en bestemt prosess. Det er den totale tiden det tar å vente på å komme inn i minnet, vente i køen og utføre på CPU-en. Perioden mellom tidspunktet for prosessinnsending og fullføringstidspunktet er behandlingstiden.

Intervalltimer

Timeravbrudd er en metode som er nært knyttet til forkjøpsrett. Når en bestemt prosess får CPU-allokeringen, kan en tidtaker settes til et spesifisert intervall. Både timeravbrudd og forhåndsavbrudd tvinger en prosess til å returnere CPU-en før CPU-utbruddet er fullført.

De fleste flerprogrammerte operativsystemer bruker en eller annen form for timer for å forhindre at en prosess binder opp systemet for alltid.

Hva er Dispatcher?

Dispatcheren er en modul som gir kontroll over CPU-en til prosessen. Dispatcheren bør være rask, slik at den kan kjøre på alle kontekstbrytere. Dispatch-latens er hvor lang tid CPU-planleggeren trenger for å stoppe én prosess og starte en annen.

Funksjoner utført av koordinatoren:

• Kontekstbytte.
• Bytter til brukermodus.
• Flytte til riktig plassering i det nylig lastede programmet.

Typer CPU-planlegging Algorithms

Det er hovedsakelig seks typer prosessplanleggingsalgoritmer:

1. Førstemann til mølla (FCFS)
2. Shortest-Job-First (SJF) planlegging
3. Korteste gjenværende tid
4. Prioritetsplanlegging
5. Round Robin-planlegging
6. Køplanlegging på flere nivåer

Planlegging Algorithms

Første mann til mølla

FCFS står for Første mann til møllaDet er den enkleste og enkleste CPU-planleggingsalgoritmen. I denne typen algoritme får prosessen som ber om CPU-en CPU-tildelingen først. Denne planleggingsmetoden kan administreres med en FIFO-kø.

Når en prosess går inn i klarkøen, kobles dens PCB (prosesskontrollblokk) til den ene siden av køen. Så når CPU-en blir ledig, bør den tilordnes prosessen i begynnelsen av køen.

Kjennetegn ved FCFS-metoden

• Det er en ikke-preemptiv planleggingsalgoritme.
• Jobbene utføres alltid etter førstemann-til-mølla-prinsippet.
• Det er enkelt å implementere og bruke.
• Denne metoden har imidlertid dårlig ytelse, og den generelle ventetiden er ganske høy.

Korteste gjenværende tid

Den fulle formen for SRT er Shortest Remaining Time. Det er også kjent som SJF preemptive scheduling. I denne metoden vil prosessen bli tildelt oppgaven som er nærmest fullføring. Denne metoden forhindrer at en nyere ferdigprosess forsinker fullføringen av en eldre prosess.

Kjennetegn ved SRT-planleggingsmetoden

• Denne metoden brukes hovedsakelig i batch-miljøer der korte jobber må prioriteres.
• Dette er ikke en ideell metode å implementere i et delt system der den nødvendige CPU-tiden er ukjent.
• Hver prosess er knyttet til lengden på sin neste CPU-utbrudd, så operativsystemet bruker disse lengdene for å planlegge prosessen med kortest mulig tid.

Prioritetsbasert planlegging

Prioritetsplanlegging er en metode for å planlegge prosesser basert på prioritet. I denne metoden velger planleggeren oppgavene som skal arbeides med i henhold til prioriteten deres.

Prioritetsplanlegging hjelper også operativsystemet med å involvere prioritetstildelinger. Prosessene med høyere prioritet utføres først, mens jobber med lik prioritet utføres på en round-robin- eller FCFS-basis. Prioritet kan bestemmes basert på minnekrav, tidskrav og andre faktorer.

Round-Robin-planlegging

Rund robin er en av de eldste og enkleste planleggingsalgoritmene. Navnet på denne algoritmen kommer fra round-robin-prinsippet, der hver person får en lik andel av noe etter tur. Den brukes mest til planlegging i multitasking-systemer. Denne metoden bidrar til å oppnå sultfri utførelse av prosesser.

Kjennetegn ved Round-Robin-planlegging

• Round robin er en hybridmodell som er klokkedrevet.
• Tidsintervallet som er tildelt for en spesifikk oppgave som skal behandles, bør være minimalt. Det kan imidlertid variere for ulike prosesser.
• Det oppfører seg som et tidsdelingssystem som reagerer på hver prosess innenfor en bestemt tidsfrist.

Korteste jobb først

SJF (Shortest Job First) er en planleggingsalgoritme der prosessen med kortest utførelsestid velges for neste utførelse. Denne planleggingsmetoden kan være preemptiv eller ikke-preemptiv. Den reduserer den gjennomsnittlige ventetiden betydelig for andre prosesser som venter på utførelse.

Kjennetegn ved SJF-planlegging

• Hver jobb er knyttet til en tidsenhet som skal fullføres.
• I denne metoden, når CPU-en er tilgjengelig, utføres den neste prosessen eller jobben med kortest fullføringstid først.
• Den implementeres med en ikke-preemptiv policy.
• Denne algoritmen er nyttig for batchbehandling, der det ikke er kritisk å vente på at jobber skal fullføres.
• Det forbedrer jobbutbyttet ved å utføre kortere jobber først, som vanligvis har kortere behandlingstid.

Planlegging av køer på flere nivåer

Denne algoritmen deler klarkøen inn i flere separate køer. I denne metoden tilordnes prosesser til en kø basert på en spesifikk egenskap ved prosessen, for eksempel prosessprioritet, minnestørrelse og så videre.

Dette er imidlertid ikke en uavhengig planleggingsalgoritme, ettersom den må bruke andre typer algoritmer for å planlegge jobbene.

Kjennetegn ved planlegging av køer på flere nivåer

• Flere køer bør vedlikeholdes for prosesser med delte egenskaper.
• Hver kø kan ha sin egen separate planleggingsalgoritme.
• Prioriteter tildeles hver kø.

Formålet med en planleggingsalgoritme

Her er grunnene til å bruke en planleggingsalgoritme:

• CPU-en bruker planlegging for å forbedre effektiviteten.
• Det hjelper deg med å fordele ressurser mellom konkurrerende prosesser.
• Maksimal utnyttelse av CPU-en kan oppnås med multiprogrammering.
• Prosessene som skal utføres, holdes i klarkøen.

Spørsmål og svar