Chapter-03(存儲(chǔ)管理)

1、1存儲(chǔ)管理第 3 章3.1 無(wú)存儲(chǔ)器抽象3.2 一種存儲(chǔ)器抽象：地址空間3.3 虛擬內(nèi)存3.4 頁(yè)面置換算法3.5 分頁(yè)系統(tǒng)中的設(shè)計(jì)問(wèn)題3.6 有關(guān)實(shí)現(xiàn)的問(wèn)題3.7 分段2存儲(chǔ)管理 每個(gè)程序員都?jí)粝氲膬?nèi)存： 容量無(wú)限大 速度無(wú)限快 永久性 分層存儲(chǔ)器體系 快速、昂貴且易失性的高速緩存（ cache ） 速度和價(jià)格都適中，且同樣易失的內(nèi)存（main memory） 低速、廉價(jià)、非易失性的磁盤存儲(chǔ)（disk storage ） 操作系統(tǒng)中管理分層存儲(chǔ)器體系的部分稱為存儲(chǔ)管理器3無(wú)存儲(chǔ)器抽象內(nèi)存組織的三種簡(jiǎn)單方法- 在只有操作系統(tǒng)和一個(gè)用戶進(jìn)程的情形下4在不使用內(nèi)存抽象的情況下運(yùn)行多道程序 保護(hù)鍵技

2、術(shù) 靜態(tài)重定位技術(shù)5一種存儲(chǔ)器抽象：地址空間 保護(hù)和重定位 內(nèi)存抽象：地址空間 是一個(gè)進(jìn)程可用于尋址內(nèi)存的一套地址集合 基址寄存器與界限寄存器（動(dòng)態(tài)重定位） 易提供私有地址空間 需要頻繁的進(jìn)行加法和比較運(yùn)算6交換技術(shù)（1） 處理內(nèi)存超載的兩種方法： 交換技術(shù) 虛擬內(nèi)存7交換技術(shù) (2)內(nèi)存分配情況隨著 進(jìn)程進(jìn)入內(nèi)存 進(jìn)程離開內(nèi)存陰影區(qū)域表示未使用的內(nèi)存操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)時(shí)間8Swapping (3) 為可能增長(zhǎng)的數(shù)據(jù)段預(yù)留空間 為可能增長(zhǎng)的數(shù)據(jù)段和堆棧段預(yù)留空間操作系統(tǒng)操作系統(tǒng)A程序A數(shù)據(jù)A堆棧B堆棧B數(shù)據(jù)B程序?yàn)樵鲩L(zhǎng)預(yù)留的空間為增長(zhǎng)預(yù)留的空間為增長(zhǎng)預(yù)留的

3、空間為增長(zhǎng)預(yù)留的空間實(shí)際使用的空間實(shí)際使用的空間9空閑內(nèi)存管理使用位圖的存儲(chǔ)管理 一段有5個(gè)進(jìn)程和3個(gè)空閑區(qū)的內(nèi)存 刻度表示內(nèi)存分配的單元 陰影區(qū)域表示空閑 對(duì)應(yīng)的位圖 用空閑鏈表表示的同樣的信息10使用鏈表的存儲(chǔ)管理結(jié)束進(jìn)程X時(shí)與相鄰區(qū)域的四種組合X終止之前終止之前X終止之后終止之后變成變成變成變成變成變成變成變成11內(nèi)存分配算法 首次適配算法（First fit） 下次適配算法（Next fit） 最佳適配算法（Best fit） 最差適配算法（Worst fit） 快速適配算法（Quick fit）1212【 動(dòng)態(tài)分區(qū)分配算法分類】動(dòng)態(tài)分區(qū)分配算法分類】順序搜索法順序搜索法分類搜索法分類

4、搜索法快速適配算法快速適配算法分區(qū)分配算法分區(qū)分配算法首次適配算法首次適配算法循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法(下次適配算法下次適配算法)最佳適配算法最佳適配算法最差適配算法最差適配算法131) 1)首次適配算法首次適配算法: : 空閑區(qū)按空閑區(qū)按地址大小升序地址大小升序鏈成隊(duì)列鏈成隊(duì)列;. ;. 分配時(shí)從隊(duì)首開始查到第一個(gè)滿足要求的空閑分配時(shí)從隊(duì)首開始查到第一個(gè)滿足要求的空閑區(qū)進(jìn)行分配區(qū)進(jìn)行分配OSJ2J3 J50隊(duì)列指針S1 5kS2 1kS3 8k隊(duì)列指針S1S2S35k1k8k分配2k,S1滿足要求,余S1=3k隊(duì)列指針S1S2S33k1k8k 優(yōu)點(diǎn)優(yōu)點(diǎn): : 盡量分配低地址部分盡量分

