Multiprocessor scheduling #

Simple approach #

• Shared ready queue, lock
• One dispatcher per core
• Timer interrupts per core
• Core takes highest-priority thread and runs it

When a thread becomes runnable:

• If the new thread is higher priority, preempt existing thread

Contention for lock and queues #

• Have a separate ready queue per core
• Balance load across cores (work stealing)

Work conservation #

• If there is a ready thread currently queued, and there’s an idle core, thread will run on that core

Core affinity #

• Expensive to move a thread to a new core
• Try to keep the thread on the same core

Gang scheduling #

• Run threads of a process together (on different cores)
• Otherwise, what happens is:
  • One thread locks
  • Deschedule
  • Other threads may block on lock
• Keep thread loaded even if blocked?
  • May unblock soon?
  • Busy waiting might be better in some cases!

The Linux kernel does not implement gang scheduling.