Spinlock versus Semaphore

Jakie są podstawowe różnice między semaforem a blokadą spinu?

Kiedy użylibyśmy semafora nad blokadą spinową?

Spinlock i semafor różnią się głównie czterema rzeczami:

1. Jakie są Spinlock jest możliwa realizacja zamkiem, a mianowicie taki, który jest realizowany przez ruchliwą oczekiwania ( „wirującej”). Semafor to uogólnienie blokady (lub odwrotnie, zamek jest specjalnym przypadkiem semafora). Zwykle, choć niekoniecznie , spinlocki są ważne tylko w ramach jednego procesu, podczas gdy semafory mogą być również używane do synchronizacji między różnymi procesami.

Blokada działa na zasadzie wzajemnego wykluczania, to znaczy jeden wątek na raz może uzyskać blokadę i przejść do „krytycznej sekcji” kodu. Zwykle oznacza to kod, który modyfikuje niektóre dane współdzielone przez kilka wątków. Semafor posiada licznik i pozwoli sobie przejmowanych przez jednego lub kilku wątków, w zależności jaką wartość wysłaniu do niego, oraz (w niektórych implementacjach), w zależności od tego, co jego maksymalna dopuszczalna wartość.

O ile można uznać zamek za specjalny przypadek semafora o maksymalnej wartości 1.

2. Co robią
Jak wspomniano powyżej, spinlock to zamek, a zatem mechanizm wzajemnego wykluczania (ściśle 1 do 1). Działa poprzez wielokrotne odpytywanie i / lub modyfikowanie lokalizacji pamięci, zwykle w sposób atomowy. Oznacza to, że nabycie spinlocka jest operacją „zajętą”, która prawdopodobnie spala cykle procesora przez długi czas (może na zawsze!), Podczas gdy skutecznie osiąga „nic”.
Główną zachętą do takiego podejścia jest fakt, że przełącznik kontekstu ma narzut odpowiadający obróceniu kilkaset (lub może tysięcy) razy, więc jeśli blokadę można uzyskać, spalając kilka cykli wirowania, może to być ogólnie bardzo dobre. bardziej wydajny. Ponadto w przypadku aplikacji czasu rzeczywistego blokowanie i czekanie, aż planista wróci do nich w odległej przyszłości, może być nie do przyjęcia.

Natomiast semafor albo w ogóle się nie obraca, albo obraca się tylko przez bardzo krótki czas (w celu optymalizacji, aby uniknąć narzutu wywołania systemowego). Jeśli nie można pozyskać semafora, blokuje się, oddając czas procesora innemu wątkowi, który jest gotowy do działania. Może to oczywiście oznaczać, że minie kilka milisekund, zanim twój wątek zostanie ponownie zaplanowany, ale jeśli nie stanowi to problemu (zwykle nie jest), może to być bardzo wydajne podejście, oszczędzające procesor.

3. Jak zachowują się w przypadku przeciążenia
Powszechnym błędem jest przekonanie, że spinlocki lub algorytmy wolne od blokad są „generalnie szybsze” lub że są użyteczne tylko do „bardzo krótkich zadań” (najlepiej, aby żaden obiekt synchronizacji nie był dłużej przytrzymywany niż absolutnie konieczne).
Jedną ważną różnicą jest to, jak różne podejścia zachowują się w przypadku zatorów .

Dobrze zaprojektowany system zwykle ma małe przeciążenie lub nie ma go wcale (oznacza to, że nie wszystkie wątki próbują uzyskać blokadę dokładnie w tym samym czasie). Na przykład normalnie nie pisze się kodu, który uzyskuje blokadę, a następnie ładuje pół megabajta skompresowanych zipem danych z sieci, dekoduje i analizuje dane, a na koniec modyfikuje współdzielone odniesienie (dołącza dane do kontenera itp.) przed zwolnieniem blokady. Zamiast tego można by uzyskać blokadę tylko w celu uzyskania dostępu do współdzielonego zasobu .
Ponieważ oznacza to, że jest znacznie więcej pracy poza sekcją krytyczną niż wewnątrz niej, naturalnie prawdopodobieństwo, że gwint znajduje się wewnątrz sekcji krytycznej jest stosunkowo niskie, a zatem kilka gwintów walczy jednocześnie o zamek. Oczywiście od czasu do czasu dwa wątki będą próbowały zdobyć blokadę w tym samym czasie (gdyby to nie mogło się zdarzyć, blokada nie byłaby potrzebna!), Ale jest to raczej wyjątek niż reguła w „zdrowym” systemie .

