Re: Threading - How its done?
Re: Threading - How its done?
- Subject: Re: Threading - How its done?
- From: Jens Alfke <email@hidden>
- Date: Wed, 7 May 2008 09:34:46 -0700
On 7 May '08, at 6:13 AM, Army Research Lab wrote:
As for why threads are 'hard'; in reality, they aren't hard, as long
as
you are absolutely fastidious in following the rules:
The same thing could be said of any programming task :) But
fastidiously following the rules is itself very hard; the growing
opinion is that it's actually too hard for humans (let alone
computers) to do this for any nontrivial program. That certainly
matches my experience working on the Java class libraries for Mac OS
X, where we were plagued with by deadlocks and race conditions in AWT
despite our best attempts to follow the rules.
The paper "The Problem With Threads" by Edward Lee (a senior professor
at UC Berkeley) is good reading. Its thesis is:
For concurrent programming to become mainstream, we must discard
threads as a programming model. Nondeterminism should be judiciously
and carefully introduced where needed, and it should be explicit in
programs.
Unfortunately the paper succeeds better at demolishing the case for
threads than it does at nominating a replacement, although some
interesting techniques are discussed in the second half. I'm currently
investigating the Actor model, which is used in some heavily
concurrent languages like Erlang, Io and Scala; I'd like to implement
it for Cocoa.
When I use threads nowadays, I try to avoid sharing any state. Pass
all necessary data to the thread as part of initializing it (via an
NSOperation instance, or -performSelectorInBackground:), make sure the
initializer copies any mutable data, and make sure the thread doesn't
use anything external. The caller on the main thread can then fetch
results out of the NSOperation when it's finished; or the thread can
use -performSelectorOnMainThread: to send results back.
But having multiple threads traipsing around through the same code and
the same objects leads to madness.
Some other great quotes from Lee's paper:
From a fundamental perspective, threads are seriously flawed as a
computation model because they are wildly nondeterministic, as the
"Nondeterminism and Threads" sidebar describes. The programmer's job
is to prune away that nondeterminism. We have developed tools to
assist in the pruning: Semaphores, monitors, and more modern
overlays on threads offer the programmer ever more effective
pruning. But pruning a wild mass of brambles rarely yields a
satisfactory hedge.
To offer another analogy, a folk definition of insanity is to do the
same thing over and over again and expect the results to be
different. By this definition, we in fact require that programmers
of multithreaded systems be insane. Were they sane, they could not
understand their programs.
Moreover, implementing a multithreaded computation model is
difficult. Witness, for example, the subtleties with the Java memory
model, where even astonishingly trivial programs produce
considerable debate about their possible behaviors.
And an alarming story about a multithreaded Java app designed very
rigorously by concurrency experts, which hit a serious threading bug
four years after being thought bug-free:
Part of the Ptolemy Project experiment sought to determine whether
we could develop effective software engineering practices for an
academic research setting. We developed a process that included a
four-level code maturity rating system (red, yellow, green, and
blue), design reviews, code reviews, nightly builds, regression
tests, and automated code coverage metrics. We wrote the kernel
portion that ensured a consistent view of the program structure in
early 2000, design reviewed to yellow, and code reviewed to green.
The reviewers included concurrency experts, not just inexperienced
graduate students.
The Ptolemy II system itself became widely used, and every use of
the system exercised this code. No problems were observed until the
code deadlocked in April 2004, four years later.
Our relatively rigorous software engineering practice had identified
and fixed many concurrency bugs. But that a problem as serious as a
deadlock could go undetected for four years despite this practice is
alarming. How many more such problems remain? How long must we test
before we can be sure to have discovered all such problems?
Regrettably, I must conclude that testing might never reveal all the
problems in nontrivial multithreaded code.
—Jens
Attachment:
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden