In this chapter, we will analyze the detailed process of designing and implementing two common types of data structure in concurrent programming: lock-based and mutex-free. The principal differences between the two data structures, as well as their respective usages in concurrent programming, will be discussed. Throughout the chapter, an analysis of the trade-off between the accuracy and speed of concurrent programs is also supplied. Through this analysis, readers will be able to apply the same trade-off analysis for their own concurrent applications.

The following topics will be covered in this chapter:

• Common problems with lock-based data structures, and how to address them
• A detailed analysis of how to implement a lock-based data structure
• The idea behind mutex-free data structures, along with their advantages and disadvantages, as compared to lock-based data structures
• A detailed analysis of how to implement a mutex-free data structure