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

Nathan and Ila Reynolds nathanila at gmail.com
Tue Jan 9 14:23:02 EST 2018


ConcurrentHashMap uses a striped lock to protect the contents. If I 
remember right, each array element in the table gets its own lock.  
However, there are others on this list that can tell you every detail 
about ConcurrentHashMap.

-Nathan

On 1/9/2018 12:06 PM, Andrew Nuss via Concurrency-interest wrote:
> 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
>
> _______________________________________________
> 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