Java Threads with ConcurrentModificationException

Question

I'm currently working on my first multithreaded software - a program, which calculates prime numbers...
Basically I create n (number of Threads) runnables. These runnables are added to an ArrayList. They check, whether a number is a prime. If the number is a prime I add it into an long array for later use. Since I want the primes to be in correct order in this array I need specific Threads to wait for others. I do this by looping through the ArrayList (see above) and wait for the threads, which check a lower number.
After a thread is done I want to remove it from the given ArrayList, but I cant since the other threads are still looping through it (This is the reason why the ConcurrentModificationException occurs I guess - This is my first time working with threads...).

I honestly hope that any of you guys can help me :)
Thank your really much!

Matthias

My runnable class (I just create four objects of this class in the main method):

import java.util.ArrayList;

public class PrimeRunnable implements Runnable {

    //Static Util
    public static ArrayList<PrimeRunnable> runningThreads = new ArrayList<PrimeRunnable>();
    public static long[] primes;
    public static int nextFreeIndex = 1;
    public static long nextPossiblePrime = 3;

    //Object specific
    private long numberToCheck;
    private Thread primeThread;
    private String threadName;
    private long threadID;

    public PrimeRunnable() {
        numberToCheck = nextPossiblePrime;
        increaseNextPossiblePrime();

        threadName = "ThreadToCheck" + numberToCheck;
        threadID = numberToCheck;

        runningThreads.add(this);
    }

