Add Book to My BookshelfPurchase This Book Online

Chapter 2 - Designing Threaded Programs

Pthreads Programming
Bradford Nichols, Dick Buttlar and Jacqueline Proulx Farrell
 Copyright 1996 O'Reilly & Associates, Inc.

Models
There are no set rules for threading a program. Every program is different, and when you first try to thread a program, you'll likely discover that it's a matter of trial and error. You may initially dedicate a thread to a particular task only to find that your assumptions about its activity have changed or weren't true in the first place.
Over time a few common models for threaded programs have emerged. These models define how a threaded application delegates its work to its threads and how the threads intercommunicate. Because the Pthreads standard imposes little structure on how programmers use threads, you would do well to start your multithreaded program design with a close look at each model. Although none has been explicitly designed for a specific type of application, you'll find that each model tends to be better suited than the others for certain types. We discuss:
 The boss/worker model
 The peer model
 The pipeline model
Boss/Worker Model
Figure 2-1: The boss/worker model.
Figure 2-1 depicts the boss/worker model. A single thread, the boss, accepts input for the entire program. Based on that input, the boss passes off specific tasks to one or more worker threads.
The boss creates each worker thread, assigns it tasks, and, if necessary, waits for it to finish. In the pseudo code in Example 2-1, the boss dynamically creates a new worker thread when it receives a new request. In the pthread_create call it uses to create each worker thread, the boss specifies the task-related routine the thread will execute. After creating each worker, the boss returns to the top of its loop to process the next request. If no requests are waiting, the boss loops until one arrives.
Once finished, each worker thread can be made responsible for any output resulting from its task, or it can synchronize with the boss and let it handle its output.
Example 2-1: Boss/Worker Model Program (Pseudocode)
main()
/* The boss */
{
forever {
          get a request
          switch request
          case X : pthread_create( ... taskX)
          case Y : pthread_create( ... taskY)
          .
          .
          .
}
}
taskX() /* Workers processing requests of type X */
{
perform the task, synchronize as needed if accessing shared resources
done
}
taskY() /* Workers processing requests of type Y */
{
perform the task, synchronize as needed if accessing shared resources
done
}
.
.
.
If the boss creates its workers dynamically when requests arrive, as it does in our pseudocode, there will be as many concurrent worker threads as there are concurrent requests. Alternatively, the boss could save some run-time overhead by creating all worker threads up front. In this variant of the boss/worker model, known as a thread pool and shown in Example 2-2,the boss creates all worker threads at program initialization. Each worker immediately suspends itself to wait for a wake-up call from the boss when a request arrives for it to process. The boss advertises work by queuing requests on a list from which workers retrieve them.
Example 2-2: Boss/Worker Model Program with a Thread Pool (Pseudocode)
main()
/* The boss */
{
for the number of workers
         pthread_create( ... pool_base )
forever {
         get a request
         place request in work queue
         signal sleeping threads that work is available
}
}
pool_base() /* All workers */
{
forever {
         sleep until awoken by boss
         dequeue a work request
         switch
           case request X: taskX()
           case request Y: taskY()
                  .
                  .
                  .
}
}
The boss/worker model works well with servers (database servers, file servers, window managers, and the like). The complexities of dealing with asynchronously arriving requests and communications are encapsulated in the boss. The specifics of handling requests and processing data are delegated to the workers. In this model, it is important that you minimize the frequency with which the boss and workers communicate. The boss can't spend its time being blocked by its workers and allow new requests to pile up at the inputs. Likewise, you can't create too many interdependencies among the workers. If every request requires every worker to share the same data, all workers will suffer a slowdown.
Peer Model
Unlike the boss/worker model, in which one thread is in charge of work assignments for the other threads, in the peer model, illustrated in Figure 2-2, all threads work concurrently on their tasks without a specific leader.
Figure 2-2: The peer model
In the peer model, also known as the workcrew model, one thread must create all the other peer threads when the program starts. However, unlike the boss thread in the boss/worker model, this thread subsequently acts as just another peer thread that processes requests, or suspends itself waiting for the other peers to finish.
Whereas the boss/worker model employs a stream of input requests to the boss, the peer model makes each thread responsible for its own input. A peer knows its own input ahead of time, has its own private way of obtaining its input, or shares a single point of input with other peers. The structure of such a program is shown in Example 2-3.
Example 2-3: Peer Model Program (Pseudocode)
main()
{
   pthread_create( ... thread1 ... task1 )
   pthread_create( ... thread2 ... task2 )
   .
   .
   .
   signal all workers to start
   wait for all workers to finish
   do any clean up
}
task1()
{
   wait for start
   perform task, synchronize as needed if accessing shared resources
   done
}
task2()
{
   wait for start
   perform task, synchronize as needed if accessing shared resources
   done
}
The peer model is suitable for applications that have a fixed or well-defined set of inputs, such as matrix multipliers, parallel database search engines, and prime number generators. Well-defined input allows programs to adopt what could be construed as a boss/worker model without the boss. Because there is no boss, peers themselves must synchronize their access to any common sources of input. However, like workers in the boss/worker model, peers can also slow down if they must frequently synchronize to access shared resources.
Consider an application in which a single plane or space is divided among multiple threads, perhaps so they can calculate the spread of a life form (such as in the SimLife computer game) or changes in temperature as heat radiates across geographies from a source. Each thread can calculate one delta of change. However, because the results of each thread's calculations require the adjustment of the bounds of the next thread's calculations, all threads must synchronize afterward to exchange and compare each other's results. This is a classic example of a peer model application.
Pipeline Model
The pipeline model assumes:
 A long stream of input
 A series of suboperations (known as stages or filters) through which every unit of input must be processed
 Each processing stage can handle a different unit of input at a time
