This document is under construction.

Intent:

Some parallel algorithms can be effectively implemented using a queue that is shared among processes. The SharedQueue pattern describes such queues.

Also Known As:

To be added.

Motivation:

Queues shared among processes are not uncommon in implementations of parallel algorithms. Careful thought, however, suggests that a naive sequential implementation of the queue ADT is not guaranteed to work if multiple concurrently-executing units of execution have access to a queue. What is needed in this context is an implementation of the queue ADT that can be used by concurrent callers without problems -- a "thread-safe" implementation, in other words.

Applicability:

Use the SharedQueue pattern when concurrently-executing UEs must share a queue data structure (i.e., a data structure that implements the usual queue operations -- enqueue, dequeue, etc.).

Structure:

This pattern is simply a "thread-safe" version of the usual queue ADT.

Usage:

Outside agents interact with this pattern as with any other implementation of the queue ADT, through an interface that supports the following operations:

• new, which creates a new queue.
• empty, which indicates whether a queue is empty.
• enqueue, which adds a specified element to the tail of the queue.
• dequeue, which removes and returns the element at the head of the queue.

Consequences:

This pattern is helpful in guaranteeing correctness of an algorithm in which concurrently-executing UEs must share a queue. It would likely lead to inefficiency, however, if used in a context in which its thread safety is not needed (e.g., a context in which only one UE could ever access it at a time).

Implementation:

As noted previously, this pattern would ideally already be implemented as part of a library of components compatible with the programmer's chosen programming environment. This section nonetheless indicates how to implement the pattern if no suitable implementation is available.

The key issue to be addressed in implementing this pattern is guaranteeing that the semantics of the queue are preserved even with multiple concurrent callers. (Careful thought will suggest how unrestricted concurrent access to the shared data structure that represents the queue could cause problems.) An easy, though probably not optimally efficient, way to do this is to ensure that at most one process at a time has access to the shared data structure that represents the queue.

Examples:

To be added.

Known Uses:

This pattern has many uses, for example in implementations of the EmbarrassinglyParallel pattern.

Related Patterns:

Related patterns include those representing other shared data structures, for example SharedCounter.