Multithreading: synchronization

Today we’re going to start talking about an interesting and complex topic: synchronization. As we’ve seen in previous posts, and even though we should strive for having immutable objects, the truth is that shared state will always exist and this means that we need to synchronize access whenever we have several threads that need to access that state (from previous posts, we’ve seen that the only safe scenario for allowing access to shared state *without* synchronization is when we have several read only operations).

In practice, we can classify synchronization in two sub-areas:

  • data: this is probably the most used approach, where we need to ensure that only one thread accesses data at each time.
  • control: this approach is used when one thread depends on the other having executed some piece of code (think in publish/subscriber scenarios, where the subscriber waits for the data that is published by the publisher).

Obviously, you can mix both approaches in the same application.

The solution for controlling data access (data synchronization) relies on serializing access to shared state. This is achieved by creating *critical regions* that ensure mutual exclusion for a specific region of code. In practice, a critical region delimits several instructions which are executed  by a specific thread in a serialized fashion (ie, the critical region ensures that a second thread will only enter the region and execute the instructions delimited by it when the first thread has already executed them and left the critical region).

Currently, there are several mechanisms that we can use in order to get a critical region. For instance, many of us have already used Monitors for serializing access to a specific region of code (we’ll come back to this topic in future posts,when we start looking at some code that exemplifies the usage of this feature).

The usage pattern for a critical region is simple: a thread enters a critical region,executes several instructions and then leaves the critical region (assuming, of course, that we don’t have any exceptions and that the thread isn’t aborted). When another thread tries to enter that region, it will only succeed if the first thread has exited that region. If that hasn’t happened yet, then it will block and wait for the first thread to exit the region. In other words, critical regions normally have a scope!

There are several algorithms that can be used for supporting critical regions. Nowadays, most algorithms are built on a mixture of OS waiting support and the hardware atomic CAS (compare and swap).

Control synchronization is appropriate for scenarios where you need to ensure collaboration between several parties (and lets face it, this is needed in several cases). In this case, we’ll have an intervenient which needs to wait while some condition isn’t true. There are several approaches that can be followed for implementing the waiting part:

  • busy waiting:  this means that you’ll have an infinite cycle which will run until a specific condition is true. This might be a good approach for those cases where the thread can do some useful work while it waits for that condition. On the other hand, it’s not a good approach to follow when the thread is just there, spinning, without doing anything useful;
  • real wait: in this case, the OS kernel puts the thread in a real waiting state (this means that the thread won’t be consuming processor time, but we’ll have other costs related to thread switching);
  • continuation passing: this relies in passing a closure for being executed when another specific action ends. This might be a good option for those cases where waiting is too expensive. In this scenario, shared state is encapsulated in messages which are “passed” between threads.

And I guess that this a lot for one post. We’ll come back to this topic with some code samples.

~ by Luis Abreu on May 11, 2009.

One Response to “Multithreading: synchronization”

  1. Hi,

    It is very nice to found this. It is a perfect forum

    sexy ass

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: