Scheduling and Synchronization

  • The scheduler is a replaceable component.
  • The scheduler runs in user mode.
  • The scheduler implements all actions that may change the calling thread’s state (e.g. run → blocked and blocked → ready).
  • Threads cannot block anywhere except inside the scheduler. The scheduler knows all waiting and active threads.
  • The scheduler provides synchronization via semaphores.
  • Semaphores are implemented by a pair of portals (for the P and V operations).

CPU Inheritance Scheduling

  • Threads schedule each other by donating the CPU using directed yield primitive.
  • One root scheduler thread per CPU sources all CPU time.
  • Kernel dispatcher manages threads, events and CPU donation without making any scheduling policy decisions.

The Dispatcher

  • Implements thread sleep, wakeup, schedule, etc.
  • Runs in context of currently running thread.
  • Has no notion of thread priority, CPU usage, clocks or timers.
  • Dispatcher wakes up a scheduler thread when
    • Scheduler's client blocks.
    • Event of interest to the scheduler occurs.

The schedule() operation

schedule(thread, control_port, sensitivity)

Sensitivity levels:

  • SCHEDULE_ON_BLOCK Wake the scheduler any time its client thread blocks.
  • SCHEDULE_ON_SWITCH Wake the scheduler only when a different client is requesting the CPU.
  • SCHEDULE_ON_CONFLICT Wake the scheduler only when two or more clients are runnable at the same time.

Wait-free syncronization (for lock-free scheduler)