XV6 Homework - Lock

发表于 | 分类于 |

当多个处理器上的指令对共享数据进行操作时，可能用到锁。多个处理器运行的可能是同一份代码，也可能是不同的代码。如果共享数据是常量，或者指令都是读数据，没有修改数据，应该不需要用到锁。

还有一种情况是，当中断发生时，中断 handler 也访问了共享数据，这时也需要对共享数据加锁。但是这种情况可能发生死锁，例如：

  • 线程 T 为了访问共享数据，获取锁
  • T 获取锁后，发生某一中断
  • 中断回调函数要访问共享数据，需要获取同一个锁
  • 因为线程 T 还没有释放锁，所以中断 handler 只能等待。
  • T 等待中断处理结束后，才能释放锁，但是中断处理函数又一直等待这个锁。这种情况下，系统就会死锁。

xv6 持有锁时会关闭中断，防止上述情况发生。

锁的实现

一个简单的实现如下

void acquire (struct spinlock *lk) {
  while(lk->locked == 1)
    ;

  lk->locked = 1;
}

这种实现存在的问题是，判断语句和赋值语句是多个指令，不是原子指令。线程 T1 执行到while 循环，发现锁没有被占用，此时发生调度切换（T1 还没来得及设置 lk->locked = 1)线程 T2 也执行到 while 循环，也可以占用锁。此时，就有两个线程获取了同一个锁。

所以操作系统通过硬件提供一些底层原子操作来实现锁，xv6 就是通过 xchg 指令实现的。

xchg(old_mem, new_value) 功能如下，只不过下面这些操作是原子的

old_value = *old_mem;
*old_mem = new_value;
return old_value;

锁 API

xv6 提供两个 API，用来获取和释放锁，分别是 acquire/release，下面看一下具体实现。

pushcli/popcli 函数

根据前面的介绍，在获取和释放锁时，需要关闭和开启中断，这里有两个对应的函数 pushcli/popcli 处理。

这里主要考虑，如果当前CPU需要获取多次锁时，如何管理中断。

pushcli

CPU 在第一次调用 pushcli 时，获取当前的 flag 寄存器的 IF 位，保存在 cpu->intena中。每次调用 pushcli 时，关闭中断，记录关闭中断的次数。

popcli

什么时候才需要恢复中断呢？

  • 如果 CPU 第一次调用 pushcli 时，中断就是关闭的，那么不需要开启中断。通过 pushcli 保存的 cpu->intena 可以知道第一次 pushcli 中断是否是关闭的
  • 如果调用了多次 pushcli， 那么只有最后一次调用 popcli 的时候，才需要开启中断

重复获取锁

占用锁后，CPU 再次运行 acquire 函数，会导致获取锁的指令死循环，当前系统会 hang 住

//重复调用，死循环
while(xchg(&lk->locked, 1) != 0)  
  ;

所以如果出现重复调用，系统应该 panic。

内存乱序

有时候编译器/处理器为了提高性能，可能会把指令顺序打乱。如果现在有个加锁操作，被编译器/处理器打乱了顺序，就会导致锁的功能失效

//正常逻辑               //乱序
acquire()               acquire()
i++                     release()
release()               i++

所以需要 __sync_synchronize()，禁止编译器/处理器乱序内存操作。

具体怎么个乱序法，还要再研究一下。

保存调用栈信息

acquire还会保存调用栈信息，用来做调试。 getcallerpcs() 通过参数地址，获取 ebp 地址，然后根据 ebp 信息，就可以找出整个函数的调用栈，这里只保存了最近10个函数的调用信息。

Homework

acquire两次

这个前面已经分析过了，内核会 panic

Interrupts in ide.c

这个作业是获取 ide 锁后，打开中断，运行后可能出现如下结果

cpu0: starting
sb: size 1000 nblocks 941 ninodes 200 nlog 30 logstart 2 inodestart 32 bmap start 58
init: starting sh
cpu with apicid 1: panic: acquire
 80105061 80102824 80106b9d 80106835 80102986 801001e7 80101ef3 80108492 80100cd0 8010648a

80105061: acquire() -> panic()  //spinlock.c
80102824: ideintr() -> acquire() //ide.c
80106b9d: trap() -> ideintr() // trap.c
80106835: trap()  //vectors.S
80102986: iderw() -> idestart() // ide.c
801001e7: bread -> iderw() // bio.c
80101ef3: readi -> bread() // fs.c
80108492: loaduvm -> readi() // vm.c
80100cd0: exec -> loaduvm() // exec.c
8010648a: sys_exec -> exec() //sysfile.c

通过调用栈可以发现，fork一个进程并调用 exec syscall 后，需要读磁盘，在 idestart 后发生中断（IDE中断？），进入 IDE 中断处理函数，而 ideintr() 也需要获取 ide 锁，于是导致重复获取锁，kernel panic。

Interrupts in file.c

为什么获取 file_table_lock 锁后，打开中断，kernel 没有 panic 呢？

原因就是发生中断后，所有中断处理函数，都不需要再次获取 file_table_lock。意思是中断处理函数不会访问 file_table_lock 锁保护的共享数据，所以这种情况，不需要处理中断。

xv6 lock implementation

如果释放锁后，再去清理 lk->pcs[0], lk->cpu，可能出现

  • 锁释放，但是还未清理 lk->pcs[0], lk->cpu
  • 另一个 CPU 尝试获取锁并成功，设置 lk->pcs[0], lk->cpu
  • 当前 CPU 继续执行，清理了 lk->pcs[0], lk->cpu

这就会导致锁相关的信息不正确，影响锁的功能，比如判断当前 CPU 是否占用该锁，需要用到 lk->cpu。