用户程序的执行流程
在main.cc中，当我们选择-x选项时，这段代码将-x之后的参数设置为userProgName，即我们需要执行的用户程序。
代码语言：javascript复制else if (strcmp(argv[i], "-x") == 0)
{
ASSERT(i 1 < argc);
userProgName = argv[i 1];
i ;
}然后在下面这段代码中，首先给程序执行分配资源空间，之后执行用户程序。
代码语言：javascript复制// 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函数如下。将程序加载并为程序分配内存空间。
代码语言：javascript复制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函数，由于这个函数源代码比较长，所以从中截取关键部分分析。
下面这部分代码完成取指和译码的过程
代码语言：javascript复制if (!ReadMem(registers[PCReg], 4, &raw))
return; // exception occurred
instr->value = raw;
instr->Decode();除了ReadMem()函数之外当然还有WriteMem()函数，只分析ReadMem()如下
调用Translate()函数将虚拟地址转化成物理地址，返回异常类型，如果发生异常调用RaiseException(exception, addr)将异常和异常发生的地址交由操作系统处理，否则正常从内存中读取数据。WriteMem()也是类似。
代码语言：javascript复制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机制
代码语言：javascript复制#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属性下增加置换函数的声明。
代码语言：javascript复制// 发生tlb未命中中断，进行置换
void TLBPageSwap(int addr);在machine.cc中实现置换函数如下所示。定义全局变量ptr用于循环遍历TLB寻找use位为0的页。
首先使用页表机制完成虚拟地址到物理地址的转化，然后使用模运算循环遍历TLB，当找到use位为0的算法则换出并退出循环，否则将该页的use位置为0。
此处内容已隐藏，请付费后查看
重新编译并执行任意用户程序测试如下，发生了三次未命中中断。
