1、計(jì)算機(jī)操作系統(tǒng)第四章 存儲(chǔ)器管理9/19/202219/19/202229/19/20223第四章 存儲(chǔ)器管理 4.1 程序的裝入和鏈接 4.2 連續(xù)分配方式 4.3 基本分頁存儲(chǔ)管理方式 4.4 基本分段存儲(chǔ)管理方式 4.5 虛擬存儲(chǔ)器的基本概念 4.6 請(qǐng)求分頁存儲(chǔ)管理方式 4.7 頁面置換算法 4.8 請(qǐng)求分段存儲(chǔ)管理方式 存儲(chǔ)管理研究的課題 存儲(chǔ)分配問題。 重點(diǎn)是研究存儲(chǔ)共享和各種分 配算法。 地址再定位問題。 研究各種地址變換機(jī)構(gòu)， 以 及靜態(tài)和動(dòng)態(tài)再定位方法。 存儲(chǔ)保護(hù)問題。 研究保護(hù)各類程序、 數(shù)據(jù)區(qū)的 方法。 存儲(chǔ)擴(kuò)充問題。 主要研究虛擬存儲(chǔ)器問題及其各 種調(diào)度算法。存儲(chǔ)器管理

2、主要研究三方面的問題： ?。╢etch） 放（placement） 替換（replacement）請(qǐng)調(diào)、預(yù)調(diào)連續(xù)、非連續(xù)存儲(chǔ)層次結(jié)構(gòu)9/19/20227外存(secondary storage)DOS核心命令處理程序內(nèi)存(primary storage)高速緩存(cache)寄存器(register)速度容量小大低高本章主要研究?jī)?nèi)容主存管理的功能 地址映射(地址重定位) 主存分配和回收 存儲(chǔ)保護(hù)和共享 主存擴(kuò)充(虛擬內(nèi)存) 9/19/20228 二. 主存分配與回收 要完成內(nèi)存的分配和回收工作，要求設(shè)計(jì)者選擇和確定以下幾種策略和結(jié)構(gòu)：調(diào)入策略放置策略置換策略分配結(jié)構(gòu)9/19/20229調(diào)入策略

3、用戶程序在何時(shí)調(diào)入內(nèi)存的策略。目前有請(qǐng)調(diào)和預(yù)調(diào)兩種9/19/202210放置策略用戶程序調(diào)入內(nèi)存時(shí)，確定將其放置在何處的策略。9/19/202211置換策略當(dāng)需要將某個(gè)用戶程序調(diào)入內(nèi)存而內(nèi)存空間又不夠時(shí)，就要確定哪個(gè)或哪些程序可以從內(nèi)存中移走。9/19/202212分配結(jié)構(gòu)分配結(jié)構(gòu)是用來登記內(nèi)存使用情況的數(shù)據(jù)結(jié)構(gòu)。如空閑區(qū)表、空閑區(qū)隊(duì)列等。9/19/202213引起內(nèi)存分配和回收的原因進(jìn)程的開始和結(jié)束。進(jìn)程運(yùn)行的過程中，它所占用的內(nèi)存也可能發(fā)生變化。如棧的變化。進(jìn)程映像在內(nèi)存和外存之間傳遞。由于內(nèi)存有限，系統(tǒng)中不可能容納所有進(jìn)程，有些進(jìn)程的映像可以存放在外存，當(dāng)要運(yùn)行這些進(jìn)程時(shí)，必須把它們調(diào)入

4、內(nèi)存。系統(tǒng)為了充分利用內(nèi)存空間，有時(shí)可能對(duì)內(nèi)存空間進(jìn)行調(diào)整。9/19/202214三.存儲(chǔ)保護(hù)保證在內(nèi)存中的多道程序只能在給定的存儲(chǔ)區(qū)域內(nèi)活動(dòng)并互不產(chǎn)生干擾。 包括：防止地址越界防止越權(quán)(對(duì)共享區(qū)有訪問權(quán))9/19/202215存儲(chǔ)保護(hù)的硬件支持界地址寄存器（界限寄存器）界地址寄存器被廣泛使用的一種存儲(chǔ)保護(hù)技術(shù)機(jī)制比較簡(jiǎn)單，易于實(shí)現(xiàn)9/19/202216實(shí)現(xiàn)方法在CPU中設(shè)置一對(duì)下限寄存器和上限寄存器存放用戶作業(yè)在主存中的下限和上限地址也可將一個(gè)寄存器作為基址寄存器，另一寄存器作為限長(zhǎng)寄存器（指示存儲(chǔ)區(qū)長(zhǎng)度）每當(dāng)CPU要訪問主存，硬件自動(dòng)將被訪問的主存地址與界限寄存器的內(nèi)容進(jìn)行比較，以判斷是否

5、越界如果未越界，則按此地址訪問主存，否則將產(chǎn)生程序中斷越界中斷（存儲(chǔ)保護(hù)中斷）9/19/202217圖示9/19/202218四.主存擴(kuò)充(虛擬內(nèi)存)為了使程序員在編程時(shí)不受內(nèi)存的結(jié)構(gòu)和容量的限制，系統(tǒng)為用戶構(gòu)造一種存儲(chǔ)器，其結(jié)構(gòu)可能與內(nèi)存結(jié)構(gòu)不同，容量可能遠(yuǎn)遠(yuǎn)超過內(nèi)存的實(shí)際容量。這種面向編程的存儲(chǔ)器稱為虛擬存儲(chǔ)器。由虛存構(gòu)成的存儲(chǔ)空間稱為虛存空間。或稱虛地址空間。9/19/202219實(shí)現(xiàn)虛擬內(nèi)存的基本原理將程序正在使用的部分內(nèi)容放在內(nèi)存，而暫時(shí)不用的部分放在外存，在需要時(shí)由系統(tǒng)調(diào)入內(nèi)存，并將不需要（或暫不需要）的部分調(diào)出內(nèi)存。由于程序在執(zhí)行時(shí)，在一段時(shí)間內(nèi)一般僅使用它的程序的一部分（或一小

6、部分），所以程序僅有部分裝入內(nèi)存完全能夠正確執(zhí)行。要由操作系統(tǒng)結(jié)合相關(guān)硬件來完成上述工件，這樣計(jì)算機(jī)好象為用戶提供了一個(gè)容量遠(yuǎn)大于內(nèi)存的存儲(chǔ)器，這個(gè)存儲(chǔ)器稱為虛擬存儲(chǔ)器。 9/19/2022204.1 程序的裝入和鏈接將用戶源程序變?yōu)榭稍趦?nèi)存中執(zhí)行的程序的步驟：編譯：由編譯程序?qū)⒂脩粼创a編譯成若干個(gè)目標(biāo)模塊鏈接：由鏈接程序?qū)⒕幾g后形成的一組目標(biāo)模塊，以及它們所需要的庫函數(shù)鏈接在一起，形成一個(gè)完整的裝入模塊裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存，構(gòu)造PCB，形成進(jìn)程(使用物理地址)9/19/2022214.1 程序的裝入和鏈接9/19/202222庫鏈接程序裝入模塊裝入程序編譯程序產(chǎn)生的目標(biāo)模塊第

