how to use Thread.yield to fix ConcurrentIntArrayList

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

how to use Thread.yield to fix ConcurrentIntArrayList

JSR166 Concurrency mailing list
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
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: how to use Thread.yield to fix ConcurrentIntArrayList

JSR166 Concurrency mailing list
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
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

--
-Nathan

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: how to use Thread.yield to fix ConcurrentIntArrayList

JSR166 Concurrency mailing list
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
>> [hidden email]
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: how to use Thread.yield to fix ConcurrentIntArrayList

JSR166 Concurrency mailing list
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
>>> [hidden email]
>>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

--
-Nathan

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: how to use Thread.yield to fix ConcurrentIntArrayList

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
Your comment on the "ar" field suggests that you expect stores into the
array to behave as volatile stores. This isn't the case. Only the
pointer to ar itself is volatile. I think you want a final reference to
an AtomicIntegerArray instead.

On 2018-01-09 08: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
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: how to use Thread.yield to fix ConcurrentIntArrayList

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
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:[hidden email]] On Behalf Of Andrew Nuss via Concurrency-
> interest
> Sent: Wednesday, January 10, 2018 2:49 AM
> To: [hidden email]
> 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
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: how to use Thread.yield to fix ConcurrentIntArrayList

JSR166 Concurrency mailing list
David,

Are you saying that my code works on openjdk as is, or should the loops
at the beginning of each of my functions, loop say 20 times, and then if
no progress, do a Thread.sleep?  Also Brian O'Neill responded that the
volatile marker to the effectively final "ar" member of MyArray should
be final.  Does it really matter in my use case?

Andrew

On 01/09/2018 12:59 PM, David Holmes wrote:
> 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
>
>


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: how to use Thread.yield to fix ConcurrentIntArrayList

JSR166 Concurrency mailing list
Hi Andrew,

I have not analysed the correctness, or otherwise, of your code. I'm only pointing out that you only need to be concerned about issues around thread priority if running in a full priority-preemptive scheduling environment - in which case you have even more to worry about as OpenJDK is not designed for such an environment and may itself contain livelocks either in library code or the VM (and of course suffer from priority inversion). If you want to write your code in a way that is immune to priority issues then you can't spin indefinitely if that might prevent the thread you are waiting for from ever running - hence you need to degrade from a spin to a block.

Declaring an array reference as volatile is seldom what you need because it has no effect on accessing the array elements - a read of ar[i] will be a volatile read of ar but not of ar[i]. A write to ar[i] will be a volatile read of ar, and a plain write to ar[i].

David

> -----Original Message-----
> From: Andrew Nuss [mailto:[hidden email]]
> Sent: Wednesday, January 10, 2018 9:53 AM
> To: [hidden email]
> Cc: [hidden email]
> Subject: Re: [concurrency-interest] how to use Thread.yield to fix ConcurrentIntArrayList
>
> David,
>
> Are you saying that my code works on openjdk as is, or should the loops at the beginning of each of my functions, loop say 20 times,
> and then if no progress, do a Thread.sleep?  Also Brian O'Neill responded that the volatile marker to the effectively final "ar" member
> of MyArray should be final.  Does it really matter in my use case?
>
> Andrew
>
> On 01/09/2018 12:59 PM, David Holmes wrote:
> > 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
> >
> >


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: how to use Thread.yield to fix ConcurrentIntArrayList

JSR166 Concurrency mailing list
I highly encourage you to not use Thread.sleep() for blocking. The
thread may sleep for longer than is needful and the performance may
suffer.  I have fixed a lot of performance issues where Thread.sleep()
was the problem.  When the code was adapted so that the thread could be
woken up, then the performance issues went away.

-Nathan

On 1/9/2018 5:08 PM, David Holmes via Concurrency-interest wrote:

> Hi Andrew,
>
> I have not analysed the correctness, or otherwise, of your code. I'm only pointing out that you only need to be concerned about issues around thread priority if running in a full priority-preemptive scheduling environment - in which case you have even more to worry about as OpenJDK is not designed for such an environment and may itself contain livelocks either in library code or the VM (and of course suffer from priority inversion). If you want to write your code in a way that is immune to priority issues then you can't spin indefinitely if that might prevent the thread you are waiting for from ever running - hence you need to degrade from a spin to a block.
>
> Declaring an array reference as volatile is seldom what you need because it has no effect on accessing the array elements - a read of ar[i] will be a volatile read of ar but not of ar[i]. A write to ar[i] will be a volatile read of ar, and a plain write to ar[i].
>
> David
>
>> -----Original Message-----
>> From: Andrew Nuss [mailto:[hidden email]]
>> Sent: Wednesday, January 10, 2018 9:53 AM
>> To: [hidden email]
>> Cc: [hidden email]
>> Subject: Re: [concurrency-interest] how to use Thread.yield to fix ConcurrentIntArrayList
>>
>> David,
>>
>> Are you saying that my code works on openjdk as is, or should the loops at the beginning of each of my functions, loop say 20 times,
>> and then if no progress, do a Thread.sleep?  Also Brian O'Neill responded that the volatile marker to the effectively final "ar" member
>> of MyArray should be final.  Does it really matter in my use case?
>>
>> Andrew
>>
>> On 01/09/2018 12:59 PM, David Holmes wrote:
>>> 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
>>>
>>>
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

--
-Nathan

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest