Czy „wyścig danych” i „stan wyścigu” to właściwie to samo w kontekście programowania współbieżnego

Odpowiedzi:

142

Nie, to nie to samo. Nie są one podzbiorem siebie nawzajem. Nie są też warunkiem koniecznym ani wystarczającym dla siebie nawzajem.

Definicja wyścigu danych jest dość jasna, dlatego jego wykrywanie można zautomatyzować. Wyścig danych występuje, gdy 2 instrukcje z różnych wątków uzyskują dostęp do tej samej lokalizacji pamięci, co najmniej jeden z tych dostępów jest zapisem i nie ma synchronizacji, która nakazuje jakąkolwiek kolejność między tymi dostępami.

Stan wyścigu to błąd semantyczny. Jest to wada występująca w synchronizacji lub kolejności zdarzeń, która prowadzi do błędnego zachowania programu. Wiele warunków wyścigu może być spowodowanych wyścigami danych, ale nie jest to konieczne.

Rozważmy następujący prosty przykład, w którym x jest wspólną zmienną:

Thread 1    Thread 2

 lock(l)     lock(l)
 x=1         x=2
 unlock(l)   unlock(l)

W tym przykładzie zapisy do x z wątków 1 i 2 są chronione blokadami, dlatego zawsze są wykonywane w jakiejś kolejności wymuszonej przez kolejność, z jaką są uzyskiwane blokady w czasie wykonywania. Oznacza to, że atomowość pisma nie może zostać złamana; zawsze występuje zdarzenie przed relacją między dwoma zapisami w jakimkolwiek wykonaniu. Po prostu nie możemy wiedzieć, który zapis następuje a priori przed drugim.

Nie ma ustalonej kolejności między zapisami, ponieważ zamki tego nie zapewniają. Jeśli poprawność programów jest zagrożona, powiedzmy, kiedy po zapisie do x w wątku 2 następuje zapis do x w wątku 1, mówimy, że wystąpił stan wyścigu, chociaż technicznie nie ma wyścigu danych.

O wiele bardziej przydatne jest wykrywanie warunków wyścigu niż wyścigi danych; jednakże jest to również bardzo trudne do osiągnięcia.

Skonstruowanie odwrotnego przykładu jest również trywialne. Ten wpis na blogu również bardzo dobrze wyjaśnia różnicę, na przykładzie prostej transakcji bankowej.

— Baris Kasikci
źródło
1
„wyścig danych (…) brak synchronizacji, która nakazuje jakąkolwiek kolejność między tymi dostępami”. Jestem trochę zmieszany. W twoim przykładzie operacje mogą wystąpić w obu porządkach (albo = 1, potem = 2, albo na odwrót). Dlaczego nie jest to wyścig danych?
— josinalvo
6
@josinalvo: jest to artefakt technicznej definicji wyścigu danych. Kluczową kwestią jest to, że między dwoma dostępami nastąpi zwolnienie blokady i przejęcie blokady (dla jednego z możliwych zleceń). Z definicji zwolnienie blokady i pobranie blokady ustanawia kolejność między dwoma dostępami, a zatem nie ma wyścigu danych.
— Baris Kasikci
Synchronizacja nigdy nie narzuca żadnego konkretnego porządku między operacjami, więc nie jest to zbyt szczęśliwy sposób wyrażenia tego. Z drugiej strony JMM określa, że ​​dla każdej operacji odczytu musi istnieć określona operacja zapisu, którą obserwuje, nawet w wyścigu danych. Trudno jest uniknąć wyraźnego wspominania o zdarzeniach przed i kolejności synchronizacji, ale nawet definicja JLS jest błędna, wspominając o zdarzeniu się przed : z definicji dwa jednoczesne zapisy ulotne stanowią wyścig danych.
— Marko Topolnik
@BarisKasikci „ustanawia zamówienie” nie ma żadnego znaczenia, jeśli o mnie chodzi. To tylko łajdackie słowa. Szczerze nie wierzę, że „wyścig danych” jest pojęciem zdalnie użytecznym, ponieważ dosłownie każda lokalizacja pamięci, do której uzyskuje dostęp wiele wątków, może zostać uznana za
— biorącą udział
Pary zwolnij-przejmij zawsze ustalają kolejność. Ogólne wyjaśnienie jest długie, ale trywialnym przykładem jest para sygnał-oczekiwanie. @Noldorin „Ustanawia porządek” odnosi się do kolejności zdarzają się przed, co jest kluczową koncepcją teorii współbieżności (patrz przełomowy artykuł Lamporta na temat tego, co wydarzyło się przed relacją) i systemów rozproszonych. Wyścigi danych są użyteczną koncepcją, ponieważ ich obecność stwarza wiele problemów (np. Niezdefiniowana semantyka zgodnie z modelem pamięci C ++, bardzo złożona semantyka w Javie itp.). Ich wykrywanie i eliminacja stanowią obszerną literaturę naukową i praktyczną.
— Baris Kasikci
20

