Some question about memory model(consistency)

[Yubin Ruan <ablacktshirt@gmail.com>]

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