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
          ->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
E
6/30/2005 11:07:34 AM
comp.lang.c++.moderated 10705 articles. 11 followers. allnor (8507) is leader. Post Follow

0 Replies
202 Views

Similar Articles

[PageSpeed] 40
Reply:
Similar Artilces:

instructor solution manual for Linear dynamic systems and signals by Zoran Gajic
Here are instructor's solutions manuals to the scientific textbooks in PDF format. They cover solutions to all problems. If you need any, let me know its title, edition and author. If your title is not listed here don't worry because it is a list of some .. NOTE: This service is NOT free, and Don't reply here, instead send an email to: kalvinmanual( at )gmail(dot)com solutions manual to A Course in Game Theory by Osborne, Rubinstein solutions manual to A Course in Modern Mathematical Physics by Peter Szekeres solutions manual to A First Course in Abstract Algebra (7th Ed., John ...

ALGORITHM
// MATCHCASE // REPLACE1WITHLOREPLACE2WITH + // REPLACE WITH2 REPLACE2P2WITH2LZ REPLACE2NP2WITH2L0 ...

Scrolling muliple views in a view
I have the following problem: (MacOS 9.2.2, CW 8.2) Seem to be a newby.. I can easily put a picture or a texteditview into a scroller and bring it to scroll. But I cannot put the picture into a view and thisone into the scroller, I mean I can, but nothing happens. there is no scrolling, even when the window is smaller than the picture or view. The scrollbars are shown, but they are deactivated. What is going wrong? In C++, I realized scrolling without big problems. Ruedi Heimlicher ...

Algorithm Question
I have some stupid questions.... - Why would program 1 run a lot faster than program 2? Can someone explain? If I change the sample_size to be a larger one, program 2 will my browser freeze!! - What is the optimum value (1024 in this case) to use? Program 1: ----------- int sample_size = 5120; // 5K for (i=0; i < (sample_size/1024); i++) { my_buffer = ""; for (j=1; j<=1024; j++) { my_buffer += "a"; } my_data += my_buffer; } Program 2: ------------ int sample_size = 5120; // 5K for (i=0; i < sample_size; ...

Export View as CSV-File
Hi there ist there any possibilty to export a Notes-View to a CSV-File. If I click on "File"-"Export" my Client only offers "Tabular Text", "Structured Text" & "Lotus 123 Worksheet". Regards John Joe On 2 Jul 2003 05:13:02 -0700, jjp1@gmx.de (John-Joe Para) wrote: >Hi there ist there any possibilty to export a Notes-View to a >CSV-File. >If I click on "File"-"Export" my Client only offers "Tabular Text", >"Structured Text" & "Lotus 123 Worksheet". You can w...

CFP: DATICS 2008
Apologies for any multiple copies received. We would appreciate it if you could distribute the following call for papers to any relevant mailing lists you know of. CALL FOR PAPERS =========================================================== Special Session: Design, Analysis and Tools for Integrated Circuits and Systems DATICS 2008 July 22-24, 2008 (Crete Island, Greece) http://digilander.libero.it/systemcfl/datics ===================================...

[CFP] Special Issue of JPDC on: Architectures and Algorithms for Irregular Applications
Call for papers Journal of Parallel and Distributed Computing: Special Issue on: Architectures and Algorithms for Irregular Applications =20 Motivation =20 There is an emergence of data intensive, irregular applications for knowled= ge discovery in such diverse fields as cybersecurity, bioinformatics, Compu= ter Aided Design, machine learning, and the semantic analysis of complex so= cial, transportation, and communication networks. Knowledge discovery app= lications operate on web-scale data sets best represented as graphs using p= ointer- or linked list based data structures. C...

looking for timetabling algorithms
I am looking for timetabling algorithms in Matlab...using GA, ACO, and or SA (Simulated Annealing). Thanks in advance Meggie ...

Q: Code for Eclipse view
Sorry if this isn't the right group for this question... I am considering converting a large Swing application to SWT. We use the MDI pattern. I know that SWT does not support this pattern, but I really like the way Eclipse allows the user to drag tabs to create new split windows and then back to being just tabs on a single pane. Is there sample code for doing this (or where in the Eclipse source code is this implemented)? Thanks, Ralph grk@usa.net wrote: > Sorry if this isn't the right group for this question... > > I am considering converting a large Swing applicatio...

