操作系統(tǒng)課件第7章主存管理

第7章主存管理主存管理主存管理概述主存管理的功能分區(qū)存儲管理頁式存儲管理段式及段頁式存儲管理1主存管理——主要內(nèi)容主存管理——主存管理概述計算機存儲系統(tǒng)的發(fā)展主存管理——主存管理概述主存管理——主存管理概述1956年，第一臺硬盤，IBM350，5MB1973年，溫徹斯特技術(shù)，IBM3340，60MB1979年，薄膜磁頭，IBM3370，571MB1991年，MR(磁阻)磁頭，IBM0663-E12，GB1997年，GMR巨磁阻效應(yīng)磁頭，2007年，垂直存儲技術(shù)，TB主存管理——主存管理概述主存管理——主存管理概述主存管理——主存管理概述主存管理——主存管理概述主存管理——主存管理概述主存管理——主存管理概述主存管理——主存管理概述RAM（隨機存取存儲器）RAM-randomaccessmemory隨機存儲器靜態(tài)存儲單元（SRAM）速度快、使用簡單、不需刷新、靜態(tài)功耗極低；常用作Cache動態(tài)存儲單元（DRAM）定期進行刷新，集成度遠高于SRAM、功耗低，價格也低SDRAM:SynchronousDynamicRandomAccessMemory，同步動態(tài)隨機存儲器，同步是指Memory工作需要同步時鐘SDRAM從發(fā)展到現(xiàn)在已經(jīng)經(jīng)歷了四代，分別是：第一代SDRSDRAM，第二代DDRSDRAM，第三代DDR2SDRAM，第四代DDR3SDRAM.(顯卡上的DDR已經(jīng)發(fā)展到DDR5)ROM（Read-OnlyMemory）只讀存儲器可編程只讀存儲器（PROM）、可擦可編程只讀存儲器（EPROM）和電可擦可編程只讀存儲器（EEPROM）閃存（FlashMemory）是一種長壽命的非易失性（在斷電情況下仍能保持所存儲的數(shù)據(jù)信息）的存儲器，數(shù)據(jù)刪除不是以單個的字節(jié)為單位而是以固定的區(qū)塊為單位，區(qū)塊大小一般為256KB到20MB。閃存是電子可擦除只讀存儲器（EEPROM）的變種閃存卡（FlashCard）是利用閃存（FlashMemory）技術(shù)達到存儲電子信息的存儲器主存管理——主存管理概述存儲器的功能是保存數(shù)據(jù)，存儲器的發(fā)展方向是高速讀寫、大容量和小體積。讀寫速度越快，成本越高，容量就越小；讀取速度越慢，成本越低，容量就越大；合理的存儲結(jié)構(gòu)要依據(jù)訪問速度的匹配關(guān)系、容量要求和價格。主存管理——主存管理概述計算機存儲系統(tǒng)的層次結(jié)構(gòu)快速緩存：數(shù)據(jù)Cache指令Cache內(nèi)存：DRAM,SDRAM,DDRAM等；外存：硬盤、光盤、flash、軟盤、磁帶等；主存管理——主存管理概述這一章研究的是主存(內(nèi)存)的管理地址總線數(shù)據(jù)總線控制總線主存管理——主存管理概述推薦看看“每個程序員都應(yīng)該了解的內(nèi)存知識”（英文，在有部分翻譯）第1節(jié):RAM第2節(jié):CPU的高速緩存第3節(jié):虛擬內(nèi)存第4節(jié):NUMA系統(tǒng)（非統(tǒng)一內(nèi)存訪問架構(gòu)）第5節(jié):程序員可以做什么-高速緩存的優(yōu)化第6節(jié):程序員可以做什么-多線程的優(yōu)化第7節(jié):內(nèi)存性能工具第8節(jié):未來的技術(shù)第9節(jié):附錄與參考書目主存管理——主存管理概述 主存儲器（內(nèi)存）與中央處理器一樣是計算機系統(tǒng)的重要資源（空間和時間）。任何程序的執(zhí)行最終都要從內(nèi)存中存取指令和數(shù)據(jù)。因為多個進程對內(nèi)存的共享，所以操作系統(tǒng)需要研究內(nèi)存的管理。主要內(nèi)容包括： 1內(nèi)存的分配 2內(nèi)存的保護 3內(nèi)存的擴充 4內(nèi)存地址映射51.幾個概念

(1)物理地址(實地址)

物理地址是計算機主存單元的真實地址，又稱為實地址。

(2)主存空間

物理地址的集合所對應(yīng)的空間組成了主存空間。

(3)邏輯地址

用戶的程序地址(指令地址或操作數(shù)地址)均為邏輯地址。

(4)程序地址空間用戶程序所有的邏輯地址集合對應(yīng)的空間。主存管理——主存管理功能主存管理——主存管理概述程序的內(nèi)存組織(1)一維地址結(jié)構(gòu)程序和數(shù)據(jù)經(jīng)編譯、連接后成一個連續(xù)的地址空間；確定邏輯地址空間中的指令地址或操作數(shù)地址只需要一個信息。程序地址空間一維地址結(jié)構(gòu)01