W takim przypadku spinlock znacznie przewyższa semafor, ponieważ jeśli nie ma przeciążenia zamka, narzut związany z uzyskaniem spinlocka wynosi zaledwie kilkanaście cykli w porównaniu z setkami / tysiącami cykli dla przełącznika kontekstu lub 10-20 milionów cykli dla utraty pozostałą część przedziału czasu.

Z drugiej strony, biorąc pod uwagę duże przeciążenie lub jeśli blokada jest utrzymywana przez długi czas (czasami po prostu nie możesz na to poradzić!), Spinlock spala szaloną liczbę cykli procesora, aby nic nie osiągnąć.
W tym przypadku znacznie lepszym wyborem jest semafor (lub mutex), ponieważ umożliwia on innemu wątkowi wykonywanie w tym czasie przydatnych zadań. Lub, jeśli żaden inny wątek nie ma czegoś użytecznego do zrobienia, pozwala systemowi operacyjnemu na dławienie procesora i zmniejszenie ciepła / oszczędzanie energii.

Ponadto w systemie jednordzeniowym blokada spinlock będzie dość nieefektywna w przypadku przeciążenia blokady, ponieważ wirujący wątek zmarnuje cały czas na oczekiwanie na zmianę stanu, która nie może się zdarzyć (nie do czasu zaplanowania zwalniania wątku, co nie jest dzieje się, gdy uruchomiony jest wątek oczekujący!). Dlatego, biorąc pod uwagę dowolną ilość rywalizacji, uzyskanie blokady zajmuje w najlepszym przypadku około 1,5 przedziału czasu (zakładając, że zwalniający wątek jest następnym zaplanowanym), co nie jest zbyt dobrym zachowaniem.

4. Jak są implementowane
Semafor w dzisiejszych czasach zwykle zawija się sys_futexpod Linuksem (opcjonalnie z blokadą spinlock, która kończy się po kilku próbach).
Blokada spinlocka jest zwykle implementowana przy użyciu operacji atomowych i bez korzystania z niczego, co zapewnia system operacyjny. W przeszłości oznaczało to używanie wewnętrznych funkcji kompilatora lub nieprzenośnych instrukcji asemblera. W międzyczasie zarówno C ++ 11, jak i C11 mają operacje atomowe jako część języka, więc poza ogólną trudnością pisania udowodnionego poprawnego kodu bez blokady, jest teraz możliwe zaimplementowanie kodu bez blokad w całkowicie przenośnym i (prawie) bezbolesny sposób.

po prostu semafor jest „ustępującym” obiektem synchronizacji, a spinlock to semafor typu „busywait”. (semafory są trochę więcej, ponieważ synchronizują kilka wątków, w przeciwieństwie do muteksu, ochrony, monitora lub sekcji krytycznej, która chroni region kodu z pojedynczego wątku)

W większej liczbie przypadków używałbyś semafora, ale użyj spinlocka, w którym zamierzasz zablokować się na bardzo krótki czas - blokowanie wiąże się z kosztami, zwłaszcza jeśli blokujesz dużo. W takich przypadkach bardziej efektywne może być blokowanie przez chwilę w oczekiwaniu na odblokowanie chronionego zasobu. Oczywiście zbyt długo się kręci, jeśli chodzi o wydajność.

zazwyczaj, jeśli obracasz się dłużej niż kwant wątku, powinieneś użyć semafora.

Poza tym, co powiedzieli Yoav Aviram i gbjbaanb, innym kluczowym punktem było to, że nigdy nie używałbyś blokady spin-lock na maszynie jednoprocesorowej, podczas gdy semafor miałby sens na takiej maszynie. W dzisiejszych czasach często trudno jest znaleźć maszynę bez wielu rdzeni, hiperwątkowości lub równoważnej, ale w sytuacji, gdy masz tylko jeden procesor, powinieneś używać semaforów. (Ufam, że powód jest oczywisty. Jeśli pojedynczy procesor jest zajęty czekaniem na coś innego, aby zwolnić blokadę wirowania, ale działa na jedynym procesorze, blokada prawdopodobnie nie zostanie zwolniona, dopóki bieżący proces lub wątek nie zostanie wywłaszczony przez O / S, co może chwilę potrwać i nic się nie stanie, dopóki nie nastąpi wywłaszczenie).

Ze sterowników urządzeń Linux przez Rubinni

W przeciwieństwie do semaforów, spinlocki mogą być używane w kodzie, który nie może spać, takim jak programy obsługi przerwań

Nie jestem ekspertem od jądra, ale oto kilka punktów:

Nawet maszyna jednoprocesorowa może używać blokad spinów, jeśli podczas kompilacji jądra włączone jest wywłaszczanie jądra. Jeśli wywłaszczanie jądra jest wyłączone, wówczas spin-lock (być może) rozwija się do instrukcji void .

Ponadto, kiedy próbujemy porównać Semaphore vs Spin-lock, uważam, że semafor odnosi się do tego używanego w jądrze - a NIE do tego używanego w IPC (obszar użytkownika).

Zasadniczo blokadę spinową należy stosować, jeśli sekcja krytyczna jest mała (mniejsza niż narzut uśpienia / przebudzenia), a sekcja krytyczna nie wywołuje niczego, co może spać! Jeśli sekcja krytyczna jest większa i może spać, należy użyć semafora.

Raman Chalotra.

Spinlock odnosi się do implementacji blokowania między gwintami przy użyciu instrukcji montażu zależnych od maszyny (takich jak test-and-set). Nazywa się to blokadą spinlock, ponieważ wątek po prostu czeka w pętli („kręci się”), wielokrotnie sprawdzając, aż blokada stanie się dostępna (zajęte oczekiwanie). Spinlocki są używane jako substytut muteksów, które są funkcją dostarczaną przez systemy operacyjne (nie CPU), ponieważ spinlocki działają lepiej, jeśli są zablokowane na krótki czas.

Semaphor to narzędzie dostarczane przez systemy operacyjne dla IPC, dlatego jego głównym przeznaczeniem jest komunikacja między procesami. Będąc narzędziem dostarczanym przez system operacyjny, jego wydajność nie będzie tak dobra, jak spinlock do blokowania między nimi (chociaż jest to możliwe). Semafory lepiej nadają się do blokowania przez dłuższy czas.

To powiedziawszy - wdrażanie blokad splinlock w montażu jest trudne i nie przenośne.

Chciałbym dodać moje spostrzeżenia, bardziej ogólne i niezbyt specyficzne dla Linuksa.

W zależności od architektury pamięci i możliwości procesora, możesz potrzebować blokady spinu w celu zaimplementowania semafora w systemie wielordzeniowym lub wieloprocesorowym, ponieważ w takich systemach może wystąpić sytuacja wyścigu, gdy dwa lub więcej wątków / procesów chce zdobyć semafor.

Tak, jeśli twoja architektura pamięci oferuje blokowanie sekcji pamięci przez jeden rdzeń / procesor, opóźniając wszystkie inne dostępy i jeśli twoje procesory oferują test-and-set, możesz zaimplementować semafor bez blokady spinu (ale bardzo ostrożnie! ).

Ponieważ jednak projektowane są proste / tanie systemy wielordzeniowe (pracuję w systemach wbudowanych), nie wszystkie architektury pamięci obsługują takie funkcje wielordzeniowe / wieloprocesorowe, tylko testuj i ustaw lub równoważne. Wtedy implementacja mogłaby wyglądać następująco:

• zdobyć spin-lock (zajęte czekanie)
• spróbuj zdobyć semafor
• zwolnij blokadę obrotową
• jeśli semafor nie został pomyślnie pozyskany, zawieś bieżący wątek do czasu zwolnienia semafora; w przeciwnym razie przejdź do sekcji krytycznej

Zwolnienie semafora należałoby zaimplementować w następujący sposób:

• zdobądź blokadę spin-lock
• zwolnij semafor
• zwolnij blokadę obrotową

Tak, a dla prostych semaforów binarnych na poziomie systemu operacyjnego byłoby możliwe użycie tylko blokady spin-lock jako zamiennika. Ale tylko wtedy, gdy chronione sekcje kodu są naprawdę bardzo małe.

