🚀 go-pugleaf

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"?

-- 
Pozdrawiam/Regards - Bogdan                     (GNU/Linux & FreeDOS)
Kurs asemblera x86 (DOS, GNU/Linux):http://rudy.mif.pg.gda.pl/~bogdro
Grupy dyskusyjne o asm:  pl.comp.lang.asm alt.pl.asm alt.pl.asm.win32
www.JabberPL.org www.torproject.org Soft (EN): miniurl.pl/bogdro-soft

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.
-- 
 qo   |)      CPL: cs[0..1] (ss[0..1]) p lvl of curr code!
    _x/ ,     RPL: seg_sel[0..1] privilege lvl of seg_sel!
    |    ng  __ -- __ -- __ -- __ -- __ -- __ -- __ -x86-,
,__ -- __ -- DPL: 2._word_of_seg_desc[13..14]:`f seg_desc ,

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

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"

minięty czas pisze:
> onegdaj ‟Michoo” rzecze:
>> 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.
Przeczytaj dokumentację intela, ok?

cmpxchg składa się z szeregu operacji mikrokodu oraz 2 dostępów do 
magistrali (wykonywanie tej instrukcji na rejestrach ma mało sensu).
Faza 1: pobrania wartości z pod adresu i wykonanie porównania.
Faza 2: zapisanie wyniku pod adres w pamięci LUB do rejestru.

Ponieważ w 2 fazie nie zawsze jest zapis do pamięci pomiędzy nimi 
magistrala jest zwalniana - przy dużym, równoległym ruchu na procesorze 
2 rdzeniowym wszystko się sypie w ułamku sekundy. Dodanie prefiksu lock 
powoduje zablokowanie dostępu do magistrali i danych w pamięci cache 
(cache coherency) na czas całej instrukcji. Czyli po prostu zapewnia 
ATOMOWE WYKONANIE instrukcji.

Skoro atomowe, to ten kto pierwszy ją zaczął ten zatrzymał pipeline 
wszystkich innych na czas 2 dostępów do pamięci i wymusił u nich 
odświeżenie cache - jego nikt nie zatrzyma.

>     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.  
Napisałem, że koszta są - niewielkie.

> 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’… ;-)
Jakbyś się dokształcił w kwestii tego jak działa arbitraż na magistrali, 
jak działa cache coherency protocol, jak wygląda zazwyczaj cykl 
rozkazowy, jak działa pipeline to byś doszedł do wniosku, że:
a) wszystkie instrukcje są blokujące, bo w ich obrębie jest blokowana 
np. magistrala
lub
b) dodanie prefiksu lock sprawia, że jeden opcode jest tłumaczony na 
jedną instrukcję, a nie kilka.

Potem moglibyśmy kontynuować dyskusję na temat zastosowań?

> i jak by wyglądał taki algorytm na procesor ‘risc’…?
Poczytaj specyfikację choćby arm7 (LDM). Tam jest zazwyczaj łatwiej, bo 
nie ma systemów wielordzeniowych i wystarcza zablokowanie przerwań do 
czasu ukończenia instrukcji. Jeżeli jest wiele procesorów/rdzeni/(dma) 
to już wchodzi jakiś arbitraż na magistrali i trzeba blokować równoległy 
do niej dostęp.

-- 
Pozdrawiam
Michoo

onegdaj ‟Michoo” rzecze:
> minięty czas pisze:
>> onegdaj ‟Michoo” rzecze:
>>> 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.
> Przeczytaj dokumentację intela, ok?
> 
> cmpxchg składa się z szeregu operacji mikrokodu oraz 2 dostępów do
> magistrali (wykonywanie tej instrukcji na rejestrach ma mało sensu).
> Faza 1: pobrania wartości z pod adresu i wykonanie porównania. Faza 2:
> zapisanie wyniku pod adres w pamięci LUB do rejestru.
> 
> Ponieważ w 2 fazie nie zawsze jest zapis do pamięci pomiędzy nimi
> magistrala jest zwalniana - przy dużym, równoległym ruchu na procesorze
> 2 rdzeniowym wszystko się sypie w ułamku sekundy. Dodanie prefiksu lock
> powoduje zablokowanie dostępu do magistrali i danych w pamięci cache
> (cache coherency) na czas całej instrukcji. Czyli po prostu zapewnia
> ATOMOWE WYKONANIE instrukcji.
> 
> Skoro atomowe, to ten kto pierwszy ją zaczął ten zatrzymał pipeline
> wszystkich innych na czas 2 dostępów do pamięci i wymusił u nich
> odświeżenie cache - jego nikt nie zatrzyma.
> 
>>     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.
> Napisałem, że koszta są - niewielkie.
> 
>> 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’… ;-)
> Jakbyś się dokształcił w kwestii tego jak działa arbitraż na magistrali,
> jak działa cache coherency protocol, jak wygląda zazwyczaj cykl
> rozkazowy, jak działa pipeline to byś doszedł do wniosku, że: a)
> wszystkie instrukcje są blokujące, bo w ich obrębie jest blokowana np.
> magistrala
> lub
> b) dodanie prefiksu lock sprawia, że jeden opcode jest tłumaczony na
> jedną instrukcję, a nie kilka.
> 
> Potem moglibyśmy kontynuować dyskusję na temat zastosowań?
> 
>> i jak by wyglądał taki algorytm na procesor ‘risc’…?
> Poczytaj specyfikację choćby arm7 (LDM). Tam jest zazwyczaj łatwiej, bo
> nie ma systemów wielordzeniowych i wystarcza zablokowanie przerwań do
> czasu ukończenia instrukcji. Jeżeli jest wiele procesorów/rdzeni/(dma)
> to już wchodzi jakiś arbitraż na magistrali i trzeba blokować równoległy
> do niej dostęp.
    jesteś  zwykłym trolem, który przepisuje przepisane wiadomości i do-
łącza  tylko tekst „czytaj to!” (“README.TXT”).   byłeś już w plonkowni-
cy, ale chwilowo to zignorowałem, bo odpowiedziałeś na mój tekst techni-
cznie —nigdy więcej. :-)
    nie  rozumiesz  całości podanego przez siebie przykładu, a pouczanie
innych  do  czytania tego co ty i nie rozumienia w taki sam sposób sobie
daruj… :->   he‐he‐he…
    PLONK2
-- 
 qo   |)      CPL<=dataDPL CPL==/>=codeDPL:conform'/nc';max=CPL! AV0ID bHp
    _x/ ,     CPL<=TSS,gateDPL CPL>=/==dest_DPL:/(jmp&nc') ,RPL!- #GP -o0o
    |    ng  __ -- __ -- __ -- __ -- __ -- __ -- __ -- __ -x86-, EV3RY o0o
,__ -- __ -- Current/Requested/DescriptorPrivilegeLevel C/R/DPL , d4y m:#=

onegdaj ‟minięty czas” rzecze:
>     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’…?
taka  instrukcja  w ogólności robi co następuje: używa danych globalnych
do  modyfikacji  stanu  lokalnego, a następnie warunkowo modyfikuje daną
globalną.   ze  względu na konieczność synchronizacji różnych procesorów
w świecie rzeczywistym— ta instrukcja w takiej postaci jak obecnie unie-
możliwiałaby  dołączanie niezależnych procesorów do architektury.   two-
rzenie  bardzie zaawansowanych algorytmów wymaga powiększania części mo-
dyfikującej stan lokalny, co powoduje wykonywanie przez procesory pracu-
jące synchronicznie— niepotrzebnych instrukcji i uniemożliwia skalowanie
mocy obliczeniowej przez łaczenie procesorów.   …
-- 
 qo   |)      CPL<=dataDPL CPL==/>=codeDPL:conform'/nc';max=CPL! AV0ID bHp
    _x/ ,     CPL<=TSS,gateDPL CPL>=/==dest_DPL:/(jmp&nc') ,RPL!- #GP -o0o
    |    ng  __ -- __ -- __ -- __ -- __ -- __ -- __ -- __ -x86-, EV3RY o0o
,__ -- __ -- Current/Requested/DescriptorPrivilegeLevel C/R/DPL , d4y m:#=

minięty czas pisze:
> onegdaj ‟Michoo” rzecze:

>>> i jak by wyglądał taki algorytm na procesor ‘risc’…?
>> Poczytaj specyfikację choćby arm7 (LDM). Tam jest zazwyczaj łatwiej, bo
>> nie ma systemów wielordzeniowych i wystarcza zablokowanie przerwań do
>> czasu ukończenia instrukcji. Jeżeli jest wiele procesorów/rdzeni/(dma)
>> to już wchodzi jakiś arbitraż na magistrali i trzeba blokować równoległy
>> do niej dostęp.
>     jesteś  zwykłym trolem, który przepisuje przepisane wiadomości i do-
> łącza  tylko tekst „czytaj to!” (“README.TXT”). 
Wg. mnie to TY albo się nie znasz, albo (i) trolujesz.
Co ma ALGORYTM do procesora risc? Algorytm jest jeden. Za pomocą CAE 
wstaw do ogona listy nowy element. (chyba) Wszystkie nowe procesory 
dostarczają odpowiednią instrukcję. Tak więc implementacja się różni 
właściwie jedynie składnią asma.


> byłeś już w plonkowni-
> cy, ale chwilowo to zignorowałem, bo odpowiedziałeś na mój tekst techni-
> cznie —nigdy więcej. :-)

To baaardzo ciekawe, skoro na pl.comp.lang.asm napisałem może z 3 posty?


>     nie  rozumiesz  całości podanego przez siebie przykładu, a pouczanie
> innych  do  czytania tego co ty i nie rozumienia w taki sam sposób sobie
> daruj… :->   he‐he‐he…
Chcesz mnie 'zjechać'? Proszę bardzo, zapraszam, kilku osobom się to do 
tej pory nawet udało.
Jedna prośba - merytorycznie - ODNIEŚ SIĘ DO MOJEGO TEKSTU - pokaż gdzie 
popełniłem błędy a nie przypieprzaj się personalnie "jesteś trolem".

Link do intela - w którym miejscu napisałem coś błędnie o tej instrukcji?

http://www.intel.com/software/products/documentation/vlin/mergedprojects/analyzer_ec/mergedprojects/reference_olh/mergedProjects/instructions/instruct32_hh/vc42.htm


-- 
Pozdrawiam
Michoo

On 2010-01-12 12:54, Michoo wrote:
> minięty czas pisze:
>> onegdaj ‟Michoo” rzecze:
>
>>>> i jak by wyglądał taki algorytm na procesor ‘risc’…?
>>> Poczytaj specyfikację choćby arm7 (LDM). Tam jest zazwyczaj łatwiej, bo
>>> nie ma systemów wielordzeniowych i wystarcza zablokowanie przerwań do
>>> czasu ukończenia instrukcji. Jeżeli jest wiele procesorów/rdzeni/(dma)
>>> to już wchodzi jakiś arbitraż na magistrali i trzeba blokować równoległy
>>> do niej dostęp.
>> jesteś zwykłym trolem, który przepisuje przepisane wiadomości i do-
>> łącza tylko tekst „czytaj to!” (“README.TXT”).
> Wg. mnie to TY albo się nie znasz, albo (i) trolujesz.
Wez zobacz jego inne posty, belkot taki ze nie da sie czytac.
Szkoda czasu na dyskusje, wyjasniles temat az za dobrze. Jesli gosciu 
nie rozmumie to juz jego problem.

Pozdr

Marek

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.

Proponuję autorowi pytania, by zapoznał się z pojęciem ALGORYTMU 
NIEBLOKUJĄCEGO (i zrozumiał, o jakie "blokowanie" tu chodzi) i 
paradygmatami CAS, DCAS, CAS2, MCAS, CASN. W Pentium CMPXCHG jest 
realizacja paradygmatu CAS, zaś CMPXCHG8B - paradygmatu DCAS.  W 
szczególności żeby zrozumiał różnicę między BLOKADĄ SYSTEMOWĄ nakładaną 
na zasoby, długotrwała i bez gwarancji zwolnienia, a blokadą dostępu do 
słowa pamięci na czas wykonywania jednej instrukcji. I ogólnie strategią 
przetwarzania nieblokującego (vide nieblokująca lista wiązana, 
nieblokująca kolejka, nieblokujący stos itd.) i jej różnicą w stosunku 
do klasycznego schematu ZABLOKUJ - PRZETWÓRZ - ODBLOKUJ.

Proponuję 1. rodział książki "Perełki programowania gier", tom 6. z 
HELIONa.

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.
Przykładem zastosowania algorytmu nieblokującego był funkcja $58 w DOS. 
Gdy zdarzyłoby się, że kilka procesów w sieci chciałoby równocześnie 
utworzyć plik o określonej nazwie (mało prawdopodobne, ale 
niewykluczone), to tylko jednemu się to uda, wszystkie inne dostaną kod 
powrotu 80.

onegdaj ‟Andrzej Grażyński” 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.
> Proponuję autorowi pytania, by zapoznał się z pojęciem ALGORYTMU
> NIEBLOKUJĄCEGO (i zrozumiał, o jakie "blokowanie" tu chodzi) i
> paradygmatami CAS, DCAS, CAS2, MCAS, CASN. W Pentium CMPXCHG jest
> realizacja paradygmatu CAS, zaś CMPXCHG8B - paradygmatu DCAS.  W
> szczególności żeby zrozumiał różnicę między BLOKADĄ SYSTEMOWĄ nakładaną
> na zasoby, długotrwała i bez gwarancji zwolnienia, a blokadą dostępu do
> słowa pamięci na czas wykonywania jednej instrukcji. I ogólnie strategią
> przetwarzania nieblokującego (vide nieblokująca lista wiązana,
> nieblokująca kolejka, nieblokujący stos itd.) i jej różnicą w stosunku
> do klasycznego schematu ZABLOKUJ - PRZETWÓRZ - ODBLOKUJ.
> 
> Proponuję 1. rodział książki "Perełki programowania gier", tom 6. z
> HELIONa.
nie  znam  tych  wszystkich skrócików ;-) , ale nie autor odpowiedzi się
trochę  wgłębi w list autora pytania… :-)   czy czasem te różne paradyg-
manty nie przenoszą po prostu tego samego blokowania na inne poziomy wi-
doczności  i szerokości, bardziej  ukryte dla programisty?   a to ciągle
ta sama instrukcja logiczna.
-- 
 qo   |)      CPL: cs[0..1] (ss[0..1]) p lvl of curr code!
    _x/ ,     RPL: seg_sel[0..1] privilege lvl of seg_sel!
    |    ng  __ -- __ -- __ -- __ -- __ -- __ -- __ -x86-,
,__ -- __ -- DPL: 2._word_of_seg_desc[13..14]:`f seg_desc ,

