Bezblokowe, stałe struktury drzew współbieżnych w czasie aktualizacji?

Ostatnio czytałem trochę literatury i znalazłem dość interesujące struktury danych.

Badałem różne metody skrócenia czasów aktualizacji do najgorszego przypadku [1-7].$\mathcal{O}(1)$

Ostatnio zacząłem szukać struktur danych bez blokowania, aby wspierać efektywny równoczesny dostęp.

Czy przy wdrażaniu struktur danych bez blokowania zastosowano jedną z tych najgorszych technik aktualizacji czasu ?$\mathcal{O}(1)$

Pytam, ponieważ; dla mnie wydają się oczywistym praktycznym rozszerzeniem tego „teoretycznego ulepszenia”.

1. Tarjan, Robert Endre. „Aktualizacja drzewa zrównoważonego wyszukiwania w obrotach O (1)”. Listy przetwarzania informacji 16, nr. 5 (1983): 253–257.

2. Driscoll, JR, N Sarnak, DD Sleator i RE Tarjan. „Utrwalanie struktur danych”. W toku osiemnastego dorocznego sympozjum ACM na temat teorii obliczeń, 109–121. STOC '86. Nowy Jork, NY, USA: ACM, 1986.

3. Levcopoulos, C. i Mark H. Overmars. „Zrównoważone drzewo wyszukiwania z czasem aktualizacji O (1) najgorszego przypadku.” Acta Inf. 26, nr 3 (listopad 1988): 269–277.

4. Fleischer, Rudolf. Proste zrównoważone drzewo wyszukiwania z czasem aktualizacji O (1) najgorszego przypadku

5. Dietz, Paul F. i Rajeev Raman. „Drzewo ciągłej aktualizacji wyszukiwania palcem”. Listy przetwarzające informacje 52, nie. 3 (1994): 147–154.

6. Lagogiannis, George, Christos Makris, Yannis Panagis, Spyros Sioutas i Kostas Tsichlas. „Nowe dynamiczne, zrównoważone drzewa wyszukiwania z czasem aktualizacji o najgorszym przypadku.” J. Autom. Lang. Grzebień. 8, nr 4 (lipiec 2003): 607–632.

7. Brodal, Gerth Stølting, George Lagogiannis, Christos Makris, Athanasios Tsakalidis i Kostas Tsichlas. „Optymalne drzewa wyszukiwania palcami w maszynie wskaźnikowej.” J. Comput. Syst. Sci. 67, nr 2 (wrzesień 2003): 381–418.

$O(1)$

Oznacza to, że jeśli wykonujesz modyfikację struktury danych, ważną cechą jest to, że możesz wykonać wszystkie mody w prywatnej strukturze danych, a następnie zamienić modyfikacje w pojedynczej instrukcji atomowej.

Swoboda blokowania jest zwykle najłatwiejsza, gdy struktury danych są niezmienne ( czysto funkcjonalne ). Po prostu trzymasz globalny wskaźnik do bieżącej wersji struktury danych. Czytelnicy nie muszą niczego blokować. Modyfikacje struktury danych są dokonywane poprzez zamianę wskaźnika globalnego na jedną niezmienną strukturę danych na drugą.

Na przykład: jeśli masz drzewo funkcjonalnie zrównoważone, to:

1. Zapisz bieżący wskaźnik globalny do katalogu głównego drzewa.
2. Utwórz nowe drzewo, które wstawia lub usuwa węzeł. (Jest to logarytmiczne w czasie i przestrzeni w liczbie węzłów obecnie w drzewie i obejmuje tworzenie nowych węzłów od punktu modyfikacji do katalogu głównego i po prostu wskazywanie wszystkiego nowego na stare części poprzedniej wersji struktury danych. )
3. Atomowo porównaj i zamień globalny wskaźnik na katalog główny. (Należy zauważyć, że może się to nie udać, jeśli między chwilą zarejestrowania starego wskaźnika głównego a tą zdarzy się kolejna modyfikacja. Jeśli tak się stanie, wróć do kroku 1 i spróbuj ponownie. Jest to tak zwana „optymistyczna kontrola współbieżności”).

Zauważ, że najważniejsze jest to, co powiedziałem powyżej o potrzebie utrzymania niezmienników reprezentacji. Zwykle nie wystarczy mieć algorytm, który atomowo dokonuje zmiany pośrodku drzewa. Dlaczego? Na przykład: możesz mieć wątek czytelnika, który jest w trakcie wykonywania przedprzebiegowego przejścia przez drzewo. Jeśli zmodyfikujesz węzeł, który jest przodkiem węzła, który obecnie czytają, unieważnisz warunki wstępne, które według nich wymusiły. Czytelnik musi być w stanie pracować ze strukturą danych dokładnie tak, jak było przed wprowadzeniem zmiany lub dokładnie tak, jak będzie po dokonaniu zmiany. Nie coś pomiędzy.

$O(log(N))$$O(N)$