Nachos实验11设计并实现用户空间的虚拟内存管理上.doc

实验目的
在未实现用户空间的虚拟内存管理之前，Nachos系统在运行一个用户进程的时候，需要将程序在运行时可能会用到的所有信息都拷贝到mainMemory中去。这样，因为mainMemory 的大小的限制，一些较大的文件可能无法执行；而相对应的，一些程序中可能包含着大量在执行过程中极少或根本不会被访问的数据，这些数据却又长期占据了内存的资源。本次试验的目的：
整体理解Nachos系统的组织结构。
设计并实现用户空间的虚拟内存管理。
实验环境
Linux操作系统，Nachos操作系统
实验分析
此次实验是在实验7-8——Extension of AddrSpace and System Calls Exec()的基础上更改的。实验的目录并没有在系统已有的vm目录下进行，而是将实验目录lab7-8更名为lab11，目的是使用lab7-8目录下的Makefile文件。在本次实验的过程中，发现并更改了实验7-8的一些疏漏之处。
为了说明方便，首先澄清一下基本概念和数据结构：
用bitmap做物理地址分配

图1 存取关系图
页表
class TranslationEntry {
public:
int virtualPage; // The page number in virtual memory.
// 对应于图1中的虚页
    int physicalPage; // The page number in real memory (relative to the
    // start of "mainMemory"
// 对应于图1中的物理页
    bool valid;         // If this bit is set, the translation is ignored.
    // (In other words, the entry hasn't been initialized.)
    bool readOnly; // If this bit is set, the user program is not allowed
    // to modify the contents of the page.
    bool use;           // This bit is set by the hardware every time the
    // page is referenced or modified.
    bool dirty;         // This bit is set by the hardware every time the
    // page is modified.
int inFileAddr;  //The address of this segment of data in the file.
//对于vmcode、vminitData，inFileAddr代表在源文件中的addr
//对应于图1中的linux系统下的文件*.noff.
//对于vmuninitData、vmuserStack，inFileAddr代表在SWAP文件中的位置
PageType type;  //The type of this entry.
//标明页中数据的类型
};
为了实现虚拟内存的页置换，在以上类中增加一个该页在文件中块偏移量inFileAddr和当前页存储的数据的类型的type。
其中type的类型PageType定义为枚举类型，写在文件translate.h中。
enum PageType
{vmcode,vminitData,vmuninitData,vmuserStack};
分别代表此页数据为代码，初始化数据，未初始化数据，用户栈。
交换区SWAP
曾在实验7-8中，在progtest.cc文件中声明了BitMap *Mmbmp（如图1），记录mainMemory中物理页的分配情况。它的位置表明了，此Mmbmp的作用域是整个Nachos系统，它不隶属于任何一个用户进程。当然，我们可以实现一个更好的方式：将Mmbmp放到Machine中，但是这要修改Machine的定义，如果查看Machine类定义就可以知道，Machine牵扯到Nachos的核心的系统控制，为了尽量保证Nachos系统的稳定性，则将BitMap *Mmbmp作为全局变量放在了progtest.cc中。
同样的道理，将交换区文件SWAP的生命周期与Mmbmp相似，同时SWAP也需要一个BitMap *SwapBitmap记录SWAP各个页的使用情况，所以，在protest.cc中添加声明：
BitMap *Mmbmp=new BitMap(NumPhysPages); //bitmap for allocating of physical pages infjkdjk mainMemory.
BitMap *SwapBitmap = new BitMap(NumPhysPages); //bitmap for SWAP file,
         //assume the size of SWAP file is NumPhyPages.
OpenFile *SwapFile = fileSystem->Open("SWAP"); //stub in Nachos_Linux
        //在lab11的目录下建立文件SWAP
