8

I was looking at the code of java concurrent collections and I see that they just wrap simple collections with locking some lock in the beginning of the operation and unlocking it in the end.

What about volatile? If the back end collection is not volatile the changes could be missed by other threads, and so the thread-saving is somewhat broken. I know that synchronized can solve this issue, but they use just locks without any further synchronization.

Is that a problem, or am I missing something?

Update:

After a slight discussion I want to rephrase the question a bit.

I want to use a java collections in a multi threaded environment. (For instance currently I'm talking about PriorityBlockingQueue)

I want to be sure that the changes one thread makes to the collection (push/pop) are immediately visible to others.

It is good that java concurrent collections prevent me from diving into troubles to keep the inner state of the collection stable when number of threads updates it, but I want to be sure that the data itself is visible to all threads.

The question is: am I correct that java concurrent collections don't provide this feature out of the box? And if I do, what additional (minimalistic cost) techniques should I use in order to do provide the desired visibility?

Thanks.

jutky
  • 3,895
  • 6
  • 31
  • 45
  • It is important to note that 'synchronized' in Java is not just a 'mutex' or a lock. It is a contract about happens-before relationships and consistency-of-view. A synchronized block is dynamically-scoped as it descends the call stacks along with execution (vs. merely being lexical in the scope). See http://stackoverflow.com/questions/3214938/java-volatile-modifier-and-synchronized-blocks (I've seen some really good SO questions that bring up the JLS in detail, but I can't find them at the moment :-/) Perhaps see: http://java.sun.com/docs/books/jls/second_edition/html/memory.doc.html –  Nov 23 '10 at 18:44
  • I don't want a mutex, I want just that all the changes would be seen to all the threads. So I want to avoid using unnecessary synchronization mechanisms. – jutky Nov 23 '10 at 18:48
  • It is important to note that 'synchronized' in Java *is not just* a 'mutex' or a lock.... there are other synchronization methods, but they take a good bit more thought. 1) A "lock-free" algorithm like ConcurrentLinkedQueue 2) volatile (does not create atomic sections) 3) one of the Atomic* classes (support CAS and atomic increment, etc.)... anyway. –  Nov 23 '10 at 18:49

5 Answers5

11

From BlockingQueue's Javadoc:

Memory consistency effects: As with other concurrent collections, actions in a thread prior to placing an object into a BlockingQueue happen-before actions subsequent to the access or removal of that element from the BlockingQueue in another thread.

PriorityBlockingQueue provides this behaviour by means of a ReentrantLock which (being an implementation of Lock):

...provide[s] the same memory synchronization semantics as provided by the built-in monitor lock, as described in the JLS...

SimonJ
  • 21,076
  • 1
  • 35
  • 50
8

yes, you are missing something. the ReentrantLock class provides the same guarantees as synchronized. And, ReentrantLock and synchronized both provide the same memory guarantees as volatile.

james
  • 1,230
  • 9
  • 4
  • Wow. I wish it was as simple as that. Could you cite an official source that states that. – jutky Nov 23 '10 at 20:07
  • I think that you are wrong. What happens if I obtain a lock in one function and then free it in another function, would all the code that is executed meanwhile be synchronized? That doesn't makes sense. – jutky Nov 23 '10 at 20:51
  • 3
    "All `Lock` implementations *must* enforce the same memory synchronization semantics as provided by the built-in monitor lock, as described in the JLS" - from http://download.oracle.com/javase/6/docs/api/java/util/concurrent/locks/Lock.html – SimonJ Nov 23 '10 at 20:57
  • 2
    And yes, you can acquire the lock in one function and free it in another - but the recommended usage is to call `unlock()` in a finally block immediately after acquiring the lock. Otherwise, program to ensure it gets called eventually. – SimonJ Nov 23 '10 at 20:58
6

I was looking at the code of java concurrent collections and I see that they just wrap simple collections with locking some lock in the beginning of the operation and unlocking it in the end.

What source were you reading?

This is an over-generalization. It depends entirely on which collection you're looking at. For example, CopyOnWriteArrayList does nothing of the sort, but creates an entirely new array every time you add or remove elements, which means any open Iterator or ListIterator will continue running with the old data; this effect is intentional.

What about volatile? If the back end collection is not volatile the changes could be missed by other threads, and so the thread-saving is somewhat broken. I know that synchronized can solve this issue, but they use just locks without any further synchronization.

Most of the concurrent collections exist to make sure Iterators continue to operate on the old version rather than the new version that has updated data; something that volatile would not guarantee. This behavior also means that the Iterators will not be left in an inconsistent state, and thus preventing ConcurrentModificationException from being thrown.

