Re: Threading in new C++ standard
On May 1, 7:21 am, "Boehm, Hans" <hans.bo...@hp.com> wrote:
On Apr 30, 3:23 am, Szabolcs Ferenczi <szabolcs.feren...@gmail.com>
wrote:> On Apr 28, 8:42 pm, "Boehm, Hans" <hans.bo...@hp.com> wrote:
[...]
However, even if you go this route (and for many programs that's
fine), the problem does not go away completely. Consider
Thread 1:
x = 42;
lock(l);
Thread 2:
while (trylock(l) == SUCCESS) unlock(l);
r1 = x;
Is this allowable?
Not at all. It is not only a buggy concurrent program but a very
inefficient one too. It locks and unlocks an object while busy
waiting.
Does it guarantee r1 == 42?
Not in all circumstances. It is timing dependent, which is a typical
concurrent bug. Who can guarantee it that just when one thread is
locking on `l' another one would not overwrite `x' with another value.
The `x' is meant to be a shared variable but it is not accessed in a
safe way. It is a timing dependent construction and therefore an
unsafe one.
The answer can have
substantial effect on the cost of the lock() implementation.
My answer is that it has a concurrency bug and it must be fixed.
Besides, I do not think that the cost of an operation should have any
effect on the functional behaviour.
C++0x
resolves it in a new and interesting way.
How does C++0x resolve it then? I am curious.
How will you prevent another thread changing the value `x' as I
described above?
You can of course make this problem go away too by moving to ever more
restrictive languages, in which you can't express something like
trylock(), or cannot even express code that might involve races.
The lock does not belong to the language level unless you are dealing
with some kind of assembly level programming. In a high level language
you do not instruct the computer what to do rather you express the
conditions what you would like to achieve. Leave it to the compiler to
instruct the machine at a low level.
"There are two views of programming. In the old view it is regarded as
the purpose of our programs to instruct our machines; in the new one
it will be the purpose of our machines to execute our programs."
E.W. Dijkstra, Comments at a Symposium (1975)
https://www.cs.utexas.edu/users/EWD/transcriptions/EWD05xx/EWD512.html
I
think neither is practical, in that it doesn't let me write code that
commonly needs to be written, unless we abandon the shared-memory,
lock-based programming model altogether.
What you mean by a `restrictive language' is the one that restricts
you in committing the most common concurrent programming errors.
"Parallel programs are particularly prone to time-dependent errors,
which
either cannot be detected by program testing nor by run-time checks.
It is therefore very important that a high-level language designed for
this purpose should provide complete security against time-dependent
errors by means of a compile-time check."
C. A. R. Hoare, Towards a Theory of Parallel Programming (1971)
"Well, if we cannot make concurrent programs work by proofreading
or testing, then I can see only one other effective method at the
moment:
to write all concurrent programs in a programming language that is so
structured that you can specify exactly what processes can do to
shared
variables and depend on a compiler to check that the programs satisfy
these assumptions. Concurrent Pascal is the first language that makes
this possible."
Per Brinch Hansen: The Architecture of Concurrent Programs (1977)
I think all widely used
concurrent languages and thread libraries allow me to write both
trylock (or a lock with a timeout) and data races.
I would say that no decent concurrent programming language would allow
you to instruct the machine such a low level as locking. On the other
hand, low level thread libraries do allow you to write both trylock
and data races.
For example, I need to be able to write code that initializes an
object in one thread without holding a lock, makes a shared pointer p
point to it, reads p in another thread, and then access the referenced
object in the second thread, again without holding a lock. (The
accesses to p may be lock protected.) This involves no data race.
But it's hard to tell that statically.
It does involve a data race and there is a way to solve it. So, your
requirement is that one thread constructs an object, passes its
address to another thread, and the other thread has exclusive access
to it. Let us re-state the problem in a high level language notation:
shared struct {
Ob *x;
bool constructed;
} res {NULL, false};
Thread 1:
with (res) {
constructed = true;
x = new Ob();
}
Thread 2:
with (res) {
when (constructed == true) {
// manipulate x
}
}
Now it is up to an optimising compiler to insert locks or any other
means to implement mutual exclusion. We have just expressed by
language means what we are going to achieve. The rest is up to the
compiler.
I also need to be able to protect a bunch of objects with a smaller
set of locks, by hashing the object address to an entry in an array of
locks, or do hand-over-hand locking on a linked list.
I am 100% sure that the problem to be solved does not specify that you
must use locks.
The problem might require that you arrange your algorithm in a way
that those bunch of objects should be accessed in a mutually exclusive
way. Then it is better if the language allows you to express the real
requirement and you do not have to over-specify the solution. Nothing
prevents you to apply smaller granularity of mutual exclusion
specification as required by your problem so solve.
That does mean that we would like other tools to detect data races,
since the compiler can't do so. Unfortunately that seems to be hard
precisely because syntactic disciplines that preclude races are too
restrictive.
The compiler can do a lot of checks for you including preventing data
races provided the language is well designed with respect to
concurrency. The language must include means to mark shared variables
and Critical Regions. That is the key to it.
Best Regards,
Szabolcs