5、配低地址部分, ,保留內(nèi)存高端空閑區(qū)不被保留內(nèi)存高端空閑區(qū)不被分割分割, ,以便運(yùn)行大作業(yè)以便運(yùn)行大作業(yè). .缺點(diǎn)缺點(diǎn): : 分配時(shí)可能查遍整個(gè)隊(duì)列分配時(shí)可能查遍整個(gè)隊(duì)列. .142) 2) 循環(huán)首次適配算法（下次適配算法）循環(huán)首次適配算法（下次適配算法）: : 空閑區(qū)按空閑區(qū)按地址大小升序地址大小升序鏈成鏈成環(huán)形環(huán)形隊(duì)列隊(duì)列. . 從上次分配的分區(qū)后面開始查找從上次分配的分區(qū)后面開始查找. .隊(duì)列指針隊(duì)列指針S1S1S2S2S3S35k5k1k1k8k8k作業(yè)作業(yè)申申請(qǐng)請(qǐng)2 2k k 回收時(shí)，有相鄰空閑區(qū)要合并回收時(shí)，有相鄰空閑區(qū)要合并隊(duì)列指針隊(duì)列指針S1S1S2S2S3S33k3k1k1k

6、8k8k優(yōu)點(diǎn)優(yōu)點(diǎn): : 碎片均勻分布在隊(duì)列中，回收時(shí)合并機(jī)率大碎片均勻分布在隊(duì)列中，回收時(shí)合并機(jī)率大缺點(diǎn)缺點(diǎn): : 大空閑區(qū)難以保留，不利于大作業(yè)。大空閑區(qū)難以保留，不利于大作業(yè)。153 3）最佳適配算法：）最佳適配算法：被分割的空閑區(qū)最接近作業(yè)大小，空區(qū)按被分割的空閑區(qū)最接近作業(yè)大小，空區(qū)按大小為大小為序序鏈成隊(duì)列鏈成隊(duì)列較大的空閑分區(qū)可以被保留較大的空閑分區(qū)可以被保留隊(duì)列指針隊(duì)列指針S1S1S2S2S3S31k1k2k2k10k10kS4S420k20k作業(yè)需要作業(yè)需要9 9k k，只分割，只分割S3S3，不破壞，不破壞S4S4。優(yōu)點(diǎn)優(yōu)點(diǎn): : 總是能把滿足要求、又是最小的空閑分區(qū)分配給作

7、業(yè)?？偸悄馨褲M足要求、又是最小的空閑分區(qū)分配給作業(yè)。缺點(diǎn)缺點(diǎn): : 分配后剩余部分總是最小，存儲(chǔ)器中會(huì)留下很多難以分配后剩余部分總是最小，存儲(chǔ)器中會(huì)留下很多難以利用的小空閑區(qū)。利用的小空閑區(qū)。164 4）最壞適配算法：）最壞適配算法：將所有的空閑分區(qū)按其容量從大到小的順序形成將所有的空閑分區(qū)按其容量從大到小的順序形成一空閑分區(qū)鏈，查找時(shí)只要看第一個(gè)分區(qū)能否滿一空閑分區(qū)鏈，查找時(shí)只要看第一個(gè)分區(qū)能否滿足作業(yè)要求。足作業(yè)要求。剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的幾率最小剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的幾率最小隊(duì)列指針隊(duì)列指針S1S1S2S2S3S320k20k10k10k2k2kS4S41k1k作

8、業(yè)需要作業(yè)需要9 9k k，分割，分割S1S1，還剩，還剩11k11k，可能還可滿足，可能還可滿足另一作業(yè)的需求。另一作業(yè)的需求。優(yōu)點(diǎn)優(yōu)點(diǎn): : 產(chǎn)生碎片幾率最?。粚?duì)中、小作業(yè)有利；查找效率最高。產(chǎn)生碎片幾率最??；對(duì)中、小作業(yè)有利；查找效率最高。缺點(diǎn)缺點(diǎn): : 缺乏大的空閑分區(qū)。缺乏大的空閑分區(qū)。175 5）快速適應(yīng)算法：）快速適應(yīng)算法：將所有的空閑分區(qū)按其容量大小進(jìn)行分類，對(duì)于每一類具將所有的空閑分區(qū)按其容量大小進(jìn)行分類，對(duì)于每一類具有相同容量的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表。有相同容量的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表。這樣，系統(tǒng)中存在多個(gè)空閑分區(qū)鏈表，同時(shí)在內(nèi)存中設(shè)立這樣，

9、系統(tǒng)中存在多個(gè)空閑分區(qū)鏈表，同時(shí)在內(nèi)存中設(shè)立一張管理索引表，該表的每一個(gè)表項(xiàng)對(duì)應(yīng)了一種空閑分區(qū)一張管理索引表，該表的每一個(gè)表項(xiàng)對(duì)應(yīng)了一種空閑分區(qū)類型，并記錄了該類型空閑分區(qū)鏈表表頭的指針。類型，并記錄了該類型空閑分區(qū)鏈表表頭的指針。大小大小管理索引表管理索引表2KB4KB8KB隊(duì)頭隊(duì)頭空閑分區(qū)鏈表空閑分區(qū)鏈表18優(yōu)點(diǎn)優(yōu)點(diǎn): : 查找效率高；不會(huì)產(chǎn)生分區(qū)分割；不產(chǎn)生碎片，也能滿足查找效率高；不會(huì)產(chǎn)生分區(qū)分割；不產(chǎn)生碎片，也能滿足大作業(yè)的要求。大作業(yè)的要求。缺點(diǎn)缺點(diǎn): : 回收分區(qū)時(shí)算法復(fù)雜，系統(tǒng)開銷較大。分區(qū)只屬于一回收分區(qū)時(shí)算法復(fù)雜，系統(tǒng)開銷較大。分區(qū)只屬于一個(gè)進(jìn)程，因此在為進(jìn)程所分配的一個(gè)分

10、區(qū)中，或多或少地存?zhèn)€進(jìn)程，因此在為進(jìn)程所分配的一個(gè)分區(qū)中，或多或少地存在一定的浪費(fèi)。空閑分區(qū)劃分越細(xì)，浪費(fèi)越嚴(yán)重。在一定的浪費(fèi)?？臻e分區(qū)劃分越細(xì)，浪費(fèi)越嚴(yán)重。是典型的以空間換時(shí)間的方法。是典型的以空間換時(shí)間的方法。大小大小管理索引表管理索引表2KB4KB8KB隊(duì)頭隊(duì)頭空閑分區(qū)鏈表空閑分區(qū)鏈表1919交換技術(shù)交換技術(shù)矛盾：矛盾：一方面：在內(nèi)存中的某些進(jìn)程由于某事件尚未發(fā)生而被阻塞運(yùn)行，但它卻占一方面：在內(nèi)存中的某些進(jìn)程由于某事件尚未發(fā)生而被阻塞運(yùn)行，但它卻占用了大量的內(nèi)存空間，甚至有時(shí)可能出現(xiàn)在內(nèi)存中所有進(jìn)程都被阻塞而迫使用了大量的內(nèi)存空間，甚至有時(shí)可能出現(xiàn)在內(nèi)存中所有進(jìn)程都被阻塞而迫使CPUC

11、PU停止下來(lái)等待的情況；停止下來(lái)等待的情況；另一方面：卻又有著許多作業(yè)在外存上等待，因無(wú)內(nèi)存而不能進(jìn)入內(nèi)存運(yùn)行另一方面：卻又有著許多作業(yè)在外存上等待，因無(wú)內(nèi)存而不能進(jìn)入內(nèi)存運(yùn)行的情況。的情況。解決的辦法：引入解決的辦法：引入Swapping(Swapping(交換交換) )技術(shù)。技術(shù)。交換：把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)交換：把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)調(diào)出到外存上，以便騰出足不用的程序和數(shù)據(jù)調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運(yùn)行條件的進(jìn)程或夠的內(nèi)存空間，再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)調(diào)入內(nèi)存。進(jìn)程所需要的程序和數(shù)據(jù)調(diào)入內(nèi)存。OS用戶用

12、戶空間空間換出換出換入換入外存對(duì)換區(qū)外存對(duì)換區(qū)2020（中級(jí)調(diào)度）（中級(jí)調(diào)度）活動(dòng)活動(dòng)就緒就緒運(yùn)行運(yùn)行活動(dòng)活動(dòng)阻塞阻塞靜止靜止就緒就緒靜止靜止阻塞阻塞新新?tīng)顟B(tài)狀態(tài)SuspendSuspendSuspendDispatchBlock WackeupActivateActivateTimeoutEvent OccursEvent waitAdmit（進(jìn)程調(diào)度）（進(jìn)程調(diào)度）（中級(jí)調(diào)度）（中級(jí)調(diào)度）后備后備（作業(yè)調(diào)度）（作業(yè)調(diào)度）外存輸入井外存輸入井外存對(duì)換區(qū)外存對(duì)換區(qū)內(nèi)內(nèi)存存21虛擬內(nèi)存分頁(yè) (1)內(nèi)存管理單元MMU得位置和功能CPU發(fā)送虛擬地址給MMU內(nèi)存管理單元MMU存儲(chǔ)器磁盤控制器總線MMU發(fā)

13、送物理地址給存儲(chǔ)器CPU包包22分頁(yè) (2) 頁(yè)表給出虛擬地址與物理地址之間的映射關(guān)系虛擬地址空間虛擬頁(yè)面頁(yè)框物理內(nèi)存地址2323頁(yè)面大小如何設(shè)定？頁(yè)面大小如何設(shè)定？頁(yè)面大小如何設(shè)定？頁(yè)面大小如何設(shè)定？頁(yè)面大小應(yīng)適中。頁(yè)面大小應(yīng)適中。若太?。喝籼。嚎墒箖?nèi)存碎片減小，從而減少了內(nèi)存碎片的總空間，有利于提高內(nèi)存利用率；可使內(nèi)存碎片減小，從而減少了內(nèi)存碎片的總空間，有利于提高內(nèi)存利用率；但另一方面每個(gè)進(jìn)程會(huì)占用較多的頁(yè)面，從而導(dǎo)致進(jìn)程的頁(yè)表過(guò)長(zhǎng)，占用大但另一方面每個(gè)進(jìn)程會(huì)占用較多的頁(yè)面，從而導(dǎo)致進(jìn)程的頁(yè)表過(guò)長(zhǎng)，占用大量?jī)?nèi)存；量?jī)?nèi)存；降低頁(yè)面換進(jìn)換出的效率。降低頁(yè)面換進(jìn)換出的效率。若太大：若太大：可

14、以減少頁(yè)表的長(zhǎng)度；可以減少頁(yè)表的長(zhǎng)度；提高頁(yè)面換進(jìn)換出的速度；提高頁(yè)面換進(jìn)換出的速度；頁(yè)內(nèi)碎片增大。頁(yè)內(nèi)碎片增大。頁(yè)面大小應(yīng)為頁(yè)面大小應(yīng)為2的冪次，通常為的冪次，通常為512B8KB。24分頁(yè) (3)在16個(gè)4KB頁(yè)面情況下MMU的內(nèi)部操作頁(yè)表輸出物理地址（25480）輸入虛擬地址（8196）直接從輸入復(fù)制到輸出的12位偏移量“在/不在”位虛擬頁(yè)面2被用作頁(yè)表的索引25頁(yè)表 (1)一個(gè)典型的頁(yè)表項(xiàng)訪問(wèn)位訪問(wèn)位保護(hù)位保護(hù)位“在在/不在不在”位位修改位修改位高速緩存高速緩存禁止位禁止位頁(yè)框號(hào)頁(yè)框號(hào)26加速分頁(yè)過(guò)程TLB 轉(zhuǎn)換檢測(cè)緩沖區(qū)有效位有效位虛擬頁(yè)面號(hào)虛擬頁(yè)面號(hào)修改位修改位保護(hù)位保護(hù)位頁(yè)框號(hào)頁(yè)

15、框號(hào) TLB加速分頁(yè)27針對(duì)大內(nèi)存的頁(yè)表 多級(jí)頁(yè)表 一個(gè)有兩個(gè)頁(yè)表域的32位地址 二級(jí)頁(yè)表Second-level page tablesTop-level page table二級(jí)頁(yè)表頂級(jí)頁(yè)表內(nèi)存頂部4MB的頁(yè)表至頁(yè)面位28針對(duì)大內(nèi)存的頁(yè)表倒排頁(yè)表傳統(tǒng)頁(yè)表與倒排頁(yè)表的對(duì)比傳統(tǒng)頁(yè)表。每頁(yè)一個(gè)頁(yè)表項(xiàng)，共252個(gè)頁(yè)面256MB物理內(nèi)存有216個(gè)4KB頁(yè)框哈希表頁(yè)框虛擬頁(yè)面虛擬頁(yè)面散列后，作為索引以虛擬頁(yè)面作為索引29頁(yè)面置換算法 頁(yè)面發(fā)生缺頁(yè)中斷時(shí)： 必須選擇一個(gè)頁(yè)面換出 為即將調(diào)入內(nèi)存的頁(yè)面騰出空間 已修改的頁(yè)面必須首先保存 未修改的頁(yè)面只需要覆蓋即可 不要選擇頻繁使用的頁(yè)面置換出內(nèi)存 很可能很

16、短時(shí)間內(nèi)又要被調(diào)入內(nèi)存30最優(yōu)頁(yè)面置換算法（OPT） 置換未來(lái)不再需要或最遠(yuǎn)的將來(lái)才會(huì)使用的頁(yè)面 最優(yōu)但是不可實(shí)現(xiàn) 可作為其他置換算法性能的評(píng)價(jià)標(biāo)準(zhǔn) 在運(yùn)行的進(jìn)程之前標(biāo)記頁(yè)面的使用情況 雖然這是不可能實(shí)現(xiàn)的31最近未使用頁(yè)面置換算法（NRU）每個(gè)頁(yè)面都設(shè)置一個(gè)訪問(wèn)位和修改位當(dāng)頁(yè)面被訪問(wèn)或修改時(shí)即設(shè)置訪問(wèn)位或修改位頁(yè)面被分類成：1.未被訪問(wèn), 未被修改2.未被訪問(wèn), 已被修改3.已被訪問(wèn), 未被修改4.已被訪問(wèn), 已被修改NRU 算法隨機(jī)的選擇頁(yè)面淘汰之 從類編號(hào)最小的非空類中挑選一個(gè)頁(yè)面32先進(jìn)先出頁(yè)面置換算法（FIFO） OS維護(hù)一個(gè)所有當(dāng)前在內(nèi)存中的頁(yè)面的鏈表 按照頁(yè)面進(jìn)入內(nèi)存的順序組織

17、在表頭的最久進(jìn)入頁(yè)面被置換出內(nèi)存 缺點(diǎn) 在內(nèi)存中最久的頁(yè)面常?？赡芫褪穷l繁使用的33第二次機(jī)會(huì)頁(yè)面置換算法（SCR） 第二次機(jī)會(huì)算法的操作 按先進(jìn)先出的方法排列的頁(yè)面 在時(shí)間20發(fā)生缺頁(yè)中斷并且A的R位已經(jīng)設(shè)置時(shí)的頁(yè)面鏈表先被裝入的頁(yè)面先被裝入的頁(yè)面最近裝入最近裝入的頁(yè)面的頁(yè)面A被看作是最被看作是最新裝入的頁(yè)面新裝入的頁(yè)面34時(shí)鐘頁(yè)面置換算法（Clock）當(dāng)發(fā)生缺頁(yè)中斷時(shí)，檢查表針指向的頁(yè)面。根據(jù)R位采取動(dòng)作：R0：淘汰頁(yè)面R1：清楚R位并向前移動(dòng)表針35最近最少使用頁(yè)面置換算法 (LRU) 假設(shè)最近使用的頁(yè)面很快又被使用 置換很長(zhǎng)時(shí)間沒(méi)被使用的頁(yè)面 需要在內(nèi)存中維護(hù)一個(gè)所有頁(yè)面的鏈表 最近最

18、多使用的頁(yè)面在表頭，最近最少使用的頁(yè)面在表尾 每次訪問(wèn)內(nèi)存時(shí)都必須要更新整個(gè)鏈表 ! 另外一種做法就是在每個(gè)頁(yè)表項(xiàng)中設(shè)置一個(gè)計(jì)數(shù)器 選擇計(jì)數(shù)器值最小的頁(yè)面置換出去 周期性的清零計(jì)數(shù)器36使用矩陣的LRU 頁(yè)面訪問(wèn)次序 0,1,2,3,2,1,0,3,2,3頁(yè)面頁(yè)面頁(yè)面頁(yè)面頁(yè)面最近最少使用頁(yè)面置換算法 (LRU)37 用軟件模擬LRU的老化算法 圖中所示是6個(gè)頁(yè)面在5個(gè)時(shí)鐘滴答的情況,5個(gè)時(shí)鐘滴答分別是 (a) (e)用軟件模擬LRU算法頁(yè)面頁(yè)面05的的R位，位，時(shí)鐘滴答時(shí)鐘滴答0頁(yè)面頁(yè)面05的的R位，位，時(shí)鐘滴答時(shí)鐘滴答1頁(yè)面頁(yè)面05的的R位，位，時(shí)鐘滴答時(shí)鐘滴答2頁(yè)面頁(yè)面05的的R位，位，時(shí)

19、鐘滴答時(shí)鐘滴答3頁(yè)面頁(yè)面05的的R位，位，時(shí)鐘滴答時(shí)鐘滴答4頁(yè)面38工作集頁(yè)面置換算法(1) 工作集是最近k次內(nèi)存訪問(wèn)所訪問(wèn)過(guò)的頁(yè)面的集合 函數(shù)w(k,t)是在時(shí)刻 t時(shí)工作集的大小39工作集頁(yè)面置換算法(2)工作集算法一個(gè)頁(yè)面的信息上次使用的時(shí)間這個(gè)時(shí)鐘滴答期間訪問(wèn)的頁(yè)面這個(gè)時(shí)鐘滴答期間未訪問(wèn)的頁(yè)面當(dāng)前實(shí)際時(shí)間R（訪問(wèn)）位掃描所有頁(yè)面檢查R位： 若（R1） 設(shè)置上次使用時(shí)間為當(dāng)前實(shí)際時(shí)間 若（R0且生存時(shí)間t） 移出這個(gè)頁(yè)面 若（R0且生存時(shí)間t ） 記住最小時(shí)間40工作集時(shí)鐘頁(yè)面置換算法工作集時(shí)鐘頁(yè)面置換算法的操作當(dāng)前實(shí)際時(shí)間R位上次使用時(shí)間新頁(yè)面41頁(yè)面置換算法小結(jié)算法算法注釋注釋最優(yōu)算

20、法最優(yōu)算法不可實(shí)現(xiàn)，但可用作基準(zhǔn)不可實(shí)現(xiàn)，但可用作基準(zhǔn)NRU（最近未使用）算法（最近未使用）算法LRU的很粗糙的近似的很粗糙的近似FIFO（先進(jìn)現(xiàn)出）算法（先進(jìn)現(xiàn)出）算法可能拋棄重要頁(yè)面可能拋棄重要頁(yè)面第二次機(jī)會(huì)算法第二次機(jī)會(huì)算法比比FIFO有大的改善有大的改善時(shí)鐘算法時(shí)鐘算法現(xiàn)實(shí)的現(xiàn)實(shí)的LRU（最近最少使用）算法（最近最少使用）算法很優(yōu)秀，但很難實(shí)現(xiàn)很優(yōu)秀，但很難實(shí)現(xiàn)NFU（最不經(jīng)常使用）算法（最不經(jīng)常使用）算法LRU的相對(duì)粗略的近似的相對(duì)粗略的近似老化算法老化算法非常近似非常近似LRU的有效算法的有效算法工作集算法工作集算法實(shí)現(xiàn)起來(lái)開銷很大實(shí)現(xiàn)起來(lái)開銷很大工作集時(shí)鐘算法工作集時(shí)鐘算法好的有

21、效算法好的有效算法42頁(yè)面置換算法舉例某程序在內(nèi)存中分配三個(gè)頁(yè)面，初始為空，頁(yè)面走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5。共發(fā)生7次缺頁(yè)中斷注：為了方便比較，這里的頁(yè)面按調(diào)入先后進(jìn)行了排序。43共發(fā)生10次缺頁(yè)中斷某程序在內(nèi)存中分配三個(gè)頁(yè)面，初始為空，頁(yè)面走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5。44共發(fā)生9次缺頁(yè)中斷某程序在內(nèi)存中分配三個(gè)頁(yè)面，初始為空，頁(yè)面走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5。45分頁(yè)系統(tǒng)中的設(shè)計(jì)問(wèn)題局部分配策略與全局分配策略 (1) 初始配置 局部頁(yè)面置換 全局頁(yè)面置換生存時(shí)間生存時(shí)間46局部分配策略和全局分配策略(2)缺頁(yè)中斷率是

22、分配的頁(yè)框數(shù)的函數(shù)分配的頁(yè)框數(shù)缺頁(yè)中斷數(shù)/秒47負(fù)載控制 即使是最好的設(shè)計(jì), 系統(tǒng)也可能會(huì)發(fā)生顛簸 正如PFF算法指出的 一些進(jìn)程需要更多的內(nèi)存 但是沒(méi)有進(jìn)程需要更少的內(nèi)存 解決方法 :（交換技術(shù)）減少競(jìng)爭(zhēng)內(nèi)存的進(jìn)程數(shù) 將一部分進(jìn)程交換到磁盤，并釋放他們所占的所有頁(yè)面 重新考慮多道程序設(shè)計(jì)的道數(shù)48頁(yè)面大小 (1)小頁(yè)面 優(yōu)勢(shì) 更少的內(nèi)部碎片 更加靈活適合各種程序結(jié)構(gòu)和數(shù)據(jù)段 減少內(nèi)存中沒(méi)用的程序 不足 程序需要更多頁(yè)面，更大的頁(yè)表49頁(yè)面大小 (2) 系統(tǒng)開銷取決于頁(yè)表大小和內(nèi)部碎片 在此 s = 進(jìn)程平均大小 p = 頁(yè)面大小 e = 頁(yè)表項(xiàng)大小2s epoverheadppage tab

23、le spaceinternal fragmentation最優(yōu)頁(yè)面大小當(dāng)2pse50分離的指令空間和數(shù)據(jù)空間 單個(gè)地址空間 分離的 I 空間和 D 空間單個(gè)地址空間I空間D空間數(shù)據(jù)程序數(shù)據(jù)未使用頁(yè)面程序51共享頁(yè)面兩個(gè)進(jìn)程通過(guò)共享程序頁(yè)表來(lái)共享同一個(gè)程序進(jìn)程表頁(yè)表數(shù)據(jù)1數(shù)據(jù)2程序52共享庫(kù) 靜態(tài)鏈接 動(dòng)態(tài)鏈接 位置無(wú)關(guān)代碼兩個(gè)進(jìn)程使用的共享庫(kù)53內(nèi)存映射文件 這種機(jī)制的思想是：進(jìn)程通過(guò)一個(gè)系統(tǒng)調(diào)用將一個(gè)文件映射到其虛擬地址空間的一部分，訪問(wèn)這個(gè)文件就像訪問(wèn)內(nèi)存中的一個(gè)大數(shù)組，而不是對(duì)文件進(jìn)行讀寫 在多數(shù)實(shí)現(xiàn)中，在映射共享的頁(yè)面時(shí)不會(huì)實(shí)際讀入頁(yè)面的內(nèi)容，而是在訪問(wèn)頁(yè)面時(shí)，頁(yè)面才會(huì)被每次一頁(yè)的讀

