第7章 存儲(chǔ)管理

1、第第7 7章章 存儲(chǔ)管理存儲(chǔ)管理 主講：房道偉主講：房道偉Daowei_操作系統(tǒng)原理操作系統(tǒng)原理今天雖然主存價(jià)格已相當(dāng)便宜，但主存容量仍今天雖然主存價(jià)格已相當(dāng)便宜，但主存容量仍然是計(jì)算機(jī)四大硬件資源中最關(guān)鍵而又最緊張的然是計(jì)算機(jī)四大硬件資源中最關(guān)鍵而又最緊張的“ 瓶頸瓶頸”資源。因此對(duì)主存的管理和有效使用仍然資源。因此對(duì)主存的管理和有效使用仍然是今天操作系統(tǒng)十分重要的內(nèi)容。許多操作系統(tǒng)之是今天操作系統(tǒng)十分重要的內(nèi)容。許多操作系統(tǒng)之間最明顯的區(qū)別特征之一往往是所使用的存儲(chǔ)管理間最明顯的區(qū)別特征之一往往是所使用的存儲(chǔ)管理方法不同。如方法不同。如OS/360-MFT采用采用固定分區(qū)固定分區(qū)存儲(chǔ)管理技

2、存儲(chǔ)管理技術(shù)，術(shù)，OS/360-MTV是采用是采用可變分區(qū)可變分區(qū)存儲(chǔ)管理技術(shù)，存儲(chǔ)管理技術(shù)，OS/2，WindowsNT, 是采用是采用虛擬存儲(chǔ)虛擬存儲(chǔ)管理技術(shù)。管理技術(shù)。主存儲(chǔ)器管理技術(shù)可分為兩大類：實(shí)存儲(chǔ)器管主存儲(chǔ)器管理技術(shù)可分為兩大類：實(shí)存儲(chǔ)器管理和虛擬存儲(chǔ)器管理。理和虛擬存儲(chǔ)器管理。主要內(nèi)容7.1 主存管理的基礎(chǔ)主存管理的基礎(chǔ)(1) 主存的物理組織和邏輯組織主存的物理組織和邏輯組織(a) 存儲(chǔ)器分三級(jí)：存儲(chǔ)器分三級(jí)：為能更多的存放并更快地處理用戶信息目前許多計(jì)算機(jī)把存儲(chǔ)器分為三級(jí)。高速緩存主存外存cpu可訪n+k 幾百knM 幾百M(fèi)n+MnG(G=1kn)用戶的程序在運(yùn)行時(shí)應(yīng)存放在主

3、存中，以便處理用戶的程序在運(yùn)行時(shí)應(yīng)存放在主存中，以便處理機(jī)訪問。但是由于主存容量有限。所以把那些不馬上機(jī)訪問。但是由于主存容量有限。所以把那些不馬上使用的程序、數(shù)據(jù)放在外部存儲(chǔ)器使用的程序、數(shù)據(jù)放在外部存儲(chǔ)器(又稱次級(jí)存儲(chǔ)又稱次級(jí)存儲(chǔ))中。中。當(dāng)用到時(shí)再把它們讀入主存。圖當(dāng)用到時(shí)再把它們讀入主存。圖7.1中的三級(jí)存儲(chǔ)器，中的三級(jí)存儲(chǔ)器，從高速緩沖存儲(chǔ)器從高速緩沖存儲(chǔ)器(簡(jiǎn)稱緩存簡(jiǎn)稱緩存)到外部存儲(chǔ)器到外部存儲(chǔ)器(以后簡(jiǎn)稱以后簡(jiǎn)稱外存外存)，其容量愈來愈大，而訪問數(shù)據(jù)的速度則愈來愈，其容量愈來愈大，而訪問數(shù)據(jù)的速度則愈來愈慢，價(jià)格也愈來愈便宜，如慢，價(jià)格也愈來愈便宜，如IBM的緩存的最大傳輸速的

4、緩存的最大傳輸速度為每雙字度為每雙字120225毫微秒，主存的傳輸速度每字毫微秒，主存的傳輸速度每字1微微秒。秒。)(b) 程序只能在主存中運(yùn)行程序只能在主存中運(yùn)行(c) 物理地址：物理地址：(需要區(qū)分存貯體中不同的存需要區(qū)分存貯體中不同的存貯單元，統(tǒng)一編號(hào)貯單元，統(tǒng)一編號(hào), 這些編這些編號(hào)稱為地址號(hào)稱為地址)與地址有關(guān)：20根2201M32根2324G物理地址是主存的真實(shí)地址 絕對(duì)地址物理地址的集合間 存貯空間它是：存儲(chǔ)控制部件能夠識(shí)別的主存單元編號(hào)(或字節(jié)地址)。(d)邏輯地址：又稱相對(duì)地址，是指相對(duì)于某個(gè)邏輯地址：又稱相對(duì)地址，是指相對(duì)于某個(gè)基準(zhǔn)量基準(zhǔn)量(通常用通常用0)編址時(shí)所使用的編

