CPU: Schedulering Flashcards
Hva er en ‘task’ i forhold til schedulering?
En ‘task’ er en skedulerbar entitet, noe som kan kjøre.
For eksempel en prossess/tråd som eksekverer en jobb, pakker gjennom kommunikasjons systemet eller en disk request gjennom filsystemet.
Hva gjør en scheduler?
En skeduler avgjør hvilken task/oppgave som får lov å bruke en ressurs.
Bestemmer rekkefølgen som forespørsler behandles etter ved å bruker en skedulerings algoritme.
Hva gjør en dispatcher?
En dispatcher ‘flytter’ den valgte prosessen (valgt av skeduleren) til CPU’en.
Hva vil det si at en prosess er CPU-bound eller I/O-bound?
En CPU-bound prosess har lange ‘CPU burst’, altså lange perioder for prosessen krever CPU kalkuleringen for å utføre oppgaven sin.
Hvis O beskriver CPU arbeid, og - beskriver vente på I/O:
OOOOO–OOOOO-OOOOO-OOOOO
En I/O-bound prosess har korte ‘CPU burst’, og har mer ventetid for I/O respons enn bruk av CPU.
O—-O—-OO—–O——OO
Hvilken skedulerings algoritmer kan benyttes for prosess skedulering?
First In First Out (FIFO) Round-Robin (RR) Shortest Job First Shortest Time To Completion First Shortest Remaining Time to Completion First Lottery Fair Queuing
Hvordan fungerer FIFO skedulerings algoritmen?
Som en vanlig FIFO kø, hvor det er første prosessen som kommer inn i køen som kommer ut og dermed får tilgang på CPU.
Hvilken fordeler og ulemper har FIFO skedulerings algoritmen?
Fordeler:
- Enkel, og derav enkel å implementere.
- Kan gi bra resultat for CPU-intensive jobber siden vi ikke får mye overhead fra context switching.
Ulemper:
- Lange gjennomsnittlige vente og finishing tider for prosesser.
Hvordan fungerer SJF skedulerings algoritmen?
Shortes Job First
Velger alltid den jobben som bruker kortest CPU tid for å bli ferdig.
Hvilken fordeler og ulemper har SJF skedulerings algoritmen?
Fordeler
- Enkel
- Har bedre gjennomsnittlige vente og finishing tider en FIFO.
Ulemper:
- Vanskelig å avgjøre prosessering behov, hvor lang tid en jobb tar.
- Potensielt stor finishing times og starvation.
Hvordan fungerer RR skedulerings algoritmen?
Round-Robin
Organisert i en FIFO kø, men hver prosess får kjøre en gitt tid, før det blir neste prosess sin tur å kjøre den samme gitte tiden.
- Hver prosess får 1/n av CPU i max t time units per runde.
- Den preempted’e prosessen blir plassert bakerst i køen.
Hvilken fordeler og ulemper har RR skedulerings algoritmen?
Fordeler:
- Fair
- Veldig god for interaktivitet
Ulemper:
- Kan bli mye overhead fra context switching om det er korte time slices.
Når vil det være fordelaktig å ha RR time slices på under 10ms eller over 100ms?
CPU-bound prosesser har fordel av å ha lengre time slices (>100ms), fordi de vil alltid bruke CPU og vi kan redusere antall context switcher som er kostbart.
I/O-bound prosesser har fordel av kortere time slices (<10ms), fordi de vil være kort CPU burst som trigger I/O operasjoner, og ved en kortere timeslice vil vi kunne starte flere I/O operasjoner og får en større utnyttelse av for eksempel disk.
Eksempel
- A og B kjører evig og bruker 100% CPU
- C looper evig (1ms CPU og 10ms disk)
- Time slice på 100ms
- Gir rundt 5% disk utilization med RR
- Time slice på 1ms:
- Gir rundt 91% disk utilization med RR
Hvilken mål har vi for skedulering?
Behandle lignende taks på samme måte. Ingen prosess bør vente evig. Korte respons tider. Maksimere throughput. Maksimere ressurs uttnyttelse. Minimere overhead. Forutsigbar tilgang.
- Merk at flere faktorer vil være motstridende.
I hvilken grupper kan vi klassifisere skedulerings algoritmer?
Dynamisk, statisk, preemptive, og non-preemptive.
Hva kjennetegner en dynamisk skedulerings algoritme?
Gjør skedulerings avgjørelser ved kjøretid.
Fleksibel å tilpasse.
Ser kun på den faktiske task requesten og eksekverings tid parametere.
Stor kjøretid overhead ved å finne en skedule.