n-1...示例：readelf-ahello>hello.elf.txt4主存管理——主存管理概述

(2)二維地址結(jié)構(gòu)一個程序由若干個分段組成，每個分段是一個連續(xù)的地址區(qū)；確定邏輯地址空間中的指令地址或操作數(shù)地址需要兩個信息，一是該信息所在的分段，另一個是該信息在段內(nèi)的偏移量。code_addr4KB-10代碼分段data_addr3KB-10數(shù)據(jù)分段stack_addr2KB-10棧段11.........程序地址空間——二維地址結(jié)構(gòu)4主存管理——主存管理概述

(2)二維地址結(jié)構(gòu)示例：x86實模式下的內(nèi)存管理6程序地址空間與主存空間主存管理——主存管理功能主存空間01m-1程序1地址空間01n-1程序i地址空間01k-1

...

...程序地址空間與主存空間示意圖主存管理功能主存管理——主存管理功能7主存管理——主存管理功能2.主存管理功能地址映射（邏輯地址-->物理主存）主存分配主存保護主存擴充

83.地址映射(1)為什么要進行地址映射

作業(yè)的相應(yīng)進程在處理機上運行時，所要訪問的指令和數(shù)據(jù)的實際地址和地址空間中的地址是不同的。

(2)什么是地址映射

將程序地址空間中使用的邏輯地址變換成主存中的物理地址的過程，稱為地址映射。程序地址空間裝入主存主存管理——主存管理功能movr1,[500]1230100500599程序地址空間movr1,[500]12301000110015001599256k-1存儲空間9②

在程序裝入時確定地址映射關(guān)系在程序裝入過程中隨即進行的地址變換方式稱為靜態(tài)地址映射。movr1,[500]movr1,[500+m]01005005990mm+100256k-1程序地址空間存儲空間m+500重定位裝入程序123123(3)地址映射的時機和類別①編程或編譯時確定地址映射關(guān)系在程序編寫或程序編譯時確定虛、實地址之間的對應(yīng)關(guān)系，結(jié)果是一個不能浮動的程序模塊。靜態(tài)地址重定位示意圖主存管理——主存管理功能10③在程序運行時確定地址映射關(guān)系

在程序執(zhí)行期間，隨著每條指令和數(shù)據(jù)的訪問自動地連續(xù)地進行地址映射，這種地址變換方式稱為動態(tài)地址映射。重定位寄存器

1000

500邏輯地址+0

movr1,[500]

1000256k-1存儲空間110015001600123movr1,[500]0100500599程序地址空間123動態(tài)地址重定位示意圖主存管理——主存管理功能

動態(tài)地址映射技術(shù)能滿足以下目標(biāo)：具有給一個用戶程序任意分配內(nèi)存區(qū)的能力;改變內(nèi)存地址時，不需要修改用戶程序;具有重新分配的能力;靜態(tài)映射與動態(tài)映射的區(qū)別靜態(tài)地址映射動態(tài)地址映射在作業(yè)裝入過程中進行地址映射在程序執(zhí)行期間進行地址映射需軟件重定位裝入程序需硬件地址變換機構(gòu)重定位寄存器需花費較多CPU時間地址變換快不靈活靈活31存儲保護

1.什么是存儲保護 在多用戶環(huán)境中，主存儲器按區(qū)分配給各用戶程序使用。為了互不影響，必須由硬件（軟件配合）保證每道程序只能在給定的存儲區(qū)域內(nèi)活動，這種措施叫做存儲保護。3216存儲保護方法①上下界防護

例：程序大小為4KB，主存首址為20KB。

movr1,[500]123020KB256KB-1存儲空間24KB下界寄存器

20KB上界寄存器

24KB如何設(shè)置上下界寄存器內(nèi)容？如何判斷是否越界？若20KB≤D＜24KB

允許訪問；否則發(fā)生越界中斷界限寄存器保護示意圖主存管理——主存管理功能17②基地址、限長防護

例：程序大小為4KB，主存首址為20KB。如何設(shè)置基址、限長寄存器內(nèi)容？如何判斷是否越界？若邏輯地址＜4KB

允許訪問；否則發(fā)生越界中斷

movr1,[500]123020KB256KB-1存儲空間24KB基址寄存器

20KB限長寄存器

4KB界限寄存器保護示意圖主存管理——主存管理功能主存擴充1.問題的提出 主存容量始終顯得十分緊張 如何使用戶使用計算機不受主存容量的限制？2.解決問題的思路 部分裝入，部分對換。35裝入部分程序地址空間，它還能正常執(zhí)行嗎？（效率）回答是肯定的，1968年P(guān).Denning研究了程序執(zhí)行時的局部性原理。程序的局部性原理指程序在執(zhí)行過程中的一個較短時間內(nèi)，所執(zhí)行的指令地址或操作數(shù)地址分別局限于一定的存儲區(qū)域中。36第一，程序中只有少量分支和過程調(diào)用，大都是順序執(zhí)行的指令。第二，程序包含若干循環(huán)，是由相對較少的指令組成，在循環(huán)過程中，計算被限制在程序中很小的相鄰部分中。第三，很少出現(xiàn)連續(xù)的過程調(diào)用，相反，程序中過程調(diào)用的深度限制在小范圍內(nèi)，一段時間內(nèi)，指令引用被局限在很少幾個過程中。第四，對于連續(xù)訪問數(shù)組之類的數(shù)據(jù)結(jié)構(gòu)，往往是對存儲區(qū)域中相鄰位置的數(shù)據(jù)的操作。第五，程序中有些部分是彼此互斥的，不是每次運行時都用到的，如出錯處理程序。實現(xiàn)方法程序的全部代碼和數(shù)據(jù)存放在輔存中；將程序當(dāng)前執(zhí)行所涉及的那部分程序代碼放入主存中；程序執(zhí)行時，當(dāng)所需信息不在主存，由操作系統(tǒng)和硬件相配合來完成主存從輔存中調(diào)入信息，程序繼續(xù)執(zhí)行。存儲管理機制的發(fā)展內(nèi)存管理的目標(biāo)和內(nèi)容：1、內(nèi)存分配（動態(tài)分配）2、內(nèi)存映射（動態(tài)映射）3、內(nèi)存保護4、內(nèi)存擴充8086：實地址內(nèi)存管理模式（dos）80386～現(xiàn)在：虛擬地址模式（window，linux）39虛擬存儲器的概念由操作系統(tǒng)和硬件相配合來完成主存的映射、保護、和輔存之間的信息動態(tài)交換。這樣的計算機系統(tǒng)好像為用戶提供了一個其存儲容量比實際主存大得多的存儲器，這個存儲器稱為虛擬存儲器。虛擬存儲器的容量與主存大小無直接關(guān)系，只受限于計算機的體系結(jié)構(gòu)。虛擬存儲器的核心邏輯地址與物理地址分開（完全隔離）1.物理地址（實地址） 物理地址是計算機主存單元的真實地址，又稱實地址。2.邏輯地址（虛地址） 用戶的程序地址（指令地址或操作數(shù)地址）均為邏輯地址。虛擬地址空間與物理地址空間分開（完全隔離）1.物理地址空間（實地址空間） 物理地址的集合所對應(yīng)的空間組成了主存空間。

編址不一定從0開始。2.邏輯地址空間（虛擬地址空間） 用戶程序所有的邏輯地址集合對應(yīng)的空間。

編址總是從0開始。提供地址變換機構(gòu)(地址映射)虛擬存儲器的概念圖虛擬地址空間處理器虛地址存儲管理部件實地址主存輔存物理地址空間物理內(nèi)存空間01m-1作業(yè)1邏輯地址空間01n-1……43作業(yè)i邏輯地址空間01n-1作業(yè)1虛擬地址空間01n-1作業(yè)i虛擬地址空間01n-1……主存分配分區(qū)存儲管理頁式存儲管理段式和段頁式存儲管理44分區(qū)存儲管理一種最簡單直接的存儲管理方式，適用于多道程序系統(tǒng)，分時系統(tǒng)，也適用于虛擬地址空間分配。原理：把內(nèi)存分為一些大小不等的區(qū)域，每個作業(yè)進程占用一個或幾個區(qū)域；操作系統(tǒng)占用其中一個分區(qū)域。允許多個進程共存。問題：存在碎片45動態(tài)分區(qū)的分配過程

20KB

0

os

作業(yè)1

作業(yè)2

作業(yè)3

作業(yè)4

52KB66KB130KB230KB256KB主存20KB

0

os

作業(yè)1

作業(yè)2

作業(yè)3

52KB66KB130KB256KB主存20KB

0

os

作業(yè)1

52KB256KB主存

0

os

256KB主存20KB20KB

0

os

作業(yè)1

作業(yè)2

52KB66KB256KB主存作業(yè)1申請

32KB作業(yè)2申請

14KB作業(yè)3申請

64KB作業(yè)4申請

100KB作業(yè)5申請

50KB

動態(tài)分區(qū)的回收過程

20KB

0

os

作業(yè)1

作業(yè)2

作業(yè)3

作業(yè)4

52KB66KB130KB230KB256KB主存20KB

0

os

作業(yè)1

作業(yè)3

作業(yè)4

52KB66KB130KB230KB256KB主存作業(yè)2完成作業(yè)4完成20KB

0

os

作業(yè)1

作業(yè)3

52KB66KB130KB230KB256KB主存21分配數(shù)據(jù)結(jié)構(gòu)①

主存資源信息塊(M_RIB)②分區(qū)描述器(PD)

主存管理——分區(qū)存儲管理

等待隊列頭指針空閑區(qū)隊列頭指針主存分配程序入口地址M_RIBflag：為0——空閑區(qū)為1——已分配區(qū)size：分區(qū)大小(=n+3),n為分區(qū)可用字節(jié)數(shù)next：空閑區(qū)——自由主存隊列中的勾鏈字已分配區(qū)——此項為零

分配標(biāo)志flag

大小size

指針nextPD22③空閑區(qū)隊列結(jié)構(gòu)20KB

0

52KB66KB130KB230KB256KB主存os程序1程序3程序452KBM_RIB

空閑區(qū)隊列230KB014KB026KB^動態(tài)分區(qū)的空閑區(qū)隊列結(jié)構(gòu)主存管理——分區(qū)存儲管理分區(qū)的分配與回收1.分區(qū)分配用戶請求分配一個主存塊分區(qū)分配程序在自由主存隊列中找一個滿足用戶需要的空閑塊；若找到，以空閑塊與請求的主存塊大小之間的關(guān)系（剩余大于門限值則分割，否則全部分配）進行相應(yīng)的處理，并返回所分配區(qū)域的首址；否則，告之不能滿足要求。50分區(qū)的分配與回收（續(xù)）2.分區(qū)回收回收主存塊的四種情況

r上鄰空閑區(qū)rf1作業(yè)2

r上下鄰空閑區(qū)rf1f2

r上下鄰已分配區(qū)r作業(yè)1作業(yè)2

r下鄰空閑區(qū)r作業(yè)1f251回收分區(qū)r（上鄰空閑區(qū)）r與f1合并成為一個大的空閑區(qū)f1

回收分區(qū)r（下鄰空閑區(qū)）r與f2合并成為一個大的空閑區(qū)f2

rf1作業(yè)2

f1作業(yè)2

r作業(yè)1f2

作業(yè)1f252回收分區(qū)r（上、下鄰空閑區(qū)）r與f1、f2合并成為一個大的空閑區(qū)f1

回收分區(qū)r（上、下鄰已分配區(qū)）r成為一個新的空閑區(qū)f

rf1f2

f1

r作業(yè)1作業(yè)2

f作業(yè)1作業(yè)2放置策略什么是放置策略 選擇空閑區(qū)的策略，稱為放置策略。 常用的放置策略——首次匹配（首次適應(yīng)算法）最佳匹配（最佳適應(yīng)算法）最壞匹配（最壞適應(yīng)算法）541.首次適應(yīng)算法

首次適應(yīng)算法是將輸入的作業(yè)放置到主存里第一個足夠裝入它的可利用的空閑區(qū)中。作業(yè)A18KB

os在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB55首次適應(yīng)算法的特點自由主存隊列結(jié)構(gòu)——空閑區(qū)地址由低到高排序。盡可能地利用內(nèi)存低端的空閑區(qū)，而盡量保存高端的空閑區(qū)。該算法的分配和釋放的時間性能較好，較大的空閑分區(qū)可以被保留在內(nèi)存高端。但隨著低端分區(qū)不斷劃分而產(chǎn)生較多小分區(qū)，每次分配時查找時間開銷會增大。562.最佳適應(yīng)算法

最佳適應(yīng)算法是將輸入的作業(yè)放置到主存中與它所需大小最接近的空閑區(qū)中。作業(yè)A18KB

os在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1最佳適應(yīng)算法的特點自由主存隊列結(jié)構(gòu)——空閑區(qū)大小由小到大排序。盡可能地利用存儲器中小的空閑區(qū)，而盡量保存大的空閑區(qū)。從個別來看，碎片較小，但從整體來看，會形成較多碎片。58

3.最壞適應(yīng)算法 最壞適應(yīng)算法是將輸入的作業(yè)放置到主存中主存中最不適合它的空閑區(qū)中。作業(yè)A18KB

os在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-159最壞適應(yīng)算法的特點自由主存隊列結(jié)構(gòu)——空閑區(qū)大小由大到小排序盡可能地利用存儲器中大的空閑區(qū)基本不留下小空閑分區(qū)，但較大的空閑分區(qū)不被保留。6029三種放置策略的討論①

題例

程序A要求18KB；

程序B要求25KB；

程序C要求30KB。分別用首次適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法來處理程序序列，看哪種算法合適。(畫出初始時的空閑隊列結(jié)構(gòu))

主存管理——分區(qū)存儲管理

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB主存os初始時主存分布示意圖②首次適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法的隊列結(jié)構(gòu)

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB主存os(a)首次適應(yīng)算法的空閑區(qū)隊列

20KB

030KB100KB

020KB160KB

05KB210KB

046KB^

(b)最佳適應(yīng)算法的空閑區(qū)隊列160KB

05KB100KB

020KB20KB

030KB210KB

046KB^

(c)最壞適應(yīng)算法的空閑區(qū)隊列210KB

046KB20KB

030KB100KB

020KB160KB

05KB^

主存分布示意圖主存管理——分區(qū)存儲管理31ⅰ首次適應(yīng)算法

程序A要求18KB

程序B要求25KB

程序C要求30KB

