CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 4 of 7 · 3 min read

CPU-bound case

Think of two cashiers and four customers who each need ten minutes of service. Each customer gets half of a cashier's attention, so all four take twice as long. The analogy stops in one place: a customer waits in a line, and a process that is runnable is time-sliced (Level 3) and so receives its share in small pieces.

In plain words: The program burn loops without a pause, so it uses all the processor time it is given.

#include <stdlib.h>
#include <unistd.h>

int main(int argc, char **argv) {
    alarm(argc > 1 ? atoi(argv[1]) : 10);      /* stop after N seconds */
    volatile unsigned long x = 0;
    for (;;) x++;                              /* use the CPU without a pause */
}

Four copies were started on the 2-core test machine, and after 12 seconds the numbers were read:

 r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa st
 4  0      0 7844012   2120 202604    0    0     0     0  525  567 99  0  0  0  1
 4  0      0 7844012   2120 202604    0    0     0     0  511  551 100  1  0  0  0

  PID %CPU STAT COMMAND
  955 49.2 R    burn
  956 49.2 R    burn
  957 49.7 R    burn
  958 49.2 R    burn

load average: 1.16 0.28 0.09

A worked example. Read the three USE parts. Utilisation: us is 99 to 100 and id is 0: the processors are fully used. Saturation: r is 4 on 2 cores, so two processes are always waiting. Errors: none. Each of the four loops got 49 per cent of a core, which is 2 cores / 4 loops = 0.5 each, as the scheduler's fair sharing predicts. The swap and I/O columns are all 0, and wa is 0, so memory and disk are not the problem. The load average, however, was only 1.16 for the 1-minute figure, and 0.09 for the 15-minute figure, since the averages lag: they are smoothed over 1, 5 and 15 minutes, and the loops had run only about 15 seconds. A reader who looked only at the 15-minute load would think nothing was wrong.

The key lines. The signature of a processor-bound workload is id near 0 with r above the number of cores, and wa near 0. The fix is more cores, less work, or a better algorithm, and not a faster disk.

Processor saturation

Processor saturation is the state in which more tasks are ready to run than there are cores, so some wait. It is measured by the run queue length compared with the number of cores, and it makes each task slower even though the processors are fully used.

Example: four loops on two cores each run at half speed.

Common mistake

Using the 15-minute load average to judge a problem that began a minute ago. The three numbers describe different windows: 1 minute shows the present, and 15 minutes shows the history. A rising 1-minute figure with a low 15-minute figure means that the load is new.

Check yourself: 1. What share of a core did each of the four loops get? 2. Which vmstat values show processor saturation? 3. Why was the 15-minute load average so low?