這書不好是他直接假設你知道計算機的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://www.ptt.cc/bbs/Soft_Job/M.1666361344.A.1DB.htmlntpuisbest1樓原來底層沒有提供幾點幾分喔,想問為何array是浪費複 10/21 22:49
→ ntpuisbest2樓雜度 10/21 22:49
→ ntpuisbest3樓array的話要怎麼做排程,只能無腦polling嗎? 10/21 22:49
→ gasbomb4樓因為array你沒辦法用O(1)拿到最優先的task 10/21 22:51
→ gasbomb5樓除非你每次insert的時候都sort 可是這樣更浪費 10/21 22:53
→ 本人6樓你再想一下 我覺得你沒有搞清楚問題 10/21 23:09
MoonCode7樓這id好棒 內容也讚 10/21 23:39
humanfly8樓感謝分享 10/22 00:32
jasonwung9樓推推 10/22 00:40
ntpuisbest10樓概念上大概就是對timer寫入要等待的時間跟一些參數 10/22 00:46
→ ntpuisbest11樓時間到的時候timer會拉一個interrupt 跳轉到timer的IS 10/22 00:46
→ ntpuisbest12樓R(一個函數) 10/22 00:46
→ ntpuisbest13樓我想重點應該在這句? 10/22 00:47
這樣講好了
你有很多task 分別要在不同時間執行
但你現在只有一個timer 一次只能設定一個要等的時間
那你應該怎麼做才能最有效處理這麼多task?
viper970914樓推解說 10/22 00:49
→ Firstshadow15樓大師 10/22 08:59
oneheat16樓不是Kernel沒有提供幾點幾分,而是Kernel的機制是會有一 10/22 13:56
→ oneheat17樓個固定的timer 每n ms(看freq 多少),會起來做一次一系 10/22 13:56
→ oneheat18樓列的操作 10/22 13:56
jason22233319樓推 10/22 14:03
longlongint20樓講的不錯而且有看對問題 推 10/22 14:56
Hsins21樓這文章好棒欸 10/23 14:01
Karlsland22樓大師 10/23 23:16
richer660523樓推 10/25 02:52
sxy6723024樓補充一下計時的部分,現在很多年輕一輩都不知道主機板 10/25 10:31
→ sxy6723025樓其實有一個RTC電池,主要是要儲存物理時鐘透過石英晶體 10/25 10:31
→ sxy6723026樓來計時,早期PC那個壞掉要做schedule就很麻煩,現在基 10/25 10:31
→ sxy6723027樓本上這塊已經做到很難壞了 10/25 10:31
→ sxy6723028樓我覺得原原PO把一個複合的問題沒有想得很透徹,timer、 10/25 10:34
→ sxy6723029樓interrupt、scheduler是一個複合的概念,全部都變成一 10/25 10:34
→ sxy6723030樓個就很難抽象思考 10/25 10:34