process scheduling
Summary
Scheduling algorithms
| Algorithm | Preemptive/non-preemptive | Starvation | Optimizes for | Remarks |
|---|---|---|---|---|
| FCFS | non-preemptive | no, FIFO | - | |
| RR | preemptive, quanta respecting | no, FIFO | reduce wait time | preemptive FCFS |
| SJF | non-preemptive | yes | minimize average turnaround time | |
| SRT | preemptive, no quanta | yes | minimize average turnaround time | preemptive SJF |
| Priority Scheduling | both | yes | highest priority first | |
| MLFQ | preemptive | yes | balance between response and throughput | |
| Lottery Scheduling | preemptive | no, probability | fair |
Scheduling metrics
| Metric | Description | Environment |
|---|---|---|
| Turnaround time | - total time taken for the job - includes time spent waiting for CPU - time completed - time arrived | batch processing |
| Waiting time | - time spent waiting instead of working - turnaround time - working time | batch processing |
| Throughput | - number of tasks finished per unit time | batch processing |
| CPU utilization | - percentage of CPU working on the task | batch processing |
| Response time | - time between request and response by system - time start - time arrived | interactive |
| Predictability | - variation in response time | interactive |
Concept
Concurrency
- multitasked processes
- parallelism
- virtual - single core
- physical - multi core
Timeslicing
- OS carries out context switching
- scheduler needs to run on the CPU
Process behaviour
- CPU activity
- computation, calculations
- compute-bound processes, eg. rendering
- IO activity
- requesting and receiving from IO devices, printing/reading
- IO-bound processes, eg. watching videos
Processing environment
Batch processing
- no user
- no interaction
- no need to be responsive
Interactive
- with user interaction
- should be responsive with consistent response time
Real time processing
- have deadline to meet
- perioding process
not really covered in
cs2106
Scheduling
- scheduler is triggered, OS takes over
- if context switch is needed
- current context is saved into the blocked/ready queue
- pick a process
Pto run based on scheduling algorithm - set up context for
P - let
Prun
- what metric to optimize for?
- each process have different behaviour/requirement of CPU time
Fairness
- fair share of CPU time
- can be per process or per user
- no starvation
Balance
- use all parts of the computer
- maximise concurrent use of other hardware
Non-preemptive
- cooperative
- process stays scheduled until
- it blocks
- it gives up the CPU voluntarily
Preemptive
- OS can forcibly interrupt the process before its finished
- time quanta respecting:
- processes have a fixed time quota
- can block or give up like non-preemptive
- if not finished by time quota, another process gets picked up
- fully disruptive:
- even during the time quantum the OS can interrupt
Lottery Scheduling
- give out “lottery tickets” to processes, more important processes can get more tickets
- a ticket is chosen randomly, winner is granted the resource
- responsive - even new processes can participate