Dlaczego pthread_cond_wait ma fałszywe wybudzenia?

145

Cytując stronę podręcznika:

Podczas korzystania ze zmiennych warunkowych zawsze istnieje predykat boolowski obejmujący zmienne współdzielone skojarzone z każdym warunkiem oczekiwania, który jest prawdą, jeśli wątek powinien kontynuować. Mogą wystąpić fałszywe wybudzenia z funkcji pthread_cond_timedwait () lub pthread_cond_wait (). Ponieważ powrót z pthread_cond_timedwait () lub pthread_cond_wait () nie implikuje nic o wartości tego predykatu, predykat powinien zostać ponownie oceniony po takim powrocie.

Więc pthread_cond_waitmoże wrócić, nawet jeśli tego nie zasygnalizowałeś. Przynajmniej na pierwszy rzut oka wydaje się to dość okropne. To byłoby jak funkcja, która losowo zwraca niewłaściwą wartość lub zwraca losowo, zanim faktycznie osiągnie właściwą instrukcję powrotu. Wygląda na poważny błąd. Ale fakt, że zdecydowali się udokumentować to na stronie podręcznika zamiast naprawiać, wydaje się wskazywać, że istnieje uzasadniony powód, dla którego pthread_cond_waitbudzą się fałszywie. Przypuszczalnie jest coś nieodłącznego w tym, jak to działa, co sprawia, że ​​nie można temu zaradzić. Pytanie brzmi: co.

Dlaczego nie pthread_cond_waitwrócić fałszywie? Dlaczego nie może zagwarantować, że obudzi się tylko wtedy, gdy zostanie odpowiednio zasygnalizowana? Czy ktoś może wyjaśnić powód jego fałszywego zachowania?

Jonathan M Davis
źródło
5
Wyobrażam sobie, że ma to coś wspólnego z powrotem, gdy proces złapie sygnał. Większość * nixów nie restartuje wywołania blokującego po tym, jak sygnał je przerywa; po prostu ustawiają / zwracają kod błędu, który mówi, że wystąpił sygnał.
cHao,
1
@cHao: chociaż zauważ, że ponieważ zmienne warunkowe i tak mają inne powody do fałszywych wybudzeń , obsługa sygnału nie jest błędem w przypadku pthread_cond_(timed)wait: „Jeśli sygnał jest dostarczany ... wątek wznawia oczekiwanie na zmienną warunku, tak jakby była nie zostanie przerwany lub zwróci zero z powodu fałszywego wybudzenia ”. Inne funkcje blokujące wskazują, EINTRkiedy są przerywane przez sygnał (np. read) Lub są wymagane do wznowienia (np pthread_mutex_lock.). Więc gdyby nie było innych powodów fałszywego wybudzenia, pthread_cond_waitmożna by je zdefiniować w ten sposób.
Steve Jessop
4
Podobnym artykuł na Wikipedii: Spurious budzenia
Palec
3
Przydatny Vladimir Prus: fałszywe przebudzenia .
iammilind
Wiele funkcji nie może w pełni wykonać swojej pracy (przerwane operacje we / wy), a funkcje obserwacyjne mogą otrzymać inne zdarzenia, takie jak zmiana katalogu, w którym zmiana została anulowana lub cofnięta. Jaki jest problem?
curiousguy

Odpowiedzi:

77

Następujące wyjaśnienie podaje David R. Butenhof w „Programming with POSIX Threads” (s. 80):

Fałszywe wybudzenia mogą brzmieć dziwnie, ale w niektórych systemach wieloprocesorowych całkowicie przewidywalne wybudzenie stanu może znacznie spowolnić działanie wszystkich zmiennych stanu.

W poniższej dyskusji comp.programming.threads rozwija myślenie stojące za projektem:

Patrick Doyle napisał: 
> W artykule Tom Payne napisał: 
>> Kaz Kylheku napisał: 
>>: Dzieje się tak, ponieważ implementacje czasami nie pozwalają uniknąć wstawiania 
>>: te fałszywe wybudzenia; zapobieganie im może być kosztowne.

>> Ale dlaczego? Dlaczego to takie trudne? Na przykład, czy mówimy o
>> sytuacje, w których czas oczekiwania upływa w momencie nadejścia sygnału? 

> Wiesz, zastanawiam się, czy projektanci pthreadów używali logiki w ten sposób: 
> użytkownicy zmiennych warunkowych i tak muszą sprawdzić stan na wyjściu, 
> więc nie będziemy ich obciążać, jeśli pozwolimy 
> fałszywe wybudzenia; a ponieważ można sobie wyobrazić, że zezwalanie na fałszywe
> wybudzanie może przyspieszyć implementację, może pomóc tylko wtedy, gdy my 
> pozwól im. 

> Mogli nie mieć na myśli żadnej konkretnej implementacji. 