7、一步第二步第三步內(nèi)存一.地址映射(地址重定位)物理地址（內(nèi)存地址，絕對(duì)地址，實(shí)地址）：內(nèi)存的每個(gè)存儲(chǔ)單元都有一個(gè)編號(hào)，這個(gè)編號(hào)稱為物理地址；內(nèi)存地址的集合稱為內(nèi)存空間（或物理地址空間）；物理地址可直接尋址9/19/202223一.地址映射(地址重定位)邏輯地址（程序地址，相對(duì)地址，虛地址）：用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對(duì)地址的形式；由邏輯地址組成的空間稱為邏輯地址空間（或程序地址空間）其首地址為0，其余指令中的地址都相對(duì)于首地址來編址。不能用邏輯地址在內(nèi)存中讀取信息。9/19/2022249/19/202225 地址映射（地址重定位）：用戶程序裝入內(nèi)存時(shí)對(duì)有關(guān)指令

8、的地址部分的修改定義為從程序地址到內(nèi)存地址的地址映射，或稱為地址重定位創(chuàng)建進(jìn)程時(shí)，由于程序的邏輯地址與分配到內(nèi)存物理地址不一致, 而CPU執(zhí)行指令時(shí)，是按物理地址進(jìn)行的，所以要進(jìn)行地址映射。為何要進(jìn)行地址映射？一.地址映射(地址重定位)地址映射的方式靜態(tài)地址映射（靜態(tài)重定位）動(dòng)態(tài)地址映射（動(dòng)態(tài)重定位）9/19/2022261、靜態(tài)地址映射靜態(tài)地址映射（靜態(tài)重定位）：程序被裝入內(nèi)存時(shí)由操作系統(tǒng)的鏈接裝入程序完成程序的邏輯地址到內(nèi)存地址的轉(zhuǎn)換。9/19/202227映射方法假定程序裝入內(nèi)存的首地址為BR，程序地址為VR，內(nèi)存地址為MR，則地址映射按下式進(jìn)行：MR=BR+VR 。例如，程序裝入內(nèi)存的

9、首地址為1000，則裝配程序就按MR=1000+VR對(duì)程序中所有地址部分進(jìn)行修改9/19/2022289/19/202229地址映射BR=1000Load A 1200 3456 。 。1200物理地址空間Load A data1data1 3456源程序Load A 200 34560100200編譯邏輯地址空間邏輯地址、物理地址和地址映射名空間地址空間存儲(chǔ)空間優(yōu)缺點(diǎn)優(yōu)點(diǎn)：不需要硬件的支持，可以裝入有限多道程序。缺點(diǎn)：一個(gè)程序通常需要占用連續(xù)的內(nèi)存空間，程序裝入內(nèi)存后不能移動(dòng)。不易實(shí)現(xiàn)共享。9/19/2022302、動(dòng)態(tài)地址映射動(dòng)態(tài)地址映射（動(dòng)態(tài)重定位）：是在程序執(zhí)行的過程中，每次訪問內(nèi)存之

10、前，將要訪問的程序地址轉(zhuǎn)換為內(nèi)存地址；一般來說這種轉(zhuǎn)換是由專門的硬件機(jī)構(gòu)來完成的。9/19/202231映射方法最簡(jiǎn)單的硬件機(jī)構(gòu)是重定位寄存器；在地址重定位機(jī)構(gòu)中，有一個(gè)基地址寄存器BR和一個(gè)程序地址寄存器VR，一個(gè)內(nèi)存地址寄存器MR。9/19/2022329/19/20223303456.LOAD A 200.0100200300.LOAD A 2003456110012001300200VR+1000BR1200MR地址映射的具體過程程序裝入內(nèi)存后，它所占用的內(nèi)存區(qū)的首地址由系統(tǒng)送入基地址寄存器BR中。在程序執(zhí)行的過程中，若要訪問內(nèi)存，將訪問的邏輯地址送入程序地址寄存器VR中。 地址轉(zhuǎn)換機(jī)

11、構(gòu)把VR和BR中的內(nèi)容相加，并將結(jié)果送入內(nèi)存地址寄存器MR中，作為實(shí)際訪問的地址。9/19/202234動(dòng)態(tài)地址映射的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：OS可以將一個(gè)程序分散存放于不連續(xù)的內(nèi)存空間可以移動(dòng)程序有利于實(shí)現(xiàn)共享缺點(diǎn)：需要硬件支持OS實(shí)現(xiàn)較復(fù)雜9/19/202235虛擬存儲(chǔ)的基礎(chǔ)4.1.2 程序的鏈接靜態(tài)鏈接：在程序運(yùn)行前，將目標(biāo)模塊及所需的庫函數(shù)鏈接成一個(gè)完整的裝配模塊，以后不再拆開。裝入時(shí)動(dòng)態(tài)鏈接：指將用戶源程序編譯后所得的一組目標(biāo)模塊，在裝入內(nèi)存時(shí)，采用邊裝入邊鏈接的鏈接方式。運(yùn)行時(shí)動(dòng)態(tài)鏈接：指對(duì)某些目標(biāo)模塊的鏈接，是在程序執(zhí)行中需要該目標(biāo)模塊時(shí)，才對(duì)它進(jìn)行鏈接。9/19/2022361、靜態(tài)鏈接(

12、static-linking)9/19/202237返回靜態(tài)鏈接是在生成可執(zhí)行文件時(shí)進(jìn)行的。在目標(biāo)模塊中記錄符號(hào)地址(symbolic address)，而在可執(zhí)行文件中改寫為指令直接使用的數(shù)字地址。4.1.2 程序的和鏈接9/19/202238靜態(tài)鏈接方式：事先進(jìn)行鏈接，以后不再拆開模塊ACALL B;Return;0L-1模塊BCALL C;Return;0M-1模塊CReturn;0N-1模塊AJSR “L”Return;0L-1模塊BJSR “L+M”Return;LL+M-1模塊CReturn;L+ML+M+N-1目標(biāo)模塊裝入模塊將目標(biāo)模塊裝配成裝入模塊時(shí)需解決的兩個(gè)問題：(1)變換

13、外部調(diào)用符號(hào)(2)對(duì)相對(duì)地址進(jìn)行修改對(duì)相對(duì)地址進(jìn)行修改變換外部調(diào)用符號(hào)2. 裝入時(shí)動(dòng)態(tài)鏈接 (Load-time Dynamic Linking) 邊裝入邊鏈接。優(yōu)點(diǎn)：(1) 便于修改和更新(2) 便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享9/19/202239動(dòng)態(tài)鏈接(dynamic-linking)在裝入或運(yùn)行時(shí)進(jìn)行鏈接。通常被鏈接的共享代碼稱為動(dòng)態(tài)鏈接庫(DLL, Dynamic-Link Library)或共享庫(shared library)。3. 運(yùn)行時(shí)動(dòng)態(tài)鏈接(Run-time Dynamic Linking)邊執(zhí)行邊鏈接！優(yōu)點(diǎn)： 加快裝入過程、節(jié)省內(nèi)存空間9/19/2022409/19/2022

14、414.2 連續(xù)分配方式 特點(diǎn)： 為每個(gè)用戶程序分配連續(xù)的內(nèi)存空間 方法 單一連續(xù)分配 固定分區(qū)分配 動(dòng)態(tài)分區(qū)分配 可重定位分區(qū)分配9/19/2022424.2.1 單一連續(xù)分配 最簡(jiǎn)單的一種存儲(chǔ)分配管理方法只能用于單用戶、單任務(wù)的操作系統(tǒng)中把內(nèi)存分為兩部分系統(tǒng)區(qū)：提供給OS使用，內(nèi)存的低址部分用戶區(qū)：提供給用戶使用。 內(nèi)存系統(tǒng)區(qū)（OS）用戶區(qū)0100k進(jìn)程A進(jìn)程B9/19/2022434.2.2 固定分區(qū)分配 1. 劃分分區(qū)的方法 分區(qū)大小相等， 即使所有的內(nèi)存分區(qū)大小相等。 (2) 分區(qū)大小不等。 9/19/2022442. 內(nèi)存分配 內(nèi)存OS作業(yè)A作業(yè)B作業(yè)C作業(yè)D分區(qū)號(hào)大小(K)起址(

15、K)狀態(tài)11224已分配22436已分配33060未分配43590已分配540125未分配650165已分配7297215未分配0K24K90K36K60K165K125K215K進(jìn)程F(70K)已分配進(jìn)程G(70K)分區(qū)使用表內(nèi)存分配程序9/19/2022454.2.3 動(dòng)態(tài)分區(qū)分配 1. 分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu) 空閑分區(qū)表。 (2) 空閑分區(qū)鏈。 內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K0K35K111K77K91K151K136K226K分區(qū)號(hào)大小(K)始址(K)24235420916151368302263542912022630151369/19/2022462. 分區(qū)分配算

16、法 首次適應(yīng)算法FF (2) 最佳適應(yīng)算法(3) 最壞適應(yīng)算法 首次適應(yīng)法要求空閑區(qū)按首址遞增的次序組成空閑區(qū)表（鏈）。 內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K9/19/2022470K35K111K77K91K151K136K226K354291202263015136內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K9/19/2022480K35K111K77K91K151K136K226K429135201361522630首次適應(yīng)算法FF1）作業(yè)1請(qǐng)求內(nèi)存空間25K（分配）2）作業(yè)D完成（回收）思考：作業(yè)1完成（回收）作業(yè)117K6017120K12030K作業(yè)作業(yè)A作業(yè)2

17、0K9/19/202249（1）（2）30K作業(yè)A作業(yè)20K作業(yè)（3）作業(yè)30K作業(yè)作業(yè)A20K（4）作業(yè)30K作業(yè)A20K作業(yè)1003050020100305002010030500201003018020回收內(nèi)存的四種情況20050首址200大小50K大小50K大小50K首址450大小50K80回收作業(yè)A45070100分析優(yōu)點(diǎn)：優(yōu)先利用低地址空間，從而保證高址空間有較大的空閑區(qū)缺點(diǎn)：低址部分被不斷劃分，留下許多難以利用的、很小的空閑分區(qū)每次都從低址開始，查找開銷大9/19/202250返回最佳適應(yīng)法每次把能滿足作業(yè)要求，并且是最小的空閑分區(qū)分配給作業(yè)要求按空閑區(qū)大小從小到大的次序組成空閑

18、區(qū)表（鏈）。內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K9/19/2022510K35K111K77K91K151K136K226K136159120354230226內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K9/19/2022520K35K111K77K91K151K136K226K最佳適應(yīng)算法1）作業(yè)1請(qǐng)求內(nèi)存空間25K（分配）2）作業(yè)D完成（回收）思考：作業(yè)1完成（回收）作業(yè)15K90K136159120226303542251590分析優(yōu)點(diǎn)：在系統(tǒng)中若存在一個(gè)與申請(qǐng)分區(qū)大小相等的空閑區(qū)，必定會(huì)被選中，而首次適應(yīng)法則不一定。若系統(tǒng)中不存在與申請(qǐng)分區(qū)大小相等的空閑區(qū)，則選中的

19、空閑區(qū)是滿足要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。缺點(diǎn)：空閑區(qū)的大小一般與申請(qǐng)分區(qū)大小不相等，因此將其一分為二，留下來的空閑區(qū)總是最小的，以致無法使用。隨著時(shí)間的推移，系統(tǒng)中的小空閑區(qū)會(huì)越來越多，從而造成存儲(chǔ)區(qū)的大量浪費(fèi)。 9/19/202253返回最壞適應(yīng)法每次把能滿足作業(yè)要求，并且是最大的空閑分區(qū)分配給作業(yè)要求空閑區(qū)按大小遞減的順序組織空閑區(qū)表（或鏈）。 內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K9/19/2022540K35K111K77K91K151K136K226K354222630136152091內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K9/19/20225

20、50K35K111K77K91K151K136K226K最壞適應(yīng)算法1）作業(yè)1請(qǐng)求內(nèi)存空間25K（分配）2）作業(yè)D完成（回收）思考：作業(yè)1完成（回收）作業(yè)117K120K3542226309120136156017136120分析最壞適應(yīng)法看起來似乎有些荒唐，但在嚴(yán)密地考察后，還是有它的優(yōu)點(diǎn)：當(dāng)程序裝入內(nèi)存中最大的空閑區(qū)后，剩下的空閑區(qū)還可能相當(dāng)大，還能裝下較大的程序。另一方面分配時(shí)每次僅作一次查詢工作。9/19/202256三種策略比較上述三種放置策略各有利弊，到底哪種最好不能一概而論，而應(yīng)針對(duì)具體作業(yè)序列來分析。對(duì)于某一作業(yè)序列來說，某種算法能將該作業(yè)序列中所有作業(yè)安置完畢，那么我們說該算

21、法對(duì)這一作業(yè)序列是合適的。對(duì)于某一算法而言，如它不能立即滿足某一要求，而其它算法卻可以滿足此要求，則這一算法對(duì)該作業(yè)序列是不合適的。 9/19/202257舉例例1：有作業(yè)序列：作業(yè)A要求18K；作業(yè)B要求25K，作業(yè)C要求30K。畫出空閑區(qū)鏈并分析一下哪個(gè)算法最合適此序列？9/19/202258經(jīng)分析可知：最佳適應(yīng)法對(duì)這個(gè)作業(yè)序列是合適的，而其它兩種對(duì)該作業(yè)序列是不合適的。OS30作業(yè)20作業(yè)5作業(yè)46首次最佳最壞20501001201601652100203010020210465160160510020210463020210462030160520100練習(xí)有作業(yè)序列：作業(yè)A要求21K

22、；作業(yè)B要求30K，作業(yè)C要求25K。9/19/202259思考 用動(dòng)態(tài)分區(qū)分配方式管理主存時(shí),假定主存中按地址順序依次有5個(gè)空閑區(qū),空閑區(qū)的大小依次為32K,10K,5K,228K和100K,現(xiàn)有5個(gè)作業(yè)A,B,C,D,E.它們各需主存1K,10K,108K,28K和115K.若采用首次適應(yīng)算法能把這5個(gè)作業(yè)按順序全部裝入主存嗎?你認(rèn)為怎樣的次序裝入這5個(gè)作業(yè)可使主存的利用率最高?9/19/2022609/19/2022614.2.4 可重定位分區(qū)分配OS作業(yè)110作業(yè)230作業(yè)314作業(yè)426分區(qū)號(hào)起址大小35010512030716514923026 空閑分區(qū)表 205060120150

23、165179230作業(yè)A(40)80重定位寄存器作業(yè)120作業(yè)260作業(yè)3150作業(yè)4179306015512050110125176 9 216 409/19/2022624.2.5 對(duì)換(Swapping) 1. 對(duì)換的引入 所謂“對(duì)換”， 是指把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)，調(diào)入內(nèi)存。對(duì)換是提高內(nèi)存利用率的有效措施。 9/19/2022632. 對(duì)換空間的管理 為了能對(duì)對(duì)換區(qū)中的空閑盤塊進(jìn)行管理，在系統(tǒng)中應(yīng)配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，以記錄外存的使用情況。其形式與內(nèi)存在動(dòng)態(tài)分區(qū)分配方式中所

24、用數(shù)據(jù)結(jié)構(gòu)相似，即同樣可以用空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表中的每個(gè)表目中應(yīng)包含兩項(xiàng)， 即對(duì)換區(qū)的首址及其大小，它們的單位是盤塊號(hào)和盤塊數(shù)。 9/19/2022643. 進(jìn)程的換出與換入 (1) 進(jìn)程的換出。 每當(dāng)一進(jìn)程由于創(chuàng)建子進(jìn)程而需要更多的內(nèi)存空間，但又無足夠的內(nèi)存空間等情況發(fā)生時(shí)，系統(tǒng)應(yīng)將某進(jìn)程換出。 其過程是：系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程，然后啟動(dòng)盤塊，將該進(jìn)程的程序和數(shù)據(jù)傳送到磁盤的對(duì)換區(qū)上。若傳送過程未出現(xiàn)錯(cuò)誤，便可回收該進(jìn)程所占用的內(nèi)存空間，并對(duì)該進(jìn)程的進(jìn)程控制塊做相應(yīng)的修改。 9/19/202265 (2) 進(jìn)程的換入。 系統(tǒng)應(yīng)定時(shí)地查看所有進(jìn)程

25、的狀態(tài)，從中找出“就緒”狀態(tài)但已換出的進(jìn)程，將其中換出時(shí)間(換出到磁盤上)最久的進(jìn)程作為換入進(jìn)程，將之換入，直至已無可換入的進(jìn)程或無可換出的進(jìn)程為止。 9/19/2022664.3 基本分頁存儲(chǔ)管理方式 4.3.1 分頁存儲(chǔ)管理的基本方法 將程序的邏輯地址空間和物理內(nèi)存劃分為固定大小的頁或頁面(page or page frame)，程序加載時(shí)，分配其所需的所有頁，這些頁不必連續(xù)?；痉猪摯鎯?chǔ)管理方式9/19/2022679/19/2022684.3.1 分頁存儲(chǔ)管理的基本方法優(yōu)點(diǎn)：沒有外碎片，每個(gè)內(nèi)碎片不超過頁大小。一個(gè)程序不必連續(xù)存放。便于改變程序占用空間的大小。即隨著程序運(yùn)行而動(dòng)態(tài)生成的

26、數(shù)據(jù)增多，地址空間可相應(yīng)增長(zhǎng)。缺點(diǎn)：程序全部裝入內(nèi)存。9/19/2022694.3.1 分頁存儲(chǔ)管理的基本方法基本分頁存儲(chǔ)管理方式9/19/2022704.3.1 分頁存儲(chǔ)管理的基本方法所需表目：(1)頁表，每個(gè)進(jìn)程一個(gè) 塊號(hào) 頁號(hào):152216320123所需寄存器(1) 頁表寄存器：bl系統(tǒng)一個(gè)(2) 快表：系統(tǒng)一組： 頁號(hào)塊號(hào).fp頁表首址 頁表長(zhǎng)度9/19/202271進(jìn)程頁表4.3.1 分頁存儲(chǔ)管理的基本方法基本分頁存儲(chǔ)管理方式9/19/2022721. 頁面頁面和物理塊 分頁存儲(chǔ)管理是將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片稱為頁面或頁，并為各頁加以編號(hào)，從0開始。 同時(shí)把內(nèi)

27、存空間分成與頁面相同大小的若干個(gè)存儲(chǔ)塊，稱為塊或頁框。 在為進(jìn)程分配內(nèi)存時(shí)，以塊為單位將進(jìn)程的若干個(gè)頁分別裝入到多個(gè)可以不相鄰的物理塊中。 進(jìn)程的最后一頁經(jīng)常裝不滿而形成“頁內(nèi)碎片”。4.3.1 分頁存儲(chǔ)管理的基本方法基本分頁存儲(chǔ)管理方式9/19/202273頁面大小頁面大小應(yīng)選地適中，應(yīng)是2的冪，通常是512B8KB。9/19/2022742. 地址結(jié)構(gòu)位移量W頁號(hào)P31 12 11 0地址長(zhǎng)度32位:011位為位移量(頁內(nèi)地址)，即每頁的大小為4KB12 31位為頁號(hào)，地址空間最多允許有1M頁基本分頁存儲(chǔ)管理方式 若給定一個(gè)邏輯地址空間中的地址為A，頁面大小為L(zhǎng)，則: 頁號(hào)P=INTA/L

28、 頁內(nèi)地址d=A MOD L 例如：系統(tǒng)頁面大小為1KB，設(shè)A=2170B，則: P=2，d=1229/19/202275基本分頁存儲(chǔ)管理方式9/19/202276n頁5頁4頁3頁2頁1頁0頁用戶程序59483623120頁號(hào)塊號(hào)頁表內(nèi)存203456789101頁表的作用：基本分頁存儲(chǔ)管理方式4.3.1 地址變換機(jī)構(gòu)1. 基本的地址變換機(jī)構(gòu) 頁表可以由一組專門的寄存器來實(shí)現(xiàn)，一個(gè)頁表項(xiàng)用一個(gè)寄存器。但寄存器成本高，系統(tǒng)頁表可能很大，所以頁表大多常駐內(nèi)存。 在系統(tǒng)中只設(shè)置一個(gè)頁表寄存器PTR，在其中存放頁表在內(nèi)存中的始址和頁表的長(zhǎng)度。9/19/202277基本分頁存儲(chǔ)管理方式9/19/20227

29、8頁表長(zhǎng)度頁表始址頁表寄存器頁內(nèi)地址頁號(hào)(3)邏輯地址L物理地址b1塊號(hào)頁號(hào)01234+越界中斷頁表分頁系統(tǒng)的地址變換機(jī)構(gòu)：邏輯地址1023：1023/1K得頁號(hào)為0，頁內(nèi)地址為1023，查頁表找到對(duì)應(yīng)得物理塊為2，故物理地址為2*1K+1023=3071。邏輯地址2500：2500/1K得頁號(hào)為2，頁內(nèi)地址為452，查頁表找到對(duì)應(yīng)得物理塊為6，故物理地址為6*1K+452=6596。邏輯地址4500：4500/1K得頁號(hào)為4，頁內(nèi)地址為404，頁號(hào)大于頁表長(zhǎng)度，產(chǎn)生越界中斷 某分頁系統(tǒng)，主存容量為64K，頁面大小為1K，對(duì)一個(gè)4頁大的作業(yè)，其0、1、2、3頁分別被分配到主存的2、4、6、7塊

30、中。將十進(jìn)制的邏輯地址1023、2500、4500轉(zhuǎn)換為物理地址 9/19/202279頁式地址變換舉例頁表始址頁表長(zhǎng)度控制寄存器頁號(hào)頁面號(hào)有效地址02132821C4物理地址81C4基本分頁存儲(chǔ)管理方式例：設(shè)頁長(zhǎng)為1K，程序地址字長(zhǎng)為16位，用戶程序空間和頁表如圖，求用戶程序中Move指令中相對(duì)地址對(duì)應(yīng)的絕對(duì)地址。9/19/202280用戶程序Move r1,250001001K2K25003K-1頁表頁號(hào)塊號(hào)021427內(nèi)存01K2K3K4K5K6K7K8K9K10K-1課堂練習(xí)9/19/202281 假定某頁式管理系統(tǒng)，主存為64KB，分成16塊，塊號(hào)為0，1，2，15。設(shè)某作業(yè)有4頁，

31、其頁號(hào)為0，1，2，3，被分別裝入主存的2、4、1、6塊。試問：該作業(yè)的總長(zhǎng)度是多少字節(jié)？寫出該作業(yè)每一頁在主存中的起始地址；對(duì)多個(gè)邏輯地址0，100、1，50、2，0、3，60，試計(jì)算出相應(yīng)的內(nèi)存地址。課堂練習(xí)9/19/202282例：設(shè)虛地址為(357101)8 每一塊為128字節(jié)，求出頁號(hào)及頁內(nèi)地址（偏移量）12827(357101)8(011, 101, 111, 00 1, 000, 001)21 6 74101偏移為(101)8, 頁號(hào)為(1674)8塊號(hào)由頁表指定，偏移不變2. 具有快表的地址變換機(jī)構(gòu)CPU在每存取一個(gè)數(shù)據(jù)時(shí)，需要兩次訪問內(nèi)存：第一次：訪問頁表，找到指定頁的物理塊

32、號(hào)，將塊號(hào)與頁內(nèi)偏移量拼接形成物理地址。第二次：從第一次所得地址中獲得所需數(shù)據(jù)，或向此地址中寫入數(shù)據(jù)。處理速度降低！解決方法：在地址變換機(jī)構(gòu)中，增設(shè)一個(gè)具有并行查尋能力的特殊高速緩沖寄存器，稱為“聯(lián)想存儲(chǔ)器”或“快表”。9/19/202283基本分頁存儲(chǔ)管理方式9/19/202284頁表長(zhǎng)度頁表始址頁表寄存器頁內(nèi)地址頁號(hào)(3)邏輯地址Ldb物理地址+越界中斷b1塊號(hào)頁號(hào)頁表具有快表的分頁系統(tǒng)的地址變換機(jī)構(gòu)：b塊號(hào)頁號(hào)快表輸入寄存器9/19/202285假定快表的命中率為98%,快表的訪問時(shí)間為20ns,內(nèi)存的一次訪問時(shí)間為100ns,則有效訪問時(shí)間為:課堂練習(xí)EAT(Effective Acc

33、ess Time)=98%(20+100)+2%(20+200)=122ns基本分頁存儲(chǔ)管理方式4.3.2 兩級(jí)和多級(jí)頁表 現(xiàn)代計(jì)算機(jī)系統(tǒng)都支持非常大的邏輯地址空間(232264)，頁表就非常大，需占用較大的地址空間。例如：一個(gè)具有32位邏輯地址空間的分頁系統(tǒng)，規(guī)定頁面大小為4KB即212B，則每個(gè)進(jìn)程頁表的頁表項(xiàng)可達(dá)1M個(gè)，若每個(gè)頁表項(xiàng)占用4個(gè)字節(jié)，則每個(gè)進(jìn)程的頁表就要占據(jù)4MB的內(nèi)存空間，而且要求連續(xù)存放。9/19/202286基本分頁存儲(chǔ)管理方式1. 兩級(jí)頁表 9/19/202287例如： 32位邏輯地址空間，頁面大小為4KB(即12位)，若采用一級(jí)頁表機(jī)構(gòu)，應(yīng)有20位頁號(hào)，即頁表項(xiàng)應(yīng)有

34、1M個(gè)；在采用兩級(jí)頁表機(jī)構(gòu)時(shí)，再對(duì)頁表進(jìn)行分頁，使每頁包含210(即1024)個(gè)頁表項(xiàng)，最多允許有210個(gè)頁表分頁。即頁內(nèi)地址外層頁內(nèi)地址外層頁號(hào)dp2p1 31 22 21 12 11 0 基本分頁存儲(chǔ)管理方式9/19/202288012345671141151468內(nèi)存空間641第0頁頁表0121023115114第1頁頁表01210231468第n頁頁表0121023174210781011012n外部頁表兩級(jí)分頁結(jié)構(gòu)9/19/202289外部頁表寄存器外部頁表頁表db物理地址+dP2P1邏輯地址外部頁號(hào)外部頁內(nèi)地址頁內(nèi)地址具有兩級(jí)頁表的地址變換機(jī)構(gòu)： 上述方法用離散分配空間解決了大頁表

35、無需大片存儲(chǔ)空間的問題，但并未減少頁表所占的內(nèi)存空間。 解決方法是把當(dāng)前需要的一批頁表項(xiàng)調(diào)入內(nèi)存，以后再根據(jù)需要陸續(xù)調(diào)入。2. 多級(jí)頁表 兩級(jí)頁表對(duì)32位機(jī)器適用，64位呢？ 頁面大小為4KB即212B，還剩52位，按物理塊大小212位來劃分頁表，則剩余40位用于外層頁號(hào)，此時(shí)外層頁表可能有1024G個(gè)頁表項(xiàng)，要占用4096GB的連續(xù)存儲(chǔ)空間 解決方法：采用多級(jí)頁表，將外層頁表再進(jìn)行分頁。9/19/202290基本分頁存儲(chǔ)管理方式9/19/202291多級(jí)頁表地址映射基本分頁存儲(chǔ)管理方式9/19/2022924.4 基本分段存儲(chǔ)管理方式 4.4.1 分段存儲(chǔ)管理方式的引入 引入分段存儲(chǔ)管理方式

36、， 主要是為了滿足用戶和程序員的下述一系列需要： 1) 方便編程Load r1,A,100 Store r2,B,500 2) 信息共享 3) 信息保護(hù) 4) 動(dòng)態(tài)增長(zhǎng) 5) 動(dòng)態(tài)鏈接 基本分段存儲(chǔ)管理方式9/19/202293頁式管理是把內(nèi)存視為一維線性空間；而段式管理是把內(nèi)存視為二維空間，與進(jìn)程邏輯相一致。將程序的地址空間劃分為若干個(gè)段(segment)，程序加載時(shí)，分配其所需的所有段（內(nèi)存分區(qū)），這些段不必連續(xù)；物理內(nèi)存的管理采用動(dòng)態(tài)分區(qū)。需要硬件支持。4.4.2 分段系統(tǒng)的基本原理基本分段存儲(chǔ)管理方式 程序通過分段(segmentation)劃分為多個(gè)模塊，如代碼段、數(shù)據(jù)段、共享段?？?/p>

37、以分別編寫和編譯可以針對(duì)不同類型的段采取不同的保護(hù)可以按段為單位來進(jìn)行共享，包括通過動(dòng)態(tài)鏈接進(jìn)行代碼共享 優(yōu)點(diǎn)：沒有內(nèi)碎片，外碎片可以通過內(nèi)存緊縮來消除。便于改變進(jìn)程占用空間的大小。 缺點(diǎn)：進(jìn)程全部裝入內(nèi)存。9/19/2022944.4.2 分段系統(tǒng)的基本原理基本分段存儲(chǔ)管理方式9/19/202295段號(hào)段表9/19/202296 所需表目(1) 段表：每進(jìn)程一個(gè)段首址段長(zhǎng)度100k40k80k60k段號(hào) 0: 1: 2: 3:20k200k320k300k(2) 空閑表：系統(tǒng)一個(gè) array of (addr,size)基本分段存儲(chǔ)管理方式9/19/202297 所需寄存器(1) 段表寄存器

38、：bl段表首址 段表長(zhǎng)度系統(tǒng)一個(gè)(2) 快表：系統(tǒng)一組： 段號(hào) 段首址 段長(zhǎng)度.ls.b.基本分段存儲(chǔ)管理方式9/19/2022984.4.2 分段系統(tǒng)的基本原理 1. 分段 分段地址中的地址具有如下結(jié)構(gòu)： 段號(hào)段內(nèi)地址31 16 15 0基本分段存儲(chǔ)管理方式該地址結(jié)構(gòu)允許一個(gè)作業(yè)最長(zhǎng)有64K個(gè)段，每段的最大長(zhǎng)度為64KB。2. 段表 段表可以存放在寄存器中，但更多的是存放在內(nèi)存中。 段表可以實(shí)現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射。9/19/202299基本分段存儲(chǔ)管理方式9/19/2022100 利用段表實(shí)現(xiàn)地址映射 M (0)30KX(1)20KD(2)15KF(3)10K用戶作業(yè)作業(yè)空間內(nèi)存空間

39、M (0)30KX(1)20KD(2)15KF(3)10K040K80K120K150K30K40K20K80K15K120K10K150K段表 段長(zhǎng) 基址01239/19/2022101分段系統(tǒng)的地址變換過程 3. 地址變換機(jī)構(gòu) 段號(hào)S位移量W210K控制寄存器段表始址200K段表長(zhǎng)度4越界+30K40K20K80K15K120K10K150K段長(zhǎng) 基址+內(nèi)存040K80K120K150K越界9/19/2022102例: 段表如下：回答下列問題：1計(jì)算該作業(yè)訪問 0，432，1，10，2，500，3，400 時(shí)的絕對(duì)地址2總結(jié)段式存儲(chǔ)管理的地址轉(zhuǎn)換過程。段號(hào)段長(zhǎng)主存起始地址012346601

40、401005809602219330090123719599/19/2022103 段表如下：計(jì)算該作業(yè)訪問 0，216，1，120，2，210，3，456 時(shí)的絕對(duì)地址段號(hào)段長(zhǎng)主存起始地址01234660140100580960221933009012371959課堂練習(xí)9/19/2022104 注意：當(dāng)段表存放在內(nèi)存中時(shí)，每訪問一個(gè)數(shù)據(jù)，都需訪問兩次內(nèi)存，降低了計(jì)算機(jī)的速率。 解決方法：設(shè)置聯(lián)想寄存器，用于保存最近常用的段表項(xiàng)?；痉侄未鎯?chǔ)管理方式4. 分頁和分段的主要區(qū)別相似點(diǎn)：采用離散分配方式，通過地址映射機(jī)構(gòu)實(shí)現(xiàn)地址變換不同點(diǎn)：頁是信息的物理單位，分頁是為了滿足系統(tǒng)的需要；段是信息的

41、邏輯單位，含有一組意義相對(duì)完整的信息，分段是為了滿足用戶的需要。頁的大小固定且由系統(tǒng)確定，由系統(tǒng)把邏輯地址分為頁號(hào)和頁內(nèi)地址，由機(jī)器硬件實(shí)現(xiàn)；段的長(zhǎng)度不固定，取決于用戶程序，編譯程序?qū)υ闯绦蚓幾g時(shí)根據(jù)信息的性質(zhì)劃分。分頁的作業(yè)地址空間是一維的；分段的作業(yè)地址空間是二維的。9/19/2022105基本分段存儲(chǔ)管理方式9/19/20221064.4.3 信息共享 分頁系統(tǒng)中共享editor的示意圖（頁面大小為1K）兩個(gè)進(jìn)程共享文本編輯程序Editor，程序大小4K，另每個(gè)進(jìn)程自身的數(shù)據(jù)2K進(jìn)程1ed1ed2ed3ed4data1data2進(jìn)程2ed1ed2ed3ed4data1data2頁表202

42、122234041頁表202122235051主存0Ed120Ed221Ed322ed423data140data241data150data251遼東學(xué)院信息技術(shù)學(xué)院9/19/2022107分段系統(tǒng)中共享editor的示意圖進(jìn)程1editordata1進(jìn)程2editordata2段表段長(zhǎng)基址4K20K2K40K段表段長(zhǎng)基址4K20K2K50K主存020editor40data150data2分段系統(tǒng)的一個(gè)突出優(yōu)點(diǎn)是易于實(shí)現(xiàn)段的共享，允許若干個(gè)進(jìn)程共享一個(gè)或多個(gè)分段，且對(duì)段的保護(hù)十分簡(jiǎn)單易行。遼東學(xué)院信息技術(shù)學(xué)院9/19/2022108段的共享段長(zhǎng) 段首址 . l b . .段號(hào) si .P1

43、段表：段長(zhǎng) 段首址 . l b . .段號(hào) sj .P2段表：共享段.b:l內(nèi)存空間基本分段存儲(chǔ)管理方式遼東學(xué)院信息技術(shù)學(xué)院9/19/2022109段名 共享記數(shù) 段長(zhǎng) 段首址 其它 . vi 3 35k 125k ? .共享段表：進(jìn)程段表(n)共享段表(1)共享段(1)基本分段存儲(chǔ)管理方式9/19/2022110 段的保護(hù) (1) 段表的改進(jìn)：段長(zhǎng) 段首址 . . . l b 1 0 1段號(hào) s .訪問權(quán)限R W E . . . 段號(hào) 段長(zhǎng) 段首址 . . . s l b 1 0 1訪問權(quán)限R W E(2) 快表的改進(jìn)： . . .基本分段存儲(chǔ)管理方式9/19/20221114.4.4 段頁

44、式存儲(chǔ)管理 (segmentation with paging)段式優(yōu)于頁式便于共享和保護(hù)頁式優(yōu)于段式消除“外碎片”問題段頁式：結(jié)合二者優(yōu)點(diǎn)每個(gè)進(jìn)程包含若干段每個(gè)段包含若干頁基本分段存儲(chǔ)管理方式9/19/20221121. 基本原理 圖 4-20 作業(yè)地址空間和地址結(jié)構(gòu) 頁基本分段存儲(chǔ)管理方式9/19/2022113 基本原理 內(nèi)存空間劃分：(同頁式) 靜態(tài)等長(zhǎng)，2i, 稱為一頁。 物理地址=(塊號(hào),塊內(nèi)地址)=(f,w) 進(jìn)程空間劃分： 一個(gè)進(jìn)程若干個(gè)段 一個(gè)段若干個(gè)頁 邏輯地址=(段號(hào), 邏輯頁號(hào), 頁內(nèi)地址)=(s,p,w)基本分段存儲(chǔ)管理方式9/19/2022114利用段表和頁表實(shí)現(xiàn)地

45、址映射主程序段0123子程序段01數(shù)據(jù)段012段號(hào)狀態(tài)頁表大小頁表始址041001220023400段表頁號(hào)狀態(tài)存儲(chǔ)塊#020122223324頁表頁號(hào)狀態(tài)存儲(chǔ)塊#040142頁表頁號(hào)狀態(tài)存儲(chǔ)塊#050151252頁表主存020212223244041425051529/19/2022115段表長(zhǎng)度段表始址段表寄存器塊內(nèi)地址塊號(hào)b物理地址+段超長(zhǎng)2.段頁式系統(tǒng)的地址變換機(jī)構(gòu)：頁內(nèi)地址頁號(hào)P段號(hào)Sf1塊號(hào)頁號(hào)頁表0123+段表0123頁表長(zhǎng)度頁表始址9/19/20221164.5 虛擬存儲(chǔ)器的基本概念 4.5.1 引入1.常規(guī)存儲(chǔ)管理的特征：一次性（指全部裝入）、駐留性（指駐留在內(nèi)存不換出）2、

46、局部性原理時(shí)間局部性：如循環(huán)執(zhí)行空間局部性：如順序執(zhí)行。3、虛擬存貯器具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)系統(tǒng)。實(shí)質(zhì)：以時(shí)間換空間，但時(shí)間犧牲不大。虛擬大小由_決定。9/19/2022117引入虛擬存儲(chǔ)技術(shù)的好處大程序：可在較小的可用內(nèi)存中執(zhí)行較大的用戶程序；大的用戶空間：提供給用戶可用的虛擬內(nèi)存空間通常大于物理內(nèi)存(real memory)并發(fā)：可在內(nèi)存中容納更多程序并發(fā)執(zhí)行；易于開發(fā)：與覆蓋技術(shù)比較，不必影響編程時(shí)的程序結(jié)構(gòu)9/19/20221184.5.2 虛擬存儲(chǔ)器的實(shí)現(xiàn)方法 需要?jiǎng)討B(tài)重定位一、請(qǐng)求分頁系統(tǒng)以頁為單位轉(zhuǎn)換需硬件：（1）請(qǐng)求分頁的頁表機(jī)制（2

47、）缺頁中斷（3）地址變換機(jī)構(gòu)需實(shí)現(xiàn)請(qǐng)求分頁機(jī)制的軟件（置換軟件等）二、請(qǐng)求分段系統(tǒng)以段為單位轉(zhuǎn)換:（1）請(qǐng)求分段的段表結(jié)構(gòu)（2）缺段中斷（3）地址變換機(jī)構(gòu)需實(shí)現(xiàn)請(qǐng)求分段機(jī)制的軟件（置換軟件等）9/19/20221194.5.3 虛擬存儲(chǔ)器的特征 多次性：一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行對(duì)換性：允許在作業(yè)的運(yùn)行過程中進(jìn)行換進(jìn)、換出。虛擬性：能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。遼東學(xué)院信息技術(shù)學(xué)院9/19/20221204.6 請(qǐng)求分頁存儲(chǔ)管理方式 4.6.1 請(qǐng)求分頁中的硬件支持 1. 頁表機(jī)制 頁號(hào) 物理塊號(hào) 狀態(tài)位P 訪問字段A 修改位M外存地址 指示該頁是否已

48、調(diào)入內(nèi)存記錄本頁在一段時(shí)間內(nèi)被訪問的次數(shù)，或記錄本頁最近已有多長(zhǎng)時(shí)間未被訪問，供選擇換出頁面時(shí)參考該頁在調(diào)入內(nèi)存后是否被修改過，供置換頁面時(shí)參考指出該頁在外存上的地址，供調(diào)入該頁時(shí)參考9/19/20221212. 缺頁中斷機(jī)構(gòu) TO B指令copy A A: B:頁面6543219/19/20221223. 地址變換機(jī)構(gòu) 9/19/20221234.6.2 內(nèi)存分配策略和分配算法 1. 最小物理塊數(shù)的確定 進(jìn)程應(yīng)獲得的最少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式如： Mov A, B允許間接尋址：則至少要求3個(gè)物理塊。9/19/20221242. 物理塊的分配策略 內(nèi)存

49、分配策略：固定和可變分配策略置換策略：全局置換和局部置換 1) 固定分配局部置換(Fixed Allocation, Local Replacement)缺點(diǎn)：難以確定固定分配的頁數(shù)(少：置換率高/多：浪費(fèi)) 2) 可變分配全局置換(Variable Allocation, Global Replacement) 3) 可變分配局部置換(Variable Allocation, Local Replacement）根據(jù)進(jìn)程的缺頁率進(jìn)行頁面數(shù)調(diào)整，進(jìn)程之間相互不會(huì)影響9/19/20221253. 物理塊分配算法 1) 平均分配算法 將系統(tǒng)中所有可供分配的物理塊，平均分配給各個(gè)進(jìn)程。缺點(diǎn)：未考慮各

50、進(jìn)程本身的大小。9/19/20221262) 按比例分配算法 這是根據(jù)進(jìn)程的大小按比例分配物理塊的算法。如果系統(tǒng)中共有n個(gè)進(jìn)程，每個(gè)進(jìn)程的頁面數(shù)為Si，則系統(tǒng)中各進(jìn)程頁面數(shù)的總和為： 又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個(gè)進(jìn)程所能分到的物理塊數(shù)為bi，將有：b應(yīng)該取整，它必須大于最小物理塊數(shù)。 9/19/20221273) 考慮優(yōu)先權(quán)的分配算法 在實(shí)際應(yīng)用中，為了照顧重要的、急迫的作業(yè)盡快完成，應(yīng)為它分配較多的內(nèi)存空間。方法：一部分按比例分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。9/19/20221284.6.3 調(diào)頁策略 1. 何時(shí)調(diào)入頁面 （1）

51、請(qǐng)調(diào)(demand paging) upon page fault, 發(fā)生缺頁中斷時(shí)調(diào)入（較費(fèi)系統(tǒng)開銷） （2） 預(yù)調(diào)(prepaging) before page fault, 將要訪問時(shí)調(diào)入(根據(jù)程序順序行為， 不一定準(zhǔn)）（根據(jù)空間局部性，目前：成功率50）預(yù)調(diào)必須輔以請(qǐng)調(diào)。9/19/20221292. 從何處調(diào)入頁面 外存：文件區(qū)、對(duì)換區(qū)系統(tǒng)擁有足夠的對(duì)換區(qū)空間：系統(tǒng)缺少足夠的對(duì)換區(qū)空間：UNIX方式：9/19/2022130缺頁中斷保留CPU環(huán)境缺頁中斷處理訪問內(nèi)存數(shù)據(jù)3. 頁面調(diào)入過程小結(jié)1、基本思想在進(jìn)程開始運(yùn)行之前，不是裝入全部頁面，而是裝入幾個(gè)或零個(gè)頁面，之后根據(jù)進(jìn)程運(yùn)行的需要

52、，動(dòng)態(tài)裝入其它頁面；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時(shí)，則根據(jù)某種算法淘汰某個(gè)頁面，以便裝入新的頁面9/19/20221319/19/2022132XXXX7X5XXX34061260K-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虛地址空間物理地址空間 虛頁頁框2、頁表表項(xiàng)頁號(hào)、物理塊號(hào)、狀態(tài)位、外存地址、訪問位、修

53、改位狀態(tài)位：表示該頁是在內(nèi)存還是在外存訪問位：根據(jù)訪問位來決定淘汰哪頁（由不同的算法決定）修改位：查看此頁是否在內(nèi)存中被修改過9/19/2022133頁號(hào)物理塊號(hào)狀態(tài)位外存地址訪問位修改位9/19/2022134151413121110 9 8 7 6 5 4 3 2 10000000000000000111100001011000000000000011110010001110100110101 00010000000000100011000000000100110在/不在內(nèi)存頁表虛地址8196物理地址245803、缺頁中斷（Page Fault）處理在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的

54、頁不在內(nèi)存，則產(chǎn)生缺頁中斷。操作系統(tǒng)接到此中斷信號(hào)后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給出的外存地址，準(zhǔn)備將該頁調(diào)入內(nèi)存此時(shí)應(yīng)將缺頁的進(jìn)程掛起（調(diào)頁完成喚醒）9/19/2022135如果內(nèi)存中有空閑塊，則分配一個(gè)塊，將要調(diào)入的頁裝入該塊，并修改頁表中相應(yīng)頁表項(xiàng)目的狀態(tài)位及相應(yīng)的內(nèi)存塊號(hào)若此時(shí)內(nèi)存中沒有空閑塊，則要淘汰某頁（若被淘汰頁在內(nèi)存期間被修改過，則要將其寫回外存）9/19/2022136思考缺頁中斷同一般中斷的區(qū)別？9/19/2022137缺頁中斷同一般中斷都是中斷，相同點(diǎn)是：保護(hù)現(xiàn)場(chǎng) 中斷處理 恢復(fù)現(xiàn)場(chǎng)不同點(diǎn)：一般中斷是一條指令完成后接受和處理中斷，缺頁中斷是一條指令執(zhí)行過程中產(chǎn)生和

55、處理中斷一條指令執(zhí)行時(shí)可能產(chǎn)生多個(gè)缺頁中斷。如指令可能訪問多個(gè)內(nèi)存地址，這些地址在不同的頁中。9/19/20221389/19/20221394.7 頁面置換算法 4.7.1 最佳置換算法和先進(jìn)先出置換算法 1. 最佳(Optimal)置換算法 最佳置換算法是由Belady于1966年提出的一種理論上的算法。 其所選擇的被淘汰頁面，將是以后永不使用的， 或許是在最長(zhǎng)(未來)時(shí)間內(nèi)不再被訪問的頁面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。 用于：頁淘汰、段淘汰、快表淘汰。9/19/2022140 假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊， 并考慮有以下的頁面號(hào)引用串：7，0，1，2，0，3，0，4

56、，2，3，0，3，2，1，2，0，1，7，0，1 7F7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用序列缺頁標(biāo)志70F701F201F201203F203243F243243203F203203201F201201201701F701701缺頁9次，總訪問次數(shù)20次，缺頁率9/2045頁面置換6次，置換率6/20=30%最佳置換算法（OPT）例9/19/20221412. 先進(jìn)先出(FIFO)頁面置換算法 該算法的實(shí)質(zhì)是：總是選擇作業(yè)中在主存駐留時(shí)間最長(zhǎng)（即最老）的一頁淘汰。即先進(jìn)入主存的頁先退出主存。其理由是，最早調(diào)入主存的頁，其不再被使用的可能性比最近調(diào)

57、入主存的頁要大。9/19/20221427F7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用序列缺頁標(biāo)志70F701F201F201231F230F430F420F423F023F023023013F012F012012712F702F701F缺頁15次，總訪問次數(shù)20次，缺頁率15/2075頁面置換12次，置換率12/20=60%先進(jìn)先出置換算法（FIFO）例9/19/2022143有一虛擬存儲(chǔ)系統(tǒng)，采用先進(jìn)先出的頁面淘汰算法。在內(nèi)存中為每個(gè)進(jìn)程分配3塊。進(jìn)程執(zhí)行時(shí)使用頁號(hào)的順序?yàn)?4 3 2 1 4 3 5 4 3 2 1 5(1)該進(jìn)程運(yùn)行時(shí)總共出現(xiàn)幾次

58、缺頁（假設(shè)進(jìn)程運(yùn)行前所有頁面均不在內(nèi)存中）。(2)若每個(gè)進(jìn)程在內(nèi)存有4塊，又將產(chǎn)生幾次缺頁。(3)如何解釋所出現(xiàn)的現(xiàn)象。例 9/19/20221444 3 2 1 4 3 5 4 3 2 1 5m=3413214214354352352143432共缺頁中斷9次9/19/2022145m=3時(shí)，缺頁中斷9次m=4時(shí)，缺頁中斷10次FIFO頁面淘汰算法會(huì)產(chǎn)生異常現(xiàn)象（Belady現(xiàn)象），即：當(dāng)分配給進(jìn)程的物理頁面數(shù)增加時(shí)，缺頁次數(shù)反而增加9/19/2022146 在虛存中，頁面在內(nèi)存與外存之間頻繁調(diào)度，以至于調(diào)度頁面所需時(shí)間比進(jìn)程實(shí)際運(yùn)行的時(shí)間還多，此時(shí)系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰。這種現(xiàn)

59、象稱為顛簸或抖動(dòng)原因：頁面淘汰算法不合理分配給進(jìn)程的物理頁面數(shù)太少顛簸（抖動(dòng)）9/19/20221474.7.2 最近最久未使用(LRU)置換算法 1. LRU(Least Recently Used)置換算法的描述 該算法的基本思想是:利用局部性原理，根據(jù)一個(gè)作業(yè)在執(zhí)行過程中過去的頁訪問的蹤跡來推測(cè)未來的行為。它認(rèn)為過去一段時(shí)間里不曾被訪問過的頁，在最近的將來可能也不會(huì)再被訪問。所以這種算法的實(shí)質(zhì)是：當(dāng)需要置換一頁時(shí)，選擇在最近一段時(shí)間內(nèi)最久不用的頁予以淘汰。9/19/2022148m=44 3 2 1 4 3 5 4 3 2 1 544321532154215431543214324343

60、21532共缺頁中斷10次9/19/20221497F7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用序列缺頁標(biāo)志70F701F201F201203F203403F402F432F032F032032132F132102F102107F107107缺頁12次，總訪問次數(shù)20次，缺頁率12/2060頁面置換9次，置換率9/20=45%最近最久未使用置換算法（LRU）例9/19/20221502. LRU置換算法的硬件支持 1) 寄存器 為了記錄某進(jìn)程在內(nèi)存中各頁的使用情況，須為每個(gè)在內(nèi)存中的頁面配置一個(gè)移位寄存器，可表示為 R=Rn-1Rn-2Rn-3 R2R1