Publié il y a Mis à jour il y a Operating Systeman hour de lecture (Environ 7401 mots)0 visites

Nachos Lab02 虚拟内存

第一部分 TLB异常处理

Exercise1 源代码阅读

阅读code/userprog/progtest.cc，着重理解nachos执行用户程序的过程，以及该过程中与内存管理相关的要点

Code/userprog/progtest.cc：该文件最重要的就是StartProcess函数，该函数指明了如何启动用户进程。它接收一个文件名，在函数中会打开传入的可执行文件，然后为可执行文件创建地址空间（即将可执行文件内存储的信息放入内存），接着初始化寄存器以及调用RestoreState函数将由Addrspace类内部创建的页表指针传递给machine，最后调用machine->Run()函数来跳转到用户进程执行。

具体过程如下：

  1. 在StartProcess中调用AddrSpace创建用户空间，将可执行文件读入内存
  2. 调用InitRegisters初始化寄存器，及调用RestoreState将用户线程的页表装入machine
  3. 调用machine->Run()执行用户线程的指令。
  4. 通过OneInstruction来执行指令。如果OneInstruction顺利执行，则会将PC增加，从而实现执行下一条指令。如果执行出错（即ReadMem和WriteMem出错），则会进行异常处理；异常处理结束后，由于PC并未增加，因此出现错误的指令会被再次执行。
  5. 当程序执行到末尾时，会执行start.s中的Exit指令。最终通过系统调用SyscallException中的SC_Exit调用，进行程序结束处理。由于进入到这里处理之后，用户程序已经执行结束，PC不会自动增加，系统（可能）会反复执行Exit调用。对于存在多用户线程的情况，需要在此处手动将PC增加，从而维持后续线程的执行。

阅读code/machine目录下的machine.h(cc)，translate.h(cc)文件和code/userprog目录下的exception.h(cc)，理解当前Nachos系统所采用的TLB机制和地址转换机制。

TLB机制和地址转换机制：Nachos的machine中有两个指针，分别是tlb和pageTable。当tlb指针不为空时，nachos会逐一遍历tlb表，检查其内部的valid值以及虚拟页号（virtualPage）与计算出的vpn值是否一致（其中，vpn是通过对传入的虚拟地址取高25位获得，低7位代表偏移量，即磁盘块大小为128字节）。如果二者均满足，则代表tlb命中，返回NoException信号；否则会返回一个缺页异常（PageFaultException）信号。如果tlb指针为空，则会去检查pageTable[vpn]的valid值，并直接根据vpn获取页。获取到了虚拟页表项之后，取出其中存储的物理页框号，最后根据公式physAddr = pageFrame * PageSize + offset，计算得出物理地址，完成虚拟地址到物理地址的转换。

Exercise2 TLB MISS异常处理

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

思路

通过阅读translate.cc文件，易得知地址转换工作就是发生在Machine::Translate函数中。如果转换过程中出现问题，该函数会抛出异常，如缺页异常（PageFaultException）。检索地址转换函数被调用的位置可以得知，该函数会被ReadMem或WriteMem函数调用。

查看这两个读写内存函数可以得知，由Translate返回的异常会被送入RaiseException函数引起异常（machine->RaiseException(exception, addr);）。进一步跟进到RaiseException函数的实现，可以看到它将产生异常的虚拟地址送入到BadVAddrReg寄存器中。

所以在异常处理函数ExceptionHandler中，新增对缺页异常的处理。然后通过读取BadVAddrReg寄存器来获取虚拟地址，从而实现从pageTable向tlb调页。

实现

修改异常处理函数ExceptionHandler，增加对缺页异常的处理。关于对装载页函数LoadPage的实现，参见Exercise3。（注： tlb[i].time是为了置换算法新增的属性）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
 * userprog/exception.cc中的ExceptionHandler
 */
else if (which == PageFaultException) {
        DEBUG('m', "Page miss, swap page!\n");
        // 获取引发异常的虚拟地址，然后交给装载页函数处理
        int badVAddrReg = machine->ReadRegister(BadVAddrReg);
        machine->LoadPage(badVAddrReg);
  			printTLB(machine->tlb, TLBSize);
}

