Re: [boost] Re: Threads

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;
      t->owned.insert(this);
      owner = t;
    }

    void mutex::unlock()
    {
      owner->owned.erase(this);
      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.

    Brane

-- 
Branko Èibej                 <branko.cibej_at_[hidden]>
HERMES SoftLab, Litijska 51, 1000 Ljubljana, Slovenia
voice: ([phone]     fax: [phone]