Nachos实习——Lab2虚拟内存实习报告

水深无声 2022-11-22 05:19 255阅读 0赞

# Nachos实习——Lab2虚拟内存实习报告 #

### 文章目录 ###

*  Nachos实习——Lab2虚拟内存实习报告
 *   *  内容一：总体概述
     *  内容二：任务完成情况
     *  内容三：具体完成Exercise情况
     *   *  一、TLB异常处理
         *   *  Exercise 1 源代码阅读
             *   *  1、userprog/progtest.cc
                 *  2、machine/machine.cc和machine/machine.h
                 *  3、machine/translate.h(cc)和userprog/exception.h(cc)
             *  Exercise 2 TLB MISS异常处理
             *   *  1、设计思路
                 *  2、userprog/Makefile
                 *  3、machine/translate.cc
                 *  4、userprog/exception.cc
                 *  5、测试结果截图
             *  Exercise 3 置换算法
             *   *  1、FIFO算法
                 *  2、CLOCK时钟置换算法
                 *  3、测试两个算法，并打印出TLB相关信息
                 *  4、测试结果
         *  二、分页式内存管理
         *   *  Exercise 4 内存全局管理数据结构
             *   *  1、基本思路
                 *  2、machine/machine.h
                 *  3、machine/machine.cc
                 *  4、添加内存分配回收机制
                 *  5、测试结果
             *  Exercise 5 多线程支持
             *   *  1、基本思想
                 *  2、实现程序运行结束之后切换
                 *  3、修改地址空间的上下文交换
                 *  4、测试函数
                 *  5、修改main函数
                 *  6、测试结果
             *  Exercise 6 缺页中断处理
         *  三、Lazy-loading
         *   *  Exercise 7
             *   *  1、基本思想
                 *  2、创建虚拟内存
                 *  3、缺页处理
                 *  4、测试结果
         *  四、Challenges
         *   *  Challenge 1
             *  Challenge 2
             *   *  1、基本思想
                 *  2、machine/translate.h
                 *  3、machine/machine.cc
                 *  4、userprog/addrspace.cc
                 *  5、测试结果
     *  内容四：遇到的困难以及解决方法
     *   *  困难1：
         *  困难2:
     *  内容五：收获及感想
     *  内容六：对课程的意见和建议
     *  内容七：参考文献

## 内容一：总体概述 ##

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

## 内容二：任务完成情况 ##

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th align="center">Exercise 1</th> 
   <th align="center">Exercise 2</th> 
   <th align="center">Exercise 3</th> 
   <th align="center">Exercise 4</th> 
   <th align="center">Exercise 5</th> 
   <th align="center">Exercise 6</th> 
   <th align="center">Exercise 7</th> 
   <th align="center">Challenge</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><strong>完成情况</strong></td> 
   <td align="center"><strong>Y</strong></td> 
   <td align="center"><strong>Y</strong></td> 
   <td align="center"><strong>Y</strong></td> 
   <td align="center"><strong>Y</strong></td> 
   <td align="center"><strong>Y</strong></td> 
   <td align="center"><strong>Y</strong></td> 
   <td align="center"><strong>Y</strong></td> 
   <td align="center"><strong>Y</strong></td> 
  </tr> 
 </tbody> 
</table>

## 内容三：具体完成Exercise情况 ##

### 一、TLB异常处理 ###

目前，Nachos系统对于内存的管理是基于软件模拟的TLB机制。其工作原理、异常处理、替换算法等方面，与分页式内存管理非常相像。

#### Exercise 1 源代码阅读 ####

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

##### 1、userprog/progtest.cc #####

progtest.cc文件是Nachos系统中和执行用户程序相关的文件。在里面定义了两个函数。其中StartProcess函数是用来加载并执行用户程序的。具体流程如下：

*  首先传入文件名,并打开该文件。之后会对该文件的文件格式进行一个判断。
 *  之后通过类 AddrSpace(在userprog/addrspace.cc文件下定义)的构造函数为用户程序分配并初始化地址空间，分配给当前线程/
 *  初始化用户寄存器的值,调用 RestoreState函数,将 machine的 pageTable指向该 AddrSpace对象的页表，将页表加载到 machine中
 *  调用 machine>Run执行用户程序。

