Locks

我们为什么需要锁？

如果一个应用程序运行在多个 CPU 核上，并且执行了系统调用，那么内核需要能够处理这些并行的系统调用。

如果多个内核都在运行系统调用，那么它们可能访问内核中共享的数据结构。

当有对这些数据结构的并行访问时，我们需要锁来协调对共享数据的更新。更进一步的，我们需要锁来保证共享的数据是正确的。

从 kfree 考虑，我们假设有2个CPU在处理这个函数，这时候一个CPU执行 r->next = kmem.freelist; 另一个函CPU时也执行 r->next = kmem.freelist; 这样 r1 r2 都指向 freelist 然后到了下一句 kmem.freelist = r; 两个CPU执行完之后，我们会丢失先执行的那个CPU所指向的页表。

锁的抽象

1
2
3

struct lock{

}

锁有两个关键的方法，分别是 acquire() 和 release() ，它们都接受一个指向锁的指针作为参数， acquire() 确保了只能有一个进程能够成功的获取锁，任何在同一时间获取锁的进程必须等到第一个进程调用 release 。

锁的获取和释放的代码通常被称为 critical section （临界区）

如果我们的内核只有一个锁

如果我们有一个程序并行调用多个系统调用，这些系统调用会串行执行，因为我们的内核只有一把锁。

所以一般的操作系统中，都会有多个锁，这样才能实现某种程度上的并发执行。

如果程序需要一段代码具有原子性，这是由程序员决定锁的 acquire 和 release 的。

代码不会自动加锁，程序员需要自行决定是否将锁与数据结构关联。

什么时候才需要加锁呢

如果两个进程访问了一个共享的数据结构，其中一个进程会更新数据结构，那么就需要对这个数据结构加锁。

但是加锁会导致性能的损失，上面的情景下不加锁也可能正常工作，不加锁的程序通常称之为 lock-free program ，不加锁可以获得更好的性能和并发度，

认识锁的视角

锁可以帮助避免数据更新的丢失
锁可以打包多个操作，使其具有原子性
锁可以维护共享数据结构的不变形

不恰当地使用锁可能带来一些锁特有的缺点

首先就是死锁（DeadLock）
如果我们先 acquire 一个锁，然后进入 critical section ，这时候我们再尝试 acquire 同一个锁，我们知道这是不被允许的，第二次 acquire 不会成功，会等待第一个 acquire 的 release ，但是这个时候这个程序不会继续往下推进，也就不会 release ，这样就导致了死锁。

另一种情景是：
假设我们有2个CPU，其中一个在执行 rename("d1/x","d2/y") 另一个在执行 rename("d2/a","d1/b") ，开始执行的时候，CPU1获得 d1 的锁，CPU2获得 d2 的锁，下一步CPU1需要获取 d2 的锁，CPU2需要获取 d1 的锁，就会导致死锁，因为互相都获取不到。
上面的场景有时候被称为 Deadly embrace

解决上面 Deadly embrace 的方法很简单，只需要对锁进行排序，保证所有操作必须以相同的顺序获取锁即可。在定义锁的排序时，必须是全局的

另外，锁的操作有时候还会违反代码的抽象要求，例如一个函数中涉及到另一个函数的调用，那么必须知道这个函数涉及了哪些锁。也就是说锁让代码的模块化更困难了。

最后，为了实现性能的优化，需要把锁和数据结构进行拆分，但这又会引入更多的操作。通常的开发流程是：先从大锁开始，对程序进行测试，看看程序是否能使用多核，是否得到了加速，如果得到加速说明锁已经实现的很好了，否则说明锁存在竞争，之后我们需要重构程序。

如何实现锁

while(1)
{
	if(l->lock==0)
	{
		l->lock = 1;
		return;
	}
}

上面是一个自旋锁的实现，但是存在 race condition，如果CPU1和CPU2同时看到 l->lock == 0 那么两个CPU会同时获得锁，变成死锁。

我们必须要用硬件锁才能实现软件锁。

回顾xv6的自旋锁实现，我们可以看到使用了 test_and_set

void
acquire(struct spinlock *lk)
{
push_off(); // disable interrupts to avoid deadlock.
if(holding(lk))
panic("acquire");

// On RISC-V, sync_lock_test_and_set turns into an atomic swap:
// a5 = 1
// s1 = &lk->locked
// amoswap.w.aq a5, a5, (s1)
while(__sync_lock_test_and_set(&lk->locked, 1) != 0)
;

// Tell the C compiler and the processor to not move loads or stores
// past this point, to ensure that the critical section's memory
// references happen strictly after the lock is acquired.
// On RISC-V, this emits a fence instruction.
__sync_synchronize();

// Record info about lock acquisition for holding() and debugging.
lk->cpu = mycpu();
}