24、入，磁盤文件則被當(dāng)作后備存儲(chǔ) 當(dāng)進(jìn)程退出或顯式地解除文件映射時(shí)，所有被修改頁(yè)面會(huì)寫回文件54清除策略 如果發(fā)生缺頁(yè)中斷時(shí)，系統(tǒng)中有大量的空閑頁(yè)框，分頁(yè)系統(tǒng)工作在最佳狀態(tài)。保存一定數(shù)目的頁(yè)框供給比使用所有內(nèi)存并在需要時(shí)搜索一個(gè)頁(yè)框有更好的性能 需要一個(gè)稱為分頁(yè)守護(hù)進(jìn)程的后臺(tái)進(jìn)程 周期性的檢視內(nèi)存的狀態(tài) 如果空閑頁(yè)框太少 分頁(yè)守護(hù)進(jìn)程通過(guò)頁(yè)面置換算法選擇頁(yè)面換出內(nèi)存55清除策略（續(xù)） 當(dāng)需要使用一個(gè)已被淘汰的頁(yè)面時(shí)，如果該頁(yè)框還沒(méi)有被覆蓋，將其從空閑頁(yè)框緩沖池中移出即可恢復(fù)該頁(yè)面 使用一個(gè)雙指針時(shí)鐘實(shí)現(xiàn)清除策略 前指針由分頁(yè)守護(hù)進(jìn)程控制。當(dāng)它指向一個(gè)“臟”頁(yè)面時(shí)，就把該頁(yè)面寫回磁盤，前指針向前移動(dòng)

25、。當(dāng)它指向一個(gè)干凈頁(yè)面時(shí)，僅僅指針向前移動(dòng) 后指針用于頁(yè)面置換，與標(biāo)準(zhǔn)時(shí)鐘算法一樣 由于分頁(yè)守護(hù)進(jìn)程的工作，后指針命中干凈頁(yè)面的概率會(huì)增加56虛擬內(nèi)存接口 對(duì)于一些高級(jí)系統(tǒng)而言，程序員可以對(duì)內(nèi)存映射進(jìn)行控制，并可以通過(guò)非常規(guī)的方法來(lái)增強(qiáng)程序的行為。 允許程序員對(duì)內(nèi)存映射進(jìn)行控制的一個(gè)原因就是為了允許兩個(gè)或者多個(gè)進(jìn)程共享同一部分內(nèi)存。 頁(yè)面共享也可以用來(lái)實(shí)現(xiàn)高性能的消息傳遞系統(tǒng)。 另外一種高級(jí)存儲(chǔ)管理技術(shù)是分布式共享內(nèi)存。該方法允許網(wǎng)絡(luò)上的多個(gè)進(jìn)程共享一個(gè)頁(yè)面集合，這些頁(yè)面可能（而不是必要的）作為單個(gè)的線性共享地址空間。 57有關(guān)實(shí)現(xiàn)的問(wèn)題與分頁(yè)有關(guān)的工作操作系統(tǒng)在下面四個(gè)階段做與分頁(yè)相關(guān)的工作

26、：1.進(jìn)程創(chuàng)建-要確定程序和數(shù)據(jù)在初始時(shí)的大小-創(chuàng)建頁(yè)表2.進(jìn)程執(zhí)行時(shí)-必須為新進(jìn)程重置MMU-刷新TLB3.缺頁(yè)中斷時(shí)-必須通過(guò)硬件寄存器確定哪個(gè)虛擬地址造成了缺頁(yè)中斷-置換出老頁(yè)面，換入新頁(yè)面4.進(jìn)程終止時(shí)-釋放進(jìn)程的頁(yè)表、頁(yè)面和頁(yè)面在硬盤所占用的空間58缺頁(yè)中斷處理 (1)1.硬件陷入內(nèi)核 2.啟動(dòng)一個(gè)匯編代碼例程保存通用寄存器和其他易失的信息，以免被操作系統(tǒng)破壞。 3.當(dāng)操作系統(tǒng)發(fā)現(xiàn)一個(gè)缺頁(yè)中斷時(shí)，嘗試發(fā)現(xiàn)需要哪個(gè)虛擬頁(yè)面。 4.一旦知道了發(fā)生缺頁(yè)中斷的虛擬地址，操作系統(tǒng)檢查這個(gè)地址是否有效，并檢查存取與保護(hù)是否一致。 5.如果選擇的頁(yè)框“臟”了，安排該頁(yè)寫回磁盤，并發(fā)生一次上下文切換

