infoarena

http://infoarena.ro/blog/programare-concurenta

Si mie mi se pare o idee buna. Din experienta mea, programarea concurenta e una din cele mai grele probleme. Chiar si fara sa iei in calcul optimizarile facute pe fiecare thread, sa scrii un program care functioneaza pe mai multe threaduri fara interferente e un lucru greu. Nu pare greu la prima vedere, insa cea mai mica greseala poate fi fatala, in mare parte din cauza ca aceste erori sunt foarte greu de detectat, si cu atat mai greu de reprodus. Daca faci unlock la un segment de memorie cu o instructiune prea devreme, acest bug poate sa iti treaca toate testele de sistem pe care le ai tu in place, inclusiv si daca testezi o sa ti se para ca merge bine. E posibil ca eroarea respectiva sa apara abia dupa vreo 2 luni, si va fi foarte greu sa o reproduci si sa iti dai seama ce s-a intamplat.

Când am scris primele soluÈ›ii concurente È™i rulat la o scară foarte mare, am înÈ›eles cum mintea mea era setată pe rezolvarea de probleme secvenÈ›iale. Și-i interesant să vezi lucrurile concurent / paralel, e o cu totul altă perspectivă.  Și cred că e multă lume de acord că-i bine să ai perspective diferite asupra unei probleme. Poate chiar È™i asupra vieÈ›ii. :)

Ce problema rezolvai Marius?

E foarte buna observatia ca bug-urile in programe concurente sunt greu de reprodus. De exemplu, o colega (http://www.cs.ox.ac.uk/people/jade.alglave/) a descoperit un bug in (o serie de) PowerPC care se manifesta de 2-3 ori daca rulezi un test de 100000 de ori!


Cu lock/unlock exista doua probleme principale, cel putin la nivel teoretic:
1. Nu sunt compozitionale.
2. E relativ usor sa obtii un deadlock.

In practica deadlockurile sunt probabil problema mai mica, pentru ca tinzi sa le observi repede si sa le repari.

Ce inseamna ca nu sunt compozitionale? In general un lock se presupune ca protejeaza o resursa partajata, cum ar fi o zona de memorie. Toate bucatile de cod care folosec resursa respectiva trebuie sa respecte o disciplina globala de lock/unlock. Daca o bucata de cod nu respecta disciplina, atunci este perfect posibil ca problema sa se manifeste ca si cand alta bucata de cod se comporta incorect. Asta binenteles ca face gasirea bug-urilor dificila.

Memoria tranzactionala poate fi privita ca o incercare de rezolvare a acestor doua probleme.

@Cosmin  A trebuit să creez un sistem ce are un pool de cozi ce funcÈ›ionează pe principiul unui deque (elementele intră prin față, dar ies prin spate după o perioadă de timp), dar fiindcă ordinea celor care intrau nu era tocmai perfect, a trebuit să fie un pool de cozi de priorități. O mulÈ›ime de workeri scriau milioane de date pe oră în aceste cozi È™i a trebuit să am grijă să fie distribuite bine, să mai pice (cât de rar se poate) câte-o operaÈ›ie, dar să iasă cât de bine per total. A fost un tradeoff care a mers. Și-i fun, fiindcă, în realitate, tradeoffurile sunt regula È™i nu soluÈ›iile perfecte.

@Radu, @Tibi  Sunt mai greu, ce-i drept, de investigat, dar costul lor e mic. Cred... :)

Nu stiu sigur ce vrei sa spui, dar imi inchipui ca ar putea fi una din urmatoarele variante: :)

1. Defectele greu de reprodus sunt si greu de produs. Adica utilizatorii nu vor fii afectati prea des.

2. De obicei exista mecanisme de auto-corectie pentru ca stii ca lucrurile vor merge prost. Dar uneori nici mecanismele de auto-corectie nu merg bine si atunci se pot intampla chestii destul de costisitoare. Uite de exemplu o analiza recenta a unui astfel de eveniment (http://blog.scalyr.com/2012/03/13/the-azure-outage-time-is-a-spof-leap-day-doubly-so/). (Autorul e Steve Newman: a pornit Google Docs, a contribuit la Megastore, are ~3000 la topcoder...)

Am înțeles, Radu. Eu mă gândeam la prima variantă. Iar simplitatea aparentă a problemelor de programare concurentă ce duce la problemele descrise mai sus, mă determină să fiu de acord că olimpiada ar trebui să aibă acest tip de probleme.

@Marius: Nu neaparat. Poti avea o eroare de concurenta care sa iti genereze o incosistenta in baza de date care sa se propage like crazy si pana sa o prinzi sa iti corupa toata baza de date.