Re: [boost] Threads Review

From: David Abrahams (dave_at_[hidden])
Date: 2002-10-16 16:35:14

Beman Dawes <bdawes_at_[hidden]> writes:

> At 02:12 PM 10/16/2002, David Abrahams wrote:

> It looks like most of your comments are about definitions.html 

Just the first round...

> which I wrote originally, so I try for a least a few answers.
>
> But first let me mention that I've always been very dissatisfied with
> the page, so welcome someone else working on it.
> 
>  >      "while some thread-safety violations can be determined
>  >      statically at compile time, many thread-safety errors can only
>  >      be detected at runtime"
>  >
>  >  Reasoning/justification, please? I refuse to believe that there
>  >  exist thread-safety problems which can't be detected via careful
>  >  static analysis of the system without proof. Maybe you mean to say
>  >  that some kinds of mistakes can be prevented with compile-time
>  >  constructs, but some mistakes are logic errors which compilers have
>  >  no way to detect?
> 
> IIRC, there is a whole literature devoted to which kinds of
> thread-safety problems can be detected statically, and which
> can't. Some race conditions are non-deterministic. Locating some race
> conditions is known to be NP-hard.  The ACM digital library is a good
> place to start. For example, see
> http://portal.acm.org/citation.cfm?id=130623&dl=ACM&coll=portal&CFID=5137082&CFTOKEN=94824949

Sorry, but there's a big difference between "hard" and "not
computable". Why not just say that "many thread safety problems are
hard to detect at compile-time, and some have been shown to be
NP-hard", then provide the link above?

>  >* Thread State - I think the thread state distinction between "ready"
>  >  and "running" is a false one, since the system can move a thread
>  >  from "ready" to "running" at an arbitrary time, without provocation,
>  >  and the formal description of the library would be a lot simpler if
>  >  you just had a "running" state.
> 
> Others (Bill Kempf?) have made that same point.  However, the states
> are taken from "Programming with POSIX Threads", David R. Butenhof,
> Addison-Wesley, page 40. A must-read book. Don't let the title fool
> you, it is about way more that just POSIX.

OK, but I don't have time to read it right now ;-)

> Butenhof is probably the most acknowledged practical expert on
> threading. He is very smart, very experienced, and very focused on C
> and C++ threading issues. (He has been supportive of the Boost.Threads
> effort, by the way.) If you want to disagree with him, fine, but be
> warned that he has a very good track record.

I'm don't think that I'm disagreeing him. I'm sure his book covers
elements of threading (like scheduling) for which "ready" is essential
to understanding. However, I don't think it's relevant to
Boost.Threads.

>  >  Also, you use the term "processor" which is not defined either in
>  >  Boost.Threads or in the C++ standard. It is also not detectable by a
>  >  user program AFAICT (by time-sharing/context-switching, an OS can
>  >  implement as many "virtual processors" as it wants), so I suggest
>  >  it's meaningless and should be stricken.
> 
> I believe I have seen programs in the literature that can detect a
> second processor. Seems to me they deliberately created a race
> condition, and then tested to see if actually occurred. But if you can
> rewrite the text so that "processor" isn't needed, feel free to do so.

If you let me take out "running", I think it's easy. Actually, I think
it's easy anyway. AFAICT, the Boost.Threads interface doesn't ever
promise to act differently for uniprocessor and multiprocessor
systems, so there's no need to bring up the distinction.

>  >* The definition of "Starvation" gives me pause. Is there any way to
>  >  be more-precise about what's meant by "sufficient"?
> 
> Not completing enough work to allow the thread to finish x in a
> reasonable length of time? X is intuitively "the work it is supposed
> to be doing", but I'm not sure how to express that.

Me neither.

>  >* The definition of "accessible from multiple threads" is
>  >  unintuitive:
>  >
>  >        "An object [1.8, 1.9] is accessible from multiple threads if
>  >     it is of static storage duration (static, extern) [3.7.1], or if
>  >     a pointer or reference to it is explicitly or implicitly
>  >     dereferenced in multiple threads."
>  >
>  >  It would be better to change "is explicitly or implicitly" to "can
>  >  be".
> 
> Yes, that would be an improvement.
> 
>  > It would be even better to say something like:
>  >
>  >        "An object [1.8, 1.9] is accessible from multiple threads if
>  >     it is stored in the function object passed to a thread's
>  >     constructor, it is of static storage duration (static, extern)
>  >     [3.7.1], or if a pointer or reference to it is accessible from
>  >     multiple threads."
> 
> "it is stored in the function object passed to a thread's constructor"
> is redundant (since there is a pointer or reference) 

Actually it's meaningless since the function object is copied. If the
function object weren't copied, then it wouldn't be redundant, because
the datum would still be accessible from the invoking thread. I don't
know what you mean by "since there is a pointer or reference".

> and depends on the details of a particular interface.  

I don't know what you mean by that.

> It might be better to add a second sentence: "Note that in
> Boost.threads, the function object passed to a thread's constructor"
> is accessible from multiple threads."

But it isn't.

I suggest the following simple rewrite:

      "An object [1.8, 1.9] is accessible from multiple threads if it
   is of static storage duration (static, extern) [3.7.1], or if a
   pointer or reference to it is accessible from multiple threads."

End of story.

>  >* The second and fourth rows of the table in definitions.html seem
>  >  very wrong to me.
> 
> I tried to re-write the table twice, and gave up each time.  It needs
> to be re-written by someone better at core language wording than I am.
> 
> Before trying to rewrite it, please carefully study "3.4 Memory
> visibility between Threads" in Butenhof's book. Particularly the
> four basic rules he gives on page 40. That's what the table is
> trying (and failing miserably) to capture.

I doubt I'll get a copy before I have to leave for Santa Cruz. Okay,
fine, I just ordered mine.

> Thanks for looking at definitions.html.  It needs all the help it can get!
> 
> --Beman _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

-- 
                    David Abrahams
dave_at_[hidden] * http://www.boost-consulting.com
Building C/C++ Extensions for Python: Dec 9-11, Austin, TX
http://www.enthought.com/training/building_extensions.html