Arbori concurenți

Atunci când lucrăm cu structuri mai complexe, trebuie să avem grijă la sincronizarea accesului concurent la ele, dar și la eficiența finală a implementării. Ca să vedem un exemplu concret, vom presupune că avem un arbore binar. Când se dorește inserarea unui element într-un astfel de arbore, se verifică mai întâi dacă nodul unde inserăm are copil în partea stângă. Dacă nu are, atunci nodul copil va fi inserat în stânga, altfel va fi inserat în partea dreaptă:

if (node.left == null)
    node.left = child;
else
    node.right = child;

Când mai multe thread-uri acționează asupra unui arbore binar, pot apărea probleme de concurență la inserare. Un astfel de scenariu ar putea avea loc atunci când două thread-uri încearcă să insereze simultan câte o valoare diferită în același nod din arbore:

T0	T1
Verifică dacă există copil în stânga	Verifică dacă există copil în stânga
Condiția este adevărată, trece în prima ramură a if-ului	Condiția este adevărată, trece în prima ramură a if-ului
Inserează nodul în stânga
	Inserează nodul în stânga → se suprascrie valoarea scrisă de T0

În acest caz, corect ar fi ca unul din thread-uri să insereze în stânga și celălalt să insereze în dreapta. O soluție este să folosim un lock pe operația de inserare unui nod. Dacă folosim un lock global (pentru tot arborele), două thread-uri nu pot insera noduri copii în același timp pentru două noduri părinte diferite. Din acest motiv, mai eficient ar fi să existe câte un lock pentru fiecare nod.