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 10620 articles. 8 followers. Post

0 Replies
147 Views

Similar Articles

[PageSpeed] 27


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 successfull...

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...

enable-threads with multi-threaded/multi-interp app but w/o tcl thread api?
Ive been searching for an answer to a basic question and have been unable to find it : If I have a multi-threaded C++ application with embedded tcl, using pthreads and each thread having its own tcl interpreter, do I need to build the tcl library with threads enabled? I am not using the TCL thread API, I am simply creating and using multiple tcl interpreters within separate pthreads(again, each thread having its own interp). From the Wiki ( http://wiki.tcl.tk/1339 ) Some consolidated rules for embedding Tcl in a threaded application: * You can NEVER use the same interpreter from more th...

enable-threads with multi-threaded/multi-interp app but w/o tcl thread api? #2
Ive been searching for an answer to a basic question and have been unable to find it : If I have a multi-threaded C++ application with embedded tcl, using pthreads and each thread having its own tcl interpreter, do I need to build the tcl library with threads enabled? I am not using the TCL thread API, I am simply creating and using multiple tcl interpreters within separate pthreads(again, each thread having its own interp). Hello JV, Am 26.06.11 17:39, schrieb JV: > If I have a multi-threaded C++ application with embedded tcl, using > pthreads and each thread having its own tcl inte...

multi threading, not unloading threads
ok, i found out that all sounds MUST be played in the main thread for some reason so here's what i've done detatch a thread that scans for the sound file and then loads it into an array when that thread is finished, it sets a boolean value saying the sound has been loaded. i then play the sound loaded in the main thread if the boolean flag is set it seems to work for me ok but counting the threads, it shouldn't have more than one thread running while it's playing. i have 9 running now. is this something else i have to contend with locating? -(void)pla...

Whether Tcl_FinalizeThread release the thread special data affect other threads or not in multi-threads enviornment.
--------------21A09B54FB79E8148CDFB499 Content-Type: text/plain; charset=gb2312 Content-Transfer-Encoding: 7bit -- Alex Wang IOTA Development, Lucent Qingdao(QD), R&D Tel:(Office) +86-532-8702000 ext.5371 Email:wangtianda@lucent.com http://gdcsvr.gdc.lucent.com/~alexw --------------21A09B54FB79E8148CDFB499 Content-Type: text/html; charset=gb2312 Content-Transfer-Encoding: 7bit <!doctype html public "-//w3c//dtd html 4.0 transitional//en"> <html> &nbsp; <pre>--&nbsp; Alex Wang IOTA Development, Lucent Qingdao(QD), R&amp;D Tel:(Office) +86-532-...

single threaded vs. multi threaded
1. Which programs lend themselves to be single threaded? 2. Which programs lend themselves to be multi threaded? 3. How to convert a multi threaded program to single threaded program? omar_hashmi786@yahoo.com wrote: > 1. Which programs lend themselves to be single threaded? > 2. Which programs lend themselves to be multi threaded? > 3. How to convert a multi threaded program to single threaded program? Sorry there are no general purpose answers to your questions. Get a book about mulitthreading and read the introduction. Normally this should help you to understand something about...

multi-processed VS multi-threaded
I started this discussion on the GT.M groups page on LinkedIn, but it doesn't seem to be getting much notice. Posting here hoping someone can comment. thanks.... Multi-processed vs Multi-Threaded My naive understanding of the difference between Multi-processed and multi-threaded applications is that multi-processed applications don't share process state, and multi-threaded applications do. Am I correct in my understanding of the two? Also, it is my naive understanding that GT.M can do multi-processing, but not multi-threading? Is this correct? thanks for your help... Michael I d...

multi threading in multi processor (computer)
Hello, Is anyone has experiance in running python code to run multi thread parallel in multi processor. Is it possible ? Can python manage which cpu shoud do every thread? Sincerely Yours, Pujo ajikoe@gmail.com a �crit : > Hello, > > Is anyone has experiance in running python code to run multi thread > parallel in multi processor. Is it possible ? > > Can python manage which cpu shoud do every thread? > > Sincerely Yours, > Pujo > There's just no way you can use Python in a multi-processor environment, because the GIL (Global Interpreter Lock) will ...

Multi Thread in Mathematica (not multi core)
Hi All I'm working in some web scraping using Mathematica, and today, to get velocity, I have to call bash commands inside Mathematica (xargs with parallel options with curl and wget). I would like to do All inside Mathematica, but I miss multi thread capability. I could use more cores, but it's not the answer because the leg is due to time lag, not lack of processor capacity. Some clue? Something new to Mathematica 9? I thought that would be natural to be multi thread if it's multi core. tks in advance Murta There is the code that I was looking for. CloseKernels[]; ...

Thread question
Here's a java problem I'm trying to work through. I wrote a program that solves a game a friend of mine calls the "Cracker Barrel Game" because he remembers it from restaraunts of that genre. There are 15 holes in a triangle with 14 pegs, as below. 0 p p p p p p p p p p p p p p You play by jumping over a peg and removing it, trying to get to just one peg. I implemented this with threads as follows: I wrote a class "game" implementing runnable and - in the run method - the object...

Performance Considerations for multi-core and multi-threading.
Hello, I plan to experiment a little bit with multi-core/multi-threading software and then I will see what happens. I have my doubts though for example: Suppose my software is split up into many little jobs/threads. This will lead to a certain kind of memory fragmentation. Then threads possibly cores need to pull in memory from all over the place. So I wonder what will happen then... maybe the cores still transferring lots of data back and forth which might reduce performance. Or maybe it's not so bad... maybe cores have enough L1 cache memory to store the little jobs/threads dat...

Moving multi threaded application to multi processing
**** Post for FREE via your newsreader at post.usenet.com **** Hi, This is the background of the problem. I have some code working in as multiple threads.For example SNMP Protocol is running as few threads,HTTPD running as few threads,switching application (layer 2 switching)running as few threads..etc. All the threads in HTTP or SNMP will communicate to the core switching thru a set of library calls. Since HTTP, SNMP are heavy processes.If some thing goes wrong in HTTP or SNMP thread, entire process will get effected. So if we have separate processes for HTTP and SNMP, problems in...

single threaded vs multi threaded programming
1. Which programs lend themselves to be single threaded? 2. Whcih programs lend themselves to be multi threaded? 3. How to convert a multi threaded program to single threaded program? omar_hashmi786@yahoo.com wrote: > 1. Which programs lend themselves to be single threaded? > 2. Whcih programs lend themselves to be multi threaded? A program doesn't lend itself to being single- or multi-threaded. It either is or isn't. However, there might be tasks for which a single-threaded solution would be better than a multi-threaded solution, or vice versa. > 3. How to convert a mult...

Multi-thread vs multi-process design
Hi, I would like to have your opinion about the following design problem (sorry, it is quite long but I tried to be as clear and complete as possible). Context: -------- For one week, I'm working for the development of a server responsible for configuring a park of equipments. The required performance goes til 400 simultaneous connections and a latence time of less than 3 sec (without taking into account the network). Each equipment sends a message of 2K and the server replies, using information stored in a DB, with a message of 20K. The server is a WIndows 200...

Closing only one view in multi-view SDI
Well, as I explained in an earlier posting, I decided to stick with the docview framework that comes with the wxWindows package. With quite a few derived classes and virtual functions, I managed to tailor a docview implementation that provides me what I want: single document with multiple views of that doc. Creation and manipulation works pretty well (including closing the doc), BUT... When I try to close only one view while the other view(s) are open, I get an access violation. The stack at that point looks as follows: wxNodeBase::GetData() line 169 + 10 bytes wxwxMenuItemListNod...

single threaded vs. multi threaded programming
1. What types of application are to be single threaded? 2. What types of application are to be multi threaded? 3. How to convert a multi-threaded program to single-threaded? omar_hashmi786@yahoo.com wrote: > 1. What types of application are to be single threaded? > 2. What types of application are to be multi threaded? > 3. How to convert a multi-threaded program to single-threaded? This is like asking "how do I build a bridge". It's so expansive and vague that it can only be answered with a short joke or a hundred page treatise. If you want general ...