死锁、银行家算法与哲学家就餐算法
本系列及的的文章基于自学与总结，能保证基础的准确性，但某些抽象性的理解是主观的，欢迎斧正探讨。
🔒死锁
什么是死锁？
在计算机操作系统中，死锁指的是一种资源互斥的情况，其中两个或多个进程（或线程）无限期地等待其他进程持有的资源，而这些进程都在等待彼此释放资源，从而导致所有进程都无法前进。简单来说，死锁是由于不正确的资源管理而导致的系统卡死的情况。
死锁通常发生在多个进程需要互相占用对方拥有的资源时。例如，一个进程可能持有一个资源A并等待另一个进程释放资源B，而另一个进程持有资源B并等待进程释放资源A。在这种情况下，两个进程将互相阻塞，无法继续执行。
举例：
大家都去一台ATM机取钱，大壮带着自己的女儿小美在机器那学习如何操作，后面排了一大堆的人在等待他俩使用完毕这台独占性资源——ATM机。这个就是独占资源互斥导致的死锁。
再次举例：
假设皇帝要派军队出去打仗，但决定临阵换帅，于是将中央的半片虎符交给新统帅前去调兵。新统帅到了兵营，发现旧统帅心生怨怼，拒不交付手里的半片虎符，坚持将在外君令不受——要新统帅的半片虎符交给他才行。这样僵持着直到皇帝本人来调节处理才能发兵。这个属于申请与释放资源顺序安排不当导致的死锁。
总的来说，就是关于系统资源的抢占导致了死锁。
死锁竞争的资源是什么？
系统中的资源一般被分为两类：
- 永久型资源，代表着系统中可供进程重复使用、长期存在的资源，如内存、外部设备、处理器等硬件资源，以及各种数据文件、表格、共享程序代码等软件资源
- 临时性资源，是指由某个进程所产生、只为另一个进程使用一次或短暂时间后便不再使用的资源，如I/O和始终中断信号、同步信号、消息等。
死锁产生的必要条件
我们可以仔细思考一下上面所讲的死锁和死锁产生的原因，再结合下面的概念，可以更方便的理解：
2. 不可剥夺条件（必须进程自愿释放）
3. 请求和保持条件（先申请，申请时继续占用已有资源）
4. 循环等待条件
以上给出了导致死锁的必要条件，那么如何解决死锁呢？
如何解决死锁
主要是两个方向的思路，第一是不让死锁发生，第二是检测死锁是否发生，再加以解决。
下面列出的四种方法对进程的限制由严到宽，并发程度由低到高：
2. 避免死锁（资源分配时防止进入死锁）
3. 检测与解除死锁
4. 忽略死锁（代价太大，我不管啦）
下面我只针对避免死锁做单独的剖析和记录，其他方法放到以后再录入。
🏦银行家算法
什么是银行家算法
银行家算法是最著名的死锁避免算法，是由荷兰学者艾兹格·W·迪科斯彻（牛人，还提出了最短路径算法等）提出。
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
这百度百科描述了个大概，我在下面再引用一下教科书上的四条总结：
2. 顾客可以分期贷款，但贷款的总数不能超过最大需求量。
3. 当银行家现有的资金不能满足顾客尚需的带宽数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款。
4. 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金。
这样讲下来比较通透，更好理解。至于例子，我就不列了，不好画表格。我放两个维基的摘抄在下面：
实现银行家算法需要维护的基本数据结构
让n是系统中的进程数，并且m是资源类型的数目。然后我们需要以下数据结构：
- 可用：长度为 m 的向量表示每种类型的可用资源数。如果可用[j] = k，则有 k 个资源类型 R j 的实例可用。
- 最大：一个n*m 矩阵定义了每个过程的最大需求。如果 Max[i，j] = k，则 Pi 最多可以请求资源类型 R j 的 k 个实例。
- 分配：一个n*m 矩阵定义当前分配给每个进程的每种类型的资源数。如果分配 [i，j] = k，则进程 Pi 当前分配了 k 个资源类型 R j 的实例。
- 需要：一个n*m 矩阵表示每个进程的剩余资源需求。如果 Need[i，j] = k，则 P i 可能需要 k 个资源类型 R j 的实例来完成任务。
注意：需要 [i，j] = 最大值 [i，j] - 分配 [i，j]。 n=m-a。
总结
总的来说，银行家算法通过动态地检测系统中资源分配情况和进程对资源的需求情况，来决定如何分配资源，再能确保系统处于安全状态时才把资源分配给申请这，从而避免系统出现死锁。
由于银行家算法是在系统运行期间实施的，要花费相当多的时间，该算法每一类资源需要m*n²次操作，其中n是系统中的进程数，并且m是资源类型的数目。银行家算法要求每类资源的数量在运行过程中是固定不变的，而且必须事先知道资源的最大需求量，这在实际系统中难以做到（嘿嘿，屠龙之术）。
🍜哲学家就餐问题
什么是哲学家就餐问题
哲学家就餐问题（Dining Philosophers Problem）是一个经典的并发编程问题，描述的是五位哲学家围坐在圆桌前，他们需要通过使用一只叉子才能吃饭，但是只有左右两边的哲学家同时拿起他们左右两边的叉子才能进餐。
假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。餐桌上有五碗意大利面，每位哲学家之间各有一只餐叉。因为用一只餐叉很难吃到意大利面，所以假设哲学家必须用两只餐叉吃东西。他们只能使用自己左右手边的那两只餐叉。哲学家就餐问题有时也用米饭和五根筷子而不是意大利面和餐叉来描述，因为吃米饭必须用两根筷子。
如何设计一套规则，使得在哲学家们在完全不交谈，也就是无法知道其他人可能在什么时候要吃饭或者思考的情况下，可以在这两种状态下永远交替下去？
方案有很多，我挑其中两条拿出来说说，其他的要么不实用要么被证伪了。
服务生解法
这个最容易理解，就是引入一个餐厅服务生，来掌握餐叉的使用权，让他来批准哲学家是否可以开始用餐。这样可以保证每次有两只餐叉空出来的时候，总有一个哲学家可以开始吃饭。很简单的方案，就是哲学家们有点可怜。
Chandy/Misra解法
1984年由曼尼·钱迪和米斯拉提出的。这个比较直白，我就不自己总结了，贴一下摘抄：
- 对每一对竞争一个资源的哲学家，新拿一个餐叉，给编号较低的哲学家。每只餐叉都是“干净的”或者“脏的”。最初，所有的餐叉都是脏的。
- 当一位哲学家要使用资源（也就是要吃东西）时，他必须从与他竞争的邻居那里得到。对每只他当前没有的餐叉，他都发送一个请求。
- 当拥有餐叉的哲学家收到请求时，如果餐叉是干净的，那么他继续留着，否则就擦干净并交出餐叉。
- 当某个哲学家吃东西后，他的餐叉就变脏了。如果另一个哲学家之前请求过其中的餐叉，那他就擦干净并交出餐叉。
这个解法挺好的，就是有一个问题，有点不太卫生😂
END
到这里这篇文章就结束了，有很多部分我是直接引用或者给的链接，因为这种纯理论的东西我自己总结的肯定不如前辈大佬们的准确到位。能提供一些自己的想法就很满足了。谢谢大家的观看！