第43基本頁式存儲管理

1、 存儲管理存儲管理分區(qū)分區(qū)4分區(qū)分區(qū)3分區(qū)分區(qū)2分區(qū)分區(qū)1連續(xù)分配方式連續(xù)分配方式 （）回顧：回顧：1.分區(qū)分區(qū)2.分區(qū)分區(qū)進(jìn)程進(jìn)程1進(jìn)程進(jìn)程2進(jìn)程進(jìn)程4進(jìn)程進(jìn)程3進(jìn)程進(jìn)程1進(jìn)程進(jìn)程2進(jìn)程進(jìn)程3進(jìn)程進(jìn)程4內(nèi)存的用戶可用空間內(nèi)存的用戶可用空間導(dǎo)入：導(dǎo)入： 經(jīng)過一段時(shí)間的分配回收后，內(nèi)存中存在很多很經(jīng)過一段時(shí)間的分配回收后，內(nèi)存中存在很多很小的不可利用的空閑空間小的不可利用的空閑空間-碎片碎片（零頭零頭）。）。用戶程序用戶程序1用戶程序用戶程序6用戶程序用戶程序310KB30KB14KB用戶程序用戶程序926KBa)緊湊前緊湊前用戶程序用戶程序1用戶程序用戶程序6用戶程序用戶程序3用戶程序用戶程序

2、980KBb)緊湊后緊湊后導(dǎo)入：導(dǎo)入：固定分區(qū)固定分區(qū)離散存儲離散存儲+基本分頁存儲管理基本分頁存儲管理實(shí)分頁實(shí)分頁 新授：新授：中國好聲音中國好聲音-香港行香港行這么多人，住這么多人，住在哪里好呢？在哪里好呢？前提：前提： 1.酒店的全部客房都是標(biāo)準(zhǔn)的酒店的全部客房都是標(biāo)準(zhǔn)的雙人雙人間。間。2.我們團(tuán)隊(duì)的我們團(tuán)隊(duì)的性別比例很合適性別比例很合適的哦！的哦！(共82人人)您好！請問酒店現(xiàn)在有空您好！請問酒店現(xiàn)在有空房間嗎？我需要房間嗎？我需要41個(gè)標(biāo)準(zhǔn)個(gè)標(biāo)準(zhǔn)間，間，歡迎光臨，您需要的歡迎光臨，您需要的41個(gè)標(biāo)準(zhǔn)間我們可以提供個(gè)標(biāo)準(zhǔn)間我們可以提供.但是它們不在同一樓層，但是它們不在同一樓層，房間號

3、也不連續(xù)！房間號也不連續(xù)！1組組 1號號 曹麗雪曹麗雪205號房間號房間 2號號 郭穎郭穎2組組 3號號 曹偉磊曹偉磊206號房間號房間 4號號 何晶何晶3組組 5號號 黃雪萍黃雪萍211號房間號房間 6號號 賈倩賈倩 41組組 82號號 藺秀瑩藺秀瑩415號房間號房間基本分頁存儲管理基本分頁存儲管理實(shí)分頁實(shí)分頁 一、一、實(shí)現(xiàn)原理實(shí)現(xiàn)原理 將內(nèi)存空間等分成若干將內(nèi)存空間等分成若干frameframe、頁架、幀、頁架、幀），并），并按物按物理地址遞增理地址遞增的順序連續(xù)的順序連續(xù)編號編號為為0 0，1 1，22塊塊新授：新授： 內(nèi)存空間內(nèi)存空間0#1#3#2#4#5#低地址低地址高地址高地址基本

4、分頁存儲管理基本分頁存儲管理實(shí)分頁實(shí)分頁 進(jìn)程的虛擬空間劃分成一系列與進(jìn)程的虛擬空間劃分成一系列與物理塊物理塊的的（也稱為（也稱為，并按并按邏輯地址遞增邏輯地址遞增的順序連續(xù)的順序連續(xù)編編號號為為0 0，1 1，22頁頁新授：新授：進(jìn)程的虛擬空間進(jìn)程的虛擬空間0頁頁1頁頁2頁頁一、一、實(shí)現(xiàn)原理實(shí)現(xiàn)原理 基本分頁存儲管理基本分頁存儲管理實(shí)分頁實(shí)分頁 若進(jìn)程的若進(jìn)程的總頁數(shù)不大于內(nèi)存中的總頁數(shù)不大于內(nèi)存中的可用塊數(shù)可用塊數(shù)，系統(tǒng)就可以以，系統(tǒng)就可以以頁頁為單為單位位離散分配離散分配，并在內(nèi)存中為該進(jìn)，并在內(nèi)存中為該進(jìn)程建立一個(gè)能夠反映其程建立一個(gè)能夠反映其邏輯頁與邏輯頁與物理塊映射關(guān)系物理塊映射關(guān)

