Linux Kernel Architecture

Chapter 5: Locking and Interprocess Communication

Although the structure is defined in an architecture-dependent header file, most architectures use the

structure shown.

❑ countspecifies how many processes may be in the critical region protected by the semaphore at

the same time.count == 1is used in most cases (semaphores of this kind are also known asmutex

semaphores because they are used to implementmutual exclusion).

❑ sleepersspecifies the number of processes waiting to be allowed to enter the critical region.

Unlike spinlocks, waiting processes go to sleep and are not woken until the semaphore is free;

this means that the relevant CPU can perform other tasks in the meantime.

❑ waitis used to implement a queue to hold the task structures of all processes sleeping on the

semaphore (Chapter 14 describes the underlying mechanisms).

In contrast to spinlocks, semaphores are suitable for protecting longer critical sections against parallel

access. However, they should not be used to protect shorter sections because it is very costly to put

processes to sleep and wake them up again — as happens when the semaphore is contended.

In most cases, the full potential of semaphores is not required, but they are used in the form of mutexes,

which are nothing other than binary semaphores. To simplify this case, the kernel provides the macros

DECLARE_MUTEX, which declare a binary semaphore that starts out unlocked withcount = 1.^3

DECLARE_MUTEX(mutex)

...

down(&mutex);

/* Critical section */

up(&mutex);

The usage counter is decremented withdownwhen the critical section is entered. When the counter has

reached 0, no other process may enter the section.

When an attempt is made to acquire areservedsemaphore withdown, the current process is put to sleep

and placed on the wait queue associated with the semaphore. At the same time, the process is placed

in theTASK_UNINTERRUPTIBLEstate and cannot receive signals while waiting to enter the critical region.

If the semaphore isnot reserved, the process may immediately continue without being put to sleep and

enters the critical region, but not without reserving the semaphore first.

upmust be called when the critical region is exited. The routine is responsible for waking one of the

processes sleeping on the semaphore — this process is then allowed to enter the critical section, and all

other processes continue to sleep.

In addition todown, two other operations are used to reserve a semaphore (unlike spinlocks, only oneup

function is available and is used to exitthe section protected by a semaphore):

❑ down_interruptibleworks in the same way asdownbut places the task in the

TASK_INTERRUPTIBLEstate if the semaphore could not be acquired. As a result, the

process can be woken by signals while it is sleeping.^4

(^3) Note that earlier kernel versions also provided the macroDECLARE_MUTEX_LOCKEDto initialize a locked semaphore, but this
variant has been removed during the development of kernel 2.6.24 because it was only required for operations that can be better
implemented bycompletions, as discussed in Section 14.4.
(^4) If the semaphore is acquired, the function returns 0. If the process is interrupted by a signal without acquiring the semaphore,
-EINTR is returned.