Course contentsShow
← Computer Science
Lesson 1266 of 2,87229. CPU SchedulingFree lesson

Per-CPU Run Queues

Examining separate ready queues per processor to reduce lock contention and enable parallel scheduling decisions.

Per-CPU Run Queues

What you'll learn: How modern operating systems use separate ready queues for each processor to reduce contention and improve parallel scheduling efficiency.


The Problem with a Single Global Queue

Imagine a single ticket counter at a massive airport where every airline must share it. Every time a ticket agent needs to check or update the queue, they must lock it so no one else can interfere—creating huge bottlenecks.

In early multiprocessor systems, all CPUs shared one global ready queue of processes waiting to run. Every time a scheduler on any CPU needed to pick the next process, it had to lock this queue. With many CPUs competing for the same lock, they spent more time waiting for each other than actually scheduling work—a phenomenon called lock contention.

Separate Queues per CPU

The solution: give each CPU its own private run queue (ready queue). Now each processor independently maintains its list of processes ready to execute.

How It Works

  • Each CPU has a dedicated run queue containing processes assigned to it
  • The scheduler on CPU 0 only accesses CPU 0's queue
  • The scheduler on CPU 1 only accesses CPU 1's queue
  • No lock contention when different CPUs schedule simultaneously
  • Processors make parallel scheduling decisions without blocking each other

Benefits

  1. Reduced lock contention: Each CPU locks only its own queue
  2. Parallel scheduling: All CPUs can schedule processes at the same time
  3. Better cache behavior: Keeps processes on the same CPU (processor affinity)
  4. Scalability: Performance improves as you add more CPUs

This architecture works beautifully with load balancing and push/pull migration (concepts you've already learned) to redistribute work when one CPU becomes overloaded.

Key Takeaway: Per-CPU run queues eliminate the global-queue bottleneck by giving each processor its own scheduling queue, enabling truly parallel scheduling decisions and drastically reducing lock contention in multiprocessor systems.