anki

死锁的定义

Q: 什么是死锁？死锁的本质是什么？死锁会带来什么后果？
A: 死锁是指多个进程因竞争资源而造成的一种僵局，使得各个进程都被阻塞，若无外力干涉，这些进程都无法向前推进。死锁的本质是多个进程互相等待对方释放资源，从而导致所有进程都无法继续执行。死锁会带来以下后果：

• 系统资源无法有效利用：被死锁的进程占有的资源无法被其他进程使用。
• 系统效率降低：死锁会导致系统性能下降，甚至崩溃。
  补充细节：死锁是一种常见的并发编程问题，它会导致系统资源无法有效利用，影响系统效率。

死锁与饥饿

Q: 死锁和饥饿有什么区别？
A: 死锁是指多个进程因竞争资源而造成的一种僵局，使得各个进程都被阻塞，若无外力干涉，这些进程都无法向前推进。饥饿是指进程在信号量内无穷等待的情况。死锁和饥饿的主要差别:

• 发生饥饿的进程可以只有一个; 而死锁是因循环等待对方手里的资源而导致的, 因此, 如果有死锁现象, 那么发生死锁的进程必然大于或等于两个。
• 发生饥饿的进程可能处于就绪态 (长期得不到 CPU, 如 SJF 算法的问题), 也可能处于阻塞态 (如长期得不到所需的 I/O 设备, 如上述举例); 而发生死锁的进程必定处于阻塞态。
  补充细节：死锁和饥饿都属于并发编程中的常见问题，但两者在本质上有所区别。死锁是一种“互相等待”的现象，而饥饿则是指一个或多个进程长期得不到资源，导致无法执行。

死锁产生的原因

系统资源的竞争

Q: 系统资源竞争是如何导致死锁的？
A: 通常系统中拥有的不可剥夺资源 (如磁带机、打印机等), 其数量不足以满足多个进程运行的需要, 使得进程在运行过程中, 会因争夺资源而陷入僵局。只有对不可剥夺资源的竞争才可能产生死锁, 对可剥夺资源 (如 CPU 和主存) 的竞争是不会引起死锁的。
补充细节：当多个进程同时请求不可剥夺资源时，如果资源数量不足以满足所有进程的需求，就会导致一些进程被阻塞。如果这些被阻塞的进程又互相等待对方释放资源，就会形成死锁。

进程推进顺序非法

Q: 进程推进顺序非法是如何导致死锁的？
A: 请求和释放资源的顺序不当,也同样会导致死锁。例如,进程 分别保持了资源 , 而 申请资源 申请资源 时,两者都会因为所需资源被占用而阻塞,于是导致死锁。
补充细节：进程在请求和释放资源时，需要遵循一定的顺序，如果顺序不当，就会导致死锁。例如，进程 A 先获取资源 R1，然后请求资源 R2，而进程 B 先获取资源 R2，然后请求资源 R1，这样一来，两个进程就会互相等待，最终导致死锁。

死锁产生的必要条件

Q: 死锁的四个必要条件是什么？
A: 产生死锁必须同时满足以下 4 个条件, 只要其中任一条件不成立, 死锁就不会发生。
补充细节：理解死锁的四个必要条件对于预防和避免死锁至关重要。

互斥条件

Q: 什么是互斥条件？
A: 进程要求对所分配的资源 (如打印机) 进行排他性使用, 即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源, 则请求进程只能等待。
补充细节：互斥条件是指，一个资源在同一时间只能被一个进程访问，其他进程必须等待。这是死锁发生的必要条件之一，因为如果资源可以被多个进程同时访问，就不会出现互相等待的情况。

不可剥夺条件

Q: 什么是不可剥夺条件？
A: 进程所获得的资源在未使用完之前, 不能被其他进程强行夺走, 即只能由获得该资源的进程自己来释放 (只能是主动释放)。
补充细节：不可剥夺条件是指，进程一旦获得资源，就不能被其他进程强行夺走，只能由该进程自己释放。这个条件也是死锁发生的必要条件之一，因为如果资源可以被系统强行剥夺，就可以打破互相等待的局面，从而避免死锁。

请求并保持条件

Q: 什么是请求并保持条件？
A: 进程已经保持了至少一个资源, 但又提出了新的资源请求, 而该资源已被其他进程占有, 此时请求进程被阻塞, 但对自己已获得的资源保持不放。
补充细节：请求并保持条件是指，进程在请求新的资源时，仍然持有已经分配给它的资源。这个条件也是死锁发生的必要条件之一，因为如果进程在请求新资源时必须先释放已经持有的资源，就不会出现互相等待的情况。

循环等待条件

Q: 什么是循环等待条件？
A: 存在一种进程资源的循环等待链, 链中每个进程已获得的资源同时被链中下一个进程所请求。即存在一个处于等待态的进程集合 ,其中 等待的资源被 占有, 等待的资源被 占有,如图 2.13 所示。
补充细节：循环等待条件是指，多个进程形成一个闭环，每个进程都在等待下一个进程所持有的资源。这个条件也是死锁发生的必要条件之一，因为只有当多个进程形成循环等待时，才会出现互相等待，最终导致死锁。

死锁的处理策略

Q: 死锁的处理策略有哪些？
A: 为使系统不发生死锁, 必须设法破坏产生死锁的 4 个必要条件之一, 或允许死锁产生, 但当死锁发生时能检测出死锁, 并有能力实现恢复。
补充细节：死锁的处理策略可以分为死锁预防、死锁避免和死锁检测与解除。

死锁预防

Q: 什么是死锁预防？
A: 设置某些限制条件, 破坏产生死锁的 4 个必要条件中的一个或几个。
补充细节：死锁预防是指通过设置一些限制条件，在系统运行之前就避免死锁的发生。

避免死锁

Q: 什么是死锁避免？
A: 在资源的动态分配过程中, 用某种方法防止系统进入不安全状态。
补充细节：死锁避免是指在系统运行过程中，通过动态分配资源，防止系统进入不安全状态，从而避免死锁的发生。

死锁的检测及解除

Q: 什么是死锁的检测及解除？
A: 无须采取任何限制性措施, 允许进程在运行过程中发生死锁。通过系统的检测机构及时地检测出死锁的发生, 然后采取某种措施解除死锁。
补充细节：死锁检测与解除是指在系统运行过程中，允许死锁的发生，然后通过检测机制发现死锁，并采取相应的措施解除死锁。

死锁预防

Q: 死锁预防的策略有哪些？
A: 预防死锁的发生只需破坏死锁产生的 4 个必要条件之一即可。
补充细节：死锁预防策略通过破坏死锁的四个必要条件之一来防止死锁的发生。

破坏互斥条件

Q: 如何破坏互斥条件？
A: 如果将只能互斥使用的资源改造为允许共享使用, 那么系统不会进入死锁状态。但有些资源根本不能同时访问, 如打印机等临界资源只能互斥使用。所以, 破坏互斥条件而预防死锁的方法不太可行, 而且为了系统安全, 很多时候还必须保护这种互斥性。
补充细节：破坏互斥条件意味着允许多个进程同时访问资源，但这在很多情况下是不现实的，因为许多资源本质上是不可共享的。

破坏不可剥夺条件

Q: 如何破坏不可剥夺条件？
A: 当一个已经保持了某些不可剥夺资源的进程, 请求新的资源而得不到满足时, 它必须释放已经保持的所有资源, 待以后需要时再重新申请。这意味着, 进程已占有的资源会被暂时释放, 或者说是被剥夺了, 从而破坏了不可剥夺条件。
补充细节：破坏不可剥夺条件意味着系统可以强行剥夺进程已经获得的资源，但这会带来一些问题，例如：

• 效率低下：反复申请和释放资源会增加系统开销，降低系统效率。
• 数据丢失：释放已获得的资源可能会导致进程之前的工作失效，需要重新开始。

破坏请求并保持条件

Q: 如何破坏请求并保持条件？
A: 要求进程在请求资源时不能持有不可剥夺资源, 可以通过两种方法实现:

1. 采用预先静态分配方法, 即进程在运行前一次申请完它所需要的全部资源。在它的资源未满足前, 不让它投入运行。在进程的运行期间, 不会再提出资源请求, 从而破坏 “请求” 条件。在等待期间, 进程不占有任何资源, 从而破坏了 “保持” 条件。
2. 允许进程只获得运行初期所需的资源后, 便可开始运行。进程在运行过程中再逐步释放已分配给自己且已使用完毕的全部资源后, 才能请求新的资源。
   补充细节：破坏请求并保持条件意味着进程不能在请求资源时持有其他资源，可以采取以下两种方法：

• 预先静态分配：进程在运行前一次性申请完所有需要的资源，如果无法满足，则阻塞等待，直到所有资源都可用。这种方法简单易行，但会造成资源浪费，因为一些资源可能在进程执行过程中才需要。
• 逐步释放：进程在运行过程中逐步释放已经使用完的资源，然后才能请求新的资源。这种方法可以提高资源利用率，但会增加系统开销，因为需要频繁地释放和申请资源。

破坏循环等待条件

Q: 如何破坏循环等待条件？
A: 为了破坏循环等待条件, 可以采用顺序资源分配法。首先给系统中的各类资源编号, 规定每个进程必须按编号递增的顺序请求资源, 同类资源 (编号相同的资源) 一次申请完。也就是说, 一个进程只在已经占有小编号的资源时, 才有资格申请更大编号的资源。按此规则, 已持有大编号资源的进程不可能再逆向申请小编号的资源, 因此不会产生循环等待的现象。
补充细节：破坏循环等待条件意味着限制进程请求资源的顺序，可以采用以下方法：

• 资源编号：对系统中的所有资源进行编号，规定进程必须按照编号递增的顺序请求资源。这种方法简单易行，但会降低资源利用率，因为一些进程可能需要先申请高编号的资源，再申请低编号的资源。

死锁避免

Q: 死锁避免的策略是什么？
A: 避免死锁同样属于事先预防策略, 但并不是事先采取某种限制措施破坏死锁的必要条件, 而是在每次分配资源的过程中, 都要分析此次分配是否会带来死锁风险, 只有在不产生死锁的情况下, 系统才会为其分配资源。这种方法所施加的限制条件较弱, 可以获得较好的系统性能。
补充细节：死锁避免是指在系统运行过程中，动态地分析资源分配情况，避免系统进入不安全状态，从而避免死锁的发生。

系统安全状态

Q: 什么是系统安全状态？
A: 避免死锁的方法中, 允许进程动态地申请资源, 但系统在进行资源分配之前, 应先计算此次分配的安全性。若此次分配不会导致系统进入不安全状态, 则允许分配; 否则让进程等待。
补充细节：系统安全状态是指，系统可以按照某种顺序分配资源，并使所有进程都能顺利执行完毕。

Q: 什么是安全状态？
A: 所谓安全状态,是指系统能按某种进程推进顺序 为每个进程 分配其所需的资源,直至满足每个进程对资源的最大需求,使每个进程都可顺利完成。此时称 为安全序列 (可能有多个)。若系统无法找到一个安全序列, 则称系统处于不安全状态。
补充细节：安全状态是指，系统中存在一个安全序列，按照这个序列分配资源，可以保证所有进程都能顺利执行完毕。

Q: 系统处于安全状态和不安全状态分别会导致什么？
A: 如果系统处于安全状态, 则一定不会发生死锁;
若系统进入不安全状态, 则有可能发生死锁 (处于不安全状态未必发生死锁, 但发生死锁时一定是处于不安全状态)。
补充细节：如果系统处于安全状态，则系统一定不会发生死锁；而如果系统进入不安全状态，则有可能发生死锁，但并非所有不安全状态都会导致死锁。

银行家算法

Q: 什么是银行家算法？
A: 银行家算法是最著名的死锁避免算法, 其思想是: 将操作系统视为银行家, 操作系统管理的资源视为银行家管理的资金, 进程请求资源相当于用户向银行家贷款。进程运行之前先声明对各种资源的最大需求量, 其数目不应超过系统的资源总量。当进程在运行中申请资源时, 系统必须先确定是否有足够的资源分配给该进程。若有, 再进一步试探在将这些资源分配给进程后, 是否会使系统处于不安全状态。如果不会, 才将资源分配给它, 否则让进程等待。
补充细节：银行家算法是一种死锁避免算法，它要求进程在运行之前先声明对资源的最大需求量，然后系统根据当前的资源分配情况，判断是否可以安全地分配资源给进程。

数据结构描述

Q: 银行家算法需要定义哪些数据结构？
A: 假设系统中有 个进程, 类资源,在银行家算法中需要定义下面 4 个数据结构。

1. 可利用资源向量 Available: 含有 个元素的数组,其中每个元素代表一类可用的资源数目。Available 表示此时系统中有 个 类资源可用。
2. 最大需求矩阵 Max: 矩阵,定义系统中 个进程中的每个进程对 类资源的最大需求。 表示进程 需要 类资源的最大数目为 。
3. 分配矩阵 Allocation: 矩阵,定义系统中每类资源当前已分配给每个进程的资源数。 Allocation 表示进程 当前已分得 类资源的数目为 。
4. 需求矩阵 Need: 矩阵,表示每个进程接下来最多还需要多少资源。Need 表示进程 还需要 类资源的数目为 。
   补充细节：这些数据结构包含了系统中每个进程对资源的需求信息以及当前资源的分配情况，是银行家算法进行安全检测的基础。

Q: 这四个数据结构之间有什么关系？
A: 上述三个矩阵间存在下述关系:

补充细节：需求矩阵等于最大需求矩阵减去分配矩阵，反映了每个进程还需要多少资源才能满足其最大需求。

Q: 通常情况下，哪两个矩阵是已知条件？
A: 通常, Max 矩阵和 Allocation 矩阵是题中的已知条件, 而求出 Need 矩阵是解题的第一步。
补充细节：在实际应用中，最大需求矩阵和分配矩阵通常是已知的，而需求矩阵需要根据这两个矩阵进行计算。

银行家算法描述

Q: 银行家算法的步骤是什么？
A: 设 Request 是进程 的请求向量, 表示进程 需要 类资源 个。当 发出资源请求后, 系统按下述步骤进行检查:
① 若 ,则转向步骤②; 否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。
② 若 Request Available ,则转向步骤③; 否则,表示尚无足够资源, 必须等待。
③ 系统试探着将资源分配给进程 ,并修改下面数据结构中的数值:

④ 系统执行安全性算法, 检查此次资源分配后, 系统是否处于安全状态。若安全, 才正式将资源分配给进程 ,以完成本次分配; 否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程 等待。
补充细节：银行家算法通过四个步骤来判断是否可以将资源分配给进程：

• 检查请求的资源是否超过进程的最大需求量
• 检查系统中是否有足够的可用资源
• 试探性地分配资源给进程，并更新相关数据结构
• 执行安全性算法，判断系统是否处于安全状态

安全性算法

Q: 安全性算法的步骤是什么？
A: 设置工作向量 Work,表示系统中的剩余可用资源数目,它有 个元素,在执行安全性算法前,令 Work Available。
① 初始时安全序列为空。
② 从 Need 矩阵中找出符合下面条件的行: 该行对应的进程不在安全序列中, 而且该行小于或等于 Work 向量, 找到后, 将对应的进程加入安全序列; 若找不到, 则执行步骤④。
③ 进程 进入安全序列后,可顺利执行,直至完成,并释放分配给它的资源,所以应执行 Work Work + Allocation ,其中 Allocation 是 Allocation 矩阵中对应的行,返回步骤②。
④ 若此时安全序列中已有所有进程, 则系统处于安全状态, 否则系统处于不安全状态。
补充细节：安全性算法通过以下步骤来判断系统是否处于安全状态：

• 初始化工作向量，表示系统中剩余的可用资源
• 找到一个进程，其需求量小于或等于工作向量，并将该进程加入安全序列
• 将该进程释放的资源添加到工作向量中
• 重复步骤 2 和 3，直到所有进程都加入安全序列，或无法找到满足条件的进程

死锁检测和解除

Q: 什么是死锁检测？
A: 死锁检测是指在系统中不采取任何预防或避免措施, 允许进程在运行过程中发生死锁, 然后通过系统的检测机构及时地检测出死锁的发生。
补充细节：死锁检测是指在系统运行过程中，允许死锁的发生，然后通过检测机制发现死锁。

Q: 死锁检测的方法有哪些？
A: 死锁检测一般采用两种方法: 资源有向图法 和 资源矩阵法。
补充细节：死锁检测的方法主要有两种：资源有向图法和资源矩阵法。

资源有向图法

Q: 如何使用资源有向图法进行死锁检测？
A: 可用资源分配图来检测系统所处的状态是否为死锁状态。
补充细节：资源有向图法通过构建资源分配图来判断系统是否处于死锁状态。

Q: 如何简化资源分配图？
A: 简化资源分配图可检测系统状态 是否为死锁状态。简化方法如下:

1. 在资源分配图中,找出既不阻塞又不孤立的进程 (找出一条有向边与它相连,且该有向边对应资源的申请数量小于或等于系统中已有的空闲资源数量,如在图 2.15(a)中, 没有空闲资源, 有一个空闲资源。若所有连接该进程的边均满足上述条件,则这个进程能继续运行直至完成, 然后释放它所占有的所有资源)。消去它所有的请求边和分配边, 使之成为孤立的节点。在图 2.15(a)中, 是满足这一条件的进程节点,将 的所有边消去,便得到图 2.15(b)所示的情况。
2. 进程 所释放的资源,可以唤醒某些因等待这些资源而阻塞的进程,原来的阻塞进程可能变为非阻塞进程。在图 2.15(a)中, 就满足这样的条件。根据 1) 中的方法进行一系列简化后, 若能消去图中所有的边, 则称该图是可完全简化的, 如图 2.15(c)所示。

Q: 如何判断资源分配图的资源是否空闲？
A: 这里要注意一个问题, 判断某种资源是否有空闲, 应该用它的资源数量减去它在资源分配图中的出度,例如在图 2.15(a)中, 的资源数为 3,而出度也为 3,所以 没有空闲资源, 的资源数为 2,出度为 1,所以 有一个空闲资源。
补充细节：资源有向图法通过对资源分配图进行简化来判断系统是否处于死锁状态。简化方法是：

• 找到一个既不阻塞又不孤立的进程，该进程可以获得所有需要的资源，并将其从图中删除。
• 重复上一步，直到所有进程都被删除或者无法找到满足条件的进程。
• 如果所有进程都被删除，则系统没有死锁；否则，系统处于死锁状态。

Q: 什么是死锁定理？
A: 为死锁的条件是当且仅当 状态的资源分配图是不可完全简化的,该条件为死锁定理。
补充细节：死锁定理是指，如果资源分配图不可完全简化，则系统处于死锁状态。

资源矩阵法

Q: 如何使用资源矩阵法进行死锁检测？
A: 死锁检测还可以采用资源矩阵法。资源矩阵法需要维护三个矩阵: 可用资源矩阵、分配矩阵和需求矩阵。通过对这三个矩阵进行分析，可以判断系统是否处于死锁状态。
补充细节：资源矩阵法通过分析可用资源矩阵、分配矩阵和需求矩阵来判断系统是否处于死锁状态。

死锁解除

Q: 什么是死锁解除？
A: 一旦检测出死锁, 就应立即采取相应的措施来解除死锁。
补充细节：死锁解除是指在检测到死锁后，采取一些措施来解除死锁状态。

Q: 死锁解除的主要方法有哪些？
A: 死锁解除的主要方法有:

1. 资源剥夺法。挂起某些死锁进程, 并抢占它的资源, 将这些资源分配给其他的死锁进程。 但应防止被挂起的进程长时间得不到资源而处于资源匮乏的状态。
2. 撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。这种方式实现简单, 但付出的代价可能很大, 因为有些进程可能已经接近结束, 一旦被终止, 以后还得从头再来。
3. 进程回退法。让一个或多个死锁进程回退到足以回避死锁的地步, 进程回退时自愿释放资源而非被剥夺。要求系统保持进程的历史信息, 设置还原点。
   补充细节：死锁解除的方法主要有以下几种：

• 资源剥夺法：从一个或多个死锁进程中剥夺一些资源，分配给其他死锁进程。
• 撤销进程法：强行终止一个或多个死锁进程，释放其所持有的资源。
• 进程回退法：让一个或多个死锁进程回退到一个安全状态，释放所持有的资源。