操作系統(tǒng)內(nèi)存管理-課件

內(nèi)存管理內(nèi)存管理1目的詳細(xì)描述內(nèi)存硬件的各種組織方法討論各種內(nèi)存管理技術(shù)，包括分頁(yè)和分段詳細(xì)描述IntelPentium芯片，它支持純分段和帶分頁(yè)的分段目的詳細(xì)描述內(nèi)存硬件的各種組織方法2背景為了運(yùn)行程序必須把程序從磁盤(pán)載入到內(nèi)存內(nèi)存和寄存器是CPU唯一能直接訪問(wèn)的存儲(chǔ)器寄存器的訪問(wèn)時(shí)間vs內(nèi)存的訪問(wèn)時(shí)間緩存為了確保正常運(yùn)行必須保護(hù)內(nèi)存背景為了運(yùn)行程序必須把程序從磁盤(pán)載入到內(nèi)存3首先討論：符號(hào)內(nèi)存地址到實(shí)際物理地址的綁定邏輯地址與物理地址的區(qū)別動(dòng)態(tài)裝載、動(dòng)態(tài)鏈接代碼及共享庫(kù)首先討論：4在計(jì)算機(jī)科學(xué)中，庫(kù)是用于開(kāi)發(fā)軟件的子程序集合。庫(kù)和可執(zhí)行文件的區(qū)別是，庫(kù)不是獨(dú)立程序，他們是向其他程序提供服務(wù)的代碼。庫(kù)鏈接是指把一個(gè)或多個(gè)庫(kù)包括到程序中，有兩種鏈接形式：靜態(tài)鏈接和動(dòng)態(tài)鏈接，相應(yīng)的，前者鏈接的庫(kù)叫做靜態(tài)庫(kù)后者的叫做動(dòng)態(tài)庫(kù)。在計(jì)算機(jī)科學(xué)中，庫(kù)是用于開(kāi)發(fā)軟件的子程序集合。庫(kù)和可5靜態(tài)鏈接是由鏈接器在鏈接時(shí)將庫(kù)的內(nèi)容加入到可執(zhí)行程序中的做法。鏈接器是一個(gè)獨(dú)立程序，將一個(gè)或多個(gè)庫(kù)或目標(biāo)文件（先前由編譯器或匯編器生成）鏈接到一塊生成可執(zhí)行程序。靜態(tài)鏈接的最大缺點(diǎn)是生成的可執(zhí)行文件太大，需要更多的系統(tǒng)資源，在裝入內(nèi)存時(shí)也會(huì)消耗更多的時(shí)間。靜態(tài)鏈接是由鏈接器在鏈接時(shí)將庫(kù)的內(nèi)容加入到可執(zhí)行程序中的做法6動(dòng)態(tài)鏈接，在可執(zhí)行文件裝載時(shí)或運(yùn)行時(shí)，由操作系統(tǒng)的裝載程序加載庫(kù)。大多數(shù)操作系統(tǒng)將解析外部引用（比如庫(kù)）作為加載過(guò)程的一部分。動(dòng)態(tài)鏈接，在可執(zhí)行文件裝載時(shí)或運(yùn)行時(shí)，由操作系統(tǒng)的裝載程序加7基地址寄存器和界限地址寄存器一個(gè)進(jìn)程使用的內(nèi)存地址范圍是由一對(duì)基地址寄存器和界限地址寄存器來(lái)定義基地址寄存器和界限地址寄存器一個(gè)進(jìn)程使用的內(nèi)存地址范圍是由一8一個(gè)用戶程序的多步驟處理一個(gè)用戶程序的多步驟處理9地址綁定地址綁定是從一個(gè)地址空間到另一個(gè)地址空間的映射將指令與數(shù)據(jù)綁定到內(nèi)存，有以下幾種情況不知道駐留地址地址綁定地址綁定是從一個(gè)地址空間到另一個(gè)地址空間的映射不知道10邏輯地址空間和物理地址空間邏輯地址：CPU所生成的地址–(虛擬地址)物理地址：從內(nèi)存單元所看到的地址綁定內(nèi)存管理單元(MMU)邏輯地址空間和物理地址空間邏輯地址：CPU所生成的地址–(11內(nèi)存管理單元（MMU）映射虛擬地址為物理地址的硬件設(shè)備

用戶進(jìn)程所生成的地址在送交內(nèi)存之前，都將加上重定位寄存器（基地址寄存器）的值

用戶程序決不會(huì)看到真正的物理地址內(nèi)存管理單元（MMU）映射虛擬地址為物理地址的硬件設(shè)備

12庫(kù)的鏈接及加載靜態(tài)鏈接動(dòng)態(tài)鏈接（dynamiclink）動(dòng)態(tài)加載（dynamicloading）庫(kù)的鏈接及加載靜態(tài)鏈接13動(dòng)態(tài)加載直到被調(diào)用之前，程序不會(huì)被載入到內(nèi)存，即加載延遲到運(yùn)行時(shí)優(yōu)點(diǎn)不使用的程序不會(huì)載入到內(nèi)存，既而內(nèi)存使用率高適合用戶用大量代碼來(lái)操作不常發(fā)生事件時(shí)不需要操作系統(tǒng)的特別支持，由程序員來(lái)設(shè)計(jì)動(dòng)態(tài)加載直到被調(diào)用之前，程序不會(huì)被載入到內(nèi)存，即加載延遲到運(yùn)14動(dòng)態(tài)鏈接鏈接延遲到執(zhí)行時(shí)小程序,stub（存根）,用來(lái)定位適當(dāng)?shù)膬?nèi)存駐留庫(kù)程序，或如果該程序不在內(nèi)存時(shí)應(yīng)如何裝入庫(kù)存根會(huì)用子程序地址來(lái)替換自己，并開(kāi)始子程序存根首先檢查所需子程序是否在內(nèi)存中，如果不在，就將子程序裝入內(nèi)存。動(dòng)態(tài)鏈接通常適用于系統(tǒng)庫(kù)需要操作系統(tǒng)的幫助動(dòng)態(tài)鏈接鏈接延遲到執(zhí)行時(shí)152.交換（swapping)進(jìn)程可以暫時(shí)從內(nèi)存中交換到備份存儲(chǔ)(backingstore)上，當(dāng)需要再次執(zhí)行時(shí)再調(diào)回到內(nèi)存backingstore–通常是快速磁盤(pán)優(yōu)先級(jí)調(diào)度算法中使用滾出（rollout）,滾入（rollin）交換時(shí)間轉(zhuǎn)移時(shí)間，而轉(zhuǎn)移時(shí)間與交換內(nèi)存空間量成正比問(wèn)：將交換出的進(jìn)程再交換（調(diào)回）回來(lái)的時(shí)候，應(yīng)調(diào)回哪個(gè)內(nèi)存空間（編譯時(shí)，加載時(shí)，執(zhí)行時(shí)）2.交換（swapping)進(jìn)程可以暫時(shí)從內(nèi)存中交換到備份16操作系統(tǒng)內(nèi)存管理-課件17連續(xù)分配內(nèi)存通常分為兩個(gè)區(qū)域：一個(gè)用于駐留操作系統(tǒng)，常與中斷向量一起放在低內(nèi)存另一個(gè)用于用戶進(jìn)程，常放在高內(nèi)存。單分區(qū)分配方法（Single-partitionallocation）重定位寄存器方案用來(lái)保護(hù)用戶進(jìn)程之間，用戶進(jìn)程與操作系統(tǒng)之間不會(huì)相互修改代碼與數(shù)據(jù)重定位寄存器包含了最小的物理地址；界限寄存器包含了邏輯地址的范圍，每個(gè)邏輯地址必須小于界限寄存器連續(xù)分配內(nèi)存通常分為兩個(gè)區(qū)域：18重定位和界限寄存器的硬件支持重定位和界限寄存器的硬件支持19多分區(qū)分配方法孔（Hole）：一塊可用內(nèi)存稱(chēng)為孔。不同大小的孔分布在內(nèi)存的不同地方。當(dāng)有新進(jìn)程需要內(nèi)存時(shí)，為該進(jìn)程查找足夠大的孔。操作系統(tǒng)維護(hù)的信息包括：已分配分區(qū)空閑分區(qū)（hole）多分區(qū)分配方法20動(dòng)態(tài)存儲(chǔ)分配問(wèn)題根據(jù)一組空閑孔來(lái)分配大小為n的請(qǐng)求。首次適應(yīng)（First-fit）最佳適應(yīng)（Best-fit）最差適應(yīng)（Worst-fit）First-fit和best-fit在分配速度及存儲(chǔ)效率上優(yōu)于Worst-fit動(dòng)態(tài)存儲(chǔ)分配問(wèn)題根據(jù)一組空閑孔來(lái)分配大小為n的請(qǐng)求。21碎片（Fragmentation）外部碎片內(nèi)部碎片緊縮（compaction）：用來(lái)降低外部碎片移動(dòng)內(nèi)存內(nèi)容，以便所有空閑空間合并成一整塊。如果重定位是動(dòng)態(tài)的，是在運(yùn)行時(shí)進(jìn)行的，那么就能采用緊縮另一種可能解決外部碎片問(wèn)題的方法是允許物理地址空間為非連續(xù)，這樣只要有物理內(nèi)存就可為進(jìn)程分配。分頁(yè)分段碎片（Fragmentation）外部碎片22分頁(yè)(Paging)一個(gè)進(jìn)程的物理地址可以是非連續(xù)的將物理內(nèi)存分成固定大小的塊，稱(chēng)為幀（frame）將邏輯內(nèi)存分為同樣大小的塊，稱(chēng)為頁(yè)（page）跟蹤所有的空閑幀建立頁(yè)表用來(lái)將邏輯地址轉(zhuǎn)換為物理地址。內(nèi)部碎片分頁(yè)(Paging)一個(gè)進(jìn)程的物理地址可以是非連續(xù)的23地址轉(zhuǎn)換方法CPU生成的地址分成以下兩部分頁(yè)號(hào)(p)：頁(yè)號(hào)作為頁(yè)表中的索引。頁(yè)表中包含每頁(yè)所在物理內(nèi)存的基地址。頁(yè)偏移(d)：與頁(yè)的基地址組合就形成了物理地址，就可送交物理單元。地址轉(zhuǎn)換方法CPU生成的地址分成以下兩部分24地址轉(zhuǎn)換體系結(jié)構(gòu)地址轉(zhuǎn)換體系結(jié)構(gòu)25邏輯內(nèi)存和物理內(nèi)存的分頁(yè)模型邏輯內(nèi)存和物理內(nèi)存的分頁(yè)模型26分頁(yè)示例分頁(yè)示例27空閑幀空閑幀28頁(yè)表的實(shí)現(xiàn)頁(yè)表保存在內(nèi)存中頁(yè)表基寄存器（PTBR）指向頁(yè)表頁(yè)表長(zhǎng)度寄存器（PTLR）指示頁(yè)表的大小在這種方式下，每次數(shù)據(jù)/指令的訪問(wèn)需要訪問(wèn)兩次內(nèi)存。一次訪問(wèn)頁(yè)表，另一次訪問(wèn)數(shù)據(jù)/指令兩次內(nèi)存訪問(wèn)問(wèn)題可以用特別的快速查找硬件緩沖（稱(chēng)為關(guān)聯(lián)內(nèi)存或翻譯后備緩沖器）來(lái)解決。頁(yè)表的實(shí)現(xiàn)頁(yè)表保存在內(nèi)存中29關(guān)聯(lián)存儲(chǔ)關(guān)聯(lián)內(nèi)存－并行搜索當(dāng)關(guān)聯(lián)內(nèi)存根據(jù)給定值查找時(shí)，它會(huì)同時(shí)與所有鍵進(jìn)行比較。如果找到條目，那么就得到相應(yīng)的值域地址轉(zhuǎn)換（A’,A’’）如果A’在關(guān)聯(lián)寄存器中，則直接取出其對(duì)應(yīng)的frame#否則從內(nèi)存中的頁(yè)表當(dāng)中得到frame#Page#Frame#關(guān)聯(lián)存儲(chǔ)關(guān)聯(lián)內(nèi)存－并行搜索Page#Frame#30帶TLB的分頁(yè)硬件帶TLB的分頁(yè)硬件31內(nèi)存保護(hù)內(nèi)存保護(hù)通過(guò)與每個(gè)幀關(guān)聯(lián)有保護(hù)位來(lái)實(shí)現(xiàn)。可讀、可寫(xiě)、只可讀還有一位與頁(yè)表中的每一條目相關(guān)聯(lián)，稱(chēng)為有效－無(wú)效位一個(gè)進(jìn)程很少會(huì)使用其所有的地址空間。事實(shí)上，許多進(jìn)程只使用一小部分可用的地址空間。如對(duì)于14位地址空間（0-16383）的系統(tǒng)，有一個(gè)程序，其地址空間為0-10648該位有效時(shí)表示相關(guān)的頁(yè)在進(jìn)程的邏輯地址空間內(nèi)，因此是合法的頁(yè)。該位無(wú)效時(shí)表示相關(guān)的頁(yè)不在進(jìn)程的邏輯地址空間內(nèi)。內(nèi)存保護(hù)內(nèi)存保護(hù)通過(guò)與每個(gè)幀關(guān)聯(lián)有保護(hù)位來(lái)實(shí)現(xiàn)。32頁(yè)表中的有效－無(wú)效位頁(yè)表中的有效－無(wú)效位33頁(yè)表結(jié)構(gòu)層次化分頁(yè)Hash頁(yè)表反向頁(yè)表頁(yè)表結(jié)構(gòu)層次化分頁(yè)34層次化分頁(yè)將邏輯地址空間分成多個(gè)頁(yè)表一種簡(jiǎn)單的方法是兩層分頁(yè)法層次化分頁(yè)將邏輯地址空間分成多個(gè)頁(yè)表35兩層分頁(yè)方法實(shí)例邏輯地址（32位機(jī)器，頁(yè)大小為4K）分成以下兩部分：頁(yè)號(hào)（20位）頁(yè)偏移（12位）頁(yè)表又分成頁(yè)，所以頁(yè)號(hào)又進(jìn)一步分成：10位頁(yè)號(hào)10位頁(yè)偏移因此，邏輯地址表示如下兩層分頁(yè)方法實(shí)例邏輯地址（32位機(jī)器，頁(yè)大小為4K）分成以下36操作系統(tǒng)內(nèi)存管理-課件37兩級(jí)頁(yè)表方法示意兩級(jí)頁(yè)表方法示意38地址轉(zhuǎn)換方法地址轉(zhuǎn)換方法39Hash頁(yè)表處理超過(guò)32位地址空間的常用方法是使用Hash頁(yè)表。虛擬地址中的虛擬頁(yè)號(hào)被放入hash頁(yè)表中。hash頁(yè)表的每一條目都包括一個(gè)鏈接組的元素，這些元素hash成同一位置（碰撞）。虛擬頁(yè)號(hào)與鏈表中的每一個(gè)元素的第一個(gè)域相比較。如果匹配，那么對(duì)應(yīng)的幀碼就用來(lái)形成位置地址。如果不匹配，那么就對(duì)鏈表中的下一個(gè)域進(jìn)行頁(yè)碼比較。Hash頁(yè)表處理超過(guò)32位地址空間的常用方法是使用Hash頁(yè)40Hash頁(yè)表實(shí)例Hash頁(yè)表實(shí)例41反向頁(yè)表反向頁(yè)表對(duì)于每個(gè)真正的內(nèi)存頁(yè)或幀才有一個(gè)條目。每個(gè)條目包含保存在真正內(nèi)存位置的頁(yè)的虛擬地址，以及擁有該頁(yè)的進(jìn)程的信息。雖然這種方案減低了存儲(chǔ)每個(gè)頁(yè)表所需要的內(nèi)存空間，但是當(dāng)引用頁(yè)時(shí)它增加了查找頁(yè)表所需要的時(shí)間?？墒褂胔ash表來(lái)減少查找的次數(shù)反向頁(yè)表反向頁(yè)表對(duì)于每個(gè)真正的內(nèi)存頁(yè)或幀才有一個(gè)條目。42反向頁(yè)表結(jié)構(gòu)反向頁(yè)表結(jié)構(gòu)43共享頁(yè)共享代碼可以在進(jìn)程之間共享共同代碼（只讀的，可重入的）（如文本編輯器、編譯器、Windows系統(tǒng)）共享代碼必須出現(xiàn)在所有進(jìn)程邏輯地址的同一位置私有代碼和數(shù)據(jù)每個(gè)進(jìn)程保留了代碼與數(shù)據(jù)的獨(dú)立的拷貝私有代碼和數(shù)據(jù)頁(yè)可以出現(xiàn)在邏輯地址空間的任何地方。共享頁(yè)共享代碼44共享分頁(yè)實(shí)例共享分頁(yè)實(shí)例45分段支持用戶觀點(diǎn)的內(nèi)存管理方法程序是若干段的集合主程序子程序函數(shù)方法對(duì)象局部變量，全局變量堆棧符號(hào)表，數(shù)組分段支持用戶觀點(diǎn)的內(nèi)存管理方法46用戶角度的程序用戶角度的程序47段的邏輯視角段的邏輯視角48段的體系結(jié)構(gòu)邏輯地址由兩個(gè)元素組成<段號(hào)，偏移>段表：將二維的用戶定義地址映射為一維物理地址。段表的每個(gè)條目都有段基地址和段界限?；刂罚喊蔚钠鹗嫉刂方缦蓿褐付ǘ蔚拈L(zhǎng)度段表基地址寄存器（STBR）指向內(nèi)存中的段表的位置段表長(zhǎng)度寄存器（STLR）指示程序所用的段的個(gè)數(shù)段號(hào)S小于STLR的時(shí)候才是有效的段的體系結(jié)構(gòu)邏輯地址由兩個(gè)元素組成49段硬件段硬件50分段實(shí)例分段實(shí)例51段共享段共享52問(wèn)題外部碎片問(wèn)題外部碎片53帶分頁(yè)的分段MULTICS采用帶分頁(yè)的分段方法來(lái)解決外部碎片的問(wèn)題與純粹的分段式內(nèi)存管理不同，段表的條目包含的不是段的基地址，而是該段的頁(yè)表的基地址帶分頁(yè)的分段MULTICS采用帶分頁(yè)的分段方法來(lái)解決外部碎片54內(nèi)存管理內(nèi)存管理55目的詳細(xì)描述內(nèi)存硬件的各種組織方法討論各種內(nèi)存管理技術(shù)，包括分頁(yè)和分段詳細(xì)描述IntelPentium芯片，它支持純分段和帶分頁(yè)的分段目的詳細(xì)描述內(nèi)存硬件的各種組織方法56背景為了運(yùn)行程序必須把程序從磁盤(pán)載入到內(nèi)存內(nèi)存和寄存器是CPU唯一能直接訪問(wèn)的存儲(chǔ)器寄存器的訪問(wèn)時(shí)間vs內(nèi)存的訪問(wèn)時(shí)間緩存為了確保正常運(yùn)行必須保護(hù)內(nèi)存背景為了運(yùn)行程序必須把程序從磁盤(pán)載入到內(nèi)存57首先討論：符號(hào)內(nèi)存地址到實(shí)際物理地址的綁定邏輯地址與物理地址的區(qū)別動(dòng)態(tài)裝載、動(dòng)態(tài)鏈接代碼及共享庫(kù)首先討論：58在計(jì)算機(jī)科學(xué)中，庫(kù)是用于開(kāi)發(fā)軟件的子程序集合。庫(kù)和可執(zhí)行文件的區(qū)別是，庫(kù)不是獨(dú)立程序，他們是向其他程序提供服務(wù)的代碼。庫(kù)鏈接是指把一個(gè)或多個(gè)庫(kù)包括到程序中，有兩種鏈接形式：靜態(tài)鏈接和動(dòng)態(tài)鏈接，相應(yīng)的，前者鏈接的庫(kù)叫做靜態(tài)庫(kù)后者的叫做動(dòng)態(tài)庫(kù)。在計(jì)算機(jī)科學(xué)中，庫(kù)是用于開(kāi)發(fā)軟件的子程序集合。庫(kù)和可59靜態(tài)鏈接是由鏈接器在鏈接時(shí)將庫(kù)的內(nèi)容加入到可執(zhí)行程序中的做法。鏈接器是一個(gè)獨(dú)立程序，將一個(gè)或多個(gè)庫(kù)或目標(biāo)文件（先前由編譯器或匯編器生成）鏈接到一塊生成可執(zhí)行程序。靜態(tài)鏈接的最大缺點(diǎn)是生成的可執(zhí)行文件太大，需要更多的系統(tǒng)資源，在裝入內(nèi)存時(shí)也會(huì)消耗更多的時(shí)間。靜態(tài)鏈接是由鏈接器在鏈接時(shí)將庫(kù)的內(nèi)容加入到可執(zhí)行程序中的做法60動(dòng)態(tài)鏈接，在可執(zhí)行文件裝載時(shí)或運(yùn)行時(shí)，由操作系統(tǒng)的裝載程序加載庫(kù)。大多數(shù)操作系統(tǒng)將解析外部引用（比如庫(kù)）作為加載過(guò)程的一部分。動(dòng)態(tài)鏈接，在可執(zhí)行文件裝載時(shí)或運(yùn)行時(shí)，由操作系統(tǒng)的裝載程序加61基地址寄存器和界限地址寄存器一個(gè)進(jìn)程使用的內(nèi)存地址范圍是由一對(duì)基地址寄存器和界限地址寄存器來(lái)定義基地址寄存器和界限地址寄存器一個(gè)進(jìn)程使用的內(nèi)存地址范圍是由一62一個(gè)用戶程序的多步驟處理一個(gè)用戶程序的多步驟處理63地址綁定地址綁定是從一個(gè)地址空間到另一個(gè)地址空間的映射將指令與數(shù)據(jù)綁定到內(nèi)存，有以下幾種情況不知道駐留地址地址綁定地址綁定是從一個(gè)地址空間到另一個(gè)地址空間的映射不知道64邏輯地址空間和物理地址空間邏輯地址：CPU所生成的地址–(虛擬地址)物理地址：從內(nèi)存單元所看到的地址綁定內(nèi)存管理單元(MMU)邏輯地址空間和物理地址空間邏輯地址：CPU所生成的地址–(65內(nèi)存管理單元（MMU）映射虛擬地址為物理地址的硬件設(shè)備

