How to use synchronized() {} as the basis for a freely (un)lockable mutex, using stackthreads

downs default_357-line at yahoo.de
Wed Jan 9 04:47:35 PST 2008


Disclaimer: My StackThreads are neither particularly fast (130 cycles per context switch), nor particularly stable.
This is primarily intended as a Proof of Concept, even though I do use it in some of my code. :)

Have you ever wished D had a Mutex class that could be locked or unlocked at any time?
D's synchronized() {} statement is nice and all, but does have some weaknesses, primarily that it can only be used to
synchronize some scope - it is not possible to unlock the underlying mutex in the middle of a block.

Of course, I could write code that depends upon the OS' mutexes, but that's hardly in the spirit of D.
Of course, I could write a busy-spin based mutex class, but it is my firm belief that busyspin *expletive* *expletive*.

So, there remains only one solution: twist synchronized(){} so that it becomes freely (un)lockable.

This requires a way to break out of the middle of a synchronized block, without ending the synchronization.

Stackthreads offer such a way.

Consider the following code from scrapple.tools.threads:

> 
> import tools.stackthreads, std.thread;
> class Lock {
>   StackThread!(bool, void)[] toggle;
>   Thread[] toggle_thr;
>   Object toggle_sync;
>   
>   this() { toggle_sync=new Object; }
>   
>   StackThread!(bool, void) getMyST() {
>     auto thr=Thread.getThis();
>     foreach (id, entry; toggle_thr) if (entry is thr) return toggle[id];
>     auto nt=stackthread=(Object This, bool delegate() which) {
>       while (true) {
>         if (!which()) throw new Exception("Cannot double-free lock");
>         synchronized(This) if (which()) throw new Exception("Cannot double-claim lock");
>       }
>     } /fix/ this;
>     synchronized (toggle_sync) { toggle_thr ~= thr; toggle ~= nt; }
>     return nt;
>   }
>   
>   void lock(bool locking) { getMyST()(locking); }
>   void lock() { lock(true); }
>   void unlock() { lock(false); }
>   void Synchronized(void delegate() dg) { lock; scope(exit) unlock; dg(); }
>   void Unsynchronized(void delegate() dg) { unlock; scope(exit) lock; dg(); }
> }

What does this code do?

Basically, it assigns every thread that tries to use the lock, a Stackthread (slightly wasteful but meh).
getMyST returns the current thread's Stackthread, or creates it if it doesn't exist yet.

Basically, each StackThread takes bools for input, and nothing for output ( "!(bool, void)" ).
The ST must be fed true and false in turn; true for "Go and enter the synchronized {} block", and false for "Leave the synchronized {} block".

(
  For those unfamiliar with stackthreads, whenever the delegate calls "which", the stackthread is suspended until the surrounding
  function calls it with a bool value. At this point, the stackthread delegate resumes, with "which" returning the value the stackthread
  was called with.
)

An example application would be the creation of a cache class.

class Cache(VAL, KEY) {
  VAL[KEY] buffer;
  Lock lock;
  VAL delegate(KEY) dg;
  this(typeof(dg) _dg) { dg=_dg; New(lock); }
  VAL get(KEY key) {
    VAL res;
    lock.Synchronized = {
      if (key in buffer) res = buffer[key];
      else {
        lock.Unsynchronized = { res = dg(key); };
        buffer[key] = res;
    };
    return res;
  }
}

And yes, I know this class doesn't handle the case of simulataneous evaluation of dg with the same key. It's only an example. :)

 --downs



More information about the Digitalmars-d mailing list