threads (was Re: [gclist] Re: gclist-digest V3 #84)

[Jerrold Leichter]

| We don't have that safety extended all to cover issues of
| synchronization, unfortunately, and anything that could be
| checked and enforced mechanically would necessarily be
| less expressive than how people sometimes use synchronization.
| 
| For example, an "object" might be declared to be "synchronized
| by" some other object at some simple fixed relationship
| (as in "synchronized by this"), or it can be declared as
| "reached from synchronized" (to capture the notion of a tree
| or other linked data structure that is locked at its root),
| with the assumption that these things are checked and enforced
| by a compiler (or "verifier").
| 
| I think a corollary of this is that *only* "synchronized"
| data gets written to global variables, which seems pretty
| onerous, but also necessary in any really large multithreaded
| program (as in, what the heck were you planning to do with
| that global data if it wasn't synchronized by something?)
| I've been playing with the idea for some time, but it's not
| like I have the time or funding to do anything with it, so
| it hasn't really gone anywhere, nor is it clear that anyone
| would want to use the result if I did.

Some work was done on this (at SRC?) in another direction:  Automatic
detection of incorrect synchronization at run time.  The basic algorithm
is simple:  Monitor all memory accesses.  Any memory location ever accessed
by more than one thread is declared to be shared memory.  For all accesses
to shared memory, maintain a "lock set".  The "lock set" is initialized to
the set of locks held by the first accessor.  At every subsequent access,
remove from the lock set any locks not currently held by the new accessor.
If the lock set becomes empty, declare the memory location improperly
synchronized.

Of course, the devil is in the details.  Just to get started, you have to
monitor memory allocation, since once you free a memory block any subsequent
use doesn't share with any previous use.  (This assumes no references through
dangling pointers - but without that, you're pretty well lost.)  It also
turned out that there were a couple of fairly common safe patterns of usage
that this approach would declare illegal.  I suppose one obvious one would be
a block of memory allocated and populated by thread 1 and placed on a queue
for thread 2.  Access to the queue needs interlocking, but access to the
memory block itself does not - even though it "looks" as if it's shared.

I can't dig up the reference at the moment - anyone?  There might be some
interesting clues to the kinds of things you'd need to be able to declare if
you wanted the compiler to help out.
							-- Jerry