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

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

中圖分類號:G642 文獻(xiàn)標(biāo)識碼:B

1引言

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

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

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

class TranslationEntry {

public:

int virtualPage; //邏輯頁號

int physicalPage; //物理頁號

bool valid; //有效位

bool readOnly; //只讀位

bool use; //引用位

bool dirty; //修改位

};

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

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

機(jī)制的類結(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);//分配一個(gè)段

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

private:

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

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

};

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

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

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

//當(dāng)進(jìn)程由shell命令創(chuàng)建時(shí)

AddrSpace::AddrSpace(char *filename)

{

// 建立頁表入口

pageTable = new TranslationEntry

[pageTableSize];

//初始化頁表項(xiàng)

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

//填寫頁表項(xiàng)略……

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

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

pageTable[i].valid = TRUE;

inMemPage[i] =i ;

}

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

pageTable[i].physicalPage = -1;

pageTable[i].valid = FALSE; }

}

//當(dāng)進(jìn)程由父進(jìn)程創(chuàng)建時(shí)

AddrSpace::AddrSpace(int pid)

{

//獲取父進(jìn)程頁表入口

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

//拷貝父進(jìn)程頁表

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

//建立子進(jìn)程頁表入口

pageTable = new TranslationEntry[pageTableSize];

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

//復(fù)制父進(jìn)程頁表項(xiàng),略……

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

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

inMemPage[j++] = i ;

}

else//該頁不在實(shí)存

pageTable[i].physicalPage = -1;

}

.......

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

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

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

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

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

currentThread->space->LRU(vpn);

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

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

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

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

interrupt->Replace(badVAddr);

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

stats->numPageFaults++;

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

Void Interrupt::Replace(int badVAddr){

NoffHeader noffH;

//讀出進(jìn)程映像文件頭

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

//確定當(dāng)前進(jìn)程頁表

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

//換算出錯(cuò)地址所在頁號

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è)置換入頁的頁表項(xiàng)

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

cPt[newPage].valid = TRUE;

cPt[newPage].use = TRUE;

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

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);

//記錄當(dāng)前進(jìn)程頁訪問失敗次數(shù)

currentThread->PageFaults++;}

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

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

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

vpage 邏輯頁號。

mpage 實(shí)存頁號。

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

vaild 1表示該頁在實(shí)存,0表示該頁不在實(shí)存。

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

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

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

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

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

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

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

factor進(jìn)程首先執(zhí)行完成,它打印出計(jì)算的結(jié)果,并報(bào)告了它的執(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進(jìn)程也執(zhí)行完成,它打印出排序的結(jié)果,并報(bào)告了它的執(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我們可以非常逼真地練習(xí)虛擬內(nèi)存的設(shè)計(jì),用真實(shí)的而不是模擬的程序測試、分析并清晰地揭示出虛存的工作過程和性能。據(jù)此還可以開發(fā)出更高級的虛擬內(nèi)存功能。這既可以輔助我們操作系統(tǒng)的教學(xué)和實(shí)驗(yàn),也可以輔助我們快捷地開展一些操作系統(tǒng)的課題研究。

參考文獻(xiàn):

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