當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

Nachos Lab2 虚拟内存

發(fā)布時間：2023/12/10 编程问答 35 豆豆

生活随笔收集整理的這篇文章主要介紹了 Nachos Lab2 虚拟内存小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

Lab2 虛擬內(nèi)存

任務(wù)完成情況

ExerciseY/N

Exercise1	Y
Exercise2	Y
Exercise3	Y
Exercise4	Y
Exercise5	Y
Exercise6	Y
Exercise7	Y
*challenge	Y

Exercise 1 源代碼閱讀

一些值得注意的細(xì)節(jié)

如果要讓Nachos運(yùn)行用戶程序，需要在MakeFile中添加-DUSER_PROGRAM。之后，一切的#ifdef USER_PROGRAM范圍內(nèi)的內(nèi)容都會被編譯。system.cc中初始化了一個Machine類型的對象machine，作為Nachos的模擬硬件系統(tǒng)，用來執(zhí)行用戶的程序。Nachos機(jī)器模擬的核心部分是內(nèi)存和寄存器的模擬。

nachos寄存器模擬了MIPS機(jī)(R2/3000)的全部的32個寄存器，此外還包括8個用于調(diào)試的寄存器。一些特殊寄存器描述如下表：

寄存器名編號描述

StackReg	29	進(jìn)程棧頂指針
RetAddrReg	31	存放返回地址
HiReg	32	存放乘法結(jié)果高32位
LoReg	33	存放乘法結(jié)果低32位
PCReg	34	存放當(dāng)前指令的地址
NextPCReg	35	存放下一條執(zhí)行指令的地址
PrevPCReg	36	存放上一條執(zhí)行指令的地址
LoadReg	37	存放延遲載入的寄存器編號
LoadValueReg	38	存放延遲載入的值
BadAddReg	39	發(fā)生Exception(異常或syscall)時用戶程序邏輯地址

Nachos 用宿主機(jī)的一塊內(nèi)存模擬自己的內(nèi)存。由于 Nachos 是一個教學(xué)操作系統(tǒng)，在內(nèi)存分配上和實(shí)際的操作系統(tǒng)是有區(qū)別的，且作了很大幅度的簡化。

Nachos中每個內(nèi)存頁的大小同磁盤扇區(qū)的大小相同，而整個內(nèi)存的大小遠(yuǎn)遠(yuǎn)小于模擬磁盤的大小，僅為32 * 128 = 4KB。事實(shí)上，Nachos 的內(nèi)存只有當(dāng)需要執(zhí)行用戶程序時用戶程序的一個暫存地，而作為Nachos內(nèi)核的數(shù)據(jù)結(jié)構(gòu)并不存放在 Nachos 的模擬內(nèi)存中，而是申請 Nachos 所在宿主機(jī)的內(nèi)存。所以 Nachos 的一些重要的數(shù)據(jù)結(jié)構(gòu)如線程控制結(jié)構(gòu)等的容量可以是無限的，不受 Nachos 模擬內(nèi)存大小的限制。

參考資料《Nachos中文教程》

progtest.cc

在terminal中輸入nachos -x filename，main()將調(diào)用StartProcess(char *filename)函數(shù)，其執(zhí)行流程為：打開文件->為當(dāng)前線程分配地址空間（調(diào)用addrSpace函數(shù)，根據(jù)程序的數(shù)據(jù)段、程序段和棧的總和來分配地址空間，具體的流程為：將頭文件內(nèi)容加載到NoffHeader的結(jié)構(gòu)體中，它定義了Nachos目標(biāo)代碼的格式，并且在必要的時候進(jìn)行大小端的轉(zhuǎn)換->計(jì)算用戶程序所需內(nèi)存空間大小，并計(jì)算所需頁數(shù)->建立虛擬地址到物理地址的轉(zhuǎn)換機(jī)制（目前Nachos的地址轉(zhuǎn)換是完全對等的，即采用絕對裝入的方式，只適用于單道程序）->調(diào)用machine->mainMemory初始化物理空間，將程序的數(shù)據(jù)段和代碼段拷貝到內(nèi)存中->關(guān)閉文件->初始化寄存器(InitRegisters)->將當(dāng)前線程對應(yīng)的頁表始址和頁目錄數(shù)寫入“頁表寄存器”（在Machine中用兩個public成員變量：pageTable和pageTableSize來實(shí)現(xiàn)“頁表寄存器”的功能（即存儲currentThread的頁表始址和頁表大小)->調(diào)用machine->run函數(shù)，該函數(shù)會調(diào)用OneInstruction函數(shù)逐條執(zhí)行用戶指令，同時調(diào)用OneTick函數(shù)，讓系統(tǒng)時間前進(jìn)，直到當(dāng)前進(jìn)程執(zhí)行結(jié)束或者主動/被動讓出CPU。

machine.h(cc)

machine.h中定義了一組與Nachos模擬寄存器和內(nèi)存有關(guān)的參數(shù)，比如物理頁面大小、內(nèi)存頁面數(shù)、寄存器大小等等。枚舉了Nachos的異常類型：

異常描述

NoException	無異常
SyscallException	系統(tǒng)調(diào)用（個人意見，系統(tǒng)調(diào)用不應(yīng)該屬于異常）
PageFaultException	缺頁異常（除了頁表，使用tlb時同樣會拋出此異常）
ReadOnlyException	對只讀對象做寫操作異常
BusErrorException	地址變換結(jié)果超過物理內(nèi)存異常
AddressErrorException	地址不能對齊或者地址越界異常
OverflowException	整型數(shù)加減法結(jié)果越界異常
IllegalInstrException	非法指令異常

成員變量/函數(shù)描述

