摘要：該文闡述如何根據(jù)操作系統(tǒng)的原理和x86CPU的運(yùn)行機(jī)制設(shè)計(jì)并實(shí)現(xiàn)一個(gè)簡單的操作系統(tǒng)內(nèi)核，并詳細(xì)描述了其中內(nèi)存管理，進(jìn)程管理，以及磁盤文件系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)方法。該系統(tǒng)的實(shí)現(xiàn)將有利于從微觀上觀察操作系統(tǒng)的行為特征，更好地學(xué)習(xí)、理解和實(shí)踐微內(nèi)核機(jī)制，也有利于對(duì)Linux內(nèi)核的研究學(xué)習(xí)。

關(guān)鍵詞：操作系統(tǒng)；內(nèi)核；進(jìn)程調(diào)度；文件系統(tǒng)；x86

中圖分類號(hào)：TP316.1文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)30-0648-03

The Design of A Multitask Real-Time Operating System Base on x86

ZHANG Chen

(School of Computer Science and Technology， China University of Mining and Technology， Xuzhou 221008， China)

Abstract: The article described how to design a simple operating system kernel base on the principle of operating system and the mechanism of X86， and explain the design and implament of the part of memory management， process management and hard disk file system in detail. Learning the implament of this operating system if good of looking into the microcosmic character of the operating system， learning understanding and carry out kernel mechanism， and it's also can vail the research of Linux kernel.

Key words: operating system; kernel; process schedule; file system; x86

1 引言

隨著計(jì)算機(jī)科學(xué)技術(shù)的發(fā)展，計(jì)算機(jī)在各個(gè)領(lǐng)域不斷普及，作為計(jì)算機(jī)軟件核心的計(jì)算機(jī)操作系統(tǒng)始終扮演著重要的角色。由于起步較晚，國內(nèi)對(duì)操作系統(tǒng)的研究水平始終落后于國外發(fā)達(dá)國家，并且在高等院校的操作系統(tǒng)課程中也都是重理論輕實(shí)踐，由于缺乏實(shí)踐，大多數(shù)學(xué)生對(duì)操作系統(tǒng)的理論都掌握的不深刻。文中講述了一個(gè)基于Intel x86系列CPU的微型多任務(wù)多控制臺(tái)操作系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)的方法，該操作系統(tǒng)從軟盤啟動(dòng)，并且具有簡單而有效的內(nèi)存管理，進(jìn)程調(diào)度，中斷處理，I/O控制，文件系統(tǒng)等操作系統(tǒng)必備的核心部分，希望這些內(nèi)容能給廣大操作系統(tǒng)愛好者一些參考，通過實(shí)踐來加深對(duì)操作系統(tǒng)理論的理解，同時(shí)也可以作為研究學(xué)習(xí)Linux源代碼的一個(gè)鋪路石。

2 設(shè)計(jì)環(huán)境和總體結(jié)構(gòu)

2.1 設(shè)計(jì)環(huán)境

裝有Linux的PC機(jī)（含有NASM， GCC等開發(fā)工具）；

虛擬機(jī)軟件，如VMWARE，創(chuàng)建一臺(tái)x86環(huán)境的虛擬機(jī)；

操作系統(tǒng)調(diào)試軟件Bochs；

鏡像管理工具，如WinImage；

扇區(qū)讀寫工具（用來寫軟盤的引導(dǎo)扇區(qū)）；

虛擬機(jī)的使用可以使編譯鏈接出的代碼立即在虛擬機(jī)上運(yùn)行出來，對(duì)于操作系統(tǒng)的開發(fā)來說可以大大的提高效率。

2.2 總體結(jié)構(gòu)

一個(gè)操作系統(tǒng)應(yīng)該具備基本的引導(dǎo)程序，以及內(nèi)存分配回收，進(jìn)程調(diào)度，中斷處理，I/O控制，文件系統(tǒng)等功能。總體結(jié)構(gòu)見圖1。

