The previous subsection concluded our discussion of designing a lock-based concurrent data structure in Python, and the complexities involved therein. We will now move on to one approach to the theoretical design of mutex-free concurrent data structures.
The term mutex-free in concurrent data structures indicates the lack of a locking mechanism to protect the integrity of the data structure. This does not mean that the data structure simply disregards the protection of its data; instead, the data structure has to employ other synchronization mechanisms. In this section, we will analyze one such mechanism, known as read-copy-update, and discuss how to apply it to a Python data structure.