# The Kernel Kit: Semaphores

Declared in: be/kernel/OS.h

Library: libroot.so

## Overview

A semaphore is a token that's used to synchronize multiple threads, usually for one of these reasons:

- Locking. The most common use of a semaphore is to create a mutually exclusive lock: It ensures that only one thread can execute a "protected" section of code at a time. See "Example 1: Using a Semaphore as a Lock."

- Execution Oder. Semaphores can also be used to impose an order in which a series of dependent operations are performed by two or more threads. See "Example 2: Using Semaphores to Impose an Execution Order."

The semaphore concept is simple: To enter into a semaphore-protected "critical section", a thread must first "acquire" the semaphore, through the `acquire_sem()` function. When it passes out of the critical section, the thread "releases" the semaphore through `release_sem()`.

The advantage of the semaphore system is that if a thread can't acquire a semaphore (because the semaphore is yet to be released by the previous acquirer), the thread blocks in the `acquire_sem()` call. While it's blocked, the thread doesn't waste any cycles.

The full story about semaphores is a wee bit more complicated than this quick description, but if all you want to do is create a mutually exclusive lock or impose an execution order, you'll probably learn all you need to know by visiting the examples in the sections referred to above.

## The Full Story

A semaphore acts as a key that a thread must acquire in order to continue execution. Any thread that can identify a particular semaphore can attempt to acquire it by passing its `sem_id` identifier--a system-wide number that's assigned when the semaphore is created--to the `acquire_sem()` function. The function blocks until the semaphore is actually acquired.

|  | An alternate function, `acquire_sem_etc()` lets you specify the amount of time you're willing to wait for the semaphore to be acquired. Unless otherwise noted, characteristics ascribed to `acquire_sem()` apply to `acquire_sem_etc()` as well.)

When a thread acquires a semaphore, that semaphore (typically) becomes unavailable for acquisition by other threads (less typically, more than one thread is allowed to acquire the semaphore at a time; the precise determination of availability is explained in "The Thread Count"). The semaphore remains unavailable until it's passed in a call to the `release_sem()` function.

The code that a semaphore "protects" lies between the calls to `acquire_sem()` and `release_sem()`. The disposition of these functions in your code usually follows this pattern:

       if (acquire_sem(my_semaphore) == B_NO_ERROR) {
          /* Protected code goes here. */
          release_sem(my_semaphore);
       }

Keep in mind that...

- The calls to the acquire and release functions needn't be locally balanced (although this is by far the most common use). A semaphore can be acquired within one function and released in another. Acquisition and release of the same semaphore can even be performed by two different threads.

- Checking the value returned by `acquire_sem()` is extremely important. If an acquire-blocked thread is unblocked by a signal (a return o f `B_INTERRUPTED`), the thread shouldn't procede to the critical section.

### The Thread Queue

Every semaphore has its own thread queue: This is a list that identifies the threads that are waiting to acquire the semaphore. A thread that attempts to acquire an unavailable semaphore is placed at the tail of the semaphore's thread queue where it sits blocked in the `acquire_sem()` call. Each call to `release_sem()` umblocks the thread at the head of that semaphore's queue, thus allowing the thread to return from its call to `acquire_sem()`.

Semaphores don't discriminate between acquisitive threads--they don't prioritize or otherwise reorder the threads in their queues--the oldest waiting thread is always the next to acquire the semaphore.

### The Thread Count

