Ograniczenia kolekcji bez zamków?

David Rodríguez - dribeas napisał w komentarzu do StackOverflow, że „Nie wszystkie kolekcje można zaimplementować bez blokad”. Nie jestem pewien, czy to prawda, i tak nie mogę znaleźć dowodu.

To stwierdzenie nie jest zbyt precyzyjne, ale pozwól mi spróbować sformułować je w nieco bardziej formalny sposób: Dla każdego typu kolekcji Cistnieje typ C_LF bez blokady, który oferuje ten sam zestaw operacji i gdzie każda operacja na C_LF ma taką samą złożoność-O jak odpowiednia operacja na C.

Nawiasem mówiąc, nie oczekuję transformacji.

— MSalters
źródło

Jako nie-ekspert zastanawiam się, czy „bez blokady” można rygorystycznie zdefiniować.

— Tsuyoshi Ito

@Suresh: Może synonim „struktury danych”?

— Tsuyoshi Ito

Co jeśli po prostu weźmiesz implementację STM (programową pamięć transakcyjną) bez blokady i zaimplementujesz jakieś struktury danych?

— Jukka Suomela

@Tsuyoshi: Myślę, że nie ma formalnej definicji blokady bez blokady. Nieformalnie oznacza to, że nie używasz instrukcji LOCK procesora, która jest wolna, i trzymasz się szybszego porównywania i zamiany. Ponieważ LOCK można zasymulować za pomocą porównania i zamiany, trudno jest ustalić twardą granicę między „w zasadzie używasz tutaj porównania i zamień, aby zasymulować blokadę (lub transakcji w tym przypadku)” i „och, to jest naprawdę sprytne użycie porównania i zamiany i wcale nie wygląda na to, że symuluje jakąś znaną operację wyższego poziomu. ”

— Radu GRIGore 27.01.11

O ile rozumiem, bezblokowanie jest tutaj rozumiane jako synonim nieblokowania. Nie wymaga to LOCKinstrukcji CPU, ale harmonogramu wątków poprzez mutexes / semaphores / etc.

— MSalters

Odpowiedzi:

Ponieważ byłem trochę zdezorientowany, zacznę od wyjaśnienia kilku pojęć w pytaniu.

Kolekcja . Nie widzę powodu, by poświęcać czas na rygorystyczne definiowanie, co oznacza „zbieranie”, kiedy możemy po prostu zapytać, co się dzieje z ogólnymi strukturami danych. Struktura danych zajmuje część pamięci i ma pewne operacje, które mogą uzyskać dostęp do tej pamięci i które mogą być wywoływane przez użytkowników . Ci użytkownicy mogą być odrębnymi procesorami lub po prostu różnymi wątkami, nie dotyczy nas to. Liczy się tylko to, że mogą wykonywać operacje równolegle.

Bez blokady . Herlihy i Boss twierdzą, że struktura danych jest wolna od blokowania, gdy awaria użytkownika nie uniemożliwia dalszego korzystania ze struktury danych. Na przykład wyobraź sobie, że nalewa się wodę do procesora, który właśnie wstawia węzeł do posortowanego zestawu. Cóż, jeśli inne procesory spróbują później wstawić do tego posortowanego zestawu, powinny odnieść sukces. ( Edycja: Zgodnie z tą definicją, to jest tak, że jeśli używa struktury danych zamki to nie jest lock-wolny, ale to nie jest tak, że jeśli struktura danych nie używa blokad to jest lock-wolny).

Mając te definicje, myślę, że Herlihy i Boss zasadniczo twierdzą, że odpowiedzią jest przekształcenie kluczowych regionów w transakcje.

Ale możesz zapytać, czy to ma taką samą złożoność? Nie jestem pewien, czy pytanie ma sens. Zastanów się push(x) { lock(); stack[size++] = x; unlock(); }. Czy to operacja o stałym czasie? Jeśli zignorujesz operację blokowania, a tym samym innych użytkowników, możesz odpowiedzieć TAK. Jeśli nie chcesz ignorować innych użytkowników, naprawdę nie ma sposobu, aby powiedzieć, czy wypychanie będzie działać w stałym czasie. Jeśli przejdziesz o jeden poziom wyżej i zobaczysz, w jaki sposób stos jest wykorzystywany przez określony algorytm, możesz powiedzieć, że wypychanie zawsze zajmie stały czas (mierzony teraz w zależności od tego, co stanie się wejściem równoległego algorytmu). Ale to naprawdę jest właściwość twojego algorytmu, więc nie ma sensu mówić, że push jest operacją o stałym czasie.