Progtest.cc中还有一个ConsoleTest函数,用于控制台输入输出的测试。

##### 2、machine/machine.cc和machine/machine.h #####

这两个文件主要用于模拟 nachos用户程序运行的机器。 machine.h中定义了一些内存相关的参数，如内存大小、TLB大小等，还有一些异常的种类和一些特殊用户寄存器的编号。还定义了两个类 Instruction和machine。类 Instruction用于将目标代码转为mips可执行的代码。Machine类模拟机器的运行。此外还有一个外部函数用来进行异常处理的。其中TLB的初始化是在machine/machine.cc文件中

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AfoGykpf-1604393159510)(/Users/jaggerqian/Library/Application Support/typora-user-images/image-20201029183142093.png)\]][img-AfoGykpf-1604393159510_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201029183142093.png]

目前默认是没有使用的，如需使用需要在userprog/Makefile文件中添加宏。

##### 3、machine/translate.h(cc)和userprog/exception.h(cc) #####

在translate头文件中定义了页表TranslationEntry类，包含物理页号、虚拟页号、有效位、访问位、只读位、更改位等属性。translate.cc文件中实现了machine的读写内存和地址转换功能。地址转换有两种情况，使用线性页表或使用TLB。目前没有使用tlb所以直接跳转到tlb=null下面执行。在执行地址转换过程中可能会抛出各种异常。而异常的处理则使用userprog/exception.h(cc)文件下的ExceptionHandler函数。

通过阅读以上文件，我画了一个用户程序执行图。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Edt79bSw-1604393159511)(/Users/jaggerqian/Library/Application Support/typora-user-images/image-20201027163038452.png)\]][img-Edt79bSw-1604393159511_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201027163038452.png]

#### Exercise 2 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添加宏  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70_pic_center]

##### 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){
        	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);
            }
            return;
    }
    int position = 0;
    void TLBMissHandler(int virtAddr)//快表失效处理函数
    {
        unsigned int vpn;
        vpn = (unsigned) virtAddr / PageSize;
        machine->tlb[position] = machine->pageTable[vpn];
      //下面的Exercise3才实现了具体快表置换算法，这里为了简化测试，只使用了2个size的TLB
        if(position==0) 
        	position = 1;
        else 
        	position = 0;
    }

##### 5、测试结果截图 #####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-K0qjgj2T-1604393159514)(/Users/jaggerqian/Library/Containers/com.tencent.xinWeChat/Data/Library/Application Support/com.tencent.xinWeChat/2.0b4.0.9/4bd6fb1bd54c6c60eedfec9d2b01e055/Message/MessageTemp/9e20f478899dc29eb19741386f9343c8/Image/1201603976836\_.pic\_hd.jpg)\]][img-K0qjgj2T-1604393159514_Users_jaggerqian_Library_Containers_com.tencent.xinWeChat_Data_Library_Application Support_com.tencent.xinWeChat_2.0b4.0.9_4bd6fb1bd54c6c60eedfec9d2b01e055_Message_MessageTemp_9e20f478899dc29eb19741386f9343c8_Image_1201603976836_.pic_hd.jpg]

#### 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];
            }
        }
        //更新TLB
        machine->tlb[position1] = machine->pageTable[vpn];
    }

##### 2、CLOCK时钟置换算法 #####

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

int position3 = 0;
    void TLBAlgoClock(int virtAddr)
    { 
        //寻找那个use和valid都为0的位置，选取的顺序为(0,0)->(0,1)->(1,0)->(1,1)
        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;
                }
            }
        }
        //更新TLB
        machine->tlb[position3] = machine->pageTable[vpn];
        machine->tlb[position3].use = TRUE;
    }

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

首先在translate.cc中设置两个全局变量， TLBMissCount = 0;(记录TLB MISS)；TranslateCount = 0(记录进程页面访问次数)。并在machine.h中进行扩展声明。

然后在每次发生PageFaultException让TLBMissCount+1；在每次执行TranslateCount函数时，让TranslateCount+1。分别调用两个算法最终在程序执行结束退出后调用debug函数打印出TLB缺页次数，缺页率等信息。

void
    ExceptionHandler(ExceptionType which)
    { 
        if ((which == SyscallException) && (type == SC_Halt)) { 
          	// 在程序执行结束后打印TLB信息
        		DEBUG('T', "TLB Miss: %d, TLB Hit: %d, Total Translate: %d, TLB Miss Rate: %.2lf%%\n",
            TLBMissCount, TranslateCount-TLBMissCount, TranslateCount, (double）(TLBMissCount*100)/(TranslateCount));      
        } else if(which == PageFaultException){ 
          //发生缺页终端则让TLBMissCount++
            TLBMissCount++;
        	if (machine->tlb == NULL) {  // linear page table page fault
    					……………………
            } else {  
                //TLBMissHandler(BadVAddr);//TLB MISS测试
                TLBAlgoFIFO(BadVAddr);//FIFO算法测试
                //TLBAlgoClock(BadVAddr);//CLOCK时钟算法测试
            }
            return;
        }
    }

> 记得在translate函数中让TranslateCount++

##### 4、测试结果 #####

> 测试说明：我试用了系统提供的sort排序进行测试，在最开始的时候报错`Assertion failed: line 81, file "../userprog/addrspace.cc`，仔细阅读代码发现是因为系统给的sort排序超出了内存限制，同时原来sort在最后接触进行的系统调用EXIT 尚未在本系统中实现，所以我在原来的基础上进行了修改，并重新make.
> 
> ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yJlN57OW-1604393159515)(/Users/jaggerqian/Library/Application Support/typora-user-images/image-20201031150848167.png)\]][img-yJlN57OW-1604393159515_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201031150848167.png]  
> 我将原来的数组缩小为20，同时结束之后进行halt系统调用.

**FIFO算法测试结果:**

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LRkv0dIz-1604393159515)(/Users/jaggerqian/Library/Application Support/typora-user-images/image-20201031150942119.png)\]][img-LRkv0dIz-1604393159515_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201031150942119.png]

**CLOCK 时钟算法测试结果:**

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kYwco9kl-1604393159516)(/Users/jaggerqian/Library/Application Support/typora-user-images/image-20201031151048608.png)\]][img-kYwco9kl-1604393159516_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201031151048608.png]

对比之后发现,时钟算法的效率明显优于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 #####

新增变量bitmap，和函数allocateMemory\\freeMemory.

class Machine { 
      public:
    		unsigned int bitmap[32]; 
        int allocateMemory(void); 
        void freeMemory(void);
    };

##### 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<pageTableSize;i++)
        { 
            int current=pageTable[i].physicalPage;
            if(bitmap[current]==1)
            { 
                printf("free Memory %d\n",current);
                bitmap[current]=0;
            }
        }
    }

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

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

pageTable = new TranslationEntry[numPages];
    for (i = 0; i < numPages; i++) { 
    		//原始的物理内存分配
    		//pageTable[i].physicalPage = machine->allocateMemory();
    		//现在的物理内存分配
    		pageTable[i].physicalPage = machine->allocateMemory();
    }

void ExceptionHandler(ExceptionType which)
    { 
        int type = machine->ReadRegister(2);
        if ((which == SyscallException)) { 
            if(type == SC_Halt)//halt系统调用
            				……………
    				else if (type == SC_Exit){ //Exit系统调用
                printf("program exit\n");
                printf("program exit\n");
                if (currentThread->space != NULL) { 
                    machine->freeMemory();//回收内存
                    delete currentThread->space;
                    currentThread->space = NULL;
                    currentThread->Finish();
               }
            }
        }
    }

