Linux Kernel Architecture

Chapter 5: Locking and Interprocess Communication

leaves the normal prioritytask_struct->normal_priorityuntouched. If you are confused by these

terms, it might be a good idea to refresh yourself with the discussion of the scheduler in Chapter 2.

Besides, the kernel provides several standard functions (rt_mutex_init,rt_mutex_lock,

rt_mutex_unlock,rt_mutex_trylock) that work exactly as for regular mutexes and thus need

not be discussed any further.

5.2.9 Approximate Per-CPU Counters

Counters can become a bottleneck if a system is equipped with a large number of CPUs: Only one CPU at

a time may modify the value; all other CPUs need to wait for the operation to finish until they can access

the counter again. If a counter is frequently visited, this has a severe impact on system performance.

For some counters, it is not necessary to know the exact value at all times. An approximation of the

value serves quite as well as the proper value would do. This insight can be used to accelerate counter

manipulation on SMP systems by introducing per-CPU counters. The basic idea is depicted in Figure 5-1:

The proper counter value is stored at a certain place in memory, and an array with one entry for every

CPU in the system is kept below the memory location of the proper value.

value

Per-CPU

difference

Figure 5-1: Data stucture for approximate

per-CPU counters.

If a processor wants to modify the value of the counter by adding or subtracting a numbern,itdoes

not perform this modification by directly changing the counter value because this would require locking

out other CPUs from accessing the counter, a potentially time-consuming operation. Instead, the desired

modification is stored in the CPU-specific entry of the array associated with the counter. If, for instance,

the value 3 was supposed to be added to the counter, the entry+3 would be stored in the array. If the

same CPU wants to substract a number (say, 5) from the counter at some other time, it also does not

perform the operation directly on the counter, but on the value in the CPU-specific array: 5 is subtracted

from 2, and the new value is thus−2. If any processor reads the counter value, it is not entirely accurate.

If the original value was 15, then it would be 13 after the previously mentioned modifications, but is still

15. If one wants to know the value only approximately, 13 is still a good approximation to 15.

If the changes in one of the CPU-specific array elements sum up to a value above or below a threshold

that is considered to be large, the proper counter value is changed. In this case, the kernel needs to make

sure that the access is protected by appropriate locking. But since this change now occurs only seldom,

the cost of the locking operation is not so important anymore.