5、址時(shí)所使用的地址，相對(duì)地址常用于程序編寫地址，相對(duì)地址常用于程序編寫和編譯過程中。和編譯過程中。名空間 由程序員所寫符號(hào)組成。地址空間 一個(gè)目標(biāo)程序所限定的地址集合。Address: mov Ax,1Obj 目標(biāo)地址名空間編譯地址空間EXE文件裝入存貯空間(2) 存貯管理功能：存貯管理功能：(a) 映射邏輯地址為存貯地址地址映射映射邏輯地址為存貯地址地址映射(b) 在多個(gè)用戶間分配主存主存分配在多個(gè)用戶間分配主存主存分配研究主存分配算法，以及算法的性能(c) 對(duì)主存中信息提供保護(hù)存貯保護(hù)對(duì)主存中信息提供保護(hù)存貯保護(hù)(d) 擴(kuò)充邏輯存區(qū)主存擴(kuò)充擴(kuò)充邏輯存區(qū)主存擴(kuò)充(這里指的擴(kuò)充并非指這里指的擴(kuò)充

6、并非指硬件設(shè)備上的擴(kuò)充，而是用存儲(chǔ)管理軟件來實(shí)硬件設(shè)備上的擴(kuò)充，而是用存儲(chǔ)管理軟件來實(shí)現(xiàn)邏輯上的擴(kuò)充即所謂的虛擬存貯技術(shù)現(xiàn)邏輯上的擴(kuò)充即所謂的虛擬存貯技術(shù))(I) 地址映射地址映射(重定位重定位)(a) 執(zhí)行指令時(shí)，必須將地址變?yōu)榻^對(duì)地址才可執(zhí)行指令時(shí)，必須將地址變?yōu)榻^對(duì)地址才可訪問系統(tǒng)分配的內(nèi)存。訪問系統(tǒng)分配的內(nèi)存。存貯空間地址空間程序執(zhí)行時(shí)，必須將邏輯地址正確地轉(zhuǎn)換為物理地址即地址映射。mov Ax,(500)12.30100500100011001500mov Ax,(500)12.3裝入主存出錯(cuò)解決方法：重定位(b) 使一個(gè)作業(yè)程序裝入到與其地址空間不一致使一個(gè)作業(yè)程序裝入到與其地址空

7、間不一致的存貯空間，所引起的對(duì)有關(guān)地址部分的調(diào)的存貯空間，所引起的對(duì)有關(guān)地址部分的調(diào)整過程稱為地址重定位。整過程稱為地址重定位。邏輯地址 物理地址(c) 地址映射的方式：地址映射的方式： 編程或編譯對(duì)確定地址映射關(guān)系，不靈活。 靜態(tài)地址映射 在裝入時(shí)實(shí)現(xiàn)調(diào)整 地址要有標(biāo)識(shí) 每裝入時(shí)都可要定位 裝入后不再變(靜態(tài)) 動(dòng)態(tài)重定位 在執(zhí)行尋址時(shí)重定位 訪問地址時(shí)通過地址變換機(jī)構(gòu)改變?yōu)閮?nèi)存地址mov Ax (500)12.3mov Ax (500)12.31005001100150010001000cpu運(yùn)行主存B特點(diǎn)：特點(diǎn)：(1) 任意裝入內(nèi)存區(qū)域 (不要求占用一個(gè)連續(xù)的內(nèi)存)(2) 只裝入部分代碼

8、即可運(yùn)行(3) 改變系統(tǒng)時(shí)不需改程序(程序占用的內(nèi)存空間、動(dòng)態(tài)可變，主程序從某一個(gè)存貯區(qū)域移動(dòng)時(shí)，只需修改得定位存器B即可)(4) 程序可共享(II) 主存分配：主存分配：(a) 分配策略分配策略(計(jì)算計(jì)算)放置策略 決定放的位置調(diào)入策略 裝入時(shí)機(jī)(什么時(shí)刻調(diào)入)淘汰策略 建立空閑區(qū)(b) 數(shù)據(jù)結(jié)構(gòu)：隊(duì)、表數(shù)據(jù)結(jié)構(gòu)：隊(duì)、表(c) 地址映射地址映射(III) 存貯保護(hù)：存貯保護(hù)：越界保護(hù)范圍存貯鍵保護(hù)存貯權(quán)限(IV) 主存擴(kuò)充：邏輯存貯區(qū)擴(kuò)充主存擴(kuò)充：邏輯存貯區(qū)擴(kuò)充(利用輔存)(1)單一連續(xù)區(qū)分配單一連續(xù)區(qū)分配(a)概要：存區(qū)分為概要：存區(qū)分為o.s連續(xù)區(qū)和用戶連續(xù)區(qū)連續(xù)區(qū)和用戶連續(xù)區(qū)o.s區(qū)用

