The Artima Developer Community
Sponsored Link

Weblogs Forum
Java Threads

36 replies on 3 pages. Most recent reply: Oct 18, 2005 12:19 PM by Bruce Eckel

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 36 replies on 3 pages [ « | 1 2 3 | » ]
Maarten Hazewinkel

Posts: 32
Nickname: terkans
Registered: Jan, 2005

Re: Volatile, Atomic, and ++ Posted: Sep 9, 2005 10:27 AM
Reply to this message Reply
Advertisement
Bruce,

One suggestion that I would make in regards to concurrency is that nearly all difficulties in concurrency stem from sharing state between threads. That's also the whole point in volatile fields.
I would suggest that a solid chapter on concurrency also look at ways to avoid sharing state, or sharing it in a read-only manner. It is generally possible to come up with such approaches for any problem that can also be solved with shared state, though in some cases the efficiency can be an issue.

If it were totally up to me, I would actually describe such approaches before getting into the details of handling shared state safely.

John D. Mitchell

Posts: 244
Nickname: johnm
Registered: Apr, 2003

Shared state Posted: Sep 9, 2005 10:34 AM
Reply to this message Reply
> I would suggest that a solid chapter on concurrency also
> look at ways to avoid sharing state, or sharing it in a
> read-only manner.

What do you mean by "read-only manner"? Somebody, at some point, has to have written the data so there's always a potential synchronization issue. Obviously, it is possible to simplify things by doing all of the writing up front in e.g., a global initialization phase that's done before all of the threads are fired up. But that's not so much shared state as global values.

Maarten Hazewinkel

Posts: 32
Nickname: terkans
Registered: Jan, 2005

Re: Shared state Posted: Sep 9, 2005 10:47 AM
Reply to this message Reply
> > sharing it in a
> > read-only manner.
>
> What do you mean by "read-only manner"? Somebody, at some
> point, has to have written the data so there's always a
> potential synchronization issue.

Good point. There may be a loophole there. I was thinking that sharing data would be ok as long as it's not changed after the reference is passed to other threads. I don't have enough of the new memory model in my head to really make any definitive statement about this right now. I'll probably look into it later, as I do actually enjoy these sorts of issues.

Maarten Hazewinkel

Posts: 32
Nickname: terkans
Registered: Jan, 2005

Re: Shared state Posted: Sep 9, 2005 11:28 AM
Reply to this message Reply
I verified that it is possible to share object read-only manner by using final fields. From the Java Language Specification, third edition, section 17.5:

Set the final fields for an object in that object's constructor. Do not write a reference to the object being constructed in a place where another thread can see it before the object's constructor is finished. If this is followed, then when the object is seen by another thread, that thread will always see the correctly constructed version of that object's final fields. It will also see versions of any object or array referenced by those final fields that are at least as up-to-date as the final fields are.

Note particularly the last sentence in that: objects referenced by final fields will be seen up-to-date by other threads.

So complete construction of an immutable object using final fields before sending it to another thread. Then the other thread can safely read from the object, and referenced objects.

The whole idea behind this to move from a shared-memory type interaction between threads to a message passing system within the VM (and without complete serialization-deserialization of the messages).

For the actual message passing, you do need some shared structure, but that's where you use one of the Queues in the new concurrent utilities pointed out by John.

Thomas

Posts: 4
Nickname: tal197
Registered: Sep, 2005

Word-processor background saving Posted: Sep 9, 2005 11:44 AM
Reply to this message Reply
You only have to copy things that aren't immutable. Since images make up the bulk of your document, the 'copy' won't take much memory at all. Even the text might not be copied, if it is stored as lots of strings.

(Python programmer, but always impressed by Java over-engineering ;-)

John D. Mitchell

Posts: 244
Nickname: johnm
Registered: Apr, 2003

Re: Shared state Posted: Sep 9, 2005 1:13 PM
Reply to this message Reply
> I verified that it is possible to share object read-only
> manner by using final fields. From the Java Language
> Specification, third edition, section 17.5:

That's exactly like my example... You're doing all of the work in an initialization phase and only then dealing with the cross-thread data transfer.

Is there some facillity that you're thinking of that I'm just not getting? Doing value-based message passing certainly reduces certain kinds of sharing problems but it doesn't make it go away.

Maarten Hazewinkel

Posts: 32
Nickname: terkans
Registered: Jan, 2005

Re: Shared state Posted: Sep 9, 2005 3:18 PM
Reply to this message Reply
> That's exactly like my example... You're doing all of the
> work in an initialization phase and only then dealing with
> the cross-thread data transfer.

Yes, but you can create such message objects at any time in the program. Your earlier reply sounded to me like you thought you could only use objects created at program initialization. Perhaps I simply misunderstood what you said.