> nie  znam  tych  wszystkich skrócików ;-) , ale nie autor odpowiedzi się
> trochę  wgłębi w list autora pytania… :-)   czy czasem te różne paradyg-
> manty nie przenoszą po prostu tego samego blokowania na inne poziomy wi-
> doczności  i szerokości, bardziej  ukryte dla programisty?   a to ciągle
> ta sama instrukcja logiczna.

Tak, przenoszą, z istotnymi różnicami:

0. Blokada realizowana jest w sposób sprzętowy

1. Nakładanie i zdejmowanie blokady nie jest odrębną częścią algorytmu 
rozwiązywania zadania, jest elementem atomu wchodzącego w skład tego 
algorytmu

2. Blokada nakładana jest na czas wykonywania jednej instrukcji

3. Istnieje gwarancja zdjęcia blokady, bo wykonywanie instrukcji musi 
się zakończyć (jeśli tak nie jest, mamy ogólną awarię sprzętową, co jest 
katastrofą dla całego systemu).

4. Nie istnieją problemy typowe dla synchronizacji, np. deadlock


5. Nie ma gwarancji uzyskania wyłącznego dostąpu do zasobu, nie ma więc 
gwarancji wykonania żądanej operacji.


Dla wyjaśnienia:


CAS - Compare And Swap:

CAS(M, A, B)

atomowe wykonanie sekwencji


if M = A
then
   M := B

bądź

if M = A
then
   XCHG(M, B)


bądź

if M = A
then
   M := B
else
   A := M

( tak działa CMPXCHG)

----------

DCAS - double CAS

jak wyżej, tylko dotyczy dwóch PRZYLEGŁYCH słów

if DWORD(M1, M2) = DWORD(A1, A2)
then
   DWORD(M1, M2) := DWORD(B1, B2)
else
    DWORD(A1, A2) := DWORD(M1, M2)

Tak działa CMPXCHG8B


------------

Casn

Jak wyżej, tylko dotyczy zbioru N niezależnych o siebie słów:


if {M1 .. Mn} = {A1 .. An}
then
   {M1 .. Mn} := {B1 .. Bn}
else
   {A1 .. An} := {M1 .. Mn}

W szczególności CAS2 jest szczególnym przypadkiem CASn dla n=2


Zauważ, czym CAS2 różni się od DCAS.



Przykład zastosowania:

Do wielodostępnej listy jednokierunkowej, której pierwszy element 
wskazywany jest przez TOP, dołączamy na początek nowy rekord R:

R: Record
      Next: <adres nastepnego rekordu>
    ...
    End;




A := TOP;
B := Addr(R);
R.Next := A;
CAS(TOP, A, B);

