Skip to contentSkip to conversation

Some question about memory model(consistency)

DISCUSSION Yubin Ruan 3 participants 4 messages Apr 25, 2017 – May 1, 2017

lore
Share & tools
lore

Yubin Ruan

author
#0 lore raw

Hi,
long time no see :)

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?

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

#1 lore raw
Quoted 2 lines · Yubin Ruan

Hi,
long time no see :)

Hi Yubin,

I'm afraid this is not a direct answer to your question. But I'll try.

Quoted 62 lines

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)

Quoted 1 line

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

Quoted 15 lines

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

author
#2 lore raw
Quoted 79 lines · Akira Yokosawa
Quoted 2 lines · Yubin Ruan

Hi,
long time no see :)

Hi Yubin,

I'm afraid this is not a direct answer to your question. But I'll try.

Quoted 62 lines

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)

Quoted 1 line

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)".

Quoted 8 lines

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.

Thanks for replying.

I think I mix these concepts with real world implementation. From what I have read so far, these properties are only constraints that may or may *not* be respected by CPUs and compilers. CPUs/compilers are free to reorder instructions for optimization reasons, thus violating those consistency constraints. But in real world implementation, we have special techniques that we can use to "implement" those consistency constraints(e.g memory barriers, locks, etc).

Back to the question above, those quiescent point/period can be defined by ourselves, as long as we can carry out some implementations that respect the consistency constraints we want.

Hmm...maybe that is the so-called "consequence of knowing too much"... And I'd better go read more :)

Thanks,
Yubin

Quoted 16 lines
Quoted 15 lines

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#3 lore raw
Quoted 11 lines · Yubin Ruan
Quoted 10 lines · Akira Yokosawa
Quoted 2 lines · Yubin Ruan

Hi,
long time no see :)

Hi Yubin,

I'm afraid this is not a direct answer to your question. But I'll try.

Quoted 1 line
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines

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

This can be thought of a a weaker form of eventual consistency, which is described here: http://queue.acm.org/detail.cfm?id=1466448

A rough description is that if everything goes quiet for some time, everyone has a consistent view of the data.

Quoted 1 line
Quoted 1 line
Quoted 1 line

2. sequential consistency

All CPUs agree on the order of all memory operations.

Quoted 1 line
Quoted 1 line
Quoted 1 line

3. linearizability

Roughly similar to sequential consistency, but at a higher level. Sequential consistency applies to memory accesses, but linearizability applies to API calls for a given data structure.

However, there is -no- guarantee that data structure accessed on a sequentially consistent system will be linearizable.

Quoted 61 lines
Quoted 61 lines
Quoted 53 lines

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)

Quoted 1 line

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)".

Quoted 8 lines
Quoted 8 lines

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.

Akira has it right. And the definition of quiescence gets much more tricky when you have multiple threads all accessing the same data structure. When only a single thread is accessing a given data structure, it is almost always the case that the time periods between consecutive pairs of API calls will all be quiscent states.

With multiple threads, things get much fuzzier because of the time required for state changes to propagate through the system. Yes, today's computers are small and fast, but their size is not zero and the speed of light is still finite. ;-)

Quoted 9 lines

Thanks for replying.

I think I mix these concepts with real world implementation. From what I have read so far, these properties are only constraints that may or may *not* be respected by CPUs and compilers. CPUs/compilers are free to reorder instructions for optimization reasons, thus violating those consistency constraints. But in real world implementation, we have special techniques that we can use to "implement" those consistency constraints(e.g memory barriers, locks, etc).

That we do!

Quoted 3 lines

Back to the question above, those quiescent point/period can be defined by ourselves, as long as we can carry out some implementations that respect the consistency constraints we want.

We can define them pretty much however we want. But getting a -useful- definition, now that is the trick!

Quoted 2 lines

Hmm...maybe that is the so-called "consequence of knowing too much"... And I'd better go read more :)

If a little knowledge is a very dangerous thing, just imagine what you could do with a lot of knowledge! ;-)

Thanx, Paul

Quoted 20 lines

Thanks,
Yubin

Quoted 16 lines
Quoted 15 lines

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html