作者Apache (为寺川爱美疯狂打call)
看板Soft_Job
标题Re: [请益] 排程相关的演算法(优先伫列)
时间Fri Oct 21 22:09:00 2022
这书不好是他直接假设你知道计算机的timer怎麽用
这边有个范例
https://www.embeddedrelated.com/showarticle/182.php
计算机底层没有提供几点几分做什麽事这种很高阶的排程器
你如果要计算时间的话 唯一的精确方式就是用CPU提供的timer interrupt
概念上大概就是对timer写入要等待的时间跟一些参数
时间到的时候timer会拉一个interrupt 跳转到timer的ISR(一个函数)
这样就完成一次时间的计算
但问题来了 CPU通常不会有太多timer
所以你一次只能计很有限的事情
要多排几个东西的话 就要把task都存起来
进到ISR的时候来检查现在要做什麽
其中最有效的方式就是PQ
因为PQ保证顶端的工作必定是下一个工作
只要取pq.top().time - now()就能得到下一次要等待的时间
如果中途插入也是一样的操作
当然你要用list 或array也可以 但这就单纯浪费复杂度
至於RR还是SJF 跟这边没有任何关系
顶多就是你在实现multitasking的时候会需要用timer来做scheduling
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 125.228.129.84 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Soft_Job/M.1666361344.A.1DB.html
1F：推 ntpuisbest: 原来底层没有提供几点几分喔，想问为何array是浪费复 10/21 22:49
2F：→ ntpuisbest: 杂度 10/21 22:49
3F：→ ntpuisbest: array的话要怎麽做排程，只能无脑polling吗？ 10/21 22:49
4F：→ gasbomb: 因为array你没办法用O(1)拿到最优先的task 10/21 22:51
5F：→ gasbomb: 除非你每次insert的时候都sort 可是这样更浪费 10/21 22:53
6F：→ Apache: 你再想一下 我觉得你没有搞清楚问题 10/21 23:09
7F：推 MoonCode: 这id好棒 内容也赞 10/21 23:39
8F：推 humanfly: 感谢分享 10/22 00:32
9F：推 jasonwung: 推推 10/22 00:40
10F：推 ntpuisbest: 概念上大概就是对timer写入要等待的时间跟一些参数 10/22 00:46
11F：→ ntpuisbest: 时间到的时候timer会拉一个interrupt 跳转到timer的IS 10/22 00:46
12F：→ ntpuisbest: R(一个函数) 10/22 00:46
13F：→ ntpuisbest: 我想重点应该在这句? 10/22 00:47
这样讲好了
你有很多task 分别要在不同时间执行
但你现在只有一个timer 一次只能设定一个要等的时间
那你应该怎麽做才能最有效处理这麽多task？
14F：推 viper9709: 推解说 10/22 00:49
15F：→ Firstshadow: 大师 10/22 08:59
16F：推 oneheat: 不是Kernel没有提供几点几分，而是Kernel的机制是会有一 10/22 13:56
17F：→ oneheat: 个固定的timer 每n ms(看freq 多少），会起来做一次一系 10/22 13:56
18F：→ oneheat: 列的操作 10/22 13:56
19F：推 jason222333: 推 10/22 14:03
20F：推 longlongint: 讲的不错而且有看对问题 推 10/22 14:56
21F：推 Hsins: 这文章好棒欸 10/23 14:01
22F：推 Karlsland: 大师 10/23 23:16
※ 编辑: Apache (125.228.129.84 台湾), 10/23/2022 23:25:32
23F：推 richer6605: 推 10/25 02:52
24F：推 sxy67230: 补充一下计时的部分，现在很多年轻一辈都不知道主机板 10/25 10:31
25F：→ sxy67230: 其实有一个RTC电池，主要是要储存物理时钟透过石英晶体 10/25 10:31
26F：→ sxy67230: 来计时，早期PC那个坏掉要做schedule就很麻烦，现在基 10/25 10:31
27F：→ sxy67230: 本上这块已经做到很难坏了 10/25 10:31
28F：→ sxy67230: 我觉得原原PO把一个复合的问题没有想得很透彻，timer、 10/25 10:34
29F：→ sxy67230: interrupt、scheduler是一个复合的概念，全部都变成一 10/25 10:34
30F：→ sxy67230: 个就很难抽象思考 10/25 10:34