Re: [boost] Threads Review

From: Beman Dawes (bdawes_at_[hidden])
Date: 2002-10-16 16:03:49

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

 >I realize this is almost a year too late ;-), but I've been reviewing
 >the Boost.Threads documentation in detail and I have the following
 >comments. I also have a whole lot of editorial changes to suggest,
 >which I'll post separately as a patchset.

It looks like most of your comments are about definitions.html 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.

 >* "Thread-safe": this is a term which is well-defined for programs. It
 >  is /not/ well-defined for classes or functions, though the
 >  documentation uses it that way repeatedly. The definition
 >  (definitions.html) says:
 >
 >      "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

 >* 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.

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.

 >  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.

 >* 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.

 >* 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) and depends on the 
details of a particular interface.  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."

 >* 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.

Thanks for looking at definitions.html.  It needs all the help it can get!

--Beman