Can a multi-threaded program ever be deterministic?

Knowing the algorithm will not actually allow you to predict what will happen when. All kinds of delays that happen in the execution of a program or thread are dependent on environmental conditions (free RAM -> swapping, other busy tasks, interrupts coming in, etc.).

Up vote 2 down vote favorite share g+ share fb share tw.

Normally it is said that multi threaded programs are non-deterministic, meaning that if it crashes it will be next to impossible to recreate the error that caused the condition. One doesn't ever really know what thread is going to run next, and when it will be preempted again. This off course has to do with the OS Thread scheduling algorithm and the fact that one doesn't know what thread is going to be run next, and how long it will effectively run.

Program execution order also plays a role off course, etc... But what if you had the algorithm used for Thread Scheduling and what if you could know when what thread is running, could a multi threaded program then become "deterministic", as in, you'll be able to reproduce a crash? Multithreading non-deterministic link|improve this question asked Sep 30 '10 at 12:10Tony The Lion12.7k32375 76% accept rate.

Maybe in the furture, in some machine it's not allowed multithreaded programming, there's some library framework for simulating multithreaded environment, then you can trace back and reproduce the bug. – coolkid Sep 30 '10 at 14:02.

Knowing the algorithm will not actually allow you to predict what will happen when. All kinds of delays that happen in the execution of a program or thread are dependent on environmental conditions (free RAM -> swapping, other busy tasks, interrupts coming in, etc.). -If- you were to map your multithreaded program to a sequential execution, and your threads in themselves are deterministic in their behaviour, then your whole program could be deterministic and 'concurrency' issues could be made reproducable.

Of course, at that point they would not be concurrency issues any more. If you would like to learn more, en.wikipedia.org/wiki/Process_calculus is very interesting reading.

1 I wrote a translator from C to CSP(a kind of Process_calculus) use in PAT tool(comp.nus.edu. Sg/~pat/). There're some Model checkers outthere for you checking your concurrent program.

– coolkid Sep 30 '10 at 14:06.

My opinion is: technically no (but mathematically yes). You can write deterministic threading algorithm, but it will be extremely hard to predict state of the application after some sensible amount of time that you can treat it is non-deterministic.

2 So better stated, you answer is: "mathematically, yes. Practically, no. " – San Jacinto Sep 30 '10 at 12:18.

There are some tools (in development) that will try to create race-conditions in a somewhat predictable manner but this is about forward-looking testing, not about reconstructing a 'bug in the wild'. CHESS is an example.

Lots of crashes in multithreaded programs have nothing to do with the multithreading itself (or the associated resource contention).

But I'm talking bout those that do have to do with multi threading. – Tony The Lion Sep 30 '10 at 12:19.

Normally it is said that multi threaded programs are non-deterministic, meaning that if it crashes it will be next to impossible to recreate the error that caused the condition. I disagree with this entirely, sure multi-threaded programs are non-deterministic, but then so are single-threaded ones, considering user input, message pumps, mouse/keyboard handling, and many other factors. A multi-threaded program usually makes it more difficult to reproduce the error, but definitely not impossible.

For whatever reasons, program execution is not completely random, there is some sort of repeatability (but not predictability), I can usually reproduce multi-threaded bugs rather quickly in my apps, but then I have lots of verbose logging in my apps, for the end users' actions. As an aside, if you are getting crashes, can't you also get crash logs, with call stack info? That will greatly aid in the debugging process.

It would be possible to run a program on a virtual multi-threaded machine where the allocation of virtual cycles to each thread was done via some entirely deterministic process, possibly using a pseudo-random generator (which could be seeded with a constant before each program run). Another possibly more interesting possibility would be to have a virtual machine which would alternate between running threads in 'splatter' mode (where almost any variable they touch would have its value become 'unknown' to other threads) and 'cleanup' mode (where results of operations with known operands would be visible and known to other threads). I would expect the situation would probably be somewhat analogous to hardware simulation: if the output of every gate is regarded as "unknown" between its minimum and maximum propagation times, but the simulation works anyway, that's a good indication the design is robust, but there are many useful designs which could not be constructed to work in such simulations (the states would be essentially guaranteed to evolve into a valid combination, though one could not guarantee which one).

Still, it might be an interesting avenue of exploration, since large parts of many programs could be written to work correctly even in a 'splatter mode' VM.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.