char *mainMemory;	模擬內(nèi)存，用于運(yùn)行用戶程序
int registers[NumTotalRegs];	模擬寄存器，用于運(yùn)行用戶程序
TranslationEntry *tlb;	快表，系統(tǒng)中只有一個快表
TranslationEntry *pageTable;unsigned int pageTableSize;	當(dāng)前線程的頁表起始地址和頁目錄數(shù)，相當(dāng)于執(zhí)行“頁表寄存器”的職能。注意：pageTable變量在兩個地方均有定義，一個是在thread.cc中，表示某個線程的頁表，這個pageTable可以有多個，并且與線程是一一對應(yīng)的；另一個是在machine.cc中，表示currentThread的頁表，這個pageTable只有一個，且始終指向currentThread的頁表。注意：無論是tlb還是pageTable，都不存放在模擬的mainMemory之中，而是借用宿主主機(jī)內(nèi)存存放，換言之，mainMemory只用來存放用戶程序指令、數(shù)據(jù)和棧。
Machine(bool debug)	初始化用戶程序執(zhí)行的模擬硬件環(huán)境，包括內(nèi)存，寄存器
void Run();	逐條執(zhí)行用戶程序指令
ReadRegister(int num)	讀取寄存器的值
WriteRegister(int num, int value)	將value寫入寄存器
void OneInstruction(Instruction *instr);	執(zhí)行一條用戶程序指令，其步驟為：讀取一條指令的二進(jìn)制編碼->decode()解碼->獲得對應(yīng)的操作符opCode，rs，rt和rd寄存器->根據(jù)opCode執(zhí)行相應(yīng)的運(yùn)算->更新寄存器PC，nextPC，prevPC的值，如果有異常，調(diào)用raiseException函數(shù)處理異常，然后調(diào)用異常處理程序處理異常。在Run函數(shù)中無限循環(huán)此函數(shù)直到用戶程序執(zhí)行到最后一條指令。
void DelayedLoad(int nextReg, int nextVal);	結(jié)束當(dāng)前運(yùn)行的一切東西，與mips模擬有關(guān)

translate.h(cc)

定義了頁目錄項(xiàng)，實(shí)現(xiàn)了讀寫內(nèi)存，地址轉(zhuǎn)換的功能。

變量/函數(shù)描述

int virtualPage;	邏輯地址
int physicalPage;	物理地址
bool valid;	此頁是否已在內(nèi)存
bool readOnly;	此頁是否為只讀
bool use;	此頁是否被讀或者修改過
bool dirty;	此頁是否被修改過
bool ReadMem(int addr, int size, int* value);	讀取內(nèi)存
bool WriteMem(int addr, int size, int value);	寫入內(nèi)存
ExceptionType Translate(int virtAddr, int* physAddr, int size,bool writing);	實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，其流程為：通過virtualAddr計(jì)算出vpn和offset->通過vpn來查找ppn（在tlb或頁表中查詢，否則拋出異常，調(diào)用異常處理函數(shù)，目前這部分還未實(shí)現(xiàn)）->將ppn與offset相加，得到物理地址。 Nachos中只允許tlb和頁表二選一，如果要實(shí)現(xiàn)二者并存，需要將ASSERT(tlb == NULL \|\| pageTable == NULL)和ASSERT(tlb != NULL \|\| pageTable != NULL) 注釋掉。其實(shí)現(xiàn)流程與我們之前學(xué)習(xí)的地址變換機(jī)構(gòu)相一致。

exception.cc

定義了異常處理函數(shù)ExceptionHandler，用來對相應(yīng)的異常(系統(tǒng)調(diào)用，地址越界，算數(shù)結(jié)果溢出等）做出處理。nachos對于異常或者系統(tǒng)調(diào)用的處理過程是：調(diào)用machine->raiseException函數(shù)，該函數(shù)得到異常類型和發(fā)生錯誤的虛擬地址，然后將發(fā)生錯誤的虛擬地址存入BadVAddrReg寄存器，然后調(diào)用DelayedLoad函數(shù)來結(jié)束當(dāng)前運(yùn)行中的所有東西，之后設(shè)置系統(tǒng)狀態(tài)為內(nèi)核態(tài)，然后調(diào)用ExceptionHandler函數(shù)進(jìn)行異常處理，處理完異常之后重新將系統(tǒng)設(shè)置為用戶態(tài)。

Exercise 2 TLB MISS異常處理

要使用tlb，需要在userprog/MakeFile中添加-DUSE_TLB。

DEFINES = -DUSE_TLB

Nachos是如何獲取單條指令的(重要)

在 code/machine/mipssim.cc中

Machine::Run() {...while (1) {OneInstruction(instr);...} } Machine::OneInstruction(Instruction *instr) {...// Fetch instructionif (!machine->ReadMem(registers[PCReg], 4, &raw))return; // 異常發(fā)生instr->value = raw;instr->Decode();...// 計(jì)算下一個pc的值，但是為了避免異常發(fā)生，暫時不裝載int pcAfter = registers[NextPCReg] + 4;...// 現(xiàn)在已經(jīng)成功執(zhí)行指令...// 更新PC寄存器的值，為了執(zhí)行下一條指令，PC會自增4，即PC+=4registers[PrevPCReg] = registers[PCReg]; registers[PCReg] = registers[NextPCReg];registers[NextPCReg] = pcAfter; }

如果Nachos獲取指令失敗（一般是因?yàn)镻ageFaultException），之后它并不會執(zhí)行PC+4，因?yàn)閙achine->ReadMem()會返回false。因此，我們只需要在exceptionHandler中更新tlb，這樣Nachos下一次還會執(zhí)行同一條指令并且再次嘗試地址轉(zhuǎn)換。這一知識點(diǎn)非常重要，我還會在Exercise7中提到它。

TLB miss

bool Machine::ReadMem(int addr, int size, int *value) {...exception = Translate(addr, &physicalAddress, size, FALSE);if (exception != NoException){machine->RaiseException(exception, addr);return FALSE;}... }

當(dāng)執(zhí)行code/machine/translate.cc里的 Machine::ReadMem() 或者 Machine::WriteMem()時，如果translate()返回PageFaultException，會調(diào)用Machine::RaiseException()并返回FALSE。

void Machine::RaiseException(ExceptionType which, int badVAddr) {...registers[BadVAddrReg] = badVAddr;...interrupt->setStatus(SystemMode);ExceptionHandler(which);interrupt->setStatus(UserMode); }

Machine::RaiseException()會將發(fā)生異常的虛擬地址存入BadVAddrReg，因此我們可以從BadVAddrReg中獲取發(fā)生異常的虛擬地址。最后調(diào)用exception.cc里的ExceptionHandler函數(shù)對異常進(jìn)行處理，目前它只有對Halt系統(tǒng)調(diào)用的處理。這里需要添加對TLB異常的PageFaultException處理語句:

