操作系統(tǒng)課件：第8章 Memory Management 存儲(chǔ)管理

Chap8MemoryManagement

存儲(chǔ)管理內(nèi)容背景邏輯與物理地址空間交換連續(xù)分配分頁(yè)分段段頁(yè)式各種內(nèi)存管理方案的比較

總結(jié)背景程序必需放入一個(gè)進(jìn)程，并且送入內(nèi)存才能被執(zhí)行CPU可以直接訪問(wèn)的存儲(chǔ)器只有主存和寄存器寄存器通常可以在一個(gè)（或少于一個(gè)）CPU時(shí)鐘周期內(nèi)完成訪問(wèn)完成主存訪問(wèn)可能需要多個(gè)CPU時(shí)鐘周期Cache位于主存和CPU寄存器之間，協(xié)調(diào)速度差異內(nèi)存保護(hù)需要保證正確的操作指令和數(shù)據(jù)綁定到內(nèi)存編譯時(shí)期（

Compiletime）:如果內(nèi)存位置已知，可生成絕對(duì)代碼；如果開始位置改變，需要重新編譯代碼加載時(shí)期（

Loadtime）:如果存儲(chǔ)位置在編譯時(shí)不知道，則必須生成可重定位（relocatable）代碼執(zhí)行時(shí)期（

Executiontime）:如果進(jìn)程在執(zhí)行時(shí)可以在內(nèi)存中移動(dòng)，則地址綁定可以延遲到運(yùn)行時(shí)。需要硬件對(duì)地址映射的支持（例如基址和限長(zhǎng)寄存器指令和數(shù)據(jù)綁定到內(nèi)存地址可以在三個(gè)不同的階段發(fā)生。地址綁定的三個(gè)階段動(dòng)態(tài)加載(DynamicLoading)例程在調(diào)用之前并不加載更好的內(nèi)存空間利用率；沒(méi)有被使用的例程不被載入。當(dāng)需要大量的代碼來(lái)處理不經(jīng)常發(fā)生的事情時(shí)是非常有用的。不需要操作系統(tǒng)的特別支持，通過(guò)程序設(shè)計(jì)實(shí)現(xiàn)動(dòng)態(tài)鏈接(DynamicLinking)鏈接被推遲到執(zhí)行時(shí)期一小段代碼-存根，用來(lái)定位合適的保留在內(nèi)存中的庫(kù)程序。存根用例程地址來(lái)替換自己，并開始執(zhí)行例程。操作系統(tǒng)需要檢查例程是否在進(jìn)程的內(nèi)存空間邏輯地址和物理地址空間邏輯地址空間的概念同物理地址空間相關(guān)聯(lián)，它是正確內(nèi)存管理的中心。邏輯地址Logicaladdress

—由CPU產(chǎn)生；也叫做虛擬空間。物理地址Physicaladdress—內(nèi)存設(shè)備所讀入的地址邏輯地址和物理地址在編譯時(shí)期和裝入時(shí)期的地址綁定策略是相同的，而在執(zhí)行時(shí)間的地址綁定策略是不同的。地址映射BA=1000LoadA12003456。。1200物理地址空間LoadAdata1data13456源程序LoadA20034560100200編譯連接邏輯地址空間邏輯地址和物理地址內(nèi)存管理單元（MMU）把虛擬地址映射到物理地址的硬件在MMU策略中，基址寄存器中的值在其送入內(nèi)存的時(shí)候被加入到由一個(gè)用戶進(jìn)程所產(chǎn)生的每個(gè)地址中。用戶程序所對(duì)應(yīng)到的是邏輯地址，物理地址對(duì)它從來(lái)都不可見。基址寄存器（base）和界限寄存器（limit）定義了邏輯地址空間基址寄存器和界限寄存器使用重定位寄存器的動(dòng)態(tài)重定位交換（Swapping）一個(gè)進(jìn)程可以暫時(shí)被交換（swap）到內(nèi)存外的一個(gè)備份區(qū)，隨后可以被換回內(nèi)存繼續(xù)執(zhí)行。備份區(qū)—是一個(gè)固定的足夠大的可以容納所有用戶內(nèi)存映像拷貝的快速磁盤；必須提供對(duì)這些內(nèi)存映像的直接訪問(wèn)。交換（續(xù)）滾入，滾出(Rollout,rollin

)—交換由于基于優(yōu)先級(jí)的算法而不同，低優(yōu)先級(jí)的進(jìn)程被換出，這樣高優(yōu)先級(jí)的進(jìn)程可以被裝入和執(zhí)行。交換時(shí)間的主要部分是轉(zhuǎn)移時(shí)間，總的轉(zhuǎn)移時(shí)間直接同交換的內(nèi)存的數(shù)量成比例。在許多系統(tǒng)如：UNIX，Linux，Windows中，可以找到一些被修正過(guò)的交換措施。系統(tǒng)維持一個(gè)就緒隊(duì)列，它包括在備份存儲(chǔ)或在內(nèi)存中準(zhǔn)備運(yùn)行的所有進(jìn)程交換的示意圖連續(xù)內(nèi)存分配主存通常被分為兩部分為操作系統(tǒng)保留的部分，通常用中斷矢量保存在內(nèi)存低端。用戶進(jìn)程保存在內(nèi)存高端。重定位寄存器策略用來(lái)保護(hù)用戶進(jìn)程-同其他進(jìn)程分開，并防止改變的操作系統(tǒng)代碼和數(shù)據(jù)?；芳拇嫫靼钚〉奈锢淼刂分迪揲L(zhǎng)寄存器包含邏輯地址的范圍，每個(gè)邏輯地址必需比限長(zhǎng)寄存器的值小。MMU動(dòng)態(tài)映射邏輯地址基址寄存器和界限寄存器的硬件支持連續(xù)分配（續(xù)）多分區(qū)分配分區(qū)(Hole)—可用的內(nèi)存塊，不同大小的分區(qū)分布在整個(gè)內(nèi)存中。當(dāng)一個(gè)進(jìn)程到來(lái)的時(shí)候，它將從一個(gè)足夠容納它分區(qū)中分配內(nèi)存。操作系統(tǒng)包含以下信息）:a)已分配的分區(qū)b)空的分區(qū)OSprocess5process8process2OSprocess5process2OSprocess5process2OSprocess5process9process2process9process10動(dòng)態(tài)存儲(chǔ)分配問(wèn)題首次適應(yīng)（

First-fit）:分配最先找到的合適的分區(qū)。最佳適應(yīng)（Best-fit）:搜索整個(gè)序列，找到適合條件的最小的分區(qū)進(jìn)行分配。最差適應(yīng)（

Worst-fit）:搜索整個(gè)序列，尋找最大的分區(qū)進(jìn)行分配。怎樣從一個(gè)空的分區(qū)序列中滿足一個(gè)申請(qǐng)需要?在速度和存儲(chǔ)空間的利用上，首次適應(yīng)和最佳適應(yīng)要好于最差適應(yīng)。碎片外碎片–整個(gè)可用內(nèi)存空間可以用來(lái)滿足一個(gè)請(qǐng)求，但它不是連續(xù)的。內(nèi)碎片–分配的內(nèi)存可能比申請(qǐng)的內(nèi)存大一點(diǎn)，這兩者之間的差別是在分區(qū)內(nèi)部，但又不被使用可通過(guò)緊縮來(lái)減少外碎片把一些小的空閑內(nèi)存結(jié)合成一個(gè)大的塊。只有重定位是動(dòng)態(tài)的時(shí)候，才有可能進(jìn)行緊縮，緊縮在執(zhí)行時(shí)期進(jìn)行I/O問(wèn)題當(dāng)I/O的時(shí)候，把工作鎖定在內(nèi)存中。只對(duì)操作系統(tǒng)的緩沖區(qū)進(jìn)行I/O。緊縮例子分頁(yè)（Paging）進(jìn)程的邏輯地址空間可能是不連續(xù)的，如果有可用的物理內(nèi)存，它將分給進(jìn)程。把物理內(nèi)存分成大小固定的塊，稱為幀。（大小為2的冪，512字節(jié)至8192字節(jié)）把邏輯內(nèi)存也分位固定大小的塊，稱為頁(yè)。保留所有空閑幀的記錄。運(yùn)行一個(gè)有N頁(yè)大小的程序，需要找到N個(gè)空的幀來(lái)裝入程序。建立一個(gè)頁(yè)表，把邏輯地址轉(zhuǎn)換為物理地址。存在內(nèi)碎片。產(chǎn)生的地址被分為:頁(yè)號(hào)(p)

