Summary

You were introduced to a sampling of concurrent data structures, from counters to lists and queues, and finally to the ubiquitous and heavily-used hash table. You learned a few important lessons along the way:

• To be careful with the acquisition and release of locks around control flow changes.
• Enabling more concurrency does not necessarily increase performance.
• Performance problems should only be remedied once they exist.

This last point, of avoiding premature optimization, is central to any performance-minded developer; there is no value in making something faster if doing so will not improve the overall performance of the application.

Of course, we have just scratched the surface of high-performance structures. See Moir and Shavit’s excellent survey for more information, as well as links to other sources“Concurrent Data Structures” by Mark Moir and Nir Shavit. In Handbook of Data Structures and Applications (Editors D. Metha and S.Sahni). Chapman and Hall/CRC Press, 2004. Available: www.cs.tau.ac.il/ ̃shanir/concurrent-data-structures.pdf. A short but relatively comprehensive reference on concurrent data structures. Though it is missing some of the latest works in the area (due to its age), it remains an incredibly useful reference.. In particular, you might be interested in other structures (such as B-trees); for this knowledge, a database course is your best bet. You also might be interested in techniques that don’t use traditional locks at all. Such non-blocking data structures are something you’ll get a taste of in the chapter on common concurrency bugs, but frankly, this topic is an entire area of knowledge requiring more study than is possible in this humble course. Find out more on your own if you are interested (as always!).

TIP: AVOID PREMATURE OPTIMIZATION (KNUTH’S LAW)

When building a concurrent data structure, start with the most basic approach, which is to add a single big lock to provide synchronized access. By doing so, you are likely to build a correct lock; if you then find that it suffers from performance problems, you can refine it, thus only making it fast if need be. As Knuth famously stated, “Premature optimization is the root of all evil.”

Many operating systems utilized a single lock when first transitioning to multiprocessors, including Sun OS and Linux. In the latter, this lock even had a name, the big kernel lock (BKL). For many years, this simple approach was a good one, but when multi-CPU systems became the norm, only allowing a single active thread in the kernel at a time became a performance bottleneck. Thus, it was finally time to add the optimization of improved concurrency to these systems. Within Linux, the more straightforward approach was taken: replace one lock with many. Within Sun, a more radical decision was made: build a brand new operating system, known as Solaris, that incorporates concurrency more fundamentally from day one. Read the Linux“Understanding the Linux Kernel (Third Edition)” by Daniel P. Bovet and Marco Cesati. O’Reilly Media, November 2005. The classic book on the Linux kernel. You should read it. and Solaris“Solaris Internals: Core Kernel Architecture” by Jim Mauro and Richard McDougall. Prentice Hall, October 2000. The Solaris book. You should also read this, if you want to learn about something other than Linux. kernel books for more information about these fascinating systems.