tree 7acf4b89cca4def92dced93a24e9daa45f372ee3
parent 57cc36454da6851ecd2a00abe7cfd6ee6e06928f
author dkhalanskyjb <52952525+dkhalanskyjb@users.noreply.github.com> 1567518203 +0300
committer Roman Elizarov <elizarov@gmail.com> 1567518203 +0300

Fix of a bug in the semaphore (#1477)

* Add a failing test for a semaphore

This test consistently fails for the current implementation. It
attempts to cause the following state: after `job2` increments
`availablePermits` but before it wakes up the acquirer in the
queue, the acquirer is cancelled. Then, regardless of whether
`RESUMED` or `CANCELLED` was written first, another cell in the
queue is marked to be resumed. However, this is incorrect: on
cancellation, the acquirer incremented the number of available
permits once more, making it `1`; thus, at the same time there
exist two permits for acquiring the mutex. At the next loop
iteration, a new acquirer tries to claim ownership of the mutex and
succeeds because it goes to the thread queue and sees its cell as
`RESUMED`. Thus, two entities own a mutex at the same time.

* Fix a bug in semaphore implementation

The fix works as follows: if `availablePermits` is negative, its
absolute value denotes the logical length of the thread queue.
Increasing its value if it was negative means that this thread
promises to wake exactly one thread, and if its positive, returns
one permit to the semaphore itself.

Before, the error was in that a queue could be of negative length:
if it consisted of only `N` cells, and `N` resume queries arrived,
cancelling any threads would mean that there are more wakers then
there are sleepers, which breaks the invariants of the semaphore.
Thus, if on cancellation the acquirer detects that it leaves the
queue empty in the presence of resumers, it simply transfers the
semaphore acquisition permit to the semaphore itself, because it
knows that it, in a sense, owns it already: there is a thread that
is bound to resume this cell.