nachos-虚拟内存管理_assertion failed: line 108 file ../userprog/except

nachos虚拟内存实验

---

内容一、总体概述

本次实验主要是通过阅读相关代码,了解 nachos用户程序的执行过程,之后完成TLB,页表和虚拟内存等的实现。。其中第一部分主要内容是实现TLB相关异常处理和置换算法，当前的 nachos只支持单个用户程序,没有用到TLB。第二部分的主要内容是实现全局内存管理机制,使得 nachos内存可以同时存在多个线程。第三部分的主要内容是实现程序运行过程中发生缺页中断时，才会将所需的页面从磁盘调入内存。Challenge部分是增加线程挂起状态以及实现倒排页表。

内容二、任务完成情况

任务完成列表（Y/N）

具体Exercise的完成情况

1.Exercise1 源代码阅读

• 阅读code/userprog/progtest.cc，着重理解nachos执行用户程序的过程，以及该过程中与内存管理相关的要点。
• 阅读code/machine目录下的machine.h(cc)，translate.h(cc)文件和code/userprog目录下的exception.h(cc)，理解当前Nachos系统所采用的TLB机制和地址转换机制。

(1)用户程序执行过程

userprog/progtest.cc定义函数
StartProcess主要功能是实现用户程序启动，
如果我们希望执行test中的用户程序，
那么我们进入userprog，执行./nachos -x …/test/
（用户程序），通过识别-x 参数，nachos 调用
StartProcess 执行用户程序
（具体实现在 threads/main.cc）
StartProcess 的基本流程是:
通过文件系统定义的 OpenFile 打开相关文件
通过 AddrSpace的构造函数建立用户空间，装载文件
通过 AddrSpace 的InitRegisters 函数初始化用户寄存器
通过 AddrSpace 的RestoreState 函数装载页表
通过machine的Run 函数运行用户程序
AddrSpace 的构造函数实现在 userprog/addrspace.cc，主要流程是：
获取文件头，大小端做适宜转换
通过文件头计算文件所需空间，包括代码段，初始化数据段，未初始化数据段，栈空间 4 个部分
通过文件所需空间计算出文件所需的虚拟页面数量，创建用户空间页表，指示了第 i 个虚拟页对应第 i 个物理页，将用户程序的正文段和相关数据依次调入内存。
AddrSpace 的 InitRegisters 函数实现在 userprog/addrspace.cc，主要流程是：
初始化普通寄存器（初始化为 0）
初始化当前指令指针（PC，初始化为 0）
初始化下一条指令指针（初始化为 4）
初始化栈指针（地址空间尾部适当前移）
AddrSpace 的 RestoreState 函数实现在 userprog/addrspace.cc，主要流程是：
将页表装载到machine 类中
准备执行用户程序machine 的Run函数实现在machine/mipssim.cc，基本流程是：
通过 OneInstruction 函数完成指令译码和执行
通过interrupt 的 OneTick 函数使得时钟前进
machine 的Run 函数通过 machine 的ReadMem 函数读内存数据，通过 machine的WriteMem 函数写内存数据，两个函数的实现在 machine/translate.cc，核心是 translate 函数
translate 函数实现在machine/translate.cc，主要功能是实现虚拟地址到物理地址的转换，translate 函数可能返回相应的错误，在这样的情况下，ReadMem 函数/WriteMem 函数调用 RaiseException 函数进行处理，
RaiseException 函数定义在 machine/machine.cc，基本流程是将错误信息存储在特定位置，调用 ExceptionHandler 函数处理不同的错误，
ExceptionHandler函数实现在userprog/exception.cc，主要流程是根据错误信息处理不同错误。
目前支持的错误：

NoException,	         //  正常 
SyscallException,	      //  系统调用 
PageFaultException,	   //  缺页（页表/快表） ReadOnlyException,	   //  访问只读页面 
BusErrorException,	   //  总线错误
AddressErrorException,  //  访问地址对齐错误/超出范围 OverflowException,	   //  算数溢出 
IllegalInstrException,  //  非法指令 
NumExceptionTypes
1
2
3
4
5
6
7

寄存器支持：

（2）TLB 机制和地址转换机制

表项维护的位置是machine/translate.h 中 TranslationEntry 数据结构

Class TranslationEntry {
public:
int  virtualPage;   //  虚拟页号 
int  physicalPage;  //  物理页号
boot  valid;	     //  该Entry 是否使用，TRUE 表示使用
bool readOnly;     //  对应页的访问属性，TRUE 示只读，否则为读写 
bool use;	       //  该Entry 是否被使用过，每次访问后置为TRUE 
bool  dirty;		//  对应的物理页使用情况，TRUE 表示被写过
}
1
2
3
4
5
6
7
8
9

