I. Installation.
 III. NonBlockingQueue.
 1 NonBlockingQueue design.
 2 Simplest example with NonBlockingQueue.
 3 NonBlockingQueue prototypes.
 4 Python-based acceptance test of NonBlockingQueue.
 VI. OTS Scheduler.
 VII. Bibliography

## NonBlockingQueue design.

he design is described by the picture ( NonBlockingQueue Design ).

NonBlockingQueue Design

The key idea is using an unprotected unsigned char field called "the switch". "Unprotected" means that this field is being incremented and read by every thread that passes it but this field is not being locked. Whatever, perhaps unstable, value is extracted from this field, the thread then reads a corresponding pointer from the array of 256 pointers (a pointer for each possible value of the switch). Each pointer in this non-mutable array correctly points to some Element of the circular structure (see the picture ( NonBlockingQueue Design )). Each Element has a mutex. Successful try-locking of this mutex enables access to the double-linked list of Nodes. If the try-locking fails then the thread proceeds to the next Element in the circular structure. By employing this strategy we decrease the likelihood of failed try-locking by the number of times equal to the number of elements in the circular structure.

There is, of course, a trade off. Suppose we extract Nodes and the queue is almost empty. The thread blocks Element, discovers that it is empty and moves to the next Element. If the queue is completely empty then the thread has to go around entire circle to establish that the queue is empty. Hence, the circle has to be large enough to keep down likelihood of failed try-locking but it should not be too large to keep down the performance hit when extracting final Nodes from the queue.

The NonBlockingQueue allows direct extraction of a given Node. Such extraction does not involve search. In order to extract the Node we need to lock the list of Nodes that holds it. As explained above such lock is performed on the mutex of the Element. Hence, the Node has to have a pointer to the Element. Such pointer is called "the Parent" in the code. Therefore, the Node has to have a mutex of it's own to protect the Parent. The extracting thread must have ownership of both mutexes (Node's and Element's) to extract the Node and the list of Nodes has to be double-linked. Since we need ownership of two mutexes we must avoid deadlock. It is achieved by locking Element first or using the try-release pattern.

The Consructors and Destructors for the Queues and Elements are not thread safe. For Constructor this is so because there is no need. For Destructor this is so because locking operations may throw exception and we do not have a way to handle it inside. On the other hand, letting exceptions to escape is against the Law ( [Sutter1] ). Hence, we leave it user's responsibility to make sure that the Queue is empty when destructed and to create/delete it on a single thread.

The Destructor for the Node does not do anything because Node does not take any ownership.