In an interview was asked to identify bug in the below code , if there is any.
Below class implements semaphore with certain capacity.
public class MySemaphore
{
private object _mutex = new object();
private int _currAvail;
public MySemaphore(int capacity)
{
_currAvail = capacity;
}
public void Wait()
{
lock (_mutex)
{
if (_currAvail == 0) Monitor.Wait(_mutex);
_currAvail--;
}
}
public void Signal()
{
lock (_mutex) {
_currAvail ;
Monitor.Pulse(_mutex);
}
}
}
CodePudding user response:
Problems with this Semaphore that I can see:
capacity
is actually just initial capacity, not a total capacity. Therefore one can just callSignal
1000 times and have 1000 additional capacity.- integer overflow is not handled. If you put
int.MaxValue
as the initial capacity and thenSignal
, your current capacity will be atint.MinValue
. - the constructor doesn't check if the passed-in int is negative
CodePudding user response:
Full disclosure: I don't use C#. I am not familiar with Monitor.Wait(o)
and Monitor.Pulse(o)
, but I believe that _currAvail
could go negative if two or more threads are allowed to simultaneously call sema.Wait()
.
Suppose that thread A and thread C concurrently call sema.Wait()
while thread B calls sema.Signal()
. Here's what I think could happen:
currAvail mutex Thread A Thread B Thread C
--------- ----- ------------- -------------- --------------
0 free lock(mutex) . .
0 A Await Pulse() Await mutex .
0 free '' '' lock(mutex) .
0 B '' '' currAvail Await mutex
1 B '' '' Pulse() '' ''
1 B Await mutex release(mutex) '' ''
1 free '' '' . lock(mutex)
1 C '' '' . curAvail--
0 C '' '' . release(mutex)
0 free '' '' . .
0 free lock(mutex) . .
0 A currAvail-- . .
-1 A release(mutex) . .
-1 free . . .
The fix is to re-check _currAvail
after Monitor.Wait(_mutex)
returns. I.e., call Monitor.Wait(_mutex)
in a loop:
lock (_mutex) {
while (_currAvail == 0) Monitor.Wait(_mutex);
_currAvail--;
}