[山东大学操作系统课程设计]实验7

0.写在前面

实验7的要求过多，而且是在实验6的基础上进行实现的，因此在这里我们就不阐述太多废话了。

其实大家或多或少都能找到些答案，我能做的事情也越来越少了，可能我需要花点时间找到新的信仰或者新的能支持我重新变得热爱生活这样子。。。。。。

其实那天在评分上看到了一条关于pvz中智慧树的评论：

“当智慧已经在玩家之间传递，那么这棵树的使命就已经达到了”。

是我做不到的伟大。。。。。。。

1.基本操作：

复制文件：

实验7需要复制的文件很多，有这些

这么多文件我得承认改的很多，一个一个来呗。。。

addrspace：

方法上，新增如下内容

变量上，新增如下内容：

而在具体的方法实现上，比较麻烦：

首先需要对部分方法进行修改

构造和析构全面重写

AddrSpace::AddrSpace(char *noffFileName)
{
    NoffHeader noffH;
    int i;
    unsigned int memSize;
    char sFileName[24];


    // 该部分在实验六中就已经实现，伟大无需多言
    bool flag = false;
    for(i = 0; i < NumPhysPages; i++) {
        if(!ProgMap[i]) {
            ProgMap[i] = true;
            flag = true;
            spaceID = i;
            break;
        }
    }
    ASSERT(flag);

    //lab7修改：获取文件的执行对象
    OpenFile *executable = fileSystem->Open(noffFileName);
    if (executable == NULL) {
        printf("Can't open NOFF file %s\n", noffFileName);
        currentThread->Finish();
    }

    // Read NoffHeader and change endian if needed
    executable->ReadAt((char *)&noffH, sizeof(noffH), 0);
    if ((noffH.noffMagic != NOFFMAGIC) &&
        (WordToHost(noffH.noffMagic) == NOFFMAGIC))
        SwapHeader(&noffH);
    ASSERT(noffH.noffMagic == NOFFMAGIC);

  // How big is address space?
    memSize = noffH.code.size + noffH.initData.size + noffH.uninitData.size
            + UserStackSize;  // we need to increase the size
                        // to leave room for the stack
    numPages = divRoundUp(memSize, PageSize);
    memSize = numPages * PageSize;

    ASSERT( maxFramesPerProc <= NumPhysPages &&
       maxFramesPerProc <= freeMM_Map->NumClear() );  // check we're not trying
                                // to run anything too big


    DEBUG('a', "Initializing address space, num pages %d, memory size %d\n",
                    numPages, memSize);

    // First, set up the translation 
    pageTable = new TranslationEntry[numPages];
    for (i = 0; i < numPages; i++) {
        pageTable[i].virtualPage = i;  // for TLB only
        pageTable[i].physicalPage = -1;  // Not in phy. memory
        pageTable[i].valid = false;
        pageTable[i].use = false;
        pageTable[i].dirty = false;
        pageTable[i].readOnly = false;  // if the code segment was entirely on
                    // a separate page, we could set its
                    // pages to be read-only
    }


    //从下方开始是对addrspace方法的完全改写了，不太明白发生了什么

    // Create and open swap file per user process
    sprintf(sFileName, "SWAP%d", spaceID);
    if (!fileSystem->Create(sFileName, 0)) {	 // Create swap file
	    printf("Can't create swap file %s\n", sFileName);
	    currentThread->Finish();
    }
    swapFile = fileSystem->Open(sFileName);
    if (swapFile == NULL) {
        printf("Can't open swap file %s\n", sFileName);
        currentThread->Finish();
    }


    // Fill the entire swap file with 0s for uninitialized data
    char *pageBuf = new char[PageSize];
    bzero(pageBuf, PageSize);
    for(i = 0; i < numPages; i++)
        swapFile->WriteAt(pageBuf, PageSize, i * PageSize);
    delete [] pageBuf;


    // Copy the code segment from excutable to swap file
    if (noffH.code.size > 0) {
        DEBUG('a', "Initializing code segment, at 0x%x, size %d\n",
            noffH.code.virtualAddr, noffH.code.size);
        char *buf = new char[noffH.code.size];
        executable->ReadAt(buf, noffH.code.size, noffH.code.inFileAddr);
        swapFile->WriteAt(buf, noffH.code.size, noffH.code.virtualAddr);
        delete [] buf;
    }

    // Copy the initialized data segment from excutable to swap file
    if (noffH.initData.size > 0) {
        DEBUG('a', "Initializing data segment, at 0x%x, size %d\n",
            noffH.initData.virtualAddr, noffH.initData.size);
        char *buf = new char[noffH.initData.size];
        executable->ReadAt(buf, noffH.initData.size, noffH.initData.inFileAddr);
        swapFile->WriteAt(buf, noffH.initData.size, noffH.initData.virtualAddr);
        delete [] buf;
    }

    delete executable;

    printf("User program: %s, SpaceId: %d, Memory size: %u\n", \
        noffFileName, spaceID, memSize);
    printf("Max frames per user process: %d, Swap file: %s, Page replacement algorithm: %s\n", \
        maxFramesPerProc, sFileName, pageRepAlgName[pageRepAlg]);


    // Initialize pagesInMem array
    pagesInMem = new int[maxFramesPerProc];
    for(i = 0; i < maxFramesPerProc; i++)
        pagesInMem[i] = -1;

    idx = 0;
    bottom = 0;
    count = 0;

    if(bRecRefStr) {  // Record reference string
        lastVirtPage = -1;

        sprintf(sFileName, "REFSTR%d", spaceID);
        if( (fdRefStr = open(sFileName, O_WRONLY | O_CREAT | O_TRUNC, 0666)) == -1 ) {
            printf("Can't open binary reference string file %s for write\n", sFileName);
            currentThread->Finish();
        }

        sprintf(sFileName, "REFSTR%d.TXT", spaceID);
        if((fpRefStr = fopen(sFileName, "wb")) == NULL) {
            printf("Can't open text reference string file %s for write\n", sFileName);
            currentThread->Finish();
        }
    }

    else if(pageRepAlg == PRA_OPT) {  // Optimal. Get reference string from recorded host file
        sprintf(sFileName, "REFSTR%d", spaceID);
        if( (fdRefStr = open(sFileName, O_RDONLY)) == -1 ) {
            printf("Can't open binary reference string file %s for read\n", sFileName);
            currentThread->Finish();
        }
        int refStrFileLen = lseek(fdRefStr, 0, SEEK_END);
        lseek(fdRefStr, 0, SEEK_SET);
        printf("Binary reference string file %s length: %d\n", sFileName, refStrFileLen);
        if(refStrFileLen % 2) {
            printf("The length of binary reference string file %s must be even\n", sFileName);
            currentThread->Finish();
        }

        optRefStrLen = refStrFileLen / 2;
        printf("Reference string items: %d\n", optRefStrLen);

        optRefStr = new unsigned short[optRefStrLen];
        int res, nRead = 0, nLeft = refStrFileLen;
        while(nLeft) {
            res = read(fdRefStr, (char *)optRefStr + nRead, nLeft);
            if(!res)
                break;
            else if(res == -1) {
                printf("Binary reference string file %s read error\n", sFileName);
                currentThread->Finish();
            }
            else {
                printf("%d bytes read from binary reference string file %s\n", res, sFileName);
                nRead += res;
                nLeft -= res;
            }
        }

        refIdx = 0;
        close(fdRefStr);
    }


    Print();

}  // AddrSpace::AddrSpace


//----------------------------------------------------------------------
// AddrSpace::~AddrSpace
//  Dealloate an address space.
//----------------------------------------------------------------------


//在析构方法中，需要对申请过的属性进行全面的释放
AddrSpace::~AddrSpace()
{
    ProgMap[spaceID] = 0;
    for (int i = 0; i < numPages; i++)
        if (pageTable[i].valid)
            freeMM_Map->Clear(pageTable[i].physicalPage);

    delete [] pageTable;
    delete swapFile;
    delete [] pagesInMem;

    if(pageRepAlg == PRA_OPT)
        delete [] optRefStr;

    if(bRecRefStr) {
        if(fdRefStr != -1)
            close(fdRefStr);
        if(fpRefStr != NULL)
            fclose(fpRefStr);
    }
}

重写打印的方法

void AddrSpace::Print(void)//重写打印方法
{
    printf("SpaceId: %d, Page table dump: %d pages in total\n", spaceID, numPages);
    printf("===============================\n");
    printf(" Page, Frame, Valid, Use, Dirty\n");
    for (int i = 0; i < numPages; i++)
        printf("%5d,  %4d,     %d,   %d,     %d\n",\
        i, pageTable[i].physicalPage,\
        pageTable[i].valid, pageTable[i].use, pageTable[i].dirty);
    printf("===============================\n\n");
}

对于新方法的全部实现

//下面主要是一些算法的处理
//FIFO
int AddrSpace::findPageFIFO(int inPage)
{
    int victim = pagesInMem[idx];
    pagesInMem[idx] = inPage;
    idx = (idx + 1) % maxFramesPerProc;

    return victim;
}


//2Change算法
int AddrSpace::findPage2ndChance(int inPage)
{
    bool bFound = false;
    int victim;

    while(!bFound) {
        if(pagesInMem[idx] < 0) {
            victim = -1;
            pagesInMem[idx] = inPage;
            bFound = true;
        }
        else if(pageTable[pagesInMem[idx]].use)
            pageTable[pagesInMem[idx]].use = false;
        else {
            victim = pagesInMem[idx];
            pagesInMem[idx] = inPage;
            bFound = true;
        }

        idx = (idx + 1) % maxFramesPerProc;
    }

    return victim;
}


//替换
int AddrSpace::findPageE2ndChance(int inPage)
{
    int victim;

    for(int loop = 1; loop <= 4; loop++) {
        for(int i = 0; i < maxFramesPerProc; i++) {
            if(loop == 1 || loop == 3) {
                if(loop == 1 && pagesInMem[idx] < 0) {
                    pagesInMem[idx] = inPage;
                    idx = (idx + 1) % maxFramesPerProc;
                    return -1;
                }
                else if(!pageTable[pagesInMem[idx]].use && !pageTable[pagesInMem[idx]].dirty) {
                    victim = pagesInMem[idx];
                    pagesInMem[idx] = inPage;
                    idx = (idx + 1) % maxFramesPerProc;
                    return victim;
                }
            }
            else {  // loop == 2 || loop == 4
                if(!pageTable[pagesInMem[idx]].use && pageTable[pagesInMem[idx]].dirty) {
                    victim = pagesInMem[idx];
                    pagesInMem[idx] = inPage;
                    idx = (idx + 1) % maxFramesPerProc;
                    return victim;
                }
                else if(loop == 2 && pageTable[pagesInMem[idx]].use)
                    pageTable[pagesInMem[idx]].use = false;
            }

            idx = (idx + 1) % maxFramesPerProc;
        }  // for(i)
    }  

    printf("Fatal error! Enhanced 2nd chance failed to find victim frame\n");
    return -1;
}


//LRU算法
void AddrSpace::updatePageLRU(int vpn)
{
    int i, j;

    for(i = 0; i < count; i++) {
        if(pagesInMem[(bottom + i) % maxFramesPerProc] == vpn) {  // Found in stack, merge
            for(j = i; j < count; j++)
                pagesInMem[(bottom + j) % maxFramesPerProc] = pagesInMem[(bottom + j + 1) % maxFramesPerProc];
            pagesInMem[(bottom + count - 1) % maxFramesPerProc] = vpn;
            return;
        }
    }

    printf("Fatal error! Page %d not in LRU stack\n", vpn);
}


//LRU请求页面
int AddrSpace::findPageLRU(int inPage)
{
    int victim;

    if(count < maxFramesPerProc) {
        pagesInMem[(bottom + count) % maxFramesPerProc] = inPage;
        count++;
        return -1;
    }

    victim = pagesInMem[bottom];
    pagesInMem[bottom] = inPage;
    bottom = (bottom + 1) % maxFramesPerProc;
    return victim;
}


//OPT算法更新页面
void AddrSpace::updatePageOpt(int vpn)
{
    if(optRefStr[refIdx] == vpn)  // Same page reference
        return;
    else {
        if(++refIdx >= optRefStrLen) {
            printf("Fata error! Run out of optimal reference string\n");
            currentThread->Finish();
        }
        if(optRefStr[refIdx] != vpn) {  // Next page reference not match
            printf("Fata error! Optimal reference string item #%d mismatch, expect %d, is %d\n",\
                    refIdx, optRefStr[refIdx], vpn);
            currentThread->Finish();
        }
        if(refIdx == optRefStrLen - 1) {
            char sFileName[24];
            sprintf(sFileName, "REFSTR%d", spaceID);
            printf("Reach the last reference string item in %s\n", sFileName);
        }
    }
}


//OPT算法寻找页面
int AddrSpace::findPageOpt(int inPage)
{
    int victim;

    if(pagesInMem[idx] < 0) {
        pagesInMem[idx] = inPage;
        idx = (idx + 1) % maxFramesPerProc;
        return -1;
    }

    int i, j, lookPage, dist = -1, index = 0;
    bool bInfinite;
    for(i = 0; i < maxFramesPerProc; i++) {
        lookPage = pagesInMem[i];
        bInfinite = true;
        for(j = refIdx; j < optRefStrLen; j++) {
            if(lookPage == optRefStr[j]) {  // 1st hit of this frame
                if(j - refIdx > dist) {
                    dist = j - refIdx;
                    index = i;
                }
                bInfinite = false;
                break;
            }
        }
        if(bInfinite) {
            pagesInMem[i] = inPage;
            return lookPage;
        }
    }

    victim = pagesInMem[index];
    pagesInMem[index] = inPage;
    return victim;
}


