Quantitative Analysis
Parallel Processing
Numerical Analysis
C++ Multithreading
Python for Excel
Python Utilities

I. Installation.
II. Threading primitives.
III. NonBlockingQueue.
1. NonBlockingQueue design.
2. Simplest example with NonBlockingQueue.
3. NonBlockingQueue prototypes.
A. NonBlockingQueue data fields.
B. NonBlockingQueue::push member function.
C. NonBlockingQueue::pop member function.
D. NonBlockingQueue::Element.
E. NonBlockingQueue::Node.
4. Python-based acceptance test of NonBlockingQueue.
IV. ThreadPool.
V. ThreadMaster.
VI. OTS Scheduler.
VII. Bibliography
Downloads. Index. Contents.


he class NonBlockingQueue::Node acts as described around the figure ( NonBlockingQueue Design ).

Lines 07, 07a below: This is the parent Element. This pointer is zero if the Node is not in the queue. theMutex is used to protect theParent only. The double linked list fields are protected by the mutex of theParent.

Line 08: Data is the information stored in the queue and the reason for existence.

Lines 09-10: the double linked list fields.

Lines 13-25: These are basic accessors. The presence and absence of volatile key-word explains the locking model.

Line 14: data() is volatile (thread-safe) because theData is a const pointer.

Lines 15,16,21,22,23,24: If Element is locked then list access is safe. Hence, presence of ElementGuard allow for volatile qualifier for these functions.

Line 35: remove this Node from the queue.

Line 38: Debugging feature.

Lines 39,41: Basic double linked list operations. Both the Element and Node has to be locked. Hence, the arguments.

Note that we cannot have a remove() operation accepting a Guard to Node. Such operation would require that we lock the Node first and then lock the Element. It would contradict the order of locking in the push/pop operations and lead to deadlock. For the same reason we cannot reuse a mutex field that may exist inside the Data. The Node must have mutex of its own. The implementation of existing remove() operation uses the try-release pattern of locking.

01\template <class Data>

02\ class NonBlockingQueue<Data>::Node : boost::noncopyable

03\ {

04\ public:

05\ class UnableToRemove : public boost::exception, public std::exception {};

06\ private:

07\ typename Queue::Element* theParent;

07a\ mutable typename Queue::NodeMutex theMutex;

08\ volatile Data* const theData;

09\ Node* thePrev;

10\ Node* theNext;

11\ friend class NonBlockingQueue<Data>::Element;

12\ public:

13\ inline NodeMutex& mutex() const { return theMutex; }

14\ inline volatile Data* data() const volatile { return theData; }

15\ template <class ElementGuard> bool isHead( ElementGuard& el ) volatile const;

16\ template <class ElementGuard> bool isTail( ElementGuard& el ) volatile const;

17\ inline bool hasData() const { return theData!=0; }

18\ inline void parent( typename Queue::Element* p ) { theParent=p; }

19\ inline volatile typename Queue::Element* parent() const { return theParent; }

20\ inline bool isInQueue() const { return theParent!=0; }

21\ template <class ElementGuard> volatile Node* prev( ElementGuard& el_ ) const volatile;

22\ template <class ElementGuard> void prev( ElementGuard& el_, Node* p ) volatile ;

23\ template <class ElementGuard> volatile Node* next( ElementGuard& el_ ) const volatile ;

24\ template <class ElementGuard> void next( ElementGuard& el_, Node* n ) volatile ;

25\ inline volatile Node* next() const { return theNext; }

26\ public:

27\ Node() : theParent(0),theData(0) {}

28\ explicit Node( Data& d ) : theParent(0),theData(&d) {}

29\ ~Node()

30\ {

31\ //The user has to make sure that the deleted Node is not in the queue.

32\ //This has to be user's responsibility at least because we would need to Lock to do anything

33\ //but then we cannot handle a possible thread resource exception here.

34\ }

35\ void remove() volatile;

38\ template <class ElementGuard> std::pair<bool,std::string> toString(

ElementGuard& el_,

const boost::function1<std::string,volatile Data*>& DataToString

) const volatile;

38a\ std::string toString( const boost::function1<std::pair<bool,std::string>,volatile Data*>& DataToString ) const;

39\ static void doInsert( ElementTryGuard& el_, NodeWriterGuard& node_ );

41\ template <class ElementGuard,class NodeGuard> static void doRemove( ElementGuard& el_, NodeGuard& node_ );

42\ };

Downloads. Index. Contents.

Copyright 2007