PTT評價

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

看板Soft_Job標題Re: [請益] 排程相關的演算法(優先佇列)作者
Apache
(為寺川愛美瘋狂打call)
時間推噓13 推:13 噓:0 →:17

這書不好是他直接假設你知道計算機的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 留言評論
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.129.84 (臺灣)
PTT 網址

ntpuisbest10/21 22:49原來底層沒有提供幾點幾分喔,想問為何array是浪費複

ntpuisbest10/21 22:49雜度

ntpuisbest10/21 22:49array的話要怎麼做排程,只能無腦polling嗎?

gasbomb10/21 22:51因為array你沒辦法用O(1)拿到最優先的task

gasbomb10/21 22:53除非你每次insert的時候都sort 可是這樣更浪費

Apache10/21 23:09你再想一下 我覺得你沒有搞清楚問題

MoonCode10/21 23:39這id好棒 內容也讚

humanfly10/22 00:32感謝分享

jasonwung10/22 00:40推推

ntpuisbest10/22 00:46概念上大概就是對timer寫入要等待的時間跟一些參數

ntpuisbest10/22 00:46時間到的時候timer會拉一個interrupt 跳轉到timer的IS

ntpuisbest10/22 00:46R(一個函數)

ntpuisbest10/22 00:47我想重點應該在這句?

這樣講好了 你有很多task 分別要在不同時間執行 但你現在只有一個timer 一次只能設定一個要等的時間 那你應該怎麼做才能最有效處理這麼多task?

viper970910/22 00:49推解說

Firstshadow10/22 08:59大師

oneheat10/22 13:56不是Kernel沒有提供幾點幾分,而是Kernel的機制是會有一

oneheat10/22 13:56個固定的timer 每n ms(看freq 多少),會起來做一次一系

oneheat10/22 13:56列的操作

jason22233310/22 14:03

longlongint10/22 14:56講的不錯而且有看對問題 推

Hsins10/23 14:01這文章好棒欸

Karlsland10/23 23:16大師

※ 編輯: Apache (125.228.129.84 臺灣), 10/23/2022 23:25:32

richer660510/25 02:52

sxy6723010/25 10:31補充一下計時的部分,現在很多年輕一輩都不知道主機板

sxy6723010/25 10:31其實有一個RTC電池,主要是要儲存物理時鐘透過石英晶體

sxy6723010/25 10:31來計時,早期PC那個壞掉要做schedule就很麻煩,現在基

sxy6723010/25 10:31本上這塊已經做到很難壞了

sxy6723010/25 10:34我覺得原原PO把一個複合的問題沒有想得很透徹,timer、

sxy6723010/25 10:34interrupt、scheduler是一個複合的概念,全部都變成一

sxy6723010/25 10:34個就很難抽象思考