Lock Contention and Fine Grained Locking

After having discussed the numerous locking primitives provided by the kernel, let us briefly address some of the problems related to locking and kernel scalability. While multiprocessor systems were nearly completely unknown to the average user only a decade ago, they are present on nearly every desktop today. Scalability of Linux on systems with more than a single CPU has therefore become a very important 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 purposes that 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 subsystem 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 a whole subsystem6) 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 contention is said to be high in this case, and the lock becomes a hotspot of the kernel. To remedy this situation, it is customary to identify independent parts of a data structure and use multiple locks to protect the elements. This solution is known as fine-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 operation needs to access two protected regions simultaneously, and multiple locks must be held at the same time. This makes it necessary to obey a certain lock 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.

Continue reading here: System V Interprocess Communication

Was this article helpful?

0 0