Worksheet 6

Video Lecture

There is no video lecture this week.

Readings

  1. CPU Scheduling (textbook)
  2. Scheduler
  3. Pipe pingpong
  4. Multi-core Scheduling (textbook)

In a multi-core CPU, each CPU core has its own cache. This speeds up access to memory, but ensuring cache coherence (all CPU cores see a consistent view of memory) will degrade performance. Keeping a process on the same CPU so it can reuse its warmed cache is also important to ensure good performance.

The textbook introduces two approaches for scheduling:

  • Single-Queue Multiprocessor Scheduling (SQMS): All CPUs draw from a common queue. This design is simple and naturally balances load, but it scales poorly and often destroys cache affinity, as processes jump between CPUs.
  • Multi-Queue Multiprocessor Scheduling (MQMS): Each CPU has its own queue. This improves scalability and affinity, since jobs tend to stay on the same CPU, but it risks load imbalance if some queues become emptier than others.

After reading how CFS works in Scheduler, do you see why CFS is MQMS and how it ensures cache affinity but creates imbalance problems? After reading Pipe pingpong, do you see the consequence of bad cache affinity and the price of enforcing cache coherence?

Learning Objectives

After working on this worksheet’s material, you should be able to say:

  1. I understand how the pipe ping‑pong benchmark works and why each round trip triggers two context switches.
  2. I understand the difference between CPU‑bound and I/O‑bound workloads.
  3. I understand the goals and trade‑offs of scheduling (response time vs. throughput) and how preemption and context‑switch overhead affect both.
  4. I understand CFS’s vruntime, nice, and the per-core run queue
  5. I understand why Linux maintains per‑core runqueues. I understand load balancing, work conserving, work stealing, and group scheduling
  6. I understand the scheduler’s power‑performance trade‑offs on CPUs with P‑cores + E‑cores.
  7. I understand how preemptive scheduling differs from cooperative scheduling
  8. I understand CPU affinity
  9. I understand how FIFO / FCFS / SJF / RR work (CPU Scheduling (textbook))
  10. I understand the concept of cache affinity, cache coherence, SQMS, MQMS. (Multi-core Scheduling (textbook))
Back to top