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

David Holmes davidcholmes at aapt.net.au
Tue Jan 9 15:59:10 EST 2018


Andrew,

The priority-induced deadlock  you describe can only occur if you are running under a strict priority-preemptive scheduler (i.e SCHED_FIFO) and even then it depends on the number of processors and the number of always runnable threads and their priority. The OpenJDK is not designed to run in such environments - neither the algorithms in existing j.u.c classes, nor the VM itself. To solve your problem a thread that can't make progress must eventually block to ensure other threads can make progress.

David

> -----Original Message-----
> From: Concurrency-interest [mailto:concurrency-interest-bounces at cs.oswego.edu] On Behalf Of Andrew Nuss via Concurrency-
> interest
> Sent: Wednesday, January 10, 2018 2:49 AM
> To: concurrency-interest at cs.oswego.edu
> Subject: [concurrency-interest] how to use Thread.yield to fix ConcurrentIntArrayList
> 
> 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);
> 
>     }
> 
> }
> 
> 
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest



More information about the Concurrency-interest mailing list