barrier.h

Go to the documentation of this file.

/*  Glass - a distributed computing library
    Copyright (C) 2003-2009 Bruno Barberi Gnecco
    Copyright (C) 2009-2010 Corollarium Technologies


    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
    License as published by the Free Software Foundation; either
    version 2 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public
    License along with this library; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#ifndef _GLASS_PLUGIN_BARRIER_HH_
#define _GLASS_PLUGIN_BARRIER_HH_

#include <map>
#include "plugin.h"
#include "exception.h"
#include <boost/thread.hpp>

namespace libglass {

// Barrier states: inactive, active, locked, disabled
// ==================================================
// Barriers are tricky, because they deadlock very easily...
// Suppose you have a program that consists of 2 barriers:
// 
//      Barrier *a, *b;
// 
//      a = new Barrier();
//      b = new Barrier();
// 
//      while (1) {
//              ...
//              a->sync();
// *            ...
//              b->sync();
//              ...
//      }
// 
// Lets assume the first node starts and enters the loop before a second node joins:
// 
// Consider the case if the barriers had only two states (locked/unlocked)...
//   If node 2 joined when node 1 was at * then a deadlock would occur, as node 1
//   would call b->sync(), and therefore wait for node 2 to call b->sync(), while
//   node 2 would call a->sync(), and wait for node 1 to call a->sync().
// 
// To overcome this problem Bruno and Paiva have designed the a system which uses
//      uses three barrier states: active/inactive/locked...
//      When a barrier is created (with new), it is set to the inactive state by default.
//      This means: if other nodes synchronize this barrier, they will not consider this node.
//      It's almost as if the barrier is disabled when it is in the inactive state.
//      When the first barrier sync() is called (let's say for barrier a), a is set to locked,
//      while all other barriers are still inactive. Barriers only get swithced to the active
//      state when their node calls sync() for the first time. Once in the active state, the
//      it's a locked/unlocked state machine (or more precisely locked/active using our current
//      terminology).
//      This advantage of this system is that it allows nodes to join the computation at any time
//      and synchronize automatically, avoiding deadlocks.
// 
// A fourth barrier state has also been defined - disabled. Currently, however, this state
// is not implemented.
// 
// Multithreaded nodes and Barriers...
// ===================================
// There's a conceptual problem with Barrier and multithreaded nodes that remains unsolved...
// 
// Suppose you have a Barrier b, which is global. How can Glass know which of the threads
// running on a node are going to synchronize this barrier? The idea of giving each thread a
// different Glass instance is not appealing!
// Right now what happens is: if two threads running on the same node synchronize the same
// barrier, Glass cannot distinguish this from the situation where one thread synchronises the
// barrier twice.
// Symptoms of this problem may explain the behaviour of the testthread1 application which is
// currently not working well - often the nodes are left in a deadlocked state as some threads
// are waiting on a barrier whilst other threads have destroyed it.
// Further problems may be caused by concurrent access to data. I don't know how thread safe
// the STL is, and I didn't want to clutter the code with mutexes. If there's a race condition,
// it almost certainly can be solved by a few mutexes in the Barrier class methods.



class Barrier;

class BarrierBase : public PluginBase {
        PLUGIN(BarrierBase);

private:
        typedef enum {
                Active,                 
                Inactive,               
                Locked,                 
                Disabled                
        } BarrierState;

        /* --- server --- */
        
        // Example servermap (2 barrier groups, 2 barrier numbers, 3 nodes)...
        // GroupNum     BarrierNum    NodeId      State 
        // --------------------------------------------------
        //    0              0          0         Inactive
        //    0              0          1         Inactive
        //    0              0          2         Inactive
        // --------------------------------------------------
        //    0              1          0         Inactive
        //    0              1          1         Inactive
        //    0              1          2         Inactive
        // --------------------------------------------------
        //    1              0          0         Inactive
        //    1              0          1         Inactive
        //    1              0          2         Inactive
        // --------------------------------------------------
        //    1              1          0         Inactive
        //    1              1          1         Inactive
        //    1              1          2         Inactive
        std::map<unsigned int, /* group */
                std::map<unsigned int, /* barrier num */
                        std::map<nodeId, BarrierState> > >
                                                servermap;

        // Example activemap (3 nodes)...
        // NodeId      Active
        // --------------------
        //    0         false
        //    1         false
        //    2         false
        std::map<nodeId, bool>                  activemap;

        /* --- client --- */

        // Example clientmap (2 barrier groups, 2 barrier numbers)...
        // GroupNum     BarrierNum    Barrier*
        // -------------------------------------
        //    0              0          ptr1
        //    0              1          ptr2
        // -------------------------------------
        //    1              0          ptr3
        //    1              1          ptr4
        // -------------------------------------
        std::map<unsigned int, /* group */
                std::map<unsigned int, /* number */
                        Barrier *> >
                                                clientmap;

        const char *state(BarrierState s);

        bool checkUpdate(unsigned int barriergroup, unsigned int barriernum);

protected:
        friend class Barrier;


        bool registerBarrier(Barrier *b);

        bool unregisterBarrier(Barrier *b);


        // *********************************************************************
        // Destructor should be PROTECTED to ensure singleton behaviour
        // However, Microsoft compilers prior to VC v7.0 .NET are buggy and
        // generate the following error
        //   error C2248: 'BarrierBase::~BarrierBase' : cannot access protected member declared in class 'libglass::BarrierBase'
        // The only workaround is to make the destructor PUBLIC - which kind
        // of destroys the whole reason for implementing the singleton class
#if defined(_MSC_VER) && (_MSC_VER < 1300)  // earlier than .NET compiler (VC 7.0)
public:
#else
protected:
#endif
        // *********************************************************************
        ~BarrierBase();

public:
};

class LIBGLASS_API Barrier : public PluginInterface { 
private:
        BarrierBase             *bb;            
        unsigned int            number;         
        unsigned int            group;          
        struct _syncdata {
                bool            lock;           
                bool            retval;         
                boost::condition_variable t;            
                boost::mutex t_mut;             
                boost::mutex    mutex;          
                _syncdata() : lock(false), retval(true) { }
        } syncdata;

protected:
        friend class BarrierBase;

public:
        Barrier(unsigned int num, unsigned int group = 0, 
                bool active = false) throw(Exception);

        ~Barrier();

        unsigned int getNumber(void) const { return this->number; }

        unsigned int getGroup(void) const { return this->group; }

        bool sync(void);

        bool disable(void);
        
        bool enable(void);
};

}//namespace


#endif // _GLASS_PLUGIN_BARRIER_HH_

---