L9：锁

lab通关记录

MIT-6.828实验通关记录

为什么要谈论锁？

流水线指令的并行以加速
所以内核必须处理并行系统调用
从而并行访问内核数据（缓冲区缓存、进程等）
锁有助于协调共享数据

思考锁的问题

锁抽象：

锁

acquire(lock)
    x = x + 1 -- “临界区”，即共享区的修改，需要用锁变为为原子操作
release(lock)

锁本身就是一个对象
如果多个线程调用acquire(l)
只有一个会执行临界区
其他人将等待 release() – “block”
一个程序通常有很多数据，很多锁
如果不同的线程使用不同的数据，
那么他们可能持有不同的锁，
所以他们可以并行执行——完成更多的工作。
请注意，锁 lock 没有专门绑定到数据 x
程序员有一个线程/进程通信计划：每当需要数据x修改时候，查看锁

决定何时需要锁的保守规则：
任何时候两个线程使用一个内存位置，并且至少一个是写
除非您持有正确的锁，否则不要接触共享数据！
（太严格：程序逻辑有时可能会排除共享；无锁）
（太松散：printf()；并不总是简单的锁/数据对应）

可以自动锁定吗？
也许该语言可以将锁与每个数据对象相关联
编译器在每次使用时添加获取/释放
这样的想法很省事！
这个想法往往过于僵化：

1.确定何时需要锁：

就是确定何时需要操作数据的原子性

​ rename（“d1/x”，“d2/y”）：

lock d1，erase x，unlock d1
lock d2，add y，unlock d2

​ 问题：该文件暂时不存在！
​ rename() 应该是原子的
​ 其他系统调用应该在之前或之后看到，而不是在两者之间
​ 否则写程序太难了
​ 我们需要：

lock d1 ; lock d2
      erase x，add y
unlock d2；unlcok d1

也就是说，程序员经常需要显式控制
持有锁的代码区域
为了隐藏尴尬的中间状态：保证原子性

锁有助于避免丢失更新
锁帮助你创建原子多步操作——隐藏中间状态
锁帮助操作维护数据结构的不变量
假设不变量在操作开始时为真
操作使用锁来隐藏对不变量的临时违反
操作在释放锁之前恢复不变量

2.确定保证没有死锁：

所谓死锁就是多（次）锁循环等待

问题：死锁
通知 rename() 持有两个锁
如果：

core A                 core B
renmae(d1/x, d2/y)     rename(d2/a, d1/b)
lock d1                lock d2
lock d2 ...            lock d1 ...

我们可以看到，并行的操作前提下，锁只能保证操作原子性（或者说临界区的互斥），但是这里的core A和core B互相等待，不仅如此，如果在临界区，也可以出现自己获取自己拥有的锁，那么同样也会导致循环等待。

解决方案：
程序员计算出所有锁的顺序：比如使用优先队列
所有代码都必须按该顺序获取锁
即预测锁、排序、获取——复杂！

锁与模块化

锁使得难以隐藏模块内的细节
为了避免死锁，我需要知道我调用的函数获取的锁
我可能需要在调用之前获取它们，即使我不使用它们
即锁通常不是单个模块的私有业务

如何考虑将锁放在哪里？
这是新代码的简单计划

1. 串口执行下写模块正确
   即假设单 CPU，单线程

   void insert（）{
   	e->next = l; 
   	l = e; 
   }

   但如果并行执行则不正确

2.为保证串行执行添加锁
由于获取/释放允许一次仅由一个 CPU 执行
要点：

程序员更容易推理串行代码
尽管具有并行性，锁仍可能导致您的串行代码正确

性能呢？
毕竟，我们可能将锁作为获得并行加速的计划的一部分，所以是并行不悖

锁和并行

锁防止并行执行
为了获得并行性，你经常需要拆分数据和锁
以某种方式让每个核心使用不同的数据和不同的锁
“细粒度锁”
选择数据/锁的最佳分割是一个设计挑战
整个ph.c表；每个表[]行；每个条目
整个FS；目录/文件；磁盘块
整个内核；每个子系统；每个对象
您可能需要重新设计代码以使其并行运行
示例：将单个空闲内存列表分解为每核空闲列表
如果线程在锁定单个空闲列表上等待很多，则有帮助
这种重写可能需要大量的工作！

锁粒度建议
从大锁开始，例如保护整个模块的一把锁
更少的死锁，因为更少的机会持有两个锁
不需要对不变量/原子性进行推理
衡量是否有问题
大锁通常就足够了——也许花在那个模块上的时间很少
仅在必须时才重新设计细粒度锁定

让我们看看 xv6 中的锁定。

锁的典型用途：ide.c

许多 O/S 的设备驱动程序安排的典型
图表：
用户进程、内核、FS、iderw、追加到磁盘队列
IDE磁盘硬件
标识符
并发源：进程、中断

ide.c 中只有一个锁：idelock——相当粗粒度

