🚀 go-pugleaf

minięty czas pisze:
> onegdaj ‟Bogdan (bogdro)” rzecze:
>> W dniu 08.01.2010 14:48, minięty czas pisze:
>>>     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:
         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)

-- 
Pozdrawiam
Michoo