Do czego służy test-i-zestaw?

Question

Po przeczytaniu Test-and-Set Wikipedia entry, nadal pozostaję z pytaniem "Do czego byłby użyty zestaw testowy?"

Zdaję sobie sprawę, że można go użyć do wdrożenia Mutex (jak opisano w wikipedia), ale jakie ma inne zastosowania?

Answer 1

Używa się go za każdym razem, gdy chce się zapisać dane w pamięci po wykonaniu pracy i upewnić się, że inny wątek nie zastąpił miejsca docelowego od rozpoczęcia. Wiele lock/mutex-free algorithms przyjmuje ten formularz.

Answer 2

Zasadniczo, jego użycie jest właśnie dla muteksów, biorąc pod uwagę ogromne znaczenie atomowości. to jest to!

Testowanie i ustawianie to operacja, która może być wykonywana za pomocą dwóch innych instrukcji, nieatomowych i szybszych (atomowość niesie ze sobą obciążenie sprzętowe w systemach wieloprocesorowych), więc zwykle nie używałbyś go z innych powodów.

Answer 3

Dobrym przykładem jest "inkrementacja".

Powiedz, że dwa wątki wykonują a = a + 1. Powiedzmy, że a zaczyna się od wartości 100. Jeśli oba wątki są uruchomione w tym samym czasie (wielordzeniowe), oba będą ładować a jako 100, zwiększać do 101 i zapisywać je ponownie w a. Źle!

Podczas testu i ustawiania mówisz "Ustaw a na 101, ale tylko jeśli obecnie ma on wartość 100." W takim przypadku jeden wątek przejdzie ten test, ale drugi zakończy się niepowodzeniem. W przypadku niepowodzenia wątek może ponowić próbę całego wyciągu, tym razem ładując a jako . Powodzenie.

ogół jest to szybciej niż przy użyciu mutex ponieważ:

1. Przez większość czasu nie ma wyścigu, więc aktualizacja nie dzieje się bez konieczności nabywania jakiś mutex.
2. Nawet podczas kolizji, jeden wątek wcale nie jest zablokowany, a drugi wątek jest szybszy, aby po prostu zakręcić i ponowić próbę, niż byłoby zawieszenie się w linii dla niektórych muteksów.

Answer 4

Jest używany, gdy trzeba uzyskać wartość wspólną, zrobić coś z nią i zmienić wartość, zakładając, że inny wątek jeszcze jej nie zmienił.

Jeśli chodzi o zastosowania praktyczne, po raz ostatni widziałem, że jest to implementacja współbieżnych kolejek (kolejek, które mogą być popychane/popped przez wiele wątków bez potrzeby użycia semaforów lub muteksów).

Dlaczego używałeś TestAndSet zamiast mutex? Ponieważ generalnie wymaga mniej narzutów niż muteks. Tam, gdzie muteks wymaga interwencji OS, TestAndSet może być zaimplementowany jako pojedyncza instrukcja atomowa na CPU. Podczas pracy w środowisku równoległym ze 100 wątkami pojedynczy muteks w krytycznej sekcji kodu może spowodować poważne wąskie gardła.

Answer 5

Wyobraź sobie, że piszesz aplikację bankową, a Twój wniosek zawierał prośbę o wycofanie dziesięciu funtów (tak, jestem Anglikiem;)) z konta. Musisz więc odczytać saldo rachunku bieżącego w zmiennej lokalnej, odjąć wypłatę, a następnie zapisać saldo z powrotem w pamięci.

Co jednak, jeśli pojawi się inna, równoległa prośba między odczytaniem wartości a jej zapisaniem? Istnieje możliwość, że wynik tego żądania zostanie całkowicie nadpisany przez pierwszy, a saldo konta będzie nieprawidłowe.

Testowanie i ustawianie pomaga nam rozwiązać ten problem, sprawdzając, czy wartość, jaką nadpisuje, jest taka, jaka powinna być. W takim przypadku możesz sprawdzić, czy saldo było oryginalną wartością, którą przeczytałeś. Ponieważ jest atomowy, jest nie przerywać, więc nikt nie może wyciągnąć dywanu spod siebie między czytaniem a pisaniem.

Innym sposobem rozwiązania tego samego problemu jest wyjęcie zamka w miejscu w pamięci. Niestety, zamki są niezwykle trudne do uzyskania, trudne do zrozumienia, mają problemy z skalowalnością i źle się zachowują w obliczu awarii, więc nie są idealnym (ale zdecydowanie praktycznym) rozwiązaniem. Metody testowania i ustawiania stanowią podstawę niektórych Software Transactional Memories, które optymistycznie pozwalają na jednoczesną realizację każdej transakcji, kosztem wycofania wszystkich z powrotem w przypadku konfliktu.