Czy możesz wyjaśnić, dlaczego wiele wątków wymaga blokowania procesora jednordzeniowego?

Załóżmy, że wątki te działają w jednostce centralnej. Jako procesor uruchom tylko jedną instrukcję w jednym cyklu. Mówi się, że nawet dzielą zasoby procesora. ale komputer zapewnia, że ​​jednorazowo jedna instrukcja. Czy więc blokada nie jest konieczna do wielokrotnego tworzenia wątków?

Najlepiej ilustruje to przykład.

Załóżmy, że mamy proste zadanie, które chcemy wykonywać wiele razy równolegle i chcemy globalnie śledzić liczbę wykonanych zadań, na przykład zliczanie odwiedzin na stronie internetowej.

Kiedy każdy wątek dojdzie do punktu, w którym zwiększa liczbę, jego wykonanie będzie wyglądać następująco:

1. Odczytaj liczbę trafień z pamięci do rejestru procesora
2. Zwiększ tę liczbę.
3. Zapisz ten numer z powrotem do pamięci

Pamiętaj, że każdy wątek może zawiesić się w dowolnym momencie tego procesu. Więc jeśli wątek A wykona krok 1, a następnie zostanie zawieszony, a następnie wątek B wykona wszystkie trzy kroki, po wznowieniu wątku A jego rejestry będą miały niewłaściwą liczbę trafień: jego rejestry zostaną przywrócone, z radością zwiększy starą liczbę trafień i zapisz zwiększoną liczbę.

Ponadto w czasie zawieszenia wątku A mogła działać dowolna liczba innych wątków, więc liczba wątków A zapisanych na końcu może być znacznie poniżej prawidłowej liczby.

Z tego powodu należy upewnić się, że jeśli wątek wykonuje krok 1, musi wykonać krok 3, zanim jakikolwiek inny wątek będzie mógł wykonać krok 1, co można osiągnąć przez wszystkie wątki oczekujące na pojedynczą blokadę przed rozpoczęciem tego procesu i zwolnienie blokady dopiero po zakończeniu procesu, tak że ta „krytyczna sekcja” kodu nie może być niepoprawnie przeplatana, co prowadzi do błędnego zliczenia.

Ale co, jeśli operacja byłaby atomowa?

Tak, w krainie magicznych jednorożców i tęcz, gdzie inkrementacja jest atomowa, wówczas blokowanie nie byłoby konieczne w powyższym przykładzie.

Należy jednak pamiętać, że spędzamy bardzo mało czasu w świecie magicznych jednorożców i tęcz. W prawie każdym języku programowania operacja przyrostowa jest podzielona na trzy powyższe kroki. Dzieje się tak, ponieważ nawet jeśli procesor obsługuje operację przyrostu atomowego, operacja ta jest znacznie droższa: musi czytać z pamięci, modyfikować liczbę i zapisywać ją z powrotem do pamięci ... i zwykle operacja przyrostu atomowego jest operacją, która może zawieść, co oznacza, że ​​powyższa prosta sekwencja musi zostać zastąpiona pętlą (jak zobaczymy poniżej).

Ponieważ nawet w kodzie wielowątkowym wiele zmiennych jest przechowywanych lokalnie dla jednego wątku, programy są znacznie wydajniejsze, jeśli przyjmą, że każda zmienna jest lokalna dla jednego wątku, i pozwolą programistom zająć się ochroną stanu wspólnego między wątkami. Zwłaszcza, że ​​operacje atomowe zwykle nie wystarczają do rozwiązania problemów z wątkami, jak zobaczymy później.

Zmienne zmienne

Jeśli chcieliśmy uniknąć blokad tego konkretnego problemu, najpierw musimy zdać sobie sprawę, że kroki przedstawione w naszym pierwszym przykładzie nie są w rzeczywistości tym, co dzieje się we współczesnym skompilowanym kodzie. Ponieważ kompilatory zakładają, że tylko jeden wątek modyfikuje zmienną, każdy wątek zachowa własną buforowaną kopię zmiennej, dopóki rejestr procesora nie będzie potrzebny do czegoś innego. Tak długo, jak ma kopię w pamięci podręcznej, zakłada, że ​​nie musi wracać do pamięci i czytać jej ponownie (co byłoby drogie). Nie będą też zapisywać zmiennej z powrotem do pamięci, dopóki jest ona przechowywana w rejestrze.

