I think we all agree that merging synch blocks is always legal
with respect to our new proposed memory model.
The question of whether merging synch blocks is legal with respect
to some liveness condition is a separate issue. The rule for
compile-time merging of synch blocks can be directly derived from the
corresponding run-time rule for acquisition (in particular,
reacquisition) of locks. Two synch blocks can be merged at compile
time only if the compiler can guarantee that it would have been legal
(with respect to the liveness condition) to release and reacquire the
lock at run time.
In particular, there is no sense limiting the merging that the
compiler can do if at run time no limit is put on how often a lock can
be reacquired.
To give an example, if your liveness condition is that threads
contending for a lock must gain access to the lock in FIFO order, then
you can't merge any synch blocks.
The weakest non-empty liveness condition I can think of is the
following: no thread can wait forever to acquire a lock while a single
other thread acquires that lock infinitely often. A slightly stronger
rule would replace the phrase "a single other thread acquires" with
"other threads acquire". Both of these conditions lead to the
following rule for compile-time merging of synch blocks: merge as many
synch blocks as you like, as long as you merge only a finite number of
them. For example, you would be able to move synchronization out of
any loop that the compiler could prove executed only a finite number
of times. Note that this rule would allow merging even if the
compiler could not provide any bound on the running time of the
individual original critical sections. The resulting compiled program
satisfies the liveness condition assuming the JVM satisfies it.
I suspect either one of these rules would be a reasonable default
liveness rule for Java. Another reasonable one would be the current
one, i.e., no liveness condition at all. (Note that locks with better
liveness guarantees can be built from regular locks: see
http://www.eng.uiowa.edu/~skaliann/books/jthreads/ch07_03.htm)
In any case, keep in mind that any rule for merging synch blocks at
compile time necessarily relates to the run-time rule for
reacquisition of locks. There is no point in making the merging rules
more restrictive or less restrictive than the corresponding run-time
rules you want to enforce.
-Keith
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:29 EDT