Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk