Yesterday's news

Another summary of my notes and thoughts as I read another book, this time Concurent Programming on Windows by Joe Duffy.

Basics (mostly NOT from the book):

• My favorite analogy for noobs: code is the path, while thread is the train that rides the path, hence multiple trains riding same path. As threads execute code, they might have access to same variables/fields/objects which thus becomes “shared memory”.
• We think of some operations as atomic while in reality they are not. Famous example is x++ where x is a shared variable. The ++ is compiled into several operations: getting value, incrementing, putting result back. Depending on exact timing of multiple threads doing this for the same variable some of the increments may get lost.
• Invariant is a logical relationship between several objects that must always hold true. For example one variable stores collection elements and the other collection length. From the perspective of external observer the two should never go out of sync, even though updating them (e.g. when new element is added) is not a single atomic operation.
• In order to create illusion of atomicity and preserve the invariants we use locks.
• Conceptually, basic lock consists of a boolean field and two methods: Acquire and Release.
• Conceptually, Acquire works like this: if lock is False, set it to True and return; if lock is True, wait until it becomes False, either indefinitely or until timeout is expired (if supported) by particular implementation. Release simply resets the state back to False.
• C#’s lock statement works the same way but uses special hidden field of the object that you supply to hold the state of the lock.
• The way lock is used to preserve the invariant is by making each thread acquire the lock before looking at or changing the shared piece of memory, and holding it until its done. This way nobody else can see the memory in intermediate state (while the invariant is broken) or screw its content such as in the x++ example.
• In basic scenarios, all the threads that need to be serialized using the locking technique execute same exact piece of code. Thus the region of code between Acquire and Release is traditionaly called Critical Region. This term shifts focus from the invariant to the piece of code protecting the invariant. In more complex scenarios different pieces of code may use the same lock to serialize access to a shared piece of memory.
• There are many kinds of synchronization primitives: locks, semaphors, monitors, mutexes etc. They differ in details but idea is basically the same: only limited number of people may enter the club, others must wait until somebody exits. BTW same techniques are used in the databases to guarantee ACID properties.
• While lock (aka binary semaphor) allows one person into the club, generic semaphor supports multiple threads holding the lock, thereby encapsulating access to a shared-but-limited resource.
• Another form of lock is a read/write lock, when thread specifies its intent (reading or writing). Such a lock allows multiple reader threads having shared access to the same resource. If thread wants to get a writing lock, it must wait until all readers are out. Once the writing lock is granted, no other readers or writers can get in until it’s free again. The idea is to improve throughput by decreasing contention.

More substantial info (from the book or inspired by the book):

• At CPU level, most kinds of locks (as well as Interlocked.Increment kinds of operations) are eventually compiled into an atomic Compare-And-Swap CPU instruction.
• Design-wise, shared memory + synchronization is just one way of organizing data exchange between agents. The other way is non-shared memory + messaging.
• Conceptually, there are four reasons for synchronization:
  1. to create illusion of atomicity
  2. to preserve invariants
  3. to orchestrate mutilple tasks running in parallel, for example to wait until all worker threads are done processing their chunks and
  4. to restrict simultaneous access to a shared but limited resource
• In the book, reasons 1 and 2 are called Data Synchronization while reason 3 is called Control Synchronization
• While for Data Syncrhronization we use locks, for Control Synchronization we use events (such as ManualResetEvent, AutoResetEvent etc.)
• The nice thing about events, you can wait for any of many or all of many.

All of the above seems pretty obvious so far, but even though I knew all this before, reading the book and writing the notes has helped me to organize the separate facts into a cohesive mental framework. Hope it was helpful for you too.

Enough for now. This has been 77 pages out of 900+ so I’m sure there’s gonna be more interesting stuff to write about.