Jak wspomniano wcześniej, jeśli i kiedy wdrażasz własny system operacyjny, pamiętaj, aby zachować ostrożność. Debugowanie takich błędów jest fajne (moim zdaniem, nie podzielane przez wielu), ale przede wszystkim bardzo żmudne i trudne.

„Mutex” (lub „blokada wzajemnego wykluczania”) jest sygnałem, którego mogą użyć dwa lub więcej procesów asynchronicznych, aby zarezerwować współdzielony zasób do wyłącznego użytku. Pierwszy proces, który uzyskuje własność „muteksu”, również uzyskuje własność współdzielonego zasobu. Inne procesy muszą poczekać, aż pierwszy proces zwolni własność „muteksu”, zanim będą mogły próbować go uzyskać.

Najpopularniejszym blokującym prymitywem w jądrze jest spinlock. Spinlock to bardzo prosty zamek jednozaciskowy. Jeśli proces próbuje uzyskać blokadę spinlocka i jest on niedostępny, będzie próbował (wirować), aż będzie mógł uzyskać blokadę. Ta prostota tworzy mały i szybki zamek.

Spinlock jest używany wtedy i tylko wtedy, gdy masz pewność, że oczekiwany wynik nastąpi bardzo szybko, przed upływem czasu wycinka wykonania wątku.

Przykład: W module sterownika urządzenia, sterownik zapisuje "0" w rejestrze sprzętowym R0 i teraz musi czekać, aż rejestr R0 stanie się 1. H / W odczytuje R0 i wykonuje jakąś pracę i zapisuje "1" w R0. Zwykle jest to szybkie (w mikro sekundach). Teraz kręcenie się jest o wiele lepsze niż pójście spać i przerywane przez H / W. Oczywiście podczas kręcenia należy uważać na awarię H / W!

Nie ma absolutnie żadnego powodu, aby aplikacja użytkownika się obracała. To nie ma sensu. Będziesz kręcić się, aby zdarzenie miało miejsce, a to zdarzenie musi zostać zakończone przez inną aplikację na poziomie użytkownika, co nigdy nie jest gwarantowane w krótkim czasie. Tak więc w trybie użytkownika w ogóle nie będę się obracał. Lepiej jest usypiać () lub mutexlock () lub semafor lock () w trybie użytkownika.

Od tego, co jest różnica między zamkami spin i semaforów? przez Maciej Piechotkowie :

Obaj zarządzają ograniczonymi zasobami. Najpierw opiszę różnicę między semaforem binarnym (muteksem) a blokadą spinu.

Blokady obrotowe wykonują zajęte oczekiwanie - tzn. Kontynuuje działanie pętli:

while (try_acquire_resource ()); 
 ...  
wydanie();

Wykonuje bardzo lekkie blokowanie / odblokowywanie, ale jeśli wątek blokujący zostanie przejęty przez inny, który będzie próbował uzyskać dostęp do tego samego zasobu, drugi będzie po prostu próbował odzyskać zasoby, dopóki nie wyczerpią się kwanty procesora.
Z drugiej strony mutex zachowuje się bardziej jak:

if (! try_lock ()) {
    add_to_waiting_queue ();
    czekać();
}
...
process * p = get_next_process_from_waiting_queue ();
p-> wakeUp ();

Dlatego jeśli wątek będzie próbował zdobyć zablokowany zasób, zostanie zawieszony do czasu, gdy będzie dla niego dostępny. Blokowanie / odblokowywanie jest znacznie cięższe, ale czekanie jest „darmowe” i „sprawiedliwe”.

Semafor to blokada, która może być używana wiele razy (znana z inicjalizacji) - na przykład 3 wątki mogą jednocześnie przechowywać zasób, ale nie więcej. Znajduje zastosowanie np. W problemie producenta / konsumenta lub generalnie w kolejkach:

P (zasoby_sem)
zasób = zasoby.pop ()
...
resources.push (zasoby)
V (zasoby_sem)

Różnica między semaforem, muteksem i spinlockiem?

Blokowanie w systemie Linux

blokada spinu może być utrzymana tylko przez jeden proces, podczas gdy semafor może być utrzymywany przez jeden lub więcej procesów. Blokada obrotowa czeka, aż proces zwolni blokadę, a następnie uzyska blokadę. Semafor śpi zamek tzn. Czeka i idzie spać.