##### 5、测试结果 #####

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

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fVuPzXuq-1604393159516)(/Users/jaggerqian/Library/Containers/com.tencent.xinWeChat/Data/Library/Application Support/com.tencent.xinWeChat/2.0b4.0.9/4bd6fb1bd54c6c60eedfec9d2b01e055/Message/MessageTemp/f9221300aea1edade4f9851cd6dc9b82/Image/83461604211319\_.pic\_hd.jpg)\]][img-fVuPzXuq-1604393159516_Users_jaggerqian_Library_Containers_com.tencent.xinWeChat_Data_Library_Application Support_com.tencent.xinWeChat_2.0b4.0.9_4bd6fb1bd54c6c60eedfec9d2b01e055_Message_MessageTemp_f9221300aea1edade4f9851cd6dc9b82_Image_83461604211319_.pic_hd.jpg]

#### Exercise 5 多线程支持 ####

目前Nachos系统的内存中同时只能存在一个线程，我们希望打破这种限制，使得Nachos系统支持多个线程同时存在于内存中。

##### 1、基本思想 #####

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

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

void ExceptionHandler(ExceptionType which)
    { 
        int type = machine->ReadRegister(2);
        if ((which == SyscallException)) { 
            if(type == SC_Halt)//halt系统调用
            				……………
    				else if (type == SC_Exit){ //Exit系统调用
                printf("program exit\n");
                if (currentThread->space != NULL) { 
                    ………………
                    //程序运行结束之后切换到下一个程序
                    int nextPc=machine->ReadRegister(NextPCReg);
                    machine->WriteRegister(PCReg,nextPc);
               }
            }
        }
    }

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

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

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

##### 4、测试函数 #####

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

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, (void*)1);
        thread2->Fork(UserProgThread, (void*)2);
    }
    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), -1);//注意这里设置的新线程的优先级必须高于main的优先级(0)也就是数字小于0,否则线程不能主动放处理机需要手动实现
        AddrSpace *space;
        space = new AddrSpace(executable);
        thread->space = space;
        return thread;
    }
    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);			
    }

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

void AddrSpace::PrintState() 
    { 
        printf("=== %s ===\n", "Address Space Information");
        printf("numPages = %d\n", numPages);
        printf("VPN\tPPN\tvalid\tRO\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");
    }

##### 5、修改main函数 #####

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

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3YoNBkhA-1604393159517)(/Users/jaggerqian/Library/Application Support/typora-user-images/image-20201103103014206.png)\]][img-3YoNBkhA-1604393159517_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201103103014206.png]

##### 6、测试结果 #####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Ztehijob-1604393159517)(/Users/jaggerqian/Library/Containers/com.tencent.xinWeChat/Data/Library/Application Support/com.tencent.xinWeChat/2.0b4.0.9/4bd6fb1bd54c6c60eedfec9d2b01e055/Message/MessageTemp/9e20f478899dc29eb19741386f9343c8/Image/1301604310622\_.pic\_hd.jpg)\]][img-Ztehijob-1604393159517_Users_jaggerqian_Library_Containers_com.tencent.xinWeChat_Data_Library_Application Support_com.tencent.xinWeChat_2.0b4.0.9_4bd6fb1bd54c6c60eedfec9d2b01e055_Message_MessageTemp_9e20f478899dc29eb19741386f9343c8_Image_1301604310622_.pic_hd.jpg]

#### Exercise 6 缺页中断处理 ####

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

> 这个Exercise需要结合Exercise7一起实现，所以我把所有报告内容写在了Exercise7下面

### 三、Lazy-loading ###

#### Exercise 7 ####

我们已经知道，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的构造函数（因为我不擅长使用ifdef不然更方便）

首先在addspace.h中声明新的构造函数

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-88BbifQa-1604393159518)(/Users/jaggerqian/Library/Application Support/typora-user-images/image-20201103104753494.png)\]][img-88BbifQa-1604393159518_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201103104753494.png]