Właściwie wcale nie jesteś daleko, z wyjątkiem tego, że nie posunąłeś się wystarczająco daleko. 

Celem było wymuszenie poprawnego / niezawodnego kodu przez wymaganie pętli predykatów. To było
kierowany przez możliwy do udowodnienia poprawny kontyngent akademicki wśród „głównych wątków” w 
grupę roboczą, chociaż nie sądzę, aby ktokolwiek naprawdę nie zgadzał się z intencją 
kiedy zrozumieli, co to znaczy. 

Podążaliśmy za tym zamiarem z kilkoma poziomami uzasadnienia. Pierwsza była taka
„religijnie” użycie pętli zabezpiecza aplikację przed jej własną niedoskonałością 
praktyki kodowania. Po drugie, nietrudno było to wyobrazić sobie abstrakcyjnie
maszyny i kod implementacji, które mogłyby wykorzystać to wymaganie do ulepszenia 
wydajność operacji oczekiwania na średni stan poprzez optymalizację 
mechanizmy synchronizacji. 
/ ------------------ [David.Buten ... @ compaq.com] ------------------ \ 
| Compaq Computer Corporation POSIX Thread Architect |
| Moja książka: http://www.awl.com/cseng/titles/0-201-63392-2/ |
\ ----- [http://home.earthlink.net/~anneart/family/dave.html] ----- / 

NPE
źródło
22
w zasadzie to nic nie mówi. Nie podano tutaj żadnego wyjaśnienia poza początkową myślą, że „może to przyspieszyć”, ale nikt nie wie, jak i czy w ogóle.
Bogdan Ionitza
107

Istnieją co najmniej dwie rzeczy, które może oznaczać `` fałszywe wybudzenie '':

  • Wątek zablokowany pthread_cond_waitmoże powrócić z wywołania, nawet jeśli nie wystąpiło żadne wywołanie pthread_call_signallub pthread_cond_broadcastwarunek.
  • Wątek zablokowany w pthread_cond_waitpowrocie z powodu wywołania pthread_cond_signallub pthread_cond_broadcast, jednak po ponownym uzyskaniu muteksu okazuje się, że bazowy predykat nie jest już prawdziwy.

Ale ten drugi przypadek może wystąpić, nawet jeśli implementacja zmiennej warunkowej nie zezwala na pierwszy przypadek. Rozważmy kolejkę konsumenta producenta i trzy wątki.

  • Wątek 1 właśnie usunął element z kolejki i zwolnił muteks, a kolejka jest teraz pusta. Wątek robi wszystko, co robi z elementem, który uzyskał na jakimś procesorze.
  • Wątek 2 próbuje usunąć z kolejki element, ale stwierdza, że ​​kolejka jest pusta, gdy jest sprawdzana pod muteksem, wywołaniami pthread_cond_waiti blokami w wywołaniu oczekującym na sygnał / emisję.
  • Wątek 3 uzyskuje muteks, wstawia nowy element do kolejki, powiadamia o zmiennej warunku i zwalnia blokadę.
  • W odpowiedzi na powiadomienie z wątku 3 zaplanowano uruchomienie wątku 2, który oczekiwał na warunek.
  • Jednak zanim wątek 2 zdoła dostać się do procesora i pobrać blokadę kolejki, wątek 1 kończy swoje bieżące zadanie i wraca do kolejki, aby wykonać więcej pracy. Uzyskuje blokadę kolejki, sprawdza predykat i stwierdza, że ​​w kolejce jest praca. Kontynuuje usuwanie z kolejki elementu wstawionego w wątku 3, zwalnia blokadę i robi wszystko, co robi z elementem kolejkowanym przez wątek 3.
  • Wątek 2 dostaje się teraz na procesor i uzyskuje blokadę, ale kiedy sprawdza predykat, stwierdza, że ​​kolejka jest pusta. Wątek 1 „ukradł” przedmiot, więc budzenie wygląda na fałszywe. Wątek 2 musi ponownie poczekać na stan.

Ponieważ więc już zawsze musisz sprawdzić predykat w pętli, nie ma znaczenia, czy podstawowe zmienne warunku mogą mieć inne rodzaje fałszywych wybudzeń.

acm
źródło
23
tak. Zasadniczo dzieje się tak, gdy zdarzenie jest używane zamiast mechanizmu synchronizacji z liczbą. Niestety, wydaje się, że semafory POSIX (w każdym razie w Linuksie) również podlegają pobudzeniom spurius. Po prostu uważam to za trochę dziwne, że fundamentalna awaria funkcji prymitywów synchronizacji jest akceptowana jako `` normalna '' i musi być obejść na poziomie użytkownika: (Przypuszczalnie programiści byliby zaangażowani, gdyby udokumentowano wywołanie systemowe z sekcją „Fałszywe segfault” lub „Fałszywe połączenie z niewłaściwym adresem URL” lub „Fałszywe otwarcie niewłaściwego pliku”
Martin James
2
Bardziej powszechny scenariusz „fałszywego wybudzenia” jest najprawdopodobniej efektem ubocznym wywołania pthread_cond_broadcast (). Załóżmy, że masz pulę 5 wątków, dwa budzą się na transmisję i wykonują pracę. Pozostała trójka budzi się i stwierdza, że ​​praca została wykonana. Systemy wieloprocesorowe mogą również powodować przypadkowe wybudzenie wielu wątków przez warunkowy sygnał. Kod po prostu ponownie sprawdza predykat, widzi nieprawidłowy stan i wraca do snu. W obu przypadkach sprawdzenie predykatu rozwiązuje problem. IMO, ogólnie rzecz biorąc, użytkownicy nie powinni używać surowych muteksów POSIX i warunków.
CubicleSoft
1
@MartinJames - Co powiesz na klasyczny „fałszywy” EINTR? Zgodzę się, że ciągłe testowanie EINTR w pętli jest trochę irytujące i sprawia, że ​​kod jest raczej brzydki, ale programiści i tak robią to, aby uniknąć przypadkowych awarii.
CubicleSoft
2
@Yola Nie, nie może, ponieważ powinieneś zablokować muteks wokół pthread_cond_signal/broadcasti nie będziesz w stanie tego zrobić, dopóki mutex nie zostanie odblokowany przez wywołanie pthread_cond_wait.
a3f
1
Przykład tej odpowiedzi jest bardzo realistyczny i zgadzam się, że sprawdzanie predykatów to dobry pomysł. Jednak nie można tego naprawić równie dobrze, wykonując problematyczny krok „wątek 1 kończy swoje bieżące zadanie i wraca do kolejki, aby wykonać więcej pracy” i zastępując go tekstem „Wątek 1 kończy swoje bieżące zadanie i wraca do oczekiwania zmienna warunku "? To wyeliminowałoby tryb awarii opisany w odpowiedzi i jestem prawie pewien, że poprawiłoby kod, przy braku fałszywych wybudzeń . Czy w praktyce istnieje implementacja, która powoduje fałszywe wybudzenia?
Quuxplusone,
7

Sekcja „Wielokrotne przebudzenia według sygnału stanu” w pthread_cond_signal zawiera przykładową implementację pthread_cond_wait i pthread_cond_signal, które obejmują fałszywe wybudzania.

Jingguo Yao
źródło
2
Myślę, że ta odpowiedź jest błędna, o ile chodzi. Przykładowa implementacja na tej stronie ma implementację „powiadomić jeden”, co jest równoważne z „powiadomieniem wszystkich”; ale nie wydaje się generować fałszywych wybudzeń. Jedynym sposobem na przebudzenie wątku jest wywołanie przez inny wątek „powiadamiania wszystkich” lub przez inny wątek wywoływanie tego, co jest oznaczone etykietą, „powiadomienie jednego” - który jest naprawdę - „powiadom wszystkich”.
Quuxplusone,
5

Chociaż nie sądzę, aby było to brane pod uwagę w czasie projektowania, oto rzeczywisty powód techniczny: w połączeniu z anulowaniem nici istnieją warunki, w których wybranie opcji budzenia się „niejawnie” może być absolutnie konieczne, przynajmniej jeśli nie są gotowi nałożyć bardzo duże ograniczenia na to, jakie rodzaje strategii wdrożeniowych są możliwe.

Kluczowy problem polega na tym, że jeśli wątek działa na anulowanie, gdy jest zablokowany pthread_cond_wait, efekty uboczne muszą wyglądać tak, jakby nie zużywał żadnego sygnału ze zmiennej warunku. Jednak trudno jest (i bardzo ogranicza) upewnić się, że sygnał nie został już zużyty, gdy zaczynasz działać w trybie anulowania, a na tym etapie może być niemożliwe „ponowne przesłanie” sygnału do zmiennej warunku, ponieważ możesz znajdować się w sytuacji, w której osoba dzwoniąca pthread_cond_signaljest już usprawiedliwiona, że ​​zniszczyła condvar i uwolniła pamięć, w której się znajdował.

Dodatek na fałszywe przebudzenie zapewnia łatwe wyjście. Zamiast kontynuować działanie na anulowanie, gdy nadejdzie, gdy jest zablokowane na zmiennej warunkowej, jeśli być może już zużyłeś sygnał (lub jeśli chcesz być leniwy, bez względu na wszystko), możesz zamiast tego zadeklarować fałszywe przebudzenie, i wróć z sukcesem. Nie koliduje to w ogóle z operacją anulowania, ponieważ poprawny dzwoniący po prostu zareaguje na oczekujące anulowanie przy następnym zapętleniu i pthread_cond_waitponownym wywołaniu .

R .. GitHub PRZESTAŃ POMÓC LODOWI
źródło