Synchronizing elements in an array

Question

I am new to multi-threading in Java and don't quite understand what's going on.

From online tutorials and lecture notes, I know that the synchronized block, which must be applied to a non-null object, ensures that only one thread can execute that block of code. Since an array is an object in Java, synchronize can be applied to it. Further, if the array stores objects, I should be able to synchronize each element of the array too.

My program has several threads updated an array of numbers, hence I created an array of Long objects:

synchronized (grid[arrayIndex]){
    grid[arrayIndex] += a.getNumber();
}

This code sits inside the run() method of the thread class which I have extended. The array, grid, is shared by all of my threads. However, this does not return the correct results while running the same program on one thread does.

score 7 · Accepted Answer · edited May 23 '17 at 12:10

7

This will not work. It is important to realize that grid[arrayIndex] += ... is actually replacing the element in the grid with a new object. This means that you are synchronizing on an object in the array and then immediately replacing the object with another in the array. This will cause other threads to lock on a different object so they won't block. You must lock on a constant object.

You can instead lock on the entire array object, if it is never replaced with another array object:

synchronized (grid) {
    // this changes the object to another Long so can't be used to lock
    grid[arrayIndex] += a.getNumber();
}

This is one of the reasons why it is a good pattern to lock on a final object. See this answer with more details:

Why is it not a good practice to synchronize on Boolean?

edited May 23 '17 at 12:10

Community

1
1

answered Sep 06 '12 at 16:40

Gray

115,027
24
293
354

1

You are right but it might be overkill to lock the whole array. You could set up a sibling array with lock objects final Object[] locks = new Object[arrayLength]; for (int i = 0; i< arrayLength; i++) { locks[i] = new Object(); } then synchronized (locks[arrayIndex]) { grid[arrayIndex] += a.getNumber(); } – ashirley Sep 06 '12 at 16:48
@ashirley It's worth noting that the array should never have its elements modified. It should be initialized, filled, and then never changed again. Unfortunately, declaring it as `final` isn't enough to guarantee that its inner elements won't change. – Brian Sep 06 '12 at 16:50
The OP is only protecting an array assignment @ashirley. The lock granularity does not matter in that case. – Gray Sep 06 '12 at 16:50
@Brian yeah, better than nothing though – ashirley Sep 06 '12 at 16:57
@Gray true, but worth pointing out incase it evolves into a more lengthy operation – ashirley Sep 06 '12 at 16:58
This is actually a parallel program, so to speed things up, it is not an option to lock the entire array. @ashirley, your suggestion seems good. However, when trying to implement it, I keep getting NullPointerExceptions in the threads. I initialised the locks array before calling the threads, and the threads keep giving NullPointerExceptions. However, I can access the objects from the main method that calls the threads – user929404 Sep 06 '12 at 17:40
@user929404, I hope it is a parallel program otherwise you should need to worry about `synchronized`. The cost of the `synchronized` call itself is _much_ more than the lock granularity you are supposedly saving with the array of locks. Creating an array of locks is just rarely done and _never_ to protect just an array assignment. If you were doing more work inside of the `synchronized` block then fine but otherwise keep it simple. You are not speeding it up by adding the array -- guaranteed. Take a look at my multithreading badge score if there is any doubt about my experience. – Gray Sep 06 '12 at 17:43
@user929404 Presumably there is other work happening before you need to take the lock, update the array and release the lock. This work can all still happen in parallel. Gray is right, it won't be any improvement when the only thing you need the lock for is a simple assignment, you would need to do something more complicated while holding the lock before it becomes worth it. In addition, the locks will need to be created before the Threads are started otherwise there is a risk that the lock objects aren't visible to the Threads. The easiest way of doing this would be in a static block – ashirley Sep 06 '12 at 18:02
@ashirley and (it won't let me tag gray), I see that locking for a single statement is unnecessary. But even when I implemented the array of locks, I still get incorrect results – user929404 Sep 06 '12 at 18:20
@gray Wouldn't locking on the entire array (grid) make the program sequential, as only one thread would be able to update the array at a time? This is what I was expecting and yet I am still getting incorrect results – user929404 Sep 06 '12 at 19:28
Locking on the entire array would make the assignments sequential @user929404. That's why you are doing it. All of the rest of the thread operations are in parallel. For example, you might want to move the `a.getNumber()` method out of the `synchronized` block if it does more than a field lookup. What "incorrect results" are you seeing? – Gray Sep 06 '12 at 19:34
@Gray By incorrect results, I mean they are wrong. I am comparing to a sequential version of the algorithm and the parallel version running on one thread. This is also a learning exercise, which is why I wanted to lock individual objects of the array (just to see for myself the differences in time). But at present, nothing is working. I locked the entire array, and I got wrong answers. I even put the aformentioned code into a synchronzied method and I still get wrong answers – user929404 Sep 06 '12 at 20:05
@Gray Very sorry for wasting your time, but I made a stupid error which has had me puzzled for hours. Previously in my code I typed "data.length" instead of "datalength" which screwed things up. – user929404 Sep 06 '12 at 20:13
Np @user929404. That's a good reason to make sure you camel-casing is good. `dataLength` might not confuse as much. :-) – Gray Sep 06 '12 at 20:18

score 2 · Answer 2 · answered Sep 06 '12 at 16:43

2

Another option would be to use an array of AtomicLong objects, and use their addAndGet() or getAndAdd() method. You wouldn't need synchronization to increment your objects, and multiple objects could be incremented concurrently.

answered Sep 06 '12 at 16:43

JB Nizet

678,734
91
1,224
1,255

Good one @JB. Of course you still pay the price for the memory barrier. – Gray Sep 06 '12 at 16:57

score 1 · Answer 3 · answered Sep 06 '12 at 16:48

The java class Long is immutable, you cannot change its value. So when you perform an action:

grid[arrayIndex] += a.getNumber();

it is not changing the value of grid[arrayIndex], which you are locking on, but is actually creating a new Long object and setting its value to the old value plus a.getNumber. So you will end up with different threads synchronizing on different objects, which leads to the results you are seeing

score 0 · Answer 4 · edited May 23 '17 at 10:24

0

The synchronized block you have here is no good. When you synchronize on the array element, which is presumably a number, you're synchronizing only on that object. When you reassign the element of the array to a different object than the one you started with, the synchronization is no longer on the correct object and other threads will be able to access that index.

One of these two options would be more correct:

private final int[] grid = new int[10];

synchronized (grid) {
    grid[arrayIndex] += a.getNumber();
}

If grid can't be final:

private final Object MUTEX = new Object();

synchronized (MUTEX) {
    grid[arrayIndex] += a.getNumber();
}

If you use the second option and grid is not final, any assignment to grid should also be synchronized.

synchronized (MUTEX) {
    grid = new int[20];
}

Always synchronize on something final, always synchronize on both access and modification, and once you have that down, you can start looking into other locking mechanisms, such as Lock, ReadWriteLock, and Semaphore. These can provide more complex locking mechanisms than synchronization that is better for scenarios where Java's default synchronization alone isn't enough, such as locking data in a high-throughput system (read/write locking) or locking in resource pools (counting semaphores).

edited May 23 '17 at 10:24

Community

1
1

answered Sep 06 '12 at 16:47

Brian

17,079
6
43
66

I disagree with the last paragraph. Those locks require a lot more careful programming (try/finally) so cannot be called "safer" nor "more predictable" nor do they "avoid a lot of problems". The opposite is true. More powerful and in certain situations better performance, yes. – Gray Sep 06 '12 at 17:01
Also in the first, you don't synchronize on a number, you synchronize on an object. You also use the word value which is misleading. – Gray Sep 06 '12 at 17:11
@Gray I'll concede on the word safe and remove it. As long as you're following the proper patterns for any synchronization, it'll be safe. As for predictable, native Java synchronization _is_ unpredictable. The thread that will receive the monitor if two or more threads is waiting on it is random. With other systems, I can turn fairness on and make it queue threads and give the lock first-come-first-serve instead of random order, preventing things like thread starvation. As per your second comment, I agree, the wording has been changed. – Brian Sep 06 '12 at 17:17
Interesting RE: predictability but I suspect this is an academic issue wrt to the language definition @Brian. Do you know of any situations where this is true in practice? I think it is extremely dangerous to go around using `Lock` instead of `synchronized` for this reason. _Especially_ when you are counseling newbie thread programmers on SO. – Gray Sep 06 '12 at 17:23
@Gray As far as I understand it, the first thread that the scheduler wakes up that is blocking on the monitor is the one that gets it, so in practice, it's possible if the processor scheduler's algorithm wakes the threads in an order that always puts one of the threads behind the others. I guess in a more practical sense, most systems (Windows and *NIX) have good scheduling algorithms that would likely circumvent more serious starvation issues. But it's nice to have the guarantee when working with systems where you want locks served FIFO, like in time-sensitive request/response systems. – Brian Sep 06 '12 at 17:34
I've been writing such systems for a while without issue. I suspect that programming issues are more the problem @Brian. Such as the following link. Either way, I learned something so thanks. http://stackoverflow.com/a/2960811/179850 – Gray Sep 06 '12 at 17:37
@Gray Thank you for the link :) It depends on the system, but I agree, usually the locking implementation isn't as important as simply having it, and so most systems would probably do well enough without fairness. Knowing that fairness is there isn't a bad thing, though. – Brian Sep 06 '12 at 17:47
Agreed @Brian. I just worry that some guy is going to replace all of his `synchronized` blocks with `Lock` calls because of a post like this. The _definition_ of premature optimization. When answering SO questions, be sure to realize your audience. :-) – Gray Sep 06 '12 at 17:49
@Gray Of course, since you put it that way, I've changed the answer to reflect use cases of the other mechanisms, and simply removed my other wording to not be biased. Thanks for your input, I appreciate it :) – Brian Sep 06 '12 at 18:01
Your rewording looks much better @Brian. Thanks dude. – Gray Sep 06 '12 at 18:03

Synchronizing elements in an array

4 Answers4

Linked