27、，掛起產(chǎn)生缺頁(yè)中斷的進(jìn)程，讓其他進(jìn)程運(yùn)行直至磁盤傳輸結(jié)束。 59缺頁(yè)中斷處理 (2)6.一旦頁(yè)框“干凈”后，操作系統(tǒng)查找所需頁(yè)面在磁盤上的地址，通過(guò)磁盤操作將其裝入。7.頁(yè)表已經(jīng)更新 8.恢復(fù)發(fā)生缺頁(yè)中斷指令以前的狀態(tài)，程序計(jì)數(shù)器重新指向這條指令9.調(diào)度引發(fā)缺頁(yè)中斷的進(jìn)程，操作系統(tǒng)返回調(diào)用它的匯編語(yǔ)言例程 10.該例程恢復(fù)寄存器和其他狀態(tài)信息 11.返回到用戶空間繼續(xù)執(zhí)行，就好像缺頁(yè)中斷沒(méi)有發(fā)生過(guò)一樣 60指令備份引起缺頁(yè)中斷的一條指令61鎖定內(nèi)存中的頁(yè)面 虛擬內(nèi)存和I/O通過(guò)微妙的方式相互作用著。 設(shè)想一個(gè)進(jìn)程剛剛通過(guò)系統(tǒng)調(diào)用從文件或其他設(shè)備中讀取數(shù)據(jù)到其地址空間中的緩沖區(qū) 在等待I/O完成

28、時(shí)，該進(jìn)程被掛起，另一個(gè)進(jìn)程被允許運(yùn)行 產(chǎn)生一個(gè)缺頁(yè)中斷 第一個(gè)進(jìn)程的緩沖區(qū)頁(yè)面可能被選中換出內(nèi)存 需要指定一些頁(yè)面被鎖定 鎖住正在做I/O操作的內(nèi)存中的頁(yè)面以保證它不會(huì)被移出內(nèi)存 62后備存儲(chǔ)(a) 對(duì)靜態(tài)交換區(qū)分頁(yè)(b) 動(dòng)態(tài)備份頁(yè)面63策略和機(jī)制的分離用一個(gè)外部頁(yè)面調(diào)度程序來(lái)處理缺頁(yè)中斷64分段 (1) 在一維地址空間中，當(dāng)有多個(gè)動(dòng)態(tài)增加的表 一個(gè)表可能會(huì)與另一個(gè)表發(fā)生碰撞65 段式是從段式是從方便用戶角度方便用戶角度提出的管理方案，提出的管理方案，為方便用戶引入段式管理為方便用戶引入段式管理 段式管理優(yōu)越性段式管理優(yōu)越性: :(1)(1)方便用戶編程方便用戶編程 (2) (2)便于信息

29、共享便于信息共享(3)(3)便于信息保護(hù)便于信息保護(hù) (4) (4)便于段動(dòng)態(tài)增長(zhǎng)便于段動(dòng)態(tài)增長(zhǎng)(5)(5)便于動(dòng)態(tài)鏈接便于動(dòng)態(tài)鏈接 （6 6）可以分別編寫和編譯）可以分別編寫和編譯66分段 (2)每個(gè)段都可以獨(dú)立地增加或減少而不影響其他段67分段 (3)分頁(yè)和分段的比較68純分段的實(shí)現(xiàn)(a)-(d) 棋盤形碎片的形成(e)通過(guò)緊縮消除棋盤形碎片69作業(yè)的地址空間被劃分成若干個(gè)段，每個(gè)段定義了一作業(yè)的地址空間被劃分成若干個(gè)段，每個(gè)段定義了一組邏輯信息；組邏輯信息；每段都有自己的名字，通常用段號(hào)代替段名；每段都有自己的名字，通常用段號(hào)代替段名；每段都從每段都從0 0開始編址，并采用一段連續(xù)的地址

30、空間；開始編址，并采用一段連續(xù)的地址空間；段的長(zhǎng)度由邏輯信息組的長(zhǎng)度決定；段的長(zhǎng)度由邏輯信息組的長(zhǎng)度決定；邏輯地址是二維的，由段號(hào)和段內(nèi)地址組成。邏輯地址是二維的，由段號(hào)和段內(nèi)地址組成。段號(hào)段號(hào)段內(nèi)地址段內(nèi)地址0 0151516163131該地址結(jié)構(gòu)中，允許一個(gè)作業(yè)最長(zhǎng)有該地址結(jié)構(gòu)中，允許一個(gè)作業(yè)最長(zhǎng)有64k64k個(gè)段，每個(gè)段的最大個(gè)段，每個(gè)段的最大長(zhǎng)度為長(zhǎng)度為64KB64KB。1.分段分段70為每一分段分配一個(gè)連續(xù)的分區(qū)，各段可以離散地移為每一分段分配一個(gè)連續(xù)的分區(qū)，各段可以離散地移入內(nèi)存中不同的分區(qū)中；入內(nèi)存中不同的分區(qū)中；為實(shí)現(xiàn)地址變換，應(yīng)提供一張段映射表，簡(jiǎn)稱為實(shí)現(xiàn)地址變換，應(yīng)提供一張段映射表，簡(jiǎn)稱“段段表表”；每個(gè)段在表中占有一個(gè)表項(xiàng)，其中記錄了該段在內(nèi)存每個(gè)段在表中占有一個(gè)表項(xiàng)，其中記錄了該段在內(nèi)存中的起始地址和段的長(zhǎng)度；中的起始地址和段的長(zhǎng)度；2. 段表段表71假設(shè)：有主程序段假設(shè)