On Wed, Apr 26, 2017 at 11:49:33AM +0800, Yubin Ruan wrote: > On 2017年04月25日 23:19, Akira Yokosawa wrote: > >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 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. > >> 2. sequential consistency All CPUs agree on the order of all memory operations. > >> 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. > >>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. 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. ;-) > 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! > 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! > 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 > Thanks, > Yubin > > >> > >>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
