好難……嗚嗚嗚QQ

作業要求

實現 virtual memory 並可以處理 page fault
實作 Page Replacement Algorithm 的 FIFO 與 LRU
- First in First out Page Replacement(FIFO)
- Least Recently Used Page Replacement(LRU)

Virtual Memory

為了實作 virtual memory 的部分，把前面原本 multiprogramming 的地方修改了
先在 /code/userprog/userkernel.h 中加上輔助用的記憶體

class UserProgKernel : public ThreadedKernel {
  public:
    // 利用 SynchDisk 作為輔助記憶體
    SynchDisk *virtualMemoryDisk;

還有 /code/userprog/userkernel.cc

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

    machine = new Machine(debugUserProg);
    fileSystem = new FileSystem();
	// 加上這一行增加輔助記憶體
    virtualMemoryDisk = new SynchDisk("Virtual Memory");
#ifdef FILESYS
    synchDisk = new SynchDisk("New SynchDisk");
#endif // FILESYS
}

在 /code/machine/machine.h 中加上會使用到的變數

class Machine {
  public:
    bool usedPhyPage[NumPhysPages];		// 紀錄那些 physical memory 已經被使用了
    bool usedvirPage[NumPhysPages];		// 記錄那些 virtual memory 已經被使用了
    int  ID_num;				// 每個 thread 都有一個專屬 ID_num 作為識別用的
    int PhyPageName[NumPhysPages];
    int count[NumPhysPages];			// LRU 用的 counter

    TranslationEntry *main_tab[NumPhysPages];
	static int fifo;

宣告必要參數
/code/userprog/addrspace.h

class AddrSpace {
    public:
        int ID;       // 存他 thread 的 id
    private:
        bool pageTableLoaded;
}

許多調整都在此處，這裡負責 load 程式碼到 memory 裡面，所以相當重要。
我在這裡開一個專屬這個 thread 的 page table，在 load 時一直往下找記憶體直到找到沒被用到的或是到底為止，以此來判斷 memory 夠不夠用，若不夠就需要用到輔助記憶體，需要存好一些重要參數以便要用的時候找得到。

/code/userprog/addrspace.cc
後來覺得這段很醜所以就不放過來了，留在github裡面了。

Page Replacement

宣告參數
/code/machine/tranlate.h

class TranslationEntry {
  public:
    int count;    //for LRU
    int ID;
};

主要都是改 else if (!pageTable[vpn].valid) 裡面的東西，FIFO 就是一直照順序當 victim，
LRU 則是用一個 count 來計被用到的次數，每次把次數最少的換掉。
找完 victim 之後再去做 swap in swap out 的動作。
/code/machine/tranlate.cc

else if (!pageTable[vpn].valid) {
	printf("page fault\n");
	kernel->stats->numPageFaults++;
	j = 0;
	while(kernel->machine->usedPhyPage[j] != false && j < NumPhysPages){ j++; }
	if (j < NumPhysPages) {
		char *buffer;
		buffer = new char[PageSize]; 
		kernel->machine->usedPhyPage[j] = true;
		kernel->machine->PhyPageName[j] = pageTable[vpn].ID;

		kernel->machine->main_tab[j] = &pageTable[vpn];
		pageTable[vpn].physicalPage = j;
		pageTable[vpn].valid = true;
		pageTable[vpn].count++; //for LRU

		kernel->virtualMemoryDisk->ReadSector(pageTable[vpn].virtualPage, buffer);
		bcopy(buffer, &mainMemory[j * PageSize], PageSize);
	}
	else {
		char *buffer1;
		buffer1 = new char[PageSize];
		char *buffer2;
		buffer2 = new char[PageSize];

		//FIFO
		if (kernel->vmtype == 0){
			victim = fifo % 32; // 32 is NumPhysPages
		}

		//LRU
		if (kernel->vmtype == 1) {
			int min = pageTable[0].count;
			victim = 0;
			for(int i = 0; i < 32; i++){
				//printf("%d",pageTable[i].count);
				if(min > pageTable[i].count){
					min = pageTable[i].count;
					victim = i;
				}
			} 
			pageTable[victim].count++;  
		}
		

		printf("page %d swapped\n",victim);

		// 把東西存到 disk 裡面
		bcopy(&mainMemory[victim * PageSize], buffer1, PageSize);
		kernel->virtualMemoryDisk->ReadSector(pageTable[vpn].virtualPage, buffer2);
		bcopy(buffer2, &mainMemory[victim*PageSize], PageSize);
		kernel->virtualMemoryDisk->WriteSector(pageTable[vpn].virtualPage, buffer1);

		main_tab[victim]->virtualPag e= pageTable[vpn].virtualPage;
		main_tab[victim]->valid = false;

		// 把東西 load 到 main memory 中
		pageTable[vpn].valid = true;
		pageTable[vpn].physicalPage = victim;
		kernel->machine->PhyPageName[victim] = pageTable[vpn].ID;
		main_tab[victim] = &pageTable[vpn];
		fifo ++;
	}
}