{ dlaczego nie mogę napisać CAS(TOP, R.Next , Addr(R)) ? )

onegdaj ‟Andrzej Grażyński” rzecze:
> , przenoszą, z istotnymi różnicami:
> 0. Blokada realizowana jest w sposób sprzętowy
1. :->
> 1. Nakładanie i zdejmowanie blokady nie jest odrębną częścią algorytmu
> rozwiązywania zadania, jest elementem atomu wchodzącego w skład tego
> algorytmu
> 2. Blokada nakładana jest na czas wykonywania jednej instrukcji
> 3. Istnieje gwarancja zdjęcia blokady, bo wykonywanie instrukcji musi
> się zakończyć (jeśli tak nie jest, mamy ogólną awarię sprzętową, co jest
> katastrofą dla całego systemu).
> 4. Nie istnieją problemy typowe dla synchronizacji, np. deadlock
> 5. Nie ma gwarancji uzyskania wyłącznego dostąpu do zasobu, nie ma więc
> gwarancji wykonania żądanej operacji.
od  czasu  podania  przez ciebie skrótów zatrudniłem ‟Google” za reklamy
z ‘vatem’ :-) i wynikło, że  te  skróciki mówią tylko różnych typach da-
nych przenoszonych po fakcie zajcia warunku.
teraz  sobie  pomyśl co się będzie działo dla dowolnie dużej liczby syn-
chronicznie  pracujących  procesorów, gdy  wszystkie  wykonałyby dowolną
z tych  instrukcji  na tej samej danej w równoległym algorytmie.   nadal
się skaluje bez kosztów? ;-)
-- 
―oh yea, i got it!
―oh, stupid!
D. Icke

minięty czas pisze:
> onegdaj ‟Andrzej Grażyński” rzecze:
>> , przenoszą, z istotnymi różnicami:
>> 0. Blokada realizowana jest w sposób sprzętowy
> 1. :->
>> 1. Nakładanie i zdejmowanie blokady nie jest odrębną częścią algorytmu
>> rozwiązywania zadania, jest elementem atomu wchodzącego w skład tego
>> algorytmu
>> 2. Blokada nakładana jest na czas wykonywania jednej instrukcji
>> 3. Istnieje gwarancja zdjęcia blokady, bo wykonywanie instrukcji musi
>> się zakończyć (jeśli tak nie jest, mamy ogólną awarię sprzętową, co jest
>> katastrofą dla całego systemu).
>> 4. Nie istnieją problemy typowe dla synchronizacji, np. deadlock
>> 5. Nie ma gwarancji uzyskania wyłącznego dostąpu do zasobu, nie ma więc
>> gwarancji wykonania żądanej operacji.
> od  czasu  podania  przez ciebie skrótów zatrudniłem ‟Google” za reklamy
> z ‘vatem’ :-) i wynikło, że  te  skróciki mówią tylko różnych typach da-
> nych przenoszonych po fakcie zajcia warunku.
> teraz  sobie  pomyśl co się będzie działo dla dowolnie dużej liczby syn-
> chronicznie  pracujących  procesorów, gdy  wszystkie  wykonałyby dowolną
> z tych  instrukcji  na tej samej danej w równoległym algorytmie.   nadal
> się skaluje bez kosztów? ;-)
A co by się działo, gdy każdy z tych procesorów realizował proces 
bazujący na klasycznych blokadach? Algorytm nieblokujący musi być 
przygotowany na to, że nie uda mu się wykonanie pewnej operacji 
operującej na chronionym zasobie. Oczywiście mógłby w pętli próbować aż 
do skutku, ale to jest jeszcze gorsze niż klasyczne blokady (które 
wynaleziono właśnie po to, by takich pętli unikać). Jeśli proces nie ma 
w danej chwili nic lepszego do roboty (a zwykle jednak ma), to może 
odczekać LOSOWY interwał czasu i spróbować ponownie. Ta LOSOWOŚĆ ma 
chronić przed tym by np. kilkadziesiąt procesorów w jednej chwili 
chciało wykonać np. CMPXCHG na tym samym słowie pamięci

Jednym z paradygmatów przetwarzania równoległego jest dystans 
informacyjny, czyli odległość w czasie między ustaleniem JAKĄ OPERACJĘ 
należy wykonać, a zapotrzebowaniem na WYNIKI tej operacji, na przykład 
ustalenie klucza wczytywanego rekordu, a zapotrzebowaniem na zawartość 
tego rekordu. Zapoczątkowujemy asynchroniczne czytanie, a gdy dochodzimy 
do momentu, gdy zawartość wspomnianego rekordu staje się istotna, 
upewniamy się, że wczytywanie się zakonczyło albo czekamy na jego 
zakończenie.

Jeżeli rozpatrzymy przypadek nieblokującego dodawania rekordu na szczyt 
listy, to istnieje dystans czasowy między wyprodukowaniem rekordu a 
momentem, kiedy MUSI się ów rekord znaleźć w tej liście. W trakcie tego 
interwalu proces może robić inne pożyteczne rzeczy i okresowo probować 
dodać rekord do listy. Nie marnuje się czasu na oczekiwanie na blokadzie.