Jak bezpieczeństwo wątków może być zapewnione przez język programowania podobny do bezpieczeństwa pamięci zapewnianego przez Java i C #?

10

Java i C # zapewniają bezpieczeństwo pamięci, sprawdzając granice tablic i dereferencje wskaźnika.

Jakie mechanizmy można zaimplementować w języku programowania, aby zapobiec możliwym warunkom wyścigowym i impasom?

mrpyo
źródło
3
Być może zainteresuje Cię to, co robi Rust: nieustraszona współzależność z Rustem
Vincent Savard
2
Spraw, aby wszystko było niezmienne lub spraw, aby wszystko było asynchroniczne z bezpiecznymi kanałami. Możesz być także zainteresowany Go i Erlang .
Theraot
@Theraot „spraw, aby wszystko było asynchroniczne z bezpiecznymi kanałami” - szkoda, że ​​nie możesz o tym mówić.
mrpyo
2
@ mpypy nie ujawniasz procesów ani wątków, każde wywołanie jest obietnicą, wszystko działa równolegle (w środowisku wykonawczym planuje ich wykonanie i tworzenie / łączenie wątków systemowych za scenami w razie potrzeby), a logika chroniąca stan jest w mechanizmach który przekazuje informacje dookoła ... środowisko wykonawcze może automatycznie serializować poprzez szeregowanie, i byłaby standardowa biblioteka z bezpiecznym wątkiem dla bardziej niuansowych zachowań, w szczególności potrzebne są producent / konsument i agregacje.
Theraot
2
Nawiasem mówiąc, istnieje inne możliwe podejście: pamięć transakcyjna .
Theraot

Odpowiedzi:

14

Wyścigi występują, gdy masz jednocześnie aliasing obiektu i przynajmniej jeden z nich jest mutowany.

Aby zapobiec wyścigom, musisz sprawić, by jeden lub więcej z tych warunków był nieprawdziwy.

Różne podejścia dotyczą różnych aspektów. Programowanie funkcjonalne podkreśla niezmienność, która usuwa zmienność. Blokowanie / atomika usuwają jednoczesność. Typy afiniczne usuwają aliasing (Rust usuwa modyfikowalne aliasing). Modele aktorów zwykle usuwają aliasing.

Możesz ograniczyć obiekty, które można aliasować, aby łatwiej było uniknąć powyższych warunków. Tam właśnie wkraczają kanały i / lub style przekazywania wiadomości. Nie możesz aliasować dowolnej pamięci, tylko koniec kanału lub kolejki, która jest skonfigurowana tak, aby była wolna od wyścigów. Zwykle przez unikanie jednoczesności, tj. Zamków lub atomów.

Minusem tych różnych mechanizmów jest to, że ograniczają programy, które można pisać. Im bardziej tępe ograniczenie, tym mniej programów. Więc żadne aliasing lub modyfikowalność nie działają i są łatwe do uzasadnienia, ale są bardzo ograniczające.

Właśnie dlatego Rust wywołuje takie poruszenie. Jest to język inżynierski (w porównaniu z językiem akademickim), który obsługuje aliasing i zmienność, ale ma kompilator sprawdzający, czy nie występują one jednocześnie. Chociaż nie jest to idealne, pozwala bezpiecznie pisać większą klasę programów niż wiele jego poprzedników.

Alex
źródło
11

Java i C # zapewniają bezpieczeństwo pamięci, sprawdzając granice tablic i dereferencje wskaźnika.

Ważne jest, aby najpierw pomyśleć o tym, jak robią to C # i Java. Robią to, konwertując to, co jest niezdefiniowane zachowanie w C lub C ++ w określone zachowanie: zawiesić program . Dereferencje zerowe i wyjątki indeksu tablicowego nigdy nie powinny być wychwytywane w poprawnym programie C # lub Java; nie powinny się zdarzyć w pierwszej kolejności, ponieważ program nie powinien mieć tego błędu.

Ale nie sądzę, że masz na myśli to pytanie! Moglibyśmy dość łatwo napisać środowisko uruchomieniowe „zakleszczone”, które okresowo sprawdza, czy n wzajemnie na siebie nie czeka i kończy program, jeśli tak się stanie, ale nie sądzę, żeby to cię zadowoliło.

Jakie mechanizmy można zaimplementować w języku programowania, aby zapobiec możliwym warunkom wyścigowym i impasom?

