[concurrency-interest] how to use Thread.yield to fix ConcurrentIntArrayList

Andrew Nuss andy at stagirite.com
Tue Jan 9 11:48:37 EST 2018


I have written a growable concurrent array list of ints.  For stats accumulation.  I think its ok, except for the issue
that it must currently be used by threads of the same priority or there could be deadlock due to a lower priority thread
changing the "ref" in a temporary way in the add() function, and not being able to complete the final set due to a higher
priority thread also for example starting an add() and looping waiting for the final set to occur.

Any ideas on how to fix, such as using Thread.yield() in some effective way?

Or is there something already out there that does this?

public class ConcurrentIntArrayList {

    

    private static final int        DEFAULT_CAPACITY = 16;

    

    private static class MyArray {

        

        private volatile int[]        ar;            // effectively final, but volatile to flush elem values between cores

        private final int            size;

        private final int            readsize;    // may be less than the above if a value being appended

        

        private MyArray (int[] ar, int size, int readsize)

        {

            this.ar = ar;

            this.size = size;

            this.readsize = readsize;

        }

    }

    

    private final AtomicReference<MyArray>        ref;

    private final Object                        mutex = new Object();

    

    /**

     * Construct an underlying array with initial capacity of 16

     */

    public ConcurrentIntArrayList ()

    {

        ref = new AtomicReference<>(new MyArray(new int[DEFAULT_CAPACITY], 0, 0));

    }

    

    public int size ()

    {

        do {

            MyArray ar = ref.get();

            if (ar.size != ar.readsize)

                continue;                                    // this COULD happen

            return ar.size;

        } while (true);

    }

    

    public int get (int index)

    {

        do {

            MyArray ar = ref.get();

            if (index >= ar.size)

                throw new IndexOutOfBoundsException();

            if (index < ar.readsize)

                return ar.ar[index];

        } while (true);

    }

    

    public void add (int value)

    {

        do {

            MyArray ar = ref.get();

            if (ar.size != ar.readsize)

                continue;                                    // this COULD happen

            if (ar.size == ar.ar.length) {

                synchronized (mutex) {

                    MyArray ar2 = ref.get();

                    if (ar == ar2) {

                        // we're the first, grow it

                        int[] tempar = new int[ar.size*2];

                        System.arraycopy(ar.ar, 0, tempar, 0, ar.size);

                        MyArray ar3 = new MyArray(tempar, ar.size, ar.size);

                        if (!ref.compareAndSet(ar, ar3)) {

                            // since we're in the mutex with synchronized lock, no other thread can

                            // be growing the array and since this MyArray "ar" as no other capacity

                            // no one can be adding values outside the synchronized block, and

                            // since this class has no removals, this should NOT happen!

                            continue;

                        }

                        ar = ar3;

                    } else {

                        ar = ar2;

                        if (ar.size == ar.ar.length || ar.size != ar.readsize)

                            continue;                        // this COULD happen

                    }

                }

            }

            

            // reserve room for the value, if this succeeds, then from after these two statements

            // to the ref.set() below, the array is effectively locked relative to other setters

            MyArray ar2 = new MyArray(ar.ar, ar.size+1, ar.size);

            if (!ref.compareAndSet(ar, ar2))

                continue;                                    // this COULD happen

            

            // NOTE: this critical section could fail if threads of different priority

            // use the add function.  A low priority thread could be at this point in the process

            // and a high priority thread could be stuck in add() because of this.  Deadlock.

            ar.ar[ar.size] = value;

            MyArray ar3 = new MyArray(ar.ar, ar.size+1, ar.size+1);

            ref.set(ar3);

            break;

        } while (true);

    }

    

    public int[] toArray ()

    {

        do {

            MyArray ar = ref.get();

            if (ar.size != ar.readsize)

                continue;                                    // this COULD happen

            int[] tempar = new int[ar.size];

            System.arraycopy(ar.ar, 0, tempar, 0, ar.size);

            return tempar;

        } while (true);

    }

}




More information about the Concurrency-interest mailing list