Spot the deadlock

Posted by on in Blogs
This is the final full day I'll be here in Kona, Hawaii for the ANSI/ISO C++ standards meeting and they're just going through some of the minor issues, or actually "bugs" in the standard, I've been playing with the thread pool class from my post about thread pools. I included a small project to demonstrate the concept. However, in working with it, I found a subtle deadlock condition. Can you spot it? I'll give you a hint: SendMessage. I think this highlights the complexity that can creep into even the seemingly simplest of multithreaded code. Of course I wasn't being particularly careful while writing the code as it was only a conceptual exercise.

One common thing you may want to do with thread pools is to dispatch several tasks to the pool, do some other work, and then wait for the result. Another twist is that you want to continue working in the UI and then at some point in the future, a method is called when the set of tasks are completed. I've been adding some code to the SyncObjs.pas unit, and specifically the THandleObject class. I've added a class function called WaitForMultiple(). This allows you to pass in an array of THandleObject class instances on which to wait. You can wait for one or all. This is just a wrapper around WaitForMultipleObjectsEx. In the thread pool class I've added a parameter to the QueueXXWorkItem methods allowing you to optionally pass in a TEvent object that will be signaled once the work item completes. Since you may want to dispatch many work items, all of which must be completed before continuing, you'd call THandleObject.WaitForMultiple() or a new class method on the TThreadPool class.

An interesting thing to note is that if the UI thread blocks waiting for the work items, it seems that the items are not dispatched into the worker threads at all and the application hangs. There is nothing in the MSDN documentation for QueueUserWorkItem. If I perform the wait on a separate wait thread, it seems to work OK. Any ideas? Are the tasks dispatched onto the worker threads via synchronization with the message queue? I would have figured that there was a control thread that waits for things to exist in the work item queue and then does the dispatching.


About
Gold User, Rank: 84, Points: 11

Comments

  • Guest
    m. Th. Sunday, 7 October 2007

    Thanks a lot Allen for your posts from Kona. They were very, very instructive. Once again, it was proved, imho, that a community driven development is the path to follow. Now I remember a post in .non-tech newsgroup (with title “Top 3 requests” IIRC), in which someone asked for thread-safe VCL (ie. a very daunting task, imho). Nick responded “We’re very interested in that” – response which triggered an avalanche of posts from which the conclusion was that isn’t needed to have a thread-safe VCL but rather a easy, flexible way of sync/async signaling/messaging/passing data between threads and only the main thread to have the UI message loop, ie. no forms, panels, group boxes aso. in 2ndary threads, even it would be nice. IOW, a very “doable” task, even in Tiburon time frame. It was an impressive example of how community reacts, simplifies, and gives the right focus which is needed today for any IT company, imho.

    On the technical side of things, “where is the code?” (TM) Can you post the new source in CC?

  • Guest
    m. Th. Monday, 8 October 2007

    ...while waiting for your code, some more things to note:

    - Another multithreading scenario it would be a ThreadedDataModule. Yes, I know that nowadays we can create & use a TDataModule in a thread, but what I mean is to have a TDataModule assigned to a thread in a Delphi manner, ie. Bind the UI elements (“data aware controls”) to the data sources from the thread, connect to database, fetch the data, call the methods of the threaded datasets and the UI will respond etc. All these things would happen at different moments in time, at programmer's will. (ie. something like

    TMainForm.OnButtonClick(Sender);
    begin
    with MyThreadedDataModule.SQLTable1 do
    begin
    SQL.Text:='SELECT * FROM T1 WHERE '+cMyNewFilter;
    Open; //here the UI will be updated acordingly
    end;

    end;
    - Do you are aware of very interesting things at
    http://www.bluebytesoftware.com/blog/CategoryView,category,Technology.aspx

    especially at

    http://www.bluebytesoftware.com/blog/2007/04/19/MichaelSuesssParallelProgrammingInterviews.aspx

    and, of course, at

    http://www.thinkingparallel.com/


    hth

  • Guest
    Chee Wee Chua Wednesday, 17 October 2007

    Your code will eventually call QueueWorkItem(Sender, WorkerEvent, WT_EXECUTEDEFAULT) and the WT_EXECUTEDEFAULT flag tells QueueWorkItem and hence QueueUserWorkItem will execute PaintLines and hence PaintLine in a non IO thread.

    If too many non IO threads attempt to update the screen while an IO thread is updating a screen, a deadlock will occur.

    Besides, non IO threads are not supposed to update the screen.

  • Guest
    Chee Wee Chua Wednesday, 17 October 2007

    Anyway, what is eventually painted on the screen comes from a data structure.

    So, any access to a data structure must be serialized, and the serialization of the data structure for the screen occurs only in an IO thread.

    If disorderly access to the screen's data structure occurs, what happens is usually data corruption. The OS might not react kindly to that.

  • Guest
    Allen Bauer Thursday, 18 October 2007

    Chee Wee,

    The deadlock is not in the PaintLines call. It is perfectly fine to paint to the screen from a background thread.

    Allen.

  • Guest
    Chee Wee Chua Thursday, 18 October 2007

    Okay...

    In that case, isn't locking the canvas unnecessary?

  • Guest
    Chee Wee Chua Thursday, 18 October 2007

    I don't see any SendMessage call in your code, directly or indirectly.

    Is the exact code at: http://cc.codegear.com/Download.aspx?ID=25023 what you're talking about?

  • Guest
    Chee Wee Chua Thursday, 18 October 2007

    Now that I've sit myself down, examining the code by running it, instead of calculating the issues through my head, I see where your SendMessage call is. It's in the code within FForm.ListBox1.Items.Add.

    If SendMessage blocks, your app will be in a deadlock, isn't it?

  • Guest
    Allen Bauer Friday, 19 October 2007

    Chee Wee,

    That's it. I was trying to highlight that making a "thread-safe" VCL is not something easily done nor desirable in all cases.

    Allen.

  • Guest
    Chee Wee Chua Friday, 19 October 2007

    Calling QueueIOWorkItem appears to resolve your issue. I've experimented several times, and found no deadlocks.

    QueueWorkItem, performed the same number of times, seems to run into deadlocks more often.

    These tests are performed while within the IDE and stepping through the program, and may not be conclusive though.

  • Guest
    Allen Bauer Friday, 19 October 2007

    Chee Wee,

    So tell me *why* calling QueueIOWorkItem resolves it? I have my doubts that that actually resolves the problem.

    Allen.

  • Guest
    Chee Wee Chua Friday, 19 October 2007

    Allen,

    When you call QueueUserWorkItem with either of the following flags: WT_EXECUTEINIOTHREAD, WT_EXECUTEINUITHREAD, or WT_EXECUTEINPERSISTENTIOTHREAD, QueueUserWorkItem appears to call an internal UserWorkItem function, which I'll call IntUserWorkItem (for InternalUserWorkItem).


    IntUserWorkItem eventually calls NtQueueApcThread. According to Dr Dobb's Journal, Inside NT's Asynchronous Procedure Call ( URL: http://www.ddj.com/windows/184416590 ), APC, short for Asynchronous Procedure Calls, "allow user programs and system components to execute code in the context of a particular thread and, therefore, within the address space of a particular process".

    So, if you call either QueueIOWorkItem, or QueueUIWorkItem, which actually calls QueueUserWorkItem with the WT_EXECUTEINIOTHREAD or the WT_EXECUTEINUITHREAD flag, IntUserWorkItem queues a call to your callback function by calling NtQueueApcThread. I surmise this by placing a breakpoint at PaintLines. When the breakpoint is reached, you can see that the call stack contains :7c82ec2d ntdll.KiUserApcDispatcher + 0x25, which means your function has been called from an APC thread.
    I surmise then, that your callback function is called using the context of your main thread, from a thread which calls QueueUserAPC which therefore allows you to call any functions that updates the screen, or retrieves window handles, screen objects, etc.

    If however, you call QueueWorkItem instead, IntUserWorkItem can call your thread from elsewhere, and not within the context of your user interface (main) thread. Hence, your call to SendMessage is guaranteed to fail at some point in time. Therefore, calling QueueIOWorkItem or QueueUIWorkItem really resolves your issue.

    The simple demo below shows what QueueUserAPC does, and gives the same result, as if you called QueueIOWorkItem or QueueUIWorkItem.

    {$WRITEABLECONST ON}
    unit Unit203;

    interface

    uses
    Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
    Dialogs, StdCtrls;

    type
    TForm203 = class(TForm)
    Memo1: TMemo;
    btnNewThread: TButton;
    procedure btnNewThreadClick(Sender: TObject);
    private
    { Private declarations }
    procedure WorkerEvent(Sender: TObject);
    public
    { Public declarations }
    end;

    var
    Form203: TForm203;

    implementation

    {$R *.dfm}
    type
    TUserWorkItem = class
    private
    FSender: TObject;
    FWorkerEvent: TNotifyEvent;
    public
    constructor Create(ASender: TObject; AWorkerEvent: TNotifyEvent);
    end;

    TAPCThread = class(TThread)
    private
    FSender: TObject;
    FWorkerEvent: TNotifyEvent;
    FMainThread: THandle;
    public
    constructor Create(ASender: TObject; AWorkerEvent: TNotifyEvent; AMainThread: THandle);
    protected
    procedure Execute; override;
    end;

    function InternalThreadFunction(lpThreadParameter: Pointer): Integer; stdcall;
    begin
    Result := 0;
    try
    try
    with TUserWorkItem(lpThreadParameter) do
    if Assigned(FWorkerEvent) then
    FWorkerEvent(FSender);
    finally
    TUserWorkItem(lpThreadParameter).Free;
    end;
    except

    end;
    end;

    constructor TAPCThread.Create(ASender: TObject; AWorkerEvent: TNotifyEvent; AMainThread: THandle);
    begin
    inherited Create(True);
    FSender := ASender;
    FWorkerEvent := AWorkerEvent;
    FMainThread := AMainThread;
    FreeOnTerminate := True;
    Resume;
    end;

    procedure TAPCThread.Execute;
    var
    AUserWorkItem: TUserWorkItem;
    begin
    AUserWorkItem := TUserWorkItem.Create(FSender, FWorkerEvent);
    QueueUserAPC(@InternalThreadFunction, FMainThread, Cardinal(AUserWorkItem));
    SleepEx(0, True); // Forces threads to call functions placed in the APC queue
    Terminate;
    end;

    constructor TUserWorkItem.Create(ASender: TObject; AWorkerEvent: TNotifyEvent);
    begin
    inherited Create;
    FSender := ASender;
    FWorkerEvent := AWorkerEvent;
    end;

    procedure TForm203.WorkerEvent(Sender: TObject);
    const
    I: Integer = 5;
    begin
    // Place breakpoint here and see that
    // this is called from KiUserApcDispatcher (look at the stack trace)
    Memo1.Lines.Add(IntToStr(I));
    Inc(I);
    end;


    procedure TForm203.btnNewThreadClick(Sender: TObject);
    var
    LAPCThread: TThread;
    begin
    LAPCThread := TAPCThread.Create(Self, WorkerEvent, GetCurrentThread);
    end;

    end.

  • Guest
    Dennis Landi Monday, 12 November 2007

    My goodness! you've been busy Allen!

    I'll have to take a moment to catch up on all your posts since September.

  • Guest
    David Robb Thursday, 3 April 2008

    Coincidentally I have recently written a threading library for our projects here. I have an inter-process and inter-thread waitable queue, message posting and synchronous waits (e.g. a synch. wait where ProcessMessages is called when in the main thread, or a thread's message queue is pumped while in a thread). I am not using the APC functions yet - was thinking of looking into that.

  • Please login first in order for you to submit comments
  • Page :
  • 1

Check out more tips and tricks in this development video: