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 CLF bez blokady, który oferuje ten sam zestaw operacji i gdzie każda operacja na CLF ma taką samą złożoność-O jak odpowiednia operacja na C.
Nawiasem mówiąc, nie oczekuję transformacji.
LOCKinstrukcji CPU, ale harmonogramu wątków poprzez mutexes / semaphores / etc.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.
źródło
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)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.
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)
źródło