CPU-administrasjon

Fra IT2
Hopp til: navigasjon, søk
Illustrasjonsfoto

Resymé Cpu-en er den mest sentrale av alle ressursene i datamaskinen. Alle prosesser må ha cpu-tid for å få gjort ting. Dette temaet tar opp hvordan cpu-administrasjon foregår og hvordan man kan administrere cpu-en forskjellig alt etter hva man ønsker å oppnå.

Cpu-en er i en særstilling når det gjelder ressursene i datamaskinen da alle prosessene har bruk for cpu for å kunne kjøre. Måten cpu-en administreres på er derfor avgjørende for effektiviteten til maskinen.

Cpu-administrasjon kalles ofte for scheduling . På norsk vil en ofte bruke et uttrykk som å sette opp en kjøreplan eller fordelingsmetode. Operativsystemet vil alltid ha en eller annen framgangsmåte (også kalt policy) for hvordan prosessene skal administreres slik at prosessene får en rettferdig fordeling av cpu, samtidig som effektiviteten på systemet som helhet blir god.

Mekanismer for scheduling

Med flere prosesser i minnet samtidig vil den totale ytelsen til datamskinsystemet øke. Prosessene må da stilles i en kø for bruk av cpu-en. Denne køen kalles cpu-køen, og må administreres på en fornuftig og effektiv måte. Vi sier også at prosesser som står i cpu-køen er i klar -tilstand. Prosessene må også utføre i/o, og etter at i/o-operasjonen er ferdig kommer de tilbake til cpu-køen

Det er scheduleren som administrerer denne cpu-køen på grunnlag av diverse kriterier som er satt opp for systemet. Det kan f. eks være kriterier for kortest mulig responstid, mest mulig effektiv gjennomstrømning etc.

Virkemåten til scheduler

Scheduler1.PNG

Det er scheduleren som er ansvarlig for, via cpu-køen, å fordele cpu-tid til prosessene. Scheduleren plukker ut neste prosess som skal få kjøre på cpu-en. Det er den valgte scheduling policy som avgjør når det er på tide å fjerne kjørende prosess fra cpu-en og velge ut neste prosess som skal få kjøre. Schedulerens virkemåte forteller oss hvordan selve skiftet av prosess foregår, dvs. hvordan en prosessallokeres og deallokeres til cpu-en.

Når en prosess endrer tilstand til klar-tilstand, dvs. den er klar for cpu, havner den i cpu-køen (slik som vist på figur under). Cpu-køen er en enkel datastruktur som inneholder minneadresser som peker til prosessdeskriptoren for hver prosess som er i kø. Denne køen kan være organisert som en ren ”først til mølla” – kø eller scheduleren kan beregne prioriteter til hver enkelt prosess som står i køen, og dermed gi cpu-en til den prosessen som til enhver tid har høyest prioritet.

Figuren nedenfor viser også at scheduleren består av en cpu-kø pluss en dispatcher og en context sxitcher. Begge disse to siste vil bli nærmere forklart nedenfor.

Dispatcheren (eng. for ekspedere, kjøre ut…) velger ut neste prosess som skal kjøre på cpu-en. Neste prosess kan f. eks være første prosess i køen (p3 vist nedenfor), eller det kan være en annen prosess i køen plukket ut på grunnlag av prioritet. Dispatcheren har tilgang til prosessdeskriptor for å lese f. eks prioritetsverdier.

Context switcher har som oppgave å bytte til den prosessen som skal få lov til å kjøre på cpu-en. Det er dispatcheren som velger ut prosess, og det er context swicher som står for selve skriftet. Det gjør den ved å flytte data for kjørende prosess fra cpu til prosessdeskriptore, og motsatt for den nye prosessen som skal kjøre, dvs fra prosessdeskriptor til cpu.

Figuren nedenfor viser en oversikt over hvordan cpu-administrasjonen foregår. Nye prosesser kommer inn i cpu-køen fra venstre. Scheduler administrerer selve cpu-køen, plukker ut neste prosess, skifter ut prosess som skal bruke cpu slik som vist i fuguren ovenfor.

Scheduler2.PNG

