Lecture Log

Lecture 11: Cautionary Tales in Concurrency

Title slideThis lecture concludes the set on concurrency with three distinctive challenges for concurrent programming and some possible solutions: lock networks, deadlock, and hand-over-hand locking; priority inversion in thread scheduling; and relaxed memory models for modern processor architectures.

There was also some discussion of differences between the mailbox communication style in Erlang and channel-based communication in the Go language; a couple of applications of Erlang; and the LongAdder class of Java 8.

Links: Slides for Lecture 11; Recording (screen and audio)

Homework

Find out the meaning of the following words, in the context of CPU architecture and execution.

  • Pipelining
  • Pipeline hazard
  • Superscalar
  • Out-of-order execution
  • Speculative execution
  • Branch prediction

These are particularly relevant to the concurrency challenges presented by modern processor architectures and memory models, such as those described in the later portion of the lecture.

References

  • Priority Inversions on Mars. Recent blog post explaining the concurrency issues with Pathfinder. Written by Michelle Bergeron, a CS graduate working at Microsoft on USB-C.

  • What Really Happened on Mars? Collection by Mike Jones of accounts of the priority inversion problem on software in the Mars Pathfinder lander. He’s also at Microsoft, working on digital identity and authentication.

  • Authoritative Account. What really, really happened on Mars. Technical details and full explanation by Glenn Reeves, leader of the Mars Pathfinder software team at NASA JPL.

  • Mars Pathfinder. NASA overview of the mission, the Pathfinder lander and Sojourner robot rover.

Mars Pathfinder landing arrangements Mars Pathfinder on Earth Mars Pathfinder on Mars

Those references I think fairly readable and entertaining. The next few, by contrast, are interesting but quite hard work and only there for when you really are keen to know just what’s going on with concurrent memory models. If you have a preferred tutorial or explanation on this, please let me know and I’ll add a link.