Lectores múltiples sin bloqueo único escritor

Question

Tengo una estructura de datos en la memoria que es leída por varios hilos y escrita por un solo hilo. Actualmente estoy usando una sección crítica para hacer que este acceso sea seguro para los hilos. Desafortunadamente, esto tiene el efecto de bloquear a los lectores aunque solo otro lector esté accediendo a él.

Hay dos opciones para remediar esto:

1. uso TMultiReadExclusiveWriteSynchronizer
2. acabar con cualquier bloqueo mediante el uso de un enfoque libre de bloqueo

Por 2. Tengo el siguiente hasta el momento (cualquier código que no importe ha sido dejado fuera):

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; 

Desafortunadamente, existe el pequeño problema de deshacerse de la instancia de OldData después de que se ha reemplazado. Si no hay otro subproceso actualmente en el método de lectura (ReaderCount = 0), se puede eliminar de manera segura y eso es todo. Pero, ¿qué puedo hacer si ese no es el caso? Podría simplemente almacenarlo hasta la siguiente llamada y disponerlo allí, pero la programación de Windows podría, en teoría, permitir que un lector se quede dormido mientras está dentro del método Read y todavía tiene una referencia a OldData.

Si ve algún otro problema con el código anterior, hábleme al respecto. Esto se debe ejecutar en computadoras con múltiples núcleos y los métodos anteriores se deben llamar con mucha frecuencia.

En caso de que esto importe: estoy usando Delphi 2007 con el administrador de memoria incorporado. Soy consciente de que el administrador de memoria probablemente aplica algún bloqueo de todos modos al crear una nueva clase, pero quiero ignorar eso por el momento.

Editar: Puede no haber quedado claro de lo anterior: durante toda la vida útil del objeto TDataManager solo hay un hilo que escribe en los datos, no varios que podrían competir por el acceso de escritura. Entonces este es un caso especial de MREW.

Answer 1

No conozco ningún enfoque MREW (o microbloqueo como en su ejemplo anterior) que pueda implementarse en el código Intel86.

Para pequeñas (rápido-que expira) encierra un enfoque de giro de la OmniThreadLibrary funciona bien:

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 } 

me he dado cuenta de un posible problema de alineación aquí - el código debe comprobar que se omrewReference 4-alineado. Notificará al autor.

Answer 2

Solo una adición: lo que está viendo aquí se conoce generalmente como Hazard Pointers. No tengo idea si puedes hacer algo similar en Delphi.

Answer 3

Ha pasado un tiempo desde que ensucié mis manos en Delphi, así que verifíquelo antes de usarlo, pero ... desde la memoria, puede obtener un comportamiento contado de referencia si usa una interfaz y una implementación usando 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; 

luego de hacer todas sus variables de tipo ISomeData lugar (mezcla ISomeData y TSomeData es una muy mala idea ... se obtiene fácilmente los problemas de conteo de referencias).

Básicamente, esto provocaría que el recuento de referencias se incremente automáticamente en su código de lector donde carga la referencia local a los datos, y disminuye cuando la variable abandona el alcance, en cuyo punto se desasignaría allí.

Sé que es un poco tedioso duplicar la API de su clase de datos en una interfaz y una implementación de clase, pero es la manera más fácil de obtener su comportamiento deseado.

Answer 4

Tengo una posible solución para usted; permite que los nuevos lectores comiencen en cualquier momento hasta que el escritor desee escribir. El escritor espera a que los lectores finalicen y realiza su escritura. Después de que la escritura está hecha, los lectores pueden leer una vez más.

Además, esta solución no necesita bloqueos o mutex, pero sí necesita una operación atómica de prueba y configuración. No sé, Delphi y yo escribimos mi solución en Lisp, así que trataré de describirla en un pseudo código.

(CAPS son nombres de funciones, todas estas funciones toman y devuelven sin argumentos)

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) 

Para utilizar, un lector llama LEER antes de leer y EndRead cuando haya terminado. El escritor solitario llama a ESCRIBIR antes de escribir y ENDWRITE cuando termina.

La idea es un número entero llamado modo de acceso contiene un booleano en el bit más bajo y un recuento en los bits más altos. WRITE establece el bit en 0 y luego gira hasta que los ENDREADs cuenten el modo de acceso a cero. Endwrite vuelve a establecer el modo de acceso en 1. LEA ORs el modo de acceso actual con 1, por lo que su prueba y conjunto solo pasará si el bit bajo fue alto para empezar. Suma y resta por 2 para dejar el bit bajo solo.

Para obtener el número de lectores acaba de tomar el acceso en modo correcto cambiado por uno.