努克

首页 » 常识 » 常识 » 算法之美读书笔记3时间调度与贝叶斯
TUhjnbcbe - 2021/3/18 23:41:00

时间调度理论

主要讲述在多任务的情况下我们如何安排我们时间的理论。

在双机器的时间调度理论中,基本法则就是在单机器运行时间不变的前提下,让两台机器的共同工作时间尽量加长。减少两台机器单独运行的时间。从而保证总时间最短。

对于单机器的时间调度,首先要明确我们的目标,在有一个计划之前,必须首先选择一个衡量指标。

对于一堆有处理时限的任务,要减少最大延迟时间,最佳的策略就是从截止日期最近的任务开始,再以此类推执行下去。这就是最早到期日原则。

如果要减少过期任务的数量,那么我们要用到穆尔的BM算法。即先按照最早到期日原则进行排序,从头开始判断,如果发现有任务会过期,那么就把此任务(含)之前的耗时最长的任务去掉,以此类推,直到最后。

为了最大限度的减少客户的等待时间,我们应该使用“最短加工时间”的方法,即总是做最快完成的任务,完成A的需要4天,完成B的需要1天,我们按AB顺序进行工作A需要等4天,B需要等5天,一共需要等9天,如果按BA的顺序执行,B需要等1天,A需要等5天,一共等6天。

最短加工时间法,就是要尽最大的可能减少在我们脑海中悬而未决的任务的数量,因为未完成的任务越多,给我们的压力往往越大。

如果任务在重要性上有明显区别,可以给任务进行加权处理。先去做单位时间权值高的任务

戴一只手表的人知道时间,而戴两只手表的人就不能确定时间了。

给系统无数琐碎的事情做,重要的东西就会迷失在混乱中。

有时为了减少任务数量,总是被子任务干扰,而忽略了主任务,导致了所谓拖延症的出现,最重要的事情总是被拖延。

重点不是把事情做好,更重要的是把权值更高的事情做好。每一时刻去做最重要的工作。

这样能够克服拖延症吗?答案是:在人类生活中可行,但是在机器运行中有可能出问题。

因为我们在执行低优先级任务的时候,会抢占资源,当低优先级任务被高优先级任务抢占时,发现资源被占用,无法执行,导致高级别任务阻塞,在一定情况下会导致高优先级任务一直得不到执行。

于是我们需要进行任务优先级的转化,调高占用资源的低优先级任务的等级。这叫优先级转化

高优先级的任务可以抢占低优先级的任务,等高优先级的任务执行完毕,再执行原先被抢占的任务。每当高优先级的任务到来之后都会优先执行。

这也被称为“上下文切换”,此切换消耗计算机的资源和时间,这种切换并不是真正的工作,这是无用功,每一次上下文切换都在浪费时间。

人类在上下文切换时也会付出代价,通俗点讲:就是被打扰,我们会很烦。被打扰后,把心智重新回归到原先的任务上,会耗费大量的时间和专注力。

编程和写作需要考虑整个系统的状态,所以其进行上下文切换的成本就非常的大。

把上下文切换的理论延续一下,放到时间跨度更大的事情上,做事情保持持续的状态是很有必要的,所以放假对于学习的延续性来说,是不利的,所以布置作业是必要的,作业在一天内做完也是不利的,应该每天都进行学习,保持学习的持续性。状态断的越久,恢复起来需要的时间就越长。

每天的作业应该是当天天学习知识的总结,回顾和练习,以及明天学习内容的预习和疑问记录。每周也应该是一样;每月,每学期都是一样。

程序员在一定的时间段内,一定是要集中写一个程序,如果多个程序开工就会影响效率,我们的程序要分成模块,模块的模块,一个小的时间段内,只去写一个功能单一的模块,不可9点在考虑数据存储,10点考虑地址分配,11点考虑数据通信,12点又去考虑数据存储了。

现实生活中,有很多东西在诱惑你进行上下文的切换,工作时放在桌子上的手机,手机的叮咚一响,电脑上的弹窗,搜索时的热门话题和图片。

我们采用最短时间加工法,也是在减少任务切换带来的烦恼,当我们的悬而未决的任务越多时,我们脑海中就总是会时不时的冒出这些任务,虽然切换的时间很短暂,但还是会干扰我们的当前任务进程。

做题先易后难是多么正确的选择!它最大程序上消除了悬而未决的任务。这是最短加工时间的应用

但是先易后难也要避免频繁切换,已经思考了好久了,再切换有时不一定值得。这是上下文切换的应用。

正确的做法是,看一眼,通盘没思路,立马切换,并给出难易等级;看一眼,有部分思路,但是没有通盘的思路,立即切换。看一眼,通盘思路清晰,早已胸有成竹,立即开始解答。等所有的低等级的题,解答完毕,再集中力量解答中等级的题目,以此类推,逐一攻破,此时解决低难度题带来的自信心会很有帮助。

上课开小差就是典型的任务频繁切换,浪费的时间绝不是开小差这一会的时间,其危害巨大。

有时我们写作的时候,需要思考的好几天,终于来感觉了,这时候,文思泉涌,可以写个滔滔不绝,如果这个时候被打断,我们可能需要重新再积累好几天的感觉,岂不痛哉!

结合缓存的知识,我们在任务切换的极端情况下,会出现“一事无成”,“系统宕机”的情况。

我们在开始新任务的之前,会把任务需要的项目转化为缓存,如果刚刚转化完成,就切换另一个任务,另一个任务又开始转化缓存,周而复始,系统将一事无成。

如果系统没有足够的空余内存保存其工作组,那就应该拒绝添加新的程序。

上下文切换时,无用功最大的来源就是选择下一步做什么。

所以有时候在为任务的重要程度排序困难时,不必纠结下一步要进行哪一个任务,即使以错误工作开始也比什么都不做要强。

使调度变得如此复杂和有趣的原因,就是反应速度和吞吐量之间不可调和的矛盾,

我们要想对所有的任务进行快速反应,就必须在一定的周期内快速切换,快速切换带来的后果就是吞吐量的减少,导致系统频繁切换,而没有时间进行实际工作

所以在计算机中规定了最小切片时间。如果任务不断增多,只能增加反应周期,保证最小吞吐量,牺牲反应时间。

设置花在任何一个任务上的最低时间量,有助于防止过于强调反应速度而完全忽视吞吐量。番茄时间理论大抵也缘于此。

但是我们要设置多长时间呢?大部分的情况应该是:尽可能长,直到当前任务完成。

如果你发现自己在进行很多的上下文切换,你也可以使用计算机科学的另一个做法:“中断合并”,邮递员每天只会检查邮箱一次,我们处理邮件也是一样,不是每来一次就处理一次。

这有时也被称为批处理,高德纳.克努斯就是一个极端例子,程序bug和新需求要积攒6年才会修改一次,邮件3个月处理一次。牛逼plus。

我最近决定的每一周看一次自己喜欢的

1
查看完整版本: 算法之美读书笔记3时间调度与贝叶斯