Async locks and how it queues work

May 14, 2013 at 2:55 PM
I had along hard look at your implementation of AsyncLock and I have a suggestion and hope its not too late in the project.

Currently the AsyncLock.LockAsync(...) method looks like this:
public Task<IDisposable> LockAsync(CancellationToken cancellationToken)
{
    Task<IDisposable> ret = null;
    lock (_mutex)
    {
        if (!_taken)
        {
            // If the lock is available, take it immediately.
            _taken = true;
            ret = TaskEx.FromResult<IDisposable>(new Key(this));
        }
        else
        {
            // Wait for the lock to become available or cancellation.
            ret = _queue.Enqueue(cancellationToken);
        }

        Enlightenment.Trace.AsyncLock_TrackLock(this, ret);
    }

    return ret;
}
What if it could be changed with this (and I'll explain):
public Task<IDisposable> LockAsync(CancellationToken cancellationToken)
{
    Task<IDisposable> ret = _queue.Enqueue(cancellationToken);
    Enlightenment.Trace.AsyncLock_TrackLock(this, ret);

    return ret;
}
With this change the onus will fall on the implementation of the IAsyncWaitQueue<IDisposable> to complete (or "fast path") the first task in the queue and queue the following tasks. With this I feel it would be much easier (cleaner) to implement priority queues than the example you provided with AsyncPriorityLockExample

Thoughts?
Coordinator
May 15, 2013 at 12:19 AM
The IAsyncWaitQueue<T> type represents an abstract wait queue (with cancellation support) without any particular locking strategy implied.

Wait queues are not just used by AsyncLock; they are also used by AsyncAutoResetEvent, AsyncConditionVariable, AsyncSemaphore, and AsyncReaderWriterLock (which actually has four separate wait queues). So you can't assume that the first wait should be fast-pathed to completion while the others await; most of the other synchronization types do not have that semantic. (E.g., AsyncConditionVariable should never fast-path a wait to completion unless it's cancelled).

In contrast, AsyncPriorityLock<T> is just an example. I'm 95% sure I'll never support it in the official API. If you're using asynchronous synchronization and find yourself needing a prioritized lock, there is almost certainly a design problem. There are far superior solutions out there. An async-compatible producer/consumer priority queue would make sense (and AsyncEx may eventually include one), but not a prioritized lock.

But thank you for reviewing this code! I appreciate the input!

-Steve
May 17, 2013 at 8:23 AM
StephenCleary wrote:
Wait queues are not just used by AsyncLock; they are also used by AsyncAutoResetEvent, AsyncConditionVariable, AsyncSemaphore, and AsyncReaderWriterLock (which actually has four separate wait queues). So you can't assume that the first wait should be fast-pathed to completion while the others await; most of the other synchronization types do not have that semantic. (E.g., AsyncConditionVariable should never fast-path a wait to completion unless it's cancelled).
I was expecting this answer :-) But I must say that I only mentioned the "fast path" idea in the context of the AsyncLock implementation (although it is also relevant to some of the others too). However, it does not mean that my suggestion would not work with the other implementations as well, it still just depends on the implementation of the IAsyncWaitQueue<T>. Remember, nothing stops the implementation of IAsyncWaitQueue<T> from collaborating/synchronising with other queues (as it would need to do in queues passed to the constructor of the AsyncReaderWriterLock). And you could say "but that would make the correct functionality of the 'async classes' (especially AsyncReaderWriterLock) dependent on the correct implementation of IAsyncWaitQueue<T> to be passed to their constructors". Yes, that is true, but it is true for the current implementation as well. The only suggestion I have to solve that problem is to make the 'async class' constructor parameters require some implementation of a more specific abstract base class and not just any implementation of IAsyncWaitQueue<T>.

StephenCleary wrote:
In contrast, AsyncPriorityLock<T> is just an example. I'm 95% sure I'll never support it in the official API. If you're using asynchronous synchronization and find yourself needing a prioritized lock, there is almost certainly a design problem. There are far superior solutions out there. An async-compatible producer/consumer priority queue would make sense (and AsyncEx may eventually include one), but not a prioritized lock.
A prioritized lock is actually a very valid design choice. E.g. In a communication channel, messages (protocol frames) could be queued for asynchronous transmission, however some messages could have priority over others (acknowledgement messages for incoming messages must be sent out as quickly as possible as to not time out the node that sent the message). So an implementation of a channel could have a SendMessageAsync(int priority, ..., CancellationToken token) (retuning a Task<int>) method that would largely benefit from a prioritized async lock to queue concurrent calls before sending the bytes over the wire.
An async-compatible producer/consumer priority queue suggest a "fire and forget" scenario that would not work in this case, since the completion of a sent message is critical for timing of a response (i.e. a response time is measured from when the message was set over the wire and not from the time it was put on the queue). This is especially true for slow message channels like FSK radio networks or SMS.
If you say "there are far superior solutions out there", then please share!