看板Soft_Job
作者Apache (為寺川愛美瘋狂打call)
標題Re: [請益] 排程相關的演算法(優先佇列)
時間2022-10-21 22:09:00
這書不好是他直接假設你知道計算機的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 -- ※ 發信站: 批踢踢實業坊(pttsite.org.tw), 來自: 125.228.129.84 (臺灣) ※ 文章網址: https://pttsite.org.tw/Soft_Job/M.1666361344.A.1DB
推 ntpuisbest: 原來底層沒有提供幾點幾分喔，想問為何array是浪費複 10/21 22:49
→ ntpuisbest: 雜度 10/21 22:49
→ ntpuisbest: array的話要怎麼做排程，只能無腦polling嗎？ 10/21 22:49
→ gasbomb: 因為array你沒辦法用O(1)拿到最優先的task 10/21 22:51
→ gasbomb: 除非你每次insert的時候都sort 可是這樣更浪費 10/21 22:53
推 helgalie: 我哥上包養網被我抓包.. 10/21 22:53
→ Apache: 你再想一下 我覺得你沒有搞清楚問題 10/21 23:09
推 MoonCode: 這id好棒 內容也讚 10/21 23:39
推 humanfly: 感謝分享 10/22 00:32
推 jasonwung: 推推 10/22 00:40
推 ntpuisbest: 概念上大概就是對timer寫入要等待的時間跟一些參數 10/22 00:46
推 OREOMZA: 有人包養過洋鬼子嗎 10/22 00:46
→ ntpuisbest: 時間到的時候timer會拉一個interrupt 跳轉到timer的IS 10/22 00:46
→ ntpuisbest: R(一個函數) 10/22 00:46
→ ntpuisbest: 我想重點應該在這句? 10/22 00:47
推 viper9709: 推解說 10/22 00:49
→ Firstshadow: 大師 10/22 08:59
推 punjab: 有錢人為啥都想包養 10/22 08:59
推 oneheat: 不是Kernel沒有提供幾點幾分，而是Kernel的機制是會有一 10/22 13:56
→ oneheat: 個固定的timer 每n ms(看freq 多少），會起來做一次一系 10/22 13:56
→ oneheat: 列的操作 10/22 13:56
推 jason222333: 推 10/22 14:03
推 longlongint: 講的不錯而且有看對問題 推 10/22 14:56
推 sashare: 有人被洋鬼子包養過嗎 10/22 14:56
推 Hsins: 這文章好棒欸 10/23 14:01
推 Karlsland: 大師 10/23 23:16
推 richer6605: 推 10/25 02:52
推 sxy67230: 補充一下計時的部分，現在很多年輕一輩都不知道主機板 10/25 10:31
→ sxy67230: 其實有一個RTC電池，主要是要儲存物理時鐘透過石英晶體 10/25 10:31
推 sijiex: 到底要多有錢才會想包養 10/25 10:31
→ sxy67230: 來計時，早期PC那個壞掉要做schedule就很麻煩，現在基 10/25 10:31
→ sxy67230: 本上這塊已經做到很難壞了 10/25 10:31
→ sxy67230: 我覺得原原PO把一個複合的問題沒有想得很透徹，timer、 10/25 10:34
→ sxy67230: interrupt、scheduler是一個複合的概念，全部都變成一 10/25 10:34
→ sxy67230: 個就很難抽象思考 10/25 10:34
推 VLADINA: 閨蜜上包養網還推薦我... 10/25 10:34