I read the "Little Book Of Semaphores" by Allen B. Downey and realized that I have to implement a semaphore in C first, as they appear as apart of the standard library only in C 20.
I used the definition from the book:
A semaphore is like an integer, with three differences:
- When you create the semaphore, you can initialize its value to any integer, but after that the only operations you are allowed to perform are increment (increase by one) and decrement (decrease by one). You cannot read the current value of the semaphore.
- When a thread decrements the semaphore, if the result is negative, the thread blocks itself and cannot continue until another thread increments the semaphore.
- When a thread increments the semaphore, if there are other threads wait- ing, one of the waiting threads gets unblocked.
I also used the answers to the question C 0x has no semaphores? How to synchronize threads?
My implementation is a bit different from those by the link, as I unlock my mutex before notifying a thread on signalling and also the definition by the book is a bit different.
So I implemented the semaphore and now I've realized that I don't know how I can really properly test it, except for the simplest case like e.g. sequentializing two calls for two threads. Is there any way to test the implementation like kinda using 100 threads or something like this and having no deadlock? I mean what test I should write to check the implementation? Or if the only way to check is to look through the code attentively, could you, maybe, please check?
My implementation:
// semaphore.h
#include <condition_variable>
#include <mutex>
namespace Semaphore
{
class CountingSemaphore final
{
public:
explicit CountingSemaphore(int initialValue = 0);
void signal();
void wait();
private:
std::mutex _mutex{};
std::condition_variable _conditionVar{};
int _value;
};
} // namespace Semaphore
// semaphore.cpp
#include "semaphore.h"
namespace Semaphore
{
CountingSemaphore::CountingSemaphore(const int initialValue) : _value(initialValue) {}
void CountingSemaphore::signal()
{
std::unique_lock<std::mutex> lock{_mutex};
_value;
if (0 == _value)
{
lock.unlock();
_conditionVar.notify_one();
}
}
void CountingSemaphore::wait()
{
std::unique_lock<std::mutex> lock{_mutex};
--_value;
if (0 > _value)
{
_conditionVar.wait(lock, [this]() { return (0 <= this->_value); });
}
}
} // namespace Semaphore
CodePudding user response：
This code is broken. Your current state machine uses negative numbers to indicate a number of waiters, and non-negative indicates remaining capacity (with 0 being no availability, but no waiters either).
Problem is, you only notify waiters when the count becomes zero. So if you had a semaphore with initial value 1 (basically a logical mutex), and five threads try to grab it, one gets it, and four others wait, at which point value is -4. When the thread that grabbed it finishes and signals, value rises to -3, but that's not 0, so notify_one is not called.
In addition, you have some redundant code. The predicate-based form of std::condition_variable's wait is equivalent to:
while (!predicate()) {
wait(lock);
}
so your if check is redundant (wait will check the same information before it actually waits, even once, anyway).
You could also condense the code a bit by having the increment and decrement on the same line you test them (it's not necessary since you're using mutexes to protect the whole block, not relying on atomics, but I like writing threaded code in a way that would be easier to port to atomics later, mostly to keep in the habit when I write actual atomics code). Fixing the bug and condensing the code gets this end result:
void CountingSemaphore::signal()
{
std::unique_lock<std::mutex> lock{_mutex};
if (0 >= _value) // If we were negative, had at least one waiter, notify one of them; personally, I'd find if (value < 0) clearer as meaning "if value *was* less than 0, and also increment it afterwards by side-effect, but I stuck to something closer to your design to avoid confusion
{
lock.unlock();
_conditionVar.notify_one();
}
}
void CountingSemaphore::wait()
{
std::unique_lock<std::mutex> lock{_mutex};
--_value;
_conditionVar.wait(lock, [this]() { return 0 <= this->_value; });
}
The alternative approach would be adopting a design that doesn't drop the count below 0 (so 0 means "has waiters" and otherwise the range of values is just 0 to initialValue). This is safer in theoretical circumstances (you can't trigger wraparound by having 2 ** (8 * sizeof(int) - 1) waiters). You could minimize that risk by making value a ssize_t (so 64 bit systems would be exponentially less likely to hit the bug), or by changing the design to stop at 0:
// value's declaration in header and argument passed to constructor may be changed
// to an unsigned type if you like
void CountingSemaphore::signal()
{
// Just for fun, a refactoring to use lock_guard rather than unique_lock
// since the logical unlock is unconditionally after the value read/modify
int oldvalue; // Type should match that of value
{
std::lock_guard<std::mutex> lock{_mutex};
oldvalue = value ;
}
if (0 == oldvalue) _conditionVar.notify_one();
}
void CountingSemaphore::wait()
{
std::unique_lock<std::mutex> lock{_mutex};
// Waits only if current count is 0, returns with lock held at which point
// it's guaranteed greater than 0
_conditionVar.wait(lock, [this]() { return 0 != this->_value; });
--value; // We only decrement when it's positive, just before we return to caller
}
This second design has a minor flaw, in that it calls notify_one when signaled with no available resources, but no available resources might mean "has waiters" or it might mean "all resources consumed, but no one waiting". This isn't actually a problem logically speaking though; calling notify_one with no waiters is legal and does nothing, though it may be slightly less efficient. Your original design may be preferable on that basis (it doesn't notify_one unless there were definitely waiters).