3 操作系統(tǒng)關(guān)鍵部分的設(shè)計(jì)與實(shí)現(xiàn)

3.1 引導(dǎo)程序

當(dāng)計(jì)算機(jī)電源被打開時(shí)，它會(huì)先進(jìn)行加電自檢，然后尋找啟動(dòng)盤，這里我們將啟動(dòng)盤設(shè)置為了軟驅(qū)。那么計(jì)算機(jī)就會(huì)檢查軟盤的0面0磁道1扇區(qū)，如果發(fā)現(xiàn)它以0Xaa55結(jié)束的話，那么BIOS認(rèn)為它是一個(gè)引導(dǎo)扇區(qū)，我們操作系統(tǒng)的引導(dǎo)程序就在里邊。一旦BIOS發(fā)現(xiàn)了引導(dǎo)程序，就會(huì)將這512字節(jié)的內(nèi)容裝載到內(nèi)存的0000：7c00處，然后跳轉(zhuǎn)到0000：7c00處將控制權(quán)徹底的交給我們的引導(dǎo)程序。所以在引導(dǎo)程序的匯編代碼中要有這么一句：

Org 07c00

它告訴編譯器，將來我們的這段程序要被加載到內(nèi)存的7c00處。

引導(dǎo)扇區(qū)的容量是有限的，所以在此引導(dǎo)程序的主要功能就是利用軟盤的FAT12分區(qū)表提供的信息來查找loader文件，并將其逐個(gè)扇區(qū)讀出，加載到指定的內(nèi)存地址，最后跳轉(zhuǎn)到該地址，將控制權(quán)交給Loader，由Loader來完成啟動(dòng)保護(hù)模式和加載內(nèi)核文件的工作

3.2 內(nèi)存管理

本系統(tǒng)的頁式內(nèi)存管理是建立在x86 CPU 保護(hù)模式下的頁式存儲(chǔ)的基礎(chǔ)上的。在80386下，頁的大小是固定的4KB，所以本系統(tǒng)的頁面大小也是同樣的。

本系統(tǒng)的分頁機(jī)制使用兩級(jí)頁表，第一級(jí)叫頁目錄，存儲(chǔ)在一個(gè)物理頁中，每個(gè)表項(xiàng)4字節(jié)長，每個(gè)表項(xiàng)對(duì)應(yīng)著第二級(jí)的一個(gè)頁表，第二級(jí)的每一個(gè)頁表有1024個(gè)表項(xiàng)，每一個(gè)表項(xiàng)對(duì)應(yīng)一個(gè)物理頁。頁目錄表項(xiàng)簡稱PDE(Page Directory Entry)， 頁表的表項(xiàng)簡稱PTE(Page Table Entry)。

進(jìn)行轉(zhuǎn)換的時(shí)候，先是從由寄存器CR3指定的頁目錄中根據(jù)線性地址的高10位得到頁表地址，然后在頁表中根據(jù)線性地址的第12~21位的得到物理頁首地址，將這個(gè)首地址加上線性地址低12位便得到了物理地址。分頁機(jī)制是否生效的開關(guān)位于cr0的最高位PG位，如果PG=1，則分頁機(jī)制生效。所以當(dāng)我們準(zhǔn)備好了頁目錄表和頁表，并將cr3指向頁目錄表之后，只需要PG位分頁機(jī)制就可以正常工作了。

具體工作原理如圖2。

在Loader加載內(nèi)核之前，它要首先建立好保護(hù)模式，然后按照上述方法建立頁表。在創(chuàng)建頁表時(shí)，為了減小頁表的體積，首先要通過BIOS的15號(hào)中斷獲得內(nèi)存的詳細(xì)信息，可用的內(nèi)存地址范圍等， 然后根據(jù)此信息計(jì)算出所需的PDE和PTE的個(gè)數(shù)，使用循環(huán)的方式來建立正好可以映射所有物理內(nèi)存的頁表。

