[concurrency-interest] Language extensions forjava.util.concurrent?

Jeremy Manson jmanson at cs.purdue.edu
Thu Nov 10 15:22:13 EST 2005


Dawid Kurzyniec wrote:

> The "uneasiness" was because I thought that locks would be silently 
> inserted to handle more complex atomic blocks. If atomic {} is always 
> non-blocking, then I may buy into the idea. But optimistic concurrency 
> algorithms must deal with failures and retries. How would that look 
> like? And what does the following mean:
> 
> atomic {
>   if (a == 6) { 
 >     foo();
 >     b=4;
 >     a=5;
 >   } else a = 4;
> }
> 
> Would the compiler have to ensure that a is not changed by other threads 
> after it is read in the atomic block? But how to do that without 
> blocking that other threads?

There are several ways of ensuring this, most of which just take some 
imagination; the "right" one probably depends on what you need from your 
system.  Here's some brief discussion, which is by no means complete.

First, you might say that "atomic" only means atomic if a given variable 
is always accessed in an atomic section.  Otherwise, the multivariable 
invariants don't hold.  So, for example, a thread which accesses b and a 
outside an atomic block might see b == 4, but a == something else.  This 
may seem bad, but it is roughly analogous to writing code with data 
races in it.

That would ensure that atomic blocks only need to be atomic with respect 
to each other.  And this is a significantly easier problem.

One simple solution: record all writes in an atomic block to a log, 
instead of writing them directly to memory.  At the end of the block, if 
the memory that has been accessed has not changed, then briefly block 
(in the same sense that all machine level atomic actions briefly block) 
and perform all updates atomically.  If the memory has been changed, 
then restart.

There are obviously pitfalls and elided details here.  There are also 
more sophisticated solutions out there - like I said, it is a fairly 
active research area.  If you are interested in doing some reading, a 
good place to start might be Harris and Fraser's 2003 OOPSLA paper, 
"Language Support for Lightweight Transactions".

					Jeremy


More information about the Concurrency-interest mailing list