內(nèi)存管理學(xué)習(xí)教案

1、會計學(xué)1內(nèi)存管理內(nèi)存管理第一頁，編輯于星期一：十五點 三十分。4.1 概述存儲系統(tǒng)的設(shè)計目標(biāo)可歸納成3個問題： 容量，速度，成本 容量：需求無止境 速度：能匹配處理器的速度成本：成本和其他部件相比應(yīng)在合適范圍之內(nèi)第1頁/共111頁第二頁，編輯于星期一：十五點 三十分。存儲器的層次結(jié)構(gòu)容量、速度和成本之間的矛盾：三個目標(biāo)不可能同時達(dá)到最優(yōu)，要作權(quán)衡 存取速度越快，每一個位（Bit）的價格越高追求大容量，就要降低存取速度追求高速度，就要降低容量第2頁/共111頁第三頁，編輯于星期一：十五點 三十分。存儲器的層次結(jié)構(gòu)解決方案：采用層次化的存儲體系結(jié)構(gòu) 當(dāng)沿著層次向下時 每位的價格下降容量增大 速度變

2、慢Cache內(nèi)存磁盤寄存器策略：較小、較貴的存儲器由較大、較便宜的慢速存儲器作為后援虛擬存儲器 降低較大、較便宜的慢速存儲器的訪問頻率高速緩存第3頁/共111頁第四頁，編輯于星期一：十五點 三十分。存儲器的層次結(jié)構(gòu)寄存器（Register）：在CPU內(nèi)部，用來暫存數(shù)據(jù)、地址以及指令信息。在計算機(jī)的存儲系統(tǒng)中它具有最快的訪問速度。 速度比主存快得多 造價高，容量一般都很小內(nèi)存：速度盡量快到與CPU取指速度相匹配，大到能裝下當(dāng)前運(yùn)行的程序與數(shù)據(jù)，否則CPU執(zhí)行速度就會受到內(nèi)存速度和容量的影響而得不到充分發(fā)揮 高速緩存（cache）：處于CPU和物理內(nèi)存之間，訪問速度快于內(nèi)存，但低于寄存器Cache

3、內(nèi)存 磁盤寄存器第4頁/共111頁第五頁，編輯于星期一：十五點 三十分。4.1 概述 有效利用內(nèi)存空間帕金森帕金森（parkinson）定律：定律：內(nèi)存有多大，程序就有多大 考慮管理的開銷：時間，空間 應(yīng)用程序不必特別考慮內(nèi)存的大小第5頁/共111頁第六頁，編輯于星期一：十五點 三十分。4.1 概述 記錄內(nèi)存的使用情況（是否空閑）進(jìn)程所占內(nèi)存空間的分配與回收當(dāng)內(nèi)存不足時，采取相應(yīng)措施內(nèi)存空間的共享與保護(hù)第6頁/共111頁第七頁，編輯于星期一：十五點 三十分。4.2 程序的連接與裝入一、程序連接的功能多個目標(biāo)文件及庫文件連接成1個完整的可執(zhí)行文件。 定位目標(biāo)文件可能存在的一些外部符號 浮動地址的

4、重定位第7頁/共111頁第八頁，編輯于星期一：十五點 三十分。4.2 程序的連接與裝入二、程序連接的時機(jī) 靜態(tài)連接：靜態(tài)的，只連接1次，多次運(yùn)行 裝入時連接：裝入后是靜態(tài)的 實際運(yùn)行時連接：調(diào)用時動態(tài)連接第8頁/共111頁第九頁，編輯于星期一：十五點 三十分。4.1 程序的連接與裝入裝入方式：（1）完全靜態(tài)裝入（2）靜態(tài)重定位裝入（3）動態(tài)重定位裝入三、程序的裝入方式 程序能否直接在外存中執(zhí)行？ 不行！每個程序在運(yùn)行前，必須裝入內(nèi)存。 不一定一次全部裝入。第9頁/共111頁第十頁，編輯于星期一：十五點 三十分。程序的裝入方式1. 完全靜態(tài)裝入程序裝入時不作任何修改。即裝入內(nèi)存的每個字節(jié)與其可執(zhí)

5、行文件完全相同。例如，DOS操作系統(tǒng)下的.com文件。第10頁/共111頁第十一頁，編輯于星期一：十五點 三十分。程序的裝入方式2. 靜態(tài)重定位裝入程序裝入時進(jìn)行一次地址重定位，運(yùn)行時不變。重定位： 程序中的相對地址（從0開始）絕對地址第11頁/共111頁第十二頁，編輯于星期一：十五點 三十分。程序的裝入方式n邏輯地址（相對地址） 用戶的程序經(jīng)過匯編或編譯連接后形成可執(zhí)行代碼，代碼通常采用相對地址的形式，其首地址為0，指令中的地址都采用相對于首地址的偏移量 機(jī)器是不能用邏輯地址在內(nèi)存中讀取信息的。n物理地址（絕對地址） 內(nèi)存中存儲單元的實際地址第12頁/共111頁第十三頁，編輯于星期一：十五點

6、 三十分。靜態(tài)重定位裝入MOV AX, 500H00fffh模塊AMOV BX, 600H01fffh模塊BMOV AX, 500H02fffhMOV BX, 1600HMOV AX, 10500H12fffhMOV BX, 11600H10000h連接裝入第13頁/共111頁第十四頁，編輯于星期一：十五點 三十分。程序的裝入方式3. 動態(tài)重定位裝入真正執(zhí)行到一條指令要訪問某個內(nèi)存地址時，才進(jìn)行地址重定位。好處：程序可以在內(nèi)存中移動。如何實現(xiàn)動態(tài)重定位？ 一般設(shè)置1個重定位寄存器， 存放當(dāng)前進(jìn)程在內(nèi)存的起始地址 絕對地址 = 相對地址 + 重定位寄存器的值第14頁/共111頁第十五頁，編輯于星

7、期一：十五點 三十分。動態(tài)重定位裝入1000123456MOV AX,2000100200300.MOV AX, 200123456邏輯地址空間110012001300物理地址空間200地址+1000重定位寄存器.第15頁/共111頁第十六頁，編輯于星期一：十五點 三十分。4.3 實存儲器管理程序的大小不能超過可用內(nèi)存空間的大小。一、連續(xù)分配 為每個進(jìn)程分配連續(xù)的內(nèi)存空間。 1.單一連續(xù)區(qū)分配 內(nèi)存中只存在1個用戶程序。 整個用戶區(qū)為該程序獨占。 一般將內(nèi)存劃分為2個區(qū)： 系統(tǒng)區(qū)：存放OS程序和數(shù)據(jù) 用戶區(qū)：存放用戶程序和數(shù)據(jù)只能用于單用戶、單任務(wù)OS。第16頁/共111頁第十七頁，編輯于星期

8、一：十五點 三十分。連續(xù)分配 2.固定分區(qū)將內(nèi)存的用戶區(qū)預(yù)先劃分為若干區(qū)域（分區(qū)）分區(qū)個數(shù)和每個分區(qū)的大小是固定的每個分區(qū)存放1個進(jìn)程管理所需的數(shù)據(jù)結(jié)構(gòu)： 1個分區(qū)使用表（內(nèi)存分配表），記錄分區(qū)狀態(tài)。第17頁/共111頁第十八頁，編輯于星期一：十五點 三十分。固定分區(qū)存在的問題：區(qū)號 分區(qū)大小 起始地址 狀態(tài)1 8kB 32k Used2 16kB 40k Free3 22kB 56k Free 4 34kB 78k UsedOS進(jìn)程A(6KB)進(jìn)程B(28KB) 0 32k 40k56k 78k分區(qū)使用表內(nèi)部碎片(1) 超過最大分區(qū)的程序無法裝入；(2) 存在內(nèi)部碎片(Internal fr

9、agmentation)：由于程序長度小于分區(qū)，使得分區(qū)內(nèi)部有空間浪費。第18頁/共111頁第十九頁，編輯于星期一：十五點 三十分。連續(xù)分配 3.可變分區(qū)（Variable Partition）或稱動態(tài)分區(qū)。開始時只有1個空閑分區(qū)，隨著進(jìn)程的裝入和退出，分區(qū)的個數(shù)和每個分區(qū)的大小、位置會動態(tài)變化。第19頁/共111頁第二十頁，編輯于星期一：十五點 三十分?？勺兎謪^(qū)開始OSOSA進(jìn)程A進(jìn)入OSAB進(jìn)程B進(jìn)入OSABC進(jìn)程C進(jìn)入OSADC進(jìn)程D進(jìn)入OSAC進(jìn)程B退出第20頁/共111頁第二十一頁，編輯于星期一：十五點 三十分。可變分區(qū)空閑分區(qū)表/空閑分區(qū)鏈 記錄空閑分區(qū)的起始地址和長度已分配分區(qū)表

10、 （1）分區(qū)管理所需的數(shù)據(jù)結(jié)構(gòu)第21頁/共111頁第二十二頁，編輯于星期一：十五點 三十分。OSP1P2P30K15K38K48K68K80K110K120K空閑分區(qū)表已分配分區(qū)表始址長度狀態(tài)15K23KB未分配48K20KB未分配80K30KB未分配空空始址長度進(jìn)程38K10KBP168K12KBP2110K10KBP3空空第22頁/共111頁第二十三頁，編輯于星期一：十五點 三十分。OSP1P2P30K15K38K48K68K80K110K120K空閑分區(qū)表已分配分區(qū)表始址長度狀態(tài)15K23KB未分配48K20KB未分配98K12KB未分配空空始址長度進(jìn)程38K10KBP168K12KBP

11、2110K10KBP380K 5KBP485K13KBP5P485KP598K第23頁/共111頁第二十四頁，編輯于星期一：十五點 三十分?？勺兎謪^(qū)（2）分區(qū)分配算法 最先適配法（first fit） 空閑分區(qū)鏈（表）按地址遞增的次序排列 從頭開始，選擇第1個大小足夠的分區(qū) 下次適配法（next fit） 從上次分配的分區(qū)的下一個開始，選擇第1個大小足夠的分區(qū)第24頁/共111頁第二十五頁，編輯于星期一：十五點 三十分。分區(qū)分配算法 最佳適配法（best fit） 空閑分區(qū)鏈（表）按大小遞增的次序排列 從頭開始，選擇第1個大小足夠的分區(qū) 最差適配法（worst fit） 空閑分區(qū)鏈（表）按大小

12、遞減的次序排列 從頭開始，選擇第1個分區(qū)（如果足夠大）第25頁/共111頁第二十六頁，編輯于星期一：十五點 三十分?？勺兎謪^(qū)（3）分區(qū)的回收 將回收的分區(qū)插入到空閑分區(qū)鏈（表）的合適位置 合并相鄰的多個空閑分區(qū) 考慮：上鄰、下鄰、上下相鄰、上下不相鄰考慮：上鄰、下鄰、上下相鄰、上下不相鄰存在一個問題：外部碎片（External fragmentation） 經(jīng)過一段時間的分配和回收后，內(nèi)存中存在很多很小的空閑分區(qū)。它們每一個都很小，不足以滿足分配要求，但其總和滿足分配要求。這些空閑塊被稱為碎片，造成存儲資源的浪費。第26頁/共111頁第二十七頁，編輯于星期一：十五點 三十分。可變分區(qū)（4）如何

13、解決碎片問題？內(nèi)存緊湊（compaction）：集中小碎片為大分區(qū)OSABC10KB30KB14KBOSABC54KB緊湊涉及到程序在內(nèi)存中的移動，開銷很大。第27頁/共111頁第二十八頁，編輯于星期一：十五點 三十分。可變分區(qū)為什么會產(chǎn)生大量碎片而難以利用呢？根本原因是：連續(xù)分配。如果把程序分成幾部分裝入不同分區(qū)呢？引入離散分配：分頁分段段頁式（分段 + 分頁）第28頁/共111頁第二十九頁，編輯于星期一：十五點 三十分。4.3 實存儲器管理二、分頁（Paging，靜態(tài)頁式管理） 1.基本原理（1）等分內(nèi)存為物理塊（或稱頁面，頁框，page frame） 物理塊編號為0，1，2，。（2）進(jìn)程

14、的邏輯地址空間分頁（page） 頁大小 = 物理塊大小 頁編號為0，1，2，。（3）內(nèi)存分配原則： 進(jìn)程的1頁可裝入任一物理塊第29頁/共111頁第三十頁，編輯于星期一：十五點 三十分。分頁進(jìn)程的最后1頁可能裝不滿，產(chǎn)生“頁內(nèi)碎片”。分頁類似于固定分區(qū)，但不同之處在于： 1）頁比較小，且大小相等； 2）一個進(jìn)程可占據(jù)多頁，且不要求連續(xù)。進(jìn)程的邏輯地址如何構(gòu)成？為實現(xiàn)分頁管理，OS需要記錄什么信息？如何實現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換？第30頁/共111頁第三十一頁，編輯于星期一：十五點 三十分。分頁 2.管理需要的數(shù)據(jù)結(jié)構(gòu)OS為每個進(jìn)程建立1個頁表（Page Table）記錄進(jìn)程的頁號和物理塊號的

15、對應(yīng)關(guān)系第31頁/共111頁第三十二頁，編輯于星期一：十五點 三十分。.01234560123456進(jìn)程的地址空間物理塊號頁號頁表內(nèi)存中的物理塊第32頁/共111頁第三十三頁，編輯于星期一：十五點 三十分。分頁 3.地址變換邏輯地址 物理地址（1）頁表寄存器（Page Table Register, PTR） 系統(tǒng)設(shè)置1個頁表寄存器，存放當(dāng)前進(jìn)程的頁表起始地址和長度 每個進(jìn)程的頁表起始地址和長度平時放在其PCB中，調(diào)度時由OS放入PTR第33頁/共111頁第三十四頁，編輯于星期一：十五點 三十分。分頁（2）頁大小的選擇頁小：碎片小，但頁表占用空間大頁大：頁表小，但頁內(nèi)碎片大通常，頁的大小為2的

16、整數(shù)次冪（3）進(jìn)程的邏輯地址結(jié)構(gòu)地址的高位部分為頁號，低位部分為頁內(nèi)地址1201131頁號p頁內(nèi)地址d（4）基本的地址變換第34頁/共111頁第三十五頁，編輯于星期一：十五點 三十分。p頁表地址越界 頁表長度Lp=LY 頁表起始地址b+頁號p 頁內(nèi)地址dpd物理地址頁表寄存器邏輯地址Nbp物理塊號分頁第35頁/共111頁第三十六頁，編輯于星期一：十五點 三十分。分頁邏輯地址空間page0page1page2page3頁表1437頁號0123塊號0123物理地址空間page0page2page1page345678【例】設(shè)邏輯地址是16位，頁大小為 1KB = 1024B，即第0-9位是頁內(nèi)地址

17、，第10-15位是頁號。已知邏輯地址05DEH，即0000010111011110B，物理地址為：11DEH，即0001000111011110B因為頁號 = 1，對應(yīng)的物理塊號 = 4物理地址 = 塊號頁大小 + 頁內(nèi)地址第36頁/共111頁第三十七頁，編輯于星期一：十五點 三十分。基本的地址變換CPU要存取一個數(shù)據(jù)時，需要訪問內(nèi)存幾次？2次。n 第1次：訪問頁表，找到該頁對應(yīng)的物理塊號，將此塊號與頁內(nèi)地址拼接形成物理地址；n 第2次：訪問該物理地址，存取其中的指令或數(shù)據(jù)。第37頁/共111頁第三十八頁，編輯于星期一：十五點 三十分。分頁（5）引入快表的地址變換快表，又稱聯(lián)想存儲器(Asso

18、ciative Memory) ： 具有并行查找能力的特殊高速緩沖存儲器（cache）。在80 x86系統(tǒng)中叫做TLB（Translation lookaside buffers）用途：保存當(dāng)前進(jìn)程的頁表的子集（部分表項），比如最近訪問過的頁表項。 當(dāng)切換到新進(jìn)程時，快表要刷新。目的：提高地址變換速度第38頁/共111頁第三十九頁，編輯于星期一：十五點 三十分。pp快表p頁表地址越界 頁表長度Lp=LY 頁表起始地址b+頁號p 頁內(nèi)地址dpd物理地址頁表寄存器邏輯地址Nbp物理塊號分頁第39頁/共111頁第四十頁，編輯于星期一：十五點 三十分。分頁快表表項： 頁號：進(jìn)程訪問過的地址空間的頁號

19、塊號：該頁所對應(yīng)的物理塊號 訪問位：指示該頁最近是否被訪問過（0：沒有被訪問，1：訪問過） 狀態(tài)位：該快表項是否被占用（0：空閑，1：占用）為了保證快表中的內(nèi)容為現(xiàn)正運(yùn)行程序的頁表內(nèi)容，在每個進(jìn)程被選中時，由恢復(fù)現(xiàn)場程序把快表的所有狀態(tài)位清0，或恢復(fù)已保存的快表內(nèi)容。第40頁/共111頁第四十一頁，編輯于星期一：十五點 三十分。分頁具有快表的地址變換過程：當(dāng)進(jìn)程訪問一頁時，系統(tǒng)將頁號與快表中的所有項進(jìn)行并行比較。若訪問的頁在快表中，即可取得塊號，生成物理地址。 當(dāng)被訪問的頁不在快表中時，就要根據(jù)頁號查內(nèi)存中的頁表，找到對應(yīng)的物理塊號，生成物理地址。同時將頁號與塊號填入快表中，若快表已滿，則置換

20、其中訪問位為0的一項。說明： 由于成本的關(guān)系，快表不能太大；引入快表的效果，取決于快表訪問時的命中率(hit ratio)。第41頁/共111頁第四十二頁，編輯于星期一：十五點 三十分。問題：頁表可能占用相當(dāng)大的內(nèi)存空間，而且是連續(xù)的。分頁1201131頁號p頁內(nèi)地址d每個進(jìn)程最多可達(dá)到220（1M）個頁頁表占用的內(nèi)存空間 = 4MB設(shè)每個頁表項占4B，頁表最多可占用的內(nèi)存空間是多少？如何解決？第42頁/共111頁第四十三頁，編輯于星期一：十五點 三十分。（1）基本原理將頁表進(jìn)行分頁，頁大小 = 物理塊大小設(shè)置1個一級頁表，多個二級頁表 一級頁表：第i項記錄第i號二級頁表所在的物理塊號 二級頁

21、表：第i項記錄第i頁對應(yīng)的物理塊號系統(tǒng)設(shè)置個頁表寄存器，存放一級頁表的起始地址和長度（2）進(jìn)程的邏輯地址結(jié)構(gòu)：二級頁表2202131一級頁號p1頁內(nèi)地址d11二級頁號p212 4.二級頁表第43頁/共111頁第四十四頁，編輯于星期一：十五點 三十分。二級頁表一級頁表二級頁表內(nèi)存空間第44頁/共111頁第四十五頁，編輯于星期一：十五點 三十分。（3）地址變換二級頁表邏輯地址一級頁號p1頁內(nèi)地址d二級頁號p2一級頁表起始地址頁表寄存器p1一級頁表+p二級頁表+pd物理地址第45頁/共111頁第四十六頁，編輯于星期一：十五點 三十分。說明：（1）二級頁表并未減少頁表所占的內(nèi)存空間，但解決了頁表的離散

22、分配問題；（2）對于32位地址，采用二級頁表是可以的。如果是64位地址呢？ 需要三級甚至更多級的頁表。二級頁表第46頁/共111頁第四十七頁，編輯于星期一：十五點 三十分。4.3 實存儲器管理三、分段（Segmentation，靜態(tài)段式管理） 1.基本原理（1）進(jìn)程的邏輯地址空間分段（segment）： 按程序自身的邏輯關(guān)系劃分為若干個程序段 每一個段是連續(xù)的 各個段的長度不要求相等 段號從0開始。（2）內(nèi)存分配原則： 以段為單位，各段不要求相鄰。第47頁/共111頁第四十八頁，編輯于星期一：十五點 三十分。分段分段類似于可變分區(qū)，但不同之處在于： 一個進(jìn)程可占據(jù)多個分區(qū)，而且分區(qū)之間不要求連

23、續(xù)。分段無內(nèi)部碎片，但有外部碎片。進(jìn)程的邏輯地址如何構(gòu)成？為實現(xiàn)分段管理，OS需要記錄什么信息？如何實現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換？第48頁/共111頁第四十九頁，編輯于星期一：十五點 三十分。分段 2.管理需要的數(shù)據(jù)結(jié)構(gòu)OS為每個進(jìn)程建立1個段表（Segment Table）每個段在段表中有1項，記錄該段在內(nèi)存中的基址和長度段號012段基址段長度58K20K100K110K260K140K第49頁/共111頁第五十頁，編輯于星期一：十五點 三十分。操作系統(tǒng).B0SA0NY0LX0PM0K段號01234進(jìn)程的地址空間15003200500060008000PKSLN內(nèi)存K 3200P 1500L

24、 6000N 8000S 5000長度 段基址01234操作系統(tǒng)第50頁/共111頁第五十一頁，編輯于星期一：十五點 三十分。分段 3.地址變換（1）段表寄存器 系統(tǒng)設(shè)置1個段表寄存器，存放當(dāng)前進(jìn)程的段表起始地址和長度 每個進(jìn)程的段表起始地址和長度平時放在其PCB中（2）進(jìn)程的邏輯地址結(jié)構(gòu)地址的高位部分為段號，低位部分為段內(nèi)地址1201131段號s 段內(nèi)地址w（3）基本的地址變換第51頁/共111頁第五十二頁，編輯于星期一：十五點 三十分。 段表長度L 段表起始地址b+段號s 段內(nèi)地址dbs + d段表s= L物理地址段表寄存器邏輯地址段長Ls基址 bsY地址越界地址越界YNd=LsN分段第5

25、2頁/共111頁第五十三頁，編輯于星期一：十五點 三十分。分段【例】設(shè)邏輯地址是16位，段號占4位，段內(nèi)地址占12位。已知邏輯地址12f0h，即0001001011110000b，物理地址為：2310h段號 =1， 段基址 = 2020h，段內(nèi)地址 = 2f0h基址1000h2020h4000h6300h段號01233k4k4k2k長度段表第53頁/共111頁第五十四頁，編輯于星期一：十五點 三十分?；镜牡刂纷儞QCPU要存取一個數(shù)據(jù)時，需要訪問2次內(nèi)存。n第1次：訪問段表，找到該段的基址，將基址與段內(nèi)地址相加形成物理地址；n第2次：訪問該物理地址，存取其中的指令或數(shù)據(jù)。第54頁/共111頁第

26、五十五頁，編輯于星期一：十五點 三十分。分段（4）引入快表的地址變換快表表項： 段號 段基址 段長度 訪問位 狀態(tài)位第55頁/共111頁第五十六頁，編輯于星期一：十五點 三十分。 段表長度L 段表起始地址b+段號s 段內(nèi)地址dbs + d段表s= L快表物理地址段表寄存器邏輯地址段長 LS基址 bs. sLSbs地址越界d=LSY地址越界地址越界YNd=LSNYN分段第56頁/共111頁第五十七頁，編輯于星期一：十五點 三十分。分段 4.分段與分頁的比較（1）分頁對程序員是不可見的；分段通常是可見的，并作為組織程序和數(shù)據(jù)的手段提供給程序員；（2）頁的大小由系統(tǒng)確定，段的大小由用戶程序確定；（3

27、）分段更利于多個進(jìn)程共享程序和數(shù)據(jù)；（4）分段便于實現(xiàn)動態(tài)鏈接。（5）分頁可有效提高內(nèi)存利用率，分段可更好地滿足用戶需要。如果把分段和分頁結(jié)合起來呢？第57頁/共111頁第五十八頁，編輯于星期一：十五點 三十分。4.3 實存儲器管理四、段頁式管理（分段 + 分頁） 動機(jī)：結(jié)合分段和分頁的優(yōu)點，克服二者的缺點。 1.基本原理（1）進(jìn)程分段：同段式管理 每段分頁，內(nèi)存分塊，內(nèi)存以塊為單位分配：同頁式管理（2）進(jìn)程的邏輯地址結(jié)構(gòu) 由段號、頁號和頁內(nèi)地址構(gòu)成。段號s 頁內(nèi)地址d 段內(nèi)頁號p第58頁/共111頁第五十九頁，編輯于星期一：十五點 三十分。段頁式管理 2.管理需要的數(shù)據(jù)結(jié)構(gòu) 每個進(jìn)程1個段表

28、 記錄每個段對應(yīng)的頁表起始地址和長度 每個段有1個頁表 記錄該段所有頁號與物理塊號的對應(yīng)關(guān)系第59頁/共111頁第六十頁，編輯于星期一：十五點 三十分。 3.地址變換（1）段表寄存器 系統(tǒng)設(shè)置1個段表寄存器，存放當(dāng)前進(jìn)程的段表起始地址和長度 每個進(jìn)程的段表起始地址和長度平時放在其PCB中（2）基本的地址變換段頁式管理CPU要存取一個數(shù)據(jù)時，需要訪問3次內(nèi)存。n第1次：訪問段表，獲得該段的頁表地址；n第2次：訪問頁表，取得物理塊號，形成物理地址；n第3次：訪問該物理地址，存取其中的指令或數(shù)據(jù)。第60頁/共111頁第六十一頁，編輯于星期一：十五點 三十分。（4）引入快表的地址變換快表表項： 段號

29、頁號 物理塊號 訪問位 狀態(tài)位 同時利用段號與頁號查找相應(yīng)的物理塊號。段頁式管理第61頁/共111頁第六十二頁，編輯于星期一：十五點 三十分。pp快表 段表長度L 段表起始地址b+段號s 頁號p 頁內(nèi)地址dpd物理地址段表寄存器邏輯地址p頁表段表頁表長度LS頁表地址 bss+地址變換圖中省略了地址越界檢查第62頁/共111頁第六十三頁，編輯于星期一：十五點 三十分。4.3 實存儲器管理五、覆蓋 基本原理：（1）把程序劃分為若干個功能上相對獨立的程序段（稱為覆蓋塊），按照其自身的邏輯結(jié)構(gòu)使那些不會同時執(zhí)行的程序段共享同一塊內(nèi)存區(qū)域；（2）覆蓋塊存放在磁盤上，當(dāng)一個程序段執(zhí)行結(jié)束，把后續(xù)程序段調(diào)入

30、內(nèi)存，覆蓋前面的程序段（內(nèi)存“擴(kuò)大”了）第63頁/共111頁第六十四頁，編輯于星期一：十五點 三十分。A20KBE20KBF40KBC30KBB50KBD30KB程序P的調(diào)用結(jié)構(gòu)程序P的常駐區(qū) A（20KB）覆蓋區(qū)0（50KB）覆蓋區(qū)1（40KB） CB F E D覆蓋第64頁/共111頁第六十五頁，編輯于星期一：十五點 三十分。覆蓋第65頁/共111頁第六十六頁，編輯于星期一：十五點 三十分。4.4 虛擬存儲管理一、虛擬存儲器（Virtual Memory） 1.基本思想 進(jìn)程的大小可以超過可用物理內(nèi)存的大小，由OS把當(dāng)前用到的那部分留在內(nèi)存，其余的放在外存中。 2.幾個概念 虛擬地址：程序

31、中使用的地址。進(jìn)程的虛擬地址從0開始。 物理地址：可尋址的內(nèi)存實際地址 虛擬地址空間：虛擬地址的集合 物理地址空間：實際的內(nèi)存空間第66頁/共111頁第六十七頁，編輯于星期一：十五點 三十分。虛擬存儲器 3.交換（Swapping）技術(shù)借助于外存（磁盤），將當(dāng)前要使用的那部分程序或數(shù)據(jù)裝入內(nèi)存，將暫時不需要的放在磁盤上，待需要時再裝入。交換：進(jìn)程的整體或一部分的換入/換出。換入：從磁盤移入內(nèi)存換出：從內(nèi)存移出到磁盤交換是實現(xiàn)虛擬存儲器的基礎(chǔ)。最初的交換是針對整個進(jìn)程的交換。第67頁/共111頁第六十八頁，編輯于星期一：十五點 三十分。交換技術(shù)（1）交換區(qū)（交換空間）的概念 磁盤上為虛擬內(nèi)存保留

32、的區(qū)域，稱為交換區(qū)或交換空間。（2）交換區(qū)的實現(xiàn)方式 交換分區(qū)，或稱交換設(shè)備 交換文件，用于交換的有固定長度的文件（3）交換區(qū)的分配方式 進(jìn)程創(chuàng)建時分配：每次換出在同一個地方 換出時分配：首次換出時分配，以后換出在同一個地方；或者每次換出在不同地方。第68頁/共111頁第六十九頁，編輯于星期一：十五點 三十分。虛擬存儲器 4.虛擬存儲器的特征 邏輯上擴(kuò)充了內(nèi)存容量，對于用戶程序來說，仿佛內(nèi)存“無限大”。只不過有時慢一點而已。 5.虛擬存儲管理的實現(xiàn)方案 分頁 + 虛擬存儲技術(shù) 分段 + 虛擬存儲技術(shù) 段頁式 + 虛擬存儲技術(shù)第69頁/共111頁第七十頁，編輯于星期一：十五點 三十分。4.4 虛

33、擬存儲管理二、虛擬頁式管理（動態(tài)頁式管理） 1.基本思想 在進(jìn)程開始運(yùn)行之前，不是裝入全部頁，而是裝入部分或0個頁，之后根據(jù)進(jìn)程運(yùn)行的需要，動態(tài)裝入其它頁；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁時，則根據(jù)某種算法淘汰某個頁，以便裝入新的頁。第70頁/共111頁第七十一頁，編輯于星期一：十五點 三十分。虛擬頁式管理 2.頁表項內(nèi)容的擴(kuò)充除了頁號和物理塊號外，需要增加下列字段： 有效位（狀態(tài)）：表示該頁是否在內(nèi)存中 訪問位A（訪問字段）：記錄該頁最近是否被訪問過 修改位M：表示該頁在裝入內(nèi)存后是否被修改過 外存地址：該頁在磁盤上的地址第71頁/共111頁第七十二頁，編輯于星期一：十五點 三十分。 3.

34、地址變換 虛擬地址 物理地址 類似于靜態(tài)頁式管理。由于訪問的頁p可能不在內(nèi)存中，因而引出以下幾個問題： 缺頁中斷處理 頁的換入/換出虛擬頁式管理第72頁/共111頁第七十三頁，編輯于星期一：十五點 三十分。（1）缺頁中斷（Page Fault）處理在地址變換的過程中，當(dāng)訪問頁表時，若根據(jù)狀態(tài)位發(fā)現(xiàn)所訪問的頁不在內(nèi)存，則產(chǎn)生缺頁中斷。 缺頁中斷處理： 保護(hù)當(dāng)前進(jìn)程現(xiàn)場； 根據(jù)頁表中給出的外存地址，在外存中找到該頁； 若內(nèi)存中無空閑物理塊，則選擇1頁換出； 分配一個空閑物理塊，將新調(diào)入頁裝入內(nèi)存； 修改頁表中相應(yīng)表項的狀態(tài)位及相應(yīng)的物理塊號，修改空閑物理塊表（鏈）； 恢復(fù)現(xiàn)場。虛擬頁式管理第73頁

35、/共111頁第七十四頁，編輯于星期一：十五點 三十分。（2）頁的換入/換出1）頁的分配策略：為每個進(jìn)程分配多少個物理塊 固定分配 為每個進(jìn)程分配的總物理塊數(shù)固定，在整個運(yùn)行期間不變。 可變分配 先為每個進(jìn)程分配一定數(shù)目的物理塊，OS自身維持一個空閑物理塊隊列。當(dāng)發(fā)生缺頁時，由系統(tǒng)分配一個空閑塊，存入調(diào)入的頁；當(dāng)無空閑塊時，才會換出。虛擬頁式管理第74頁/共111頁第七十五頁，編輯于星期一：十五點 三十分。2）頁的置換策略：在什么范圍內(nèi)選擇淘汰頁 全局置換 從整個內(nèi)存中選擇淘汰頁 局部置換 只從缺頁進(jìn)程自身選擇淘汰頁頁的換入/換出第75頁/共111頁第七十六頁，編輯于星期一：十五點 三十分。3）

36、頁的調(diào)入策略 何時調(diào)入 請求調(diào)頁（demand paging） 只有訪問的頁不在內(nèi)存中時，才會調(diào)入該頁。 預(yù)調(diào)頁（prepaging） 一次調(diào)入多個連續(xù)的頁。為什么這樣做？ 從何處調(diào)入：文件區(qū)（可執(zhí)行文件）、交換區(qū) 全部從交換區(qū)調(diào)入 進(jìn)程創(chuàng)建時，全部從文件區(qū)拷貝到交換區(qū)。 首次調(diào)入從文件區(qū)，以后從交換區(qū)頁的換入/換出第76頁/共111頁第七十七頁，編輯于星期一：十五點 三十分。 4.頁的置換算法（Page Replacement Algorithm）作用：選擇換出頁目的：減少缺頁率思路：以過去預(yù)測未來虛擬頁式管理第77頁/共111頁第七十八頁，編輯于星期一：十五點 三十分。（1）最優(yōu)置換算法（

37、Optimal, OPT）頁的置換算法淘汰以后永不使用的，或者過最長的時間后才會被訪問的頁。這是Belady于1966年提出的一種理論上的算法。顯然，采用這種算法會保證最低的缺頁率，但無法實現(xiàn)，因為它必須知道“將來”的訪問情況。因此，該算法只是作為衡量其他算法優(yōu)劣的一個標(biāo)準(zhǔn)。第78頁/共111頁第七十九頁，編輯于星期一：十五點 三十分。（2）先進(jìn)先出置換算法（First In First Out, FIFO）頁的置換算法淘汰最早進(jìn)入內(nèi)存的頁。實現(xiàn)方法： 只需把進(jìn)程中已調(diào)入內(nèi)存的頁，按先后次序鏈成一個隊列即可。優(yōu)點：開銷較小，實現(xiàn)簡單。缺點： 它與進(jìn)程訪問內(nèi)存的動態(tài)特性不相適應(yīng)； 會產(chǎn)生bela

38、dy現(xiàn)象。即：當(dāng)分配給進(jìn)程的物理塊數(shù)增加時，有時缺頁次數(shù)反而增加。第79頁/共111頁第八十頁，編輯于星期一：十五點 三十分。先進(jìn)先出置換算法【例】設(shè)系統(tǒng)為某進(jìn)程在內(nèi)存中固定分配m個物理塊，初始為空，進(jìn)程訪問頁的走向為1，2，3，4，1，2，5，1，2，3，4，5。采用FIFO算法，當(dāng)m=3，m=4時，缺頁次數(shù)分別是多少？m=3時，缺頁次數(shù)：9次m=4時，缺頁次數(shù)：10次產(chǎn)生Belady現(xiàn)象第80頁/共111頁第八十一頁，編輯于星期一：十五點 三十分。（3）最近最久未使用算法（Least Recently Used, LRU）頁的置換算法淘汰最近一次訪問距當(dāng)前時間最長的頁。即淘汰未使用時間最長

39、的頁關(guān)鍵：如何快速地判斷出哪一頁是最近最久未使用的。算法較好，但實現(xiàn)代價高。第81頁/共111頁第八十二頁，編輯于星期一：十五點 三十分。LRU算法實現(xiàn)方法：1）計時器 對于每一頁增設(shè)一個訪問時間計時器 每當(dāng)某頁被訪問時，當(dāng)時的絕對時鐘內(nèi)容被拷貝到對應(yīng)的訪問時間計時器中，這樣系統(tǒng)記錄了內(nèi)存中所有頁最后一次被訪問的時間。 淘汰時，選取訪問時間計時器值最小的頁。2）移位寄存器 為內(nèi)存中的每一頁配置一個移位寄存器 當(dāng)訪問某頁時，將相應(yīng)移位寄存器的最高位置1 每隔一定時間，寄存器右移1位 淘汰寄存器值最小的頁。第82頁/共111頁第八十三頁，編輯于星期一：十五點 三十分。LRU算法實現(xiàn)方法3）棧 每次

40、訪問某頁時，將其頁號移到棧頂。使得棧頂始終是最近被訪問的頁，棧底是最近最久未用的?！纠吭O(shè)一進(jìn)程所訪問的頁號順序為 4, 7, 0, 7, 1, 0, 1, 2, 1, 2, 6設(shè)給該進(jìn)程固定分配5個物理塊，則棧中頁號的變化情況如下：第83頁/共111頁第八十四頁，編輯于星期一：十五點 三十分。LRU算法實現(xiàn)方法當(dāng)訪問頁6時，發(fā)生缺頁，淘汰處于棧底的頁4。 2 1 2 6 1 0 1 1 2 1 2 0 7 7 1 0 0 0 0 1 7 7 0 0 7 7 7 7 7 0 4 4 4 4 4 4 4 4 4 4 74，7，0，7，1，0，1，2，1，2，6第84頁/共111頁第八十五頁，編輯

41、于星期一：十五點 三十分。頁的置換算法第85頁/共111頁第八十六頁，編輯于星期一：十五點 三十分。頁的置換算法第86頁/共111頁第八十七頁，編輯于星期一：十五點 三十分。頁的置換算法第87頁/共111頁第八十八頁，編輯于星期一：十五點 三十分。頁的置換算法第88頁/共111頁第八十九頁，編輯于星期一：十五點 三十分。（4）最近未使用算法（Not Recently Used, NRU）頁的置換算法1）簡單的NRU算法頁表中設(shè)置一個訪問位，當(dāng)訪問某頁時，將訪問位置1將內(nèi)存中的所有頁鏈成一個循環(huán)隊列從上次換出頁的下一個位置開始掃描在掃描過程中，將訪問位=1的頁清0，直到遇到訪問位=0的頁，淘汰該

42、頁，并將指針指向下一頁NRU算法是用得較多的LRU的近似算法由于該算法循環(huán)檢查各頁的訪問位，故稱Clock算法。問題：如果考慮頁是否已被修改，選擇什么頁換出好？第89頁/共111頁第九十頁，編輯于星期一：十五點 三十分。頁的置換算法2）改進(jìn)的NRU算法（改進(jìn)的Clock算法）該算法的提出基于如下考慮： 對于已修改的頁，換出時必須重新寫回到磁盤上。因此，優(yōu)先選擇未訪問過、未修改過的頁換出。 淘汰一個最近未訪問的已修改頁要比淘汰一個被頻繁訪問的“干凈”頁好。 第90頁/共111頁第九十一頁，編輯于星期一：十五點 三十分。改進(jìn)的NRU算法基本方法： 設(shè)置1個訪問位A，1個修改位M 按照下列次序選擇淘

43、汰頁：第1類：A = 0，M = 0：未訪問，未修改；最佳淘汰頁第2類：A = 0，M = 1：未訪問，已修改第3類：A = 1，M = 0：已訪問，未修改；有可能再次訪問第4類：A = 1，M = 1：已訪問，已修改第91頁/共111頁第九十二頁，編輯于星期一：十五點 三十分。改進(jìn)的NRU算法實現(xiàn)算法： 找第1類頁，將遇到的第1個頁作為淘汰頁； 若查找1周后未找到第1類頁，則尋找第2類頁，并將掃描經(jīng)過的頁的訪問位清0。將遇到的第1個頁作為淘汰頁； 否則，轉(zhuǎn)、，一定能找到淘汰頁。第92頁/共111頁第九十三頁，編輯于星期一：十五點 三十分。（5）最少使用算法（Least Frequently

44、Used, LFU）頁的置換算法選擇最近訪問次數(shù)最少的頁淘汰。實現(xiàn)方法： 通常不直接利用計數(shù)器來記錄頁的訪問次數(shù)，而是采用移位寄存器R。 類似于LRU算法，每次訪問某頁時，將其移位寄存器的最高位置1。每隔一定時間將移位寄存器右移1位。 這樣，在最近一段時間內(nèi)使用次數(shù)最少的頁就是移位寄存器各位之和最小的頁。 當(dāng)然，這并不能真正反映出頁的訪問次數(shù)。因為，在每一時間間隔內(nèi)，只用1位來記錄頁的訪問情況，訪問1次和100次是等效的。第93頁/共111頁第九十四頁，編輯于星期一：十五點 三十分。（6）頁緩沖算法（Page Buffering Algorithm）頁的置換算法出發(fā)點：與上述算法配合使用，以提

45、高效率?；痉椒ǎ涸O(shè)置2個鏈表：空閑頁鏈表，已修改頁鏈表 若淘汰頁未修改，則直接放入空閑頁鏈表，否則放入已修改頁鏈表； 當(dāng)已修改頁達(dá)到一定數(shù)量時，再將其一起寫回磁盤，即成簇寫回，以減少I/O操作的次數(shù)。第94頁/共111頁第九十五頁，編輯于星期一：十五點 三十分。5.局部性原理（1）程序的局部性特征程序在執(zhí)行過程中的一個較短時期，所執(zhí)行的指令地址和操作數(shù)地址，分別局限于一定區(qū)域。表現(xiàn)在時間與空間兩方面。 時間局部性 一條指令被執(zhí)行了，則在不久的將來它可能再被執(zhí)行；數(shù)據(jù)也類似。例如循環(huán)。 空間局部性 若某一存儲單元被訪問，則在一定時間內(nèi)，與該存儲單元相鄰的單元可能被訪問。如程序的順序結(jié)構(gòu)、數(shù)組的

46、處理。虛擬頁式管理第95頁/共111頁第九十六頁，編輯于星期一：十五點 三十分。（2）程序結(jié)構(gòu)對性能的影響【例】將二維整型數(shù)組a256256的每個元素初始化為0的C語言程序：局部性原理程序1：int a256256;for (i = 0; i 256; i+) for (j = 0; j 256; j+) aij = 0;程序2：int a256256;for (j = 0; j 256; j+) for (i = 0; i 256; i+) aij = 0;假定在分頁系統(tǒng)中，頁的大小為1KB，int類型占4B，設(shè)分配給該程序1個物理塊。這兩個程序哪個好？忽略該程序代碼所占的內(nèi)存空間。程序1好

47、。因為C數(shù)組在內(nèi)存中以行主次序存放，程序1的缺頁次數(shù)是256，程序2的缺頁次數(shù)為256*256=65536。第96頁/共111頁第九十七頁，編輯于星期一：十五點 三十分。缺頁率與程序的行為有關(guān)，因此，在設(shè)計程序時，要力求提高程序訪問的局部性。局部性特征正是虛擬存儲技術(shù)能有效發(fā)揮作用的基礎(chǔ)。局部性原理第97頁/共111頁第九十八頁，編輯于星期一：十五點 三十分。6.抖動（顛簸）虛擬頁式管理 指頁在內(nèi)存與外存之間頻繁換入/換出，以至于調(diào)度頁所需時間比進(jìn)程實際運(yùn)行的時間還多，此時系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰。這種現(xiàn)象稱為顛簸或抖動。導(dǎo)致抖動的原因： 頁置換算法不合理分配給進(jìn)程的物理塊數(shù)太少第9

48、8頁/共111頁第九十九頁，編輯于星期一：十五點 三十分。7.工作集(Working Set)虛擬頁式管理 是由Denning提出并加以推廣的，對于虛擬存儲管理有著深遠(yuǎn)的影響。 一個進(jìn)程在時刻t、參數(shù)為的工作集W(t, )，表示該進(jìn)程在過去的個時間單位中被訪問到的頁的集合。 稱為工作集的窗口大小。 工作集的內(nèi)容取決于三個因素： 訪頁序列特性 時刻t 觀察該進(jìn)程的時間窗口大小()第99頁/共111頁第一百頁，編輯于星期一：十五點 三十分。工作集工作集的基本思想： 根據(jù)程序的局部性原理，一般情況下，進(jìn)程在一段時間內(nèi)總是集中訪問一些頁，這些頁稱為活動頁。 如果分配給一個進(jìn)程的物理塊數(shù)太少了，使該進(jìn)程所需的活動頁不能全部裝入內(nèi)存，則進(jìn)程在運(yùn)行過程中將頻繁發(fā)生缺頁中斷。 如果能為進(jìn)程提供