計(jì)算機(jī) 存儲(chǔ)管理

1、第5章 存儲(chǔ)管理本章要點(diǎn)連續(xù)分配存儲(chǔ)管理方式 段式存儲(chǔ)管理 頁式存儲(chǔ)管理 虛擬存儲(chǔ)管理 1 存儲(chǔ)器管理 1 存儲(chǔ)器管理的主要功能存儲(chǔ)分配的方法為多道程序分配大小相同的存儲(chǔ)區(qū)還是大小不同的存儲(chǔ)區(qū)； 內(nèi)存的分配在程序執(zhí)行前分配還是在執(zhí)行過程中動(dòng)態(tài)分配。地址變換程序執(zhí)行的內(nèi)存區(qū)域是連續(xù)的還是分散的。 地址保護(hù)如何保證程序之間既不沖突又可共享資源。內(nèi)存擴(kuò)充如何將內(nèi)存和外存結(jié)合起來，為用戶提供更大的存儲(chǔ)空間。25 存儲(chǔ)器管理 2 邏輯地址和物理地址邏輯地址(相對(duì)地址)用戶程序經(jīng)編譯后生成的目標(biāo)模塊是以0為開始地址順序編址。 目標(biāo)模塊中的地址稱為相對(duì)地址或邏輯地址。物理地址(絕對(duì)地址)內(nèi)存的地址以字節(jié)為單

2、位，每個(gè)存儲(chǔ)單元都有唯一的地址。33 程序的鏈接和裝入 一個(gè)源程序要變?yōu)榭梢栽趦?nèi)存中運(yùn)行的程序，通常要經(jīng)過編譯、鏈接和裝入三個(gè)步驟： 1）編譯：用戶程序經(jīng)編譯后生成的目標(biāo)模塊是以0為開始地址順序編址。 目標(biāo)模塊中的地址稱為相對(duì)地址或邏輯地址。 2）鏈接：將編譯后形成的多個(gè)目標(biāo)模塊以及它們運(yùn)行所需要的庫函數(shù)，鏈接在一起形成裝入模塊。裝入模塊仍以0作為起始地址。 3）裝入：將裝入模塊裝入內(nèi)存實(shí)際物理地址空間。5 存儲(chǔ)器管理4（1）鏈接靜態(tài)鏈接：程序裝入內(nèi)存之前將整個(gè)目標(biāo)模塊鏈接，形成可執(zhí)行文件。裝入時(shí)動(dòng)態(tài)鏈接：在各目標(biāo)模塊裝入內(nèi)存時(shí)鏈接，邊裝入邊鏈接。運(yùn)行時(shí)動(dòng)態(tài)鏈接：在執(zhí)行過程中將需要的模塊調(diào)入內(nèi)

3、存，并鏈接到調(diào)用模塊上。動(dòng)態(tài)鏈接有利于實(shí)現(xiàn)目標(biāo)模塊的共享。通常被鏈接的共享代碼稱為動(dòng)態(tài)鏈接庫(DLL)或共享庫(shared library)。5（2）程序裝入程序的邏輯地址與分配的內(nèi)存絕對(duì)地址不一致。每個(gè)邏輯地址也沒有一個(gè)固定的絕對(duì)地址與其對(duì)應(yīng)。例如： 程序被裝入到內(nèi)存A單元開始的內(nèi)存區(qū)域，則該程序訪問邏輯地址的K單元的數(shù)據(jù)時(shí)，實(shí)際應(yīng)訪問A+K單元。 為保證程序?qū)?shù)據(jù)的正確訪問，必須把邏輯地址轉(zhuǎn)換為絕對(duì)地址，把這個(gè)地址轉(zhuǎn)換過程稱為重定位。5 存儲(chǔ)器管理6程序的裝入方式重定位（地址映射） 把用戶程序中的相對(duì)地址（邏輯地址）轉(zhuǎn)換為主存中的絕對(duì)地址（物理地址）過程。靜態(tài)重定位 在程序裝入內(nèi)存時(shí)，裝

