Scheduling

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 events.

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)