1、1北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)2主要內(nèi)容主要內(nèi)容 虛擬內(nèi)存技術(shù)的引入虛擬內(nèi)存技術(shù)的引入 虛擬內(nèi)存技術(shù)概念虛擬內(nèi)存技術(shù)概念 虛擬內(nèi)存的實(shí)現(xiàn)虛擬內(nèi)存的實(shí)現(xiàn) 分頁(yè)技術(shù)實(shí)現(xiàn)的虛擬內(nèi)存分頁(yè)技術(shù)實(shí)現(xiàn)的虛擬內(nèi)存北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)3虛擬內(nèi)存技術(shù)的引入虛擬內(nèi)存技術(shù)的引入 內(nèi)存空間大小的問(wèn)題內(nèi)存空間大小的問(wèn)題 內(nèi)存空間問(wèn)題的解決辦法內(nèi)存空間問(wèn)題的解決辦法 軟件解決方案的基礎(chǔ)軟件解決方案的基礎(chǔ) 操作系統(tǒng)的解決辦法操作系統(tǒng)的解決辦法北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)4內(nèi)存空間大小的問(wèn)題內(nèi)存空間大小的問(wèn)題 每個(gè)程序運(yùn)行所需空間不能超過(guò)可用內(nèi)每個(gè)程序運(yùn)行所需空間不能超過(guò)可用內(nèi)存存 程序會(huì)因不能裝入內(nèi)

2、存而無(wú)法運(yùn)行程序會(huì)因不能裝入內(nèi)存而無(wú)法運(yùn)行 程序的功能越來(lái)越復(fù)雜、代碼越來(lái)越長(zhǎng)程序的功能越來(lái)越復(fù)雜、代碼越來(lái)越長(zhǎng) 采用覆蓋技術(shù)采用覆蓋技術(shù) 限制太大限制太大 程序員在寫(xiě)程序時(shí)要考慮內(nèi)存大小、考慮程序員在寫(xiě)程序時(shí)要考慮內(nèi)存大小、考慮覆蓋覆蓋北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)5內(nèi)存空間問(wèn)題的解決辦法內(nèi)存空間問(wèn)題的解決辦法 硬件：增加內(nèi)存硬件：增加內(nèi)存 軟件：改變程序的要求軟件：改變程序的要求 問(wèn)題關(guān)鍵：如果程序可以不用全部放在內(nèi)問(wèn)題關(guān)鍵：如果程序可以不用全部放在內(nèi)存中就能夠執(zhí)行存中就能夠執(zhí)行北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)6軟件解決方案的基礎(chǔ)軟件解決方案的基礎(chǔ) 并不需要所有代碼和數(shù)據(jù)都放到內(nèi)存中

3、并不需要所有代碼和數(shù)據(jù)都放到內(nèi)存中 一個(gè)一個(gè)CPU在某個(gè)時(shí)刻只能訪問(wèn)一條語(yǔ)句或在某個(gè)時(shí)刻只能訪問(wèn)一條語(yǔ)句或者一個(gè)數(shù)據(jù)者一個(gè)數(shù)據(jù) 有成熟的地址重定向技術(shù)有成熟的地址重定向技術(shù) 允許程序在內(nèi)存中的位置不連續(xù)且可以變?cè)试S程序在內(nèi)存中的位置不連續(xù)且可以變化化北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)7操作系統(tǒng)的解決辦法操作系統(tǒng)的解決辦法 不再一次把一個(gè)進(jìn)程的全部信息都裝入到不再一次把一個(gè)進(jìn)程的全部信息都裝入到內(nèi)存中內(nèi)存中 只是裝入一部分只是裝入一部分 然后調(diào)度進(jìn)程運(yùn)行然后調(diào)度進(jìn)程運(yùn)行 其他部分等到需要時(shí)再裝入其他部分等到需要時(shí)再裝入北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)8操作系統(tǒng)的解決辦法操作系統(tǒng)的解決辦法 多大

4、的程序都可以在有限的內(nèi)存中運(yùn)行多大的程序都可以在有限的內(nèi)存中運(yùn)行 程序員寫(xiě)程序時(shí)再不用考慮內(nèi)存的大小程序員寫(xiě)程序時(shí)再不用考慮內(nèi)存的大小 程序員可以編寫(xiě)使用任意大內(nèi)存空間的程程序員可以編寫(xiě)使用任意大內(nèi)存空間的程序序 1G的程序，編譯程序編址地址空間從的程序，編譯程序編址地址空間從0到到1G，程序可在只有程序可在只有256M內(nèi)存的計(jì)算機(jī)上運(yùn)行內(nèi)存的計(jì)算機(jī)上運(yùn)行 程序員感覺(jué)他有程序員感覺(jué)他有1G大的內(nèi)存空間，而不是大的內(nèi)存空間，而不是256M北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)9虛擬內(nèi)存技術(shù)虛擬內(nèi)存技術(shù) 虛擬內(nèi)存空間虛擬內(nèi)存空間 程序員寫(xiě)程序時(shí)使用的地址空間程序員寫(xiě)程序時(shí)使用的地址空間 虛擬內(nèi)存技術(shù)虛

