在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(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的置换。
完成上面所有步骤之后,我们只需要实现TLB的置换算法即可。使用时钟(CLOCK)算法(一种NRU算法)实现。
在machine.h的machine类的public属性下增加置换函数的声明。
// 发生tlb未命中中断,进行置换
void TLBPageSwap(int addr);
在machine.cc中实现置换函数如下所示。定义全局变量ptr用于循环遍历TLB寻找use位为0的页。
首先使用页表机制完成虚拟地址到物理地址的转化,然后使用模运算循环遍历TLB,当找到use位为0的算法则换出并退出循环,否则将该页的use位置为0。
重新编译并执行任意用户程序测试如下,发生了三次未命中中断。