Dlaczego większość implementacji Mutex jest niesprawiedliwa?

Rozumiem, że najpopularniejsze implementacje muteksu (np. Std :: mutex w C ++) nie gwarantują uczciwości - to znaczy, nie gwarantują, że w przypadku niezgody zamek zostanie przejęty przez wątki w kolejności, w jakiej o nazwie lock (). W rzeczywistości jest nawet możliwe (choć mam nadzieję, że rzadkie), że w przypadkach dużej rywalizacji niektóre wątki oczekujące na muteks mogą go nigdy nie nabyć.

Wydaje mi się to nieprzydatnym zachowaniem - wydaje mi się, że uczciwy muteks dałby zachowanie bardziej zgodne z tym, czego programista chciałby / oczekiwałby.

Podany powód, dla którego muteksy zwykle nie są wprowadzane w celu zachowania uczciwości, to „wydajność”, ale chciałbym lepiej zrozumieć, co to oznacza - w szczególności, w jaki sposób złagodzenie wymogu uczciwości muteksu poprawia wydajność? Wydaje się, że „sprawiedliwy” muteks byłby trywialny do wdrożenia - wystarczy, że lock () doda wątek wywołujący do końca listy połączonych mutexów przed uśpieniem, a następnie odblokuje () pop następny wątek z na czele tej samej listy i obudźcie ją.

Jakich informacji na temat wdrażania mutexów brakuje mi tutaj, co wyjaśniałoby, dlaczego warto poświęcić sprawiedliwość dla lepszej wydajności?

Odpowiedź Jima Sawyera wskazuje na jedną odpowiedź: jeśli masz wątki o różnych priorytetach, „uczciwe” zachowanie byłoby nieprawidłowe. Jeśli masz wiele wątków, które można uruchomić, wątek o najwyższym priorytecie jest generalnie tym, który powinien zostać uruchomiony.

Jest jednak trochę dyskutowany sekret implementacji systemu operacyjnego, o którym powinieneś wiedzieć, a mianowicie, że czasami systemy operacyjne uruchamiają kod jako użytkownik poprzez przejęcie wątku użytkownika. Ze względów bezpieczeństwa większość systemów operacyjnych, które to robią, robi to tylko wtedy, gdy wątek jest zablokowany. Po zakończeniu działania systemu operacyjnego wątek jest ponownie zawieszany, co zwykle powoduje przeniesienie wątku na tył kolejki oczekiwania.

Typowym przykładem jest procedura obsługi sygnałów w systemie Unix, asynchroniczna pułapka systemowa w VMS lub asynchroniczne wywołanie procedury w Windows NT. Wszystko to w zasadzie to samo: system operacyjny musi powiadomić proces użytkownika o wystąpieniu jakiegoś zdarzenia i jest to obsługiwane przez uruchomienie kodu w przestrzeni użytkownika.

Wiele usług systemu operacyjnego, takich jak asynchroniczne operacje we / wy, jest często implementowanych w ramach tej funkcji.

Innym przykładem jest proces kontrolowany przez debugger. W takim przypadku system debugowania może wykonać kod jako zadanie użytkownika z różnych powodów.

„Inwersja priorytetowa” jest jednym z powodów, dla których uczciwość może być niepożądana. Proces o niskim priorytecie uderza w zablokowany muteks i śpi. Następnie uderza proces o wyższym priorytecie, a także śpi. Kiedy mutex zostanie odblokowany, który proces powinien następnie uzyskać blokadę?

Sprawiedliwy muteks spędza więcej czasu w swoim życiu zamknięty niż niesprawiedliwy muteks, przy czym wszystkie pozostałe są równe. Ponieważ wątek uwalniający niesprawiedliwy muteks zawsze może go po prostu odblokować. Ale wątek zwalniający uczciwy muteks może go odblokować tylko wtedy, gdy kolejka kelnera jest pusta. W przeciwnym razie wątek zwalniający musi pozostawić muteks zablokowany ze względu na następny wątek, czyli pierwszy wątek w kolejce kelnera, który jest następnie usuwany z kolejki i budzony. Muteks pozostaje zablokowany przynajmniej do momentu, gdy nowo przebudzony wątek zostanie zaplanowany na CPU, co może zająć dużo czasu, jeśli istnieje wiele aktualnie uruchomionych wątków.

A jeśli wątek zwalniający natychmiast próbuje odzyskać ten sam muteks, musi umieścić się z tyłu kolejki kelnerów i iść spać. Nie zdarzyłoby się to, gdyby wątek nie wypuścił muteksu na początek. Dlatego zachęca to do dłuższych „bardziej chciwych” odcinków krytycznych.