Scheduling (and Multitasking)

Scheduling

  • Scheduler

    • 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)

  • Timeslicing

    • 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

Fairness Criteria

  • 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

    • ⟶ throughput

  • Dynamic meaning of “best”, based on usage patterns

    • ⟶ CPU bound vs. I/O bound

CPU bound vs. I/O bound

  • CPU bound

    • Task use up its timeslice ⟶ preempted by scheduler

  • I/O bound

    • 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

Demo: I/O vs CPU bound

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

Note

Use top to show CPU usage

Scheduling Decision, Runnability

  • 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)