Lock free multiple readers single writer

Question

I have got an in memory data structure that is read by multiple threads and written by only one thread. Currently I am using a critical section to make this access threadsafe. Unfortunately this has the effect of blocking readers even though only another reader is accessing it.

There are two options to remedy this:

1. use TMultiReadExclusiveWriteSynchronizer
2. do away with any blocking by using a lock free approach

For 2. I have got the following so far (any code that doesn't matter has been left out):

type
  TDataManager = class
  private
    FAccessCount: integer;
    FData: TDataClass;
  public
    procedure Read(out _Some: integer; out _Data: double);
    procedure Write(_Some: integer; _Data: double);
  end;

procedure TDataManager.Read(out _Some: integer; out _Data: double);
var
  Data: TDAtaClass;
begin
  InterlockedIncrement(FAccessCount);
  try
    // make sure we get both values from the same TDataClass instance
    Data := FData;
    // read the actual data
    _Some := Data.Some;
    _Data := Data.Data;
  finally
    InterlockedDecrement(FAccessCount);
  end;
end;

procedure TDataManager.Write(_Some: integer; _Data: double);
var
  NewData: TDataClass;
  OldData: TDataClass;
  ReaderCount: integer;
begin
  NewData := TDataClass.Create(_Some, _Data);
  InterlockedIncrement(FAccessCount);
  OldData := TDataClass(InterlockedExchange(integer(FData), integer(NewData));
  // now FData points to the new instance but there might still be
  // readers that got the old one before we exchanged it.
  ReaderCount := InterlockedDecrement(FAccessCount);
  if ReaderCount = 0 then
    // no active readers, so we can safely free the old instance
    FreeAndNil(OldData)
  else begin
    /// here is the problem
  end;
end;

Unfortunately there is the small problem of getting rid of the OldData instance after it has been replaced. If no other thread is currently within the Read method (ReaderCount=0), it can safely be disposed and that's it. But what can I do if that's not the case? I could just store it until the next call and dispose it there, but Windows scheduling could in theory let a reader thread sleep while it is within the Read method and still has got a reference to OldData.

If you see any other problem with the above code, please tell me about it. This is to be run on computers with multiple cores and the above methods are to be called very frequently.

In case this matters: I am using Delphi 2007 with the builtin memory manager. I am aware that the memory manager probably enforces some lock anyway when creating a new class but I want to ignore that for the moment.

Edit: It may not have been clear from the above: For the full lifetime of the TDataManager object there is only one thread that writes to the data, not several that might compete for write access. So this is a special case of MREW.

Blurt

I'm wary of self-written lock-free code, it's nearly impossible to get it right. As for TMREWS: There's no way around timing your use-case on typical machines, as there are different ways to implement them, and the VCL gives you only one. For an article comparing different implementations (including timing) see codeproject.com/KB/threads/testing_rwlocks.aspx – Tremor

Answer 1

I don't know of any lock-free (or micro-locking as in your example above) MREW approach that could be implemented on Intel86 code.

For small (fast-expiring) locks a spinning approach from the OmniThreadLibrary works fine:

type
TOmniMREW = record
strict private
  omrewReference: integer;      //Reference.Bit0 is 'writing in progress' flag
public
  procedure EnterReadLock; inline;
  procedure EnterWriteLock; inline;
  procedure ExitReadLock; inline;
  procedure ExitWriteLock; inline;
end; { TOmniMREW }

procedure TOmniMREW.EnterReadLock;
var
  currentReference: integer;
begin
  //Wait on writer to reset write flag so Reference.Bit0 must be 0 than increase Reference
  repeat
    currentReference := omrewReference AND NOT 1;
  until currentReference = InterlockedCompareExchange(omrewReference, currentReference + 2, currentReference);
end; { TOmniMREW.EnterReadLock }

procedure TOmniMREW.EnterWriteLock;
var
  currentReference: integer;
begin
  //Wait on writer to reset write flag so omrewReference.Bit0 must be 0 then set omrewReference.Bit0
  repeat
    currentReference := omrewReference AND NOT 1;
  until currentReference = InterlockedCompareExchange(omrewReference, currentReference + 1, currentReference);
  //Now wait on all readers
  repeat
  until omrewReference = 1;
end; { TOmniMREW.EnterWriteLock }

procedure TOmniMREW.ExitReadLock;
begin
  //Decrease omrewReference
  InterlockedExchangeAdd(omrewReference, -2);
end; { TOmniMREW.ExitReadLock }

procedure TOmniMREW.ExitWriteLock;
begin
  omrewReference := 0;
end; { TOmniMREW.ExitWriteLock }

I just noticed a possible alignment issue here - the code should check that omrewReference is 4-aligned. Will notify the author.

Exteriorize

If I'm not mistaken you'll notify yourself ;-) It is a nice library by the way. – Montanez

@gabr: For multi-core systems this is a very nice thing to have in the toolbox, +1. It does share one aspect with the slim R/W lock introduced with Vista, though: access can't be upgraded from reading to writing. If I read this code correctly doing so would lead to an infinite loop. Maybe it's worth to add a note to that effect. – Tremor

@Davy: No, I'm not the author, GJ is - the guy that also wrote lock-free (or, rather, microlocking) stack and queue. – Exteriorize

@DavyLandman, I had the same question when I read gabr said that :) – Ulysses

@Tremor You're right, this lock will spin forever. The corresponding Windows slim R/W lock will only spin 1024 times. After that it will fall back to a fast user-space mutex; the undocumented Keyed Event. – Scar

Answer 2

Just an addition - what you are looking at here is generally known as Hazard Pointers. I have no idea if you can do something similar in Delphi.

Conard

Answer 3

It's been a while since I got my hands dirty in Delphi, so verify this before using, but... from memory, you can get reference-counted behaviour if you use an interface and an implementation using TInterfacedObject.

type
    IDataClass = interface
        function GetSome: integer;
        function GetData: double;

        property Some: integer read GetSome;
        property Data: double read GetData;
    end;

    TDataClass = class(TInterfacedObject, IDataClass)
    private
        FSome: integer;
        FData: double;
    protected
        function GetSome: integer;
        function GetData: double;
    public
        constructor Create(ASome: integer; AData: double);
    end;

Then you make all your variables of type ISomeData instead (mixing ISomeData and TSomeData is a very bad idea... you easily get reference-counting problems).

Basically this would cause the reference count to increment automatically in your reader code where it loads the local reference to the data, and it gets decremented when the variable leaves scope, at which point it would de-allocate there.

I know it's a bit tedious to duplicate the API of your data class in an interface and a class implementation, but it is the easiest way to get your desired behaviour.

Syrinx

Unfortunately reference counting for interfaces is not thread safe. – Blurt

Reference-counting IS thread-safe. Sharing a single interface variable among multiple threads is NOT thread-safe. – Asis

That does however complicate matters a little in itself. I clearly need to dig back into Delphi to verify what is safe when using TInterfacedObject in threaded code. – Syrinx

Answer 4

I've got a potential solution for you; it lets new readers start anytime until the writer wishes to write. The writer then waits for the readers to finish and performs its write. After the writing is done the readers can read once more.

Furthermore, this solution does not need locks or mutexs, but it does need an atomic test-and-set operation. I don't know Delphi and I wrote my solution in Lisp, so I'll try to describe it in pseudo code.

(CAPS are function names, all these functions take and return no arguments)

integer access-mode = 1; // start in reader mode. 

WRITE  loop with current = accessmode, 
            with new = (current & 0xFFFFFFFe) 
            until test-and-set(access-mode, current to new)
       loop until access-mode = 0; 

ENDWRITE assert( access-mode = 0)
         set access-mode to 1

READ loop with current = ( accessmode | 1 ),
          with new = (current + 2),
          until test-and-set(access-mode, current to new)
ENDREAD loop with current = accessmode
             with new = (current - 2),
             until test-and-set(access-mode, current to new)

To use, a reader calls READ before reading and ENDREAD when done. The lone writer calls WRITE before writing and ENDWRITE when done.

The idea is an integer called access-mode holds a boolean in the lowest bit, and a count in the higher bits. WRITE sets the bit to 0, and then spins until the enough ENDREADs count down access mode to zero. Endwrite sets access-mode back to 1. READ ORs the current access-mode with 1, so their test-and-set will only ever pass if the low-bit was high to begin with. I add and subtract by 2 to leave the low-bit alone.

To get a count of readers just take access-mode right shifted by one.

Lipophilic