Lock-based Concurrent Data Structures

Beforemoving beyond locks, we’ll first describe how to use locks in some common data structures. Adding locks to a data structure to make it us-able 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 we add locks to it, in order to make it work correctly? Further, how do we add locks such that the data structure yields high performance, enabling many threads to access the structure at once, i.e., concurrently? 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 think-ing 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 [MS04]. 29.1 Concurrent Counters One of the simplest data structures is a counter. It is a structure that is commonly used and has a simple interface. We define a simple non-concurrent counter in Figure 29.1. Simple But Not Scalable As you can see, the non-synchronized counter is a trivial data structure, requiring a tiny amount of code to implement. We now have our next challenge: how can we make this code thread safe? Figure 29.2 shows how we do so. 1 2 LOCK-BASED CONCURRENT DATA STRUCTURES 1 typedef struct __counter_t