9、戶區(qū)越界R受保護(hù)o.s存取區(qū)特權(quán)管態(tài)目態(tài)7.2 實(shí)存管理實(shí)存管理 (b) 簡(jiǎn)單、低放、單一用戶簡(jiǎn)單、低放、單一用戶單用戶o.s的內(nèi)存管理十分簡(jiǎn)單，因?yàn)榇尜A器在任何時(shí)候都只保存一個(gè)用戶進(jìn)程，除o.s本身占據(jù)的內(nèi)存外都可分配給用戶使用。方案：方案： o.s可以占據(jù)可以占據(jù)RAM的底部的底部(a)或頂部或頂部(b) 也可以部分在內(nèi)存頂部的也可以部分在內(nèi)存頂部的Rom中，另一中，另一部分存放部分存放RAM底部底部(c)IBM PC在MS/Dos下，其內(nèi)存分配便條用(c) 其裝有設(shè)備驅(qū)動(dòng)程序的8k.Rom占據(jù)IM地址空間的最高區(qū)通常稱Rom中的這些設(shè)備驅(qū)動(dòng)程序?yàn)锽IOS用戶程序o.s(a)用戶程序o.s

10、(b)Rom設(shè)備驅(qū)動(dòng)程序o.s用戶程序(c)(2) 固定分區(qū)：把主存分成若干個(gè)固定大小的存固定分區(qū)：把主存分成若干個(gè)固定大小的存儲(chǔ)區(qū)儲(chǔ)區(qū)(存儲(chǔ)塊存儲(chǔ)塊)(a) 概要：主存被劃分為多個(gè)分區(qū)，每個(gè)分區(qū)分給概要：主存被劃分為多個(gè)分區(qū)，每個(gè)分區(qū)分給某一作業(yè)使用，并由分區(qū)說明表指明某一作業(yè)使用，并由分區(qū)說明表指明作業(yè)按區(qū)分配直到該作業(yè)完成后才把作業(yè)按區(qū)分配直到該作業(yè)完成后才把該存儲(chǔ)區(qū)歸返系統(tǒng)。該存儲(chǔ)區(qū)歸返系統(tǒng)。o.s區(qū)20k28k60k90k128k256k0區(qū)1區(qū)2區(qū)3區(qū)4區(qū)區(qū)號(hào) 大小起址狀態(tài)123420k28k60k128kin usingNuL8k32k68k128kin usingNuL(存貯分

11、塊表MBT)固固定定分分區(qū)區(qū)分分配配算算法法大大區(qū)區(qū)圖圖要求xk大小的分區(qū)取分區(qū)說明表的第一項(xiàng)該分區(qū)空閑嗎？分區(qū)大小xk表結(jié)束嗎？返回分區(qū)號(hào)狀態(tài)位置1無法分配取下一項(xiàng)NNNYYY(b) 特點(diǎn)特點(diǎn)由操作員劃分分區(qū)MBT應(yīng)放在操作系統(tǒng)區(qū)內(nèi)，填分區(qū)表多道程序零頭缺點(diǎn)：缺點(diǎn)：不允許兩個(gè)作業(yè)同時(shí)放于同一個(gè)分區(qū)中剩下的空閑部分稱為內(nèi)存碎片內(nèi)存碎片，降低了主存利用率。(3) 可變分區(qū)可變分區(qū)(a) 概要：概要：存貯空間的劃分在作業(yè)裝入時(shí)進(jìn)行(事先并未劃分成一塊塊分區(qū))，且使分區(qū)大小與作業(yè)大小一致(按作業(yè)大小建立)分區(qū)大小、個(gè)數(shù)，不固定的(系統(tǒng)啟動(dòng)時(shí)，整個(gè)主存除o.s塊外，其余主存區(qū)可看成是整個(gè)一個(gè)分區(qū))。O

12、.S自由分區(qū)0512k1536k序號(hào) 大小起址狀態(tài)1234312k320k384k已分已分8k32k120k空表目已分5空表目大小起址狀態(tài)352k504k自由空表目32k520k自由空表目空表目已分配分區(qū)表已分配分區(qū)表 UBT表表自由分區(qū)表自由分區(qū)表FBT20k28k94k232k248ko.s區(qū)Job1(8k)Job2(16k)Job4(50k)Job3(124k)Job5(16k)44k108k256k分裂分裂 來了job4(50k), job5(16k)未分配分區(qū)表(自由分區(qū)表)FBT的變化序號(hào)大小起址狀態(tài)1264k14k24k8k44k94k232k248k自由自由 job2, job

13、3完成后、釋放(如下圖) o.s區(qū)Job1 Job4 Job5合并空申請(qǐng)分配一個(gè)xk大小的分區(qū)置空白區(qū)號(hào)F1(F)的狀態(tài)可用？空白區(qū)F大小xk？loc(F)的始址否是請(qǐng)求主存塊程序框圖請(qǐng)求主存塊程序框圖F未分配表的結(jié)尾？置空白區(qū)F，F(xiàn)的狀態(tài)空表目(F)的大小xk(F)的大小loc+xk (F)的始邊在分配表中找一個(gè)狀態(tài)空表目的分區(qū)P置P分區(qū)的大小xk置P分區(qū)的地址loc置狀態(tài)已分配返回一個(gè)分區(qū)號(hào)P本次無法分配一個(gè)分區(qū)F+1Fnk，但不能裝入nk作業(yè)(iii) 解決的方法：(I) 將程序裝入分散存區(qū)中 多重分區(qū)Job1Job2Job3RR11RR 12Job4部分2Job4部分1RR21RR22

