4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I think part of the confusion might be that there are 2 equivalent definitions for the wait operation: 1) decrement and if the new value is < 0, wait. 2) Wait until the value > 0, then decrement. The two are equivalent, but with the former your semaphore can take on negative values, while with the latter it does not. This can lead to confusion if you say a binary semaphore has 2 states, when under the former definition it does not seem to (if you have multiple waiters, the value keeps going negative). $\endgroup$
    – 1110101001
    Sep 21, 2023 at 4:57
  • $\begingroup$ So a binary semaphore just has a max value of 1, and the fact that you do not exceed this is simply an invariant. Note even under the former definition you could imagine a restricted counting semaphore which can take on 0 and 1, i.e. just one waiter. This gives you a signaling primitive, and you can build a wait queue to get back to a traditional binary semaphore (multiple waiters, max value 1), with which you can then build a counting semaphore (can increment beyond 1). $\endgroup$
    – 1110101001
    Sep 21, 2023 at 4:57

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.