On 2017/04/25 21:02:22 +0800, Yubin Ruan wrote:
> Hi,
> long time no see :)
Hi Yubin,
I'm afraid this is not a direct answer to your question.
But I'll try.
>
> This email relates to some confusion about computer system memory model.
> Recently I spent sometime reading stuff about momery model and finally I get
> to the subject of safety properties of concurrent data structure. When
> discussing concurrent data structures, three important properties are proposed:
> 1. quiescent consistency
> 2. sequential consistency
> 3. linearizability
>
> But...hmm...I don't fully understand them. sad :(
> I know there might be someone in this lists to discuss these questions with, so
> I try to post them here. Any feedback is welcome.
>
> Let's start with some simple concepts to make this communication valid.
>
> 1. what exactly counts as a "Quiescence"?
> -------
> I understand the concept of quiescent consistency: An execution of a
> concurrent program is quiescently consistent if the method calls can be
> correctly arranged while still retaining the mutual order of calls
> separated by quiescence, a period of time where no method is being
> called in any thread
>
> Basically it can be illustrated very vividedly by the following figures:
>
> Program order specified:
> <--A--> <--B--> <--C--> <--D--> <--E--> <--F-->
> ~~~~~~~
> (quiescence point)
>
> Real execution order:
> <--A--> <--C--> <--B--> <--E--> <--D--> <--F-->
> ~~~~~~~
> (quiescence point)
>
> The above model is quiescent consistent because there is no execution
> reordering across the quiescence point. But this one is not:
>
> Program order specified:
> <--A--> <--B--> <--C--> <--D--> <--E--> <--F-->
> ~~~~~~~
> (quiescence point)
>
> Real execution order:
> <--A--> <--B--> <--D--> <--C--> <--E--> <--F-->
> ~~~~~~~
> (quiescence point)
>
> This one is NOT quiescent consistent because the reordering of D and E
> across the quiescent point.
>
> But, in real world program, how can we identify those quiescent points?
> I mean, in a program like this:
>
> 1: q.enqueue(something)
> 2:
> 3: q.enqueue(something)
> 4:
> 5: k.enqueue(something)
> 6:
> 7: k.dequeue(something)
>
> which is a quiescent point/period? Is it 2 or 4 or 6?
It depends on which set of API you use to enqueue and dequeue.
Have you read through Section 9.5 "Read-Copy Update" in perfbook?
Especially, Figure 9.19 "RCU QSBR: Waiting for Pre-Existing Readers"
depicts "quiescent state based reclamation (QSBR)".
Also, Section 9.5.5.9 "RCU Based on Quiescent States" explains its toy
implementation.
On thing you might be missing here is that a quiescent state is *not*
necessarily a global state but can be a state local to an object to
be updated.
Hope this could be a starting point for you.
Regards, Akira
>
> I am not so a hardware guy and I don't have so much experience with memory
> model. But I am really interested in these models because I think it
> provides foundation for concurrent programming and distributed system
> building, which is what I interested in.
>
> Any feedback is welcome :)
>
> Thanks
> Yubin
> --
> To unsubscribe from this list: send the line "unsubscribe perfbook" in
> the body of a message to majordomo@xxxxxxxxxxxxxxx
> More majordomo info at http://vger.kernel.org/majordomo-info.html
>
--
To unsubscribe from this list: send the line "unsubscribe perfbook" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