當(dāng)分頁機(jī)制開啟時(shí)，處理器把任務(wù)中的虛擬地址轉(zhuǎn)換成物理地址，步驟如下：

1) 查找段選擇子在GDT 或 LDT 中的描述符，進(jìn)行權(quán)限檢查，看看能否訪問；

2) 以描述符中的基址相加頁目錄基址得到一個(gè)線性地址；

3) 在頁表中索引虛擬地址所對(duì)應(yīng)的頁表項(xiàng)，得到頁地址；

4) 查找偏移得到實(shí)際物理地址。

如果實(shí)際物理頁不存在（可能交換到硬盤中去了），則引發(fā)異常，可以在這個(gè)異常里面做想要做的事情。

3.3 進(jìn)程管理

進(jìn)程是操作系統(tǒng)中的一個(gè)重要概念，多任務(wù)也是現(xiàn)代操作系統(tǒng)的基本特征。因此進(jìn)程調(diào)度是操作系統(tǒng)非常重要的一部分。

3.3.1 進(jìn)程的創(chuàng)建

每個(gè)進(jìn)程都有自己的堆棧段，數(shù)據(jù)段，以及代碼段，還有進(jìn)程ID，優(yōu)先級(jí)，進(jìn)程名等信息。所以需要一個(gè)數(shù)據(jù)結(jié)構(gòu)來管理和保存這些信息，在本系統(tǒng)中使用的是進(jìn)程表數(shù)據(jù)結(jié)構(gòu)。進(jìn)程表不僅有保存上述信息的功能，還具有保存現(xiàn)場的作用。當(dāng)一個(gè)進(jìn)程被掛起時(shí)，所有通用寄存器的內(nèi)容都被保存到進(jìn)程表的相應(yīng)表項(xiàng)中，以便進(jìn)程下次被調(diào)度時(shí)能夠順利回復(fù)現(xiàn)場，繼續(xù)以前的狀態(tài)運(yùn)行。進(jìn)程表的定義如圖3。

上述兩個(gè)結(jié)構(gòu)中，STACK_FRAME是用來在進(jìn)程切換的時(shí)候保存現(xiàn)場的一個(gè)數(shù)據(jù)結(jié)構(gòu)。PROCESS則是用來保存一個(gè)進(jìn)程的各種必須的信息。

當(dāng)一個(gè)進(jìn)程被新創(chuàng)建時(shí)，首先創(chuàng)建一個(gè)PROCESS結(jié)構(gòu)，然后初始化它的各類必須的信息，其中最重要的是指定程序的入口地址和初始化程序自己的堆棧；最后將其加入到進(jìn)程表數(shù)組以及就緒隊(duì)列中，等待下一次進(jìn)程調(diào)度時(shí)被調(diào)度運(yùn)行。

3.3.2 進(jìn)程的調(diào)度

本系統(tǒng)采用的是優(yōu)先級(jí)調(diào)度法，調(diào)度發(fā)生在每次時(shí)鐘中斷處理的時(shí)候。每當(dāng)調(diào)度程序運(yùn)行時(shí)，就檢查當(dāng)前進(jìn)程的優(yōu)先級(jí)和就緒隊(duì)列中進(jìn)程的優(yōu)先級(jí)，將優(yōu)先級(jí)最大的進(jìn)程調(diào)度出來運(yùn)行，如果不是當(dāng)前進(jìn)程，則將當(dāng)前進(jìn)程被掛起放入就緒隊(duì)列中。

由于大部分進(jìn)程都是運(yùn)行在用戶態(tài)的，而進(jìn)程調(diào)度程序是運(yùn)行在核心態(tài)的，所以進(jìn)程在不同特權(quán)級(jí)之間切換的時(shí)候不僅要保存自己的寄存器信息，同時(shí)還要涉及到在用戶堆棧和核心堆棧之間的切換，這時(shí)要從TSS中獲得核心棧的ss以及esp并加載（TSS是在之前初始化好的），以使進(jìn)程調(diào)度程序能夠正常工作在核心態(tài)下。

