cs4231-cheatsheet.pdf

01. 互斥 (Mutual Exclusion)

• 互斥算法属性
  • 互斥性 (Mutual Exclusion)
  • 进展性 (Progress)
  • 无饥饿性 (No Starvation)
• Peterson算法
  • 证明方法：矛盾法
    • 互斥性：turn变量的作用
    • 进展性：至少一个进程能进入临界区
    • 无饥饿性：等待进程最终能进入
• Lamport面包店算法
  • 基于“取号-服务”机制
  • 共享变量：choosing[]（取号中标记）、number[]（队列号）
• 硬件解决方案
  • 中断禁用
  • 原子指令（如TestAndSet）

02. 同步原语 (Synchronisation Primitives)

• 信号量 (Semaphores)
  • P()（等待）与V()（信号）的原子操作
  • 应用场景：互斥锁、生产者-消费者问题
• 哲学家就餐问题
  • 死锁条件：循环等待
  • 解决方案：资源有序分配
• 管程 (Monitors)
  • Hoare风格：notify()立即切换线程
  • Java风格：notify()后当前线程继续执行
  • 嵌套管程问题：wait()仅释放直接关联的锁
• 经典问题
  • 生产者-消费者（环形缓冲区）
  • 读者-写者（读写锁设计）

03. 一致性条件 (Consistency Conditions)

• 历史 (History)
  • 顺序历史 (Sequential) vs. 并发历史 (Concurrent)
  • 合法历史 (Legal History)：符合顺序语义
• 顺序一致性 (Sequential Consistency)
  • 存在合法顺序历史，保留进程顺序
• 线性化 (Linearizability)
  • 强于顺序一致性，保留外部事件顺序
  • 局部性：系统线性化当且仅当每个对象线性化
• 寄存器一致性模型
  • 原子性 (Atomic) > 正则性 (Regular) > 安全性 (Safe)