|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
a boring naive synchronized implementation.
There's a race condition in my design of the lockless data structure. I haven't been able to come up with a lockless algorithm that actually works, and the naive one seems to be fine. In Blaze's usage, performance actually isn't super important so the naive implementation is fine.
Consider three threads and a MultisetSemaphore with 2 max unique values.
T1: acquireAll({a, b})
T2: acquireAll({a, c})
T3: acquireAll({a, d})
For the for-loop before the 'acquire' call, suppose:
-T1 wins the race to acquire 'a' [1] and also wants to acquire 'b' [1]
-T2 loses the race to acquire 'a' [2] and also wants to acquire 'c' [1]
-T3 loses the race to acquire 'a' [2] and also wants to acquire 'd' [1]
So then in [3] we have:
-T1 tries to acquire 2 permits
-T2 tries to acquire 1 permit
-T3 tries to acquire 1 permit
Suppose the execution order in [3] is T2, T3, T1. So that means we then have T1 still at [3] and both T2 and T3 at [4], which is a deadlock.
[1] https://github.com/bazelbuild/bazel/blob/fa96b04f6c8ca6b6b3464727672267133e852959/src/main/java/com/google/devtools/build/lib/concurrent/MultisetSemaphore.java#L184
[2] https://github.com/bazelbuild/bazel/blob/fa96b04f6c8ca6b6b3464727672267133e852959/src/main/java/com/google/devtools/build/lib/concurrent/MultisetSemaphore.java#L191
[3] https://github.com/bazelbuild/bazel/blob/fa96b04f6c8ca6b6b3464727672267133e852959/src/main/java/com/google/devtools/build/lib/concurrent/MultisetSemaphore.java#L199
[4] https://github.com/bazelbuild/bazel/blob/fa96b04f6c8ca6b6b3464727672267133e852959/src/main/java/com/google/devtools/build/lib/concurrent/MultisetSemaphore.java#L210
--
PiperOrigin-RevId: 148272171
MOS_MIGRATED_REVID=148272171
|