用操作系统课的知识解决自助餐排队问题背景 总结——如何对系统进行优化

背景

这是在北京刚刚结束的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. 扩展系统的关键资源或减少对关键资源的依赖。

最后,为什么是操作系统课?——因为操作系统就是用来解决资源有效分配问题的啊!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏互联网技术栈

读《大型网站技术架构》

《大型网站技术架构》是自己接触的第一本架构知识的书籍,还是在14年时买的实体书,前后读了几遍,颇有所得,后来实体书被朋友借走再没归还,也就没再翻过。

13220
来自专栏分享达人秀

Android开发环境概述

工欲善其事,必先利其器。Android开发人员在自己的计算机上编写和测试应用程序,然后将其部署到实际的设备上,那首先必不可少的就是开发环境的搭建。 ...

33750
来自专栏开源项目

走过微软20年,埋头并发编程15年,如何减少代码的认知负荷?| 码云周刊

每周为您推送最有价值的开源技术内参! 技术干货 从Visual Studio看微软20年技术变迁 spring cloud netflix 微服务使用实例 20...

582130
来自专栏服务端技术杂谈

[硅谷热门公司技术巡礼]:UBER数据大迁徙

想象一下如果你必须在几个星期内迁移数以亿计的数据和100多个服务项目,同时还要保持UBER被几百万的乘客正常使用,这是多么艰巨的任务啊!而以下这个故事就是关于数...

30270
来自专栏C语言及其他语言

手游后台PVP系统网络同步方案总结

来源:游迅网 发布者:wuyu 概述   PVP系统俨然成为现在新手游的上线标配,手游Pvp系统体验是否优秀,很大程度上决定了游戏的品质。从最近半年上线的新...

53250
来自专栏企鹅号快讯

Go 语言如何去解决 Web 开发人员面临的众多问题?

坦白的说,我的团队非常厌恶我对 Go 语言传道的方式,每当我们团队的代码库出现问题时,他们希望我用一种更委婉的方式提出。 我学会的第一门编程语言是 PHP,这是...

346100
来自专栏Java架构师学习

数据库高可用实战案例:架构优化背景前期调研详细调研测试过程实施过程细节问题处理

24660
来自专栏嵌入式程序猿

我怼了硬件工程师,让你不按datasheet设计

最近有个项目是使用NXP的KEAZ64芯片,基于cortex M0+内核。带有mscan模块,mscan是NXP的8位机和低端32位上用的CAN模块外设,和我们...

40070
来自专栏沃趣科技

备份重于一切:远离“Gitlab删库事件”,QBackup是你的最佳选择!

作者简介:孙朝阳 沃趣科技高级产品经理。 案发现场: Gitlab删库事件回顾 Gitlab是大家很熟悉的开源Git代码托管工具,国内公司大多使用社区版自行搭...

38680
来自专栏云计算D1net

谨记四点选择适合云存储

云存储已经成为我们现代生活中手机的一个重要的组成部分。如谷歌Drive,Dropbox,OneDrive,iCloud等,都在争先恐后的抢夺用户将重要信息存储在...

411130

扫码关注云+社区

领取腾讯云代金券