第四章存儲(chǔ)管理概述

現(xiàn)代計(jì)算機(jī)最重要的兩個(gè)硬件—處理器和內(nèi)存

內(nèi)存管理是一項(xiàng)重要的基礎(chǔ)工作內(nèi)存管理的基本功能：分配和釋放抽象和映射隔離與共享存儲(chǔ)擴(kuò)充編譯、鏈接與加載

編譯器完成的是代碼的翻譯，在鏈接之前，它不確定具體的地址，而是把需要重定位地址的地方寫到符號(hào)表里

連接器把各個(gè)“可重定位目標(biāo)文件”組合成一個(gè)可執(zhí)行文件，并確定具體的地址

加載器根據(jù)文件中的地址，以及具體的內(nèi)存管理方案，把程序加載到特定的位置內(nèi)核用戶棧共享庫映射區(qū)域堆可讀/寫數(shù)據(jù)只讀代碼/數(shù)據(jù)未用0xFFFFFFFF0xC00000000x400000000x08048000可執(zhí)行文件加載編譯：將源程序翻譯為機(jī)器指令，生成目標(biāo)文件，這些目標(biāo)文件并不能直接執(zhí)行

編譯器記錄外部函數(shù)和變量的引用位置，每個(gè)目標(biāo)文件都有記錄這些位置的符號(hào)表鏈接：將多個(gè)目標(biāo)文件模塊裝配成一個(gè)完整的程序，它解析符號(hào)表，把對符合的引用轉(zhuǎn)換成具體的數(shù)值地址

一般都把地址做成相對于地址0開始的偏移，便于下一步的再修改，因?yàn)榇藭r(shí)并不知道具體會(huì)在內(nèi)存的哪個(gè)位置運(yùn)行加載：執(zhí)行程序之前，當(dāng)獲得了一塊實(shí)際的內(nèi)存之后，加載器根據(jù)該內(nèi)存的首地址，再次修改和調(diào)整可執(zhí)行文件中的地址，完成地址的最后綁定靜態(tài)地址重定位：

分配內(nèi)存后，程序執(zhí)行前，一次性修改程序中的地址，它無需硬件支持，但修改后不能更換內(nèi)存地址

動(dòng)態(tài)地址重定位：

分配內(nèi)存地址后，把該內(nèi)存的首地址賦給一個(gè)硬件裝置，但不修改鏈接以后的可執(zhí)行文件中的邏輯地址

采用“首地址+邏輯地址”的方法來生成真正的物理地址存儲(chǔ)器層次

現(xiàn)代的存儲(chǔ)器，已經(jīng)不僅僅指內(nèi)存了，它包括了寄存器，緩存，內(nèi)存，磁盤這樣一種層次結(jié)構(gòu)寄存器高速緩存內(nèi)存磁盤從下往上

訪問速度越來越快

容量越來越少

價(jià)格越來越貴存儲(chǔ)器層次設(shè)計(jì)的目的——提高訪問速度當(dāng)訪問數(shù)據(jù)時(shí)，首先在高層次的存儲(chǔ)單元里查找，當(dāng)找不到時(shí)，再向下一層去查找每一層都是其上一層的緩存幾種內(nèi)存管理方法固定分區(qū)

主存空間被劃分成固定數(shù)目、大小不等的分區(qū)，每個(gè)分區(qū)可執(zhí)行一個(gè)作業(yè)，各作業(yè)并發(fā)執(zhí)行執(zhí)行方法：根據(jù)當(dāng)天的作業(yè)情況，進(jìn)行分區(qū)建立“主存分配表”根據(jù)待運(yùn)行作業(yè)的內(nèi)存需求，選擇合適的分區(qū)，載入運(yùn)行缺點(diǎn)分區(qū)大小需要事先由管理員確定內(nèi)存利用率不高分區(qū)的個(gè)數(shù)，限制了并發(fā)進(jìn)程的個(gè)數(shù)不容易進(jìn)行內(nèi)存的動(dòng)態(tài)擴(kuò)充可變分區(qū)

