algorithmic view of multi-threaded systems

  • Permalink
  • submit to reddit
  • Email
  • Follow


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
          ->attach(
              // post the input
              agent_pnt(
                  start<agent>()->out<int>()
              )
              // OR post 'done'
              +agent_pnt(
                  start<agent>()->out<done>()->stop()
              )
          )
      );
      input_agent->repeat(); //repeat indefinitely

      //console output agent
      agent::agent_pnt output_agent(
          // output the input
          agent_pnt(
              start<agent>()
              ->in<int>()  //wait for the next input
              ->act( cons_output, "console_output" )  //action
          )
          // OR wait for 'done' and stop
          +agent_pnt(
              start<agent>()
              ->in<done>()->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.

Thanks,
Eugene

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

0
Reply E 6/30/2005 11:07:34 AM

See related articles to this posting
comp.lang.c++.moderated 10589 articles. 6 followers. Post

0 Replies
139 Views

Similar Articles

[PageSpeed] 54

Reply:

Similar Artilces:

Unblocking System.in in a multi-threaded app
Hello everyone, I am writing a multi-threaded application. One thread in particular is waiting for input from the server console using System.in. In some cases one of the other threads may encounter an error condition and force the shutdown of the system. All threads terminate correctly except for my Console input thread. This thread continues to run as it is still waiting for input from the console. How do I unblock this thread without input from the console? Code follows. BufferedReader serverInput = new BufferedReader(new InputStreamReader(System.in)); String inputLine = ""...

Tcl threads in Multi-CPU systems
I have read previous posts but it is still unclear : Can Tcl threads be dispatched to different CPU in a multi-CPU computer? Here is why I'm asking the question : I have built a Tcl application that interpolates 3Dimensionnal data. The application is build in the following manner : - An extension written in C has the code to perform the interpolation and do the IO. The library is thread safe. It has been tested with multi-threaded C programs. - A Tcl interface to that library ( The interpolation extension ) provides acces to the interpolation and IO functions via Tcl commands. The d...

System Calls Hang in Multi-Threaded Webcrawler
I'm writing a multi-threaded web crawler designed to periodically archive all the documents on my University's web server. The crawler is written in C++ on a system running Ubuntu 6, and uses standard POSIX threads (pthreads). Problem: When I run a certain number of threads concurrently, (usually around 30), a handful of threads will hang indefinitely on system calls, such as recv(), or sleep(). I tried numerous methods to handle this problem. I use non-blocking sockets, and even created a background thread monitor which tracks threads, so that hanging threads can be identified. ...

measure consumed time in multi-thread system
hi, I got a muti-threaded system, and I want to measure the whole used to tranverse the system, I mean packet processing actually. As it's a multi-threaded system, if I output the time difference between leaving and entering system to output: 1. whether the output operation will consume a lot of time itself? 2. whether multiple threads will cause race conditions to the output buffer? How to solve them? Thanks. Hi, I recommend you store the time metrics in thread-specific storage (e.g., via ACE_TSS), which will eliminate locking overhead. You could store the met...

Scaleable multi-threaded allocator solutions for embedded systems with NO heap...
You can create a single threaded allocator (e.g., try to do so without using any static's)... In other words, the invention needs to be able to "create" an allocator on a strictly per-thread/cpu basis. So, I need an explicit constructor function-pointer to "your" extern "C" declared method/static-func in order to render a viable pointer for my library to cache "and" use. I need function pointer to your single-threaded static variable free "heap" object constructor. After that, the rendered impl, (e.g., rendered wrt our discussions o...

Using the system command to launch a multi-threaded PC executable
I have a Windows executable file that runs stochastic simulations as separate threads and then averages the results together at the end. I would like to run the simulations from MATLAB using the system command. Everything works fine if I run the 4-threaded version of the executable but the executable returns early (without reporting an error) if I try to run 5 or more threads. I suspect that this is because my Windows 7 machine has 4 cores and maxNumCompThreads (see http://www.mathworks.com/help/techdoc/ref/maxnumcompthreads.html) is therefore equal to 4. Is there a way of successfully laun...

call of system(const char*) crashes in multi-thread-application
Hello Readers, (Linux 2.4.10, pthread library) I have the problem, that any call of the ansi c function "system", which should execute a program, crashes my multithreaded application (It just hangs or exits the application without any error message). If I call "system(const char*)" just before creation of the threads (5 to 10), everything works fine. It does not matter, what I call (script, invalid command, application). Is there a problem with multiple threads? Greetings Ernst Murnleitner "Ernst Murnleitner" <mur@awite.de> wrote ...

Hyperthreading & multi-threaded driver causes system crash!
Hi, I am working on a multi-threaded NDIS WDM driver. It runs fine on a Dual Xeon based system (with both processors enabled) and has passed an entire suite of tests. But when Hyperthreading is enabled (even with the second processor disabled), the system hangs. The problem is - I can't even break in with the debugger (SoftICE - DriverStudio 3.0) at this point - have to cold boot the system. Are there any special considerations for supporting Hyperthreading in device drivers? Regards, Kishore No issues. Hyperthreading is the same as SMP in software, and any driver mu...

Change Multi threaded DLL to Multi threaded
Hi, If I redistribute an app which is built with the "Multi threaded DLL" option (windows), can I be sure that the user has all the necessary run-time DLL files on his/her computer? I want to build the calendar sample as a Multi threaded instead of Multi threaded DLL, to get rid of run-time dll depencies. When I change the code generation setting in MS Visual C++ 2008 Express Ddition to Multi threaded, I get lots of link errors, for example: Error 1 error LNK2005: _free already defined in LIBCMTD.lib(dbgfree.obj) MSVCRTD.lib Error 2 error LNK2005...