Reducing the scope of a synchronized block in Java unexpectedly corrupts my ArrayList, why is that the case?

user_7736820 0
Viewed 84

A bit late, I have a Christmas special for you. There is a Santa class with an ArrayList of presents and a Map to keep track which children already have got their presents. Children modeled as threads constantly asking Santa for presents at the same time. For simplicity, each child receives exactly one (random) present.

Here is the method in the Santa class occasionally yielding a IllegalArgumentException because presents.size() is negative.

public Present givePresent(Child child) {
        if(gotPresent.containsKey(child) && !gotPresent.get(child)) {
            synchronized(this) {
                gotPresent.put(child, true);
                Random random = new Random();
                int randomIndex = random.nextInt(presents.size());
                Present present = presents.get(randomIndex);
                presents.remove(present);
                return present;
            }
        }
        return null;
}

However, making the whole method synchronized works just fine. I don't really understand the problem with the smaller sized synchronized block shown before. From my point of view, it should still assure that a present isn't assigned to a kid multiple times and there shouldn't be concurrent writes (and also reads) on the presents ArrayList. Could you please tell me why my assumption is wrong?

synchronization parallel-processing thread-safety multithreading java
1 Answers

That happens because the code contains a race condition. Let us use the following example to illustrate that race condition.

Imagine that Thread 1 reads

`if(gotPresent.containsKey(child) && !gotPresent.get(child))`

and it evaluates as true. While Thread 1 enters the synchronized block, another thread (i.e., Thread 2) also reads

if(gotPresent.containsKey(child) && !gotPresent.get(child))

before Thread 1 has had the time to do gotPresent.put(child, true);. Consequently, the aforementioned if also evaluates as true for Thread 2.

Thread 1 is inside the synchronized(this) and removes the present from the list of presents (i.e., presents.remove(present);). Now the size of the present list is 0. Thread 1 exits the synchronized block, while Thread 2 just enters it, and eventually calls

int randomIndex = random.nextInt(presents.size());

since presents.size() will return 0, and the random.nextInt implementation is as follows:

  public int nextInt(int bound) {
        if (bound <= 0)
            throw new IllegalArgumentException(BadBound);
        ...
    }

you get the IllegalArgumentException exception.

However, making the whole method synchronized works just fine.

Yes, because with

 synchronized(this) {
    if(gotPresent.containsKey(child) && !gotPresent.get(child)) {
            gotPresent.put(child, true);
            Random random = new Random();
            int randomIndex = random.nextInt(presents.size());
            Present present = presents.get(randomIndex);
            presents.remove(present);
            return present;
    }
 }

in the aforementioned race-condition example Thread 2 would have been waiting before the

if(gotPresent.containsKey(child) && !gotPresent.get(child))

and because Thread 1, before exiting the synchronized block, would have done

gotPresent.put(child, true);

by the time Thread 2 would have entered the synchronized block the following statement

!gotPresent.get(child)

would have evaluated as false, and consequently Thread 2 would have exit immediately without calling int randomIndex = random.nextInt(presents.size()); with a list of size 0.

Since the method that you have shown is being executed in parallel by multiple threads you should ensure mutual exclusion of the shared data structure among threads, namely gotPresent and presents. Which implies, for instance, that operations like containsKey, get, and put should be performed within the same synchronized block.

user_13668710
Related