Re: Threading - How its done?
Re: Threading - How its done?
- Subject: Re: Threading - How its done?
- From: Army Research Lab <email@hidden>
- Date: Wed, 07 May 2008 13:33:37 -0400
- Thread-topic: Threading - How its done?
On 5/7/08 12:34 PM, "Jens Alfke" <email@hidden> wrote:
> 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.
I agree with this statement, and I want to point to you a few articles.
Read up on Mealy machines (http://en.wikipedia.org/wiki/Mealy_machine) and
Moore machines (http://en.wikipedia.org/wiki/Moore_machine), as well as HDL
(http://en.wikipedia.org/wiki/Hardware_description_language). Pay
particular attention to the section titled "HDL and programming languages".
Chip designers have had to contend with these problems for years, and
developed languages for expressing parallelism with implicit threading
already (everything in an HDL is parallel unless you carefully force it to
be sequential). We should be using ideas from those languages.
> 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.
http://en.wikipedia.org/wiki/Concurrency_pattern and
http://en.wikipedia.org/wiki/Actor_model. Actually, now that I've skimmed
the Actor pattern, I'd say that it looks very similar to how various HDLs
operate, and very much like what I was thinking of implementing on my own.
Hmmm... maybe I won't have to work that hard after all! :D
> 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.
It can lead to madness, but (at least in my experience), if you use queues,
you can model message passing (I'm talking about pthreads, not Cocoa, which
is why I have to make my own queues), which keeps the madness to a minimum.
The only times I've had real trouble is when I put something in the message
queue to another thread, but accidentally continued using the object; then
two threads were sharing it, and when one finally free()ed it...
> 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.
This tends to be true of single threaded programs as well though; as the
complexity increases, so do the chances for subtle bugs to creep in. Anyone
that has ever done a cast from integer to char array, or some other bit of
nastiness has seen it when they went from big-endian to little-endian
systems. That doesn't stop us from doing it though. I do agree that it
would be better to have a language that took care of this automatically; I
would like to treat objects, and even collections of objects (like arrays)
as atomic objects, guaranteed to have all writes fully visible to other
threads, and be modifiable in an incorruptible manner. But I'm not holding
my breath for that.
Thanks,
Cem Karan
_______________________________________________
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