"Cut view" of assembly
I have an assembly and would like to see it "as if cut at a plane" - it would in this case be at a plane along a shaft centre line. How is that done? You can use the section tool, or you can actually cut it using the Insert>Cut with Surface feature and use a plane (or a surface) as your surface. HTH, Muggs "steve" <steve@nomail.com> wrote in message news:ipAXe.312$EE6.177@news.get2net.dk... >I have an assembly and would like to see it "as if cut at a plane" - it > would in this case be at a plane along a shaft centre line. > > How is ...

Ruby Threads in Windows
Hi all. And thankyou in advance to anyone who responds. I am quite new to Ruby and am working on Windows. I need to spawn new threads in ruby on windows which I can do fine, and I can see them in the windows process list. Is there are way of getting the process ID back for a thread? I can not use the Process module as my threads need to run concurrently (and everythign I have read says I should be using threads) and every time I try the "fork" command I am told its not supported. I also looked at the windows-pr gem but so far no luck. If I can get the ID of the process that th...

Bitwise 2K7
BITWISE is an annual online programming contest. The contest is organized by the Computer Science and Engineering Department Society of IIT Kharagpur, on the second Sunday of February every year. The contest is time constrained and you would be expected to submit solutions to some of the toughest programming and algorithms challenges in a short span of 12 hours. Prizes worth 120,000 Rs or $2600 at stake. Visit http://www.bitwise.iitkgp.ernet.in for more details. Registrations close on February 4th. ...

[News] Patent System's Problems Highlighted: How Taxpayers Punish Themselves
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Why Does The US Gov't Get To Patent Research Paid For By Public Tax Dollars? ,----[ Quote ] | An anonymous reader links us to a report | from The National Institute of Standards and | Technology (NIST), which came out earlier | this year, that highlights how, in 2008, the | US government brought in $170 million (pdf) | by licensing federally (i.e., taxpayer- | funded) technology and patents to private | companies. `---- http://techdirt.com/articles/20100429/0214049233.shtml Will Cloud Computing Lead To Patent Liabili...

US-TX-Austin,: Firmware Developer, Real time embedded systems, C, File Systems (45338332402)
US-TX-Austin,: Firmware Developer, Real time embedded systems, C, File Systems (45338332402) ============================================================================================ Position: Firmware Developer Reference: JGG00044 Location: Austin, TX Duration: contract to possible perm Skills: BS in Computer Science/Electrical Engineering or Equivalent Experience Required: 5 years of experience Real time embedded systems High proficiency in C Strong knowledge of assembl...

8051 system development from scratch
Hi, I wan to develop a system with the 8051 Micro controller. I have used a development KIT in college days. In the Kit, it was mearly entering Op-codes and running the program. so, I am not aware of the system the Kit had. Now, i want to buy a 8051 and other required chips and i want to make a system. Can you people guide us, how to proceed. and how can i donwnload the File in to 8051. Ie., i need to donwload the program right? and how can i run ? Before that, do i need to try with some simultors? Thanks in advance. Regards, Muthu muthu_nano@yahoo.co.in (Muthu) wrote in news:28c66cd3....

What is gnuplot contour generation algorithm?
Can anybody gives some details on how gnulot generate contours given 2d gridded data? It is easy to think of very stupid ways. But I'm wondering how gnuplot make the contour generation fast and efficient? Thanks, Peng In article <1143766931.201722.303710@z34g2000cwc.googlegroups.com>, PengYu.UT@gmail.com <PengYu.UT@gmail.com> wrote: >Can anybody gives some details on how gnulot generate contours given 2d >gridded data? It is easy to think of very stupid ways. But I'm >wondering how gnuplot make the contour generation fast and efficient? http://cvs....

combination algorithm
Is there any combination parsing algorithm/source code available to handle the combination problem of inputting a sequence (using Q and N as delimiter): YGEQLGMREMVRNCMQDL and generating sequences: YGEQLGMREMVRNCMQDL YGE QLGMREMVRNCMQDL YGE QLGMREMVR NCMQDL YGE QLGMREMVR NCM QDL YGEQLGMREMVR NCMQDL YGEQLGMREMVR NCM QDL YGEQLGMREMVRNCM QDL "Ross" <kk-leung@cuhk.edu.hk> wrote in message news:cp9gqu$lud$1@justice.itsc.cuhk.edu.hk... > Is there any combination parsing algorithm/source code available to handle > the combination problem o...

