Windows System Programming Third Edition [Electronic resources] نسخه متنی

Semaphores

Semaphores, the second of the three kernel synchronization objects, maintain a count, and the semaphore object is signaled when the count is greater than 0. The semaphore object is unsignaled when the count is 0.

Threads or processes wait in the normal way, using one of the wait functions. When a waiting thread is released, the semaphore's count is decremented by 1.

The semaphore functions are CreateSemaphore, OpenSemaphore, and ReleaseSemaphore, which can increment the count by 1 or more. These functions are similar to their mutex counterparts.

HANDLE CreateSemaphore (
LPSECURITY_ATTRIBUTES lpsa,
LONG lSemInitial,
LONG lSemMax,
LPCTSTR lpSemName)

lSemMax, which must be 1 or greater, is the maximum value for the semaphore. lSemInitial, with 0 lSemInitial lSemMax, is the initial value, and the semaphore value is never allowed to go outside this range. A NULL return value indicates failure.

It is possible to decrease the count only by 1 with any given wait operation, but a semaphore release can increment its count by any value up to the maximum.

BOOL ReleaseSemaphore (
HANDLE hSemaphore,
LONG cReleaseCount,
LPLONG lpPreviousCount)

Notice that you can find the count preceding the release, but the pointer can be NULL if this value is not needed.

The release count must be greater than 0, but if it would cause the semaphore count to exceed the maximum, the call will fail, returning FALSE, and the count will remain unchanged. Use the previous count value with caution as the semaphore count can also be changed by other threads. Also, you cannot determine whether the count is at its maximum as there is no legal release count. An example in the Web site code demonstrates using the previous count.

While it is tempting to think of a semaphore as a special case of a mutex with a maximum value of 1, this would be misleading because there is no ownership of a semaphore. Any thread can release a semaphore, not just the one that performed the wait. Likewise, since there is no ownership, there is no concept of an abandoned semaphore.

Using Semaphores

The classic semaphore application regards the semaphore count as representing the number of available resources, such as the number of messages waiting in a queue. The semaphore maximum then represents the maximum queue size. Thus, a producer would place a message in the buffer and call ReleaseSemaphore, usually with a release count of 1. Consumer threads would wait on the semaphore, consuming a message and decrementing the semaphore count.

Another important use is described in the discussion following Program 9-1, where a semaphore can be used to limit the number of worker threads actually running at any one time, thereby decreasing contention between threads and, in some cases, improving performance. Chapter 9 discusses this technique, using a semaphore throttle.

The potential race condition in sortMT (Program 7-2) illustrates another use of a semaphore to control the exact number of threads to wake up. All the threads could be created without being suspended. All of them would immediately wait on a semaphore initialized to 0. The boss thread, rather than resuming the threads, would simply call ReleaseSemaphore with a count of 4 (or whatever the number of threads is), and the four threads could then proceed.

While semaphores can be convenient, they are redundant in the sense that mutexes and events (described in the next major section), used together, are more powerful than semaphores. See Chapter 10 for more information.

A Semaphore Limitation

There is still an important limitation with the Windows semaphore implementation. How can a thread request that the count be decremented by 2? The thread can wait twice in succession, as shown below, but this would not be an atomic operation because the thread could be preempted between waits. A deadlock could result, as described next.

/* hsem is a semaphore handle.
The maximum semaphore count is 2. */
...
/* Decrement the semaphore by 2. */
WaitForSingleObject (hSem, INFINITE);
WaitForSingleObject (hSem, INFINITE);
...
/* Release two semaphore counts. */
ReleaseSemaphore (hSem, 2, &PrevCount);

To see how a deadlock is possible in this situation, suppose that the maximum and original semaphore counts are set to 2 and that the first of two threads completes the first wait and is then preempted. A second thread could then complete the first wait, reducing the count to 0. Both threads will block forever because neither will be able to get past the second wait. This simple deadlock situation is typical.

A possible correct solution, shown in the following code fragment, is to protect the waits with a mutex or CRITICAL_SECTION.

/* Decrement the semaphore by 2. */
EnterCriticalSection (&csSem);
WaitForSingleObject (hSem, INFINITE);
WaitForSingleObject (hSem, INFINITE);
LeaveCriticalSection (&csSem);
...
ReleaseSemaphore (hSem, 2, &PrevCount);

Even this implementation, in general form, is limited. Suppose, for example, that the semaphore has two remaining units, and that Thread A needs three units and Thread B needs just two. If Thread A arrives first, it will complete two waits and block on the third while owning the mutex. Thread B, which only needs the two remaining units, will still be blocked.

Another proposed solution would be to use WaitForMultipleObjects with the same semaphore handle used several times in the handle array. This suggestion fails for two reasons. First, WaitForMultipleObjects will return an error if it detects two handles for the same objects. What is more, the handles would all be signaled, even if the semaphore count were only 1, which would defeat the purpose.

Exercise 1011 provides a complete solution to this multiple-wait problem.

The Windows semaphore design would be more convenient if we could perform an atomic multiple-wait operation.