首次適應(yīng)算法對該作業(yè)序列是不合適的

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB主存os(a)首次適應(yīng)算法的空閑區(qū)隊列

20KB

030KB100KB

020KB160KB

05KB210KB

046KB^

主存分布示意圖主存管理——分區(qū)存儲管理32ⅱ最佳適應(yīng)算法

程序A要求18KB

程序B要求25KB

程序C要求30KB

最佳適應(yīng)算法對該程序序列是合適的

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB主存os(b)最佳適應(yīng)算法的空閑區(qū)隊列160KB

05KB100KB

020KB20KB

030KB210KB

046KB^

主存分布示意圖主存管理——分區(qū)存儲管理33ⅲ最壞適應(yīng)算法

程序A要求18KB

程序B要求25KB

程序C要求30KB

最壞適應(yīng)算法對該程序序列是不合適的

os在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB主存(c)最壞適應(yīng)算法的空閑區(qū)隊列210KB

046KB20KB

030KB100KB

020KB160KB

05KB^

主存分布示意圖主存管理——分區(qū)存儲管理29習(xí)題6-11：主存中有兩個空閑區(qū)，現(xiàn)有如下作業(yè)序列：

程序1要求50KB；

程序2要求60KB；

程序3要求70KB。如果用首次適應(yīng)算法和最佳適應(yīng)算法來處理這個作業(yè)序列，問：哪一種算法可以分配的下？簡要說明分配過程。主存管理——分區(qū)存儲管理

78KB0KB150KB120KB300KB主存碎片問題及拼接技術(shù)1.什么是碎片問題 在已分配區(qū)之間存在著的一些沒有被充分利用的小空閑區(qū)。

2.拼接技術(shù)所謂拼接技術(shù)是指移動存儲器中某些已分配區(qū)中的信息，使本來分散的空閑區(qū)連成一個大的空閑區(qū)。如何解決碎片問題？

020KBos

52KB58KB130KB250KB256KB主存138KB作業(yè)１作業(yè)２作業(yè)３拼接技術(shù)圖示

20KB0OS

52KB124KB236KB256KB主存作業(yè)1作業(yè)2作業(yè)320KBOS

52KB58KB130KB250KB256KB主存138KB作業(yè)１作業(yè)２作業(yè)３680(3)拼接技術(shù)缺點移動分區(qū)花費CPU時間拼接時，停止了所有工作，影響性能需要重新定義內(nèi)存中的作業(yè)二、伙伴算法把內(nèi)存分為大小相等的頁，每次只能分配2n個的內(nèi)存單元。(n=0,1,...)滿足伙伴的的要求如下：1）兩個塊具有相同的大小，記作2b。2）它們的物理地址是連續(xù)的。3）第一塊的第一個頁的物理地址是2b的倍數(shù)，第0塊和第1塊是伙伴，第2塊和第3塊是伙伴，但是第1塊和第2塊不是伙伴。這樣規(guī)定的目的是確保一對伙伴中的兩個塊可以合并成更高級的大塊。 伙伴：2n*2b(2n+1)*2b70二、伙伴算法總大小1M的內(nèi)存，以1K為分配單位1.請求A=100KB2.請求B=240KB3.請求C=64KB4.請求D=256KB5.釋放B6.釋放A7.請求E=75KB8.釋放C9.釋放E10.釋放D71頁式存儲管理主存管理——頁式存儲管理背景，碎片問題：

用戶要求分配的邏輯地址是一個連續(xù)的范圍，它要求主存也有一個連續(xù)的區(qū)域，當(dāng)主存中現(xiàn)有的空閑區(qū)大小都小于要求分配的大小時，就是碎片。采用拼接手段解決碎片問題代價太大。 為了尋找解決碎片問題的新路徑，能否避開程序?qū)B續(xù)性的要求，使得可以將程序放到不相鄰的區(qū)域中。這正是分頁的思想。背景，主存的擴容：

分區(qū)存儲中，當(dāng)程序的地址空間小于主存可用空間時，該作業(yè)是不能投入運行的。

能否不必把所有程序地址空間裝入主存，而只把當(dāng)前所需的一部分內(nèi)容裝入主存？在程序運行時，由操作系統(tǒng)和硬件配合，自動的從輔存調(diào)入運行所需的內(nèi)容。背景：1、分區(qū)存儲管理的碎片問題；2、程序部分裝入，主存的擴容；3、內(nèi)存保護；4、實現(xiàn)了虛擬存儲；一、頁式系統(tǒng)的基本概念1.分頁

程序的虛擬地址空間被等分成大小相等的片，稱為頁面，又稱為虛頁。 物理內(nèi)存也被等分成大小相等的片，稱為主存塊，又稱為實頁。2.動態(tài)映射 虛頁和實頁的大小是一樣的，連續(xù)的虛頁可以被映射到不連續(xù)的實頁。解決了碎片問題。 程序開始運行時，每個頁面裝入到一個主存塊中，程序可以部分裝入就運行，在運行時按需加載。

