non-concurrent collection visibility question

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

non-concurrent collection visibility question

JSR166 Concurrency mailing list
 
Hi all,
 
First of, Happy New Year everyone and all the best in 2018!
 
Secondly, have a question that should be easy to answer for most of you here .
 
In some class (say AggregateBuffer) that has a method dispatching multiple buffers, we have a collection that holds references to those ring buffers:
 
final List<Buffer> buffers = new ArrayList<>(); //simple array list, non-concurrent collection
 
 
Then we have a method to add a new publisher (effectively a new buffer). The buffer gets created and gets added to the array list. We know that this method always gets called by the same bootstrap-thread that wires all the components.
 
 
Publisher<M> addPublisher()
{
       Buffer buffer = new Buffer();
       buffers.add(ringBuffer);
}
 
And finally we have a dispatching thread that calls receive() method on the AggregateBuffer class scrolling over the buffer collection and dispatching each buffer one by one using some dispatching strategy (say attempt to read up to N messages at a time from each buffer)
 
 
    int receive()
    {
        for (Buffer buf:buffers)//the line in question
        {
            buffer.read()
        }
    }
 
The question is -
 
    if we make sure that the dispatcher-thread gets created and gets passed the reference to the AggregateBuffer class AFTER all the calls to addPublisher() are done with, is it guaranteed that dispatcher-thread will see all the changes to the non-concurrent "buffers" collection and if so then what guarantees that? In other words – is it possible that a dispatcher-thread may see an empty “buffers” collection?
   
 
thank you


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

Re: non-concurrent collection visibility question

JSR166 Concurrency mailing list
Hi Andriy,

The answer to your question lies in the specification of "AFTER" order of actions that you are using.

If by "AFTER" you mean an "order according to wall clock", then there is nothing you can say about visibility based on such an order.

If by "AFTER" you mean happens-before order, that is B AFTER A if and only if A happens-before B, then according to your description, all writes to buffers list happens-before all reads done by receive() method. This means that your receive() method is guaranteed to see all buffers that were added to buffers list.

However, since you did not specify "AFTER" in the question, no one can say what it means, except for you. So could you please specify what did you mean by "AFTER"?

I would also discourage anyone from using such misleading words like before/after (without specifying the order you are talking about), immediately or visible immediately when reasoning about visibility in multithread programming.

Regards,
Valentin

------------------------------

Message: 2
Date: Sat, 6 Jan 2018 16:06:41 +0000 (UTC)
From: Andriy Bukatar <[hidden email]>
To: "[hidden email]"
        <[hidden email]>
Subject: [concurrency-interest] non-concurrent collection visibility
        question
Message-ID: <[hidden email]>
Content-Type: text/plain; charset="utf-8"

  Hi all,
 First of, Happy New Year everyone and all the best in 2018! Secondly, have a question that should be easy to answer for most of you here . In some class (say AggregateBuffer) that has a method dispatching multiple buffers, we have a collection that holds references to those ring buffers: final List<Buffer> buffers = new ArrayList<>(); //simple array list, non-concurrent collection  Then we have a method to add a new publisher (effectively a new buffer). The buffer gets created and gets added to the array list. We know that this method always gets called by the same bootstrap-thread that wires all the components.  Publisher<M> addPublisher(){       Buffer buffer = new Buffer();       buffers.add(ringBuffer);} And finally we have a dispatching thread that calls receive() method on the AggregateBuffer class scrolling over the buffer collection and dispatching each buffer one by one using some dispatching strategy (say attempt to read up to N messages at a time from each buffer)      int receive()    {        for (Buffer buf:buffers)//the line in question        {            buffer.read()        }    } The question is -     if we make sure that the dispatcher-thread gets created and gets passed the reference to the AggregateBuffer class AFTER all the calls to addPublisher() are done with, is it guaranteed that dispatcher-thread will see all the changes to the non-concurrent "buffers" collection and if so then what guarantees that? In other words – is it possible that a dispatcher-thread may see an empty “buffers” collection?    thank you
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20180106/e3f1404d/attachment.html>

------------------------------

Subject: Digest Footer

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


------------------------------

End of Concurrency-interest Digest, Vol 156, Issue 3
****************************************************


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

Re: non-concurrent collection visibility question

JSR166 Concurrency mailing list
Thanks Valentin.
Yes, the devil is in the details.

I could rephrase the question as follows:

There’s a class C containing the non-concurrent list L.

Thread T1 adds a few items to the list L. 

Thread T2 starts (note it did not exist at the time when T1 was updating the list L). Thread T2 gets a reference to C and iterates over its list L.

So “AFTER” in this case is a “wall clock distance” between the time T1 performs the last update to L and the time when T2 starts. 

I know the answer to this question when T2 starts iterating over L before (or at the time when) T1 performs updates to non-concurrent L - no visibility guarantees whatsoever. 

The question I suppose is whether non-existence of T2 at the time of the last update to L has any impact on visibility of the contents of L.

Not sure if this makes it any clearer and my apologies if it does not.

Thank you


On Jan 6, 2018, at 11:40 AM, Valentin Kovalenko <[hidden email]> wrote:

Hi Andriy,

The answer to your question lies in the specification of "AFTER" order of actions that you are using.

If by "AFTER" you mean an "order according to wall clock", then there is nothing you can say about visibility based on such an order.

If by "AFTER" you mean happens-before order, that is B AFTER A if and only if A happens-before B, then according to your description, all writes to buffers list happens-before all reads done by receive() method. This means that your receive() method is guaranteed to see all buffers that were added to buffers list.

However, since you did not specify "AFTER" in the question, no one can say what it means, except for you. So could you please specify what did you mean by "AFTER"?

I would also discourage anyone from using such misleading words like before/after (without specifying the order you are talking about), immediately or visible immediately when reasoning about visibility in multithread programming.

Regards,
Valentin

------------------------------

Message: 2
Date: Sat, 6 Jan 2018 16:06:41 +0000 (UTC)
From: Andriy Bukatar <[hidden email]>
To: "[hidden email]"
        <[hidden email]>
Subject: [concurrency-interest] non-concurrent collection visibility
        question
Message-ID: <[hidden email]>
Content-Type: text/plain; charset="utf-8"

  Hi all,
 First of, Happy New Year everyone and all the best in 2018! Secondly, have a question that should be easy to answer for most of you here . In some class (say AggregateBuffer) that has a method dispatching multiple buffers, we have a collection that holds references to those ring buffers: final List<Buffer> buffers = new ArrayList<>(); //simple array list, non-concurrent collection  Then we have a method to add a new publisher (effectively a new buffer). The buffer gets created and gets added to the array list. We know that this method always gets called by the same bootstrap-thread that wires all the components.  Publisher<M> addPublisher(){       Buffer buffer = new Buffer();       buffers.add(ringBuffer);} And finally we have a dispatching thread that calls receive() method on the AggregateBuffer class scrolling over the buffer collection and dispatching each buffer one by one using some dispatching strategy (say attempt to read up to N messages at a time from each buffer)      int receive()    {        for (Buffer buf:buffers)//the line in question        {            buffer.read()        }    } The question is -     if we make sure that the dispatcher-thread gets created and gets passed the reference to the AggregateBuffer class AFTER all the calls to addPublisher() are done with, is it guaranteed that dispatcher-thread will see all the changes to the non-concurrent "buffers" collection and if so then what guarantees that? In other words – is it possible that a dispatcher-thread may see an empty “buffers” collection?    thank you
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20180106/e3f1404d/attachment.html>

------------------------------

Subject: Digest Footer

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


------------------------------

End of Concurrency-interest Digest, Vol 156, Issue 3
****************************************************


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

Re: non-concurrent collection visibility question

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
Thank you for the clarification. In this case, read actions in T2 are not ordered by happens-before order (HB) with the write actions in T1. And all these actions act on the same shared variables (fields of the list L). So by definition, you have a data race. And there is no guarantee that you will correctly read all the buffers that T1 added to the L.

I want to add, that generally there is no guarantee that you will see a non-null when reading L field from T2. However is your case this field is final, and the semantics of a final field guarantees HB* between a write to the field L (T1 writes there a reference to a new ArrayList()) and a read of the reference from L field in T2. Unfortunately, this HB* is not transitive with the normal HB, hence you don't have guarantees you initially asked about.

And one more thing: if you had started T2 from T1 after (in program order (PO)) T1 added all buffers to L, then you would have had HB between all actions in T1 (which are ordered in PO before the start of T2) and all actions in T2. But as far as I understand, your case is different and T2 is started not from T1.

Regards,
Valentin

On 6 January 2018 at 20:07, Andriy Bukatar <[hidden email]> wrote:
Thanks Valentin.
Yes, the devil is in the details.

I could rephrase the question as follows:

There’s a class C containing the non-concurrent list L.

Thread T1 adds a few items to the list L. 

Thread T2 starts (note it did not exist at the time when T1 was updating the list L). Thread T2 gets a reference to C and iterates over its list L.

So “AFTER” in this case is a “wall clock distance” between the time T1 performs the last update to L and the time when T2 starts. 

I know the answer to this question when T2 starts iterating over L before (or at the time when) T1 performs updates to non-concurrent L - no visibility guarantees whatsoever. 

The question I suppose is whether non-existence of T2 at the time of the last update to L has any impact on visibility of the contents of L.

Not sure if this makes it any clearer and my apologies if it does not.

Thank you

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

Re: non-concurrent collection visibility question

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
By the way, could you please elaborate further and tell how exactly T2 obtains a reference to the object X (unknown from your description) that has this final field L (i.e. final List<Buffer> buffers = new ArrayList<>())?

Regards,
Valentin

On 6 January 2018 at 20:50, Valentin Kovalenko <[hidden email]> wrote:
Thank you for the clarification. In this case, read actions in T2 are not ordered by happens-before order (HB) with the write actions in T1. And all these actions act on the same shared variables (fields of the list L). So by definition, you have a data race. And there is no guarantee that you will correctly read all the buffers that T1 added to the L.

I want to add, that generally there is no guarantee that you will see a non-null when reading L field from T2. However is your case this field is final, and the semantics of a final field guarantees HB* between a write to the field L (T1 writes there a reference to a new ArrayList()) and a read of the reference from L field in T2. Unfortunately, this HB* is not transitive with the normal HB, hence you don't have guarantees you initially asked about.

And one more thing: if you had started T2 from T1 after (in program order (PO)) T1 added all buffers to L, then you would have had HB between all actions in T1 (which are ordered in PO before the start of T2) and all actions in T2. But as far as I understand, your case is different and T2 is started not from T1.

Regards,
Valentin

On 6 January 2018 at 20:07, Andriy Bukatar <[hidden email]> wrote:
Thanks Valentin.
Yes, the devil is in the details.

I could rephrase the question as follows:

There’s a class C containing the non-concurrent list L.

Thread T1 adds a few items to the list L. 

Thread T2 starts (note it did not exist at the time when T1 was updating the list L). Thread T2 gets a reference to C and iterates over its list L.

So “AFTER” in this case is a “wall clock distance” between the time T1 performs the last update to L and the time when T2 starts. 

I know the answer to this question when T2 starts iterating over L before (or at the time when) T1 performs updates to non-concurrent L - no visibility guarantees whatsoever. 

The question I suppose is whether non-existence of T2 at the time of the last update to L has any impact on visibility of the contents of L.

Not sure if this makes it any clearer and my apologies if it does not.

Thank you


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

Re: non-concurrent collection visibility question

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
Thanks very much Valentin. Actually your last statement about Program Order addresses my question in its entirety - T1 is a boot-strap thread that creates all the machinery and starts all the receivers (like T2) after it adds all the buffers to L. 

I believe this is the guarantee I was looking for.

Thank you


On Jan 6, 2018, at 12:50 PM, Valentin Kovalenko <[hidden email]> wrote:

Thank you for the clarification. In this case, read actions in T2 are not ordered by happens-before order (HB) with the write actions in T1. And all these actions act on the same shared variables (fields of the list L). So by definition, you have a data race. And there is no guarantee that you will correctly read all the buffers that T1 added to the L.

I want to add, that generally there is no guarantee that you will see a non-null when reading L field from T2. However is your case this field is final, and the semantics of a final field guarantees HB* between a write to the field L (T1 writes there a reference to a new ArrayList()) and a read of the reference from L field in T2. Unfortunately, this HB* is not transitive with the normal HB, hence you don't have guarantees you initially asked about.

And one more thing: if you had started T2 from T1 after (in program order (PO)) T1 added all buffers to L, then you would have had HB between all actions in T1 (which are ordered in PO before the start of T2) and all actions in T2. But as far as I understand, your case is different and T2 is started not from T1.

Regards,
Valentin

On 6 January 2018 at 20:07, Andriy Bukatar <[hidden email]> wrote:
Thanks Valentin.
Yes, the devil is in the details.

I could rephrase the question as follows:

There’s a class C containing the non-concurrent list L.

Thread T1 adds a few items to the list L. 

Thread T2 starts (note it did not exist at the time when T1 was updating the list L). Thread T2 gets a reference to C and iterates over its list L.

So “AFTER” in this case is a “wall clock distance” between the time T1 performs the last update to L and the time when T2 starts. 

I know the answer to this question when T2 starts iterating over L before (or at the time when) T1 performs updates to non-concurrent L - no visibility guarantees whatsoever. 

The question I suppose is whether non-existence of T2 at the time of the last update to L has any impact on visibility of the contents of L.

Not sure if this makes it any clearer and my apologies if it does not.

Thank you

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

Re: non-concurrent collection visibility question

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
Great, then you are OK.

Regards,
Valentin