在進(jìn)行進(jìn)程調(diào)度時(shí)，調(diào)度程序?qū)γ總€(gè)進(jìn)程的優(yōu)先級(jí)進(jìn)行判斷，選出當(dāng)前優(yōu)先級(jí)最高的進(jìn)程，先將其優(yōu)先數(shù)減1，然后將其STACK_FRAME的地址放入esp，然后使用pop命令恢復(fù)現(xiàn)場，繼續(xù)執(zhí)行該程序。每次進(jìn)程調(diào)度都是同樣的處理過程，直到所有進(jìn)程的優(yōu)先級(jí)都為0時(shí)，再將每個(gè)進(jìn)程恢復(fù)為原來的優(yōu)先級(jí)數(shù)，反復(fù)循環(huán)，直到進(jìn)程結(jié)束為止。

3.3.3 進(jìn)程結(jié)束

當(dāng)進(jìn)程結(jié)束時(shí)微內(nèi)核負(fù)責(zé)回收其占用的系統(tǒng)資源。具體體現(xiàn)在，根據(jù)進(jìn)程任務(wù)控制塊信息釋放掉占用的相關(guān)資源，主要是地址空間的數(shù)據(jù)結(jié)構(gòu)以及存于端口上的尚未處理的消息。

3.4 I/O控制

I/O控制是使系統(tǒng)和用戶溝通的一個(gè)重要部分。在這個(gè)部分，本系統(tǒng)實(shí)現(xiàn)了多個(gè)控制臺(tái)同時(shí)工作的效果，用戶可以使用快捷鍵來在不同控制臺(tái)之間進(jìn)行切換，輸入命令，運(yùn)行程序。并且定義了一個(gè)printf函數(shù)通過系統(tǒng)調(diào)用write進(jìn)行輸出，所有進(jìn)程的輸出都是通過該函數(shù)實(shí)現(xiàn)的。

在輸入的處理中，鍵盤中斷處理程序首先檢查鍵盤上8042芯片傳來的鍵碼，判斷是普通字符還是功能鍵，是按下還是彈起狀態(tài)，然后查找對(duì)應(yīng)的鍵碼表，將對(duì)應(yīng)的字符放入輸入緩沖區(qū)，等待相應(yīng)進(jìn)程讀取。鍵盤中斷處理程序還處理了多種組合鍵。

顯示輸出是簡單的直接寫顯存，開機(jī)默認(rèn)的顯示模式為80*25文本模式，在這種模式下，顯存地址0xB8000~0xBFFF，共計(jì)32KB，每2字節(jié)代表一個(gè)字符。這樣的操作方式優(yōu)點(diǎn)是簡單便捷，而且通過將輸出函數(shù)編寫成系統(tǒng)調(diào)用的形式，可以避免對(duì)顯存的危險(xiǎn)操作。多控制臺(tái)的設(shè)計(jì)是簡單的將顯存分成多個(gè)區(qū)域，每個(gè)區(qū)域?qū)?yīng)于一個(gè)控制臺(tái)，在切換控制臺(tái)時(shí)只要把顯示區(qū)域的首地址設(shè)為當(dāng)前控制臺(tái)對(duì)應(yīng)顯存區(qū)域的首地址就可以了。每個(gè)控制臺(tái)的結(jié)構(gòu)中有一個(gè)記錄當(dāng)前光標(biāo)位置的變量，切換到該控制臺(tái)的時(shí)候自動(dòng)將光標(biāo)定位到該變量記錄的相應(yīng)位置。這些定位操作都可以通過操作CRT Controller Data Registers 來實(shí)現(xiàn)。

3.5 文件系統(tǒng)

文件系統(tǒng)涉及到了硬盤的管理。硬盤最小的管理單位是扇區(qū)，每個(gè)扇區(qū)512字節(jié)。柱面也稱為磁軌，通常硬盤每柱面含有64扇區(qū)。有兩種方式定位訪問磁盤。一種是CHS模式（Cylinder， Head， Sector），它反映了磁盤的物理結(jié)構(gòu)。在CHS模式下，磁盤容量最大可表示為：柱面數(shù)*每柱面扇區(qū)數(shù)*磁頭數(shù)*512。另一種硬盤訪問模式叫LBA（Linear Block Addressing）：線性塊尋址模式），它是物理硬盤的邏輯尋址方式。和線性內(nèi)存尋址一樣，LBA用線性地址來定位扇區(qū)（這樣，柱面和磁頭就不會(huì)用到了）。這種方式非常簡單，但是驅(qū)動(dòng)使用的是CHS模式，所以需要進(jìn)行轉(zhuǎn)換。

硬盤提供了多個(gè)端口號(hào)，端口0x1f7用于讀硬盤狀態(tài)或者寫操作命令。寫0x1f7端口常用的命令字如下：

#define HD_READ 0x20// 讀硬盤

#define HD_WRITE0x30// 寫硬盤

硬盤的第一個(gè)扇區(qū)必須包含硬盤分區(qū)表。這個(gè)分區(qū)表從第一個(gè)扇區(qū)的0x1be偏移開始，長度是64字節(jié)。最多可以包含4個(gè)分區(qū)（本文不考慮邏輯分區(qū)，都使用主分區(qū)）。這4個(gè)分區(qū)的相對(duì)偏移分別為0x1be， 0x1ce， 0x1de， 0x1fe，第一個(gè)扇區(qū)的最后兩個(gè)字節(jié)必須是0xaa55。

每個(gè)分區(qū)項(xiàng)的格式如下：

Byte0引導(dǎo)標(biāo)識(shí)Bytes 1-3CHS 信息

Byte4分區(qū)類型Bytes 5-7 CHS 信息

Bytes 8-11該分區(qū)的起始扇區(qū)號(hào)ytes 12-16 扇區(qū)數(shù)量

第0個(gè)字節(jié)是引導(dǎo)標(biāo)識(shí)，如果值為0x80標(biāo)識(shí)可引導(dǎo)。對(duì)于一塊硬盤來說，只有一個(gè)分區(qū)是可以引導(dǎo)的。第4個(gè)字節(jié)定義分區(qū)類型，例如FAT32， NTFS， ext2等。由于本系統(tǒng)使用LBA方式，所以不需要具體解釋字節(jié)1~3和字節(jié)5~7的具體格式。

首先我們根據(jù)上述信息先編輯好一個(gè)大小為512的字符數(shù)組（本系統(tǒng)采用的是自定義的FST_FS分區(qū)類型），然后通過端口0x1f7寫到第一個(gè)扇區(qū)中，這樣引導(dǎo)扇區(qū)就建立好了，這里出于簡單的原則，我們僅建立了一個(gè)128MB的主分區(qū)和一個(gè)32MB的交換分區(qū)，交換分區(qū)留在實(shí)現(xiàn)虛擬內(nèi)存的時(shí)候使用，但是本系統(tǒng)目前還未實(shí)現(xiàn)該功能。

分區(qū)建立好了，下面就是建立文件系統(tǒng)的工作了。本系統(tǒng)采用了類似于Linux的節(jié)點(diǎn)管理方法。操作系統(tǒng)中的所有文件都有一個(gè)獨(dú)一無二的節(jié)點(diǎn)編號(hào)，如果有了這個(gè)節(jié)點(diǎn)號(hào)，就可以找到對(duì)應(yīng)的文件。最開始的兩個(gè)文件永遠(yuǎn)是\".\" 和 \"..\"，表示當(dāng)前目錄和上級(jí)目錄。另外為了指定從哪里搜索節(jié)點(diǎn)號(hào)，我們?cè)诖疟P中組織所有節(jié)點(diǎn)為數(shù)組，并由節(jié)點(diǎn)號(hào)來索引節(jié)點(diǎn)數(shù)組。\"/\"沒有父節(jié)點(diǎn)，所以就放在節(jié)點(diǎn)數(shù)組的第一項(xiàng)。

