第4章存儲器管理

課程主要內(nèi)容操作系統(tǒng)引論（1章）進程管理（2-3章）

進程控制、進程同步、進程通信、進程調(diào)度存儲管理（4章）存儲分配與回收地址變換內(nèi)存擴充存儲保護與共享設(shè)備管理（5章）文件管理（6章）OS中的存儲管理是指對內(nèi)存(并涉及外存)的管理，是OS的重要功能之一。第4章存儲器管理存儲器的層次結(jié)構(gòu)第4章存儲器管理任務(wù)為多道程序的運行提供良好的環(huán)境，提高存儲器的利用率并從邏輯上擴充存儲器。功能存儲分配與回收地址變換內(nèi)存擴充存儲保護與共享第4章存儲器管理程序的裝入和鏈接連續(xù)分配存儲管理基本分頁存儲管理基本分段存儲管理虛擬存儲器的基本概念請求分頁存儲管理頁面置換算法請求分段存儲管理補充：請求段頁式存儲管理4.1程序的鏈接和裝入從源程序到程序執(zhí)行編譯：由編譯程序?qū)⒂脩粼闯绦蚓幾g成若干個目標模塊。如VC++中的Ctrl+F7(Compile)鏈接：由鏈接程序?qū)⒛繕四K和相應(yīng)的庫函數(shù)鏈接成裝入模塊。如VC++中的F7(Build)裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存。如VC++中的Ctrl+F5(BuildExecute)4.1程序的鏈接和裝入庫匯編編譯主子1子2目標模塊鏈接程序裝入模塊庫主子1子2裝入程序內(nèi)存庫主子1子24.1程序的鏈接和裝入地址空間程序名字空間：匯編或高級語言程序中通常用符號名(符號地址)訪問數(shù)據(jù)和子程序。這些符號名集合所限定的空間稱作程序名字空間。相對/邏輯/虛地址空間：(匯編或編譯程序?qū)⒎柕刂忿D(zhuǎn)換為相對地址)目標程序中的相對地址集合。絕對/物理/實地址空間：內(nèi)存中實際存儲單元的地址集合。4.1程序的鏈接和裝入物理地址

內(nèi)存000000000100002...0100001FFF主子1子2主子1子2相對地址

裝入模塊000...FFF主子1子2相對地址單個目標模塊0005FF0003FF0003FF4.1程序的鏈接和裝入地址重定位將程序中的邏輯/相對地址轉(zhuǎn)換成物理/絕對地址的過程(地址變換/映射過程)。重定位的類型靜態(tài)重定位：程序執(zhí)行前，一次性，鏈接裝入程序。動態(tài)重定位：處理機每次訪問主存時，由動態(tài)地址變換機構(gòu)（硬件）自動執(zhí)行。4.1程序的鏈接和裝入靜態(tài)重定位示意圖4.1程序的鏈接和裝入動態(tài)重定位示意圖4.2連續(xù)分配存儲管理基本思想：為一個用戶程序分配一片連續(xù)的內(nèi)存空間。單一連續(xù)分區(qū)固定分區(qū)動態(tài)分區(qū)動態(tài)可重定位分區(qū)一、單一連續(xù)分區(qū)(單道作業(yè)固定分區(qū))將內(nèi)存分為系統(tǒng)區(qū)(常為內(nèi)存低端，分配給OS用)和用戶區(qū)(內(nèi)存高端，分配給用戶用)。優(yōu)點：簡單易實現(xiàn)(算法簡單、硬件開銷小)缺點：主存利用率低有內(nèi)碎片，造成很大浪費不支持多道程序設(shè)計，資源利用率低不能實驗存儲擴充改進：多個分區(qū)固定分區(qū)可變分區(qū)基本原理預先(系統(tǒng)初始化時)將主存儲器空間分割成大小相等或不等的若干塊，每塊稱為一個分區(qū)。分區(qū)個數(shù)和每個分區(qū)的大小固定不變，每個分區(qū)裝一個且只能裝一個作業(yè)直到該作業(yè)完成后才釋放該分區(qū)(一個作業(yè)占用連續(xù)的一片存儲空間)。二、固定分區(qū)(多道作業(yè)固定分區(qū))固定分區(qū)(大小相同)固定分區(qū)(大小不同)二、固定分區(qū)(多道作業(yè)固定分區(qū))數(shù)據(jù)結(jié)構(gòu)--分區(qū)說明表(MBT)（1）內(nèi)存分配圖二、固定分區(qū)(多道作業(yè)固定分區(qū))區(qū)號大小起址狀態(tài)18k20k已分配232k28k已分配364k60k已分配4132k124k未分配(2)分區(qū)說明表

通常將分區(qū)按

大小進行排序內(nèi)碎片內(nèi)碎片內(nèi)碎片內(nèi)存分配：內(nèi)存回收：程序執(zhí)行完畢

后釋放占用的分區(qū)，管理

程序修改說明表。地址變換：靜態(tài)重定位或動態(tài)重定位(需要一對界地址寄存器)二、固定分區(qū)(多道作業(yè)固定分區(qū))二、固定分區(qū)(多道作業(yè)固定分區(qū))優(yōu)點：簡單易實現(xiàn)(算法簡單、硬件開銷小)缺點：主存利用率低有內(nèi)碎片，造成浪費雖然支持多道程序設(shè)計，但限制道數(shù)不能實現(xiàn)存儲共享與擴充基本原理：內(nèi)存不預先劃分好(相當于開始時用戶區(qū)是一個連續(xù)分區(qū))，當作業(yè)裝入時，按照作業(yè)的大小動態(tài)地建立分區(qū)。三、動態(tài)(可變)分區(qū)三、動態(tài)分區(qū)數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表：記錄空閑分區(qū)的情況(分區(qū)號、分區(qū)起始地址、分區(qū)大小及狀態(tài))。缺點：表長不易確定，管理困難且查找效率低。三、動態(tài)分區(qū)數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)鏈：用鏈頭指針將空閑分區(qū)鏈接起來。每個空閑分區(qū)的起始部分存放本塊大小和指向下一空閑分區(qū)的指針。頭指針動態(tài)分區(qū)內(nèi)存分配流程圖三、動態(tài)分區(qū)內(nèi)存分配三、動態(tài)分區(qū)根據(jù)空閑分區(qū)的四種組織方式，可有四種分配算法：首次適應(yīng)算法(按起址升序排序，從表首找起)循環(huán)首次適應(yīng)算法(按起址升序排序，從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始找起)最佳適應(yīng)算法(按容量升序排序，從表首找起)最壞適應(yīng)算法(按容量降序排序，從表首找起)四種算法各有優(yōu)缺點，沒有一種是最好的。三、動態(tài)分區(qū)首次適應(yīng)算法（最先適應(yīng)算法）

空閑分區(qū)按起始地址遞增的次序排列。

在進行內(nèi)存分配時，從空閑分區(qū)表(鏈)首開始順序查找，直到找到第一個滿足作業(yè)要求的空閑分區(qū)為止。(找不到則分配失敗，返回)

然后再按作業(yè)大小從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍留在空閑分區(qū)表(鏈)中(要修改相關(guān)數(shù)據(jù))。區(qū)號大小起址132k20k28k52k3120k60k4331k180k空閑分區(qū)表例：空閑分區(qū)表如右，現(xiàn)有三個作業(yè)分配申請內(nèi)存空間100K、30K及7K。給出按首次適應(yīng)算法分配后的空閑分區(qū)表。解：首次適應(yīng)算法(最先適應(yīng)算法)區(qū)號大小起址12k50k21k59k320k160k4331k180k優(yōu)點：分配和釋放時間性能較好，較大的空閑分區(qū)得以保留缺點：隨著低端分區(qū)不斷劃分而產(chǎn)生較多小分區(qū)，每次分配時查找時間開銷會增大循環(huán)首次適應(yīng)算法(下次適應(yīng)算法)由首次適應(yīng)算法演變而來。在為作業(yè)分配內(nèi)存空間時，從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找（到最后分區(qū)時再回到開頭），直到找到第一個能滿足其大小要求的空閑分區(qū)為止。三、動態(tài)分區(qū)區(qū)號大小起址132k20k28k52k3120k60k4331k180k空閑分區(qū)表例：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個作業(yè)分配申請內(nèi)存空間100K、30K及7K。給出按循環(huán)首次適應(yīng)算法分配后的空閑分區(qū)表。解：循環(huán)首次適應(yīng)算法(下次適應(yīng)算法)區(qū)號大小起址132k20k28k52k320k160k4294k217k優(yōu)點：內(nèi)存利用更加均衡，不會使低端形成很多小分區(qū)缺點：但這會導致缺乏大的空閑分區(qū)。三、動態(tài)分區(qū)最佳適應(yīng)算法

“最佳”是指每次為作業(yè)分配內(nèi)存時，總是把既能滿足要求的又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用”。

空閑分區(qū)按容量遞增的次序排列。在進行內(nèi)存分配時，從空閑分區(qū)表(鏈)首開始順序查找，直到找到第一個滿足其大小要求的空閑分區(qū)為止。

分配后，所有空閑分區(qū)要重新進行排序。例：系統(tǒng)中的空閑分區(qū)表如右，現(xiàn)有三個作業(yè)分配申請內(nèi)存空間100K、30K及7K。給出按最佳適應(yīng)算法分配后的空閑分區(qū)表。解：區(qū)號大小起址18k52k232k20k3120k60k4331k180k空閑分區(qū)表最佳適應(yīng)算法區(qū)號大小起址11k59k22k50k320k160k4331k180k優(yōu)點：用最小空間滿足要求。從個別來看，外部碎片較小但從整體來看，會形成較多外部碎片。最壞適應(yīng)算法空閑分區(qū)按容量遞減的次序排列。在進行內(nèi)存分配時，從空閑分區(qū)表(鏈)首開始順序查找，直到找到第一個比之大的空閑分區(qū)為止。

