Zablokuj wiele czytników pojedynczego pisarza

Question

Mam strukturę danych w pamięci, która jest odczytywana przez wiele wątków i zapisana przez tylko jeden wątek. Obecnie używam krytycznej sekcji, aby zapewnić bezpieczny dostęp do wątków. Niestety ma to wpływ na blokowanie czytelników, mimo że korzysta z niego tylko inny czytelnik.

Istnieją dwie opcje do zaradzenia tej:

1. użycie TMultiReadExclusiveWriteSynchronizer
2. rezygnacji z jakiegokolwiek blokowania za pomocą blokady wolnego podejście

Na 2. Mam następujące dotychczas (kod, który nie ma znaczenia został pominięty):

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; 

Niestety istnieje mały problem z pozbyciem się instancji OldData po jej wymianie. Jeśli żaden inny wątek nie znajduje się obecnie w metodzie odczytu (ReaderCount = 0), można go bezpiecznie usunąć i to wszystko. Ale co mogę zrobić, jeśli tak nie jest? Mogę po prostu przechować to do następnego połączenia i usunąć je tam, ale harmonogram systemu Windows może teoretycznie pozostawić wątek czytnika w stanie uśpienia, gdy jest w ramach metody Read i nadal ma odniesienie do OldData.

Jeśli widzisz inny problem z powyższym kodem, proszę powiedz mi o tym. Powinien być uruchamiany na komputerach z wieloma rdzeniami, a powyższe metody należy wywoływać bardzo często.

Jeśli to ma znaczenie: używam Delphi 2007 z wbudowanym menedżerem pamięci. Mam świadomość, że kierownik pamięci prawdopodobnie wymusza pewną blokadę podczas tworzenia nowej klasy, ale chcę to zignorować w tej chwili.

Edycja: Być może nie wynikało to z powyższego: Dla całego okresu istnienia obiektu TDataManager istnieje tylko jeden wątek, który zapisuje dane, a nie kilka, które mogą konkurować o dostęp do zapisu. Jest to szczególny przypadek MREW.

Answer 1

Nie znam żadnej blokady (lub mikro-blokowania, jak w powyższym przykładzie) podejścia MREW, które można zaimplementować na kodzie Intel86.

Dla małych (szybko upływającym) blokuje podejście przędzenia z OmniThreadLibrary działa dobrze:

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 } 

Właśnie zauważyłem problem ewentualnego wyrównania tutaj - kod powinien sprawdzić, czy omrewReference jest 4-wyrównane. Powiadomi autora.

Answer 2

Tylko dodatek - to, na co patrzysz, jest ogólnie znany jako Hazard Pointers. Nie mam pojęcia, czy możesz zrobić coś podobnego w Delphi.

Answer 3

Minęło trochę czasu, odkąd zabrudziły mi się ręce w Delphi, więc zweryfikuj to przed użyciem, ale ... z pamięci, możesz uzyskać referencyjne zachowanie, jeśli korzystasz z interfejsu i implementacji za pomocą 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; 

Następnie zrobić wszystkie zmienne typu ISomeData zamiast (mieszanie ISomeData i TSomeData to bardzo zły pomysł ... łatwo dostać problemy odniesienia liczenia).

Zasadniczo spowoduje to automatyczne zwiększenie liczby odwołań w kodzie czytnika, w wyniku czego zostanie załadowane lokalne odwołanie do danych, a wartość zmiennej zostanie zmniejszona, gdy zmienna opuszcza zakres, w którym to momencie zostanie ona cofnięta.

Wiem, że trochę nudne jest powielać API klasy danych w interfejsie i implementacji klasy, ale jest to najprostszy sposób na uzyskanie pożądanego zachowania.

Answer 4

Mam dla ciebie potencjalne rozwiązanie; pozwala nowym czytelnikom zacząć w dowolnym momencie, dopóki pisarz nie napisze. Pisarz następnie czeka na czytelników, aby zakończyć i wykonuje jego zapis. Po zakończeniu pisania czytelnicy mogą przeczytać raz jeszcze.

Co więcej, to rozwiązanie nie wymaga blokad ani muteksów, ale potrzebuje atomowej operacji testowania i ustawiania. Nie znam Delphi i napisałem swoje rozwiązanie w Lisp, więc spróbuję opisać to w pseudo kodzie.

(CAPS są nazwy funkcji, wszystkie te funkcje podjęcia i powrócić żadnych argumentów)

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) 

Aby go wykorzystać, czytelnik zwraca przeczytać przed zapoznaniem ENDREAD po zakończeniu. Samotny pisarz dzwoni WRITE przed pisaniem i ENDWRITE po zakończeniu.

Pomysł jest liczbą całkowitą zwaną trybem dostępu, która zawiera wartość logiczną w najniższym bicie, a liczba w bitach wyższą: . WRITE ustawia bit na 0, a następnie obraca się, aż wystarczająca liczba ENDREAD odlicza tryb dostępu do zera. Endwrite ustawia tryb dostępu z powrotem na 1. READ ORs aktualny tryb dostępu z 1, więc ich test-i-zestaw kiedykolwiek przejdzie, jeśli niski bit był na początku wysoki. Dodaję i odejmuję o 2, aby zostawić niski bit w spokoju.

Aby uzyskać liczbę czytelników, po prostu ustaw tryb dostępu w prawo, przesunięty o jeden.