> 这个lab参数没什么意义

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);
        size = noffH.code.size + noffH.initData.size + noffH.uninitData.size + UserStackSize;   
        numPages = divRoundUp(size, PageSize);
        size = numPages * PageSize;
    		//上面的内容与原来的一样
      //用fileSystem创建VirtualMemory文件，运行nachos之后，会在在usrprog目录下面生成该文件
        bool success_create_vm = fileSystem->Create("VirtualMemory", size);
        ASSERT(numPages <= NumPhysPages);       // check we're not trying
        pageTable = new TranslationEntry[numPages];
        for (i = 0; i < numPages; i++) { 
        pageTable[i].virtualPage = i;  
        pageTable[i].physicalPage = 0;//因为我们没有将用户程序内容装载进内存，所以physicalPage的值可以都设置为0
        pageTable[i].valid = FALSE;//表示没有从磁盘装载任何页面进内存
        pageTable[i].use = FALSE;
        pageTable[i].dirty = FALSE;
        pageTable[i].readOnly = FALSE;  
        }
    		//初始化整个物理内存
        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; 
    }
    //同时在StartProcess函数中的构造函数应该替换成上述构造函数

##### 3、缺页处理 #####

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

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);//处理快表失效
      //我把快表失效放在页表失效里进行处理 ，这里的原因我会在后面解释！
    }
    
    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(); //打印地址空间信息
    }
    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;
    }
    //我把ExceptionHandler也放上来了，主要是防止大家出错
    void
    ExceptionHandler(ExceptionType which)
    { 
      		……………………
      		else if(which == PageFaultException){ 
            TLBMissCount++; 
            //本来我们应该把TLBMissHandler(BadVAddr);函数放在页表失效的处理中，但是在这里我放在了快表失效中，是因为我们启用了tlb的功能，所以在第一次执行缺页异常的时候，首先执行的是快表失效，所以我们应该把TLBMissHandler(BadVAddr)函数放在快表失效中，然后把快表失效的函数时时钟算法放在了TLBMissHandler中进行处理。很多人可能有疑问为什么不能在快表失效调用时钟处理函数在页表失效中调用TLBMissHandler。其实理论上是应该这样的，但是因为我实现的函数问题，这里我们是事先把用户程序的内容放进了虚拟内存，所以其实物理内存中没有内容，如果在快表中发生失效时，会采用时钟算法先去物理内存中寻找，然后物理内存还是没有东西，有发生PageFaultException，然后进行一场处理，因为machine->tlb ！= NULL，跟第一次一样，还是会执行时钟算法处理 缺页异常，这样就陷入了死循环。而把TLBMissHandler函数放在快表中，当发生缺页异常首先进行快表失效中调用TLBMissHandler，他会首先把用户程序内容放到页表中，这个时候在调用时钟算法就解决了问题。
        	if (machine->tlb == NULL) {  
                DEBUG('m', "=> Page table page fault.\n");
                ASSERT(FALSE);
            } else {  
                DEBUG('m', "=> TLB miss (no TLB entry)\n");
                int BadVAddr = machine->ReadRegister(BadVAddrReg); 
                TLBMissHandler(BadVAddr);
                //TLBAlgoFIFO(BadVAddr);
                //TLBAlgoClock(BadVAddr);
            }
    				………………………………
    }

##### 4、测试结果 #####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KyQaEyny-1604393159518)(/Users/jaggerqian/Library/Application Support/typora-user-images/image-20201103101732988.png)\]][img-KyQaEyny-1604393159518_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201103101732988.png]

### 四、Challenges ###

#### Challenge 1 ####

为线程增加挂起SUSPENDED状态，并在已完成的文件系统和内存管理功能的基础之上，实现线程在“SUSPENDED”，“READY”和“BLOCKED”状态之间的切换。

TODO

#### Challenge 2 ####

多级页表的缺陷在于页表的大小与虚拟地址空间的大小成正比，为了节省物理内存在页表存储上的消耗，请在Nachos系统中实现倒排页表。

##### 1、基本思想 #####

倒排页表是一个全局性的页表，而不是每个线程都具有一个页表。因此我们需要在machine中创建维护这个页表，而不是在addspace中为每个线程创建和维护页表。因此为了区分没个线程的使用情况，我们需要在machine类中新增一个线程id的标识。同时因为所有线程都共用倒排页表，所以不需要将每个线程的页表倒入内存空间。除此之外，在最后回收内存空间的时候我们还需要加一个线程id的判断，已确定回收的线程是否是当前回收线程。

##### 2、machine/translate.h #####

添加线程标识

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bTcWoDHG-1604393159519)(/Users/jaggerqian/Library/Application Support/typora-user-images/image-20201103152543994.png)\]][img-bTcWoDHG-1604393159519_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201103152543994.png]

