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?