A semaphore is a counter that takes positive integer values called units. Threads release units to and wait for units from the semaphore. A semaphore can:

Creating a semaphore

High-level semaphores

You specify these parameters when creating a high-level semaphore using CreateRtSemaphore:

• The initial number of units in the custody of the new semaphore.
• The maximum number of units the semaphore can have in custody at any given time. The lower limit is automatically 0 (zero).
• Whether the thread queue is FIFO or priority-based.

Low-level semaphores

Create low-level semaphores with knCreateRtSemaphore. To create a low-level semaphore specify:

• The memory area for the semaphore object.
• The type (priority-based or FIFO thread queue, or region semaphore).
• The initial number of units in the semaphore, 0 or 1. If a region is created with 0 initial units, the creating thread owns the region and other threads cannot use the region until the creating thread releases a unit.

To provide additional units to a low-level semaphore after creation, use knReleaseRtSemaphore once for each additional unit you need. Low-level region semaphores cannot accept more than one unit.

Thread queue

Use a priority-based queue so high-priority threads do not wait behind lower-priority threads in the queue. Within a priority-based queue, threads of equal priority are queued in FIFO order.

For more information, see Priority bottlenecks and blocking.

Deleting a semaphore

High-level semaphores

When you use DeleteRtSemaphore, the RT kernel awakens any threads waiting for units at the semaphore with an E_EXIST condition code.

Low-level semaphores

Delete low-level semaphores with knDeleteRtSemaphore. If a low-level semaphore is deleted, all threads in the semaphore's thread queue are awakened with an E_KN_NONEXIST status code.

Binary semaphores and mutual exclusion

If a thread waits for a unit from a binary (single-unit) semaphore to gain access to a resource and a unit is not available, it means some other thread is using the resource. The requesting thread cannot access the resource until the unit is released.

The following figure illustrates a binary semaphore guarding a resource. Threads queue up for access to the resource.

Create the semaphore with one initial unit and a maximum of one unit, using CreateRtSemaphore.

• Thread A waits for a unit from the semaphore using WaitForRtSemaphore and receives it. Thread B also waits for a unit from the semaphore using WaitForRtSemaphore and specifies it is willing to wait. Thread B goes to sleep by waiting in the queue until thread A has released the unit.
• Thread A accesses the resource. No other thread should access the resource at the same time. When thread A is done using the resource, it releases the unit to the semaphore using ReleaseRtSemaphore.
• Now thread B wakes up and receives the unit. If thread B has a higher priority than thread A, it begins running. Otherwise it will be ready.

Priority bottlenecks and blocking

You may encounter several problems when you use semaphores for mutual exclusion of shared data. To eliminate the problems, use regions rather than semaphores to control shared resources.

The first bottleneck is a high-priority ready thread blocked by a lower-priority running thread. This occurs if the lower-priority thread obtained the required units before the higher-priority thread became ready. The running thread, regardless of priority, controls the resource until it releases the units to the semaphore.

The second bottleneck, priority inversion, occurs when a low-priority thread obtains the required units to access a resource, then is preempted by a medium-priority thread, which is then preempted by a high-priority thread that needs to access the resource. This shows what could happen:

1. Low-priority thread A is running and obtains a unit from a binary semaphore to access some data. It starts accessing the data.
2. Thread B, a medium priority thread, preempts A.
3. Higher-priority thread C preempts B, but cannot access the data while the low-priority thread holds the unit. The low-priority thread A cannot complete its operation and return the unit because it is preempted by B.

The third bottleneck occurs when a thread holding a semaphore unit and using shared data is suspended or deleted, and no other thread can gain access to the shared data. Only after the suspended thread resumes and releases the unit to the semaphore can the other threads use the data. In the case of a deleted thread, the semaphore prevents any other threads from ever using the shared data.

Low-level calls

The same priority bottleneck and inversion problems may arise when using non-region low-level semaphores. Low-level region semaphores, like RT regions, provide dynamic priority adjustment to avoid blocking a high priority thread.