Możemy powrócić do sytuacji, którą podaliśmy w pierwszym przykładzie (z tymi samymi problemami związanymi z wątkami, które zidentyfikowaliśmy powyżej), zaznaczając zmienną jako niestabilną , co informuje kompilator, że ta zmienna jest modyfikowana przez innych i dlatego należy ją odczytać z lub zapisywane w pamięci za każdym razem, gdy jest otwierane lub modyfikowane.

Tak więc zmienna oznaczona jako lotna nie zabierze nas do krainy operacji przyrostu atomowego, zbliża nas tylko tak blisko, jak nam się wydawało.

Zrobienie przyrostu atomowego

Gdy użyjemy zmiennej zmiennej, możemy uczynić naszą operację przyrostową atomową za pomocą operacji warunkowego ustawiania niskiego poziomu, która jest obsługiwana przez większość współczesnych procesorów (często nazywana porównywaniem i ustawianiem lub porównywaniem i zamianą ). Takie podejście zastosowano na przykład w klasie AtomicInteger w Javie :

197       /**
198        * Atomically increments by one the current value.
199        *
200        * @return the updated value
201        */
202       public final int incrementAndGet() {
203           for (;;) {
204               int current = get();
205               int next = current + 1;
206               if (compareAndSet(current, next))
207                   return next;
208           }
209       }

Powyższa pętla wielokrotnie wykonuje następujące kroki, aż do pomyślnego wykonania kroku 3:

1. Odczytaj wartość zmiennej lotnej bezpośrednio z pamięci.
2. Zwiększ tę wartość.
3. Zmień wartość (w pamięci głównej) wtedy i tylko wtedy, gdy jej bieżąca wartość w pamięci głównej jest taka sama jak wartość, którą wstępnie odczytaliśmy, za pomocą specjalnej operacji atomowej.

Jeśli krok 3 nie powiedzie się (ponieważ wartość została zmieniona przez inny wątek po kroku 1), ponownie odczytuje zmienną bezpośrednio z pamięci głównej i próbuje ponownie.

Chociaż operacja porównywania i zamiany jest kosztowna, jest nieco lepsza niż stosowanie blokowania w tym przypadku, ponieważ jeśli wątek zostanie zawieszony po kroku 1, inne wątki, które osiągną krok 1, nie muszą blokować i czekać na pierwszy wątek, który może zapobiec kosztownemu przełączaniu kontekstu. Gdy pierwszy wątek zostanie wznowiony, nie powiedzie się przy pierwszej próbie zapisu zmiennej, ale będzie mógł kontynuować, ponownie czytając zmienną, co ponownie jest prawdopodobnie tańsze niż przełącznik kontekstu, który byłby konieczny przy blokowaniu.

Możemy więc dotrzeć do krainy przyrostów atomowych (lub innych operacji na jednej zmiennej) bez użycia rzeczywistych blokad, poprzez porównanie i zamianę.

Kiedy więc ryglowanie jest absolutnie konieczne?

Jeśli musisz zmodyfikować więcej niż jedną zmienną w operacji atomowej, wówczas konieczne będzie zablokowanie, nie znajdziesz do tego specjalnej instrukcji procesora.

Tak długo, jak pracujesz nad jedną zmienną i jesteś przygotowany na każdą pracę, którą wykonałeś, aby zawieść i musisz przeczytać zmienną i zacząć od nowa, porównanie i zamiana będą jednak wystarczające.

Rozważmy przykład, w którym każdy wątek najpierw dodaje 2 do zmiennej X, a następnie mnoży X przez dwa.

Jeśli X jest początkowo jeden i działają dwa wątki, oczekujemy, że wynikiem będzie (((1 + 2) * 2) + 2) * 2 = 16.

Jednakże, jeśli wątki się przeplatają, moglibyśmy, nawet przy wszystkich operacjach atomowych, zamiast tego, aby oba dodania występowały najpierw, a mnożenia następowały później, w wyniku czego (1 + 2 + 2) * 2 * 2 = 20.

Dzieje się tak, ponieważ mnożenie i dodawanie nie są operacjami przemiennymi.

Tak więc same operacje atomowe nie wystarczą, musimy uczynić kombinację operacji atomowymi.

