参考教材：
Operating Systems: Three Easy Pieces
Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau
在线阅读：
http://pages.cs.wisc.edu/~remzi/OSTEP/
University of Wisconsin Madison 教授 Remzi Arpaci-Dusseau 认为课本应该是免费的。
————————————————————————————————————————
这是专业必修课《操作系统原理》的复习指引。
在本文的最后附有复习指导的高清截图。需要掌握的概念在文档截图中以蓝色标识，并用可读性更好的字体显示 Linux 命令和代码。代码部分语法高亮。
操作系统原理不是语言课，本复习指导对用到的编程语言的语法的讲解也不会很细致。如果不知道代码中的一些关键字或函数的具体用法，你应该自行查找相关资料。
九 死锁与活锁
有学者研究了常见的开源软件中的并发过程的Bug，它们大部分是非死锁引起的：
在这一章，我们对并发中的错误进行一些稍微深入的讨论。
1、违反原子性（atomicity-violation）是并发过程中的一种常见Bug。示例：
线程1：
if(thd->proc_info){
fputs(thd->proc_info, …);
}
线程2：
thd->proc_info = nullptr;
相信你已经很容易举出问题发生的条件：如果线程1在判断分支条件后就被打断，转而执行线程2，那么proc_info就变成了空指针。再次切回线程1的时候，对空指针的解引用将报错。
解决方法很简单：在这些代码前后增加获得锁和释放锁的语句。修正后的代码在这里略去。线程2虽然只有单条赋值语句，但是也需要用锁来确保原子性。因为很多时候写操作是非原子的。如果写的过程被调度器打断，转由其它线程对共享资源进行写入，那么接下来被打断的线程继续写入时，刚才的线程所做的更改就丢失了。这很可能会引发严重问题。
2、多个线程错误的执行顺序也有概率引发严重问题。举例：
线程1：
void init() {
mThread = PR_CreateThread(mMain, …);
}
线程2：
void mMain(…) {
mState = mThread->State;
}
显然，线程2应该在线程1的第一个语句之后再执行。但是，如果线程2一被创建就立刻运行（返回的指针还没来得及写入到mThread），那么线程2就是在尝试访问空指针或内存中的任意位置（当mThread未初始化时）。
解决方法是：引入条件变量来固定执行顺序。一种修改如下：
pthread_mutex_t mtLock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t mtCond = PTHREAD_COND_INITIALIZER;
int mtInit = 0;
//Thread 1::
void init() {
…
mThread = PR_CreateThread(mMain, …);
// signal that the thread has been created…
pthread_mutex_lock(&mtLock);
mtInit = 1;
pthread_cond_signal(&mtCond);
pthread_mutex_unlock(&mtLock);
…
}
//Thread 2::
void mMain(…) {
…
// wait for the thread to be initialized…
pthread_mutex_lock(&mtLock);
while (mtInit == 0)
pthread_cond_wait(&mtCond, &mtLock);
pthread_mutex_unlock(&mtLock);
mState = mThread->State;
…
}
可见，当线程2抢先于线程1运行时，不会执行到mState = mThread->State一句，而是会在这之前就休眠。当然，mThread指针本身也可以代替指示变量mtInit。当有线程可能被等待时，没有指示变量刻画被等待线程是否结束的后果在第八章已经强调过了：当被等待的线程在等待的线程开始等待之前抢先结束，那么等待的线程将无法被唤醒。
3、死锁（deadlock），又譯為死结，計算機科學名詞。當兩個以上的運算單元，雙方都在等待對方停止執行，以取得資源，但是沒有一方提前退出時，就稱為死結。
例如：线程1持有锁1，但线程2需要锁1；线程2持有锁2，但线程1需要锁2。线程1等待线程2释放锁2，线程2等待线程1释放锁1。如果没有干预，这两个线程就会一直干等下去。
可能你会觉得解决这种问题很容易：在获取资源的顺序上下功夫，让它们都遵循特定的顺序。但事实上，在庞大的计算机软件中，依赖关系非常复杂。这是死锁容易发生的第一个原因。例如在OS中，虚拟内存子系统要访问文件系统，将一页换入内存；文件系统随后又从内存中读出一页。操作系统、文件系统这种大型软件一旦出现死锁，影响是极其严重的。如果系统中只有一个进程，当然不会产生死锁。如果每个进程仅需不同的资源，也不会产生死锁。不过这只是理想状态，在现实中是可遇不可求的。
第二个原因是封装（encapsulation）。有的库本身会引发死锁，例如Java的Vector类。看下面的语句：
Vector v1, v2;
v1.addAll(v2);
v1.addAll(v2);在执行前，会先请求需要的锁。如果v1.addAll(v2);开始执行了，而另一个线程几乎同时开始执行v2.addAll(v1);，则有引发死锁的潜在风险。
Java中的Vector对所有add()、get()、set()方法都加了synchronized同步块，但某些情况仍然需要自己处理同步。例如有个线程在遍历某个Vector、有个线程同时在add这个Vector，依然很容易出现ConcurrentModificationException。
由于Vector类为了预防死锁，过多采用了相应的机制，但有的时候效果又不甚理想（还显著影响了性能），目前Vector类已经不被建议在无需多线程同步的场景中使用。
库本身引发死锁，是使用库的用户很难预料到的。
4、如果系统中只有一个进程，当然不会产生死锁。如果每个进程仅需求不同的资源，也不会产生死锁。不过这只是理想状态，在现实中是可遇不可求的。
死锁的发生需要四个条件：
【1】互斥（mutual exclusion）。线程要求独占一些需要的资源（例如互斥锁）。
【2】持有和等待（hold-and-wait）。线程们占有了分配给它们的资源（例如已经获得的互斥锁），而又在等待另外的资源（例如要求另外的互斥锁解锁）。
【3】非抢占（no preemption）。资源（例如：锁）不能被强制从拥有它们的线程中剥夺。
【4】循环等待（circular wait）。存在一个关于线程的环形链，即链上的每个线程都需要下一个线程占用的资源。
如果这四个条件有一个不满足，那么死锁不会发生。所以我们从这四个条件着手去阻止死锁。
5、避免死锁最常见的切入点是阻止循环等待。即让线程按照一定的顺序获得资源。一个小技巧是根据需要的资源（例如：锁）所在的地址高低决定获取顺序。于是环形链变成了直线，不会发生循环等待。
但是这种方案也存在它的缺点，比如在大型系统当中，模块隔离得非常彻底，不同模块的研发人员之间都不清楚具体的实现细节，在这样的情况下就很难做到整个系统层面的全局锁排序了。不过我们可以对方案进行扩充，例如Linux在内存映射代码就使用了一种锁分组排序的方式来解决这个问题。锁分组排序首先按模块将锁分为了不同的组，每个组之间定义了严格的加锁顺序，然后再在组内对具体的锁按规则进行排序，这样就保证了全局的加锁顺序一致。在Linux的对应的源码顶部，我们可以看到有非常详尽的注释定义了明确的锁排序规则。
这种策略使得资源的利用率和系统吞吐量都有很大提高，但是也存在以下缺点：
（1）限制了进程对资源的请求，同时给系统中所有资源合理编号也是件困难事，并增加了系统开销；
（2）为了遵循按编号申请的次序，暂不使用的资源也需要提前申请，从而增加了进程对资源的占用时间。
6、破坏保持和等待条件，是指一次性将所有的锁都获得。整个过程也是原子性的，于是别的线程无法在该线程获得锁期间也来获得同样的锁，死锁也就无法发生。如果某个线程所需的全部资源得不到满足，则不分配任何资源，此线程暂不运行。只有当系统能够满足当前线程的全部资源需求时，才一次性地将所申请的资源全部分配给该线程。但是，这种策略也有如下缺点：
（1）许多情况下，一个线程在执行之前不可能知道它所需要的全部资源。这是由于线程在执行时是动态的，不可预测的；
（2）资源利用率低。无论所分资源何时用到，一个线程只有在占有所需的全部资源后才能执行。即使有些资源最后才被该线程用到一次，但该线程在生存期间却一直占有它们，造成长期占着不用的状况。这显然是一种极大的资源浪费；
（3）降低并发性。因为资源有限，又加上存在浪费，能分配到所需全部资源的线程个数就必然少了。
7、如果一个线程已经获取到了一些锁，那么这个线程释放锁之前这些锁是不会被强制抢占的。但是为了防止死锁的发生，可以让线程在获取后续的锁失败时主动放弃已经持有的锁并在之后重新获取，其它等待这些锁的线程就得以继续执行了。
同样的，这个方案也有自己的缺陷：
（1）虽然这种方式可以避免死锁，但是如果几个互相存在竞争的线程不断地放弃、重试、放弃，那么就会导致活锁（livelock），也称活结。與死結相似，死結是行程都在等待對方先釋放資源（它们均因为等待而被阻塞，即“拿不到就死等”）；活結則是行程彼此釋放資源又同時占用對方釋放的資源（即“拿不到就重试”），當此情況持續發生時，儘管資源的狀態不斷改變，但每個行程都無法取得所需資源，使得事情沒有任何進展。在这种情况下，虽然线程没有因为锁冲突被卡死，有可能自行解开活锁，但是线程仍然会被阻塞相当长的时间甚至一直处于重试当中。
一种解决方式是每次重试前添加一个随机的延迟时间，这样就能大大降低冲突概率了。在一些接口请求框架中也使用了这种技巧来分散服务高峰期的请求重试操作，避免过多的无用重试导致服务崩溃。
（2）还是因为程序的封装性，在一个模块中难以释放其他模块中已经获取到的锁。
另外，在释放锁时，如果在获得将要释放的锁之后还获取了其它资源（例如申请了新的内存空间），那么这些资源也要一并释放。
其实这种方法也可以不算作真正的抢占，因为这并不是强行把线程拥有的资源夺走并且不归还。
这种预防死锁的方法实现起来比较困难，会降低系统性能。
8、还剩最后一个方向，就是破坏互斥条件。可是我们总不能永远不编写不具有临界区的代码。怎么办？
答案是借助硬件实现的无锁（lock-free）方法。一个例子是CAS（compare-and-swap）指令。第7章的第12点已经提到，该操作通过将内存中的值与指定数据进行比较，当数值一样时将内存中的数据替换为新的值。
以原子性地增加某个变量的值为例，我们可以这样做：
void AtomicIncrement(int* value, int amount) {
do {
int old = value;
} while (CompareAndSwap(value, old, old + amount) == 0);
}
这个过程无需获得锁，也就不会产生死锁了。不过如果一个变量同时被多个线程以CAS方式修改，那么就有可能导致出现活锁，多个线程将会一直不断重试CAS操作。所以CAS操作的成本和数据竞争的激烈程度密切相关，在一些竞争非常激烈的情况下，CAS操作的成本甚至会超过互斥锁。
再举一个复杂些的例子：链表的插入。在链表的头部插入节点的过程如下：
void insert(int value) {
node_t n = malloc(sizeof(node_t));
assert(n != NULL);
n->value = value;
n->next = head;
head = n;
}
当然，如果多个线程几乎同时调用这个操作，也会引发竞争条件：如果一个线程在n->next = head;之后被打断，然后另一个线程完整执行了一次插入，而后被打断的线程继续执行。最终就会有一个节点无法通过链表的一端被遍历到。
因为链表的头结点head是共享的，所以在操作head的语句前后加上锁的相关语句即可。修正后的代码是这样的：
void insert(int value) {
node_t* n = malloc(sizeof(node_t));
assert(n != NULL);
n->value = value;
pthread_mutex_lock(listlock); // begin critical section
n->next = head;
head = n;
pthread_mutex_unlock(listlock); // end critical section
}
如果使用CAS指令，代码就变成这样（答案不唯一）：
void insert(int value) {
node_t* n = malloc(sizeof(node_t));
assert(n != NULL);
n->value = value;
do {
n->next = head;
} while (CompareAndSwap(&head, n->next, n) == 0);
}
当另一个线程把这个修改头结点的过程打断，do-while循环就会重试。请自行在草稿纸上画图，验证该方法的正确性。
9、还可以通过调度策略来预防死锁。
设有2个CPU核心和4个线程。如果我们知道线程T1、T2都需要获得锁L1和L2，T3只需要获得锁L2，T4不获得锁：
一个机智的调度器就会使T1和T2不同时运行，这样就不会产生死锁。一种调度方式是：
T3、T1或者T3、T2都是可以重叠运行的。因为T3只获得一个锁，之后就不会再需要其它锁，也就无法形成至少两个进程互相持有对方请求的资源并互相等待对方释放已有资源的换路。
如果锁的需求是这样的：
一种不产生死锁的保守性调度策略如下：
T4不获得锁，所以可以和任何进程并发。T1、T2、T3都需要获得锁L1和L2，因此具有引发死锁的可能性。如果调度策略一时不好决定，就只好保守地采用并发度较低的调度策略了。
10、对付死锁的另一个策略是：允许死锁发生，并且检测到死锁以后采取措施解除死锁。这个策略多为数据库采用。常用的方法有：
（1）超时法。如果事务的等待时间超时，就一律认为发生了死锁。这个方法实现简单，但是具有一定的误判概率。
（2）等待图法。等待图的每个节点是一个事务，边的起点和终点分别代表等待另一事务锁的事务和被等待释放锁的事务。每隔一段时间（比如数秒）生成事务等待图并检测是否具有环路。如果是，则表示出现死锁，以付出代价最小的方式结束引发死锁的一个事务。
对操作系统中的死锁，则利用资源分配图（resource allocation graph）来描述。
资源分配图G = (N, E)是一个对偶图，节点集N = 进程节点集P∪资源节点集R。每一条边都连接一个进程节点和一个资源节点。由进程指向资源的边为请求边，代表该进程请求1单位该资源；由资源指向进程的边为分配边，代表1单位该资源分配给该进程。
一个资源分配图的示例如下。连接资源的边实际上连接到该种资源中的一个。
11、根据资源分配图，可以判断是否陷入死锁。每次删去一个不阻塞的进程对应的非孤立节点及其请求边和分配边，直到无法再删去。我们有死锁定理：一张资源分配图代表的状态S为死锁，当且仅当S中仍然存在非孤立节点。
有关文献已经证明：资源分配图的简化顺序与简化结果无关。
死锁检测方法的代价不低。如果每次分配资源后都进行死锁检测，虽然能尽早发现死锁，但会耗费大量的CPU时间。于是我们可以选择定期检查，或者当CPU使用率下降到一定程度后自动触发检查。
12、刚才讲的破坏死锁的四个条件的方法，都需要由程序员在编程期间做好相应工作。在操作系统中，如果发现了死锁，怎么当场处理呢？
【1】抢占资源。即从一个或多个进程中强制剥夺足够数量的资源分配给死锁的进程来解除死锁。
【2】终止或回滚进程。出现死锁时，如果可能，也可以将进程回滚到获得死锁前的某个状态，再继续运行。如果不能，则需要结束进程。而终止（或回滚）进程也有不同的方案：
（1）终止全部死锁进程。这种方法简单粗暴，但代价很大。因为强行结束进程会导致未保存的数据丢失，使得许多工作不得不从头再来。还可能有其它方面的代价，这里不一一列举。
（2）逐个终止进程，直到拥有足够的资源。怎样处理使得破坏死锁付出的代价最小呢？怎样才算代价最小，很难有一个精确的度量。这里只简单说明一下选择被终止进程时需要考虑的若干因素：
·优先级。
·已执行时间，以及剩余时间（如果可以得知的话）。
·已使用资源的多少，以及以后还需要的资源种类和数量（如果可以得知的话）。
·进程是交互式的还是批处理（batch）式的？
13、有时候可以不处理死锁。例如如果某个操作系统一两年才出现一个死锁，那么出现死锁后简单重启一下就可以（只要不会造成不可接受的损失）。Tom West定律告诉我们：“不是所有值得做的事情都值得把它们做好。”如果一件坏事几乎不会发生，而且即使发生了，造成的损失也很小。那么我们的首要选择是：不去管它。当然，不是所有场合都可以这样的。如果你在设计航天飞机，假设某一错误概率很低，但它可能令航天器直接爆炸导致机上人员全员罹难，那么你不应该听从这个建议。
在工程的世界里，很多工作受到工期和成本的限制。工程师们应当有能力判断哪些事情是紧要的，必须尽快完成；哪些事情可以在以后慢慢补上；又或者哪些事情根本不用去做。这个能力只能凭借经验去形成，并结合具体情境给出结论。
14、Dijkstra还发明了银行家算法（banker’s algorithm）。但是银行家算法并不是普适性的算法。它只在少数领域有用，例如只运行特定任务、对每个运行任务的行为都知根知底的一些嵌入式系统。总之，死锁一般是不可完全避免的。各种预防、避免死锁的方法都有其弊端。具体采用哪些方案，应当结合操作系统面对的应用环境来决定。
关于银行家算法，我会单独写一篇文章来解析。