也是根據(jù)作業(yè)的大小選擇分區(qū)，但分區(qū)的劃分是根據(jù)作業(yè)和空余內(nèi)存來動(dòng)態(tài)分配的執(zhí)行方法：每當(dāng)來一個(gè)新進(jìn)程，從可用內(nèi)存中劃分出一塊連續(xù)的區(qū)域，供進(jìn)程使用，沒有合適的區(qū)域，則等待別的進(jìn)程釋放內(nèi)存幾種分配策略最先適應(yīng)分配算法（FirstFit）下次適應(yīng)分配算法（NextFit）最優(yōu)適應(yīng)分配算法（BestFit）最壞適應(yīng)分配算法（WorstFit）快速適應(yīng)分配算法（QuickFit）伙伴系統(tǒng)（buddy算法）

原理：任何尺寸為2i的空閑塊，都可以分解成兩個(gè)2i-1的塊，反過來也可以把他們合并起來，這兩個(gè)塊，成為伙伴執(zhí)行方法：建立一個(gè)空閑數(shù)組free[i]，i=0,…N，每個(gè)元素表示一個(gè)鏈表，該鏈表中的元素是大小為2^i的分配單元分配：

若需要分配大小為n單元的內(nèi)存，則在free中尋找滿足n<=2^i的這樣的i

在free[i]中尋找有沒有空閑塊，有就分配，沒有就繼續(xù)在free[i+1]中尋找，…，直到找到這樣的k（k>i），使得存在空閑塊

把該塊一分為二，L與R，R放入下一級(jí)的free[k-1]中，看大小是否為i，如果還不是，則繼續(xù)分割，再把另一半放入free[k-2]，直到分割到2^i大小

釋放：

當(dāng)某尺寸為2^i的塊回收時(shí)，檢查這個(gè)塊的伙伴是否已經(jīng)被回收，若沒有，則該塊放入free[i]中，若已回收，則他們兩個(gè)合并成一個(gè)2^(i+1)的塊

重復(fù)以上過程，直到不能合并下去，最后放入某一個(gè)free[k]，k>=i中伙伴算法有些重要的應(yīng)用場景，比如在Linux中的Slab分配器一些輔助技術(shù)

當(dāng)出現(xiàn)內(nèi)存不足時(shí)，可以用另一些技術(shù)來補(bǔ)充

內(nèi)存不足有兩種情況：1，總的物理內(nèi)存足夠，只是沒有合適的分區(qū)；2，程序的內(nèi)存要求已經(jīng)超過了實(shí)際物理內(nèi)存移動(dòng)技術(shù)：

適用于第一種情況

把已經(jīng)分配的內(nèi)存塊移動(dòng)到內(nèi)存的一段，而把空閑區(qū)移到另一端缺點(diǎn)：引起很大的開銷

很多時(shí)候不允許進(jìn)行移動(dòng)

對換技術(shù)

也是針對第一種情況

選擇一個(gè)已經(jīng)阻塞、占用內(nèi)存大小合適的進(jìn)程，將其換到磁盤緩沖區(qū)中，然后調(diào)其他進(jìn)程進(jìn)去運(yùn)行核心問題：

按照什么原則，選擇換出進(jìn)程

換進(jìn)程的那些部分

什么時(shí)間來換覆蓋技術(shù)

主要針對第二種情況

原因：盡管程序的總內(nèi)存需求超過了實(shí)際物理內(nèi)存，但并不是每時(shí)每刻都要這么多，實(shí)際上每時(shí)刻，都只有部分代碼在運(yùn)行執(zhí)行方法：

在程序執(zhí)行過程中，將程序的不同模塊在內(nèi)存中交替運(yùn)行，每次運(yùn)行一部分。頁式內(nèi)存管理由于不知將來會(huì)被載入到何處，鏈接器在進(jìn)行目標(biāo)文件的裝配時(shí)，安排的地址，都是相對于0開始的地址由此，所有的程序，地址都是類似的，因此在實(shí)際內(nèi)存管理中，需要有一種機(jī)制，把相同的虛擬地址映射為互不相同的物理地址磁盤緩沖分頁真實(shí)地址進(jìn)程1進(jìn)程2虛擬地址從上圖可以看到，每個(gè)進(jìn)程發(fā)出的虛擬地址，經(jīng)過分頁機(jī)制的轉(zhuǎn)換，都映射為不同的物理地址由于虛擬地址總量大于實(shí)際物理地址，因此，有一部分虛擬地址對應(yīng)的實(shí)際物理地址，會(huì)放在磁盤緩沖區(qū)中，根據(jù)需要?jiǎng)討B(tài)換進(jìn)換出概念：頁面把虛擬地址劃分成大小相等的塊，每個(gè)塊中的地址是連續(xù)的，這些塊稱為頁面

物理空間也做這樣的劃分，即虛擬頁面與物理頁面大小完全相同

分配空間時(shí)，以頁面為單位進(jìn)行分配我們可以認(rèn)為，進(jìn)程的虛擬空間劃分成若干頁（0、1、2、。。。2^n），然后各自映射到物理空間的若干頁面進(jìn)程的虛擬頁面，有一些是空的，所以我們只需關(guān)心非空的那些頁面由于進(jìn)程虛擬頁面的數(shù)量一般大于實(shí)際物理空間的頁面，所以有一些虛擬頁面是映射到磁盤緩沖區(qū)中例如：某進(jìn)程具有1、4、17、33四個(gè)虛擬頁面，分別映射到物理頁面的67、34、59、101頁面如果給出在第4個(gè)頁面中的某個(gè)偏移地址，那么其物理地址就是第34個(gè)物理頁面中相同的偏移處的地址我們可以利用表格來記錄每一個(gè)虛擬頁面和其物理頁面的對應(yīng)關(guān)系，通過查表就可以得知每一個(gè)虛擬地址對應(yīng)的物理地址下面的問題是，如何在計(jì)算機(jī)系統(tǒng)中實(shí)現(xiàn)上述原理？分頁機(jī)制概述

與分頁機(jī)制有關(guān)的是：頁面頁表頁表基址寄存器MMU頁面

一般把頁面的大小設(shè)為4KB

對于4G的虛擬地址空間，就會(huì)有2^20個(gè)虛擬頁面物理內(nèi)存中有多少頁面，根據(jù)具體的內(nèi)存容量來定如何進(jìn)行虛擬地址到物理地址的映射

查表

每個(gè)進(jìn)程分配一張表，稱為“頁表”，這個(gè)表記錄了虛擬頁面到物理頁面的映射關(guān)系

那么每次進(jìn)行地址訪問時(shí)，只要查這張表，就可以知道虛擬頁面對應(yīng)于哪個(gè)物理頁面頁表（PageTable）中的每一個(gè)表項(xiàng)，稱為頁表項(xiàng)（PageTableEntry），其中記錄了對應(yīng)的物理頁面在哪PTEPTEPTEPTEPTEPT每一個(gè)PTE大小是4個(gè)字節(jié)，其中記錄了物理頁面的內(nèi)存起始地址，以及其他的關(guān)于該物理頁面的信息由于物理頁面是4KB，因此只要記錄其高20位即可，PTE的低12位，就用來記錄其他信息在分頁機(jī)制下，虛擬地址有了新的含義

這里的頁表內(nèi)偏移，指找到了物理頁面后，在其中的偏移地址頁面內(nèi)偏移頁表內(nèi)偏移20位12位比如虛擬地址0x00001001,前20位，即0x00001，就表示這個(gè)地址所在的虛擬頁面對應(yīng)的物理頁面信息，位于頁表中偏移1，即第二個(gè)頁表項(xiàng)中取出這個(gè)頁表項(xiàng)，里面存有對應(yīng)的物理頁面的基地址，找到這個(gè)物理頁面，然后再加上上面虛擬地址的低12位，即，就得到了實(shí)際的物理地址如果虛擬頁面對應(yīng)的物理頁面此時(shí)不在內(nèi)存中，則頁表項(xiàng)中的P位就為0，訪問這樣的頁表項(xiàng)，會(huì)產(chǎn)生缺頁異常，異常處理程序就會(huì)去磁盤緩沖區(qū)中找這個(gè)物理頁面，然后調(diào)入內(nèi)存，并更新頁表項(xiàng)如果P位為0，則余下的31位就可以用來記錄該物理頁面存在磁盤哪個(gè)地方頁表基址寄存器

由于每個(gè)進(jìn)程都需要一張頁表，則需要專門有一個(gè)寄存器，來保存頁表的起始地址

以Intel為例，專門設(shè)立了與分頁機(jī)制有關(guān)的4個(gè)寄存器，CR0，CR1，CR2，CR3CR0的最高位（31）位的PG位，表明是否啟用分頁機(jī)制，1代表啟用，所有CPU發(fā)出來的地址都要經(jīng)過分頁機(jī)制的映射；0代表不啟用分頁機(jī)制，此時(shí)，虛擬地址就是物理地址CR3的高20位，就是頁表的起始地址，該地址的后面12位為0，故無需保存只要設(shè)置好頁表，CR3，則虛擬地址到物理地址的映射，都是由硬件自動(dòng)完成的完成這個(gè)映射的硬件叫做內(nèi)存管理單元（MemoryManagementUnit，MMU）CR3虛擬地址物理地址PTMMU提高分頁機(jī)制的效率

有了頁表，CR3，MMU，其實(shí)已經(jīng)完成了分頁機(jī)制所需要的條件

下面看看效率問題空間：頁表會(huì)占用多少空間時(shí)間：地址映射占用多少時(shí)間計(jì)算一下頁表會(huì)占用多少空間

對每一個(gè)進(jìn)程，其虛擬地址空間為2^32，以4KB為一個(gè)頁面，則一共需要2^20個(gè)頁面

這個(gè)進(jìn)程的頁表，就需要2^20個(gè)頁表項(xiàng)，每個(gè)頁表項(xiàng)為4字節(jié)

從而得出：一個(gè)進(jìn)程的頁表大小為4MB這意味著，如果系統(tǒng)中有100個(gè)進(jìn)程，光頁表就要占用400MB解決這個(gè)問題的辦法：同物理頁面的策略一樣，把一部分頁表項(xiàng)，也保存到磁盤緩沖區(qū)中此時(shí)，虛擬地址的含義，又要發(fā)生進(jìn)一步的變化頁內(nèi)偏移一級(jí)頁表偏移二級(jí)頁表偏移10位10位12位即，原來只要查一次表，就能得出物理頁的地址，現(xiàn)在需要查兩次：第一次根據(jù)最高10位，從一級(jí)頁表中查到PTE，這里面保存的是二級(jí)頁表所在物理頁面的地址，二級(jí)頁表如果不在內(nèi)存，也要從磁盤緩沖區(qū)中調(diào)出；然后根據(jù)中間10位，在二級(jí)頁表中找出PTE，這里面才是真正物理頁面的信息。系統(tǒng)中現(xiàn)在就只有一級(jí)頁表是常駐內(nèi)存的，二級(jí)頁表則根據(jù)具體情況，需要時(shí)調(diào)入，不需要時(shí)保存到磁盤緩沖區(qū)如果只保存一級(jí)頁表的話，就只要2^10個(gè)，每個(gè)PTE占4個(gè)字節(jié)，因此此時(shí)頁表的大小就只有4KB，正好一個(gè)頁面（注：每一個(gè)二級(jí)頁表，也是一個(gè)頁面大小）從以上的映射過程來看，即使采用一張頁表，從一個(gè)虛擬地址到物理地址，也需要好幾步，如果是采用二級(jí)頁表，則花費(fèi)的時(shí)間更多，嚴(yán)重影響效率

Linux中甚至采用三級(jí)頁表結(jié)構(gòu)，這樣的做法，Linux還能作為嵌入式操作系統(tǒng)嗎？為解決這個(gè)問題，CPU中特地加入了一個(gè)緩存硬件裝置—TranslationLook-AsideBuffer，TLB，用來保存最近訪問的從虛擬頁面到物理頁面的映射關(guān)系，那么當(dāng)進(jìn)行實(shí)際的映射時(shí)，先在這個(gè)緩沖裝置里找，找不到才進(jìn)行真正的映射盡管每個(gè)進(jìn)程的CR3的值都不同，相同的虛擬地址，會(huì)被映射到不同的物理地址，但虛擬地址中對內(nèi)核地址的映射，都會(huì)映射到相同的物理頁面例如Linux中，虛擬地址中最高的1G空間，其對應(yīng)的PTE中，會(huì)把他們都映射為同一些物理頁面物理內(nèi)存進(jìn)程虛擬空間頁表磁盤緩沖一級(jí)頁表下的內(nèi)存映射二級(jí)頁表下的內(nèi)存映射進(jìn)程虛擬空間一級(jí)頁表二級(jí)頁表物理內(nèi)存磁盤緩沖段式內(nèi)存管理頁式內(nèi)存管理的兩大難以解決的缺陷共享內(nèi)存進(jìn)程所需內(nèi)存超過虛擬空間大小共享內(nèi)存

當(dāng)兩個(gè)進(jìn)程A、B需要共享一段代碼時(shí)，分頁機(jī)制難以做到當(dāng)進(jìn)程所需內(nèi)存大于實(shí)際物理內(nèi)存時(shí)，可以通過“交換技術(shù)”加以解決

但當(dāng)所需內(nèi)存大于虛擬內(nèi)存時(shí)，分頁機(jī)制就無可奈何了在分頁機(jī)制中，基本特點(diǎn)是：每個(gè)進(jìn)程都占用獨(dú)立的虛擬地址空間

但是只能占用一個(gè)虛擬地址空間可能會(huì)占用大量虛擬內(nèi)存空間的程序：

編譯器符號(hào)表常數(shù)表詞法樹代碼段極端例子：如果你寫一個(gè)程序，定義一億個(gè)對象，那編譯可能會(huì)失敗，并非由于變量定義了太多，而是因?yàn)?G的虛擬地址空間已經(jīng)不能滿足要求了因此分頁機(jī)制并非萬能的，完美的

段式內(nèi)存管理，卻可以很容易解決這兩個(gè)問題段式內(nèi)存管理，有點(diǎn)類似于可變分區(qū)的升級(jí)版

可變分區(qū)：一個(gè)進(jìn)程占據(jù)一個(gè)區(qū)（物理）

段式管理：一個(gè)進(jìn)程分成幾個(gè)部分，每一個(gè)部分占據(jù)一個(gè)區(qū)（邏輯）

段式管理最大的一個(gè)特點(diǎn)：每個(gè)段都是一個(gè)獨(dú)立的虛擬地址空間

這里的“段”，指的是邏輯段，它們也要通過某種映射機(jī)制，把邏輯段，映射為物理內(nèi)存的專門區(qū)域符號(hào)表代碼段常數(shù)表詞法樹段式映射注意：上圖中，每一個(gè)段長都根據(jù)需要，各有長短，但實(shí)際上，每一個(gè)段最長可以有最大虛擬空間地址因此采用段式管理，每個(gè)進(jìn)程的虛擬地址空間，可以遠(yuǎn)大于4G（以32位機(jī)器為例）如何實(shí)現(xiàn)段式管理

與段式管理有關(guān)的東西

新的虛擬地址

段表內(nèi)偏移、段寄存器

段表、段表項(xiàng)

段表基址寄存器實(shí)現(xiàn)段式管理的基本思想：每個(gè)段都是獨(dú)立的地址空間，它們都被映射成為物理內(nèi)存上不同的物理段

物理段，就是物理內(nèi)存中一段連續(xù)的區(qū)域如果每個(gè)段，都是從0開始的虛擬地址，那么，光靠這個(gè)地址，就無法辨認(rèn)出，它屬于哪個(gè)段

地址的改進(jìn)

16位32位段表內(nèi)偏移虛擬地址（作為物理段內(nèi)偏移）段寄存器、段選擇符

在實(shí)模式下，CS，DS，ES，SS用來存放一個(gè)段的基地址

在保護(hù)模式下，它們存放了新的東西—段選擇符，里面存放了段表內(nèi)偏移

因?yàn)榕虏粔?，Intel又增加了兩個(gè)段寄存器FS，GS段表、段表項(xiàng)

它們的關(guān)系跟頁表、頁表項(xiàng)的關(guān)系一樣，段表里面放了很多段表項(xiàng)，Intel里叫“段描述符”

段描述符里存放了，該邏輯段，會(huì)被映射到的物理段的基地址

段選擇符里存放了應(yīng)該訪問第幾個(gè)段描述符，即上面圖中的“段號(hào)”段選擇符結(jié)構(gòu)（段表內(nèi)偏移）段表內(nèi)偏移其他信息段描述符結(jié)構(gòu)（段表項(xiàng)）物理段基地址段長度32位段表基址寄存器

同CR3一樣，每一個(gè)進(jìn)程，都有一個(gè)段表，他保存的是該進(jìn)程的段表的基地址段基址寄存器段選擇符虛擬地址段描述符共享與保護(hù)

對于分頁機(jī)制，要考慮是數(shù)據(jù)共享，還是代碼共享，他們實(shí)現(xiàn)的機(jī)制不同數(shù)據(jù)共享：可以為兩個(gè)進(jìn)程分配不同的頁表項(xiàng)，只要這些頁表項(xiàng)所存儲(chǔ)的物理頁面地址一致就可以了代碼共享：由于代碼跳轉(zhuǎn)中包含了指令，因此，兩個(gè)進(jìn)程共享代碼，就必須共享相同的頁表項(xiàng)，即共享的虛擬地址是唯一的頁面的保護(hù)，是根據(jù)頁表項(xiàng)上面響應(yīng)的位來表示的對于分段機(jī)制，實(shí)現(xiàn)共享是相似的，只要給定相同的段選擇符，即可虛擬存儲(chǔ)定義：在具有層次結(jié)構(gòu)存儲(chǔ)器的計(jì)算機(jī)系統(tǒng)中，自動(dòng)實(shí)現(xiàn)部分裝入和部分替換功能，能從邏輯上為用戶提供一個(gè)比物理主存容量大得多的、可尋址的“主存儲(chǔ)器”

虛擬存儲(chǔ)器的容量與物理主存的大小無關(guān)，而受限于計(jì)算機(jī)的地址結(jié)構(gòu)和可用的磁盤容量為何要引入虛擬存儲(chǔ)為程序員提供一個(gè)虛擬的、簡單的、連續(xù)的地址空間，簡化編程的工作盡量高效地利用主存：一個(gè)進(jìn)程的所有部分不一定要在同一時(shí)刻全部裝入主存，有了虛擬存儲(chǔ)，就可以多跑一些進(jìn)程虛擬存儲(chǔ)實(shí)現(xiàn)的可行性

既討論程序部分裝入是否可行，以及由此帶來的系統(tǒng)開銷是否合適

虛擬存儲(chǔ)可行的基礎(chǔ)，來自對“局部性”的研究局部性：某存儲(chǔ)單元被引用之后，程序傾向于一段時(shí)間再次引用該單元（時(shí)間局部性），或者傾向于一段時(shí)間引用該單元附近的存儲(chǔ)單元（空間局部性）以下為關(guān)于局部性的一些研究成果：程序中大部分是順序結(jié)構(gòu)，分支與函數(shù)調(diào)用等跳轉(zhuǎn)結(jié)構(gòu)較少循環(huán)結(jié)構(gòu)由少量代碼組成，多次執(zhí)行過程調(diào)用深度并不大數(shù)組、記錄之類的結(jié)構(gòu)，一般是分配連續(xù)的空間程序中不少部分是互斥的，并非每次都運(yùn)行局部性的意義：通俗地說，局部性就是指一塊存儲(chǔ)單元在某一時(shí)刻被引用之后，它周圍的一部分，會(huì)被引用一段時(shí)間，那么，把這部分放入內(nèi)存，就可以保證程序的運(yùn)行，即部分裝入

另外，可以把這一部分需要被引用一段時(shí)間的存儲(chǔ)單元，放到上一級(jí)的緩存中，以加快訪問速度實(shí)現(xiàn)虛擬存儲(chǔ)，需要解決的一些問題主存與輔助存儲(chǔ)的的統(tǒng)一管理問題邏輯地址到物理地址的轉(zhuǎn)換部分裝入和部分替換問題開銷問題存儲(chǔ)器層次寄存器高速緩存主存磁盤其他輔助外部存儲(chǔ)馮諾依曼計(jì)算機(jī)體系結(jié)構(gòu)：

運(yùn)算單元+存儲(chǔ)單元

如果有這樣一種內(nèi)存：它大到可以容納很多進(jìn)程同時(shí)運(yùn)行，而且訪問速度又很快，那就不用設(shè)計(jì)虛擬存儲(chǔ)了事實(shí)情況時(shí)：