Event objects Threading on Serial Port on Win32 #2
David: Tube el mismo problema que vos con el hilo del ejemplo de pyserial. Me paso que en Linux andaba bien, obvio, pero tenia un peque=F1o problemilla en Windows, tambi=E9n obvio. Lo solucione de la siguiente manera: Asi es el codigo original de la funci=F3n ComPortThread def ComPortThread(self): """Thread that handles the incomming traffic. Does the basic input transformation (newlines) and generates an SerialRxEvent""" while self.alive.isSet(): #loop while alive event is = true if self.ser.inWaiting() !=3D...

US-CA-Brea: Systems Support, Data Warehouse Solutions, Bus Intelligence; 7M (45341832408)
US-CA-Brea: Systems Support, Data Warehouse Solutions, Bus Intelligence; 7M (45341832408) ========================================================================================= Position: Systems Support Reference: SMC01944 Location: Brea CA Duration: 7M Skills: Data Warehouse Solutions Business Intelligence relational databases (Oracle a must) Business Intelligence tools (preferably Brio) data modeling tools such as Erwin, data modeling/architecture techniques (star schema ...

US-TX-Austin: Signal Processing Eng., C/C++, Matlab, Verilog, algorithm devel.; (45338414402)
US-TX-Austin: Signal Processing Eng., C/C++, Matlab, Verilog, algorithm devel.; (45338414402) ============================================================================================= Position: Signal Processing Eng. Reference: SMC01894 Location: Austin TX Duration: Perm Skills: 6 years of total industry experience or greater An in-depth knowledge of signal processing algorithm development A solid understanding of C/C++ and Matlab A solid understanding of Verilog or similar language Prior experienc...

Starting wxWin in a secondary thread
Hi I am writing a plotting library and I would like to allow computational programs to call the plotting routines without worrying about clearing the message queue etc for the plotting window. My idea is to start wxWindows in a secondary thread and listen for messages from the primary computational thread. My question is: is it possible to use wxThread to start wxWindows? I tried it and got an error about TLS not initialised. From the mailing list I see that this is because the thread stuff has not been initialised. The problem is that I want to call wxEntry in the secondar...

Mitel IP System DHCP Issues
Hi We have started to implement a MItel solution using 3300ICP controllers and 5201,5215 and 5220 handsets. Our network design is 2 w2k DHCP servers with multiple scopes set up and split over the 2 servers these include all the voice and data scopes. we have multiple stub vlans setup through 2 layer 3 switches (Allied Telesyn Rapiers) with Layer 3 interfaces on each vlan to allow routing between the vlans all vlans come back to the same to servers for DHCP using the IP Helper setup on the Rapiers. The problem is with the phones hanging at boot the boot method is below this is ta...

US-NY-New York: Solaris System Admin, EMC, DNS, Sendmail, Veritas, TCP/IP; 6M (45344732409)
US-NY-New York: Solaris System Admin, EMC, DNS, Sendmail, Veritas, TCP/IP; 6M (45344732409) =========================================================================================== Position: Solaris System Admin Reference: SMC02002 Location: New York NY Duration: 6M Skills: Strong skills in EMC, DNS, and Sendmail, Veritas Volume Manager/Filesystem, Veritas Cluster, VCS, Veritas Netbackup, TCP/IP, Shell scripting, NIS, Unix security Excellent communication skills Project management skills ...

The Blank Algorithm
// Window main # Window object called "main" // title "Main" # Initial value of attribute // width 600px # Initial value of attribute // /message (.*)/: # Pattern of a received message // status $1. # Action: send message to status // /quit/: // self halt. // Label status // background #CCCCCC // /.*/: // self.value $1. posted by http://www.meami.org ...

Noise reduction through multi-tracking
Hi. I'm vaguely aware that noise in a recording can be reduced by recording a sound (say on analogue) tape multiple times, and then mixing the multiple recordings together on playback. The noise should, to a degree, cancel, while the signal reinforces. I'm just wondering if there is a more technical description of this. Assuming that the noise is random, then adding together multiple sources of noise should cancel so that the noise level is not I simulated this with a very short program that generated multiple "tracks" of uniformly distributed (around zero) noise, then adde...