Podsumowując, jeśli zignorujesz, ile użytkownik wykonujący operację czeka na innych użytkowników, wówczas użycie transakcji zamiast regionów krytycznych odpowiada twierdząco. Jeśli nie zignorujesz czasu oczekiwania, musisz spojrzeć na to, jak używana jest struktura danych.

— Radu GRIGore
źródło

Nie jestem zbyt pewien, czy rzeczywiście można uznać, że pushoperacja, jak wspomniano powyżej, nie jest operacją o stałym czasie. W przypadku stałej liczby procesorów i wspólnej implementacji, lockktóra nie gwarantuje głodu, powyższa operacja (w najgorszym przypadku dla dowolnego procesora przyjmuje N_proc * O (1), co można naiwnie założyć jako O (1) ( liczba procesorów jest uwzględniona w ukrytej stałej)

— David Rodríguez - dribeas

n

$n$

f (n)

$f(n)$

f

$f$

Dostęp do pamięci jest tego częstym przypadkiem. Większość analiz algorytmów zakłada, że dostęp do pamięci jest O (1) niezależny od użytej pamięci; architektury pamięci rzeczywistej (z pamięcią podręczną itp.) są lepiej przybliżone przez O (log N), gdzie N jest użytą pamięcią.

— MSalters

Chociaż założenie, że liczba procesorów jest stała, jest dość praktyczne, uniknę go. Problem polega na tym, że złożoności nie można analizować w jednowymiarowy sposób, ponieważ rozmiar problemu musi wzrosnąć zarówno pod względem wielkości danych wejściowych, jak i liczby procesorów, z których oba są wymiarami ortogonalnymi. Zakładając konkretny kontener w standardowej bibliotece C ++ (oczywiście wybieram trudny) jednym z wymagań jest to, aby wszystkie elementy były przechowywane w ciągłym bloku pamięci.

— David Rodríguez - dribeas

Teraz dołączenie elementu do wektora jest zamortyzowaną operacją o stałym czasie (jeśli nie mieści się w uprzednio przydzielonym bloku, wywołanie zajmie liniowy czas na liczbę elementów w kontenerze, ale jeśli zarezerwowany blok pamięci jest nabyte po sekwencji wykładniczej zamortyzowany koszt jest stały). Jeśli wdrożysz pojemnik bezpieczny dla wątków, zablokujesz, a następnie wykonasz zmianę, koszt operacji jest proporcjonalny do kosztu blokady - czego tak naprawdę nie wiem ... ale w pierwszym przybliżeniu można rozważyć głównie stała

— David Rodríguez - dribeas

Myślę, że „KOLEKCJE” oznaczają „kolejki, stosy, powiązane listy, drzewa, ...”

From http://www.cl.cam.ac.uk/research/srg/netos/lock-free/

Dzięki starannemu projektowaniu i implementacji możliwe jest budowanie struktur danych, które są bezpieczne do równoczesnego użycia bez konieczności zarządzania blokadami lub wątkami blokowymi. Te nieblokujące struktury danych mogą zwiększyć wydajność, umożliwiając dodatkową współbieżność i mogą poprawić niezawodność, unikając niektórych problemów spowodowanych przez inwersję priorytetów w ustawieniach lokalnych lub awarie maszyn i łączy w systemach rozproszonych.

Najlepszym ogólnym wprowadzeniem do naszych nieblokujących algorytmów jest obecnie opracowywany dokument „Współbieżne programowanie bez blokad”, który obejmuje nasze projekty wieloprzetwarzowej porównywania i zamiany, opartej na słowach pamięci transakcyjnej oprogramowania i obiektowej pamięci transakcyjnej.

Jeśli „bez blokady” oznacza „nie używaj semaforów, muteksów, monitorów systemu operacyjnego” ... myślę (ale nie jestem ekspertem), że każdą kolekcję można zablokować za pomocą atomowego odczytu i zapisu modyfikować operacje podstawowe, które muszą być obsługiwane przez sprzęt.

$O(\cdot)$

Wyczerpującą dokumentację na ten temat można znaleźć w Internecie:

http://www.google.it/search?q=lock+free+alameterm+filetype%3Apdf

(... i dalsze odniesienia na końcu każdego dokumentu)

— Marzio De Biasi
źródło