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, long jobs | minimize average turnaround time | |
| SRT | preemptive, no quanta | yes, long jobs | minimize average turnaround time | preemptive SJF |
| Priority Scheduling | both | yes, low priority | highest priority first | |
| MLFQ | preemptive | yes, low priority | 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 |
Scheduling optimisation
| Scheduling Algorithm | CPU Utilization | Throughput | Response Time | Turnaround Time | Wait Time | Notes |
|---|---|---|---|---|---|---|
| FCFS | ✓ | ~ | ✗ | ✗ | ✓, bounded wait | suffers from convoy effect (short jobs wait behind long ones) |
| RR | ~, big quantum | ~ | ✗ | ~ | ✓, small quantum | fairness via time quantum, bounded wait time |
| SJF | ✓ | ✓ | ~ | ✓, optimal average | ✗ | starvation of long jobs |
| SRT | ✓ | ✓ | ~ | ✓ | ✗ | good responsiveness but starvation possible |
| Priority Scheduling | ~, big quantum | ✓ | ✓, high priority | ~ | ✓ | low-priority processes may starve |
| MLFQ | ~, big quantum | ✓ | ✓, IO bound | ✓, CPU bound | ✓ | approximates SJF while preventing starvation |
| Lottery Scheduling | ~, big quantum | ~ | ~ | ~ | ✓ | probabilistic fairness |
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