4、入程序把程序的邏輯地 址改成物理地址。物理地址固定，且必須連續(xù)。動(dòng)態(tài)重定位 在程序執(zhí)行期間，通過重定位寄存器把程序的 邏輯地址改成物理地址。指令執(zhí)行之前無須修改地址，因此運(yùn)行之前可以變換存儲(chǔ)位置，且各目標(biāo)模塊不需要連續(xù)存放。7靜態(tài)重定位示意圖 8動(dòng)態(tài)重定位示意圖 9動(dòng)態(tài)重定位示意圖10連續(xù)分配指為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間。單一連續(xù)分配固定分區(qū)分配可變分區(qū)分配5.3連續(xù)分配存儲(chǔ)管理方式（P113）11單一連續(xù)分配基本思想是將系統(tǒng)程序和用戶程序分開。單用戶單任務(wù)操作系統(tǒng)示意圖12固定分區(qū)方法分區(qū)在系統(tǒng)啟動(dòng)后劃分好，以后不能改變。劃分分區(qū)方法分區(qū)大小相等分區(qū)大小不等缺點(diǎn)內(nèi)存利用率低13分區(qū)

5、可變方法分區(qū)的大小和個(gè)數(shù)隨系統(tǒng)的運(yùn)行而不斷改變14動(dòng)態(tài)分區(qū)分配數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表（P116）空閑分區(qū)鏈（P117）動(dòng)態(tài)分區(qū)分配算法首次適應(yīng)法下次適應(yīng)法最佳適應(yīng)法最壞適應(yīng)法動(dòng)態(tài)分區(qū)的分配和回收操作可變分區(qū)15可變分區(qū)內(nèi)存的回收回收分區(qū)與前面一個(gè)（低地址）空閑分區(qū)F1相鄰接，圖（a）回收分區(qū)與后面一個(gè)（高地址）空閑分區(qū)F2相鄰接，圖（b） 回收分區(qū)與前、后兩個(gè)空閑分區(qū)F1和F2均相鄰，圖（c）回收分區(qū)不與其它空閑分區(qū)相鄰接 16條件空閑分區(qū)鏈以存儲(chǔ)空間地址遞增的次序鏈接。優(yōu)點(diǎn)釋放時(shí)，因不改變?cè)搮^(qū)在隊(duì)列中的位置，因此速度快。保證高地址有空閑空間，可留給大作業(yè)。缺點(diǎn)常用大空閑區(qū)適應(yīng)小作業(yè)，從而留下小空

6、閑區(qū)，且這些小空閑區(qū)在鏈表的前面，影響分配速度?？勺兎謪^(qū)分配算法最佳適應(yīng)法首次適應(yīng)法下次適應(yīng)法最壞適應(yīng)法條件空閑分區(qū)鏈以存儲(chǔ)空間地址遞增的次序連接成循環(huán)鏈，為進(jìn)程分配存儲(chǔ)空間時(shí)，不是從隊(duì)首開始找，而是從上次找到的空閑空間的下一個(gè)空閑分區(qū)開始找。優(yōu)點(diǎn)存儲(chǔ)空間利用均衡。缺點(diǎn)沒有了較大空閑空間，使大作業(yè)無法運(yùn)行。條件空閑分區(qū)鏈以存儲(chǔ)空間大小遞增的次序拉鏈。優(yōu)點(diǎn)若存儲(chǔ)空間中存在與申請(qǐng)大小相等的空閑區(qū)，則必然被選中，否則選一個(gè)稍大的空閑區(qū)，而避免毀掉更大的空閑區(qū)。缺點(diǎn)小碎片增加碎片問題嚴(yán)重。回收時(shí)，將空閑區(qū)插入適當(dāng)?shù)奈恢觅M(fèi)時(shí)。條件空閑分區(qū)鏈以存儲(chǔ)空間大小遞減的次序拉鏈。優(yōu)點(diǎn)分配后，剩下的空閑區(qū)還好用。申

7、請(qǐng)時(shí)，查找容易，因此速度快。缺點(diǎn)當(dāng)有大作業(yè)時(shí)，可能就沒有空間可用了。17練習(xí)1.在可變分區(qū)分配方案中，最佳適應(yīng)法是將空閑塊按_ _次序排序.A.地址遞增 B.地址遞減 C.大小遞增 D.大小遞減2.在分區(qū)存儲(chǔ)管理方式中，如果在按地址升序排列的未分配分區(qū)表中順序登記了下列未分配分區(qū)：1-起始地址17K，分區(qū)長(zhǎng)度為9KB；2-起始地址54KB,分區(qū)長(zhǎng)度13KB,現(xiàn)有一個(gè)分區(qū)被釋放，其起始地址為39KB，分區(qū)長(zhǎng)度為15KB，則系統(tǒng)要_。A.合并第一個(gè)未分配分區(qū) B.合并第一個(gè)及第二個(gè)未分配分區(qū)C.合并第二個(gè)為分配分區(qū) D.不合并任何分區(qū)1.C2.C18練習(xí)3.在固定分區(qū)存儲(chǔ)管理中，每個(gè)分區(qū)的大小是_