Powerlord
  • 87,612
  • 17
  • 125
  • 175
  • I was looking at `PriorityBlockingQueue`. – jutky Nov 23 '10 at 18:45
  • But if I want number of threads to use same collection, I can't reimplement the backbone collection to be `volatile`. So I'm obligated to make synchronization on each access to the collection? – jutky Nov 23 '10 at 18:46
  • 1
    @jutky It is not equivalent. `volatile` only "flushes" access to a *single variable* (this does not propagate to any data of the actual object for a reference type). **It does not introduce an atomic section.**. This trivial code is not thread safe (assume i is a shared volatile int): `if (i > 10) { i = 0; ... } else { i++; ... }` –  Nov 23 '10 at 18:53
  • That is exactly what I wants. The atomicity is already provided by the `java.concurrent` classes, by using the locks. I want to know what additional things should I use in order to "flush" the changes to all member variables of the collection, so that all the threads would see the updates. – jutky Nov 23 '10 at 19:00
  • @jutky There are orthogonal issues floating around here. And it's become very hard to tell which is which. Perhaps shed more light by updating the question with more details about a particular use-case and *specific* java.concurrent ADT/class used? –  Nov 23 '10 at 19:12
5

EDIT: since the original question was clarified, this answer is no longer relevant. The answer below is relevant for the case when using Collections.synchronized* methods for making non-threadsafe collections threadsafe.

If you synchronize a block of code that will also cause different threads to synchronize the (possibly changed) state.

[...] Either solution requires the clkID variable to be reconciled with main memory. Accessing the clkID variable from synchronized method or block does not allow that code to execute concurrently, but it does guarantee that the clkID variable in main memory is updated appropriately. Main memory is updated when the object lock is obtained before the protected code executes, and then when the lock is released after the protected code executes. [...]

Source: Use Synchronized or Volatile when Accessing Shared Variables

Neeme Praks
  • 8,956
  • 5
  • 47
  • 47
  • I understand that, but isn't the point of concurrent collections is to avoid any other explicit synchronization? correct me if I wrong. – jutky Nov 23 '10 at 18:24
  • I'm not sure if I understand your question. What do you mean by "any other explicit synchronization"? The point of synchronized collection wrapper is to synchronize access to the otherwise non-threadsafe collection. – Neeme Praks Nov 23 '10 at 18:29
  • As Bemrose mentioned, it would be helpful if you would explicitly state which class source are you looking at. – Neeme Praks Nov 23 '10 at 18:39
  • @Neeme Praks If you keep onto the original collection after wrapping it, an then access it through that means, you have bypassed the "explicit synchronization" added by the wrapper. Locks are 'advisory' in that parties must agree to use the same monitor (or to lock at all). –  Nov 23 '10 at 18:40
  • I mean a `synchronized` block. So each time I access the thread-safe collection I should do it from inside a `synchronized` block? – jutky Nov 23 '10 at 18:40
  • No. Thread-safe means that it is safe to access from multiple threads and the object itself will ensure that the internal state will not become corrupted as a result. What class(es) are you referring to when talking about "thread-safe collection"? – Neeme Praks Nov 23 '10 at 18:43
  • Oh, I see. I taught thread-safe promises a bit more. I was looking on `PriorityBlockingQueue`. – jutky Nov 23 '10 at 18:50
  • -1 because though the content of the answer are technically correct, they don't answer the OPs question. The OPs question is specifically whether or not the concurrent collections guarantee thread visibility (spoiler, they do), the answer provided above is tangential and confusing in nature. – Tim Bender Nov 23 '10 at 21:39
  • agree - the original question was confusing and I misunderstood it. – Neeme Praks Nov 24 '10 at 00:25
0

Here is the point wise answers to your questions. 1. All Java collection data structures in concurrency package do not wrap corresponding non thread safe collection data structures. 2. There are ways to achieve thread safety without using locks or synchronization. Writing lock free data structures is more involved and normally you should avoid for general development. But if there is one available, you should use them instead of the corresponding lock version of the data structure. 3. Lock free data structure do not use locks, still provide all the safety and liveness property. 4. Sample API is ConcurrentSkipListMap, which is lock free concurrent probabilistic map ( probably the most complicated implementation in Java)

Mahesh
  • 611
  • 9
  • 16
  • 1 - sometime they does. 2 - disagree, sometimes there are scenarios where you are obligated to use synchronization. 4 - ConcurrentSkipListMap indeed a complicated class, never used it before. I'll take a look what is it about. thanks. – jutky Dec 06 '10 at 16:29