Thread-safe prime number source

I am working on some multi-threaded code that requires a prime-number source.

The following code keeps an array of primes in memory, extending it as needed. It works in the 'int' domain, being careful to avoid overflows, and to keep the memory for storing the data relatively small.

it uses a state-based concurrency model... it keeps an immutable state that covers a range of primes (from 1..range). If a request is for some data that is outside that range, it will defer to a backup process which is single-threaded, where one thread extends the state. At any time, some other thread can query the state, and it is not blocked if the existing state covers its needs.

The idea is that only one thread is working at a time on calculating primes, and any pre-calculated primes are reused by other threads.

Additionally, during prime calculation, if one thread is calculating a really large extension, it regularly creates a new state, then 'breaks' out of the locked code, and allows any other waiting threads to use that new state if it is good enough.... The long-calculating thread will then start again on the next extension.

PrimeReserveInt.java

```
import java.util.Arrays;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicReference;

/**
* A thread-safe container that stores a list of prime numbers. The prime number
* list will be extended if needed to satisfy any request for primes up to
* MAX_PRIME_ALLOWED (Integer.MAX_VALUE). This is the 105097565th prime number
* (MAX_PRIME_NTH). Int primes require 4 bytes per number, or just less than
* 400MB to contain. Because of the way this code works, it occasionally needs
* to have two copies of the data in memory at a time, which leads to an
* occasional need for up to 1GB to do the work. Use -Xmx2g to get up these
* limits.
*
* Many sieve implementations would require an array of 2 Billion int values
* (8GB) to calculate this 100Millionth prime, so, in reality, this is a sma

Think I've found one concurrency issue :

in

private void extendStateTo(final PrimeState estate, final int to) {
    if (lock.compareAndSet(false, true)) {
        // we are the thread with the lock...
        try {
            // OK, we are the only thread in here, and the state is not good
            // enough...
            // create a new state that will be good enough....
            PrimeState nextstate = extendStateInternal(estate, to);
            if (!safestate.compareAndSet(estate, nextstate)) {
                throw new IllegalStateException(
                        "This can never happen, if it does, then shoot Monkey!");
            }
            estate.replaced();
        } finally {
            lock.compareAndSet(true, false);
        }
    } else {
        estate.waitReplaced();
    }

}

It is possible to start waiting for an ongoing replacement, when it has already signaled it is done.

Suppose thread T1 is doing the replacement and thread T2 arrives in this method. This scheduling is possible :

• T2 : lock.compareAndSet() returns false

• T1 : estate.replaced() executed.

• T2 : estate.waitReplaced() : starts waiting, but the signal has been missed.

T2 is now blocked until another thread triggers a replacement and it finishes. This may even never occur.

StackExchange Code Review Q#42636, answer score: 11