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

看板Soft_Job作者 (阿龍)時間1年前 (2022/10/21 20:24), 1年前編輯推噓11(11推 0噓 35→)
留言46則, 15人參與, 1年前最新討論串1/3 (看更多)
目前工作大概一年多 想問一下各位關於排程相關的算法 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://www.ptt.cc/bbs/Soft_Job/M.1666355061.A.EE8.html
推
10/21 20:39, 1年前 , 1F
不管怎麼樣你總該有地方放所有預定的工作吧 那要用什麼資料
10/21 20:39, 1F
→
10/21 20:39, 1年前 , 2F
結構存 比一下就是PQ最適合啊
10/21 20:39, 2F
→
10/21 20:41, 1年前 , 3F
PQ已經是蠻底層的資料結構了吧 再更底層你是想用硬體去做
10/21 20:41, 3F
→
10/21 20:41, 1年前 , 4F
？
10/21 20:41, 4F
我的問題是用list或是陣列去存時間也可以吧 但是書上說的好像 要每秒去go through 整個array 看有沒有發生 現在時間等於array[i]的時間 但是沒有其他更簡單的做法嗎？除了pq外 ※ 編輯: ntpuisbest (118.160.137.197 臺灣), 10/21/2022 20:45:10
推
10/21 20:55, 1年前 , 5F
用LL或array存 那新增task的時間就會要O(n)
10/21 20:55, 5F
→
10/21 21:03, 1年前 , 6F
電腦沒法指定時間，會有潤秒問題
10/21 21:03, 6F
→
10/21 21:03, 1年前 , 7F
搞懂wall clock和monolithic clock，你大概就能解惑
10/21 21:03, 7F
→
10/21 21:03, 1年前 , 8F
其他高級一點的做法像是timing wheel，但底層也是p
10/21 21:03, 8F
→
10/21 21:03, 1年前 , 9F
olling+pq的實現
10/21 21:03, 9F
→
10/21 21:07, 1年前 , 10F
電腦的世界沒有魔法 你看到的便利功能都是人家刻出來的
10/21 21:07, 10F
→
10/21 21:07, 1年前 , 11F
想到之前有人問說刪資料夾一定要跑recursive嗎?
10/21 21:07, 11F
→
10/21 21:08, 1年前 , 12F
windows都可以一鍵刪除整個資料夾耶
10/21 21:08, 12F
→
10/21 21:08, 1年前 , 13F
可是windows的刪除功能也是下去跑recursive啊
10/21 21:08, 13F
推
10/21 21:09, 1年前 , 14F
你可以用LinkedList配合二元樹去做，這樣取排程就是O(1)
10/21 21:09, 14F
→
10/21 21:10, 1年前 , 15F
取完排程再插回去就是O(log n)
10/21 21:10, 15F
→
10/21 21:20, 1年前 , 16F
你講的東西相比之下不夠底層
10/21 21:20, 16F
→
10/21 21:30, 1年前 , 17F
你的假設套PQ不適合
10/21 21:30, 17F
→
10/21 21:31, 1年前 , 18F
你如果把派任務給你的人想成你主管 會比較好像
10/21 21:31, 18F
→
10/21 21:31, 1年前 , 19F
比較好想像 （前面打錯字
10/21 21:31, 19F
→
10/21 21:32, 1年前 , 20F
一直抽插任務 一下很急一下又取消
10/21 21:32, 20F
→
10/21 21:32, 1年前 , 21F
然後一直改順序+要你多工顧多個任務
10/21 21:32, 21F
→
10/21 21:33, 1年前 , 22F
然後跟你說哪個任務重要也不知道 你想辦法讓客戶爽
10/21 21:33, 22F
→
10/21 21:35, 1年前 , 23F
這時候OS就要猜優先度+用PQ(linux是CFS 紅黑樹）
10/21 21:35, 23F
→
10/21 21:35, 1年前 , 24F
看要排什麼事情做，然後又不能單一任務做太久
10/21 21:35, 24F
→
10/21 21:38, 1年前 , 25F
問就是去看底層
10/21 21:38, 25F
→
10/21 21:39, 1年前 , 26F
電腦裡面沒有小精靈
10/21 21:39, 26F
→
10/21 21:39, 1年前 , 27F
要動時間不是polling就是timer interrupt
10/21 21:39, 27F
推
10/21 21:42, 1年前 , 28F
這東西跟排程無關 有機會去看單片機實現排程的方式
10/21 21:42, 28F
推
10/21 21:47, 1年前 , 29F
用 map 日期時間字串當 key value 放該時間要跑的東西就
10/21 21:47, 29F
→
10/21 21:47, 1年前 , 30F
不用掃全部了？
10/21 21:47, 30F
推
10/21 21:51, 1年前 , 31F
用map不是更瞎忙.....
10/21 21:51, 31F
推
10/21 21:53, 1年前 , 32F
好像是耶 push 然後 loop 省事
10/21 21:53, 32F
推
10/21 22:17, 1年前 , 33F
原PO把許多問題混在一起了。用舉例解釋，就PO開會等老
10/21 22:17, 33F
→
10/21 22:18, 1年前 , 34F
闆但拉肚子想跑廁所，一直看手錶(scan)也沒用。書中少
10/21 22:18, 34F
→
10/21 22:20, 1年前 , 35F
少提到預估時間這件事，而電腦中多數Task的執行時間是
10/21 22:20, 35F
→
10/21 22:25, 1年前 , 36F
很難預估的，受到很多因素影響，所以電腦要在特定時間
10/21 22:25, 36F
→
10/21 22:26, 1年前 , 37F
執行特定功能也無法保證
10/21 22:26, 37F
推
10/21 22:28, 1年前 , 38F
玩 Javascript RTS: Screeps 就會有實際的感受
10/21 22:28, 38F
推
10/21 23:17, 1年前 , 39F
一定十分鐘是怎麼保證的？
10/21 23:17, 39F
→
10/21 23:19, 1年前 , 40F
很多東西都是沒辦法預測的，要是可以預測大家早就做了
10/21 23:19, 40F
推
10/21 23:45, 1年前 , 41F
設定cronjob 其實就是以最小時間單位下去檢查是不是該tr
10/21 23:45, 41F
→
10/21 23:45, 1年前 , 42F
igger
10/21 23:45, 42F
→
10/21 23:46, 1年前 , 43F
有queue 在檢查的時候只要看queue 就好
10/21 23:46, 43F
→
10/21 23:48, 1年前 , 44F
電腦只有指令週期的概念 沒有時間的概念 時間是前人做出
10/21 23:48, 44F
→
10/21 23:48, 1年前 , 45F
來的方便東西
10/21 23:48, 45F
→
10/22 12:28, 1年前 , 46F
你說的可以，但怎麼實現的？
10/22 12:28, 46F
‣ 更多 ntpuisbest 的文章
文章代碼(AID): #1ZKezrxe (Soft_Job)
‣ 更多 ntpuisbest 的文章
文章代碼(AID): #1ZKezrxe (Soft_Job)