OS Kernel 相關閱讀與實作心得﹝一﹞

極慚愧的是,這次寒假的計劃並未完全如期完成,實作 OS Kernel 的計劃只進行到 IRQ 的部份。不過,自從最近拜讀《即時多工核心程式設計》之後,深深被其所影響,讓我想好好重新調整實作的步調並整理針對 OS Kernel 設計的心得。

這本大作將核心架構在 DOS 環境上,用 DOS 省去了讀者摸索低階的時間,並以 C++ 的邏輯表達和 Template 的優勢加上必要的 ASM coding 設計一個 pure 的即時多工核心。尤其以直接切入 Kernel 運作為主題的方式,讓讀者更能立即擁有享受 Hacking Kernel 的成就感。

一個多工 OS Kernel 應該具備的機制,大致如下:
  1. Task Context Switching/Scheduler
  2. IPC (Inter Process Communication)
  3. Semaphore

事實上, OS Kernel 基礎的結構本來就並不龐大、複雜,這與『 microkernel 』的定義指標極為相似。而且,只存在該有的 Task Handler 和各工作 Connection 的機制,也容易理解與設計。至於其它的 Hardware Manager 等功能,其實並不需要在第一時間就去規劃,依據需求再決定於 Kernel Mode 或 User Mode 之下實作就可以了。


【Task Context Switching/Scheduler】

除了 Context Switching 會無可避免的消耗 CPU 資源之外,在 Task 控制的規劃上,有著兩種模式,可視 OS 用途而定:
  1. Preemptive
  2. Non-preemptive

Preemptive 即為強佔式〔強取式〕核心,在 Scheduler 被觸發時,優先權高的 Task 將會搶去優先權低的排隊位置,取得先執行的權力。此方式的系統回應快,對於 Realtime OS 是非常必要的技術。Linux 在 2.6 版後就加入了這項技術,以提升需要 Realtime 的多媒體效能。

Non-preemptive 則是無論如何,每個 Task 用完自己的時間後交出使用權利,照順序一個個 Task 執行,對於優先權高的 Task 來說也不能不遵守此規則,要等到自己的時間到來才可以執行,故可能造成 Task 無法即時回應使用者的需求。此種核心適合需平穩執行與資源平均分配的系統,如 Server 用途就屬此類。

至於工作排程器(Task Scheduler) 的設計細節包含兩種方法:
  1. Priority Scheduling
  2. Round-robin Scheduling/Time Slicing

Priority Scheduling 方法是依照 Task Priority 的大小為順序,依序切換執行 Task。

而為避免 Task 的執行時間過長,就出現了 Round-robin Scheduling/Time Slicing 方法,使用時間切割的方式,讓每個 Task 執行一段時間就交出執行權,如此便可實現 Tasks 同時執行的多工錯覺。當然,也可更進一步控制執行時間片斷的長短,使優先權較高的 Task 有較充裕的時間可使用。

關於更多 Sheduler 的實作,在之前提到過的 [OrzMicroKernel task.asm] 可以找到一些簡潔又基本的設計。


【IPC (Inter Process Communication)】

在多工的系統中,Tasks 有如同時在執行一般,所以有很多機會協同工作。由於 Task 之間會互相傳遞資訊,需要 IPC 機制來達成這任務,IPC 通常分為兩個部份:
  1. Message Pipe (不具名的管道)
  2. Message Port (具名的管道)

Message Pipe 是一個不需要具名的通訊管道,將資料排隊存在一個『環狀緩充佇列』,然後接收端會以 FIFO(先進先出) 的方式讀出。而 Message Port 是一個需要指定收件人的通訊管道,有如寄信件一般。


【Semaphore】

同樣也是 Task/Thread 在做協同工作時必要的功能,Semaphore 使資源能夠共享而不打架。

Semaphore 的實作是建立一個計數器開關,預設值賦予 1。計數器的值大於 0 代表無人使用和等待,小於等於 0 則代表有人在等待資源。每當 Task/Thread 求資源時,先減一然後檢查計數器的值,若大於等於 0 就取用資源,若是小於 0 則進入等待區;用完資源後,則將計數器加一並叫醒下一個正在等待區排隊的程式。

用 C 語言表示其邏輯,大致像這樣:

/* 取用 semaphore */
sem--;
if (sem<0)
pend(); /* 進入等待區 */

/* 釋放 semaphore */
sem++;
if (sem<=0)
post(); /* 叫醒下一個正在等待的程式 */



後記

過去總認為,一個 Kernel 就是要從 Booting 開始著手,一步步解決 A20 、 protect mode 、IRQ、Memory 等低階的問題,再開始實作 Task Sheduler 等更進階的部份。事實上,由於低階的部份較不直覺,通常會花不少時間在研究其原理,因此在實用機制上的設計,反到是從未注重過。這也或許是市面上的書籍和 Open Source Community 對於 Coding OS Kernel 都強調從頭開始實作所致,讓從零開始的章節反而成為是實作過程的重點。

留言

  1. Hi,我最近在尋找如何將micro kernel 嵌入
    一般OS(Linux, windows....)中, 構思有如
    VM, 但是是強佔中斷向量表, 所以可能一個OS屬於
    Time trigger基礎的OS, 一個則是事件中斷
    基礎OS, 你有什麼 點子 呢??

    回覆刪除
  2. 有趣的點子, 請問是有什麼特殊的用途要使用這樣 OS?

    由於要在一個 正在運作的 OS 中搶走整個中斷是有所困難的, 比較可行的做法是實作從硬體端就實作, 目前或許可行的就是 VM 的方法.

    當然, 近年來的 EFI BIOS, 或許可以達到你想要的需求. 實作 EFI Extension, 讓 BIOS 層直接在觸發時機, 替你做 OS 的切換和強佔.

    回覆刪除

張貼留言

這個網誌中的熱門文章

有趣的邏輯問題:是誰在說謊

Web 技術中的 Session 是什麼?

淺談 USB 通訊架構之定義(二)

淺談 USB 通訊架構之定義(一)

Reverse SSH Tunnel 反向打洞實錄