🚀 go-pugleaf

onegdaj ‟Michoo” rzecze:
> minięty czas pisze:
>> onegdaj ‟Bogdan (bogdro)” rzecze:
>>>>     czy  instrukcja ‘compare  and  set’ (oraz  wszystkie  podobne),
>>>> to  nie jest instrukcja blokująca?   co z tego, że sama w sobie nie
>>>> blo- kuje, jeśli  i tak  oparte  na  niej algorytmy używają jej jako
>>>> blokera? algorytmy, które  zwą siebie mianem ‘lock—free’…   to chyba
>>>> tylko zwykła reklama.
>>>  Sam sobie odpowiadasz: "co z tego, że sama w sobie nie blokuje". Ta
>>> instrukcja jest nieblokująca, dlatego należy ją poprzedzić prefiksem
>>> LOCK. Wtedy, oczywiście, staje się blokująca.
>>>  Swoją drogą, nie masz na myśli "compare and exchange"?
>> 	ale nie o to dokładnie.
>> 	wiadomo, że prefiks “lock” blokuje procesor (czy cokolwiek)
>> 	·wewnętrznie·, ale mam na myśli typowe zastosowania tej instrukcji
>> 	(tak, ‘and exchange’). ta instrukcja w algorytmach ‘lock–free’
>> 	występuje zwykle jako warunek pętli, co wydaje się, że działa tak samo
>> 	jak każdy inny mechanizm blokowania.
> Typowe przykłady zastosowania ssą ;) (Tzn zazwyczaj robi się na tym taki
> mutex z aktywnym oczekiwaniem.)
> 
> Rozważmy kolejkę fifo służącą do przekazywania komunikatów między n
> producentami a k konsumentami:
> standardowo)
> blokujesz dostęp do kolejki
> wstawiasz element
> odblokowujesz dostęp
> 
> blokowanie jak sama nazwa wskazuje uniemożliwia innym równoległy dostęp,
>   jeżeli zderzą się 4 procesy to 1 wejdzie do sekcji krytycznej a reszta
> pójdzie spać (co jest drogie - zmiana kontekstu)
> 
> w podejściu lock-free)
> próbujesz wstawić coś do kolejki
> jeżeli próba się nie powiodła to ją ponawiasz
> 
> cały czas nie blokujesz nikomu dostępu - jeżeli zderzą się 4 procesy to
> 1 zakończy akcję z sukcesem a reszta ponowi próbę w następnym cyklu a
> dzięki prefiksowi lock za każdym razem jednemu się powiedzie.
> 
> O ile dobrze pamiętam to jest to działające wstawianie do listy
> jednokierunkowej:
> 
> extern "C" int enqueue(void *item,void *queue)__attribute__((fastcall));
> 
> section .text
>          global enqueue
> ;edx - wskażnik na wskaźnik na kolejkę, ecx - wskaźnik na wstawiany
> element enqueue:
wskaźnik na adres pierwszego elementu kolejki. ;-)
>          mov eax,[edx]           ;[**]ładujemy adres aktualnego ogona
> pre:    mov [ecx],eax           ;[*]ustawiamy go jako poprzednika we
> wstawianym elemencie
>          lock cmpxchg [edx],ecx  ;staramy się podmienić wskaźnik na ogon
> listy
>          jne pre                 ;jak się nie powiodło to ponawiamy
>          próbę ret
> 
> koszt całości jest niewielki, mimo, że lock zaburza trochę przetwarzanie
> strumieniowe (blokada magistrali)
    raczej  nie  ma  gwarancji, że jednemu wątkowi się powiedzie w pier-
wszym podejściu, chyba że w doborze instrukcji i ich ułożeniu uwzględnić
docelową architekturę, by wydawało się, że dzięki jednoczesnemu przetwa-
rzaniu kilku instrukcji przetworzy je w jednym cyklu.
    to  co  powyżej  to  jest  właśnie  blokada  dostępu (czyli  tzw.
‘lock’), ale  przeniesiona  na  poziom instrukcji procesora architektury
‘cisc’, co nie oznacza, że automatycznie zawsze i w każdym przypadku ta-
ka  instrukcja  jest  wykonywana  bez dodatkowych kosztów, niewidocznych
dla  programu.   więc wydaje się, że odpowiedniejszą nazwą dla tego typu
algorytmów byłaby ‘mutex—free’, czyli pozbycie się blokowania uniwersal-
nego  na  rzecz  blokowania  wewnątrzprocesorowego.   jakby  zmierzanie
do  rozwiązań  typu ‘clean  box’, ale  w rzeczywistości  to  jest zwykłe
‘black box’… ;-)
    a o co mi tak naprawdę chodzi? :-)   tego można się dowiedzieć, zas-
tanawiając  się, kiedy ·nie· można  zastosować  instrukcji typu ‘compare
and  set’ i dlaczego —ale  nie  dlatego, że  przenosi  zbyt mało danych.
i jak by wyglądał taki algorytm na procesor ‘risc’…?
    „―it's very suspicious…   ―he's a garbage boy.   get relax.”
-- 
/ qo   |)    :@=N%_g=v=a=g_eD_e=c()=d=8! =%!gN@8'Re. w8in/ad
\    _x/ ,   ;h-%-a'hA'H4,X0'Xo~xo~xO,R`-%EXp01ITed: *-7/+eh
/    |    ng `-%__%--'__%--'__%--~__%--^%B`/$qV3r[o; &GooMee
L_._o_O_*_^_"_'_`_ -> http://thereis.notlong.com <- `L"EnOF"