昆明理工大學 付湘瓊《操作系統(tǒng)》第四章 存儲器管理ppt課件

1、 計算機操作系統(tǒng) 第四章 存儲器管理存儲管理4.1 存儲器管理的假設干概念 存儲器 地址變換 虛擬存儲器 存儲管理一存儲器1存儲器 存儲器主存 內(nèi)部存儲器，磁芯存 儲器輔存 外存磁盤、磁鼓、 磁帶、 軟盤存儲管理 主存 系統(tǒng)區(qū) OS規(guī)范子程序 用戶區(qū) 用戶程序、數(shù)據(jù)2主存儲器的物理組織，多級存儲器高速緩存 主存外存存儲管理 3存儲器管理的功能： (1) 主存空間分配和維護：主存儲器中允許同時包容各種軟件和多個用戶程序時，必需處理主存空間如何分配以及各存儲區(qū)內(nèi)的信息如何維護等問題。對不同的存儲管理方式，采用的主存空間分配戰(zhàn)略是不同的。為了維護區(qū)域內(nèi)信息不被破壞，必需實現(xiàn)存儲維護。存儲維護的任務必

2、需由硬件和軟件配合來實現(xiàn)。 (2)主存空間的重定位 配合硬件做好地址轉換任務，把一組邏輯地址空間轉換成絕對地址空間，以保證處置器的正確執(zhí)行。存儲管理 (3) 主存空間的共享 在多道程序設計的系統(tǒng)中，同時進入主存儲器執(zhí)行的作業(yè)能夠要調(diào)用同的程序。例如，調(diào)用編譯程序進展編譯，把這個編譯程序存放在某個區(qū)域中，各作業(yè)要調(diào)用時就訪問這個區(qū)域，因此這個區(qū)域就是共享的。同樣也可實現(xiàn)公共數(shù)據(jù)的公享。 (4) 主存空間的擴展 提供虛擬存儲器，運用戶編制程序時不用思索主存儲器的實踐容量，使計算機系統(tǒng)似乎有一個比實踐主存儲器容量大得多的主存空間。 存儲管理 二地址變換 1.存儲空間 地址空間一個目的程序所限定的地址

3、范圍 邏輯地址相對地址當對源程序進展編譯時，編譯后一個目的程序所限定的地址范圍稱為該作業(yè)的邏輯地址空間。 物理地址絕對地址主存中一系列存儲 物理單元。 地址空間是邏輯地址的集合。存儲空間是物理地址的集合。一個是虛的概念，一個是實的物體。存儲管理 2.重定位 當一個地址裝入與其地址空間不一致的存儲空間中，就得要地址變換。也就是說將虛地址映射為內(nèi)存地址，把這種作法叫做地址重定位 (1) 靜態(tài)地址重定位 在裝入一個作業(yè)時，把作業(yè)中的指令地址全部轉換為絕對地址地址轉換任務是在作業(yè)執(zhí)行前集中一次完成的在作業(yè)執(zhí)行過程中就無須再進展地址轉換任務。存儲管理靜態(tài)地址重定位優(yōu)點 它的主要優(yōu)點是，無需添加硬件地址變

4、換機構，因此可在普通計算機上實現(xiàn)。靜態(tài)地址重定位缺陷 主要缺陷有： 要求給每個作業(yè)分配一個延續(xù)的存儲空間，且在作業(yè)的整個執(zhí)行期間不能再挪動，因此也就不能實現(xiàn)重新分配主存。 用戶必需事先確定所需的存儲量，假設所需的存儲量超越可用存儲空間時，用戶必需思索覆蓋構造。 用戶之間難以共享主存中的同一程序副本。存儲管理 2動態(tài)地址重定位： 動態(tài)地址重位置是在程序執(zhí)行過程中，在cpu訪問內(nèi)存之前,將要訪問的程序或數(shù)據(jù)地址轉換成內(nèi)存地址. 動態(tài)重定位依托硬件地址變換機構完成。 Load A500 123455001000 Load A500 12345+虛擬空間 內(nèi)存空間 VR BR

5、.存儲管理 地址重定位機構需求一個或多個基地址存放器BR和一個或多個程序虛地址存放器VR。指令或數(shù)據(jù)的內(nèi)存地址MA與虛地址的關系為：MA=(BR)+(VR) 其中，(x)表示存放器x中的內(nèi)容 存儲管理 最簡單的方法是利用一個重定位存放器。該存放器的值由調(diào)度程序根據(jù)作業(yè)分配到的存儲空間的起始地址來設定。在具有這種地址變換機構的計算機系統(tǒng)中，當作業(yè)執(zhí)行時，不是根據(jù)CPU給出的邏輯地址去訪問主存，而是將邏輯地址與重定位存放器中的內(nèi)容相加后得到的地址作為訪問主存的地址。 存儲管理動態(tài)重定位的主要優(yōu)點有： 用戶作業(yè)不要求分配延續(xù)的存儲空間。 用戶作業(yè)在執(zhí)行過程中，可以動態(tài)懇求存儲空間和在主存中挪動。 有

6、利于程序段的共享。動態(tài)重定位的主要缺陷有： 需求附加的硬件支持。 實現(xiàn)存儲管理的軟件算法比較復雜。存儲管理 三.虛擬存儲器 什么是虛擬存儲器？ 虛擬存儲器是一種存儲管理技術，用以完成用小的內(nèi)存實如今大的虛擬空間中程序的運轉任務。 為了給大作業(yè)用戶提供方便,使它們擺脫對主存和輔存的分配和管理問題,由操作系統(tǒng)把多級存儲器一致管理起來,實現(xiàn)自動覆蓋。既一個大作業(yè)在執(zhí)行時, 其一部分地址空間在主存,另一部分在輔存,當訪問的信息不在主存時.因此,從效果來看,這樣的系統(tǒng),好象用戶提供了存儲容量比實踐主存大得多的存儲器,人們稱這個為虛擬存儲器。之所以稱它為虛擬存儲器,由于這樣的存儲器實踐上并不存在而只是系統(tǒng)

7、添加自動覆蓋功能，給用戶呵斥的一種幻覺,仿佛它有一個很大的主存供它運用。這是虛擬存儲器的最初概念。存儲管理 這種想法的中心,本質(zhì)上也就是把作業(yè)的地址空間和實踐主存的存儲空間似為兩個不同的概念.一個計算機系統(tǒng)算題人員提供了一個多大的地址空間,它就所在這個地址空間編制程序,而完全用不著思索實踐主存的大小.換句話說, 虛擬存儲器就是一個地址空間.一個虛存儲器的最大容量是由計算機的地址構造確定的.假設CPU給出的有效地址長度為18位,可以尋址范圍為:0-256k;假設地址的長度為為20位,那么尋址范圍為:1024k. 實踐虛擬存儲器其一是要相當容量的輔存,足以存放一切并列作業(yè)的地址空間.其二是要有一定

8、的主存,由于處置機上運轉的作業(yè),必需有一定的信息在主存中.其三是地址變換機構.存儲管理 4.2 分區(qū)存儲管理 4.2.1 分區(qū)管理根本原理 1.固定分區(qū)法 固定分區(qū)把主存分成假設干個固定大小的存儲區(qū)。區(qū)號分區(qū)長度起始地址 狀態(tài)18K20K已分配232K28K已分配364K60K已分配4132K124K已分配OS20K28K60K124K256K進程A6K進程B25K進程C36K存儲管理 2.動態(tài)分區(qū)法 由于固定分區(qū)主存利用率不高，運用起來不靈敏，所以出現(xiàn)了可變分區(qū)的管理技術。 動態(tài)分區(qū)原那么：存儲空間的劃分是在裝作業(yè)時進展的。從可用的自在存儲空間內(nèi)，劃出一個大小正好等于作業(yè)大小的存儲區(qū)，并分配

9、給這一作業(yè)。 進程 A8K進程 D124K進程 B16K進程 C64KOS進程A進程B進程C進程DOS進程A進程B進程COS進程A進程BOS進程A存儲管理OSA8K24K空閑區(qū)B16KC完成64K空閑區(qū)D124KOSA8K8K空閑區(qū)B16KE50KD124K14K空閑區(qū)F16KOSA8K8K空閑區(qū)空閑區(qū)16KE50KD124K空閑合并124+14=K進程E50K進程F16K進入內(nèi)存進程B16K進程D124K完成內(nèi)存分配變化過程存儲管理 4.2.2分區(qū)的分配與回收固定式分區(qū)和可變式分區(qū)的存儲管理算法有如下三種： 最正確順應算法(Best Fit) 1含義 最正確順應算法就是為一作業(yè)選擇分區(qū)時總是

