CYSDL 3: Solution

This is the solution to the Can You Spot the DeadLock 3.

The problem

No deadlock today, this code does not produce the expected result (27000) with certainty. So it raises an explicit exception, most of the time.

why does it occur?

As you have probably guessed, the general intent is to have three agents, each of them responsible for applying a factor (2,3,5) in a sequential way. Sequence is orchestrated thanks to a step counter and the use of modulo so that each agent acts on the appropriate steps.

Expected Result

The major failure here is the use of if(!condition) instead of while(!condition).
Improper use of the monitor pattern: agents assume that if they are woken up, it means their condition is fulfilled, which is clearly not the case: they are waken for each forward steps. Afterward, it’s a race condition between threads to get the lock.

Sample result
Sample result

As you can see, neither order nor execution count is secured. This code fails in many ways.

how to fix?

You just need to replace the ‘if(!condition)’ with ‘while(!condition)’ and bang, you’re done.

Actually, writing this code was harder than anticipated. My original plan was to use Pulse instead of PulseAll as I feared that PulseAll was giving too much away. But it turns out that all my attempts led to non working code or too obvious problems.

Feel free to submit your own if you want.

And see you for the next exercise.

CYSDL 2: Solution

This is the solution to the Can You Spot the DeadLock 2.

The problem

This code can deadlock. It actually deadlocks pretty fast on my testbed. The deadlock occurs between the notification mechanism and the unsubscription method in the client class!

Where does it occur?

The notification thread is locked trying to gets its notification through

public class Client: IDisposable {
private void OnEvent(object sender, EventArgs arguments) {
lock (this) // notification thread is locked here

The main thread is locked trying to unsubscribe properly
public class EventSource {
public event EventHandler EventOccured{
remove {
lock (this) // main thread is locked here

The source of the issue is that we have two conflicting resource acquisition paths:
1) The notification path, where first (the lock for) the event is acquired (to prevent modification on the fly of the subscribers list) and then the client (lock) is acquired (to ensure exclusive access to its internals).
2) The unsubscription path wich first acquire the client (to ensure exclusive access to its internals) and then acquire the event for safe unsubscription.

How can it be fixed?

That is the impossible part. There is no proper solution to this problem! That one of the reason I like it so much. But the keyword here is proper. You can resolve the deadlock assuming you are ok to relax the contract a bit.

What is the contract here?

This code (unsuccessful) implements a strong contract: The Client will not receive any notification before the end of the subscription method and it will not receive any notifications after the end of unsubscription method. The first assumption is in fact trivial: how could a client receive notifications from a source it has not subscribed to yet :-). The second one looks similar and quite harmless, it even looks like very desirable. But its a trap: every implementation of this contract offers deadlock opportunities!

You need to relax it a bit and remove the second requirement: you must accept to (potentialy) receive notifications even after a succesful unsubscription. Then you can drop the locks in EventSource.