Cooperating components design pattern

From 1993 to 2004, I led the developpement of various real-time business systems for fleets of connected vehicles: taxis, public transportation buses, ambulances, etc. Functions provided by each system were specified and implemented according to the requirements of each customer. But underlying technical architecture and design were partly shared: embedded device (hardware and lower software layers), communication protocols, application software components (Geographic Information System functions, permanent storage functions, etc.)

Software code had to be developed for several different targets (mainly: embedded device running our proprietary kernel and runtime libraries, PC running Microsoft Windows, PC running Linux). Consequently, it was not possible to reuse code. But design patterns fitted well this type of context.

This article describes a pattern we used intensively. Before going through its description, keep in mind that our target environments were very different. Our embedded device had 32 KB of program memory and 4 KB of RAM, with an 8-bit processor using an 8 MHz clock. Which is fairly enough when you are an experienced embedded developer, but had to be taken into account when defining a technical architecture. Another point: when we started developing our first systems, the Gang of Four's book had not been published yet. And we discovered it (and design pattern concept) only several years after its publication. This explains why we simply reused existing patterns...

So, what type of problems our pattern tries to solve? To better understand the intent, let's take an example, the one of a taxi dispatch system:

• in each taxi, the on-board application had to:
  • manage the radiocommunication link
  • decode location data generated by the GPS receiver, format it and deliver it to various other functions that required it
  • handle incoming customer requests dispatched by the central dispatch office
  • maintain a buffer of last received requests
  • handle interface with taximeter, modifying taxi availability state accordingly
  • handle alarm button
  • handle driver user interface
  • etc.
• at central dispatch office, the application had to:
  • manage the radiocommunication link
  • handle interface with the PBX
  • mirror every taxi state
  • select the right taxi for a given customer request
  • manage customer request handling, for a given taxi (the taxi driver could reject a request)
  • manage bookings
  • display location of a taxi in real-time
  • etc.

As it can be seen from this example, every computing device has to run a lot of concurrent tasks. As you certainly know, writing correct concurrent programs is hard. Our design pattern copes with a part of this problem using a message-passing scheme.

Using a message-passing scheme alleviates part of concurrency complexity: synchronized access to shared data can be implemented very easily. It does not prevent from liveliness hazards, but it helps in decreasing their number. To summarize: beware, our solution is not miracle! But it really helps in building concurrent systems.

Overview

Every system function is implemented using one or more task. Every task is designed as a finite-state machine.

A transition is triggered only upon reception of a message. A message is generated by an event that can be either external to the thread, or internal to it.

Waiting for a message is a blocking operation. Or, said differently, the wait operation must not hog the processor. Sending a message to another task is never blocking.

The automaton should be back to an idle state after a finite amount of time.

Detailed description

The most important point in the implementation of this pattern relates to the message-passing mechanism: it must be concurrency compatible. The exact implementation depends on the target environment. With Borland Delphi and Microsoft Windows, we used some dedicated Windows system services. In Java, we used synchronized collections that appeared in JDK 1.2, and wait() and notify(). Using such data structures means that several messages may be sent "simultaneously" to one task. They are processed on a first-in first-out basis.

For our embedded device, in assembly language first, and in C later, we used flags and memory zones, protected by interrupt disabling.

The overall structure of one task, in pseudo-language, looks like this:

  currentState := IDLESTATE;

  while(true) do

    message := waitForMessage();

    switch(currentState) do
      ...
      case STATEx do
        switch(message.type) do
          ...
          case MESSAGETYPEx do
          ... 
          /* process message, switch to another state. */
          ...
          endCase  /* MESSAGETYPEx */
          ...
        endSwitch  /*message.type */
      endCase  /* STATEx */
      ... 
    endSwitch  /* currentState */

  endWhile

When a timed wait is required, a timer is started (in previous state), and timeout action is defined as generating a specific message. Thus, an asynchronous event generated by a timeout is handled the same way than other system events.

Every task is provided with a synchronized data structure (queue) that receives incoming messages. As already stated, this queue allows the task to get incoming messages on a first-in first-out basis. A control can be placed on the maximum number of messages that can be queued. When this limit is reached, any write operation returns an error.

At startup time, the application creates one queue per task. Then it creates the threads, passing to each one a reference to its receiving queue, and references to the queues it will have to send messages to.

A message contains a type, and some payload, depending on the type.

Conclusion

This simple design pattern helped us a lot in implementing reliable and easily-maintainable systems. It is not perfect, but it works well.

Among its drawbacks, one can list the fact that lot of attention must be paid to the definition of different tasks, associated states, and generated messages. And everything should be thoroughly documented...

Check this project on GitHub for a recent use of this pattern.