Saturday, July 12, 2008

Lock Up Unlocked

In my last post (Locked Up!), I gave an example of a simple deadlocking application. If you run it and click the button a few times rapidly, the application stops responding. Then, if you pause the program and examine the stack trace of each thread, you find the GUI thread waiting for the lock, and the child thread waiting for Invoke() to return. The child thread is holding the lock, so the application is deadlocked. This is also known as a "deadly embrace".

So, I affectionately referred to the two resources as Resource RA and Resource RB and asked you to identify them in the program. One of the resources is pretty obvious. That would be the lblResult.Text. It doesn't matter whether you call this RA or RB, so I'll call it Resource RA. Regardless, for some odd reason, the programmer has decided that the lblResult.Text property needs to be protected from simultaneous read and write. This protection is not really necessary, but pretend for a moment a valid sort of resource did indeed need this kind of protection. Thus, we have the lock on Resource RA as lock(lockObject) { ... }. Were you going to say lockObject is RA? That's okay, that can work, too. But, as I'll try to show, its preferable to think of the lockObject as part of the mechanism for locking a resource, and consider the code or resource being protected as the true resource.

Determining Resource RB is more difficult, since there are no other locks in the code to make it stand out. There is only the lock around the reading and the lock around the writing of the text field. The key to figuring out what Resource RB is is to look for where the program is waiting or blocking.

The child thread is stuck waiting for Invoke() to complete. Invoke() is not the resource and technically, its not the lock either. But, none the less, that is the point at which the child appears blocked. The child is waiting for a resource to come free. The Resource RB is then the GUI thread's processing of the child thread's request. But, the GUI thread did not lock a resources, or did it?

The GUI thread is regularly returning to the event loop to process the next event on the queue or wait until there are events (it's more complex than this, but we'll keep it simple for the sake of the discussion). A queue such as this is a locking mechanism. While the GUI is busy, servicing an event, anyone waiting for a particular event to complete is blocked until the GUI pulls the event and processes the event being waited for. You can think of the GUI thread as having locked RB by pulling an event and working on it. In this simple case, the GUI thread actually pulled the child thread's event (Invoke request) and tried to work on it. But, the child had locked the resource the GUI needed to continue. Consider the more complex case where the GUI pulls some other event for some other thread waiting for service and the problem could become daunting.

Now, the whole purpose in thinking about this problem as dealing with just two resources RA and RB is to present a simple analytic approach. You may have hit a deadlock or two in your novice foray into multi-threaded applications. Having hit a deadlock or related race condition, you may not have had the analytic tools to diagnose the problem. So start with the first tool called "understanding". The basic or classic deadlock or deadly-embrace occurs when one thread holds a resource (RA) and needs another resource (RB) while another thread holds the second resource (RB) and needs the first resource (RA). If you can understand this, and if you can boil the problem down to this simple formula, you can begin solving the problem with basic locking principles. As you advance in multi-threaded programming, you'll learn more and more of the locking patterns and how to apply them. But, in the mean time, if you boil everything down to simply "locking a resource", some basic guidelines will help you correct your logic or design.

Basic guidelines for locking.

  • Avoid simultaneously locking multiple shared resources in a single thread.

  • If multiple shared resources must be locked simultaneously, endeavor that all threads lock the resources in the same order and unlock them in reverse order.

  • If they can't be unlocked in reverse order, then endeavor to unlock in the same order and do not lock an earlier resource till all later locks are released.

  • If you can't follow these guidelines, then timeout.



  • There's more to be said about these basic locking principles, and I'd like to touch on the touchy subject of knowing one's resources. But, I'll save that for the next post and instead leave you with some code that breaks the deadlock and hopefully provokes some more thought about the often overlooked event loop "resource". Maybe you can tell why this breaks the deadlock based upon the RA/RB discussion.

    Here's the code.


    using System;
    using System.Collections.Generic;
    using System.ComponentModel;
    using System.Data;
    using System.Drawing;
    using System.Linq;
    using System.Text;
    using System.Windows.Forms;
    using System.Threading;
    // Now let's see how we can avoid locking ourselves up
    //
    namespace LockupExample
    {
    public partial class Form1 : Form
    {
    public Form1()
    {
    InitializeComponent();
    _t = new Thread(new ParameterizedThreadStart(WorkerThread));
    }

    private Thread _t;
    private object lockObject = new object();
    private bool StopThread = false; // to let the thread quit gracefully
    private void WorkerThread(object sender)
    {
    Thread.Sleep(1000);
    while (!StopThread)
    {
    string result = "This is a Test";
    IAsyncResult aResult;

    lock (lockObject)
    {
    Thread.Sleep(25);
    aResult = lblResult.BeginInvoke(new MethodInvoker(delegate { lblResult.Text = result; }));
    }
    lblResult.EndInvoke(aResult);
    Thread.Sleep(500);
    }
    }

    private void Form1_Load(object sender, EventArgs e)
    {
    _t.Start();
    }

    private void button1_Click(object sender, EventArgs e)
    {
    lock (lockObject)
    {
    lblResult.Text = "Override the Test";
    }
    }

    private void Form1_FormClosing(object sender, FormClosingEventArgs e)
    {
    StopThread = true;
    }
    }
    }

    No comments: