MTX操作系統(tǒng)內(nèi)核與啟動流程分析

任振強

(國家知識產(chǎn)權(quán)局專利局專利審查協(xié)作天津中心，天津 300304)

0 引言

MTX是美國華盛頓大學(xué)電子工程與計算機科學(xué)系教授WANG K C于2015年發(fā)布的一款小型操作系統(tǒng)[1]，該系統(tǒng)基于Intel x86體系結(jié)構(gòu)，具有結(jié)構(gòu)標(biāo)準(zhǔn)的類Unix內(nèi)核，可在x86的實模式下實現(xiàn)內(nèi)存管理，進程控制，進程調(diào)度，線程、進程間消息、管道、中斷處理，輸入輸出設(shè)備驅(qū)動等典型的UNIX/Linux內(nèi)核[2]功能。此外，MTX還支持對稱多處理器結(jié)構(gòu)(SMP)，并使用了與Linux兼容的EXT2文件系統(tǒng)；其所有功能模塊均能在編譯時進行裁剪選擇，編譯后內(nèi)核體積可以控制在幾十甚至十幾KB。而且由于MTX內(nèi)核模塊間耦合度極低，因此可以自由調(diào)整進程調(diào)度功能以滿足實時性要求。整體而言，MTX操作系統(tǒng)具有高度的靈活性和較低的學(xué)習(xí)門檻，非常適合于課堂教學(xué)和二次開發(fā)。

目前主流的類UNIX操作系統(tǒng)均不在實模式下運行[3-4]，國內(nèi)開發(fā)者雖然對UNIX/Linux內(nèi)核設(shè)計原理較熟悉，但對MTX的實現(xiàn)方案并不了解。因此本文選擇對MTX內(nèi)核的實現(xiàn)代碼進行研究，重點分析靠近底層硬件的進程切換和系統(tǒng)調(diào)用代碼，并且對系統(tǒng)引導(dǎo)程序設(shè)計要點進行總結(jié)，整體通過進程視角對MTX操作系統(tǒng)進行初步分析。

1 內(nèi)核編譯

MTX操作系統(tǒng)內(nèi)核在Linux環(huán)境下使用BCC(Bruce’s C Compiler)Cross-Compiling Package進行編譯和鏈接。MTX使用BCC而不是GCC進行編譯，因為BCC不僅能編譯生成8086兼容的16位匯編代碼，還可以基于單一內(nèi)存段(one-segment memory)模型對代碼進行編譯。

工作于實模式的CPU以64 KB分段的形式訪問物理內(nèi)存的最低1 MB地址，CPU設(shè)置了4個16位段寄存器CS、DS、SS、ES，分別用于標(biāo)記代碼(Code)段、數(shù)據(jù)(Data)段、棧(Stack)段和附加(Extra)段。BCC編譯生成的CS、DS和SS完全重合，相當(dāng)于只有一個段，簡化了內(nèi)存模型，方便了程序的初始化。由于只有一個段，程序可以被載入內(nèi)存中任意一個可用段中運行，加載和啟動更為靈活。

2 內(nèi)核引導(dǎo)

內(nèi)核作為MTX操作系統(tǒng)的第0進程，其加載和啟動方式有一定特殊性，同時又影響著其他進程的加載和運行。

2.1 引導(dǎo)程序的加載

計算機硬件啟動后首先將BIOS載入內(nèi)存運行，BIOS完成自檢并尋找可啟動設(shè)備進行啟動。具體而言，BIOS首先將啟動設(shè)備的起始512 B載入內(nèi)存地址(0x0000,0x7C00)，也就是物理地址0x07C00，隨后跳轉(zhuǎn)到該內(nèi)存地址運行指令。該起始512 B即為引導(dǎo)程序。完整的引導(dǎo)程序往往大小會超過512 B，因此當(dāng)計算機運行該512 B的代碼時，需要完成以下步驟：將引導(dǎo)程序的剩余部分載入內(nèi)存運行，尋找操作系統(tǒng)內(nèi)核并將其載入內(nèi)存，最后運行操作系統(tǒng)內(nèi)核的起始代碼。

在系統(tǒng)引導(dǎo)的過程中，引導(dǎo)程序會將其載入段地址為0x1000的內(nèi)存段中，隨后引導(dǎo)程序會跳轉(zhuǎn)到0x1000段執(zhí)行操作系統(tǒng)內(nèi)核代碼。之所以將內(nèi)核載入到0x1000段，一是為了給內(nèi)核足夠的內(nèi)存空間，二是為了方便進程管理和系統(tǒng)調(diào)用。MTX將第 1個用戶程序加載到內(nèi)存0x2000段、第 2個用戶程序加載到0x3000段，并以此類推。當(dāng)用戶程序執(zhí)行系統(tǒng)調(diào)用后，CPU將返回0x1000段運行內(nèi)核代碼。

2.2 引導(dǎo)程序分析

引導(dǎo)程序的前512 B已經(jīng)被加載到內(nèi)存中，該512 B程序運行時不能覆蓋自身，因此通常將完整的引導(dǎo)程序加載到另外的內(nèi)存地址。MTX的選擇與早期Linux內(nèi)核zImage的引導(dǎo)程序相同[5]，即內(nèi)存的0x9000段。

引導(dǎo)程序運行時沒有任何庫可用，只能使用BIOS中斷INT13提供的讀寫功能。當(dāng)完整的引導(dǎo)程序加載到0x9000段之后，執(zhí)行以下指令：

jmpi start,0x9000

start:

mov ax,cs

mov ds,ax

mov ss,ax

mov es,ax

mov sp,8192

call _main

jmpi指令將代碼段寄存器設(shè)置為0x9000后執(zhí)行start處的代碼。由于BCC編譯生成的CS、DS和SS段重合，因此該段代碼使用4個mov語句將所有段寄存器都設(shè)置為0x9000，之后通過“mov sp,8192”將棧指針設(shè)在偏移量為8KB的地址上，為后面的main函數(shù)提供了足夠的?？臻g，隨后調(diào)用內(nèi)核的main函數(shù)?？梢姡捎谝龑?dǎo)程序是由自己的前512 B代碼將自身載入內(nèi)存，因此也必須自己為自己設(shè)置好所有的寄存器狀態(tài)。

此時操作系統(tǒng)尚未載入內(nèi)存中，因此讀磁盤寫內(nèi)存的I/O工作依然要通過BIOS中斷INT13來完成。main函數(shù)在EXT2文件系統(tǒng)中尋找到MTX內(nèi)核文件，并將其載入內(nèi)存的0x1000段。從main函數(shù)返回后，引導(dǎo)程序執(zhí)行“jmpi 0,0x1000”，該指令將CPU的代碼段寄存器設(shè)置為內(nèi)核加載地址0x1000，并運行段內(nèi)第一條代碼。內(nèi)核正式啟動。

3 MTX內(nèi)核的進程實現(xiàn)

MTX內(nèi)核main函數(shù)的部分工作可簡化為如下算法：

while (1) {

if (readyQueue)

tswitch();

}

上述代碼只要readyQueue不為空則運行tswitch進行進程切換。readyQueue中保存著所有可運行的進程，tswitch從readyQueue中取出一個進程并將上下文(context)切換為該進程的上下文。完成切換之后，CPU將運行與main函數(shù)完全無關(guān)的另一個進程。如果其他進程運行tswitch()后又切換回上述內(nèi)核進程，則此時CPU繼續(xù)運行tswitch之后的下一條語句。

要理解進程切換，必須對進程的數(shù)據(jù)結(jié)構(gòu)進行了解。

3.1 進程控制塊

操作系統(tǒng)使用一個進程代表一個程序的執(zhí)行，內(nèi)核通常使用一個進程控制塊(Process Control Block，PCB)代表一個進程[6]。MTX的進程控制塊具有如下結(jié)構(gòu)：

typedef struct proc {

struct proc *next;

int *ksp;

…

int kstack[SSIZE];

} PROC