NoffHeader
修改原有的结构体NoffHeader为类类型，目的是为了能够将NoffHeader作为AddrSpace类的私有实例变量存取，结构体无法实例化为类的私有变量，所以将结构体NoffHeader重写，变为类NoffHeader，并一起更改结构体NoffSegment为类类型。两者的功能在保证原结构体功能的基础上，为了调试和输出方便，添加输出函数Print()。具体定义如下：
#define NOFFMAGIC 0xbadfad
class NoffSegment
{
public:
int virtualAddr;
int inFileAddr;
int size;

void Print();
NoffSegment();
~NoffSegment();
};
class NoffHeader
{
public:
int noffMagic;
NoffSegment code;
NoffSegment initData;
NoffSegment uninitData;

void Print();
NoffHeader();
~NoffHeader();
};
AddrSpace
扩展原有的AddrSpace的属性：
添加属性——当下正在执行的用户文件的指针OpenFile *executable，因为我们无法一次读取所有需要的数据，更多情况下，我们边用边读，所以设置一个变量executable来保存指向用户文件的指针。
添加属性——当下正在执行的用户文件的NoffHeader，因为NoffHeader在初始化时，将会加载到mainMemory的0号地址中，一旦程序运行之后，原0号地址中的内容必定会被用户程序重写，但因为我采用的是bitmap做物理地址与虚地址的变换，其中的变换细节要求需要在进行物理和虚拟页变换时知道code的virtualAddr，initData的virtualAddr等的数据，（详细细节见AddrSpace::Translate介绍）所以为了访问方便，设置其为用户进程的一个属性。
添加virtualMem数组和p_vm指针，用来实现FIFO算法。virtualMem存储的是按进入内存的先后顺序排列的当前占用内存空间的虚页，p_vm指针指向数组中当前将要被换出的那个位置。（详细说明见AddrSpace::FIFO介绍）
private:
TranslationEntry *pageTable; // Assume linear page table translation for now!
unsigned int numPages; // Number of pages in the virtual address space
OpenFile *executable; //A pointer to the executing file
NoffHeader noffH;   // The header of the OpenFile executable
int virtualMem[MemPages]; // Store virtual pages of the pages in the main memory
int p_vm;     //The pointer to next memory to swap out
添加AddrSpace实现用户空间虚拟内存的函数：
void InitPageTable(); //用于初始化AddrSpace的pageTable的基本信息
void InitInFileAddr(); //初始化pageTable中各个entry的inFileAddr、type
void FIFO(int newPage); //调用translate和swap实现先进先出的虚拟内存置换算法
void Translate(int addr,unsigned int* vpn, unsigned int *offset);
       //将addr对应的虚拟页页号vpn和页内偏移量offset计算出来
void Swap(int oldPage, int newPage); //调用WriteBack和ReadIn
//实现将mainMemory中的oldPage替换成newPage
void WriteBack(int oldPage); //将oldPage这一个页写回
     //code和initData将会被写回文件；
//uninitData和userStack内容将会被写回交换区SWAP
void ReadIn(int newPage); //将newPage写入到mainMemory
     //code和initData将通过inFileAddr从文件中读出；
     //uninitData和userStack或从交换区SWAP读出，或只是将mainMemory中分配到的地址段清零
关键源代码及注释
首先，简要说明一下现在Nachos系统的虚拟存储功能的能力。为了简便起见，规定系统默认给每个用户进程分配MemPages大小的主存，当用户的进程装入内存，进行数据初始化的时候，按照用户程序在pageTable中的存储顺序从前向后装入MemPages大小的页到内存中去。在用户进程在运行的过程之中，如果访问内存无法找到想要的virtualAddr，那么采用FIFO策略进行不同页之间的切换。
那么接下来，按照一个用户进程在Nachos下执行的过程顺序对本次实验的程序进行解剖说明。
用户进程（pageTable）的初始化
用户程序从progtest.cc的StartProcess接口开始装载，通过传递OpenFile *executable到AddrSpace space生成新的AddrSpace实例。此时space进行初始化：
AddrSpace::AddrSpace(OpenFile *exe)
{
unsigned int size;
executable = exe; [1]
    executable->ReadAt((char *)&noffH, sizeof(noffH), 0);
    if ((noffH.noffMagic != NOFFMAGIC) &&
   (WordToHost(noffH.noffMagic) == NOFFMAGIC))
    SwapHeader(&noffH);
    ASSERT(noffH.noffMagic == NOFFMAGIC);
numPages = divRoundUp(noffH.code.size,PageSize) + divRoundUp(noffH.initData.size, PageSize)
       + divRoundUp(noffH.uninitData.size,PageSize) + StackPages;
size = (MemPages + StackPages) * PageSize;
//加粗语句决定了在给定虚拟地址addr,换算虚页vpn和页内偏移量offset时不再是
//vpn = (unsigned) virtAddr / PageSize;
//offset = (unsigned) virtAddr % PageSize;
//具体转换令写函数AddrSpace::Translate实现
printf("numPages is %d\n",numPages);
printf("numPages = %d + %d + %d + %d\n",divRoundUp(noffH.code.size,PageSize), divRoundUp(noffH.initData.size, PageSize),
       divRoundUp(noffH.uninitData.size,PageSize), StackPages);
    DEBUG('a', "Initializing address space, num pages %d, size %d\n",
      numPages, size);
// zero out the entire address space, to zero the unitialized data segment
// and the stack segment
bzero(machine->mainMemory, size);
// first, set up the translation
InitPageTable(); [2]
// then, copy in the code and data segments into memory
InitInFileAddr(); [3]
Print();    
}
[1]在原Nachos的progtest.cc中可以看到，当使用executable完成AddrSpace space的初始化工作后，采用了直接“delete executable”的语句，将文件关闭，但是在进行WriteBack和ReadIn函数调用的过程中，仍然需要诸如“executable -> WriteAt (&(machine->mainMemory[pageTable[oldPage].physicalPage * PageSize]), PageSize, pageTable[oldPage].inFileAddr);”的语句，所以注释掉progtest.cc中的delete语句，将exectuable的指针传递给AddrSpace，令AddrSpace的属性保存控制executable。
[2]调用新添加到AddrSpace类中的函数InitPageTable，这个函数主要作用是完成初始化原pageTable的基本信息，这些信息都是不需要根据此Entry的type或者是NoffHeader就可以直接确定的信息：virtualPage，use，dirty，readOnly，valid，physicalPage等。
void
AddrSpace::InitPageTable()
{
p_vm = 0;
    pageTable = new TranslationEntry[numPages];
    for (int i = 0; i < numPages; i++)
    {
   pageTable[i].virtualPage = i; // for now, virtual page # = phys page #
   pageTable[i].use = FALSE;
   pageTable[i].dirty = FALSE;
   pageTable[i].readOnly = FALSE; // if the code segment was entirely on
      // a separate page, we could set its
      // pages to be read-only
pageTable[i].inFileAddr = -1;
//初始化inFileAddr为-1，具体值会在InitFileAddr中计算出。
   if(i >= numPages - StackPages)
    pageTable[i].type = vmuserStack; //we can be sure that the stack
// must be located in the last StackPages pages,
// thus initiate the type of stack pages.
   //最后，将前MemPages个虚页的内容分配mainMemory的物理页，准备将其写入到mainMemory中去，写入过程有InitFileAddr完成。
   if(i < MemPages)
   {
    virtualMem[p_vm] = pageTable[i].virtualPage;//==i
    p_vm = (p_vm + 1) % MemPages;
    pageTable[i].physicalPage = Mmbmp -> Find ();
    pageTable[i].valid = TRUE;
   }
   else{
    pageTable[i].physicalPage = -1;
    pageTable[i].valid = FALSE;
   }
    }
}
[3]新添加到AddrSpace中的函数，作用是初始化各个page的inFileAddr、type，并将已经分配了物理页的page写入到mainMemory，通过调用[2][3] ，完成整个pageTable的初始化工作。
void
AddrSpace::InitInFileAddr()
{
    if (noffH.code.size > 0)
    {
   unsigned int numP = divRoundUp(noffH.code.size, PageSize);

   for (int i = 0; i < numP; i++)
   {
    pageTable[i].inFileAddr = noffH.code.inFileAddr + i * PageSize;
    pageTable[i].type = vmcode;
    if(pageTable[i].valid)
    {
   executable->ReadAt( &(machine->mainMemory[pageTable[i].physicalPage * PageSize]),PageSize, pageTable[i].inFileAddr);
//If the page has been allocated with physical page, read into the mainMemory
    }
   }
}
    if (noffH.initData.size > 0)
    {
   unsigned int numP,firstP;   
   numP = divRoundUp(noffH.initData.size, PageSize);
   firstP = divRoundUp(noffH.initData.virtualAddr, PageSize);
   for (int i = firstP; i < numP + firstP; i++)
   {
    pageTable[i].inFileAddr = noffH.initData.inFileAddr + (i - firstP) * PageSize;
    pageTable[i].type = vminitData;
    if(pageTable[i].valid)
    {
   executable->ReadAt(&(machine->mainMemory[pageTable[i].physicalPage * PageSize]),PageSize, pageTable[i].inFileAddr);
//If the page has been allocated with physical page, read into the mainMemory
    }
   }
    }
if(noffH.uninitData.size > 0)
{
   unsigned int numP,firstP;
   numP = divRoundUp(noffH.uninitData.size, PageSize);
   firstP = divRoundUp(noffH.uninitData.virtualAddr, PageSize);
   for (int i = firstP; i < numP + firstP; i++)
   {
    pageTable[i].type = vmuninitData;
    if(pageTable[i].valid)
   {/*brzero();*/}
   }
}
}
需要说明的是，在调用完InitInFileAddr函数之后，各中类型的pageTable的entry的type和inFileAddr对应关系如下：

