Concurrent data structures
Locking is a fundamental mechanism to ensure mutually exclusive concurrent access to
a single item of information. But when one considers data structures that maintain a
set of related data items, it is highly inefficient to consider the data structure
as one entity and use a single lock to regulate access. The locking has to be more
fine grained, and interesting issues and trade-offs need to be considered. In this
talk we illustrate these issues with two examples: linked lists and stacks.