##### 3、machine/machine.cc #####

创建和维护倒排页表，倒排页表的空间应该和物理内存相同

Machine::Machine(bool debug)
    { 
    		...
        pageTable = new TranslationEntry[NumPhysPages];
        //初始化倒排页表
        for (i = 0; i < NumPhysPages; i++) { 
            pageTable[i].physicalPage = i;
            pageTable[i].virtualPage = i;
            pageTable[i].valid = FALSE;
            pageTable[i].dirty = FALSE;
            pageTable[i].readOnly = FALSE;
            pageTable[i].threadId = -1;
        }
        ...
    }
    //修改回收空间函数
    void Machine::freeMemory()
    { 
        for (int i = 0; i < NumPhysPages; i++) { 
            if (pageTable[i].threadId == currentThread->getTid()) { 
                if(bitmap[i]==1)
                { 
                    printf("free Memory %d\n",i);
                    bitmap[i]=0;
                }
            }
        }
    }

##### 4、userprog/addrspace.cc #####

因为我们所有线程共用一个倒排页表，而页表已经在machine中创建，所以在addrspace中需要修改页表初始化，同时物理地址才具有决定意义

//pageTable = new TranslationEntry[numPages];//这行被注释掉了，因为不再需要了，我们是直接对machine指向的倒排页表进行赋值
        for (i = 0; i < numPages; i++) { 
    	machine->pageTable[i].virtualPage = i;
        machine->pageTable[i].physicalPage = machine->allocateMemory();
    	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(); 
        }
    //因为不需要将每个线程的页表倒入内存空间，所以注释掉RestoreState()内容
    void AddrSpace::RestoreState() 
    { 
        // machine->pageTable = pageTable;
        // machine->pageTableSize = numPages;
    }

##### 5、测试结果 #####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rZ0eNAb7-1604393159519)(/Users/jaggerqian/Library/Application Support/typora-user-images/image-20201103154355056.png)\]][img-rZ0eNAb7-1604393159519_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201103154355056.png]

测试结果与 exercise4是一样的，但是他们具有本质的区别，主要注意理解区分。

## 内容四：遇到的困难以及解决方法 ##

### 困难1： ###

Nachos系统的debug功能很强大，但是最开始的时候不擅长使用，导致走了很多弯路

### 困难2: ###

在Exercise7那里我已经阐述过困难2了，但是因为没有全局性的代码思想，导致无限陷入了缺页异常报错。（其实最开始我还不知道是死循环了，当是不会用debug还以为没执行，因为输入命令之后半天没有输出信息，后来尝试debug才知道死循环了），也是经过多番尝试解决。

## 内容五：收获及感想 ##

最开始我以为做完lab2之后后面的实验应该会轻松些。以为做完lab2就算入门nachos了，后来发现是我想多了。这lab3的工作量对我个人而言是要多与lab2的，难度也高于lab2。花了接近两个星期的时间才完成了lab3。完成的过程虽然曲折复杂，结果可能也不尽人意，但是至少我对内存的各种管理机制，如TLB、页表、地址转换机制都有了进一步比较深刻的理解，顺便学习了后面lab6需要的系统调用。

这里有个建议给大家，我最开始做实验的时候都是阅读各种网上的大佬的博客，但是基本所有大佬写的博客都只解释他们觉得需要解释的东西，就算你完全按照他们的额代码写下来也不一定能够运行通过，就算通过了你可能也不知道原理是啥。这次lab我遇到了很多的困难，于是我很无奈的研读了一下nachos中文文档的各个部分，包括machine、线程、中断、虚拟内存管理部分，特别是虚拟内存管理部分对我解决这个实验有很大的帮助。我解决过程中遇到的困难的核心思想就是理解nachos运行的机制，如果你对nachos各个模块怎么工作，各个函数的功能是啥，函数之间怎么调用，当是同时你必须掌握相关实验的基础知识。我就是通过以上过程解决我实验中遇到的bug的。

