Home > Software engineering >  Find bug on below semaphore implementation using monitor
Find bug on below semaphore implementation using monitor

Time:09-28

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 call Signal 1000 times and have 1000 additional capacity.
  • integer overflow is not handled. If you put int.MaxValue as the initial capacity and then Signal, your current capacity will be at int.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--;
}
  • Related