您的位置:首页 > 科技观察 > 科技资讯 > 正文

Reading Club | 无处不在的调度算法:如何科学地管理自己的时间?

2018-07-09 21:28:54   原文来源:中国财经观察报

大数据文摘出品

作者:Andy

主播:段天霖

《生活中的算法 (Algorithms to live by)》:调度算法

新的一周开始了!有效率的一周应该始于一份安排得当的计划表。

但安排日程不是件容易的事情,有些任务得在其他任务后进行(比如说洗完衣服后,才能晾衣服);有些有准确的截止日期,而有些却没有,还有些呢,介于两者之间;有些紧急,但不重要;有些重要,但又不紧急...

面对这一堆乱七八糟的任务,到底该如何安排效率最高?这涉及到计算机科学中非常常见的调度 (Scheduling) 算法。

本周,我们来聊聊【调度】这个或大或小的话题,以及如何利用它来进行科学时间管理。

点击收听由来自杜克大学美女主播段天霖与大家分享:如何科学地管理自己的时间。

听了主播的分享,你是否对调度算法有了更深刻的影响,在留言区留你的心得吧,文摘菌会选出获赞数最高的两位同学,免费邮寄送出《算法之美》这本书哟~~~ 我们日常都会遇到时间管理问题,去做什么,什么时候做,以及什么顺序做?

我们总会想着找到一个最好的方法来进行时间管理,市面上也有无数的书告诉我们该怎么办,但他们却又互不相同,甚至互相矛盾。比如说《搞定:无压工作的艺术》里就推崇一种把任何想到的能在两分钟以内完成的工作,迅速搞定的做法;而与此相对,在《吃掉那只青蛙》里面,却又倡导先从困难的事开始,然后到简单事...

似乎每位作者都有着自己的一套理论,那到底该听谁的呢?

那不妨借鉴一下计算机科学中的调度 (Scheduling) 算法,来进行科学时间管理。

调度算法:起源

虽然,时间管理这个概念可能与时间本身一样古老,但说到调度算法科学,可能得追溯到19世纪末了。Frederick Taylor 在拒绝了哈佛大学的录取后,成了一名光荣的机械师学徒,之后一番打拼,从学徒升到了总工程师。期间,他越来越坚定一个想法,那就是,很多机器的时间没有得到最大程度的利用,于是他就提出了一个新的叫作“

科学管理”的学科。

于是 Taylor 建立了计划办公室,房间中一块大板子上列着店内所有机器,以及正在进行的工作和正在等待的工作。之后他的同事 Henry Gantt 在此基础上进一步提出了现在大家熟悉的甘特图,如今被广泛应用在各个大公司的项目管理中,比如亚马逊和 SpaceX。

然而他们只是提出概念还有视觉化,却没解决怎么调度这个根本问题。而这还得等到几十年后 RAND 公司的数学家 Selmer Johnson 来解决了。

Johnson 碰上的是书本装订问题,或者说洗衣服问题。洗衣服分两步,洗和烘干。假设你有几篮子衣物(糙汉子表示只有一个篮子),有的比较脏得长时间洗,烘干时间正常;还有的衣物多得长时间烘干,洗倒不用太久。于是 Johnson 就问,到底怎样的顺序来洗衣服最好呢。

答案很简单,先找出这些篮子里洗或烘干所需时间最短步骤,如果是洗就放最前面,如果是烘干就放最后面,不断重复这个步骤就能获得最优顺序。

因为洗衣过程中,必然有些时间只在洗或只在干,而不是同时进行。为了避免这种浪费,只要使它俩最小就好。于是这就是调度算法中第一个算法:

从最好洗的开始,以最好干的结束。

此外,Johnson 还揭示了两点:

调度是可以用算法形式表现

最优的调度方案是存在的

于是这就为调度延伸出了各种问题,比如说一个有各种各样机器的虚拟工厂,它的最优调度策略是什么。

但今天,我们不谈这些复杂问题。只谈一台机器情况,因为我们最关心的调度问题也就只有一台机器——我们自己。

截止日期是第一生产力

然而,当挽起衣袖准备开始解决单机器调度问题时,却突然发现好像有点不对。因为一台机器一次只能做一件事,那无论怎样的顺序来做花的时间都一样,还需要什么调度。

但是,慢着,在现实生活中却又是需要考虑做事顺序的不是吗?

那是哪儿出问题了呢,这里就要说到调度中最重要的概念:

度量指标 (metric),明确你的目标。也就是你得对不同方案好坏设置一个度量标准,是越快越好,还是先干重要的好。这也是计算机科学里的一个重要原则:在计划前,先设定一个评判标准(这也是机器学习中evaluation的重要性)。

因此即使同一个问题,如果评判标准不同,那最优策略也就不同。

比如说我们希望尽量不拖延,也就是超过截止日期的时间最短。那就可以使用称为

最早完成日期 (Earliest Due Date)的最佳策略。只看截止日期,先做截止日期最近的,很简单。

或许都不用这里说,你早就已经会用这个策略了。但现实中不光拖延时间,还会有很多其他因素。比如你买了很多新鲜食物,如果把品尝日期当做截止日期,应用上述策略的话,确实能最小化你食物的过期时间,但就不保证味道了。

于是改变一下测量标准,最小化会过期食物的数量。于是就得到摩尔算法 (Moore’s Algorithm)。它最初也是先按过期日期先后来吃,但是一旦看到之后的事物可能会在吃之前过期。那么立刻停下来,把最大的食物(需要最长时间吃)丢掉。这样就能尽量减少过期食物数量了。

搞定任务

有时候我们关心的可能不是截止日期,而是越快越多的搞定手头事情。而此时的最优算法又成了最短处理时间(Shortest processing Time) 算法,即先完成能最快完成的任务。

这就类似《搞定:无压工作的艺术》中的策略了。先把能快速解决的事先解决,也能减少心理负担,使得集中精力于困难的事。

但在现实中,并不是说越快越多完成任务就越好。特别是事有轻重,有些事要比另一些事重要些。那么我们可以对最短处理时间算法进行少许修改,不同的任务有各自权重,利用权重与所需时间比得到“单位时间重要度”,之后只需优先执行重要度高的任务即可。这个算法可以称为加权最短处理时间策略,非常实用。

有意思的是,当观察动物觅食时,也会观察到类似策略,它们会倾向于寻找“单位时间更多能量”的食物。

认清问题

从上面的两个例子可以清晰看出,虽然针对各个标准都能给出最优解法,但选择哪个标准却是在于我们自己。

这也提供了看待拖延症(时间管理的死敌)的另一个视角。一般认为拖延症是一种坏习惯和行为,但会不会实际上拖延症只是用了匹配错了最优策略和度量方法呢。

通常认为拖延症是懒或者逃避,但其实对于一些勤奋想快点做完事情的人也非常容易出现。比如2014年的一项研究就发现,有时候人们为了尽快完成任务,结果却花了更多时间和精力,也就是欲速则不达。

那么他们采用了错的策略吗,不,他们只是把一个好策略用在了错误的标准上。因为他们可能用的是最短处理时间方法, 但是实际上应该进行衡量的标准并不是最快最多完成任务。

这就是成也标准败也标准。比如说现在的智能手机,会在应用图标的右上角标上未读信息,不管信息的重要性都只计数一,这导致我们不能分清信息的重要性,而会浪费很多时间去检查不重要信息。只因为我们是以尽快完成尽可能多的任务为策略。

而实际上应该做的可能应该是,先把重要的事情做完。这听起来是解决拖延症的可靠方法,但是对于NASA的人来说确实在最戏剧性地情况下意识到这个问题:火星的表面,而且是众目睽睽下。

优先级倒置和优先限制

1997年夏天,当人们兴奋地将价值一亿五千万美元的探路者号送上火星,却发现它居然出现了拖延症。寻路者号对于优先度最高的任务不闻不问,却把时间都花在那些中等优先度的任务上。

大名鼎鼎的 JpL(喷气推进实验室)小组爆肝数日,最终发现了元凶,那就是调度中的大敌人:优先级倒置 (priority inversion)。具体是这样的,系统先运行一个低优先级任务占用一些系统资源,然后根据计时器中途中断任务,调用调度程序。

这时调度程序想运行高优先级的任务,但因为要用的部分资源被低优先级任务占着,所以只能退而运行中优先级不使用相同资源的任务,或是这个占用着资源的低优先级任务。因为这个原因,往往有些最高优先级的任务被丢在一旁长一段时间不执行。

JpL 一旦发现问题就知道怎么解决了,写了个代码发送到火星。这个解决方法便是优先级继承,方法很简单:一旦发现低优先级任务占用了高优先级任务的资源,便立刻将其优先级升为与被占用任务相同优先级,尽快执行完。

生活中也会遇到很多优先级倒置的问题,可以说它也是拖延症的罪魁祸首之一。比如我最近的例子,需要交学费,非常紧急(不按时交开除学籍!),然而银行在山下,下山得骑车。借车这事,在我心里优先级又不高,结果便一直没借车,去忙些其他事情了。

直到最近学校发来最后通牒:“快交学费!” 可以去会计科,于是便不用下山了,也就不用借自行车,也就没有低优先任务阻碍交学费这个紧急任务了,于是我也就没有被开除了(这才是重点)。

事实上,下次碰到这样这样的事情,正确做法是将借自行车升级为交学费一样紧急的事情。

以上讲的都涉及到优先限制,也就是有些事只能在某些事之后完成。

撞上墙了! Eugene Lawler 可以说是20世纪研究优先限制最杰出的科学家,他几乎花了一生时间来思考怎么才能更有效地完成一系列接连任务。因为当一个普通调度问题加入优先限制后,可能会变得很不一样。

比如说最早完成日期,如果加入优先限制,就会发现原来策略行不通了,因为有些任务即使截止日期早,但却得在另一件任务之后做。而 Lawler 证明只需要反过来从后往前就能很好解决,也就是先找没有未完成任务中没有其他任务依赖的任务,找出其中截止日期最晚的,放在调度表最后,然后不断重复这个操作就行了。

此外,他还发现了很多很有意思的其他问题。比如说最短处理时间,当加入优先限制后,似乎还是一个很基础的问题,但事实上却没有一个有效解决它的方法。不光是 Lawler 没想出来,其他研究人员也都没想出来。

而且不光最短处理时间问题, 情况远远比这更糟。那就是, Lawler 发现有一系列类似问题,都不能得到有效解决,于是调度理论也就撞上墙了。

不过这也激起了像 Lawler 这样的顶尖研究人员的雄心,去探索调度问题中到底哪些是无法被解决的,哪些又能被解决的。也就是说对整个调度理论,进行一次大勘察,而这个大勘察现在都还在继续着。

最近研究显示,调度问题中有7%的问题现在尚未理解。

而即使是剩下93%理解的问题,情况也不容乐观,其中只有9%是可以被有效解决的,而剩下84%都被证明无法被解决。也就是说事实上对于大多数调度问题,确实也没有最佳方法。

所以当我们对管理时间感到压力山大时,也不用太自责,或许它本来就太难了。然而,这里提到的一些算法还是可以作为你处理这些难问题的起点,即使不是最优方法,但至少有个比较好的方法可以使用。

停停停,先来干这个:优先处理

到目前为止说的都是些让问题变得更复杂的因素,那现在来看看让问题变得更简单的吧。比如如果能够在某件任务中途停下来,而去干其他事。这个叫作抢先 (preemption)的性质,让问题又发生了大大的改变。

一些之前无法被解决的问题,又能被解决了。比如说加入优先限制的最短处理时间问题,如果加入抢先后,就又能得到有效解决了。只要不停切换为处理当前重要度最大的任务即可。

抢先,尤其适合应对不确定性。假设在进行一些任务时,同时有新的任务突然加入,那么就需要重新考虑当前该运行的任务,也就是设置哪个任务抢先。

不确定性对策略的影响不大,仍然按照加入抢先后的策略进行就可以了。

抢先处理的代价 抢先有它的好处,当然也就有其缺点,环境切换 (Context Switch)。而环境切换时,是需要付出一些代价的。

日常中我们也常会碰到,从某事切换到另一件事时,有时需要调整下心理状态,或者工作环境。比如说查看邮件时,得打开邮件软件,等上好一会;如果要写代码,得登录终端,调节好状态;如果写作,又得找来卡片,笔墨,工具书...

任务和任务之间切换时,是需要耗费额外时间的。当任务少时,或许还看不出有什么问题,但当我们把任务切换频率提到很高时,就会出现一个很奇怪的现象系统颠簸 (thrashing).

简单的解释就是,假设有很多任务,我们想进行多任务处理,于是就给每个任务分配相等但少量的时间,不停地来回切换处理任务,这类似于计算机系统的分时处理。

假设每个任务都需要准备时间,于是当任务太多,分配给每个任务的时间块很短时,就会出现不断在任务之间切换,而每次准备时间就把时间块用完了的现象。这样就会不断在各个任务上移动,而实际工作却一点没做的现象,即系统颠簸。

日常生活中类似的,一有邮件就点开瞧瞧,一有信息就拿起来看看,有过经验的人也知道这样对效率影响有多大。

对于计算机来说,这个问题可以简单用升级内存或缓存的手法解决,当然对于我们人,要升级大脑可没那么简单,或许还得等到多年以后生物技术的发展。

但也还是有些方法来避免这个问题的。第一,我们可以减少任务的数量,对不重要的事情说不,把精力只集中在少数任务上。第二,我们可以规定最短时间块得有的时间,也就是很流行的番茄钟,给每个任务规定一个充足的最短时间。

当然,如果你不想减少任务数量,也不想麻烦的使用番茄钟,调度中一些其他技巧也能帮组你避免环境切换的损耗。

比如说中断结合 (Interrupt Coalescing),其实就是批量处理。简单说就是把类似任务放在一起完成,这样也就避免了环境切换。比如说把一天的特定半个小时全部用来回复邮件和发邮件,就能提高很多效率。

运用这个技巧的典范人物就是大神级程序员 Donald Knuth,他说:“我一次只干一件事。” 当然,他说的一件事是指需要相同环境的一类任务。比如说在“2014 TeX 大调整”中,他就一下把过去6年大家关于 TeX 反应的所有bug都修复了。完成之后还挂上“等待2021年的大调整”。不仅如此,他也没有电子邮箱,就连邮件都是三个月才看一次,而传真更是六个月才看一次。

其实我想知道其他时间他都干什么去了。

怎么管理自己的时间 最后回到主题,怎么利用调度算法最优地管理自己的时间?

很遗憾,答案是没有。因为现实中要处理的调度问题往往都是不可解决的,也就是没有最好的调度方案。

但是呢,至少我们也能从中借鉴到一些小技巧运用于时间管理中,比漫无目的地东一棒西一锤瞎干的好。

明确度量任务完成的标准,根据这个标准制定计划。

明确手头任务的重要性,再根据任务完成所需时间进行估算,先完成最紧急最重要的任务。

当一个紧急任务必须在一个不紧急任务之后才能进行时,将这个不紧急任务升级为同样紧急的任务。

不要尝试短时间内进行多任务,而是将相同任务归类,然后一段时间只做一类任务。

本文首发于微信公众号:大数据文摘。文章内容属作者个人观点,不代表和讯网立场。投资者据此操作,风险请自担。

版权与免责声明:
1、凡本站及其子站注明"文章类型:原创"的所有作品,其版权属于中国财经观察网站及其子站所有。其他媒体、网站或个人转载使用时必须注明:"文章来源:中国财经观察网"。
2、凡本站未注明来源为"中国财经观察网"的所有作品,均转载、编译或摘编自其它媒体,转载、编译或摘编的目的在于传递更多信息,并不代表本站及其子站赞同其观点和对其真实性负责。其他媒体、网站或个人转载使用时必须保留本站注明的文章来源,并自负法律责任。
3、如您不希望作品出现在本站,可联系我们要求撤下您的作品。邮箱:sue@xsgou.com

相关阅读

    无相关信息

网罗天下

投诉举报:sue@xsgou.com 在线投稿:tougao@xsgou.com 广告投放:ad@xsgou.com 商业合作:bd@xsgou.com
版权声明: 本网站部分文章和信息来源互联网,并不意味着赞同其观点或证实其内容的真实性,不构成投资建议。如转载稿涉及版权等问题,请立即联系管理员,我们会予以改正或删除相关文章,保证您的权利!
版权所有: 中国财经观察报·中国财经观察网www.xsgou.com (2012-2018)互联网ICP备案 中ICP备120056699号-1