第7章 存儲管理

1、第第7 7章章 存儲管理存儲管理 主講：房道偉主講：房道偉Daowei_操作系統(tǒng)原理操作系統(tǒng)原理今天雖然主存價格已相當便宜，但主存容量仍今天雖然主存價格已相當便宜，但主存容量仍然是計算機四大硬件資源中最關鍵而又最緊張的然是計算機四大硬件資源中最關鍵而又最緊張的“ 瓶頸瓶頸”資源。因此對主存的管理和有效使用仍然資源。因此對主存的管理和有效使用仍然是今天操作系統(tǒng)十分重要的內(nèi)容。許多操作系統(tǒng)之是今天操作系統(tǒng)十分重要的內(nèi)容。許多操作系統(tǒng)之間最明顯的區(qū)別特征之一往往是所使用的存儲管理間最明顯的區(qū)別特征之一往往是所使用的存儲管理方法不同。如方法不同。如OS/360-MFT采用采用固定分區(qū)固定分區(qū)存儲管理技

2、存儲管理技術(shù)，術(shù)，OS/360-MTV是采用是采用可變分區(qū)可變分區(qū)存儲管理技術(shù)，存儲管理技術(shù)，OS/2，WindowsNT, 是采用是采用虛擬存儲虛擬存儲管理技術(shù)。管理技術(shù)。主存儲器管理技術(shù)可分為兩大類：實存儲器管主存儲器管理技術(shù)可分為兩大類：實存儲器管理和虛擬存儲器管理。理和虛擬存儲器管理。主要內(nèi)容7.1 主存管理的基礎主存管理的基礎(1) 主存的物理組織和邏輯組織主存的物理組織和邏輯組織(a) 存儲器分三級：存儲器分三級：為能更多的存放并更快地處理用戶信息目前許多計算機把存儲器分為三級。高速緩存主存外存cpu可訪n+k 幾百knM 幾百Mn+MnG(G=1kn)用戶的程序在運行時應存放在主

3、存中，以便處理用戶的程序在運行時應存放在主存中，以便處理機訪問。但是由于主存容量有限。所以把那些不馬上機訪問。但是由于主存容量有限。所以把那些不馬上使用的程序、數(shù)據(jù)放在外部存儲器使用的程序、數(shù)據(jù)放在外部存儲器(又稱次級存儲又稱次級存儲)中。中。當用到時再把它們讀入主存。圖當用到時再把它們讀入主存。圖7.1中的三級存儲器，中的三級存儲器，從高速緩沖存儲器從高速緩沖存儲器(簡稱緩存簡稱緩存)到外部存儲器到外部存儲器(以后簡稱以后簡稱外存外存)，其容量愈來愈大，而訪問數(shù)據(jù)的速度則愈來愈，其容量愈來愈大，而訪問數(shù)據(jù)的速度則愈來愈慢，價格也愈來愈便宜，如慢，價格也愈來愈便宜，如IBM的緩存的最大傳輸速的

4、緩存的最大傳輸速度為每雙字度為每雙字120225毫微秒，主存的傳輸速度每字毫微秒，主存的傳輸速度每字1微微秒。秒。)(b) 程序只能在主存中運行程序只能在主存中運行(c) 物理地址：物理地址：(需要區(qū)分存貯體中不同的存需要區(qū)分存貯體中不同的存貯單元，統(tǒng)一編號貯單元，統(tǒng)一編號, 這些編這些編號稱為地址號稱為地址)與地址有關：20根2201M32根2324G物理地址是主存的真實地址 絕對地址物理地址的集合間 存貯空間它是：存儲控制部件能夠識別的主存單元編號(或字節(jié)地址)。(d)邏輯地址：又稱相對地址，是指相對于某個邏輯地址：又稱相對地址，是指相對于某個基準量基準量(通常用通常用0)編址時所使用的編

