Operating Systems: Three Easy Pieces Ch. 29
Lock-based Concurrent Data structures
- thread safe
- Adding locks to a data structure to make it usable by threads makes the structure thread-safe
- Monitors
- Where locks are acquired and released automatically as you call and return from object methods
- Approximate counter
- When a thread running on a given core wishes to increment the counter, it increments its local counter; access to this local counter is synchronized via the corresponding local lock.
- accuracy/performance tradeoff is what approximate counters enable
- Concurrent Linked Lists
- hand-over-hand locking
- Concurrent Queues
- Concurrent Hash Table
- Summary
- Chapter 29 introduces concurrent data structures, including counters, lists, queues, and hash tables. Important lessons learned include careful lock handling, the lack of guaranteed performance gains from increased concurrency, and the importance of avoiding premature optimization. Moir and Shavit’s survey is recommended for more information, and B-trees are suggested as another structure to explore. Non-blocking data structures are covered in the chapter on common concurrency bugs, and independent exploration is encouraged for a deeper understanding
- The paragraph suggests starting with a basic approach of adding a single big lock for synchronized access when building a concurrent data structure. This ensures correctness, and if performance issues arise, the lock can be refined to improve speed. It emphasizes the quote by Knuth about avoiding premature optimization. The paragraph also mentions that many operating systems, like Sun OS and Linux, initially used a single lock (referred to as the big kernel lock or BKL) during the transition to multiprocessors. However, as multi-CPU systems became more common, allowing only one active thread at a time became a performance bottleneck. Linux opted for the approach of replacing one lock with many, while Sun took a more radical approach by developing the Solaris operating system that fundamentally incorporated concurrency from the beginning. It recommends reading books on Linux and Solaris kernels for more information about these systems.