5、擬內(nèi)存技術(shù) 采用虛擬空間獨(dú)立編址、操作系統(tǒng)負(fù)責(zé)把采用虛擬空間獨(dú)立編址、操作系統(tǒng)負(fù)責(zé)把一個(gè)大的虛擬空間的內(nèi)容分階段裝入實(shí)際一個(gè)大的虛擬空間的內(nèi)容分階段裝入實(shí)際內(nèi)存中運(yùn)行的技術(shù)內(nèi)存中運(yùn)行的技術(shù) 程序員以為自己有一很大內(nèi)存空間，且獨(dú)享程序員以為自己有一很大內(nèi)存空間，且獨(dú)享 虛擬空間受限于地址寬度虛擬空間受限于地址寬度 32位虛擬地址，虛擬空間上限位虛擬地址，虛擬空間上限4G北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)10虛擬內(nèi)存技術(shù)的實(shí)現(xiàn)虛擬內(nèi)存技術(shù)的實(shí)現(xiàn) 內(nèi)存分配內(nèi)存分配 訪問(wèn)內(nèi)存訪問(wèn)內(nèi)存 淘汰淘汰北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)11內(nèi)存分配內(nèi)存分配 先把程序分成若干部分先把程序分成若干部分 選擇把一部分

6、裝載到內(nèi)存中選擇把一部分裝載到內(nèi)存中 記錄信息記錄信息 哪些部分裝載到內(nèi)存中，哪些沒(méi)有哪些部分裝載到內(nèi)存中，哪些沒(méi)有 裝載到內(nèi)存中的部分放在什么位置裝載到內(nèi)存中的部分放在什么位置 可采用頁(yè)式、段式、段頁(yè)式可采用頁(yè)式、段式、段頁(yè)式北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)12內(nèi)存分配內(nèi)存分配 頁(yè)式頁(yè)式 虛擬空間仍然分成頁(yè)虛擬空間仍然分成頁(yè) 在頁(yè)表中增加一個(gè)標(biāo)志，表示這個(gè)頁(yè)是否在頁(yè)表中增加一個(gè)標(biāo)志，表示這個(gè)頁(yè)是否在內(nèi)存中在內(nèi)存中 如果在內(nèi)存中，頁(yè)表中記錄相應(yīng)頁(yè)框號(hào)如果在內(nèi)存中，頁(yè)表中記錄相應(yīng)頁(yè)框號(hào)北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)13訪問(wèn)內(nèi)存訪問(wèn)內(nèi)存 查找頁(yè)表或者段表，判斷內(nèi)容是否在內(nèi)查找頁(yè)表或者段表，判

7、斷內(nèi)容是否在內(nèi)存中存中 已經(jīng)被裝入到內(nèi)存中已經(jīng)被裝入到內(nèi)存中 利用頁(yè)表或者段表中的信息，把虛擬地址利用頁(yè)表或者段表中的信息，把虛擬地址轉(zhuǎn)換成對(duì)應(yīng)的物理地址轉(zhuǎn)換成對(duì)應(yīng)的物理地址 未裝入到內(nèi)存未裝入到內(nèi)存 在內(nèi)存中找一塊空閑空間分配給進(jìn)程在內(nèi)存中找一塊空閑空間分配給進(jìn)程 把要訪問(wèn)的內(nèi)容從外存讀取到內(nèi)存把要訪問(wèn)的內(nèi)容從外存讀取到內(nèi)存 修改頁(yè)表或者段表修改頁(yè)表或者段表北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)14淘汰淘汰 如果內(nèi)存中沒(méi)有空閑空間，或者空閑空如果內(nèi)存中沒(méi)有空閑空間，或者空閑空間低于限定值間低于限定值 選擇內(nèi)存中一些正被使用的單元選擇內(nèi)存中一些正被使用的單元 把里面的內(nèi)容寫(xiě)回到外存把里面的內(nèi)容寫(xiě)回

8、到外存 把這些空間釋放出來(lái)把這些空間釋放出來(lái) 分配給需要的進(jìn)程分配給需要的進(jìn)程北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)15淘汰淘汰 抖動(dòng)抖動(dòng) 選擇今后不會(huì)或者最近不會(huì)用到的內(nèi)容選擇今后不會(huì)或者最近不會(huì)用到的內(nèi)容換出換出 局部性原理局部性原理 一般情況下一個(gè)進(jìn)程在一段時(shí)間內(nèi)要訪問(wèn)一般情況下一個(gè)進(jìn)程在一段時(shí)間內(nèi)要訪問(wèn)的指令和數(shù)據(jù)都集中在一起的指令和數(shù)據(jù)都集中在一起北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)16虛擬內(nèi)存技術(shù)虛擬內(nèi)存技術(shù) 實(shí)現(xiàn)的基礎(chǔ)實(shí)現(xiàn)的基礎(chǔ) 局部性原理局部性原理 地址重定向技術(shù)地址重定向技術(shù) 使程序在一定程度上不再受物理內(nèi)存大小使程序在一定程度上不再受物理內(nèi)存大小的限制的限制北京工業(yè)大學(xué)軟件學(xué)院

9、張麗操作系統(tǒng)17分頁(yè)技術(shù)實(shí)現(xiàn)的虛擬內(nèi)存分頁(yè)技術(shù)實(shí)現(xiàn)的虛擬內(nèi)存 內(nèi)存分配內(nèi)存分配 虛擬空間的管理虛擬空間的管理 物理內(nèi)存空間分成與頁(yè)面大小相同頁(yè)框物理內(nèi)存空間分成與頁(yè)面大小相同頁(yè)框 空閑頁(yè)框管理空閑頁(yè)框管理 頁(yè)表頁(yè)表 內(nèi)存訪問(wèn)內(nèi)存訪問(wèn) 缺頁(yè)中斷缺頁(yè)中斷 頁(yè)面淘汰頁(yè)面淘汰北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)18虛擬空間的管理虛擬空間的管理 地址長(zhǎng)度確定虛擬空間的大小地址長(zhǎng)度確定虛擬空間的大小 如如32位的位的Linux操作系統(tǒng)的虛擬空間大小操作系統(tǒng)的虛擬空間大小4G 分為系統(tǒng)空間和用戶空間分為系統(tǒng)空間和用戶空間北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)19空閑頁(yè)框管理空閑頁(yè)框管理 鏈表鏈表 位圖位圖北京工業(yè)

10、大學(xué)軟件學(xué)院 張麗操作系統(tǒng)20頁(yè)表頁(yè)表 創(chuàng)建新進(jìn)程時(shí)，在內(nèi)存中為進(jìn)程創(chuàng)建一創(chuàng)建新進(jìn)程時(shí)，在內(nèi)存中為進(jìn)程創(chuàng)建一個(gè)頁(yè)表個(gè)頁(yè)表 為進(jìn)程分配內(nèi)存，填寫(xiě)頁(yè)表相關(guān)內(nèi)容為進(jìn)程分配內(nèi)存，填寫(xiě)頁(yè)表相關(guān)內(nèi)容北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)21頁(yè)表表項(xiàng)結(jié)構(gòu)頁(yè)表表項(xiàng)結(jié)構(gòu) 頁(yè)面訪問(wèn)位頁(yè)面訪問(wèn)位 A A 0頁(yè)面不在內(nèi)存頁(yè)面不在內(nèi)存1 1頁(yè)面在內(nèi)存頁(yè)面在內(nèi)存0頁(yè)面未被訪問(wèn)頁(yè)面未被訪問(wèn)1 1頁(yè)面已被訪問(wèn)頁(yè)面已被訪問(wèn)0頁(yè)面未被修改頁(yè)面未被修改1 1頁(yè)面已被修改頁(yè)面已被修改判斷缺頁(yè)中斷判斷缺頁(yè)中斷影響頁(yè)影響頁(yè)面面置換策略置換策略是否重寫(xiě)外存是否重寫(xiě)外存 頁(yè)面存在位頁(yè)面存在位 P P 頁(yè)面修改位頁(yè)面修改位 M M 頁(yè)號(hào)頁(yè)號(hào)頁(yè)框號(hào)

11、頁(yè)框號(hào) 存取控制存取控制 北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)22頁(yè)表大小頁(yè)表大小 4GB虛擬空間分成虛擬空間分成512字節(jié)大小的頁(yè)，共字節(jié)大小的頁(yè)，共有有 4*230/29 = 4*221 = 8M個(gè)頁(yè)個(gè)頁(yè) 每個(gè)頁(yè)的頁(yè)表項(xiàng)占每個(gè)頁(yè)的頁(yè)表項(xiàng)占4個(gè)字節(jié)個(gè)字節(jié) 進(jìn)程頁(yè)表大小為進(jìn)程頁(yè)表大小為 8M*4B= 32MB北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)23解決辦法解決辦法 把頁(yè)表看作是在虛擬空間中把頁(yè)表看作是在虛擬空間中 整個(gè)頁(yè)表也被分頁(yè)整個(gè)頁(yè)表也被分頁(yè) 頁(yè)表不全部放在內(nèi)存中頁(yè)表不全部放在內(nèi)存中 每次系統(tǒng)只裝載頁(yè)表的一部分每次系統(tǒng)只裝載頁(yè)表的一部分 放在內(nèi)存中的頁(yè)表頁(yè)也不再連續(xù)存放放在內(nèi)存中的頁(yè)表頁(yè)也不再

12、連續(xù)存放 北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)24多級(jí)頁(yè)表多級(jí)頁(yè)表 頁(yè)目錄表頁(yè)目錄表 描述哪些頁(yè)表頁(yè)已經(jīng)在內(nèi)存中、哪些還不在描述哪些頁(yè)表頁(yè)已經(jīng)在內(nèi)存中、哪些還不在 在內(nèi)存中的頁(yè)表頁(yè)放在什么地方在內(nèi)存中的頁(yè)表頁(yè)放在什么地方北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)25多多級(jí)級(jí)頁(yè)頁(yè)表表北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)26兩級(jí)頁(yè)表結(jié)構(gòu)的地址轉(zhuǎn)換兩級(jí)頁(yè)表結(jié)構(gòu)的地址轉(zhuǎn)換北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)27倒排頁(yè)表倒排頁(yè)表 按頁(yè)框號(hào)排序按頁(yè)框號(hào)排序 每個(gè)頁(yè)框占有一個(gè)表項(xiàng)每個(gè)頁(yè)框占有一個(gè)表項(xiàng) 每個(gè)表項(xiàng)每個(gè)表項(xiàng) 存放在該頁(yè)框中頁(yè)面的虛擬頁(yè)號(hào)存放在該頁(yè)框中頁(yè)面的虛擬頁(yè)號(hào) 擁有該頁(yè)面的進(jìn)程標(biāo)識(shí)符擁有該頁(yè)面的進(jìn)程標(biāo)識(shí)符北

13、京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)28倒排頁(yè)表倒排頁(yè)表北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)29倒排頁(yè)表倒排頁(yè)表 節(jié)省空間節(jié)省空間 虛擬空間很大，如虛擬空間很大，如64位位 頁(yè)表大?。?yè)面大小為頁(yè)表大小（頁(yè)面大小為4KB，每個(gè)頁(yè)表項(xiàng)，每個(gè)頁(yè)表項(xiàng)8個(gè)字節(jié)）個(gè)字節(jié)） 8*264/212= 255= 235*220 = 235G 查找費(fèi)時(shí)查找費(fèi)時(shí) 按照虛擬頁(yè)號(hào)查找整個(gè)頁(yè)表按照虛擬頁(yè)號(hào)查找整個(gè)頁(yè)表 解決辦法解決辦法 散列頁(yè)表散列頁(yè)表 快表快表TLB北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)30散列頁(yè)表散列頁(yè)表 以頁(yè)號(hào)作為參數(shù)形成散列值以頁(yè)號(hào)作為參數(shù)形成散列值 散列表中每一項(xiàng)有一個(gè)鏈表散列表中每一項(xiàng)有一個(gè)鏈表 把有相

14、同散列值的元素鏈接起來(lái)把有相同散列值的元素鏈接起來(lái) 每個(gè)鏈表元素由三部分組成每個(gè)鏈表元素由三部分組成 頁(yè)號(hào)頁(yè)號(hào) 對(duì)應(yīng)的內(nèi)存塊號(hào)對(duì)應(yīng)的內(nèi)存塊號(hào) 指向鏈表中下一個(gè)元素的指針指向鏈表中下一個(gè)元素的指針北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)31散列頁(yè)表散列頁(yè)表北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)32關(guān)聯(lián)高速緩存關(guān)聯(lián)高速緩存TLB 實(shí)現(xiàn)虛擬內(nèi)存引入時(shí)間開(kāi)銷實(shí)現(xiàn)虛擬內(nèi)存引入時(shí)間開(kāi)銷 地址轉(zhuǎn)換的時(shí)間開(kāi)銷地址轉(zhuǎn)換的時(shí)間開(kāi)銷 讀取進(jìn)程的頁(yè)表、頁(yè)面目錄讀取進(jìn)程的頁(yè)表、頁(yè)面目錄 一次訪存變成兩次、三次訪存動(dòng)作一次訪存變成兩次、三次訪存動(dòng)作 CPU內(nèi)部設(shè)置專門用來(lái)存放頁(yè)表的緩存內(nèi)部設(shè)置專門用來(lái)存放頁(yè)表的緩存 放置最近經(jīng)常用

15、到的頁(yè)表項(xiàng)放置最近經(jīng)常用到的頁(yè)表項(xiàng)北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)33高速關(guān)聯(lián)緩存高速關(guān)聯(lián)緩存 提高查找頁(yè)表項(xiàng)的速度提高查找頁(yè)表項(xiàng)的速度 以其中某一存儲(chǔ)項(xiàng)內(nèi)容作為地址來(lái)存取的以其中某一存儲(chǔ)項(xiàng)內(nèi)容作為地址來(lái)存取的存儲(chǔ)器存儲(chǔ)器 也稱也稱TLB，Translation Lookaside Buffer（轉(zhuǎn)換檢測(cè)緩沖區(qū)）（轉(zhuǎn)換檢測(cè)緩沖區(qū)） 北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)34高速關(guān)聯(lián)緩存高速關(guān)聯(lián)緩存北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)35單元訪問(wèn)單元訪問(wèn) 訪問(wèn)虛擬地址單元的內(nèi)容訪問(wèn)虛擬地址單元的內(nèi)容 按照頁(yè)面的大小計(jì)算頁(yè)號(hào)查詢頁(yè)表按照頁(yè)面的大小計(jì)算頁(yè)號(hào)查詢頁(yè)表 檢查該頁(yè)表項(xiàng)中檢查該頁(yè)表項(xiàng)中 “存在存

16、在”標(biāo)志位標(biāo)志位 如果存在標(biāo)志位被設(shè)置如果存在標(biāo)志位被設(shè)置 按頁(yè)表項(xiàng)中的頁(yè)框號(hào)計(jì)算物理地址；按頁(yè)表項(xiàng)中的頁(yè)框號(hào)計(jì)算物理地址； 如果存在標(biāo)志位未被設(shè)置如果存在標(biāo)志位未被設(shè)置 缺頁(yè)異常缺頁(yè)異常北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)36缺頁(yè)異常缺頁(yè)異常 異常與中斷異常與中斷 異常異常 也稱為同步中斷也稱為同步中斷 在處理器執(zhí)行到由于編程失誤而導(dǎo)致的錯(cuò)誤指令在處理器執(zhí)行到由于編程失誤而導(dǎo)致的錯(cuò)誤指令時(shí)，或者在執(zhí)行期間出現(xiàn)特殊情況（如缺頁(yè)），時(shí)，或者在執(zhí)行期間出現(xiàn)特殊情況（如缺頁(yè)），必須靠?jī)?nèi)核處理時(shí)，處理器就會(huì)產(chǎn)生一個(gè)異常必須靠?jī)?nèi)核處理時(shí)，處理器就會(huì)產(chǎn)生一個(gè)異常 中斷中斷 外部硬件產(chǎn)生的一個(gè)電信號(hào)，從外部硬

17、件產(chǎn)生的一個(gè)電信號(hào)，從CPU的中斷引腳的中斷引腳進(jìn)入，打斷當(dāng)前進(jìn)入，打斷當(dāng)前CPU的運(yùn)行的運(yùn)行 把需要的內(nèi)容裝入到內(nèi)存中并設(shè)置相應(yīng)的把需要的內(nèi)容裝入到內(nèi)存中并設(shè)置相應(yīng)的頁(yè)表項(xiàng)頁(yè)表項(xiàng)北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)37缺缺頁(yè)頁(yè)中中斷斷北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)38多級(jí)頁(yè)表的使用多級(jí)頁(yè)表的使用 計(jì)算出頁(yè)表項(xiàng)位于哪個(gè)頁(yè)表頁(yè)中計(jì)算出頁(yè)表項(xiàng)位于哪個(gè)頁(yè)表頁(yè)中 根據(jù)頁(yè)表頁(yè)號(hào)查找頁(yè)目錄根據(jù)頁(yè)表頁(yè)號(hào)查找頁(yè)目錄 如果頁(yè)表項(xiàng)在內(nèi)存中如果頁(yè)表項(xiàng)在內(nèi)存中 得到頁(yè)表項(xiàng)在內(nèi)存中的位置，讀取頁(yè)表項(xiàng)、得到頁(yè)表項(xiàng)在內(nèi)存中的位置，讀取頁(yè)表項(xiàng)、找到頁(yè)框號(hào)、計(jì)算出物理地址、訪問(wèn)物理找到頁(yè)框號(hào)、計(jì)算出物理地址、訪問(wèn)物理單元單元

18、 如果頁(yè)表項(xiàng)未在內(nèi)存中，缺頁(yè)異常如果頁(yè)表項(xiàng)未在內(nèi)存中，缺頁(yè)異常 異常處理程序創(chuàng)建一個(gè)新的頁(yè)表頁(yè)異常處理程序創(chuàng)建一個(gè)新的頁(yè)表頁(yè)北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)39頁(yè)面的裝入頁(yè)面的裝入 預(yù)裝入預(yù)裝入 訪問(wèn)速度很快訪問(wèn)速度很快 浪費(fèi)空間浪費(fèi)空間 按需裝入按需裝入 不浪費(fèi)空間不浪費(fèi)空間 浪費(fèi)時(shí)間浪費(fèi)時(shí)間北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)40頁(yè)面的裝入頁(yè)面的裝入 通常操作系統(tǒng)會(huì)綜合利用這兩種方式通常操作系統(tǒng)會(huì)綜合利用這兩種方式 創(chuàng)建進(jìn)程時(shí)，為每個(gè)進(jìn)程預(yù)裝入一定數(shù)量創(chuàng)建進(jìn)程時(shí)，為每個(gè)進(jìn)程預(yù)裝入一定數(shù)量的頁(yè)面的頁(yè)面 當(dāng)進(jìn)程執(zhí)行到一定階段，需要新頁(yè)面時(shí)，當(dāng)進(jìn)程執(zhí)行到一定階段，需要新頁(yè)面時(shí)，再按需要裝入再按需

19、要裝入 裝入要訪問(wèn)的頁(yè)時(shí)捎帶把后面的頁(yè)也預(yù)裝裝入要訪問(wèn)的頁(yè)時(shí)捎帶把后面的頁(yè)也預(yù)裝入一些入一些 局部性原理局部性原理北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)41頁(yè)面的淘汰頁(yè)面的淘汰 盡量減少缺頁(yè)異常的發(fā)生盡量減少缺頁(yè)異常的發(fā)生 選擇以后再也不會(huì)用到的頁(yè)面淘汰選擇以后再也不會(huì)用到的頁(yè)面淘汰 選擇那些再次使用的時(shí)間距離現(xiàn)在最遠(yuǎn)的選擇那些再次使用的時(shí)間距離現(xiàn)在最遠(yuǎn)的頁(yè)面淘汰頁(yè)面淘汰北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)42淘汰算法淘汰算法 最優(yōu)策略（最優(yōu)策略（OPT） 先進(jìn)先出法（先進(jìn)先出法（FIFO） 第二次機(jī)會(huì)置換法（第二次機(jī)會(huì)置換法（SCR） 最近最少訪問(wèn)的策略（最近最少訪問(wèn)的策略（LRU） 簡(jiǎn)化形式的簡(jiǎn)

20、化形式的LRU 工作集算法工作集算法 工作集時(shí)鐘算法工作集時(shí)鐘算法北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)43最優(yōu)策略（最優(yōu)策略（OPT） 選擇以后再也不會(huì)用到的頁(yè)面淘汰選擇以后再也不會(huì)用到的頁(yè)面淘汰 選擇那些再次使用的時(shí)間距離現(xiàn)在最遠(yuǎn)的選擇那些再次使用的時(shí)間距離現(xiàn)在最遠(yuǎn)的頁(yè)面淘汰頁(yè)面淘汰北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)44最優(yōu)策略（最優(yōu)策略（OPT）北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)45最優(yōu)策略（最優(yōu)策略（OPT） 操作系統(tǒng)需要知道將來(lái)要使用的頁(yè)面順序操作系統(tǒng)需要知道將來(lái)要使用的頁(yè)面順序 作為一個(gè)最好的標(biāo)準(zhǔn)用在理想的實(shí)驗(yàn)環(huán)境作為一個(gè)最好的標(biāo)準(zhǔn)用在理想的實(shí)驗(yàn)環(huán)境下評(píng)測(cè)其他實(shí)用的淘汰策略下評(píng)測(cè)其他實(shí)

21、用的淘汰策略北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)46先進(jìn)先出（先進(jìn)先出（FIFO）法）法 直接換出最早裝入的頁(yè)面直接換出最早裝入的頁(yè)面 容易理解容易理解 方便程序設(shè)計(jì)方便程序設(shè)計(jì)北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)47先進(jìn)先出（先進(jìn)先出（FIFO）法）法北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)48先進(jìn)先出（先進(jìn)先出（FIFO）法）法 性能并不很好性能并不很好 缺點(diǎn)缺點(diǎn) 存在存在Belady異?，F(xiàn)象，即缺頁(yè)率隨內(nèi)存塊增異?，F(xiàn)象，即缺頁(yè)率隨內(nèi)存塊增加而增加加而增加 反常的現(xiàn)象：內(nèi)存中可裝入頁(yè)面數(shù)增加了，缺頁(yè)反常的現(xiàn)象：內(nèi)存中可裝入頁(yè)面數(shù)增加了，缺頁(yè)異常數(shù)反而也增加了異常數(shù)反而也增加了 淘汰的是常用頁(yè)面淘汰的

22、是常用頁(yè)面北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)49第二次機(jī)會(huì)置換法（第二次機(jī)會(huì)置換法（SCR） Second Chance Page Replacement, SCR 對(duì)對(duì)FIFO算法的改進(jìn)算法的改進(jìn) 避免把經(jīng)常使用的頁(yè)面置換出去避免把經(jīng)常使用的頁(yè)面置換出去 按時(shí)間順序檢查按時(shí)間順序檢查 設(shè)置頁(yè)面訪問(wèn)位，檢查隊(duì)首頁(yè)面的訪問(wèn)位設(shè)置頁(yè)面訪問(wèn)位，檢查隊(duì)首頁(yè)面的訪問(wèn)位 0： 淘汰該頁(yè)；淘汰該頁(yè)；1：轉(zhuǎn)移到隊(duì)尾，給第二次機(jī)會(huì)：轉(zhuǎn)移到隊(duì)尾，給第二次機(jī)會(huì)北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)時(shí)鐘置換法（時(shí)鐘置換法（Clock） 將頁(yè)面保存在環(huán)形鏈表中將頁(yè)面保存在環(huán)形鏈表中 避免避免SCR法法在鏈表中移動(dòng)頁(yè)面在鏈表

23、中移動(dòng)頁(yè)面50北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)51最近最少訪問(wèn)的策略最近最少訪問(wèn)的策略 LRU，Least Recently Used 猜測(cè)將來(lái)可能訪問(wèn)的頁(yè)面序列猜測(cè)將來(lái)可能訪問(wèn)的頁(yè)面序列 如果一個(gè)頁(yè)面很久沒(méi)有被訪問(wèn)，根據(jù)局部如果一個(gè)頁(yè)面很久沒(méi)有被訪問(wèn)，根據(jù)局部性原理，將來(lái)被訪問(wèn)的可能性也比較小性原理，將來(lái)被訪問(wèn)的可能性也比較小 選擇未被訪問(wèn)時(shí)間最長(zhǎng)的那些頁(yè)面換出選擇未被訪問(wèn)時(shí)間最長(zhǎng)的那些頁(yè)面換出北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)52LRU策略策略北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)53最近最少訪問(wèn)的策略最近最少訪問(wèn)的策略 為每個(gè)在內(nèi)存中的頁(yè)面維持一個(gè)計(jì)時(shí)器為每個(gè)在內(nèi)存中的頁(yè)面維持一個(gè)計(jì)時(shí)器

24、頁(yè)面被訪問(wèn)時(shí)，計(jì)時(shí)器清頁(yè)面被訪問(wèn)時(shí)，計(jì)時(shí)器清0，否則隨時(shí)間增長(zhǎng)，否則隨時(shí)間增長(zhǎng) 操作系統(tǒng)要淘汰頁(yè)面時(shí)，比較頁(yè)面計(jì)時(shí)器，操作系統(tǒng)要淘汰頁(yè)面時(shí)，比較頁(yè)面計(jì)時(shí)器，選出時(shí)間最長(zhǎng)的頁(yè)面選出時(shí)間最長(zhǎng)的頁(yè)面 實(shí)驗(yàn)表明實(shí)驗(yàn)表明LRU的效果比的效果比FIFO要好要好北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)54簡(jiǎn)化形式的簡(jiǎn)化形式的LRU LRU策略的實(shí)現(xiàn)開(kāi)銷非常大策略的實(shí)現(xiàn)開(kāi)銷非常大 為每個(gè)頁(yè)設(shè)置一個(gè)標(biāo)志位，表示這個(gè)頁(yè)為每個(gè)頁(yè)設(shè)置一個(gè)標(biāo)志位，表示這個(gè)頁(yè)面最近是否被訪問(wèn)過(guò)，稱為訪問(wèn)位面最近是否被訪問(wèn)過(guò)，稱為訪問(wèn)位 通常設(shè)置在每個(gè)頁(yè)的頁(yè)表項(xiàng)中通常設(shè)置在每個(gè)頁(yè)的頁(yè)表項(xiàng)中 頁(yè)面被訪問(wèn)時(shí)，訪問(wèn)位設(shè)置為頁(yè)面被訪問(wèn)時(shí)，訪問(wèn)位設(shè)置為1