5、址時所使用的地址，相對地址常用于程序編寫地址，相對地址常用于程序編寫和編譯過程中。和編譯過程中。名空間 由程序員所寫符號組成。地址空間 一個目標程序所限定的地址集合。Address: mov Ax,1Obj 目標地址名空間編譯地址空間EXE文件裝入存貯空間(2) 存貯管理功能：存貯管理功能：(a) 映射邏輯地址為存貯地址地址映射映射邏輯地址為存貯地址地址映射(b) 在多個用戶間分配主存主存分配在多個用戶間分配主存主存分配研究主存分配算法，以及算法的性能(c) 對主存中信息提供保護存貯保護對主存中信息提供保護存貯保護(d) 擴充邏輯存區(qū)主存擴充擴充邏輯存區(qū)主存擴充(這里指的擴充并非指這里指的擴充

6、并非指硬件設備上的擴充，而是用存儲管理軟件來實硬件設備上的擴充，而是用存儲管理軟件來實現(xiàn)邏輯上的擴充即所謂的虛擬存貯技術(shù)現(xiàn)邏輯上的擴充即所謂的虛擬存貯技術(shù))(I) 地址映射地址映射(重定位重定位)(a) 執(zhí)行指令時，必須將地址變?yōu)榻^對地址才可執(zhí)行指令時，必須將地址變?yōu)榻^對地址才可訪問系統(tǒng)分配的內(nèi)存。訪問系統(tǒng)分配的內(nèi)存。存貯空間地址空間程序執(zhí)行時，必須將邏輯地址正確地轉(zhuǎn)換為物理地址即地址映射。mov Ax,(500)12.30100500100011001500mov Ax,(500)12.3裝入主存出錯解決方法：重定位(b) 使一個作業(yè)程序裝入到與其地址空間不一致使一個作業(yè)程序裝入到與其地址空

7、間不一致的存貯空間，所引起的對有關地址部分的調(diào)的存貯空間，所引起的對有關地址部分的調(diào)整過程稱為地址重定位。整過程稱為地址重定位。邏輯地址 物理地址(c) 地址映射的方式：地址映射的方式： 編程或編譯對確定地址映射關系，不靈活。 靜態(tài)地址映射 在裝入時實現(xiàn)調(diào)整 地址要有標識 每裝入時都可要定位 裝入后不再變(靜態(tài)) 動態(tài)重定位 在執(zhí)行尋址時重定位 訪問地址時通過地址變換機構(gòu)改變?yōu)閮?nèi)存地址mov Ax (500)12.3mov Ax (500)12.31005001100150010001000cpu運行主存B特點：特點：(1) 任意裝入內(nèi)存區(qū)域 (不要求占用一個連續(xù)的內(nèi)存)(2) 只裝入部分代碼

8、即可運行(3) 改變系統(tǒng)時不需改程序(程序占用的內(nèi)存空間、動態(tài)可變，主程序從某一個存貯區(qū)域移動時，只需修改得定位存器B即可)(4) 程序可共享(II) 主存分配：主存分配：(a) 分配策略分配策略(計算計算)放置策略 決定放的位置調(diào)入策略 裝入時機(什么時刻調(diào)入)淘汰策略 建立空閑區(qū)(b) 數(shù)據(jù)結(jié)構(gòu)：隊、表數(shù)據(jù)結(jié)構(gòu)：隊、表(c) 地址映射地址映射(III) 存貯保護：存貯保護：越界保護范圍存貯鍵保護存貯權(quán)限(IV) 主存擴充：邏輯存貯區(qū)擴充主存擴充：邏輯存貯區(qū)擴充(利用輔存)(1)單一連續(xù)區(qū)分配單一連續(xù)區(qū)分配(a)概要：存區(qū)分為概要：存區(qū)分為o.s連續(xù)區(qū)和用戶連續(xù)區(qū)連續(xù)區(qū)和用戶連續(xù)區(qū)o.s區(qū)用

9、戶區(qū)越界R受保護o.s存取區(qū)特權(quán)管態(tài)目態(tài)7.2 實存管理實存管理 (b) 簡單、低放、單一用戶簡單、低放、單一用戶單用戶o.s的內(nèi)存管理十分簡單，因為存貯器在任何時候都只保存一個用戶進程，除o.s本身占據(jù)的內(nèi)存外都可分配給用戶使用。方案：方案： o.s可以占據(jù)可以占據(jù)RAM的底部的底部(a)或頂部或頂部(b) 也可以部分在內(nèi)存頂部的也可以部分在內(nèi)存頂部的Rom中，另一中，另一部分存放部分存放RAM底部底部(c)IBM PC在MS/Dos下，其內(nèi)存分配便條用(c) 其裝有設備驅(qū)動程序的8k.Rom占據(jù)IM地址空間的最高區(qū)通常稱Rom中的這些設備驅(qū)動程序為BIOS用戶程序o.s(a)用戶程序o.s