10、尋覓其大小最接近于作業(yè)所要求的存儲空間。換句話說，把作業(yè)放入這樣的分區(qū)后剩下的部分最小。2優(yōu)點 這種算法的優(yōu)點是：假設存儲空間中具有正好是所要求大小的空閑區(qū)，那么必然被選中；假設不存在這樣的空閑區(qū)，也只對比要求稍大的空閑區(qū)劃分，而絕不會去劃分一個更大的空閑區(qū)。3實現(xiàn)方法 為了加快查找速度，應將空閑區(qū)按其大小遞增的順序陳列，組織成一空閑區(qū)鏈。存儲管理最壞順應算法最壞順應算法Worst Fit(1含義含義 它在為作業(yè)選擇存儲空間時，總是尋它在為作業(yè)選擇存儲空間時，總是尋覓最大的空閑區(qū)。覓最大的空閑區(qū)。2實現(xiàn)方法實現(xiàn)方法 空閑區(qū)應按其大小遞減的順序陳列?？臻e區(qū)應按其大小遞減的順序陳列。分配時只看鏈頭

11、空閑區(qū)能否滿足要求，決分配時只看鏈頭空閑區(qū)能否滿足要求，決議能否分配。議能否分配。存儲管理初次順應算法初次順應算法(First Fit) 1含義含義 最正確順應和最壞順應算法各有利弊。初最正確順應和最壞順應算法各有利弊。初次順應算法是對它們進展折衷思索后設計出來的。次順應算法是對它們進展折衷思索后設計出來的。2實現(xiàn)方法實現(xiàn)方法 將空閑區(qū)按其在存儲空間中的起始地址遞增將空閑區(qū)按其在存儲空間中的起始地址遞增的順序陳列。為作業(yè)分配存儲空間時，從空閑區(qū)的順序陳列。為作業(yè)分配存儲空間時，從空閑區(qū)鏈的始端開場查找，選那么第一個滿足要求的空鏈的始端開場查找，選那么第一個滿足要求的空閑區(qū)。閑區(qū)。存儲管理存儲管

12、理1分區(qū)分配的主要步驟有： 從未分配表中找到一個足以包容該作業(yè)的可用空閑區(qū)； 如這個空閑區(qū)比所要求的大，那么將它分成兩部分：一部分成為已分配的分區(qū)，剩下部分仍為空閑區(qū)； 修正兩張表的有關信息，并回送一個所分配分區(qū)的序號或該區(qū)的首址。存儲管理要求Xk大小分區(qū)取分區(qū)闡明表第一項形狀位置正在運用取下一表項無法分配該分區(qū)空閑？分區(qū)長度Xk?表終了？前往分區(qū)號否否否是是是固定分區(qū)分配算法存儲管理最正確分配算法例子最正確分配算法例子 存儲管理系統(tǒng)回收一個分區(qū)的主要步驟有： 檢查回收分區(qū)能否與空閑區(qū)鄰接，如鄰接那么加以合并，使之成為一個延續(xù)的大空閑區(qū)。 修正兩張闡明表。存儲管理可重定位分區(qū)存儲管理 含義含義

13、 采用動態(tài)分配的可變分區(qū)管理，即分采用動態(tài)分配的可變分區(qū)管理，即分配時可以將主存重的空閑區(qū)拼接后再分配。配時可以將主存重的空閑區(qū)拼接后再分配。 由于可變式分區(qū)存儲管理是根據(jù)作業(yè)由于可變式分區(qū)存儲管理是根據(jù)作業(yè)的需求量劃分分區(qū)的，因此消除了固定式的需求量劃分分區(qū)的，因此消除了固定式分區(qū)分配呵斥的分區(qū)分配呵斥的內(nèi)零頭內(nèi)零頭。但是，由于作。但是，由于作業(yè)的多次懇求和釋放，主存中經(jīng)常能夠出業(yè)的多次懇求和釋放，主存中經(jīng)常能夠出現(xiàn)大量的不能充分利用的小空閑區(qū)?，F(xiàn)大量的不能充分利用的小空閑區(qū)。 存儲管理存儲管理 采用拼接技術，把零頭集中起來構成一個大的空閑區(qū)。實現(xiàn)方法是挪動某些已分配區(qū)中的信息，挪動夠分配為

14、止或者使一切的作業(yè)位于存儲器的一端，把空閑區(qū)全部留在另一端， 存儲管理空閑區(qū)拼接的時機選擇空閑區(qū)拼接的時機選擇 進展拼接的時機可選那么為進展拼接的時機可選那么為 1當有作業(yè)完成釋放分區(qū)時，就立刻拼接。當有作業(yè)完成釋放分區(qū)時，就立刻拼接。這樣的拼接是比較頻繁的，要破費較多的處置機這樣的拼接是比較頻繁的，要破費較多的處置機時間。時間。 2當某一作業(yè)懇求分配存儲空間時，假當某一作業(yè)懇求分配存儲空間時，假設當時主存沒有足夠大的空閑區(qū)，但一切空閑區(qū)設當時主存沒有足夠大的空閑區(qū)，但一切空閑區(qū)的總和可以滿足該作業(yè)的要求，此時進展拼接。的總和可以滿足該作業(yè)的要求，此時進展拼接。這樣的拼接可節(jié)省處置機時間。這樣

15、的拼接可節(jié)省處置機時間。存儲管理 分配算法流程分配算法流程 存儲管理 4 45 5 頁式管理頁式管理 4.5.1 4.5.1 頁式管理的根本頁式管理的根本原理原理 在分區(qū)存儲管理中，都要在分區(qū)存儲管理中，都要求把一個作業(yè)的地址空間裝入到延續(xù)求把一個作業(yè)的地址空間裝入到延續(xù)的存儲空間內(nèi)，不是存在內(nèi)零頭，就的存儲空間內(nèi)，不是存在內(nèi)零頭，就是存在外零頭或為處理外零頭破費時是存在外零頭或為處理外零頭破費時間進展間進展“拼接。假設我們能取消作拼接。假設我們能取消作業(yè)對延續(xù)性的要求，必然會進一步提業(yè)對延續(xù)性的要求，必然會進一步提高主存的利用率，又無需為挪動信息高主存的利用率，又無需為挪動信息付出代價。分頁

16、管理就是在這個指點付出代價。分頁管理就是在這個指點思想下設計出來的。思想下設計出來的。 存儲管理 1. 分頁技術的實現(xiàn)原理 等分主存： 把主存的存儲空間劃分成大小相等的片，稱為存儲塊，或稱為頁架Page Frame 用戶邏輯地址空間的分頁： 把用戶的邏輯地址空間虛地址空間劃分成假設干個與存儲塊大小相等的片，稱之為頁面或頁Page。并給各頁從零開場依次編以延續(xù)的頁號0，1，2，。 邏輯地址的表示： 用戶的邏輯地址普通是從基地址“0開場延續(xù)編址，即是相對地址。在分頁系統(tǒng)中，每個虛擬地址相對地址用一個數(shù)對p,d來表示。其中p是頁號，d是該虛擬地址在頁面號為p的頁中的相對地址，稱為頁內(nèi)地址位移量。 主

17、存分配原那么： 系統(tǒng)以存儲塊為單位把主存分給作業(yè)或進程，并且分給一個作業(yè)的各存儲塊不一定是相鄰和延續(xù)的。 存儲管理頁表頁表 在分頁系統(tǒng)中，作業(yè)的一頁可以分配到主存空間中任何在分頁系統(tǒng)中，作業(yè)的一頁可以分配到主存空間中任何一個可用的存儲塊。但是，系統(tǒng)怎樣知道作業(yè)的哪一頁分一個可用的存儲塊。但是，系統(tǒng)怎樣知道作業(yè)的哪一頁分配到哪一存儲塊內(nèi)？為此，系統(tǒng)建立了一張頁面映象表，配到哪一存儲塊內(nèi)？為此，系統(tǒng)建立了一張頁面映象表，簡稱頁表。用一張頁表來描畫每頁的頁號與所在塊的塊號簡稱頁表。用一張頁表來描畫每頁的頁號與所在塊的塊號的映射。的映射。存儲管理為了便于管理和維護，系統(tǒng)為每個裝入主存的作業(yè)建立一張相應

18、的頁表，它的起始地址及大小保管在該作業(yè)的PCB中。一旦這個作業(yè)被調(diào)度執(zhí)行，把它的頁表始址及大小裝入特定的頁表存放器中。頁號塊號存取控制021328存儲管理 4.5.2 簡單分頁管理 在作業(yè)或進程開場執(zhí)行之前，把該作業(yè)或進程的程序段和數(shù)據(jù)全部裝入主存的各個空閑塊中，并經(jīng)過頁表和硬件地址變換機構實現(xiàn)虛擬地址到主存物理地址的地址映射。1主存的分配與回收 所需的表格 為了實現(xiàn)分頁存儲管理，在軟件方面應建立如下表格，并由操作系統(tǒng)實施管理。 (1頁表PMT。每個作業(yè)一張表，用于該作業(yè)的地址變換，該作業(yè)有多少頁面就有多少表目。 2 存 儲 分 塊 表 M B T 。 整個系一致張表。該表中每一表目對應一個存

19、儲塊，記錄了該塊的形狀：已分配或空閑。 存儲管理2.分配算法分配算法 當進程或作業(yè)要求分配主存塊時，首先檢查能否有足當進程或作業(yè)要求分配主存塊時，首先檢查能否有足夠的空閑塊，假設沒有，那么本次無法分配。假設有那么夠的空閑塊，假設沒有，那么本次無法分配。假設有那么首先分配設置頁表，將分到的主存快號添入頁表中。首先分配設置頁表，將分到的主存快號添入頁表中。存儲管理3.地址變換地址變換 地址變換過程地址變換過程 1當調(diào)度一個作業(yè)執(zhí)行時，首先將頁表始址及大小裝入當調(diào)度一個作業(yè)執(zhí)行時，首先將頁表始址及大小裝入頁表存放器。頁表存放器。 2作業(yè)執(zhí)行過程中作業(yè)執(zhí)行過程中CPU產(chǎn)生的每一個邏輯地址，由硬件產(chǎn)生的

20、每一個邏輯地址，由硬件地址變換機構自動將其分成兩部分：一部分為頁號，另一部地址變換機構自動將其分成兩部分：一部分為頁號，另一部分是頁內(nèi)位移量。分是頁內(nèi)位移量。 3這個頁號先與頁表存放器中的當前頁表大小進展比較。這個頁號先與頁表存放器中的當前頁表大小進展比較。假設頁號太大，表示訪問越界，系統(tǒng)產(chǎn)生相應的中斷。假設假設頁號太大，表示訪問越界，系統(tǒng)產(chǎn)生相應的中斷。假設頁訪問是合法的，那么由頁表始址和頁號計算出所對應的物頁訪問是合法的，那么由頁表始址和頁號計算出所對應的物理塊號；理塊號； 4取出其存取控制字段，作存取控制驗證，假設合法那取出其存取控制字段，作存取控制驗證，假設合法那么將物理塊號與邏輯地址

21、中的位移量拼接，構成最終訪問的么將物理塊號與邏輯地址中的位移量拼接，構成最終訪問的物理地址。否那么，產(chǎn)生相應訪問非法中斷。物理地址。否那么，產(chǎn)生相應訪問非法中斷。存儲管理地址變換例子地址變換例子 例如，設一個例如，設一個3頁長的進程具有頁號頁長的進程具有頁號0、1、2,分到的主存快分到的主存快號為號為2、3、8。假設頁的大小為。假設頁的大小為1K,指令指令LOAD 1,2500的虛地址為的虛地址為100。下面我們以該例子來闡明地址變換過程。下面我們以該例子來闡明地址變換過程。 存儲管理 1指令地址100轉換 由虛地址100可知，指令LOAD 1,2500在第0頁的100單元中。由于第0頁在主存

22、的第二塊中，因此，該指令在主存的地址為2048+100=2148。 2指令地址2500轉換 當CPU執(zhí)行到第2148單元的指令時，地址變換機構首先將2500轉換為頁號與頁內(nèi)地址兩部分，即P=2,W=452。由頁表，可知第二頁所對應的主存快為8。將塊號8與頁內(nèi)地址452相連，得到待訪問的主存物理地址為8644。存儲管理存儲管理4. 超高速緩存超高速緩存 聯(lián)想存儲器聯(lián)想存儲器 為了提高地址變換速度，且不添加太多的硬件投資，經(jīng)為了提高地址變換速度，且不添加太多的硬件投資，經(jīng)過在地址變換機構中增設一組數(shù)量不多的存放器，把它作為過在地址變換機構中增設一組數(shù)量不多的存放器，把它作為超高速緩沖存放器來運用，

23、存放當前訪問的那些頁的頁號和超高速緩沖存放器來運用，存放當前訪問的那些頁的頁號和塊號。塊號。 地址轉換過程地址轉換過程 1當運轉進程要訪問邏輯地址當運轉進程要訪問邏輯地址v時，硬件自動將邏輯地時，硬件自動將邏輯地址址v截成頁號截成頁號p和頁內(nèi)地址和頁內(nèi)地址d。 2地址轉換機構首先以頁號地址轉換機構首先以頁號p和高速緩沖器中各表目相和高速緩沖器中各表目相比較。比較。 3假設該頁不在高速緩沖器中，那么訪問存儲器中的假設該頁不在高速緩沖器中，那么訪問存儲器中的頁表。假設相符，那么它送出相應的塊號與頁內(nèi)地址一同構頁表。假設相符，那么它送出相應的塊號與頁內(nèi)地址一同構成物理地址，并按此地址訪主存。成物理地

24、址，并按此地址訪主存。 存儲管理 超高速緩存找到存儲管理 超高速緩存未找到存儲管理 4.5.3 懇求分頁管理 懇求分頁存儲管理是在簡單分頁管理根底上開展起來的。懇求頁式管理在作業(yè)或進程開場執(zhí)行之前，只把當前需求的一部分頁面裝入主存，其它部分在作業(yè)執(zhí)行過程中需求時，再從輔存上調(diào)入主存 存儲管理 1.頁表的擴展 頁表添加信息 通常頁表表目應添加如下信息： 1中斷位：表示該頁能否在主存。中斷位為0表示該頁在主存；為1表示不在主存。 2修正位：該位為0時，表示該頁面中的數(shù)據(jù)未被修正正。該位為1時，表示該頁面中的信息已被修正正。 3訪問位：表示該頁面在最近期間能否被訪問過。該位為0時，表示該頁面未被訪問

25、過。為1時，表示該頁面最近被訪問過。該位主要用于頁面置換戰(zhàn)略中。 4輔存地址：指出該頁面在輔存上的存放地址。擴展后的頁表如下圖： 頁號塊號存取控制改變位引用位中斷位 輔存地址存儲管理2.地址變換地址變換 懇求分頁的地址變換初始過程非常類似于簡單分頁系懇求分頁的地址變換初始過程非常類似于簡單分頁系統(tǒng)的地址變換，其全部任務：存儲空間的分配，頁面的置統(tǒng)的地址變換，其全部任務：存儲空間的分配，頁面的置換等都是在指令執(zhí)行過程中完成的，更準確地說，是在換等都是在指令執(zhí)行過程中完成的，更準確地說，是在CPU訪問內(nèi)存的過程中完成的。訪問內(nèi)存的過程中完成的。存儲管理3.缺頁中斷處置缺頁中斷處置 當中斷位為當中斷

26、位為1時，表示該頁不在主時，表示該頁不在主存，那么必需確定它在輔存中的存放地址。存，那么必需確定它在輔存中的存放地址。并把它從輔存中調(diào)入主存。缺頁中斷的處并把它從輔存中調(diào)入主存。缺頁中斷的處置過程如圖：置過程如圖：存儲管理4. 提取頁面戰(zhàn)略提取頁面戰(zhàn)略 這是一個何時把頁面裝入主存的問題。這是一個何時把頁面裝入主存的問題。 兩種戰(zhàn)略兩種戰(zhàn)略 1懇求式提取懇求式提取:僅當需求時才提取頁面的戰(zhàn)略；僅當需求時才提取頁面的戰(zhàn)略； 2預先調(diào)頁預先調(diào)頁:把事先提取頁面的戰(zhàn)略。任何預先調(diào)頁把事先提取頁面的戰(zhàn)略。任何預先調(diào)頁戰(zhàn)略都是以預測為根底的。假設能裝入適宜的不久要訪問戰(zhàn)略都是以預測為根底的。假設能裝入適宜

27、的不久要訪問的頁面，那么可減少缺頁中斷。在很長一段時間內(nèi)甚至的頁面，那么可減少缺頁中斷。在很長一段時間內(nèi)甚至本次運轉都不被存取，這樣的預先調(diào)頁是失敗的。由于本次運轉都不被存取，這樣的預先調(diào)頁是失敗的。由于預先調(diào)頁的勝利率約為預先調(diào)頁的勝利率約為50，因此，大多數(shù)系統(tǒng)采用純懇，因此，大多數(shù)系統(tǒng)采用純懇求式提取頁面戰(zhàn)略。求式提取頁面戰(zhàn)略。存儲管理 4.5.4懇求頁式管理中的置換算法 頁式淘汰算法 1.先進先出FIFO算法 FIFO：總是淘汰最先進入主存儲器的那一頁。 FIFO算法容易實現(xiàn)，但是它所根據(jù)的理由不是普遍成立的。哪些在內(nèi)存中駐留很久的頁，往往是被經(jīng)常訪問的頁，結果這些常用的頁都被淘汰調(diào)，

28、而能夠又需求立刻調(diào)回內(nèi)存。 采用FIFO算法還會產(chǎn)生一種奇異景象，直觀上，分配給的作業(yè)的實頁越多，進程執(zhí)行時發(fā)生的缺頁中斷率就越小，但對FIFO算法這個結論并不是絕對的。在某些情況下，當分配的頁面多反而導致更多的缺頁中斷，這種景象稱為FIFO異常景象或稱Belady景象。 創(chuàng)建進程式時往往只向內(nèi)存裝入了第0頁。 存儲管理 當需求淘汰某一頁時，選擇在最近一段時間里最久沒有被運用過的頁淘汰。 A.近似算法(LFU)：當需求淘汰時，應淘汰被訪問次數(shù)最少的頁。一種簡單的方法是為每一頁設置一個計數(shù)器，每當訪問一頁時，就把該頁對應的計數(shù)器加一，隔一個周期T，把左右計數(shù)器清0。當發(fā)生缺頁中斷時，選擇計數(shù)值最

29、小的頁，可把它淘汰，同時把一切計數(shù)器清0。1.最近最久未運用頁面置換算法LRU存儲管理 B.最近沒有運用的頁面淘汰算法NUR 需求淘汰某一頁時，從那些最近一個時期內(nèi)未被訪問的頁中任選一頁淘汰。 實現(xiàn)方法：在頁內(nèi)增設一個訪問位，當這一頁被訪問時，硬件把它置成“1，而沒有被訪問過的頁，訪問位為“0。因此，在產(chǎn)生缺頁中斷時，可從那些訪問位為0的頁中選一頁進展淘汰。存儲管理抖動和任務集抖動和任務集 1. 部分性概念部分性概念 部分性含義部分性含義 (1)時間部分性：是指某個位置最近被訪問了，時間部分性：是指某個位置最近被訪問了，那么往往很快又要被再次訪問。那么往往很快又要被再次訪問。 (2)空間部分性

30、：是指一旦某個位置被訪問了，空間部分性：是指一旦某個位置被訪問了，那么它附近的位置也將被訪問。那么它附近的位置也將被訪問。 2. 抖動抖動(或稱顛簸或稱顛簸) 抖動：抖動： 假設一個進程破費多于執(zhí)行時間的時間來完假設一個進程破費多于執(zhí)行時間的時間來完成頁面交換任務，我們稱該進程是顛簸的。成頁面交換任務，我們稱該進程是顛簸的。存儲管理 4.5.5 存儲維護 一種是地址越界維護，另一種存取控制維護。 地址越界維護可由地址變換機構中的控制存放器的值頁表長度和所要訪問的虛地址經(jīng)過比較完成。 存取控制維護是經(jīng)過頁表控制對內(nèi)存信息的操作方式提供維護。它的實現(xiàn)那么是在頁表添加相應的維護位即可。存儲管理 頁式

31、管理的優(yōu)缺陷 優(yōu)點優(yōu)點 (1) 由于它不要求作業(yè)或進程的程序段和數(shù)據(jù)在主存由于它不要求作業(yè)或進程的程序段和數(shù)據(jù)在主存中延續(xù)存放，從而有效的處理了碎片問題。中延續(xù)存放，從而有效的處理了碎片問題。 (2) 懇求分頁管理提供了虛擬存儲器。提高了主存的利懇求分頁管理提供了虛擬存儲器。提高了主存的利用率，更加有利于多道程序的運轉和方便用戶，特別是大用率，更加有利于多道程序的運轉和方便用戶，特別是大作業(yè)用戶。作業(yè)用戶。 缺陷缺陷 1要求有相應的硬件支持。要求有相應的硬件支持。 2為處置缺頁中斷，添加了處置機時間的開銷。為處置缺頁中斷，添加了處置機時間的開銷。 3為防止系統(tǒng)抖動所采取的各種措施會添加系統(tǒng)的為

32、防止系統(tǒng)抖動所采取的各種措施會添加系統(tǒng)的復雜性。復雜性。 4每個作業(yè)或進程的最后一頁內(nèi)總有一部分空間得每個作業(yè)或進程的最后一頁內(nèi)總有一部分空間得不到利用。不到利用。存儲管理 4.6 段式與段頁式管理1.作業(yè)的邏輯地址空間：分段情況下要求每個作業(yè)的地址空間按照程序的自然邏輯關系分成假設干段，每個段有本人的段名。子程序子程序數(shù)組數(shù)組子程子程序序主程序主程序數(shù)組數(shù)組主程序主程序作業(yè)作業(yè)A02K00.5k 03000200存儲管理 2. 段式存儲管理的地址構造段號段號段內(nèi)地址段內(nèi)地址a:虛擬地址段號段號 始址始址 長度長度存取方式存取方式內(nèi)外內(nèi)外 訪問位訪問位b:段表段表每個作業(yè)一個，這個段表實施段維

33、護，提供虛存。存取方式讀/寫、只讀、執(zhí)行。存儲管理段號其他頁表長度起始地址051024171029291036段表長度 起始地址段表地址存放器頁號其他頁面11221932148510頁號 其他 頁面12933.段地址變換 存儲管理 4.段的共享與維護 段的共享是比較容易實現(xiàn)的，只需用戶運用一樣的段名，在新的段表中填入已在主存中的段的起始地址，并置以適當?shù)淖x寫控制權，就可做到共享一個邏輯上完好的段的信息。 存儲管理段號段號 標志標志始址始址. 0執(zhí)行執(zhí)行 218 1讀讀/寫寫 365 2只讀只讀 542 共享共享 主存主存 共享共享 數(shù)據(jù)數(shù)據(jù)段號段號 標志標志始址始址. 0 執(zhí)行執(zhí)行 218 1

34、只讀只讀 542 2讀讀/寫寫 103段的共享存儲管理分段存儲管理系統(tǒng)的維護可采用如下幾種措施: (1)在段表中設置一個段長值，以指明該段的長度。當存儲訪問時，段地址的位移量與段長相比較，如超越段長，便發(fā)出越界中斷信號。 (2) 建立存取控制,在段表的每個表目中，還添加存取方式項。 (3) 采用存儲維護鍵。 在一個段式存儲管理系統(tǒng)中，經(jīng)過在段表中施加段長、存取控制、設置存儲維護鍵等，可提供一個多級的存儲維護體系。存儲管理分段與分頁的區(qū)別與聯(lián)絡分段與分頁的區(qū)別與聯(lián)絡 分段與分頁的區(qū)別分段與分頁的區(qū)別 1分頁的作業(yè)地址空間是單一的線性地分頁的作業(yè)地址空間是單一的線性地址空間，而分段作業(yè)的地址空間是

35、二維的。址空間，而分段作業(yè)的地址空間是二維的。 2頁頁是信息的是信息的物理物理單位，大小固定。單位，大小固定。段段是信息的邏輯單位，其長度不定。是信息的邏輯單位，其長度不定。 3分頁管理是單段式虛擬存儲系統(tǒng)，而分頁管理是單段式虛擬存儲系統(tǒng)，而分段存儲管理實現(xiàn)多段式虛擬存儲系統(tǒng)。分段存儲管理實現(xiàn)多段式虛擬存儲系統(tǒng)。存儲管理 段式管理的主要優(yōu)點 1便于程序模塊化處置和便于處置變換的數(shù)據(jù)構造。2便于動態(tài)銜接。3便于共享分段。4可以實現(xiàn)虛擬存儲器，使作業(yè)的地址空間不受主存容量的限制。 段式管理的主要缺陷 1和分頁管理一樣，處置機要為地址變換破費時間；要為表格提供附加的存儲空間；這使操作系統(tǒng)復雜化。2為

36、滿足分段的動態(tài)增長和減少外零頭，要采用拼接手段。3分段的最大尺寸遭到主存可用空間的限制。存儲管理 4.6.4 段頁式管理的根本思想 分段構造具有邏輯上明晰的優(yōu)點，但它的一個致命弱點是每個段必需占據(jù)主存儲器的延續(xù)區(qū)域，于是，要裝入一個分段時能夠要挪動已在主存儲器中的信息，為了抑制這個缺陷，可兼用分段和分頁的方法，構成段頁式存儲管理。 每個作業(yè)仍按邏輯分段，但對每一段不是按單一的延續(xù)整體存放到存儲器中，而是把每個段再分成假設干個頁面，每一段不用占據(jù)延續(xù)的主存空間，可把它按頁存放在不延續(xù)的主存塊中。存儲管理 4.6.5 段頁式管理的實現(xiàn)原理 1 虛地址的構成 一個進程中所包含的具有獨立邏輯功能的程序

37、和數(shù)據(jù)仍被劃分為段，并有各自的段號S。把段劃成假設干個頁，和頁式系一致樣。段號段號頁號頁號 頁內(nèi)地址頁內(nèi)地址存儲管理 2 段表和頁表 在段頁式系統(tǒng)中,每個分段又被分成假設干個固定大小的頁面，那么每個段又必需建立一張頁表把段中的虛頁變換成內(nèi)存中的實踐頁面。顯然，與頁式管理時一樣，頁表中也要有相應的實現(xiàn)缺頁中斷處置和頁面維護等功能表項。 每個段有一個頁表，段表中應有專項指出該段所對應頁表的頁表始址和頁表長度。存儲管理段表、頁表、段表地址存放器。為了進展地址轉換，系統(tǒng)為每個作業(yè)建立一個段表，并且要為該作業(yè)段表中的每一個段建立一個頁表。系統(tǒng)中有一個段表地址存放器來指出作業(yè)的段表起始地址和段表長度。存儲

38、管理 3.動態(tài)地址變換過程 關鍵問題仍是如何將二維虛地址映射成一維實地址，為了實現(xiàn)動態(tài)地址變換。 段頁式系統(tǒng)必需為每個作業(yè)建立一張段表，段表表目中的地址部分指出該段的頁表在主存的始址。 為每個段建立一張頁表，每個表目指示該頁所在主存的頁面號。 每個作業(yè)有一個段表地址存放器，指示它的段表所在位置和段表長度。 設置快速聯(lián)想存放器，存放當前最常用的段號S，頁號P和對應的內(nèi)存頁面與其它控制用欄目。存儲管理 查找方法:假設所訪問的段或頁在快速聯(lián)想存放器中，那么系統(tǒng)不再訪問內(nèi)存中的段表、頁表。把快速聯(lián)想存放器中的值與頁內(nèi)相對地址D拼接起來得到內(nèi)存地址。假設快速聯(lián)想存放器中沒有，才去經(jīng)過段表、頁表進展內(nèi)存地

39、址查找。存儲管理慢速地址轉換過程慢速地址轉換過程 存儲管理假設運轉進程訪問虛地址假設運轉進程訪問虛地址v=(s,p,d)，在沒有聯(lián)想存，在沒有聯(lián)想存放器的情況下，地址變換過程如下：放器的情況下，地址變換過程如下： 1由段表控制存放器確定段表在主存中的位由段表控制存放器確定段表在主存中的位置。置。 2將虛地址中的段號和控制存放器中的段表將虛地址中的段號和控制存放器中的段表大小比較，以確保其訪問的有效性。大小比較，以確保其訪問的有效性。 3硬件地址轉換機構根據(jù)虛地址中的段號硬件地址轉換機構根據(jù)虛地址中的段號S，得到欲訪問段在該作業(yè)的段表中的表目。并驗證存得到欲訪問段在該作業(yè)的段表中的表目。并驗證存取權限，然后，檢查分段存在標識取權限，然后，檢查分段存在標識