On 6 January 2018 at 21:04, Andriy Bukatar <[hidden email]> wrote:
Thanks very much Valentin. Actually your last statement about Program Order addresses my question in its entirety - T1 is a boot-strap thread that creates all the machinery and starts all the receivers (like T2) after it adds all the buffers to L. 

I believe this is the guarantee I was looking for.

Thank you



On Jan 6, 2018, at 12:50 PM, Valentin Kovalenko <[hidden email]> wrote:

Thank you for the clarification. In this case, read actions in T2 are not ordered by happens-before order (HB) with the write actions in T1. And all these actions act on the same shared variables (fields of the list L). So by definition, you have a data race. And there is no guarantee that you will correctly read all the buffers that T1 added to the L.

I want to add, that generally there is no guarantee that you will see a non-null when reading L field from T2. However is your case this field is final, and the semantics of a final field guarantees HB* between a write to the field L (T1 writes there a reference to a new ArrayList()) and a read of the reference from L field in T2. Unfortunately, this HB* is not transitive with the normal HB, hence you don't have guarantees you initially asked about.

And one more thing: if you had started T2 from T1 after (in program order (PO)) T1 added all buffers to L, then you would have had HB between all actions in T1 (which are ordered in PO before the start of T2) and all actions in T2. But as far as I understand, your case is different and T2 is started not from T1.

Regards,
Valentin

On 6 January 2018 at 20:07, Andriy Bukatar <[hidden email]> wrote:
Thanks Valentin.
Yes, the devil is in the details.

I could rephrase the question as follows:

There’s a class C containing the non-concurrent list L.

Thread T1 adds a few items to the list L. 

Thread T2 starts (note it did not exist at the time when T1 was updating the list L). Thread T2 gets a reference to C and iterates over its list L.

So “AFTER” in this case is a “wall clock distance” between the time T1 performs the last update to L and the time when T2 starts. 

I know the answer to this question when T2 starts iterating over L before (or at the time when) T1 performs updates to non-concurrent L - no visibility guarantees whatsoever. 

The question I suppose is whether non-existence of T2 at the time of the last update to L has any impact on visibility of the contents of L.

Not sure if this makes it any clearer and my apologies if it does not.

Thank you


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

Re: non-concurrent collection visibility question

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
The reference to the class C containing list L is passed into the T2’s constructor or to the T2’s (non-synchronized) setter-method which I don’t believe constitutes a safe publication of C’s contents if that’s what you were getting at?

Thank you

On Jan 6, 2018, at 12:55 PM, Valentin Kovalenko <[hidden email]> wrote:

By the way, could you please elaborate further and tell how exactly T2 obtains a reference to the object X (unknown from your description) that has this final field L (i.e. final List<Buffer> buffers = new ArrayList<>())?

Regards,
Valentin

On 6 January 2018 at 20:50, Valentin Kovalenko <[hidden email]> wrote:
Thank you for the clarification. In this case, read actions in T2 are not ordered by happens-before order (HB) with the write actions in T1. And all these actions act on the same shared variables (fields of the list L). So by definition, you have a data race. And there is no guarantee that you will correctly read all the buffers that T1 added to the L.

I want to add, that generally there is no guarantee that you will see a non-null when reading L field from T2. However is your case this field is final, and the semantics of a final field guarantees HB* between a write to the field L (T1 writes there a reference to a new ArrayList()) and a read of the reference from L field in T2. Unfortunately, this HB* is not transitive with the normal HB, hence you don't have guarantees you initially asked about.

And one more thing: if you had started T2 from T1 after (in program order (PO)) T1 added all buffers to L, then you would have had HB between all actions in T1 (which are ordered in PO before the start of T2) and all actions in T2. But as far as I understand, your case is different and T2 is started not from T1.

Regards,
Valentin

On 6 January 2018 at 20:07, Andriy Bukatar <[hidden email]> wrote:
Thanks Valentin.
Yes, the devil is in the details.

I could rephrase the question as follows:

There’s a class C containing the non-concurrent list L.

Thread T1 adds a few items to the list L. 

Thread T2 starts (note it did not exist at the time when T1 was updating the list L). Thread T2 gets a reference to C and iterates over its list L.

So “AFTER” in this case is a “wall clock distance” between the time T1 performs the last update to L and the time when T2 starts. 

I know the answer to this question when T2 starts iterating over L before (or at the time when) T1 performs updates to non-concurrent L - no visibility guarantees whatsoever. 

The question I suppose is whether non-existence of T2 at the time of the last update to L has any impact on visibility of the contents of L.

Not sure if this makes it any clearer and my apologies if it does not.

Thank you


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