8、。A.相同 B.隨進(jìn)程的大小變化C.可以不同，需預(yù)先設(shè)定 D.可以不同，根據(jù)進(jìn)程的大小設(shè)定4.在可變分區(qū)存儲(chǔ)管理中，合并分區(qū)的目的是_。A.合并空閑區(qū) B.合并分區(qū) C.增加內(nèi)存容量 D.便于地址交換3. C4. A19練習(xí)5.把程序地址空間中的邏輯地址轉(zhuǎn)換為內(nèi)存的物理地址稱_。A.加載 B.重定位 C.物理化 D.鏈接6.在以下存儲(chǔ)管理方案中，不適用于多道程序設(shè)計(jì)系統(tǒng)的是_。A.單一連續(xù)分區(qū) B.固定分區(qū)C.可變分區(qū) D.頁式存儲(chǔ)管理5. B6. A20練習(xí)7.在可變分區(qū)系統(tǒng)中，當(dāng)一個(gè)進(jìn)程撤銷后，系統(tǒng)回收其占用的內(nèi)存空間，回收后造成空閑分區(qū)的個(gè)數(shù)減1的情況是_。A.回收區(qū)與空閑區(qū)無鄰接 B.

9、回收區(qū)與上面的空閑區(qū)鄰接C.回收區(qū)與下面的空閑區(qū)鄰接 D.回收區(qū)與上下兩個(gè)空閑區(qū)鄰接8.在可變分區(qū)分配方案中，首次適應(yīng)法是將空閑塊按_次序排序.A.地址遞增 B.地址遞減 C.大小遞增 D.大小遞減7 . D8 . A21練習(xí)9.在可變分區(qū)的分配算法中，傾向于優(yōu)先使用低地址部分空閑區(qū)的是_，能使內(nèi)存空間的空閑區(qū)分布得較均勻的是_,每次分配時(shí)，若內(nèi)存中有和進(jìn)程需要的分區(qū)的大小相等的空閑區(qū)，一定能分配給進(jìn)程的是_。首次適應(yīng)算法下次適應(yīng)算法最佳適應(yīng)算法22練習(xí)10. 在系統(tǒng)中采用可變分區(qū)存儲(chǔ)管理，操作系統(tǒng)占用低地址部分的126KB，用戶區(qū)的大小是386KB，若采用空閑分區(qū)表管理空閑分區(qū)。若分配時(shí)均從

10、高地址開始，對(duì)于下述的作業(yè)申請(qǐng)序列：作業(yè)1申請(qǐng)80KB；作業(yè)2申請(qǐng)56KB；作業(yè)3申請(qǐng)120KB；作業(yè)1完成；作業(yè)3完成；作業(yè)4申請(qǐng)156KB；作業(yè)5申請(qǐng)80KB。（1）畫出作業(yè)1、2、3進(jìn)入內(nèi)存后。內(nèi)存分布情況。（2）畫出作業(yè)1、3完成后。內(nèi)存的分布情況。（3）畫出作業(yè)4、5進(jìn)入內(nèi)存后。內(nèi)存分布的情況。23練習(xí)（1）作業(yè)1、2、3進(jìn)入內(nèi)存后，內(nèi)存分布如下圖0KB126KB256KB376KB432KB操作系統(tǒng)126KB作業(yè)3:120KB作業(yè)2:56KB作業(yè)1:80KB24練習(xí)（2）作業(yè)1、3完成后，內(nèi)存的分布情況如下圖0KB126KB256KB376KB432KB操作系統(tǒng)126KB作業(yè)2:5

11、6KB512-1KB25練習(xí)（3）作業(yè)4、5進(jìn)入內(nèi)存后，內(nèi)存的分布情況如下圖0KB126KB256KB376KB432KB操作系統(tǒng)126KB作業(yè)4:156KB作業(yè)2:56KB作業(yè)5:80KB512-1KB26離散分配方式的引入連續(xù)分配方式帶來的問題是會(huì)在存儲(chǔ)空間中產(chǎn)生許多“碎片”。能否將進(jìn)程分配到許多不相鄰的分區(qū)中呢？由此產(chǎn)生離散分配方式。分頁存儲(chǔ)管理方式存儲(chǔ)管理的需要分段存儲(chǔ)管理方式用戶編程的需要27基本原理 內(nèi)存空間分成大小相等的若干個(gè)存儲(chǔ)塊，稱為物理塊或頁框。 將進(jìn)程的邏輯地址空間分成與塊大小相等的若干頁，稱為頁面或頁； 在為進(jìn)程分配內(nèi)存時(shí)，以塊為單位，將進(jìn)程中的若干頁分別裝入多個(gè)可以不

12、相鄰的塊中。5.3頁式存儲(chǔ)管理28頁面的大小由機(jī)器的地址結(jié)構(gòu)決定的。頁面的大小的權(quán)衡 頁面較小-內(nèi)存碎片?。豁摫磉^長(zhǎng)，占用較大內(nèi)存空間。 頁面較大-頁表短，占用較少內(nèi)存；內(nèi)存碎片大。 通常頁面的大小要適中，在512B4MB之間。頁面大小的選擇29地址轉(zhuǎn)換方法 CPU生成的邏輯地址分成以下兩部分:頁號(hào)(p)：頁號(hào)作為頁表中的索引。頁表中包含每頁所在物理內(nèi)存的基地址。頁偏移(d)：與頁的物理基地址組合就形成了物理地址。30地址轉(zhuǎn)換示意圖31邏輯地址被分為兩部分： 頁號(hào) 頁內(nèi)位移例如邏輯地址1500的二進(jìn)制形式為0000 0101 1101 1100如果頁的大小為1024B，故頁內(nèi)位移占10位，剩下

13、6位為頁號(hào)邏輯地址1500對(duì)應(yīng)的頁號(hào)為1（二進(jìn)制為0000 01） 頁內(nèi)位移為476（二進(jìn)制為01 1101 1100）頁式存儲(chǔ)管理邏輯地址結(jié)構(gòu)32頁式存儲(chǔ)管理地址變換機(jī)構(gòu)LOAD 1,150012345050015003000進(jìn)程邏輯地址空間LOAD 1,15002 70 41 6頁號(hào) 塊號(hào)頁表000001 0111011100邏輯地址1500000110 0111011100物理地址662066201K2K3K4K5K6K7K8K內(nèi)存物理地址空間33頁表的組織現(xiàn)代的計(jì)算機(jī)系統(tǒng)都支持大的邏輯地址空間，當(dāng)?shù)刂房臻g較大（32位或64位）如32位時(shí)，若頁面大小為4KB=212B，有頁表項(xiàng)目220=

14、1M，若每個(gè)頁表項(xiàng)占4B，故每張頁表要占用4MB內(nèi)存。對(duì)頁表所需地址空間采用離散分配方式來解決將當(dāng)前需要的部分頁表項(xiàng)調(diào)入內(nèi)存，其余的頁表項(xiàng)仍駐留在磁盤上，需要時(shí)再調(diào)入內(nèi)存。34習(xí)題1. 某系統(tǒng)采用頁式存儲(chǔ)管理方法，主存儲(chǔ)器容量為256MB，分成64K個(gè)塊。某用戶作業(yè)有4頁，其頁號(hào)依次為0，1，2，3被分別放在主存塊號(hào)為2，4，l，6的塊中。要求：(1)寫出該作業(yè)的頁表；(2)指出該作業(yè)總長(zhǎng)度的字節(jié)(Byte)數(shù)；(3)分別計(jì)算相對(duì)地址0，100和2，0對(duì)應(yīng)的絕對(duì)地址(方括號(hào)內(nèi)的第一元素為頁號(hào)，第二元素為頁內(nèi)地址)。35習(xí)題36習(xí)題2. 某頁式存儲(chǔ)管理系統(tǒng)，內(nèi)存的大小為64KB，被分成16塊，塊

15、號(hào)為0、1、2、15。設(shè)某進(jìn)程有4頁，其頁號(hào)為0、1、2、3，被分別裝入內(nèi)存的2、4、7、5塊，問：（1）該進(jìn)程的大小是多少字節(jié)？（2）寫出該進(jìn)程每一頁在內(nèi)存的起始地址。（3）邏輯地址4146對(duì)應(yīng)的物理地址是多少？37例題（1）內(nèi)存的大小為64KB，被分成16塊，所以塊的大小是64KB/16=4KB。因?yàn)閴K的大小與頁面的大小相等，所以頁的大小是4KB。該進(jìn)程的大小是4*4=16KB。（2）因?yàn)檫M(jìn)程頁號(hào)為0、1、2、3，被分別裝入內(nèi)存的2、4、7、5。第0頁在內(nèi)存的起始地址是：2*4KB=8KB；第1頁在內(nèi)存的起始地址是：4*4KB=16KB；第2頁在內(nèi)存的起始地址是：7*4KB=28KB；第3

16、頁在內(nèi)存的起始地址是：5*4KB=20KB。38例題（3）邏輯地址4146對(duì)應(yīng)的物理地址：4146/4096=1，50。邏輯地址4146對(duì)應(yīng)的頁號(hào)為1，頁內(nèi)位移為50。查找頁表，得知頁號(hào)為1的存儲(chǔ)塊號(hào)為4，所以邏輯地址4146對(duì)應(yīng)的物理地址是：4*4096+50=16434。39習(xí)題3. 某系統(tǒng)采用頁式存儲(chǔ)管理策略，某進(jìn)程的邏輯地址空間為32頁，頁的大小為2KB，物理地址空間的大小是4MB。（1）寫出邏輯地址的格式。（2）該進(jìn)程的頁表有多少項(xiàng)？每項(xiàng)至少占多少位？（3）如果物理地址空間減少一半，頁表的結(jié)構(gòu)有何變化？40習(xí)題（1）進(jìn)程的邏輯地址空間為32頁，故邏輯地址中的頁號(hào)需要5位（二進(jìn)制），由

17、于每頁的大小為2KB，因此頁內(nèi)位移須用11位（二進(jìn)制）表示，這樣邏輯地址格式如下圖。頁號(hào) 頁內(nèi)位移1511 10041習(xí)題（2）因?yàn)檫M(jìn)程的邏輯地址空間為32頁，因此該進(jìn)程的頁表項(xiàng)有32項(xiàng)。頁表中應(yīng)存儲(chǔ)每頁的塊號(hào)。因?yàn)槲锢淼刂房臻g的大小是4MB，4MB的物理地址空間內(nèi)分成4MB/2KB=2K個(gè)塊，因此塊號(hào)部分需要11位（二進(jìn)制），所以頁表中每項(xiàng)占16位。（3）如果物理地址空間減少一半，頁表的頁表項(xiàng)數(shù)不變，但每一項(xiàng)的長(zhǎng)度從16位（二進(jìn)制）減少到15位（二進(jìn)制）。42方便編程分段共享分段保護(hù)動(dòng)態(tài)鏈接動(dòng)態(tài)增長(zhǎng)引入原因5.4 段式存儲(chǔ)管理43段式存儲(chǔ)管理的基本原理整個(gè)作業(yè)的地址空間被分成若干個(gè)段，每個(gè)段

18、采用一段連續(xù)的地址空間，段的長(zhǎng)度由相應(yīng)的邏輯信息的長(zhǎng)度決定。44段式存儲(chǔ)管理地址變換機(jī)構(gòu)45例題（P127）段號(hào)內(nèi)存起始地址段長(zhǎng)02105001235020210090在一個(gè)分段式存儲(chǔ)管理系統(tǒng)中，其段表如表5.2所示。求表5.3中邏輯地址對(duì)應(yīng)的物理地址。 表5.2 段表 表5.3 邏輯地址段號(hào)段內(nèi)位移0430110250046分頁和分段的區(qū)別分頁和分段的目的頁是信息的物理單位，分頁是系統(tǒng)管理的需要，而不是用戶的需要。段是信息的邏輯單位，它含一組意義完整的信息。分段是為了更好地滿足用戶的要求。頁和段長(zhǎng)度頁的大小固定，由系統(tǒng)確定。段的長(zhǎng)度不固定，決定于用戶所編寫的程序。地址空間分頁的作業(yè)地址空間是

19、一維的，即單一的線性地址空間。分段的作業(yè)地址空間是二維的，程序員在標(biāo)識(shí)一個(gè)地址時(shí)，需給出段名和段內(nèi)地址。47段的共享與保護(hù) 頁共享與段共享的比較 由于段是信息的邏輯單位，用戶易于實(shí)現(xiàn)對(duì)段的共享，也容易對(duì)段進(jìn)行保護(hù)。而頁雖也可共享，但不方便。舉例例如有一個(gè)多用戶系統(tǒng)，可同時(shí)容納40個(gè)用戶，它們都執(zhí)行一個(gè)文本編輯程序，該文本編輯程序含有160KB的代碼和40KB的數(shù)據(jù)，如不共享，共需160*40+40*40=8MB的內(nèi)存空間來支持40個(gè)用戶。若代碼是可重入的，則無論是分頁系統(tǒng)還是分段系統(tǒng)都可以共享該代碼段，因此內(nèi)存只需留一個(gè)文本編輯程序，所需空間為160+40*40=1760KB。48頁的共享注意：頁的共享要求作業(yè)地址空間的共享頁必須具有相同的頁號(hào)。使用分頁系統(tǒng)，每個(gè)頁面