//随机算法寻找页面
int AddrSpace::findPageRand(int inPage)
{
    int index, victim;

    if(pagesInMem[idx] < 0) {
        pagesInMem[idx] = inPage;
        idx = (idx + 1) % maxFramesPerProc;
        return -1;
    }

    index = Random() % maxFramesPerProc;
    victim = pagesInMem[index];
    pagesInMem[index] = inPage;
    return victim;
}


//LRU更新页面
void AddrSpace::updatePage(int vpn)
{
    if(pageRepAlg == PRA_LRU)
        updatePageLRU(vpn);
    else if(pageRepAlg == PRA_OPT) {
        updatePageOpt(vpn);
        return;
    }

    if(bRecRefStr && vpn != lastVirtPage) {
        lastVirtPage = vpn;

        // Write new page number to reference string files
        if(fdRefStr != -1) {
            if(vpn > SHRT_MAX)
                printf("Can't record page %d, page number must <= %d\n", vpn, SHRT_MAX);
            else
                write(fdRefStr, &vpn, sizeof(unsigned short));
        }

        if(fpRefStr != NULL)
            fprintf(fpRefStr, "%d\n", vpn);
    }
}


//页面进行调换的算法
void AddrSpace::replacePage(unsigned int badVAddr)
{
    int inPage, outPage;

    stats->numPageFaults++;
    inPage = badVAddr / PageSize;

    switch(pageRepAlg) {
        case PRA_FIFO:
            outPage = findPageFIFO(inPage);
            break;
        case PRA_2ND:
            outPage = findPage2ndChance(inPage);
            break;

        case PRA_E2ND:
            outPage = findPageE2ndChance(inPage);
            break;

        case PRA_OPT:
            outPage = findPageOpt(inPage);
            break;

        case PRA_RAND:
            outPage = findPageRand(inPage);
            break;

        case PRA_LRU:
        default:
            outPage = findPageLRU(inPage);
            break;
    }

    if(outPage < 0) {  // Allocated frames not used out
        printf("Demand page %d in", inPage);
        pageTable[inPage].physicalPage = freeMM_Map->Find();
        if(pageTable[inPage].physicalPage < 0) {
            printf("\nPanic! Run out of user physical memory\n");
            currentThread->Finish();
        }
        printf("(frame %d)\n", pageTable[inPage].physicalPage);
    }
    else {  // Swap out, swap in
        printf("Swap page %d out, demand page %d in(frame %d)\n", outPage, inPage, pageTable[outPage].physicalPage);
        writeBack(outPage);
        pageTable[outPage].valid = false;
        pageTable[inPage].physicalPage = pageTable[outPage].physicalPage;
    }
    pageTable[inPage].valid = true;
    pageTable[inPage].use = true;
    pageTable[inPage].dirty = false;

    // Read to the physical frame just swapped out
    swapFile->ReadAt(&(machine->mainMemory[pageTable[inPage].physicalPage * PageSize]),
               PageSize, inPage * PageSize);
    Print();
}


//写回方法

void AddrSpace::writeBack(int victimPage)
{
    if(pageTable[victimPage].dirty) {
        printf("Write back victim page %d to disk\n", victimPage);
        swapFile->WriteAt(&(machine->mainMemory[pageTable[victimPage].physicalPage * PageSize]),
                    PageSize, victimPage * PageSize);
        stats->numPageWrites++;
    }
}

exception：

同实验六，对其中唯一的方法作出一些改写

void
ExceptionHandler(ExceptionType which)
{
    int type = machine->ReadRegister(2);

    if (which == SyscallException) {
        switch (type) {	
            case SC_Halt:
                DEBUG('a', "Shutdown, initiated by user program.\n");
                interrupt->Halt();
                break;

            case SC_Exec:
                interrupt->Exec();
                machine->WriteRegister(PrevPCReg, machine->ReadRegister(PCReg)); 
	            machine->WriteRegister(PCReg, machine->ReadRegister(NextPCReg)); 
	            machine->WriteRegister(NextPCReg, machine->ReadRegister(NextPCReg) + 4); 
                break;
            default:
                printf("Syscall %d not implemented\n", type);
                	machine->WriteRegister(PrevPCReg, machine->ReadRegister(PCReg)); 
	                machine->WriteRegister(PCReg, machine->ReadRegister(NextPCReg)); 
	                machine->WriteRegister(NextPCReg, machine->ReadRegister(NextPCReg) + 4); 
                break;
        }
    }
    else if (which == PageFaultException)
        interrupt->PageFault();
    else {
        printf("Unexpected user mode exception %d %d\n", which, type);
        ASSERT(FALSE);
    }
}

interrupt：

在头文件中声明：

在cc中实现和调整如下代码：

//切换运行一个用户进程的方法

void RunProcess(int id)
{
    ASSERT(currentThread->space->getSpaceID() == id);
    currentThread->space->InitRegisters();  // set the initial register values
    currentThread->space->RestoreState();   // load page table register

    machine->Run();	 // jump to the user progam
    ASSERT(FALSE);   // machine->Run never returns;
					 // the address space exits
					 // by doing the syscall "exit"
}


//切换并且执行另一个用户进程的方法

void Interrupt::Exec(void)
{
    printf("Execute system call of Exec()\n");

    // read argument
    char fileName[50];
    int addr = machine->ReadRegister(4);
    int i = 0;

    do {
       machine->ReadMem(addr + i, 1, (int*) &fileName[i]); // read filename from mainMemory
    } while(fileName[i++] != '\0');

    printf("Exec(%s):\n", fileName); 

    AddrSpace *space = new AddrSpace(fileName);    

    Thread *thread = new Thread(fileName);  // New thread for another user program
    thread->space = space;

    thread->Fork(RunProcess, (int)space->getSpaceID());
    currentThread->Yield();

    machine->WriteRegister(2, (int)space->getSpaceID());  // Return SpaceId
}


//错误页方法

void
Interrupt::PageFault()
{
	int badVAddr = machine->ReadRegister(BadVAddrReg); // The failing virtual address on an exception
	AddrSpace *space = currentThread->space;
	space->replacePage(badVAddr);
}


//来自实验6的，在用户进程中打印整数的方法

void Interrupt::PrintInt(int v)
{
    printf("%d\n", v);
}


//调度方法
void
Interrupt::Schedule(VoidFunctionPtr handler, _int arg, int fromNow, IntType type)
{
    int when = stats->totalTicks + fromNow;
    PendingInterrupt *toOccur = new PendingInterrupt(handler, arg, when, type);

    DEBUG('i', "Scheduling interrupt handler the %s at time = %d\n", 
					intTypeNames[type], when);
    ASSERT(fromNow > 0);

    pending->SortedInsert(toOccur, when);
}

testporg.cc：

只需要调整这一个方法即可

void
StartProcess(char *filename)
{
    AddrSpace *space;

    space = new AddrSpace(filename);    
    currentThread->space = space;

    //答案中该部分去掉了可行性检查。。。。
    //剩下的该文件中就没啥变化了

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

    machine->Run();			// jump to the user progam
    ASSERT(FALSE);			// machine->Run never returns;
					// the address space exits
					// by doing the syscall "exit"
}

translate：

只需要这个方法中新增一条就可以

xceptionType
Machine::Translate(int virtAddr, int* physAddr, int size, bool writing)
{
    。。。。。。。。。。。。

    currentThread->space->updatePage(vpn);  //当前线程更新页面

    return NoException;
}

stats：

只要新增一个属性的说明就行了

并且在对应类的输出语句中进行如下修改即可

void
Statistics::Print()
{
    printf("Ticks: total %d, idle %d, system %d, user %d\n", totalTicks, 
	idleTicks, systemTicks, userTicks);
    printf("Disk I/O: reads %d, writes %d\n", numDiskReads, numDiskWrites);
    printf("Console I/O: reads %d, writes %d\n", numConsoleCharsRead, 
	numConsoleCharsWritten);
    printf("Paging: faults %d, write backs %d\n", numPageFaults, numPageWrites);  //输出语句新增错误修改
    printf("Network I/O: packets received %d, sent %d\n", numPacketsRecvd, 
	numPacketsSent);
}

system：

说实话这个文件里的改动我是一个字都不认识。。。

头文件中改动如下：

在cc文件中改动如下

以上就是实验7的全部修改内容了

2.实验调试

实验调试内容如下：

使用指令

./nachos -x ../test/sort.noff???
?

然后调用指令

./nachos -mf 4 -pra 1 -x ../test/sort.noff???