內(nèi)存容量遠(yuǎn)遠(yuǎn)滿足不了全部裝入很多進(jìn)程全部的地址空間

內(nèi)存的訪問速度與寄存器和高速緩存相比，還是遠(yuǎn)遠(yuǎn)不及

因此我們需要這種層次，一方面來實(shí)現(xiàn)虛擬存儲(chǔ)，一方面提高訪問的效率存儲(chǔ)器層次，也跟局部性有關(guān)系：

由于局部性的存在，就可以把最近引用到的存儲(chǔ)單元，盡量放到高層次的、速度更快的存儲(chǔ)硬件當(dāng)中，提高訪問的速度由于局部性的存在，使得盡管當(dāng)今的存儲(chǔ)系統(tǒng)設(shè)計(jì)的非常復(fù)雜，但依然擁有滿意的效率的原因

或者說：首次訪問某個(gè)存儲(chǔ)單元時(shí)，可能會(huì)有效率問題，但一旦該單元被放入高層次的緩存之后，訪問就會(huì)快很多舉例說明：取一個(gè)變量a的值在高層次存儲(chǔ)器里查找a找到，則取a的值，過程結(jié)束若未找到，則去下一層存儲(chǔ)器里找如果在下一層找到了a，則返回a的值，并把a(bǔ)調(diào)入上一層次存儲(chǔ)器（可能會(huì)進(jìn)行交換）如果還是未找到，則再到下一層去找。。。局部性對于程序設(shè)計(jì)的影響

理論上來說，虛擬存儲(chǔ)屬于底層實(shí)現(xiàn)，與上層的程序設(shè)計(jì)，應(yīng)該沒有什么關(guān)系

如果我們寫了個(gè)不符合虛擬存儲(chǔ)原理的程序，編譯器應(yīng)該負(fù)責(zé)優(yōu)化代碼，但實(shí)際上，現(xiàn)在的編譯器還未達(dá)到這個(gè)水平良好的局部性程序：在程序中，訪問的數(shù)據(jù)要傾向于具有良好的局部性（空間上，或是時(shí)間上）假設(shè)有個(gè)問題：把一個(gè)N×M的矩陣各個(gè)元素加起來求和，我們就可以寫一個(gè)“具有良好局部性”和“不具有良好局部性”的程序良好局部性 很差的局部性

int

a[N][M]; int

a[N][M];

for(i=0;i<N;i++) for(j=0;j<M;j++)

for(j=0;j<M;j++) for(i=0;i<N;i++)

sum+=a[i][j]; sum+=a[i][j];為何會(huì)出現(xiàn)這種情況？

因?yàn)閿?shù)組是按行連續(xù)分配的，如果像第二種方式來訪問，就會(huì)進(jìn)行“跳躍式”的訪問，從一個(gè)區(qū)域跳到另一個(gè)區(qū)域，而第一種方式，只是在上一次訪問過的單元附近來訪問表現(xiàn)在虛擬存儲(chǔ)實(shí)現(xiàn)中：第一種方式，當(dāng)調(diào)入一塊內(nèi)存單元入高層次的緩存后，可以使用一段時(shí)間，不用向下去查找；而第二種方式，因?yàn)橄乱淮蔚囊貌辉诋?dāng)前內(nèi)存單元中，系統(tǒng)就不得不多次向下面的速度慢的存儲(chǔ)器中去尋找，頻繁發(fā)生頁面查找和替換，花去了太多的時(shí)間分頁機(jī)制中的虛擬存儲(chǔ)管理 前面已經(jīng)介紹過地址轉(zhuǎn)換的方法，下面講另一些跟虛擬存儲(chǔ)有關(guān)的內(nèi)容

核心的硬件裝置：MMU

MMU的功能：管理頁表基址寄存器分解邏輯地址管理TLB訪問頁表發(fā)出缺頁異常管理頁表項(xiàng)中的各個(gè)標(biāo)志位大致的工作過程：創(chuàng)建進(jìn)程時(shí)，進(jìn)程的一部分裝入內(nèi)存，一部分放入磁盤緩沖，同步頁表根據(jù)訪問牽涉到的地址，如果是在內(nèi)存中就直接訪問，如果是在磁盤緩沖，就去調(diào)入該頁面頁面裝入策略

請頁式（demandpaging）：地址訪問到哪一個(gè)頁面時(shí)，根據(jù)需要去調(diào)入該頁預(yù)調(diào)式（preparing）：根據(jù)某種算法，預(yù)測到可能用到哪些頁面，預(yù)先調(diào)入若干個(gè)頁面替換策略

有裝入，就有移出，或者叫替換局部：換出的頁面僅限于本進(jìn)程所擁有的頁面全局：可在所有進(jìn)程的頁面進(jìn)行替換頁面分配策略進(jìn)程分配固定的頁面數(shù)目，如果不夠用，就放在磁盤緩沖中進(jìn)程分配的頁面數(shù)目，根據(jù)該進(jìn)程的負(fù)載，動(dòng)態(tài)調(diào)整，如果負(fù)載小，則減少頁面數(shù)目，如果負(fù)載大，則增加頁面數(shù)目比較好的做法是把兩者結(jié)合起來：一開始分配一定數(shù)目的頁面，然后運(yùn)行中，定期檢測進(jìn)程的缺頁頻率，適當(dāng)增加或減少頁面數(shù)目缺頁中斷率：衡量一個(gè)頁面調(diào)度算法的標(biāo)準(zhǔn)相關(guān)概念：頁面替換：當(dāng)主存空間已滿而又要裝入新頁時(shí)，必須按照預(yù)定算法把已經(jīng)在主存中的頁面換出來淘汰（調(diào)度）算法：用來確定被淘汰頁面的算法選用不好的算法的后果抖動(dòng)

剛被淘汰的頁面立即又被調(diào)入，而調(diào)入不久的又隨即被淘汰，如此反復(fù)...，從而導(dǎo)致系統(tǒng)的大部分時(shí)間都花在了頁面調(diào)度上，而不是計(jì)算時(shí)間上定義（缺頁中斷率）：假設(shè)進(jìn)程P需要的總內(nèi)存需求為n頁，而實(shí)際分得的在主存中的頁面為m頁，1≤m≤n。

P成功訪問的次數(shù)為S（Success），不成功訪問（發(fā)生缺頁異常）的次數(shù)為F（Failure），則總的訪問次數(shù)為A=S+F，那么缺頁中斷率

f=F/A影響缺頁中斷率的因素：分得的主存頁面數(shù)目m，越多，中斷率越小頁面大小，頁面越大，缺頁中斷率越小頁面替換算法程序的特性，是否符合局部性下面講頁面替換策略：全局頁面替換策略

所有進(jìn)程的頁面均可以用來替換，而非僅限于進(jìn)程本身的頁面最佳頁面替換算法（OPTimalreplacement，1966，Belady）

思想：淘汰以后不再訪問的頁，或距現(xiàn)在最長時(shí)間以后要訪問的頁面

這個(gè)算法如果能得以實(shí)現(xiàn)，將是最好的替換算法用處

只有理論價(jià)值，無實(shí)用價(jià)值，可用來衡量其他算法與之相比的性能

原因：很難預(yù)知程序?qū)硪L問哪些頁面，不訪問哪些頁面先進(jìn)先出頁面替換算法（FIFO）

思想：總是淘汰最先調(diào)入主存的頁面，或者說淘汰駐留在主存中時(shí)間最長的頁面

該算法實(shí)現(xiàn)較為容易，但效率一般，與OPT算法相比，缺頁中斷率為其的2~3倍，并且在一定程度上違反局部性原則最近最少使用頁面替換算法（LeastRecentlyUsed，LRU）

淘汰在最近一段時(shí)間內(nèi)最久未被訪問的那一頁

由于局部性原則，最近被訪問的頁面，將會(huì)被訪問一段時(shí)間，因此選擇淘汰長時(shí)間沒有被訪問的實(shí)現(xiàn)方式：維護(hù)一個(gè)隊(duì)列，每次訪問一個(gè)頁面，都將其放入隊(duì)尾

隊(duì)首為最近最少使用的頁面，淘汰時(shí)，從隊(duì)列首進(jìn)行選擇第二次