1

2021年的暑假，各地发生的一些事使得很多民间志愿者团体相互呼应，加入到对特定地区的支援行动中，这是问题的背景。

有限资源的分配在非常时期非常考验决策者

某民间志愿者团体接到α、β、γ、δ四个地区对A、B、C三种物资的需求。在此设定，这些物资都是可回收的，使用完成后全数回收到志愿者团体本身。已知这4个地区对3种物资的需求，已经分配给4个地区的物资量，现有3种物资各自的总量，可用的3种物资的总量分别如下表：

问题在于，能否使得物资全部被分配到目标地区，且不会出现死锁（即物资出现地区之间相互抢占或等待）的情况？

计算的方法如下：当送达某个地区的时候，清零物资的需求和已经分配的物资，当物资回收时，可用的物资数量加上已经分配的物资数量。当可用的物资总量少于物资总量且（需求-已经分配）<=可用的物资总量时，循环此操作。

只有当志愿者团体有资源的时候才能把资源送到目标

送达的顺序可以是β地区，γ地区，α地区，δ地区，这时候表格的变化如下：

β地区被分配后

γ地区被分配后

α地区被分配后

δ地区被分配后

如果把δ地区已经分配的A物资从11增加到13，相应地，可用的A物资变成0。如果先分配β地区，物资也和上面一样可以全部分配到目标，这种被称为安全状态。这个问题的目标是任何时候都要保持在安全状态。

如果先分配δ地区，由于没有可用的A物资，为了防止出现死锁的情况，需要中止分配到δ地区的行动以维持安全状态，被称为阻塞。

所以从物资分配的问题可以看出，阻塞的行为只能预料死锁的发生，并不能避免死锁的发生，因为它只能判断当前有没有死锁的可能性。

阻塞是为了防止不同的进程循环等待资源，就像你想得到资源，我也想得到资源，总有人要得不到

还有另外一种方法，标记一个和V向量相等的W向量，然后当找到某个地区还需要任意一种物资的数量都比可用的物资数量少的情况时，把物资送到该地区并还回后，W向量加上已分配的物资的数量，直到全部地区都被送达或找不到还需要任意一种物资的数量都比可用的物资数量少的地区。

本问题对W向量的求解如下：

这种方法也能检测死锁的发生，但它只能判断每一步是否存在死锁，而是否死锁则取决于如何分配。

如果出现死锁的情况，可以用下面的方式恢复。

第一种是发现死锁之后终止所有进程重来，例如分配到δ地区不够用，则重新进行分配。但这样的代价很大，尤其是在时效性很强的行为中。

当没有资源的时候，强行退出可能会造成较大的损失，例如某些地区没有足够的资源分配的话，即使重新配置，也不能保证资源能符合需求

第二种是抢占资源，例如当δ地区已经分配的A物资为13时，因为没有可用的A物资，所以需要抢占至少1单位的A物资。这样的话可以保证某些优先级更高的地区首先得到资源上的满足。

为了避免死锁的发生，可能需要抢占资源，体现在把资源先集中在需求最大的地区

这个问题的原型是银行家算法，志愿者团体借还物资的过程的原型体现在银行对客户的贷款过程。这个算法可以应用于例如阅览室的书籍借阅，以及计算机的进程管理等方面。

这个问题在真实状况下还需要解决物资借用的时限和运输、损耗等问题，不过真实情况下可以通过各种渠道获取更多物资以及初始状态设置更多的可用物资以避免死锁，但人为的囤积资源等问题也需要被考虑。

真实情况下，当资源有限的时候，资源的损耗和等待资源时的插队现象是需要考虑的

2

8位美食评论家来到了某家饭店，希望能品尝美食之都的精湛厨艺。但是这8位美食评论家桌前的摆设却不同寻常：筷子摆在两个美食评论家中间，每双筷子有一支黑筷子，一支白筷子，根据饭店规定，饭店的客人只能使用黑筷子吃饭，白筷子作为公筷夹菜。

为了某种需求，美食评论家们不能做干杯等接触性行为

为了保证美食评论的客观性，所有美食评论家在整个吃饭的时间段内只能做三件事：夹菜、吃饭并在自己的智能设备上写对美食的评价。不过美食评论家们看到黑筷子和白筷子的用法之后，想到如果每个人都拿着自己左边的白筷子夹菜和右边的黑筷子吃饭的话，总有人因没有筷子用夹不到菜，吃不到饭，怎么办？

黑色线代表请求||竞争黑筷子，白色线代表请求||竞争白筷子，下同

这时，思聪正坐在隔壁桌和一些朋友吃饭，看到这样的情况，也在思考解决的方案。

在这样的条件下，再好吃的美味都没有一种防止死锁的方法重要

解决美食评论家问题的理论最好方案，是给所有美食评论家配齐每人一双黑筷子，一双白筷子，可是饭店不能保证有足够多的黑筷子或白筷子使用。这时候就衍生出下面的方法。

思聪思考了一段时间，可用的方法大致有以下几种。

1、初始的时候8位美食评论家分开4个4个地进行夹菜、吃饭并写评论。即1、3、5、7号美食评论家先夹菜，然后1、3、5、7号美食评论家吃饭写评论，2、4、6、8号美食评论家夹菜，之后1、3、5、7号美食评论家再夹菜，2、4、6、8号美食评论家吃饭写评论，以此往复。

2、8位美食评论家只能有其中7位同时请求同一种颜色的筷子。此时，假定每位美食评论家都只请求其左边的白筷子和右边的黑筷子，总有一位美食评论家可以同时拿到两边的白筷子夹菜或黑筷子吃饭。例如1-7号美食评论家都拿起左边的白筷子的时候，2-8号拿起右边的黑筷子；此时1号美食评论家可以同时拿到其右边的白筷子，8号同时拿到其左边的黑筷子。然后1号依次放下左边的白筷子和右边的白筷子，于是2号可以同时拿到两边的白筷子夹菜，且8号拿到左边的白筷子，同时1号拿到两边的黑筷子吃饭。其他同理，以实现滚动吃饭的目的。

3、每一位美食评论家只有在他的左边和右边的同颜色筷子都能使用的时候才能用白筷子夹菜或黑筷子吃饭（允许左边和右边的白筷子都被占用且黑筷子都不被占用的情况下使用黑筷子吃饭，反之同）。例如1号的左右白筷子都是空闲的，2号的左右黑筷子都是空闲的，1号可以用白筷子夹菜，3、5、7号亦然，2号可以用黑筷子吃饭并写评论，4、6、8号亦然。之后1、3、5、7号放下左边的白筷子，然后放下右边的白筷子，使得2、4、6、8号两边的白筷子都不被占用，此时2、4、6、8号拿起白筷子夹菜，1、3、5、7号拿起黑筷子。依此类推，每位美食评论家用完之后先释放左边的筷子再释放右边的筷子，以此实现白筷子夹菜和黑筷子吃饭的交换。

黑筷子和白筷子占用的过程，灰色线表示不占用任何筷子

4、奇数号美食评论家请求左边的白筷子和右边的黑筷子，偶数号美食评论家请求右边的白筷子和左边的黑筷子。

当美食评论家的数量为奇数的时候，号码最大的美食评论家由于独自竞争其左边的白筷子或黑筷子，所以总能拿到两边的白筷子夹菜或黑筷子吃饭。但美食评论家的数量为偶数的时候，只有先竞争到筷子的美食评论家才能拿到两边的白筷子夹菜或黑筷子吃饭。最终可以实现像解法1一样的半数美食评论家用白筷子夹菜，半数美食评论家用黑筷子吃饭写评论的局面。

红色代表竞争白筷子，青色代表竞争黑筷子

思聪发现，当行为竞争有限的资源的时候，不仅会出现循环等待导致死锁的情况，还可能会因为没有资源出现饥饿。所以如果一个行为迟迟不能得到实现它的资源是一件很浪费的事情。

美食致富之路也一样，只有每个制作美食的人都有实现致富的资源才能达到幸福，图片来自青年大学习

就像美食评论家的问题，为了让每个美食评论家都可以夹到菜、吃到饭、写下评论，需要用到适当的算法。对黑筷子和白筷子的占用和竞争，这就是一种体现资源分配如何能够使得所有行为都能实现的智慧。

美食评论家的问题并不只是每个人都能夹菜、吃饭、写评论这么简单，还是新的历史时期如何满足有没有，追求好不好的映射