10、(b)Rom設備驅(qū)動程序o.s用戶程序(c)(2) 固定分區(qū)：把主存分成若干個固定大小的存固定分區(qū)：把主存分成若干個固定大小的存儲區(qū)儲區(qū)(存儲塊存儲塊)(a) 概要：主存被劃分為多個分區(qū)，每個分區(qū)分給概要：主存被劃分為多個分區(qū)，每個分區(qū)分給某一作業(yè)使用，并由分區(qū)說明表指明某一作業(yè)使用，并由分區(qū)說明表指明作業(yè)按區(qū)分配直到該作業(yè)完成后才把作業(yè)按區(qū)分配直到該作業(yè)完成后才把該存儲區(qū)歸返系統(tǒng)。該存儲區(qū)歸返系統(tǒng)。o.s區(qū)20k28k60k90k128k256k0區(qū)1區(qū)2區(qū)3區(qū)4區(qū)區(qū)號 大小起址狀態(tài)123420k28k60k128kin usingNuL8k32k68k128kin usingNuL(存貯分

11、塊表MBT)固固定定分分區(qū)區(qū)分分配配算算法法大大區(qū)區(qū)圖圖要求xk大小的分區(qū)取分區(qū)說明表的第一項該分區(qū)空閑嗎？分區(qū)大小xk表結(jié)束嗎？返回分區(qū)號狀態(tài)位置1無法分配取下一項NNNYYY(b) 特點特點由操作員劃分分區(qū)MBT應放在操作系統(tǒng)區(qū)內(nèi)，填分區(qū)表多道程序零頭缺點：缺點：不允許兩個作業(yè)同時放于同一個分區(qū)中剩下的空閑部分稱為內(nèi)存碎片內(nèi)存碎片，降低了主存利用率。(3) 可變分區(qū)可變分區(qū)(a) 概要：概要：存貯空間的劃分在作業(yè)裝入時進行(事先并未劃分成一塊塊分區(qū))，且使分區(qū)大小與作業(yè)大小一致(按作業(yè)大小建立)分區(qū)大小、個數(shù)，不固定的(系統(tǒng)啟動時，整個主存除o.s塊外，其余主存區(qū)可看成是整個一個分區(qū))。O

12、.S自由分區(qū)0512k1536k序號 大小起址狀態(tài)1234312k320k384k已分已分8k32k120k空表目已分5空表目大小起址狀態(tài)352k504k自由空表目32k520k自由空表目空表目已分配分區(qū)表已分配分區(qū)表 UBT表表自由分區(qū)表自由分區(qū)表FBT20k28k94k232k248ko.s區(qū)Job1(8k)Job2(16k)Job4(50k)Job3(124k)Job5(16k)44k108k256k分裂分裂 來了job4(50k), job5(16k)未分配分區(qū)表(自由分區(qū)表)FBT的變化序號大小起址狀態(tài)1264k14k24k8k44k94k232k248k自由自由 job2, job

13、3完成后、釋放(如下圖) o.s區(qū)Job1 Job4 Job5合并空申請分配一個xk大小的分區(qū)置空白區(qū)號F1(F)的狀態(tài)可用？空白區(qū)F大小xk？loc(F)的始址否是請求主存塊程序框圖請求主存塊程序框圖F未分配表的結(jié)尾？置空白區(qū)F，F(xiàn)的狀態(tài)空表目(F)的大小xk(F)的大小loc+xk (F)的始邊在分配表中找一個狀態(tài)空表目的分區(qū)P置P分區(qū)的大小xk置P分區(qū)的地址loc置狀態(tài)已分配返回一個分區(qū)號P本次無法分配一個分區(qū)F+1Fnk，但不能裝入nk作業(yè)(iii) 解決的方法：(I) 將程序裝入分散存區(qū)中 多重分區(qū)Job1Job2Job3RR11RR 12Job4部分2Job4部分1RR21RR22

