"The English can form a queue of 1"
Flow-Based Programming (FBP) [1], Communicating Sequential Processes (CSP) [2] and Active Objects (AO) [3] rely on message passing between otherwise environmentally opaque conccurent components.
There are lots of ways of providing this communication[4], be that synchronous or asynchronous, but one of the most frequently used is that of a message queue.
The principle reference for my development of the concurrent queues is the, totally excellent, The Art of Multiprocessor Programming (Herlihy & Shavit 2008)
- type safe
- multiple writer (producer)
- single reader (consumer)
- concurrent (thread safe)
- FIFO (first-in-first-out)
- ordered sequence of items
This can be generalised to a template programmed, multiple producer, multiple consumer, thread safe FIFO queue.
As an abstract data type the queue is theoretically unbounded and whilst traditionally implemented as a linked list, it can also be implemented using an array as a circular buffer - which offers the saving on allocation and deallocation by simply and blindly over-writing.
To this end the C++ standard template library offers the choice of implementing the std::queue container adaptor, which is not thread safe, using either the std::list or std::deque (a double ended queue implemented using a modified dynamic array).
In order to make the std::queue thread safe it is necessary to provide a wrapper that provides some form of synchronized access to the head and tail of the queue.
The simplest and most obviously correct (a property which should not be underestimated) method of serving multiple concurrent enqueuers and dequerers is to use a single data structure global lock.
Such a course grained approach enforces a single linearization point whenever a message is enqueued or dequeued and, consequently, reduces liveliness. (The property of liveliness is a good thang in concurrent programming - being the ability to execute in a timely manner for increased throughput.)
However, because all of the member functions act on the std::queue only whilst holding that single lock then the execution is essentially sequential and, ergo, obviously correct - a useful property when debugging multiprocessor software.
The next two design decisions are:
- how to react to an empty queue when making a dequeue request?
- how to react to a full queue when making an enqueue request?
1. The two main ways of reacting to an empty queue are for the dequeue member function to either:
- wait until the the queue is no longer empty.
- exit with an error.
Whilst waiting is good logical behaviour with a simple interface that can send the calling thread to sleep and free processing resources to maintain liveliness, it denies the consuming thread with information about the state of communication.
Such denial of knowledge prevents a consuming thread from being able to make its own decisions about if and how long it might want to wait for a message, further, the opportunity for more intelligent behaviour such as a thread changing its own or a producer's priority is lost.
Consequently, the latter approach is proposed using the traditional idiom of a try member function that returns true or false on success or failure.
2. The unbounded nature of the abstract queue data type would seem to render the second question moot.
However, the prospect of a multithreaded program being able to relentlessly fill up a message queue without limitation, other than chewing up all of the available memory, is (trust me) a recipe for disaster!
Consequently having a bounded message queue offers a fail safe option and implementing the enqueue member function using the same try idiom as the dequeue member function, returning true on success and false on failure, increases the awareness of the producing thread.
Thus the design specifications for a general purpose (GP) multi-producer, multi-consumer, course grained (CG) thread safe message queue are in place for then next blog entry coding the gpcg_message_queue.
References:
No comments:
Post a Comment