This is the thirteenth part of the Async Wandering series. For your convenience you can find other parts in the table of contents in Part 1 – Why creating Form from WinForms in unit tests breaks async?
Today I’ll discuss some misconception regarding the reentrant recursive async lock described in this article.
It shows the following code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
AsyncLock _asyncLock = new AsyncLock(allowReentry: true); int CurrentThreadId => Thread.CurrentThread.ManagedThreadId; async Task MainAsync() { using (await _asyncLock.LockAsync()) { Console.WriteLine($"1. {nameof(MainAsync)} starting on thread {CurrentThreadId}"); var childTask = ChildAsync(delay: TimeSpan.FromMilliseconds(100)); await Task.Delay(TimeSpan.FromMilliseconds(101)).ConfigureAwait(false); Console.WriteLine($"4. {nameof(MainAsync)} continuing on thread {CurrentThreadId}"); NonThreadSafe(); Console.WriteLine($"6. {nameof(MainAsync)} finished {nameof(NonThreadSafe)}"); await childTask; } } async Task ChildAsync(TimeSpan delay) { Console.WriteLine($"2. {nameof(ChildAsync)} starting on thread {CurrentThreadId}"); await Task.Delay(delay).ConfigureAwait(false); using (await _asyncLock.LockAsync()) { Console.WriteLine($"3. {nameof(ChildAsync)} continuing on thread {CurrentThreadId}"); NonThreadSafe(); Console.WriteLine($"5. {nameof(ChildAsync)} finished {nameof(NonThreadSafe)}"); } } |
with the following output:
|
1 2 3 4 5 6 |
1. MainAsync starting on thread 1 2. ChildAsync starting on thread 1 3. ChildAsync continuing on thread 2 4. MainAsync continuing on thread 3 5. ChildAsync finished NonThreadSafe 6. MainAsync finished NonThreadSafe |
and concludes that the reentrant recursive async lock is impossible. Sounds plausible but the code is simply incorrect.
The code tries to get the lock in a recursive manner but mixes two contradictory requirements. It effectively wants the lock to be recursive and to be non-recursive at the same time.
Why? Let’s say that the lock is indeed possible and it works okay. With all the sleeping around, we may get the following order of events:
|
1 2 3 4 |
Main triggers ChildAsync. ChildAsync goes to sleep in line 26. Main goes to sleep in line 11. Because of scheduling and clock imprecision - main wakes up earlier in line 11. |
What can happen next? If main goes to the NonThreadSafe then we don’t want the child to take the lock. But we wanted the lock to be reentrant recursive so that’s against the rules. The child should be allowed to take the lock.
But let’s say that what we meant is that only one execution context can get the lock and that execution context is allowed to take it recursively. In that case, we want the main to finish the NonThreadSafe and then wait for the child to complete in line 18. But this line is still inside the critical section so the child shouldn’t be allowed to take the lock as it’s in a different execution context. But since we wait for the child to complete — we just get a deadlock.
The code is incorrect, that’s all. Let’s make it a little better:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
AsyncLock _asyncLock = new AsyncLock(allowReentry: true); int CurrentThreadId => Thread.CurrentThread.ManagedThreadId; async Task MainAsync() { using (await _asyncLock.LockAsync()) { Console.WriteLine($"1. {nameof(MainAsync)} starting on thread {CurrentThreadId}"); var childTask = ChildAsync(delay: TimeSpan.FromMilliseconds(100)); await Task.Delay(TimeSpan.FromMilliseconds(101)).ConfigureAwait(false); Console.WriteLine($"4. {nameof(MainAsync)} continuing on thread {CurrentThreadId}"); using (await _asyncLock.LockAsync()) { NonThreadSafe(); } Console.WriteLine($"6. {nameof(MainAsync)} finished {nameof(NonThreadSafe)}"); await childTask; } } async Task ChildAsync(TimeSpan delay) { Console.WriteLine($"2. {nameof(ChildAsync)} starting on thread {CurrentThreadId}"); await Task.Delay(delay).ConfigureAwait(false); using (await _asyncLock.LockAsync()) { Console.WriteLine($"3. {nameof(ChildAsync)} continuing on thread {CurrentThreadId}"); NonThreadSafe(); Console.WriteLine($"5. {nameof(ChildAsync)} finished {nameof(NonThreadSafe)}"); } } |
The difference is in line 14 — we take the lock in the main context again.
Can we now implement such a lock? The answer is — yes. Here it goes:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
class AsyncLock : IAsyncDisposable { private object locker = new object(); private string path = ""; private AsyncLocal<string> contextPath; private Random random = new Random(); private List<TaskCompletionSource> waiters = new List<TaskCompletionSource>(); public AsyncLock(){ contextPath = new AsyncLocal<string>(); contextPath.Value = ""; } public Task<IAsyncDisposable> LockAsync(){ bool taken = false; TaskCompletionSource waiter = null; while(!taken){ lock(locker){ char nextCharacter = (char)((int)'a' + random.Next('z' - 'a')); if(contextPath.Value == path){ path = path + nextCharacter; contextPath.Value = path; taken = true; }else{ waiter = new TaskCompletionSource(TaskCreationOptions.RunContinuationsAsynchronously); waiters.Add(waiter); } } if(!taken && waiter != null){ return waiter.Task.ContinueWith(t => LockAsync()).Result; } } return Task.FromResult((IAsyncDisposable)this); } public ValueTask DisposeAsync (){ lock(locker){ if(path.Length == 1){ path = ""; }else{ path = path.Substring(0, path.Length - 1); } contextPath.Value = path; foreach(var waiter in waiters){ waiter.SetResult(); } waiters.Clear(); Monitor.PulseAll(locker); } return ValueTask.CompletedTask; } } |
That’s a super simple implementation but it shows the idea which shouldn’t be surprising when we understand how a regular lock works.
The regular locking mechanism is tied to a thread. Since the thread ID cannot change, we don’t need to keep an extensive track of it. Just holding the ID is enough. However, that’s not enough with async contexts. We need to hold the context, but also understand how it changes. If we had a way to keep a strong reference to the ExecutionContext instance, we could do it in a much more robust way. However, we don’t have such an option, so we need to track it manually.
The idea is: every time we take a lock, we create a new hash of the execution trace. We represent it with just a random letter (told you it’s a super simple implementation). So now, when someone tries to take the lock, we check the hash and use it to determine whether the reentrancy is allowed.
We start with a field used for global synchronization (line 2). Next goes the “lock path” representing current hash of the owner (line 3). Line 4 holds the hash value of the execution context.
We initialize the lock in the constructor.
Next, LockAsync does the job. It locks all the competing threads, randomizes new character, and the checks if we can take the lock. If we’re allowed, we just store the new path and return. Otherwise, we create a new waiter, and add it to the queue (lines 25-26). We then schedule a continuation to try taking the lock again (line 31) and return. Notice, that LockAsync is not marked as async — that would change the execution context and the contents of contextPath variable! Yet another tricky part of async code.
Releasing the lock is similar. We lock all the threads and remove last letter of the path. We then wake up all the waiters.
Obviously, this is not a production-ready code.
Full snippet at dotnetfiddle:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
using System; using System.Collections.Generic; using System.Threading.Tasks; using System.Threading; class Program { public static int CurrentThreadId => Thread.CurrentThread.ManagedThreadId; AsyncLock asyncLock = new AsyncLock(); public static async Task Main(string []args){ await new Program().MainAsync(); } public async Task MainAsync(){ await using(await asyncLock.LockAsync()){ Console.WriteLine($"1. {nameof(MainAsync)} starting on thread {CurrentThreadId}"); var childTask = ChildAsync(delay: TimeSpan.FromMilliseconds(100)); await Task.Delay(TimeSpan.FromMilliseconds(101)).ConfigureAwait(false); Console.WriteLine($"4. {nameof(MainAsync)} continuing on thread {CurrentThreadId}"); await using(await asyncLock.LockAsync()){ Console.WriteLine($"In Critical section on main thread {CurrentThreadId}"); } Console.WriteLine($"6. {nameof(MainAsync)} finished on main thread"); await childTask; } } async Task ChildAsync(TimeSpan delay) { Console.WriteLine($"2. {nameof(ChildAsync)} starting on thread {CurrentThreadId}"); await Task.Delay(delay).ConfigureAwait(false); await using (await asyncLock.LockAsync()) { Console.WriteLine($"3. {nameof(ChildAsync)} continuing on thread {CurrentThreadId}"); Console.WriteLine($"In Critical section on child thread {CurrentThreadId}"); Console.WriteLine($"5. {nameof(ChildAsync)} finished on child thread"); } } } class AsyncLock : IAsyncDisposable { private object locker = new object(); private string path = ""; private AsyncLocal<string> contextPath; private Random random = new Random(); private List<TaskCompletionSource> waiters = new List<TaskCompletionSource>(); public AsyncLock(){ contextPath = new AsyncLocal<string>(); contextPath.Value = ""; } public Task<IAsyncDisposable> LockAsync(){ bool taken = false; TaskCompletionSource waiter = null; while(!taken){ lock(locker){ char nextCharacter = (char)((int)'a' + random.Next('z' - 'a')); if(contextPath.Value == path){ path = path + nextCharacter; contextPath.Value = path; taken = true; }else{ waiter = new TaskCompletionSource(TaskCreationOptions.RunContinuationsAsynchronously); waiters.Add(waiter); } } if(!taken && waiter != null){ return waiter.Task.ContinueWith(t => LockAsync()).Result; } } return Task.FromResult((IAsyncDisposable)this); } public ValueTask DisposeAsync (){ lock(locker){ if(path.Length == 1){ path = ""; }else{ path = path.Substring(0, path.Length - 1); } contextPath.Value = path; foreach(var waiter in waiters){ waiter.SetResult(); } waiters.Clear(); Monitor.PulseAll(locker); } return ValueTask.CompletedTask; } } |
Output:
|
1 2 3 4 5 6 7 8 |
1. MainAsync starting on thread 1 2. ChildAsync starting on thread 1 4. MainAsync continuing on thread 5 3. ChildAsync continuing on thread 7 In Critical section on child thread 7 5. ChildAsync finished on child thread In Critical section on main thread 5 6. MainAsync finished on main thread |
Okay, but what if we go with the original snippet (with no additional lock taking on the main task)? Is it possible to implement such a lock with “only one execution context allowed, reentrant and recursive” semantic? It’s still not smart (as the code is prone to a data corruption) but look at this:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
class AsyncLock : IAsyncDisposable { private object locker = new object(); private string path = ""; private AsyncLocal<string> contextPath; private Random random = new Random(); private List<TaskCompletionSource> waiters = new List<TaskCompletionSource>(); public AsyncLock(){ contextPath = new AsyncLocal<string>(valueChangedArgs => { if (valueChangedArgs.ThreadContextChanged) { lock(locker){ while(valueChangedArgs.CurrentValue != path && valueChangedArgs.PreviousValue != null && valueChangedArgs.CurrentValue != null && valueChangedArgs.CurrentValue.Length > valueChangedArgs.PreviousValue.Length){ Monitor.Wait(locker); } } } }); contextPath.Value = ""; } public Task<IAsyncDisposable> LockAsync(){ bool taken = false; TaskCompletionSource waiter = null; Console.WriteLine($"Taking lock with local {contextPath.Value} and global {path} and thread {Program.CurrentThreadId}"); while(!taken){ lock(locker){ char nextCharacter = (char)((int)'a' + random.Next('z' - 'a')); if(contextPath.Value == path){ path = path + nextCharacter; contextPath.Value = path; taken = true; }else{ waiter = new TaskCompletionSource(TaskCreationOptions.RunContinuationsAsynchronously); waiters.Add(waiter); } } if(!taken && waiter != null){ return waiter.Task.ContinueWith(t => LockAsync()).Result; } } return Task.FromResult((IAsyncDisposable)this); } public ValueTask DisposeAsync (){ lock(locker){ if(path.Length == 1){ path = ""; }else{ path = path.Substring(0, path.Length - 1); } contextPath.Value = path; foreach(var waiter in waiters){ waiter.SetResult(); } waiters.Clear(); Monitor.PulseAll(locker); } return ValueTask.CompletedTask; } } |
It’s almost the same as before. The idea is that when setting a new value for the local hash, we check if it should be allowed to run, or if something changed it in the middle. We check for it in line 13 and detect that the new value is “entering the context to execute” because it’s longer than the previous value of the field. We then stop the thread (line 14) and wait for someone unlocking the lock (line 61). Again, this is prone to the state corruption as the main task may be in the middle of the critical section and then the child may take ownership of the lock.
Generally, it is possible to implement a reentrant recursive async lock, but you need to be careful and understand that the reasoning is much harder. Especially, that every continuation may or may not be executed on a different thread (because of finishing synchronously).