> Is there some facillity that you're thinking of that I'm
> just not getting? Doing value-based message passing
> certainly reduces certain kinds of sharing problems but it
> doesn't make it go away.

What I'm thinking of is that many of the facilities designed specifically for multi-threading or multi-processing are designed around message-passing instead of shared state.

Some examples are the Linda tuple space communication, which forms the basis of the JavaSpaces design for Jini. Also the language Erlang, which is based on CSP (Communicating Sequential Processes), which is a mathematical basis for multi-processing.

In larger scale space, on enterprise systems you often deal with multi-machine setups (clusters, multi-layer architectures). In these cases you don't even have the option of shared memory. Modern architectures using SOA and message busses are also message based.

I do not think it accidental that so many diverse solutions to multi-processing are based around message passing instead of shared state. It is a much easier concept to keep in your head than all the hairy details that crop up in a shared state architecture. I think one reason that we can deal better with a message passing system is that the way humans work in real life is much more like a message passing system that a shared state system.

I agree that multi-processing remains far from simple, but from what I've seen message passing makes it easier to handle for many developers. In the end, what I'm advocating is that a good introduction to concurrency should introduce both. It's been my experience that most books focus only on the shared state approach and it seems a shame to ignore another widely used successful approach to multi-processing.

John D. Mitchell

Posts: 244
Nickname: johnm
Registered: Apr, 2003

Message passing is not a panacea Posted: Sep 10, 2005 8:57 AM
Reply to this message Reply
> Yes, but you can create such message objects at any time
> in the program. Your earlier reply sounded to me like you
> thought you could only use objects created at program
> initialization. Perhaps I simply misunderstood what you
> said.

Ah, sorry. "E.g." literally means "for example".

> > Is there some facillity that you're thinking of that I'm
> > just not getting? Doing value-based message passing
> > certainly reduces certain kinds of sharing problems but it
> > doesn't make it go away.
>
> What I'm thinking of is that many of the facilities
> designed specifically for multi-threading or
> multi-processing are designed around message-passing
> instead of shared state.

You're using the term "shared state" in a loose, imprecise way. "Message passing", as you've said, is still sharing state data. Sharing state via e.g., "shared memory" is, one way or another, still involved in any state sharing mechanism -- message passing doesn't make that go away.

> Some examples are the Linda tuple space communication,
> which forms the basis of the JavaSpaces design for Jini.
> Also the language Erlang, which is based on CSP
> (Communicating Sequential Processes), which is a
> mathematical basis for multi-processing.
>
> In larger scale space, on enterprise systems you often
> deal with multi-machine setups (clusters, multi-layer
> architectures). In these cases you don't even have the
> option of shared memory. Modern architectures using SOA
> and message busses are also message based.
>
> I do not think it accidental that so many diverse
> solutions to multi-processing are based around message
> passing instead of shared state. It is a much easier
> concept to keep in your head than all the hairy details
> that crop up in a shared state architecture. I think one
> reason that we can deal better with a message passing
> system is that the way humans work in real life is much
> more like a message passing system that a shared state
> system.
>
> I agree that multi-processing remains far from simple, but
> from what I've seen message passing makes it easier to
> handle for many developers. In the end, what I'm
> advocating is that a good introduction to concurrency
> should introduce both. It's been my experience that most
> books focus only on the shared state approach and it seems
> a shame to ignore another widely used successful approach
> to multi-processing.

I strongly concur that most training materials on threads do a poor job of educating developers on how to solve real problems in threading with the tools that are specifically made to help them do so without having to become experts in all of the nasty details. It's really unfortunate because it has meant that there's a lot of code written that's buggy and the people usually don't know it.

IMHO, it's important to realize that all of those higher-level approaches to sharing state are still based on some amount of shared memory. Higher-order approaches make managing sharing data (much) more tractable for most problems and people but the basis is still shared memory at some point in the food chain.

To be clear, I really like good message passing systems because they can deal well with a lot of issues more clearly, robustly, etc. but they don't make the problems with sharing state go away. In fact, the assumptions and biases in each approach and implementation can hide and exacerbate some kinds of problems.

I like how Ousterhout said it, best: "State is the second worst thing in distributed computing. No state is the worst." :-)

Isaac Gouy

Posts: 527
Nickname: igouy
Registered: Jul, 2003

Re: Shared state Posted: Sep 10, 2005 9:21 AM
Reply to this message Reply
-snip-
> Some examples are the Linda tuple space communication,
> which forms the basis of the JavaSpaces design for Jini.
> Also the language Erlang, which is based on CSP
> (Communicating Sequential Processes), which is a
> mathematical basis for multi-processing.

