Intent:

This pattern describes what may be the most loosely structured type of concurrent program, in which semi-independent tasks interact through asynchronous events.

Also Known As:

• Event-driven programming?

Motivation:

Some problems are most naturally represented as a collection of semi-independent entities interacting in an irregular way. Examples of such problems include the following:

• Discrete-event simulation, in which a physical system consisting of a collection of objects whose interaction is represented by a sequence of discrete "events". The following figure sketches an example of such a physical system consisting of a car, its driver, and its physical environment; arrows represent interactions.

• Event-driven programming, in which the program is defined in terms of a number of concurrently-executing tasks interacting via "events". Many GUI-based programs are, or could be, structured in this way, with one task that accepts user input, one task that displays results, and one or more tasks to perform background computation. The program can be thought of as being driven by intertask events (e.g., the user presses a key), hence the name. The following two figures sketch this idea. First we show the overall structure of the design (the tasks and their interaction).

• Real-time control programs.

For such problems, it often makes sense to base a parallel algorithm on defining a task for each of the entities (or possibly a group of tasks, if a hierarchical design makes sense). Interaction between these tasks is then based on ordering constraints (e.g., "this calculation in task A must happen before that calculation in task B").

Applicability:

Use this pattern when:

• The most natural decomposition of your problem is into tasks whose interaction is organized by ordering constraints, as described.

This pattern is particularly appropriate when:

• The problem description is inherently concurrent, as in the examples above.

Structure:

Implementations of this pattern include the following key elements:

• Defining the tasks/entities.
• Representing their interaction, often in terms of events.
• Scheduling the tasks.

Usage:

This pattern is typically used to provide high-level structure for an application; that is, the application is typically structured as an instance of this pattern.

Consequences:

• It can be difficult to use this pattern for problems in which the interaction is especially irregular. Discrete-event simulations can fall into this category: For example, if object A's behavior depends on whether it receives an event from object B, and B can generate these events irregularly or not at all, the program designer may have to choose between having A proceed with computation that could be invalidated by an event from B and having A wait for an event that may never arrive.

Implementation:

Key elements.

Defining the tasks.

What is needed here is a program structure to hold the computations associated with the tasks/entities. This is essentially the same as the problem of defining the pipeline elements in the PipelineProcessing pattern, and the same approaches apply.

Representing their interaction.

What is needed here is a mechanism for representing the interaction among tasks/entities. If the interaction is in terms of events, what is needed is a way for the task generating the event to communicate it to the task that will process it. In a shared-memory environment, this can be done via a shared queue data structure (which can be implemented with the SharedQueue pattern), with the generating task adding items to the queue and the processing task removing and processing them. In a message-passing environment, an event corresponds to a message sent from the generating task to the processing task.

Scheduling the tasks.

What is needed here is a way of scheduling the tasks or task groups that make up the design. It is simplest to schedule all tasks to execute concurrently (as in the PipelineProcessing pattern), since this makes it easier to avoid deadlock.

Examples:

Examples to be added soon.

Known Uses:

Known uses of this pattern are in event-driven programming and discrete event simulation.

Related Patterns:

This pattern is similar to the PipelineProcessing pattern in that both patterns apply to problems where it is natural to decompose the computation into a collection of semi-independent entities. The difference is that in the PipelineProcessing pattern, these entities interact in a more regular way, with all "stages" of the pipeline proceeding in a loosely synchronous way, whereas in the AsynchronousComposition pattern, there is no such requirement, and the entities can interact in very irregular and asynchronous ways.