Prosesser blir ferdige på cpu av forskjellige årsaker:

  • Prosessen er ferdig.
  • Prosessen ber om en ressurs, f. eks utføre i/o eller aksessere felles dataområde.
  • Prosessen blir fratatt cpu-en fordi tidkvantet utløper eller den gir fra seg cpu frivillig.

Prosesskiftet

Når prosesser skifter på å bruke cpu-en skjer det som kalles kontekst-skifter. Det foregår kopiering av data mellom prosessdeskriptor og cpu når ny prosess skal inn på cpu-en. Ved hvert skifte er det snakk om til sammen fire slike kopieringsoperasjoner kalt kontekstskifter.

Først er det to kopieringer for bytte av prosess som skal kjøre på cpu-en, dvs. flytte data mellom cpu og prosessdeskriptor for prosess som stoppes og for prosess som nå skal kjøre.

Men i tillegg til dette er det også snakk om to kopieringer fordi scheduler må kjøre på cpu-en for å utføre selve kontekstskiftet til brukerprosessene. Det betyr følgende kontekstskifter:

  • Når kjørende prosess er ferdig lagres data om denne prosessen unna i prosessdeskriptor.
  • Scheduler gjøres til kjørende prosess for å velge ut neste prosess som skal kjøre på cpu-en. Prosessdesktiptor til scheduler må derfor hentes fram.
  • Når scheduler er ferdig med oppgaven sin flyttes data fra cpu-registrene til schedulers prosessdeskriptor.
  • Data fra prosessdeskriptor til ny prosess flyttes over til cpu, og denne prosessen gjøres til kjørende.

Som du ser, er det forbundet en viss kostnad med å skifte mellom prosesser som skal kjøre på cpu-en. Det å kjøre flere prosesser ”samtidig” krever altså en del administrasjon da mange av cpu-syklusene går med til å skifte mellom prosessene. Det er derfor viktig å velge metoder og systemer for administrasjon av cpu som gjør denne kostnaden lavest mulig, og dermed få flest mulig cpu-sykluser til kjøring av brukerprosesser.

Scheduling-strategi

Administrasjon av cpu-køen stiller oss overfor flere forskjellige valg med hensyn på hvordan neste prosess skal velges ut. Skal den velges ut på grunnlag av ”først til mølla” – prinsippet ? Skal den velges ut på grunnlag av prioriteter gitt på grunnlag av hvem som eier prosessen? , eller på grunnlag av hvor mye cpu-tid den allerede har fått?

Hvilke strategier som skal velges avhenger av hva slags operativsystem det er snakk om. Dersom det er et sanntids operativsystem av typen styre et fly eller et atomkraftverk, må prosessene velges ut fra helt spesifikk tidskrav. Prosessene i et slikt system må tildeles prioriteter ut fra viktighet, og dermed velger scheduler prosess ut fra prioritet.

I et tidsdelt system med flere innloggede interaktive brukere, er kravene noe annerledes. Da er det snakk om å tildele cpu-tid mest mulig likt til prosessene, eventuelt tildele på grunnlag av kortest mulig responstid.

Ved sammenligning av metoder for cpu-scheduling er følgende begreper viktige:

  • Total cpu-tid: Dette er total cpu-tid som prosessen trenger for å fullføre oppgaven sin. Her regner vi altså ikke med ventetid for i/o og lignende. Kun den tida prosessen benytter cpu-en.
  • Ventetid: Dette er den tiden prosessen står i cpu-køen og venter før den får cpu-en for første gang. Ventetida kalles for responstida.
  • Omløpstid: Tida fra prosessen entrer cpu-køen første gang til den forlater cpu-en og er ferdig.
  • Gjennomstrømning: Dette er antall prosesser som kommer igjennom systemet i en gitt tidsperiode.


Tidskvant

Med flere prosesser som kjører på cpu-en samtidig er det vanlig å tildele cpu-tid etter en fast størrelse angitt av det som kalles et tidskvant. Det betyr at ingen prosess kan ta over hele cpu-en, og dermed få monopol på cpu-en. En prosess som kjører på cpu-en vil alltid miste CPU-en når tidskvantet utløper, hvis den ikke allerede har mistet den tidligere på grunn av ankomne prosesser med høyere prioritet eller at prosessen sjøl har bedt om en i/o- operasjon.


