2008年2月22日 星期五

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

Standard
極慚愧的是,這次寒假的計劃並未完全如期完成,實作 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 都強調從頭開始實作所致,讓從零開始的章節反而成為是實作過程的重點。