14、(II) 將碎片集中(緊湊或拼接) 可重定位分配Job1Job2Job3Job4可重定位分區(qū)分配法是利用分區(qū)的“ 拼接”(對空白區(qū)而言)或“ 緊湊”(作業(yè)程序而言)技術(shù)解決“ 零頭”。(4) 可重定位分區(qū)分配可重定位分區(qū)分配(a) 概要：概要：移動內(nèi)存已分配區(qū)的信息，使得所有分配區(qū)靠在一起使空白區(qū)連成一片，采用浮動方法。(b) 浮動浮動(重定位動態(tài)重定位動態(tài))進行主存的壓縮，就進行主存的壓縮，就要將主存中用戶程序移動要將主存中用戶程序移動(浮動浮動)，對作業(yè)，對作業(yè)中與地址有關的部分進行調(diào)整。中與地址有關的部分進行調(diào)整。請求分配一個大小為xk的分區(qū)有大于xk的空閑區(qū)嗎？空閑區(qū)的總和xk嗎？緊縮

15、存儲并相應地修改諸表(得到一個完整的空閑區(qū)xk)分配分區(qū)并修改諸表此刻已經(jīng)分配一個分區(qū)返回一個分區(qū)號數(shù)是是否否(c) 動態(tài)重定位可變分區(qū)分配算法：動態(tài)重定位可變分區(qū)分配算法：20k28k88k132k182ko.s作業(yè)1(8k)(36k)作業(yè)3(24k)(24k)作業(yè)2(20k)作業(yè)4(50k)(74k)64k112k256k(a)初始狀態(tài)20k202ko.s1324作業(yè)5(80k)(54k)122k(c)分配作業(yè)5之后(b)移動之后(即浮動)20k28k72ko.s1(8k)3(24k)2(20k)4(50k)(134k)52k122k256k作業(yè)580k實現(xiàn)這種重定位，可通過類似于重定位裝

16、入程序的軟件來達到，但這種方案要在費許多處理機時間，而且限制較大。較好的辦法是采用動態(tài)重定位技術(shù)(在本章中，當一個作業(yè)裝入與其地址空間不一致的存儲空間時，可在每次訪問指令或數(shù)據(jù)時，通過重定位寄存器來自動修改訪問存儲器的地址)因而，一個作業(yè)在主存中移動后，只需要改變重定位寄存器的內(nèi)容即可。圖(a)是作業(yè)拼接之前的執(zhí)行情況，這時重定位寄存器RR的值為64k，(b)是拼接后作業(yè)3執(zhí)行情況，作業(yè)3被移動到28k大字節(jié)開始的分區(qū)中。為保證在新的位置上仍能正確執(zhí)行，只需要將重點定位寄存器RR的值改為28k即可。LDAD 1,50012345Load 1,5001 2 3 4 550064K0100500R

17、R656366603664作業(yè)3的分區(qū)88K處理機一側(cè)存貯器一側(cè)(a) 拼接前相對地址定位寄存器Load 1,50012345Load 1,5001 2 3 4 550028K0100500RR287722917228k(b) 拼接后的執(zhí)行情況52k256k主存24k相對地址定位寄存器采取動態(tài)重定位后，由于目標程序裝入主存后不需修改地址指針及所有與地址有關的項，因而程序可在主存中隨意浮動而不影響其正確執(zhí)行。這樣，就可以方便地進行存儲器緊縮，較好地解決了碎片問題。(d) 拼湊時機拼湊時機(i) 出現(xiàn)相鄰空白區(qū)即拼接；(或某分區(qū)被釋放后即緊縮)(ii) 存貯不足(空白分區(qū)不夠大)時進行拼接緊縮工作

18、大，開銷大，但管理簡單緊縮次數(shù)少，但管理(算法)較復雜。前面已有框圖表示(5) 多重分區(qū)分配不拼接而解決零頭問題多重分區(qū)分配不拼接而解決零頭問題(a) 概要概要將程序分為若干段，按小段申請存區(qū)，即將程序分散在不連續(xù)存區(qū)中運行。程序：程序、數(shù)據(jù)區(qū)等(也可解決共亨信息問題)：給一個作業(yè)分配二個分區(qū)o.s作A 0區(qū)作A 1區(qū)下界0上界0下界1上界1采用動態(tài)重定位技術(shù)： 利用下界寄存器作為重定位Reg 而上界可供檢查地址越界用在實存管理技術(shù)中，多重分區(qū)的多重程序不宜過多，否則會增加管理的復雜性，一般不超過34對界地址寄存器。多重分區(qū)技術(shù)的進一步發(fā)展導致了段式虛擬存儲管理技術(shù)的出現(xiàn)。(6) 覆蓋覆蓋(o

19、verlay): 指一個作業(yè)的若干程序段指一個作業(yè)的若干程序段(或數(shù)據(jù)或數(shù)據(jù)段段)或幾個作業(yè)的某些部分間共享某主存空間或幾個作業(yè)的某些部分間共享某主存空間(a) 目標：用較小的存區(qū)滿足較大的存區(qū)要求目標：用較小的存區(qū)滿足較大的存區(qū)要求(b) 程序的分析：并不是作業(yè)的每一部分都是時時程序的分析：并不是作業(yè)的每一部分都是時時要用的要用的mainA 20kA0, 30kB0, 40kB1, 30kA2, 30kA1, 60kA4, 40kA3, 20kB0, 40kB1, 30kA1, 60kA2, 30kA3, 20kA4, 40kmain20k覆蓋段040k覆蓋段160k覆蓋段240kAmain

