Further reading

  • Axioms for Concurrent Objects, Maurice Herlihy and Jeannette Wing. This paper by Herlihy and Wing introduced the formal definition of linearizability and the formal analysis framework. Subsequent work has expanded or simplified on this paper, but the reader is warmly encouraged to digest the first half of the paper, at least.
  • Distributed Algorithms, Nancy Lynch. To my knowledge, Lynch's work was the first general overview of distributed algorithms in textbook form. It is incredibly accessible and Chapter 13 of Lynch's book is especially relevant to this discussion.
  • In C++, are acquire-release memory order semantics transitive?, available at https://softwareengineering.stackexchange.com/questions/253537/in-c-are-acquire-release-memory-order-semantics-transitive. The consequences of memory orderings are not always clear. This question on StackExchange, which influenced the writing of this chapter, is about the consequence of splitting Acquire and Release across threads. The reader is encouraged to ponder the question before reading the answer.
  • std::memory_order, CppReference, available at http://en.cppreference.com/w/cpp/atomic/memory_order. Rust's memory model is LLVM's, which is, in turn, influenced by the C++ memory model. This discussion of memory ordering is particularly excellent, as it has example code and a less language-lawyer approach to explaining orders.
  • Peterson's lock with C++0x atomics, available at https://www.justsoftwaresolutions.co.uk/threading/petersons_lock_with_C++0x_atomics.html. This post discusses Bartosz Milewski's implementation of Peterson's algorithm for Mutex, demonstrates how and why it is incorrect, and describes a functional alternative. Milewski is a well-known C++ expert. It just goes to show, atomic programming is difficult and easy to get subtly wrong.
  • Algorithms for Mutual Exclusion, Michael Raynal. This book by Raynal was written in 1986, well before the x86_64 architecture we've discussed was introduced and a mere year after ARMv1 was introduced. Raynal's book remains useful, both as a historical overview of mutual exclusion algorithms and for environments where synchronization primitives are not available, such as on file systems.
  • Review of many Mutex implementations, available at http://cbloomrants.blogspot.com/2011/07/07-15-11-review-of-many-mutex.html. As it says on the tin, this post is a review of many mutex implementations that are given a more modern context than Raynal's book. Some explanations rely on Microsoft Windows features, which may be welcome to the reader as this book is heavily invested in a Unix-like environment.
  • Encheapening Cernan Metrics, available at http://blog.troutwine.us/2017/08/31/encheapening-cernan-internal-metrics/. In this chapter we have discussed atomics largely in terms of synchronization. There are many other use cases. This post discusses the application of atomics to providing cheap self-telemetry to a complicated software project.
  • Roll Your Own Lightweight Mutex, available at http://preshing.com/20120226/roll-your-own-lightweight-mutex/. Preshing On Programming has a run of excellent atomics material, focused on C++ and Microsoft environments. This particular post is to do with implementing mutexes—a topic dear to this chapter—and has an excellent follow-up conversation in the comments. The post discusses a variant of semaphores called benaphores.
  • Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms, Maged Michael and Michael Scott. This paper introduces the Michael and Scott Queue, discussed in this chapter, and that's what it's best known for. You may also recognize their queue with two locks from the previous chapter, adapted through the Erlang VM, of course.
  • Lock-Free Data Structures. The Evolution of a Stack, available at https://kukuruku.co/post/lock-free-data-structures-the-evolution-of-a-stack/. This post discusses the libcds implementation of Trieber stacks, as well as making reference to other areas of the literature. Readers will note that previous Further reading have introduced some of the same literature; it's always good to seek alternate takes. Readers are especially encouraged to investigate the Hendler, Shavit, and Yerushalmi paper referenced in the post.
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.223.239.226