Kolejnym problemem, przed którym stoimy, jest to, że „warunki wyścigu”, w przeciwieństwie do impasu, są trudne do wykrycia. Pamiętaj, że naszym celem w bezpieczeństwie nici nie jest eliminowanie wyścigów . Chcemy, aby program był poprawny bez względu na to, kto wygra wyścig ! Problem z warunkami wyścigu nie polega na tym, że dwa wątki biegną w nieokreślonej kolejności i nie wiemy, kto skończy jako pierwszy. Problem z warunkami wyścigu polega na tym, że programiści zapominają, że niektóre zamówienia wykończenia wątków są możliwe i nie uwzględniają tej możliwości.

Więc twoje pytanie sprowadza się w zasadzie do „czy jest jakiś sposób, że język programowania może zapewnić, że mój program jest poprawny?” a odpowiedź na to pytanie brzmi w praktyce nie.

Do tej pory krytykowałem tylko twoje pytanie. Pozwól mi spróbować zmienić bieg tutaj i zająć się duchem twojego pytania. Czy projektanci języków mogą dokonać wyboru, który złagodziłby straszną sytuację związaną z wielowątkowością?

Sytuacja jest naprawdę okropna! Poprawienie wielowątkowego kodu, szczególnie w przypadku słabych architektur modeli pamięci, jest bardzo, bardzo trudne. Warto zastanowić się, dlaczego jest to trudne:

  • Trudno uzasadnić wiele wątków kontroli w jednym procesie. Jeden wątek jest wystarczająco trudny!
  • Abstrakcje stają się bardzo nieszczelne w świecie wielowątkowym. W świecie jednowątkowym gwarantujemy, że programy zachowują się tak, jakby były uruchamiane po kolei, nawet jeśli nie są uruchamiane po kolei. W świecie wielowątkowym tak już nie jest; Optymalizacje, które byłyby niewidoczne dla pojedynczego wątku, stały się widoczne, a teraz programista musi zrozumieć te możliwe optymalizacje.
  • Ale robi się coraz gorzej. Specyfikacja C # mówi, że implementacja NIE jest wymagana, aby mieć spójną kolejność odczytu i zapisu, która może być uzgodniona przez wszystkie wątki . Pogląd, że w ogóle są „wyścigi” i że jest wyraźny zwycięzca, w rzeczywistości nie jest prawdziwy! Rozważ sytuację, w której istnieją dwa zapisy i dwa odczyty niektórych zmiennych w wielu wątkach. W rozsądnym świecie moglibyśmy myśleć: „no cóż, nie wiemy, kto wygra wyścigi, ale przynajmniej będzie wyścig i ktoś wygra”. Nie jesteśmy w tym rozsądnym świecie. C # pozwala wielu wątkom nie zgadzać się co do kolejności odczytu i zapisu; niekoniecznie istnieje spójny świat, który wszyscy obserwują.

Jest więc oczywisty sposób, że projektanci języków mogą poprawić sytuację. Porzuć wydajność wygrywa nowoczesne procesory . Spraw, aby wszystkie programy, nawet te wielowątkowe, miały wyjątkowo silny model pamięci. Spowoduje to, że programy wielowątkowe będą o wiele, wiele razy wolniejsze, co działa bezpośrednio przeciwko powodom posiadania programów wielowątkowych w pierwszej kolejności: w celu zwiększenia wydajności.

Nawet pomijając model pamięci, istnieją inne powody, dla których wielowątkowość jest trudna:

  • Zapobieganie impasom wymaga analizy całego programu; musisz znać globalną kolejność, w jakiej można wyjąć blokady, i egzekwować tę kolejność w całym programie, nawet jeśli program składa się z komponentów napisanych w różnym czasie przez różne organizacje.
  • Podstawowym narzędziem, które dajemy tobie oswoić wielowątkowość, jest blokada, ale blokad nie można skomponować .

Ten ostatni punkt zawiera dalsze wyjaśnienia. Przez „kompozycyjny” rozumiem co następuje:

Załóżmy, że chcemy obliczyć int int dublet. Piszemy poprawną implementację obliczeń:

int F(double x) { correct implementation here }

Załóżmy, że chcemy obliczyć ciąg podany jako int:

string G(int y) { correct implementation here }

Teraz jeśli chcemy obliczyć ciąg znaków, biorąc pod uwagę podwójne:

double d = whatever;
string r = G(F(d));

G i F można skomponować jako prawidłowe rozwiązanie bardziej złożonego problemu.

Ale zamki nie mają tej właściwości z powodu zakleszczeń. Prawidłowa metoda M1, która przyjmuje blokady w kolejności L1, L2, oraz poprawna metoda M2, która przyjmuje blokady w kolejności L2, L1, nie mogą być używane w tym samym programie bez utworzenia niepoprawnego programu. Zamki sprawiają, że nie można powiedzieć „każda metoda jest poprawna, więc wszystko jest prawidłowe”.

