利用Ｎａｃｈｏｓ操作系統(tǒng)研究和實驗虛擬內(nèi)存

摘要:本文分析和論述了如何利用教學指導(dǎo)型操作系統(tǒng)Nachos研究和實驗虛擬內(nèi)存。通過詳細的實例設(shè)計與分析,闡述了在Nachos操作系統(tǒng)中如何構(gòu)建虛擬內(nèi)存,如何實現(xiàn)虛擬內(nèi)存的各種調(diào)度算法;如何實驗和分析虛擬內(nèi)存的工作過程和性能。對虛擬內(nèi)存的教學和科研具有一定的指導(dǎo)輔助作用。

關(guān)鍵詞:操作系統(tǒng);虛擬內(nèi)存;實踐教學;Nachos

中圖分類號:G642 文獻標識碼:B

1引言

虛擬內(nèi)存的實現(xiàn)和運行同時涉及到內(nèi)存管理、調(diào)度與中斷、文件系統(tǒng)等內(nèi)核諸多方面的問題。因此在操作系統(tǒng)的教學和實驗中虛擬內(nèi)存的講解和實驗是較為棘手和困難的一個問題。為了能夠講清虛擬內(nèi)存的基本構(gòu)造和工作原理或想獨立實踐一下虛擬內(nèi)存的構(gòu)造和各種虛擬內(nèi)存策略,我們可以利用一下教學指導(dǎo)型操作系統(tǒng)Nachos。由于Nachos提供了一個自由構(gòu)造虛擬內(nèi)存的框架,可讓我們在其上開發(fā)和構(gòu)造自主設(shè)計的虛擬內(nèi)存,輔助我們更好的開展好虛擬內(nèi)存的教學和研究。

2內(nèi)存管理和虛擬內(nèi)存構(gòu)造機制

Nachos在它的頁表機制中僅提供了可讓用戶構(gòu)造虛擬內(nèi)存的基本機制。頁表結(jié)構(gòu)是由TranslationEntry 類定義的,該定義在文件machine/translation.h中:

class TranslationEntry {

public:

int virtualPage; //邏輯頁號

int physicalPage; //物理頁號

bool valid; //有效位

bool readOnly; //只讀位

bool use; //引用位

bool dirty; //修改位

};

為了實現(xiàn)虛擬內(nèi)存的頁置換,我們需要在以上類中增加一個該頁在文件中的塊偏量:int inFilePage。

原始的Nachos內(nèi)存無法實現(xiàn)多道程序同時駐留內(nèi)存,為此可以為其增設(shè)了分段式內(nèi)存管理,從而實現(xiàn)了多道程序同時駐留內(nèi)存并發(fā)執(zhí)行。增設(shè)的段式內(nèi)存管理

機制的類結(jié)構(gòu)為:

class SegmentEntry { //段表

public:

int segID; //段號

int segBase; //段基址

int segPages; //段頁數(shù)

} ;

class MemManager{ //段管理器

public:

MemManager();// 段構(gòu)造

~MemManager(); // 段析構(gòu)

SegmentEntry * Allocate(int segPages,int pid);//分配一個段

void Deallocate(int Pid); //回收一個段

private:

List *usedList; //已用內(nèi)存頁表鏈

List *idleList; //空閑內(nèi)存頁表鏈

};

用戶的可執(zhí)行文件按段裝入到模擬機的物理內(nèi)存中并發(fā)執(zhí)行的過程(無虛擬內(nèi)存方案)可參見文獻[1]。為了構(gòu)造虛存,設(shè)定每個進程一個固定大小的工作集,限定每進程可用的實存頁數(shù),補充了宏定義:

#define MemPages 4; //默認的工作集實存頁數(shù)

其中的裝入構(gòu)造函數(shù)AddrSpace中進行了如下的擴充:

//當進程由shell命令創(chuàng)建時

AddrSpace::AddrSpace(char *filename)

{

// 建立頁表入口

pageTable = new TranslationEntry

[pageTableSize];

//初始化頁表項

for (i = 0; i < pageTableSize; i++) {

//填寫頁表項略……

if(i < MemPages){//如果有實存

pageTable[i].physicalPage = segment->segBase + i;//分配物理頁

pageTable[i].valid = TRUE;

inMemPage[i] =i ;

}

else{//如果無實存物理頁號置為-1

pageTable[i].physicalPage = -1;

pageTable[i].valid = FALSE; }

}

//當進程由父進程創(chuàng)建時

AddrSpace::AddrSpace(int pid)

{

//獲取父進程頁表入口

TranslationEntry *pTp=currentThread->space->GetPageTable();

//拷貝父進程頁表

pageTableSize = currentThread->space->GetPageSize();

//建立子進程頁表入口

pageTable = new TranslationEntry[pageTableSize];

for (j=0,i=0;i < pageTableSize; i++) {

//復(fù)制父進程頁表項,略……

if(pTp[i].valid){//該頁在實存

pageTable[i].physicalPage = segment-> segBase + (pTp[i].physicalPage-pSg-> segBase);

inMemPage[j++] = i ;

}

else//該頁不在實存

pageTable[i].physicalPage = -1;

}

.......

這樣當一個進程空間初始生成時就按照虛擬內(nèi)存規(guī)定的工作集大小在內(nèi)存中生成了初始進程映像。

3地址變換和虛擬內(nèi)存調(diào)度策略

上節(jié)中由裝入構(gòu)造函數(shù)AddrSpace生成的地址空間是一個邏輯的地址空間。在程序執(zhí)行時邏輯地址需要變換為物理空間。在真實的計算機中,這一工作是由 MMU硬件完成的。當變換發(fā)生錯誤時MMU會自動發(fā)出各種異常中斷。

Nachos 模擬帶有 TLB 的頁式內(nèi)存管理。MMU 由函數(shù) Translate 模擬。

兩個函數(shù)ReadMem和WriteMem 在訪問物理內(nèi)存之前都要調(diào)用函數(shù)Translate將要訪問的邏輯地址變換為物理地址。Translate函數(shù)的代碼可以在machine/translate.cc中找到。應(yīng)在其中加入我們的虛擬內(nèi)存調(diào)度策略算法,以實現(xiàn)虛擬內(nèi)存的頁調(diào)度。例如可模擬一個最近最少用調(diào)度算法在其中調(diào)用它:

currentThread->space->LRU(vpn);

4內(nèi)存頁訪問異常的處理與虛擬內(nèi)存的頁置換算法

當進程要訪問的邏輯地址不在實存時會引發(fā)頁訪問失敗異常。我們可在userprog/exception.cc文件的xception Handler函數(shù)中引入頁訪問失敗異常處理。例如設(shè)計一個頁置換中斷處理函數(shù),當

頁訪問失敗時,找出出錯的地址,調(diào)用該函數(shù):

//根據(jù)出錯地址進行頁置換

interrupt->Replace(badVAddr);

//記錄總的頁訪問失敗的次數(shù)

stats->numPageFaults++;

函數(shù)Replace(badVAddr)的實現(xiàn):

Void Interrupt::Replace(int badVAddr){

NoffHeader noffH;

//讀出進程映像文件頭

currentThread->space->GetExecfile()->ReadAt((char *)&noffH, sizeof(noffH), 0);

//確定當前進程頁表

TranslationEntry *cPt = currentThread->space-> GetPageTable();

//換算出錯地址所在頁號

unsigned int newPage = badVAddr/PageSize;

//調(diào)用不同的虛擬內(nèi)存調(diào)度算法確定置換頁

unsigned int oldPage = currentThread->space-> LRU (newPage);

//unsigned int oldPage = currentThread-> space->FIFO (newPage);

//找到要換入的外存頁塊

unsigned int offset = noffH.code.virtualAddr + cPt [oldPage].physicalPage * PageSize;

//設(shè)置換入頁的頁表項

cPt[newPage].physicalPage = cPt[oldPage].physicalPage ;

cPt[newPage].valid = TRUE;

cPt[newPage].use = TRUE;

//設(shè)置換出頁的頁表項

cPt[oldPage].physicalPage = -1 ;

cPt[oldPage].valid = FALSE;

if(cPt[oldPage].dirty)

//如果換出頁修改過則回寫到外存頁

currentThread->space->GetExecfile()->WriteAt(&(machine->mainMemory[offset]),

PageSize, cPt[oldPage].inFilePage);

//將要換入的頁讀入換出頁所在內(nèi)存頁

currentThread->space->GetExecfile()->ReadAt(&(machine->mainMemory[offset]),

PageSize, cPt[newPage].inFilePage);

//記錄當前進程頁訪問失敗次數(shù)

currentThread->PageFaults++;}

5虛擬內(nèi)存的實驗和性能分析

現(xiàn)在我們已經(jīng)實現(xiàn)了一個簡單而適用的帶有虛擬內(nèi)存機制的操作系統(tǒng)。為了檢測和分析該系統(tǒng)的性能,我們可以在Linux系統(tǒng)下編譯和生成帶有shell命令、多道程序并發(fā)執(zhí)行和具有LRU調(diào)度策略的虛擬內(nèi)存功能的內(nèi)核執(zhí)行文件

此時我們看到nshell被裝入并執(zhí)行。為了解進程內(nèi)存映像的情況,我們打印出了每個進程初始裝入時 的頁表,其中各欄的含義為:

vpage 邏輯頁號。

mpage 實存頁號。

inFile 該頁在外存文件中的偏量。

vaild 1表示該頁在實存,0表示該頁不在實存。

use 1表示該頁被引用過,0表示該頁未被引用過。

dirty 1表示該頁被修改過,0表示該頁未被修改過。

可以看出當前進程nshell共有19頁其中僅有頭4頁被裝入內(nèi)存0-3頁的段中,進程剛被裝入還未執(zhí)行,沒有頁被引用和修改。

進一步我們通過nshell再裝入兩個并發(fā)進程,一個數(shù)組排序程序sort和一個階乘計算程序factor。

nshell接收到命令為sort和factor建立兩個子進程,首先執(zhí)行sort子進程的父進程(nshell)映像的副本,可以看到nshell的頁表已經(jīng)發(fā)生了變化,第1,9,17,18頁最近被訪問,第0,2,3頁當前被淘汰。接下來sort程序的頭4頁被裝入內(nèi)存4-7頁的段中,它共有17頁。

現(xiàn)在進程切換到factor子進程的父進程(nshell)副本,情況同以上sort被裝入前的情況類似:

現(xiàn)在factor的進程映像也被裝入。它共有12頁,頭4頁被裝入到8-11頁的段中。

factor進程首先執(zhí)行完成,它打印出計算的結(jié)果,并報告了它的執(zhí)行過程中發(fā)生了8次頁訪問失敗。

6! = 720

134643816 process exit 0

In kernel 0; In user 211; PageFaults 8

Idle Segment Table

SegID BaseSize

000000000 8 312

之后sort進程也執(zhí)行完成,它打印出排序的結(jié)果,并報告了它的執(zhí)行過程中發(fā)生了278次頁訪問失敗。

Sort by ascending order

0 1 2 3 4 5 6 7 8 9

34617896 process exit 0

n kernel 310; In user 4187; PageFaults 278

Idle Segment Table

SegID BaseSize

000000000 4 316

命令執(zhí)行結(jié)束,控制重新返回到了nshell 。

6結(jié)束語

通過以上討論可以看出利用Nachos我們可以非常逼真地練習虛擬內(nèi)存的設(shè)計,用真實的而不是模擬的程序測試、分析并清晰地揭示出虛存的工作過程和性能。據(jù)此還可以開發(fā)出更高級的虛擬內(nèi)存功能。這既可以輔助我們操作系統(tǒng)的教學和實驗,也可以輔助我們快捷地開展一些操作系統(tǒng)的課題研究。

參考文獻:

[1] 張鴻烈.利用Nachos操作系統(tǒng)研究和實驗多道程序的并發(fā)執(zhí)行[J]. 煙臺大學學報:自然科學與工程版,2007(20):60.