    @Override
    public void run() {
        boolean isPrime = true;
        double sqrtOfPossiblePrime = Math.sqrt(numberToCheck);

        long lastDevider = 0;

        for(int index = 0; index < nextFreeIndex; index++) {
            lastDevider = primes[index];
            if(numberToCheck%primes[index] == 0) {
                isPrime = false;
                break;
            }
            if(primes[index] > sqrtOfPossiblePrime) {
                break;
            }
        }

        while(lastDevider < sqrtOfPossiblePrime) {
            lastDevider += 1;

            if(numberToCheck%lastDevider == 0) {
                isPrime = false;
                break;
            }
        }

        if(isPrime) {
            //Wait for lower Threads.

            for(PrimeRunnable runnable : runningThreads) {
                if(runnable.getThreadID() < this.getThreadID()) {
                    try {
                        runnable.primeThread.join();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }

            primes[nextFreeIndex] = numberToCheck;
            increaseNextFreeIndex();
            System.out.println(numberToCheck);
        }
        runningThreads.remove(this);
    }

    public void start() {
        if(primeThread == null) {
            primeThread = new Thread(this, threadName);
        }

        primeThread.start();
    }

    public void reset() {
        numberToCheck = nextPossiblePrime;
        increaseNextPossiblePrime();

        threadName = "ThreadToCheck" + numberToCheck;
        threadID = numberToCheck;

        //No need to readd into runningThread, since we only manipulate an already existing object.
        primeThread = new Thread(this, threadName);
        primeThread.start();
    }

    public static void setUpperBorder(int upperBorder) {
        if(primes == null) {
            primes = new long[upperBorder];
            primes[0] = 2;
        } else {
            System.err.println("You are not allowed to set the upper border while running.");
        }
    }

    public long getNumberToCheck() {
        return numberToCheck;
    }

    private void increaseNextPossiblePrime() {
        nextPossiblePrime += 2;
    }

    private void increaseNextFreeIndex() {
        nextFreeIndex += 2;
    }

    public long getThreadID() {
        return threadID;
    }

    public boolean isAlive() {
        return primeThread.isAlive();
    }
}

Answer 1

I was able to replicate the issue and fix it using Java implementation of a concurrent list CopyOnWriteArrayList

Here's my main class

public class PrimeRunnableMain {

    public static void main(String[] args) {
        PrimeRunnable.setUpperBorder(10);
        PrimeRunnable primeRunnable1 = new PrimeRunnable();
        PrimeRunnable primeRunnable2 = new PrimeRunnable();
        PrimeRunnable primeRunnable3 = new PrimeRunnable();
        PrimeRunnable primeRunnable4 = new PrimeRunnable();
        primeRunnable1.start();
        primeRunnable2.start();
        primeRunnable3.start();
        primeRunnable4.start();
    }
}

and here's PrimeRunnable

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class PrimeRunnable implements Runnable {

    // Static Util
    public static List<PrimeRunnable> runningThreads = new CopyOnWriteArrayList<PrimeRunnable>();
    public static long[] primes;
    public static int nextFreeIndex = 1;
    public static long nextPossiblePrime = 3;

    // Object specific
    private long numberToCheck;
    private Thread primeThread;
    private String threadName;
    private long threadID;

    public PrimeRunnable() {
        numberToCheck = nextPossiblePrime;
        increaseNextPossiblePrime();

        threadName = "ThreadToCheck" + numberToCheck;
        threadID = numberToCheck;

        runningThreads.add(this);
    }

    @Override
    public void run() {
        boolean isPrime = true;
        double sqrtOfPossiblePrime = Math.sqrt(numberToCheck);

        long lastDevider = 0;

        for (int index = 0; index < nextFreeIndex; index++) {
            lastDevider = primes[index];
            if (numberToCheck % primes[index] == 0) {
                isPrime = false;
                break;
            }
            if (primes[index] > sqrtOfPossiblePrime) {
                break;
            }
        }

        while (lastDevider < sqrtOfPossiblePrime) {
            lastDevider += 1;

            if (numberToCheck % lastDevider == 0) {
                isPrime = false;
                break;
            }
        }

        if (isPrime) {
            // Wait for lower Threads.

            for (PrimeRunnable runnable : runningThreads) {
                if (runnable.getThreadID() < this.getThreadID()) {
                    try {
                        runnable.primeThread.join();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }

            primes[nextFreeIndex] = numberToCheck;
            increaseNextFreeIndex();
            System.out.println(numberToCheck);
        }
        runningThreads.remove(this);
    }

    public void start() {
        if (primeThread == null) {
            primeThread = new Thread(this, threadName);
        }

        primeThread.start();
    }

    public void reset() {
        numberToCheck = nextPossiblePrime;
        increaseNextPossiblePrime();

        threadName = "ThreadToCheck" + numberToCheck;
        threadID = numberToCheck;

        // No need to readd into runningThread, since we only manipulate an
        // already existing object.
        primeThread = new Thread(this, threadName);
        primeThread.start();
    }

    public static void setUpperBorder(int upperBorder) {
        if (primes == null) {
            primes = new long[upperBorder];
            primes[0] = 2;
        } else {
            System.err
                    .println("You are not allowed to set the upper border while running.");
        }
    }

    public long getNumberToCheck() {
        return numberToCheck;
    }

    private void increaseNextPossiblePrime() {
        nextPossiblePrime += 2;
    }

    private void increaseNextFreeIndex() {
        nextFreeIndex += 2;
    }

    public long getThreadID() {
        return threadID;
    }

    public boolean isAlive() {
        return primeThread.isAlive();
    }
}

Answer 2

The main distinction between fail-fast and fail-safe iterators is whether or not the collection can be modified while it is being iterated. Fail-safe iterators allow this; fail-fast iterators do not.

Fail-fast iterators operate directly on the collection itself. During iteration, fail-fast iterators fail as soon as they realize that the collection has been modified (i.e., upon realizing that a member has been added, modified, or removed) and will throw a ConcurrentModificationException. Some examples include ArrayList, HashSet, and HashMap (most JDK1.4 collections are implemented to be fail-fast). Fail-safe iterates operate on a cloned copy of the collection and therefore do not throw an exception if the collection is modified during iteration. Examples would include iterators returned by ConcurrentHashMap or CopyOnWriteArrayList.

Answer 3

What about a PrimeListener class that contains a synchronized method publishPrime that inserts the prime in the correct position in the list? Inserting at the right position into the list should not take too much time, if you start at the last index of a LinkedList.

Alternatively you could also insert it into a SortedSet (implementation: TreeSet). I presume you don't want any duplicate primes anyway. In that case synchronizedSortedSet may be directly used instead of the listener.

Note that you still seem rather stuck on lower level structures. When programming concurrently on Java it pays off to use the higher level constructs (executors, futures, concurrent queue's etc. etc.).