contributed by < bevmmf
>
注意細節!
我覺得材料對 scheduler 的描述很有趣且直觀,「scheduler 就是一個數學函數,功能是映射 process 到系統資源」。單單要將此功能實現可能不難,但若是還需考慮性能規格如以下,那就不是件容易的事情。
NUMA
(Non-Uniform Memory Access)架構時,還能維持相同程度的規格( fairness ~ Real-Time Support ),即是此規格關注的。而材料也做了一小實驗嘗試去求得scheduler之效能,也可以粗略地說是 Context switch 的效能。 本來使用 perf 出現的失真問題是因為 scheduler 可能將兩 process 在不同的 core 執行而導致跨核心通訊(透過共享記憶體或 interconnect,引發 cache coherence 延遲(cache misses 或 invalidation))與核心間協調問題(例如 IPI,Inter-Processor Interrupts)。因此改為使用 taskset 工具將兩 process affinity 指派到同一 core 底下。最後得出結果為 。此數量級十分重要,因為scheduler 切出的 time slice 必需在此數量級 scale 以下才有意義。
最後針對 scheduler ,因為不同任務所追求的規格不同,劃分了任務種類 :
普通 process
交互式行程 (interactive processs)
: 對延遲敏感,追求 low latency (如 GUI 應用 等 IO-bound 任務)批處理行程 (batch process)
: 追求 throughput (如背景執行資料處理等 CPU-bound 任務)即時 process
: 有deadlineLinux Scheduler 演進的時間順序
時間:Linux 2.4 系列(約 2001 年發布,持續使用至 2003 年左右)。
特點:使用 global runqueue,O(n) 複雜度,支援 SMP 但 scalability 差,non-determinism 高。原因是因為dequeue時需要lock,同時多核競爭一lock導致開銷隨 core 數上升 (scalability 差)。再來因為將執行完一 time slice 的 process 放到 expired queue 時以 O(N) 搜尋要放置的位置造成效率隨負載量上升 (non-determinism 高)
背景:單核或少量核心系統為主,任務數較少,real-time support 需求不強。
2. Linux 2.6.0 至 2.6.22:O(1) Scheduler (2003-2007):
時間:Linux 2.6.0(2003 年)至 2.6.22(2007 年)。
特點:引入 priority array 和 bitarrays,實現 O(1) 操作,提升 scalability 和 determinism,但 fairness 不足。而該O(1)實現設計思路分為三 :
而實作原理為以下 :
將本來的 runqueue 換成 priority queue ,同時因為搜尋下一個任務的 priority 為 O(M) 常數時間,以 bit array 作為索引達成 O(1)。而在expired array 的搜索放置也有一樣問題,因此也多維護一 expired bit array 作為索引。
運作原理為以下 :
APA[x]
;APA[x]
中 dequeue 一個 process,dequeue 後,如果 APA[x]
的 queue 為空,那麼將 active bitarray 裡第 x bit 設定為 0;EPA[priority]
;這篇文章熱血的像是少年漫畫,同時也很符合現實的將真實世界遇到的種種問題反映吃來。因此讓我在看的過程能夠享受其中,跟著作者的視角看整個自動飲料機誕生,也在這個過程當中學習到很多學校教育不會告訴我們的有趣、實濟、現實與寶貴的經驗與辛苦談。
其中有幾個部分與幾句話是讓我產生共鳴與有感的。
第一個部分是作者起初做機構實驗遇到的體悟,「資工系實驗維度是數小時到數日,而機械系的實驗維度是數周到數月」。硬體的迭代週期與軟體的實驗分析維度的不同也是我最近很有感的。正好最近也面臨採購研究實驗器材的狀況,光是決定一個馬達規格其中就有許多因素要考慮,若是還要加上齒輪箱與耦合機構,涉及的不僅是尺寸,還有運動規劃、負載效應、馬達額定與最大轉速是否足夠與轉速太低不好控制等等問題。
第二部分是作者遇到設備不足時該如何解決。我認為作者的決定 : 租借設備(系所老師 -> 公家機關 -> 企業行號),在成本限制高時是個很好的思考流程。
第三部分是作者買設備時的感悟,「花大錢買設備首要之務就是訂規格,多花錢買不需要的規格是浪費,為了省錢買性能不足的產品是更大的浪費。」,盡可能的量化需要的規格,知道需要什麼程度的規格,也是系統開發很重要得一環,畢竟成本不是無限的。系統還有一個重要的觀念就是整合,反過來說要先將系統拆分成多個子系統,在對每個子系統做模組測試成功後,再將多個子系統整合起來測試,最後才能讓系統做最後整合測試。
除了以上實務經驗之外,我認為心態層面也是不可忽視的重要能力。我認為在過程中最關鍵的點其實是中間作者因為機構問題做不出製冰機一度想放棄的那時間點。就像是學習曲線最高點一樣,是問題最關鍵的部分,只要熬過那個x點,後面的問題會越來越順利。這也呼應到老師所說的,「你該學習的不是看到事情要完蛋了就去避免失敗,而是應該學習如何處理與承受失敗,你才能變得比以前更強大。」,那個失敗才是整個過程中最精華的段落。然而有時候也不應對一個問題的解決過於執著,如同文章所說「如果問題過於困難無法解決,那就重新定義問題吧!」。
看完這篇文章與經過這幾周課程,我認為老師不只想教授我們相對應的知識,更多的是素養、對抗重大問題的能力與與人有效溝通的實例。「誠實面對自己」,這句話是我目前覺得簡單但又重要也是時時刻刻提醒自己的一句話。我現在養成每次學習都會問自己有沒有誠實面對自己。有那裡是自己想偷懶又含糊帶過的。這句話給我很多主動審視自己的機會。