Nachos内存管理-能不能吃完饭再说

用户程序的执行流程

在main.cc中，当我们选择-x选项时，这段代码将-x之后的参数设置为userProgName，即我们需要执行的用户程序。

else if (strcmp(argv[i], "-x") == 0)
{            
    ASSERT(i + 1 < argc);         
    userProgName = argv[i + 1];
    i++;
}

然后在下面这段代码中，首先给程序执行分配资源空间，之后执行用户程序。

// finally, run an initial user program if requested to do so
if (userProgName != NULL)
{
    AddrSpace *space = new AddrSpace;
    ASSERT(space != (AddrSpace *)NULL);
    if (space->Load(userProgName))
    {                       // load the program into the space
        space->Execute();   // run the program
        ASSERTNOTREACHED(); // Execute never returns
    }
}

在addrspace.cc中，AddrSpace()的构造函数如下，它为这个进程维护了一个页表，并且初始化该页表。

AddrSpace::AddrSpace()
{
    pageTable = new TranslationEntry[NumPhysPages];
    for (int i = 0; i < NumPhysPages; i++)
    {
        pageTable[i].virtualPage = i; // for now, virt page # = phys page #
        pageTable[i].physicalPage = i;
        pageTable[i].valid = TRUE;
        pageTable[i].use = FALSE;
        pageTable[i].dirty = FALSE;
        pageTable[i].readOnly = FALSE;
    }

    // zero out the entire address space
    bzero(kernel->machine->mainMemory, MemorySize);
}

Load函数如下。将程序加载并为程序分配内存空间。

bool AddrSpace::Load(char *fileName)
{
    OpenFile *executable = kernel->fileSystem->Open(fileName);
    NoffHeader noffH;
    unsigned int size;

    if (executable == NULL)
    {
        cerr << "Unable to open file " << fileName << "\n";
        return FALSE;
    }

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

#ifdef RDATA
    // how big is address space?
    size = noffH.code.size + noffH.readonlyData.size + noffH.initData.size +
           noffH.uninitData.size + UserStackSize;
    // we need to increase the size
    // to leave room for the stack
#else
    // 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
#endif
    numPages = divRoundUp(size, PageSize);
    size = numPages * PageSize;

    ASSERT(numPages <= NumPhysPages); // check we're not trying
                                      // to run anything too big --
                                      // at least until we have
                                      // virtual memory

    DEBUG(dbgAddr, "Initializing address space: " << numPages << ", " << size);

    // then, copy in the code and data segments into memory
    // Note: this code assumes that virtual address = physical address
    if (noffH.code.size > 0)
    {
        DEBUG(dbgAddr, "Initializing code segment.");
        DEBUG(dbgAddr, noffH.code.virtualAddr << ", " << noffH.code.size);
        executable->ReadAt(
            &(kernel->machine->mainMemory[noffH.code.virtualAddr]),
            noffH.code.size, noffH.code.inFileAddr);
    }
    if (noffH.initData.size > 0)
    {
        DEBUG(dbgAddr, "Initializing data segment.");
        DEBUG(dbgAddr, noffH.initData.virtualAddr << ", " << noffH.initData.size);
        executable->ReadAt(
            &(kernel->machine->mainMemory[noffH.initData.virtualAddr]),
            noffH.initData.size, noffH.initData.inFileAddr);
    }

#ifdef RDATA
    if (noffH.readonlyData.size > 0)
    {
        DEBUG(dbgAddr, "Initializing read only data segment.");
        DEBUG(dbgAddr, noffH.readonlyData.virtualAddr << ", " << noffH.readonlyData.size);
        executable->ReadAt(
            &(kernel->machine->mainMemory[noffH.readonlyData.virtualAddr]),
            noffH.readonlyData.size, noffH.readonlyData.inFileAddr);
    }
#endif

    delete executable; // close file
    return TRUE;       // success
}

之后继续调用addrspace.cc中的Execute函数。使用this->InitRegisters()初始化寄存器的值，之后调用this->RestoreState()载入进程的分页表，完成这两项准备工作之后使用kernel->machine->Run()开始执行程序。

void AddrSpace::Execute()
{

    kernel->currentThread->space = this;

    this->InitRegisters(); // set the initial register values
    this->RestoreState();  // load page table register

    kernel->machine->Run(); // jump to the user progam

    ASSERTNOTREACHED(); // machine->Run never returns;
                        // the address space exits
                        // by doing the syscall "exit"
}

在mipssim.cc中定义的Run函数如下，使用软件模拟硬件执行指令。调用setStatus函数将处理器状态设置为用户态，表示执行的是用户程序。然后使用OneInstruction(instr)执行指令，再使用OneTick()移动时钟周期。

void Machine::Run()
{
	Instruction *instr = new Instruction; // storage for decoded instruction

	if (debug->IsEnabled('m'))
	{
		cout << "Starting program in thread: " << kernel->currentThread->getName();
		cout << ", at time: " << kernel->stats->totalTicks << "\n";
	}
	kernel->interrupt->setStatus(UserMode);
	for (;;)
	{
		OneInstruction(instr);
		kernel->interrupt->OneTick();
		if (singleStep && (runUntilTime <= kernel->stats->totalTicks))
			Debugger();
	}
}

继续深入分析OneInstruction函数，由于这个函数源代码比较长，所以从中截取关键部分分析。

下面这部分代码完成取指和译码的过程

if (!ReadMem(registers[PCReg], 4, &raw))
    return; // exception occurred
instr->value = raw;
instr->Decode();

除了ReadMem()函数之外当然还有WriteMem()函数，只分析ReadMem()如下

调用Translate()函数将虚拟地址转化成物理地址，返回异常类型，如果发生异常调用RaiseException(exception, addr)将异常和异常发生的地址交由操作系统处理，否则正常从内存中读取数据。WriteMem()也是类似。

bool Machine::ReadMem(int addr, int size, int *value)
{
	int data;
	ExceptionType exception;
	int physicalAddress;

	DEBUG(dbgAddr, "Reading VA " << addr << ", size " << size);

	exception = Translate(addr, &physicalAddress, size, FALSE);
	if (exception != NoException)
	{
		RaiseException(exception, addr);
		return FALSE;
	}
	switch (size)
	{
	case 1:
		data = mainMemory[physicalAddress];
		*value = data;
		break;

	case 2:
		data = *(unsigned short *)&mainMemory[physicalAddress];
		*value = ShortToHost(data);
		break;

	case 4:
		data = *(unsigned int *)&mainMemory[physicalAddress];
		*value = WordToHost(data);
		break;

	default:
		ASSERT(FALSE);
	}

	DEBUG(dbgAddr, "\tvalue read = " << *value);
	return (TRUE);
}

完成内存读之后

译码函数如下，在这里完成对Instruction的二进制表示value，操作码opcode，rs、rt两个操作数寄存器和rd一个结果寄存器以及extra字段的解析。

void Instruction::Decode()
{
	OpInfo *opPtr;

	rs = (value >> 21) & 0x1f;
	rt = (value >> 16) & 0x1f;
	rd = (value >> 11) & 0x1f;
	opPtr = &opTable[(value >> 26) & 0x3f];
	opCode = opPtr->opCode;
	if (opPtr->format == IFMT)
	{
		extra = value & 0xffff;
		if (extra & 0x8000)
		{
			extra |= 0xffff0000;
		}
	}
	else if (opPtr->format == RFMT)
	{
		extra = (value >> 6) & 0x1f;
	}
	else
	{
		extra = value & 0x3ffffff;
	}
	if (opCode == SPECIAL)
	{
		opCode = specialTable[value & 0x3f];
	}
	else if (opCode == BCOND)
	{
		int i = value & 0x1f0000;

		if (i == 0)
		{
			opCode = OP_BLTZ;
		}
		else if (i == 0x10000)
		{
			opCode = OP_BGEZ;
		}
		else if (i == 0x100000)
		{
			opCode = OP_BLTZAL;
		}
		else if (i == 0x110000)
		{
			opCode = OP_BGEZAL;
		}
		else
		{
			opCode = OP_UNIMP;
		}
	}
}

回到OneInstruction函数继续分析，这里截取了switch-case代码段的一部分。根据不同的操作码opcode，执行对应的操作，以OP_ADD这一个操作码为例，使用指令sum = registers[instr->rs] + registers[instr->rt]计算rs和rd两个寄存器内操作数的和，然后使用registers[instr->rd] = sum将结果存入到rd寄存器当中。在这之后还定义了许多opcode对应的操作。

switch (instr->opCode)
{

case OP_ADD:
    sum = registers[instr->rs] + registers[instr->rt];
    if (!((registers[instr->rs] ^ registers[instr->rt]) & SIGN_BIT) &&
        ((registers[instr->rs] ^ sum) & SIGN_BIT))
    {
        RaiseException(OverflowException, 0);
        return;
    }
    registers[instr->rd] = sum;
    break;

增加TLB机制

上述用户进程执行的使用的是传统的页表，为了减少寻找物理地址所消耗时间，一般使用TLB(Translation Lookaside Buffer)转换检测缓冲区来提高虚拟地址到物理地址转换速度。

接下来将Nachos的虚拟地址到物理地址的转换机制由传统的页表改为TLB。在machine的构造函数中，有这么一小段代码，如果def了USE_TLB，则使用TLB机制

#ifdef USE_TLB
    tlb = new TranslationEntry[TLBSize];
    for (i = 0; i < TLBSize; i++)
        tlb[i].valid = FALSE;
    pageTable = NULL;
#else // use linear page table
    tlb = NULL;
    pageTable = NULL;
#endif

因此我们修改build.linux目录下Makefile，大概在195行的位置，增加-DUSE_TLB。

在这之后，我们的页表和TLB均不为空了，因此需要将translate.cc中大概220行的这个断言注释掉，否则程序会中断。

接下来修改ReadMem()函数，修改部分内容如下，当发生错误时，交给操作系统处理错误（后续在这部分执行置换算法），如果是TLB未命中中断，在操作系统完成TLB的置换后再次执行将虚拟地址转化成物理地址。WriteMem()函数的修改同理。

这部分完成之后，还需要实现对PageFaultException错误的处理，在exception.cc当中的ExceptionHandler（）函数的switch (which)增加一个case，如下。获取发生错误的地址，然后调用置换算法完成TLB的置换。

使用NRU置换算法

完成上面所有步骤之后，我们只需要实现TLB的置换算法即可。使用时钟（CLOCK）算法（一种NRU算法）实现。

在machine.h的machine类的public属性下增加置换函数的声明。

// 发生tlb未命中中断，进行置换
void TLBPageSwap(int addr);

在machine.cc中实现置换函数如下所示。定义全局变量ptr用于循环遍历TLB寻找use位为0的页。

首先使用页表机制完成虚拟地址到物理地址的转化，然后使用模运算循环遍历TLB，当找到use位为0的算法则换出并退出循环，否则将该页的use位置为0。

重新编译并执行任意用户程序测试如下，发生了三次未命中中断。

------本页内容已结束，喜欢请分享------

文章作者

能不能吃完饭再说

隐私政策

PrivacyPolicy

用户协议

UseGenerator

许可协议

NC-SA 4.0

文章版权归作者所有，未经允许请勿转载。

THE END

操作系统干货教程
# Nachos # 内存管理

Nachos内存管理

用户程序的执行流程

增加TLB机制

使用NRU置换算法

1SQL注入基础教程

2Nachos文件系统调用与shell

3Adaline自适应线性神经元和学习收敛

4系统调用详解:以Nachos为例实现系统调用

5信号量+令牌桶算法实现的简单限流组件

6SeedLab——Environment Variable and Set-UID Program Lab