Lecture 10

有一段时间没看了忘了好多

锁

why need it

多个CPU核的并行计算可以带来倍数级的提升但是假如一个程序运行在多个核上会同时带来一些竞态的问题并且需要内核能够正确的处理它们

有很多老生常谈的环境例如说什么生产者消费者模式共享内存的情景下我们都需要使用锁来保证多个核之间数据的一致性

简而言之多核并行计算带来了效率提升也带来了多核时的并发控制成本和编码难度

实际的情况有些令人失望，因为我们想要通过并行来获得高性能，我们想要并行的在不同的CPU核上执行系统调用，但是如果这些系统调用使用了共享的数据，我们又需要使用锁，而锁又会使得这些系统调用串行执行，所以最后锁反过来又限制了性能。

那么除了使用锁还有其他的方法可以提高性能吗肯定是有的但是之前的技术发展路线已经解释了为什么锁的使用频率会越来越高

text

从这图可以看到从2000年开始：

CPU时钟频率就没有再增加过了（绿）
意味着 CPU单线程下的性能达到了一个极限（蓝）

于是就往增加并行计算能力这个方向思考了

CPU的晶体管数量增加（深红）
CPU数量增加（黑）

粗略的理解就是同一份工作单个人的工作效率已经到瓶颈了无法再提升了所以此时唯一提高效率的方法就是找多一个人一起工作（并行）

同理，某个应用程序如果想要提升性能必须要依赖于多核即其所依赖的操作系统也需要高效的在多个CPU核上运行

而锁就是保证在这多个CPU核上运行时的正确性

如果在kfree()的时候取消掉上锁下锁的语句此时会发生什么？

void kfree(void *pa){
    struct run *r;
    ...
    acquire(&kmem.lock);
    r->next = kmem.freelist;
    kmem.freelist = r;
    release(&kmem.lock);
}

当并发发生的时候多个程序同时执行可能会导致他们的freelist都仅加上了自己的空余空间即race condition 竞态问题

而通过锁就可以保证该中间语句执行的原子性他们要么就一起执行要么就一条都不会执行被称为 critical section

他所起到的作用就是序列化代码的执行让本该并行执行的代码串行

当多个CPU都遇到锁的时候此时的的并行度不再取决于CPU核的数量而是取决于此时锁的数量

这个问题其实很简单如何理解？假如内核中只有一把big kernel lock。某个地方取了锁此时其他的地方无论执行到什么地步无论是否会导致竞态问题的产生都只会阻塞在这

换句话来说也就是通过多把锁可以换取一定程度上的并行度但其本身就需要耗费一定的资源罢了

经典两害取其轻～

when use it

标准回答：当涉及到临界资源的时候要加锁

但是有些情况下有可能即使多个进程同时操作同一个数据结构在某些场合不加锁也可以正常工作称为lock-free program

特性

作用：

避免丢失更新（race condition导致的丢失更新）
打包多个操作使其具有原子性
维护共享数据结构的不变性（在修改操作进行的时候不变性暂时被破坏修改前和修改后都存有）

死锁

也是老生常谈的一个问题资源争用的时候如果锁住的对方所需要的临界资源此时都需要阻塞直至对方放弃此时产生死锁

也有一个最简单的触发例子一个地方acquire()一把锁之后再次acquire()同一把锁就会导致死锁（被自己死锁了）

如何解决死锁？

这里没有什么方法论只是从设计思路上给了一些建议

确定锁对象的顺序

在获取锁的时候我门根据这个顺序总是先获取考前的目录的锁本质意思就是将程序中所有涉及到并行计算的地方（所有用得到锁的地方）都拓扑出来根据这个拓扑的关系图对锁的使用顺序进行排序

但是这个就违背了代码抽象的原则因为正常的要求下代码抽象是要求A模块完全不知道相邻模块 B模块的实现

但是此处为了实现锁排序就需要暴露这些信息

同时这里所指的排序指的是有几率会产生死锁为单位的锁集合并不是指所有锁

一辈子的不会干扰到的锁们无需排序可正常的并行运行

自旋锁内部实现

// 获取当前锁
// Acquire the lock.
// Loops (spins) until the lock is acquired.
void acquire(struct spinlock* lk) {
    // 获取锁的时候 关闭中断
    push_off();  // disable interrupts to avoid deadlock.
    if (holding(lk))
        panic("acquire");

    // 开始自旋 类似atom swap 直至成功获取到锁
    while (__sync_lock_test_and_set(&lk->locked, 1) != 0)
        ;

    // 给cpu发送指令 禁止此时发生的store等指令
    __sync_synchronize();

    // Record info about lock acquisition for holding() and debugging.
    // 记录当前获得锁的是哪个核
    lk->cpu = mycpu();
}

// Release the lock.
void release(struct spinlock* lk) {
    if (!holding(lk))
        panic("release");

    lk->cpu = 0;
    // 给cpu发送指令 禁止此时发生的store等指令
    __sync_synchronize();
    // 再次进行一个atom release本质上也是atom swap
    __sync_lock_release(&lk->locked);

    pop_off();
}