【并发3】并发控制(1)：互斥

【并发3】并发控制(1)：互斥

这是 2020 南京大学 “操作系统：设计与实现” (蒋炎岩) 的课程笔记

本节要点：
- 互斥问题
- 共享内存上的互斥
- 原子指令的互斥
- 数据竞争

目录

• • • 互斥问题
    • • 互斥：直观理解
      • 共享内存上的互斥
    • 共享内存上的互斥
    • • Peterson 算法真正的问题
      • 共享内存带来的更多问题
    • 实现互斥：软件不够，硬件来凑
    • • 原子操作 - lock指令前缀
      • 实现互斥：自旋锁
      • 数据竞争

互斥问题

互斥：直观理解

理解并发的另一个工具：把线程想象成人、把共享内存想象成物理世界

• 物理世界是天生并发的，在小范围宏观意义上，所有部分的空间“同时”沿着时间方向前进
  • 物理世界 = 共享内存
  • 我们（根据想法执行物理世界动作）=线程（根据程序局部状态访问共享状态）

线程不想被别人打断地做一件事

• 一旦某个人已经开始，其他人就必须等待

共享内存上的互斥

互斥（mutual exclusion） “互相排斥”

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

typedef struct{...
} lock_t;// 试图获得锁的独占访问，成功获得后返回
void lock(lock_t = lk);
// 释放锁的独占访问
void unlock(lockk_t = lk);

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

• 在任何线程调度（线程执行的顺序）下
  • 若某个线程持有锁（这个线程调用了lock(lk)返回且未释放）
  • 则任何其他线程的 lock(lk) 函数都不能返回

状态机的视角

• lock返回会进入 “locked”状态；unlock会清除该状态
• 初始状态 s_0 不能有 两个线程都进入locked状态

上了锁的代码完全不能并发执行

先执行的代码，它对共享内存的写，对之后执行的代码是可见的。

在共享内存上，贡献资源的访问太危险（原子性、顺序性、可见性丧失），互斥用来阻止代码块之间的并发，实现“串行化”

• lock/unlock 保护的区域成为一个原子的黑盒子
• 黑盒子的代码不能随意并发，顺序满足要么 T1 - T2, 要么 T2 - T1
• 先完成的黑盒子的内存访问在之后的黑盒子中可见

锁帮我们拯救了原子性、顺序性、可见性。

共享内存上的互斥

共享内存多线程：独立的寄存器/堆栈：共享内存

支持的基本操作

• 线程本地(thread-local) 计算（寄存器/堆栈上的数值的读写/修改）
• load，读共享内存
• store，写共享内存
• 假设 load/store 是原子的，状态机每执行一条 load/store

困难之处在于：不能同时读/写共享内存

• load（环顾四周）的时候不能写，只能“干看”
• store （改变物理世界的状态）的时候不能读，只能“闭着眼动手”

Peterson 算法真正的问题

int x = 0, y = 0;void thread_1{[1]store(x, 1); [2]t = load(y); // 处理器允许 1-2 交换printf("y = %dn", t); 
}void thread_2{[1]store(y, 1); [2]t = load(x); // 处理器允许 1-2 交换printf