March 2017

One of the biggest qualitative improvements in concurrency took more than 15 years to catch on. [1] That is lock-free processing: the ability to read, write, update, or delete values in a data structure without acquiring a lock.

Say two threads both want to access the data structure; one to insert, the other to delete. One thread has to block the other to avoid corrupting the data structure. But since taking a write lock blocks all of the threads out instead of just one, it slows down programs that have many threads.

Lock-free processing protects from this condition without a lock. If one thread wants to insert and the other to delete, the conflict is detected while it happens, and one of the two threads restarts. Because conflicts happen rarely, restarts are rare.

That's the key idea. The details are more complex.

There is a limitation to lock-free processing though. It protects only the data structure from concurrency, not the data inside each element of the data structure. If a thread safely gets a pointer to a data element, and another thread frees the memory of the data element, the first thread will access invalid memory. The first thread has no way of knowing another thread freed the memory.

Nothing about lock-free processing protects from this. Marking deleted elements to defer their removal from the data structure doesn't make the lock-free data structure aware of another thread holding a pointer to one of its elements indefinitely.

Removal from the data structure, and removal from the heap, are two separate types of removal.

The solution is a form of garbage collection. The lock-free data structure can store a field in each element that helps with garbage collection. But the lock-free data structure alone can't fix this problem. The program has to cooperate.


[1]  The idea was first published in 1988. Some practical implementations begun to surface within 10 years but it took roughly 20 years for the field to get hot.