Lettore di scritture multiple free lock singolo

Question

Ho una struttura dati in memoria che viene letta da più thread e scritta da un solo thread. Attualmente sto usando una sezione critica per rendere questo accesso sicuro. Sfortunatamente questo ha l'effetto di bloccare i lettori anche se solo un altro lettore vi accede.

Ci sono due opzioni per porre rimedio a questo:

1. uso TMultiReadExclusiveWriteSynchronizer
2. farla finita con qualsiasi blocco utilizzando un approccio libero blocco

Per 2. Ho ottenuto il seguente finora (qualsiasi codice che non importa è stato tralasciato):

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; 

Sfortunatamente c'è il piccolo problema di eliminare l'istanza di OldData dopo che è stata sostituita. Se nessun altro thread è correntemente nel metodo di lettura (ReaderCount = 0), può essere smaltito in modo sicuro e il gioco è fatto. Ma cosa posso fare se non è questo il caso? Potrei semplicemente memorizzarlo fino alla prossima chiamata e disporlo lì, ma la programmazione di Windows potrebbe in teoria far dormire un lettore mentre è all'interno del metodo di lettura e ha ancora un riferimento a OldData.

Se si riscontrano altri problemi con il codice precedente, comunicacelo. Questo deve essere eseguito su computer con più core e i metodi sopra indicati devono essere chiamati molto frequentemente.

Nel caso questo importi: sto usando Delphi 2007 con il gestore di memoria incorporato. Sono consapevole del fatto che il gestore della memoria probabilmente impone qualche blocco in ogni caso durante la creazione di una nuova classe, ma per il momento voglio ignorarlo.

Modifica: Potrebbe non essere stato chiaro da quanto sopra: Per l'intera durata dell'oggetto TDataManager c'è solo un thread che scrive sui dati, non diversi che potrebbero competere per l'accesso in scrittura. Quindi questo è un caso speciale di MREW.

Answer 1

Non conosco alcun lock-free (o micro-locking come nell'esempio precedente) approccio MREW che potrebbe essere implementato su codice Intel86.

Per i piccoli (fast-scadenza) blocca un approccio di filatura dal OmniThreadLibrary funziona bene:

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 } 

Ho appena notato un possibile problema di allineamento qui - il codice dovrebbe verificare che omrewReference è 4-allineato. Informerà l'autore.

Answer 2

Solo un'aggiunta: quello che stai vedendo qui è generalmente noto come Hazard Pointers. Non ho idea se tu possa fare qualcosa di simile in Delphi.

Answer 3

È passato un po 'di tempo da quando mi sono sporcato le mani in Delphi, quindi verificarlo prima di utilizzarlo, ma ... dalla memoria, è possibile ottenere un conteggio di riferimento se si utilizza un'interfaccia e un'implementazione utilizzando 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; 

Poi fate tutte le variabili di tipo ISomeData invece (miscelazione ISomeData e TSomeData è una pessima idea ... si ottiene facilmente problemi di riferimento di conteggio).

In pratica, il conteggio dei riferimenti incrementa automaticamente il codice del lettore in cui carica il riferimento locale ai dati e diminuisce quando la variabile lascia l'ambito, a quel punto si disalloca.

So che è un po 'noioso duplicare l'API della classe dati in un'interfaccia e un'implementazione di classe, ma è il modo più semplice per ottenere il comportamento desiderato.

Answer 4

Ho una soluzione potenziale per voi; consente ai nuovi lettori di iniziare in qualsiasi momento fino a quando lo scrittore non desidera scrivere. Lo scrittore attende quindi che i lettori finiscano e esegua la sua scrittura. Dopo che la scrittura è terminata, i lettori possono leggere ancora una volta.

Inoltre, questa soluzione non ha bisogno di blocchi o mutex, ma necessita di un'operazione di test-and-set atomica. Non conosco Delphi e ho scritto la mia soluzione in Lisp, quindi cercherò di descriverlo in pseudo codice.

(CAPS sono i nomi delle funzioni, tutte queste funzioni prendono e tornare senza argomenti)

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) 

Per utilizzare, un lettore chiama LEGGI prima di leggere e EndRead quando fatto. Lo scrittore solitario chiama WRITE prima di scrivere e ENDWRITE quando finisce.

L'idea è un numero intero chiamato access-mode contiene un valore booleano nel bit più basso e un conteggio in i bit più alti. WRITE imposta il bit su 0, quindi gira finché gli ENDREAD non sono sufficienti per il conto alla rovescia fino a zero. Endwrite imposta la modalità di accesso su 1. LEGENDA la modalità di accesso corrente con 1, quindi il test-and-set passerà sempre se il low-bit era alto per cominciare. Aggiungo e sottraggo per 2 per lasciare il low-bit da solo.

Per ottenere un conteggio dei lettori basta spostare la modalità di accesso a destra spostata di uno.