CHAPTER 6 Concurrency：deadlock And Starvation 内容提要 产生死锁与饿死的原因 解决死锁的方法 死锁/同步的经典问题：哲学家进餐问题

6.1 Principles of Deadlock 死锁的定义: Permanent blocking of a set of processes that either compete for system resources or communicate with each other(一组竞争系统资源或互相通信的进程间相互的“永久”阻塞。 ) No efficient solution Involve conflicting needs for resources by two or more processes（所有死锁涉及到两个或更多的进程之间因对资源的需求所引起的冲突。 ）

现在考虑涉及进程和计算机资源的死锁的描述。 例, Process P and Q compete two resources, Their general forms are: Process P Process Q … … Get A Get B … … Get B Get A … … Release A Release B … … Release B Release A

死锁与进程的推进顺序有关。若修改P的代码，则不会产生死锁 Process P … Get A Release A Get B Release B

Reusable Resources (可重用资源) 资源通常可分为两类：可重用的和可消费的。 Used by one process at a time and not depleted by that use ( 可重用资源是指一次只能供一个进程安全地使用，并且不会由于使用而耗尽。) 可重用资源释放之后供其他进程再次使用。 可重用资源的例子：Processors、 I/O channels, main and secondary memory（辅存）、files、 databases、 and semaphores Deadlock occurs if each process holds one resource and requests the other

Example of Deadlock

Another Example of Deadlock Space is available for allocation of 200K bytes, and the following sequence of events occur Deadlock occurs if both processes progress to their second request P1 P2 . . . . . . Request 70K bytes; Request 80K bytes; . . . . . . Request 80K bytes; Request 60K bytes;

Consumable Resources (可消耗资源) Created (produced) and destroyed (consumed) by a process（可消费资源是指可以创建（生产）并且可以销毁（消费）的资源。当进程得到一个资源时，该资源就不再存在了。 ） 可消费资源的例子 ：Interrupts, signals, messages, and information in I/O buffers 可消费资源死锁的例子如下页 ：

Example of Deadlock Deadlock occurs if receive is blocking 此类死锁是由于设计失误造成的，很难发现，且潜伏期较长 P1 P2 . . . . . . Receive(P2); Receive(P1); . . . . . . Send(P2, M1); Send(P1, M2);

Conditions for Deadlock （死锁条件） Mutual exclusion(互斥) only one process may use a resource at a time Hold-and-wait(保持并等待) A process may hold allocated resources while awaiting　assignment of　other No preemption(不剥夺)

Circular wait(环路等待)

Conditions for Deadlock 条件Mutual exclusion、 Hold-and-wait 、 No preemption是死锁产生的必要条件，而非充分条件。 条件Circular wait是前3个条件的潜在的结果。 4个条件连在一起构成了死锁的充分必要条件。

6.2 Deadlock Prevention (预防死锁) 预防死锁是设制一些限制条件,排除死锁发生的可能性. 采用破坏死锁条件,防止死锁发生. “互斥” ： 是某些系统资源固有的属性，不能禁止. 禁止“保持并等待”条件：要求进程一次性地申请其所需的全部资源。若系统中没有足够的资源可分配给它，则进程阻塞。

3.禁止“不剥夺”条件： ①若一个进程占用了某些系统资源，又申请新的资源，则不能立即分配给它。必须让它首先释放出已占用资源，然后再重新申请； ②若一个进程申请的资源被另一个进程占有，OS可以剥夺低优先权进程的资源分配给高优先权的进程（要求此类可剥夺资源的状态易于保存和恢复，否则不能剥夺） 4.禁止“环路等待”的发生 可以将系统的所有资源按类型不同进行线性排队，并赋予不同的序号。进程对某类资源的申请只能按照序号递增的方式进行。

6.3 Deadlock Avoidance (避免死锁) 预防死锁通过实施较强的限制条件实现，降低了系统性能。 避免死锁的关键在于为进程分配资源之前，首先通过计算，判断此次分配是否会导致死锁，只有不会导致死锁的分配才可实行。

Two Approaches to Deadlock Avoidance Do not start a process if its demands might lead to deadlock Do not grant an incremental resource request to a process if this allocation might lead to deadlock

Resource Allocation Denial 资源分配拒绝策略，又称作银行家算法 . State of the system is the current allocation of resources to process 指系统能按某种顺序如<P1，P2，…，Pn>（称<P1，P2，…，Pn>为安全序列），来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成，则称系统处于safe state 若系统不存在这样一个安全序列，则称系统处于unsafe state

图6．6a显示了一个含有4个进程和3个资源的系统的状态。R1、R2和R3的资源总量分别为9、3和6。在当前状态下资源分配给4个进程，资源2和资源3各剩下1个可用单元。

P2 Runs to Completion

P1 Runs to Completion

P3 Runs to Completion

Unsafe State

Unsafe State

死锁避免的优点是它不需要死锁预防中的剥夺和重新运行进程，并且比死锁预防的限制少，但是在使用中也有许多限制： Maximum resource requirement must be stated in advance(预先必须申明每个进程需要的资源总量) Processes under consideration must be independent; no synchronization requirements (考虑的进程必须是无关的，它们执行的顺序必须没有任何同步要求的限制。) There must be a fixed number of resources to allocate(分配的资源数目必须是固定的。) No process may exit while holding resources(若进程占有资源，则不能让其退出系统)

6.4 Deadlock Detection (检测死锁) 检测死锁不同于预防死锁，不限制资源访问方式和资源申请。 OS周期性地执行死锁检测例程，检测系统中是否出现死锁。 死锁检测的算法通过标记没有死锁的进程来确定是否有死锁存在,当所有进程打上标记则未发生死锁,否则死锁发生。

死锁检测算法的执行过程:(最初，所有的进程都是未标记的，然后执行下列步骤：) 1．标记Allocation矩阵中一行全为零的进程： 2．初始化一个临时向量w，令w等于Avai1ab1e向量； 3．查找下标i，使进程i当前未标记且Q(为请求矩阵)的第i行小于等于w，也就是说，对所有的l≤k≤m Qik≤Wk。如果找不到这样的行，终止算法； 4．如果找到这样的行，标记进程i，并把分配矩阵中的相应行加到w中，也就是说，对所有的 1≤ k≤m，令Wk=Wk+Aik，返回步骤3。

Recovery(恢复) 一旦检测到死锁，就需要某种策略以恢复死锁 ,列出恢复死锁的方法： 1．取消所有的死锁进程。 2．把每个死锁进程备份到前面定义的某些检查点，并且重新启动所有进程。这要求在系统中构造重新运行和重新启动机制。该方法的风险是会再次发生原来的死锁。但是，并发进程的不确定性通常能保证不会发生这种情况。 3．逐个取消死锁进程直到不再存在死锁。 4．逐个剥夺资源直到不再存在死锁。

Dining Philosophers Problem 描述：有5个哲学家，他们的生活方式是交替地进行思考和进餐。哲学家们共用一张圆桌，分别坐在周围的五张椅子上。圆桌中间放有一大碗面条，每个哲学家分别有1个盘子和1支叉子。如果哲学家想吃面条，则必须拿到靠其最近的左右两支叉子。进餐完毕，放下叉子继续思考。 要求：设计一个合理的算法，使全部哲学家都能进餐（非同时）。算法必须避免死锁和饥饿，哲学家互斥共享叉子。

Dining Philosophers Problem

Dining Philosophers Problem 利用Semaphores解决哲学家进餐的问题 见图6.11，P272 可能出现死锁和饥饿  

Dining Philosophers Problem 可行的解决方案：只允许4个哲学家同时进餐厅用餐，则至少有一个哲学家可以拿到两支叉子进餐，完毕，放下叉子，其他哲学家就可进餐。不会出现死锁和饥饿 见图6.12, P273