作者ntpuisbest (阿龙)
看板Soft_Job
标题[请益] 排程相关的演算法(优先伫列)
时间Fri Oct 21 20:24:19 2022
目前工作大概一年多
想问一下各位关於排程相关的算法
https://i.imgur.com/DBthnys.png
我在书上观看这个高性能定时器的章节
他提到每一秒扫描整张大表的坏处有二
1.任务的约定执行时间可能跟当前时间距离很久，所以扫描是徒劳的
2.如果列表很大，这会很徒劳
关於这两点我都可以理解 每秒扫描会有这两个坏处
也理解优先伫列可以避免这些问题
但我的问题是，这真的要动用到优先伫列吗?
我对电脑底层不熟悉
没有办法直接去设定说
假设每个任务只要做十分钟就一定可以做完好了
八点做A任务
九点做B任务
十点做C任务
我看很多框架都有支援这种方式
我朋友是跟我说那些框架可能底层也是靠priority queue来做的
我是不太理解，如果都可以每隔某段时间做某件事
电脑应该也可以指定时间做事吧?
为何一定要依靠每秒轮询polling 或是 priority queue来做
这是我查到的排程相关算法的资料，每秒轮询应该就是下面的
Round Robin (RR)
https://data-flair.training/blogs/scheduling-algorithms-in-operating-system/
希望各位版友可以解惑
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.160.137.197 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Soft_Job/M.1666355061.A.EE8.html
1F：推 itoni: 不管怎麽样你总该有地方放所有预定的工作吧 那要用什麽资料10/21 20:39
2F：→ itoni: 结构存 比一下就是PQ最适合啊10/21 20:39
3F：→ aa06697: PQ已经是蛮底层的资料结构了吧 再更底层你是想用硬体去做10/21 20:41
4F：→ aa06697: ？10/21 20:41
我的问题是用list或是阵列去存时间也可以吧
但是书上说的好像
要每秒去go through 整个array 看有没有发生
现在时间等於array[i]的时间
但是没有其他更简单的做法吗？除了pq外
※ 编辑: ntpuisbest (118.160.137.197 台湾), 10/21/2022 20:45:10
5F：推 itoni: 用LL或array存 那新增task的时间就会要O(n) 10/21 20:55
6F：→ lwoody84857: 电脑没法指定时间，会有润秒问题 10/21 21:03
7F：→ lwoody84857: 搞懂wall clock和monolithic clock，你大概就能解惑 10/21 21:03
8F：→ lwoody84857: 其他高级一点的做法像是timing wheel，但底层也是p 10/21 21:03
9F：→ lwoody84857: olling+pq的实现 10/21 21:03
10F：→ gasbomb: 电脑的世界没有魔法 你看到的便利功能都是人家刻出来的 10/21 21:07
11F：→ gasbomb: 想到之前有人问说删资料夹一定要跑recursive吗? 10/21 21:07
12F：→ gasbomb: windows都可以一键删除整个资料夹耶 10/21 21:08
13F：→ gasbomb: 可是windows的删除功能也是下去跑recursive啊 10/21 21:08
14F：推 MyNion: 你可以用LinkedList配合二元树去做，这样取排程就是O(1) 10/21 21:09
15F：→ MyNion: 取完排程再插回去就是O(log n) 10/21 21:10
16F：→ GTR12534: 你讲的东西相比之下不够底层 10/21 21:20
17F：→ longlongint: 你的假设套PQ不适合 10/21 21:30
18F：→ longlongint: 你如果把派任务给你的人想成你主管 会比较好像 10/21 21:31
19F：→ longlongint: 比较好想像 （前面打错字 10/21 21:31
20F：→ longlongint: 一直抽插任务 一下很急一下又取消 10/21 21:32
21F：→ longlongint: 然後一直改顺序+要你多工顾多个任务 10/21 21:32
22F：→ longlongint: 然後跟你说哪个任务重要也不知道 你想办法让客户爽 10/21 21:33
23F：→ longlongint: 这时候OS就要猜优先度+用PQ(linux是CFS 红黑树） 10/21 21:35
24F：→ longlongint: 看要排什麽事情做，然後又不能单一任务做太久 10/21 21:35
25F：→ Apache: 问就是去看底层 10/21 21:38
26F：→ Apache: 电脑里面没有小精灵 10/21 21:39
27F：→ Apache: 要动时间不是polling就是timer interrupt 10/21 21:39
28F：推 Apache: 这东西跟排程无关 有机会去看单片机实现排程的方式 10/21 21:42
29F：推 lovdkkkk: 用 map 日期时间字串当 key value 放该时间要跑的东西就 10/21 21:47
30F：→ lovdkkkk: 不用扫全部了？ 10/21 21:47
31F：推 xam: 用map不是更瞎忙..... 10/21 21:51
32F：推 lovdkkkk: 好像是耶 push 然後 loop 省事 10/21 21:53
33F：推 OriginStar: 原PO把许多问题混在一起了。用举例解释，就PO开会等老 10/21 22:17
34F：→ OriginStar: 板但拉肚子想跑厕所，一直看手表(scan)也没用。书中少 10/21 22:18
35F：→ OriginStar: 少提到预估时间这件事，而电脑中多数Task的执行时间是 10/21 22:20
36F：→ OriginStar: 很难预估的，受到很多因素影响，所以电脑要在特定时间 10/21 22:25
37F：→ OriginStar: 执行特定功能也无法保证 10/21 22:26
38F：推 enthos: 玩 Javascript RTS: Screeps 就会有实际的感受 10/21 22:28
39F：推 wulouise: 一定十分钟是怎麽保证的？ 10/21 23:17
40F：→ wulouise: 很多东西都是没办法预测的，要是可以预测大家早就做了 10/21 23:19
41F：推 Zerocks: 设定cronjob 其实就是以最小时间单位下去检查是不是该tr 10/21 23:45
42F：→ Zerocks: igger 10/21 23:45
43F：→ Zerocks: 有queue 在检查的时候只要看queue 就好 10/21 23:46
44F：→ Zerocks: 电脑只有指令周期的概念 没有时间的概念 时间是前人做出 10/21 23:48
45F：→ Zerocks: 来的方便东西 10/21 23:48
46F：→ GoalBased: 你说的可以，但怎麽实现的？ 10/22 12:28