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

Andrew Nuss andy at stagirite.com
Tue Jan 9 14:06:05 EST 2018


I'm currently using this class with all threads of the same priority. 
However, given the lack of this type of concurrent arraylist in
java.util.concurrent, I was hoping for a way to generalize the add()
function which mutates the "ref" AtomicReference in such a way that the
add() can be used by both high priority and lower priority threads. 
Again, my read on the commented critical section near the end of the
add() function is that if the compareAndSet() to MyArray with space for
growth succeeds in a low priority thread, and then immediately a high
priority thread calls add(), the high priority thread will deadlock in
the beginning of add() with a busy loop, while the low priority thread
is then unable to get any cpu cycles to free the critical section by
finishing to the point of ref.set(ar3).

This must be solveable, because I assume that ConcurrentHashMap can be
used for put() by both high priority and low priority concurrent
threads, and always makes progress in the high priority thread, because
there is no way a low priority thread can deadlock it.


On 01/09/2018 09:53 AM, Nathan and Ila Reynolds via Concurrency-interest
wrote:
> 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
>




More information about the Concurrency-interest mailing list