ロックフリーの複数のリーダーシングルライター

Question

私は複数のスレッドで読み込まれ、1つのスレッドのみによって書き込まれるメモリ内のデータ構造を持っています。現在、私はこのアクセスをスレッドセーフにするためにクリティカルセクションを使用しています。残念ながら、これは別のリーダーだけがアクセスしていても、リーダーをブロックする効果があります。

これを解決するには、2つのオプションがあります。

1. 使用TMultiReadExclusiveWriteSynchronizerの
2. は、私がこれまでに以下を持っている2.について

ロックフリーのアプローチを使用して、任意のブロックを廃止（問題取り残されていない、任意のコード）：

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; 

残念ながら、OldDataインスタンスが置き換えられた後にそれを取り除くという小さな問題があります。他のスレッドが現在Readメソッド内にない場合（ReaderCount = 0）、それは安全に破棄できます。しかし、そうでない場合はどうすればいいですか？ 私は次の呼び出しまでそれを保存してそこに置くことができますが、Windowsのスケジューリングは理論的には読み取りメソッド内にある間に読み取りスレッドをスリープさせることができ、まだOldDataへの参照を持っています。

上記のコードに他の問題がある場合は、教えてください。これは、複数のコアを持つコンピュータ上で実行され、上記の方法は非常に頻繁に呼び出されます。

この場合、Delphi 2007を内蔵メモリマネージャとともに使用しています。私は、新しいクラスを作成するときにメモリマネージャがおそらく何らかのロックを強制している可能性があることを認識していますが、私は今それを無視したいと思います。

編集：上記から明らかではないかもしれません：TDataManagerオブジェクトの全期間にわたって、書き込みアクセスのために競合する可能性のあるものではなく、データに書き込むスレッドは1つだけです。これはMREWの特別なケースです。

Answer 1

私は、Intel86コードで実装可能なMREWのアプローチがロックフリー（または上記の例ではマイクロロック）であるかどうかわかりません。小（速い期限）については

がOmniThreadLibraryからスピニングアプローチをロックし正常に動作します：

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 } 

私はちょうどここに可能アライメントの問題に気づいた - コードがomrewReferenceは4位置合わせされていることを確認する必要があります。著者に通知します。

Answer 2

ちょうど追加 - あなたがここで見ているものは、一般にHazard Pointersとして知られています。私はあなたがデルファイで何か似たようなことをすることができるかどうか分かりません。

Answer 3

私はDelphiで手を汚しているので、しばらくしていますので、使用する前にこれを確認してください。しかし、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; 

次に、あなたは（あなたが簡単に参照カウントの問題を取得... ISomeDataとTSomeDataを混合することは非常に悪い考えである）の代わりにタイプISomeDataのすべての変数を作ります。

これは基本的に、ローカル参照がデータにロードされる読者コード内で参照カウントを自動的にインクリメントし、変数がスコープを離れるとデクリメントされ、そこでは割り当てが解除されます。

私は、インターフェイスとクラスの実装でデータクラスのAPIを複製するのはちょっと面倒ですが、希望の動作を得るには最も簡単な方法です。

Answer 4

私はあなたのための潜在的な解決策を持っています。それは、ライターが書くことを望むまで、いつでも新しいリーダーを開始させることができます。次に、ライターは、読者が終了してその書き込みを行うのを待ちます。執筆が終わったら、読者はもう一度読むことができます。

さらに、この解決策ではロックやミューテックスは必要ありませんが、アトミックなテスト＆セット操作が必要です。私はDelphiを知らず、Lispで私のソリューションを書いたので、私は擬似コードで記述しようとします。

（CAPSは、関数名で、これらすべての機能が取ると引数を返さない）

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) 

使用するために行われたとき、読者は読書とENDREAD前にREADを呼び出します。孤独な作家は書く前にWRITEを呼び出し、完了したらENDWRITEを呼び出します。

アイデアは、アクセスモードと呼ばれる整数で、最下位ビットにブール値を保持し、より高いビットを とカウントします。 WRITEはそのビットを0にセットし、十分なENDREADがアクセス・モードをゼロにカウントするまでスピンします。 Endwriteは、アクセスモードを1に戻します。READは、現在のアクセスモードを1でORします。したがって、それらのテストセットは、ロービットが高い場合にのみ通過します。私は2を加えて減算するだけで低ビットだけを残します。

読者数を取得するには、アクセスモードを1だけ右にシフトします。