Co więc możemy zrobić jako projektanci języków?

Po pierwsze, nie idź tam. Wiele wątków kontroli w jednym programie jest złym pomysłem, a dzielenie pamięci między wątkami jest złym pomysłem, więc nie umieszczaj go w języku ani w środowisku wykonawczym.

To najwyraźniej nie jest starter.

Zwróćmy zatem uwagę na bardziej fundamentalne pytanie: dlaczego w ogóle mamy wiele wątków? Są dwa główne powody i często łączą się w to samo, choć są bardzo różne. Są skonfliktowane, ponieważ oba dotyczą zarządzania opóźnieniami.

  • Niepoprawnie tworzymy wątki, aby zarządzać opóźnieniami we / wy. Musisz napisać duży plik, uzyskać dostęp do zdalnej bazy danych, cokolwiek, utworzyć wątek roboczy zamiast blokować wątek interfejsu użytkownika.

Kiepski pomysł. Zamiast tego należy użyć asynchronicznej jednowątkowej za pomocą coroutines. C # robi to pięknie. Java, nie tak dobrze. Jest to jednak główny sposób, w jaki obecny projektanci języków pomagają rozwiązać problem wątków. awaitOperator C # (inspirowany f # asynchroniczne Procedury i drugi stan techniki) jest włączone w coraz większej liczbie języków.

  • Właściwie tworzymy wątki, aby nasycić bezczynne procesory ciężką pracą obliczeniową. Zasadniczo używamy wątków jako lekkich procesów.

Projektanci języków mogą pomóc, tworząc funkcje językowe, które działają dobrze z równoległością. Pomyśl na przykład o tym, jak LINQ rozszerza się tak naturalnie na PLINQ. Jeśli jesteś rozsądną osobą i ograniczasz swoje operacje TPL do operacji związanych z procesorem, które są wysoce równoległe i nie dzielą pamięci, możesz tutaj uzyskać duże wygrane.

Co jeszcze możemy zrobić?

  • Spraw, aby kompilator wykrył najbardziej błędne błędy i przekształcił je w ostrzeżenia lub błędy.

C # nie pozwala ci czekać w zamku, ponieważ jest to przepis na zakleszczenia. C # nie pozwala na zablokowanie typu wartości, ponieważ zawsze jest to niewłaściwa czynność; blokujesz pudełko, a nie wartość. C # ostrzega cię, jeśli masz alias niestabilny, ponieważ alias nie narzuca semantyki pobierania / wydawania. Kompilator może wykrywać typowe problemy i im zapobiegać na wiele innych sposobów.

  • Zaprojektuj funkcje „jakości”, w których najbardziej naturalny sposób to również najbardziej poprawny sposób.

C # i Java popełniły ogromny błąd projektowy, pozwalając na użycie dowolnego obiektu referencyjnego jako monitora. To zachęca do wszelkiego rodzaju złych praktyk, które utrudniają wyśledzenie impasu i trudniej jest zapobiegać im statycznie. I marnuje bajty w każdym nagłówku obiektu. Należy wymagać, aby monitory pochodziły z klasy monitorów.

  • Ogromna ilość czasu i wysiłku Microsoft Research poświęcona była próbie dodania pamięci transakcyjnej oprogramowania do języka podobnego do C # i nigdy nie osiągnęli wystarczającej wydajności, aby włączyć ją do głównego języka.

STM to piękny pomysł i bawiłem się implementacjami zabawek w Haskell; pozwala znacznie bardziej elegancko komponować prawidłowe rozwiązania z prawidłowych części niż rozwiązania oparte na blokadzie. Nie wiem jednak wystarczająco dużo na temat szczegółów, aby stwierdzić, dlaczego nie można było sprawić, by działało na dużą skalę; spytaj Joe Duffy'ego następnym razem, gdy go zobaczysz.

  • W innej odpowiedzi wspomniano już o niezmienności. Jeśli masz niezmienność połączoną z wydajnymi koroutynami, możesz budować takie cechy, jak model aktora bezpośrednio w swoim języku; na przykład Erlang.

Przeprowadzono wiele badań nad językami opartymi na rachunku procesowym i nie rozumiem tej przestrzeni zbyt dobrze; spróbuj sam przeczytać kilka artykułów na ten temat i sprawdź, czy uzyskasz jakieś spostrzeżenia.

  • Ułatw stronom trzecim pisanie dobrych analizatorów

Po tym, jak pracowałem w Microsoft na Roslyn, pracowałem w Coverity, a jedną z rzeczy, które zrobiłem, było uzyskanie frontonu analizatora przy użyciu Roslyn. Dysponując dokładną analizą leksykalną, składniową i semantyczną firmy Microsoft, mogliśmy skoncentrować się na ciężkiej pracy nad pisaniem detektorów, które wykryły typowe problemy z wielowątkowością.

  • Podnieś poziom abstrakcji

