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.
|
