Email	Print Reprint
	add to:
	Del.icio.us Digg Google Furl	Slashdot Y! MyWeb Blink
	TABLE OF CONTENTS Lock Ordering Locks and Types Proof of Concept D Implementation

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.

Previous Page | 1 Lock Ordering | 2 Locks and Types | 3 Proof of Concept | 4 D Implementation Next Page

RELATED ARTICLES Cloud Computing: Detecting Scalability Problems Logging In C++ : Part 2 recls 100% .NET QuickThread: A New C++ Multicore Library C Snippet #8		TOP 5 ARTICLES No Top Articles.