Concurrency - Concurrent Objects

Concurrent Objects

有锁数据结构真好写

Sequence Consistency

p 和 q 都是顺序一致的。（可以平移）

但是这个执行过程并不是顺序一致的（有环）

Linearizability

顺序一致性不可合成。

Principle: Each method call should appear to take effect instantaneously at some moment between its invocation and response.

Every linearizable execution is sequentially consistent, but not vice versa.

The usual way to show that a concurrent object implementation is linearizable is to identify for each method a linearization point where the method takes effect.

For lock-based implementations, each method’s critical section can serve as its linearization point. For implementations that do not use locking, the linearization point is typically a single step where the effects of the method call become visible to other method calls.

看懂了没？