頁式系統(tǒng)實例02KB4KB254KB256KB-102KB4KB6KB0頁1頁2頁3頁主存作業(yè)地址空間…………8KB頁式系統(tǒng)需要解決的問題：地址映射（方法和效率）。請調(diào)機制能夠判斷當(dāng)前訪問頁面是否在內(nèi)存中。如果不在內(nèi)存時如何處理。淘汰策略（置換算法）7836頁表①

什么是頁表為了實現(xiàn)從邏輯地址空間到物理主存的映象，系統(tǒng)建立的記錄頁與內(nèi)存塊之間對應(yīng)關(guān)系的地址變換的機構(gòu)稱為頁面映像表，簡稱頁表。

主存管理——頁式存儲管理地址映射37(5)分頁映像存儲的例子01KB01KB2KB3KB-1主存程序2地址空間2KB3KB4KB5KB6KB7KB8KB9KB10KB-101KB2KB-1程序1地址空間01KB-1程序3地址空間0516頁號塊號02140827程序1頁表程序2頁表程序3頁表osos分頁映像存儲主存管理——頁式存儲管理頁式地址變換虛地址結(jié)構(gòu)當(dāng)CPU給出的虛地址長度為16位，頁面大小為1KB時，在分頁系統(tǒng)中地址結(jié)構(gòu)的格式如下：

pw151090頁號P頁內(nèi)位移Wmovr1,[2500]12301KB2KB3KB-1程序2地址空間虛地址結(jié)構(gòu)主存管理——頁式存儲管理021427頁表40②頁式地址變換過程頁表始址寄存器movr1,[2500]12301KB2KB3KB-1程序2地址空間+021427頁表0000100111000100151090頁號P頁內(nèi)位移W250001KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB-1ososmovr1,[2500]123......頁號P頁內(nèi)位移W

24527×1024+452=7620頁式地址變換過程主存管理——頁式存儲管理41③頁式地址變換步驟CPU給出操作數(shù)地址(為2500)；由分頁機構(gòu)自動地把邏輯地址分為兩部分，得到頁號p和頁內(nèi)相對位移w(p=2，w=452)；根據(jù)頁表始址寄存器指示的頁表始地址，以頁號為索引，找到第2頁所對應(yīng)的塊號(為7)；將塊號b和頁內(nèi)位移量w拼接在一起，就形成了訪問主存的物理地址(7*1024+452=7620)主存管理——頁式存儲管理41習(xí)題6-14已知主存容量為64KB，某一作業(yè)A的地址空間如圖所示，它的四個頁面（頁面大小為1KB）0、1、2、3被分配到主存的2、4、6、7塊中。主存管理——頁式存儲管理movr1,[3500]1234501KB3KB4KB-1作業(yè)地址空間2KB（1）試畫出作業(yè)A的頁面映射表；（2）當(dāng)200號單元初有一條指令“movr1,[3500]”執(zhí)行時，如何進行正確的地址變化，以使得3500處的內(nèi)容12345裝入寄存器r1中，要求用圖畫出地址變換過程，并給出最終的物理地址。二級頁表：頁表頁表目錄…頁表索引頁表目錄索引頁表偏移線性地址………物理地址（實地址）頁內(nèi)偏移頁首地址110122122310111231效率分析： 每次讀寫一個數(shù)據(jù)至少需要訪問2次內(nèi)存。執(zhí)行速度下降100%。怎么辦： 一種特殊的高速緩沖存儲器：聯(lián)想存儲器8642(4)采用聯(lián)想存儲器加快查表速度①

什么是聯(lián)想存儲器

高速、小容量半導(dǎo)體存儲部件，又稱高速緩沖存儲器。②

快表在高速緩沖存儲器中存放正在運行的進程當(dāng)前用到的頁號和對應(yīng)的塊號，又稱為快表。主存管理——頁式存儲管理43③利用快表進行地址映射

a

+

Pw

僅在聯(lián)想映像不匹配時進行頁號

bw首先選擇聯(lián)想存儲器所有頁表在主存中物理地址pb┇┇┇┇┇┇ba+pa聯(lián)想寄存器和主存頁表相結(jié)合的分頁地址變換主存管理——頁式存儲管理頁表起始地址寄存器邏輯地址采用聯(lián)想存儲器的地址轉(zhuǎn)換假定訪問主存時間為100微秒，訪問聯(lián)想存儲器時間為10微秒，聯(lián)想存儲器為32個單元時快表命中率可達99%，按邏輯地址存取的平均時間為：(100＋10)×99%＋(100+100)×(1-99%)＝111微秒兩次訪問主存的時間為： 100×2＝200微秒。只裝入一個作業(yè)的部分頁面即可投入運行，一個作業(yè)事先分配固定數(shù)目的主存塊。在程序執(zhí)行過程中，如果需執(zhí)行的指令或訪問的數(shù)據(jù)尚未在內(nèi)存（稱為缺頁），則由處理器通知操作系統(tǒng)將相應(yīng)的頁或段調(diào)入到內(nèi)存，然后繼續(xù)執(zhí)行程序。內(nèi)存擴充（即程序部分裝入問題）44擴充頁表功能

頁號主存塊號中斷位輔存地址中斷位i

：標(biāo)識該頁是否在主存

若i=1，表示此頁不在主存；

若i=0，表示該頁在主存輔存地址：該頁面在輔存的位置主存管理——頁式存儲管理程序部分裝入需解決的問題怎樣發(fā)現(xiàn)所訪問的頁面在不在主存？當(dāng)發(fā)現(xiàn)所需訪問的頁面不在主存時如何處理?45缺頁處理示例①

程序2在請求分頁系統(tǒng)中的存儲映像01KB2KB4KB-1程序2地址空間movr1,[2120]addr1,[3410]0062510068023KB01KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB102142程序2頁表osos程序2第1頁程序2第0頁3頁號輔存地址中斷位塊號

0011地址地址地址地址主存管理——頁式存儲管理程序2在請求分頁系統(tǒng)中的存儲映像程序2的固定主存塊數(shù)為m=3，討論程序執(zhí)行46②

缺頁處理

“movr1，[2120］”指令執(zhí)行過程：CPU產(chǎn)生的虛地址為2120分頁機構(gòu)得p=2，w=72查頁表。該頁中斷位i=1發(fā)生缺頁中斷！

獲取輔存位置？如主存中有空白塊，且n<m，則直接調(diào)入如主存中無空白塊，或n=m，則需淘汰該程序在主存中的一頁中斷返回

01KB2KB4KB-1程序2地址空間movr1,[2120]addr1,[3410]0062510068023KB主存管理——頁式存儲管理47③缺頁處理過程圖示

啟動要處理的指令給出虛地址得到頁號該頁在主存?有空閑塊?缺頁中斷執(zhí)行完該指令準(zhǔn)備執(zhí)行下條指令選一頁淘汰從外存讀入所需的頁調(diào)整存儲分配表和頁表重新啟動被中斷的指令調(diào)整存儲分配表和頁表要重寫入?該頁寫入外存YNNY硬件軟件YN指令執(zhí)行步驟和缺頁中斷處理過程主存管理——頁式存儲管理484.淘汰機制與策略

(1)什么是淘汰策略用來選擇淘汰哪一頁的規(guī)則叫做置換策略，或稱淘汰算法。

主存管理——頁式存儲管理顛簸：

顛簸(thrashing)，又稱為“抖動”。 簡單地說，導(dǎo)致系統(tǒng)效率急劇下降的主存和輔存之間的頻繁頁面置換現(xiàn)像稱為“抖動”。

原因：淘汰的頁面恰好是不久又要訪問的頁面。

顛簸嚴(yán)重影響了系統(tǒng)的性能。缺頁中斷率假定作業(yè)p共計n頁，系統(tǒng)分配給它的主存塊只有m塊（1≤m≤n）。如果作業(yè)p在運行中成功的訪問次數(shù)為S，不成功的訪問次數(shù)為F，則總的訪問次數(shù)Ａ為：A=S+F

又定義：f=F/A

稱f為缺頁中斷率。(1)分配給進程的主存頁面數(shù)(2)頁面本身的大小(3)程序的編制方法(4)頁面淘汰算法影響缺頁中斷率的因素50(5)常用的頁面淘汰算法（置換算法）①

最佳算法(OPT算法)假定程序p有n頁，分配的主存塊只有m塊(1<=m<=n)。在程序執(zhí)行過程中，缺頁中斷次數(shù)最少的淘汰算法就是最佳算法。當(dāng)要調(diào)入一新頁而必須先淘汰一舊頁時，所淘汰的那一頁應(yīng)是以后不再要用的，或者是在最長的時間以后才會用到的那頁。

最佳算法是一個理論算法，是無法實現(xiàn)的，因為在程序運行中無法對以后要使用的頁面做出精確的判斷。最佳算法可以用來作為衡量各種具體算法優(yōu)劣的判斷。主存管理——頁式存儲管理51什么是先進先出淘汰算法總是選擇在主存中居留時間最長(即最早進入主存)的一頁淘汰。理由：最早調(diào)入主存的頁，其不再被使用的可能性比最近調(diào)用入的可能性大。先進先出淘汰算法的實現(xiàn)方法（1）建立一個頁號表p[m]，記錄頁面進入主存的先后次序；（m就是固定分配的主存塊數(shù)）一個替換指針，指向最早進入主存的頁面；當(dāng)需要置換一頁時，選擇替換指向的那一頁，然后調(diào)整替換指針的內(nèi)容。②

先進先出淘汰算法(FIFO算法)

主存管理——頁式存儲管理52m=4，頁面進入主存的先后次序：

4->5->1->2

替換指針指向最老的一頁頁號表

2

4

5

16

當(dāng)要調(diào)入第6頁時：替換第4頁將第4頁改為6替換指針指向下一個，第5頁

先進先出淘汰算法圖例主存管理——頁式存儲管理53實現(xiàn)方法（2）：在存儲分塊表中建立次序表在存儲分塊表中記錄頁面進入主存的先后次序：

4->5->1->2

當(dāng)要調(diào)入第6頁時：如何處理?5->1->2->67102345642516^74

2替換指針塊號頁號指針710234566251^274

6替換指針塊號頁號指針先進先出淘汰算法存儲塊構(gòu)造主存管理——頁式存儲管理51先進先出淘汰算法的實際效果：算法簡單容易實現(xiàn)，對于具有按照線性順序訪問地址空間的程序是比較適合的，而其他情況效率不高。因為，那些常常被訪問的頁，可能在主存中也停留得最久。據(jù)估計，先進先出淘汰算法的缺頁中斷率差不多是最優(yōu)算法的三倍。主存管理——頁式存儲管理54③最久未使用淘汰算法(LRU算法)總是選擇最長時間未被使用的那一頁淘汰。根據(jù)程序局部性原理，那些剛被使用過的頁面，可能馬上還要被使用，而在較長時間里未被使用的頁面，可能也不會馬上使用到。最久未使用淘汰算法的實現(xiàn)1、硬件計數(shù)器2、頁號堆棧3、近似算法實現(xiàn)主存管理——頁式存儲管理55硬件計數(shù)器：為每個頁表項關(guān)聯(lián)一個使用時間域，為CPU增加一個時鐘計數(shù)器。每次對主存的訪問，計數(shù)器都增加，并且相應(yīng)頁表項的時間域都記錄當(dāng)前的計數(shù)器。當(dāng)需要淘汰一頁時，選擇具有最小時間域的頁。

精確實現(xiàn)很困難！

（搜索時間域，更新時間域，時鐘計數(shù)器溢出）主存管理——頁式存儲管理55頁號堆棧頁面訪問軌跡：4->5->1->2->5->64512訪問第5頁訪問第6頁淘汰第4頁41251256訪問4、5、1、2頁后棧的內(nèi)容

訪問第5頁后，調(diào)整棧的內(nèi)容

訪問第6頁后，棧的內(nèi)容

用頁號堆棧記錄最近訪問的頁主存管理——頁式存儲管理57LRU淘汰近似算法實現(xiàn)主存管理——頁式存儲管理擴充頁表功能

①

引用位

——

標(biāo)識該頁最近是否被訪問為“0”——該頁沒有被訪問；為“1”——該頁已被訪問(由硬件自動置1，頁面管理軟件周期性將所有引用位置0)②

改變位——

表示該頁是否被修改為“0”——該頁未被修改；為“1”——該頁已被修改頁號主存塊號中斷位改變位引用位輔存地址57LRU淘汰近似算法實現(xiàn)7102345642514172

4替換指針塊號頁號引用位指針60017102345642564072

7替換指針塊號頁號引用位指針6011當(dāng)要調(diào)入第6頁時，如何處理?LRU近似算法舉例主存管理——頁式存儲管理56④LRU淘汰近似算法流程圖入口讀出替換指針指向的塊號移動指針指向下一個存儲塊引用位為0?選擇該頁淘汰，記錄該頁的頁號、塊號。根據(jù)改變位將該頁寫回輔存。將該頁所在的塊號送到替換指針返回置引用位為0YN主存管理——頁式存儲管理56LRU淘汰近似算法效果主存管理——頁式存儲管理1、周期T的選擇2、近似，不一定是最久未使用的頁缺頁處理練習(xí)：計算缺頁次數(shù) 某程序在內(nèi)存中分配三個主存塊，初始頁面為空，程序執(zhí)行時，頁面走向為4，3，2，1，4，3，5，4，3，2，1，5FIFO432143543215432143555211432143335224321444355xxxxxxxvv

xxv共缺頁中斷9次塊1塊2塊3調(diào)入先后次序

LRU432143543215432143543215432143543214321435432xxxxxxxvv

xxx共缺頁中斷10次塊1塊2塊3訪問時間次序?qū)⒎峙涞闹鞔鎵K數(shù)改為4，情況如何？

432143543215(FIFO)432143543215(LRU)432111543215432221543214333215432444321543XXXXvvXXXXXX432143543215432143543214321435432432111543XXXXvvXvvXXX41習(xí)題6-21在請求分頁系統(tǒng)中，某作業(yè)A有10個頁面，系統(tǒng)為其分配了3個主存塊。設(shè)該作業(yè)第0頁已裝入主存，進程運行時訪問頁面的軌跡是0、1、3、0、5、2、0，試用頁號棧的方法回答如下問題。主存管理——頁式存儲管理（1）在先進先出頁面置換算法下，缺頁中斷次數(shù)是多少？要求用圖畫出每一次頁面置換前后的情況。（2）若采用最久未使用淘汰算法呢？段頁式存儲管理主存管理——段頁式存儲管理581.段式地址空間

(1)什么是段分段是程序中自然劃分的一