–它包含每個(gè)頁(yè)在物理內(nèi)存中的基址，用來(lái)作為頁(yè)表的索引。頁(yè)偏移(d)

–同基址相結(jié)合，用來(lái)確定送入內(nèi)存設(shè)備的物理內(nèi)存地址。對(duì)給定邏輯地址空間2m和頁(yè)大小2npagenumberpageoffsetpdm-nn地址轉(zhuǎn)換機(jī)制分頁(yè)的硬件支持邏輯內(nèi)存和物理內(nèi)存的分頁(yè)模型32-byte內(nèi)存和4-byte的頁(yè)分頁(yè)的例子空閑幀的分配頁(yè)表的實(shí)現(xiàn)頁(yè)表被保存在主存中頁(yè)表基址寄存器(PTBR)指向頁(yè)表頁(yè)表限長(zhǎng)寄存器(PRLR)表明頁(yè)表的長(zhǎng)度在這個(gè)機(jī)制中，每一次的數(shù)據(jù)/指令存取需要兩次內(nèi)存存取，一次是存取頁(yè)表，一次是存取數(shù)據(jù)/指令解決兩次存取的問(wèn)題，是采用小但專用且快速的硬件緩沖，這種緩沖稱為轉(zhuǎn)換表緩沖器(TLB)或聯(lián)想寄存器。聯(lián)想寄存器聯(lián)想寄存器—并行查找

地址轉(zhuǎn)換(A′,A′′)如果A’在聯(lián)想寄存器中，把幀號(hào)取出來(lái)。否則從內(nèi)存中的頁(yè)表中取出幀號(hào)。頁(yè)號(hào)幀號(hào)使用TLB的分頁(yè)硬件有效訪問(wèn)時(shí)間聯(lián)想寄存器的查找需要時(shí)間單位假設(shè)內(nèi)存一次存取需要1微秒命中率—在聯(lián)想寄存器中找到頁(yè)號(hào)的百分比，比率與聯(lián)想寄存器的大小有關(guān)。命中率=有效訪問(wèn)時(shí)間(EAT)

EAT=(1+)+(2+)(1–) =2+–

內(nèi)存保護(hù)內(nèi)存的保護(hù)由與每個(gè)幀相連的保護(hù)位來(lái)實(shí)現(xiàn)。有效-無(wú)效位附在頁(yè)表的每個(gè)表項(xiàng)中:有效”表示相關(guān)的頁(yè)在進(jìn)程的邏輯地址空間，并且是一個(gè)合法的頁(yè)?！盁o(wú)效”表示頁(yè)不在進(jìn)程的邏輯地址空間中。頁(yè)表中的有效位和無(wú)效位共享代碼如果代碼是可重入代碼（只讀），可以在進(jìn)程間共享(如文本編輯器,編譯器,window系統(tǒng)).共享代碼必須出現(xiàn)在所有進(jìn)程的邏輯地址空間的相同位置

私有代碼和數(shù)據(jù)

每個(gè)進(jìn)程保留一個(gè)代碼和數(shù)據(jù)的私有備份存有私有數(shù)據(jù)和代碼的頁(yè)能夠出現(xiàn)在邏輯地址空間的任意位置頁(yè)共享一個(gè)共享頁(yè)的例子層次頁(yè)表哈希頁(yè)表反向頁(yè)表頁(yè)表結(jié)構(gòu)將邏輯地址空間分成多個(gè)頁(yè)表一種簡(jiǎn)單的方法是使用兩級(jí)頁(yè)表層次頁(yè)表兩級(jí)頁(yè)表機(jī)制一個(gè)兩級(jí)分頁(yè)的例子一個(gè)邏輯地址被分為(在4K頁(yè)大小的32位機(jī)器上):一個(gè)20位的頁(yè)號(hào)一個(gè)12位的頁(yè)偏移由于頁(yè)表所在頁(yè)也被分頁(yè)，頁(yè)號(hào)被進(jìn)一步分為:一個(gè)10位的頁(yè)號(hào)一個(gè)10位的頁(yè)偏移因此，邏輯地址表示如下:

p1

是外頁(yè)表的索引，而

p2

是外部頁(yè)表的頁(yè)偏移.pagenumberpageoffsetpip2d101012地址轉(zhuǎn)換機(jī)制一個(gè)兩級(jí)32位分頁(yè)結(jié)構(gòu)的地址轉(zhuǎn)換機(jī)制三級(jí)分頁(yè)機(jī)制通常地址空間>32位虛擬頁(yè)號(hào)被散列到一個(gè)頁(yè)表中。這種頁(yè)表的每一個(gè)條目都包括了一個(gè)鏈表元素，這些元素哈希成同一位置。虛擬頁(yè)號(hào)與鏈表中的每個(gè)元素相比較，找到匹配項(xiàng)。如果匹配，則相應(yīng)的物理幀被取出。哈希頁(yè)表哈希頁(yè)表反向頁(yè)表對(duì)于每個(gè)真正的內(nèi)存頁(yè)或幀有一個(gè)條目。每個(gè)條目保存在真正內(nèi)存位置的頁(yè)的虛擬地址，以及包括擁有這個(gè)頁(yè)的進(jìn)程的信息。減少了需要儲(chǔ)存每個(gè)頁(yè)表的內(nèi)存，但是當(dāng)訪問(wèn)一個(gè)頁(yè)時(shí)，增加了尋找頁(yè)表需要的時(shí)間。使用哈希表來(lái)將查找限制在一個(gè)或少數(shù)幾個(gè)頁(yè)表?xiàng)l目。反置頁(yè)表機(jī)制分段(Segmentation)內(nèi)存管理機(jī)制支持用戶觀點(diǎn)的內(nèi)存。一個(gè)程序是一些段的集合，一個(gè)段是一個(gè)邏輯單位，如:

mainprogram, procedure, function, localvariables,globalvariables, commonblock, stack, symboltable,arrays分段的邏輯視圖13241423用戶空間物理內(nèi)存空間分段機(jī)制一個(gè)邏輯地址是兩個(gè)向量的集合: <segment-number,offset>,段表-映射二維物理地址，每個(gè)表項(xiàng)包括:基址-包括內(nèi)存中段物理地址的起始地址。限長(zhǎng)-指定段的長(zhǎng)度。段表基址寄存器(STBR)指向段表在內(nèi)存中的地址。段表限長(zhǎng)寄存器(STLR)表明被一個(gè)程序所使用的段的數(shù)目。

segmentnumbersislegalifs<STLR.分段機(jī)制（續(xù)）重定位動(dòng)態(tài)由段表來(lái)執(zhí)行共享共享的段同樣的段號(hào)分配首先/最佳適配外碎片分段機(jī)制（續(xù)）保護(hù)，每個(gè)段表的表項(xiàng)有: