Lock free multiple readers single writer

delphi, lock-free, multithreading

Solution

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.

Problem

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: - use TMultiReadExclusiveWriteSynchronizer - 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.

Original source