type inFileAddr
vmcode noffH.code.inFileAddr + i * PageSize
vminitData noffH.initData.inFileAddr + (i - firstP) * PageSize
vmuninitData -1
vmuserStack -1
请注意，最后两项vmuninitData和vmuserStack中inFileAddr的值初始化时都被定义为-1，但它们都有可能在程序执行的过程中被赋予大于0的值，当inFileAddr值大于0时，表明此页已经被修改过，修改过的页被写在SWAP交换区文件中的inFileAddr位置处。
缺页异常处理
用户进程在初始化完成后，正式开始执行，在执行的过程中必然会出现mips cpu想要访问某个初始化时并不在mainMemory中的virtualAddr，此时，发生缺页异常后，会进入userprog/exception.cc中的 ExceptionHandler函数，并且MIPS CPU想访问的那个虚拟地址在寄存器BadVAddrReg中。此时，只需使这个虚页进入主存，然后令MIPS CPU重新执行原来那条指令。
在处理缺页异常之前，我们应首先注意到，cpu访问内存的时候用的是virtualAddr，而非virtualPage，我们打开translate.cc的Machine::Translate方法就可以发现，cpu进行virtualAddr翻译成虚页号vpn和页内偏移量offset时使用的默认方法是
vpn = (unsigned) virtAddr / PageSize;
offset = (unsigned) virtAddr % PageSize;
但是这样翻译的得到结果，并不等价于我们的pageTable的virtualPage（即pageTable数组的下标号），回想我们的设计在code，initData，uninitData，userStack之间两两存在着碎片。所以为了让cpu明确地知道它究竟想要访问的页是哪一个，在AddrSpace中添加方法Translate：
void
AddrSpace::Translate(int addr, unsigned int* vpn, unsigned int *offset)
{
int page = -1;
int off = 0;
if(addr >= numPages * PageSize - UserStackSize)
//addr位于pageTable的userStack段中
{
   int userPages = numPages - StackPages;
   page = userPages + (addr - userPages * PageSize) / PageSize;
   off = (addr - userPages * PageSize) % PageSize;
}
else if(noffH.uninitData.size > 0 && addr >= noffH.uninitData.virtualAddr)
//addr位于uninitData
{
   page = divRoundUp(noffH.code.size, PageSize) + divRoundUp(noffH.initData.size, PageSize) +
    (addr-noffH.uninitData.virtualAddr) / PageSize;
   off = (addr - noffH.uninitData.virtualAddr) % PageSize;
}
else if(noffH.initData.size> 0 && addr >= noffH.initData.virtualAddr)
{
//addr位于initData
   page = divRoundUp(noffH.code.size, PageSize) + (addr-noffH.initData.virtualAddr) / PageSize;
   off = (addr - noffH.initData.virtualAddr) % PageSize;
}
else
{
//addr位于code中
   page = addr / PageSize;
   off = addr % PageSize;
}
*vpn = page;
*offset = off;
// printf("vpn is %d, offset is %d\n",*vpn,*offset);
}
如此可以计算出正确的地址了，那么当然要修改Machine::Translate中的求vpn和offset的语句为：currentThread->space->Translate(virtAddr, &vpn, &offset);
再来，看一下在exception.cc中对于缺页异常的处理：

else if(which == PageFaultException)
{
  int badVAddr=(int)machine->ReadRegister(BadVAddrReg);
   printf("badVAddr is %d\n",badVAddr);
   currentThread->space->FIFO(badVAddr); [1]
   stats->numPageFaults++;
   machine->registers[NextPCReg] = machine->registers[PCReg];
   machine->registers[PCReg]-=4;
   printf("PCReg = %d, NextPCReg = %d\n",machine->registers[PCReg],machine->registers[NextPCReg]);
}
[1]AddrSpace::FIFO的实现，首先要将badVaddr通过Translate转换成pageTable的虚页号newPage，然后通过FIFO获得将要被换出mainMemory的虚页号oldPage，使用这两个页号调用Swap函数，进行页的换入和换出。
void AddrSpace::FIFO(int badVAddr)
{  
unsigned int oldPage = virtualMem[p_vm];
unsigned int newPage;
unsigned int temp;
Translate(badVAddr, &newPage,&temp);
ASSERT(newPage < numPages);
// printf("newPage is %d\n",newPage);
virtualMem[p_vm]=newPage;
p_vm = (p_vm + 1) % MemPages;

printf("swap vm page %d: %d==>%d\n",pageTable[oldPage].physicalPage,
   pageTable[oldPage].virtualPage,pageTable[newPage].virtualPage);
Swap(oldPage,newPage); [2]
}
[2]Swap函数通过获取到的oldPage和newPage，首先将oldPage换出mainMemory，然后再将newPage换进到mainPage，这个过程又需要分别调用WriteBack和ReadIn两个函数实现。
void
AddrSpace::Swap(int oldPage, int newPage)
{
WriteBack(oldPage); [3]
pageTable[newPage].physicalPage = pageTable[oldPage].physicalPage;
pageTable[oldPage].physicalPage = -1;
pageTable[oldPage].valid = FALSE;

pageTable[newPage].valid = TRUE;
pageTable[newPage].use = TRUE;
pageTable[newPage].dirty = FALSE;
ReadIn(newPage); [4]
Print();
}
[3]如果oldPage在用户程序运行的过程中曾经被修改过，（系统自动将该页的dirty位置1）将oldPage换出内存之前就需要先将修改的数据写回。在写回时，根据换出页的type的不同就需要进行不同的处理，其处理分类如表2所示。

void
AddrSpace::WriteBack(int oldPage)
{ //before change the oldpage's physicalPage
if(pageTable[oldPage].dirty)
{
  switch(pageTable[oldPage].type)
   {
   case vmcode:
    case vminitData:
     ASSERT(pageTable[oldPage].type!=vmcode);
     ASSERT(pageTable[oldPage].type!=vminitData);
     executable->WriteAt(&(machine->mainMemory[pageTable[oldPage].physicalPage * PageSize]),PageSize, pageTable[oldPage].inFileAddr);
     break;
    case vmuninitData:
    case vmuserStack:
    pageTable[oldPage].inFileAddr = (SwapBitmap->Find()) * PageSize;
//注意，此处正是前文所指，当vmuninitData和vmuserStack的inFileAddr>=0时，表明此页已经被修改过，再次读入时需要将其从SWAP中读取。
     SwapFile->WriteAt(&(machine->mainMemory[pageTable[oldPage].physicalPage * PageSize]),PageSize, pageTable[oldPage].inFileAddr);
     break;
   }
   pageTable[oldPage].dirty = FALSE;
}
}
[4]在读入一个newPage的时候，也需要进行分类讨论，vmcode和vminitData只需要从源文件读入即可，但对于vmuninitData、vmuserStack则要特别处理。如果vmuninitData或是vmuserStack从来没有被读入mainMemory并被修改（对应的inFileAddr = -1），那么则将分配给该页的mainMemory内容清零；如果vmuninitData或是vmuserStack曾经被读入到mainMemory并被修改（对应得inFileAddr >= 0），那么将该页从SWAP文件中读入。
void
AddrSpace::ReadIn(int newPage)
{ //after allocate the newpage's physicalPage
switch(pageTable[newPage].type)
{
   case vmcode:
   case vminitData:
    printf("copy from source file pageTable[newPage].inFileAddr:%d =====> mainMemorty[%d]\n", pageTable[newPage].inFileAddr, pageTable[newPage].physicalPage * PageSize);

    executable->ReadAt(&(machine->mainMemory[pageTable[newPage].physicalPage * PageSize]),PageSize, pageTable[newPage].inFileAddr);
    break;
   case vmuninitData:
   case vmuserStack:
   if(pageTable[newPage].inFileAddr >= 0)
    {
     printf("copy from swap file pageTable[newPage].inFileAddr:%d =====> mainMemorty[%d]\n", pageTable[newPage