Is there a better AtomicInteger compare feature for race conditions?

Question

I am trying to write a decorator to an existing class that rejects if there are not enough resources available. Here is an example version of the code with no multithreading at all:

public interface Handler {
    boolean handleTask(Task myTask); // returns true if successful, false if failure
}

public interface Task {
    int getResources();
    // Among other things
}

public BlockingHandler implements Handler {
    private int occupied;
    private final int limit;

    private final Handler backingHandler;

    BlockingHandler(Handler backingHandler) {
        this.backingHandler = backingHandler;
    }

    @Override
    public boolean handleTask(Task myTask) {
        if(myTask.getResources() + occupied > limit) return false;
        occupied += myTask.getResources();
        return backingHandler.handleTask(myTask);
    }

    // Don't worry about this part, I'm not doing it this way, I just want the code to make sense
    public void notifyResourceRelease(Task finishedTask) {
        if(finishedTask.isDone()) occupied -= myTask.getResources();
    }
}

The problem is, this handleTask method can be called on multiple threads, and I want to be very fast (i.e. avoid synchronized). It's not enough to make occupied be volatile or an AtomicInteger, because a race condition is still possible, for instance:

Thread 1: call handleTask
Thread 1: call atomicOccupied.get()
Thread 2: call handleTask
Thread 1: evaluate if condition
Thread 2: call atomicOccupied.get()

Is it possible to do this without using synchronized? Is there, for instance, an extended AtomicInteger class with a more powerful compareAndSet?

Sounds like a job for a [semaphore](http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Semaphore.html). — assylias, Feb 24 '14 at 14:47
Why don't you use an ArrayBlockingQueue? That class is built for this type of functionality — JoseM, Feb 24 '14 at 14:48
I believe this has already been answered. http://stackoverflow.com/questions/4210292/can-atomicinteger-replace-synchronized — D-Klotz, Feb 24 '14 at 14:49
@durron597 You can use `if (!semaphore.tryAcquire()) throw new SomeException();`. It is essentially an AtomicInteger under the hood, so I'd use that instead of reimplementing a very similar logic manually. — assylias, Feb 24 '14 at 14:49
@assylias Never mind I misremembered how `Semaphore` works, I remembered `.acquire()` but not `.tryAcquire()` — durron597, Feb 24 '14 at 14:51

score 6 · Accepted Answer · edited May 23 '17 at 11:50

6

Is it possible to do this without using synchronized? Is there, for instance, an extended AtomicInteger class with a more powerful compareAndSet?

You should be able to do that without a synchronized block. No there isn't more extended AtomicInteger class.

If I'm understanding you requirements, you can do this in a while loop. Something like:

final AtomicInteger occupied = new AtomicInteger();
...
int prev;
int numResources = myTask.getResources();
do {
    prev = occupied.get();
    if (numResources + prev > limit) return false;
} while (!occupied.compareAndSet(prev, prev + numResources));

This loop will spin updating the occupied if possible. If it reaches the limit it will return false. You need the spin because if other threads have updated the occupied count between when you get the previous value and you go to adjust the value then you will need to loop around and get the occupied count again. This is a typical pattern.

Also, you need to use AtomicInteger over volatile because you are using compareAndSet. See this question for more information:

What is the difference between using a volatile primitive over atomic variables?

edited May 23 '17 at 11:50

Community

1
1

answered Feb 24 '14 at 14:49

Gray

115,027
24
293
354

I thought of this but I wasn't sure it was faster than `synchronized` – durron597 Feb 24 '14 at 14:53
In most situations, it will be faster than blocking @durron597. The only exception is if there are a ton of threads and the occupied update is highly contended. Even then it might outperform a `synchronized` but a blocking queue or something might outperform both. – Gray Feb 24 '14 at 14:54
@durron597 Consider that a `synchronized` does at least one volatile read (`AtomicInteger.get` and one volatile set `AtomicInteger.set`). This would certainly be higher performing. – John Vint Feb 24 '14 at 14:55
I think the answer is "yes it is required" but I just want to check: is `AtomicInteger` still required or will `volatile` suffice? – durron597 Feb 24 '14 at 14:55
3

Use AtomicInteger and declare it final. It wraps a volatile field (with some CAS/atomic instructions), but you need not worry about it. The volatile increment of a primitive is not atomic, there are plenty of explanations on why. – John Vint Feb 24 '14 at 14:57
`AtomicInteger` is required because of the `compareAndSet(...)` @durron597. – Gray Feb 24 '14 at 14:58

Is there a better AtomicInteger compare feature for race conditions?

1 Answers1