Roach motels

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Roach motels

Steve Kautz
Reading Brian Goetz's article on synchronization optimizations in Mustang
got me thinking again about Bill Pugh's roach motel analogy (statements can
move into a sync block, but they can't move out...).  Does anyone have any
information about conditions under which statements might be moved into a
preceding sync block (or similarly, whether adjacent synchronized blocks may
be coalesced when there is intervening code)?


E.g. suppose we have something like:

boolean foo()
{
synchronized(this)
{
if (inProgress) return false;
inProgress = true;
}

// make this call without lock
Result result = someOtherObject.bar();

synchronized(this)
{
updateState(result);
inProgress = false;
return true;
}
}

When is the compiler allowed to move the call to bar() into the upper sync
block or to coalesce the two blocks?

I'm just wondering about several situations that have come up recently in
which we need to guarantee that the call to bar() is made without holding
the sync lock. This is generally to avoid a possible deadlock, but it may be
for other liveness-related reasons (call to bar() may block).

For example, in the OSGi framework, calls on the bundle registry must not be
made from synchronized code. (The problem is that any call on the registry
may trigger callbacks on other bundles (listeners) and these callbacks are
always made synchronously, so if two threads call the registry at about the
same time, and they are holding sync locks on bundles that are listening for
registry events, it is easy to get deadlock.)

Thanks in advance for any information or pointers to information.
-- Steve K


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Roach motels

Jeremy Manson
Steve Kautz wrote:

> boolean foo()
> {
> synchronized(this)
> {
> if (inProgress) return false;
> inProgress = true;
> }
>
> // make this call without lock
> Result result = someOtherObject.bar();
>
> synchronized(this)
> {
> updateState(result);
> inProgress = false;
> return true;
> }
> }
>
> When is the compiler allowed to move the call to bar() into the upper sync
> block or to coalesce the two blocks?
>
> I'm just wondering about several situations that have come up recently in
> which we need to guarantee that the call to bar() is made without holding
> the sync lock. This is generally to avoid a possible deadlock, but it may be
> for other liveness-related reasons (call to bar() may block).

The system is allowed to introduce fairness issues, but can't introduce
deadlock.  This is because fairness is considered a quality-of-service
guarantee, but deadlock is considered a correctness issue.

For example, if you have:

while (true) {
   synchronized (this) {
     // stuff
   }
}

The system could change it to this:

synchronized (this) {
   while (true) {
     // stuff
   }
}

Any other thread that actually wants to acquire the lock on this would
wait forever, which is legal under the Java spec.  This falls under the
same category of badness as giving all of the runtime to a single
thread, and never allowing another thread to run.  It's legal, but a
well-designed system would probably not do it.

OTOH, a system cannot, in general, take this:

   synchronized (this) {
     // stuff
   }
   synchronized (that) {
     // more stuff
   }
   synchronized (this) {
     // even more stuff
   }

and change it to this:

synchronized (this) {
   // stuff

   synchronized (that) {
     // more stuff
   }

   // even more stuff
}

because this can introduce deadlock, which may introduce errors in your
program.

Interesting aside: There are caveats to this, but those caveats should
never be seen to affect the correctness of your program.  An example of
such a caveat would be if the system can determine that the lock on
"that" is never acquired by any other thread.  In this case, it can do
the lock coalescing, because doing so won't introduce deadlock.

                                        Jeremy
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Roach motels

Steve Kautz
In reply to this post by Steve Kautz
Jeremy, thanks for that quick reply.

> OTOH, a system cannot, in general, take this:
>
>    synchronized (this) {
>      // stuff
>    }
>    synchronized (that) {
>      // more stuff
>    }
>    synchronized (this) {
>      // even more stuff
>    }
>
> and change it to this:
>
> synchronized (this) {
>    // stuff
>
>    synchronized (that) {
>      // more stuff
>    }
>
>    // even more stuff
> }
>
> because this can introduce deadlock, which may introduce errors in your
> program.


Right. So I think the interesting question is then, in which direction does
the burden of proof go?   For example, if instead of literally having
synchronized(that) we again have something like:

  synchronized (this) {
     // stuff
   }

   otherObject.bar();

   }
   synchronized (this) {
     // even more stuff
   }

how far is the system obligated to look before concluding that bar() will,
or won't, enter a block of the form synchronized(that)?

In particular, in the OSGi example mentioned earlier, method bar()
ultimately invokes callback methods for a list of listeners, some of which
may be synchronized, and which are added/removed dynamically at runtime.  So
no amount of static analysis will show whether or not a call to bar() will
end up invoking "synchronized(that)".   Does the system a) assume that a
method call may end up in synchronized code unless it can prove otherwise,
or does it b) assume it's ok to coalesce the blocks unless it can show that
the call includes something like "synchronized(that)"?

-- Steve K

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Roach motels

Jeremy Manson
Steve Kautz wrote:
> Jeremy, thanks for that quick reply.

No problem.  In answer to your question below, the answer is "a)", the
system has to ensure that it isn't introducing deadlock.  If it can't do
so, then it can't perform the transformation.  If it can't analyze
unknown method calls, then it can't perform the transformation.

[I thought I sent this hours ago!]

                                        Jeremy

>
>
>>OTOH, a system cannot, in general, take this:
>>
>>   synchronized (this) {
>>     // stuff
>>   }
>>   synchronized (that) {
>>     // more stuff
>>   }
>>   synchronized (this) {
>>     // even more stuff
>>   }
>>
>>and change it to this:
>>
>>synchronized (this) {
>>   // stuff
>>
>>   synchronized (that) {
>>     // more stuff
>>   }
>>
>>   // even more stuff
>>}
>>
>>because this can introduce deadlock, which may introduce errors in your
>>program.
>
>
>
> Right. So I think the interesting question is then, in which direction does
> the burden of proof go?   For example, if instead of literally having
> synchronized(that) we again have something like:
>
>   synchronized (this) {
>      // stuff
>    }
>
>    otherObject.bar();
>
>    }
>    synchronized (this) {
>      // even more stuff
>    }
>
> how far is the system obligated to look before concluding that bar() will,
> or won't, enter a block of the form synchronized(that)?
>
> In particular, in the OSGi example mentioned earlier, method bar()
> ultimately invokes callback methods for a list of listeners, some of which
> may be synchronized, and which are added/removed dynamically at runtime.  So
> no amount of static analysis will show whether or not a call to bar() will
> end up invoking "synchronized(that)".   Does the system a) assume that a
> method call may end up in synchronized code unless it can prove otherwise,
> or does it b) assume it's ok to coalesce the blocks unless it can show that
> the call includes something like "synchronized(that)"?
>
> -- Steve K
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest