Re: [請益] 排程相關的演算法(優先佇列)

看板Soft_Job作者 (為寺川愛美瘋狂打call)時間1年前 (2022/10/21 22:09), 1年前編輯推噓13(13推 0噓 17→)
留言30則, 15人參與, 1年前最新討論串2/3 (看更多)
這書不好是他直接假設你知道計算機的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.html
推
10/21 22:49, 1年前 , 1F
原來底層沒有提供幾點幾分喔，想問為何array是浪費複
10/21 22:49, 1F
→
10/21 22:49, 1年前 , 2F
雜度
10/21 22:49, 2F
→
10/21 22:49, 1年前 , 3F
array的話要怎麼做排程，只能無腦polling嗎？
10/21 22:49, 3F
→
10/21 22:51, 1年前 , 4F
因為array你沒辦法用O(1)拿到最優先的task
10/21 22:51, 4F
→
10/21 22:53, 1年前 , 5F
除非你每次insert的時候都sort 可是這樣更浪費
10/21 22:53, 5F
→
10/21 23:09, 1年前 , 6F
你再想一下 我覺得你沒有搞清楚問題
10/21 23:09, 6F
推
10/21 23:39, 1年前 , 7F
這id好棒 內容也讚
10/21 23:39, 7F
推
10/22 00:32, 1年前 , 8F
感謝分享
10/22 00:32, 8F
推
10/22 00:40, 1年前 , 9F
推推
10/22 00:40, 9F
推
10/22 00:46, 1年前 , 10F
概念上大概就是對timer寫入要等待的時間跟一些參數
10/22 00:46, 10F
→
10/22 00:46, 1年前 , 11F
時間到的時候timer會拉一個interrupt 跳轉到timer的IS
10/22 00:46, 11F
→
10/22 00:46, 1年前 , 12F
R(一個函數)
10/22 00:46, 12F
→
10/22 00:47, 1年前 , 13F
我想重點應該在這句?
10/22 00:47, 13F
這樣講好了 你有很多task 分別要在不同時間執行 但你現在只有一個timer 一次只能設定一個要等的時間 那你應該怎麼做才能最有效處理這麼多task？
推
10/22 00:49, 1年前 , 14F
推解說
10/22 00:49, 14F
→
10/22 08:59, 1年前 , 15F
大師
10/22 08:59, 15F
推
10/22 13:56, 1年前 , 16F
不是Kernel沒有提供幾點幾分，而是Kernel的機制是會有一
10/22 13:56, 16F
→
10/22 13:56, 1年前 , 17F
個固定的timer 每n ms(看freq 多少），會起來做一次一系
10/22 13:56, 17F
→
10/22 13:56, 1年前 , 18F
列的操作
10/22 13:56, 18F
推
10/22 14:03, 1年前 , 19F
推
10/22 14:03, 19F
推
10/22 14:56, 1年前 , 20F
講的不錯而且有看對問題 推
10/22 14:56, 20F
推
10/23 14:01, 1年前 , 21F
這文章好棒欸
10/23 14:01, 21F
推
10/23 23:16, 1年前 , 22F
大師
10/23 23:16, 22F
※ 編輯: Apache (125.228.129.84 臺灣), 10/23/2022 23:25:32
推
10/25 02:52, 1年前 , 23F
推
10/25 02:52, 23F
推
10/25 10:31, 1年前 , 24F
補充一下計時的部分，現在很多年輕一輩都不知道主機板
10/25 10:31, 24F
→
10/25 10:31, 1年前 , 25F
其實有一個RTC電池，主要是要儲存物理時鐘透過石英晶體
10/25 10:31, 25F
→
10/25 10:31, 1年前 , 26F
來計時，早期PC那個壞掉要做schedule就很麻煩，現在基
10/25 10:31, 26F
→
10/25 10:31, 1年前 , 27F
本上這塊已經做到很難壞了
10/25 10:31, 27F
→
10/25 10:34, 1年前 , 28F
我覺得原原PO把一個複合的問題沒有想得很透徹，timer、
10/25 10:34, 28F
→
10/25 10:34, 1年前 , 29F
interrupt、scheduler是一個複合的概念，全部都變成一
10/25 10:34, 29F
→
10/25 10:34, 1年前 , 30F
個就很難抽象思考
10/25 10:34, 30F
‣ 更多 Apache 的文章
文章代碼(AID): #1ZKgW07R (Soft_Job)
‣ 更多 Apache 的文章
文章代碼(AID): #1ZKgW07R (Soft_Job)