25、 操作系統(tǒng)定期將所有頁(yè)面的訪問(wèn)位清操作系統(tǒng)定期將所有頁(yè)面的訪問(wèn)位清0 當(dāng)操作系統(tǒng)需要挑選頁(yè)面換出時(shí)，選擇當(dāng)操作系統(tǒng)需要挑選頁(yè)面換出時(shí)，選擇訪問(wèn)位為訪問(wèn)位為0的頁(yè)面的頁(yè)面 使用最多的策略使用最多的策略北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)工作集替換算法工作集替換算法 工作集工作集 一個(gè)進(jìn)程當(dāng)前正在使用的頁(yè)面的集合一個(gè)進(jìn)程當(dāng)前正在使用的頁(yè)面的集合 working set 若整個(gè)工作集都被裝入內(nèi)存，若整個(gè)工作集都被裝入內(nèi)存， 進(jìn)程在運(yùn)進(jìn)程在運(yùn)行到下一運(yùn)行階段前，不會(huì)產(chǎn)生很多缺頁(yè)行到下一運(yùn)行階段前，不會(huì)產(chǎn)生很多缺頁(yè)中斷中斷 找出一個(gè)不在工作集中的頁(yè)面并淘汰它找出一個(gè)不在工作集中的頁(yè)面并淘汰它 工作集工作集

26、w(k, t) 在任一時(shí)刻在任一時(shí)刻t，包含所有最近，包含所有最近k次內(nèi)存訪問(wèn)所次內(nèi)存訪問(wèn)所訪問(wèn)過(guò)的頁(yè)面的一個(gè)集合訪問(wèn)過(guò)的頁(yè)面的一個(gè)集合55北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)工作集替換算法工作集替換算法 工作集模型工作集模型 設(shè)法跟蹤進(jìn)程的工作集，以確保在讓進(jìn)程運(yùn)設(shè)法跟蹤進(jìn)程的工作集，以確保在讓進(jìn)程運(yùn)行以前，它的工作集就已在內(nèi)存中了行以前，它的工作集就已在內(nèi)存中了 跟蹤進(jìn)程的工作集跟蹤進(jìn)程的工作集 用長(zhǎng)度為用長(zhǎng)度為k的移位寄存器，每次內(nèi)存訪問(wèn)把寄的移位寄存器，每次內(nèi)存訪問(wèn)把寄存器左移一位，在最右端插入剛訪問(wèn)的頁(yè)面存器左移一位，在最右端插入剛訪問(wèn)的頁(yè)面號(hào)號(hào) 缺頁(yè)時(shí)，讀出移位寄存器內(nèi)容并排序，刪除

27、缺頁(yè)時(shí)，讀出移位寄存器內(nèi)容并排序，刪除重復(fù)的頁(yè)面，即得到工作集重復(fù)的頁(yè)面，即得到工作集 維護(hù)移位寄存器并在缺頁(yè)中斷時(shí)處理它所需維護(hù)移位寄存器并在缺頁(yè)中斷時(shí)處理它所需的開(kāi)銷很大，從未被用過(guò)的開(kāi)銷很大，從未被用過(guò)56北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)工作集替換算法工作集替換算法 頁(yè)表設(shè)置頁(yè)表設(shè)置“訪問(wèn)位訪問(wèn)位”、上次訪問(wèn)近似時(shí)間、上次訪問(wèn)近似時(shí)間 定期的時(shí)鐘中斷用軟件方法清除訪問(wèn)位定期的時(shí)鐘中斷用軟件方法清除訪問(wèn)位 替換算法過(guò)程替換算法過(guò)程 檢查頁(yè)面的訪問(wèn)位，若訪問(wèn)位檢查頁(yè)面的訪問(wèn)位，若訪問(wèn)位 1：把當(dāng)前實(shí)際時(shí)間寫(xiě)進(jìn)頁(yè)表項(xiàng)的：把當(dāng)前實(shí)際時(shí)間寫(xiě)進(jìn)頁(yè)表項(xiàng)的“上次使用時(shí)間上次使用時(shí)間”域，以表示缺頁(yè)中斷發(fā)生時(shí)該頁(yè)面正在被使用域，以表示缺頁(yè)中斷發(fā)生時(shí)該頁(yè)面正在被使用 該頁(yè)面在當(dāng)前時(shí)鐘滴答中已經(jīng)被訪問(wèn)過(guò)，在工作集中，該頁(yè)面在當(dāng)前時(shí)鐘滴答中已經(jīng)被訪問(wèn)過(guò)，在工作集中，不應(yīng)該被刪除不應(yīng)該被刪除 若所有頁(yè)面都被訪問(wèn)過(guò)，則隨機(jī)選擇若所有頁(yè)面都被訪問(wèn)過(guò)，則隨機(jī)選擇57北京工業(yè)大學(xué)軟件學(xué)院 張麗操作系統(tǒng)工作集替換算法工作集替換算法 替換算法過(guò)程替換算法過(guò)程 檢查頁(yè)面的訪問(wèn)位，若