Czytanie 17: współbieżność

#### oprogramowanie w 6.005

#### cele + przekazywanie wiadomości & pamięć współdzielona+ procesy & wątki+ krojenie czasu+ Warunki wyścigu## współbieżność*współbieżność* oznacza, że wiele obliczeń dzieje się w tym samym czasie. Współbieżność jest wszędzie w nowoczesnym programowaniu, czy tego chcemy, czy nie: + wiele komputerów w sieci+ wiele aplikacji działających na jednym komputerze+ wiele procesorów w komputerze (obecnie często wiele rdzeni procesora na jednym chipie)współbieżność jest niezbędna we współczesnym programowaniu: + strony internetowe muszą obsługiwać wielu jednoczesnych użytkowników.+ Aplikacje mobilne muszą wykonać część swojego przetwarzania na serwerach (“w chmurze”).+ Graficzne interfejsy użytkownika prawie zawsze wymagają pracy w tle, która nie przerywa użytkownikowi. Na przykład Eclipse kompiluje Twój kod Java podczas jego edycji.Możliwość programowania przy użyciu współbieżności będzie nadal ważna w przyszłości. Szybkość zegara procesora nie wzrasta. Zamiast tego otrzymujemy więcej rdzeni z każdą nową generacją chipów. Więc w przyszłości, aby obliczenia działały szybciej, będziemy musieli podzielić obliczenia na równoległe części.## Dwa modele programowania współbieżnego istnieją dwa wspólne modele programowania współbieżnego: * pamięć współdzielona * i * przekazywanie wiadomości*.

* * pamięć współdzielona.** W modelu współbieżności pamięci współbieżnej współbieżne Moduły współdziałają poprzez odczyt i zapis obiektów współdzielonych w pamięci. Inne przykłady modelu pamięci współdzielonej: + a i B mogą być dwoma procesorami (lub rdzeniami procesora) w tym samym komputerze, współdzielącymi tę samą fizyczną pamięć.+ A i B mogą być dwoma programami działającymi na tym samym komputerze, współdzielącymi wspólny system plików z plikami, które mogą odczytywać i zapisywać.+ A i B mogą być dwoma wątkami w tym samym programie Java (wyjaśnimy, czym jest wątek poniżej), dzieląc te same obiekty Java.

**przekazywanie wiadomości.** W modelu przekazywania wiadomości współbieżne Moduły współdziałają, wysyłając wiadomości do siebie za pośrednictwem kanału komunikacyjnego. Moduły wysyłają wiadomości, a wiadomości przychodzące do każdego modułu są kolejkowane do obsługi. Przykłady obejmują:+ A i B mogą być dwoma komputerami w sieci, komunikującymi się za pomocą połączeń sieciowych.+ A i B mogą być przeglądarką internetową i serwerem internetowym — a otwiera połączenie z B, pyta o stronę internetową, A B wysyła dane strony internetowej z powrotem do A.+ A i B mogą być komunikatorem i serwerem.+ A i B mogą być dwoma programami uruchomionymi na tym samym komputerze, których wejście i wyjście zostały połączone przez rurę, jak `LS / grep ‘ wpisane do wiersza polecenia.## Processes, Threads, Time-slicingmodele message-passing i shared-memory są o tym, jak współbieżne Moduły się komunikują. Same moduły współbieżne występują w dwóch różnych rodzajach: procesach i wątkach.**Proces**. Proces jest instancją uruchomionego programu, który jest * odizolowany* od innych procesów na tej samej maszynie. W szczególności ma własną prywatną sekcję pamięci maszyny.Abstrakcją procesu jest * komputer wirtualny*. To sprawia, że program ma wrażenie, że ma całą maszynę dla siebie-jak nowy komputer został stworzony, ze świeżą pamięcią, tylko po to, aby uruchomić ten program.Podobnie jak komputery podłączone do sieci, procesy zwykle nie współdzielą między sobą pamięci. Proces nie może w ogóle uzyskać dostępu do pamięci lub obiektów innego procesu. Współdzielenie pamięci między procesami jest* możliwe * w większości systemów operacyjnych, ale wymaga specjalnego wysiłku. Natomiast nowy Proces jest automatycznie gotowy do przekazywania wiadomości, ponieważ jest tworzony ze standardowymi wejściowymi & wyjściowymi strumieniami, które są `systemem.out ” i “System.in’ strumienie, których używałeś w Javie.** Wątek**. Wątek jest locus kontroli wewnątrz uruchomionego programu. Pomyśl o tym jak o miejscu w uruchamianym programie, plus stosie wywołań metod, które doprowadziły do tego miejsca, do którego trzeba będzie powrócić.Tak jak proces reprezentuje komputer wirtualny, tak abstrakcja wątku reprezentuje *wirtualny procesor*. Tworzenie nowego wątku symuluje tworzenie nowego procesora wewnątrz wirtualnego komputera reprezentowanego przez proces. Ten nowy wirtualny procesor uruchamia ten sam program i dzieli tę samą pamięć, co inne wątki w procesie.Wątki są automatycznie gotowe do pamięci współdzielonej, ponieważ wątki współdzielą całą pamięć w procesie. Wymaga specjalnego wysiłku, aby uzyskać pamięć “thread-local”, która jest prywatna dla pojedynczego wątku. Konieczne jest również jawne skonfigurowanie przekazywania wiadomości poprzez tworzenie i używanie struktur danych kolejki. Porozmawiamy o tym, jak to zrobić w przyszłym czytaniu.