To assess availability, a semaphore looks at its thread count. This is a counting variable that's initialized when the semaphore is created. Ostensibly, a thread count's initial value (which is passed as the first argument to `create_sem()`) is the number of threads that can acquire the semaphore at a time. (As we'll see later, this isn't the entire story, but it's good enough for now.) For example, a semaphore that's used as a mutually exclusive lock takes an initial thread count of 1--in other words, only one thread can acquire the semaphore at a time.

|  | An initial thread count of 1 is by far the most common use; a thread count of 0 is also useful. Other counts are much less common.

Calls to `acquire_sem()` and `release_sem()` alter the semaphore's thread count: `acquire_sem()` decrements the count, and `release_sem()` increments it. When you call `acquire_sem()`, the function looks at the thread count (before decrementing it) to determine if the semaphore is available:

- If the count is greater than zero, the semaphore is available for acquisition, so the function returns immediately.

- If the count is zero or less, the semaphore is unavailable, and the thread is placed in the semaphore's thread queue.

The initial thread count isn't an inviolable limit on the number of threads that can acquire a given semaphore--it's simply the initial value for the sempahore's thread count variable. For example, if you create a semaphore with an initial thread count of 1 and then immediately call `release_sem()` five times, the semaphore's thread count will increase to 6. Furthermore, although you can't initialize the thread count to less-than-zero, an initial value of zero itself is common--it's an integral part of using semaphores to impose an execution order (as demonstrated later).

Summarizing the description above, there are three significant thread count value ranges:

- A positive thread count (n) means that there are no threads in the semaphore's queue, and the next n `acquire_sem()` calls will return without blocking.

- If the count is 0, there are no queued threads, but the next `acquire_sem()` call will block.

- A negative count (-n) means there are n threads in the semaphore's thread queue, and the next call to `acquire_sem()` will block.

Although it's possible to retrieve the value of a semaphore's thread count (by looking at a field in the semaphore's `sem_info` structure, as described later), you should only do so for amusement--while you're debugging, for example.

|  | You should never predicate your code on the basis of a semaphore's thread count.

### Deleting a Semaphore

Every semaphore is owned by a team (the team of the thread that called`create_sem()`). When the last thread in a team dies, it takes the team's semaphores with it.

Prior to the death of a team, you can explicitly delete a semaphore through the `delete_sem()` call. Note, however, that `delete_sem()` must be called from a thread that's a member of the team that owns the semaphore--you can't delete another team's semaphores.

You're allowed to delete a semaphore even if it still has threads in its queue. However, you usually want to avoid this, so deleting a semaphore may require some thought: When you delete a semaphore (or when it dies naturally), all its queued threads are immediately allowed to continue--they all return from`acquire_sem()` at once. You can distinguish between a "normal" acquisition and a "semaphore deleted" acquisition by the value that's returned by `acquire_sem()` (the specific return values are listed in the function descriptions, below).

### Broadcasting Semaphores

The `sem_id` number that identifies a semaphore is a system-wide token--the `sem_id` values that you create in your application will identify your semaphores in all other applications as well. It's possible, therefore, to broadcast the`sem_id` numbers of the semaphores that you create and so allow other applications to acquire and release them--but it's not a very good idea.

|  | A semaphore is best controlled if it's created, acquired, released, and deleted within the same team.

If you want to provide a protected service or resource to other applications, you should accept messages from other applications and then spawn threads that acquire and release the appropriate semaphores.

## Example 1: Using a Semaphore as a Lock

The most typical use of a semaphore is to protect a "critical section": This is a chunk of code that needs to be executed without interruption. The semaphore acts as a lock; `acquire_sem()` locks the code, `release_sem()` releases it. Semaphores that are used as locks are (almost always) created with a thread count of 1.

As a simple example, let's say you keep track of a maximum value like this:

       /* max_val is a global. */
       uint32 max_val = 0;
       ...

       /* bump_max() resets the max value, if necessary. */
       void bump_max(uint32 new_value)
       {
          if (new_value > max_value)
             max_value = new_value;
       }

bump_max() isn't thread safe; there's a race condition between the comparison and the assignment. So we protect it with a semaphore:

       sem_id max_sem;
       uint32 max_val = 0;

       ...
       /* Initialize the semaphore during a setup routine. */
       status_t init()
       {
          if ((max_sem = create_sem(1, "max_sem")) < B_NO_ERROR)
             return B_ERROR;
          ...
       }
       void bump_max(uint32 new_value)
       {
          if (acquire_sem(max_sem) != B_NO_ERROR)
             return;
          if (new_value > max_value)
             max_value = new_value;
          release_sem();
       }

#### Benaphores

A "benaphore" is a combination of an atomic variable and a semaphore that can improve locking efficiency. If you're using a semaphore as shown in the previous example, you almost certainly want to use the benaphore mechanism instead (if you can).

Here's the example re-written to use a benaphore:

       sem_id max_sem;
       uint32 max_val = 0;
       int32 ben_val = 0;

       status_t init()
       {
          /* This time we initialized the semaphore to 0. */
          if ((max_sem = create_sem(0, "max_sem")) < B_NO_ERROR)
             return B_ERROR;
          ...
       }
       void bump_max(uint32 new_value)
       {
          int32 previous = atomic_add(&ben_val, 1);
          if (previous >= 1)
             if (acquire_sem(max_sem) != B_NO_ERROR)
                goto get_out;

          if (new_value > max_value)
             max_value = new_value;

       get_out:
          previous = atomic_add(&ben_val, -1);
          if (previous > 1)
             release_sem(max_sem);
       }

The point, here, is that `acquire_sem()` is called only if it's known (by checking the previous value of `ben_val`) that some other thread is in the middle of the critical section. On the releasing end, the `release_sem()` is called only if some other thread has since entered the function (and is now blocked in the `acquire_sem()` call). An important point, here, is that the semaphore is initialized to 0.

## Example 2: Using Semaphores to Impose an Execution Order

Semaphores can also be used to coordinate threads that are performing separate operations, but that need to perform these operations in a particular order. In the following example, we have a global buffer that's accessed through separate reading and writing functions. Furthermore, we want writes and reads to alternate, with a write going first.

We can lock the entire buffer with a single semaphore, but to enforce alternation we need two semaphores:

       sem_id write_sem, read_sem;
       char buffer[1024];

       /* Initialize the semaphores */
       status_t init()
       {
          if ((write_sem = create_sem(1, "write")) < B_NO_ERROR) {
             return;
          if ((read_sem = create_sem(0, "read")) < B_NO_ERROR) {
             delete_sem(write_sem);
             return;
          }
       }

       status_t write_buffer(const char *src)
       {
          if (acquire_sem(write_sem) != B_NO_ERROR)
             return B_ERROR;

          strncpy(buffer, src, 1024);

          release_sem(read_sem);
       }

       status_t read_buffer(char *dest, size_t len)
       {
          if (acquire_sem(read_sem) != B_NO_ERROR)
             return B_ERROR;

          strncpy(dest, buffer, len);

          release_sem(write_sem);
       }

The initial thread counts ensure that the buffer will be written to before it's read: If a reader arrives before a writer, the reader will block until the writer releases the `read_sem` semaphore.

## Semaphore Functions

### acquire_sem(), acquire_sem_etc()

          status_t acquire_sem(sem_id sem)
          status_t acquire_sem_etc(sem_id sem,
             uint32 count,
             uint32 flags,
             bigtime_t timeout)

These functions attempt to acquire the semaphore identified by the sem argument. Except in the case of an error, `acquire_sem()` doesn't return until the semaphore has actually been acquired.

`acquire_sem_etc()` is the full-blown acquisition version: It's essentially the same as `acquire_sem()`, but, in addition, it lets you acquire a semaphore more than once, and also provides a timeout facility:

- The count argument lets you specify that you want the semaphore to be acquired count times. This means that the semaphore's thread count is decremented by the specified amount. It's illegal to specify a count that's less than 1.

- To enable the timeout, you pass `B_TIMEOUT` as the flags argument, and set timeout to the amount of time, in microseconds, that you're willing to wait for the semaphore to be acquired. If the semaphore hasn't been acquired within timeout microseconds, the function returns anyway (`B_TIMED_OUT`). If you specify a timeout of 0 and the semaphore isn't immediately available, the function immediately returns `(B_WOULD_BLOCK`).

|  | In addition to`B_TIMEOUT`, the Kernel Kit defines two other semaphore-acquisition flag constants (`B_CAN_INTERRUPT` and `B_CHECK_PERMISSION`). These additional flags are used by device drivers--adding these flags into a "normal" (or "user-level") acquisition has no effect. However, you should be aware that the `B_CHECK_PERMISSION` flag is always added in to user-level semaphore acquisition in order to protect system-defined semaphores.

Other than the timeout and the acquisition count, there's no difference between the two acquisition functions. Specifically, any semaphore can be acquired through either of these functions; you always release a semaphore through`release_sem()` (or `release_sem_etc()`) regardless of which function you used to acquire it.

To determine if the semaphore is available, the function looks at the semaphore's thread count (before decrementing it):

- If the thread count is positive, the semaphore is available and the current acquisition succeeds. The `acquire_sem()` (or `acquire_sem_etc()`)`` function returns immediately upon acquisition.

- If the thread count is zero or less, the calling thread is placed in the semaphore's thread queue where it waits for a corresponding `release_sem()` call to de-queue it (or for the timeout to expire).

RETURN CODES

- `B_NO_ERROR`. The semaphore was successfully acquired.

- `B_BAD_SEM_ID`. The sem argument doesn't identify a valid semaphore. It's possible for a semaphore to become invalid while an acquisitive thread is waiting in the semaphore's queue. For example, if your thread calls `acquire_sem()` on a valid (but unavailable) semaphore, and then some other thread deletes the semaphore, your thread will return `B_BAD_SEM_ID` from its call to `acquire_sem()`.

The other return values apply to `acquire_sem_etc()` only:

- `B_BAD_VALUE`. Illegal count value (less than 1).
- `B_WOULD_BLOCK`. You specified a timeout of 0 and the semaphore isn't available.
- `B_TIMED_OUT`. The timeout expired (for all values of timeout other than 0).

### create_sem()

          sem_id create_sem(uint32 thread_count, const char *name)

Creates a new semaphore and returns a system-wide `sem_id` number that identifies it. The arguments are:

- thread_count initializes the semaphore's thread count, the counting variable that's decremented and incremented as the semaphore is acquired and released (respectively). You can pass any non-negative number as the count, but you typically pass either 1 or 0, as demonstrated in the examples above.

- name is an optional string name that you can assign to the semaphore. The name is meant to be used only for debugging. A semaphore's name needn't be unique--any number of semaphores can have the same name.

Valid `sem_id` numbers are positive integers. You should always check the validity of a new semaphore through a construction such as

       if ((my_sem = create_sem(1,"My Semaphore")) < B_NO_ERROR)
          /* If it's less than B_NO_ERROR, my_sem is invalid. */

`create_sem()` sets the new semaphore's owner to the team of the calling thread. Ownership may be re-assigned through the `set_sem_owner()` function. When the owner dies (when all the threads in the team are dead), the semaphore is automatically deleted. The owner is also signficant in a`delete_sem()` call: Only those threads that belong to a semaphore's owner are allowed to delete that semaphore.

RETURN CODES

- `B_BAD_VALUE`. Invalid thread_count value (less than 0).
- `B_NO_MEMORY`. Not enough memory to allocate the semaphore's name.
- `B_NO_MORE_SEMS`. All valid `sem_id` numbers are being used.

### delete_sem()

          status_t delete_sem(sem_id sem)

Deletes the semaphore identified by the argument. If there are any threads waiting in the semaphore's thread queue, they're immediately unblocked.

|  | This function may only be called from a thread that belongs to the semaphore's owner.

RETURN CODES

- `B_NO_ERROR`. The semaphore was successfully deleted.
- `B_BAD_SEM_ID. sem` is invalid, or the calling thread doesn't belong to the team that owns the semaphore.

### get_sem_count()

          status_t get_sem_count(sem_id sem, int32 *thread_count)

|  | For amusement purposes only; never predicate your code on this function.

Returns, by reference in thread_count, the value of the semaphore's thread count variable:

- A positive thread count (n) means that there are no threads in the semaphore's queue, and the next n `acquire_sem()` calls will return without blocking.

- If the count is zero, there are no queued threads, but the next `acquire_sem()` call will block.

- A negative count (-n) means there are n threads in the semaphore's thread queue and the next call to `acquire_sem()` will block.

By the time this function returns and you get a chance to look at the thread_count value, the semaphore's thread count may have changed. Although watching the thread count might help you while you're debugging your program, this function shouldn't be an integral part of the design of your application.

RETURN CODES

- `B_NO_ERROR`. Success.
- `B_BAD_SEM_ID`. sem is invalid(thread_count isn't changed).

### get_sem_info(), get_next_sem_info(), sem_info

          status_t get_sem_info(sem_id sem, sem_info *info)
          status_t get_next_sem_info(team_id team,
             uint32 *cookie,
             sem_info *info)

          struct {} sem_info

Copies information about a particular semaphore into the `sem_info` structure designated by info. The first version of the function designates the sempahore directly, by `sem_id`.

The `get_next_sem_info()` version lets you step through the list of a team's semaphores through iterated calls on the function. The team argument identifies the team you want to look at; a team value of 0 means the team of the calling thread. The cookie argument is a placemark; you set it to 0 on your first call, and let the function do the rest. The function returns `B_BAD_VALUE` when there are no more sempahores to visit:

       /* Get the sem_info for every sempahore in this team. */
       sem_info info;
       int32 cookie = 0;

       while (get_next_sem_info(0, &cookie, &info) == B_OK)
          ...

The `sem_info` structure is:

          typedef struct sem_info {
                sem_id sem;
                team_id team;
                char name[B_OS_NAME_LENGTH];
                int32 count;
                thread_id latest_holder;
             } sem_info

The structure's fields are:

- `sem`. The `sem_id` number of the semaphore.
- `team`. The`team_id` of the semaphore's owner.
- `name`. The name assigned to the semaphore.
- `count`. The semaphore's thread count.
- `latest_holder`. The thread that most recently acquired the semaphore.

|  | The `lastest_holder` field is highly undependable; in some cases, the kernel doesn't even record the semaphore acquirer. Although you can use this field as a hint while debugging, you shouldn't take it too seriously. Love, Mom.

The information in the `sem_info` structure is guaranteed to be internally consistent, but the structure as a whole should be consider to be out-of-date as soon as you receive it. It provides a picture of a semaphore as it exists just before the info-retrieving function returns.

RETURN CODES

- `B_NO_ERROR`. Success.
- `B_BAD_SEM_ID`. Invalid sem value.
- `B_BAD_TEAM_ID`. Invalid team value.

### release_sem(), release_sem_etc()

          status_t release_sem(sem_id sem)
          status_t release_sem_etc(sem_id sem, int32 count, uint32 flags)

The `release_sem()` function de-queues the thread that's waiting at the head of the semaphore's thread queue (if any), and increments the semaphore's thread count. `release_sem_etc()` does the same, but for count threads.

Normally, releasing a semaphore automatically invokes the kernel's scheduler. In other words, when your thread calls `release_sem()`, you're pretty much guaranteed that some other thread will be switched in immediately afterwards, even if your thread hasn't gotten its fair share of CPU time. If you want to subvert this automatism, call `release_sem_etc()` with a flags value of `B_DO_NOT_RESCHEDULE`. Preventing the automatic rescheduling is particularly useful if you're releasing a number of different semaphores all in a row: By avoiding the rescheduling you can prevent some unnecessary context switching.

RETURN CODES

- `B_NO_ERROR`. The semaphore was successfully released.
- `B_BAD_SEM_ID`. Invalid sem value.
- `B_BAD_VALUE`. Invalid count value (less than zero; `release_sem_etc()` only).

See also: `acquire_sem()`

### set_sem_owner()

          status_t set_sem_owner(sem_id sem, team_id team)

Transfers ownership of the designated semaphore to team. A semaphore can only be owned by one team at a time; by setting a semaphore's owner, you remove it from its current owner.

There are no restrictions on who can own a semaphore, or on who can transfer ownership. In practice, however, the only reason you should ever transfer ownership is if you're writing a device driver and you need to bequeath a semaphore to the kernel (the team of which is known, for this purpose, as `B_SYSTEM_TEAM`).

Semaphore ownership is meaningful for two reason:

- When a team dies (when all its threads are dead), the semaphores that are owned by that team are deleted.

- Threads can only by deleted by threads that belongs to a semaphore's owner.

To discover a semaphore's owner, use the `get_sem_info()` function.

RETURN CODES

- `B_NO_ERROR`. Ownership was successfully transferred.
- `B_BAD_SEM_ID`. Invalid sem value.
- `B_BAD_TEAM_ID`. Invalid team value.

The Be Book, in lovely HTML, for BeOS Release 3.

Copyright © 1998 Be, Inc. All rights reserved.

Last modified March 26, 1998.