Preemptive og ikke-preemptive cpu-administrasjon

Metodene for scheduling deles i to forskjellige hovedgrupper. Det er ikke-preemptive og preemptive metoder (preemptive = ta i fra, forkjøpsrett og lignende). Ikke-preemptiv betyr at prosessen som entrer kjørende tilstand ikke avgir cpu-en før den er ferdig, dvs. har ikke brukt hele sin cpu-tid, eller at den frivillig gir fra seg cpu-en. Preemptiv betyr at operativsystemet kan gripe inn og skifte prosess. Dette skiftet kan skje til en prosess med høyere prioritet eller til neste prosess i køen fordi tidskvantet utløper.


Skifte av prosesser og avbrudd

En prosess som får cpu-en kan beholde den inntil en prosess med høyere prioritet ankommer (avhenger av valgte scheduling - metode), til prosessen eventuelt utfører i/o eller til tidskvantet utløper.

I løpet av den tiden prosessen bruker cpu-en vil det også komme avbrudd fra bl.a. i/o- enheter. Dette er avbrudd som operativsystemet må håndtere der og da. Det blir kjørt en avbruddsrutine for å behandle avbruddet. Dette tar ganske kort tid, og cpu-en gis tilbake til avbrutt prosess når avbruddet er ferdig behandlet.

Figuren nedenfor viser hvordan dette tar seg ut langs en tidslinje der prosessene P1, P2 og P3 kjører på cpu-en, og blir avbrutt av flere slike korte hendelser fra for eksempel. i/o- enheter.

SkifteAvProsesserOgAvbrudd.PNG

Merk at disse korte avbruddene er raske å behandle, og forsinker derfor ikke prosessen nevneverdig. Svært ofte ser en at cpu-en har flere sett med cpu-registre slik at det ikke er nødvendig å skifte ut innholdet på cpu-en for å behandle avbruddet. Det er nok å bare skifte til et annet sett av cpu-registre.

First-come-first-served (FCFS)

Med denne metoden får prosessene cpu-en i samme rekkefølge som de ankommer cpu-køen. hva kommer først er behandlet først, neste venter til den første er ferdig , osv. .

Det er derfor analogt med oppførselen til personer som står i kø, hvor personer forlater køen i den rekkefølgen de kommer, eller venter en tur på en trafikk-kontroll.

Shortest job next (SJN)

Denne metoden forutsetter at kjøretiden er kjent på forhånd. Det er f. eks tilfelle når det kjøres såkalt satsvise kjøringer hver natt i forsikringsselskaper, banker og lignende. Alle jobbene er da lagt inn i en kø, og kjøringen starter på et gitt tidspunkt.

Shortest job next ( SJN ) (også kjent som Shortest job first (SJF) eller Shortest Process Next (SPN)) er en planleggings politikk som velger å vente Prosessen med den minste kjørings-tid til å utføre neste.

SJN en fordel på grunn av sin enkelhet og fordi den maksimerer prosessens gjennomstrømning (i forhold til antallet prosesser som kjører til ferdigstillelse i en gitt tidsperiode). Det reduserer også den gjennomsnittlige mengden tid hver prosess må vente til sin kjøring er fullført. Det har imidlertid potensialet for å "sulte" prosessen for prosesser som vil kreve lang tid å fullføre dersom korte prosesser er stadig lagt til.

Korteste jobb neste planlegging blir sjelden brukt utenfor spesialiserte miljøer fordi det krever nøyaktige beregninger av kjøretid i alle prosesser som venter på å utføre.

Prioritet

Denne metoden baserer seg på prioriteter som er gitt til hver prosess. Prioriteten kan være av ekstern og intern art. Ekstern prioritet kan være gitt ut fra type personell som eier prosessen, f. eks student eller ansatt, eller den kan være gitt ut fra hvor mye man betaler for bruken av datamaskinsystemet. Intern prioritet kan beregnes ut fra hvor mye ressurser den legger beslag på til enhver tid.

