Using a counting semaphore as a binary semaphore

Question

Are there any methods, so that I can use a counting semaphore as a binary semaphore?

A binary semaphore should have two possible states: 0 and 1. The operation wait() should atomically look at the state, if the state is > 0, the state should be decremented and the process should continue. If the state is 0, the process should be atomically placed on a queue of waiters and the process should block. The operation signal() should atomically look at the state, if the state is 0, and there are processes blocked, exactly one of them should be woken. If there are no blocked processes the value of the semaphore should be set to 1.

I specifically need a binary semaphore, not a mutex. A mutex assumes ownership: that a processes will first lock and then after a resource is used, the process will unlock the mutex. But in my case there are some processes that will only do semaphore signal() operation, without ever performing a wait() operation.

How can I make sure that the value of the counting semaphore never goes above 1?

I asked a similar question, on Stack Overflow, specifically about solving this problem with the POSIX synchronization APIs, but the suggestion I got there was to use file locking, which is much slower than semaphores, and also seems to have the mutex semantics I can't use.

Answer 1

A binary semaphore is just a semaphore whose values are limited to 0 and 1 (locked and unlocked; when locked there can be an unlimited queue of tasks waiting). When using such a semaphore you have to be careful never to increment it past 1. The point is that if the values are thus limited, some tricks are possible that speed up the implementation quite a bit, and this is also the most common use (think using the semaphore as a mutex). There is no real conceptual difference involved.

If you want a detailed discussion of the use of semaphores and other synchronization primitives (with some implementation discussion) see Downey's "Little Book of Semaphores". The Linux kernel used to have highly optimized semaphore implementations for contemplation, but they were removed a while back.