Re: Concurrency always is non-deterministic?

[Niklas Holsti <niklas.holsti@tidorum.invalid>]

On 12-02-13 19:41 , Long Hoàng Đình wrote:
> The author of this post said so. If Ada were non-deterministic at concurrency, I guess it couldn't be real-time, right?
>
> http://ghcmutterings.wordpress.com/2009/10/06/parallelism-concurrency/
>
> Please let me know your opinions about that post.

It is a nice and clear position statement, with its own definitions of 
the terms.

The author's main point is that when a program is multi-threaded (or 
multi-tasked, in Ada terms), with tasks that can have side effects on 
shared data, then the results computed can depend on the order in which 
the tasks are scheduled and executed (on one or several cores). This is 
what the author calls "non-deterministic" concurrent execution. As the 
author says, to write such a program, the programmer must usually make 
careful use of task synchronization and control access to shared data. 
Ada has nice high-level features for that.

On the other hand, if all computations use only private data (and do not 
include non-deterministic data such as inputs or clock readings in their 
computations) then the end result does not depend on the order or timing 
of the computations (whether divided into tasks or not), even if they 
are executed in parallel on many cores. This is what the author calls 
deterministic parallel execution. In other words, the programmer does 
not have to consider task scheduling or synchronization; that is handled 
by the compiler and run-time system.

However, for most real-time programs "non-determinism" in the author's 
sense is desirable, because the results of the computation are 
*required* to depend on timing, inputs, and clock-readings. Moreover, in 
real-time programs, tasks must be executed at certain times, as 
specified in the program -- whether or not the tasks share data.

The right conclusion is therefore the opposite: using the author's 
terms, "deterministic parallelism" is unusable for real-time systems, 
because real-time systems must be "non-deterministic".

Note that the author's term "non-deterministic" does not imply 
"unreliable" or "unpredictable".

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .