CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 2 of 7 · 2 min read

Queues

Think of it this way. A supermarket can have one long line that feeds all the tills, or one line per till. One line keeps every till busy, but the people at the front must be handed out carefully, since two tills may call the same customer. Separate lines are simple, but one line may be long while another till stands idle. The analogy stops in one place: a customer can switch lines at once, and moving a process costs cache contents (Level 1, page 5).

Two designs exist for the ready queue of a multiprocessor.

  1. A single shared queue. All processors take from one list. This keeps all processors busy as long as work exists, but the list is shared data, so every access needs a lock (Level 4), and with many processors the lock becomes a bottleneck. A task also runs on a different processor each time, so its cached data is lost.
  2. One queue per processor. Each processor serves its own list. There is no lock fight, and a task tends to stay on one processor, keeping its cache. The weakness is imbalance: one list can be long while another is empty.

In plain words: Linux uses a queue per processor. To fix the imbalance, it moves tasks between queues from time to time: load balancing.

A small example, made up to show the idea. Five jobs of lengths 4, 4, 4, 4 and 2 (total 18) are on two processors. If four jobs sit in the queue of processor 0 and one in the queue of processor 1, then processor 0 needs 16 units and processor 1 needs 2 and then idles: the work ends at 16. If the balancer moves one 4-unit job over, processor 0 does 4 + 4 + 2 = 10, processor 1 does 4 + 4 = 8, and the work ends at 10. The best possible is 18 ÷ 2 = 9, and 10 is close.

Balancing has two styles. In push migration, a periodic task finds a busy processor and pushes some tasks to a less busy one. In pull migration, an idle processor takes a task from a busy one. Linux does both.

Load balancing

Load balancing is the movement of tasks from the ready queue of a busy processor to that of a less busy one, so that all processors have about equal work and none idles while another has waiting tasks.

Example: a processor that finishes its queue pulls a waiting task from the queue of a processor that still has four.

Check yourself: 1. Why does a single shared ready queue limit the number of processors? 2. In the example, why does the work end at 10 and not 9? 3. What is the difference between push and pull migration?