相关参数

以下参数定义在filesys/disk.h 
#define SectorSize 128
以下参数定义在machine/machine.h
#define PageSize SectorSize #define NumPhysPages 32
#define MemorySize (NumPhysPages * PageSize) 
#define TLBSize 4
1
2
3
4
5
6

TLB 初始化的位置是machine/machine.cc 中machine 的构造函数

TLB 的使用的位置是machine/translate.cc中的translate函数，基本流程是遍历TLB 数组，查找是否有对应映射，如果有，那么 TLB 命中，直接进行物理地址转换，否则，TLB 没有命中，标志 PageFaultException，进入Exception处理。（目前还没有对应的处理函数）
地址转换机制的位置是machine/translate.cc中的translate 函数，基本流程是:通过虚拟地址得到vpn和offset，通过TLB或是 Pagetable得到vpn对应的ppn,（否则抛出异常，在异常处理函数中做处理，但目前这部分没有实现），通过ppn 和offset 得到物理地址，返回物理地址。
需要说明的是，在处理完TLB的miss或者Pagefault 之后，不需要将PC+4，因为异常处理函数结束后，返回的最终位置会是OneInstruction函数的取指阶段。取指失败后，OneInstruction函数会退出，然后再用相同的PC取指。而这次就能够TLB hit或者pagetable hit了。
machine/machine.cc 的 Machine 类模拟内存，重要函数包括

Run 运行用户程序
ReadRegister/WriteRegister	读/写寄存器 
OneInstruction	执行一条指令 
ReadMem/WriteMem	读/写内存
Translate	 地址转换（虚拟地址->物理地址）  
RaiseException	抛出异常
userprog/addrspace.cc 的 AddrSpace 类模拟用户程序内存，重要函数包括 
InitRegisters	初始化相关寄存器
SaveState	保存机器状态 
RestoreState	恢复机器状态
1
2
3
4
5
6
7
8
9
10

2.Exercise2 TLB MISS 异常处理

修改code/userprog目录下exception.cc中的ExceptionHandler函数，使得Nachos系统可以对TLB异常进行处理（TLB异常时，Nachos系统会抛出PageFaultException，详见code/machine/machine.cc）

1、设计思路

首先Translate()方法,启动TLB，让用户程序在运行的时候先访问 TLB,如果出现 TLB MISS,会立刻抛出一个 RaiseException(),然后通过 ExceptionHandler()处理这个缺页异常,处理的动作就是让系统从pageTable 页表中查找要找的页表项。

2、userprog/Makefile

我们需要使用TLB，但是TLB并没有启用（在Exercise1里面解释过），所以我们需要先在userprog/Makefile添加宏。

然后在machine/machine.h中对USE_TLB进行宏定义，只有这样宏才能真正起作用。

3、machine/translate.cc

因为系统是默认没有启用TLB的，但是我们现在启用了TLB，所以我们应该注释掉ASSERT(tlb == NULL || pageTable == NULL); ,否则会报错Assertion failed: line 203, file “…/machine/translate.cc”

4、userprog/exception.cc

修改ExceptionHandler函数，因为之前系统是没有PageFaultException异常的（因为之前系统默认是把物理页面全部装入内存的，也没有启用TLB所以不会出现PageFaultException），所以我们需要添加PageFaultException，并进行处理。

