Jak zaimplementowana jest synchronizacja wątków na poziomie języka asemblacji?

Chociaż znam koncepcje programowania współbieżnego, takie jak muteksy i semafory, nigdy nie rozumiałem, jak są one implementowane na poziomie języka asemblera.

Wyobrażam sobie, że istnieje zestaw pamięci "flagi" mówiące:

  • blokada a jest trzymana przez wątek 1
  • blokada B jest trzymana przez wątek 3
  • blokada C nie jest utrzymywana przez żaden gwint
  • etc

Ale jak dostęp do tych flag jest synchronizowany między wątkami? Coś w tym stylu. naiwny przykład stworzyłby tylko warunek rasy: 

  mov edx, [myThreadId]
wait:
  cmp [lock], 0
  jne wait
  mov [lock], edx
  ; I wanted an exclusive lock but the above 
  ; three instructions are not an atomic operation :(
Author: Andras Vass, 2010-03-03
Source

3 answers

  • w praktyce są one realizowane z CAS i LL / SC. (...i trochę wirowania przed rezygnacją z wycinka czasu wątku-zwykle przez wywołanie funkcji jądra, która przełącza kontekst.)
  • Jeśli potrzebujesz tylko spinlock , wikipedia podaje przykład, który wymienia CAS na lock prefiks xchg Na x86/x64. Tak więc w ścisłym sensie CAS nie jest potrzebny do wytworzenia spinlocka - ale nadal wymagana jest pewna atomiczność. W tym przypadku wykorzystuje operację atomową, która może zapisać rejestr do pamięci i zwrócić poprzednią zawartość tego gniazda pamięci w jednym kroku . (Dla wyjaśnienia: prefiks lock zapewnia sygnał #LOCK, który zapewnia, że obecny procesor ma wyłączny dostęp do pamięci. Na dzisiejszych procesorach niekoniecznie odbywa się to w ten sposób, ale efekt jest taki sam. Używając xchg upewniamy się, że nie zostaniemy uprzedzeni gdzieś pomiędzy czytaniem a pisaniem, ponieważ instrukcje nie zostaną przerwane w połowie drogi. Gdybyśmy więc mieli wyimaginowaną parę lock MOV reg0, mem / lock mov mem, reg1 (której nie mamy), to nie byłoby to dokładnie to samo - mogłoby być poprzedzone tylko pomiędzy tymi dwoma ruchami.)
  • na obecnych architekturach, jak podkreślono w komentarzach, najczęściej używa się atomowych prymitywów procesora i protokołów koherencji dostarczanych przez podsystem pamięci.
  • z tego powodu, nie tylko trzeba używać tych prymitywów, ale także konto dla spójności pamięci podręcznej / pamięci gwarantowanej przez architekturę.
  • mogą również występować niuanse implementacji. Biorąc pod uwagę np. spinlock:
    • zamiast naiwnej implementacji, powinieneś prawdopodobnie użyć np. ttas spin-lock z jakimś wykładniczym backoffem ,
    • na procesorze Hyper-Threaded powinieneś prawdopodobnie wydać pause instrukcje, które służą jako wskazówki, które obracasz - aby rdzeń, na którym pracujesz, mógł zrobić coś użytecznego podczas to
    • naprawdę powinieneś zrezygnować z przędzenia i kontroli nad innymi nitkami po jakimś czasie
    • itd...
  • jest to nadal tryb użytkownika - jeśli piszesz jądro, możesz mieć również inne narzędzia, których możesz użyć (ponieważ to Ty planujesz wątki i obsługujesz/włączasz / wyłączasz przerwania).
 23
Author: Andras Vass,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-03-07 14:27:11

Architektura x86 od dawna ma instrukcję o nazwie xchg, która zamieni zawartość rejestru z lokalizacją pamięci. xchg zawsze był atomowy.

Zawsze istniał prefiks lock, który mógłby być zastosowany do dowolnej pojedynczej instrukcji, aby uczynić tę instrukcję atomową. Zanim pojawiły się systemy wieloprocesorowe, wszystko to naprawdę miało na celu uniemożliwienie dostarczenia przerwania w środku zablokowanej instrukcji. (xchg było w domyśle zamknięte).

Ten artykuł zawiera przykładowy kod wykorzystujący xchg do zaimplementowania spinlocka http://en.wikipedia.org/wiki/Spinlock

Kiedy zaczęto budować systemy wielordzeniowe i wielordzeniowe, potrzebne były bardziej wyrafinowane systemy, aby zapewnić, że lock i xchg zsynchronizują wszystkie podsystemy pamięci, w tym pamięć podręczną l1 na wszystkich procesorach. Mniej więcej w tym czasie nowe badania nad algorytmami blokującymi i bezkluczowymi wykazały, że Atomic CompareAndSet był bardziej elastyczny prymitywne mieć, więc bardziej nowoczesne procesory mają to jako instrukcję.

Dodatek: w komentarzach andras dostarczył "zakurzony Stary" wykaz instrukcji, które pozwalają na prefiks lock. http://pdos.csail.mit.edu/6.828/2007/readings/i386/LOCK.htm

 11
Author: John Knoeller,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-03-03 03:48:29

Lubię myśleć o synchronizacji wątków jako oddolnej, gdzie procesor i system operacyjny zapewniają konstrukcję prymitywną do bardziej wyrafinowanej

Na poziomie procesora masz CAS I LL / SC, które pozwalają wykonać test i przechowywać w jednej operacji atomowej ... masz również inne konstrukcje procesorów, które pozwalają na wyłączanie i włączanie przerwań (jednak są one uważane za niebezpieczne ... w pewnych okolicznościach nie masz innej opcji, jak tylko użyć them)

System operacyjny zapewnia możliwość przełączania kontekstu między zadaniami, które mogą się zdarzyć za każdym razem, gdy wątek użyje swojego wycinka czasu ... lub może się to zdarzyć z innych powodów (przyjdę do tego)

Potem są konstrukcje wyższego poziomu, takie jak mutexy, które wykorzystują te prymitywne mechanizmy dostarczane przez procesor (myśl spinning mutex)... która będzie stale czekać na spełnienie warunku i sprawdza go atomicznie

Then these spinning mutex może korzystać z funkcjonalności dostarczanej przez system operacyjny (przełącznik kontekstowy i wywołania systemowe, takie jak yield, które zrzeka się kontroli na inny wątek) i daje nam mutexes

Te konstrukcje są dalej wykorzystywane przez konstrukcje wyższego poziomu, takie jak zmienne warunkowe (które mogą śledzić, ile wątków czeka na mutex i który wątek ma zezwolić jako pierwszy, gdy mutex stanie się Dostępny)

Te konstrukcje mogą być dalej wykorzystywane w celu zapewnienia bardziej wyrafinowanej synchronizacji konstrukcje ... przykład: semafory itp

 2
Author: jsshah,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-03-03 02:32:47