Fw: OFFLIST and slightly OT (over, not off topic) Re: [boost] Boost.Threads Locking Delima

From: William E. Kempf (williamkempf_at_[hidden])
Date: 2002-05-16 13:51:17

----- Original Message -----
From: "Chris Russell" <cdr_at_[hidden]>

> Dear William,
>
> an interesting post. I'm writing you directly as my response shoots far
past
> your RFC and starts picking at some higher-level design issues related to
> working with threads and parallelism generally. If you feel this is an
> appropriate response to your post, please forward it on to the developers
> list for consideration. If not, then just something to think about.

I think the discussion is appropriate, so I'm forwarding this with my
responses to the list.

> Pulling way up from the specific details of threads and locking
mechanisms,
> scheduling, let me make a few seemingly trite obersations:
>
> - data dependencies within any system (be they in a single application
> running on a desktop or distributed across embedded systems or wired
across
> the web) can be modeled as graphs (as in the BGL).
> - given a graph G that represents the relationships between data in a
> system, and given some set of threads T that can operate on the data
> represented by the G's vertices, the problem reduces to scheduling the
> members of T so that they can safely operate on subgraphs of G.
>
> Synchronization primitives such as mutexes, critical sections, events,
> semaphors, spin-locks etc. are, by my way of thinking crude, low-level
> mechanisms for enforcing this scheduling. Using these primitives
effectively
> models G implicitly and the OS does the scheduling of the members of the
> thread set T. As we all know too well, once T has a few member threads,
the
> implicit approach becomes very, very costly in terms of time and developer
> brain cells.

First, I agree with this.  In fact, the documentation for Boost.Threads
explains why we have a low level design instead of a higher level design
such as you suggest here.  To put it in a nutshell, there are several higher
level designs that can be used more safely, can easily be proven correct and
probably are easier to program.  But all of these will generally be built on
the lower level primitives, so even if this is your only goal the low level
design is still important.  More importantly, a very large amount of code
exists written using the lower level primitives and there are many
developers familiar with them, so there's definite utility in having a
standardized/portable low level design even with out the goal of producing
higher level designs.

> I think what is really needed is to motivate some generic way to represent
> application data relationships using graph theory, and create new locking
> mechanisms that internally use graph algorithms to decide who can run and
> who must block at any given time. Viewed at this high-orbit level of
> abstraction, questions about exposing public lock/unlock on the mutex and
> the issues it raises about locking in one scope and unlocking in another
> would appear to beg the wrong question (at least for complex
multithreaded,
> and distributed applications).

I'd be excited to see you submit a higher level design to Boost.  But
regardless, I don't think I've "begged the wrong question" here.

> Forgive me if this is a lot more than what you were looking for - I've
been
> deeply involved in such issues lately struggling with an enormously
complex
> multithreaded client that talks to multiple distributed servers and have
> effectively given up on tracking race conditions and deadlocks in my
> internal graph structures. I've come to the conclusion that the only way
> I'll ever get it working is to formally take threading and synchronization
> sub-problem on directly as a graph problem in its own right.
>
> Comments?
>
> Thanks for a thought provoking post.
>
> - Regards
> Chris Russell

Bill Kempf