Sleep sort and TThread corner case

If you have not heard it yet – an anonymous genius from 4chan invented a sleep sort, brilliant esoteric sorting algorithm. I have written sleep sort implementation based on Delphi TThread class for rosettacode project, and started to experiment with the code. One of the working variants is:

program SleepSortDemo2;

{$APPTYPE CONSOLE}

uses
  SysUtils, Classes, SyncObjs;

type
  TSleepThread = class(TThread)
  private
    FValue: Integer;
    FLock: TCriticalSection;
  protected
    constructor Create(AValue: Integer; ALock: TCriticalSection);
    procedure Execute; override;
  end;

const
  ArrLen = 16;

var
  A: array[0..ArrLen - 1] of Integer;
  Threads: array[0..ArrLen - 1] of TThread;
  Lock: TCriticalSection;
  I: Integer;

constructor TSleepThread.Create(AValue: Integer; ALock: TCriticalSection);
begin
  FValue:= AValue;
  FLock:= ALock;
  inherited Create(False);
end;

procedure TSleepThread.Execute;
begin
  Sleep(1000 * FValue);
  FLock.Acquire;
  Write(FValue:3);
  FLock.Release;
end;

begin
  for I:= 0 to ArrLen - 1 do begin
    A[I]:= Random(15);
    Write(A[I]:3);
  end;
  Writeln;

  Lock:= TCriticalSection.Create;
  for I:= 0 to ArrLen - 1 do
    Threads[I]:= TSleepThread.Create(A[I], Lock);
  for I:= 0 to ArrLen - 1 do begin
    Threads[I].WaitFor;
    Threads[I].Free;
  end;
  Lock.Free;

  Writeln;
  Readln;
end.

Now, if you look at TThread source code you can see that TThread.WaitFor is called from TThread.Destroy, so it seems that there is no need for a separate  Threads[I].WaitFor call and the line #53 can be commented. Try it, and the code does not work anymore (at least it does not work on the system I used for testing – Windows 7 SP1, Celeron 530 CPU, 2 Gb RAM).

After pondering at the problem for some time I understood that TThread.Destroy just does not wait for the thread to terminate. But why? Look at the code snippet from TThread.Destroy:

  if (FThreadID <> 0) and not FFinished and not FExternalThread then
  begin
    Terminate;
    if FCreateSuspended then
      Resume;
    WaitFor;
  end;

All conditions are satisfied. You can set a breakpoint on WaitFor line and see that WaitFor method is actually called…

The answer was found in the ThreadProc function. Here is a code snippet from it:

  ..
  try
    if not Thread.Terminated then
    try
      Thread.Execute;
    except
      Thread.FFatalException := AcquireExceptionObject;
    end;
  finally
  ..

See what happens? TThread.Destroy calls Terminate and sets TThread.Terminated flag. But the thread has not started yet. Now the thread starts, ThreadProc function checks TThread.Terminated flag, and the Execute method is never called!

Advertisement