Title: Besturingssystemen / hoofdstuk 5

Naam: preemptive schedulng
Wat is/doet het?: scheduling policy
Hoe werkt het?: proces wordt van de CPU afgehaald terwijl het nog CPU nodig heeft
Waar gebruikt?: scheduling
Wanneer gebruikt?: bij interrupts of eindigen van IO van een ander proces
Voordelen: meer processen kunnen de CPU krijgen per tijdseenheid
Nadelen: mogelijk onderbroken tijdens uitvoeren van kritieke sectie
Alternatieven: nonpreemtive = cooperative scheduling
Pagina: 204

Naam: dispatcher
Wat is/doet het?: voer beslissingen van scheduler uit
Hoe werkt het?: context switch maken
wisselen van kernel naar user mode
programateller juist zetten
Waar gebruikt?: scheduling
Wanneer gebruikt?: als een proces de CPU krijgt
Nadelen: dispatch latency: tijd om proces in uitvoering te brengen
Pagina: 205

Naam: criteria voor bepalen v.e. process scheduling algoritme
Welke types zijn er?: - hoeveelheid CPU-gebruik
- throughput: # afgewerkte processen per tijdseenheid
- turnaround time: tijd om proces te beeindigen
- waiting time: hoeveelheid tijd doorgebracht in de READY queue
- response time
Pagina: 205

Naam: FCFS (process scheduling)
Wat is/doet het?: processen in queue plaatsen
Hoe werkt het?: FIFO
Waar gebruikt?: scheduler
Wanneer gebruikt?: bij fork/preemption/io completion/...
Voordelen: simpele implementatie
Nadelen: lange gem. wachttijd
convoy effect als langste vooran in queue staat
Alternatieven: SJF, RR, priority, multilevel (feedback)
Pagina: 206

Naam: SJF
Wat is/doet het?: processen in ready queue plaatsen
Hoe werkt het?: korste proces eerst
lengte van CPU burst wordt heuristisch bepaald op basis van vorige tijd en vorige geschatte tijd
Welke types zijn er?: - afhankeljk van parameter [$]\alpha[/$]
- preemptive/nonpreemtive
- preemtive zal bij aankomen van nieuw proces kijken of dit korter is dan het uitvoerende. zo ja, dan wordt het huidig uitvoerende onderbroken
Waar gebruikt?: scheduler
Wanneer gebruikt?: bij fork/preemtion/io completion/...
Voordelen: optimale wachttijd
Nadelen: schatting niet altijd correct
Alternatieven: FCFS, RR, priority, multilevel (feedback)
Pagina: 207
Figuur: 5.3

Naam: Priority process scheduling
Wat is/doet het?: processen in queue plaatsen
Hoe werkt het?: scheduling op basis van prioriteit
Waar gebruikt?: scheduler
Wanneer gebruikt?: bij fork/preemtion/io completion/...
Voordelen: aging
Nadelen: starvation bij slechte implementatie
Alternatieven: FCFS, SJF, RR, multilevel (feedback)
Pagina: 210

Naam: Round Robin
Wat is/doet het?: processen in queue plaatsen
Hoe werkt het?: FCFS met time quantum
Welke types zijn er?: lengte van quantum kan varieren
Waar gebruikt?: scheduler
Wanneer gebruikt?: bij fork/preemption/io completion/...
Voordelen: responstijd, geen starvation of lange wachttijden
Nadelen: meer context switches
Alternatieven: FCFS, SJF, priority, multilevel (feedback)
Pagina: 211
Figuur: 5.4, 5.5

Naam: multilevel queue scheduling
Wat is/doet het?: processen schedulen
Hoe werkt het?: elk type proces (system, batch, interactive, ...) heeft een eigen queue, die volgens een bepaalde queuediscipline beheerd wordt
Welke types zijn er?: afhankelijk van hoe queues ingedeeld worden
Waar gebruikt?: scheduling
Wanneer gebruikt?: bij fork/preemption/io completion/...
Voordelen: modulair, niet alles hetzelfde
Nadelen: starvation als een belangrijkere queue nooit leeg is
Alternatieven: FCFS, SJF, RR, priority, multilevel feedback
Pagina: 213
Figuur: 5.6

Naam: multilevel feedback queue
Wat is/doet het?: scheduling
Hoe werkt het?: meerdere queues, waarbij processen die na een bepaald quantum niet af geraken naar een volgende queue migreren
Welke types zijn er?: afhankelijk van welke queues gemaakt worden, wat de sequentie van queues is, ...
Wanneer gebruikt?: bij fork/preemption/io completion/...
Voordelen: divers, veelzijdig, algemeen
Nadelen: complex
Alternatieven: starvation bij processen die te lang duren en dus naar latere queues migreren
Pagina: 215
Figuur: 5.7

Naam: contention scope
Wat is/doet het?: competitie tussen threads om gescheduled te worden
Welke types zijn er?: process contention scope (PCS): thread library schedulet threads op een LWP
system contention scope (SCS): kernel schedulet kernel threads om uitgevoerd te worden
Waar gebruikt?: thread library / scheduling door kernel
Alternatieven: afhankelijk van implementatie (1TM, MTM, MT1) is gebeurt meer PCS of SCS
Pagina: 217

Naam: Assymmetric multiprocessing
Wat is/doet het?: processor scheduling
Hoe werkt het?: alle kerneltaken gaan naar 1 processor (incl scheduling van andere CPUs)
Waar gebruikt?: multi-CPU scheduling
Wanneer gebruikt?: continu
Voordelen: minder data die gedeeld moeten worden
geen conflicten bij scheduling (race conditions)
Nadelen: minder load sharing
Alternatieven: symmetric multiprocessing
Pagina: 218

Naam: symmetric multiprocessing
Wat is/doet het?: processor scheduling
Hoe werkt het?: elke processor schedulet zichzelf en kan kerneltaken uitvoeren
Welke types zijn er?: meestal heeft elke CPU een eigen queue maar dit is niet altijd nodig
Waar gebruikt?: multi-CPU scheduling bij NT, Darwin, Linux, ...
Wanneer gebruikt?: continu
Voordelen: load sharing
Nadelen: delen van kernel datastructuren
conflicten bij scheduling (race conditions)
Alternatieven: assymmetric multiprocessing
Pagina: 218

Naam: processor-affiniteit
Wat is/doet het?: neiging van proces om door specifieke CPU uitgevoerd te worden omwille van opgeslagen cache of NUMA
Welke types zijn er?: soft affinity: proberen affiniteit respecteren
hard aff'ty: garantie
Waar gebruikt?: CPU scheduling
Wanneer gebruikt?: scheduling v.e. proces
Voordelen: performance
Nadelen: soms veel meer affiniteit bij de ene dan bij de andere, dan heeft deze meer werk
Alternatieven: affinity wel of niet garanderen
Pagina: 220
Figuur: 5.9

Naam: load balancing
Wat is/doet het?: CPUs bezig houden
Hoe werkt het?: jobs worden bij idle CPU gescheduled om load te balanceren
Welke types zijn er?: push migration: regelmatig kijken naar welke CPU het druk heeft, dan taken doorgeven
pull migration: CPU kijkt zelf of deze een andere CPU kan helpen
Waar gebruikt?: CPU scheduling
Wanneer gebruikt?: wanneer CPUs idle zijn een werk kunnen opnemen
Voordelen: throughput
Nadelen: minder respect voor CPU affiniteit => pas vanaf bepaalde drempelwaarde voor load wordt balancing ingezet
Alternatieven: 1 queue voor het hele systeem, i.p.v. 1 per CPU (meestal niet gedaan)
Pagina: 221

Naam: multicore multithreaded scheduling
Wat is/doet het?: CPU continu bezighouden
Hoe werkt het?: CPU voert een andere thread uit als het moet wachten op geheugen (memory stall)
Welke types zijn er?: coarse grained: wissel van thread bij wachten op geheugen
fine grained: per instructie wisselen
Waar gebruikt?: CPU thread scheduling
Wanneer gebruikt?: memory stall
Pagina: 222
Figuur: 5.10, 5.11

Naam: event latency
Wat is/doet het?: tijd tussen gebeurtenis en behandeling
Welke types zijn er?: interrupt latency: tijd tussen interrupt en interrupt service routine
dispatch latency: tijd om een proces te beeindigen en een nieuw te starten
Waar gebruikt?: Kritiek bij real-time systemen
Pagina: 223

Naam: Rate monotonic scheduling
Wat is/doet het?: real-time processen schedulen
Hoe werkt het?: prioriteit [$]\sim \frac{1}{periode}[/$], preemption als ander proces gescheduled moet worden
Waar gebruikt?: hard real time systems
Wanneer gebruikt?: bij fork/preemption/io completion/...
Voordelen: elk mogelijk real-time systeem kan met rate-monotonic gescheduled worden
Nadelen: proces moet periodisch zijn
constante tijd nodig per burst
Alternatieven: EDF, proportional share, (POSIX rt)
Pagina: 227
Figuur: 5.17, 5.18

Naam: EDF
Wat is/doet het?: hard real time scheduling
Hoe werkt het?: proces schedulen met eerste deadline, preemtion als er een nieuw proces bijkomt met vroegere deadline
Waar gebruikt?: hard real time system
Wanneer gebruikt?: bij fork/preemption/io completion/...
Voordelen: proces moet niet periodiek zijn
geen constante tijd nodig per burst
optimaal
Nadelen: proces moet deadline aangeven als het aangemaakt wordt
veel context switches, dus overhead bij wisselen
Alternatieven: Rate monotonic scheduling, proportional share
Pagina: 228
Figuur: 5.19

Naam: proporitonal share scheduling
Wat is/doet het?: real-time processen schedulen
Hoe werkt het?: tijd van CPU opdelen in aandelen, proces moet aantal aandelen vooraf vragen
Waar gebruikt?: hard real time systems
Wanneer gebruikt?: aanmaken proces
Pagina: 229