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.

Circumvolution

Relevant: #3798392 – Replay

Answer 1

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();
        }
    }
}

Circumvolution

Answer 2

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.

Lowgrade

This doesn't answer OP question - I'm trying to design a data-structure around a stack that blocks until the stack has an item available. – Eckstein

No it doesn't particularly - which is why I noted he/she might just be wanting to understand what's going on. If they are actually trying to create this structure to use though the better option is to use the blocking collection (if using .net4). Creating blocking collections is hard to get right and very easy to get wrong in subtle ways. – Lowgrade

That's exactly what the blocking collection does. You call Take() on it and it blocks until there is something available to take from the underlying collection. – Lowgrade

I should have mentioned that this is for Silverlight. Edited. – Circumvolution

@Circumvolution Actually that sounds like a good solution, you can implement stack on top of BlockingCollection using Take method – Eckstein

That's a shame about silverlight - the BlockingCollection is REALLY useful. I actually just ran your code after staring at it for a while and not being to see how you could take something when the stack is empty. Works fine for me. Are you getting an exception? As it stands you wont be able to retrieve the initial values from the stack until the first time something is added, and AutoResetEvents are notorious for not doing what you would expect, but it seems like it should work. – Lowgrade

Yeah, I'm getting an exception thrown by trying to pop an empty stack. Basically, my AutoResetEvent is signaled and I grab my lock on the _internalStack but it's count is 0. I thought it looked pretty good, myself, but apparently not, haha. I'm guessing it is an implementation detail of the AutoResetEvent. Too bad SL doesn't have a Semaphore, either. – Circumvolution

Ugh. Realised I didn't quite have it right the first time. I actually had to get out of bed and think this through because it just kept going round in my head. Pretty sure I have it this time. I hope so, could really do with some sleep :) – Lowgrade

Answer 3

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);
        }
    }
}

Profit

Doesn't work, call Push, Pop, Pop, Push and observe the deadlock. – Replay

@HansPassant, Why would you call Push, Pop, Pop, Push on a single thread? Do you expect it to call Push somehow on the same thread, although Pop is blocking the thread? – Profit

@HansPassant, Please see update, and see if I got it right this time :) – Profit

Note the while loop in the post I linked, required when there's more than one consumer thread. – Replay

@HansPassant, I'm not sure why you want a while loop... Could you please elaborate? – Profit