- The Building Blocks
- Multiword Operations
- Lockless Message-Passing
- Hybrid Structures
- Pointers and Deletion
- Other Approaches
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Pointers and Deletion
In a structure like a linked list or an unbalanced tree, it's very easy to handle insertion in a way that can be performed concurrently with search, without the need for any synchronization. When you insert a node, you first set its next pointer to the node that you expect to follow it; then you use a compare-and-exchange instruction to set the preceding node's next pointer to your new node. If that fails, then you try again with the next new node value.
Removing a node is much harder. If you allow access to the list without any kind of synchronization, you have no way of telling whether it's safe to delete a node. One relatively simple approach is to have a traversal count on the list, which you increment whenever a bit of code starts manipulating the list, and then decrement when it finishes. Rather than deleting items from the list, you make the next pointer in the previous node skip over it and add it to another list.
At some point when the traversal count is 0 and the second list is not null, you collect all of the garbage. You can use the technique described in the preceding section to trigger the collection.
Of course, this trick adds a little overhead to every traversal. In a lot of cases, you may find it preferable simply to leak deleted objects. The leak can be temporary. You can delete everything when you delete the list itself, because you know that no one should hold any pointers to it by that point.
Another alternative is to use a fuzzy barrier. A traditional barrier is a place in the code where all threads block until the other threads are in the same place. A fuzzy barrier simply tracks whether all threads have passed that point. You could implement this approach by having each thread increment as a separate counter when it completed a traversal. Periodically, another thread would copy all of these counters and acquire the garbage list. When every counter had been incremented at least once, the garbage list could be freed, and the collector thread could copy the barrier counts and the garbage list again.
Alternatively, you might use hazard pointers. For a linked list, each traversing thread has two pointers at most: a current pointer and a next pointer. While traversing, it could store these two pointers in a well-known location. After removing a node from the list, a thread would just have to check whether the previous node or the deleted node address is stored in the hazard pointer list. If not, then it's safe to delete.