Multi-unit semaphores

You typically use a multi-unit semaphore as a counter, for example, managing the available space in a circular buffer. A thread can wait for more than one unit from a multi-unit semaphore and the semaphore tries to satisfy the request.

The semaphore either sends all the requested units or none at all. So, a multi-unit semaphore might have threads waiting for units and also have units available, but not enough to satisfy the thread at the head of the thread queue. This is a possible scenario:

Two queued threads wait for units:

• Thread A, first in the queue, wants three units.
• Thread B, second in the queue, wants one unit.

  The semaphore has zero units available when the requests are made.

These are possible outcomes for a FIFO queue:

• The semaphore receives three units. Thread A receives the units, awakens and runs while B remains asleep in the queue.
• The semaphore receives two units. Both threads remain asleep. There aren't enough units for thread A, and thread B's request cannot be satisfied because thread A is still ahead of it in the queue.
• The semaphore receives four units. Both thread A and thread B receive their requested units and awaken. Thread A runs first because it is first in the queue.

These are possible outcomes for a priority queue, with thread B having a higher priority than A:

• The semaphore receives two or three units. Thread B receives a unit, awakens and runs while A remains asleep in the queue.
• The semaphore receives four units. Both A and B receive their requested units and awaken. Thread B runs first because it is higher priority.

The next figure shows how threads can share a fixed-length list of buffers using two semaphores: one binary and one multi-unit counting semaphore.

• The binary semaphore prevents two different threads taking buffers from the list at the same time.
• The counting semaphore prevents a thread from spending time searching the list for an available buffer when there is none.

Create a binary semaphore B that provides mutually-exclusive access to the buffer list using CreateRtSemaphore.

Create a counting semaphore C that tracks the number of available buffers, eight in this example, using CreateRtSemaphore. Set the initial units and maximum units equal to the number of buffers: eight.

1. Thread A requests the only unit from semaphore B using WaitForRtSemaphore. The semaphore sends the unit. Now, only thread A can request units from semaphore C.
2. Thread A requests three units from semaphore C using WaitForRtSemaphore. The semaphore sends the units. Now thread A has access to three buffers in the shared list. Thread A then returns the unit to semaphore B using ReleaseRtSemaphore.
3. Thread D requests the unit from semaphore B using WaitForRtSemaphore and receives it.
4. Thread D can now request four units from semaphore C. Since the semaphore has enough remaining units to satisfy the request, thread D receives them. If it had not, D would have waited.

All threads should return their units to C as soon as possible to free resources for other threads.

Sending and receiving low-level semaphore units

Wait for a unit from a semaphore with knWaitForRtSemaphore. You must repeat the call for each unit you need. If the semaphore contains units, the unit count decrements by one and the thread proceeds. If the semaphore has no units and the thread can wait, the thread goes to sleep in the semaphore's thread queue. Release a unit to a semaphore with knReleaseRtSemaphore. If threads wait at the semaphore, the thread at the head of the queue awakens.

Using low-level region semaphores

A low-level region semaphore can provide mutual exclusion and synchronization. If a thread must get a unit from a region before entering a critical section, and if it returns the unit when leaving the area, only one thread ever executes in the critical section at a time. Low-level region semaphores contain a maximum of one unit and support priority adjustment.

Low-level region semaphores are similar to RT regions. RT regions additionally protect a thread inside the region from suspension or deletion.

System calls

This lists common operations on semaphores and the semaphore system calls that do the operations:

Follow these semaphore rules:

• A thread does not have to wait for a unit from a semaphore in order to release a unit to it.
• A semaphore cannot wait for more units than the maximum specified when it was created.

This figure shows the order in which you make semaphore system calls.

This shows the order to make semaphore system calls and lists calls that semaphores frequently use:

1. Make these calls from the thread that has the resource that needs to be shared.
2. Make these calls from the threads that need to use the resource.
3. Make these calls from the thread that created the semaphore.