else if(which == PageFaultException){
	//发生缺页中断则让TLBMissCount++
	TLBMissCount++;
	if(machine->tlb == NULL){
	     //页表失效，因为默认不会出现所以直接用ASSERT（FALSE）；
	     ASSERT(FALSE);
	}
	else{
	     //快表失效，处理流程首先调用machine的ReadRegister函数，从BadVAddrReg寄存器中取出发生异常的虚拟地址，并算出vpn
	     //DEBUG('m',"=> TLB miss (no TLB entry)\n");
	     int BadVAddr = machine->ReadRegister(BadVAddrReg);
	     TLBMissHandler(BadVAddr);
	     //TLBAlgoFIFO(BadVAddr);    //FIFO算法测试
	     //TLBAlgoClock(BadVAddr);  //CLOCK时钟算法测试
	    }
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int position = 0;
void TLBMissHandler(int virtAddr) //页表失效处理函数
{
     unsigned int vpn;
     vpn = (unsigned) virtAddr / PageSize;
     TranslationEntry page = machine->pageTable[vpn];
     
     if(!page.valid){
	DEBUG('m',"\t=> Page miss\n");
	page = PageFaultHandler(vpn);
     }
     TLBAlgoClock(virtAddr);  //处理快表失效
}
1
2
3
4
5
6
7
8
9
10
11
12
13

5、测试结果

Exercise 3 置换算法

为TLB机制实现至少两种置换算法，通过比较不同算法的置换次数可比较算法的优劣。

1、FIFO算法

算法的思想是每次淘汰最先进入TLB的页面。具体实现方式则是每次移除块表数组的第一项，然后一次将后面的往前移，新的表项放在快表数组的尾项。
userprog/exception.cc

void TLBAlgoFIFO(int virtAddr)
{
      int position1 = -1;
      unsigned int vpn;
      vpn = (unsigned)virtAddr / PageSize;
      //寻找空的TLB数组
      for(int i=0; i<TLBSize;i++){
	if(machine->tlb[i].valid == FALSE){
	    position1 = i;
	    break;
	}
      }
      //如果满了，移除首页，然后把每一项往前移，然后放在最后一项
      if(position1 == -1){
	position1 = TLBSize - 1;
	for(int i=0;i<TLBSize - 1;i++){
		machine->tlb[i] = machine->tlb[i+1];
	   }
	}
	machine->tlb[position1] = machine->pageTable[vpn];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2、CLOCK时钟置换算法

Nachos系统已经定义了TLB的use和valid，所以我们可以很方便的实现时钟算法。具体实现是首先判断valid的值，看该位置是否被访问过，如果为false则直接进行替换；如果为true，则进一步判断use的值，来看是否被修改过，如果修改过则将其值置为false，然后判断下一位。如果为use为false则直接进行替换。

void TLBAlgoClock(int virtAddr)
{
      unsigned int vpn;
      vpn = (unsigned) virtAddr / PageSize;
      while(1){
	position3 %= TLBSize;
	if(machine->tlb[position3].valid == FALSE){
	    break;
	}
	else{
	     if(machine->tlb[position3].use){
		  //更新use的值
	          machine->tlb[position3].use = FALSE;
		  position3++;
	      }
	      else{break;}
	}
      }
	machine->tlb[position3] = machine->pageTable[vpn];
	machine->tlb[position3].use = TRUE;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3、测试两个算法，并打印出TLB相关信息

首先在translate.cc中设置两个全局变量， TLBMissCount = 0;(记录TLB MISS)；TranslateCount = 0(记录进程页面访问次数)。并在machine.h中进行扩展声明。然后在每次发生PageFaultException让TLBMissCount+1；在每次执行TranslateCount函数时，让TranslateCount+1。分别调用两个算法最终在程序执行结束退出后调用debug函数打印出TLB缺页次数，缺页率等信息。

4、测试结果

测试说明：我试用了系统提供的sort排序进行测试，在最开始的时候报错Assertion failed: line 81, file "…/userprog/addrspace.cc，仔细阅读代码发现是因为系统给的sort排序超出了内存限制，同时原来sort在最后接触进行的系统调用EXIT 尚未在本系统中实现，所以我在原来的基础上进行了修改，并重新make。

#include "syscall.h"

int A[20];	/* size of physical memory; with code, we'll run out of space!*/

int
main()
{
    int i, j, tmp;

    /* first initialize the array, in reverse sorted order */
    for (i = 0; i < 20; i++)		
        A[i] = 20 - i;

    /* then sort! */
    for (i = 0; i < 19; i++)
        for (j = i; j < (19 - i); j++)
	   if (A[j] > A[j + 1]) {	/* out of order -> need to swap ! */
	      tmp = A[j];
	      A[j] = A[j + 1];
	      A[j + 1] = tmp;
    	   }
    //Exit(A[0]);		/* and then we're done -- should be 0! */
    Halt();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

我将原来的数组缩小为20，同时结束之后进行halt系统调用.

FIFO算法测试结果:

CLOCK 时钟算法测试结果:

对比之后发现,时钟算法的效率明显优于FIFO算法。

分页式内存管理

目前Nachos系统中，类Class Thread的成员变量AddrSpace* space中使用TranslationEntry* pageTable来管理内存。应用程序的启动过程中，对其进行初始化；而在线程的切换过程中，亦会对该变量进行保存和恢复的操作（使得类Class Machine中定义的Class Machine::TranslationEntry* pageTable始终指向当前正在运行的线程的页表）。

Exercise 4 内存全局管理数据结构

设计并实现一个全局性的数据结构（如空闲链表、位图等）来进行内存的分配和回收，并记录当前内存的使用状态。

1、基本思路

这里我选择使用位图(bitMap)来管理空闲的内存。在machine类中增加成员变量bitmap，类型为数组。因为Nachos系统拥有32位的物理页面，所以设置了一个大小为32的数组，初始值都为0，分配之后设置为1。每次申请物理内存的时候调用allocateMemory函数来寻找一块空闲的页面 ，如果没有空闲的页面则返回-1。freeMemory函数则是负责回收内存的。具体就是将当前页表对应的所有位图位置设为0。

2、machine/machine.h

    unsigned int bitmap[32];
    int allocateMemory(void);
    void freeMemory(void);

1
2
3
4

3、machine/machine.cc

实现上述函数

int Machine::allocateMemory()
{
      for(int i=0;i<32;i++)
      {
	  if(bitmap[i]==0)
	  {
	       bitmap[i]=1;
		printf("allocate memory %d\n",i);
		return i;
	  }
      }
      return -1;
}


void Machine::freeMemory(void)
{
     for(int i=0;i<NumPhysPages;i++)
     {
	//int current=pageTable[i].physicalPage;
	if(pageTable[i].threadId == currentThread->getTid())
	{
	    if(bitmap[i]==1){
	          printf("free Memory %d\n",i);
	          bitmap[i]=0;
	    }
	}
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

4、添加内存分配回收机制

分配内存的allocateMemory函数主要是在内存初始化的时候调用的,主要通过修改userprog/addrspace.cc文件。而内存的回收则是在程序结束之后通过Exit进行调用，而系统还未实现Exit系统调用，所以在这个部分我们还需要实现Exit，具体实现是修改userprog/exception.cc文件。
addrspace.cc

//addrspace.cc中构造函数做的修改
    pageTable = new TranslationEntry[numPages];
    for (i = 0; i < numPages; i++) {
	pageTable[i].virtualPage = i;	// for now, virtual page # = phys page #
	//pageTable[i].physicalPage = i;
	pageTable[i].physicalPage = machine->allocateMemory();
1
2
3
4
5
6

//exception.cc中的ExceptionHandler(ExceptionType which)函数中做的修改
 if ((which == SyscallException)) {
	if((type == SC_Halt)){
	DEBUG('T', "TLB Miss: %d, TLB Hit: %d, Total Translate: %d, TLB Miss Rate: %.2lf%%\n",
	TLBMissCount,TranslateCount-TLBMissCount,TranslateCount,(double)(TLBMissCount*100)/(TranslateCount));
   	interrupt->Halt();
	}
	else if(type == SC_Exit){
	     printf("program exit\n");
	     if(currentThread->space != NULL){
		  machine->freeMemory();
		  delete currentThread->space;
		  currentThread->space = NULL;
		  currentThread->Finish();
		  int nextPc=machine->ReadRegister(NextPCReg);
		  machine->WriteRegister(PCReg,nextPc);
	     }

	}
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

5、测试结果

为了方便截图，我们直接运行一个空的程序，将原有的halt.c进行修改，注释掉Halt()(后面的测试基本上都使用修改后的halt.c文件进行测试)。

Exercise 5 多线程支持

1、基本思想

目前因为系统的内存中同时只能存在一个线程，所以规定系统将程序的内容调入内存时是根据虚拟地址来确定的，并且规定了这个虚拟地址和物理地址相同。基于上一个exercise修改之后，我们将实现掉入内存的位置根据物理地址来确定。同时之前在程序退出之后因为默认系统同时只存在一个线程，所以系统就运行结束了，现在我们因为有多个线程，所以在程序结束之后我们需要切换到下一个程序。

2、实现程序运行结束之后切换

//exception.cc中的ExceptionHandler(ExceptionType which)函数中做的修改
else if(which == PageFaultException){
	//发生缺页中断则让TLBMissCount++
	TLBMissCount++;
	if(machine->tlb == NULL){
	     //页表失效，因为默认不会出现所以直接用ASSERT（FALSE）；
	     ASSERT(FALSE);
	}
	else{
	     //快表失效，处理流程首先调用machine的ReadRegister函数，从BadVAddrReg寄存器中取出发生异常的虚拟地址，并算出vpn
	     //DEBUG('m',"=> TLB miss (no TLB entry)\n");
	     int BadVAddr = machine->ReadRegister(BadVAddrReg);
	     TLBMissHandler(BadVAddr);
	     //TLBAlgoFIFO(BadVAddr);    //FIFO算法测试
	     //TLBAlgoClock(BadVAddr);  //CLOCK时钟算法测试
	    }
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3、修改地址空间的上下文交换

在进上下文交换的时候因为切换了程序，所以TLB原有的内容则失效了，所以我们应该清楚TLB的内容，否则会频繁出现页面替换，降低效率。

void AddrSpace::SaveState() 
{
      for(int i=0;i<TLBSize;i++){
	  machine->tlb[i].valid = FALSE;
      }
}
1
2
3
4
5
6

4、测试函数

Nachos执行用户程序的函数入口是通过StartProcess函数，但是这个函数只能执行一个用户程序。因此我们仿照StartProcess的思想，重新构造了一个新的函数入口StartTwoThread用于执行两个程序。同时为了方便，我们将两个线程载入同一个程序（就是之前的halt.c)。

Thread* CreateSingleThread(OpenFile *executable,int number)
{
      printf("Creating user program thread %d\n",number);
      char ThreadName[20];
      sprintf(ThreadName,"User program %d",number);
      Thread *thread = new Thread(strdup(ThreadName),0);//注意这里设置的新线程的优先级必须高于main的优先级，否则线程不能主动放弃处理机需要手动实现
      AddrSpace *space;
      space = new AddrSpace(executable);
      thread->space = space;
      return thread;
}
1
2
3
4
5
6
7
8
9
10
11

void UserProgThread(int number)
{
     printf("Running user program thread %d\n",number);
     currentThread->space->InitRegisters();
     currentThread->space->RestoreState();
     currentThread->space->PrintState();
     machine->Run();
     ASSERT(FALSE);
}
1
2
3
4
5
6
7
8
9

void
StartTwoThread(char *filename)
{
     OpenFile *executable = fileSystem->Open(filename);
     if(executable == NULL){
	printf("Unable to open file %s\n",filename);
	return ;
     }
     //CreateSingleThread函数主要实现了原来StartProcess函数的
     //space = new AddrSpace(executable,5);和
     //currentThread->space = space;部分
     Thread *thread1 = CreateSingleThread(executable,1);
     Thread *thread2 = CreateSingleThread(executable,2);
     delete executable;
     //UserProgThread函数的目的是进行相关寄存器的初始化以及加载页表
     thread1->Fork(UserProgThread,1);
     thread2->Fork(UserProgThread,2);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

实现一个在类AddrSpace中实现一个PrintState函数，打印出Address Space的相关信息。

void
AddrSpace::PrintState()
{
   printf("=== %s ===\n","Address Space Information");
   printf("numPages = %d\n",numPages);
   printf("VPN\tPPN\tvalid\tR0\tuse\tdirty\n");
   for(int i=0;i<numPages;i++){
	printf("%d\t",pageTable[i].virtualPage);
        printf("%d\t",pageTable[i].physicalPage);
        printf("%d\t",pageTable[i].valid);
        printf("%d\t",pageTable[i].use);
        printf("%d\t",pageTable[i].dirty);
        printf("%d\t",pageTable[i].readOnly);
        printf("\n");
   }
   printf("========================================\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

5、修改main函数

原来的程序执行函数入口通过-x调用StartProcess,但是现在我们修改了程序入口，所以我们应该新增参数-X调用StartTwoThread

#ifdef USER_PROGRAM
        if (!strcmp(*argv, "-x")) {        	// run a user program
	    ASSERT(argc > 1);
            StartTwoThread(*(argv + 1));
            argCount = 2;
        } else if (!strcmp(*argv, "-c")) {      // test the console
	    if (argc == 1)
	        ConsoleTest(NULL, NULL);
	    else {
		ASSERT(argc > 2);
	        ConsoleTest(*(argv + 1), *(argv + 2));
	        argCount = 3;
	    }
	    interrupt->Halt();		// once we start the console, then 
					// Nachos will loop forever waiting 
					// for console input
	}
#endif // USER_PROGRAM
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

6、测试结果

由于Exercise6和Exercise7是密切关联的，所以我把两个实验放在一起写。

Exercise 6 缺页中断处理

基于TLB机制的异常处理和页面替换算法的实践，实现缺页中断处理（注意！TLB机制的异常处理是将内存中已有的页面调入TLB，而此处的缺页中断处理则是从磁盘中调入新的页面到内存）、页面替换算法等。

Exercise 7 lazy-loading

我们已经知道，Nachos系统为用户程序分配内存必须在用户程序载入内存时一次性完成，故此，系统能够运行的用户程序的大小被严格限制在4KB以下。请实现Lazy-loading的内存分配算法，使得当且仅当程序运行过程中缺页中断发生时，才会将所需的页面从磁盘调入内存。

1、基本思想

Exercise 6缺页中断处理的思想是将发生缺页中断的虚拟页面从磁盘调入物理页面，也就是虚拟内存的概念，在这里的虚拟内存通过filesystem创建了一个virtual_memory模拟。当发生PageFaultException时（分为两种情况，页表失效和快表失效）通过ExceptionHandler函数处理，前面实现了快表失效，在这里需要实现页表失效处理。而之前Nachos系统本身是不会发生缺页中断的，因为系统直接将程序一次性装载进入内存 ，所以不存在页表失效，这就需要结合Exercise 7 的内存分配机制Lazy-loading才可能发生页表失效。
对于Lazy-loading即按需请求调页而不是一次性全部装载，这就需要修改Addspace的构造函数，将用户程序的内容先装载到虚拟内存，等需要的时候再从virtual_memory中调入。

2、创建虚拟内存

在基本思想中已经描述过，通过fileSystem创建一个virtual_memory文件来模拟虚拟内存，同时将数据装载到virtual_memory中。为了尽可能的使每个实验代码能够运行，我这里重构了addspace的构造函数，首先在addspace.h中声明新的构造函数。

    AddrSpace(OpenFile *executable);	// Create an address space,
					// initializing it with the program
					// stored in the file "executable"
    AddrSpace(OpenFile *executable,int lab);      //虚拟内存实验所重构的构造函数,lab参数没有意义
    ~AddrSpace();			// De-allocate an address space
1
2
3
4
5

AddrSpace::AddrSpace(OpenFile *executable,int lab)
{
    NoffHeader noffH;
    unsigned int i, size;

    executable->ReadAt((char *)&noffH, sizeof(noffH), 0);
    if ((noffH.noffMagic != NOFFMAGIC) && 
		(WordToHost(noffH.noffMagic) == NOFFMAGIC))
    	SwapHeader(&noffH);
    ASSERT(noffH.noffMagic == NOFFMAGIC);

// how big is address space?
    size = noffH.code.size + noffH.initData.size + noffH.uninitData.size 
			+ UserStackSize;	// we need to increase the size
						// to leave room for the stack
    numPages = divRoundUp(size, PageSize);
    size = numPages * PageSize;
    //上面的内容与原来的一样
    //用filesystem创建VirtualMemory文件，运行nachos之后，会在userprog目录下面生成该文件
    bool success_create_vm = fileSystem->Create("VirtualMemory",size);
    ASSERT(numPages <= NumPhysPages);
    //pageTable = new TranslationEntry[numPages];
    for(i=0;i<numPages;i++){
       machine->pageTable[i].virtualPage = i;
       machine->pageTable[i].physicalPage = machine->allocateMemory();   //因为我们没有将用户程序内容装载进内存，所以physicalPage的值可以为0
       machine->pageTable[i].valid = TRUE;   //表示没有从磁盘装载任何页面进内存
       machine->pageTable[i].use = FALSE;
       machine->pageTable[i].dirty = FALSE;
       machine->pageTable[i].readOnly = FALSE;
       machine->pageTable[i].threadId = currentThread->getTid();
    }
        //初始化整个物理内存
    bzero(machine->mainMemory,MemorySize);
    OpenFile *vm = fileSystem->Open("VirtualMemory");
    

    char *virtualMemory_temp;
    virtualMemory_temp = new char[size];  //该数组主要是用于将用户程序的内容写入磁盘的中间过度
    for(i=0;i<size;i++)
	virtualMemory_temp[i] = 0;


   if(noffH.code.size>0){
	DEBUG('a',"\tCopying code segment, at 0x%x, size %d\n",
	noffH.code.virtualAddr,noffH.code.size);
	executable->ReadAt(&(virtualMemory_temp[noffH.code.virtualAddr]),
	noffH.code.size,noffH.code.inFileAddr);
	vm->WriteAt(&(virtualMemory_temp[noffH.code.virtualAddr]),
	noffH.code.size,noffH.code.virtualAddr*PageSize);
   }
   if(noffH.initData.size >0){
	DEBUG('a',"\tCopying data segment, at 0x%x, size %d\n",
		noffH.initData.virtualAddr,noffH.initData.size);
	executable->ReadAt(&(virtualMemory_temp[noffH.initData.virtualAddr]),
		noffH.initData.size,noffH.initData.inFileAddr);
	vm->WriteAt(&(virtualMemory_temp[noffH.initData.virtualAddr]),
		noffH.initData.size,noffH.initData.virtualAddr*PageSize);
   }
   //上面的内容仿照原始的addspace构造函数编写
   delete vm;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

3、缺页处理

当发生缺页异常时，通过ExceptionHandler函数调用TLBMissHandler函数，TLBMissHandler将将缺页异常的地址装换成虚拟地址，然后调用PageFaultHandler函数，该函数首先通过machine->allocateMemory()寻找一个空闲页，如果返回-1则调用NaivePageReplacement函数，该函数的作用是进行页面替换。首先寻找一个未被修改过的页面进行替换，如果找到则结束；否则将第一个(1,1)的页面进行替换，并将页表内容写会磁盘。

int NaivePageReplacement(int vpn)
{
    int pageFrame = -1;
    for(int temp_vpn = 0;temp_vpn < machine->pageTableSize,temp_vpn != vpn;temp_vpn++){
	if(machine->pageTable[temp_vpn].valid){
    	    if(!machine->pageTable[temp_vpn].dirty){
		pageFrame = machine->pageTable[temp_vpn].physicalPage;
		break;
	    }
	}
    }
    if(pageFrame == -1){
	for(int replaced_vpn = 0; replaced_vpn < machine->pageTableSize, replaced_vpn != vpn;replaced_vpn++){
	     if(machine->pageTable[replaced_vpn].valid){
		  machine->pageTable[replaced_vpn].valid = FALSE;
		  pageFrame = machine->pageTable[replaced_vpn].physicalPage;
 		  //将页表写回磁盘
		  OpenFile *vm = fileSystem->Open("VirtualMemory");
		  vm->WriteAt(&(machine->mainMemory[pageFrame*PageSize]),
			PageSize,replaced_vpn*PageSize);
		  delete vm;
		  break;
	     }
	}
    }
    return pageFrame;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

TranslationEntry PageFaultHandler(int vpn)
{
     int pageFrame = machine->allocateMemory();
     if(pageFrame == -1){
	pageFrame == NaivePageReplacement(vpn);
     }
     machine->pageTable[vpn].physicalPage = pageFrame;
     OpenFile *vm = fileSystem->Open("VirtualMemory");
     vm->ReadAt(&(machine->mainMemory[pageFrame*PageSize]),PageSize,vpn*PageSize);
     delete vm;
     machine->pageTable[vpn].valid = TRUE;
     machine->pageTable[vpn].use = FALSE;
     machine->pageTable[vpn].dirty = FALSE;
     machine->pageTable[vpn].readOnly = FALSE;
     currentThread->space->PrintState(); //打印地址空间信息
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int position = 0;
void TLBMissHandler(int virtAddr) //页表失效处理函数
{
     unsigned int vpn;
     vpn = (unsigned) virtAddr / PageSize;
     TranslationEntry page = machine->pageTable[vpn];
     
     if(!page.valid){
	DEBUG('m',"\t=> Page miss\n");
	page = PageFaultHandler(vpn);
     }
     TLBAlgoClock(virtAddr);  //处理快表失效
}
1
2
3
4
5
6
7
8
9
10
11
12
13

void
ExceptionHandler(ExceptionType which)
{
    int type = machine->ReadRegister(2);

    if ((which == SyscallException)) {
	if((type == SC_Halt)){
	DEBUG('T', "TLB Miss: %d, TLB Hit: %d, Total Translate: %d, TLB Miss Rate: %.2lf%%\n",
	TLBMissCount,TranslateCount-TLBMissCount,TranslateCount,(double)(TLBMissCount*100)/(TranslateCount));
   	interrupt->Halt();
	}
	else if(type == SC_Exit){
	     printf("program exit\n");
	     if(currentThread->space != NULL){
		  machine->freeMemory();
		  delete currentThread->space;
		  currentThread->space = NULL;
		  currentThread->Finish();
		  int nextPc=machine->ReadRegister(NextPCReg);
		  machine->WriteRegister(PCReg,nextPc);
	     }

	}
    }
    else if(which == PageFaultException){
	//发生缺页中断则让TLBMissCount++
	TLBMissCount++;
	if(machine->tlb == NULL){
	     //页表失效，因为默认不会出现所以直接用ASSERT（FALSE）；
	     ASSERT(FALSE);
	}
	else{
	     //快表失效，处理流程首先调用machine的ReadRegister函数，从BadVAddrReg寄存器中取出发生异常的虚拟地址，并算出vpn
	     //DEBUG('m',"=> TLB miss (no TLB entry)\n");
	     int BadVAddr = machine->ReadRegister(BadVAddrReg);
	     TLBMissHandler(BadVAddr);
	     //TLBAlgoFIFO(BadVAddr);    //FIFO算法测试
	     //TLBAlgoClock(BadVAddr);  //CLOCK时钟算法测试
	    }
	} 
    else {
	printf("Unexpected user mode exception %d %d\n", which, type);
	ASSERT(FALSE);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

4、测试结果

Challenge2 多线程实现基本思路：

前面实现的倒排页表并不是严格意思的倒排页表，实际上，倒排页表与进程/线程数量无关，所以，我们需要在 machine 类维护倒排页表，而不是在 addrspace类维护倒排页表。
考虑到多线程共用倒排页表的实际情况，我们需要在页表项记录线程 ID

class TranslationEntry {
	...
	int threadID;
};
1
2
3
4

在mahine/machine.cc 的machine 类的构造函数完成倒排页表的初始化

#ifdef USE_TLB
    pageTable = new TranslationEntry[NumPhysPages];
     //初始化倒排页表
    for (i = 0; i < NumPhysPages; i++)
	pageTable[i].physicalPage = i;
	pageTable[i].virtualPage = i;
	pageTable[i].valid = FALSE;
	pageTable[i].use= FALSE;
        pageTable[i].dirty = FALSE;
	pageTable[i].readOnly = FALSE;
	pageTable[i].threadId = -1;
#else	// use linear page table
    tlb = NULL;
    pageTable = NULL;
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

考虑到所有线程共用相同倒排页表，不需要从线程内存空间载入页表,这样的修改同时意味着我们在addrspace 定义的页表失去了作用

void AddrSpace::RestoreState() 
{
   // machine->pageTable = pageTable;
    //machine->pageTableSize = numPages;
}
1
2
3
4
5

//由于引入了线程ID，在表项判断时增加判断内容
pageTable[i].threadID == currentThread->getThreadID()
//在表项修改时增加修改内容
machine->pageTable[pos].threadID = currentThread->getThreadID();
1
2
3
4

同时改写释放空间函数，根据线程ID 释放相关空间

void Machine::freeMemory(void)
{
     for(int i=0;i<NumPhysPages;i++)
     {
	//int current=pageTable[i].physicalPage;
	if(pageTable[i].threadId == currentThread->getTid())
	{
	    if(bitmap[i]==1){
	          printf("free Memory %d\n",i);
	          bitmap[i]=0;
	    }
	}
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

测试结果：

内容三：遇到的困难及解决方法

困难 1：理解#ifdef

根据nachos 的默认设置，TLB 没有开启，查看相关代码发现#ifdef 相关命令，查询相关资料得知，#ifdef 是条件编译的重要命令，所谓条件编译，就是对程序中的部分内容只在满足特定条件的情况下进行编译，条件编译包括许多指令，其中#ifdef 的常见形式为：
#ifdef 标识符
//程序段 1
#else
//程序段 2
#endif
这段语句的作用是当标识符已经被定义过(一般是用#define 命令定义)，则对程序段1 进行编译，否则编译程序段2。进一步查询相关资料，得知我们需要修改userprog/Makefile，开启 USE_TLB
DEFINES = … -DUSE_TLB

困难2：理解nachos文件系统

如果希望利用文件而不是内存的额外空间实现 Exercise6和 Exercise7,那么需要涉及 nahcos 文件系统。主要涉及的部分包括文件系统数据结构FileSystem和打开文件数据结构Openfile。
文件系统数据结构FileSystem 的重要函数包括
Create函数：基本功能是文件系统中创建固定大小的文件，如果创建成功，那么返回TRUE，否则返回 FALSE
Open函数：基本功能是打开已经存在的文件，返回的是打开文件数据结构
Remove函数：基本功能是删除已经存在的文件，如果删除成功，那么返回TRUE，否则返回FALSE
需要说明的是，如果我们希望关闭已经打开的文件，那么需要调用相应打开文件数据结构的析构函数
打开文件数据结构Openfile 的重要函数包括
Length函数：基本功能是返回文件长度
Seek函数：基本功能是移动当前文件位置指针
ReadAt函数：基本功能是从文件特定位置读取特定长度的数据到特定位置，返回值是实际读出的字节数
WriteAt函数：基本功能是从特定位置向文件特定位置写入特定长度的数据，返回值是实际写入的字节数
Read函数：基本功能是从文件读取特定长度的数据到特定位置，返回值是实际读出的字节数，基于ReadAt 函数实现
Write函数：基本功能是从特定位置向文件写入特定长度的数据，返回值是实际写入的字节数，基于WriteAt 函数实现

困难3 理解DEBUG

对DEBUG函数不熟悉，刚开始在对程序进行调试的时候总是使用printf函数，然而nachos系统定义的DEBUG函数功能更加强大。

内容四：收获及感想

实习课程和理论课程相得益彰。通过本次实习，我强化了对存储模型相关知识的理解，锻炼了编程能力。经过一段时间的接触，感觉对 nachos 系统有了一定的了解，对课程有了一定的兴趣，期待在以后的实习中能够了解nachos 更多的功能并且在此基础上进行更多的修改。

内容五：对课程的意见和建议

我觉得课程方式很好，老师讲课非常认真，对同学们也很宽容，布置给我们的实验虽然让我们在做的过程中一直怀疑人生，但是在实验完成之后回想整个过程，我们获得的提高非常巨大！由于实验逐渐变难，所以在实验过程中大家出现了很多分歧，也无法确定谁的想法是正确的，希望老师能在课上对实验进行一定的梳理。