Możemy to zrobić albo za pomocą blokowania do serializacji procesu, albo możemy użyć jednej zmiennej lokalnej do przechowywania wartości X, gdy rozpoczęliśmy nasze obliczenia, drugiej zmiennej lokalnej dla kroków pośrednich, a następnie użyć porównania i zamiany, aby ustaw nową wartość tylko wtedy, gdy bieżąca wartość X jest taka sama jak pierwotna wartość X. Jeśli zawiedziemy, będziemy musieli zacząć od nowa, czytając X i wykonując ponownie obliczenia.

Wiąże się to z kilkoma kompromisami: gdy obliczenia stają się dłuższe, staje się znacznie bardziej prawdopodobne, że bieżący wątek zostanie zawieszony, a wartość zostanie zmodyfikowana przez inny wątek przed wznowieniem, co oznacza, że ​​awarie stają się znacznie bardziej prawdopodobne, co prowadzi do zmarnowania czas procesora. W skrajnym przypadku dużej liczby wątków z bardzo długimi obliczeniami, możemy mieć 100 wątków odczytających zmienną i zaangażowanych w obliczenia, w którym to przypadku tylko pierwszy, kto skończy, zapisuje nową wartość, pozostałe 99 nadal będzie dokończyć obliczenia, ale po zakończeniu odkryć, że nie mogą zaktualizować wartości ... w którym momencie odczytają wartość i rozpoczną obliczenia od nowa. Prawdopodobnie pozostałe 99 wątków powtórzy ten sam problem, marnując ogromne ilości czasu procesora.

Pełna serializacja sekcji krytycznej za pomocą zamków byłaby znacznie lepsza w tej sytuacji: 99 wątków zawiesiłoby się, gdy nie otrzymały zamka, i prowadziliśmy każdy wątek w kolejności przybycia do punktu zamka.

Jeśli serializacja nie jest krytyczna (jak w naszym przypadku inkrementacji), a obliczenia, które zostałyby utracone w przypadku niepowodzenia aktualizacji liczby, są minimalne, można skorzystać z operacji porównywania i zamiany, ponieważ ta operacja jest tańszy niż blokowanie.

Rozważ ten cytat:

Niektórzy ludzie, gdy napotykają problem, myślą: „Wiem, użyję nici”, a potem dwóch ma już poblesms

widzicie, nawet jeśli 1 instrukcja działa na CPU w danym momencie, programy komputerowe zawierają znacznie więcej niż tylko instrukcje montażu atomowego. Na przykład pisanie do konsoli (lub pliku) oznacza, że ​​musisz zablokować, aby upewnić się, że działa tak, jak chcesz.

Wydaje się, że wielu próbowało wyjaśnić blokowanie, ale myślę, że OP potrzebuje wyjaśnienia, czym tak naprawdę jest wielozadaniowość.

Jeśli w systemie działa więcej niż jeden wątek, nawet z jednym procesorem, istnieją dwie główne metodologie, które określają, w jaki sposób te wątki zostaną zaplanowane (tj. Umieszczone w taki sposób, aby działały w Twoim jednordzeniowym procesorze):

• Wielozadaniowość kooperacyjna - używana w Win9x wymagała od każdej aplikacji jawnego poddania się kontroli. W takim przypadku nie musisz się martwić blokowaniem, ponieważ dopóki wątek A wykonuje jakiś algorytm, masz gwarancję, że nigdy nie zostanie on przerwany
• Zapobiegawcza wielozadaniowość - używana w większości współczesnych systemów operacyjnych (Win2k i nowsze). Wykorzystuje to przedziały czasu i przerywa wątki, nawet jeśli nadal wykonują pracę. Jest to o wiele bardziej niezawodne, ponieważ pojedynczy wątek nigdy nie może zawiesić całej maszyny, co było realną możliwością w przypadku współpracy wielozadaniowej. Z drugiej strony, teraz musisz się martwić blokadami, ponieważ w dowolnym momencie jeden z twoich wątków może zostać przerwany (tzn. Wstrzymany), a system operacyjny może zaplanować uruchomienie innego wątku. Podczas kodowania aplikacji wielowątkowych za pomocą tego zachowania, MUSISZ wziąć pod uwagę, że między każdą linią kodu (a nawet każdą instrukcją) może działać inny wątek. Teraz nawet w przypadku jednego rdzenia blokowanie staje się bardzo ważne, aby zapewnić spójny stan danych.

Problem nie dotyczy poszczególnych operacji, ale większe zadania, które wykonują.

Wiele algorytmów zostało napisanych przy założeniu, że mają pełną kontrolę nad stanem, w którym działają. W przypadku modelu wykonania z przeplotem uporządkowanym, takiego jak ten, który opisujesz, operacje mogą być dowolnie przeplatane ze sobą, a jeśli dzielą stan, istnieje ryzyko, że stan jest niespójny.

Możesz porównać to z funkcjami, które mogą tymczasowo złamać niezmiennik, aby zrobić to, co robią. Tak długo, jak państwo pośrednie nie jest widoczne z zewnątrz, mogą robić wszystko, co chcą, aby osiągnąć swoje zadanie.

Kiedy piszesz współbieżny kod, musisz upewnić się, że stan rywalizacji jest uważany za niebezpieczny, chyba że masz do niego wyłączny dostęp. Częstym sposobem na uzyskanie wyłącznego dostępu jest synchronizacja na prymitywie synchronizacji, np. Trzymanie zamka.

Inną rzeczą, którą prymitywy synchronizacji powodują na niektórych platformach, jest to, że emitują bariery pamięci, które zapewniają spójność pamięci między procesorami.

Z wyjątkiem ustawienia „bool” nie ma gwarancji (przynajmniej w c), że czytanie lub pisanie zmiennej wymaga tylko jednej instrukcji - a raczej nie można jej przerwać w trakcie czytania / pisania

Pamięć współdzielona.

To definicja ... wątków : kilka współbieżnych procesów ze wspólną pamięcią.

Jeśli nie ma pamięci współużytkowanej, są one zwykle nazywane procesami old-school-UNIX .
Jednak od czasu do czasu mogą potrzebować blokady podczas uzyskiwania dostępu do udostępnionego pliku.

(pamięć współdzielona w jądrach podobnych do UNIX-a rzeczywiście była zwykle implementowana przy użyciu fałszywego deskryptora pliku reprezentującego adres pamięci współdzielonej)

Procesor wykonuje jedną instrukcję na raz, ale co, jeśli masz dwa lub więcej procesorów?

Masz rację, że blokady nie są potrzebne, jeśli możesz napisać program tak, aby korzystał z instrukcji atomowych: instrukcji, których wykonanie nie jest przerywane na danym procesorze i wolne od zakłóceń przez inne procesory.

Blokady są wymagane, gdy kilka instrukcji musi być chronionych przed zakłóceniami i nie ma równoważnych instrukcji atomowych.

Na przykład wstawienie węzła do podwójnie połączonej listy wymaga aktualizacji kilku lokalizacji pamięci. Przed wstawieniem i po wstawieniu niektóre niezmienniki trzymają się struktury listy. Jednak podczas wstawiania niezmienniki są tymczasowo łamane: lista znajduje się w stanie „w budowie”.

Jeśli inny wątek przemierza listę podczas niezmienników lub też próbuje ją zmodyfikować, gdy jest to stan, struktura danych prawdopodobnie ulegnie uszkodzeniu, a zachowanie będzie nieprzewidywalne: być może oprogramowanie ulegnie awarii lub będzie kontynuowało z niepoprawnymi wynikami. W związku z tym wątki muszą w jakiś sposób zgodzić się na to, aby nie przeszkadzać sobie nawzajem podczas aktualizowania listy.

Odpowiednio zaprojektowanymi listami można manipulować za pomocą instrukcji atomowych, dzięki czemu zamki nie są potrzebne. Algorytmy do tego są nazywane „bez blokady”. Należy jednak pamiętać, że instrukcje atomowe są w rzeczywistości formą blokowania. Są one specjalnie implementowane w sprzęcie i działają poprzez komunikację między procesorami. Są droższe niż podobne instrukcje, które nie są atomowe.

Na wieloprocesorach, które nie mają luksusu instrukcji atomowych, prymitywy dla wzajemnego wykluczania muszą być zbudowane z prostych dostępu do pamięci i pętli wyborczych. Nad takimi problemami pracowali Edsger Dijkstra i Leslie Lamport.