RE: JavaMemoryModel: Guaranteed semantics for Thread.yield()

From: Roly Perera (roly.perera@ergnosis.com)
Date: Mon Dec 31 2001 - 11:23:08 EST


Bill Pugh wrote:

> In finishing up our writeup on fairness, I think we need to guarantee
> some semantics for Thread.yield() and Thread.sleep().
>
> Specifically, either operation should have the semantics that with
> some finite probability, some other eligible thread of equal or
> higher priority is allowed to execute at least one instruction.
>
> [...]
>
> This guarantee will ensure that both of the following two examples
> terminate, while without the guarantee they can both fail to
> terminate.
>
> Example 1:
> Initially, volatile x = 0
>
> Thread 1:
> while (x == 0) {
> Thread.yield();
> }
>
> Thread 2:
> x = 1
>
> Example 2:
> Initially, x = 0 (x is non-volatile in this example).
>
> Thread 1:
> int r1;
> do {
> Thread.yield();
> synchronized(this) {
> r1 = x;
> }
> } while (r1 == 0);
>
> Thread 2:
> synchronized(this) {
> x = 1
> }

Could someone humour me and outline (or point me to) the theory behind
this?

What I'm unclear about is the meaning of the claim that example 1
terminates "eventually". How long does one have to wait to be sure that
the example isn't going to terminate, and therefore that the
implementation executing the code is broken? It seems to me (naively,
no doubt) that the assertion that example 1 terminates isn't testable in
finite time.
 
- Roly

Roly Perera
Ergnosis Ltd

-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel



This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:36 EDT