Channels ▼
RSS

Design

Lock Options

Source Code Accompanies This Article. Download It Now.


D Implementation

To make my deadlock-prevention scheme practical, I need to automate code generation. In D, code can be generated from strings using mixins. Strings can be manipulated during compile time to produce the desired code. Moreover, in D, you don't have to learn a separate language to evaluate things at compile time. A sizable subset of D can be executed at compile time. Because compile-time functions can also be called at runtime, testing and debugging is a breeze.

I start with the task of creating some global declarations. I need to:

  • Declare a global array of mutexes.
  • Generate code that will initialize it at startup.
  • Declare the hierarchy of interfaces that encapsulate lock options.
  • Generate some helper functions for type parsing.

The input, known at compile time, is the list of lock names. Here, I name my locks "A", "B", and "C" (normally, one would use more meaningful names). In client's code, all this is accomplished in one top-level statement:


mixin(declareAllLocks   (["A", "B", "C"])); 


The order in which lock names are specified doesn't matter—they will be sorted alphabetically at compile time.

Particular lock options are generated using a compile-time function, Options, which again takes a list of lock names. The result of Options, a string, is converted to a proper type at compile time using a template ToType. For instance, to generate the type that encapsulates the option to take locks "A" and "B", the client writes:


ToType!(Options(["A", "B"])) 


D's template syntax uses the exclamation mark to introduce template parameters (equivalent to angle brackets in C++ and lookalikes). Here, the template ToType is parametrized by a compile-time string returned by Options.

Below is the declaration of a function with the option to take locks "A" and "B":


void takeAB(ToType!(Options(["A",     "B"])) lockOptions); 


Notice that the lock option variable must be named lockOptions for another mixin, LOCK, to work. This mixin combines the taking of a named lock with the declaration of a new local variable, lockOptions, as described earlier. Here, lock "A" is taken for the duration of its scope:


mixin(LOCK("A")); 


Listing Two shows the example of user code. The complete implementation is available online at www.ddj.com/code/).

Conclusion

The deadlock-prevention scheme described here has a lot of limitations. It doesn't work with fine-grain locking, where the number of dynamically created objects with their own locks is unpredictable. It doesn't deal with more general reentrancy, where a thread can retake any of the locks it already holds. On the other hand, lock-taking is encoded in the type system, so once the program compiles, it is guaranteed not to deadlock (at least not on the locks that take part in the scheme). That's a much stronger guarantee than even the most comprehensive runtime testing can provide.

Acknowledgments

I'm grateful to Scott Meyers for making an early version of his paper available to me, and to Andrei Alexandrescu and Walter Bright for valuable comments.

interface NoLock {} 
interface A: NoLock {} 
interface B: NoLock {} 
interface C: NoLock {} 
interface A_B: B,A {} 
interface A_C: C,A {} 
interface B_C: C,B {} 
interface A_B_C: B_C,A_C,A_B {} 


Listing One

mixin(declareAllLocks(["A", "B", "C"])); 
void takeC(ToType!(Options(["C"])) lockOptions) { 
  { 
    mixin(LOCK("C")); 
  } 
} 
void takeBC(ToType!(Options(["B", "C"])) lockOptions) { 
  { 
    mixin(LOCK("B")); 
    takeC(lockOptions); 
  } 
} 
void main() { 
  ToType!(Options(["C", "B", "A"])) lockOptions; 
  takeBC(lockOptions); 
}
Listing Two


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