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

Nathan and Ila Reynolds nathanila at gmail.com
Tue Jan 9 12:53:09 EST 2018


Thread.yield() will not solve the problem.  The higher priority threads 
will only yield to other threads of the same priority. Hence, the lower 
priority thread will never get a chance to run on the processor.  You 
will have to block enough threads so that the lower priority threads are 
allowed to run.  In other words, you are facing priority inversion.

Is there some way the higher priority thread can do the work that the 
lower priority thread is trying to do?

-Nathan

On 1/9/2018 9:48 AM, Andrew Nuss via Concurrency-interest wrote:
> 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

-- 
-Nathan



More information about the Concurrency-interest mailing list