Re: [boost] Design and documentation of Boost.Threads

From: Beman Dawes (bdawes_at_[hidden])
Date: 2001-11-11 15:47:46

At 02:09 PM 11/11/2001, Kevin S. Van Horn wrote:

 >I finally managed to eke out enough free time to finish reviewing and
 >commenting on the documentation for the Boost threads library (as a 
prelude
 >to attempting some formal correctness proofs.)  Here are my 
remarks.  They
 >include a mixture of comments on design, exposition, wording, and 
sometimes
 >grammar.

Thanks for your extensive comments.

I'm sure Bill Kempf will respond to the bulk of them, but I'll try for the 
couple of documentation pages that I wrote.

 >
 >DOCUMENT-SPECIFIC COMMENTS
 >==========================
 >
 >overview.html:
 >--------------
 >
 >Quote: "Priority failures (priority inversion, infinite overtaking,
 >starvation, etc.)"
 >
 >Comment: The programmer cannot do anything about priority inversion; that 

 >has to be addressed at the OS level.  I don't believe that "infinite
 >overtaking" and "starvation" are defined anywhere.  I'm not sure that
 >"priority failure"
 >is an appropriate term to describe starvation.  Absence of starvation 
just
 >means that a thread waiting its turn to do something does, eventually, 
get
 >its turn; the concept is meaningful even in the absence of any notion of
 >thread priorities.
 >
 >Quote: "Every multithreaded program must be designed carefully to avoid
 >race conditions and deadlock."
 >
 >Comment: I would add starvation to the list of things to avoid.  This is 
a
 >commonly-overlooked error in multithreaded code.
 >
 >Quote: "Common requirements for all Boost.Threads components."
 >
 >For implementors they are requirements, but for users (the great majority 

 >of those who will be reading the document) they are guarantees /
 >specifications.

In general I agree with all of the above, but what would really be helpful 
would be for you to supply your preferred wording, preferably in the form 
of a diff.

 >...
 >
 >definitions.html
 >----------------
 >
 >Quote: "Thread State." [Followed by definitions of "Ready" and "Running".
 >
 >Comment: You are getting into scheduler implementation details that have 
no
 >place in a behavioral specification.  The usual way of reasoning about
 >concurrent programs is that you assume nothing about the relative speeds 
of
 >different threads, and that arbitrarily long (but finite) delays may 
occur
 >at any point in the execution of a thread.  The change of state from
 >Running to Ready and then eventually back to Running again looks just
 >like an arbitrary pause in the execution of the thread.

The concept of the states came from Butenhof, and this allows the effects 
of various functions to be specified in terms of state changes.  IIRC, I 
followed his state transition diagram.  I'd have to see your proposed 
replacement wording to really understand what change you are proposing.

Some mention of assuming "nothing about the relative speeds of different 
threads, and that arbitrarily long (but finite) delays may occur at any 
point in the execution of a thread" would certainly be a nice 
addition.  There also should be some mention of the usual assumption that 
I've seen in the literature that while the scheduling mechanism is 
unspecified and unknown, it is assumed to be "fair".  I don't remember 
seeing a definition of "fair", however.

 >Quote: [Under "Race Condition"] "The result of a race condition may be a
 >bit pattern which isn't even a valid value for the data type."
 >
 >Comment: It's worth mentioning why this is so (see previous comment on
 >atomicity.)
 >
 >Quote: "A priority failure (such as priority inversion or infinite
 >overtaking)..."
 >
 >Comment: Need to define priority inversion and infinite overtaking.  Also 

 >need to define and discuss starvation.

Please send improved wording!

Thanks,

--Beman