14、(II) 將碎片集中(緊湊或拼接) 可重定位分配Job1Job2Job3Job4可重定位分區(qū)分配法是利用分區(qū)的“ 拼接”(對(duì)空白區(qū)而言)或“ 緊湊”(作業(yè)程序而言)技術(shù)解決“ 零頭”。(4) 可重定位分區(qū)分配可重定位分區(qū)分配(a) 概要：概要：移動(dòng)內(nèi)存已分配區(qū)的信息，使得所有分配區(qū)靠在一起使空白區(qū)連成一片，采用浮動(dòng)方法。(b) 浮動(dòng)浮動(dòng)(重定位動(dòng)態(tài)重定位動(dòng)態(tài))進(jìn)行主存的壓縮，就進(jìn)行主存的壓縮，就要將主存中用戶程序移動(dòng)要將主存中用戶程序移動(dòng)(浮動(dòng)浮動(dòng))，對(duì)作業(yè)，對(duì)作業(yè)中與地址有關(guān)的部分進(jìn)行調(diào)整。中與地址有關(guān)的部分進(jìn)行調(diào)整。請(qǐng)求分配一個(gè)大小為xk的分區(qū)有大于xk的空閑區(qū)嗎？空閑區(qū)的總和xk嗎？緊縮

15、存儲(chǔ)并相應(yīng)地修改諸表(得到一個(gè)完整的空閑區(qū)xk)分配分區(qū)并修改諸表此刻已經(jīng)分配一個(gè)分區(qū)返回一個(gè)分區(qū)號(hào)數(shù)是是否否(c) 動(dòng)態(tài)重定位可變分區(qū)分配算法：動(dòng)態(tài)重定位可變分區(qū)分配算法：20k28k88k132k182ko.s作業(yè)1(8k)(36k)作業(yè)3(24k)(24k)作業(yè)2(20k)作業(yè)4(50k)(74k)64k112k256k(a)初始狀態(tài)20k202ko.s1324作業(yè)5(80k)(54k)122k(c)分配作業(yè)5之后(b)移動(dòng)之后(即浮動(dòng))20k28k72ko.s1(8k)3(24k)2(20k)4(50k)(134k)52k122k256k作業(yè)580k實(shí)現(xiàn)這種重定位，可通過類似于重定位裝

16、入程序的軟件來達(dá)到，但這種方案要在費(fèi)許多處理機(jī)時(shí)間，而且限制較大。較好的辦法是采用動(dòng)態(tài)重定位技術(shù)(在本章中，當(dāng)一個(gè)作業(yè)裝入與其地址空間不一致的存儲(chǔ)空間時(shí)，可在每次訪問指令或數(shù)據(jù)時(shí)，通過重定位寄存器來自動(dòng)修改訪問存儲(chǔ)器的地址)因而，一個(gè)作業(yè)在主存中移動(dòng)后，只需要改變重定位寄存器的內(nèi)容即可。圖(a)是作業(yè)拼接之前的執(zhí)行情況，這時(shí)重定位寄存器RR的值為64k，(b)是拼接后作業(yè)3執(zhí)行情況，作業(yè)3被移動(dòng)到28k大字節(jié)開始的分區(qū)中。為保證在新的位置上仍能正確執(zhí)行，只需要將重點(diǎn)定位寄存器RR的值改為28k即可。LDAD 1,50012345Load 1,5001 2 3 4 550064K0100500R

17、R656366603664作業(yè)3的分區(qū)88K處理機(jī)一側(cè)存貯器一側(cè)(a) 拼接前相對(duì)地址定位寄存器Load 1,50012345Load 1,5001 2 3 4 550028K0100500RR287722917228k(b) 拼接后的執(zhí)行情況52k256k主存24k相對(duì)地址定位寄存器采取動(dòng)態(tài)重定位后，由于目標(biāo)程序裝入主存后不需修改地址指針及所有與地址有關(guān)的項(xiàng)，因而程序可在主存中隨意浮動(dòng)而不影響其正確執(zhí)行。這樣，就可以方便地進(jìn)行存儲(chǔ)器緊縮，較好地解決了碎片問題。(d) 拼湊時(shí)機(jī)拼湊時(shí)機(jī)(i) 出現(xiàn)相鄰空白區(qū)即拼接；(或某分區(qū)被釋放后即緊縮)(ii) 存貯不足(空白分區(qū)不夠大)時(shí)進(jìn)行拼接緊縮工作

18、大，開銷大，但管理簡(jiǎn)單緊縮次數(shù)少，但管理(算法)較復(fù)雜。前面已有框圖表示(5) 多重分區(qū)分配不拼接而解決零頭問題多重分區(qū)分配不拼接而解決零頭問題(a) 概要概要將程序分為若干段，按小段申請(qǐng)存區(qū)，即將程序分散在不連續(xù)存區(qū)中運(yùn)行。程序：程序、數(shù)據(jù)區(qū)等(也可解決共亨信息問題)：給一個(gè)作業(yè)分配二個(gè)分區(qū)o.s作A 0區(qū)作A 1區(qū)下界0上界0下界1上界1采用動(dòng)態(tài)重定位技術(shù)： 利用下界寄存器作為重定位Reg 而上界可供檢查地址越界用在實(shí)存管理技術(shù)中，多重分區(qū)的多重程序不宜過多，否則會(huì)增加管理的復(fù)雜性，一般不超過34對(duì)界地址寄存器。多重分區(qū)技術(shù)的進(jìn)一步發(fā)展導(dǎo)致了段式虛擬存儲(chǔ)管理技術(shù)的出現(xiàn)。(6) 覆蓋覆蓋(o

19、verlay): 指一個(gè)作業(yè)的若干程序段指一個(gè)作業(yè)的若干程序段(或數(shù)據(jù)或數(shù)據(jù)段段)或幾個(gè)作業(yè)的某些部分間共享某主存空間或幾個(gè)作業(yè)的某些部分間共享某主存空間(a) 目標(biāo)：用較小的存區(qū)滿足較大的存區(qū)要求目標(biāo)：用較小的存區(qū)滿足較大的存區(qū)要求(b) 程序的分析：并不是作業(yè)的每一部分都是時(shí)時(shí)程序的分析：并不是作業(yè)的每一部分都是時(shí)時(shí)要用的要用的mainA 20kA0, 30kB0, 40kB1, 30kA2, 30kA1, 60kA4, 40kA3, 20kB0, 40kB1, 30kA1, 60kA2, 30kA3, 20kA4, 40kmain20k覆蓋段040k覆蓋段160k覆蓋段240kAmain

20、20kA0, 30k則總計(jì)270k 160k內(nèi)存即可可裝入(c) 注意：注意：(i) 每次僅放入作業(yè)的一個(gè)部分(ii) 覆蓋段程序員事先確定(iii) 系統(tǒng)自動(dòng)覆蓋虛存(iv) 可與其內(nèi)存分配方法結(jié)合使用(7) 交換：交換：(swapping)(a) 目標(biāo)：解決小主存分區(qū)大作業(yè)的矛盾目標(biāo)：解決小主存分區(qū)大作業(yè)的矛盾 利用輔存利用輔存(b) 概要：概要：將主存中已阻塞的作業(yè)信息存入輔存，將輔存中的活動(dòng)作業(yè)調(diào)入主存并運(yùn)行。job1job2job3job1job2job1job2job3job3job1主存輔存上部上部下部job3job2job2覆蓋的部分保存好！Job2下部Job1 Job3 主存

21、大小作業(yè)無法運(yùn)行“ 擴(kuò)充”主存 虛擬存貯技術(shù)(b) 虛擬存貯器：虛擬存貯器：地址空間存貯空間(編程)(運(yùn)行)邏輯物理虛空間(虛存)實(shí)存、實(shí)空間交換o.s 程序的訪問地址稱為虛地址而程序可訪問的虛地址范圍叫做程序的虛地址空間。 可使用的實(shí)地址范圍叫實(shí)地址空間(即主存)(c) 虛空間獨(dú)立于實(shí)空間虛空間獨(dú)立于實(shí)空間虛空間實(shí)空間(也可以虛空間實(shí)空間)系統(tǒng)地址空間 虛存空間地址結(jié)構(gòu)20位有效地址長(zhǎng)度 0220(尋址范圍)，實(shí)存64k虛存220作業(yè)可以大于內(nèi)存，部分作業(yè)調(diào)入運(yùn)行，其余放入磁盤。利用輔存存放放不進(jìn)內(nèi)存的作業(yè)部分。 主存輔存虛擬存(僅與地址結(jié)構(gòu)有關(guān))(2) 分頁存貯管理：分頁存貯管理：(a)

22、實(shí)現(xiàn)原理：實(shí)現(xiàn)原理：地址空間分成大小相同的部分 頁存貯空間分成大小相同的部分 塊(頁架)頁大小塊大小頁大小塊大小頁號(hào)塊號(hào)狀態(tài)012238該頁是否在內(nèi)存分配時(shí)頁對(duì)應(yīng)塊，但不要求連續(xù)頁表(PMT)又稱頁面映象表由內(nèi)存一個(gè)特殊區(qū)域擔(dān)任重定位(地址變換)包括：頁號(hào)，塊號(hào)以及狀態(tài)mov Ax (2500)mov AX (2500)123 頁號(hào) 塊號(hào)012238頁表2頁0頁頁 1k分3頁0塊1塊2塊3塊8塊01k2k3k9k8k4k1k2k3k1002500250010242452作業(yè)地址空間1頁邏輯地址的表示(p, d)P = INT A/L；d = A mod L其中A：虛地址 L：頁大小P ：頁號(hào)

23、d：頁內(nèi)位移例：2452頁塊012238頁表長(zhǎng) 頁表始址8452123實(shí)地址虛地址(頁)d (偏移)P(頁)9k8644頁表地址reg+例：設(shè)虛地址為(357101)8 每一塊為128字節(jié)12827(357101)8( 01 110 111 100 1 000 001)21 6 7 4 101偏移為(101)8, 頁號(hào)為(1674)8塊號(hào)由頁表指定，偏移不變(b) 多級(jí)頁表的地址轉(zhuǎn)換多級(jí)頁表的地址轉(zhuǎn)換進(jìn)程的頁表表目可達(dá)222個(gè)。而Windows NT 等使用x86的CPU的32位地址，使用4KB的頁面(212)，這意味著進(jìn)程最多可以使用多達(dá)220(100多萬)個(gè)頁面。如果每個(gè)頁表表目占4byt

24、e，那么每個(gè)進(jìn)程的頁表所占的空間是222byte，占去主存的1的空間，顯然這樣大的頁表是不能全放在主存中的。為此對(duì)頁表本身也采取分頁措施。即把頁表本身按固定大小分成為一個(gè)個(gè)頁面(頁面大小為 212=4KB)。每個(gè)小頁表形成的頁面中可以有2101K個(gè)頁表表目（每個(gè)表目4byte），共有2101K個(gè)小頁表。為了對(duì)1K個(gè)小頁表進(jìn)行管理和索引查找，設(shè)置一個(gè)頁表目錄，又稱之為頂級(jí)頁表，該頂級(jí)頁表包含有1K個(gè)表目項(xiàng)，分別指出每個(gè)次級(jí)小頁表所在物理頁號(hào)和其他有關(guān)狀態(tài)信息。這樣，每個(gè)進(jìn)程有一個(gè)頁目錄，它的每個(gè)表目映射一個(gè)頁表。頁目錄本身大小剛好是一個(gè)頁面大小，頁目錄是一級(jí)表。而每個(gè)小頁表本身就是二級(jí)頁表。以后

25、一律使用頁目錄和頁表的名稱。頁目錄寄存器當(dāng)前進(jìn)程頁目錄31110頁架號(hào)+面目錄號(hào) 頁號(hào) 偏移虛擬地址+3112 110 頁架號(hào)頁架號(hào) 偏移物理地址3122 21 12 11 0當(dāng)前進(jìn)程的某個(gè)次級(jí)頁表31 12 110二級(jí)頁表地址變換通過二級(jí)頁表的地址映射訪問主存存取數(shù)據(jù)需要三次訪問主存（一次頁目錄，一次頁表，最后是數(shù)據(jù)所在物理地址），所需時(shí)間是原來的三倍。當(dāng)然對(duì)64位的地址，也可組織成三級(jí)、四級(jí)頁表，但性能的影響是不可忽視的。(若頁表全部放在主存，則要取一個(gè)數(shù)據(jù)(一條指令)至少要訪問二次主存，第一次是訪問頁表，確定所取數(shù)據(jù)(或指令)的物理地址，第二次是根據(jù)該地址取數(shù)(或指令)將作業(yè)中最常用的頁

26、塊號(hào)置入高速緩存，提高查表速度(在地址變換機(jī)構(gòu)中加入一個(gè)高速、不容易的聯(lián)想存儲(chǔ)器)(c) 快表快表(聯(lián)想存貯器聯(lián)想存貯器)訪問主存訪頁表訪主存訪問主存訪頁表訪主存存放頁表部分內(nèi)容的快速存貯器稱為聯(lián)想存貯器，聯(lián)想存貯器中存放的部分頁表稱為“ 快表”。聯(lián)想存貯器一般由816個(gè)單元組成，它們用來存放正在運(yùn)行進(jìn)程的當(dāng)前最常用的頁號(hào)和相應(yīng)的塊號(hào)，并具有并行查尋能力。 查聯(lián)想表物理地址(訪問一次主存) 查頁表物理地址(訪問二次主存) 有效地址同時(shí)進(jìn)行這個(gè)聯(lián)想存貯器的查表速度可以做到比一般存儲(chǔ)器的速度快一個(gè)數(shù)量級(jí)。PBPB輸入輸出B WPW聯(lián)想表物理地址頁表起址PB頁表虛地址(分頁)B例：設(shè)訪問主存時(shí)間為2

27、00ns,訪問聯(lián)想存貯器為40ns，命中率為90，則平均存取時(shí)間為多少？查頁表兩次訪存：平均為200200400ns查塊表(200+40)90(200+200)10256ns解：方法方法1：方法方法2：(3) 請(qǐng)求分頁式存儲(chǔ)管理請(qǐng)求分頁式存儲(chǔ)管理(a) 目標(biāo)：實(shí)現(xiàn)小內(nèi)存大作業(yè)目標(biāo)：實(shí)現(xiàn)小內(nèi)存大作業(yè)(b) 實(shí)現(xiàn)方法：作業(yè)運(yùn)行時(shí)，只將當(dāng)前的一部分裝實(shí)現(xiàn)方法：作業(yè)運(yùn)行時(shí)，只將當(dāng)前的一部分裝入內(nèi)存其余的放在輔存，一旦發(fā)現(xiàn)訪問的頁不入內(nèi)存其余的放在輔存，一旦發(fā)現(xiàn)訪問的頁不在主存中，則發(fā)出缺頁中斷，由在主存中，則發(fā)出缺頁中斷，由o.s將其從輔存將其從輔存調(diào)入主存，如果內(nèi)存無空塊，則選擇一個(gè)頁淘調(diào)入主存，如

28、果內(nèi)存無空塊，則選擇一個(gè)頁淘汰。汰。怎樣發(fā)現(xiàn)頁不在內(nèi)存？擴(kuò)充表(以前頁表結(jié)構(gòu)只包含頁號(hào)和塊號(hào)兩個(gè)信息，這是進(jìn)行地址變換機(jī)構(gòu)所必須的，為了判斷頁面在不在主存，可在原頁表上擴(kuò)充，增加兩個(gè)數(shù)據(jù)項(xiàng)、中斷位I，輔存的位置)。第一個(gè)問題：第一個(gè)問題：頁號(hào)塊號(hào)中斷位輔存1. 不在內(nèi)存0. 在內(nèi)存當(dāng)進(jìn)程運(yùn)行時(shí)，在內(nèi)存中至少有一塊為該進(jìn)程所對(duì)應(yīng)的程序所占用，并正在執(zhí)行此塊內(nèi)的一條指令。若這條指令不涉及訪內(nèi)地址則罷，如果涉及訪內(nèi)地址，則由分頁機(jī)構(gòu)得到頁號(hào)，并以該頁號(hào)為索引查頁表PT，這時(shí)將有兩種可能性：發(fā)生缺頁中斷請(qǐng)求調(diào)入此頁，當(dāng)缺頁中斷發(fā)生時(shí)，用戶程序被中斷，控制轉(zhuǎn)到os的調(diào)頁程序，由調(diào)頁程序把所需的頁面從磁盤

29、調(diào)入內(nèi)存的某塊中，并把頁表中該頁面登記項(xiàng)中的中斷位I由1改為0，填入實(shí)際塊號(hào)，隨后繼續(xù)執(zhí)行被中斷的程序，這一頁面是根據(jù)請(qǐng)求而裝入的，因而稱為請(qǐng)求分頁存貯管理。 此頁對(duì)應(yīng)頁表中的中斷位為0，表示此頁已調(diào)入主存，可查得塊號(hào)B，形成BW的物理地址，從而指令得以執(zhí)行，繼而執(zhí)行下條指令； 當(dāng)中斷位為1，表示此頁不在主存，而是在磁盤上(輔存地址指示)指令執(zhí)行和缺頁中斷處理指令執(zhí)行和缺頁中斷處理啟動(dòng)要處理的指令該頁在主存給出虛地址形成頁號(hào)有空閑塊從外存讀入需要的頁調(diào)整存貯分塊表和頁表重新啟動(dòng)被中斷的指令準(zhǔn)備執(zhí)行下條指令執(zhí)行完該指令選一頁淘汰調(diào)整存貯分塊表和頁表要重新寫入該頁寫入外存YYYNN硬件軟件N缺頁中

30、斷如何處理缺頁一缺頁中斷管理？ 發(fā)現(xiàn)中斷、調(diào)入所缺頁第二個(gè)問題：第二個(gè)問題：如果內(nèi)存不足，選一頁淘汰，選擇哪一頁呢？引用位是來指示某頁最近被訪問過沒有？修改位是來指示某頁的數(shù)據(jù)修改過沒有？“ 0”表示沒有訪問過“ 1”表示已被訪問過引用位修改位0修改位 寫回輔存1未修改過 不必寫回輔存輔存地址引用位中斷位改變位主存塊號(hào)頁號(hào)頁表表目為(c) 置換算法置換算法 確定淘汰哪一頁的策略確定淘汰哪一頁的策略系統(tǒng)抖動(dòng) 內(nèi)外存交換頻繁使效率下降(導(dǎo)致系統(tǒng)效率急劇下降的主、輔存之間的頻繁轉(zhuǎn)換現(xiàn)象)駐留集 駐留在內(nèi)存中頁面的集合。成功失敗失敗成功的訪問次數(shù)不成功的訪問次數(shù)缺頁中斷率FSF)()(i) 最佳置換算

31、法：(OPT)“ 淘汰在將來再不被訪問(以后不再要的)，或者在最遠(yuǎn)的將來才被訪問的頁”然而這樣的算法是無法實(shí)現(xiàn)的，因?yàn)樵诔绦蜻\(yùn)行中無法對(duì)后面要使用的頁面作精確的判斷，不過可作為衡量各種具體算法的標(biāo)準(zhǔn)。(ii) 先進(jìn)先出算法(FIFO)例：設(shè)頁面請(qǐng)求次序7.0.1.2.0.3.0.4.2.3.0.3.2.1.2.存貯塊為3時(shí)(駐留集為3)3012302302304230423042301230120127017012707 0 1 2 0 3 0 4 2 3 0 3 2 1 2+ + + + + + + + + + + +頁面跡蹤圖缺頁率為801001512駐留集越大，缺頁中斷率越小嗎？(不一定

32、)。一般來說，對(duì)于任何一個(gè)頁的訪問順序(或序列)和任何一種換頁算法，如果分給的頁架數(shù)增加，則缺頁(所訪問頁不在主存)的頻率應(yīng)該減少。但這個(gè)結(jié)論并不普遍成立，對(duì)于某些頁面訪問序列，F(xiàn)IFO有隨著分給的頁架數(shù)增加，缺頁頻率也增加的異?，F(xiàn)象。頁 面 訪問 序 列九 次缺 頁三塊頁架A BC D A BEABC DEA BCDABEEEC D DAB C DA B B BEC CA BCDA AA BEE+頁 面 訪問 序 列十 次缺 頁四塊頁架ABCDABEABC D EABCDDDEAACD EABCCCDEEBCDABBBCDDA BC+ +AAABCCEAB+(iii) 最近最久未用頁面算法(

33、最近最少使用)LRU其思想：“ 若發(fā)生缺頁中斷，則選擇最近一段時(shí)間內(nèi)最長(zhǎng)時(shí)間沒有被訪問的頁淘汰掉，將要使用的頁調(diào)入主存”。基本理由是認(rèn)為過去一段時(shí)間里不曾被訪問過的頁，在最近的將來也可能不再會(huì)被訪問。1232303020323242404 0303230202121010772130770 1 2 0 3 0423 0 3 2 1 2+ + + + + + + + 缺頁率7 .661001510缺頁次數(shù)：10該算法實(shí)現(xiàn)起來比較困難，因?yàn)橐獮槊恳豁撛O(shè)置一特定單元來記錄自上次訪問后到現(xiàn)在的時(shí)間量 t，并選擇 t值最大的頁淘汰。得到廣泛使用的是最近最久未使用算法的近似方法 最近未使用更換算法(NUR

34、)，它比較易于實(shí)現(xiàn)，開銷也比較少，此更換算法，不但希望淘汰的頁是最近未使用的頁，而且還希望被挑選的頁在主存駐留期間，其頁面內(nèi)的數(shù)據(jù)未被修改過。為此，要為每頁增設(shè)兩個(gè)硬件位、訪問位和修改位。(iv) 最近未用更換算法 (NUR)訪問位0；該頁尚未被訪問過。1；該頁已經(jīng)被訪問過。修改位0；該頁尚未被修改過。1；該頁已經(jīng)被修改過。其具體工作過程如下：開始時(shí)，所有頁的訪問位、修改位置為“0”。當(dāng)訪問某頁時(shí)，將該頁訪問位置“1”。當(dāng)某頁的數(shù)據(jù)被修改，則該頁的修改位置“1”。當(dāng)要選一頁淘汰時(shí)，挑選下面序列中屬于低序號(hào)情況的頁進(jìn)行淘汰。序號(hào)：1234訪問位： 0011修改位： 0101在多道程序系統(tǒng)中，主存

35、中所有頁架的訪問位或修改位可能都會(huì)被置成了“1”，這時(shí)就難以決定淘汰哪一頁。當(dāng)前大多數(shù)系統(tǒng)的解決辦法是避免出現(xiàn)這種情況，為此，周期性地(經(jīng)一定時(shí)間間隔)把所有訪問位重新清成“0”。當(dāng)以后再訪問頁面時(shí)重新置“1”，這里一個(gè)主要問題是選擇適當(dāng)?shù)那辶銜r(shí)間間隔，如果間隔太大，可能所有頁架的訪問位均成為“1”。如果間隔太小，則訪問位為“0”的頁架又可能過多。LRU和NUR算法沒有異?，F(xiàn)象，即駐留集越大，缺頁中斷率越小。(d) 注意：注意：(i) 虛存：頁面并未全部放入內(nèi)存，使用戶感到“ 內(nèi)存”很大用戶不用考慮覆蓋系統(tǒng)“ 擴(kuò)充內(nèi)存”用戶編程在虛空間，運(yùn)行在物理空間缺頁中斷處理屬于中級(jí)調(diào)度外存、內(nèi)存、高速緩

36、沖，三級(jí)存貯變?yōu)橐患?jí)。(e) 評(píng)價(jià)：評(píng)價(jià)：虛存大，有效地利用了主存，適合多道程序，方便用戶編程。處理頁面調(diào)度的開銷，防止抖動(dòng)開銷較大。(4) 分段存貯管理分段存貯管理(segrmanent)(a) 段地址空間：作業(yè)由若干個(gè)邏輯分段組成，段地址空間：作業(yè)由若干個(gè)邏輯分段組成，如由代碼分段如由代碼分段(cs)數(shù)據(jù)分段數(shù)據(jù)分段(ds),棧段棧段(ss)附加段附加段(Es)組成組成一個(gè)段可定義為一組邏輯信息，如子程序，數(shù)組或工作區(qū)，(分段是程序中自然劃分的一組邏輯意義完整的信息集合，它是用戶在編程時(shí)決定的)。因此，每個(gè)作業(yè)的地址空間是由一些分段構(gòu)成的，每段都有自己的名字，且都是一段連續(xù)的地址空間。如下圖，可見整個(gè)作業(yè)的地址空間是二維的Y:0500C:0200D:0300CallLoadstore01kMain(主程序)分段X(子程序)分段A(數(shù)據(jù))分段B(工作區(qū))分段地址系統(tǒng)中的地址結(jié)構(gòu)有如下形式：(24位)段號(hào)S位移量W0723loadY D 12345C 段號(hào) 段長(zhǎng) 主存始址01k6k15004k23008k32009200SB段表LOAD 1, 11001234501k050003000200100