Doua fire, patru variabile

[•Cosmin]

http://infoarena.ro/blog/concurent-pb-1

[•Mishu91]

Pentru că instructiunile se executa pe threaduri separate?

[•rgrig]

Da, sintaxa parallel P and Q vrea sa inseamne ca P si Q sunt in fire separate. Si?

[•claudiumihail]

In mod normal nu ar trebui sa fie nici o problema chiar si intr-un program multi threaded. Cat timp instructiunile alea se executa in ordinea din exemplu in fiecare thread, nu prea vad cum ar putea a=b=0 la final. Macar una ar trebui sa fie diferita de 0. Dar daca compilatorul decide sa schimbe ordinea instructiunilor si sa ai ceva gen:

Cod:

{ X = Y = 0 }
parallel
  a := X
  Y := 1
and
  b := Y
  X := 1

atunci ajungi sa ai a=b=0. Bine, fara vreun motiv anume nu cerd ca se apuca compilatorul sa modifice arbitrar ordinea instructiunilor tale. Poate daca are impresia ca optimizeaza ceva (ordinea instructiunilor afecetaza viteza in functie de cati cicli de procesor dureaza fiecare instructiune, sau ceva de genul). Si cum nu prea are de unde sti ca afecteaza logica programului in multi threaded execution, posibil sa se intample, I don't know.

Just my 2 cents.

[•andrei.finaru]

Eu cred ca cele 2 seturi de instructiuni se pot executa fara ca cele 2 threaduri sa comunice, astfel incat, pe fiecare thread, variabila X, respectiv Y, ramane 0, urmand ca sincronizarea variabilelor globale sa se execute dua terminarea executarii celor 2 ramuri paralele.
In apararea eventualelor aberatii pe care le-am scris, pot spune ca nu stiu programare concurenta.

[•repp4radu]

Pai daca cele 2 thread-uri se executa separat, in momentul in care se executa a := X, valoarea lui X nu s-a modificat inca, analog petru b := Y.
Practic prima data s-ar executa a := X, concomitent cu b := Y, moment la care X si Y sunt 0, iar mai apoi X := 1 si Y := 1. E corect?

[•bent_larsen]

Se citeste intai X in primul thread care va avea valoarea
0 dupa care se citeste Y in al doilea thread care va avea tot
valoarea 0. Daca la atribuire nu se citesc din nou valorile
pentru X si Y atunci la final a si b vor avea valorea 0.
Daca X si Y ar fi declarate ca volatile atunci nu ar mai aparea
situatia asta pentru ca valorile pentru X si Y ar fi recitite din nou (compilatorul nu
va mai face optimizari -in cazul nostru o optimizare e sa nu mai reciteasca valorile pentru X si Y).
Parerea mea...

[•rgrig]

Bravo, ati gasit trei explicatii posibile! O sa reformulez un pic ce ati spus pentru ca am niste lucruri de adaugat.

Intrebarea e un pic ciudata. De obicei vezi intrebari cu forma "ce face programul P" si modelul de executie este implicit, de exemplu definitia limbajului C. Aici insa intrebarea este "gasiti un model de executie in care programul X face cutare lucru". Din cauza asta nu exista un raspuns corect: poti inventa o gramada de modele de executie. Dar binenteles ca unele sunt mai bune ca altele. Ar trebui sa fie cat mai simple si cat mai apropiate de ce fac calculatoarele adevarate. Toata faza la intrebarea asta e sa descrii modelul de executie si sa argumentezi de ce are sens, nu sa spui pas cu pas ce se intampla intr-un model de executie care ramane implicit.

Pana nu demult modelul de memorie prevalent era consistenta secventiala (sequential consistency). Modelul acesta spune ca fiecare executie e echivalenta cu executia unui program secvential obtinut prin intercalarea instructiunilor. Binenteles ca e important ce anume constituie o instructiune. Sa zicem deocamdata ca fiecare linie din ce am scris e o instructiune. Atunci sunt 6 intercalari posibile.

1) Y:=1; a:=X; X:=1; b:=Y { a=0 /\ b=1 }
2) Y:=1; X:=1; a:=X; b:=Y { a=1 /\ b=1 }
3) Y:=1; X:=1; b:=Y; a:=X { a=1 /\ b=1 }
4) X:=1; Y:=1; a:=X; b:=Y { a=1 /\ b=1 }
5) X:=1; Y:=1; b:=Y; a:=X { a=1 /\ b=1 }
6) X:=1; b:=Y; Y:=1; a:=X { a=1 /\ b=0 }

In nici unul dintre cazuri nu e posibil ca a=b=0 la sfarsit.

Prima explicatie este ca granularitatea pentru instructiuni este mai mica: Fiecare linie din ce am scris este de fapt o citire urmata de o scriere. In practica insa problema se observa chiar daca a si b sunt registrii, caz in care granularitatea chiar e de o instructiune pe linie.

Alta explicatie este ca modelul de executie nu asigura consistenta secventiala. Motivul pe scurt e performanta, dar e bine sa vedem mai exact.

Executie speculativa. Aproape toate procesoarele au un pic de paralelism intern. De exemplu au o bucata de circuit care face adunari si una care face inmultiri. Daca instructiunea curenta e o adunare si peste cinci instructiuni vine o inmultire atunci n-o sa stea ci o sa faca si inmultirea acum, cu niste check-uri ca asta e OK (sa nu existe dependente de date). In cazul nostru, daca esti primul dintre procesoare atunci vezi instructiunile (Y:=1; a:=X) si nu le vezi pe cele executate de celalalt procesor/core. Din ce vezi, nu ai absolut nici un motiv sa crezi ca s-ar schimba ceva daca le executi in alta ordine, asa ca n-o sa ai nici o jena sa faci a:=X inainte de Y:=1. Compilatorul poate si el sa reordoneze instructiuni, dar problema apare chiar daca scriem direct in asamblor.

Cache. In fine, alta explicatie este ca fiecare procesor lucreaza cu cache-ul lui local, care nu se sincronizeaza decat din cand in cand cu memoria globala, fiindca operatia de sincronizare este lenta. (Inca o data, nu e necesar sa luam in considerare optimizari de compilator pentru a observa acest efect; hardware-ul deja are problema asta.)

Cam toate modelele de memorie ofera garantia ca memoria e coerenta: fiecare locatie de memorie are o istorie liniara. Dar nu prea mai garanteaza mult in afara de asta.

De obicei exista instructiuni speciale pentru a-i spune procesorului ca nu vrei sa reordoneze instructiuni (isync pe PowerPC) sau ca vrei sa-si syncronizeze cache-ul cu memoria globala (sync pe PowerPC, se mai numeste si bariera de memorie). Mai exista si alte instructiuni care garanteaza ca lucreaza direct cu memoria globala fara sa foloseasca cache (de exemplu compare&swap).

O problema care e studiata destul de activ este urmatoarea: Dat fiind un program si un model de memorie, ce bariere trebuie introduse pentru ca programul sa se comporte ca si cand modelul de memorie ar fi consistenta secventiala? De exemplu, unde trebuie pus sync/isync in programul de mai sus ca sa se comporte ca in modelul consistent secvential?

[•dbaluta]

Interesant de citit: http://lxr.linux.no/linux+v3.3/Documentation/memory-barriers.txt