An automotive assembly line is a classic example of a pipeline. Each car goes through a series of stages on its way to the exit gates. At any given time many cars are in some stage of completion. A RISC (reduced instruction set computing) processor also fits the pipeline model. The input to this pipeline is a stream of instructions. Each instruction must pass through the stages of decoding, fetching operands, computation, and storing results. That many instructions may be at various stages of processing at the same time contributes to the exceptionally high performance of RISC processors.
In each of these examples, a pipeline improves throughput because it can accomplish the many different stages of a process on different input units (be they cars or instructions) concurrently. Instead of taking each car or instruction from start to finish before starting the next, a pipeline allows as many cars or instructions to be worked on at the same time as there are stages to process them. It still takes the same amount of time from start to finish for a specific car (that red one, for instance) or instruction to be processed, but the overall throughput of the assembly line or computer chip is greatly increased.
Figure 2-3 shows a thread pipeline.
Figure 2-3: A thread pipeline
As the pseudocode in Example 2-4 illustrates, a single thread receives input for the entire program, always passing it to the thread that handles the first stage of processing. Similarly a single thread at the end of the pipeline produces all final output for the program. Each thread in between performs its own stage of processing on the input it received from the thread that performed the previous stage, and passes its output to the thread performing the next. Applications in which the pipeline might be useful are image processing and text processing or any application that can be broken down into a series of filter steps on a stream of input.
Example 2-4: Pipeline Model Program (pseudocode)
main()
{
  pthread_create( ... stage1 )
  pthread_create( ... stage2 )
  .
  .
  .
  wait for all pipeline threads to finish
  do any clean up
}
stage1()
{
forever {
         get next input for the program
         do stage 1 processing of the input
         pass result to next thread in pipeline
         }
}
stage2()
{
forever {
         get input from previous thread in pipeline
         do stage 2 processing of the input
         pass result to next thread in pipeline
         }
}
stageN()
{
forever {
         get input from previous thread in pipeline
         do stage N processing to the input
         pass result to program output
         }
}
We could add multiplexing or demultiplexing to this pipeline, allowing multiple threads to work in parallel on a particular stage. We could also dynamically configure the pipeline at run time, having it create and terminate stages (and the threads to service them) as needed.
Note that the overall throughput of a pipeline is limited by the thread that processes its slowest stage. Threads that follow it in the pipeline cannot perform their stages until it has completed. When designing a multithreaded program according to the pipeline model, you should aim at balancing the work to be performed across all stages; that is, all stages should take about the same amount of time to complete.

Previous SectionNext Section
Books24x7.com, Inc 2000   Feedback