Programare concurenta

Radu Grigore
13 martie 2012

Olimpiadele ar trebui să aibă probleme de programare concurentă. Argumentul pe scurt este următorul. Programatorii trebuie să utilizeze primitive simple pentru a micşora numărul defectelor software. Primitivele oferite de hard nu sunt simple, pentru a fi eficiente. Puntea dintre ce oferă hardul şi ce văd programatorii este în biblioteci şi în compilatore. Ideea este că numai un număr mic de programatori, cei foarte buni, trebuie să scrie codul complicat. Şi ghici unde se pregătesc viitorii super-programatori. :)

Dar s-o luăm pe-ndelete.

Programarea concurentă este importantă. Timp de ~30 de ani, cumpărarea un procesor nou garanta că programele vor merge mai repede. Însă în 2003 frecvenţa procesoarelor a încetat să crească. Acum cumperi un procesor nou pentru nişte core-uri în plus. Programele care folosesc un singur core vor merge la fel de repede; doar că vei putea rula mai multe în paralel. Pentru mai multe detalii vă recomand eseul „The Free Lunch is Over” al lui Herb Sutter.

Este încă relativ neplăcut să scrii programe concurente, dar lucrurile evoluează rapid înspre bine.

Iată câteva exemple de primitive concurente de nivel înalt care câştigă teren: memorie tranzacţională, futures, MapReduce. Toate trei merită învăţate. Alternativa, să foloseşti chestii de genul „synchronized” în Java sau pthreads în C, e ca şi când ai programa în limbaj de asamblare deşi a apărut deja Pascal. În mare, scopul primitivelor concurente de nivel înalt este să permită programatorilor să pretindă că anumite bucăţi de cod se execută secvenţial, fără interferenţe.

Implementarea acestor primitive este dificilă. De exemplu, futures sunt implementate în biblioteca „java.util.concurrent”, dar semantica firelor de execuţie în Java nu e clară. Pentru o vreme programatorii se aşteptau ca o execuţie pe câteva core-uri să fie echivalentă cu o intercalare a instrucţiunilor pe un singur core. Erau apoi surprinşi cum un program „concurent” care mergea perfect pe un core brusc începea să aibă defecte când era rulat pe mai multe core-uri. Motivul este că maşina virtuală şi compilatoarele fac tot felul de optimizări în cadrul fiecărui fir, ca şi când ar fi un program secvenţial. OK, dar dacă nu te poţi gândi la un program concurent ca şi când firele de execuţie pot fi intercalate, atunci cum? Evident, nu vrei să iei în considerare toate posibilele optimizări. Trebuie să există o altă descriere concisă a ceea ce e permis şi ceea ce nu e permis. Într-adevăr există: e o teză de doctorat ... în care au fost găsite probleme, care au fost corectate, apoi au fost găsite alte probleme şi tot aşa.

În concluzie, am văzut două motive pentru care ar fi bine ca olimpiadele să aibă probleme de programare concurentă. Pe de o parte participanţii vor fi mai pregătiţi pentru cum se va programa în viitor. Pe de altă parte există probleme de dificultate ridicată.

Totuşi, sunt multe întrebări la care habar nu am care e răspunsul. Putem proiecta probleme a căror soluţie să fie verificată automat? E bine să fie verificate automat ca la informatică sau ar fi mai bine pe hârtie ca la matematică? Nu cumva problemele interesante sunt prea grele şi nu se pot rezolva în timp util? Putem să inventăm probleme suficient de variate cât să fie interesante?