所以强烈建议大家好好研读nachos中文文档。

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

这是一门非常值得推荐的课。

## 内容七：参考文献 ##

*  \[1\] [Nachos中文教程][Nachos]
 *  \[2\] [虚拟内存实习报告][Link 1]
 *  \[3\] [虚拟内存实习报告][Link 2]
 *  \[4\] [Nachos实验][Nachos 1]

[img-AfoGykpf-1604393159510_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201029183142093.png]: /images/20221120/a8b71574982c4676a20db16c2f08f06d.png
[img-Edt79bSw-1604393159511_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201027163038452.png]: /images/20221120/c2c8245be2314282ae770c35fc29b1dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/d2dd58bd89184f33b57367705c4fbe3b.png
[img-K0qjgj2T-1604393159514_Users_jaggerqian_Library_Containers_com.tencent.xinWeChat_Data_Library_Application Support_com.tencent.xinWeChat_2.0b4.0.9_4bd6fb1bd54c6c60eedfec9d2b01e055_Message_MessageTemp_9e20f478899dc29eb19741386f9343c8_Image_1201603976836_.pic_hd.jpg]: /images/20221120/9747d3d0d01943d0bdc2cfb0ef696a42.png
[img-yJlN57OW-1604393159515_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201031150848167.png]: /images/20221120/5ae810a5b79542f1ae6134a125925128.png
[img-LRkv0dIz-1604393159515_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201031150942119.png]: /images/20221120/86708853864c44d98a63feb1bd223aef.png
[img-kYwco9kl-1604393159516_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201031151048608.png]: /images/20221120/38e9972928b14eb6a12b80b99e8f1c0a.png
[img-fVuPzXuq-1604393159516_Users_jaggerqian_Library_Containers_com.tencent.xinWeChat_Data_Library_Application Support_com.tencent.xinWeChat_2.0b4.0.9_4bd6fb1bd54c6c60eedfec9d2b01e055_Message_MessageTemp_f9221300aea1edade4f9851cd6dc9b82_Image_83461604211319_.pic_hd.jpg]: /images/20221120/aeab0e4fc6be42589b795ba2df8d52ce.png
[img-3YoNBkhA-1604393159517_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201103103014206.png]: /images/20221120/5a0867599d744612ae38d7ada17257fc.png
[img-Ztehijob-1604393159517_Users_jaggerqian_Library_Containers_com.tencent.xinWeChat_Data_Library_Application Support_com.tencent.xinWeChat_2.0b4.0.9_4bd6fb1bd54c6c60eedfec9d2b01e055_Message_MessageTemp_9e20f478899dc29eb19741386f9343c8_Image_1301604310622_.pic_hd.jpg]: /images/20221120/c2f05a5f04894701b8fc2cc81ab31937.png
[img-88BbifQa-1604393159518_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201103104753494.png]: /images/20221120/f74f55b7da374602be092f822267781b.png
[img-KyQaEyny-1604393159518_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201103101732988.png]: /images/20221120/e80c22853791410580ba8dbc2e87cb5f.png
[img-bTcWoDHG-1604393159519_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201103152543994.png]: /images/20221120/6e1d786610a14a1cbe75257eca91db2a.png
[img-rZ0eNAb7-1604393159519_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201103154355056.png]: /images/20221120/5b74154c44964f7fa6ae33869c0c69cd.png
[Nachos]: https://wenku.baidu.com/view/400357de5022aaea998f0fb0.html
[Link 1]: https://wenku.baidu.com/view/be56dfe2541810a6f524ccbff121dd36a32dc430.html?re=view
[Link 2]: https://github.com/BACKPGJ/nachos
[Nachos 1]: https://github.com/daviddwlee84/OperatingSystem