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 at hash tables, which are used to efficiently implement a set abstraction. A set holds unique elements and needs to cater for...