5、系的的“”。新授：新授：一、一、實(shí)現(xiàn)原理實(shí)現(xiàn)原理 進(jìn)程的頁表進(jìn)程的頁表頁號頁號塊號塊號存取控存取控制字段制字段基本分頁存儲管理原理圖示基本分頁存儲管理原理圖示Os區(qū)區(qū)進(jìn)程進(jìn)程B013245內(nèi)存空間內(nèi)存空間進(jìn)程進(jìn)程A的虛擬空間的虛擬空間0頁頁1頁頁2頁頁0頁頁1頁頁2頁頁進(jìn)程進(jìn)程A的頁表的頁表頁號頁號塊號塊號021325由由硬件決定硬件決定，頁面大小要頁面大小要適適中中，常為，常為2的的冪字節(jié)，一般冪字節(jié)，一般為為512B4KB。1.基本上解決了基本上解決了碎片碎片問題。問題。2.實(shí)現(xiàn)了由實(shí)現(xiàn)了由連續(xù)存儲到連續(xù)存儲到離散存儲離散存儲的的飛躍。飛躍?；痉猪摯鎯芾砘痉猪摯鎯芾硪黄饋矸治鲆黄饋?/p>

6、分析 ：為什么塊尺寸為什么塊尺寸太大太大或或太小太小都不好？都不好？基本分頁存儲管理基本分頁存儲管理一起來分析一起來分析 ：新授：新授：例如例如：對：對8B8B的進(jìn)程虛擬空間按頁大小為的進(jìn)程虛擬空間按頁大小為2B2B進(jìn)行分頁。進(jìn)行分頁。0頁頁1頁頁2頁頁3頁頁0B1B2B3B4B5B6B7B邏輯地址邏輯地址如何表示？如何表示？7 73 3 * * 2 2 + + 1 1邏輯頁號邏輯頁號頁內(nèi)偏移量頁內(nèi)偏移量頁大小頁大小二、二、地址轉(zhuǎn)換地址轉(zhuǎn)換 P = A / L 1.邏輯地址結(jié)構(gòu)：邏輯地址結(jié)構(gòu)：十進(jìn)制表示十進(jìn)制表示邏輯地址邏輯地址頁面大小頁面大小頁號頁號頁內(nèi)地址頁內(nèi)地址新授：新授： A = P

7、* L W W = A%L二、二、地址轉(zhuǎn)換地址轉(zhuǎn)換 頁號頁號 P頁內(nèi)地址頁內(nèi)地址 W0i i-1n1新授：新授：二進(jìn)制表示二進(jìn)制表示1.邏輯地址結(jié)構(gòu)：邏輯地址結(jié)構(gòu)：對于對于n n位的邏輯地址，設(shè)頁大小為位的邏輯地址，設(shè)頁大小為字節(jié)。字節(jié)。高高n ni i位位2.物理地址結(jié)構(gòu)：物理地址結(jié)構(gòu)：A 物理地址物理地址L 塊大小塊大小P 塊號塊號W塊內(nèi)地址塊內(nèi)地址新授：新授：類似于邏輯地址類似于邏輯地址 A = P * L W 查查頁表頁表二、二、地址轉(zhuǎn)換地址轉(zhuǎn)換 由由地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)實(shí)現(xiàn)實(shí)現(xiàn)3. 地址轉(zhuǎn)換過程：地址轉(zhuǎn)換過程：新授：新授：頁表頁表頁表寄存器頁表寄存器PTR (Page-Table

8、 Register)二、二、地址轉(zhuǎn)換地址轉(zhuǎn)換 頁表始址頁表始址頁表長度頁表長度頁表寄存器頁表寄存器PTRPTR+頁號頁號 P 頁內(nèi)地址頁內(nèi)地址 W邏輯地址邏輯地址A A0頁號頁號塊號塊號P頁表頁表越界中斷越界中斷新授：新授：NY塊號塊號 P 塊內(nèi)地址塊內(nèi)地址W物理地址物理地址AAP內(nèi)存內(nèi)存地址轉(zhuǎn)換過程圖地址轉(zhuǎn)換過程圖當(dāng)執(zhí)行一條指令需訪問內(nèi)存當(dāng)執(zhí)行一條指令需訪問內(nèi)存兩兩次次4. 具有具有的地址變換機(jī)構(gòu)的地址變換機(jī)構(gòu) 為提高效率，克服為提高效率，克服兩次訪存兩次訪存的弊端的弊端, ,在地址變換機(jī)構(gòu)中，增設(shè)一在地址變換機(jī)構(gòu)中，增設(shè)一個(gè)具有并行查找能力的個(gè)具有并行查找能力的高速緩沖寄存器高速緩沖寄存器

