银行家算法

发表于 2024/04/15 更新于 2024/04/15

作者 Moear

19 分钟阅读

前言

银行家算法不是万能的,在现实生活中,很多程序并不知道自己要占用多少资源(贷款多少钱),和有多少的资源额度上限(信用额度)

死锁

死锁是什么

死锁是指在计算机操作系统中，两个或多个进程无限期地等待系统资源，而这些资源又被等待的进程所占有。这导致了这些进程都无法向前执行。以下是一些常见的死锁条件：

1 互斥条件：一个资源每次只能被一个进程使用。

2 持有等待：一个进程因请求资源而阻塞时，对已获得的资源保持不放。

3 不能抢占：进程已获得的资源，在未使用完之前，不能强行剥夺。

4 环路等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。这些条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。

死锁有哪些场景

数据库系统：当两个或多个事务试图访问同一资源时，可能会发生死锁。例如，事务A锁定了资源1并试图访问资源2，而事务B锁定了资源2并试图访问资源1。这就形成了一个循环等待，导致死锁。

多线程编程：在多线程环境中，如果两个或多个线程互相等待对方释放资源，也可能发生死锁。例如，线程A锁定了对象1并等待对象2，而线程B锁定了对象2并等待对象1。

操作系统：在操作系统中，进程可能需要多种资源才能执行。如果一个进程持有一种资源并请求另一种资源，而这种资源被另一个进程持有，那么就可能发生死锁。

哲学家进餐问题是一个经典的并发问题，用于描述死锁的情况。问题描述如下：

假设有五位哲学家围坐在圆桌旁，进行思考和进餐。每位哲学家面前都有一碗面条，而每两位哲学家之间有一只筷子。哲学家只有在拿到左右两只筷子的情况下才能吃面，吃完后再把筷子放下，继续思考。

这个问题的死锁情况是：当每位哲学家都拿起了左手边的筷子，准备拿起右手边的筷子时，他们就会陷入死锁。因为每位哲学家都在等待右手边的筷子，而这些筷子都已经被其他哲学家拿起，所以没有人能够进餐。

这个问题展示了死锁的四个必要条件：互斥条件（每只筷子一次只能被一个哲学家使用），请求与保持条件（每位哲学家都保持着一只筷子并请求另一只），不剥夺条件（已经拿起的筷子不能被其他哲学家强行拿走），以及循环等待条件（每位哲学家都在等待下一位哲学家放下他的筷子）。

死锁的危害

资源浪费：当进程陷入死锁时，它们可能会占用大量的系统资源，如CPU、内存和磁盘空间，但却无法执行任何有用的工作。这就造成了资源的浪费。

系统性能下降：死锁可能会导致系统的性能大幅下降。因为系统需要花费大量的时间和资源来处理和避免死锁，而这些时间和资源本可以用于执行其他有用的任务。

系统不可用：在严重的情况下，死锁可能会导致整个系统变得不可用。例如，如果操作系统的关键进程陷入死锁，那么整个系统可能就无法正常运行。

数据丢失或损坏：在数据库系统中，死锁可能会导致数据丢失或损坏。因为当事务陷入死锁时，数据库可能需要回滚事务以解决死锁，这可能会导致数据丢失。此外，如果数据库在处理死锁时出现错误，那么数据可能会被损坏。

ppt问题解决: 问题一：代码中死锁会发生吗？

答：会发生死锁。原因分析：代码中展示了两个线程 A 和 B 对资源 x 和 y 的加锁操作：线程 A 先锁住 x，再锁住 y。线程 B 先锁住 y，再锁住 x。如果线程 A 获得了 x 的锁，而线程 B 获得了 y 的锁，那么它们都会尝试获取对方持有的锁，从而陷入互相等待的死锁状态。

问题二：上述代码一定会发生死锁吗？答：不一定。原因分析：虽然代码中存在死锁的风险，但死锁的发生还需要满足特定的时序条件。如果线程 A 在获得 x 的锁之后，能够在线程 B 获得 y 的锁之前，成功获取 y 的锁，那么死锁就不会发生。同样，如果线程 B 在获得 y 的锁之后，能够在线程 A 获得 x 的锁之前，成功获取 x 的锁，那么死锁也不会发生。

处理死锁的基本方法

不予理睬: 忽略问题的存在假装没有问题此种策略在如下情况下是合理的死锁出现的概率很低预防死锁的代价很大 UNIX 和Windows都采取这种方法方便和正确性之间的一种折中

静态预防: 消除死锁发生的4个必要条件中的任何一个。消除四个必要条件中的一个消除资源独占条件消除持有和等待条件消除非抢占条件消除环路等待条件

一些设备可以被共享仅打印机daemon使用打印资源这样消除了打印机的死锁不是所有的设备都可以共享原则: 不是绝对必须的时候避免分配资源尽可能少的进程获得资源

进程在启动之前请求所有的资源不要去等待所需的资源消除持有和等待

阶段 1a. acquire all resources
阶段1b. while (not done) {
     work
}
阶段2. release all resources

此方法的特点: A. 等待所有你需要的资源都被释放然后一次都获取它们 B. 如果获取资源失败释放所有已经拥有的资源缺点：一次获取所有的资源，造成资源浪费开始运行的时候可能不知道所有需要的资源

消除非抢占条件允许抢占! 可以抢占 CPU ：通过将信息保存到进程控制表，之后再恢复它。可以抢占内存通过把内存倒出到磁盘上，之后再把它装回局限性：有些资源不可以被抢占，比如锁、打印机
消除环路等待条件环路等待的原因是由于进程请求资源的顺序是随机的指定需要资源的次序激光照排机扫描仪绘图仪打印机

动态避免: 仔细的资源分配

死锁检测与解除 让死锁出现然后采取措施去纠正

如果想检测死锁，自然得知道是否已经死锁了。所以死锁的修复的第一件事情就是死锁检测。死锁的原因是资源竞争，只要我们对资源的拥有和资源的请求都清楚，问题就解决了。

死锁的恢复 一旦检测到死锁如何修复?

抢占将某个进程所占的资源强行拿走取决于资源的性质
上翻定期检查进程上翻到一个安全的状态如果发现死锁重启进程
杀死进程中断进程的最简单方法杀死死锁循环中的一个进程其他进程获得它的资源选择可以重新开始运行的进程

死锁的动态避免

实现原理

贪心!!!

算法思想：

Dijkstra在1965年提出了银行家算法，源于银行家发放贷款时采取的控制方法,类似于一开始就预留所有的资源,但是更加高效实现动态避免死锁

事先声明所需的最大资源,但实际上并不获得资源,当之后进程要求资源时

银行家算法的策略:

安全状态下满足要求
如果处于不安全状态则阻塞进程

将系统中的资源看作是银行的资金，进程看作是客户。每个客户需要向银行贷款（申请资源），银行需要评估客户的信用度（安全性），确保贷款后不会发生资金无法收回的情况（死锁）。

数据结构

数据结构：可利用资源向量 Available：长度为 m 的向量，表示每种资源的可用数量。

最大需求矩阵 Max：n x m 的矩阵，Max[i,j] 表示进程 i 对资源 j 的最大需求量。

分配矩阵 Allocation：n x m 的矩阵，Allocation[i,j] 表示进程 i 当前已分配到的资源 j 的数量。

需求矩阵 Need：n x m 的矩阵，Need[i,j] = Max[i,j] - Allocation[i,j]，表示进程 i 还需要的资源 j 的数量。

算法步骤

检查进程提出的资源请求是否超过其最大需求和系统可用资源。假设分配资源给进程，更新数据结构。使用安全性算法检查系统是否处于安全状态。如果安全，则正式分配资源；否则，拒绝请求。

安全性算法

安全状态：

指系统能够找到一个安全序列，使得所有进程都能按顺序获得所需资源并顺利完成。

安全序列：

指一个进程执行的顺序，使得每个进程都能获得所需资源并完成。

算法步骤：

设置工作向量 Work = Available，表示系统当前可分配的资源。找到一个进程 i，满足 Finish[i] = false 且 Need[i,j] <= Work[j]。假设分配资源给进程 i，更新 Work = Work + Allocation[i]。将进程 i 标记为完成 Finish[i] = true。重复步骤 2-4，直到所有进程都完成或找不到满足条件的进程。

结果判定：

如果所有进程都能完成，则系统处于安全状态，否则处于不安全状态。