En ulempe med denne metoden er at prosesser med lav prioritet kan risikere å ikke få tilstrekkelig med cpu-tid, og derfor lide den som kalles starvation. For å unngå starvation kan en sakte øke prioriteten til gamle prosesser, slik at de har en mulighet for å bli ferdige innen endelig tid.

Preemptiv cpu-scheduling

Med preemptiv scheduling kan kjørende prosess bli avbrutt og ny prosess allokert til cpu-en. Hver gang en ny prosess ankommer cpu-køen vil scheduleren bli aktivisert for å se om dette er en prosess med høyere prioritet. Hvis det er tilfellet blir kjørende prosess fjernet fra cpu-en (dvs. tilbake til cpu-kø), og den nettopp ankomne prosessen får cpu-en.

Det er dette som er preemptiv scheduling. Kjørende prosess mister cpu-en. Og cpu overlates til neste prosess som har høyere prioritet.

Scheduler blir også startet hver gang tidskvantet utløper. Da blir kjørende prosess fjernet fra cpu og lagt bakerst i cpu-kø, mens neste prosess i cpu-køen får kjøre på cpu-en.

Preemptive teknikker sikrer rask responstid for prosesser med høy prioritet, og den gir en god og rettferdig fordeling av cpu-tiden mellom prosessene.

Ulempen

Vi har tidligere sett på kostnader forbundet med hvert kontekstskifte. For hvert slikt skifte går det med et antall cpu-sykluser for å kjøre scheduler. Ved ikke-preemptiv scheduling er denne kostnaden vanligvis lav grunnet få kontekstskifter, men for preemptiv scheduling kan denne kostnaden bli betydelig grunnet mange kontekstskifter. Dette er spesielt aktuelt dersom tidskvantet er relativt lite, og/eller det er mange interaktive prosesser i systemet, dvs. prosesser som bruker lite cpu-tid mellom hver gang du utfører i/o.

Round-robin

Er den vanligste metoden for å tildele cpu-tid til prosesser. Med denne metoden tildeles cpu-tiden likt mellom alle prosessene som befinner seg i systemet. Hver prosess tildeles et gitt tidsintervall kalt tidskvant, som den får lov til å bruke cpu-en. Når et tidskvant utløper er den neste prosess i prosesskøen sin tur og kjørende prosess legges dermed bakerst i cpu-køen. Dersom prosessen blir ferdig før tidskvantet utløper, f.eks. fordi prosessen skal utføre i/o, slipper neste prosess til cpu-en med en gang. Tidskvantet ved bruk av Round robin må ses i relasjon til den tiden det tar for et kontektsskifte. Avhengig av tidskvantet vil prosesskifter forekomme ofte ved et lavt tidskvant. Ved lavt tidskvant vil en stor del av prosentandel av tida gå med til ren administrasjon av prosessene ved at det må foretas hyppige skifter av prosesser. Ulempen med små tidskvant er dårlig utnyttelse av cpu til å gjøre nyttig arbeid, mesteparten av tida går med til administrasjon. Fordelen med lavt tidskvant er raskresponstid fordi prosessene skiftes raskt ut og prosessene vil komme raskt til cpu-en. Ved økt tidskvant vil kontekstskifter forekomme sjeldnere, og større del av tiden brukes til nyttig arbeid, dvs å kjøre brukeprosesser. Større tidskvant vil gå ut over responstiden, fordi hver prosess nå kan holde på cpu-en i en lengre periode.

Konklusjon blir da at for lite tidskvant gir for mange kontekstskifter og dermed lav cpu-utnyttelse, mens for stor tidskvant bedrer cpu-utnyttelesen, men gir lengre responstid. Verdier for et typisk tidskvant er rundt 10 - 50 millisekunder.


Flere-nivå cpu-køer

Prosesser deles inn i forskjellige klasser alt etter hva slags type prosesser det er. Det finnes nemlig forskjellige typer prosesser alt etter hvor ofte det har bruk for cpu-en og hvor lang totalttid det er snakk om. Det finnes alt etter hvor ofte de har bruk for cu-en og hvor lang totalttid det er snakk om. Det finnes i/o bundne prosesser som bruker cpu-en i korte øyblikk mellom hver gang det trenger å utføre i/o-operasjoner. Dette er typisk interaktive prosesser der brukeren jobber mot prosessen hele tidem, f.eks. regneark, tekstbehandlere, databaser osv. På den andre siden finnes de såkalte cpu-bundne prosessene. Disse bruker cpu-en så lenge når de først har fått den, og har sjelden behov for å utføre i/o-operasjoner. Som oftest er dette gjirt helt i starten av kjøringen. Det finnes mange prosesser som befinner seg i en mellomstilling mellom i/o-bundne og cpu-bundne. Prosesser som starter som i/o-bundne kan gå over til å bli cpu-bundne etter en tid, og omvendt. Med flere -nivå-cpu-køer er dette mulig. Figuren viser en slik fler-nivå- cpu-kø.


Øverst finner du prosesser med høyest prioritet og minst størrelse på tidskvant. Lenger ned finner du køer med lavere priorite og større tidskvant. Poenget her er at en kan gi høy prioritet til prosesser som "gir et løfte" om at de skal bruke cpu-en i et lite tidskvant.

En ny prosess som kommer inn i systemet starter alltid på høyeste prioritet (dvs på prioritet 4 i figuren ovenfor). Dersom den bruker opp tidskvant sitt faller den et hakk ned på prioritet 3. Slik fortsetter det, hver gang den bruker opp tidskvantet faller den ett hakk ned, og vil til slutt havne på laveste nivå. Prosesser med dette forløpet er såkalte cpu-bundne prosesser som trenger mye cpu-tid, og dermed trives best med lange tidskvant. Dersom denne prosessen forsatt bruker mye cpu-tid, og dermed trives best med lange tidskvant. Dersom denne prosessen fortsatt bruker mye cpu-tid vil den befinne seg på laveste nivå og kjøre Round-Robin med andre prosesser som befinner seg på dette nivået. Dersom prosessen på et av nivåene ikke bruker opp tidskvantet sitt, vil den blitt værende på dette nivået, og ville kunne avansere oppover igjen i prioritets nivå dersom den fortsette å bruke lite cpu-tid. Lite cpu-tid bruker prosessen når den ofte gjør kall til i/o-opersajoner før tidskvantet utløper. Dvs det er en interaktiv prosess, f.eks. når brukeren skriver inn teksten i en tekstbehandler. Dersom prosessen som ankommer er en typisk i/o-bundnet prosess med hyppige i/o-operasjoner og lite prosesseringstid hver gang den får cpu-en, vil prosessen bli værenede i køen med høy prioritet. I/o-bundne prosesser befinner seg i køen med høyest prioritet og cpu-bundne prosesser befinner seg i køen med lavest prioritet. Dette er en fornuftig fordeling da i/o-bundne prosesser er inaktive prosesser der brukeren sitter forann tastaturet og gir inn data. Med høy prioritet får disse prosessene kort responstid, og dermed fornøyde brukere. Cpu-bundne prosesser derimot er cpu-intensive prosesser som krever lang prosesseringistid. Typiske prosesser av denne kategorien er simulering av forskjellige slag, f.eks. simulere værsituasjoner, simulering av belastninger på fly ved landing osv. Brukere av disse prosessene forventer ikke kort responstid, og siden de trenger mye cpu-tid er det fornuftig med lange tidskvant på disse for best mulig utnyttelse av cpu-en. Kan fler-nivå cpu-køer bety at det kun prosesser på de øverste prioritets nivåene som får kjørt på cpu-en, og de på lavere nivåer får aldri kjørt ("starvation")? Nei, det skjer ikke, fordi prosessene på øverste nivå trenger cpu-en bare i korte øyeblikk før den igjen utfører kall til i/o-operasjoner. De bruker ikke opp tidskvantene. Dette er typiske kjennetegn ved i/o-bundne prosesser. Derfor vil de øverste køene som oftest stå tomme, og dermed får også prosesser i de laveste køene kjørt. Men så snart det ankommer en prosess med høyere prioritet vil den straks få cpu-en.

Kilder

  • Kompendium i Operativsystemer av Geir Maribu
  • eng.Wikipedia.org
  • no.wikipedia.org