作业九
阅读参考书目Operating Systems: Three Easy Pieces的28节，并进行总结。 （不少于1500字）
1 背景
在并行环境下编程时，很多情况下程序运行的结果并不如我们所期望，因为很多程序对共享变量的使用存在风险——不能保证原子性。所以，我们需要对共享变量加锁来保证指令的原子性执行，牺牲一定执行效率来保证执行的正确性。
那么程序中的“锁”到底长什么样子，是如何实现的呢？我们先把“上锁”和“解锁”两个行为看作一个函数，从整体上看看在程序中，锁该如何使用。
在这里，我们假设 balance 是我们需要保护的共享变量，简单来看，我们只需要在使用它前进行上锁，用完解锁就可以了。当然，在使用锁前，我们需要申请一把锁（我们当然也可以申请多把锁来给多个共享变量上锁，或者给一个共享变量上多把锁 —— 如果闲的没事干的话）
在上锁时，其余需要使用该共享变量的线程会被阻塞，直到解锁为止，这样我们就保证了在完成必要的修改前，不会有其他线程使用它，造成混乱。可以看到，锁在操作系统的调度系统产生的迷雾中拨开了一片天地，让程序员能够捋清程序的临界区运行的顺序。
我们来看看一个锁的实例 —— Pthread Locks：
在 POSIX 库中的锁名为 pthread_mutex ，即互斥锁（ mutual exclusion ），它的使用就如我们上面所说：
2 具体实现
我们现在已经理解了锁的功能，那么一个锁具体应该如何实现呢？一个好的实现应该以尽可能小的性能代价，实现尽可能高的公平性（避免饥饿），当然，这些都建立在正确实现的前提之上。
1）最早期的锁：开闭中断
最开始的想法非常朴素，我们将目光投向导致需要锁的根源 —— 中断机制。在需要上锁时，我们关闭中断信号，在解锁时，我们则开启中断信号，便保证了指令运行的原子性。
这样的实现在单核处理器上当然是正确的，但是也带来很多问题：
a.开启中断和关闭中断的行为风险过大，将这样的权限交给用户，很难避免这样的权限不被滥用或是恶意使用，造成问题。
b.对于多核处理器，这样的实现并不起作用
c.关闭中断可能带来给操作系统带来许多其他麻烦，如错过其它重要的中断信号等（如关闭中断的期间接受到了磁盘完成读操作的中断信号，CPU就会遗失该信号而无法唤醒对应的进程）
因此，在实际应用中，只有 OS 内部有时会采用开闭中断来对自身的一些关键数据结构进行访问，或是进行信号处理。
2）一个失败的尝试
代码很容易读懂：flag 为 0 代表该锁可用，为 1 则代表有其它线程在使用该锁，需要等待。
然而，这样的实现存在两个问题：
a.正确性问题：考虑线程1在完成第9行代码，即将进入第11行时被调度，线程2通过lock函数进入到临界区，此时会存在两个线程同时进入到临界区，导致问题。
b.性能问题：通过“自旋”，即无限循环等待的方式给性能带来的开销过大。
c.存在“优先级反转”问题
3）利用硬件指令对实现进行纠正
可以看到，现在的这种实现相比上面的错误实现使用了 TestAndSet(oldptr,new_value) 函数来进行赋值，这个函数是由硬件保证执行的原子性的，因而避免了之前的问题。值得注意的是，之所以这个函数叫做 Test 和 Set，是因为其不仅能够设置新值，它还会返回旧值来供你进行检测。
这种锁被称作“自旋锁”，是因为它在等待锁可用时一直在循环等待。显然，这种锁应该和“可抢占式调度器”共同使用。
我们终于正确实现了一种锁，那么这种锁好不好呢？首先是公平性：这种锁没有提供任何公平性保证。其次是性能：自旋锁在多核处理器上表现还不错——进入临界区的线程可以较快退出临界区，但是在单核处理器上的性能表现可能极其糟糕。
4）自旋锁补充
除了 TestAndSet 外，可能还有多种硬件支持的原子性操作可供我们使用，如 CompareAndSwap，CompareAndSwap(oldptr,testvalue,setvalue)的功能是检测oldptr指向的值是否为testvalue，如果是，则设置oldptr指向的为新值setvalue，否则什么也不做。
可以用该操作替换 TestAndSet，实现自旋锁，同时我们也可以看到，CompareAndSwap 的功能是比 TestAndSet 要强大的，只需要将 CompareAndSwap的 testvalue 设置为 oldptr 指向的值即可实现 TestAndSet 的功能。
此外，还有通过“一对”操作实现原子性操作的指令，如：Load-linked 和 Store-Conditional。
LoadLinked(*ptr) 负责返回该指针的值并设置该指针为待检查，StoreConditional(*ptr,value) 首先检查ptr指针自LoadLinked以来值是否经过更改，如果没有更改，则更新值，并返回1，否则什么也不做，返回0。
我们同样可以使用这一对操作替换 TestAndSet 实现锁。
最后介绍的硬件提供的原子性操作是FetchAndAdd(*ptr)，它提供的作用时为ptr指向的指加一，并返回之前的值。
使用 FetchAndAdd 可以制作一个有趣的 Ticket Lock。
利用了“先取票，再服务”的思想，如果有多个进程取了票，但是还没有被服务，则按照取票顺序服务，保护了临界区。
5）抛弃Spining，走向Yield
考虑到在某些情况自旋锁效率太低，我们可能需要其它的锁的形式。这需要额外的操作系统的支持。
我们假设操作系统支持yield()系统调用，即线程主动让出CPU，给其他线程使用，我们则只需要在自旋锁的基础上，将自旋操作转化为yield()即可。
我们来思考一下这样的锁的表现：在很多线程都需要使用同一个锁时，这样的锁表现显然比自旋锁好，但是其仍然会产生许多上下文切换的开销，同时并没有解决饥饿问题。
此时我们就需要请出之前我们在调度中解决公平性问题的专家：队列。（因为先前调度器只是在诸多等待锁的进程中进行随机尝试，并没有选择的依据）
实现如下：
注意，这里的guard是作为lock→flag的锁，flag是真正对于临界区的锁。而park()和unpark()是操作系统提供的进入和退出队列的函数。这里虽然guard仍然引入了自旋的操作，但这样自旋的时间是非常有限的，因为在临界区的指令执行时间很有限。
值得注意的是，在解锁时，如果队列非空，线程并不会把 flag 重新置0，而是简单的将锁“传递给”下个线程，这不仅是为了方便，同时也是正确性的保障：被唤醒的线程并不持有guard的锁，无法设置flag。
同时，该实现存在一个致命的问题：在线程1即将进入park()时，如果线程2先被唤醒并执行完了临界区，释放锁时，如果队列为空（线程1还没有进入队列），那么线程1就会永远的沉睡下去，直至下一次再有线程要获取这把锁。
Solaris的解决方法是，在执行park()前先进行setpark()操作，这个操作是把将要park()但还未park()的线程也类似地组织进一个队列，如果unpark()结束时，该队列不为空，则这个线程的park()立刻返回，进入临界区。
6）不同操作系统的实现
下面给出了Linux系统中一个关于mutex锁的实现：
futex_wait(mutex,expected)，只有在mutex值等于expected时会使线程睡眠，否则会立刻返回。futex_wake(mutex)则会唤醒睡眠队列中的某一个线程。
当线程被唤醒后：futex_wait会返回，重新进入循环，此时atomic_bit_test_set(mutex,31)检测会通过（因为unlock时加了0x80000000)，于是就持有了锁。
值得一说的是，Linux采用的是一种“二阶段”锁，在没有拿到锁的第一阶段，其会先尝试自旋，若经过自旋后，其仍未拿到锁，才进入睡眠。避免了“锁即将释放”，但是线程仍要进入睡眠，增加上下文切换消耗的情况。
3 总结
总之，在软件层面实现锁是复杂的，我们往往需要硬件和操作系统支持，在这两者的支持下，我们可以实现多种锁，每种锁有不同的使用场景，当然，也可以像Linux系统一样实现一个“混合”锁，来提高适用性。