用戶進(jìn)程所生成的地址在送交內(nèi)存之前，都將加上重定位寄存器（基地址寄存器）的值

用戶程序決不會(huì)看到真正的物理地址內(nèi)存管理單元（MMU）映射虛擬地址為物理地址的硬件設(shè)備

66庫(kù)的鏈接及加載靜態(tài)鏈接動(dòng)態(tài)鏈接（dynamiclink）動(dòng)態(tài)加載（dynamicloading）庫(kù)的鏈接及加載靜態(tài)鏈接67動(dòng)態(tài)加載直到被調(diào)用之前，程序不會(huì)被載入到內(nèi)存，即加載延遲到運(yùn)行時(shí)優(yōu)點(diǎn)不使用的程序不會(huì)載入到內(nèi)存，既而內(nèi)存使用率高適合用戶用大量代碼來(lái)操作不常發(fā)生事件時(shí)不需要操作系統(tǒng)的特別支持，由程序員來(lái)設(shè)計(jì)動(dòng)態(tài)加載直到被調(diào)用之前，程序不會(huì)被載入到內(nèi)存，即加載延遲到運(yùn)68動(dòng)態(tài)鏈接鏈接延遲到執(zhí)行時(shí)小程序,stub（存根）,用來(lái)定位適當(dāng)?shù)膬?nèi)存駐留庫(kù)程序，或如果該程序不在內(nèi)存時(shí)應(yīng)如何裝入庫(kù)存根會(huì)用子程序地址來(lái)替換自己，并開(kāi)始子程序存根首先檢查所需子程序是否在內(nèi)存中，如果不在，就將子程序裝入內(nèi)存。動(dòng)態(tài)鏈接通常適用于系統(tǒng)庫(kù)需要操作系統(tǒng)的幫助動(dòng)態(tài)鏈接鏈接延遲到執(zhí)行時(shí)692.交換（swapping)進(jìn)程可以暫時(shí)從內(nèi)存中交換到備份存儲(chǔ)(backingstore)上，當(dāng)需要再次執(zhí)行時(shí)再調(diào)回到內(nèi)存backingstore–通常是快速磁盤(pán)優(yōu)先級(jí)調(diào)度算法中使用滾出（rollout）,滾入（rollin）交換時(shí)間轉(zhuǎn)移時(shí)間，而轉(zhuǎn)移時(shí)間與交換內(nèi)存空間量成正比問(wèn)：將交換出的進(jìn)程再交換（調(diào)回）回來(lái)的時(shí)候，應(yīng)調(diào)回哪個(gè)內(nèi)存空間（編譯時(shí)，加載時(shí)，執(zhí)行時(shí)）2.交換（swapping)進(jìn)程可以暫時(shí)從內(nèi)存中交換到備份70操作系統(tǒng)內(nèi)存管理-課件71連續(xù)分配內(nèi)存通常分為兩個(gè)區(qū)域：一個(gè)用于駐留操作系統(tǒng)，常與中斷向量一起放在低內(nèi)存另一個(gè)用于用戶進(jìn)程，常放在高內(nèi)存。單分區(qū)分配方法（Single-partitionallocation）重定位寄存器方案用來(lái)保護(hù)用戶進(jìn)程之間，用戶進(jìn)程與操作系統(tǒng)之間不會(huì)相互修改代碼與數(shù)據(jù)重定位寄存器包含了最小的物理地址；界限寄存器包含了邏輯地址的范圍，每個(gè)邏輯地址必須小于界限寄存器連續(xù)分配內(nèi)存通常分為兩個(gè)區(qū)域：72重定位和界限寄存器的硬件支持重定位和界限寄存器的硬件支持73多分區(qū)分配方法孔（Hole）：一塊可用內(nèi)存稱(chēng)為孔。不同大小的孔分布在內(nèi)存的不同地方。當(dāng)有新進(jìn)程需要內(nèi)存時(shí)，為該進(jìn)程查找足夠大的孔。操作系統(tǒng)維護(hù)的信息包括：已分配分區(qū)空閑分區(qū)（hole）多分區(qū)分配方法74動(dòng)態(tài)存儲(chǔ)分配問(wèn)題根據(jù)一組空閑孔來(lái)分配大小為n的請(qǐng)求。首次適應(yīng)（First-fit）最佳適應(yīng)（Best-fit）最差適應(yīng)（Worst-fit）First-fit和best-fit在分配速度及存儲(chǔ)效率上優(yōu)于Worst-fit動(dòng)態(tài)存儲(chǔ)分配問(wèn)題根據(jù)一組空閑孔來(lái)分配大小為n的請(qǐng)求。75碎片（Fragmentation）外部碎片內(nèi)部碎片緊縮（compaction）：用來(lái)降低外部碎片移動(dòng)內(nèi)存內(nèi)容，以便所有空閑空間合并成一整塊。如果重定位是動(dòng)態(tài)的，是在運(yùn)行時(shí)進(jìn)行的，那么就能采用緊縮另一種可能解決外部碎片問(wèn)題的方法是允許物理地址空間為非連續(xù)，這樣只要有物理內(nèi)存就可為進(jìn)程分配。分頁(yè)分段碎片（Fragmentation）外部碎片76分頁(yè)(Paging)一個(gè)進(jìn)程的物理地址可以是非連續(xù)的將物理內(nèi)存分成固定大小的塊，稱(chēng)為幀（frame）將邏輯內(nèi)存分為同樣大小的塊，稱(chēng)為頁(yè)（page）跟蹤所有的空閑幀建立頁(yè)表用來(lái)將邏輯地址轉(zhuǎn)換為物理地址。內(nèi)部碎片分頁(yè)(Paging)一個(gè)進(jìn)程的物理地址可以是非連續(xù)的77地址轉(zhuǎn)換方法CPU生成的地址分成以下兩部分頁(yè)號(hào)(p)：頁(yè)號(hào)作為頁(yè)表中的索引。頁(yè)表中包含每頁(yè)所在物理內(nèi)存的基地址。頁(yè)偏移(d)：與頁(yè)的基地址組合就形成了物理地址，就可送交物理單元。地址轉(zhuǎn)換方法CPU生成的地址分成以下兩部分78地址轉(zhuǎn)換體系結(jié)構(gòu)地址轉(zhuǎn)換體系結(jié)構(gòu)79邏輯內(nèi)存和物理內(nèi)存的分頁(yè)模型邏輯內(nèi)存和物理內(nèi)存的分頁(yè)模型80分頁(yè)示例分頁(yè)示例81空閑幀空閑幀82頁(yè)表的實(shí)現(xiàn)頁(yè)表保存在內(nèi)存中頁(yè)表基寄存器（PTBR）指向頁(yè)表頁(yè)表長(zhǎng)度寄存器（PTLR）指示頁(yè)表的大小在這種方式下，每次數(shù)據(jù)/指令的訪問(wèn)需要訪問(wèn)兩次內(nèi)存。一次訪問(wèn)頁(yè)表，另一次訪問(wèn)數(shù)據(jù)/指令兩次內(nèi)存訪問(wèn)問(wèn)題可以用特別的快速查找硬件緩沖（稱(chēng)為關(guān)聯(lián)內(nèi)存或翻譯后備緩沖器）來(lái)解決。頁(yè)表的實(shí)現(xiàn)頁(yè)表保存在內(nèi)存中83關(guān)聯(lián)存儲(chǔ)關(guān)聯(lián)內(nèi)存－并行搜索當(dāng)關(guān)聯(lián)內(nèi)存根據(jù)給定值查找時(shí)，它會(huì)同時(shí)與所有鍵進(jìn)行比較。如果找到條目，那么就得到相應(yīng)的值域地址轉(zhuǎn)換（A’,A’’）如果A’在關(guān)聯(lián)寄存器中，則直接取出其對(duì)應(yīng)的frame#否則從內(nèi)存中的頁(yè)表當(dāng)中得到frame#Page#Frame#關(guān)聯(lián)存儲(chǔ)關(guān)聯(lián)內(nèi)存－并行搜索Page#Frame#84帶TLB的分頁(yè)硬件帶TLB的分頁(yè)硬件85內(nèi)存保護(hù)內(nèi)存保護(hù)通過(guò)與每個(gè)幀關(guān)聯(lián)有保護(hù)位來(lái)實(shí)現(xiàn)?？勺x、可寫(xiě)、只可讀還有一位與頁(yè)表中的每一條目相關(guān)聯(lián)，稱(chēng)為有效－無(wú)效位一個(gè)進(jìn)程很少會(huì)使用其所有的地址空間。事實(shí)上，許多進(jìn)程只使用一小部分可用的地址空間。如對(duì)于14位地址空間（0-16383）的系統(tǒng)，有一個(gè)程序，其地址空間為0-10648該位有效時(shí)表示相關(guān)的頁(yè)在進(jìn)程的邏輯地址空間內(nèi)，因此是合法的頁(yè)。該位無(wú)效時(shí)表示相關(guān)的頁(yè)不在進(jìn)程的邏輯地址空間內(nèi)。內(nèi)存保護(hù)內(nèi)存保護(hù)通過(guò)與每個(gè)幀關(guān)聯(lián)有保護(hù)位來(lái)實(shí)現(xiàn)。86頁(yè)表中的有效－無(wú)效位頁(yè)表中的有效－無(wú)效位87頁(yè)表結(jié)構(gòu)層次化分頁(yè)Hash頁(yè)表反向頁(yè)表頁(yè)表結(jié)構(gòu)層次化分頁(yè)88層次化分頁(yè)將邏輯地址空間分成多個(gè)頁(yè)表一種簡(jiǎn)單的方法是兩層分頁(yè)法層次化分頁(yè)將邏輯地址空間分成多個(gè)頁(yè)表89兩層分頁(yè)方法實(shí)例邏輯地址（32位機(jī)器，頁(yè)大小為4K）分成以下兩部分：頁(yè)號(hào)（20位）頁(yè)偏移（12位）頁(yè)表又分成頁(yè)，所以頁(yè)號(hào)又進(jìn)一步分成：10位頁(yè)號(hào)10位頁(yè)偏移因此，邏輯地址表示如下兩層分頁(yè)方法實(shí)例邏輯地址（32位機(jī)器，頁(yè)大小為4K）分成以下90操作系統(tǒng)內(nèi)存管理-課件91兩級(jí)頁(yè)表方法示意兩級(jí)頁(yè)表方法示意92地址轉(zhuǎn)換方法地址轉(zhuǎn)換方法93Hash頁(yè)表處理超過(guò)32位地址空間的常用方法是使用Hash頁(yè)表。虛擬地址中的虛擬頁(yè)號(hào)被放入hash頁(yè)表中。hash頁(yè)表的每一條目都包括一個(gè)鏈接組的元素，這些元素hash成同一位