9、，又稱，又稱“聯(lián)想寄存器聯(lián)想寄存器” ” (Associative Memory)(Associative Memory)或或“快表快表”, ,用以存放當(dāng)前用以存放當(dāng)前被頻繁訪問的被頻繁訪問的頁面號和對應(yīng)的頁表項(xiàng)頁面號和對應(yīng)的頁表項(xiàng)。 快表一般只存放快表一般只存放16-51216-512表項(xiàng)，表滿時(shí)需進(jìn)行淘汰。由于程序表項(xiàng)，表滿時(shí)需進(jìn)行淘汰。由于程序和數(shù)據(jù)的訪問有局部性，所以快表和數(shù)據(jù)的訪問有局部性，所以快表“命中率命中率”可達(dá)可達(dá)90%90%以上以上。新授：新授：二、二、地址轉(zhuǎn)換地址轉(zhuǎn)換 具有塊表的地址變換機(jī)構(gòu)具有塊表的地址變換機(jī)構(gòu)新授：新授：頁表始址頁表始址頁表長度頁表長度頁表寄存器頁表寄

10、存器PTRPTR+頁號頁號 P 頁內(nèi)地址頁內(nèi)地址 W邏輯地址邏輯地址A A0頁號頁號塊號塊號P頁表頁表越界中斷NY塊號塊號 P 塊內(nèi)地址塊內(nèi)地址W物理地址物理地址AAP內(nèi)存內(nèi)存頁號 塊號P快快表表例：設(shè)訪問主存時(shí)間為例：設(shè)訪問主存時(shí)間為200ms,訪問聯(lián)想存貯器為訪問聯(lián)想存貯器為40ms，命，命中率為中率為90，則平均存取時(shí)間為多少？，則平均存取時(shí)間為多少？查頁表查頁表兩次訪存兩次訪存：平均為：平均為200200400ms查塊表查塊表、頁表、頁表 (200+40)90(200+200)10256ms解：解：方法方法1：只設(shè)頁表只設(shè)頁表方法方法2：增加快表增加快表小練習(xí)小練習(xí)1011107801

11、21742n第0頁頁表1460121023第1頁頁表114115011023外部頁表012345671141151468第n頁頁存空間1. 相關(guān)數(shù)據(jù)結(jié)構(gòu)相關(guān)數(shù)據(jù)結(jié)構(gòu) 1 1）：每個(gè)進(jìn)程一個(gè)頁表，存在于內(nèi)存的：每個(gè)進(jìn)程一個(gè)頁表，存在于內(nèi)存的OSOS空間，記錄各個(gè)空間，記錄各個(gè) 邏輯頁到物理塊之間的映射關(guān)系及頁內(nèi)存取控制權(quán)限等。邏輯頁到物理塊之間的映射關(guān)系及頁內(nèi)存取控制權(quán)限等。新授：新授：三、三、分配與回收分配與回收2 2）：整個(gè)系統(tǒng)一個(gè)表，存放每個(gè)進(jìn)程請求分配的頁面數(shù)：整個(gè)系統(tǒng)一個(gè)表，存放每個(gè)進(jìn)程請求分配的頁面數(shù) 及實(shí)際分配給它的內(nèi)存空間的頁表信息、請求是否及實(shí)際分配給

12、它的內(nèi)存空間的頁表信息、請求是否 得到滿足等。得到滿足等。進(jìn)程號進(jìn)程號請求塊數(shù)請求塊數(shù)頁表始址頁表始址 頁表長度頁表長度狀態(tài)狀態(tài)1. 相關(guān)數(shù)據(jù)結(jié)構(gòu)相關(guān)數(shù)據(jù)結(jié)構(gòu) 3 3）內(nèi)存分配表內(nèi)存分配表位示圖位示圖 整個(gè)系統(tǒng)一個(gè)表，存在于內(nèi)存的整個(gè)系統(tǒng)一個(gè)表，存在于內(nèi)存的OSOS空間，用比特位來記錄內(nèi)空間，用比特位來記錄內(nèi)存每一塊是否已分配的信息。（存每一塊是否已分配的信息。（如：如：1 1已分；已分；0 0未分未分）新授：新授：三、三、分配與回收分配與回收舉例舉例：已知某系統(tǒng)內(nèi)存的可分配區(qū)被分為：已知某系統(tǒng)內(nèi)存的可分配區(qū)被分為256256塊，則位示圖需占塊，則位示圖需占 用用256/8256/83232字

13、節(jié)字節(jié)的內(nèi)存空間。的內(nèi)存空間。0 1 0 0 1 1 1 01 0 0 1 0 1 0 0 0 0 0 1 1 0 0 101310174 4）空閑頁面鏈空閑頁面鏈：不占額外的內(nèi)存空間：不占額外的內(nèi)存空間 2. 分配分配 新授：新授：三、三、分配與回收分配與回收3. 回收：回收： 刪除頁表，并將歸還的塊對應(yīng)的位由刪除頁表，并將歸還的塊對應(yīng)的位由1 1置為置為0 01. 共享共享 若兩個(gè)進(jìn)程的某若兩個(gè)進(jìn)程的某2 2個(gè)邏輯頁號對應(yīng)的物理塊號相同，則可達(dá)到共個(gè)邏輯頁號對應(yīng)的物理塊號相同，則可達(dá)到共享該塊的目的。享該塊的目的。新授：新授：四、四、共享與保護(hù)共享與保護(hù)013245內(nèi)存內(nèi)存022513頁表

14、頁表10314頁表頁表22. 保護(hù)保護(hù) 1 1）越界檢查越界檢查2 2）存取控制檢查存取控制檢查： 在頁表中設(shè)置相應(yīng)的位在頁表中設(shè)置相應(yīng)的位可讀可讀、可寫可寫、可執(zhí)行可執(zhí)行新授：新授：四、四、共享與保護(hù)共享與保護(hù)答答：2）對邏輯地址（對邏輯地址（2500）D：Pint（25001K）2W25001K452 由已知，頁號由已知，頁號 P2 對應(yīng)的頁面號對應(yīng)的頁面號 P4， 邏輯（邏輯（2500）D對應(yīng)物理地址對應(yīng)物理地址P 1KW（4548）D 例例1：一個(gè)分頁式存儲管理系統(tǒng)中，用戶虛擬空間每頁：一個(gè)分頁式存儲管理系統(tǒng)中，用戶虛擬空間每頁1KB，假定，假定某時(shí)刻用戶的第某時(shí)刻用戶的第0，1，2，

15、3頁分別分配的物理塊號為頁分別分配的物理塊號為10，8，4，17，將邏輯地址（，將邏輯地址（2500）D轉(zhuǎn)換為物理地址。轉(zhuǎn)換為物理地址。練習(xí)：練習(xí)：例例2：設(shè)虛擬地址為：設(shè)虛擬地址為(7101)8 ,每一物理塊為每一物理塊為128字節(jié)字節(jié),請描述請描述如何進(jìn)行地址重定位如何進(jìn)行地址重定位?12827(7101)8 ( 111, 00 1, 000, 001)2 = ( 3 4 1 0 1 )8頁號為頁號為(34)8, 偏移量為偏移量為(101)8, 塊號塊號p由由頁表頁表指定，偏移量指定，偏移量w不變不變， 按按 A = p * L w 形成物理地址。形成物理地址。練習(xí)：練習(xí)：解惑解惑: :( 11 , 100 1, 000, 001)21：有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是：有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，頁，頁大小為大小為2KB，依次裝入內(nèi)存的第，依次裝入內(nèi)存的第7、9、10、5塊，試將塊，試將十進(jìn)十進(jìn)制邏輯制邏輯地址地址7145，3412轉(zhuǎn)換成轉(zhuǎn)換成對應(yīng)的物理對應(yīng)的物理地址。地址。（電子作業(yè)文檔詳見網(wǎng)絡(luò)平臺電子作業(yè)文檔詳見網(wǎng)絡(luò)平臺）作業(yè)：作業(yè)：基本分頁存儲管理基本分頁存儲管理實(shí)分頁實(shí)分頁 系統(tǒng)自動(dòng)將系統(tǒng)自動(dòng)將內(nèi)存分塊內(nèi)存分塊，將，將虛擬空間分頁虛擬空間分頁，頁、塊等大小，頁、塊等大小，且都從且都從0 0連續(xù)編號，在進(jìn)