nachos-虚拟内存管理
nachos虛擬內(nèi)存實(shí)驗(yàn)
文章目錄
- nachos虛擬內(nèi)存實(shí)驗(yàn)
- 內(nèi)容一、總體概述
- 內(nèi)容二、任務(wù)完成情況
- 具體Exercise的完成情況
- 1.Exercise1 源代碼閱讀
- 2.Exercise2 TLB MISS 異常處理
- Exercise 3 置換算法
- Exercise 4 內(nèi)存全局管理數(shù)據(jù)結(jié)構(gòu)
- Exercise 5 多線程支持
- Exercise 6 缺頁(yè)中斷處理
- Exercise 7 lazy-loading
- Challenge2 多線程實(shí)現(xiàn)基本思路：
- 內(nèi)容三：遇到的困難及解決方法
- 內(nèi)容四：收獲及感想
- 內(nèi)容五：對(duì)課程的意見(jiàn)和建議
內(nèi)容一、總體概述
本次實(shí)驗(yàn)主要是通過(guò)閱讀相關(guān)代碼,了解 nachos用戶程序的執(zhí)行過(guò)程,之后完成TLB,頁(yè)表和虛擬內(nèi)存等的實(shí)現(xiàn)。。其中第一部分主要內(nèi)容是實(shí)現(xiàn)TLB相關(guān)異常處理和置換算法，當(dāng)前的 nachos只支持單個(gè)用戶程序,沒(méi)有用到TLB。第二部分的主要內(nèi)容是實(shí)現(xiàn)全局內(nèi)存管理機(jī)制,使得 nachos內(nèi)存可以同時(shí)存在多個(gè)線程。第三部分的主要內(nèi)容是實(shí)現(xiàn)程序運(yùn)行過(guò)程中發(fā)生缺頁(yè)中斷時(shí)，才會(huì)將所需的頁(yè)面從磁盤(pán)調(diào)入內(nèi)存。Challenge部分是增加線程掛起狀態(tài)以及實(shí)現(xiàn)倒排頁(yè)表。
內(nèi)容二、任務(wù)完成情況
任務(wù)完成列表（Y/N）
| Y | Y | Y | Y | Y | Y | Y | Y |
具體Exercise的完成情況
1.Exercise1 源代碼閱讀
- 閱讀code/userprog/progtest.cc，著重理解nachos執(zhí)行用戶程序的過(guò)程，以及該過(guò)程中與內(nèi)存管理相關(guān)的要點(diǎn)。
- 閱讀code/machine目錄下的machine.h(cc)，translate.h(cc)文件和code/userprog目錄下的exception.h(cc)，理解當(dāng)前Nachos系統(tǒng)所采用的TLB機(jī)制和地址轉(zhuǎn)換機(jī)制。
(1)用戶程序執(zhí)行過(guò)程
userprog/progtest.cc定義函數(shù)
StartProcess主要功能是實(shí)現(xiàn)用戶程序啟動(dòng)，
如果我們希望執(zhí)行test中的用戶程序，
那么我們進(jìn)入userprog，執(zhí)行./nachos -x …/test/
（用戶程序），通過(guò)識(shí)別-x 參數(shù)，nachos 調(diào)用
StartProcess 執(zhí)行用戶程序
（具體實(shí)現(xiàn)在 threads/main.cc）
StartProcess 的基本流程是:
通過(guò)文件系統(tǒng)定義的 OpenFile 打開(kāi)相關(guān)文件
通過(guò) AddrSpace的構(gòu)造函數(shù)建立用戶空間，裝載文件
通過(guò) AddrSpace 的InitRegisters 函數(shù)初始化用戶寄存器
通過(guò) AddrSpace 的RestoreState 函數(shù)裝載頁(yè)表
通過(guò)machine的Run 函數(shù)運(yùn)行用戶程序
AddrSpace 的構(gòu)造函數(shù)實(shí)現(xiàn)在 userprog/addrspace.cc，主要流程是：
獲取文件頭，大小端做適宜轉(zhuǎn)換
通過(guò)文件頭計(jì)算文件所需空間，包括代碼段，初始化數(shù)據(jù)段，未初始化數(shù)據(jù)段，?？臻g 4 個(gè)部分
通過(guò)文件所需空間計(jì)算出文件所需的虛擬頁(yè)面數(shù)量，創(chuàng)建用戶空間頁(yè)表，指示了第 i 個(gè)虛擬頁(yè)對(duì)應(yīng)第 i 個(gè)物理頁(yè)，將用戶程序的正文段和相關(guān)數(shù)據(jù)依次調(diào)入內(nèi)存。
AddrSpace 的 InitRegisters 函數(shù)實(shí)現(xiàn)在 userprog/addrspace.cc，主要流程是：
初始化普通寄存器（初始化為 0）
初始化當(dāng)前指令指針（PC，初始化為 0）
初始化下一條指令指針（初始化為 4）
初始化棧指針（地址空間尾部適當(dāng)前移）
AddrSpace 的 RestoreState 函數(shù)實(shí)現(xiàn)在 userprog/addrspace.cc，主要流程是：
將頁(yè)表裝載到machine 類中
準(zhǔn)備執(zhí)行用戶程序machine 的Run函數(shù)實(shí)現(xiàn)在machine/mipssim.cc，基本流程是：
通過(guò) OneInstruction 函數(shù)完成指令譯碼和執(zhí)行
通過(guò)interrupt 的 OneTick 函數(shù)使得時(shí)鐘前進(jìn)
machine 的Run 函數(shù)通過(guò) machine 的ReadMem 函數(shù)讀內(nèi)存數(shù)據(jù)，通過(guò) machine的WriteMem 函數(shù)寫(xiě)內(nèi)存數(shù)據(jù)，兩個(gè)函數(shù)的實(shí)現(xiàn)在 machine/translate.cc，核心是 translate 函數(shù)
translate 函數(shù)實(shí)現(xiàn)在machine/translate.cc，主要功能是實(shí)現(xiàn)虛擬地址到物理地址的轉(zhuǎn)換，translate 函數(shù)可能返回相應(yīng)的錯(cuò)誤，在這樣的情況下，ReadMem 函數(shù)/WriteMem 函數(shù)調(diào)用 RaiseException 函數(shù)進(jìn)行處理，
RaiseException 函數(shù)定義在 machine/machine.cc，基本流程是將錯(cuò)誤信息存儲(chǔ)在特定位置，調(diào)用 ExceptionHandler 函數(shù)處理不同的錯(cuò)誤，
ExceptionHandler函數(shù)實(shí)現(xiàn)在userprog/exception.cc，主要流程是根據(jù)錯(cuò)誤信息處理不同錯(cuò)誤。
目前支持的錯(cuò)誤：
寄存器支持：
（2）TLB 機(jī)制和地址轉(zhuǎn)換機(jī)制
表項(xiàng)維護(hù)的位置是machine/translate.h 中 TranslationEntry 數(shù)據(jù)結(jié)構(gòu)
Class TranslationEntry { public: int virtualPage; // 虛擬頁(yè)號(hào) int physicalPage; // 物理頁(yè)號(hào) boot valid; // 該Entry 是否使用，TRUE 表示使用 bool readOnly; // 對(duì)應(yīng)頁(yè)的訪問(wèn)屬性，TRUE 示只讀，否則為讀寫(xiě) bool use; // 該Entry 是否被使用過(guò)，每次訪問(wèn)后置為TRUE bool dirty; // 對(duì)應(yīng)的物理頁(yè)使用情況，TRUE 表示被寫(xiě)過(guò) }相關(guān)參數(shù)
以下參數(shù)定義在filesys/disk.h #define SectorSize 128 以下參數(shù)定義在machine/machine.h #define PageSize SectorSize #define NumPhysPages 32 #define MemorySize (NumPhysPages * PageSize) #define TLBSize 4TLB 初始化的位置是machine/machine.cc 中machine 的構(gòu)造函數(shù)
TLB 的使用的位置是machine/translate.cc中的translate函數(shù)，基本流程是遍歷TLB 數(shù)組，查找是否有對(duì)應(yīng)映射，如果有，那么 TLB 命中，直接進(jìn)行物理地址轉(zhuǎn)換，否則，TLB 沒(méi)有命中，標(biāo)志 PageFaultException，進(jìn)入Exception處理。（目前還沒(méi)有對(duì)應(yīng)的處理函數(shù)）
地址轉(zhuǎn)換機(jī)制的位置是machine/translate.cc中的translate 函數(shù)，基本流程是:通過(guò)虛擬地址得到vpn和offset，通過(guò)TLB或是 Pagetable得到vpn對(duì)應(yīng)的ppn,（否則拋出異常，在異常處理函數(shù)中做處理，但目前這部分沒(méi)有實(shí)現(xiàn)），通過(guò)ppn 和offset 得到物理地址，返回物理地址。
需要說(shuō)明的是，在處理完TLB的miss或者Pagefault 之后，不需要將PC+4，因?yàn)楫惓Ｌ幚砗瘮?shù)結(jié)束后，返回的最終位置會(huì)是OneInstruction函數(shù)的取指階段。取指失敗后，OneInstruction函數(shù)會(huì)退出，然后再用相同的PC取指。而這次就能夠TLB hit或者pagetable hit了。
machine/machine.cc 的 Machine 類模擬內(nèi)存，重要函數(shù)包括
2.Exercise2 TLB MISS 異常處理
修改code/userprog目錄下exception.cc中的ExceptionHandler函數(shù)，使得Nachos系統(tǒng)可以對(duì)TLB異常進(jìn)行處理（TLB異常時(shí)，Nachos系統(tǒng)會(huì)拋出PageFaultException，詳見(jiàn)code/machine/machine.cc）
1、設(shè)計(jì)思路
首先Translate()方法,啟動(dòng)TLB，讓用戶程序在運(yùn)行的時(shí)候先訪問(wèn) TLB,如果出現(xiàn) TLB MISS,會(huì)立刻拋出一個(gè) RaiseException(),然后通過(guò) ExceptionHandler()處理這個(gè)缺頁(yè)異常,處理的動(dòng)作就是讓系統(tǒng)從pageTable 頁(yè)表中查找要找的頁(yè)表項(xiàng)。
2、userprog/Makefile
我們需要使用TLB，但是TLB并沒(méi)有啟用（在Exercise1里面解釋過(guò)），所以我們需要先在userprog/Makefile添加宏。
然后在machine/machine.h中對(duì)USE_TLB進(jìn)行宏定義，只有這樣宏才能真正起作用。
3、machine/translate.cc
因?yàn)橄到y(tǒng)是默認(rèn)沒(méi)有啟用TLB的，但是我們現(xiàn)在啟用了TLB，所以我們應(yīng)該注釋掉ASSERT(tlb == NULL || pageTable == NULL); ,否則會(huì)報(bào)錯(cuò)Assertion failed: line 203, file “…/machine/translate.cc”
4、userprog/exception.cc
修改ExceptionHandler函數(shù)，因?yàn)橹跋到y(tǒng)是沒(méi)有PageFaultException異常的（因?yàn)橹跋到y(tǒng)默認(rèn)是把物理頁(yè)面全部裝入內(nèi)存的，也沒(méi)有啟用TLB所以不會(huì)出現(xiàn)PageFaultException），所以我們需要添加PageFaultException，并進(jìn)行處理。
else if(which == PageFaultException){//發(fā)生缺頁(yè)中斷則讓TLBMissCount++TLBMissCount++;if(machine->tlb == NULL){//頁(yè)表失效，因?yàn)槟J(rèn)不會(huì)出現(xiàn)所以直接用ASSERT（FALSE）；ASSERT(FALSE);}else{//快表失效，處理流程首先調(diào)用machine的ReadRegister函數(shù)，從BadVAddrReg寄存器中取出發(fā)生異常的虛擬地址，并算出vpn//DEBUG('m',"=> TLB miss (no TLB entry)\n");int BadVAddr = machine->ReadRegister(BadVAddrReg);TLBMissHandler(BadVAddr);//TLBAlgoFIFO(BadVAddr); //FIFO算法測(cè)試//TLBAlgoClock(BadVAddr); //CLOCK時(shí)鐘算法測(cè)試}} int position = 0; void TLBMissHandler(int virtAddr) //頁(yè)表失效處理函數(shù) {unsigned int vpn;vpn = (unsigned) virtAddr / PageSize;TranslationEntry page = machine->pageTable[vpn];if(!page.valid){DEBUG('m',"\t=> Page miss\n");page = PageFaultHandler(vpn);}TLBAlgoClock(virtAddr); //處理快表失效 }5、測(cè)試結(jié)果
Exercise 3 置換算法
為TLB機(jī)制實(shí)現(xiàn)至少兩種置換算法，通過(guò)比較不同算法的置換次數(shù)可比較算法的優(yōu)劣。
1、FIFO算法
算法的思想是每次淘汰最先進(jìn)入TLB的頁(yè)面。具體實(shí)現(xiàn)方式則是每次移除塊表數(shù)組的第一項(xiàng)，然后一次將后面的往前移，新的表項(xiàng)放在快表數(shù)組的尾項(xiàng)。
userprog/exception.cc
2、CLOCK時(shí)鐘置換算法
Nachos系統(tǒng)已經(jīng)定義了TLB的use和valid，所以我們可以很方便的實(shí)現(xiàn)時(shí)鐘算法。具體實(shí)現(xiàn)是首先判斷valid的值，看該位置是否被訪問(wèn)過(guò)，如果為false則直接進(jìn)行替換；如果為true，則進(jìn)一步判斷use的值，來(lái)看是否被修改過(guò)，如果修改過(guò)則將其值置為false，然后判斷下一位。如果為use為false則直接進(jìn)行替換。
void TLBAlgoClock(int virtAddr) {unsigned int vpn;vpn = (unsigned) virtAddr / PageSize;while(1){position3 %= TLBSize;if(machine->tlb[position3].valid == FALSE){break;}else{if(machine->tlb[position3].use){//更新use的值machine->tlb[position3].use = FALSE;position3++;}else{break;}}}machine->tlb[position3] = machine->pageTable[vpn];machine->tlb[position3].use = TRUE; }3、測(cè)試兩個(gè)算法，并打印出TLB相關(guān)信息
首先在translate.cc中設(shè)置兩個(gè)全局變量， TLBMissCount = 0;(記錄TLB MISS)；TranslateCount = 0(記錄進(jìn)程頁(yè)面訪問(wèn)次數(shù))。并在machine.h中進(jìn)行擴(kuò)展聲明。然后在每次發(fā)生PageFaultException讓TLBMissCount+1；在每次執(zhí)行TranslateCount函數(shù)時(shí)，讓TranslateCount+1。分別調(diào)用兩個(gè)算法最終在程序執(zhí)行結(jié)束退出后調(diào)用debug函數(shù)打印出TLB缺頁(yè)次數(shù)，缺頁(yè)率等信息。
4、測(cè)試結(jié)果
測(cè)試說(shuō)明：我試用了系統(tǒng)提供的sort排序進(jìn)行測(cè)試，在最開(kāi)始的時(shí)候報(bào)錯(cuò)Assertion failed: line 81, file "…/userprog/addrspace.cc，仔細(xì)閱讀代碼發(fā)現(xiàn)是因?yàn)橄到y(tǒng)給的sort排序超出了內(nèi)存限制，同時(shí)原來(lái)sort在最后接觸進(jìn)行的系統(tǒng)調(diào)用EXIT 尚未在本系統(tǒng)中實(shí)現(xiàn)，所以我在原來(lái)的基礎(chǔ)上進(jìn)行了修改，并重新make。
#include "syscall.h"int A[20]; /* size of physical memory; with code, we'll run out of space!*/int main() {int i, j, tmp;/* first initialize the array, in reverse sorted order */for (i = 0; i < 20; i++) A[i] = 20 - i;/* then sort! */for (i = 0; i < 19; i++)for (j = i; j < (19 - i); j++)if (A[j] > A[j + 1]) { /* out of order -> need to swap ! */tmp = A[j];A[j] = A[j + 1];A[j + 1] = tmp;}//Exit(A[0]); /* and then we're done -- should be 0! */Halt(); }我將原來(lái)的數(shù)組縮小為20，同時(shí)結(jié)束之后進(jìn)行halt系統(tǒng)調(diào)用.
FIFO算法測(cè)試結(jié)果:
CLOCK 時(shí)鐘算法測(cè)試結(jié)果:
對(duì)比之后發(fā)現(xiàn),時(shí)鐘算法的效率明顯優(yōu)于FIFO算法。
分頁(yè)式內(nèi)存管理
目前Nachos系統(tǒng)中，類Class Thread的成員變量AddrSpace* space中使用TranslationEntry* pageTable來(lái)管理內(nèi)存。應(yīng)用程序的啟動(dòng)過(guò)程中，對(duì)其進(jìn)行初始化；而在線程的切換過(guò)程中，亦會(huì)對(duì)該變量進(jìn)行保存和恢復(fù)的操作（使得類Class Machine中定義的Class Machine::TranslationEntry* pageTable始終指向當(dāng)前正在運(yùn)行的線程的頁(yè)表）。
Exercise 4 內(nèi)存全局管理數(shù)據(jù)結(jié)構(gòu)
設(shè)計(jì)并實(shí)現(xiàn)一個(gè)全局性的數(shù)據(jù)結(jié)構(gòu)（如空閑鏈表、位圖等）來(lái)進(jìn)行內(nèi)存的分配和回收，并記錄當(dāng)前內(nèi)存的使用狀態(tài)。
1、基本思路
這里我選擇使用位圖(bitMap)來(lái)管理空閑的內(nèi)存。在machine類中增加成員變量bitmap，類型為數(shù)組。因?yàn)镹achos系統(tǒng)擁有32位的物理頁(yè)面，所以設(shè)置了一個(gè)大小為32的數(shù)組，初始值都為0，分配之后設(shè)置為1。每次申請(qǐng)物理內(nèi)存的時(shí)候調(diào)用allocateMemory函數(shù)來(lái)尋找一塊空閑的頁(yè)面 ，如果沒(méi)有空閑的頁(yè)面則返回-1。freeMemory函數(shù)則是負(fù)責(zé)回收內(nèi)存的。具體就是將當(dāng)前頁(yè)表對(duì)應(yīng)的所有位圖位置設(shè)為0。
2、machine/machine.h
unsigned int bitmap[32];int allocateMemory(void);void freeMemory(void);3、machine/machine.cc
實(shí)現(xiàn)上述函數(shù)
int Machine::allocateMemory() {for(int i=0;i<32;i++){if(bitmap[i]==0){bitmap[i]=1;printf("allocate memory %d\n",i);return i;}}return -1; }void Machine::freeMemory(void) {for(int i=0;i<NumPhysPages;i++){//int current=pageTable[i].physicalPage;if(pageTable[i].threadId == currentThread->getTid()){if(bitmap[i]==1){printf("free Memory %d\n",i);bitmap[i]=0;}}} }4、添加內(nèi)存分配回收機(jī)制
分配內(nèi)存的allocateMemory函數(shù)主要是在內(nèi)存初始化的時(shí)候調(diào)用的,主要通過(guò)修改userprog/addrspace.cc文件。而內(nèi)存的回收則是在程序結(jié)束之后通過(guò)Exit進(jìn)行調(diào)用，而系統(tǒng)還未實(shí)現(xiàn)Exit系統(tǒng)調(diào)用，所以在這個(gè)部分我們還需要實(shí)現(xiàn)Exit，具體實(shí)現(xiàn)是修改userprog/exception.cc文件。
addrspace.cc
5、測(cè)試結(jié)果
為了方便截圖，我們直接運(yùn)行一個(gè)空的程序，將原有的halt.c進(jìn)行修改，注釋掉Halt()(后面的測(cè)試基本上都使用修改后的halt.c文件進(jìn)行測(cè)試)。
Exercise 5 多線程支持
1、基本思想
目前因?yàn)橄到y(tǒng)的內(nèi)存中同時(shí)只能存在一個(gè)線程，所以規(guī)定系統(tǒng)將程序的內(nèi)容調(diào)入內(nèi)存時(shí)是根據(jù)虛擬地址來(lái)確定的，并且規(guī)定了這個(gè)虛擬地址和物理地址相同?；谏弦粋€(gè)exercise修改之后，我們將實(shí)現(xiàn)掉入內(nèi)存的位置根據(jù)物理地址來(lái)確定。同時(shí)之前在程序退出之后因?yàn)槟J(rèn)系統(tǒng)同時(shí)只存在一個(gè)線程，所以系統(tǒng)就運(yùn)行結(jié)束了，現(xiàn)在我們因?yàn)橛卸鄠€(gè)線程，所以在程序結(jié)束之后我們需要切換到下一個(gè)程序。
2、實(shí)現(xiàn)程序運(yùn)行結(jié)束之后切換
//exception.cc中的ExceptionHandler(ExceptionType which)函數(shù)中做的修改 else if(which == PageFaultException){//發(fā)生缺頁(yè)中斷則讓TLBMissCount++TLBMissCount++;if(machine->tlb == NULL){//頁(yè)表失效，因?yàn)槟J(rèn)不會(huì)出現(xiàn)所以直接用ASSERT（FALSE）；ASSERT(FALSE);}else{//快表失效，處理流程首先調(diào)用machine的ReadRegister函數(shù)，從BadVAddrReg寄存器中取出發(fā)生異常的虛擬地址，并算出vpn//DEBUG('m',"=> TLB miss (no TLB entry)\n");int BadVAddr = machine->ReadRegister(BadVAddrReg);TLBMissHandler(BadVAddr);//TLBAlgoFIFO(BadVAddr); //FIFO算法測(cè)試//TLBAlgoClock(BadVAddr); //CLOCK時(shí)鐘算法測(cè)試}}3、修改地址空間的上下文交換
在進(jìn)上下文交換的時(shí)候因?yàn)榍袚Q了程序，所以TLB原有的內(nèi)容則失效了，所以我們應(yīng)該清楚TLB的內(nèi)容，否則會(huì)頻繁出現(xiàn)頁(yè)面替換，降低效率。
void AddrSpace::SaveState() {for(int i=0;i<TLBSize;i++){machine->tlb[i].valid = FALSE;} }4、測(cè)試函數(shù)
Nachos執(zhí)行用戶程序的函數(shù)入口是通過(guò)StartProcess函數(shù)，但是這個(gè)函數(shù)只能執(zhí)行一個(gè)用戶程序。因此我們仿照StartProcess的思想，重新構(gòu)造了一個(gè)新的函數(shù)入口StartTwoThread用于執(zhí)行兩個(gè)程序。同時(shí)為了方便，我們將兩個(gè)線程載入同一個(gè)程序（就是之前的halt.c)。
Thread* CreateSingleThread(OpenFile *executable,int number) {printf("Creating user program thread %d\n",number);char ThreadName[20];sprintf(ThreadName,"User program %d",number);Thread *thread = new Thread(strdup(ThreadName),0);//注意這里設(shè)置的新線程的優(yōu)先級(jí)必須高于main的優(yōu)先級(jí)，否則線程不能主動(dòng)放棄處理機(jī)需要手動(dòng)實(shí)現(xiàn)AddrSpace *space;space = new AddrSpace(executable);thread->space = space;return thread; } void UserProgThread(int number) {printf("Running user program thread %d\n",number);currentThread->space->InitRegisters();currentThread->space->RestoreState();currentThread->space->PrintState();machine->Run();ASSERT(FALSE); } void StartTwoThread(char *filename) {OpenFile *executable = fileSystem->Open(filename);if(executable == NULL){printf("Unable to open file %s\n",filename);return ;}//CreateSingleThread函數(shù)主要實(shí)現(xiàn)了原來(lái)StartProcess函數(shù)的//space = new AddrSpace(executable,5);和//currentThread->space = space;部分Thread *thread1 = CreateSingleThread(executable,1);Thread *thread2 = CreateSingleThread(executable,2);delete executable;//UserProgThread函數(shù)的目的是進(jìn)行相關(guān)寄存器的初始化以及加載頁(yè)表thread1->Fork(UserProgThread,1);thread2->Fork(UserProgThread,2); }實(shí)現(xiàn)一個(gè)在類AddrSpace中實(shí)現(xiàn)一個(gè)PrintState函數(shù)，打印出Address Space的相關(guān)信息。
void AddrSpace::PrintState() {printf("=== %s ===\n","Address Space Information");printf("numPages = %d\n",numPages);printf("VPN\tPPN\tvalid\tR0\tuse\tdirty\n");for(int i=0;i<numPages;i++){printf("%d\t",pageTable[i].virtualPage);printf("%d\t",pageTable[i].physicalPage);printf("%d\t",pageTable[i].valid);printf("%d\t",pageTable[i].use);printf("%d\t",pageTable[i].dirty);printf("%d\t",pageTable[i].readOnly);printf("\n");}printf("========================================\n"); }5、修改main函數(shù)
原來(lái)的程序執(zhí)行函數(shù)入口通過(guò)-x調(diào)用StartProcess,但是現(xiàn)在我們修改了程序入口，所以我們應(yīng)該新增參數(shù)-X調(diào)用StartTwoThread
#ifdef USER_PROGRAMif (!strcmp(*argv, "-x")) { // run a user programASSERT(argc > 1);StartTwoThread(*(argv + 1));argCount = 2;} else if (!strcmp(*argv, "-c")) { // test the consoleif (argc == 1)ConsoleTest(NULL, NULL);else {ASSERT(argc > 2);ConsoleTest(*(argv + 1), *(argv + 2));argCount = 3;}interrupt->Halt(); // once we start the console, then // Nachos will loop forever waiting // for console input} #endif // USER_PROGRAM6、測(cè)試結(jié)果
由于Exercise6和Exercise7是密切關(guān)聯(lián)的，所以我把兩個(gè)實(shí)驗(yàn)放在一起寫(xiě)。
Exercise 6 缺頁(yè)中斷處理
基于TLB機(jī)制的異常處理和頁(yè)面替換算法的實(shí)踐，實(shí)現(xiàn)缺頁(yè)中斷處理（注意！TLB機(jī)制的異常處理是將內(nèi)存中已有的頁(yè)面調(diào)入TLB，而此處的缺頁(yè)中斷處理則是從磁盤(pán)中調(diào)入新的頁(yè)面到內(nèi)存）、頁(yè)面替換算法等。
Exercise 7 lazy-loading
我們已經(jīng)知道，Nachos系統(tǒng)為用戶程序分配內(nèi)存必須在用戶程序載入內(nèi)存時(shí)一次性完成，故此，系統(tǒng)能夠運(yùn)行的用戶程序的大小被嚴(yán)格限制在4KB以下。請(qǐng)實(shí)現(xiàn)Lazy-loading的內(nèi)存分配算法，使得當(dāng)且僅當(dāng)程序運(yùn)行過(guò)程中缺頁(yè)中斷發(fā)生時(shí)，才會(huì)將所需的頁(yè)面從磁盤(pán)調(diào)入內(nèi)存。
1、基本思想
Exercise 6缺頁(yè)中斷處理的思想是將發(fā)生缺頁(yè)中斷的虛擬頁(yè)面從磁盤(pán)調(diào)入物理頁(yè)面，也就是虛擬內(nèi)存的概念，在這里的虛擬內(nèi)存通過(guò)filesystem創(chuàng)建了一個(gè)virtual_memory模擬。當(dāng)發(fā)生PageFaultException時(shí)（分為兩種情況，頁(yè)表失效和快表失效）通過(guò)ExceptionHandler函數(shù)處理，前面實(shí)現(xiàn)了快表失效，在這里需要實(shí)現(xiàn)頁(yè)表失效處理。而之前Nachos系統(tǒng)本身是不會(huì)發(fā)生缺頁(yè)中斷的，因?yàn)橄到y(tǒng)直接將程序一次性裝載進(jìn)入內(nèi)存 ，所以不存在頁(yè)表失效，這就需要結(jié)合Exercise 7 的內(nèi)存分配機(jī)制Lazy-loading才可能發(fā)生頁(yè)表失效。
對(duì)于Lazy-loading即按需請(qǐng)求調(diào)頁(yè)而不是一次性全部裝載，這就需要修改Addspace的構(gòu)造函數(shù)，將用戶程序的內(nèi)容先裝載到虛擬內(nèi)存，等需要的時(shí)候再?gòu)膙irtual_memory中調(diào)入。
2、創(chuàng)建虛擬內(nèi)存
在基本思想中已經(jīng)描述過(guò)，通過(guò)fileSystem創(chuàng)建一個(gè)virtual_memory文件來(lái)模擬虛擬內(nèi)存，同時(shí)將數(shù)據(jù)裝載到virtual_memory中。為了盡可能的使每個(gè)實(shí)驗(yàn)代碼能夠運(yùn)行，我這里重構(gòu)了addspace的構(gòu)造函數(shù)，首先在addspace.h中聲明新的構(gòu)造函數(shù)。
AddrSpace(OpenFile *executable); // Create an address space,// initializing it with the program// stored in the file "executable"AddrSpace(OpenFile *executable,int lab); //虛擬內(nèi)存實(shí)驗(yàn)所重構(gòu)的構(gòu)造函數(shù),lab參數(shù)沒(méi)有意義~AddrSpace(); // De-allocate an address space AddrSpace::AddrSpace(OpenFile *executable,int lab) {NoffHeader noffH;unsigned int i, size;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; // we need to increase the size// to leave room for the stacknumPages = divRoundUp(size, PageSize);size = numPages * PageSize;//上面的內(nèi)容與原來(lái)的一樣//用filesystem創(chuàng)建VirtualMemory文件，運(yùn)行nachos之后，會(huì)在userprog目錄下面生成該文件bool success_create_vm = fileSystem->Create("VirtualMemory",size);ASSERT(numPages <= NumPhysPages);//pageTable = new TranslationEntry[numPages];for(i=0;i<numPages;i++){machine->pageTable[i].virtualPage = i;machine->pageTable[i].physicalPage = machine->allocateMemory(); //因?yàn)槲覀儧](méi)有將用戶程序內(nèi)容裝載進(jìn)內(nèi)存，所以physicalPage的值可以為0machine->pageTable[i].valid = TRUE; //表示沒(méi)有從磁盤(pán)裝載任何頁(yè)面進(jìn)內(nèi)存machine->pageTable[i].use = FALSE;machine->pageTable[i].dirty = FALSE;machine->pageTable[i].readOnly = FALSE;machine->pageTable[i].threadId = currentThread->getTid();}//初始化整個(gè)物理內(nèi)存bzero(machine->mainMemory,MemorySize);OpenFile *vm = fileSystem->Open("VirtualMemory");char *virtualMemory_temp;virtualMemory_temp = new char[size]; //該數(shù)組主要是用于將用戶程序的內(nèi)容寫(xiě)入磁盤(pán)的中間過(guò)度for(i=0;i<size;i++)virtualMemory_temp[i] = 0;if(noffH.code.size>0){DEBUG('a',"\tCopying code segment, at 0x%x, size %d\n",noffH.code.virtualAddr,noffH.code.size);executable->ReadAt(&(virtualMemory_temp[noffH.code.virtualAddr]),noffH.code.size,noffH.code.inFileAddr);vm->WriteAt(&(virtualMemory_temp[noffH.code.virtualAddr]),noffH.code.size,noffH.code.virtualAddr*PageSize);}if(noffH.initData.size >0){DEBUG('a',"\tCopying data segment, at 0x%x, size %d\n",noffH.initData.virtualAddr,noffH.initData.size);executable->ReadAt(&(virtualMemory_temp[noffH.initData.virtualAddr]),noffH.initData.size,noffH.initData.inFileAddr);vm->WriteAt(&(virtualMemory_temp[noffH.initData.virtualAddr]),noffH.initData.size,noffH.initData.virtualAddr*PageSize);}//上面的內(nèi)容仿照原始的addspace構(gòu)造函數(shù)編寫(xiě)delete vm; }3、缺頁(yè)處理
當(dāng)發(fā)生缺頁(yè)異常時(shí)，通過(guò)ExceptionHandler函數(shù)調(diào)用TLBMissHandler函數(shù)，TLBMissHandler將將缺頁(yè)異常的地址裝換成虛擬地址，然后調(diào)用PageFaultHandler函數(shù)，該函數(shù)首先通過(guò)machine->allocateMemory()尋找一個(gè)空閑頁(yè)，如果返回-1則調(diào)用NaivePageReplacement函數(shù)，該函數(shù)的作用是進(jìn)行頁(yè)面替換。首先尋找一個(gè)未被修改過(guò)的頁(yè)面進(jìn)行替換，如果找到則結(jié)束；否則將第一個(gè)(1,1)的頁(yè)面進(jìn)行替換，并將頁(yè)表內(nèi)容寫(xiě)會(huì)磁盤(pán)。
int NaivePageReplacement(int vpn) {int pageFrame = -1;for(int temp_vpn = 0;temp_vpn < machine->pageTableSize,temp_vpn != vpn;temp_vpn++){if(machine->pageTable[temp_vpn].valid){if(!machine->pageTable[temp_vpn].dirty){pageFrame = machine->pageTable[temp_vpn].physicalPage;break;}}}if(pageFrame == -1){for(int replaced_vpn = 0; replaced_vpn < machine->pageTableSize, replaced_vpn != vpn;replaced_vpn++){if(machine->pageTable[replaced_vpn].valid){machine->pageTable[replaced_vpn].valid = FALSE;pageFrame = machine->pageTable[replaced_vpn].physicalPage;//將頁(yè)表寫(xiě)回磁盤(pán)OpenFile *vm = fileSystem->Open("VirtualMemory");vm->WriteAt(&(machine->mainMemory[pageFrame*PageSize]),PageSize,replaced_vpn*PageSize);delete vm;break;}}}return pageFrame; } TranslationEntry PageFaultHandler(int vpn) {int pageFrame = machine->allocateMemory();if(pageFrame == -1){pageFrame == NaivePageReplacement(vpn);}machine->pageTable[vpn].physicalPage = pageFrame;OpenFile *vm = fileSystem->Open("VirtualMemory");vm->ReadAt(&(machine->mainMemory[pageFrame*PageSize]),PageSize,vpn*PageSize);delete vm;machine->pageTable[vpn].valid = TRUE;machine->pageTable[vpn].use = FALSE;machine->pageTable[vpn].dirty = FALSE;machine->pageTable[vpn].readOnly = FALSE;currentThread->space->PrintState(); //打印地址空間信息 } int position = 0; void TLBMissHandler(int virtAddr) //頁(yè)表失效處理函數(shù) {unsigned int vpn;vpn = (unsigned) virtAddr / PageSize;TranslationEntry page = machine->pageTable[vpn];if(!page.valid){DEBUG('m',"\t=> Page miss\n");page = PageFaultHandler(vpn);}TLBAlgoClock(virtAddr); //處理快表失效 } void ExceptionHandler(ExceptionType which) {int type = machine->ReadRegister(2);if ((which == SyscallException)) {if((type == SC_Halt)){DEBUG('T', "TLB Miss: %d, TLB Hit: %d, Total Translate: %d, TLB Miss Rate: %.2lf%%\n",TLBMissCount,TranslateCount-TLBMissCount,TranslateCount,(double)(TLBMissCount*100)/(TranslateCount));interrupt->Halt();}else if(type == SC_Exit){printf("program exit\n");if(currentThread->space != NULL){machine->freeMemory();delete currentThread->space;currentThread->space = NULL;currentThread->Finish();int nextPc=machine->ReadRegister(NextPCReg);machine->WriteRegister(PCReg,nextPc);}}}else if(which == PageFaultException){//發(fā)生缺頁(yè)中斷則讓TLBMissCount++TLBMissCount++;if(machine->tlb == NULL){//頁(yè)表失效，因?yàn)槟J(rèn)不會(huì)出現(xiàn)所以直接用ASSERT（FALSE）；ASSERT(FALSE);}else{//快表失效，處理流程首先調(diào)用machine的ReadRegister函數(shù)，從BadVAddrReg寄存器中取出發(fā)生異常的虛擬地址，并算出vpn//DEBUG('m',"=> TLB miss (no TLB entry)\n");int BadVAddr = machine->ReadRegister(BadVAddrReg);TLBMissHandler(BadVAddr);//TLBAlgoFIFO(BadVAddr); //FIFO算法測(cè)試//TLBAlgoClock(BadVAddr); //CLOCK時(shí)鐘算法測(cè)試}} else {printf("Unexpected user mode exception %d %d\n", which, type);ASSERT(FALSE);} }4、測(cè)試結(jié)果
Challenge2 多線程實(shí)現(xiàn)基本思路：
前面實(shí)現(xiàn)的倒排頁(yè)表并不是嚴(yán)格意思的倒排頁(yè)表，實(shí)際上，倒排頁(yè)表與進(jìn)程/線程數(shù)量無(wú)關(guān)，所以，我們需要在 machine 類維護(hù)倒排頁(yè)表，而不是在 addrspace類維護(hù)倒排頁(yè)表。
考慮到多線程共用倒排頁(yè)表的實(shí)際情況，我們需要在頁(yè)表項(xiàng)記錄線程 ID
在mahine/machine.cc 的machine 類的構(gòu)造函數(shù)完成倒排頁(yè)表的初始化
#ifdef USE_TLBpageTable = new TranslationEntry[NumPhysPages];//初始化倒排頁(yè)表for (i = 0; i < NumPhysPages; i++)pageTable[i].physicalPage = i;pageTable[i].virtualPage = i;pageTable[i].valid = FALSE;pageTable[i].use= FALSE;pageTable[i].dirty = FALSE;pageTable[i].readOnly = FALSE;pageTable[i].threadId = -1; #else // use linear page tabletlb = NULL;pageTable = NULL; #endif考慮到所有線程共用相同倒排頁(yè)表，不需要從線程內(nèi)存空間載入頁(yè)表,這樣的修改同時(shí)意味著我們?cè)赼ddrspace 定義的頁(yè)表失去了作用
void AddrSpace::RestoreState() {// machine->pageTable = pageTable;//machine->pageTableSize = numPages; } //由于引入了線程ID，在表項(xiàng)判斷時(shí)增加判斷內(nèi)容 pageTable[i].threadID == currentThread->getThreadID() //在表項(xiàng)修改時(shí)增加修改內(nèi)容 machine->pageTable[pos].threadID = currentThread->getThreadID();同時(shí)改寫(xiě)釋放空間函數(shù)，根據(jù)線程ID 釋放相關(guān)空間
void Machine::freeMemory(void) {for(int i=0;i<NumPhysPages;i++){//int current=pageTable[i].physicalPage;if(pageTable[i].threadId == currentThread->getTid()){if(bitmap[i]==1){printf("free Memory %d\n",i);bitmap[i]=0;}}} }測(cè)試結(jié)果：
內(nèi)容三：遇到的困難及解決方法
困難 1：理解#ifdef
根據(jù)nachos 的默認(rèn)設(shè)置，TLB 沒(méi)有開(kāi)啟，查看相關(guān)代碼發(fā)現(xiàn)#ifdef 相關(guān)命令，查詢相關(guān)資料得知，#ifdef 是條件編譯的重要命令，所謂條件編譯，就是對(duì)程序中的部分內(nèi)容只在滿足特定條件的情況下進(jìn)行編譯，條件編譯包括許多指令，其中#ifdef 的常見(jiàn)形式為：
#ifdef 標(biāo)識(shí)符
//程序段 1
#else
//程序段 2
#endif
這段語(yǔ)句的作用是當(dāng)標(biāo)識(shí)符已經(jīng)被定義過(guò)(一般是用#define 命令定義)，則對(duì)程序段1 進(jìn)行編譯，否則編譯程序段2。進(jìn)一步查詢相關(guān)資料，得知我們需要修改userprog/Makefile，開(kāi)啟 USE_TLB
DEFINES = … -DUSE_TLB
困難2：理解nachos文件系統(tǒng)
如果希望利用文件而不是內(nèi)存的額外空間實(shí)現(xiàn) Exercise6和 Exercise7,那么需要涉及 nahcos 文件系統(tǒng)。主要涉及的部分包括文件系統(tǒng)數(shù)據(jù)結(jié)構(gòu)FileSystem和打開(kāi)文件數(shù)據(jù)結(jié)構(gòu)Openfile。
文件系統(tǒng)數(shù)據(jù)結(jié)構(gòu)FileSystem 的重要函數(shù)包括
Create函數(shù)：基本功能是文件系統(tǒng)中創(chuàng)建固定大小的文件，如果創(chuàng)建成功，那么返回TRUE，否則返回 FALSE
Open函數(shù)：基本功能是打開(kāi)已經(jīng)存在的文件，返回的是打開(kāi)文件數(shù)據(jù)結(jié)構(gòu)
Remove函數(shù)：基本功能是刪除已經(jīng)存在的文件，如果刪除成功，那么返回TRUE，否則返回FALSE
需要說(shuō)明的是，如果我們希望關(guān)閉已經(jīng)打開(kāi)的文件，那么需要調(diào)用相應(yīng)打開(kāi)文件數(shù)據(jù)結(jié)構(gòu)的析構(gòu)函數(shù)
打開(kāi)文件數(shù)據(jù)結(jié)構(gòu)Openfile 的重要函數(shù)包括
Length函數(shù)：基本功能是返回文件長(zhǎng)度
Seek函數(shù)：基本功能是移動(dòng)當(dāng)前文件位置指針
ReadAt函數(shù)：基本功能是從文件特定位置讀取特定長(zhǎng)度的數(shù)據(jù)到特定位置，返回值是實(shí)際讀出的字節(jié)數(shù)
WriteAt函數(shù)：基本功能是從特定位置向文件特定位置寫(xiě)入特定長(zhǎng)度的數(shù)據(jù)，返回值是實(shí)際寫(xiě)入的字節(jié)數(shù)
Read函數(shù)：基本功能是從文件讀取特定長(zhǎng)度的數(shù)據(jù)到特定位置，返回值是實(shí)際讀出的字節(jié)數(shù)，基于ReadAt 函數(shù)實(shí)現(xiàn)
Write函數(shù)：基本功能是從特定位置向文件寫(xiě)入特定長(zhǎng)度的數(shù)據(jù)，返回值是實(shí)際寫(xiě)入的字節(jié)數(shù)，基于WriteAt 函數(shù)實(shí)現(xiàn)
困難3 理解DEBUG
對(duì)DEBUG函數(shù)不熟悉，剛開(kāi)始在對(duì)程序進(jìn)行調(diào)試的時(shí)候總是使用printf函數(shù)，然而nachos系統(tǒng)定義的DEBUG函數(shù)功能更加強(qiáng)大。
內(nèi)容四：收獲及感想
實(shí)習(xí)課程和理論課程相得益彰。通過(guò)本次實(shí)習(xí)，我強(qiáng)化了對(duì)存儲(chǔ)模型相關(guān)知識(shí)的理解，鍛煉了編程能力。經(jīng)過(guò)一段時(shí)間的接觸，感覺(jué)對(duì) nachos 系統(tǒng)有了一定的了解，對(duì)課程有了一定的興趣，期待在以后的實(shí)習(xí)中能夠了解nachos 更多的功能并且在此基礎(chǔ)上進(jìn)行更多的修改。
內(nèi)容五：對(duì)課程的意見(jiàn)和建議
我覺(jué)得課程方式很好，老師講課非常認(rèn)真，對(duì)同學(xué)們也很寬容，布置給我們的實(shí)驗(yàn)雖然讓我們?cè)谧龅倪^(guò)程中一直懷疑人生，但是在實(shí)驗(yàn)完成之后回想整個(gè)過(guò)程，我們獲得的提高非常巨大！由于實(shí)驗(yàn)逐漸變難，所以在實(shí)驗(yàn)過(guò)程中大家出現(xiàn)了很多分歧，也無(wú)法確定誰(shuí)的想法是正確的，希望老師能在課上對(duì)實(shí)驗(yàn)進(jìn)行一定的梳理。
總結(jié)
以上是生活随笔為你收集整理的nachos-虚拟内存管理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： Android recycleview使
- 下一篇： Android Studio如何导出可供