Subj : Re: Challenge: Multithreading & Synchronization
To   : comp.programming.threads
From : Uenal Mutlu
Date : Wed May 18 2005 09:48 pm

/*
  Here's my solution.

  It applies the deadlock theorem, and by this it is deadlock-free, and
  everything is also thread-safe.

  The right order of the locks is obviously important (it follows the deadlock theorem).

  Performance is theoretically the fastest possible (unless someone
  uses hand crafted assembler code).

  It's that simple by using recursive mutex and applying the deadlock theorem.

*/


//----------------------------------------------------------
// recursive mutex:
class rmutex
  {
    public:
      rmutex()      { /*..*/ }
      ~rmutex()     { /*..*/ }
      void lock()   { /*..*/ }
      void unlock() { /*..*/ }
  };

//----------------------------------------------------------
// helper classes:

class Locker
  {
    public:
      Locker(rmutex& Am) : m(Am) { m.lock();   }
      ~Locker()                  { m.unlock(); }
    private:
      rmutex& m;
  };

template<typename T> class Lockable : public T
  { public: rmutex m; };  // uses recursive mutex


//----------------------------------------------------------
// The "Server" class:

#include <vector>


struct SessionData
  {
    int iSessId;
    //...
  };

struct JobData
  {
    int iJobId;
    //...
  };

struct MiscData
  {
    int iMiscId;
    //...
  };


class Server
  {
    public:
      Server()
        {
        }

      ~Server()
        {
        }

      // assume all public functions can make calls to each other,
      // and also to internal funcs

      void f1(void* Ap = 0)
        { // uses vJD, vMD
          Locker L1(vJD.m);       // the order of the locks is important
          Locker L2(vMD.m);

          //...
        }

      void f2(void* Ap = 0)
        { // uses vMD, vSD
          Locker L1(vSD.m);
          Locker L2(vMD.m);

          //...
        }

      void f3(void* Ap = 0)
        { // uses vSD, vMD
          Locker L1(vSD.m);
          Locker L2(vMD.m);

          //...
        }

      void f4(void* Ap = 0)
        { // uses vJD
          Locker L(vJD.m);

          //...
        }

      void f5(void* Ap = 0)
        { // uses vMD, vJD, vSD
          Locker L1(vSD.m);
          Locker L2(vJD.m);
          Locker L3(vMD.m);

          //...
        }

      void f6(void* Ap = 0)
        { // uses vMD
          Locker L(vMD.m);

          //...
        }

      void f7(void* Ap = 0)
        { // uses vMD
          Locker L(vMD.m);

          //...
        }

      void f8(void* Ap = 0)
        { // uses none

          //...
        }

      void f9(void* Ap = 0)
        { // uses vMD, vJD, vSD
          Locker L1(vSD.m);
          Locker L2(vJD.m);
          Locker L3(vMD.m);

          //...
        }


    private:

      // assume all internal functions can make calls to each other.

      void if1(void* Ap = 0)
        { // uses vSD, vJD
          Locker L1(vSD.m);
          Locker L2(vJD.m);

          //...
        }

      void if2(void* Ap = 0)
        { // uses vSD, vMD
          Locker L1(vSD.m);
          Locker L2(vMD.m);

          //...
        }

      void if3(void* Ap = 0)
        { // uses vJD, vMD, vSD
          Locker L1(vSD.m);
          Locker L2(vJD.m);
          Locker L3(vMD.m);

          //...
        }

      void if4(void* Ap = 0)
        { // uses vMD
          Locker L(vMD.m);

          //...
        }

      void if5(void* Ap = 0)
        { // uses vSD, vMD
          Locker L1(vSD.m);
          Locker L2(vMD.m);

          //...
        }


    private:
      // shared data: accessed by most member functions:
      // all data members are independent of each other
      Lockable<std::vector<SessionData> > vSD;
      Lockable<std::vector<JobData> >     vJD;
      Lockable<std::vector<MiscData> >    vMD;
  };

//----------------------------------------------------------
Server gServer;  // only 1 Server object exists in application

extern bool IsPgmTerminating();

void* thread_proc(void* Ap)  // all threads use the same one thread proc
  { // no need to write code for this func
    // client gets registered and unregistered in gServer by the calling thread

    while (!IsPgmTerminating())
      {
        // serve client by calling functions of gServer
      }

    return 0;
  }

//----------------------------------------------------------

.