Podstawowym powodem, dla którego mamy wyścigi, impasy i tak dalej, jest to, że piszemy programy, które mówią, co robić , i okazuje się, że wszyscy jesteśmy gówniani w pisaniu programów imperatywnych; komputer robi to, co mu powiesz, a my mówimy, żeby robił złe rzeczy. Wiele współczesnych języków programowania coraz częściej mówi o programowaniu deklaratywnym: powiedz, jakie wyniki chcesz, i pozwól kompilatorowi znaleźć skuteczny, bezpieczny i prawidłowy sposób na osiągnięcie tego wyniku. Ponownie pomyśl o LINQ; chcemy, żebyś powiedział from c in customers select c.FirstName, co wyraża intencję . Pozwól kompilatorowi dowiedzieć się, jak napisać kod.

  • Używaj komputerów do rozwiązywania problemów z komputerem.

Algorytmy uczenia maszynowego są znacznie lepsze w niektórych zadaniach niż algorytmy kodowane ręcznie, choć oczywiście istnieje wiele kompromisów, w tym poprawność, czas potrzebny na szkolenie, błędy wynikające z niewłaściwego szkolenia i tak dalej. Jest jednak prawdopodobne, że bardzo wiele zadań, które obecnie kodujemy „ręcznie”, wkrótce będzie można zastosować do rozwiązań generowanych maszynowo. Jeśli ludzie nie piszą kodu, nie piszą błędów.

Przepraszam, że trochę się tam włóczyło; jest to ogromny i trudny temat, a społeczność PL nie wypracowała wyraźnego konsensusu w ciągu 20 lat, gdy śledzę postępy w tej dziedzinie problemów.

Eric Lippert
źródło
„Więc twoje pytanie w zasadzie sprowadza się do:„ czy jest jakiś sposób, że język programowania może zapewnić, że mój program jest poprawny? ”, A odpowiedź na to pytanie w praktyce brzmi„ nie ”. - właściwie jest to całkiem możliwe - nazywa się to weryfikacją formalną i chociaż jest to niewygodne, jestem pewien, że jest to rutynowo wykonywane na krytycznym oprogramowaniu, więc nie nazwałbym tego niepraktycznym. Ale będąc projektantem językowym prawdopodobnie wiesz o tym ...
mrpyo
6
@mrpyo: Jestem tego świadomy. Jest wiele problemów. Po pierwsze: raz uczestniczyłem w formalnej konferencji weryfikacyjnej, podczas której zespół badawczy MSFT przedstawił ekscytujący nowy wynik: byli w stanie rozszerzyć swoją technikę weryfikacji programów wielowątkowych o długości do dwudziestu linii i uruchomić weryfikator w niecały tydzień. To była ciekawa prezentacja, ale bezużyteczna dla mnie; Miałem 20 milionów programów do analizy.
Eric Lippert
@mrpyo: Po drugie, jak już wspomniałem, dużym problemem związanym z blokadami jest to, że program wykonany z metod bezpiecznych dla wątków niekoniecznie jest programem bezpiecznym dla wątków. Formalna weryfikacja poszczególnych metod niekoniecznie pomaga, a analiza programów jest trudna w przypadku programów nietrywialnych.
Eric Lippert
6
@mrpyo: Po trzecie, dużym problemem związanym z analizą formalną jest to, co zasadniczo robimy? Prezentujemy specyfikację warunków wstępnych i dodatkowych, a następnie sprawdzamy, czy program spełnia tę specyfikację. Świetny; w teorii jest to całkowicie wykonalne. W jakim języku jest napisana specyfikacja? Jeśli istnieje jednoznaczny, weryfikowalny język specyfikacji, napiszmy po prostu wszystkie nasze programy w tym języku i skompilujmy to . Dlaczego tego nie robimy? Ponieważ okazuje się, że naprawdę trudno jest pisać poprawne programy również w języku specyfikacji!
Eric Lippert
2
Możliwa jest analiza wniosku pod kątem poprawności przy użyciu warunków wstępnych / dodatkowych (np. Przy użyciu umów kodowania). Jednak taka analiza jest możliwa tylko pod warunkiem, że warunki są możliwe do skomponowania, a blokady nie. Zauważę też, że pisanie programu w sposób umożliwiający analizę wymaga starannej dyscypliny. Na przykład aplikacje, które nie są ściśle zgodne z zasadą substytucji Liskowa, mają tendencję do odrzucania analizy.
Brian