struct semaphore {

atomic_t count; int sleepers; wait_queue_head_t wait;

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

□ count specifies how many processes may be in the critical region protected by the semaphore at the same time. count == 1 is used in most cases (semaphores of this kind are also known as mutex semaphores because they are used to implement mutual exclusion).

□ sleepers specifies 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.

□ wait is 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 with count = 1.3



The usage counter is decremented with down when 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 a reserved semaphore with down, 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 the task_uninterruptible state and cannot receive signals while waiting to enter the critical region. If the semaphore is not reserved, the process may immediately continue without being put to sleep and enters the critical region, but not without reserving the semaphore first.

up must 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 to down, two other operations are used to reserve a semaphore (unlike spinlocks, only one up function is available and is used to exit the section protected by a semaphore):

□ down_interruptible works in the same way as down but places the task in the task_interruptible state if the semaphore could not be acquired. As a result, the process can be woken by signals while it is sleeping.4

3Note that earlier kernel versions also provided the macro DECLARE_MUTEX_LOCKED to 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 by completions, as discussed in Section 14.4.

4If the semaphore is acquired, the function returns 0. If the process is interrupted by a signal without acquiring the semaphore, -EINTR is returned.

□ down_trylock attempts to acquire a semaphore. If it fails, the process does not go to sleep to wait for the semaphore but continues execution normally. If the semaphore is acquired, the function returns a false value, otherwise a true value.

In addition to mutex variables that can be used in the kernel only, Linux also features so-called futexes (fast userspace mutex) that consist of a combination of kernel and user mode. These provide mutex functionality for userspace processes. However, it must be ensured that they are used and manipulated as quickly and efficiently as possible. For reasons of space, I dispense with a description of their implementation, particularly as they are not especially important for the kernel itself. See the manual page futex(2) for more information.

Continue reading here: The Read CopyUpdate Mechanism

Was this article helpful?

0 0