Nachos虛擬內(nèi)存機(jī)制實(shí)習(xí)報(bào)告

虛擬內(nèi)存機(jī)制實(shí)習(xí)匯報(bào)善良的大姐姐.4.18

目錄一：總體概述 3二：任務(wù)完畢狀況 3任務(wù)完畢列表（Y/N） 3詳細(xì)Exercise的完畢狀況 3三：碰到的困難以及處理措施 15四：收獲及感想 15五：對(duì)課程的意見和提議 15六：參照文獻(xiàn) 15一：總體概述 通過認(rèn)真仔細(xì)閱讀Nachos系統(tǒng)虛擬內(nèi)存部分的源代碼，理解虛擬內(nèi)存的管理和應(yīng)用機(jī)制，顧客程序的運(yùn)行邏輯，并修改源代碼，到達(dá)“實(shí)現(xiàn)虛擬存儲(chǔ)系統(tǒng)”的目的。二：任務(wù)完畢狀況任務(wù)完畢列表（Y/N）Exercise1Exercise2Exercise3Exercise4Exercise5Exercise6Exercise7Challengeyesyesyesyesyesyesyesyes詳細(xì)Exercise的完畢狀況Exercise1:源代碼閱讀 Part1:閱讀code/userprog/progtest.cc，著重理解nachos執(zhí)行顧客程序的過程，以及該過程中與內(nèi)存管理有關(guān)的要點(diǎn)。 閱讀狀況：顧客程序執(zhí)行過程：環(huán)節(jié)有關(guān)解釋在main函數(shù)中，假如檢測(cè)到傳入的參數(shù)和“執(zhí)行顧客程序”有關(guān)，那么執(zhí)行StartProcess函數(shù)（progtest.cc）在StartProcess函數(shù)中裝載并運(yùn)行一種顧客程序StartProcess函數(shù)中：用OpenFile類打開文獻(xiàn)OpenFile類在文獻(xiàn)系統(tǒng)中定義，包括多種對(duì)文獻(xiàn)的基本操作，如read,write。實(shí)質(zhì)上是包裝了操作系統(tǒng)的底層函數(shù)。用AddrSpace類創(chuàng)立一種顧客空間，并將打開的文獻(xiàn)裝載進(jìn)去創(chuàng)立顧客空間包括：獲取文獻(xiàn)頭，并將大小端做合適轉(zhuǎn)換；通過文獻(xiàn)頭計(jì)算出文獻(xiàn)所需空間，包括代碼段，初始化數(shù)據(jù)段，未初始化數(shù)據(jù)段，?？臻g4個(gè)部分通過文獻(xiàn)所需空間計(jì)算出文獻(xiàn)所需的虛擬頁數(shù)量創(chuàng)立顧客空間的pagetable，指示了第i個(gè)虛擬頁（將）對(duì)應(yīng)第i個(gè)物理頁由于目前是最基本的【直接映射+單顧客程序無切換】模式，因此此時(shí)要將所有的虛擬頁中的內(nèi)容寫到物理頁（主存）當(dāng)中。3.（AddrSpace::InitRegisters()）初始化顧客空間中的多種寄存器，包括PC設(shè)為0，棧指針移到空間底部為執(zhí)行顧客程序做準(zhǔn)備！（AddrSpace::RestoreState()）將顧客的部分狀態(tài)（如pagetable）裝載到machine類中，準(zhǔn)備執(zhí)行實(shí)際上，僅僅是將顧客空間的Pagetable（在第二步創(chuàng)立的）裝載到machine的指針中，相稱于是顧客程序在machine上運(yùn)行時(shí)，是通過machine的pagetable映射找到對(duì)應(yīng)內(nèi)容運(yùn)行的調(diào)用machine->Run，運(yùn)行顧客程序Machine->run是在mipssim.cc中定義的。其工作原理為：通過OneInstruction(instr)模擬mips，將一條指令進(jìn)行分割，并軟件模擬執(zhí)行。其中，在OneInstruction函數(shù)中，通過machine->ReadMem，讀取主存中目前PC值指向的地址里的指令。在ReadMem函數(shù)中，通過Translate函數(shù)對(duì)傳入的虛地址做轉(zhuǎn)換。在Translate函數(shù)中，假如虛地址沒有找到對(duì)應(yīng)的實(shí)地址轉(zhuǎn)換，就會(huì)拋出異常（返回異常值）。返回的異常值在ReadMem中判斷，并傳入RaiseException函數(shù)中RaiseException函數(shù)會(huì)調(diào)用ExceptionHandler函數(shù)對(duì)不一樣的異常做對(duì)應(yīng)的處理。（以上是異常處理機(jī)制。在這里就順便說了。）調(diào)用onetick讓時(shí)間前進(jìn)反復(fù)1,2 Part2:閱讀code/machine目錄下的machine.h(cc)，translate.h(cc)文獻(xiàn)和code/userprog目錄下的exception.h(cc)，理解目前Nachos系統(tǒng)所采用的TLB機(jī)制和地址轉(zhuǎn)換機(jī)制。TLB機(jī)制和地址轉(zhuǎn)換機(jī)制：有關(guān)內(nèi)容簡(jiǎn)樸解釋TranslationEntry類（translate.h），包括：virtualPage,physicalPage,以及某些標(biāo)志位：valid,readonly等。標(biāo)識(shí)了顧客空間的第i個(gè)虛擬頁應(yīng)當(dāng)映射到主存的第j個(gè)物理頁，并且這個(gè)物理頁目前所處的狀態(tài)。（valid?readOnly?等）TLB初始化（machine.cc構(gòu)造函數(shù)）：生成指定數(shù)量的TranslationEntry構(gòu)成的數(shù)組，并且設(shè)置均為Invalid.TLB自身就類似于Pagetable的子集，有若干的<vpn,ppn>的映射對(duì)。TLB的使用（translate.cctranslate函數(shù)）：遍歷TLB數(shù)組，查找與否有對(duì)應(yīng)映射假如有，TLB命中，直接進(jìn)行物理地址轉(zhuǎn)換；否則，TLBMISS，進(jìn)入Exception處理。（目前還沒有對(duì)應(yīng)的處理函數(shù)）無地址轉(zhuǎn)換機(jī)制：在translate.cctranslate函數(shù)中進(jìn)行。通過virtualaddr，計(jì)算出vpn和offset；通過TLB或是直接通過Pagetable，獲得vpn對(duì)應(yīng)的ppn；（否則拋出異常，在異常處理函數(shù)中做處理，但目前這部分沒有實(shí)現(xiàn)）通過ppn和offset得到物理地址，將物理地址返回。無TLBmiss或是pagefault處理（exception.cc）：在上一種表格中已經(jīng)對(duì)異常處理是怎樣進(jìn)入的做了簡(jiǎn)介。但這里要補(bǔ)充一點(diǎn)：在處理完TLBmiss或是Pagefault之后，不需要將PC+4，由于異常處理函數(shù)結(jié)束后，返回的最終位置會(huì)是OneInstruction函數(shù)的取指階段。取指失敗后，OneInstruction函數(shù)會(huì)退出，然后再用同樣的PC取一次指令。而這次就可以TLBhit或者pagetablehit了。無Exercise2:TLBMISS異常處理 任務(wù)：修改code/userprog目錄下exception.cc中的ExceptionHandler函數(shù)，使得Nachos系統(tǒng)可以對(duì)TLB異常進(jìn)行處理（TLB異常時(shí)，Nachos系統(tǒng)會(huì)拋出PageFaultException，詳見code/machine/machine.cc）。 完畢狀況：有關(guān)異常處理的機(jī)理已經(jīng)在Exercise1中闡明了。因此可以對(duì)TLB異常進(jìn)行處理，我們只要在判斷傳入的參數(shù)為TLBMISS的異常，并對(duì)其進(jìn)行處理即可。實(shí)際上，我在實(shí)際操作的時(shí)候，TLBMISS和PAGEFAULT，拋出的異常都是PageFaultException，此后再判斷machine->tlb與否為空。假如為空，則執(zhí)行PagefaultFunc；否則，執(zhí)行TLBmissFunc。TLBmissFunc:環(huán)節(jié)簡(jiǎn)樸解釋從machine的BadVAddrReg寄存器中取出發(fā)生異常的虛擬地址，并算出vpn；在RaiseException函數(shù)中，將發(fā)生異常的虛擬地址放入該寄存器的。掃描pagetable，尋找該vpn對(duì)應(yīng)的項(xiàng)。目前狀況，是一定可以找到的。由于目前顧客程序運(yùn)行的機(jī)理是：將所有segment所有寫入主存中，并且所有做好了虛實(shí)映射，放在自己的PageTable中。當(dāng)mechine需要加載這個(gè)顧客程序時(shí)，會(huì)獲得這個(gè)pagetable。于是相稱于是，mechine通過這個(gè)pagetable，可以得到顧客空間所有虛地址對(duì)應(yīng)的實(shí)地址。因此當(dāng)TLBMISS時(shí)，查找pagetable，是一定不會(huì)Miss的。接下來是尋找放入TLB的位置：先考慮TLB中invalid的項(xiàng)，假如存在，寫入該項(xiàng)；假如不存在invalid項(xiàng)，那么就波及TLB置換算法，這在Exercise3中簡(jiǎn)介?？傊罱K一定可以找到一種放置新的entry項(xiàng)的位置。無Exercise3:置換算法 任務(wù)：為TLB機(jī)制實(shí)現(xiàn)至少兩種置換算法，通過比較不一樣算法的置換次數(shù)可比較算法的優(yōu)劣。 完畢狀況：FIFO替代算法LRU替代算法假如替代的是Invalid項(xiàng)，那么不波及算法。否則，將數(shù)組第一種項(xiàng)丟棄，其他項(xiàng)向前移動(dòng)一位。新添加的項(xiàng)放在數(shù)組最終為每個(gè)entry設(shè)置一種lru數(shù)值。當(dāng)TLBHIT時(shí)，HIT項(xiàng)的lru左移加一，其他項(xiàng)的lru左移；當(dāng)TLBMISS時(shí)，進(jìn)入異常處理函數(shù)異常處理函數(shù)中，假如替代的是Invalid項(xiàng)，則將所有valid項(xiàng)（包括目前替代項(xiàng)）的lru值清零否則，掃描TLB數(shù)組，找到Lru值最小的一項(xiàng)進(jìn)行替代，并將所有項(xiàng)的lru值清零測(cè)試的顧客程序?qū)?shù)組大小改成5的矩陣相乘：matmult。將會(huì)分派18個(gè)物理頁，TLB訪問次數(shù)為15000左右。（visittime不一樣，是由于每次miss異常處理之后，還會(huì)再次訪問該地址，因此Miss次數(shù)不一樣，導(dǎo)致visittime次數(shù)也會(huì)不一樣。）測(cè)試成果FIFO：LRU：結(jié)論：LRU算法略優(yōu)于FIFO。Exercise4:內(nèi)存全局管理數(shù)據(jù)構(gòu)造 任務(wù)：設(shè)計(jì)并實(shí)現(xiàn)一種全局性的數(shù)據(jù)構(gòu)造（如空閑鏈表、位圖等）來進(jìn)行內(nèi)存的分派和回收，并記錄目前內(nèi)存的使用狀態(tài)。 完畢狀況：增改狀況簡(jiǎn)樸解釋創(chuàng)立Machine類中，新增一種bitmap的數(shù)據(jù)構(gòu)造memoryMNG，大小設(shè)置為物理頁大小memoryMNG的每一種bit對(duì)應(yīng)一種物理頁的分派狀況內(nèi)存分派Addrspace.cc構(gòu)造函數(shù)中，在構(gòu)建顧客空間的pagetable時(shí)，通過bitmap的組員函數(shù)find返回第一種為0的位，將其作為空閑物理頁分派。Find函數(shù)返回第一種為0的位，并將該位置1。這非常符合我們的規(guī)定。假如不存在為0的位，返回-1。因此我會(huì)用Assert來保證可以對(duì)的分派物理頁。內(nèi)存回收Exception.cchandler函數(shù)中，對(duì)于exit系統(tǒng)調(diào)用的處理函數(shù)中，通過bitmap的組員函數(shù)clear，將pagetable中的所有物理頁釋放，并設(shè)置該項(xiàng)為invalid有關(guān)在哪回收內(nèi)存，這是個(gè)比較麻煩的問題。由于顧客程序運(yùn)行完畢之后，是不會(huì)離開machine->run的for循環(huán)的，并且在調(diào)用machine->run之后的語句也不會(huì)被執(zhí)行。因此，只能在exit系統(tǒng)調(diào)用中回收比較可行。補(bǔ)充：有關(guān)exit系統(tǒng)調(diào)用的異常處理函數(shù)其實(shí)有點(diǎn)麻煩，由于顧客程序可以顯式調(diào)用Exit，而顧客程序結(jié)束之后，也會(huì)自動(dòng)執(zhí)行一種exit。因此，有也許會(huì)有2個(gè)exit被執(zhí)行。考慮到這個(gè)狀況，需要做如下處理：1）假如bitmap已經(jīng)被回收過了，就break出來。2）exit處理函數(shù)之后，PC要+4。測(cè)試成果截圖：釋放頁顧客程序結(jié)束開始執(zhí)行顧客程序分派頁釋放頁顧客程序結(jié)束開始執(zhí)行顧客程序分派頁Exercise5:多線程支持 任務(wù)：目前Nachos系統(tǒng)的內(nèi)存中同步只能存在一種線程，我們但愿打破這種限制，使得Nachos系統(tǒng)支持多種線程同步存在于內(nèi)存中。 完畢狀況： 考慮：目前顧客程序?qū)ainMemory的操作是：在初始化顧客空間的時(shí)候，會(huì)將mainMemory清零，并寫入自己的內(nèi)容。因此，每次運(yùn)行顧客程序，只能有一種在主存中。（主存里僅容許一種顧客程序寄存）如下截圖： 此外，目前mainMemory并沒有真正實(shí)現(xiàn)分頁，所有的segment都是直接且一次性所有寫入的，如下圖： 因此，我們但愿實(shí)現(xiàn)的目的是，將主存分頁（物理頁），也將顧客程序分頁（虛擬頁）這樣不一樣的顧客程序的某些虛擬頁就可以映射到某些物理頁上，也就可以“共存”了，原理如下圖： 在真正實(shí)現(xiàn)的時(shí)候，是按照字節(jié)寫入的，先寫代碼段，再寫數(shù)據(jù)段。 測(cè)試的時(shí)候，在startprocess函數(shù)體中，再新創(chuàng)立一種線程，并讓這個(gè)線程裝載一種顧客程序，且搶占式執(zhí)行。因此我們會(huì)看到：主函數(shù)的顧客程序分派完頁表后，還沒開始執(zhí)行，另一種線程的顧客程序就分派頁表，并執(zhí)行了。當(dāng)這個(gè)線程執(zhí)行完畢之后，才輪到主函數(shù)的顧客程序執(zhí)行。這就闡明了，可以多線程同步存在于主存當(dāng)中。 此外，尚有一種需要闡明的點(diǎn)：線程切換是怎樣影響顧客程序切換的？ 在scheduler->run函數(shù)的ifdefuser_program的宏定義語句中，包括如下兩個(gè)函數(shù)：函數(shù)簡(jiǎn)樸解釋Switch之前①currentThread->SaveUserState()將所有顧客程序的寄存器，從machine的寄存器數(shù)組拷貝到裝載線程的寄存器數(shù)組中，包括PC寄存器等。②currentThread->space->SaveState()目前函數(shù)體為空。改寫：將machine的TLB數(shù)組所有設(shè)置為invalid。（由于線程切換后，TLB中的內(nèi)容所有失效）Switch之后③currentThread->RestoreUserState()與①對(duì)應(yīng)，將所有顧客程序的寄存器，從裝載線程的寄存器數(shù)組拷貝到machine的寄存器數(shù)組中，相稱于恢復(fù)上下文環(huán)境。④currentThread->space->RestoreState()與②對(duì)應(yīng)，將顧客空間的Pagetable裝載到machine上。總結(jié)：通過寄存器數(shù)組以及pagetable的轉(zhuǎn)換，實(shí)現(xiàn)了不一樣顧客程序的切換。 測(cè)試截圖：（測(cè)試函數(shù)：主線程和第二個(gè)線程均運(yùn)行一種只有空函數(shù)體的顧客程序。）第二個(gè)線程中的顧客程序分派頁第二個(gè)線程中的顧客程序釋放頁第二個(gè)線程中的顧客程序結(jié)束運(yùn)行第二個(gè)線程中的顧客程序開始運(yùn)行主線程中的顧客程序分派頁第二個(gè)線程中的顧客程序分派頁第二個(gè)線程中的顧客程序釋放頁第二個(gè)線程中的顧客程序結(jié)束運(yùn)行第二個(gè)線程中的顧客程序開始運(yùn)行主線程中的顧客程序分派頁主線程中的顧客程序釋放頁主線程中的顧客程序結(jié)束運(yùn)行主線程中的顧客程序開始運(yùn)行線程切換主線程中的顧客程序釋放頁主線程中的顧客程序結(jié)束運(yùn)行主線程中的顧客程序開始運(yùn)行線程切換Exercise6:缺頁中斷處理 任務(wù)：基于TLB機(jī)制的異常處理和頁面替代算法的實(shí)踐，實(shí)現(xiàn)缺頁中斷處理（注意！TLB機(jī)制的異常處理是將內(nèi)存中已經(jīng)有的頁面調(diào)入TLB，而此處的缺頁中斷處理則是從磁盤中調(diào)入新的頁面到內(nèi)存）、頁面替代算法等。Exercise7:Lazy-loading 任務(wù)：我們已經(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)行過程中缺頁中斷發(fā)生時(shí)，才會(huì)將所需的頁面從磁盤調(diào)入內(nèi)存。Challenge2:倒排頁表 任務(wù)：多級(jí)頁表的缺陷在于頁表的大小與虛擬地址空間的大小成正比，為了節(jié)省物理內(nèi)存在頁表存儲(chǔ)上的消耗，請(qǐng)?jiān)贜achos系統(tǒng)中實(shí)現(xiàn)倒排頁表。 完畢狀況： Exercise6,Exercise7和Challenge2我是一起完畢的。 分析：缺頁中斷怎樣發(fā)生？（Exercise6）對(duì)于目前的虛擬內(nèi)存系統(tǒng)來說，缺頁中斷是不會(huì)發(fā)生的。由于無論是單線程還是多線程，在顧客程序運(yùn)行之前，就已經(jīng)將所有內(nèi)容拷貝到了主存當(dāng)中，pagetable也做好了所有映射。因此缺頁中斷要想發(fā)生，就不能在一開始就將所有內(nèi)容拷貝到主存當(dāng)中。而這恰恰是Exercise7要做的。缺頁中斷發(fā)生時(shí)，需要做什么？（Exercise7）關(guān)鍵任務(wù)是將發(fā)生缺頁中斷的虛擬地址所在的虛擬頁拷貝到某一張物理頁當(dāng)中。因此，需要：1）找到該虛擬頁；2）確定合適拷貝的物理頁（必要時(shí)候需要考慮臟頁寫出的問題）。缺頁中斷怎樣支持多線程顧客程序的交替運(yùn)行？（Challenge2）雖說每個(gè)顧客空間都維護(hù)一張pagetable也是可行的，但假如是多線程顧客程序運(yùn)行，使用倒排頁表顯然愈加節(jié)省空間。在倒排頁表中，記錄了第i個(gè)物理頁對(duì)應(yīng)的虛擬頁以及進(jìn)程id，于是缺頁中斷（問題2）發(fā)生時(shí)，只需通過倒排頁表找到對(duì)應(yīng)線程進(jìn)行頁表內(nèi)容的寫入、寫出即可。 改動(dòng)：改動(dòng)簡(jiǎn)樸解釋增變化量取消顧客空間的pagetable，維護(hù)machine類中的物理頁大小的倒排頁表數(shù)組倒排頁表的每一項(xiàng)包括：虛擬頁號(hào)，進(jìn)程id，某些標(biāo)志位（如dirty位）第i項(xiàng)表達(dá)第i個(gè)物理頁的狀況。Thread類中新增char*變量，用于記錄顧客程序文獻(xiàn)的文獻(xiàn)名。在Progtest.cc中，初始化顧客程序空間的地方，賦值。Thread類中新增int變量，用于記錄顧客程序文獻(xiàn)的codesegment的起始位置。在addrspace.cc中，addrspace構(gòu)造函數(shù)的是偶，賦值。線程運(yùn)行流程中虛實(shí)地址轉(zhuǎn)換（translate.cc）（取消了TLB?。。⑻摂M地址算出所在的虛擬頁vpn對(duì)比倒排頁表中，與否有某項(xiàng)滿足：valid;虛擬頁號(hào)=vpn;線程Id=目前線程Id。假如有，表達(dá)pagehit，可以計(jì)算出物理地址從而訪問主存假如沒有，拋出Pagefault異常。實(shí)際上，TLB可以使用，但太麻煩了。Pagefault處理函數(shù)（exception.cc）使用Exercise4中寫的內(nèi)存管理器，調(diào)用bitmap的find函數(shù)，尋找與否有空閑的物理頁面由于bitmap和倒排頁表此時(shí)是一一對(duì)應(yīng)的，即：假如bitmap某位為0，那么證明該物理頁未分派，那么倒排頁表中該項(xiàng)就一定沒有內(nèi)容。假如有，1）修改該物理頁面對(duì)應(yīng)的倒排頁表項(xiàng)，填寫“虛擬頁號(hào)”和“線程ID”項(xiàng)2）設(shè)置標(biāo)志位3）通過目前線程指針找到顧客程序文獻(xiàn)，把虛擬頁面寫入主存Thread類中新增了顧客程序文獻(xiàn)的名稱以及codesegment的偏移量?？梢詫?duì)的拷貝一張?zhí)摂M頁的內(nèi)容進(jìn)入主存假如沒有，根據(jù)頁面替代算法，選擇倒排頁表中的一項(xiàng)進(jìn)行替代：1）判斷dirty位，假如是臟頁，通過該項(xiàng)找到對(duì)應(yīng)的線程，從而獲得顧客程序文獻(xiàn)，將對(duì)應(yīng)的頁面寫回2）執(zhí)行環(huán)節(jié)2.這里有兩個(gè)問題：臟頁寫回：實(shí)際上應(yīng)當(dāng)采用互換空間，臨時(shí)寄存換出主存的頁面的；但由于維護(hù)起來過于麻煩，貪圖以便，就將臟頁直接寫回文獻(xiàn)了。通過倒排頁表中的線程id找到對(duì)應(yīng)線程：在LAB1中實(shí)現(xiàn)了一種寄存所有線程的線程池，池內(nèi)的線程Id和在池內(nèi)的下標(biāo)是一一對(duì)應(yīng)的。線程切換Addrspace.cc中，restorestate()函數(shù)中，載入顧客程序的pagetable的兩條語句需要注釋掉不再需要維護(hù)顧客空間的pagetable線程結(jié)束（exception.cc）Exit系統(tǒng)調(diào)用中，需要將本來對(duì)Pagetable的操作轉(zhuǎn)移到對(duì)倒排頁表的操作。將占用的物理頁償還（bitmap對(duì)應(yīng)位置清0），將倒排頁表對(duì)應(yīng)項(xiàng)清空無頁面替代算法LRU替代算法：Translate.cc中，倒排頁表命中一次，將命中項(xiàng)的Lru左移加一，其他項(xiàng)的Lru左移Pagefault處理函數(shù)中，對(duì)新添表項(xiàng)處理完畢之后，都需要將所有的倒排頁表的lru清0Lru是一種Int型數(shù)值，在頁面替代的時(shí)候，選用最小的一項(xiàng)進(jìn)行替代。并且每次pagefault發(fā)生時(shí)，需要將所有項(xiàng)的Lru從0開始計(jì)算，防止某個(gè)頁面反復(fù)被替代。 于是，到目前為止，我們已經(jīng)可以在Nachos系統(tǒng)中多線程同步（交替上