Wednesday, October 8, 2014

Software Transactional Memory: Dining Philosophers

Software transactional memory (STM) is a concurrency alternative to lock-based synchronization. It is similar to database transactions except instead of modifying database records, you are modifying variables in shared memory. STM transactions are atomic (a transaction is all or nothing), consistent (all changes made from a transaction must preserve invariants), and isolated (concurrent transactions result in the same system state as transactions executed serially). Since they are in-memory they are not durable.

With STM you are separating identity from state with persistent data structures. While state is constantly changing, the current state for an identity is immutable. Changes made by one thread will not affect another with a reference to the same data structure.1

Without locks multiple threads can also modify different parts of a data structure that would normally share the same lock. Optimistic concurrency control assumes multiple transactions can run in parallel and if wrong, they will be retried.2

Example Code

Motivated by the book Seven Concurrency Models In Seven Weeks, I have implemented the dining philosophers problem in Scala. The book uses Clojure, but ScalaSTM is inspired by the STMs in Haskell and Clojure and I am trying to get better with Scala, so this seemed like a good way to reinforce what I was reading. It turns out that a dining philosophers solution is in the ScalaSTM documentation, but nonetheless it was a worthwhile exercise.

Conclusion

Atomic variables are enough for a lot of problems and functional programming discourages mutable data anyway, but if it is simpler to use multiple mutable variables then STM might be the way to go. As always, you need to compare performance of both though.

1 http://clojure.org/state
2 https://nbronson.github.io/scala-stm/intro.html