/*
void printTLB(TranslationEntry *tlb, int size) {
    printf("==============TLB with size %d==============\n", size);
    printf("time vPg pPg valid rdOnly use dirty\n");
    for (int i = 0; i < size; i++) {
        printf("%d  %d  %d  %d  %d  %d  %d\n", tlb[i].time, tlb[i].virtualPage,
               tlb[i].physicalPage, tlb[i].valid, tlb[i].readOnly, tlb[i].use, tlb[i].dirty);
    }
    printf("==============TLB END==============\n");
}
*/

这里的LoadPage使用FIFO置换算法。由于Nachos默认没有启用TLB，可以修改userprog/Makefile添加USE_TLE的宏以启动TLB（如果发现添加了之后依然没启用TLB，参见下文困难1的解决方案）。

为了更好的看效果，将TLBSize改为2。

1
2
3
4
/*
 * machine/machine.h
 */
#define TLBSize    2     // if there is a TLB, make it small

然后使用./userprog/nachos -x test/halt命令来进行测试（注：可以使用-d am参数来输出相关的debug信息，a和m代表的函数见threads/utility.h）。

如果执行出现如下错误，需要注释code/machine/translate.cc中Translate内部的ASSERT函数，因为该函数阻止了tlb和pageTable同时启用。

每次执行完缺页中断后输出TLB表的信息，最后测试结果如下。可以看到TLB表按照FIFO的规则替换。

Exercise3 置换算法

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

思路

此处实现的是FIFO和LRU算法。

对于FIFO，使用一个属性time来记录页换入TLB的时间。置换策略为：如果TLB还有剩余空间（即存在invalid的项），则直接将新页换入；否则，淘汰TLB中最早换入的项，并换入新页。

对于LRU，同样使用time属性来记录页最后一次被访问的时间（或最后一次TLB命中的时间）。置换策略为：如果TLB还有剩余空间（即存在invalid的项），则直接将新页换入；否则，淘汰TLB中最近最久未被访问的项，并换入新页。

这个时间可以使用stats中记录的总时间totalTicks。并且由于该值是int类型，FIFO和LRU均等价于查找time属性最小的项进行淘汰。

实现

首先实现一个通用（不仅适用与tlb也适用内存缺页）的装载函数LoadPage对缺页进行处理，这里暂时只考虑对TLB缺页进行处理，而不考虑内存缺页的情况，因此调度算法中均假定需要访问的页均在页表中。在此处实现了FIFO和LRU两种置换算法。

1
2
3
4
5
6
7
8
9
10
/*
 * machine/machine.h中的Machine类
 */
private:
		// tlb缺页处理函数
    void TlbSwap_FIFO (unsigned int vpn);
    void TlbSwap_LRU(unsigned int vpn);
public:
    // 页装载处理函数
    void LoadPage(int virtAddr);

其中LoadPage中同时考虑了页表缺页和tlb缺页两种情况。如果没有启用tlb，则必然是内存页表缺页；如果启用了tlb，也需要考虑内存页表是否缺页，先处理内存缺页，再处理tlb缺页。因此此处暂不考虑内存缺页的情况，因此相关的处理代码暂时先不写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Machine::LoadPage(int virtAddr) {
    unsigned int vpn = (unsigned) virtAddr / PageSize;
    unsigned int offset = (unsigned) virtAddr % PageSize;

    if (machine->tlb == NULL) {
        // 如果tlb为NULL引发PageFaultException的原因是pageTable[vpn].valid为false
        return;
    } else { // 此时表明tlb未命中，因此执行tlb置换策略
        if (!(machine->pageTable[vpn]).valid) {
            /* 如果页表也缺页，先给页表调页 */
//            printf("=====> %s Page Table Swap！\n", currentThread->getName());
        }

        // 为tlb调页
//        printf("=====> %s TLB Swap！\n", currentThread->getName());
        TlbSwap_LRU(vpn);
    }
}

对于FIFO算法，需要记录每个转换表项换入TLB中的时间，所以转换表项TranslationEntry类中增加一个time的变量，用于记录每个表项换入TLB的时间。其时间值来自于stats对象中记录的totalTicks值。FIFO算法的实现思路为：遍历TLB表，如果出现未使用的项（即valid为FALSE），则直接从pageTable复制信息到TLB中，并记录换入的时间；如果所有的项均使用（即valid为TRUE），则根据规则，选择淘汰最早被换入的项，然后换入新表项。

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
void Machine::TlbSwap_FIFO(unsigned int vpn) {
    int min_tlb_in_time = 0x7fffffff;
    int min_idx = 0;
    int i;

    for (i = 0; i < TLBSize; i++) {
        if (!tlb[i].valid) {
            // pageTableSize缺页的情况暂不考虑
            swap_from_pgtable_to_TLB(tlb[i], pageTable[vpn]);
            tlb[i].time = stats->totalTicks;
            break;
        } else if (tlb[i].time < min_tlb_in_time){
            min_idx = i;
            min_tlb_in_time = tlb[i].time;
        }
    }

    // 如果i与TLBSize相等则说明，TLB中所有的项都是valid，此时需要淘汰掉最早进入的项
    if (i == TLBSize) {
        swap_from_pgtable_to_TLB(tlb[min_idx], pageTable[vpn]);
        tlb[min_idx].time = stats->totalTicks;
    }
}

/*
void swap_from_pgtable_to_TLB(TranslationEntry &tlbEntry, TranslationEntry &pgTableEntry) {
    tlbEntry.virtualPage = pgTableEntry.virtualPage;
    tlbEntry.physicalPage = pgTableEntry.physicalPage;
    tlbEntry.valid = TRUE;
    tlbEntry.readOnly = pgTableEntry.readOnly;
    tlbEntry.use = pgTableEntry.use;
    tlbEntry.dirty = pgTableEntry.dirty;
}
*/

对于LRU算法，也是使用变量time来记录每个表项最后一次被访问的时间，然后该值会在Translate函数中被更新，即每次TLB命中时，会同时更新最后被访问的时间。LRU算法在实现上与FIFO算法完全一致，唯一的区别就是LRU会在TLB命中时更新time的值。

1
2
3
4
5
6
7
8
9
10
11
12
/*
 * machine/translate.cc
 */
