Boost logo

Boost :

From: Branko Èibej (branko.cibej_at_[hidden])
Date: 2000-08-24 03:56:39

William Kempf wrote:
> --- In boost_at_[hidden], Jens Maurer <Jens.Maurer_at_g...> wrote:
> > - Implement generic debugging aids, if possible. For example, a
> > mutex deadlock detection is a must.
> Yep. Though I'm not the one to tell you how this can be done ;).

It's relatively straight-forward, although it's a bit tricky to implement
the check efficiently. Each thread needs to have a list of mutexes it
currently owns, and which mutex (if any) it's waiting for; a mutex needs
to know its current owner. Then, before a thread starts waiting on a
mutex, it (recursively) checks whether the owner of the mutex is
waiting on one of the mutexes the thread owns.

Something like this:

    struct thread;

    struct mutex {
      thread* owner;
      void lock();
      void unlock();

    struct thread {
      mutex* waiting_for;
      std::set<mutex*> owned;

    bool would_deadlock (mutex* m, thread* t)
      while (m->owner != NULL)
        if (t->owned.end() != t->owned.find(m->owner->waiting_for))
          return true;
        m = m->owner->waiting_for;
      return false;

    void mutex::lock()
      thread* t = current_thread();
      while (owner != NULL)
        if (would_deadlock(this, t))
          t->waiting_for = NULL;
          throw deadlock;
        t->waiting_for = this;
        // Sleep until mutex is unlocked

      t->waiting_for = NULL;
      owner = t;

    void mutex::unlock()
      owner = NULL;
      // Wake waiting threads

Of course, the interesting bit is that all of mutex::lock must be
atomic, otherwise you've got a race condition.


Branko Èibej                 <branko.cibej_at_[hidden]>
HERMES SoftLab, Litijska 51, 1000 Ljubljana, Slovenia
voice: (+386 1) 586 53 49     fax: (+386 1) 586 52 70

Boost list run by bdawes at, gregod at, cpdaniel at, john at