Jak mogę mieć wiele równoległych wątków z jednym lub dwoma procesorami w moim komputerze? Gdy istnieje więcej wątków niż procesory, współbieżność jest symulowana przez * * cięcie czasu**, co oznacza, że procesor przełącza się między wątkami. Rysunek po prawej pokazuje, jak trzy wątki T1, T2 i T3 mogą być skrojone w czasie na maszynie, która ma tylko dwa rzeczywiste procesory. Na rysunku czas płynie w dół, więc na początku jeden procesor pracuje z gwintem T1, a drugi z gwintem T2, a następnie drugi procesor przełącza się na uruchamianie gwintu T3. Wątek T2 po prostu zatrzymuje się, aż do następnego cięcia czasu na tym samym procesorze lub innym procesorze.W większości systemów, cięcie czasu dzieje się nieprzewidywalnie i niedeterministycznie, co oznacza, że wątek może zostać wstrzymany lub wznowiony w dowolnym momencie.

mitx: C613ec53e92840a4a506f3062c994673 procesy & wątki# # przykład pamięci współdzielonej Celem tego przykładu jest pokazanie, że programowanie współbieżne jest trudne, ponieważ może zawierać subtelne błędy.

wyobraź sobie, że bank ma Bankomaty, które używają modelu pamięci współdzielonej, więc wszystkie bankomaty mogą odczytywać i zapisywać te same obiekty konta w memory.To zilustrujmy, co może pójść nie tak, uprośćmy bank do jednego konta, z saldem dolara przechowywanym w zmiennej “saldo” i dwiema operacjami “depozyt” i “wypłata”, które po prostu dodają lub usuwają dolara ` “‘ Java / / Załóżmy, że wszystkie bankomaty mają jeden rachunek bankowyprivate static int balance = 0; private static void deposit() { balance = balance + 1;}private static void withdraw () { balance = balance-1;} “‘klienci używają bankomatów do dokonywania transakcji takich jak:“javadeposit(); // Wpłać dolarawithdraw(); // take it back out “‘ w tym prostym przykładzie, każda transakcja jest tylko wpłatą jednego dolara, a następnie wypłatą jednego dolara, więc saldo na koncie powinno pozostać niezmienione. Przez cały dzień każdy bankomat w naszej sieci przetwarza sekwencję transakcji wpłat/wypłat.”‘java / / każdy bankomat wykonuje kilka transakcji, które / / modyfikują saldo, ale pozostawiają je niezmienione afterwardprivate static void cashMachine () {for (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) {deposit (); / / put a dollar in withdraw (); / / take it back out }}“więc na koniec dnia, niezależnie od tego, ile bankomatów było uruchomionych lub ile transakcji zrealizowaliśmy, powinniśmy oczekiwać, że saldo konta nadal będzie równe 0.Ale jeśli uruchomimy ten kod, często odkryjemy, że saldo na koniec dnia to *nie * 0. Jeśli więcej niż jedno wywołanie `cashMachine () ‘ jest uruchomione w tym samym czasie-powiedzmy, na oddzielnych procesorach w tym samym komputerze-wtedy `saldo` może nie być zerowe na koniec dnia. Dlaczego nie?## Interleaving here ‘ s one thing that can happen. Załóżmy, że dwa bankomaty, A i B, pracują jednocześnie nad depozytem. Oto jak krok deposit() zazwyczaj rozkłada się na instrukcje procesora niskiego poziomu:“get balance (balance=0)add 1 write back the result (balance=1)“Gdy a i B działają jednocześnie, te instrukcje niskiego poziomu przeplatają się ze sobą (niektóre mogą być nawet jednoczesne, ale na razie martwimy się o przeplatanie):“a get balance (balance=0)a add 1 A write back the result (balance=1) B get balance (balance=1) B add 1 B write back the result (balance=2) ” `to przeplatanie jest w porządku-kończymy z balance 2, więc zarówno a, jak i B z powodzeniem wpłaciły dolara. Ale co, jeśli przeplot wyglądał tak:”‘A get balance (balance=0) b get balance (balance=0)a add 1 B add 1 A write back the result (balance=1) B write back the result (balance=1)“the balance is now 1 — A’ S dollar was lost! A i B odczytują saldo w tym samym czasie, obliczają oddzielne salda końcowe, a następnie ścigają się, aby zapisać nowe saldo – co nie uwzględniło depozytu drugiego.## Warunki wyścigu jest to przykład * * warunki wyścigu**. Warunek rasy oznacza, że poprawność programu (zadowolenie warunków postkondensacyjnych i niezmienników) zależy od względnego czasu zdarzeń w równoległych obliczeniach A I B. kiedy to się dzieje, mówimy “a jest w wyścigu z B.”Niektóre sploty zdarzeń mogą być w porządku, w tym sensie, że są one zgodne z tym, co pojedynczy, niezwiązany z prądem proces mógłby wytworzyć, ale inne sploty dają błędne odpowiedzi-naruszające warunki postkondensacyjne lub niezmienniki.## Poprawianie kodu nie pomoże Wszystkie te wersje kodu konta bankowego wykazują ten sam stan rasy:”‘java / / wersja 1private static void deposit () { balance = balance + 1;} private static Void withdraw () {balance = balance – 1;}“java// wersja 2private static void deposit () {balance += 1;}private static Void withdraw () {balance -= 1;}“java// wersja 3private static void deposit () {++balance;}private static void withdraw () {–balance;}“nie można powiedzieć po prostu patrząc na kod Javy, jak procesor ma go wykonać. Nie wiadomo, jakie będą niepodzielne operacje atomowe. Nie jest atomowy tylko dlatego, że jest jedną linią Javy. Nie dotyka balansu tylko raz, tylko dlatego, że identyfikator balansu występuje tylko raz w wierszu. Kompilator Javy, a właściwie sam procesor, nie podejmuje żadnych zobowiązań co do tego, jakie operacje niskiego poziomu wygeneruje z twojego kodu. W rzeczywistości typowy nowoczesny kompilator Javy wytwarza dokładnie ten sam kod dla wszystkich trzech tych wersji!Kluczową lekcją jest to, że nie można stwierdzić, patrząc na wyrażenie, czy będzie ono bezpieczne od warunków wyścigowych.

## Zmiana kolejności jest nawet gorsza. Stan rasowy na saldzie konta bankowego można wyjaśnić różnymi przeplotami sekwencyjnych operacji na różnych procesorach. Ale w rzeczywistości, gdy używasz wielu zmiennych i wielu procesorów, nie możesz nawet liczyć na zmiany tych zmiennych, które pojawią się w tej samej kolejności.Oto przykład:“javaprivate boolean ready = false;private int answer = 0; / / computeAnswer działa w jednym threadprivate void computeAnswer () {answer = 42; ready = true;} / / useAnswer działa w innym threadprivate void useAnswer () {while (!ready) { Thread.plon (); } if (answer = = 0) throw new RuntimeException (“answer wasn’ t ready!”);} “‘Mamy dwie metody, które są uruchamiane w różnych wątkach. ‘computeAnswer’ wykonuje długie obliczenia, w końcu wymyśla odpowiedź 42, którą umieszcza w zmiennej answer. Następnie ustawia zmienną ‘ready `na true, aby sygnalizować metodzie działającej w innym wątku,` useAnswer’, że odpowiedź jest gotowa do użycia. Patrząc na kod, ‘answer’ jest ustawione przed ready jest ustawione, więc gdy ‘useAnswer’ widzi ‘ready’ jako prawdziwe, wydaje się rozsądne, że może założyć, że` answer ‘ będzie 42, prawda? Nie.Problem polega na tym, że nowoczesne kompilatory i procesory robią wiele rzeczy, aby Kod był szybki. Jedną z tych rzeczy jest tworzenie tymczasowych kopii zmiennych, takich jak answer I ready w szybszym magazynie (rejestry lub pamięci podręczne na procesorze) i praca z nimi tymczasowo, zanim ostatecznie zapiszą je z powrotem do ich oficjalnej lokalizacji w pamięci. Storeback może występować w innej kolejności niż zmienne, którymi manipulowano w kodzie. Oto, co może się dziać pod okładkami (ale wyrażone w składni Javy, aby było jasne). Procesor tworzy dwie zmienne tymczasowe, `tmpr ‘ i ‘tmpa`, aby manipulować polami ready I answer:`’ javaprivate void computeAnswer() { boolean tmpr = ready; int tmpa = answer; tmpa = 42; tmpr = true; ready = tmpr; // <– co się stanie, jeśli useAnswer() przeplata się tutaj? // ready is set, but answer isn ‘t. answer = tmpa;} “‘ mitx:2bf4beb7ffd5437bbbb9c782bb99b54e Race Conditions## Message Passing Example

Spójrzmy teraz na podejście message-passing do naszego przykładu konta bankowego.Teraz nie tylko Moduły bankomatów, ale także konta są modułami. Moduły współdziałają, wysyłając do siebie wiadomości. Przychodzące żądania są umieszczane w kolejce do obsługi pojedynczo. Nadawca nie przestaje pracować, czekając na odpowiedź na swoje żądanie. Obsługuje więcej żądań z własnej kolejki. Odpowiedź na jego prośbę w końcu wraca jako kolejna wiadomość.Niestety przekazywanie wiadomości nie eliminuje możliwości zaistnienia warunków wyścigu. Załóżmy, że każde konto obsługuje operacje “get-balance” I “withdraw”, z odpowiednimi komunikatami. Dwóch użytkowników, w bankomacie A i B, oboje próbują wypłacić dolara z tego samego konta. Najpierw sprawdzają saldo, aby upewnić się, że nigdy nie wypłacają więcej niż Posiada konto, ponieważ kredyty w rachunku bieżącym powodują duże kary bankowe` “‘get-balancejeśli saldo >= 1 następnie wycofaj 1 “‘ problem ponownie przeplata się, ale tym razem przeplata * wiadomości * wysłane na konto bankowe, a nie * instrukcje * wykonywane przez A I B. Jeśli konto zaczyna się od dolara, to jakie przeplatanie wiadomości zmyli A i B do myślenia, że mogą zarówno wypłacić dolara, a tym samym przelać konto?Jedną z lekcji jest to, że musisz starannie wybrać operacje modelu przekazywania wiadomości. “Wypłać-jeśli-wystarczające-środki” byłoby lepszą operacją niż tylko “Wypłać”.## Współbieżność jest trudna do przetestowania i Debugujeśli nie przekonaliśmy Cię, że współbieżność jest trudna, oto najgorsza z nich. Bardzo trudno jest odkryć warunki wyścigu za pomocą testów. I nawet gdy test znajdzie błąd, może być bardzo trudno zlokalizować go w części programu, która go powoduje.Błędy współbieżności wykazują bardzo słabą odtwarzalność. Trudno sprawić, by stało się to w ten sam sposób dwa razy. Przeplatanie instrukcji lub wiadomości zależy od względnego czasu zdarzeń, na które silnie wpływa środowisko. Opóźnienia mogą być spowodowane przez inne uruchomione programy, inny ruch sieciowy, decyzje dotyczące harmonogramu systemu operacyjnego, różnice w taktowaniu procesora itp. Za każdym razem, gdy uruchamiasz program zawierający warunek rasy, możesz uzyskać inne zachowanie. Tego rodzaju błędy są * * heisenbugs**, które są niedeterministyczne i trudne do odtworzenia, w przeciwieństwie do “bohrbug”, który pojawia się wielokrotnie za każdym razem, gdy na niego patrzysz. Prawie wszystkie błędy w programowaniu sekwencyjnym to bohrbugs.Heisenbug może nawet zniknąć, gdy próbujesz na niego spojrzeć za pomocą “println” lub “debugger”! Powodem jest to, że drukowanie i debugowanie są tak dużo wolniejsze niż inne operacje, często 100-1000x wolniejsze, że radykalnie zmieniają czas operacji i przeplatania. Wstawianie prostego polecenia print do cashMachine ():”‘javaprivate static void cashMachine () {for (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) {deposit (); / / put a dollar in withdraw (); / / take it back out System.Wynocha.println (balance); / / powoduje zniknięcie błędu! }}“`…i nagle bilans jest zawsze 0, zgodnie z życzeniem, i błąd wydaje się zniknąć. Ale jest tylko zamaskowany, Nie Naprawiony. Zmiana czasu w innym miejscu programu może nagle spowodować powrót błędu.Współbieżność jest trudna do uzyskania. Częścią tego czytania jest trochę przestraszyć. Podczas kolejnych odczytów zobaczymy zasadne sposoby projektowania równoległych programów, aby były bezpieczniejsze od tego rodzaju błędów.mitx:704b9c4db3c6487c9f1549956af8bfc8 współbieżność testowania # # podsumowanie + współbieżność: wiele obliczeń uruchomionych jednocześnie + współdzielona pamięć & paradygmaty przekazywania wiadomości+ procesy & wątki + Proces jest jak komputer wirtualny; wątek jest jak wirtualny procesor+ Warunki Race + gdy poprawność wyniku (postconditions i niezmienniki) zależy od względnego czasu zdarzeń. te pomysły łączą się z naszymi trzema kluczowymi właściwościami dobrego oprogramowania głównie w zły sposób. Współbieżność jest konieczna, ale powoduje poważne problemy z poprawnością. Będziemy pracować nad rozwiązaniem tych problemów w następnych odczytach.+ * * Bezpieczny od błędów.** Błędy współbieżności są jednymi z najtrudniejszych błędów do znalezienia i naprawienia, i wymagają starannego projektowania, aby uniknąć.+ * * Łatwe do zrozumienia.** Przewidywanie, jak współbieżny kod może przeplatać się z innym współbieżnym kodem, jest bardzo trudne dla programistów. Najlepiej projektować w taki sposób, aby programiści nie musieli o tym myśleć. + * * Gotowy na zmiany.** Nie jest to szczególnie istotne.