20、20kA0, 30k則總計270k 160k內(nèi)存即可可裝入(c) 注意：注意：(i) 每次僅放入作業(yè)的一個部分(ii) 覆蓋段程序員事先確定(iii) 系統(tǒng)自動覆蓋虛存(iv) 可與其內(nèi)存分配方法結(jié)合使用(7) 交換：交換：(swapping)(a) 目標：解決小主存分區(qū)大作業(yè)的矛盾目標：解決小主存分區(qū)大作業(yè)的矛盾 利用輔存利用輔存(b) 概要：概要：將主存中已阻塞的作業(yè)信息存入輔存，將輔存中的活動作業(yè)調(diào)入主存并運行。job1job2job3job1job2job1job2job3job3job1主存輔存上部上部下部job3job2job2覆蓋的部分保存好！Job2下部Job1 Job3 主存

21、大小作業(yè)無法運行“ 擴充”主存 虛擬存貯技術(shù)(b) 虛擬存貯器：虛擬存貯器：地址空間存貯空間(編程)(運行)邏輯物理虛空間(虛存)實存、實空間交換o.s 程序的訪問地址稱為虛地址而程序可訪問的虛地址范圍叫做程序的虛地址空間。 可使用的實地址范圍叫實地址空間(即主存)(c) 虛空間獨立于實空間虛空間獨立于實空間虛空間實空間(也可以虛空間實空間)系統(tǒng)地址空間 虛存空間地址結(jié)構(gòu)20位有效地址長度 0220(尋址范圍)，實存64k虛存220作業(yè)可以大于內(nèi)存，部分作業(yè)調(diào)入運行，其余放入磁盤。利用輔存存放放不進內(nèi)存的作業(yè)部分。 主存輔存虛擬存(僅與地址結(jié)構(gòu)有關)(2) 分頁存貯管理：分頁存貯管理：(a)

22、實現(xiàn)原理：實現(xiàn)原理：地址空間分成大小相同的部分 頁存貯空間分成大小相同的部分 塊(頁架)頁大小塊大小頁大小塊大小頁號塊號狀態(tài)012238該頁是否在內(nèi)存分配時頁對應塊，但不要求連續(xù)頁表(PMT)又稱頁面映象表由內(nèi)存一個特殊區(qū)域擔任重定位(地址變換)包括：頁號，塊號以及狀態(tài)mov Ax (2500)mov AX (2500)123 頁號 塊號012238頁表2頁0頁頁 1k分3頁0塊1塊2塊3塊8塊01k2k3k9k8k4k1k2k3k1002500250010242452作業(yè)地址空間1頁邏輯地址的表示(p, d)P = INT A/L；d = A mod L其中A：虛地址 L：頁大小P ：頁號

23、d：頁內(nèi)位移例：2452頁塊012238頁表長 頁表始址8452123實地址虛地址(頁)d (偏移)P(頁)9k8644頁表地址reg+例：設虛地址為(357101)8 每一塊為128字節(jié)12827(357101)8( 01 110 111 100 1 000 001)21 6 7 4 101偏移為(101)8, 頁號為(1674)8塊號由頁表指定，偏移不變(b) 多級頁表的地址轉(zhuǎn)換多級頁表的地址轉(zhuǎn)換進程的頁表表目可達222個。而Windows NT 等使用x86的CPU的32位地址，使用4KB的頁面(212)，這意味著進程最多可以使用多達220(100多萬)個頁面。如果每個頁表表目占4byt

