# Nachos OS Project 3
HackMD好讀版： https://hackmd.io/@He1sEnBerG/HyClb7j8p
## Part 1
### What is your motivation, problem analysis and plan ?
由於這次跑得 code 會耗費大量記憶體，所以不像是 HW1 時可以把程式都放進 memory 裡，需要設計虛擬記憶體(Virtual Memory)的機制，所以我打算先看我 HW1 對 PageTable 的實做並照著助教的提示完成作業。
### Explain the details of code snippet you added or modified.
首先我們在 kernel 裡加入一個 class 專門處理 PageFault
#### Private members
- phy2virPage
*考慮到我們需要同時運行兩個 process，因此在進行 Page Swap 的過程中，我們需要確定目前正在使用 Physical Page 的 Page 的是誰（可能位於另一個 PageTable 中）。因此，我們使用 **phy2virPage** 來儲存與 Physical Page 對應的 Page (TranslationEntry)。*
- swap
*用 nachos 裡的 synchDisk 做硬碟讀寫*
- vmPages
*紀錄那些 Virtual Pages 已被使用，這裡會用 Virtual Page Num 來當作硬碟讀寫的 sector*
- fifo
*FIFO replacement會用到的 counter*
#### Public members
- getVmPageNum()
*回傳尚未被使用的 Virtual Page Number*
- trackPhyPage(int, TranslationEntry)
*把使用 PhyPage 的 Page 記錄進 phy2virPage
- write2Disk(int sector, char *data)
*把 data 寫進 disk 裡的 sector
- swapPage(int vpn, int algo)
*把目前 PageTable[vpn] 裡的 Page swap 進 main memory，algo目前只有FIFO*

**userprog/userkernel.h**

class VirtualMemory;
class UserProgKernel : public ThreadedKernel
{
public:
    ...
    Machine *machine;
    FileSystem *fileSystem;
    // add here
    VirtualMemory *virtualMemory;
    ...
}

class VirtualMemory
{
public:
    VirtualMemory();
    int getVmPageNum();
    void trackPhyPage(int phyPageNum,TranslationEntry *entry);
    void write2Disk(int sector, char *data);
    void swapPage(int vpn, int algo);
private:
    // Tracks the virtual page that uses physical page
    TranslationEntry *phy2virPage[NumPhysPages];
    SynchDisk *swap;
    bool vmPages[1024];  // 1024 = NumSector
    int fifo;
};

**userprog/userkernel.cc**

VirtualMemory::VirtualMemory()
{
    swap = new SynchDisk("Swap");
    memset(vmPages, 0, 1024);
    fifo = 0;
}
int VirtualMemory::getVmPageNum()
{
    int i;
    for (i = 0; i < 1024; i++) {
        if (vmPages[i] == 0) {
            vmPages[i] = 1;
            break;
        }
    }
    return i;
}
void VirtualMemory::write2Disk(int sector, char *data)
{
    swap->WriteSector(sector, data);
}
void VirtualMemory::trackPhyPage(int phyPageNum, TranslationEntry *entry)
{
    phy2virPage[phyPageNum] = entry;
}

void VirtualMemory::swapPage(int vpn, int algo)
{
    int target;
    char *buf1;
    char *buf2;

    if (algo == 0) {    // FIFO
        target = fifo;
        fifo = (fifo + 1) % NumPhysPages;
    }
    
    buf1 = new char[PageSize];
    buf2 = new char[PageSize];
    
    // Read target Page from main memory to buf1
    memcpy(buf1, &kernel->machine->mainMemory[target * PageSize], PageSize);
    // Read virtual page data from disk to buf2
    swap->ReadSector(kernel->machine->pageTable[vpn].virtualPage, buf2);
    // Load buf2 to main memory
    memcpy(&kernel->machine->mainMemory[target * PageSize], buf2, PageSize);
    // Write buf1 to disk
    swap->WriteSector(kernel->machine->pageTable[vpn].virtualPage, buf1);

    phy2virPage[target]->virtualPage = kernel->machine->pageTable[vpn].virtualPage;
    phy2virPage[target]->valid = FALSE;

    kernel->machine->pageTable[vpn].valid = TRUE;
    kernel->machine->pageTable[vpn].physicalPage = target;
    trackPhyPage(target,&kernel->machine->pageTable[vpn]);

    delete[] buf1;
    delete[] buf2;

    return;
}

void UserProgKernel::Initialize()
{
    ThreadedKernel::Initialize();  // init multithreading

    machine = new Machine(debugUserProg);
    fileSystem = new FileSystem();
    // add VM
    virtualMemory = new VirtualMemory();
    ...
}

再來就是修改 addrspace 中把 code load 進記憶體的部份

**userprog/addrspace.h**

用 pageTable_loaded 紀錄 pageTable 是否 Load 完成，防止 AddrSpace::SaveState() 把 addrspace 內資料覆蓋掉

class AddrSpace{
    ...
private:
    bool pageTable_loaded;
    ...
};

**userprog/addrspace.cc**
透過使用 gdb，發現 noffH.initData.size 的值都為 0，因此這次作業只需要處理 noffH.code。解決方式大致上是，如果 phyPage 仍然足夠，則採取與之前作業相同的處理方式。但如果 phyPage 不足，則將資料寫入 Disk，再將存儲的 disk sector 存放到 Page 資訊中，同時將 valid 設置為 false。這樣在程式執行時，讀取這些頁面將引發 PageFaultException

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);

    // how big is address space?
    size = noffH.code.size + noffH.initData.size \
         + noffH.uninitData.size + UserStackSize; 
                                                                                           // to leave room for the stack
    numPages = divRoundUp(size, PageSize);
    // cout << "number of pages of " << fileName<< " is "<<numPages<<endl;

    pageTable = new TranslationEntry[numPages];


    for (unsigned int i = 0; i < numPages; i++) {
        pageTable[i].virtualPage = 0;
        pageTable[i].physicalPage = 0;
        pageTable[i].valid = FALSE;
        pageTable[i].use = FALSE;
        pageTable[i].dirty = FALSE;
        pageTable[i].readOnly = FALSE;
    }

    size = numPages * PageSize;

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

    // then, copy in the code and data segments into memory

    if (noffH.code.size > 0) {
        for (unsigned int i = 0; i < numPages; i++) { 
            unsigned int j;
            for (j = 0; j < NumPhysPages; j++) {  // find unused Physical pages
                if (!usedPhysicalPage[j]) {
                    break;
                }
            }

            if (j < NumPhysPages) {  // if there is unused Physical pages
                DEBUG(dbgAddr, "Phy page found: " << i);
                usedPhysicalPage[j] = true;
                pageTable[i].physicalPage = j;
                pageTable[i].valid = TRUE;
                kernel->virtualMemory->trackPhyPage(j,&pageTable[i]);

                executable->ReadAt(&(kernel->machine->mainMemory[j * PageSize])\
                            , PageSize, noffH.code.inFileAddr + (i * PageSize));
            } else {  // write in disk
                DEBUG(dbgAddr, "No enough physical pages for page " << i);
                char *buffer;
                buffer = new char[PageSize];

                // Find empty Virtual Page
                pageTable[i].virtualPage = kernel->virtualMemory->getVmPageNum();
                pageTable[i].valid = FALSE;
                executable->ReadAt(buffer, PageSize, \ 
                                   noffH.code.inFileAddr + (i * PageSize));
                kernel->virtualMemory->write2Disk(pageTable[i].virtualPage, buffer);
                delete[] buffer;
            }
        }
    }
    ...
}

void AddrSpace::SaveState()
{
    if (pageTable_loaded) {
        pageTable = kernel->machine->pageTable;
        numPages = kernel->machine->pageTableSize;
    }
}

最終要處理的是當遇到 PageFault 時的 ExceptionHandler。計算完 vpn 就傳入上面寫好的**VirtualMemory::swapPage**進行處理。

**userprog/exception.cc**

void ExceptionHandler(ExceptionType which)
{
    int type = kernel->machine->ReadRegister(2);
    int val, vaddr, vpn;

    switch (which) {
    case PageFaultException:
        kernel->stats->numPageFaults++;
        vaddr = kernel->machine->ReadRegister(39);
        vpn = vaddr / PageSize;

        // algo: 0:FIFO, 1:LFU, 2:LRU
        kernel->virtualMemory->swapPage(vpn,0);
        return;
            
    case SyscallException:
        ...
}

### Experiment result and some discussion, observation.
首先 sort.c 應該寫錯了，第 25 行 j 要從 0 開始而非 i，然後最小值 A[0] 應該為 1 而非 0
#### FIFO
matmult
sort
Running Both

### What problem you face and how to tackle it?
### 問題一
在處理 addrspace.cc 的時候遇到了一個重要的問題。具體來說，當我在寫到 addrspace.cc 中的 Load() 函數時，想要測試在 phyPage 不足的情況下，能否成功將資料寫入硬碟。然而當我打開了 debug flag a 觀察時，發現 Load() 在儲存了 phyPage + 1 個頁面後就終止了。

通過使用 gdb 進行逐步執行，我發現在執行完 WriteSector 後，Addrspace 中的數據都會消失。進一步觀察 WriteSector 函數，我發現它設置了計時器中斷，模擬讀取硬碟的時間。這讓我誤以為在 HW2 中，我將計時器的 CallBack() 寫錯了。但是當我回到 HW1 時的 commit，仍然發現了相同的問題。

最終，我發現處理 timer interrupt 時 context switch 會執行 AddrSpace::SaveState()，這會導致機器中的空數據覆蓋我們正在寫入一半的 PageTable。解決這個問題的方法是在執行 Load 之前設置一個變數 pageTable_loaded，等到所有頁面都成功加載後再允許 SaveState 執行。
### 問題二
第二個問題是在實作 Page Replacement Algorithm 遇到的問題，就是不管是 LFU 還是 LRU 都需要紀錄 Page 的讀取，我原本是在Machine::Translate裡統計讀取資訊，但由於作業規定不能更改 machine 裡的檔案，變成只有 PageFault Exception 發生時我們才有控制權，這會使其他演算法無法設計。