利用Nachos操作系统研究和实验虚拟内存

摘要:本文分析和论述了如何利用教学指导型操作系统Nachos研究和实验虚拟内存。通过详细的实例设计与分析,阐述了在Nachos操作系统中如何构建虚拟内存,如何实现虚拟内存的各种调度算法;如何实验和分析虚拟内存的工作过程和性能。对虚拟内存的教学和科研具有一定的指导辅助作用。

关键词:操作系统;虚拟内存;实践教学;Nachos

中图分类号:G642 文献标识码:B

1引言

虚拟内存的实现和运行同时涉及到内存管理、调度与中断、文件系统等内核诸多方面的问题。因此在操作系统的教学和实验中虚拟内存的讲解和实验是较为棘手和困难的一个问题。为了能够讲清虚拟内存的基本构造和工作原理或想独立实践一下虚拟内存的构造和各种虚拟内存策略,我们可以利用一下教学指导型操作系统Nachos。由于Nachos提供了一个自由构造虚拟内存的框架,可让我们在其上开发和构造自主设计的虚拟内存,辅助我们更好的开展好虚拟内存的教学和研究。

2内存管理和虚拟内存构造机制

Nachos在它的页表机制中仅提供了可让用户构造虚拟内存的基本机制。页表结构是由TranslationEntry 类定义的,该定义在文件machine/translation.h中:

class TranslationEntry {

public:

int virtualPage; //逻辑页号

int physicalPage; //物理页号

bool valid; //有效位

bool readOnly; //只读位

bool use; //引用位

bool dirty; //修改位

};

为了实现虚拟内存的页置换,我们需要在以上类中增加一个该页在文件中的块偏量:int inFilePage。

原始的Nachos内存无法实现多道程序同时驻留内存,为此可以为其增设了分段式内存管理,从而实现了多道程序同时驻留内存并发执行。增设的段式内存管理

机制的类结构为:

class SegmentEntry { //段表

public:

int segID; //段号

int segBase; //段基址

int segPages; //段页数

} ;

class MemManager{ //段管理器

public:

MemManager();// 段构造

~MemManager(); // 段析构

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

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

private:

List *usedList; //已用内存页表链

List *idleList; //空闲内存页表链

};

用户的可执行文件按段装入到模拟机的物理内存中并发执行的过程(无虚拟内存方案)可参见文献[1]。为了构造虚存,设定每个进程一个固定大小的工作集,限定每进程可用的实存页数,补充了宏定义:

#define MemPages 4; //默认的工作集实存页数

其中的装入构造函数AddrSpace中进行了如下的扩充:

//当进程由shell命令创建时

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

}

//当进程由父进程创建时

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++) {

//复制父进程页表项,略……

if(pTp[i].valid){//该页在实存

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

inMemPage[j++] = i ;

}

else//该页不在实存

pageTable[i].physicalPage = -1;

}

.......

这样当一个进程空间初始生成时就按照虚拟内存规定的工作集大小在内存中生成了初始进程映像。

3地址变换和虚拟内存调度策略

上节中由装入构造函数AddrSpace生成的地址空间是一个逻辑的地址空间。在程序执行时逻辑地址需要变换为物理空间。在真实的计算机中,这一工作是由 MMU硬件完成的。当变换发生错误时MMU会自动发出各种异常中断。

Nachos 模拟带有 TLB 的页式内存管理。MMU 由函数 Translate 模拟。

两个函数ReadMem和WriteMem 在访问物理内存之前都要调用函数Translate将要访问的逻辑地址变换为物理地址。Translate函数的代码可以在machine/translate.cc中找到。应在其中加入我们的虚拟内存调度策略算法,以实现虚拟内存的页调度。例如可模拟一个最近最少用调度算法在其中调用它:

currentThread->space->LRU(vpn);

4内存页访问异常的处理与虚拟内存的页置换算法

当进程要访问的逻辑地址不在实存时会引发页访问失败异常。我们可在userprog/exception.cc文件的xception Handler函数中引入页访问失败异常处理。例如设计一个页置换中断处理函数,当

页访问失败时,找出出错的地址,调用该函数:

//根据出错地址进行页置换

interrupt->Replace(badVAddr);

//记录总的页访问失败的次数

stats->numPageFaults++;

函数Replace(badVAddr)的实现:

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;

//调用不同的虚拟内存调度算法确定置换页

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

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

//找到要换入的外存页块

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

//设置换入页的页表项

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

cPt[newPage].valid = TRUE;

cPt[newPage].use = TRUE;

//设置换出页的页表项

cPt[oldPage].physicalPage = -1 ;

cPt[oldPage].valid = FALSE;

if(cPt[oldPage].dirty)

//如果换出页修改过则回写到外存页

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

PageSize, cPt[oldPage].inFilePage);

//将要换入的页读入换出页所在内存页

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

PageSize, cPt[newPage].inFilePage);

//记录当前进程页访问失败次数

currentThread->PageFaults++;}

5虚拟内存的实验和性能分析

现在我们已经实现了一个简单而适用的带有虚拟内存机制的操作系统。为了检测和分析该系统的性能,我们可以在Linux系统下编译和生成带有shell命令、多道程序并发执行和具有LRU调度策略的虚拟内存功能的内核执行文件

此时我们看到nshell被装入并执行。为了解进程内存映像的情况,我们打印出了每个进程初始装入时 的页表,其中各栏的含义为:

vpage 逻辑页号。

mpage 实存页号。

inFile 该页在外存文件中的偏量。

vaild 1表示该页在实存,0表示该页不在实存。

use 1表示该页被引用过,0表示该页未被引用过。

dirty 1表示该页被修改过,0表示该页未被修改过。

可以看出当前进程nshell共有19页其中仅有头4页被装入内存0-3页的段中,进程刚被装入还未执行,没有页被引用和修改。

进一步我们通过nshell再装入两个并发进程,一个数组排序程序sort和一个阶乘计算程序factor。

nshell接收到命令为sort和factor建立两个子进程,首先执行sort子进程的父进程(nshell)映像的副本,可以看到nshell的页表已经发生了变化,第1,9,17,18页最近被访问,第0,2,3页当前被淘汰。接下来sort程序的头4页被装入内存4-7页的段中,它共有17页。

现在进程切换到factor子进程的父进程(nshell)副本,情况同以上sort被装入前的情况类似:

现在factor的进程映像也被装入。它共有12页,头4页被装入到8-11页的段中。

factor进程首先执行完成,它打印出计算的结果,并报告了它的执行过程中发生了8次页访问失败。

6! = 720

134643816 process exit 0

In kernel 0; In user 211; PageFaults 8

Idle Segment Table

SegID BaseSize

000000000 8 312

之后sort进程也执行完成,它打印出排序的结果,并报告了它的执行过程中发生了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

命令执行结束,控制重新返回到了nshell 。

6结束语

通过以上讨论可以看出利用Nachos我们可以非常逼真地练习虚拟内存的设计,用真实的而不是模拟的程序测试、分析并清晰地揭示出虚存的工作过程和性能。据此还可以开发出更高级的虚拟内存功能。这既可以辅助我们操作系统的教学和实验,也可以辅助我们快捷地开展一些操作系统的课题研究。

参考文献:

[1] 张鸿烈.利用Nachos操作系统研究和实验多道程序的并发执行[J]. 烟台大学学报:自然科学与工程版,2007(20):60.