Semaphores

Semaphores are routines that ensure orderly access to regions of code. Like spinlocks, semaphores guard kernel data structures by controlling access to regions of code associated with a set of data structures. Unlike spinlocks, semaphores require the waiting thread to relinquish the CPU while awaiting the lock. Semaphores are implemented using a swtch() to allow another thread to run.

Figure 1-7 Conceptual view of a semaphore

Semaphores serve two functions mutual exclusion and synchronization. Mutual-exclusion semaphores protect data and are further classified by their degree of restrictiveness.

Mutual-Exclusion Semaphores

Mutual-exclusion semaphores provide mutually exclusive access to regions of code that are associated with a set of data structures.

In a mutual-exclusion semaphore, a processor attempting to acquire a semaphore already held by another processor puts its current thread of control to sleep and switches to another. It is assumed that the expected time duration the thread will wait while the lock is busy will be much greater than the overhead of a process switch.

The kernel makes available two types of mutual-exclusion semaphores:

Alpha semaphores, which must be released when a thread of control sleeps.
The alpha semaphore cannot be held during sleep because it is used to protect data structures that must be consistent at the time of context switch. This applies, for example, to the fields in structures that describe the process state of a thread of control.
A broadly encompassing alpha semaphore, called an empire semaphore, protects a collection of data structures.
Beta semaphores, which a thread of control may hold while sleeping.
A beta semaphore can be held while sleeping because the protected data structures need not be consistent at the time of context switch. An example of this is the page frame lock during a page fault. The resource must remain locked during the resolution of the fault but the thread yields the processor while its page is brought in from memory.

Synchronization Semaphores

Synchronization semaphores signal events rather than block access to data structures and are used when events are awaited. They synchronize a thread with other threads and external events. The table that follows describes some of these differences in practice.

Comparison of Blocking vs Synchronization Semaphore

Data protection (blocking or mutual exclusion) semaphores and synchronization semaphores differ in four ways.

Locking and unlocking operations
Signal handling
Initialization
Count

Table 1-7 Differences between mutual-exclusion and synchronization semaphores

Mutual-Exclusion (Alpha/Beta)

Synchronization

Lock and unlock operations are always performed by the same thread.

Lock and unlock operations performed by different threads.

Synchronization is provided by one thread doing a lock, which causes it to block. While blocked, the thread sleeps until another thread does an unlock, causing the locking thread to awaken.

This mechanism enables you to use semaphores to cause a thread to wait on an event from another thread

Thread blocked on semaphore cannot be awakened by a signal.

Signals are deferred until the thread acquires the semaphore, on the assumption that semaphores are not held for long durations.

Threads blocked on a synchronization semaphore have three options:

Signals can be caught and handled.
Signals can be deferred until the semaphore operation is complete.
Signals can be handled as though the code were unsemaphored.

Sample Semaphores

The table below shows some of the semaphores the kernel creates at initialization time from init_semaphores() and realmain(). They are listed only by type and name. You can look at the kernel source to observe how each are used.

Table 1-8 A Sampling of semaphores

Type of semaphore Sample

Alpha Semaphores

filesys_sema

pm_sema

up_io_sema

mdisc2_sema

vmsys_sema

Beta Semaphores

msem_betasem

iomap_betasem

Synchronization Semaphores

runin

runout

Empire Semaphores

Some alpha semaphores are classified as empire semaphores, because they protect data structures for an entire subsystem. Empire semaphores are locked when any of the structures within the set must be modified. Because they control access to an entire subsystem, empire semaphores are used to serialize operations within the subsystem. For example, the filesystem empire (filesys_sema) is locked when calling sync(), to prevent other threads from invalidating pages of data that are being flushed from cache.

Empire semaphores are acquired and released with pxsema()/vxsema() calls.

MP Safety

The up_io_sema empire semaphore provides "single threading" (access control) for I/O drivers that are not MP safe. An MP-safe driver is one that synchronizes multiple accesses to code and structures, so that more than one instance of the driver may be active at any given time without contention.

Semaphores

Technical documentation

» Table of Contents

Mutual-Exclusion Semaphores

Synchronization Semaphores

Comparison of Blocking vs Synchronization Semaphore

Sample Semaphores

Empire Semaphores

MP Safety