Introduction to Locked Data Structures

This lesson presents a motivation to study locked data structures.

Before moving beyond locks, you’ll first learn how to use locks in some common data structures. Adding locks to a data structure to make it usable by threads makes the structure thread safe. Of course, exactly how such locks are added determines both the correctness and performance of the data structure. And thus, our challenge:

CRUX: HOW TO ADD LOCKS TO DATA STRUCTURES

When given a particular data structure, how should one add locks to it, in order to make it work correctly? Further, how can locks be added such that the data structure yields high performance, enabling many threads to access the structure at once, i.e., concurrently?

Press + to interact

Of course, we will be hard-pressed to cover all data structures or all methods for adding concurrency, as this is a topic that has been studied for years, with (literally) thousands of research papers published about it. Thus, we hope to provide a sufficient introduction to the type of thinking required, and refer you to some good sources of material for further inquiry on your own. We found Moir and Shavit’s survey to be a great source of information“Concurrent Data Structures” by Mark Moir and Nir Shavit. In Handbook of Data Structures and Applications (Editors D. Metha and S.Sahni). Chapman and Hall/CRC Press, 2004. Available: www.cs.tau.ac.il/ ̃shanir/concurrent-data-structures.pdf. A short but relatively comprehensive reference on concurrent data structures. Though it is missing some of the latest works in the area (due to its age), it remains an incredibly useful reference..

Get hands-on with 1400+ tech skills courses.