This chapter covers the various strategies for increasing the concurrency of data structures. We will look at the lock-free variants of stacks and queues. These lock-free versions use compare and swap (CAS) instead of explicit synchronization. This is a complex programming model, and as we will soon see, it requires extreme caution and deep analysis to make sure there are no subtle concurrency bugs, such as the ABA problem. The ABA problem is also described in this chapter, along with a strategy that can be used to deal with it effectively.
This chapter will also cover commonly used data structures, such as the following:
- Concurrent stacks
- Queues
- Hash tables
Finally, we will have a look athashtables, which are used to efficiently implement a setabstraction. A set holds unique elements and needs to cater for a fast lookup operation, whether a value is present in the set or not. First, we will look at the solution for this using explicit locking and thelock...