Communicating Sequential Processes for Java (JCSP)
http://www.cs.kent.ac.uk/projects/ofa/jcsp/

JCSP Network Edition
http://www.quickstone.com/xcsp/jcspnetworkedition/

Frank Zitters

Posts: 5
Nickname: fzitters
Registered: Aug, 2005

Re: Java Threads Posted: Sep 10, 2005 5:23 PM
Reply to this message Reply
I've decided to split my post into two parts: First I'll quickly spit out some thoughts related to this discussion. Only then I'll add some additional comments for the interested. Of course this post only reflects my personal impressions and understanding. Although I have spent quite some time trying to master Java threading (both in Java 1.4 and 1.5), I'm certainly not an expert on the topic. Feel free to correct me any time. That said, let's start!

1) "Java Threads" (3rd Edition) contains many unclear explanations, inaccuracies and mistakes.

2) A single access to (read of or write to) a volatile variable is always atomic. This includes volatile variables whose associated type is a reference type, long or double, and holds both for Java 1.4 and 1.5.

3) As was pointed out already, an increment or decrement operation amounts to two variable accesses (a read followed by a write). Such an operation <b>must</b> be synchronized to be thread-safe (declaring the variable "volatile" is not enough).

4) I agree with an earlier writer that the notion of "happens-before" helps a lot to understand threading in Java 1.5.

5) Understanding "volatile" and "final" wrt. threading should be easier in Java 1.5 than it was in 1.4. One of the main motivations behind the changes was to bring their semantics more in line with people's intuition. In both cases semantics were strengthened, meaning that everything that worked in 1.4 will still work (and probably also make sense) in 1.5.

6) Generalizing on the last statement, all programs that were thread-safe in Java 1.4 are also thread-safe in 1.5.

7) To better understand "volatile" in Java 1.5, the following comparison might help: Declaring a variable x "volatile" is equivalent to wrapping all operations on x in synchronized blocks sharing the same lock object, except that "volatile" doesn't enforce mutual exclusion.

Now for the comments:

ad 1) Threading is a very delicate topic. Therefore I expect any good publication in this field to be particularly clear, accurate and correct. "Java Threads" clearly fails in this respect. Hopefully there will soon be a better work on threading in Java 1.5.

ad 2) This is one of the points where the authors of "Java Threads" err. They claim on several occasions that an access to a volatile long/double value is not atomic. For example, in chapter 5.2 they say the following: "Volatile variables can be safely used only for a single load or store operation and can't be applied to long or double variables." However, a quick look into chapter 17.7 of the JLS proves them wrong: "Writes and reads of volatile long and double values are always atomic."

ad 4) "happens-before" describes a relationship between certain program actions such as variable reads, variable writes, monitor locks and monitor unlocks. (In mathematical terms, happens-before is a partial order relation.) It lets us reason about programs in the following way: Given two actions A and B, only if A "happens-before" B it is guaranteed that B sees the effects of A. In other words, if we want to ensure that B sees the effects of A, we have to structure our program in such a way that A happens-before B. For example, A happens-before B if:
- A and B are actions of the same thread and A comes before B (according to the semantics of single-threaded programs)
- A is a write to a volatile variable and B is a subsequent read of the same variable (possibly in a different thread)
For a more exhaustive and accurate description, see the JLS.

ad 7) It is a common misconception that the sole purpose of synchronized blocks is to enforce mutual exclusion. In fact, they also help to control issues of visibility and ordering.
One more try to explain the semantics of "volatile" in Java 1.5: In addition to the globally shared main memory, each thread maintains its own working memory (an abstraction of registers, caches, etc.). If a thread is to access a volatile variable, it first invalidates its working memory, then it accesses the variable, then it flushes its working memory. Note that this might also have effects on other variables: Suppose we have two threads named A and B operating on shared variable x. If A writes x and B subsequently reads x, B will not only see A's write to x, but also all prior writes by A to other shared variables (assuming none of them was meanwhile written to by yet another thread). This has changed from Java 1.4, where B was only guaranteed to see A's write to x.

Finally some resources on Java threading that I found particularly enlightening:

Brian Goetz: Java theory and practice: Fixing the Java Memory Model, Part 1
http://www-128.ibm.com/developerworks/library/j-jtp02244.html
Brian Goetz: Java theory and practice: Fixing the Java Memory Model, Part 2
http://www-128.ibm.com/developerworks/library/j-jtp03304/
Doug Lea: Concurrent Programming in Java: Design Principles and Patterns (2nd Edition)
See http://java.sun.com/docs/books/cp/
The Java Language Specification, 3rd Edition
Freely available at http://java.sun.com/docs/books/jls/

