Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

C/C++

Lock Options


Proof of Concept

In my first attempt at an implementation, I annotate functions by hand. To begin with, any function that explicitly takes a lock must have this lock in its signature—it must take a dummy parameter of the appropriate type. For the callers of these functions to compile, they too have to take dummy parameters of the appropriate type and pass them to the callees. It's as if functions that take locks were tainted, and all functions that call them become tainted, too. Below, the function CallsBoth is tainted with lock options A and B because it calls tainted functions TakesA and TakesB:


void TakesA(A lockOptions); 
void TakesB(B lockOptions); 
void CallsBoth(A_B lockOptions) { 
  TakesA(lockOptions); 
  TakesB(lockOptions); 
} 


The annotation (tainting) process ends at some high level, where you simply define a dummy variable of the appropriate type and pass it down. For instance:


void main() { 
A_B lockOptions; 
CallsBoth(lockOptions); 
} 


Now that I have the type system on my side, let's talk about locking. Because I'm assuming that locks are known at compile time, I can simplify things by putting all mutexes in a global associative array:


Mutex[string] mutexes; 


Taking a lock for the duration of a given scope is done by declaring a scope variable:


scope __scopelock =     new Lock(mutexes["B"]); 


Scope variables in D are guaranteed to be destroyed at the end of their scope (without waiting for a garbage collection sweep).

There is one piece of the puzzle missing. What should I do when a function takes a given lock and then calls another function that declares lock options? Consider this example:

void f(int x, A_B_C lockOptions) { 
  { // begin lock scope 
    scope __scopelock =       new Lock(mutexes["B"]); 
    TakesA(lockOptions);     // Oh no!!! 
  } // end lock scope 
} 


This function compiles because A_B_C is convertible to A. On the other hand, this is exactly the situation we tried to avoid—taking lock A after lock B (remember, I assumed that locks must be taken in alphabetical order). A recipe for a deadlock!

My solution is to redefine the variable lockOptions immediately after taking the lock. The type of that new variable should be derived from the type of the outer lockOptions and from the name of the lock that's been just taken. This type must encapsulate the remaining lock options.

Here's the key to my algorithm—the new lock options (a sequence of locks that may still be taken safely) are the old lock options stripped of all locks that alphabetically precede the lock just taken. If these new lock options are enforced when calling other functions, a deadlock is impossible—no lock can be taken out of order.

Here's the modified example:


void f(int x, A_B_C lockOptions) { 
  TakesA(lockOptions); // OK 
  { 
    // These two lines will be     // generated together 
    scope __scopelock = new        Lock(mutexes ["B"]); 
    B_C lockOptions; // stripped A 
    TakesC(lockOptions);   
  // Okay to take C after B 
    TakesA(lockOptions);     // Compile error! 
  } 
  TakesA(lockOptions);    // OK, using outer lockOptions 
} 


The outer-scope variable lockOptions is redefined in the inner scope and given a different type. It is this shadowing that makes the scheme virtually foolproof—the outer lockOptions cannot be accessed after the inner lockOptions is declared. The shadowing lasts until the end of the scope, which coincides with the end of the scope of the lock itself, which is exactly what was ordered.


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.