分配后，所有空閑分區(qū)要重新進行排序。三、動態(tài)分區(qū)三、動態(tài)分區(qū)區(qū)號大小起址1331k180k2120k60k332k20k48k52k空閑分區(qū)表最壞適應(yīng)算法例：空閑分區(qū)表如右，現(xiàn)有三個作業(yè)分配申請內(nèi)存空間100K、30K及7K。給出按最壞適應(yīng)算法分配后的空閑分區(qū)表。解：區(qū)號大小起址1194k317k2120k60k332k20k48k52k優(yōu)點：分割后空閑塊仍為較大空塊?；静涣粝滦】臻e分區(qū)缺點：但較大的空閑分區(qū)不被保留。三、動態(tài)分區(qū)練習：軟件設(shè)計師試題假設(shè)某計算機系統(tǒng)的內(nèi)存大小為256K，在某一時刻內(nèi)存的使用情況如圖A所示。此時，若進程順序請求20K、10K和5K的存儲空間，系統(tǒng)采用____算法為進程依次分配內(nèi)存，則分配后的內(nèi)存情況如圖B所示。三、動態(tài)分區(qū)起始地址0K20K

50K90K100K105K135K160K175K195K220K狀態(tài)已用未用已用已用未用已用未用已用未用未用已用容量20K30K40K10K5K30K25K15K20K25K36K圖A起始地址0K20K40K50K90K100K105K135K145K160K175K195K200K220K狀態(tài)已用已用未用已用已用未用已用已用未用已用未用已用未用已用容量20K20K10K40K10K5K30K10K15K15K20K5K20K36K圖BA．最佳適應(yīng)B．最差適應(yīng)C.首次適應(yīng)D．循環(huán)首次適應(yīng)分別畫出四種算法分配前后的空閑分區(qū)表。三、動態(tài)分區(qū)內(nèi)存回收(四種情況)地址變換：動態(tài)重定位(需要一對界限R)。存儲保護：基址/限長保護法；保護鍵法。優(yōu)點分區(qū)的大小和數(shù)目可變沒有內(nèi)碎片，提高了主存利用率支持多道程序設(shè)計且不限制道數(shù)缺點：存在外碎片；不能實現(xiàn)存儲共享與擴充。三、動態(tài)分區(qū)固定分區(qū)和可變分區(qū)的碎片問題內(nèi)碎片示意圖外碎片示意圖內(nèi)碎片內(nèi)碎片內(nèi)碎片外碎片問題的解決方法之一緊湊（拼接）技術(shù)將內(nèi)存中的所有作業(yè)移到內(nèi)存一端，同時修改每個作業(yè)的起始地址，使本來分散的多個小空閑分區(qū)連成一個大的空閑區(qū)。外碎片問題的解決方法之一緊湊（拼接）技術(shù)在動態(tài)分區(qū)存儲管理中增加拼接功能，在找不到足夠大的空閑分區(qū)來滿足作業(yè)要求、而系統(tǒng)中空閑分區(qū)總?cè)萘靠梢詽M足作業(yè)要求時進行拼接。四、動態(tài)可重定位分區(qū)動態(tài)可重定位分區(qū)分配算法流程圖四、動態(tài)可重定位分區(qū)四、動態(tài)可重定位分區(qū)優(yōu)點可以充分利用內(nèi)存中的碎片，提高內(nèi)存利用率。缺點動態(tài)重定位需要硬件支持。緊湊處理增加系統(tǒng)開銷。不能實現(xiàn)內(nèi)存共享和擴充。五、存儲保護固定分區(qū)、可變分區(qū)、動態(tài)可重定位分區(qū)的存儲保護措施：界限寄存器上下界寄存器方法：用這兩個寄存器分別存放作業(yè)的起始地址和結(jié)束地址?；贰⑾揲L寄存器方法：用這兩個寄存器分別存放作業(yè)的起始地址和作業(yè)的地址空間長度。五、存儲保護存儲保護鍵給每個存儲塊（大小相同，一個分區(qū)是存儲塊的整數(shù)倍）分配一個單獨的保護鍵，它相當于一把鎖。系統(tǒng)中的每個進程也賦予一個保護鍵，它相當于一把鑰匙。當進程運行時，檢查鑰匙和鎖是否匹配，如果不匹配，則系統(tǒng)發(fā)出保護性中斷信號，停止作業(yè)運行。連續(xù)分配存儲管理方式小結(jié)單一連續(xù)分區(qū)：不支持多道程序設(shè)計，資源利用率低固定分區(qū)：支持多道但存在內(nèi)碎片動態(tài)分區(qū)沒有內(nèi)碎片但存在外碎片分配與回收慢(分配時查找時間長，釋放時要合并)動態(tài)可重定位分區(qū)：解決了外碎片問題，但存儲緊縮費時，代價較高四種技術(shù)都是連續(xù)分配方式，不能實現(xiàn)存儲共享與擴充。外碎片問題的解決方法之二離散分配：允許將程序離散放到多個不相鄰接的分區(qū)中，可以避免拼接。基于這一思想產(chǎn)生了以下離散分配方式：基本分頁存儲管理基本分段存儲管理基本段頁式存儲管理1.內(nèi)存空間分成若干個大小相等的塊(頁框)，各塊從0開始編號。4.3基本分頁存儲管理一、基本思想物理內(nèi)存01234567…01103.以頁面為單位，將進程中若干頁裝入到多個可能不相鄰的頁框中。2.邏輯空間劃分成若干個大小與塊相等的頁(頁面)，各頁也從0開始編號。用戶進程k4.3基本分頁存儲管理二、數(shù)據(jù)結(jié)構(gòu)系統(tǒng)為每個進程設(shè)一張頁表，描述該進程占用的物理塊號等信息，放在內(nèi)存。4.3基本分頁存儲管理二、數(shù)據(jù)結(jié)構(gòu)頁表：為便于在進程運行時準確地找到各個物理塊，系統(tǒng)用頁表(頁面映像表)記錄進程邏輯頁與內(nèi)存物理塊之間的對應(yīng)關(guān)系及存取控制位。系統(tǒng)設(shè)頁表寄存器用于存儲正在運行進程的頁表基址及長度。訪問1B數(shù)據(jù)/指令需訪問內(nèi)存二次(頁表一次，數(shù)據(jù)/指令一次)，故內(nèi)存訪問速度降低。4.3基本分頁存儲管理三、地址結(jié)構(gòu)采用頁式管理時，用戶程序中的邏輯地址仍然是連續(xù)的、一維的。頁號p頁內(nèi)地址dn-1k+1k0(n位)邏輯地址結(jié)構(gòu)(p,d)

：假設(shè)我們的一頁只能容納1000行，請問我們寫的文章的第5678行(從0開始)會分到第幾頁(從0開始)的第幾行(從0開始)？自然截斷4.3基本分頁存儲管理三、地址結(jié)構(gòu)內(nèi)存地址是連續(xù)的、一維的。塊號b塊內(nèi)地址dm-1k+1k0(m位)物理地址結(jié)構(gòu)(b,d)：假設(shè)我們寫的文章的第5678行(從0開始)被抄寫在第8號(從0開始)紙上，請問第5678行對應(yīng)的物理行號是多少？自然拼接4.3基本分頁存儲管理三、地址結(jié)構(gòu)例：設(shè)有一頁式存儲管理系統(tǒng)，向用戶提供的邏輯地址空間最大為16頁，每頁2048B，內(nèi)存總共有8個存儲塊，(1)邏輯地址至少應(yīng)為多少位？(2)內(nèi)存空間有多大？(1)2048=211，所以頁內(nèi)地址為11位。

16=24，頁號為4位。故邏輯地址至少為15位。(2)塊與頁大小相等，所以塊內(nèi)地址也為11位。

8=23，塊號為3位。故內(nèi)存空間應(yīng)為214=16KB。4.3基本分頁存儲管理三、地址結(jié)構(gòu)若給定一個邏輯地址空間中的地址為A，頁面大小為L，則頁號p和頁內(nèi)地址d的計算公式為：4.3基本分頁存儲管理三、地址結(jié)構(gòu)例1：頁大小為1024B，邏輯地址3456對應(yīng)的數(shù)對(p,d)為多少？（3，384）思考頁內(nèi)地址占幾位？10位(210=1024)若邏輯地址最大為123456，則頁號需幾位？int(123456/1024)=120；27=128>1214.3基本分頁存儲管理三、地址結(jié)構(gòu)例2：頁大小為1024B，則邏輯地址(4101)d的頁號和頁內(nèi)地址可按如下二種方法計算：方法一：p=int(4101/1024)=4

d=4101-4*1024=5所以4101對應(yīng)的數(shù)對是：(4,5)方法二：

(4101)d=(1000000000101)b

因為1024=210，所以頁內(nèi)地址需要10位

結(jié)果4101對應(yīng)的數(shù)對是：(4,5)。4.3基本分頁存儲管理四、地址變換(p,d→b,d)基本的地址變換機構(gòu)示意圖≤物理地址的計算也有兩種方法：b*L+d拼接思考：越界中斷有可能是頁內(nèi)地址引起的嗎？4.3基本分頁存儲管理四、地址變換(p,d→b,d)例：在一分頁存儲管理系統(tǒng)中，某作業(yè)的頁表如表所示，已知頁面大小為1024B，試將十進制邏輯地址1011、2148和5012轉(zhuǎn)換為相應(yīng)的物理地址。邏輯地址1011對應(yīng)的物理地址為3059。

邏輯地址2148對應(yīng)的物理地址為1124。

邏輯地址5012產(chǎn)生越界中斷。頁號塊號021321364.3基本分頁存儲管理四、地址變換(p,d→b,d)快表(聯(lián)想存儲器)：是一種特殊的高速緩沖存儲器。存放當前訪問的那些頁表項。先在快表中尋找頁對應(yīng)的物理塊；若未找到(未命中)，再到頁表中找，并將該頁表項復制到快表。若快表已滿，則按某種算法淘汰某些頁表項。4.3基本分頁存儲管理四、地址變換(p,d→b,d)≤具有快表的地址變換機構(gòu)4.3基本分頁存儲管理五、頁的共享4.3基本分頁存儲管理五、頁的共享與保護頁的共享：一般不能實現(xiàn)共享，因為頁的劃分沒有邏輯意義頁的保護

地址越界檢查在頁表中設(shè)置存取控制位進行越權(quán)檢查(定義操作權(quán)限：只讀、讀寫、執(zhí)行等)4.3基本分頁存儲管理優(yōu)點離散存放、無外碎片；內(nèi)存分配和釋放速度快。缺點(頁表、動態(tài)地址轉(zhuǎn)換機構(gòu)、快表等)增加系統(tǒng)開銷；內(nèi)存訪問速度降低；每個進程平均擁有半頁內(nèi)碎片；頁面共享困難；程序需全部裝入內(nèi)存，不能進行存儲擴充。4.4基本分段存儲管理程序按邏輯關(guān)系劃分為段，從0編號，有名字和段長。邏輯地址由段號和段內(nèi)地址確定。引入原因：滿足用戶要求便于編程和調(diào)試便于共享便于保護動態(tài)鏈接動態(tài)增長：某些段(數(shù)據(jù)段)會不斷增長，前面的存儲管理方法難以實現(xiàn)。4.4基本分段存儲管理一、基本原理邏輯地址空間：分段劃分為若干大小不等的段（由用戶根據(jù)邏輯信息的相對完整來劃分），段號從0開始，每段內(nèi)的邏輯地址空間都從0開始編址(段內(nèi)地址)。物理地址空間：可變分區(qū)在為作業(yè)分配內(nèi)存時，以段為單位，分配一段連續(xù)的物理地址空間；段間不必連續(xù)。4.4基本分段存儲管理基本原理示意圖二、數(shù)據(jù)結(jié)構(gòu)：段表每個進程設(shè)置一個段表，描述該進程占用的物理分區(qū)及邏輯排列順序，放在內(nèi)存。段表的基址及長度(段數(shù))由段表寄存器給出4.4基本分段存儲管理段號段長基址030k40k120k80k215k120k310k150k訪問1B數(shù)據(jù)/指令需訪問內(nèi)存二次(段表一次，內(nèi)存一次)，所以也出現(xiàn)內(nèi)存訪問速度降低的問題。4.4基本分段存儲管理三、邏輯地址結(jié)構(gòu)子程序段X數(shù)據(jù)段A┇call[X]∣<E>(調(diào)用X段的入口E)┇call[Y]∣<E>(調(diào)用Y段的入口E)┇load1,[A]∣<E>

(調(diào)用數(shù)組段A[E])┇主程序段E：┅┅┅E：┅┅┅子程序段YE：┅┅┅模塊化程序設(shè)計的分段結(jié)構(gòu)三、邏輯地址結(jié)構(gòu)進程的地址空間分成多個段，因而其邏輯地址是二維的，由段號(段名)和段內(nèi)地址（段內(nèi)偏移量）組成。4.4基本分段存儲管理內(nèi)存四、存儲分配以段為單位，每段分配一塊連續(xù)的分區(qū)，一次分配作業(yè)所需的所有分區(qū)，一個進程的各段所分到的分區(qū)不必相鄰。4.4基本分段存儲管理第0段第1段第2段第3段用戶作業(yè)段表基址段長150K35K500K9K300K20K100K42K3210段號第0段第1段第2段第3段≤≤4.4基本分段存儲管理五、地址變換注意：兩種越界情況！①②③④44.4基本分段存儲管理五、地址轉(zhuǎn)換邏輯地址(S,W)-->物理地址當進程要訪問某個邏輯地址中的數(shù)據(jù)時，系統(tǒng)將段號S與段表寄存器中的段表長度TL進行比較。如STL，則訪問越界，發(fā)生越界中斷；否則，根據(jù)S讀出該段的基址；若段內(nèi)地址W段長，則訪問越界，發(fā)生越界中斷；否則，將段的基址與段內(nèi)地址W相加，得到邏輯地址對應(yīng)的物理地址；根據(jù)此物理地址訪問內(nèi)存。4.4基本分段存儲管理五、地址轉(zhuǎn)換例：現(xiàn)有一作業(yè)，在段式存儲管理系統(tǒng)中，已為主存分配建立了如表所示的段表，試回答：該作業(yè)訪問(1，120)、(2，200)、(4，600)時的絕對地址。（第一個元素為段號，第二個為段內(nèi)地址）段號段長基址068017601160100022001560389028004.4

基本分段存儲管理六、存儲保護段表寄存器越界檢查：段表長度與段號S比較；段長與段內(nèi)位移量W比較存取控制位越權(quán)檢查分段系統(tǒng)中共享editor的示意圖4.4

基本分段存儲管理七、存儲共享4.4

基本分段存儲管理優(yōu)點沒有內(nèi)碎片；外碎片有改善且可通過緊湊技本來消除；便于編程、動態(tài)鏈接、動態(tài)申請內(nèi)存、動態(tài)增長、存儲共享和保護。缺點仍有外碎片；進程需全部裝入內(nèi)存，不能進行存儲擴充。基本分頁和基本分段的比較頁式存儲管理段式存儲管理目的解決碎片問題更好滿足用戶需要信息單位頁（物理單位）段（邏輯單位）大小固定(由系統(tǒng)定)用戶不可見不定(由用戶程序定)用戶可見內(nèi)存分配單位頁段邏輯地址一維二維優(yōu)點解決了碎片問題提高內(nèi)存利用率便于共享、保護段可動態(tài)增長便于動態(tài)鏈接二者優(yōu)點的結(jié)合----段頁式存儲管理(本章最后補充)基本存儲管理方式單一連續(xù)分區(qū)固定分區(qū)動態(tài)分區(qū)動態(tài)可重定位分區(qū)基本分頁基本分段非請求段頁式4.5虛擬存儲器的基本概念一、虛擬存儲器的引入局部性原理：程序在執(zhí)行時呈現(xiàn)出局部性規(guī)律，即在一較短時間內(nèi)，程序的執(zhí)行僅限于某個部分，相應(yīng)地，它所訪問的存儲空間也局限于某個區(qū)域。時間局部性(程序的循環(huán)結(jié)構(gòu))：一條指令被執(zhí)行/一個存儲單元被訪問，則在不久的將來它可能再次被執(zhí)行/訪問空間局部性(程序的順序結(jié)構(gòu))：一條指令被執(zhí)行/一個存儲單元被訪問，則在不久的將來，其附近的指令/存儲單元也可能被執(zhí)行/訪問4.5虛擬存儲器的基本概念一、虛擬存儲器的引入虛擬存儲管理的基本思想在程序裝入時，只需將當前需要執(zhí)行的部分頁/段讀入到內(nèi)存，就可讓程序開始執(zhí)行。在程序執(zhí)行過程中，如果需執(zhí)行的指令或訪問的數(shù)據(jù)不在內(nèi)存(缺頁/段)，則由處理器通知OS將相應(yīng)的頁/段調(diào)入內(nèi)存，然后繼續(xù)執(zhí)行程序。另一方面，OS將內(nèi)存中暫時不用的頁/段調(diào)出內(nèi)存，騰出空間存放將要裝入的程序及將要調(diào)入的頁/段。4.5虛擬存儲器的基本概念一、虛擬存儲器的引入虛擬存儲器：具有請求調(diào)入功能和頁/段置換功能，能從邏輯上對內(nèi)存容量進行擴充的存儲器系統(tǒng)。邏輯容量=可尋址范圍實際容量=內(nèi)存+外存對換區(qū)若CPU的有效地址長度為32位，則程序可以尋址范圍是0～232-1，即虛存邏輯容量為4GB。XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K

8K-12K

4K-8K

0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K

8K-12K

4K-8K

0K-4K虛地址空間實地址空間}虛頁頁框虛擬頁式存儲器示意圖4.5虛擬存儲器的基本概念一、虛擬存儲器的引入實現(xiàn)虛擬存儲器的代價頁表、段表等數(shù)據(jù)結(jié)構(gòu)缺頁中斷機構(gòu)動態(tài)地址變換機構(gòu)缺頁/段時的請求調(diào)頁/段和頁/段置換以CPU時間和輔存空間換取內(nèi)存空間。4.5虛擬存儲器的基本概念二、虛擬存儲器的特征多次性：是虛擬存儲器最重要的特征。指一個作業(yè)被分成多次調(diào)入內(nèi)存運行。對換性：指允許在作業(yè)運行過程中進行換進、換出。換進、換出可提高內(nèi)存利用率。虛擬性：指能夠從邏輯上擴充內(nèi)存容量，使用戶看到的內(nèi)存容量遠大于實際內(nèi)存容量。4.6請求分頁存儲管理在基本分頁存儲管理系統(tǒng)的基礎(chǔ)上，增加請求調(diào)頁和頁面置換功能所形成的頁式虛擬存儲器系統(tǒng)。基本思想地址空間的劃分與基本分頁相同。作業(yè)裝入時，不裝入全部頁面，只裝入作業(yè)的一部分(運行所需)頁即可運行，之后根據(jù)進程運行的需要，動態(tài)裝入其它頁面。當內(nèi)存已滿而又需要裝入新頁時，則根據(jù)某種算法淘汰某個頁面，以裝入新頁。4.6請求分頁存儲管理一、硬件支持

1.頁表

狀態(tài)位：指示該頁是否在內(nèi)存。訪問字段：記錄本頁在一段時間內(nèi)被訪問的次數(shù)或最近未被訪問的時間。修改位：表示該頁在調(diào)入內(nèi)存后是否被修改過。若修改過，則換出時需重寫至外存。外存地址：指出該頁在外存上的地址。頁號塊號狀態(tài)位訪問字段修改位外存地址4.6請求分頁存儲管理一、硬件支持

2.缺頁中斷機構(gòu)

當要訪問的頁不在內(nèi)存(即缺頁)時，便產(chǎn)生一個缺頁中斷，請求OS將所缺頁調(diào)入內(nèi)存空閑塊，若無空閑塊，則需置換某一頁，同時修改頁表。4.6請求分頁存儲管理開始頁號>頁表長度？CPU檢索快表NNY頁表項在快表中？訪問頁表頁在內(nèi)存？修改訪問位和修改位修改快表形成物理地址地址變換結(jié)束越界中斷程序請求訪問一頁YN缺頁中斷處理Y保留CPU現(xiàn)場內(nèi)存滿嗎？將一頁從外存換入內(nèi)存OS命令CPU從外存讀缺頁啟動I/O硬件Y從外存中找到缺頁選擇一頁換出該頁被修改否？將該頁寫回外存修改頁表NYN一、硬件支持3.地址變換機構(gòu)≤4.6請求分頁存儲管理一、硬件支持

3.地址變換機構(gòu)地址變換示意圖≤第4章請求分頁地址轉(zhuǎn)換.swf4.6請求分頁存儲管理例：某虛擬存儲器的用戶空間共有32個頁面，每頁1KB，主存16KB。假定某時刻系統(tǒng)為用戶的第0、1、2、3頁分別分配的物理塊號為5、10、4、7，試將虛擬地址0A5C和093C變換為物理地址。解：頁內(nèi)位移和塊內(nèi)位移為10bits（110=1024）虛擬地址OA5C對應(yīng)的二進制為：

000101001011100即虛擬地址OA5C的頁號為2，對應(yīng)的物理塊號為4，所以對應(yīng)的物理地址為：

01001001011100即125C4.6請求分頁存儲管理二、頁面調(diào)入過程保留CPU現(xiàn)場內(nèi)存滿嗎？將一頁從外存換入內(nèi)存OS命令CPU從外存讀缺頁啟動I/O硬件Y從外存中找到缺頁選擇一頁換出該頁被修改否？將該頁寫回外存修改頁表NYN內(nèi)存空間有限，不能裝入進程申請的所有頁面。在裝入新的頁面時，如果內(nèi)存滿，需要淘汰已裝入頁面。4.7頁面置換算法也稱頁面淘汰算法，是決定選擇淘汰哪一頁的規(guī)則。算法衡量標準：缺頁中斷率f=F/A;其中，A：作業(yè)執(zhí)行中訪問頁面的總次數(shù)

F：缺頁中斷次數(shù)算法目標：降低缺頁率4.7頁面置換算法常用算法最佳置換算法OPT：淘汰永遠不再需要的頁面或最遠的將來才需要訪問的頁面。先進先出置換算法FIFO：淘汰最先進入內(nèi)存的頁面。最近最久未用置換算法LRU：淘汰最近一次訪問發(fā)生在最遠的過去的頁面。4.7頁面置換算法一、最佳置換算法OPT思想：Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的，或者是在最長(未來)時間內(nèi)不再被訪問的頁面。簡單地說，淘汰在最遠的將來才需要訪問的頁面。4.7頁面置換算法一、最佳置換算法OPT例：假定系統(tǒng)為某進程分配了3個頁框。該進程的頁面引用序列為：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。開始時3個物理塊均為空。6次頁面置換，9次缺頁中斷，缺頁率為9/20頁面置換圖為：4.7頁面置換算法一、最佳置換算法OPT優(yōu)點：理論上，性能最佳。缺點：實際上，無法實現(xiàn)，因為難以預知一個作業(yè)將來會用到哪些頁面。通常只用在研究其它算法時做參考評價。4.7頁面置換算法二、先進先出置換算法FIFO思想：淘汰在內(nèi)存中駐留時間最長的頁面?；蛘哒f是淘汰最早進入內(nèi)存的頁面。依據(jù)：最早調(diào)入內(nèi)存的頁面，其不再被訪問的可能性會大一些。實現(xiàn)：進入主存的各頁面按進入的時間次序用鏈指針鏈成隊列，新進入的頁面放在鏈尾，先進入的頁面放在鏈頭，總是從鏈頭淘汰頁面。4.7頁面置換算法二、先進先出置換算法FIFO例：假定系統(tǒng)為某進程分配了3個頁框。該進程的頁面引用序列為：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。開始時3個物理塊均為空。頁面置換圖為：12次頁面置換，15次缺頁中斷，缺頁率為15/204.7頁面置換算法二、先進先出置換算法FIFO優(yōu)點：實現(xiàn)簡單；對具有線性順序訪問的程序比較合適。缺點效率不高（因為經(jīng)常被訪問的頁面，往往在內(nèi)存中停留最久，結(jié)果這些常用的頁面卻因變老而被淘汰）存在Belady現(xiàn)象(即在某些情況下會出現(xiàn)分配給的進程物理塊數(shù)增多，缺頁次數(shù)有時增加、有時減少的現(xiàn)象)。4.7頁面置換算法二、先進先出置換算法FIFOBelady現(xiàn)象示例。設(shè)程序訪問頁的順序為1,2,3,4,1,2,5,1,2,3,4,5如果在內(nèi)存中分配3個物理塊，頁面置換圖如下所示(頁號按FIFO排序)缺頁率：9/124.7頁面置換算法二、先進先出置換算法FIFOBelady現(xiàn)象示例。如果在內(nèi)存中分配4個物理塊，頁面置換圖如下所示(頁號按FIFO排序)缺頁率：10/124.7頁面置換算法三、最近最久未用算法LRU思想：淘汰內(nèi)存中到目前為止最長時間未被訪問過的頁面。依據(jù)：如果某頁被訪問了，它可能馬上還要被訪問；或者說，如果某頁很長時間未被訪問，則它在最近一段時間也不會被訪問。優(yōu)點：性能接近于OPT算法缺點：不易實現(xiàn)，系統(tǒng)開銷大4.7頁面置換算法三、最近最久未用算法LRU例：假定系統(tǒng)為某進程分配了3個頁框。該進程的頁面引用序列為：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。開始時3個物理塊均為空。頁面置換圖為：9次頁面置換，12次缺頁中斷，缺頁率12/204.7頁面置換算法練習：某進程在內(nèi)存中分配三個頁框，初始均為空，頁面走向為4,2,1,4,3,5,4,3,2,1,5。請分別用最佳置換、先進先出和最近最久未用算法計算該引用串共發(fā)生了多少次缺頁，并分析先進先出算法是否會產(chǎn)生Belady現(xiàn)象？4.7頁面置換算法444444442112222555555113333333OPT算法：421435432157次缺頁，4次置換4.7頁面置換算法444333222222555111114445FIFO算法：421435432159次缺頁，6次置換4.7頁面置換算法444444112233335115222LRU算法：421435432158次缺頁，5次置換4.7頁面置換算法假設(shè)為進程分配4個頁框，F(xiàn)IFO算法：444221421435432158次缺頁，5次置換4.8請求分段存儲管理在基本分段存儲管理系統(tǒng)的基礎(chǔ)上，增加請求調(diào)段和段置換功能所形成的段式虛擬存儲器系統(tǒng)?；舅枷氲刂房臻g的劃分與基本分段相同。在作業(yè)裝入時，不裝入全部段，只裝入零或一段，之后根據(jù)進程運行的需要，動態(tài)裝入其它段。當內(nèi)存已滿而又需要裝入新段時，則根據(jù)某種算法淘汰某個段，以裝入新段。4.8請求分段存儲管理硬件支持

1.段表機制存取方式：存取屬性（執(zhí)行、只讀、允許讀/寫）訪問字段：記錄該段被訪問的頻繁程度修改位：該段在進入內(nèi)存后，是否被修改過。存在位：該段是否在內(nèi)存中。增補位：在運行過程中，該段是否做過動態(tài)增長。外存地址：該段在外存中的起始地址。段長段的基址存取方式訪問字段修改位存在位增補位外存地址4.8請求分段存儲管理硬件支持

2.缺段中斷機構(gòu)當要訪問的段不在內(nèi)存中（即缺段）時，將產(chǎn)生缺段中斷信號，請求OS將所缺段調(diào)入內(nèi)存空閑塊，若無空閑塊，則需置換某一段，同時修改段表。4.8請求分段存儲管理開始返回w≤段長？修改訪問字段形成內(nèi)存地址分段越界中斷處理NYY段S在內(nèi)存？符合存取方式？分段保護中斷處理缺段中斷處理YNN硬件支持

3.地址變換機構(gòu)請求分段地址轉(zhuǎn)換.swf

Cl

Cb+段號S段內(nèi)地址w≤≤b+w段表快表物理地址段表寄存器段表長度寄存器邏輯地址lb...Slb地址越界地址越界地址越界≤具有快表的請求分段地址變換機構(gòu)示意圖第4章請求分段地址轉(zhuǎn)換.swf補充：(請求)段頁式存儲管理一、基本原理：段式與頁式結(jié)合將主存劃分為若干頁框?qū)⑦M程的地址空間先分段，每段再分頁主存以頁框為單位分配邏輯地址結(jié)構(gòu)：

(段號s,段內(nèi)頁號p,頁內(nèi)地址d)段號段內(nèi)地址w段內(nèi)頁號p頁內(nèi)地址d補充：(請求)段頁式存儲管理一、基本原理一個程序首先被劃分成若干程序段，每段一個分段標識符。然后，將每一分段分成若干固定大小的頁面。主程序段數(shù)據(jù)段子程序段補充：(請求)段頁式存儲管理二、數(shù)據(jù)結(jié)構(gòu)段表：每個進程一個段表(表目包括段號、頁表基址、頁表長度、存取控制位)頁表：每段建立一個(段內(nèi))頁表(表目包括頁號、物理塊號、狀態(tài)位、外存地址、訪問位、修改位、存取控制位等)段表寄存器：標識當前正在運行進程的段表基址和長度。補充：(請求)段頁式存儲管理段表、頁表之間的關(guān)系……段表始址段表長度段表13021110頁表始址頁表長度狀態(tài)段號段表寄存器頁表03121110存儲塊號狀態(tài)頁號頁表1110存儲塊號狀態(tài)頁號補充：(請求)段頁式存儲管理二、地址變換從段表地址寄存器中讀取段表基址，找到段表；由段號＋段表基址得到段描述子地址；從段描述子讀取頁表基址，找到頁表；由頁號＋頁表基址得到頁描述子地址；從頁描述子讀取頁框(物理塊)號；頁框號