Scheduling (and Multitasking)¶
Core kernel subsystem
Assigns CPU resources to runnable tasks (tasks that do not wait for anything; e.g. network I/O, timer)
Task: process or thread; kernel makes no difference (see Tasks? Processes? Threads? for difference and motivation)
Each task can run on the CPU for only a short period of time (variable, but lets say 20ms)
Many tasks ⟶ illusion of parallelism, even on a single CPU
No task must starve (not scheduled onto a CPU for a long time)
Each task must receive an equal CPU share
Among all runnable tasks, the “best” tasks is chosen to run next
When a task becomes runnable (e.g. network packet arrived), it does not run immediately
Only added to set of runnable tasks ⟶ scheduler picks “best” task when CPU becomes available
⟶ tasks not interrupted; can achieve more work
Dynamic meaning of “best”, based on usage patterns
⟶ CPU bound vs. I/O bound
Task use up its timeslice ⟶ preempted by scheduler
Task mostly waits for something (e.g. network I/O, timer)
Wakes up for a short time period to process the event
Waits for next event ⟶ no need to preempt
I/O bound: waits for timer to expire. Start one of it.
$ i=0; while true; do sleep 0.1; echo $i; i=$((i+1)); done
CPU bound: computes SHA1 checksum over infinite stream of 0-bytes. Start many.
$ sha1sum /dev/zero
top to show CPU usage
Question when a CPU has become available: Which one do I pick next?
How do CPUs become available?
Preemption: a task has exhausted its timeslice. Still runnable, but not running.
Voluntarily: a task goes to sleep (wait for some external event). Not runnable.
Which one do I pick next?
Not easily answered
CPU vs. I/O bound (⟶ dynamic prioritization)
Nice value (⟶ later)
Realtime (⟶ later)