內(nèi)核使用全局變量PROC proc[NPROC]保存系統(tǒng)中所有的進程，因此系統(tǒng)最多可以建立NPROC個進程。main函數(shù)在運行while(1)循環(huán)之前完成以下步驟：初始化proc[]數(shù)組，設(shè)置好proc[0]并將其關(guān)聯(lián)給內(nèi)核自身，建立第一個程序的PROC結(jié)構(gòu)proc[1]，并將proc[1]加入readyQueue中。因此第一次運行while(1)循環(huán)時，判斷readyQueue不為空后，系統(tǒng)切換到proc[1]進程開始運行內(nèi)核以外的第一個程序。

PROC中的next指針指向下一個進程，進程因此可以被放入進程隊列中，如前文中所述的readyQueue。ksp用于存放內(nèi)核的棧指針；進程的內(nèi)核棧kstack則位于PROC結(jié)構(gòu)的最尾端。

PROC中next、ksp和kstack三個變量的順序至關(guān)重要：next是struct proc的第1項，ksp是第2項，kstack是最后一項。當(dāng)running保存當(dāng)前進程PROC結(jié)構(gòu)的內(nèi)存地址時，running+2為該PROC的ksp的地址，而running+sizeof(PROC)正好是其kstack數(shù)組中最后一項的內(nèi)存地址，也就是空棧棧頂?shù)奈恢谩?/p>

3.2 進程切換

進程切換的過程非常簡單：將當(dāng)前進程的上下文存入當(dāng)前進程的PROC，從另一個PROC中取出另一進程的上下文，最后用新進程的上下文設(shè)置CPU，從而使CPU運行新進程。MTX操作系統(tǒng)用全局變量PROC *running指向當(dāng)前運行的進程。tswitch的代碼如下：

_tswitch:

SAVE:

push ax

push bx

push cx

push dx

push bp

push si

push di

pushf

mov bx,_running

mov 2[bx],sp

FIND: call _scheduler

RESUME:

mov bx,_running

mov sp,2[bx]

popf

pop di

pop si

pop bp

pop dx

pop cx

pop bx

pop ax

ret

SAVE過程保存上下文，push和pushf語句將MTX用到的CPU寄存器值壓入running的kstack棧中，再將running的值(即當(dāng)前進程的PROC結(jié)構(gòu)的地址)賦給bx，由之前的討論可知bx+2即為該PROC中ksp變量的地址，因此“mov 2[bx],sp”語句將棧頂?shù)刂繁４嬖趉sp變量中。至此，當(dāng)前進程的上下文被保存至running的kstack棧當(dāng)中。

與SAVE對應(yīng)的RESUME負(fù)責(zé)對進程上下文的恢復(fù)，其完全是SAVE的逆向過程。保存和恢復(fù)之間的是進程調(diào)度函數(shù)scheduler。scheduler將當(dāng)前進程的PROC放入readyQueue，從readyQueue中取出一個新PROC，并將running指向該PROC。而RESUME函數(shù)通過彈棧設(shè)置CPU寄存器，從而設(shè)置好新進程的上下文。

由上述代碼還可以看出，MTX的進程調(diào)度功能由scheduler完成，其不與系統(tǒng)其他部分耦合，可單獨更換以滿足實時性要求。

3.3 進程建立和系統(tǒng)調(diào)用

MTX內(nèi)核的main函數(shù)在初始階段建立第一個用戶程序的PROC結(jié)構(gòu)proc[1]，tswitch()之后系統(tǒng)運行該程序。MTX內(nèi)核建立新進程的過程被稱為fork，MTX內(nèi)核中的函數(shù)原型為PROC *kfork(char *filename)，kfork可以通過filename參數(shù)指定程序的路徑，并返回該程序?qū)?yīng)的PROC的指針。例如，內(nèi)核可在初始階段運行kfork(“/bin/shell”)，將shell程序作為第一個程序，以允許用戶通過shell執(zhí)行命令。

與Linux相同，MTX將內(nèi)核所在的內(nèi)核空間(Kernel space)與用戶程序所在的用戶空間(User space)分離。MTX的內(nèi)核加載至內(nèi)存0x1000段，proc1程序加載到0x2000段。因此0x1000段為內(nèi)核空間，0x2000段為用戶空間。操作系統(tǒng)的核心功能由內(nèi)核程序完成，當(dāng)運行于User space的用戶程序需要使用核心功能時，其通過系統(tǒng)調(diào)用運行相應(yīng)的內(nèi)核函數(shù)。系統(tǒng)調(diào)用被稱為System call或syscall[7]。當(dāng)用戶程序運行系統(tǒng)調(diào)用之后，CPU跳轉(zhuǎn)到0x1000段運行內(nèi)核代碼，該過程通常被稱為陷入內(nèi)核(trap)。而當(dāng)內(nèi)核代碼運行完畢之后，CPU返回User space內(nèi)存段繼續(xù)運行用戶程序的代碼。

3.3.1進程的建立

MTX將內(nèi)核加載到0x1000段，將用戶程序Uimage加載到0x2000、0x3000等段。內(nèi)核的CS、DS、SS段寄存器均為0x1000，而用戶程序的段寄存器值為其所在的內(nèi)存段地址。因此，fork建立第i進程的過程，就是將用戶程序Uimagei加載到內(nèi)存0x(i+1)000段并初始化proc[i]的過程。加載用戶程序的原理與加載內(nèi)核的原理相同，而初始化過程就是將proc[i]中的變量賦值為該進程對應(yīng)的值。因此要了解fork如何賦值PROC結(jié)構(gòu)中的變量，必須理解該變量在進程中代表的含義。

以第1進程proc1為例：MTX內(nèi)核通過kfork語句加載Uimage1并初始化proc[1]，執(zhí)行tswitch()之后，內(nèi)核設(shè)置Uimage1的上下文，并最終使CPU進入內(nèi)存的0x2000段運行Uimage1。tswitch函數(shù)最后的ret語句設(shè)置CPU的返回地址，即CPU要執(zhí)行的下一條指令的地址。該返回地址存儲在運行完“pop ax”之后的棧中，也就是kstack數(shù)組的最后一項kstack[SSIZE-1]之中。執(zhí)行ret之后CPU將執(zhí)行kstack[SSIZE-1]保存地址的語句，開始設(shè)置Uimage1的上下文。MTX內(nèi)核中設(shè)置Uimage上下文的過程為goUmode函數(shù)。

與tswitch函數(shù)類似，goUmode函數(shù)使用pop類指令設(shè)置Uimage1運行上下文的CPU寄存器。Uimage1被加載到內(nèi)存0x2000段，因此其CS、DS、ES均應(yīng)為0x2000。這三個寄存器以及ax、bx等其他寄存器的值均保存在用戶程序的棧中，以便通過pop類命令進行彈棧。

一個用戶程序加載到哪個段無法由程序自身決定，因此用戶程序的棧是在kfork過程中建立的。kfork將Uimage1加載到0x2000段之后，手動在0x2000段結(jié)尾的空內(nèi)存中開辟出proc1的棧，將CS、DS等所有寄存器的值寫入棧中，再把棧頂?shù)膬?nèi)存地址寫回到PROC，以便goUmode過程能正確設(shè)置用戶程序的棧頂。

因此，PROC結(jié)構(gòu)中應(yīng)包含用戶程序的棧信息，MTX在PROC中設(shè)置了uss和usp兩項，以存儲用戶程序棧的ss和sp寄存器信息。添加uss和usp之后的PROC結(jié)構(gòu)代碼如下：

typedef struct proc {

struct proc *next;

int *ksp;

int uss;

int usp;

…

int kstack[SSIZE];

} PROC

其中uss在proc結(jié)構(gòu)中的偏移量為4，usp的偏移量為6，因此_running+4指向PROC中的uss，_running+6指向usp。因此goUmode的代碼如下，其中USS=4，USP=6：

_goUmode:

mov bx,_running

mov ax,USS[bx]

mov ss,ax

mov sp,USP[bx]

pop ds

pop es

pop di

pop si

pop bp

pop dx

pop cx

pop bx

pop ax

iret

正如前文所述，上述代碼通過PROC結(jié)構(gòu)中的uss和usp設(shè)置好棧頂?shù)奈恢?，此后通過一系列pop命令設(shè)置CPU的寄存器，從而設(shè)置好用戶程序的運行上下文。當(dāng)最后的iret命令執(zhí)行后，CPU正式開始運行用戶程序。

