General Considerations
Implementing thread-safe data structures is special. Before I dive into each of these special concerns, here is a concise overview including the answers you have to give.
- Locking Strategy: Should the data structure support coarse-grained or fine-grained locking? Coarse-grained locking might be easier to implement but introduces contention.
- The Granularity of the Interface: The bigger the interface of the thread-safe data structure, the more difficult becomes it to reason about the concurrent usage of the data structure.
- Typical Usage Pattern: When readers use your data structure mainly, you should not optimise for writers.
- Avoidance of Loopholes: Don’t pass internals of your data structure to clients.
- Contention: Do concurrent client requests seldom or often use your data structure?
- Scalability: How is the performance characteristic of your data structure when the number of concurrent clients increases or the data structure is bounded...