Din nou un articol pentru programatori. Link-ul video din final m-a inspirat sa popularizez cateva concepte despre arhitecturi multi-threading, inclusiv cateva idei din prezentare (pentru lenesi).
Ce sunt theadurile (pentru foarte incepatori)
O aplicatie se executa de obicei intr-un singur process (exemplu programul Word cand il gasiti in "Task Manager"). Procesul poate contine insa mai multe fire de executie, numite threaduri. De exemplu in timpul in care se editeaza documentul, un thread separat parcurge ciclic documentul si semnaleaza erorile de tastare. Threadurile sunt ca niste procese care folosesc in comun aceeasi memorie si care sunt distruse impreuna cand se distruge procesul.
De ce programare multi-threading ?
1. Aplicatiile multi-threading pot fi distribuite pe mai multe procesoare/cores. O aplicatie single-threaded functioneaza la aceeasi viteza indiferent daca serverul are 1 procesor sau 4 procesoare (presupunem procesoarele identice). O aplicatie care imparte treaba egal pe 4 threaduri poate rula pana la de 4 ori mai repede pe un procesor modern "multicore" cu 4 cores.
2. Chiar daca exista doar un singur procesor, unele operatii au un fir logic separat si este mai usor sa fie descrise ca threaduri (fire de executie) diferite. De exemplu un browser poate descarca (download) un fisier mare si in acelasi timp sa afiseze o pagina. Teoretic asta s-ar putea face si intr-un singur thread, dar in acest caz ar trebui ca bucata de program care afiseaza pagina sa traga cu ochiul din cand in cand si sa mai lucreze si la download. Situatia se complica cand exista mai multe actiuni care trebuiesc multiplexate. Este mai simplu ca fiecare actiune sa fie programata ca executandu-se in paralel (pe un thread) si aproape fara legatura cu celelalte.
3. Spre deosebire de doua procese diferite, comunicarea intre doua threaduri este mult mai simpla si economica din punct de vedere al comunicatiei. Doua procese pot comunica copiind datele si trecand prin kernel-ul sistemului de operare. Exista intr-adevar si varianta cu shared-memory, dar nu este simplu de implementat.
Doua threaduri pot folosi in comun aceleasi date fara a fi necesara copierea. Bineinteles, in acest caz trebuie gestionat cu atentie accesul concurent la date, pentru a nu folosi date incomplet modificate de catre alt thread.
Probleme in programarea multithreading
Este dificil sa programezi corect multi-threading. Este foarte complicat sa prevezi toate interactiunile posibile care se pot intampla intre threaduri diferite care actioneaza asupra acelorasi date. As spune chiar ca atunci cand este posibil este recomandata programarea single-thread si separarea operatiilor in procese diferite. Totusi, uneori cea mai buna solutie este un program multi-threading.
P1: Utilizarea unor informatii incomplete (corupte)
Pe procesoarele obisnuite, operatiile mai mari de 32biti (4 bytes) nu sunt de obicei atomice. Asta inseamna ca un alt thread poate accesa datele in mijlocul operatiei care le modifica.
Un exemplu redus la cifre mai mici, ar insemna ca daca un thread (1) modifica o variabila din 32768 (1000000000000000) in 32767(0111111111111111), un alt thread (2) poate gasi operatia efectuata doar pe prima jumatate a numarului si sa citeasca 32512 (0111111100000000).
Aceste "race-conditions" se intampla foarte rar, de aceea sunt foarte greu de descoperit la teste. Totusi, atunci cand se intampla pot face programul sa "crape".
Lucrurile sunt mult mai complexe atunci cand operatiile concurente manipuleaza date mai mari. Atunci creste si probabilitatea ca evenimentul "improbabil" sa apara. Probabilitatea mai creste si cu numarul de "cores" ale sistemului. Ce nu se intampla pe 2 cores, poate deveni destul de probabil pe 4 cores.
S1: Protejarea datelor accesate concurent cu "lock-uri"
"Lock-urile" sunt apeluri prin care se blocheaza accesul la o zona de date (resursa) pana la terminarea modificarii. Accesul este protejat de o structura de date numita "mutex" (de la "mutual exclusive"). Aceasta structura spune daca resursa respectiva este blocata de altcineva (precum un bec aprins la baie).
Totusi, in majoritatea limbajelor de programare, lock-ul nu impiedica efectiv accesul la date. Se presupune ca alt thread utilizator va verifica "mutex-ul" inainte de a incepe o modificare, va astepta pana se elibereaza si apoi va bloca la randul lui "mutex-ul". Este ca becul de la baie fara un zavor, poate functiona ok daca toti oamenii sunt suficient de atenti :)
Ar mai fi de spus ca lock-urile se fac folosind primitive speciale ale bibliotecilor, nu se pot implementa cu simple variabile.
Problema este ca a pune un lock face doua operatii : 1) Verific ca lock-ul nu este pus de altcineva; 2) Pun lock-ul (actualizez valoarea variabilei mutex).
Daca lock-ul este liber la inceput, dar intre cele doua operatii alt thread verifica si el lock-ul, ambele threaduri vor crede ca resursa este ne-blocata si ambele vor pune lock-ul pe resursa, ajungand sa opereze ambele in paralel.
Primitivele de lock se bazeaza pe operatii atomice gen "test & set", care garanteaza ca o alta verificare nu se poate face in mijlocul acestei operatii de pe alt thread (eventual alt procesor).
De fapt o operatie de lock este destul de complexa la nivelul hardware. Procesorul care o executa trebuie sa blocheze accesul tuturor celorlalte procesoare la acea locatie de memorie (de exemplu blocheaza tot bus-ul spre memorie). Apoi informatia din cache-ul celorlalte procesoare trebuie actualizata cu noua valoare. Pe acea mica perioada de timp practic procesoarele nu pot lucra in paralel, limitand paralelismul.
Legat de limitarea paralelismului trebuie notat ca lock-urile blocheaza executia celorlalte threaduri care doresc sa foloseasca zona de date protejata de un lock. De aceea este recomandabil ca aceste sectiuni "critice" sa fie facute cat mai mici posibil, pentru ca celelalte threaduri sa fie deblocate cat mai repede.
In final as mai aminti de asteptarea "optimista" a eliberarii unui lock (spin-lock). Pornind de la ipoteza ca o sectiune protejata de un lock se termina foarte rapid, exista strategia de a verifica in bucla varibila mutex pana se elibereaza si poate fi pusa pe "lock" de catre noul thread. Aceasta asteptare "activa" consuma ceva procesor. In mod normal, dupa o vreme threadul trece la o verificare mai putin agresiva. Oricum, este inca un argument pentru a face sectiunile critice cat mai scurte cu putinta - dar nu mai scurte ;)
S1 rafinat
Atunci cand se modifica date mai complexe, pentru a nu avea sectiuni critice prea mari, se poate utiliza o tehnica speciala.
Fiecare thread care modifica o entitate complexa, creeaza o copie locala a acelor date, pe care o modifica si o "publica" celorlalte threaduri abia dupa ce modificarea este completa.
In momentul in care datele au fost modificate complet, threadul care modifica deschide o sectiune critica (lock) si schimba referinta/pointerul de la versiunea veche la versiunea noua.
Cat timp datele sunt in modificare (inconsistente), nu vor fi citite de catre alt thread. In acest timp, threadurile vor "vedea" versiunea veche a datelor, fara a fi blocate. De obicei acest lucru este acceptabil, cel putin cand avem un singur thread care modifica datele si mai multe care le citesc.
Copierea datelor nu trebuie sa fie completa. Daca se construiesc structurile mari de date (arbori, hash-uri) din structuri mici imutabile (ne-modificabile) se poate crea noua structura folosind nodurile vechi plus cateva noduri modificate. Este important ca semantica limbajului sa poata garanta ca aceste structuri nu pot fi modificate/distruse cat timp ele sunt folosite de macar un thread.
O versiunea mai elaborata poate sincroniza citirea/scrierea mai multor threaduri asupra acelorasi date, astfel incat ele sa nu faca modificari pe baza unor informatii vechi.
De exemplu daca mai multe threaduri adauga comenzi intr-o coada comuna, este important nu numai ca coada sa ramana coerenta, dar si sa nu se piarda vreo comanda. Daca fiecare thread copiaza versiunea curenta, incepe sa o modifice local si apoi inlocuieste versiunea comuna, apare riscul de a suprascrie o adaugare facuta de alt thread in acel timp.
O solutie care nu blocheaza threadurile prea mult este ca "referinta" sa contina de fapt o ierarhie de stari/versiuni consistente si sa controleze accesul concurent la acele versiuni ("managed refferences").
Este vorba de ceva similar cu un sistem de versionare software (SCM), precum CVS. Fiecare thread poata porni ("checkout") de la ultima versiune completa a acelor date, sa o modifice local si sa publice ("commit") datele modificate.
Daca apare un conflict de "merge" cu datele comise intre timp, atunci tranzactia va da eroare la cel care a "commis" al doilea. Acelasi sistem se foloseste in sistemele tranzactionale de baze de date (exemplu Oracle).
Combinata cu tehnici diferite de checkout, eventual retry se poate asigura un sistem coerent de gestionare concurenta a datelor cu minim de inter-blocare a threadurilor. Intrucat se poate gresi foarte usor la gestionarea lock-urilor, este recomandabil sa se folosesca un sistem unic de acces concurent la date, de exemplu "managed refferences". Este mai probabil sa implementezi bine un sistem unic de lock-ing decat 100 de sisteme distribuite prin tot codul.
va urma
Bonus un link la o prezentare video foarte interesanta (in engleza). Este vorba de un tip de abordare inovativa legata de asigurarea consistentei in programarea multi-threading, utilizand structuri imutabile. Conceptele prezentate mi s-au parut o reala inspiratie pentru programarea multi-threading in general, indiferent de limbaj. Prezentarea este exemplificata pe limbajul Clojure, o implementare Lisp peste masina virtuala Java : http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey
Ce sunt theadurile (pentru foarte incepatori)
O aplicatie se executa de obicei intr-un singur process (exemplu programul Word cand il gasiti in "Task Manager"). Procesul poate contine insa mai multe fire de executie, numite threaduri. De exemplu in timpul in care se editeaza documentul, un thread separat parcurge ciclic documentul si semnaleaza erorile de tastare. Threadurile sunt ca niste procese care folosesc in comun aceeasi memorie si care sunt distruse impreuna cand se distruge procesul.
De ce programare multi-threading ?
1. Aplicatiile multi-threading pot fi distribuite pe mai multe procesoare/cores. O aplicatie single-threaded functioneaza la aceeasi viteza indiferent daca serverul are 1 procesor sau 4 procesoare (presupunem procesoarele identice). O aplicatie care imparte treaba egal pe 4 threaduri poate rula pana la de 4 ori mai repede pe un procesor modern "multicore" cu 4 cores.
2. Chiar daca exista doar un singur procesor, unele operatii au un fir logic separat si este mai usor sa fie descrise ca threaduri (fire de executie) diferite. De exemplu un browser poate descarca (download) un fisier mare si in acelasi timp sa afiseze o pagina. Teoretic asta s-ar putea face si intr-un singur thread, dar in acest caz ar trebui ca bucata de program care afiseaza pagina sa traga cu ochiul din cand in cand si sa mai lucreze si la download. Situatia se complica cand exista mai multe actiuni care trebuiesc multiplexate. Este mai simplu ca fiecare actiune sa fie programata ca executandu-se in paralel (pe un thread) si aproape fara legatura cu celelalte.
3. Spre deosebire de doua procese diferite, comunicarea intre doua threaduri este mult mai simpla si economica din punct de vedere al comunicatiei. Doua procese pot comunica copiind datele si trecand prin kernel-ul sistemului de operare. Exista intr-adevar si varianta cu shared-memory, dar nu este simplu de implementat.
Doua threaduri pot folosi in comun aceleasi date fara a fi necesara copierea. Bineinteles, in acest caz trebuie gestionat cu atentie accesul concurent la date, pentru a nu folosi date incomplet modificate de catre alt thread.
Probleme in programarea multithreading
Este dificil sa programezi corect multi-threading. Este foarte complicat sa prevezi toate interactiunile posibile care se pot intampla intre threaduri diferite care actioneaza asupra acelorasi date. As spune chiar ca atunci cand este posibil este recomandata programarea single-thread si separarea operatiilor in procese diferite. Totusi, uneori cea mai buna solutie este un program multi-threading.
Cateva probleme frecvente in utilizarea threadurilor
P1: Utilizarea unor informatii incomplete (corupte)
Pe procesoarele obisnuite, operatiile mai mari de 32biti (4 bytes) nu sunt de obicei atomice. Asta inseamna ca un alt thread poate accesa datele in mijlocul operatiei care le modifica.
Un exemplu redus la cifre mai mici, ar insemna ca daca un thread (1) modifica o variabila din 32768 (1000000000000000) in 32767(0111111111111111), un alt thread (2) poate gasi operatia efectuata doar pe prima jumatate a numarului si sa citeasca 32512 (0111111100000000).
Aceste "race-conditions" se intampla foarte rar, de aceea sunt foarte greu de descoperit la teste. Totusi, atunci cand se intampla pot face programul sa "crape".
Lucrurile sunt mult mai complexe atunci cand operatiile concurente manipuleaza date mai mari. Atunci creste si probabilitatea ca evenimentul "improbabil" sa apara. Probabilitatea mai creste si cu numarul de "cores" ale sistemului. Ce nu se intampla pe 2 cores, poate deveni destul de probabil pe 4 cores.
S1: Protejarea datelor accesate concurent cu "lock-uri"
"Lock-urile" sunt apeluri prin care se blocheaza accesul la o zona de date (resursa) pana la terminarea modificarii. Accesul este protejat de o structura de date numita "mutex" (de la "mutual exclusive"). Aceasta structura spune daca resursa respectiva este blocata de altcineva (precum un bec aprins la baie).
Totusi, in majoritatea limbajelor de programare, lock-ul nu impiedica efectiv accesul la date. Se presupune ca alt thread utilizator va verifica "mutex-ul" inainte de a incepe o modificare, va astepta pana se elibereaza si apoi va bloca la randul lui "mutex-ul". Este ca becul de la baie fara un zavor, poate functiona ok daca toti oamenii sunt suficient de atenti :)
Ar mai fi de spus ca lock-urile se fac folosind primitive speciale ale bibliotecilor, nu se pot implementa cu simple variabile.
Problema este ca a pune un lock face doua operatii : 1) Verific ca lock-ul nu este pus de altcineva; 2) Pun lock-ul (actualizez valoarea variabilei mutex).
Daca lock-ul este liber la inceput, dar intre cele doua operatii alt thread verifica si el lock-ul, ambele threaduri vor crede ca resursa este ne-blocata si ambele vor pune lock-ul pe resursa, ajungand sa opereze ambele in paralel.
Primitivele de lock se bazeaza pe operatii atomice gen "test & set", care garanteaza ca o alta verificare nu se poate face in mijlocul acestei operatii de pe alt thread (eventual alt procesor).
De fapt o operatie de lock este destul de complexa la nivelul hardware. Procesorul care o executa trebuie sa blocheze accesul tuturor celorlalte procesoare la acea locatie de memorie (de exemplu blocheaza tot bus-ul spre memorie). Apoi informatia din cache-ul celorlalte procesoare trebuie actualizata cu noua valoare. Pe acea mica perioada de timp practic procesoarele nu pot lucra in paralel, limitand paralelismul.
Legat de limitarea paralelismului trebuie notat ca lock-urile blocheaza executia celorlalte threaduri care doresc sa foloseasca zona de date protejata de un lock. De aceea este recomandabil ca aceste sectiuni "critice" sa fie facute cat mai mici posibil, pentru ca celelalte threaduri sa fie deblocate cat mai repede.
In final as mai aminti de asteptarea "optimista" a eliberarii unui lock (spin-lock). Pornind de la ipoteza ca o sectiune protejata de un lock se termina foarte rapid, exista strategia de a verifica in bucla varibila mutex pana se elibereaza si poate fi pusa pe "lock" de catre noul thread. Aceasta asteptare "activa" consuma ceva procesor. In mod normal, dupa o vreme threadul trece la o verificare mai putin agresiva. Oricum, este inca un argument pentru a face sectiunile critice cat mai scurte cu putinta - dar nu mai scurte ;)
S1 rafinat
Atunci cand se modifica date mai complexe, pentru a nu avea sectiuni critice prea mari, se poate utiliza o tehnica speciala.
Fiecare thread care modifica o entitate complexa, creeaza o copie locala a acelor date, pe care o modifica si o "publica" celorlalte threaduri abia dupa ce modificarea este completa.
In momentul in care datele au fost modificate complet, threadul care modifica deschide o sectiune critica (lock) si schimba referinta/pointerul de la versiunea veche la versiunea noua.
Cat timp datele sunt in modificare (inconsistente), nu vor fi citite de catre alt thread. In acest timp, threadurile vor "vedea" versiunea veche a datelor, fara a fi blocate. De obicei acest lucru este acceptabil, cel putin cand avem un singur thread care modifica datele si mai multe care le citesc.
Copierea datelor nu trebuie sa fie completa. Daca se construiesc structurile mari de date (arbori, hash-uri) din structuri mici imutabile (ne-modificabile) se poate crea noua structura folosind nodurile vechi plus cateva noduri modificate. Este important ca semantica limbajului sa poata garanta ca aceste structuri nu pot fi modificate/distruse cat timp ele sunt folosite de macar un thread.
O versiunea mai elaborata poate sincroniza citirea/scrierea mai multor threaduri asupra acelorasi date, astfel incat ele sa nu faca modificari pe baza unor informatii vechi.
De exemplu daca mai multe threaduri adauga comenzi intr-o coada comuna, este important nu numai ca coada sa ramana coerenta, dar si sa nu se piarda vreo comanda. Daca fiecare thread copiaza versiunea curenta, incepe sa o modifice local si apoi inlocuieste versiunea comuna, apare riscul de a suprascrie o adaugare facuta de alt thread in acel timp.
O solutie care nu blocheaza threadurile prea mult este ca "referinta" sa contina de fapt o ierarhie de stari/versiuni consistente si sa controleze accesul concurent la acele versiuni ("managed refferences").
Este vorba de ceva similar cu un sistem de versionare software (SCM), precum CVS. Fiecare thread poata porni ("checkout") de la ultima versiune completa a acelor date, sa o modifice local si sa publice ("commit") datele modificate.
Daca apare un conflict de "merge" cu datele comise intre timp, atunci tranzactia va da eroare la cel care a "commis" al doilea. Acelasi sistem se foloseste in sistemele tranzactionale de baze de date (exemplu Oracle).
Combinata cu tehnici diferite de checkout, eventual retry se poate asigura un sistem coerent de gestionare concurenta a datelor cu minim de inter-blocare a threadurilor. Intrucat se poate gresi foarte usor la gestionarea lock-urilor, este recomandabil sa se folosesca un sistem unic de acces concurent la date, de exemplu "managed refferences". Este mai probabil sa implementezi bine un sistem unic de lock-ing decat 100 de sisteme distribuite prin tot codul.
va urma
Bonus un link la o prezentare video foarte interesanta (in engleza). Este vorba de un tip de abordare inovativa legata de asigurarea consistentei in programarea multi-threading, utilizand structuri imutabile. Conceptele prezentate mi s-au parut o reala inspiratie pentru programarea multi-threading in general, indiferent de limbaj. Prezentarea este exemplificata pe limbajul Clojure, o implementare Lisp peste masina virtuala Java : http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey
Comentarii
Trimiteți un comentariu
Comentarii?