Channels ▼
RSS

Parallel

Locks and Holds: The Basics of Synchronization


Sergey is a senior developer for Aleri. He can be contacted at babkin@verizon.net


A great many ways of parallel processes (or threads) synchronization have been invented over time. They are devised with different usage models in mind and with different levels of overhead. Some synchronization primitives are really most basic.

Even before multithreading became popular in the user programs, it was used in the operating system kernels. Quite a few terms and primitives came from there. Many of them pre-date even the multiprocessor systems: even the single-processor kernels had very similar synchronization needs.

Two of the very basic primitives connecting a portion of code to a portion of data are locks and holds. Both are widely used in the OS kernels and often get people confused. Locks, also known as "mutexes," are the simplest, most lightweight, and widely used synchronization mechanism. When a lock is locked (or, in other words, "acquired" or "held"), a thread says "don't anybody touch these data", until it unlocks (or "releases") the lock. Locks are used often, in many interesting ways, and are mentioned in every introductory text on the subject. Still, there are interesting points that aren't always considered.

Let's start with simple things. What lock granularity should be used? How many locks to use? How much data should be protected by each lock? Obviously, if all the data in the program is protected by one lock, this essentially means single-threading all the logic. Not very good. However too many locks may be bad too: locking and unlocking creates extra overhead. What is the best granularity? Depends on the particular program. The only way to find out is to try and see what happens.

A typical place where this issue comes up is in the composite data structures. Suppose, we have a list. The choice here is to have a single lock for the whole list, or have a lock for the whole list plus a lock for each element of the list. With a single lock, the logic is simple: anyone using the list or any of its elements must acquire the lock. With the multiple locks, the logic can be written in pseudocode:


Addition of an element:
    Create and initialize the new element;
    Lock the list;
    Add the new element to the list;
    Unlock the list;

Access of an element:
    Lock the list;
    Find the element;
    Lock the element;
    Unlock the list;
    Perform the operation on the element;
    Unlock the element;

Deletion of an element:
    Lock the list;
    Find the element;
    Lock the element;
    Remove the element from the list;
    Unlock the list;
    Unlock the element;
    Destroy and free the element;

Note that locking an element guarantees not only that the element won't be accessed by anyone else but also that the element won't be destroyed. Because of this, the deletion also needs to lock the element before destroying it. What if you work with an element and then decide that you need to delete it? You can't just lock the list and proceed. This would create a possibility of a deadlock, if some other thread has already locked the list and now tries to lock the same element as the first thread. The only way around is to unlock the element and then proceed with the deletion from scratch: lock the list, find the element, lock the element, and only then delete it. Even the finding of the element can't be skipped, since some other thread might have already deleted in the meantime.

This applies to any kind of composite data structures, and the structures may be nested further and make the question of the best lock granularity even more complicated. The rule of thumb is: if there is not likely to be much contention for some data, don't bother with the fine-granularity locks around it.

Mixing the locks with object-oriented languages makes some things easier and some things harder. Exceptions are a bit of a pain. Normally you don't want to leave the locks unintentionally locked if some error condition is found. In a classic procedural language it's not that hard to get it right:


lock();
ok = call();
unlock();
if (!ok)
    return false;

But exceptions happen unexpectedly and make the function return without showing it obviously in the code. So if there is any chance of exceptions, the locks must be wrapped in try/catch statements:


lock();
try {
    call();
} catch() {
    unlock();
    throw;
}
unlock();

In C++ another feature comes to the resque. The objects defined in a block get destroyed on any exit from the block, normal or on exception. So many multithreading libraries feature an "automatic lock" class, as in Listing One. The constructor remembers the lock and locks it; the destructor unlocks the remembered lock. This makes the code a lot cleaner. Java doesn't have the destructors but it does one better: it provides a keyword synchronized() that does the same thing and more.

However a thing that is usually overlooked and missing is the opposite thing, an "automatic unlock". It's often necessary to release a lock temporarily in the middle of a loop, to perform some lengthy operation:


lock();
for(...) {
    ...
    unlock();
    long_operation();
    lock();
}
unlock();

If we look at it sequentially, locks and unlocks don't line up, they have mismatched block boundaries. But if we look at it the other way, that's an "automatic unlock" nested inside "automatic lock" and they line up perfectly. A simple C++ implementation is shown in the Listing Two. This way things are much harder to get wrong. An important point is that the variable in the loop block is normally created and destroyed with the lock locked. It may depend on that. If the long operation throws an exception, this condition won't be violated. First, on destruction of AutoUnlock the lock would get locked, then the variable destroyed, then on destruction of AutoLock the lock will be unlocked again.

Unfortunately, things aren't so easy in Java. There is not only no opposite to synchronized() but it also uses an implicit lock built into the object, and there is no apparent way to work with that lock explicitly at all. This adds a startling amount of complication to things that could be so very simple. Even the simple loop shown above becomes a tangle.

For another concrete example, suppose you have a socket or a device driver file. How do you check if there is data available on it without blocking? Java gives no built-in way to do it but the solution is straightforward: make a wrapper object containing a buffer and a background thread that keeps reading data and placing it into the buffer. Then all you need is to check the buffer: if the buffer is empty, there is no data available. It would be so easy to just make the whole class synchronized and forget about the manual locking. But things don't work this way.

When the background thread gets stuck reading from the file, it takes the lock with it. Any attempt to check the state of the buffer gets stuck forever until the file gets closed, since that's when the method run() in the background thread exits and releases the lock. The manual synchronization has to be used instead.

Now let's move on to the holds. The holds have been used even in the single-procesor Unix OS kernels (the interrupt priority levels were playing the role of the locks at the time). When a thread gets a hold on an object, it says "I may be not actively working with this object right now but I need it, so don't anybody dare to delete it". Essentially, it's a reference counter. Get a hold -- increase the counter, release a hold -- decrease the counter.

With the classic reference counters, whoever decreses the counter to zero deletes the object. In the multithreaded programs things may be more complicated. Only a certain thread might be capable to delete the object correctly. So when the counter goes down to 0, instead of deleting the object, often some other thread gets notified and takes over from there. A class implementing such an approach with POSIX threads is shown in Listing Three.

In other cases the object with hold count of zero doesn't get immediately deleted but is put for a while into the cache of free objects. If someone needs it again, it can be quickly resurrected from the cache. Unless the memory becomes needed for something else and the cache gets cleared.

In some cases the objects on the cache may stay referenced even while their reference counts are zero. This works only if all the objects in the cache are pre-allocated once and never freed. Then a thread that needs the same kind of an object again can try to go directly to the object it used last time, get a lock on it and check if the object hasn't been cleared or reused yet. The lock guarantees that the object won't get reused while the check is in progress. If it wasn't reused, the thread can get a hold on this object (i.e. increase the reference count) and proceed like nothing happened. This approach is often used for all kinds of buffer caches, an object may be a page from a disk file cached in memory.

Of course, locks and holds are not sufficient by themselves to solve all the synchronization needs. But they form the important basics.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video