24、e，那么每個進程的頁表所占的空間是222byte，占去主存的1的空間，顯然這樣大的頁表是不能全放在主存中的。為此對頁表本身也采取分頁措施。即把頁表本身按固定大小分成為一個個頁面(頁面大小為 212=4KB)。每個小頁表形成的頁面中可以有2101K個頁表表目（每個表目4byte），共有2101K個小頁表。為了對1K個小頁表進行管理和索引查找，設置一個頁表目錄，又稱之為頂級頁表，該頂級頁表包含有1K個表目項，分別指出每個次級小頁表所在物理頁號和其他有關狀態(tài)信息。這樣，每個進程有一個頁目錄，它的每個表目映射一個頁表。頁目錄本身大小剛好是一個頁面大小，頁目錄是一級表。而每個小頁表本身就是二級頁表。以后

25、一律使用頁目錄和頁表的名稱。頁目錄寄存器當前進程頁目錄31110頁架號+面目錄號 頁號 偏移虛擬地址+3112 110 頁架號頁架號 偏移物理地址3122 21 12 11 0當前進程的某個次級頁表31 12 110二級頁表地址變換通過二級頁表的地址映射訪問主存存取數(shù)據(jù)需要三次訪問主存（一次頁目錄，一次頁表，最后是數(shù)據(jù)所在物理地址），所需時間是原來的三倍。當然對64位的地址，也可組織成三級、四級頁表，但性能的影響是不可忽視的。(若頁表全部放在主存，則要取一個數(shù)據(jù)(一條指令)至少要訪問二次主存，第一次是訪問頁表，確定所取數(shù)據(jù)(或指令)的物理地址，第二次是根據(jù)該地址取數(shù)(或指令)將作業(yè)中最常用的頁

26、塊號置入高速緩存，提高查表速度(在地址變換機構(gòu)中加入一個高速、不容易的聯(lián)想存儲器)(c) 快表快表(聯(lián)想存貯器聯(lián)想存貯器)訪問主存訪頁表訪主存訪問主存訪頁表訪主存存放頁表部分內(nèi)容的快速存貯器稱為聯(lián)想存貯器，聯(lián)想存貯器中存放的部分頁表稱為“ 快表”。聯(lián)想存貯器一般由816個單元組成，它們用來存放正在運行進程的當前最常用的頁號和相應的塊號，并具有并行查尋能力。 查聯(lián)想表物理地址(訪問一次主存) 查頁表物理地址(訪問二次主存) 有效地址同時進行這個聯(lián)想存貯器的查表速度可以做到比一般存儲器的速度快一個數(shù)量級。PBPB輸入輸出B WPW聯(lián)想表物理地址頁表起址PB頁表虛地址(分頁)B例：設訪問主存時間為2

27、00ns,訪問聯(lián)想存貯器為40ns，命中率為90，則平均存取時間為多少？查頁表兩次訪存：平均為200200400ns查塊表(200+40)90(200+200)10256ns解：方法方法1：方法方法2：(3) 請求分頁式存儲管理請求分頁式存儲管理(a) 目標：實現(xiàn)小內(nèi)存大作業(yè)目標：實現(xiàn)小內(nèi)存大作業(yè)(b) 實現(xiàn)方法：作業(yè)運行時，只將當前的一部分裝實現(xiàn)方法：作業(yè)運行時，只將當前的一部分裝入內(nèi)存其余的放在輔存，一旦發(fā)現(xiàn)訪問的頁不入內(nèi)存其余的放在輔存，一旦發(fā)現(xiàn)訪問的頁不在主存中，則發(fā)出缺頁中斷，由在主存中，則發(fā)出缺頁中斷，由o.s將其從輔存將其從輔存調(diào)入主存，如果內(nèi)存無空塊，則選擇一個頁淘調(diào)入主存，如

28、果內(nèi)存無空塊，則選擇一個頁淘汰。汰。怎樣發(fā)現(xiàn)頁不在內(nèi)存？擴充表(以前頁表結(jié)構(gòu)只包含頁號和塊號兩個信息，這是進行地址變換機構(gòu)所必須的，為了判斷頁面在不在主存，可在原頁表上擴充，增加兩個數(shù)據(jù)項、中斷位I，輔存的位置)。第一個問題：第一個問題：頁號塊號中斷位輔存1. 不在內(nèi)存0. 在內(nèi)存當進程運行時，在內(nèi)存中至少有一塊為該進程所對應的程序所占用，并正在執(zhí)行此塊內(nèi)的一條指令。若這條指令不涉及訪內(nèi)地址則罷，如果涉及訪內(nèi)地址，則由分頁機構(gòu)得到頁號，并以該頁號為索引查頁表PT，這時將有兩種可能性：發(fā)生缺頁中斷請求調(diào)入此頁，當缺頁中斷發(fā)生時，用戶程序被中斷，控制轉(zhuǎn)到os的調(diào)頁程序，由調(diào)頁程序把所需的頁面從磁盤

29、調(diào)入內(nèi)存的某塊中，并把頁表中該頁面登記項中的中斷位I由1改為0，填入實際塊號，隨后繼續(xù)執(zhí)行被中斷的程序，這一頁面是根據(jù)請求而裝入的，因而稱為請求分頁存貯管理。 此頁對應頁表中的中斷位為0，表示此頁已調(diào)入主存，可查得塊號B，形成BW的物理地址，從而指令得以執(zhí)行，繼而執(zhí)行下條指令； 當中斷位為1，表示此頁不在主存，而是在磁盤上(輔存地址指示)指令執(zhí)行和缺頁中斷處理指令執(zhí)行和缺頁中斷處理啟動要處理的指令該頁在主存給出虛地址形成頁號有空閑塊從外存讀入需要的頁調(diào)整存貯分塊表和頁表重新啟動被中斷的指令準備執(zhí)行下條指令執(zhí)行完該指令選一頁淘汰調(diào)整存貯分塊表和頁表要重新寫入該頁寫入外存YYYNN硬件軟件N缺頁中

30、斷如何處理缺頁一缺頁中斷管理？ 發(fā)現(xiàn)中斷、調(diào)入所缺頁第二個問題：第二個問題：如果內(nèi)存不足，選一頁淘汰，選擇哪一頁呢？引用位是來指示某頁最近被訪問過沒有？修改位是來指示某頁的數(shù)據(jù)修改過沒有？“ 0”表示沒有訪問過“ 1”表示已被訪問過引用位修改位0修改位 寫回輔存1未修改過 不必寫回輔存輔存地址引用位中斷位改變位主存塊號頁號頁表表目為(c) 置換算法置換算法 確定淘汰哪一頁的策略確定淘汰哪一頁的策略系統(tǒng)抖動 內(nèi)外存交換頻繁使效率下降(導致系統(tǒng)效率急劇下降的主、輔存之間的頻繁轉(zhuǎn)換現(xiàn)象)駐留集 駐留在內(nèi)存中頁面的集合。成功失敗失敗成功的訪問次數(shù)不成功的訪問次數(shù)缺頁中斷率FSF)()(i) 最佳置換算

