Testing and static analysis for concurrency errors

See the book: The Architecture of Concurrent Programs by Per Brinch Hansen (1977). He presents there three concurrent programming example. It is written and documented by a fairly competent person.

Reproducible behaviour, i.e. eliminating non-determinacy for the test.

You can find some initial effort in this from me on another discussion forum. It is not completed yet, in fact there is a known bug left behind, but in turn I am going to continue it by applying some form of mocking at the testing of the scheduling.

TDD for multi-threaded programs

(You might check a cached version where the indentation is preserved for the code fragments, e.g.

Best Regards, Szabolcs

snipped-for-privacy@yahoo.com schrieb:

Maybe you can look for process controlling or measurement controlling software. If the setup to control is complicated enough then rather tricky concurrency issues are not that uncommon. There are many asynchronuous events if component protection, user interaction and maybe unpredictable measurement results affect the control flow. Real time software for nuclear physics experiments are sometimes in this range. Of course, it is unlikely the you will find a real world application which will also fit to your condition d).

mostly true.

Well, in theory there are ways to describe the coverage, but nobody wants to know the number since it will be close to zero. In fact yo have to run the code with any possible thred swichtching which is of course not possible. And if it would be possible than many of the the testcases are that unlikely that they likely will never happen while our universe exists. I think the coverage in terms it is used for convetional unit testing is not the significant value.

I would wonder if this changes this way. In fact the times where it was possible to prove that a software works is gone a long time ago. We should better think on how we deal with software that is /not/ free of faults. This is much closer to the reality and not that susceptible to systematic errors of all kind. Of course, this will not remove the need for well written software, but it may give another point of view to bugs in general. Not their existance is a problem but the probability of their occurence.

From my experience especially including code written from other people data races are the most common threading bugs. Maybe because deadlocks are very obvious, once they occur. In contrast wrong results are often taken as they are without thinking twice. "If the pocket calculator say

2+2=5 then this must be true." Other sources of bugs are that the programmers somtimes do not realize the locality of their objects. Things like thread local data, session data and so on are intermixed if the dependencies ares not that obvious.

More helpful than (complicated) tests or at leat an important part would be a threading support at language level. If the association of an object to a thread or a mutex is (implicit?) part of the declaration, compiletime checks would be possible that could check for some of the most common threading issues. Debug versions of the runtime environment could verify that the objects that are read or written to are not potentially accessable by other readers or writers in the meanwhile in an unallowed way. At least for high level languages like java this should be possible. I do not know any /common/ language the really supports threads beyond the library level. Of course the programmer still will have the job to put semantically dependant objects into one logical object. But this is close to OOP concepts anyway.

Marcel

... snip ...

How about Ada?

--
 
 
 
                        cbfalconer at maineline dot net

Are you considering concurrency issues on a single processor or concurrency issues across multiple processors?

For the former, there would be plenty to look at in some of the embedded control projects that deal with lots of individual interface.

For the latter, there may not be much about, but the shared computing resource projects may be best to look at in this category.

--
********************************************************************
Paul E. Bennett ....................
Forth based HIDECS Consultancy .....
Mob: +44 (0)7811-639972
Tel: +44 (0)1235-811095
Going Forth Safely ..... EBA. www.electric-boat-association.org.uk..
********************************************************************

I would check out what PolySpace have been doing. They have pretty advanced static and run-time analysis tools and are likely to have looked at the sort of things you are asking about.

Whilst their tools are too expensive for the size of my projects, they did give away the best freebies at the Embedded Systems Show and so I am always happy to give them a plug!

In a post timestamped Sat, 07 Jul 2007 09:53:44 -0000, snipped-for-privacy@yahoo.com posted: "[..]

The second question is: what features would you like to see in a testing tool for concurrent software? My understanding is that concurrency testing in the real-world setting is really stress testing, and that there are no good notions of coverage. [..]"

Apparently some properties of Plan9 were verified with Spin, but a post timestamped 22 May 2007 08:56:24 -0700 in news:comp.specification.misc ( Message-ID:

) is not encouraging: "Hello.

A colleague and I are trying to use SPIN to find all the potential error paths in a model. As near as we can tell, this is hard to do without getting lots and lots of redundant results. We have the following never claim:

never { /* p */ T0_init: if :: (1) -> goto T0_init :: (p) -> goto accept_all fi; accept_all: skip }

We use "spin -a foo.pml" followed by "gcc -o pan -DSAFETY pan.c", and then run "pan -c -e". A simple example that should have two unique error paths gives tens of thousands of trails. I understand that we will see some redundancy because, e.g., some process will change state after the condition p has been violated, but before this is detected, but this seems completely out of hand. Are we missing something? Better yet, is there a switch that tells spin/pan to do what we want?

Thanks.

-- Durward McDonell snipped-for-privacy@jhuapl.edu "

Regards, Colin Paul Gloster

P.S. Good luck. You will need it. You may also wish to try the comp.parallel.* newsgroups.

In news: snipped-for-privacy@n60g2000hse.googlegroups.com timestamped Sat, 07 Jul 2007 11:32:10 -0000, Szabolcs Ferenczi posted: "On Jul 7, 11:53 am, snipped-for-privacy@yahoo.com wrote: [..] > The second question is: what features would you like to see in a > testing tool for concurrent software? Reproducible behaviour, i.e. eliminating non-determinacy for the test. You can find some initial effort in this from me on another discussion forum. It is not completed yet, in fact there is a known bug left behind, but in turn I am going to continue it by applying some form of mocking at the testing of the scheduling. TDD for multi-threaded programs

(You might check a cached version where the indentation is preserved for the code fragments, e.g. Best Regards, Szabolcs"

Szabolcs,

This seems to be good. I do have a reservation however.

From

:"[..]

Step 1: A thread should be suspended on an empty buffer

@Test public void parSuspendOnEmptyBuffer() throws InterruptedException { Thread t1 = new Thread() { public void run() { q.get(); }}; t1.start(); Thread.sleep(DELAY); assertEquals("Buffer is empty and thread is waiting on get()", Thread.State.valueOf("WAITING"), t1.getState()); t1.interrupt(); t1.join(); }

Note that the delay is inserted for the test to allow some time for the tester thread to stabilize. This way we can make the test deterministic.

[..]

1. I don't like to see `Thread.sleep(DELAY);' in production code

[..]

His idea was to allow enough time for the processes to stabilise by using a virtual clock on which the test processes could synchronise. So we know that at each tick of the virtual clock which state we are at. I used explicit delays for simplicity. [..]

[..]"

How do you test production code?

Also, what penalties can be expected in the Globally Asysnchronous Locally Synchronous (GALS) paradigm?

Regards, Colin Paul Gloster

I have shown an example for production code test in that demonstration. Although, I have written the test before writing the production code. (Note that it is not finished yet.)

I never heard about that paradigm but I have looked it up. It looks to me that it applies to hardware blocks that have different clock sources. So, I would say the idea is the same: As far as I could conclude from the stories of the hardware guys, in the GALS paradigm, the clocks are also synchronised during the test. Just as I have suggested: make the system deterministic for the test.

Best Regards, Szabolcs