Can You Spot the Deadlock 3?

Hello dear readers and coders

Welcome to the third ‘Can You Spot the Deadlock?’ trivia. Today’s exercise is still dedicated to the Monitor Pattern. Next one will explore other horizons.

As usual the code is in C#, it does compile but it will not run as is.

So:

  • What is the issue here?
  • Where does it occur?
  • Can you fix it ? if yes how, if not, why

And please share your ideas through the comment!

using System;
using System.Threading;

namespace SpotTheDeadLock
{
  internal class SpotTheDeadlock3
  {
    readonly object _synchro = new object(); // lock object

    public int _x = 1; // resulting data

    bool _mustStop;
    int _iteration = 0;
    int []_factor={2,3,5};

    // first running thread

    public void Runner1(int stepId) {
      while (true) {
        lock (_synchro) {
          if (_iteration % 3 != stepId && !_mustStop)
            Monitor.Wait(_synchro);

          if (_mustStop)
            return;

          _x = _x * _factor[stepId];
          NextStep();

        } // _synchro
      } // while
    }

  private void NextStep() {
    if (_iteration == 8)
      _mustStop = true;
    else
      _iteration++;
    Monitor.PulseAll(_synchro);
  }

  public static void Runner() {

    SpotTheDeadlock3 agent = new SpotTheDeadlock3();
    Thread thread1 = new Thread(() => agent.Runner1(0));
    Thread thread2 = new Thread(() => agent.Runner1(1));
    Thread thread3 = new Thread(() => agent.Runner1(2));

    thread1.Start();
    thread2.Start();
    thread3.Start();

    thread1.Join();
    thread2.Join();
    thread3.Join();

    if (agent._x != 2 * 2 * 2 * 3 * 3 * 3 * 5 * 5 * 5)
      throw new ApplicationException("Invalid result");
    }

  } // class
} // namespace

Quizz time is closed, solution is available here

Advertisements

Can You Spot the DeadLock access

In order not to spoil the fun for late comers to the game, CYSDL solutions are no longer attached to SpotTheDeadLock category.
So if you wanna try the challenge, you can access directly all problems thanks to the FastTrack menun top left of this page.

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.

Can You Spot the Deadlock 2?

Hello dear readers and coders

Welcome to the second ‘Can You Spot the Deadlock?’ trivia. I surely hope you had fun with the first one. Yeah, I know, it was kinda easy. So today, I raise the bar a bit and bring you one of my favorites: the transactional subscription/un subscription pattern.

The code compiles but it will not run, as I did not show the scaffolding code. Suffice to say that there is a notification mechanism that lives in its own thread(s) and some client code logic that rely on the main(starting) thread.

So:

  • What is the issue here?
  • Where does it occur?
  • Can you fix it ? if yes how, if now, why

Problem is now closed, please find the solution

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SpotTheDeadLock2
{
///
/// Implements aynchronous notification
///
public class EventSource
{
    private EventHandler _eventHandler;
    ///
    /// notification event
    ///

    public event EventHandler EventOccured
    {
        add {
            // lock to secure subscription
            lock (this){
                _eventHandler += value;
            }
        }
        remove {
            // lock to secure unsubscription
            lock (this) {
                _eventHandler -= value;
            }
        }
    }
    // implementation of notification
    private void TriggerEvent() {
        lock (this) {
            if (_eventHandler != null) {
                _eventHandler(this, new EventArgs());
            }
        }
    }
}

///
/// client implementation
///
public class Client: IDisposable
{
    private EventSource _source;
    ///
    /// Simple constructor
    ///
    ///data source to subsribe to
    public Client(EventSource source) {
        _source = source;
        _source.EventOccured += OnEvent;
    }

    ///
    /// Method in charge of processing events
    ///
    private void OnEvent(object sender, EventArgs arguments) {
        // use lock as we do not have control of calling thread
       lock (this) {
           // do my job
           ...
       }
    }
    // unsubscribe on clean up
    public void Dispose() {
    // use lock to ensure no processing is in progress
        lock (this) {
            _source.EventOccured -= OnEvent;
        }
    }
}
}