湯子贏_計算機操作系統(tǒng)課件第4章

1、第四章 存 儲 器 管 理 第四章第四章 存儲器管理存儲器管理 4.1 4.1 程序的裝入和鏈接程序的裝入和鏈接 4.2 4.2 連續(xù)分配方式連續(xù)分配方式 4.3 4.3 基本分頁存儲管理方式基本分頁存儲管理方式 4.4 4.4 基本分段存儲管理方式基本分段存儲管理方式 4.5 4.5 虛擬存儲器的基本概念虛擬存儲器的基本概念 4.6 4.6 請求分頁存儲管理方式請求分頁存儲管理方式 4.7 4.7 頁面置換算法頁面置換算法 4.8 4.8 請求分段存儲管理方式請求分段存儲管理方式 第四章 存 儲 器 管 理 4.1 程序的裝入和鏈接程序的裝入和鏈接 圖 4-1 對用戶程序的處理步驟 庫鏈接程

2、序裝入模塊裝入程序編譯程序產生的目標模塊第一步第二步第三步內存第四章 存 儲 器 管 理 4.1.1 程序的裝入程序的裝入1. 絕對裝入方式絕對裝入方式(Absolute Loading Mode) 程序中所使用的絕對地址，既可在編譯或匯編時給出， 也可由程序員直接賦予。 但在由程序員直接給出絕對地址時， 不僅要求程序員熟悉內存的使用情況，而且一旦程序或數(shù)據被修改后，可能要改變程序中的所有地址。因此，通常是寧可在程序中采用符號地址，然后在編譯或匯編時，再將這些符號地址轉換為絕對地址。 第四章 存 儲 器 管 理 2. 可重定位裝入方式可重定位裝入方式(Relocation Loading Mo

3、de) 圖 4-2 作業(yè)裝入內存時的情況 LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作業(yè)地址空間內存空間第四章 存 儲 器 管 理 3. 動態(tài)運行時裝入方式動態(tài)運行時裝入方式(Denamle Run-time Loading) 動態(tài)運行時的裝入程序，在把裝入模塊裝入內存后，并不立即把裝入模塊中的相對地址轉換為絕對地址，而是把這種地址轉換推遲到程序真正要執(zhí)行時才進行。因此， 裝入內存后的所有地址都仍是相對地址。 第四章 存 儲 器 管 理 4.1.2 程序的鏈接程序的鏈接 1. 靜態(tài)鏈接方式靜態(tài)鏈接方式(Static

4、 Linking) 圖 4-3 程序鏈接示意圖 模塊 ACALL B；Return；0L1模塊 BCALL C；Return；0M1模塊 CReturn；0N10模塊 AJSR“L”Return；L1模塊 BJSR“LM”Return；LLM1LMLMN1模塊 CReturn；(a) 目標模塊(b) 裝入模塊第四章 存 儲 器 管 理 在將這幾個目標模塊裝配成一個裝入模塊時，須解決以下兩個問題： (1) 對相對地址進行修改。 (2) 變換外部調用符號。 第四章 存 儲 器 管 理 2. 裝入時動態(tài)鏈接裝入時動態(tài)鏈接(Loadtime Dynamic Linking) 裝入時動態(tài)鏈接方式有以下優(yōu)

5、點： (1) 便于修改和更新。 (2) 便于實現(xiàn)對目標模塊的共享。 第四章 存 儲 器 管 理 3. 運行時動態(tài)鏈接運行時動態(tài)鏈接(Run-time Dynamic Linking) 近幾年流行起來的運行時動態(tài)鏈接方式，是對上述在裝入時鏈接方式的一種改進。這種鏈接方式是將對某些模塊的鏈接推遲到執(zhí)行時才執(zhí)行，亦即，在執(zhí)行過程中，當發(fā)現(xiàn)一個被調用模塊尚未裝入內存時，立即由OS去找到該模塊并將之裝入內存， 把它鏈接到調用者模塊上。凡在執(zhí)行過程中未被用到的目標模塊，都不會被調入內存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內存空間。 第四章 存 儲 器 管 理 4.2 連續(xù)分

6、配方式連續(xù)分配方式4.2.1 單一連續(xù)分配單一連續(xù)分配 這是最簡單的一種存儲管理方式，但只能用于單用戶、單任務的操作系統(tǒng)中。采用這種存儲管理方式時，可把內存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內存空間， 提供給用戶使用。 第四章 存 儲 器 管 理 4.2.2 固定分區(qū)分配固定分區(qū)分配 1. 劃分分區(qū)的方法劃分分區(qū)的方法 (1) 分區(qū)大小相等， 即使所有的內存分區(qū)大小相等。 (2) 分區(qū)大小不等。 第四章 存 儲 器 管 理 2. 內存分配內存分配 圖 4-4 固定分區(qū)使用表 第四章 存 儲 器 管 理 4.2.3 動態(tài)分區(qū)分

7、配動態(tài)分區(qū)分配 1. 分區(qū)分配中的數(shù)據結構分區(qū)分配中的數(shù)據結構 (1) 空閑分區(qū)表。 (2) 空閑分區(qū)鏈。 圖 4-5 空閑鏈結構 前向指針N20N個字節(jié)可用后向指針N20第四章 存 儲 器 管 理 2. 分區(qū)分配算法分區(qū)分配算法 (1) 首次適應算法FF。 (2) 循環(huán)首次適應算法，該算法是由首次適應算法演變而成的。(3) 最佳適應算法。 第四章 存 儲 器 管 理 3. 分區(qū)分配操作分區(qū)分配操作 1) 分配內存 從頭開始查表檢索完否？m.sizeu.size?m.sizeu.sizesize?從該分區(qū)中劃出u.size大小的分區(qū)將該分區(qū)分配給請求者修改有關數(shù)據結構返回返回繼續(xù)檢索下一個表項

8、將該分區(qū)從鏈中移出YNNYYN圖 4-6 內存分配流程第四章 存 儲 器 管 理 2) 回收內存 圖 4-7 內存回收時的情況 第四章 存 儲 器 管 理 4.2.4 可重定位分區(qū)分配可重定位分區(qū)分配 1. 動態(tài)重定位的引入動態(tài)重定位的引入 圖 4-8 緊湊的示意 操作系統(tǒng)用戶程序1用戶程序310 KB30 KB用戶程序614 KB用戶程序926 KB操作系統(tǒng)用戶程序1用戶程序3用戶程序6用戶程序980 KB(a) 緊湊前(b) 緊湊后第四章 存 儲 器 管 理 2. 動態(tài)重定位的實現(xiàn)動態(tài)重定位的實現(xiàn) 圖 4-9 動態(tài)重定位示意圖 LOAD1,25003650100250050002500相對

9、地址10000重定位寄存器LOAD1,250036510000101001250015000作業(yè)J處理機一側 存儲器一側主存第四章 存 儲 器 管 理 3. 動態(tài)重定位分區(qū)分配算法動態(tài)重定位分區(qū)分配算法 圖 4-10 動態(tài)分區(qū)分配算法流程圖 請求分配u.size分區(qū)檢索空閑分區(qū)鏈(表)找到大于u.size的可用區(qū)否?按動態(tài)分區(qū)方式進行分配修改有關的數(shù)據結構返回分區(qū)號及首批空閑分區(qū)總和u.size?進行緊湊形成連續(xù)空閑區(qū)修改有關的數(shù)據結構否是無法分配返回否第四章 存 儲 器 管 理 4.2.5 對換對換(Swapping) 1. 對換的引入對換的引入 所謂“對換”， 是指把內存中暫時不能運行的進

10、程或者暫時不用的程序和數(shù)據，調出到外存上，以便騰出足夠的內存空間，再把已具備運行條件的進程或進程所需要的程序和數(shù)據，調入內存。對換是提高內存利用率的有效措施。 第四章 存 儲 器 管 理 2. 對換空間的管理對換空間的管理 為了能對對換區(qū)中的空閑盤塊進行管理，在系統(tǒng)中應配置相應的數(shù)據結構，以記錄外存的使用情況。其形式與內存在動態(tài)分區(qū)分配方式中所用數(shù)據結構相似，即同樣可以用空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表中的每個表目中應包含兩項， 即對換區(qū)的首址及其大小，它們的單位是盤塊號和盤塊數(shù)。 第四章 存 儲 器 管 理 3. 進程的換出與換入進程的換出與換入 (1) 進程的換出。 每當一進程由于創(chuàng)建

11、子進程而需要更多的內存空間，但又無足夠的內存空間等情況發(fā)生時，系統(tǒng)應將某進程換出。 其過程是：系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級最低的進程作為換出進程，然后啟動盤塊，將該進程的程序和數(shù)據傳送到磁盤的對換區(qū)上。若傳送過程未出現(xiàn)錯誤，便可回收該進程所占用的內存空間，并對該進程的進程控制塊做相應的修改。 第四章 存 儲 器 管 理 (2) 進程的換入。 系統(tǒng)應定時地查看所有進程的狀態(tài)，從中找出“就緒”狀態(tài)但已換出的進程，將其中換出時間(換出到磁盤上)最久的進程作為換入進程，將之換入，直至已無可換入的進程或無可換出的進程為止。 第四章 存 儲 器 管 理 4.3 基本分頁存儲管理方式基本分頁存儲管理方式

12、 4.3.1 頁面與頁表頁面與頁表 1. 頁面頁面 1) 頁面和物理塊 分頁存儲管理，是將一個進程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁，并為各頁加以編號，從0開始，如第0頁、第1頁等。相應地，也把內存空間分成與頁面相同大小的若干個存儲塊，稱為(物理)塊或頁框(frame)， 也同樣為它們加以編號，如0塊、1塊等等。在為進程分配內存時，以塊為單位將進程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中。由于進程的最后一頁經常裝不滿一塊而形成了不可利用的碎片，稱之為“頁內碎片”。 第四章 存 儲 器 管 理 2) 頁面大小 在分頁系統(tǒng)中的頁面其大小應適中。頁面若太小，一方面雖然可使內存

13、碎片減小，從而減少了內存碎片的總空間， 有利于提高內存利用率，但另一方面也會使每個進程占用較多的頁面，從而導致進程的頁表過長，占用大量內存； 此外，還會降低頁面換進換出的效率。然而，如果選擇的頁面較大，雖然可以減少頁表的長度，提高頁面換進換出的速度，但卻又會使頁內碎片增大。因此，頁面的大小應選擇得適中，且頁面大小應是2的冪，通常為512 B8 KB。 第四章 存 儲 器 管 理 2. 地址結構地址結構 分頁地址中的地址結構如下： 頁號P位移量W3112110 對某特定機器，其地址結構是一定的。若給定一個邏輯地址空間中的地址為A，頁面的大小為L，則頁號P和頁內地址d可按下式求得： MODLAdL

14、AINTP第四章 存 儲 器 管 理 3. 頁表頁表 圖 4-11 頁表的作用 用戶程序0 頁1 頁2 頁3 頁4 頁5 頁n 頁頁表頁號塊號02132638495內存012345678910第四章 存 儲 器 管 理 4.3.2 地址變換機構地址變換機構 1. 基本的地址變換機構基本的地址變換機構 圖 4-12 分頁系統(tǒng)的地址變換機構 頁表寄存器頁表始址頁表長度頁號(3)頁內地址邏輯地址L越界中斷1塊號b頁表頁號012物理地址3第四章 存 儲 器 管 理 2. 具有快表的地址變換機構具有快表的地址變換機構 圖 4-13 具有快表的地址變換機構 頁表寄存器頁表始址頁表長度頁號頁內地址邏輯地址L

15、越界中斷塊號b頁表頁號頁號輸入寄存器塊號bb快表d物理地址第四章 存 儲 器 管 理 4.3.3 兩級和多級頁表兩級和多級頁表 現(xiàn)代的大多數(shù)計算機系統(tǒng)，都支持非常大的邏輯地址空間(232264)。在這樣的環(huán)境下，頁表就變得非常大，要占用相當大的內存空間。例如，對于一個具有32位邏輯地址空間的分頁系統(tǒng)，規(guī)定頁面大小為4 KB即212 B，則在每個進程頁表中的頁表項可達1兆個之多。又因為每個頁表項占用一個字節(jié)， 故每個進程僅僅其頁表就要占用4 KB的內存空間，而且還要求是連續(xù)的。 可以采用這樣兩個方法來解決這一問題： 采用離散分配方式來解決難以找到一塊連續(xù)的大內存空間的問題： 只將當前需要的部分頁

16、表項調入內存， 其余的頁表項仍駐留在磁盤上，需要時再調入。 第四章 存 儲 器 管 理 1. 兩級頁表兩級頁表(Two-Level Page Table) 邏輯地址結構可描述如下： 第四章 存 儲 器 管 理 圖 4-14 兩級頁表結構 101110780121742n第0頁頁表1460121023第1頁頁表114115011023外部頁表012345671141151468第n頁頁存空間第四章 存 儲 器 管 理 圖 4-15 具有兩級頁表的地址變換機構 外部頁號P1P2外部頁內地址頁內地址d邏輯地址外部頁表寄存器外部頁表db頁表頁表物理地址第四章 存 儲 器 管

17、理 2. 多級頁表多級頁表 對于32位的機器，采用兩級頁表結構是合適的；但對于64位的機器，如果頁面大小仍采用4 KB即212 B，那么還剩下52位， 假定仍按物理塊的大小(212位)來劃分頁表，則將余下的42位用于外層頁號。此時在外層頁表中可能有4096 G個頁表項， 要占用16384 GB的連續(xù)內存空間。 必須采用多級頁表，將外層頁表再進行分頁，也是將各分頁離散地裝入到不相鄰接的物理塊中，再利用第2級的外層頁表來映射它們之間的關系。 對于64位的計算機，如果要求它能支持2(=1844744 TB)規(guī)模的物理存儲空間，則即使是采用三級頁表結構也是難以辦到的；而在當前的實際應用中也無此必要。第

18、四章 存 儲 器 管 理 4.4 基本分段存儲管理方式基本分段存儲管理方式 4.4.1 分段存儲管理方式的引入分段存儲管理方式的引入 引入分段存儲管理方式， 主要是為了滿足用戶和程序員的下述一系列需要： 1) 方便編程 2) 信息共享 3) 信息保護 4) 動態(tài)增長 5) 動態(tài)鏈接 第四章 存 儲 器 管 理 4.4.2 分段系統(tǒng)的基本原理分段系統(tǒng)的基本原理 1. 分段分段 分段地址中的地址具有如下結構： 段號段內地址31 16 15 02. 段表段表 第四章 存 儲 器 管 理 圖 4-16 利用段表實現(xiàn)地址映射 作業(yè)空間(MAIN)0030K(X)1020K(D)2015K(S)3010K

19、30K20K15K10K40K80K120K150K段長基址段號(MAIN)030K(X)120K(D)215K(S)310K040K80K120K150K段表內存空間0123第四章 存 儲 器 管 理 控制寄存器段表始址段表長度2100段號S越界1 K段長600段號01236 K4 K5002008 K9200基址位移量W82928K82928692主存物理地址有效地址圖 4-17 分段系統(tǒng)的地址變換過程 3. 地址變換機構 第四章 存 儲 器 管 理 4. 分頁和分段的主要區(qū)別分頁和分段的主要區(qū)別 (1) 頁是信息的物理單位，分頁是為實現(xiàn)離散分配方式，以消減內存的外零頭， 提高內存的利用率

20、?；蛘哒f， 分頁僅僅是由于系統(tǒng)管理的需要而不是用戶的需要。段則是信息的邏輯單位，它含有一組其意義相對完整的信息。 分段的目的是為了能更好地滿足用戶的需要。 第四章 存 儲 器 管 理 (2) 頁的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分為頁號和頁內地址兩部分，是由機器硬件實現(xiàn)的，因而在系統(tǒng)中只能有一種大小的頁面；而段的長度卻不固定， 決定于用戶所編寫的程序，通常由編譯程序在對源程序進行編譯時，根據信息的性質來劃分。 (3) 分頁的作業(yè)地址空間是一維的，即單一的線性地址空間，程序員只需利用一個記憶符，即可表示一個地址； 而分段的作業(yè)地址空間則是二維的，程序員在標識一個地址時，既需給出段名， 又

21、需給出段內地址。 第四章 存 儲 器 管 理 4.4.3 信息共享信息共享 ed 1ed 2ed 40data 1data 10進程12122606170頁表ed 1ed 2ed 40data 1data 10進程22122607180ed 1ed 2ed 40data 1data 10data 1data 10主存021226061707180頁表圖 4-18 分頁系統(tǒng)中共享editor的示意圖第四章 存 儲 器 管 理 圖 4-19 分段系統(tǒng)中共享editor的示意圖 editor進程1data 1進程2editordata 2段表段長基址16080402401608040380edito

22、rdata 1data 280240280380420第四章 存 儲 器 管 理 4.4.4 段頁式存儲管理方式段頁式存儲管理方式 1. 基本原理基本原理 圖 4-20 作業(yè)地址空間和地址結構 04K8K12K15K16K子程序段04K8K數(shù)據段04K8K10K12K(a)段號(S)段內頁號(P)段內地址(W)(b)主程序段第四章 存 儲 器 管 理 圖 4-21 利用段表和頁表實現(xiàn)地址映射 段號狀態(tài)頁表大小頁表始址0111213041頁號狀態(tài)存儲塊#0111213041操作系統(tǒng)主存頁表段表段表大小段表始址段表寄存器第四章 存 儲 器 管 理 2. 地址變換過程地址變換過程 圖 4-22 段頁

23、式系統(tǒng)中的地址變換機構 段表寄存器段表始址段表長度段號S頁號P段超長段表0123頁內地址頁表0123b塊號 b塊內地址頁表始址頁表長度第四章 存 儲 器 管 理 4.5 虛擬存儲器的基本概念虛擬存儲器的基本概念 4.5.1 虛擬存儲器的引入虛擬存儲器的引入 1. 常規(guī)存儲器管理方式的特征常規(guī)存儲器管理方式的特征 (1) 一次性。 (2) 駐留性。 第四章 存 儲 器 管 理 2. 局部性原理局部性原理 早在1968年， Denning.P就曾指出： (1) 程序執(zhí)行時， 除了少部分的轉移和過程調用指令外， 在大多數(shù)情況下仍是順序執(zhí)行的。 (2) 過程調用將會使程序的執(zhí)行軌跡由一部分區(qū)域轉至另一

24、部分區(qū)域， 但經研究看出，過程調用的深度在大多數(shù)情況下都不超過5。 (3) 程序中存在許多循環(huán)結構， 這些雖然只由少數(shù)指令構成， 但是它們將多次執(zhí)行。 (4) 程序中還包括許多對數(shù)據結構的處理， 如對數(shù)組進行操作， 它們往往都局限于很小的范圍內。 第四章 存 儲 器 管 理 局限性又表現(xiàn)在下述兩個方面： (1) 時間局限性。如果程序中的某條指令一旦執(zhí)行， 則不久以后該指令可能再次執(zhí)行；如果某數(shù)據被訪問過， 則不久以后該數(shù)據可能再次被訪問。產生時間局限性的典型原因，是由于在程序中存在著大量的循環(huán)操作。 (2) 空間局限性。一旦程序訪問了某個存儲單元，在不久之后，其附近的存儲單元也將被訪問，即程序

25、在一段時間內所訪問的地址，可能集中在一定的范圍之內，其典型情況便是程序的順序執(zhí)行。 第四章 存 儲 器 管 理 3. 虛擬存儲器定義虛擬存儲器定義 所謂虛擬存儲器， 是指具有請求調入功能和置換功能， 能從邏輯上對內存容量加以擴充的一種存儲器系統(tǒng)。其邏輯容量由內存容量和外存容量之和所決定，其運行速度接近于內存速度，而每位的成本卻又接近于外存。可見，虛擬存儲技術是一種性能非常優(yōu)越的存儲器管理技術，故被廣泛地應用于大、 中、 小型機器和微型機中。 第四章 存 儲 器 管 理 4.5.2 虛擬存儲器的實現(xiàn)方法虛擬存儲器的實現(xiàn)方法 1. 分頁請求系統(tǒng)分頁請求系統(tǒng) (1) 硬件支持。 請求分頁的頁表機制，

26、它是在純分頁的頁表機制上增加若干項而形成的，作為請求分頁的數(shù)據結構； 缺頁中斷機構，即每當用戶程序要訪問的頁面尚未調入內存時 便產生一缺頁中斷，以請求OS將所缺的頁調入內存； 地址變換機構， 它同樣是在純分頁地址變換機構的基礎上發(fā)展形成的。 (2) 實現(xiàn)請求分頁的軟件。第四章 存 儲 器 管 理 4.5.3 虛擬存儲器的特征虛擬存儲器的特征 1. 多次性多次性 2. 對換性對換性3. 虛擬性虛擬性 第四章 存 儲 器 管 理 4.6 請求分頁存儲管理方式請求分頁存儲管理方式 4.6.1 請求分頁中的硬件支持請求分頁中的硬件支持 1. 頁表機制頁表機制 頁號 物理塊號 狀態(tài)位P 訪問字段A 修改

27、位M外存地址 第四章 存 儲 器 管 理 2. 缺頁中斷機構缺頁中斷機構 圖 4-23 涉及6次缺頁中斷的指令 頁面B：A：654321指令copy ATO B第四章 存 儲 器 管 理 3. 地址變換機構地址變換機構 缺頁中斷處理保留CPU現(xiàn)場從外存中找到缺頁內存滿否？選擇一頁換出該頁被修改否？將該頁寫回外存OS命令CPU從外存讀缺頁啟動I/O硬件將一頁從外存換入內存修改頁表否是是否頁表項在快表中？CPU檢索快表訪問頁表否頁在內存？修改訪問位和修改位形成物理地址地址變換結束否頁號頁表長度?開始程序請求訪問一頁產生缺頁中斷請求調頁修改快表是越界中斷是是圖 4-24 請求分頁中的地址變換過程 第

28、四章 存 儲 器 管 理 4.6.2 內存分配策略和分配算法內存分配策略和分配算法 1. 最小物理塊數(shù)的確定最小物理塊數(shù)的確定 是指能保證進程正常運行所需的最小物理塊數(shù)。當系統(tǒng)為進程分配的物理塊數(shù)少于此值時，進程將無法運行。進程應獲得的最少物理塊數(shù)與計算機的硬件結構有關，取決于指令的格式、 功能和尋址方式。對于某些簡單的機器，若是單地址指令且采用直接尋址方式，則所需的最少物理塊數(shù)為2。其中，一塊是用于存放指令的頁面，另一塊則是用于存放數(shù)據的頁面。如果該機器允許間接尋址時，則至少要求有三個物理塊。對于某些功能較強的機器， 其指令長度可能是兩個或多于兩個字節(jié)，因而其指令本身有可能跨兩個頁面，且源地

29、址和目標地址所涉及的區(qū)域也都可能跨兩個頁面。第四章 存 儲 器 管 理 2. 物理塊的分配策略物理塊的分配策略 在請求分頁系統(tǒng)中，可采取兩種內存分配策略，即固定和可變分配策略。在進行置換時， 也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。 1) 固定分配局部置換(Fixed Allocation, Local Replacement) 2) 可變分配全局置換(Variable Allocation, Global Replacement) 3) 可變分配局部置換(Variable Allocation, Local Replacemen 第四章 存 儲 器 管 理 3

30、. 物理塊分配算法物理塊分配算法 1) 平均分配算法 這是將系統(tǒng)中所有可供分配的物理塊，平均分配給各個進程。 例如，當系統(tǒng)中有100個物理塊，有5個進程在運行時，每個進程可分得20個物理塊。這種方式貌似公平，但實際上是不公平的，因為它未考慮到各進程本身的大小。如有一個進程其大小為200頁，只分配給它20個塊，這樣，它必然會有很高的缺頁率；而另一個進程只有10頁，卻有10個物理塊閑置未用。 第四章 存 儲 器 管 理 2) 按比例分配算法 這是根據進程的大小按比例分配物理塊的算法。如果系統(tǒng)中共有n個進程，每個進程的頁面數(shù)為Si，則系統(tǒng)中各進程頁面數(shù)的總和為：又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每

31、個進程所能分到的物理塊數(shù)為bi，將有：b應該取整，它必須大于最小物理塊數(shù)。 niiSS1mSSbii第四章 存 儲 器 管 理 3) 考慮優(yōu)先權的分配算法 在實際應用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成， 應為它分配較多的內存空間。通常采取的方法是把內存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進程；另一部分則根據各進程的優(yōu)先權，適當?shù)卦黾悠湎鄳蓊~后，分配給各進程。在有的系統(tǒng)中，如重要的實時控制系統(tǒng)，則可能是完全按優(yōu)先權來為各進程分配其物理塊的。 第四章 存 儲 器 管 理 4.6.3 調頁策略調頁策略 1. 何時調入頁面何時調入頁面 1) 預調頁策略 2) 請求調頁策

32、略 第四章 存 儲 器 管 理 2. 從何處調入頁面從何處調入頁面 在請求分頁系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對換頁面的對換區(qū)。通常，由于對換區(qū)是采用連續(xù)分配方式，而事件是采用離散分配方式，故對換區(qū)的磁盤I/O速度比文件區(qū)的高。這樣，每當發(fā)生缺頁請求時，系統(tǒng)應從何處將缺頁調入內存，可分成如下三種情況： (1) 系統(tǒng)擁有足夠的對換區(qū)空間，這時可以全部從對換區(qū)調入所需頁面，以提高調頁速度。為此，在進程運行前， 便須將與該進程有關的文件，從文件區(qū)拷貝到對換區(qū)。 第四章 存 儲 器 管 理 (2) 系統(tǒng)缺少足夠的對換區(qū)空間，這時凡是不會被修改的文件，都直接從文件區(qū)調入；而當換出這

33、些頁面時，由于它們未被修改而不必再將它們換出，以后再調入時，仍從文件區(qū)直接調入。但對于那些可能被修改的部分，在將它們換出時，便須調到對換區(qū)，以后需要時，再從對換區(qū)調入。 (3) UNIX方式。由于與進程有關的文件都放在文件區(qū)，故凡是未運行過的頁面，都應從文件區(qū)調入。而對于曾經運行過但又被換出的頁面，由于是被放在對換區(qū)，因此在下次調入時，應從對換區(qū)調入。由于UNIX系統(tǒng)允許頁面共享，因此， 某進程所請求的頁面有可能已被其它進程調入內存，此時也就無須再從對換區(qū)調入。 第四章 存 儲 器 管 理 3. 頁面調入過程頁面調入過程 每當程序所要訪問的頁面未在內存時，便向CPU發(fā)出一缺頁中斷，中斷處理程序

34、首先保留CPU環(huán)境，分析中斷原因后， 轉入缺頁中斷處理程序。該程序通過查找頁表，得到該頁在外存的物理塊后， 如果此時內存能容納新頁，則啟動磁盤I/O將所缺之頁調入內存，然后修改頁表。如果內存已滿，則須先按照某種置換算法從內存中選出一頁準備換出；如果該頁未被修改過，可不必將該頁寫回磁盤；但如果此頁已被修改， 則必須將它寫回磁盤，然后再把所缺的頁調入內存， 并修改頁表中的相應表項，置其存在位為“1”，并將此頁表項寫入快表中。在缺頁調入內存后，利用修改后的頁表， 去形成所要訪問數(shù)據的物理地址，再去訪問內存數(shù)據。 第四章 存 儲 器 管 理 4.7 頁面置換算法頁面置換算法 4.7.1 最佳置換算法和

35、先進先出置換算法最佳置換算法和先進先出置換算法 1. 最佳(Optimal)置換算法 最佳置換算法是由Belady于1966年提出的一種理論上的算法。 其所選擇的被淘汰頁面，將是以后永不使用的， 或許是在最長(未來)時間內不再被訪問的頁面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。 第四章 存 儲 器 管 理 假定系統(tǒng)為某進程分配了三個物理塊， 并考慮有以下的頁面號引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 進程運行時， 先將7，0，1三個頁面裝入內存。 以后， 當進程要訪問頁面2時， 將會產生缺頁中斷。此時OS根據最佳置換算法， 將選擇頁面7予

36、以淘汰。 引用率70770170122010320304243230321201201770101頁框(物理塊）203圖 4-25 利用最佳頁面置換算法時的置換圖 第四章 存 儲 器 管 理 2. 先進先出先進先出(FIFO)頁面置換算法頁面置換算法 引用率70770170122010323104430230321013201770201頁框2304204230230127127011圖 4-26 利用FIFO置換算法時的置換圖 第四章 存 儲 器 管 理 4.7.2 最近最久未使用最近最久未使用(LRU)置換算法置換算法 1. LRU(Least Recently Used)置換算法的描述置

37、換算法的描述 圖 4-27 LRU頁面置換算法 引用率70770170122010320304403230321132201710701頁框402432032102第四章 存 儲 器 管 理 2. LRU置換算法的硬件支持置換算法的硬件支持 1) 寄存器寄存器 為了記錄某進程在內存中各頁的使用情況，須為每個在內存中的頁面配置一個移位寄存器，可表示為 R=Rn-1Rn-2Rn-3 R2R1R0 第四章 存 儲 器 管 理 圖 4-28 某進程具有8個頁面時的LRU訪問情況 第四章 存 儲 器 管 理 2) 棧棧 圖 4-29 用棧保存當前使用頁面時棧的變化情況 44747074070471704

38、10174010741210742120741210742621076第四章 存 儲 器 管 理 4.7.3 Clock置換算法置換算法 1. 簡單的簡單的Clock置換算法置換算法 圖 4-30 簡單Clock置換算法的流程和示例 入口查尋指針前進一步，指向下一個表目頁面訪問位0?選擇該頁面淘汰是返回置頁面訪問位“0”否塊號頁號訪問位指針0124034215650711替換指針第四章 存 儲 器 管 理 2. 改進型改進型Clock置換算法置換算法 由訪問位A和修改位M可以組合成下面四種類型的頁面： 1類(A=0, M=0): 表示該頁最近既未被訪問， 又未被修改， 是最佳淘汰頁。 2類(A

39、=0, M=1)： 表示該頁最近未被訪問， 但已被修改， 并不是很好的淘汰頁。 3類(A=1, M=0)： 最近已被訪問， 但未被修改， 該頁有可能再被訪問。 4類(A=1, M=1): 最近已被訪問且被修改， 該頁可能再被訪問。 第四章 存 儲 器 管 理 其執(zhí)行過程可分成以下三步： (1) 從指針所指示的當前位置開始， 掃描循環(huán)隊列， 尋找A=0且M=0的第一類頁面， 將所遇到的第一個頁面作為所選中的淘汰頁。 在第一次掃描期間不改變訪問位A。 (2) 如果第一步失敗，即查找一周后未遇到第一類頁面， 則開始第二輪掃描，尋找A=0且M=1的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的訪問位都置0。 (3) 如果第二步也失敗，亦即未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位復0。 然后重復第一步，如果仍失敗，必要時再重復第二步，此時就一定能找到被淘汰的頁。 第四章 存 儲 器 管 理 4.7.4 其它置換算法其它置換算法 1. 最少使用(LFU： Least Frequently Used)置換算法2. 頁面緩沖算法(PBA： Page Buffering Algorithm) 第四章 存 儲