algorithmic view of multi-threaded systems

It seems like Alex Stepanov definitely hates
OO methods (STL isn't an OO stuff).
In one of his interview, he used rather harsh words toward the OO guys.
  From his point of view, software design should be driven by algorithms
not data structures. I agree with him.

C++ templates give us a tool (not a perfect one though) to do just that
including generic and meta-programming
(if they aren't the same:) methods.

However when it is time to implement a multi-threaded application,
the OO methods are typically creeping in.
It all starts with thread objects, synchronization objects
and gradually turns into a full blown OO system.

It is not clear how to prove such multi-threaded
OO systems or/and apply a math analysis to them.

So I decided to use the Alex's approach and
tried to look at the problem from the algorithmic standpoint.
There are relatively well formulated process algebras
to deal with concurrent systems.

One of them is Synchronous Calculus of Communicating Systems (SCCS).
The calculus is algorithmic in nature.
It allows a mathematical analysis of concurrent systems (to discover
deadlocks, etc.).
I got interested in what SCCS would look like if it were
to be expressed in C++.

Just as an experiment, I put together a small library, SCCS++.
It could be found at http://sourceforge.net/projects/tinytl
(look at the sccs namespace).

First let me give you a taste of SCCS equations.

      input_agent = console_input:(int!:input_agent + done!:[STOP])

It could be read as the following.

The 'input_agent' agent is defined as follows:
   - invoke action 'console_input' (read console input
     and convert it to 'int')
   - send message to the 'int' port and start over
     or send message to the 'done' port and stop.

Note that the symbol '!' indicates output ports.
The '+' symbol indicates choice.

We can also define an agent that accepts 'int' values and prints them
out to the console.

      output_agent = int?:console_output:output_agent + done?:[STOP]

output_agent is waiting for 'int' or 'done' messages.
If it is 'int', it prints the value by calling console_output
and starts over. If it is 'done', the agents stops.

Note that the symbol '?' indicates input ports.

Now we can combine the agents into

      full_agent = input_agent * output_agent;

full_agent consists of two agents input_agent and output_agent
operating concurrently and synchronizing on their input/output ports.

full_agent accepts the user input from the console and prints it back.

In general in SCCS, '*' indicates concurrency and '+' indicates
choice between agents.

In SCCS++, the above agents can be directly mapped to:

      //console input agent
      agent_pnt input_agent(
          start<agent>()  //start
          ->act( cons_input, "console_input" ) //action
              // post the input
              // OR post 'done'
      input_agent->repeat(); //repeat indefinitely

      //console output agent
      agent::agent_pnt output_agent(
          // output the input
              ->in<int>()  //wait for the next input
              ->act( cons_output, "console_output" )  //action
          // OR wait for 'done' and stop
      output_agent->repeat(); //repeat indefinitely

      // the full agent is a product of input_agent and output_agent
      // it means that input_agent and output_agent will run concurrently
      // (in different threads)
      agent_pnt full_agent( input_agent * output_agent );

Here input ports are presented by in<> function template and output
ports by out<>function template. Where the template parameter
is the type of the message (port name). Actions are provided
by act() methods. The '*' and '+' operators have the
same semantic as in the calculus (see above).

When you run full_agent, it will create all necessary
threads, synchronize on input/output ports and
make proper transitions and choices defined
by the equations. SCCS++ uses boost.threads

There is the 'print' function that can format structures
of SCCS++ agents into strings that look like normal
SCCS equations. The strings could be used for mathematical
analysis of agents.

If you download TTL from http://sourceforge.net/projects/tinytl,
you'll find a working sample.

I'd be very interested to get your feedback on
the whole concurrency thing.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

6/30/2005 11:07:34 AM
comp.lang.c++.moderated 10738 articles. 1 followers. allnor (8510) is leader. Post Follow

0 Replies

Similar Articles

[PageSpeed] 15