iderw() – idelock 保护什么？
1. 出队操作无竞争
2. 如果队列不为空，IDE h/w 正在执行队列头
3.没有对IDE寄存器的并发访问
ideintr() – 中断处理程序
获取锁——可能必须在中断级别等待！
使用 idequeue (1)
将下一个排队的请求交给 IDE h/w (2)
接触 IDE 硬件寄存器 (3)

如何实现锁？

为什么不：

struct { int locked; }
    acquire（l）{
      while（1）{
        if(l->locked == 0){ // A
          l->clocked= 1; // B
          return;
        }
      }
    }

oops：A 线和 B 之间的原子性问题，如果他们不原子，那么我们从指令角度假设以下情况：CPU得到了lock的0，但是还未修改为1，这将导致同时另一个线程得到了0，那么他们各自将会将locked置为1，因此临界区将会允许两个线程进入，从而破坏临界区的互斥原则。

那么，我们如何原子地做 A 和 B？

硬件提供了原子交换指令：

mov $1, %eax
xchg %eax, addr
或者
xchg $1, addr

1.这样有什么用呢？关键在于这个交换指令，我们先想想需要原子的是哪些操作？
	获得锁，根据情况等待或者锁定
对于等待而言，和获得锁一起进行原子并没有必要，是可以并行不悖，问题出在锁定上：假如我们使用xchg，那么1的交换就会导致
	交换1和1:等待，很好
	交换0和1:原子修改了locked为1，非常不错
2.等待的判断需要原子吗？不需要，因为锁的获取和修改我们发现：也是临界区，等待并不修改临界区
3.给出的汇编指令为什么可以有两种？因为mov $1这样的操作并不会出问题
总之，想想有没可能出问题，再决定锁的需要和实现，这很重要

在硬件中执行此操作：

globle lock addr（其他内核无法使用）
    temp= *addr
    *addr = %eax
    %eax = temp
unlock addr

x86 h/w 提供了锁定内存位置的概念
不同的 CPU 有不同的实现
图：内核、总线、RAM、锁
所以我们把问题推到了硬件上
h/w 在缓存行或整个总线的粒度上实现
内存锁强制并发 xchg 一次运行一个，而不是交错

现在：

acquire（l）{
    while（xchg(&l->locked, 1) == 0）{}//wait or not
  }

如果 l->locked 已经是 1，则 xchg 设置为 1（再次），返回 1，
并且循环继续旋转
如果 l->locked 为 0，则最多有一个 xchg 会看到 0；它会设置
它为 1 并返回 0；其他 xchgs 将返回 1
这是一个“自旋锁”，因为在获取循环中等待内核“自旋”

看 xv6 自旋锁实现

spinlock.h——你可以看到结构锁的“锁定”成员
spinlock.c/acquire():
参见 while-loop 和 xchg() 调用
pushcli() 是关于什么的？
为什么要禁用中断？
release（）：
设置 lk->locked = 0
并重新启用中断

详细信息：内存读/写排序
假设两个内核使用一个锁来保护一个计数器，x
我们有一个简单的锁实现

核心 A：	  				核心 B：
locked = 1
x = x + 1   			while（locked == 1）
locked = 0 ...end
                  locked= 1
                  x = x + 1
                  locked = 0

然而我们的编译器和 CPU 重新排序内存访问
即它们不遵守源程序的内存引用顺序
例如，编译器可能会为核心 A 生成此代码：

locked = 1
locked = 0
x = x + 1

将增量移动到临界区外！！！
1.为什么这么干，在其他方面会有好处吗？有，假如你很快就要再次修改这个地址（事实上确实这样），那么我们可以优化为修改后不放入内存，等待下次访问，加速访问（就像某种缓存和回写）。
2.那么有什么办法禁止呢？c代码使用同步函数：sync_synchronize()，汇编代码使用asm关键字来防止这种优化

release() 对 sync_synchronize() 的调用防止重新排序
编译器不会将内存引用移过 sync_synchronize()
并且（可能）发出“内存屏障”指令来告诉 CPU
Acquire() 对 xchg() 的调用具有类似的效果：
英特尔承诺不会重新订购过去的 xchg 指令
x86.h 中的一些垃圾 xchg() 告诉 C 编译器不要删除或重新排序
（volatile asm 表示不要删除，“m”表示不重新排序）
如果使用锁，则无需了解内存排序规则
如果您想编写异国情调的“无锁”代码，则需要它们

为什么使用自旋锁？

他们在等待时不会浪费CPU吗？
为什么不放弃CPU并切换到另一个进程，让它运行？
如果持有线程需要运行怎么办；不应该等待线程让出 CPU 吗？
自旋锁指南：
保持自旋锁很短的时间
持有自旋锁时不要让出 CPU
系统通常为较长的关键部分提供“阻塞”锁：这将会是后面介绍的协调（coordination），通过sleep和wakeup来完成
等待线程产生 CPU
但管理费用通常更高
稍后你会看到一些 xv6 阻塞方案

建议：

如果没有必要，请不要随意指定共享区：因为会在并行模式下导致问题
从几个粗粒度的锁开始
检测你的代码——哪些锁阻止了并行性？
仅在并行性能需要时才使用细粒度锁
使用检测器来检测效果

Donate