31、法：(OPT)“ 淘汰在將來再不被訪問(以后不再要的)，或者在最遠的將來才被訪問的頁”然而這樣的算法是無法實現(xiàn)的，因為在程序運行中無法對后面要使用的頁面作精確的判斷，不過可作為衡量各種具體算法的標準。(ii) 先進先出算法(FIFO)例：設頁面請求次序7.0.1.2.0.3.0.4.2.3.0.3.2.1.2.存貯塊為3時(駐留集為3)3012302302304230423042301230120127017012707 0 1 2 0 3 0 4 2 3 0 3 2 1 2+ + + + + + + + + + + +頁面跡蹤圖缺頁率為801001512駐留集越大，缺頁中斷率越小嗎？(不一定

32、)。一般來說，對于任何一個頁的訪問順序(或序列)和任何一種換頁算法，如果分給的頁架數(shù)增加，則缺頁(所訪問頁不在主存)的頻率應該減少。但這個結(jié)論并不普遍成立，對于某些頁面訪問序列，F(xiàn)IFO有隨著分給的頁架數(shù)增加，缺頁頻率也增加的異?，F(xiàn)象。頁 面 訪問 序 列九 次缺 頁三塊頁架A BC D A BEABC DEA BCDABEEEC D DAB C DA B B BEC CA BCDA AA BEE+頁 面 訪問 序 列十 次缺 頁四塊頁架ABCDABEABC D EABCDDDEAACD EABCCCDEEBCDABBBCDDA BC+ +AAABCCEAB+(iii) 最近最久未用頁面算法(

33、最近最少使用)LRU其思想：“ 若發(fā)生缺頁中斷，則選擇最近一段時間內(nèi)最長時間沒有被訪問的頁淘汰掉，將要使用的頁調(diào)入主存”。基本理由是認為過去一段時間里不曾被訪問過的頁，在最近的將來也可能不再會被訪問。1232303020323242404 0303230202121010772130770 1 2 0 3 0423 0 3 2 1 2+ + + + + + + + 缺頁率7 .661001510缺頁次數(shù)：10該算法實現(xiàn)起來比較困難，因為要為每一頁設置一特定單元來記錄自上次訪問后到現(xiàn)在的時間量 t，并選擇 t值最大的頁淘汰。得到廣泛使用的是最近最久未使用算法的近似方法 最近未使用更換算法(NUR

34、)，它比較易于實現(xiàn)，開銷也比較少，此更換算法，不但希望淘汰的頁是最近未使用的頁，而且還希望被挑選的頁在主存駐留期間，其頁面內(nèi)的數(shù)據(jù)未被修改過。為此，要為每頁增設兩個硬件位、訪問位和修改位。(iv) 最近未用更換算法 (NUR)訪問位0；該頁尚未被訪問過。1；該頁已經(jīng)被訪問過。修改位0；該頁尚未被修改過。1；該頁已經(jīng)被修改過。其具體工作過程如下：開始時，所有頁的訪問位、修改位置為“0”。當訪問某頁時，將該頁訪問位置“1”。當某頁的數(shù)據(jù)被修改，則該頁的修改位置“1”。當要選一頁淘汰時，挑選下面序列中屬于低序號情況的頁進行淘汰。序號：1234訪問位： 0011修改位： 0101在多道程序系統(tǒng)中，主存

35、中所有頁架的訪問位或修改位可能都會被置成了“1”，這時就難以決定淘汰哪一頁。當前大多數(shù)系統(tǒng)的解決辦法是避免出現(xiàn)這種情況，為此，周期性地(經(jīng)一定時間間隔)把所有訪問位重新清成“0”。當以后再訪問頁面時重新置“1”，這里一個主要問題是選擇適當?shù)那辶銜r間間隔，如果間隔太大，可能所有頁架的訪問位均成為“1”。如果間隔太小，則訪問位為“0”的頁架又可能過多。LRU和NUR算法沒有異?，F(xiàn)象，即駐留集越大，缺頁中斷率越小。(d) 注意：注意：(i) 虛存：頁面并未全部放入內(nèi)存，使用戶感到“ 內(nèi)存”很大用戶不用考慮覆蓋系統(tǒng)“ 擴充內(nèi)存”用戶編程在虛空間，運行在物理空間缺頁中斷處理屬于中級調(diào)度外存、內(nèi)存、高速緩

36、沖，三級存貯變?yōu)橐患墶?e) 評價：評價：虛存大，有效地利用了主存，適合多道程序，方便用戶編程。處理頁面調(diào)度的開銷，防止抖動開銷較大。(4) 分段存貯管理分段存貯管理(segrmanent)(a) 段地址空間：作業(yè)由若干個邏輯分段組成，段地址空間：作業(yè)由若干個邏輯分段組成，如由代碼分段如由代碼分段(cs)數(shù)據(jù)分段數(shù)據(jù)分段(ds),棧段棧段(ss)附加段附加段(Es)組成組成一個段可定義為一組邏輯信息，如子程序，數(shù)組或工作區(qū)，(分段是程序中自然劃分的一組邏輯意義完整的信息集合，它是用戶在編程時決定的)。因此，每個作業(yè)的地址空間是由一些分段構(gòu)成的，每段都有自己的名字，且都是一段連續(xù)的地址空間。如下圖，可見整個作業(yè)的地址空間是二維的Y:0500C:0200D:0300CallLoadstore01kMain(主程序)分段X(子程序)分段A(數(shù)據(jù))分段B(工作區(qū))分段地址系統(tǒng)中的地址結(jié)構(gòu)有如下形式：(24位)段號S位移量W0723loadY D 12345C 段號 段長 主存始址01k6k15004k23008k32009200SB段表LOAD 1, 11001234501k050003000200100