Linux Kernel Architecture

Chapter 5: Locking and Interprocess Communication

today. Scalability of Linux on systems with more than a single CPU has therefore become a very impor-

tant goal. This needs especially to be taken into account when locking rules are designed for a piece of

kernel code. Locking needs to fulfill two purposesthat are often hard to achieve simultaneously:

1. Code must be protected against concurrent access, which would lead to failures.


2. The impact on performance must be as little as possible.

Having both things at the same time is especially complicated when data are heavily used by the kernel.

Consider a really important data structure that is accessed very often — the memory management sub-

system contains such structures, for instance, but also the networking code and many other components

of the kernel. If the whole data structure (or, even worse, multiple data structures, or a whole driver, or

awholesubsystem^6 ) is protected by only a single lock, than chances are high that the lock is acquired by

some other part of the system when one part want to get hold of it.Lock contentionis said to be high in

this case, and the lock becomes ahotspotof the kernel. To remedy this situation, it is customary to iden-

tify independent parts of a data structure and usemultiplelocks to protect the elements. This solution is

known asfine-grained locking. While the approach is beneficial for scalability on really big machines, it

raises two other problems:

1. Taking many locks increases the overhead of an operation, especially on smaller SMP
   machines.


2. When a data structure is protected by multiple locks, then cases naturally arise that an oper-
   ation needs to access two protected regions simultaneously, and multiple locks must be held
   at the same time. This makes it necessary to obey a certainlock ordering, which mandates
   in which order locks are to be acquired and released. If not, then again deadlocks will be
   the result! Since the code paths through the kernel can be complicated and interwoven, it is
   especially hard to ensure that all cases are right.

Achieving fine-grained locking for good scalability while making sure to avoid deadlocks is therefore

currently among the kernel’s foremost challenges.

5.3 System V Interprocess Communication

Linux uses mechanisms introduced in System V (SysV) to support interprocess communication and syn-

chronization for user processes. System calls provide various routines to enable user libraries (typically

the C standard library) to implement the required operations.

In addition to semaphores, the SysV scheme of interprocess communication includes an option for

exchanging messages and sharing memory areas between processes in accordance with a controlled

pattern as described below.^7

5.3.1 System V Mechanisms

The three IPC mechanisms of System VUnix(semaphores, message queues, and shared memory) reflect

three very different concepts but have one thing in common. They all make use of system-wide resources

(^6) This is not so ridiculous as it may first sound, but the initial SMP-capable kernels even went one step further: After all, the big
kernel lock protectsallof the kernel!
(^7) The POSIX standard has now introduced similar structures in a more modern form. I do not discuss these because most applications
still use SysV mechanisms.