算法优化人生之 —— 调度算法

量子计算9 · 发表于 2021-7-10 13:48

电脑就是人脑的复刻，这是我大学时学《操作系统》这门课时的感受。最近在复习调度算法，又重拾了这种感觉，他俩太像了，电脑就是模仿人脑的机制制造出来的，但现在我们可以反过来从它身上学习一些优秀的算法，反哺自身（可能早已遗忘的）做事方法。
什么是调度算法

调度，你就理解成安排吧，大家应该都懂，懂的同学，这一节就直接跳过吧。

我来举个常见的栗子——电梯。据说每个程序员坐电梯的时候都会想电梯调度算法[1]，我也不例外……
最简单的调度方法是什么呢？当然是“谁先按的谁先坐”，这个在计算机里叫先来先服务(FCFS-First Come First Serve)算法，不管你是在几楼按的电梯，电梯都是按顺序去接人、送人。你可以想象一下，一个人在 1 楼按了去 20 楼，然后第 2 个人在 2 楼按了去 5 楼，第 3 个人在 21 楼按了要去 1 楼。这时候电梯它首先会跑去 1 楼把第 1 个人送到 20 楼，再跑去 2 楼把第 2 个人送到 5 楼，最后再跑去 21 楼把第 3 个人送到 1楼。
是不是很蠢？它明明可以在送完第 1 个人之后去 21 楼接上第 3 个人，把他送到 1 楼后再去 2 楼接第 2 个人，这一下子能省多少电费啊！
所以有了第二种调度算法：最短寻找楼层时间优先(SSTF-Shortest Seek Time First) 算法，用人话说就是优先停到最近的楼层。这样还是刚才那个例子就会如我们所愿，在电梯送第 1 个人到 20 楼之后，就会找到最近的需要停的楼层 21 楼。但是这个算法有一个问题，比如有第 4 个人又在 20 楼按了电梯要下去，但第 5 个人是在 5 楼按的要下去，第 6 个人是在 1 楼按的……以此类推总之都是在低楼层。由于它们第楼层距离都比去 20 楼近，所以第 4 个人好惨，等到天荒地老也等不来电梯……
还有一种调度算法是扫描算法（SCAN），就是电梯不停的从最底层到最高层，再从最高层到最底层，遇到有需要停的地方停就好了，是不是很像我们现在见到的电梯第样子了？还存在什么问题吗？其实还有个小问题，比如高楼层很少人去的话，那么是不是就没必要非要扫描到最高层。所以查找算法（LOOK）就是对它的改进版，当发现当前运行方向之后没有需要停的楼层了，那么就直接改变方向。
其实刚才说的还只是一个电梯的调度，假如这个大楼里每层有 6 部电梯呢，如何最大程度的利用电梯？假如这个大楼 3 楼和 10 楼是最频繁使用电梯的楼层，你有什么办法对特定楼层优化呢？再假如 12 点和 18 点是吃饭下班高峰期，要怎么调度才能最大程度节省人们等电梯的时间呢？……好了，你可以坐电梯的时候想想。
总之现在你对调度应该是理解了。
调度算法和我们有什么关系

我们现在每个人都很忙，每天面对的信息量、要处理的事务都超级多，如何更好地分配任务、管理进度，这都是对我们时间的调度，如何切分目标、规划未来，这些是对我们人生的调度。按理来说电脑是模仿人脑发明的，但我这篇文章却用电脑的机制往人脑上套，有点本末倒置的意思，:) 但是没办法，谁让我只学过计算机科学，没学过脑科学。
接下来我会结合操作系统的调度算法，举的都是现实生活中做事的例子，来看看我们有什么可以借鉴的地方，每个算法都是层层递进的。
操作系统的调度算法

1. 先来先服务调度算法（FCFS）

最简单的算法，刚才我们介绍电梯算法的时候已经说过了。现在很多人都用 To-Do 清单来管理自己的任务，老板每交代你一个新的任务，你就把它写到清单的最下面，然后你按照从上到下的顺序去一件一件完成这些事，这就是 FCFS 算法。你应该明显能感觉到这里面的问题，我们做事是要分轻重缓急的，而且很多事你不知道完成它到底需要多久，万一一直没完成，你单子里下面的事是不是也跟着都完成不了，这显然是不行的，明天估计就被开除了。

所以来看看第二种算法：
2. 短作业优先调度算法（SJF）

老板给你安排事情以后，你肯定要预估一下每件事的完成时间，哪件事用的时间最短就最先做哪件事，这就是 SJF 算法。这里又有明显的问题了，万一这件事用时很长但又很重要，那你可能永远都没机会去完成，好了别说了，明天你又被开除了……
为啥这些算法这么傻呢？别急，这只是开胃菜，毕竟设计操作系统的人一开始也没想的那么完备。
3. 优先权调度算法（FPF）

很好理解，就是哪件事的优先级最高先去做哪件事。这下你学会了，老板给你安排任务之后，你不仅预估了时间，还预估了一下这件事的重要程度，列了个优先级。按找优先级来一件件完成，这样这下总没错了吧。
然鹅，又有问题了，你本来在做用户调研，结果老板明天要去开会让你今晚把参会演讲的 PPT 帮忙做一下（我不是黑老板们不亲自做 PPT 哈），显然这个 PPT 的优先级更高，但是呢调研刚做了一小半也很重要，这时候就要分两种情况了：如果你就一根筋要先做完一件事才能再做下一件事，那么你就得今天把用户调研先赶完，然后加班去做 PPT，很惨。第二种情况，你思路灵活，肯定先给老板做 PPT 要紧啊，三下五除二把 PPT 做完了，结果老板一看，“不行，这里得改”，结果你改了一天，加班……很惨。本来想着说第二天把调研做完，没想到老板又让你去一同参会，显然这件事情的优先级又比调研高，那你又思路灵活的去参会了，没想到回来当天老板问你要调研报告，你拿不出来，好了，你被开除了，again！

很惨，经过第三次被开除你明白：优先权调度算法的问题就在于你要做的那件事很有可能一直被优先级更高的事情抢占。
4. 高响应比优先调度算法（HRRN）

这个算法可以说是采前 3 种之长，兼顾了任务的优先级，也不会让任务有一直拖着没完成的情况。具体来说，除了任务本身的优先级之外，还通过“响应比”来计算任务的优先级，不要怕这个名词，可以把计算响应比的公式通俗化一下：
响应比 =（已经拖了多久 + deadline）/ deadline可以看出，你拖的越久，这个任务的优先级越高，很有可能就超过你当前任务的优先级。还是刚才那个栗子，你发现用户调研报告拖了 3 天了，优先级已经比参会更重要，所以你参会当天就抽时间挤时间去做报告，晚上免不了加班，很惨，但总算没被开除。
5. 时间片轮转调度算法（RR）

经过刚才的 4 个算法，你已经对任务如何排序驾轻就熟，很快升职加薪迎娶白富美当上了高管，这时就又有问题了……假如你相同优先级的事有很多呢？毕竟大老板了，手底下 10 个团队，你肯定都要兼顾，任务齐头并进的时候，你怎么办？时间片轮转法你可以试一下。
一周 5 天工作日，每天按上下午分的话，你正好有 10 整块的时间。你的 To-Do list 里列了 10 项任务分别是跟每个团队交涉，具体交涉需要的时长你没法预估，所以你就每个半天，集中处理一个团队的事情，这就是时间片轮转算法，轮转的是你清单里的任务，“时间片”是一个半天，每个时间片结束后如果任务没有完成，就继续把它放到清单的末尾，下次去轮转。这样就保证了每个团队每周都能有一个半天去协调安排工作（尽管可能存在没有交涉完的情况，但你保证了雨露均沾）。
例子里我图方便，时间片设成了半天，你当然可以设置更细粒度的。比如，1980 年代由 Francesco Cirillo 提出的番茄工作法[2]可以用作时间片轮转的形式。它的理念是把你的时间按每 30 分钟分割，每 30 分钟里，25 分钟集中用于工作，5 分钟用于休息。感兴趣的可以看《番茄工作法图解》[3]这本书，比较玄学说什么 25 分钟时候大脑结构，更利于处理中断等等，我这里就不过多介绍了，早些年我也尝试过，感觉没啥效果就不用了，25 分钟集中工作不如调自己效率高的时候猛工作一下午。
6. 多级反馈队列调度算法（MLFQ）

这个算法就厉害了，集上面所以算法优点，还避免了它们的问题。具体是这样的，它把任务分成多个清单，而不是都统统扔进一个单子里（队列理解成任务清单就行）。这里为了好说，我们采用众所周知的艾森豪威尔法则[4]：

设置四个任务清单，按照优先级分别是：重要紧急的，重要不紧急的，不重要紧急的，不重要不紧急的。
这里有几个点：

是不是第三点你很疑惑，万一放到最后一个清单，你事情岂不是一直完不成？你别忘了，优先级越低的清单时间片越长，你有更多的时间去集中攻克一个任务。
基本上 MLFQ 算法是兼顾各种因素的较好的算法了，保证了短任务很快完成、重要任务优先完成、拖延的任务能集中精力完成，是不是很完美。不知道你有没有看过《无压工作的艺术》[5]这本书，这个算法和书中的内容几乎契合。这本书中说 5 分钟之内能做完的事，就赶紧做完，不让它占用大脑的“内存”，做完就可以完全置诸脑后。如果需要超过 5 分钟来完成，就把它列在清单里，之后抽专门的时间再统一分配。等等理念，我觉得还是很值得借鉴的。
尾

调度算法有很多，这篇文章粗浅的介绍了一些操作系统常用的调度算法，还有很多其他方面的调度算法有待大家去探索（比如负载均衡之类的，就是你一个人实在忙不过来了怎么办）。最后的“多级反馈调度”算法目测是最符合我们人处理事情思维的，但还是要结合自己的习惯，变法很多很灵活，这里只是做个简介，具体的理解全看你了，当然只要你觉得有趣就好。另外，文章里面的例子与现实严重不符，迎娶白富美靠的是颜值，升职加薪靠的是运气，所以，提升颜值且积攒人品吧 :) 抖个机灵。
其实很多算法的思想，都可以运用在生活中，无论大事小事，比如贪心算法，分治法等，敬请期待算法优化人生系列的下一篇。
References

[1] 电梯调度算法: https://www.cnblogs.com/jianyungsun/archive/2011/03/16/1986439.html
[2] 番茄工作法: https://zh.wikipedia.org/zh-hans/番茄工作法
[3] 《番茄工作法图解》: https://book.douban.com/subject/5916234/
[4] 艾森豪威尔法则: https://baike.baidu.com/item/艾森豪威尔法则/8409768
[5] 《无压工作的艺术》: https://book.douban.com/subject/4849382/

LiteralliJeff · 发表于 2021-7-10 13:58

作者写得很好，感觉将算法用于人生还是用处，对我们生活中的决策和问题处理都有处理意义。现在正在用日事清，很喜欢它的时间四象限

RedZero9 · 发表于 2021-7-10 13:58

请问，什么是分组队列调度算法哒？

LiteralliJeff · 发表于 2021-7-10 14:00

是的，真的写的挺好的

		自动登录	找回密码
密码			立即注册

算法优化人生之 —— 调度算法

本帖子中包含更多资源