https://jyywiki.cn/OS/2023/build/lect7.ipynb

互斥问题：定义与假设

互斥问题：定义

互斥 (mutual exclusion)，“互相排斥”

• 实现 lock_t 数据结构和 lock/unlock API:

typedef struct {
  ...
} lock_t;
void lock(lock_t *lk);
void unlock(lock_t *lk);

一把 “排他性” 的锁——对于锁对象 lk

• 如果某个线程持有锁，则其他线程的 lock 不能返回 (Safety)
• 在多个线程执行 lock 时，至少有一个可以返回 (Liveness)
• 能正确处理处理器乱序、宽松内存模型和编译优化

互斥问题的经典算法

Peterson 算法

• 包间、旗子和门上的字条
• 假设 atomic load/store
  • 实现这个假设也不是非常容易的 (peterson.c)

因此，假设很重要

• 不能同时读/写共享内存 (1960s) 不是一个好的假设
  • Load (环顾四周) 的时候不能写，“看一眼就把眼睛闭上”
  • Store (改变物理世界状态) 的时候不能读，“闭着眼睛动手”
  • 这是《操作系统>课
    • 更喜欢直观、简单、粗暴 (稳定)、有效的解决方法

实现互斥的基本假设

允许使用使我们可以不管一切麻烦事的原子指令

void atomic_inc(long *ptr);
int atomic_xchg(int val, int *ptr);