Skeduleringsalgoritmer

Formålet med skedulering
Operativsystemer kan bruke forskjellige teknikker for å skedulere en mengde arbeidsoppgaver i form av tråder og prosesser,  med en begrenset mengde ressurser (CPU).
Du har en PC med en Intel i7 prosessor (CPU) og kan velge mellom en rekke forskjellige operativsystemer som bruker forskjellige skeduleringsalgoritmer. Hvilken skeduleringsalgoritmer er best?. Det avhenger først og fremst av formålet med bruken. For eksempel en server kan ha et annet krav til ytelse enn en bærbar PC. I de fleste tilfeller er det ønskelig at CPU utnyttes på best mulig måte. CPU bør derfor til en hver tid ha tilgang på nok arbeidsmengde i form av prosesser og tråder for å være så effektivt som mulig. Dette konseptet kalles multiprogrammering siden operativsystemet kjører mer enn en prosess om gangen.
Long Term Scheduler er ansvarlig for å velge ut antall prosesser fra en kø av programmer som ligger lagret i sekundærminnet. Disse programmene ønskes lastet inn i primærminnet, slik at programmene blir til prosesser og blir plassert i “Ready”-køen som overvåkes av Short Term Scheduler.
Short Term Scheduler er ansvarlig for å ta en avgjørelse for hvilke prosess som skal få lov til å kjøre for holde CPU mest mulig opptatt. Short Term Scheduler velger ut en prosess fra “Ready”-køen og laster den videre inn i CPU registrene. Når folk snakker om “CPU Scheduler” refererer de gjerne til Short Term Scheduler.
CPU er avhengig av Short Term Scheduler som igjen er avhengig av Long Term Scheduler.
Skeduleringsalgoritmer deles inn i to kategorier: Non-preemptive og Preemptive. Non-preemptive er når Short Term Scheduler ikke har lov til å røre prosessen som kjører før den er helt ferdig, eller prosessen selv frivillig gir fra seg CPU. Preemptive er når Short Term Scheduler kan gå inn å stoppe prosessen, ta den ut fra CPU og velge en ny prosess som skal få lov til å kjøre i CPU.
Følgende kriterier er ofte brukt for å sammenligne skeduleringsalgoritmer:

  • CPU Utilization: Antall prosent av tiden CPU er opptatt
  • Throughput: Antall prosesser som fullføres for hver tidsenhet
  • Turnaround time: Tiden (inkludert ventetid) fra en prosess opprettes til den termineres – hvordan lang tid prosessen oppholder seg i systemet
  • Waiting time: Den totale tiden hvor prosessen må vente i “Ready”-køen
  • Response time: Tiden fra en prosess starter å kjøre til den krever input eller gir output (I/O)

Det er gjerne ønskelig å optimalisere disse mest mulig, men det er urealistisk. Ønsker man å forbedre et av kriteriene, så kan det gå på bekostning av et annet kriterie. Det som er viktigst er at man velger ut de kriteriene som vi ønsker skedulereren skal være god på.
FCFS (First-Come-First-Served) / FIFO (First-In First-Out)

  • Veldig enkel skedulseringsalgoritme
  • Short Term Scheduler utfører arbeid i den rekkefølgen som prosessene kommer inn
  • En non-preemptive algoritme (prosessen får kjøre til den er ferdig)
  • Prosesser som krever kort tid fra CPU, kan ende opp med å stå i kø å vente på andre
    – CPU-bundet prosesser kan ende opp med å tvinge I/O-bundet prosesser til å vente. Stor sannsynlighet for høy ventetid blant prosessene

Round Robin

  • Ulike varianter at Round Robin er det som brukes i de fleste flerbruker-operativsystemer
  • Deler CPU rettferdig mellom prosesser
  • Round Robin er preemptive (Short Term Scheduler kan ta tilbake kontrollen over CPU)
  • Bruker en klokke (timer) for å forårsake avbrudd (interrupts). Waiting time kontrolleres av time slice. Hvis for stor time slice så blir prosesser stående å vente slik som med FCFS. Hvis for liten time slice, så ender man oppe med for mye kontekstskifte. Finn en balanse.
  • Etter tråden har kjørt sin tidsskive (time slice) flytt tråden bakerst i køen, og fortsette med neste tråd

 
 
 

Leave a Comment