用操作系统课的知识解决自助餐排队问题背景 总结——如何对系统进行优化
用操作系统课的知识解决自助餐排队问题背景 总结——如何对系统进行优化
背景
这是在北京刚刚结束的2016年的第11届ThoughtWorks China AwayDay上发生的一件事：
上午的KeyNote全部结束后，大家都要去吃午餐，午餐是自助式的。我刚进入餐厅，看到了以下场景：
团体自助餐经典场景：排队
进入餐厅后如图所示：
资源和任务都空闲，但是都在等待
这里面有几个现象：
任务队列已满：排队拿盘子的人前后已经形成了一个环，后续任务（新来吃饭的同事）必须等待队列有空位。
任务等待：很多情况下排队的任务不知道队伍前方会有什么样的食物，所以等待遍历所有食物。
资源空闲：很多情况下，因为队列阻塞（没有轮到你不能夹食物），某些食物是没有人夹的。
资源访问时间短：看到食物以及把食物放到自己盘子里的时间远远小于排队等待时间。
资源非互斥：每个夹盛食物的用具至少有两把。
任务饥饿：每个人都拿着空着盘子，排队等待很长时间才能获取到食物。
任务消费资源有限：盘子只能盛装有限的食物。
任务可分享，可互斥：每个人可以选择和他人分享盘中的食物，也可以独占自己的盘中的食物。
总之，这个系统有很大的问题：资源存在空闲，任务存在饥饿。
这是一个典型的批处理系统的情况，你可以把批处理看做一种任务调度算法：特点是所有的任务都在队列里等待被处理，同时存在空闲的资源和等待的任务。
于是为了解决自己的问题，我修改了任务调度算法：给自己加上优先级。
我一是这么做的：
1. 降低自己任务的优先级，等队伍空闲了之后再去拿。
2. 由于带权等待时间较长（我周围的同事已经吃了一半了），我提高了自己的优先级。
3. 由于队伍仍然阻塞。所以我新开了一个线程：绕队列一周，遍历一遍资源占用状况。
4. 根据资源状况，规划好了盘中需要取得食物，避免资源浪费。
5. 提升我自己的优先级：插队。
6. 由于资源占用时长较小（瞅准了夹菜很快的），我对队列里整体的平均等待时间影响较小。
7. 我完成了自己的任务，去和同桌的同事一起享用。
8. 剩下的同事仍在队列中等待。
效果如图所示：
我给自己增加了优先级，我的等待时间缩短了
很多人会批评我插队的不道德，但是从系统的角度考虑，我通过新的调度算法解决了我的等待和资源空闲的问题。如果大家都插队，那么问题就更大了，如果每个任务都优先，还是会退化到等待队列的状况。而且会让剩下的任务等待时间更长。
所以，其实还有更好的调度算法。
理想的调度算法——多线程、依据资源排队和任务资源共享：
1. 每个人先不排队，查看资源的整体情况。
2. 任务互斥的情况：规划自己的任务资源使用情况。你就有可以根据了平均带权等待时间。
3. 任务共享的情况：和同桌的其它同事把所有资源都拿一遍，然后共享。缺点是会产生单个任务资源不足（几个人都喜欢吃一个菜），或者浪费（有些菜没有人吃）。
4. 移除任务等待队列：都不按照顺时针的方向排队。
5. 每个人都是独立的线程，按资源进行排队。根据资源的使用情况选择。
效果如图所示：
理想的最佳方案
这个调度算法有以下几个优势：
1. 物尽其用，没有空闲的资源。
2. 任务随机访问，降低了队伍等待时间。
3. 根据资源状况做好访问规划：规划好准备拿几样菜。
4. 根据资源忙闲程度进行排队和调度：可以先拿排队较少的，缩小任务平均等待时间。
5. 加大了系统吞吐量：因为资源使用繁忙，所以食物消费很快。
唯一的不足就是要改变整体的调度算法，这个代价比较大。
总结——如何对系统进行优化
系统优化的第一要务就是要能识别出系统里的关键资源，当这个资源阻塞后，会对影响整体性能。在这个例子里，等待队列就是关键资源。但它也可以是你团队里的某个人，也可能是CI，也可能是客户的流程，等等。
作为咨询师你所要做的就是：
1. 发现系统关键资源。
2. 根据资源的重要程度排序。
3. 扩展系统的关键资源或减少对关键资源的依赖。