Basic Synchronization Principles

This article discusses approaches and issues involved with managing concurrency. The objective is to be able to do multiple things at the same time (i.e. using multiple threads), while avoiding coordination problems.

Three Concurrency Problems to Address

Synchronization

Synchronization, a.k.a. serialization, is making tasks run in a serial sequence (one at a time) instead of all at once, because of dependencies between the tasks. An example of this is that when building a house the person building basement needs to tell person building ground floor when the basement is done, so that work on the ground floor can start.

In a more complex case, it may be that parts of the ground floor are only dependent on parts of the basement, so the person building the ground floor may be able to begin work sooner. This more complex case is related to the Producer-Consumer pattern discussed below.

Mutual Exclusion

Mutual exclusion is controlling access to shared resources. Continuing with the construction example, only one person can use the same drill at the same time, or things get ugly. Likewise, things like a disk or a data structure often require a limit of one thread accessing it at a time to ensure the desired effect.

Data Sharing

Data sharing, which is closely related to mutual exclusion, is managing the duplication of data structures or devices. These duplicated resources would in turn send updates to a manager of sorts, and would be informed of updates by the manager.

An example of this is what Massively-Multiplayer Online (MMO) games do to avoid certain problems associated with network lag (the delay between sending a notification of action to the server and receiving the result of that action). If this was done with all world data processing done on the server, a player wouldn't know whether or not an opponent had been defeated until the network responds with the result. With data sharing, the client program can immediately determine, based on its copy of the local environment, that it is likely that the opponent has been defeated, and then receive either confirmation or rejection of that assumption when the server responds with its "official version" of events.

Message Passing is this way of managing duplication of state via coordinated communication between copies. Shared Memory is a way to simulate duplication of state in a way that in some circumstances, can allow concurrent access, and generally access with less overhead than message passing.

Tackling Mutual Exclusion

NOTE: I'll add the rest of the notes tomorrow.