void ExceptionHandler(ExceptionType which) {if (which = PageFaultException){ASSERT(machine->tlb);//保證tlb存在int badVAddr = machine->ReadRegister(BadVAddrReg);//獲取發(fā)生錯誤的虛擬地址TLBMissHandler(badVAddr);//調(diào)用頁面置換算法對該虛擬地址進(jìn)行處理}//syscall... }

Exercise 3 置換算法

準(zhǔn)備工作

TLB命中率

為了獲取TLB命中率，我在code/machine/machine.h中定義了tlbVisitCnt和tlbHitCnt, 并在code/machine/machine.cc中對它們初始化為0。每當(dāng)調(diào)用code/machine/translate.cc中的translate函數(shù)時tlbVisitCnt++，每當(dāng)tlb命中時，tlbHitCnt++；

ExceptionType Machine::Translate(int virtAddr, int *physAddr, int size, bool writing) {tlbVisitCnt++;//每當(dāng)調(diào)用translate函數(shù)時，tlbVisitCnt++...for (entry = NULL, i = 0; i < TLBSize; i++)if (tlb[i].valid && (tlb[i].virtualPage == vpn)){tlbHitCnt++;//每當(dāng)tlb命中時，tlbHitCnt++...}... }

自定義用戶程序

在code/test中有幾個用于測試的用戶程序，其中halt太小了，只會用到三頁，因此對任意的頁面置換算法，使用halt測試出來的結(jié)果都是一樣的；而其他幾個又太大了，裝載進(jìn)mainMemory的時候會報(bào)錯，例如matmult，但是我會在Exercise7實(shí)現(xiàn)了lazy-loading之后測試它。

//運(yùn)行matmult報(bào)錯 vagrant@precise32:/vagrant/nachos/nachos-3.4/code/userprog$ ./nachos -d a -x ../test/matmult //a 表示 address，它是Nachos自帶的debug flag，后面還會用到m，表示machine Assertion failed: line 81, file "../userprog/addrspace.cc" Aborted

所以我自己寫了一個簡單的用戶程序——計(jì)算99乘法表code/test/99table.c。

/*Author: litangDescription: 99table.c，用于簡單測試用戶程序，內(nèi)容為計(jì)算99乘法表Since: 2020/11/811:33:38 */#include "syscall.h" #define N 9int main() {int table[N][N];for (int i = 1; i <= N; ++i)for (int j = 1; j <= N; ++j)table[i - 1][j - 1] = i * j;Exit(table[N - 1][N - 1]); }

并且將下面的內(nèi)容加入 code/test/Makefile

all: ... 99table...# For Lab2: Test the TLB Hit Rate 99table.o: 99table.c$(CC) $(CFLAGS) -c 99table.c 99table: 99table.o start.o$(LD) $(LDFLAGS) start.o 99table.o -o 99table.coff../bin/coff2noff 99table.coff 99table

完成上述步驟之后，需要在Nachos3.4/code/test下重新make一遍。

不同算法的轉(zhuǎn)換

我用了一些宏來作為不同算法切換的開關(guān)

TLB_FIFO
TLB_LRU

需要注意的是：每次通過修改code/machine/Makefile中的開關(guān)來調(diào)試程序時，需要對任意代碼做一些修改，然后再改回來，否則Nachos編譯的時候無法檢測MakeFile的改動。

LRU算法

LRU（Least recently used，最近最少使用）。

用tlb來記錄最近訪問的頁
若頁在tlb中已存在，則將該頁移到tlb頭部，這樣就能保證頭部頁是最近訪問的，尾部頁是最早訪問的，當(dāng)需要置換頁的時候，直接丟棄尾部頁，然后將新頁插入頭部即可；
若頁在TLB中不存在，要分兩種情況討論：若TLB還有空位，需要先在頁表中查找該頁，且valid為True，表明此頁在內(nèi)存中存在，再將該頁插入TLB的頭部；若TLB沒有空位，需要丟棄尾部頁，然后將新頁插入TLB頭部。
Nachos默認(rèn)TLB是數(shù)組，每次插入都需要移動元素，而移動元素需要較大的時間開銷。

優(yōu)化

為了減少移動元素的時間開銷，可以在頁表項(xiàng)TranslationEntry中添加成員變量lastVisitedTime，每當(dāng)訪問某頁時，更新此成員變量為當(dāng)前的totalTicks，每次需要替換頁面時，需要遍歷整個TLB，找出lastVisitedTime最小的表項(xiàng)，替換之。此方法和原始方法相比，每次更新頁的訪問時間時，只需要更新其lastVisitedTime即可，節(jié)約了移動元素的時間，但是增加了頁表項(xiàng)的空間開銷和查找最小的lastVisitedTime頁的時間（需要遍歷整個TLB，時間復(fù)雜度O(n)）。考慮到Nachos的tlb很小，只有4，因此我在本次試驗(yàn)中將使用此方法。
用數(shù)組實(shí)現(xiàn)LRU需要多次移動元素，而使用鏈表則不需要考慮這個問題。若要使用鏈表，則需要使用雙向鏈表（為了維護(hù)rear指針，后面會說明），需要在TranslationEntry 中添加next和prior指針，還需要改動machine.cc中對于tlb數(shù)組的初始化，將數(shù)組改為鏈表。還需要一個全局變量currTLBSize來記錄當(dāng)前TLB的大小，維護(hù)front和rear指針指向TLB的鏈頭和鏈尾，每次從尾部移除元素時，rear都需要指向前一個元素，所以需要雙向鏈表。此方法和添加lastVisitedTime的方法相比，增加了一個額外的空間開銷（next/prior指針），并增加了currTLBSize/front/rear變量，空間復(fù)雜度為O(n)+O(1）~=O(n)；另一方面，由于頁面的訪問時間在鏈表中是順序排列的，最早訪問的頁就在鏈尾，查找最早訪問頁面的時間復(fù)雜度為O(1)，可以大大減少查找最早訪問頁的時間，故此方法是綜合性能最優(yōu)的。（TOBEDONE）

FIFO算法

和LRU算法相比，FIFO算法實(shí)現(xiàn)比較簡單。

維護(hù)一個FIFO隊(duì)列，按照時間順序?qū)⒏鲾?shù)據(jù)（已分配頁面）鏈接起來組成隊(duì)列，并將置換指針指向隊(duì)列的隊(duì)首。
進(jìn)行置換時，只需把置換指針?biāo)傅臄?shù)據(jù)（頁面）順次換出，并把新加入的數(shù)據(jù)插到隊(duì)尾即可。

TLBMissHandler

我的TLBMissHandler(Exercise2中曾提到過）實(shí)現(xiàn)如下：

void TLBMissHandler(int virtAddr) {unsigned int vpn = (unsigned)virtAddr / PageSize;unsigned int tlbExchangeIndex = -1;//tlb未滿，直接插入空位for (int i = 0; i < TLBSize; ++i){if (!machine->tlb[i].valid){tlbExchangeIndex = i;break;}}//tlb滿if (tlbExchangeIndex == -1){DEBUG('a', "tlb get max size.\n");#ifdef TLB_FIFOtlbExchangeIndex = TLBSize - 1;//將后n-1個元素向前挪動一個單位，并將新元素插入隊(duì)尾for (int i = 0; i < TLBSize - 1; ++i){machine->tlb[i] = machine->tlb[i + 1];} #endif#ifdef TLB_LRUunsigned int min = __INT_MAX__;//找lastVisitedTime最小的元素for (int i = 0; i < TLBSize; ++i){if (machine->tlb[i].lastVisitedTime < min){min = machine->tlb[i].lastVisitedTime;tlbExchangeIndex = i;}} #endif}machine->tlb[tlbExchangeIndex] = machine->pageTable[vpn]; //將頁表中的頁面加載到tlb中//因?yàn)閳?bào)錯了，所以pc還沒增加，所以Nachos會重新執(zhí)行一次相同的地址轉(zhuǎn)換，這次在tlb中就會命中。這點(diǎn)在Nachos如何獲取單條指令中提到過// #ifdef TLB_LRU// machine->tlb[tlbExchangeIndex].lastVisitedTime = stats->totalTicks;// #endif//注意，此時只是加載頁面，還沒訪問頁面，所以不用更新訪問時間。正確更新訪問時間的位置如下： } //更新tlb訪問時間，code/machine/translate.cc ExceptionType Machine::Translate(int virtAddr, int *physAddr, int size, bool writing) {...for (entry = NULL, i = 0; i < TLBSize; i++)if (tlb[i].valid && (tlb[i].virtualPage == vpn)){...tlb[i].lastVisitedTime = stats->totalTicks;//更新tlb的lastVisitedTime值...break;}... }

LRU vs. FIFO

FIFO算法的優(yōu)點(diǎn)在于它是最簡單，最公平的一種思想：即如果一個數(shù)據(jù)是最早進(jìn)入的，那么可以認(rèn)為在未來訪問它的概率很小。空間滿的時候，最先進(jìn)入的數(shù)據(jù)將被替換掉。

缺點(diǎn)：判斷頁面置換算法優(yōu)劣的指標(biāo)就是缺頁率。而FIFO算法的一個顯著的缺點(diǎn)是：在某些情況下，缺頁率反而會隨著分配空間的增加而增加，稱為Belady異常。產(chǎn)生Belady異常的原因是：FIFO置換算法與內(nèi)存訪問頁面的動態(tài)特性不相容，FIFO算法置換的頁面很可能是最頻繁訪問的頁面，因此FIFO算法會導(dǎo)致一些頁面頻繁地被替換，從而導(dǎo)致缺頁率增加。因此，FIFO算法逐漸被淘汰。

LRU是一種常見的緩存算法，在很多分布式系統(tǒng)（如Redis，Memcached）中均有廣泛應(yīng)用。LRU算法的思想是：如果一個數(shù)據(jù)近期被訪問過，那么可以認(rèn)為在未來訪問它的概率很大，空間滿的時候，近期沒有被訪問過的數(shù)據(jù)將被替換掉。LRU算法的優(yōu)點(diǎn)在于它和內(nèi)存訪問頁面的動態(tài)特性是相容的，是一種基于時間局部性原理的算法。因此，它的缺頁率往往會低于FIFO算法。

缺點(diǎn)：實(shí)現(xiàn)比FIFO算法復(fù)雜，并且時間開銷更多。

先用Nachos自帶的DEBUG檢查tlb在miss之后是否會進(jìn)行處理，這里用Nachos自帶的code/test/halt進(jìn)行測試即可。在terminal中輸入./nachos -d a -x ../test/halt

debug flags : ‘a(chǎn)’ – address space, ‘m’ – machine, ‘r’–rate，測試結(jié)果如下：

vagrant@precise32:/vagrant/nachos/nachos-3.4/code/userprog$ ./nachos -d a -x ../test/halt Initializing address space, num pages 10, size 1280 Initializing code segment, at 0x0, size 256 Initializing stack register to 1264 Reading VA 0x0, size 4Translate 0x0, read: *** no valid TLB entry found for this virtual page! tlb[0] has been exchanged by PageTable[0].//請關(guān)注這里 Reading VA 0x0, size 4Translate 0x0, read: phys addr = 0x0value read = 0c000034 Reading VA 0x4, size 4Translate 0x4, read: phys addr = 0x4value read = 00000000 Reading VA 0xd0, size 4Translate 0xd0, read: *** no valid TLB entry found for this virtual page! tlb[1] has been exchanged by PageTable[1].//這里 Reading VA 0xd0, size 4Translate 0xd0, read: phys addr = 0xd0value read = 27bdffe8 Reading VA 0xd4, size 4Translate 0xd4, read: phys addr = 0xd4value read = afbf0014 Writing VA 0x4ec, size 4, value 0x8Translate 0x4ec, write: *** no valid TLB entry found for this virtual page! tlb[2] has been exchanged by PageTable[9].//還有這里 Reading VA 0xd4, size 4Translate 0xd4, read: phys addr = 0xd4value read = afbf0014 Writing VA 0x4ec, size 4, value 0x8Translate 0x4ec, write: phys addr = 0x4ec Reading VA 0xd8, size 4Translate 0xd8, read: phys addr = 0xd8value read = afbe0010 Writing VA 0x4e8, size 4, value 0x0Translate 0x4e8, write: phys addr = 0x4e8 Reading VA 0xdc, size 4Translate 0xdc, read: phys addr = 0xdcvalue read = 0c000030 Reading VA 0xe0, size 4Translate 0xe0, read: phys addr = 0xe0value read = 03a0f021 Reading VA 0xc0, size 4Translate 0xc0, read: phys addr = 0xc0value read = 03e00008 Reading VA 0xc4, size 4Translate 0xc4, read: phys addr = 0xc4value read = 00000000 Reading VA 0xe4, size 4Translate 0xe4, read: phys addr = 0xe4value read = 0c000004 Reading VA 0xe8, size 4Translate 0xe8, read: phys addr = 0xe8value read = 00000000 Reading VA 0x10, size 4Translate 0x10, read: phys addr = 0x10value read = 24020000 Reading VA 0x14, size 4Translate 0x14, read: phys addr = 0x14value read = 0000000c Shutdown, initiated by user program. Machine halting!Ticks: total 45, idle 0, system 30, user 15 Disk I/O: reads 0, writes 0 Console I/O: reads 0, writes 0 Paging: faults 0 Network I/O: packets received 0, sent 0Cleaning up...

結(jié)果顯示，tlb正確調(diào)用了TLBMissHandler，并正確地從頁表中加載了頁面。

此外還可以發(fā)現(xiàn)：雖然halt初始化了10個頁面，但是訪問的僅有3個，分別為0/1/9號頁，tlb并沒有滿，無法比較不同置換算法的優(yōu)劣，所以我寫了99table。這點(diǎn)在前面的準(zhǔn)備工作中提到過。

分別打開FIFO和LRU的開關(guān)，即在code/userprog/MakeFile中分別加上

DEFINES = -DTLB_LRU DEFINES = -DTLB_FIFO

在terminal中輸入：./nachos -d r -x ../test/99table

測試結(jié)果如下：

//LRU r意為rate of tlb hit vagrant@precise32:/vagrant/nachos/nachos-3.4/code/userprog$ ./nachos -d r -x ../test/99table LRU : TLB Hit: 3423, Total Visit: 3446, TLB Hit Rate: 99.33% Machine halting!Ticks: total 145, idle 0, system 30, user 115 Disk I/O: reads 0, writes 0 Console I/O: reads 0, writes 0 Paging: faults 0 Network I/O: packets received 0, sent 0Cleaning up... //FIFO vagrant@precise32:/vagrant/nachos/nachos-3.4/code/userprog$ ./nachos -d r -x ../test/99table FIFO : TLB Hit: 3431, Total Visit: 3479, TLB Hit Rate: 98.62% Machine halting!Ticks: total 145, idle 0, system 30, user 115 Disk I/O: reads 0, writes 0 Console I/O: reads 0, writes 0 Paging: faults 0 Network I/O: packets received 0, sent 0Cleaning up...

結(jié)論

LRU算法的命中率高于FIFO算法，換言之，LRU的缺頁率略微低于FIFO算法。理論上，二者的差距應(yīng)該很大，但是在實(shí)際的測試結(jié)果中顯示，二者的差距只有百分之一，這是因?yàn)?9table空間局部性很強(qiáng)，經(jīng)常訪問的頁面就是這么幾個，所以二者的差距拉不開。我們需要更大的程序來論證我們的觀點(diǎn)，比如matmult（完成Exercise 7之后進(jìn)行）。

Exercise4 內(nèi)存全局管理數(shù)據(jù)結(jié)構(gòu)

位圖bitMap

所謂位圖，就是利用bit來記錄內(nèi)存的分配情況,每一位只有0和1兩種狀態(tài)，0表示未分配，1表示已分配。一個int型變量占4B = 32bit的物理空間，一個bool型變量占1B =8bit的物理空間，若開辟一個bool型數(shù)組來記錄內(nèi)存分配情況，其空間開銷將為位圖的八倍，故使用位圖可以大大減少空間開銷。

為了實(shí)現(xiàn)位圖，我將bitMap封裝成一個類，成員變量和函數(shù)如下表：

成員變量/函數(shù)描述

unsigned int bitmap;	由于Nachos物理空間為32頁，因此使用一個無符號int型變量正好可以記錄內(nèi)存分配情況。
int findZeroBit()	找到第一個為0的位，返回其下標(biāo)，若沒有，則返回-1；該函數(shù)使用了一些簡單的位運(yùn)算實(shí)現(xiàn)逐位檢查并check該位是否為1的功能。
void setBit(int index, bool zeroOrOne)	根據(jù)bool型參數(shù)zeroOrOne的值（true表示1，false表示0），將下標(biāo)為index的位設(shè)為0或1。用于內(nèi)存分配/回收。
void freeMem()	回收內(nèi)存
int allocateMem()	分配內(nèi)存
void printBitMap()	按二進(jìn)制格式打印bitMap信息

我在code/machine/machine.h中新增了一個bitMap類：

// lab2 定義bitMap class bitMap {public:int findZeroBit();void setBit(int index, bool zeroOrOne);int allocateMem();void freeMem();void printBitMap();private:unsigned int bitmap; };

在code/machine/machine.cc中實(shí)現(xiàn)了所有的成員函數(shù)：

//lab2 實(shí)現(xiàn)bitMap int bitMap ::findZeroBit() // 找到為0的位 {int index = 0;for (; index < NumPhysPages; index++){if (!(bitmap >> index & 0x1)){return index;}}return -1; }void bitMap ::setBit(int index, bool zeroOrOne) //將index置0/1 {if (zeroOrOne)bitmap |= (0x1 << index); //置0elsebitmap &= (0x1 << index); //置1 }int bitMap ::allocateMem() {int ppn = findZeroBit();if (ppn != -1){DEBUG('p', "Using bitmap, physical page frame: %d is allocated.\n", ppn); //p代表physical pagesetBit(ppn, true);}elseDEBUG('p', "Exceeded number of physical pages!\n");return ppn; }void bitMap::freeMem() {for (int i = 0; i < machine->pageTableSize; i++){if (machine->pageTable[i].valid){ // Free currentThread's all page framesint pageFrameNum = machine->pageTable[i].physicalPage;setBit(pageFrameNum, false);DEBUG('p', "Physical page frame: %d freed.\n", pageFrameNum);}}DEBUG('p', "After freed, bitmap : ");machine->bitmap->printBitMap(); }void bitMap::printBitMap() //c語言沒有輸出2進(jìn)制的接口，所以用一個循環(huán)逐位輸出bitmap {printf("bitmap : ");unsigned int shift = 1 << 31;for (; shift >= 0; shift >>= 1){if (shift & bitmap)printf("1");elseprintf("0");}printf("\n"); }

在code/machine/machine.h的machine類中定義一個bitmap，并在code/machine/machine.cc中初始化它

class Machine {public:...//lab2 bitmapbitMap *bitmap;... } Machine::Machine(bool debug) {//lab2 bitmapbitmap = new bitMap;... }

至此，我們已經(jīng)有了自己的bitmap對象，并可以用它來分配內(nèi)存了。

內(nèi)存分配

在addrSpace的構(gòu)造函數(shù)中：利用bitMap成員函數(shù)allocateMem來分配內(nèi)存。

AddrSpace::AddrSpace(OpenFile *executable) {...//初始化頁表for (i = 0; i < numPages; i++){pageTable[i].virtualPage = i; pageTable[i].use = FALSE;pageTable[i].dirty = FALSE;pageTable[i].readOnly = FALSE; int ppn = machine->bitmap->allocateMem();if (ppn != -1){pageTable[i].physicalPage = ppn;pageTable[i].valid = TRUE;}elsepageTable[i].valid = FALSE;}DEBUG('p',"After allocate, ");//內(nèi)存分配完畢，打印bitmapmachine->bitmap->printBitMap();... }

內(nèi)存回收

正如code/machine/machine.cc中的注釋所言，machine->run()永遠(yuǎn)不會return，要回收addrSpace要借助系統(tǒng)調(diào)用Exit（在exercise5中我會詳細(xì)解釋Exit系統(tǒng)調(diào)用）。

在Exit系統(tǒng)調(diào)用中添加如下語句：

//lab2 bitmap內(nèi)存回收 void Exit(int exitCode) { #ifdef USER_PROGRAMmachine->bitmap->freeMem(); #endifexit(exitCode); }

測試

本次測試使用debug flag p，代表physical page management。在terminal中輸入./nachos -d p -x ../test/halt，結(jié)果如下

vagrant@precise32:/vagrant/nachos/nachos-3.4/code/userprog$ ./nachos -d p -x ../test/halt Physical page frame: 0 is allocated. Physical page frame: 1 is allocated. Physical page frame: 2 is allocated. Physical page frame: 3 is allocated. Physical page frame: 4 is allocated. Physical page frame: 5 is allocated. Physical page frame: 6 is allocated. Physical page frame: 7 is allocated. Physical page frame: 8 is allocated. Physical page frame: 9 is allocated. After allocated : bitmap : 00000000000000000000001111111111 Machine halting!Ticks: total 45, idle 0, system 30, user 15 Disk I/O: reads 0, writes 0 Console I/O: reads 0, writes 0 Paging: faults 0 Network I/O: packets received 0, sent 0Cleaning up... Physical page frame: 0 is freed. Physical page frame: 1 is freed. Physical page frame: 2 is freed. Physical page frame: 3 is freed. Physical page frame: 4 is freed. Physical page frame: 5 is freed. Physical page frame: 6 is freed. Physical page frame: 7 is freed. Physical page frame: 8 is freed. Physical page frame: 9 is freed. After freed, bitmap : 00000000000000000000000000000000

結(jié)果顯示：Nachos結(jié)束之后才釋放bitmap，這顯然是不對的。你知道原因嗎？因?yàn)閔alt沒有顯式地調(diào)用Exit，這個Exit是在code/thread/system.cc中的cleanup()調(diào)用的，在這之前已經(jīng)執(zhí)行了Halt系統(tǒng)調(diào)用，所以屏幕打印halt信息早于bitmap回收信息。

我們應(yīng)該在code/userprog/exception.cc中的exceptionHandler中添加對Halt系統(tǒng)調(diào)用的處理語句：

void ExceptionHandler(ExceptionType which) {...if (which == SyscallException){if (type == SC_Halt){machine->bitmap->freeMem();}}... }

再次執(zhí)行./nachos -d p -x ../test/halt，結(jié)果正確。

vagrant@precise32:/vagrant/nachos/nachos-3.4/code/userprog$ ./nachos -d p -x ../test/halt Physical page frame: 0 is allocated. Physical page frame: 1 is allocated. Physical page frame: 2 is allocated. Physical page frame: 3 is allocated. Physical page frame: 4 is allocated. Physical page frame: 5 is allocated. Physical page frame: 6 is allocated. Physical page frame: 7 is allocated. Physical page frame: 8 is allocated. Physical page frame: 9 is allocated. After allocated， bitmap : 00000000000000000000001111111111 Physical page frame: 0 is freed. Physical page frame: 1 is freed. Physical page frame: 2 is freed. Physical page frame: 3 is freed. Physical page frame: 4 is freed. Physical page frame: 5 is freed. Physical page frame: 6 is freed. Physical page frame: 7 is freed. Physical page frame: 8 is freed. Physical page frame: 9 is freed. After freed, bitmap : 00000000000000000000000000000000 Machine halting!Ticks: total 45, idle 0, system 30, user 15 Disk I/O: reads 0, writes 0 Console I/O: reads 0, writes 0 Paging: faults 0 Network I/O: packets received 0, sent 0Cleaning up...

結(jié)論

成功利用bitMap實(shí)現(xiàn)對內(nèi)存的分配與回收。

其實(shí)Nachos在code/userprog/bitmap.h(cc)中已經(jīng)實(shí)現(xiàn)了BitMap，如果以后有擴(kuò)展物理內(nèi)存的需求，以至于當(dāng)前的unsigned int類型無法滿足需求時，應(yīng)該切換為Nachos自帶的bitmap。

Exercise 5

線程切換和用戶程序切換的關(guān)系

寄存器和內(nèi)存

thread.h中定義了userRegisters用于保存和恢復(fù)Nachos的模擬寄存器，定義了兩個函數(shù)來保存和恢復(fù)寄存器，分別為SaveUserState函數(shù)和RestoreUserState函數(shù)。在schedule->run函數(shù)中，在Switch之前調(diào)用currentThread->SaveUserState將machine的寄存器數(shù)組拷貝到線程的userRegisters數(shù)組中，并調(diào)用currentThread->space->SaveState()函數(shù)來保存地址空間，目前函數(shù)體為空，我們需要改寫：將TLB的內(nèi)容清空：

void AddrSpace::SaveState() { #ifdef USE_TLB // Lab2: Clean up TLBDEBUG('T', "Clean up TLB due to Context Switch!\n");for (int i = 0; i < TLBSize; i++){machine->tlb[i].valid = FALSE;} #endif }

在Switch之后調(diào)用currentThread->RestoreUserState函數(shù)來將線程中userRegisters數(shù)組中保存的數(shù)據(jù)拷貝到machine的寄存器數(shù)組中，再調(diào)用currentThread->space->RestoreState()函數(shù)來將線程的頁表始址拷貝到machine中的pageTable變量中。

構(gòu)造多線程

我在 code/userprog/progtest.cc中加入了startMultiProgress()函數(shù)，并注釋掉了原來的startProgress(),調(diào)用方法還是輸入-x。

在startMultiProgress中，會構(gòu)造三個線程，并執(zhí)行相同的程序。

//lab2 多線程 #define N 3 //線程數(shù) void startMultiProcess(char *filename) {OpenFile *executable = fileSystem->Open(filename);if (executable == NULL){printf("Unable to open file %s\n", filename);return;}//創(chuàng)建一個thread指針數(shù)組Thread *thread[N];//創(chuàng)建三個一樣的線程,并插入就緒隊(duì)列for (int i = 0; i < N; ++i){thread[i] = initThreadSpace(executable, i);thread[i]->Fork(runUserProg, i);}delete executable; // close filecurrentThread->Yield(); }

創(chuàng)建線程時，需要初始化地址空間：

//lab2 實(shí)現(xiàn)多線程初始化地址空間Thread * initThreadSpace(OpenFile *executable, int number) {printf("Creating user program thread %d\n", number);char *ThreadName;sprintf(ThreadName, "User program %d", number);Thread *thread = new Thread(ThreadName, 1);AddrSpace *space;space = new AddrSpace(executable);thread->space = space;return thread; }

對每個用戶程序，我們都需要初始化它們的寄存器和頁表。

//lab2 運(yùn)行用戶程序void runUserProg(int number) {printf("Running user program thread %d\n", number);currentThread->space->InitRegisters(); // set the initial register valuescurrentThread->space->RestoreState(); // load page table register// currentThread->space->PrintState(); // debug usagemachine->Run(); // jump to the user progamASSERT(FALSE); // machine->Run never returns;// the address space exits// by doing the syscall "exit" }

測試

在前面的實(shí)驗(yàn)中我們已經(jīng)知道Nachos自帶的halt會占用10頁物理內(nèi)存，3個halt線程應(yīng)該占30頁。在terminal中輸入./nachos -d rtp -x ../test/halt,

r表示rate of tlb hit(命中率），t是Nachos自帶的thread debug flag, p表示physical page management。測試結(jié)果如下：

vagrant@precise32:/vagrant/nachos/nachos-3.4/code/userprog$ ./nachos -d rtp -x ../test/halt Creating user program thread 0 Physical page frame: 0 is allocated. Physical page frame: 1 is allocated. Physical page frame: 2 is allocated. Physical page frame: 3 is allocated. Physical page frame: 4 is allocated. Physical page frame: 5 is allocated. Physical page frame: 6 is allocated. Physical page frame: 7 is allocated. Physical page frame: 8 is allocated. Physical page frame: 9 is allocated. After allocated, bitmap : 00000000000000000000001111111111 Forking thread "User program 0" with func = 0x804d14b, arg = 0 Putting thread User program 0 on ready list. Creating user program thread 1 Physical page frame: 10 is allocated. Physical page frame: 11 is allocated. Physical page frame: 12 is allocated. Physical page frame: 13 is allocated. Physical page frame: 14 is allocated. Physical page frame: 15 is allocated. Physical page frame: 16 is allocated. Physical page frame: 17 is allocated. Physical page frame: 18 is allocated. Physical page frame: 19 is allocated. After allocated, bitmap : 00000000000011111111111111111111 Forking thread "User program 1" with func = 0x804d14b, arg = 1 Putting thread User program 1 on ready list. Creating user program thread 2 Physical page frame: 20 is allocated. Physical page frame: 21 is allocated. Physical page frame: 22 is allocated. Physical page frame: 23 is allocated. Physical page frame: 24 is allocated. Physical page frame: 25 is allocated. Physical page frame: 26 is allocated. Physical page frame: 27 is allocated. Physical page frame: 28 is allocated. Physical page frame: 29 is allocated. After allocated, bitmap : 00111111111111111111111111111111 Forking thread "User program 2" with func = 0x804d14b, arg = 2 Putting thread User program 2 on ready list. Yielding thread "main" Putting thread main on ready list. Switching from thread "main" to thread "User program 0" Running user program thread 0 Yielding thread "User program 0" Putting thread User program 0 on ready list. Switching from thread "User program 0" to thread "User program 1" ...//線程切換 Deleting thread "main" LRU : TLB Hit: 29, Total Visit: 40, TLB Hit Rate: 72.50% Physical page frame: 0 is freed. Physical page frame: 1 is freed. Physical page frame: 2 is freed. Physical page frame: 3 is freed. Physical page frame: 4 is freed. Physical page frame: 5 is freed. Physical page frame: 6 is freed. Physical page frame: 7 is freed. Physical page frame: 8 is freed. Physical page frame: 9 is freed. After freed, bitmap : 00000000000000000000000000000000 Machine halting!Ticks: total 165, idle 0, system 130, user 35 Disk I/O: reads 0, writes 0 Console I/O: reads 0, writes 0 Paging: faults 0 Network I/O: packets received 0, sent 0Cleaning up...

結(jié)論

成功實(shí)現(xiàn)多線程。

Exercise 6 缺頁中斷

缺頁時需要從硬盤讀取頁，Nachos沒有對disk進(jìn)行模擬，所以我用文件代替。

虛擬存儲

我用一個文件virtualMemory來裝載用戶程序的數(shù)據(jù)段和代碼段。并對addrSpace()作了如下修改：

pageTable[i] = FALSE;表示我們一開始并不把任何頁裝入內(nèi)存
從executable中復(fù)制數(shù)據(jù)段和代碼段到virtualMemory文件中

缺頁中斷處理函數(shù)

在code/userprog/exception.cc中，每當(dāng)替換頁面valid位為FALSE時，將產(chǎn)生缺頁異常。

void TLBMissHandler(int virtAddr) {unsigned int vpn = virtAddr / PageSize;// 尋找置換頁TranslationEntry page = machine->pageTable[vpn];if (!page.valid) { page = PageMissHandler(vpn);}...

PageMissHandler將做如下的工作：

通過bitmap成員函數(shù)allocateMem()來分配mainMemory中的空閑頁
從硬盤中加載對應(yīng)頁面到mainMemory中
- 如果mainMemory滿了，將調(diào)用頁面置換算法，這里使用FIFO算法（我將在Exercise 7 中詳細(xì)說明）

TranslationEntry PageMissHandler(int vpn) {int ppn = machine->allocateFrame(); // ppnif (ppn == -1) { // Need page replacementppn = naiveReplacement(vpn);}machine->pageTable[vpn].physicalPage = ppn;//從硬盤中加載頁面到mainMemoryDEBUG('a', "Demand paging: loading page from virtual memory!\n");OpenFile *vm = fileSystem->Open("VirtualMemory"); vm->ReadAt(&(machine->mainMemory[pageFrame*PageSize]), PageSize, vpn*PageSize);delete vm; //設(shè)置頁面參數(shù)machine->pageTable[vpn].valid = TRUE;machine->pageTable[vpn].use = FALSE;machine->pageTable[vpn].dirty = FALSE;machine->pageTable[vpn].readOnly = FALSE; }

exercise 7 Lazy-loading

樸素頁面置換算法Naive page replacement

尋找mainMemory中一個dirty位為FALSE的頁面進(jìn)行置換
如果不存在，則將一個dirty位為TRUE的頁面寫入硬盤

//lab2 Lazy-loading //樸素頁面置換算法 int NaiveReplacement(int vpn) {int ppn = -1;for (int i = 0; i < machine->pageTableSize; i++){if(i == vpn) continue;//跳過自己if (machine->pageTable[i].valid){if (!machine->pageTable[i].dirty){ppn = machine->pageTable[i].physicalPage;break;}}}if (ppn == -1){for (int i = 0; i < machine->pageTableSize; i++){if(i == vpn) continue;if (machine->pageTable[i].valid){machine->pageTable[i].valid = FALSE;ppn = machine->pageTable[i].physicalPage;//寫回硬盤OpenFile *vm = fileSystem->Open("VirtualMemory");vm->WriteAt(&(machine->mainMemory[ppn * PageSize]), PageSize, i * PageSize);delete vm; // close filebreak;}}}return ppn; }

測試

在terminal中輸入.\nachos -d rp -x ../test/halt可得到結(jié)果：

vagrant@precise32:/vagrant/nachos/nachos-3.4/code/userprog$ ./nachos -d rp -x ../test/halt Allocate physical page frame: 0 Bitmap : 000000000000000000000000000001 Allocate physical page frame: 1 Bitmap: 000000000000000000000000000011 Allocate physical page frame: 2 Bitmap: 000000000000000000000000000111 LRU : TLB Hit: 29, Total Visit: 40, TLB Hit Rate: 72.50% Machine halting!Ticks: total 28, idle 0, system 10, user 18

結(jié)論

一開始沒有頁面加載進(jìn)入內(nèi)存，之后每需要一頁就加載進(jìn)入內(nèi)存，成功實(shí)現(xiàn)了請求分頁。

*challenge2 倒排頁表

所謂倒排頁表，就是與頁表相反，為所有物理地址維護(hù)一張頁表，其大小等于物理地址空間，頁表項(xiàng)包括虛擬地址，所屬線程ID和一些標(biāo)志位。一般來說虛擬地址空間是遠(yuǎn)大于物理地址空間的，因此為每個用戶線程維護(hù)一個頁表的空間開銷將遠(yuǎn)遠(yuǎn)大于倒排頁表。

倒排頁表的優(yōu)點(diǎn)顯而易見：可以大大減少頁表的空間開銷；但是它也有缺點(diǎn)：會導(dǎo)致更長的查詢時間（要查詢某頁是否在內(nèi)存，每次都需要遍歷整個倒排頁表，時間復(fù)雜度O(n)，而頁表的查詢時間為O(1)）。并且它會導(dǎo)致進(jìn)程間的內(nèi)存共享更加困難。好在Nachos的物理空間很小，只有32頁，所以使用倒排頁表導(dǎo)致的額外時間開銷很小，甚至可以忽略不計(jì)。

在translation.h中新增invertedPageTableEntry類，其成員變量和描述如下表：

成員變量/函數(shù)描述

int vpn	虛擬頁號vpn
int tID	所屬線程ID
bool valid	合法位(頁面在內(nèi)存中為True)
bool readOnly	只讀位
bool dirty	臟位(當(dāng)某頁被修改時置為true)
int lastVisitedTime	上次被訪問的時間（為后面的LRU頁面置換算法做準(zhǔn)備）
構(gòu)造函數(shù)	使用默認(rèn)構(gòu)造函數(shù)
void recycle()	回收某頁，將所有成員變量置為0/false

在machine.cc中定義一個大小為NumPhysPages的iPageTable(invertedPageTableEntry *iPageTable = new invertedPageTableEntry[NumPhysPages])至此，倒排頁表已經(jīng)實(shí)現(xiàn)了。

總結(jié)

以上是生活随笔為你收集整理的Nachos Lab2 虚拟内存的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。