Według Wikipedii termin „stan wyścigu” jest używany od czasów pierwszych elektronicznych bramek logicznych. W kontekście języka Java stan wyścigu może dotyczyć dowolnego zasobu, takiego jak plik, połączenie sieciowe, wątek z puli wątków itp.

Termin „wyścig danych” najlepiej jest zarezerwowany dla jego specyficznego znaczenia zdefiniowanego przez JLS .

Najbardziej interesującym przypadkiem jest sytuacja wyścigu, która jest bardzo podobna do wyścigu danych, ale nadal nim nie jest, jak w tym prostym przykładzie:

class Race {
  static volatile int i;
  static int uniqueInt() { return i++; }
}

Ponieważ ijest niestabilny, nie ma wyścigu danych; jednak z punktu widzenia poprawności programu istnieje warunek wyścigu ze względu na nieatomowość dwóch operacji: odczytu i, zapisu i+1. Wiele wątków może otrzymać tę samą wartość z uniqueInt.

— Marko Topolnik
źródło
1
czy możesz dodać wiersz w swojej odpowiedzi opisujący, co data racewłaściwie oznacza w JLS?
— Geek
@geek Słowo „JLS” jest hiperłączem do odpowiedniej sekcji JLS.
— Marko Topolnik
@MarkoTopolnik Jestem trochę zdezorientowany przykładem. Czy mógłbyś wyjaśnić: „Ponieważ i jest niestabilny, nie ma wyścigu danych”? Zmienność zapewniała tylko to, że jest widoczna, ale nadal: 1) nie jest zsynchronizowana i wiele wątków może jednocześnie czytać / pisać i 2) jest współdzielonym polem nieostatecznym, więc zgodnie z Java Concurrency in Practice (również cytowane poniżej) , to wyścig danych, a nie stan wyścigu, prawda?
— aniliitb 10
@ aniliitb10 Zamiast polegać na cytatach z drugiej ręki wyrwanych z kontekstu, należy przejrzeć sekcję JLS 17.4, do której odsyłam w mojej odpowiedzi. Dostęp do zmiennej nietrwałej jest działaniem synchronizującym zdefiniowanym w §17.4.2.
— Marko Topolnik
@ aniliitb10 Votaltiles nie powoduje wyścigu danych, ponieważ można zamówić ich dostęp. Oznacza to, że możesz rozumować ich kolejność w ten lub inny sposób, prowadząc do innego wyniku. Dzięki wyścigowi danych nie masz możliwości uzasadnienia zamówienia. Na przykład operacja i ++ każdego wątku może po prostu wystąpić na ich odpowiedniej lokalnie buforowanej wartości i. Globalnie nie masz możliwości uporządkowania tych operacji (z punktu widzenia programisty) - chyba że masz określony model pamięci języka.
— Xiao-Feng Li
3

Nie, są różne i żaden z nich nie jest podzbiorem jednego lub odwrotnie.

