Programming with POSIX® Threads

Pipeline	Each thread repeatedly performs the same operation on a sequence of data sets, passing each result to another thread for the next step. This is also known as an "assembly line."
Work crew	Each thread performs an operation on its own data. Threads in a work crew may all perform the same operation, or each a separate operation, but they always proceed independently.
Client/server	A client "contracts" with an independent server for each job. Often the "contract" is anonymous—a request is made through some interface that queues the work item.

TABLE 4.1Thread programming models

All of these models can be combined in arbitrary ways and modified beyond all recognition to fit individual situations. A step in a pipeline could involve requesting a service from a server thread, and the server might use a work crew, and one or more workers in the crew might use a pipeline. Or a parallel search "engine" might initiate several threads, each trying a different search algorithm.

4.1 Pipeline

"I want a clean cup," interrupted the Hatter: "let's all move one place on.

" He moved on as he spoke, and the Dormouse followed him: the March Hare moved into the Dormouse's place, and Alice rather unwillingly took the place of the March Hare. The Hatter was the only one who got any advantage from the change; and Alice was a good deal worse off than before, as the March Hare had just upset the milk-jug into his plate.

— Lewis Carroll, Alice's Adventures in Wonderland

In pipelining, a stream of "data items" is processed serially by an ordered set of threads (Figure 4.1). Each thread performs a specific operation on each item in sequence, passing the data on to the next thread in the pipeline.

For example, the data might be a scanned image, and thread A might process an image array, thread B might search the processed data for a specific set of fea-tures, and thread C might collect the serial stream of search results from thread B into a report. Or each thread might perform a single step in some sequence of modifications on the data.

The following program, called pipe.c, shows the pieces of a simple pipeline program. Each thread in the pipeline increments its input value by 1 and passes it to the next thread. The main program reads a series of "command lines" from stdin. A command line is either a number, which is fed into the beginning of the pipeline, or the character "=," which causes the program to read the next result from the end of the pipeline and print it to stdout.

FIGURE4.1Pipelining

1 #include

2 #include "errors.h" 3

4 /*

5 * Internal structure describing a "stage" in the

6 * pipeline. One for each thread, plus a "result

7 * stage" where the final thread can stash the value.

8 */

9 typedef struct stage_tag {

10 pthread_mutex_t mutex; /* Protect data */

11 pthread_cond_t avail; /* Data available */

12 pthread_cond_t ready; /* Ready for data */

13 int data_ready; /* Data present */

14 long data; /* Data to process */

15 pthread_t thread; /* Thread for stage */

16 struct stage_tag *next; /* Next stage */

17 } stage_t; 18

19 /*

20 * External structure representing the entire

21 * pipeline.

22 */