Java – lock free protection for synchronous acquisition / release

I have a shared temporary file resource, divided into 4K blocks (or some such value) Each 4K in the file is represented by a zero - based index For this shared resource, I track the 4K block index in use and always return the lowest unused 4K block index, or - 1 if all are in use

The resourceset class of the index has a public get and release method. They all use synchronous locks, and its duration is about equivalent to generating four random numbers (expensive, CPU wise)

Therefore, as can be seen from the following code, I use atomicinteger "count semaphores" to prevent a large number of threads from entering the critical area at the same time on acquire(), and there are too many threads returning - 1 (not available now)

At present, I use the constant of 100 as a tight CAS loop to try to increase the atomic integer in the acquisition, set the constant of the maximum number of threads to 10, and then allow entry into the critical area, which is enough to generate contention My question is, what should these constants be for medium to high load servlet engines? How many threads are trying to access these 4K blocks?

public class ResourceSet {

    // ??? what should this be
    // maximum number of attempts to try to increment with CAS on acquire
    private static final int    CAS_MAX_ATTEMPTS = 50;

    // ??? what should this be
    // maximum number of threads contending for lock before returning -1 on acquire
    private static final int    CONTENTION_MAX = 10;

    private AtomicInteger        latch = new AtomicInteger(0);

    ... member variables to track free resources

    private boolean aquireLatchForAquire ()
    {
        for (int i = 0; i < CAS_MAX_ATTEMPTS; i++) {
            int val = latch.get();
            if (val == -1)
                throw new AssertionError("bug in ResourceSet");        // this means more threads than can exist on any system,so its a bug!
            if (!latch.compareAndSet(val,val+1))
                continue;
            if (val < 0 || val >= CONTENTION_MAX) {
                latch.decrementAndGet();
                // added to fix BUG that comment pointed out,thanks!
                return false;
            }
        }
        return false;
    }

    private void aquireLatchForRelease ()
    {
        do {
            int val = latch.get();
            if (val == -1)
                throw new AssertionError("bug in ResourceSet");    // this means more threads than can exist on any system,so its a bug!
            if (latch.compareAndSet(val,val+1))
                return;
        } while (true);
    }

    public ResourceSet (int totalResources)
    {
        ... initialize
    }

    public int acquire (ResourceTracker owned)
    {        
        if (!aquireLatchForAquire())
            return -1;

        try {
            synchronized (this) {
                ... algorithm to compute minimum free resoource or return -1 if all in use
                return resourceindex;
            }
        } finally {
            latch.decrementAndGet();
        }
    }

    public boolean release (ResourceIter iter)
    {
        aquireLatchForRelease();
        try {
            synchronized (this) {
                ... iterate and release all resources
            }
        } finally {
            latch.decrementAndGet();
        }
    }
}

Solution

Writing an excellent and high-performance spin lock is actually very complex and requires a good understanding of memory barriers Just choosing a constant doesn't cut it. It's definitely not portable Google's gperftools has an example you can see, but it may be more complex than you need

If you really want to reduce lock contention, you may need to consider using a more granular and optimistic solution A simple way is to divide your blocks into n groups and associate locks with each group (also known as stripping) This will help reduce contention and improve throughput, but will not help reduce latency You can also associate atomicboolean with each block and CAS to get it (try again in case of failure) Be careful when dealing with lockless algorithms because they are often difficult to do correctly If you do it right, it can greatly reduce the delay of getting blocks

Please note that it is difficult to propose a finer grained method without knowing what the block selection algorithm looks like I also assume that you do have a performance problem (it has been analyzed and everything is there)

Although I'm on it, your spiral lock implementation is flawed You should never rotate directly on CAS because you are sending a memory barrier Any serious contention (related to the thundering herd problem) will be very slow At a minimum, first check the availability of variables before CAS (it will be simple if there is no barrier reading) It is better not to have all threads rotate at the same value This should prevent associated cache rows from Ping - pong between your cores

Please note that I do not know which type of memory barrier is associated with atomic operations in Java, so my above suggestions may not be optimal or correct

Finally, the art of multiprocessor programming is an interesting book that allows me to better understand all the non feelings I spew out in this answer