Termin wyścig jest często mylony z powiązanym terminem wyścig danych, który pojawia się, gdy synchronizacja nie jest używana do koordynowania całego dostępu do współdzielonego pola nie ostatecznego. Ryzykujesz wyścig danych za każdym razem, gdy wątek zapisze zmienną, która może następnie zostać odczytana przez inny wątek lub odczyta zmienną, która mogła zostać ostatnio zapisana przez inny wątek, jeśli oba wątki nie używają synchronizacji; kod z wyścigami danych nie ma użytecznej zdefiniowanej semantyki w modelu pamięci Java. Nie wszystkie warunki wyścigu to wyścigi danych, a nie wszystkie wyścigi danych są warunkami wyścigu, ale oba mogą powodować niepowodzenia równoległych programów w nieprzewidywalny sposób.

Zaczerpnięte z doskonałej książki - Java Concurrency in Practice autorstwa Joshua Bloch & Co.

— Shirgill Farhan
źródło
Zauważ, że pytanie ma tag niezależny od języka.
— martinkunev
1

TL; DR: Rozróżnienie między rasą danych a stanem wyścigu zależy od natury sformułowania problemu oraz od tego, gdzie wyznaczyć granicę między niezdefiniowanym zachowaniem a dobrze zdefiniowanym, ale nieokreślonym zachowaniem. Obecne rozróżnienie jest konwencjonalne i najlepiej odzwierciedla interfejs między architektem procesora a językiem programowania.

1. Semantyka

Wyścig danych w szczególności odnosi się do niezsynchronizowanych sprzecznych „dostępów do pamięci” (lub działań lub operacji) do tej samej lokalizacji pamięci. Jeśli nie ma konfliktu w dostępie do pamięci, podczas gdy nadal występuje nieokreślone zachowanie spowodowane kolejnością operacji, jest to stan wyścigu.

Uwaga: „Dostęp do pamięci” ma tutaj określone znaczenie. Odnoszą się one do „czystej” operacji ładowania lub przechowywania pamięci, bez żadnej dodatkowej semantyki. Na przykład magazyn pamięci z jednego wątku nie (koniecznie) wie, ile czasu zajmie zapisanie danych do pamięci, a ostatecznie propagacja do innego wątku. W innym przykładzie, magazyn pamięci w jednej lokalizacji przed innym magazynem w innej lokalizacji przez ten sam wątek nie gwarantuje (koniecznie), że pierwsze dane zapisane w pamięci będą przed drugą. W rezultacie kolejność tych czystych dostępów do pamięci nie (koniecznie) może być „uzasadniona” i wszystko może się zdarzyć, chyba że jest dobrze zdefiniowane w inny sposób.

Kiedy „dostęp do pamięci” jest dobrze zdefiniowany pod względem kolejności poprzez synchronizację, dodatkowa semantyka może zapewnić, że nawet jeśli czas dostępu do pamięci jest nieokreślony, ich kolejność może być „uzasadniona” poprzez synchronizacje. Należy zauważyć, że chociaż kolejność między dostępami do pamięci może być uzasadniona, niekoniecznie są one określone, stąd stan wyścigu.

2. Skąd ta różnica?

Ale jeśli kolejność jest nadal nieokreślona w stanie wyścigu, po co zawracać sobie głowę odróżnianiem go od wyścigu danych? Powód jest raczej praktyczny niż teoretyczny. Dzieje się tak, ponieważ istnieje różnica w interfejsie między językiem programowania a architekturą procesora.

Instrukcja ładowania / przechowywania pamięci w nowoczesnej architekturze jest zwykle implementowana jako „czysty” dostęp do pamięci, ze względu na charakter potoku poza kolejnością, spekulację, wielopoziomową pamięć podręczną, połączenia między procesorami i ramami, zwłaszcza wielordzeniowe itp. Jest wiele czynników prowadzących do nieokreślonego czasu i kolejności. Wymuszanie porządkowania dla każdej instrukcji pamięci wiąże się z ogromnymi karami, zwłaszcza w przypadku konstrukcji procesora obsługującego wielordzeniowe. Tak więc semantyka porządkowania ma dodatkowe instrukcje, takie jak różne bariery (lub ogrodzenia).

Wyścig danych to sytuacja, w której wykonywane są instrukcje procesora bez dodatkowych przeszkód, które pomagają w rozumowaniu kolejności sprzecznych dostępów do pamięci. Rezultat jest nie tylko nieokreślony, ale także być może bardzo dziwny, np. Dwa zapisy w tym samym miejscu słowa przez różne wątki mogą skutkować każdym zapisem połowy słowa lub mogą działać tylko na ich lokalnie buforowanych wartościach. - Są to niezdefiniowane zachowania z punktu widzenia programisty. Ale są (zwykle) dobrze zdefiniowane z punktu widzenia architekta procesorów.

Programiści muszą mieć sposób, aby uzasadnić wykonanie swojego kodu. Wyścig danych to coś, czego nie mogą mieć sensu, dlatego zawsze należy go unikać (normalnie). Dlatego specyfikacje języka, które są wystarczająco niskie, zwykle definiują wyścig danych jako niezdefiniowane zachowanie, różniące się od dobrze zdefiniowanego zachowania pamięci warunków wyścigu.

3. Modele pamięci językowej

Różne procesory mogą mieć różne zachowania dostępu do pamięci, tj. Model pamięci procesora. Dla programistów jest to niezręczne badanie modelu pamięci każdego nowoczesnego procesora, a następnie opracowywanie programów, które mogą z nich skorzystać. Pożądane jest, aby język mógł zdefiniować model pamięci, tak aby programy tego języka zawsze zachowywały się zgodnie z oczekiwaniami, zgodnie z definicją modelu pamięci. Dlatego Java i C ++ mają zdefiniowane modele pamięci. Obowiązkiem programistów kompilatora / środowiska wykonawczego jest zapewnienie wymuszania modeli pamięci języka w różnych architekturach procesorów.

To powiedziawszy, jeśli język nie chce ujawniać niskiego poziomu zachowania procesora (i jest skłonny poświęcić pewne korzyści wydajnościowe współczesnych architektur), może zdefiniować model pamięci, który całkowicie ukrywa szczegóły „czystego” dostęp do pamięci, ale stosuj semantykę porządkowania dla wszystkich operacji pamięciowych. Następnie programiści kompilatora / środowiska uruchomieniowego mogą traktować każdą zmienną pamięci jako ulotną we wszystkich architekturach procesorów. W przypadku tych języków (które obsługują pamięć współdzieloną między wątkami) nie ma wyścigów danych, ale nadal mogą występować warunki wyścigu, nawet w przypadku języka o pełnej spójności sekwencyjnej.

Z drugiej strony model pamięci procesora może być bardziej rygorystyczny (lub mniej rozluźniony lub na wyższym poziomie), np. Wdrażając sekwencyjną spójność, tak jak robił to wczesny procesor. Następnie wszystkie operacje pamięci są uporządkowane i nie istnieje wyścig danych dla żadnego języka uruchomionego w procesorze.

4. Wniosek

Wracając do pierwotnego pytania, IMHO dobrze jest zdefiniować wyścig danych jako szczególny przypadek stanu wyścigu, a stan wyścigu na jednym poziomie może stać się wyścigiem danych na wyższym poziomie. Zależy to od natury sformułowania problemu i od tego, gdzie wyznaczyć granicę między niezdefiniowanym zachowaniem a dobrze zdefiniowanym, ale nieokreślonym zachowaniem. Po prostu obecna konwencja definiuje granicę na interfejsie język-procesor, niekoniecznie oznacza, że ​​zawsze i musi tak być; ale obecna konwencja prawdopodobnie najlepiej odzwierciedla najnowocześniejszy interfejs (i mądrość) między architektem procesora a językiem programowania.

— Xiao-Feng Li
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.