3.3.2系統(tǒng)調(diào)用

當(dāng)運行于User space的用戶程序需要內(nèi)核功能時，例如運行于0x2000段中的proc1需要內(nèi)核fork以建立新進程時，其使用系統(tǒng)調(diào)用(syscall)調(diào)用內(nèi)核中的函數(shù)。由于用戶程序與內(nèi)核分別位于不同的內(nèi)存段中，proc1無法通過普通的函數(shù)調(diào)用(function call)來調(diào)用內(nèi)核函數(shù)。因此系統(tǒng)調(diào)用需要做到：讓0x1000段中的kfork函數(shù)獲得0x2000段中proc1程序代碼的調(diào)用參數(shù)，運行kfork，再將結(jié)果返回給0x2000段中的程序代碼。其效果好像proc1運行了普通的函數(shù)調(diào)用一樣，但參數(shù)和返回值跨越內(nèi)核空間和用戶空間進行傳遞。

跨越內(nèi)核空間和用戶空間傳遞參數(shù)較為容易，其本質(zhì)上是在兩個確定的內(nèi)存地址之間進行復(fù)制，只不過二者位于不同的段中。而CPU則需要在用戶空間和內(nèi)核空間的指令之間切換運行，因此在CPU進入內(nèi)核空間前，必須對用戶空間的上下文進行保存，以便當(dāng)內(nèi)核函數(shù)返回之后，對用戶程序的上下文進行恢復(fù)，從而繼續(xù)運行用戶程序的代碼?；謴?fù)用戶程序上下文的代碼即是前述的goUmode，保存上下文的過程是goUmode的逆過程。而保存上下文之后則應(yīng)為CPU設(shè)置內(nèi)核棧，并使CPU開始運行內(nèi)核函數(shù)代碼。

與Linux操作系統(tǒng)一樣，MTX以函數(shù)的形式進行系統(tǒng)調(diào)用，并在函數(shù)中觸發(fā)0x80中斷(INT80)。接收到INT80之后，CPU將當(dāng)前標(biāo)志位(flag)和CS、PC寄存器壓入用戶程序棧保存(與此對應(yīng)，goUmode結(jié)尾的iret指令彈?；謴?fù)這三個值)，然后將預(yù)存于指定地址的數(shù)據(jù)載入PC、CS，從而開始運行與當(dāng)前完全無關(guān)的指令。該預(yù)存的(PC,CS)被稱為中斷向量(interrupt vector)，中斷向量保存在內(nèi)存的0x0000段中。因此可以將內(nèi)核函數(shù)地址(0x1000)作為中斷向量保存于0x0000段的指定位置。

INT80中斷處理程序的部分關(guān)鍵代碼如下：

mov bx,_running

…

mov sp,bx

add sp,_procSize

call _kcinth

_goUmode:

…

其中procSize為sizeof(PROC)的值，也就是PROC結(jié)構(gòu)的大小。因此上述代碼將棧頂設(shè)置在當(dāng)前進程的PROC結(jié)構(gòu)的結(jié)尾，即kstack[]數(shù)組的最后一項，然后運行kcinth函數(shù)。kcinth函數(shù)所做的工作即如前文所述，從用戶空間取得系統(tǒng)調(diào)用的參數(shù)，根據(jù)參數(shù)調(diào)用內(nèi)核函數(shù)，最后將函數(shù)的返回值復(fù)制回用戶空間。由于用戶程序以函數(shù)形式進行系統(tǒng)調(diào)用，因此返回值應(yīng)覆蓋用戶程序棧中的ax寄存器。當(dāng)kcinth返回后，CPU執(zhí)行g(shù)oUmode函數(shù)以返回User space繼續(xù)執(zhí)行用戶程序。

4 結(jié)論

MTX操作系統(tǒng)在實模式下構(gòu)建了結(jié)構(gòu)標(biāo)準(zhǔn)的類UNIX內(nèi)核，其對硬件的要求極低，甚至可運行于8086 CPU上，為操作系統(tǒng)微型化[8]和定制化提供了一個新的思路，并為嵌入式控制提供了一個新的方案。