如圖4，i_block的前6個(gè)整形表示文件的前6個(gè)扇區(qū)號(hào)，第七個(gè)表示二級(jí)指針扇區(qū)，它指向一個(gè)扇區(qū)，這個(gè)扇區(qū)里面存放文件后續(xù)部分使用扇區(qū)號(hào)，由512/4=128 扇區(qū)，表示文件接下來使用的128個(gè)扇區(qū)。128*512=64K。i_block數(shù)組的最后一個(gè)表示三級(jí)指針，最大可以表示(512/4)*(512/4)*512=8MB字節(jié)。所以這個(gè)i_block數(shù)組最大可以表示3k+64K+8M文件的大小。

為了高效管理文件系統(tǒng)資源，我們使用硬盤塊位圖用來存放硬盤使用信息，節(jié)點(diǎn)位圖用來保存節(jié)點(diǎn)分布信息。這兩項(xiàng)信息都存放在每個(gè)分區(qū)的超級(jí)塊中。同時(shí)定義幾個(gè)系統(tǒng)調(diào)用來負(fù)責(zé)節(jié)點(diǎn)和扇區(qū)的分配和回收。初始化文件系統(tǒng)時(shí)要將啟動(dòng)扇區(qū)，超級(jí)塊，兩個(gè)位圖所占的空間都設(shè)置好。

現(xiàn)在還沒有根目錄，首先使用分配扇區(qū)函數(shù)來分配空間并使用DIR_ENTRY和INODE結(jié)構(gòu)建立根節(jié)點(diǎn)。根節(jié)點(diǎn)點(diǎn)總是使用節(jié)點(diǎn)0，以方便查找文件時(shí)定位根目錄。同時(shí)將\".\" 和 \"..\"寫入到根目錄下，并將它們指向根目錄。這樣一個(gè)空的文件系統(tǒng)就建立好了。以后想建立或者刪除文件或文件夾都可以遵循類似的步驟，這里就不再贅述了。

4 結(jié)束語

至此，本文已經(jīng)詳細(xì)介紹了一個(gè)簡單的基于x86平臺(tái)操作系統(tǒng)的內(nèi)存管理，進(jìn)程調(diào)度，I/O控制，文件系統(tǒng)等重要部分的設(shè)計(jì)和實(shí)現(xiàn)，我們也看到了一個(gè)多任務(wù)多控制臺(tái)操作系統(tǒng)的雛形。由于本操作系統(tǒng)主要是為了演示和學(xué)習(xí)操作系統(tǒng)的底層機(jī)制，所以很多地方都比較簡單而且缺乏效率，不過該系統(tǒng)已經(jīng)具備了完善的中斷處理機(jī)制以及系統(tǒng)調(diào)用等機(jī)制，可以方便的對(duì)其進(jìn)行進(jìn)一步的擴(kuò)展。

參考文獻(xiàn)：

[1] Andrew S Tanenbaum， Albert SWoodhull. 操作系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[M]. 2版. 王鵬， 譯. 北京：電子工業(yè)出版社，1998.

[2] 趙炯. Linux內(nèi)核0.11完全注釋[M]. 北京：機(jī)械工業(yè)出版社， 2005.

[3] 于淵. 自己動(dòng)手寫操作系統(tǒng)[M]. 北京：電子工業(yè)出版社， 2005.

[4] 苑勛， 王琰， 黃利萍. 一個(gè)微型操作系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)[J]. 沈陽工業(yè)學(xué)院學(xué)報(bào)，2001(2):30-34.

[5] 湯子瀛. 計(jì)算機(jī)操作系統(tǒng)[M]. 西安：西安電子科技大學(xué)出版社， 1996.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文