并发性和正确性
并发对象的正确性往往不容易描述。
如果能将并发执行转化为顺序执行，则只需对该顺序执行进行分析，从而简化了并发对象的分析。
顺序对象
每个对象都有一个状态，通常由一组字段（field）给出。队列示例：项目序列。
每个对象都有一组方法，这是操纵状态的唯一方法。队列示例：enq() 和 deq() 方法。
Sequential vs Concurrent
- Sequential:
- Object needs meaningful state only between method calls
- Each method described in isolation
- Can add new methods without affecting older methods
- Concurrent:
- Because method calls overlap, object might never be between method calls
- Must characterize all possible interactions with concurrent calls
- What if two
enq()s overlap? - Two
deq()s?enq()anddeq()?
- What if two
- Everything can potentially interact with everything else
Big Question
What does it mean for a concurrent object to be correct?
- What is a concurrent FIFO queue?
- FIFO means strict temporal order
- Concurrent means ambiguous temporal order
静态一致性
顺序一致性
可线性化性 Linearizability
Each method should
- “take effect”
- Instantaneously
- Between invocation and response events
Object is correct if this “sequential” behavior is correct
Any such concurrent object is Linearizable™
