AutoResetEvent and multiple Sets

Question

I'm trying to design a data-structure around a stack that blocks until the stack has an item available. I tried using an AutoResetEvent but I think I misunderstood how that synchronization process works. Basically, looking at the following code, I am trying to Pop from stack when there's nothing available.

It seems that the AutoResetEvent is behaving like a semaphore. Is that correct? Can I just get rid of the Set() in BlockingStack.Get() and be done with it? Or will that result in a situation where I'm only using one of my stack items.

public class BlockingStack
{
    private Stack<MyType> _internalStack;
    private AutoResetEvent _blockUntilAvailable;

    public BlockingStack()
    {
        _internalStack = new Stack<MyType>(5);
        _blockUntilAvailable = new AutoResetEvent(false);

        for (int i = 0; i < 5; ++i)
        {
            var obj = new MyType();
            Add(obj);
        }
    }

    public MyType Get()
    {
        _blockUntilAvailable.WatiOne();

        lock (_internalStack)
        {
            var obj = _internalStack.Pop();
            if (_internalStack.Count > 0)
            {
                _blockUntilAvailable.Set(); // do I need to do this?
            }

            return obj;
        }
    }

    public void Add(MyType obj)
    {
        lock (_internalStack)
        {
            _internalStack.Push(obj);
            _blockUntilAvailable.Set();
        }
    }
}

My assumption was the AutoResetEvent resets for all waiting threads when one gets through on the WaitOne() function call. However, it seems that multiple threads are getting in. Unless I've messed up my logic somewhere.

EDIT: This is for Silverlight.

Answer 1

You'd be better off using a blocking collection unless you're just trying to understand how threading works. This would give you a blocking collection backed by a stack:

ConcurrentStack<SomeType> MyStack = new ConcurrentStack<SomeType>();
BlockingCollection<SomeType> SharedStack = new BlockingCollection<SomeType>(MyStack)

You can then access it in a threadsafe fashion with all the blocking done properly for you. See here

You can use the sharedStack by calling sharedStack.Take() which would then block on the take until there is something to take from the stack.

---

Edit: Took me a while (and two tries) but I've worked out your issue I think.

Consider an empty stack with 3 threads waiting on the event.

Add is called, the stack has one object and one thread is allowed through the event.

Immediately Add is called again.

The first thread through now waits to get the lock from the Add.

The Add adds a second object to the stack and lets another thread through the event.

Now two objects on stack and 2 threads through the event, both waiting on the lock.

First Get thread now takes lock and pops. Sees one object on the stack still and CALLS SET.

Third thread allowed though the event.

Second Get thread now takes lock and pops. Sees nothing in stack and does not call set.

BUT. It's too late. The third thread has already been allowed through, so when the second thread relinquishes the lock the third thread tries to pop from an empty stack and throws.

Answer 2

No, your current code makes no sense. At the moment you're blocking the thread everytime the Get method is invoked (the .WaitOnecall).

You probably want something like:

public class BlockingStack<T>
{
    private Stack<T> _internalStack;
    private AutoResetEvent _blockUntilAvailable;

    public BlockingStack()
    {
        _internalStack = new Stack<T>(5);
        _blockUntilAvailable = new AutoResetEvent(false);
    }

    public T Pop()
    {
        lock (_internalStack)
        {
            if (_internalStack.Count == 0)
                _blockUntilAvailable.WaitOne();

            return _internalStack.Pop();
        }
    }

    public void Push(T obj)
    {
        lock (_internalStack)
        {
            _internalStack.Push(obj);

            if(_internalStack.Count == 0)
                _blockUntilAvailable.Set();
        }
    }
}

The idea is that, if the current number of items in the _internalStack is 0, then it should wait for a signal from the Push method. Once it's signaled, it moves on and pops an item from the stack.

---

EDIT: There's 2 problems with the code above:

1. Whenever Pop blocks with .WaitOne, it doesn't release the lock on _internalStack, and therefore Push can never obtain the lock.

2. When Pop is called multiple times on the same thread, they share the same initialState for the AutoResetEvent - ex. Push signals the AutoResetEvent when an item is added. Now when I Pop an item it works fine the first time, since there's actually an item in the Stack. However the second time, there's no value in the Stack so it waits by calling .WaitOne on the AutoResetEvent - but since the call to Push signaled this event, it'll just return true, and not wait as expected.

An (working) alternative:

public class BlockingStack<T>
{
    private Stack<T> _internalStack;

    public BlockingStack()
    {
        _internalStack = new Stack<T>(5);
    }

    public T Pop()
    {
        lock (_internalStack)
        {
            if (_internalStack.Count == 0)
                Monitor.Wait(_internalStack);

            return _internalStack.Pop();
        }
    }

    public void Push(T obj)
    {
        lock (_internalStack)
        {
            _internalStack.Push(obj);
            Monitor.Pulse(_internalStack);
        }
    }
}

Answer 3

I did not verify the Monitor based solution, but I did write a semaphore-based solution that appears to be working:

public class Semaphore
{
    private int _count;
    private int _maximum;
    private object _countGuard;

    public Semaphore(int maximum)
    {
        _count = 0;
        _maximum = maximum;
        _countGuard = new object();
    }

    public void WaitOne()
    {
        while (true)
        {
            lock (_countGuard)
            {
                if (_count < _maximum)
                {
                    _count++;
                    return;
                }
            }
            Thread.Sleep(50);
        }
    }

    public void ReleaseOne()
    {
        lock (_countGuard)
        {
            if (_count > 0)
            {
                _count--;
            }
        }
    }
}

public class BlockingStack
{
    private Stack<MyType> _internalStack;
    private Semaphore _blockUntilAvailable;

    public BlockingStack()
    {
        _internalStack = new Stack<MyType>(5);
        _blockUntilAvailable = new Semaphore(5);

        for (int i = 0; i < 5; ++i)
        {
            var obj = new MyType();
            Add(obj);
        }
    }

    public MyType Get()
    {
        _blockUntilAvailable.WaitOne();

        lock (_internalStack)
        {
            var obj = _internalStack.Pop();
            return obj;
        }
    }

    public void Add(MyType obj)
    {
        lock (_internalStack)
        {
            _internalStack.Push(obj);
            _blockUntilAvailable.ReleaseOne();
        }
    }
}