else {
		for (entry = NULL, i = 0; i < TLBSize; i++)
  			if (tlb[i].valid && (tlb[i].virtualPage == vpn)) {
		entry = &tlb[i];			// FOUND!
		// LRU算法，更新访问时间
		tlb[i].time = stats->totalTicks;

		break;
}
两种置换算法的比较

使用test/halt进行测试。由于halt仅是一个空程序，只占用很少的页，所以修改器程序代码，对一个二位数组按行遍历，代码如下图。

然后在machine/machine.h中添加两个计数变量，并在machine/translate.cc的头部将其初始化为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
// machine/machine.h
extern int TLBMissCount;
extern int TranslateCount;

// machine/translate.cc顶部
int TLBMissCount = 0;
int TranslateCount = 0;

// machine/translate.cc中Translate，在未命中处累加
if (entry == NULL) {				// not found
	  TLBMissCount++;
 
// machine/translate.cc中Translate，进入该函数就累加
TranslateCount++;

// userprog/exception中ExceptionHandler，
// 因为全面提到的halt程序执行了Halt函数，所以在Halt异常处打印统计结果
    if (which == SyscallException) {
        if (type == SC_Halt) {
            DEBUG('a', "Shutdown, initiated by user program.\n");

            printf("TLB Miss: %d, TLB Hit: %d, Total Translate: %d, TLB Miss Rate: %.2lf%%\n",
                  TLBMissCount, TranslateCount-TLBMissCount, TranslateCount, (double)(TLBMissCount*100)/(TranslateCount));
            interrupt->Halt();

测试halt程序结果如下（这里仍是以TlbSize为2进行测试的）：

FIFO置换算法

LRU算法

相比之下，可以看到LRU算法的缺页率略低于FIFO算法。

第二部分 分页式内存管理

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

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

思路

在Machine类中新增一个位图数据结构来管理内存空间。然后在每次分配物理页的时候，先从位图中查找一块未使用的物理页并在位图中将其置1，然后返回物理块号并将页表项设为valid。反之，在回收的时候，直接在位图中将该物理页置0，并将页表项设为invalid。

实现

考虑到Nachos中已经实现了一个位图的数据结构，位于userprog/bitmap.h(cc)中。因此直接在machine.h文件中#include "bitmap.h"，并且在Machine类中添加用于内存管理的位图指针memBitMap（BitMap *memBitMap;）。因为调用的都是BitMap中的方法，为了简便将该指针设为public。该指针在Machine构造函数中被初始化，其位图的大小为物理页数量NumPhysPages。

1
2
3
4
/*
 * machine/machine.cc中Machine构造函数
 */
memBitMap = new BitMap(NumPhysPages);

由progtest.cc文件可知，用户进程在Addrspace中初始化用户空间，因此修改Addrspace类的构造函数。对pageTable初始化的部分，将物理页的分配改为从内存位图中获取第一个未分配（即位值为0）的物理页。此处加上了断言函数，因为如果位图没有找到值为0的位，则会返回-1。

1
2
3
4
5
6
7
/*
 * userprog/addrspace.cc中的Addrspace构造函数
 */
int phyPage = machine->memBitMap->Find();
DEBUG('m', "Physical memory page %d is allocated!\n", phyPage);
ASSERT(phyPage != -1);
pageTable[i].physicalPage = phyPage;

紧接着改造exception.cc中的异常处理函数。由该函数可知，Nachos仅实现了Halt调用的处理，没有对Exit调用（即用户进程退出时执行的系统调用）的处理。因此增加Exit调用的处理，并实现从内存位图中回收所有的物理页，然后对将要结束的进程执行*Finish()*方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
if (which == SyscallException) {
        if (type == SC_Halt) {
            DEBUG('a', "Shutdown, initiated by user program.\n");
            interrupt->Halt();
        } else if (type == SC_Exit) {
            DEBUG('a', "User program Exit！\n");
            if (currentThread->space != NULL) {
                for (unsigned int i = 0; i < machine->pageTableSize; i++) {
                    // 回收物理空间
                    int phyPage = machine->pageTable[i].physicalPage;
                    DEBUG('m', "Physical memory page %d is cleared!\n", phyPage);
                    machine->memBitMap->Clear(phyPage);
                }
                // 此处本质上是实现了exit系统调用
                // 回收space空间，执行进程Finish函数
                delete currentThread->space;
                currentThread->space = NULL;
                currentThread->Finish();

            }

}

测试结果如下（因为使用了DEBUG方式来输出信息，因此截图中省略了与该实现无关的信息）：

Exercise 5 多线程支持

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

思路

因为Addrspace类涉及用户空间的创建，因此阅读它的相关代理来了解用户程序是如何被读入内存的。查看Addrspace的构造函数可以发现，它创建用户空间的时候会先把内存写0，然后将可执行程序的代码（code）以及数据初始化部分（initData）完整地顺序写入内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
 * userprog/addrspace.cc中Addrspace构造函数
 */
// zero out the entire address space, to zero the unitialized data segment 
// and the stack segment
    bzero(machine->mainMemory, size);
...
  
 if (noffH.code.size > 0) {
     DEBUG('a', "Initializing code segment, at 0x%x, size %d\n", 
		 noffH.code.virtualAddr, noffH.code.size);
     executable->ReadAt(&(machine->mainMemory[noffH.code.virtualAddr]),
				noffH.code.size, noffH.code.inFileAddr);
}

if (noffH.initData.size > 0) {
      DEBUG('a', "Initializing data segment, at 0x%x, size %d\n", 
			noffH.initData.virtualAddr, noffH.initData.size);
      executable->ReadAt(&(machine->mainMemory[noffH.initData.virtualAddr]),
					noffH.initData.size, noffH.initData.inFileAddr);

所以为了实现多线程同时存在内存，需要让用户数据支持按页离散存放。可以采取逐字节读取数据，然后计算其存放的物理地址并存入内存。

实现

基于上一个Exercise实现的内存全局管理，使得用户进程允许离散位置的物理空间分配。但是在Addrspace的构造函数中可以看到，创建一个用户进程的时候会把内存空间置零。因此如果要支持多个进程同时存在内存，需要将该行代码bzero(...)注释。

然后修改可执行程序的代码写入内存的方式。原来的方法是按照虚拟内存来一次性线性写入内存，但是这种方式不适合多线程的支持。因此按照下述的方式，以字节为单位把内容一一写入到进程所分配到的物理页当中。简单来说就是读取每一个字节，然后根据页表计算物理地址，最后在其内写入数据，其中物理页号由之前位图分配给页表。对于code部分处理方式如下图，initData的处理方式类似。

最后修改exception.cc中的Exit系统调用处理部分，在处理的最后加入下述代码，使PC+4从而切换到下一个线程。（这里暂时没弄清楚为什么PC+4可以引发进程切换）

1
2
3
4
5
6
/* 
 * userprog/exception.cc中SC_Exit
 */
// PC + 4
int nextPc = machine->ReadRegister(NextPCReg);
machine->WriteRegister(PCReg, nextPc);

另外当进程切换时，需要将该进程所有的TLB项失效。因此在SaveState时将所有的TLB项设为invalid。

1
2
3
4
5
6
7
8
9
10
/*
 * userprog/addrspace.cc
 */
void AddrSpace::SaveState() 
{
    // 因为上下文切换时，旧进程的TLB全部失效，因此全部置为invalid
    for (unsigned int i = 0; i < TLBSize; i++) {
        machine->tlb[i].valid = FALSE;
    }
}

最后修改测试函数，让它能够同时执行两个线程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 
 * userprog/progtest.cc
 */
// multi process test
void TestMultiProc(char *filename) {
    Thread * thread_1 = new Thread("thread 1");
    Thread * thread_2 = new Thread("thread 2");

    thread_1->setPriority(10);
    thread_2->setPriority(5);

    thread_1->Fork(StartProcess, (void *)filename);
    thread_2->Fork(StartProcess, (void *)filename);

    currentThread->Yield();
}

同时main.cc也要做修改，以调用TestMultiProc

1
2
3
4
5
6
7
8
/* 
 * threads/main.cc中main
 */
#ifdef USER_PROGRAM
        if (!strcmp(*argv, "-x")) {            // run a user program
       ASSERT(argc > 1);
            TestMultiProc(*(argv + 1));
            argCount = 2;

测试结果如下：

Exercise 6 缺页中断处理

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

思路

设计一个所有进程都能访问到的全局交换空间。该空间可以利用文件系统fileSystem来创建，从而实现内存页面被换出到磁盘上，或磁盘上的页换入到内存中。

同时该交换空间需要一个管理机制，可以参照物理页的分配一样使用位图管理。同时还需要在页表项中新增一个交换地址，用于查找被换出到交换空间的页。

实现

首先在Nachos中实现一个简易的交换分区。在Machine类中增加两个公共成员，交换分区位图swapBitMap，以及交换分区的磁盘文件swapFile。并在Machine构造函数中将其初始化为内存的两倍大小，另外交换分区一页的大小与内存一页大小相等。以及在~Machine析构函数中将它们删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * machine/machine.h中Machine类
 */
BitMap *swapBitMap;  // 交换页位图
OpenFile *swapFile;

/*
 * machine/machine.cc中Machine构造函数
 */
swapBitMap = new BitMap(NumPhysPages * 2);
fileSystem->Create("VirtualMemory", MemorySize * 2);
swapFile = fileSystem->Open("VirtualMemory");

/*
 * machine/machine.cc中~Machine析构函数
 */
delete swapBitMap;
fileSystem->Remove("VirtualMemory");
delete swapFile;

然后给页表项的结构中加入swapPage成员，用于记录当前页存储在交换分区的页号，在初始化的时候swapPage的值为-1。该值与valid值不同时使用，即当分配物理页使得valid为TRUE时，页调入内存中，交换分区会回收之前分配给该页的空间。因此如果要将页从内存换出到交换分区时，需要重新分配交换分区页。

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

/*
 * machine/translate.h
 */
class TranslationEntry {
  public:
    int time;  // 用于置换算法的凭据，
    // 对于FIFO是记录该项进入tlb或者页表的时间，
    // 对于LRU是记录该项最近被访问的时间

    int swapPage;  // 交换分区页号，它和valid不能共存，即如果有物理块号，则必然不会有交换分区页号

    int virtualPage;   // The page number in virtual memory.
    int physicalPage;      // The page number in real memory (relative to the
         //  start of "mainMemory"
    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.

};

缺页中断的设计建立在之前的TLB的基础上，为TLB调页之前，需要检查页表中的页是否存在，如果不存在则从虚拟内存文件中进行调页。

对于页表调页算法，分为两部分。如果内存中有还未分配的内存空间，则从内存位图中获取物理页号，并从虚拟内存文件中读取数据写入到该物理页中。如果内存中不存在未分配的空间，则使用LRU算法进行调页。

而LRU算法的实现，与TLB中的LRU算法实现方式一致，均使用time变量来记录每次命中时的访问时间，然后选择最早被访问的项淘汰。但是页表的置换还需考虑是否要将内存中的页写回磁盘。因此如果页的dirty位为TRUE，则获取交换分区的一页空间，并将该物理页的数据写入到交换分区中。

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
62
63
64
void Machine::LoadPage(int virtAddr) {
    unsigned int vpn = (unsigned) virtAddr / PageSize;
    unsigned int offset = (unsigned) virtAddr % PageSize;

    if (machine->tlb == NULL) {
        // 如果tlb为NULL引发PageFaultException的原因是pageTable[vpn].valid为false
        PageTableSwap(vpn);
        return;
    } else { // 此时表明tlb未命中，因此执行tlb置换策略
        if (!(machine->pageTable[vpn]).valid) {
            /* 如果页表也缺页，先给页表调页 */
            printf("=====> %s Page Table Swap！\n", currentThread->getName());
            PageTableSwap(vpn);
        }

        // 为tlb调页
        printf("=====> %s TLB Swap！\n", currentThread->getName());
        TlbSwap_LRU(vpn);
    }
}

void Machine::PageTableSwap(unsigned int vpn) {
    int phyPage = memBitMap->Find();
    if (phyPage == -1) {
        // 如果没找到物理页，则使用置换算法找到被换出的页
        phyPage = PageTableSwap_LRU(vpn);
    }

    // 从交换分区取出数据，并回收该交换页
    int spn = pageTable[vpn].swapPage;
    swapFile->ReadAt(&(mainMemory[phyPage * PageSize]), PageSize, spn * PageSize);
    swapBitMap->Clear(spn);  // 回收该页

    pageTable[vpn].swapPage = -1;
    pageTable[vpn].valid = TRUE;
    pageTable[vpn].physicalPage = phyPage;
    pageTable[vpn].use = FALSE;
    pageTable[vpn].dirty = FALSE;
    pageTable[vpn].readOnly = FALSE;
    pageTable[vpn].time = stats->totalTicks;
}

int Machine::PageTableSwap_LRU(unsigned int vpn) {
    int i;
    int min_pgTable_last_time = 0x7fffffff;
    int min_idx = 0;

    for (i = 0; i < pageTableSize; i++) {
        if (pageTable[i].time < min_pgTable_last_time) {
            min_idx = i;
            min_pgTable_last_time = pageTable[i].time;
        }
    }
    // 给待换出的页分配交换分区号
    int spn = swapBitMap->Find(); ASSERT(spn != -1);
    if (pageTable[min_idx].dirty) {
        swapFile->WriteAt(&(mainMemory[pageTable[min_idx].physicalPage * PageSize]),
                        PageSize, spn * PageSize);
    }
    pageTable[min_idx].swapPage = spn;
    pageTable[min_idx].valid = FALSE;

    return pageTable[min_idx].physicalPage;
}

该部分是与Exercise一同实现的，所以待Lazy-loading实现后再作测试。

第三部分 Lazy-loading

Exercise 7

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

思路

上一个练习实现了交换分区，因此考虑将可执行文件读入内存时，不将所有内容读入到内存，而是将所有（或一部分）页先存储在交换分区。仅当发生缺页中断时才从交换分区调页到内存。

需要注意的是，Addrspace类的构造函数中仅将代码code和初始数据initdata两个部分做了处理。因此将他们写入交换分区之后，还需要保证其余的留给用户栈UserStackSize和未初始化数据uninitData的空间也被分配到交换分区。

否则，用户栈UserStackSize和未初始化数据uninitData的空间是未被分配任何空间的（交换分区还未分配，内存中也不分配）。这样就会导致，内存调页去写入用户栈或者数据的时候，可能会写在一个未被分配的空间上，从而引发问题。

实现

修改Addrspace类的构造函数，在用户程序初始化的时候，不读入内存，而是全部采用读入到交换分区的操作。直到用户程序执行引发了缺页中断，才从交换分区调页到内存中。因此在分配页表的时候对每一个页都分配一个交换分区号sp。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 * code/userprog/addrspace.cc
 */
AddrSpace::AddrSpace(OpenFile *executable)
{
...
    pageTable = new TranslationEntry[numPages];
    for (i = 0; i < numPages; i++) {
...
					int sp = machine->swapBitMap->Find(); ASSERT(sp != -1);
					pageTable[i].swapPage = sp;
...
    }
...
}


然后对noffH.code和noffH.initData做处理，即现将数据写入到交换分区。观察代码可以发现，其写入方式与物理页几乎完全一致，区别仅在于写入的位置是交换分区文件，而不是物理内存。noffH.initData的处理方式与noffH.code一致。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * userprog/addrspace.cc中Addrspace构造函数
 */
    if (noffH.code.size > 0) {
        DEBUG('a', "Initializing code segment, at 0x%x, size %d\n", 
			noffH.code.virtualAddr, noffH.code.size);
      
        int pos_file = noffH.code.inFileAddr;

        char cur_char;
        for (int p = 0; p < noffH.code.size; p++) {
            int cur_vpn = (noffH.code.virtualAddr + p) / PageSize;
            int cur_spn = pageTable[cur_vpn].swapPage;
            int swap_offset = (noffH.code.virtualAddr + p) % PageSize;

            executable->ReadAt(&(cur_char), 1, pos_file++);
            machine->swapFile->WriteAt(&(cur_char), 1, cur_spn * PageSize + swap_offset);
        }
    }

测试结果如下：

第四部分 Challenges

Challenge 1

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

Challenge 2

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

实现

倒排页表主要完成的是根据物理地址来查找页表项，因此全局仅需要一个倒排页表。修改Machine类的构造函数，将其内的pageTable改造为倒排页表。设置pageTable的大小为物理页数量，并初始化其内的值。

与此同时，需要在页表项的结构中添加tid，用于标示该物理页属于哪个进程。

然后修改物理页的分配方式，修改Addrpace的构造函数，删除其内部创建的pageTable，而是直接使用machine中的全局倒排页表，其中物理页号与页表下标一致。

由于此时全局仅有一张页表，因此不需要替换machine中的页表指针，所以将RestoreState函数注释。

最后，在异常处理函数ExceptionHandler中修改，页回收的方式。根据tid搜索页表中属于该线程的页，并将其回收。

最后测试结果如下：

可以看到仅分配给进程的部分有tid，且valid的值为1，满足倒排页表的可能结果。

遇到的困难以及解决方法

困难1 在Makefile增加USE_TLB宏之后，tlb的值依然为NULL

增加多处DEBUG信息，检查tlb的初始化以及调用，但仍得到如下信息。在无意中修改了#ifdef USE_TLB中的代码之后发现，TLB的值不为NULL了。

解决办法：执行make clean清除掉之前编译留下的.o文件，然后重新make。如果出现报错说“bin/csh: not found”，那么修改code/Makefile将其中的csh修改为sh。

经过分析得知，在编译之后保留了编译好的那些.o文件以加快后续的编译速度，但也正是保留了这些静态目标文件，从而导致了修改Makefile增加USE_TLB宏不生效。猜测Makefile自动检测改动只考虑代码的变动，而不考虑Makefile自身的变动，从而导致对Makefile的改动不生效。

参考文献

[1] 百度文库. Nachos虚拟内存机制实习报告[EB/OL]. https://wenku.baidu.com/view/ee473599964bcf84b9d57b89.html

[2] Github. 1200012964_彭广举_虚拟内存实习报告.pdf[EB/OL]. https://github.com/BACKPGJ/nachos/blob/master/homework/1200012964_%E5%BD%AD%E5%B9%BF%E4%B8%BE_%E8%99%9A%E6%8B%9F%E5%86%85%E5%AD%98%E5%AE%9E%E4%B9%A0%E6%8A%A5%E5%91%8A.pdf

[3] CSDN. Nachos实习——Lab2虚拟内存实习报告[EB/OL]. https://blog.csdn.net/sinat_40875078/article/details/109472895

[4] 百度文库. nachos Lab4实习报告[EB/OL]. https://wenku.baidu.com/view/be56dfe2541810a6f524ccbff121dd36a32dc430.html

Nachos Lab02 虚拟内存

https://rlyown.github.io/2020/11/17/Nachos-Lab02-虚拟内存/

Author

Chaos Chen

Posted on

2020-11-17

Updated on

2023-06-30

Licensed under

#

Commentaires

×