PS: Thanks to Bruce Eckel for the great "Thinking in Java" books! I'm already looking forward to the next edition.

Maarten Hazewinkel

Posts: 32
Nickname: terkans
Registered: Jan, 2005

Re: Message passing is not a panacea Posted: Sep 12, 2005 1:13 AM
Reply to this message Reply
John,

I think that we are, as someone once put it, in violent agreement.

Thank you for an enlightening discussion.

Brian Goetz

Posts: 6
Nickname: briangoetz
Registered: Sep, 2005

Re: Java Threads Posted: Sep 12, 2005 2:38 PM
Reply to this message Reply
> Finally some resources on Java threading that I found
> particularly enlightening:

And you can add to this list the soon-to-be-completed Java Concurrency in Practice: http://www.amazon.com/exec/obidos/ASIN/0321349601/ref=nosim/none0b69


The JMM offers a clear semantics for volatile: a write of a volatile happens-before a subsequent read of that variable in another thread.

In only slightly less JMM terms: writing a volatile has the same memory semantics (release) as exiting a synchronized block, and reading a volatile has the same memory semantics (acquire) as entering a synchronized block.

Where people get hung up is on the question of "what is it good for." The fact that volatile had a meaning in C which is a subset of the meaning in Java adds to the confusion.

> Especially with the advent of multicore processors and
> the cache coherency problem, this can no longer be
> described in a simple fashion.

The only issue that multicore and the wider availability of weaker-memory-model multiprocessors is that it makes the bugs actually manifest more often. In reality, the vast majority of Java code out there works "by accident" and contains hidden concurrency bugs that are undisclosed because they don't get run enough on MP systems under heavy load, or on systems with weaker memory models. So things work "by accident."

Here are some simple rules about when you can use volatile instead of synchronized:

- When the variable does not participate in any invariants with other variables, and
- It is only ever written from a single thread, or
- Updates to that variable do not depend on its previous value

Bruce, does that help?

Brian Goetz

Posts: 6
Nickname: briangoetz
Registered: Sep, 2005

Re: Java Threads Posted: Sep 12, 2005 2:43 PM
Reply to this message Reply
> Here are some simple rules about when you can use volatile
> instead of synchronized:
>
> - When the variable does not participate in any
> y invariants with other variables, and
> - It is only ever written from a single thread, or
> - Updates to that variable do not depend on its
> n its previous value
>
> Bruce, does that help?


Oh, crap, the formatting got lost here. If

NI = doesn't participate in invariants with other variables
1T = only written from one thread
UN = Updates do not depend on previous value

Then you can use volatile instead of locking if

NI && (1T || UN)

Tim Peierls

Posts: 3
Nickname: tpeierls
Registered: Sep, 2005

Re: Java Threads Posted: Sep 14, 2005 9:14 AM
Reply to this message Reply
> NI = doesn't participate in invariants with other variables
> 1T = only written from one thread
> UN = Updates do not depend on previous value
>
> Then you can use volatile instead of locking if
>
> NI && (1T || UN)

And some common uses are:

- A boolean latch that starts false and can be set true by any thread (NI && UN).
  private volatile Thing found = null;
  private final Thing target;
 
  /** Potentially called in many threads */
  void search(Iterable<Thing> candidates) {
      for (Thing candidate : candidates) {
          if (matches(candidate, target))
              found = candidate;
          if (found != null) break;
      }
  }
Have to be careful here, since there is nothing to stop found from being set to different non-null values by different threads. If you want only the first found thing, then the update does depend on a previous value, so you can't use volatile alone.

- A counter that is incremented by one thread and read by many (NI && 1T).
  private volatile long counter = 0;
 
  /** Only ever called by one thread */
  void bumpCounter() { 
      ++counter; 
  }
 
  /** Called by many threads */
  public long getCount() { 
      return counter; 
  }
Again, you have to be careful. You can't use volatile to implement a unique value generator:
  // This does *not* work!
  public long brokenGetUniqueValue() {
      return ++counter;
  }
That breaks both UN and 1T.

Bruce Eckel

Posts: 875
Nickname: beckel
Registered: Jun, 2003

To Tim Peierls Posted: Sep 14, 2005 11:47 AM
Reply to this message Reply
To Tim Peierls:

Since you're being helpful, I'd like to bother you with a puzzle I'm struggling with, since Brian Goetz is teaching this week. Please email me at Bruce@EckelObjects.com (my spam blocker will challenge you). Thanks!

Flat View: This topic has 36 replies on 3 pages [ « | 1  2  3 | » ]
Topic: Back to Generics: Contravariance and Erasure Previous Topic   Next Topic Topic: Designing a Language for Library Developers

Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2019 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use