第6章 存儲管理

第六章存儲管理6.1存儲管理的基本概念6.2實存儲管理技術(shù)6.3虛擬存儲系統(tǒng)的基本概念6.4分頁存儲管理6.5請求分段存儲管理6.6段頁式存儲管理6.1存儲管理的基本概念6.1.1存儲器的層次中央處理器能直接訪問的存儲器稱為內(nèi)存儲器，它包括高速的緩沖存儲器和主存儲器。中央處理器不能直接訪問輔助存儲器。從高速緩沖存儲器到輔助存儲器，容量越來越大，一般每級之間相差幾個數(shù)量級。而訪問數(shù)據(jù)的速度則越來越慢，價格也越來越便宜。6.1.2地址重定位(relocation)

1．邏輯地址空間用戶在編程或編輯源程序時，將其源程序存于程序員建立的符號名字空間（簡稱名空間）內(nèi)。編譯后一個目標程序所限定的地址范圍稱為該作業(yè)的邏輯地址空間或相對地址。2．物理地址空間所謂物理地址空間（也稱存儲空間）是指主存中物理單元的集合。這些單元的編號稱為物理地址或絕對地址。名空間、邏輯地址空間和物理地址空間由于一個作業(yè)裝入到與其地址空間不一致的存儲空間所引起的，對有關(guān)地址部分的調(diào)整過程稱為地址的重定位。這個調(diào)整過程就是把作業(yè)地址空間中使用的邏輯地址變換成主存中物理地址的過程。這種地址變換也稱為地址映射。3．地址重定位4．重定位類型(1)靜態(tài)重定位靜態(tài)重定位是在程序運行之前由裝配程序完成的。當操作系統(tǒng)為目標程序分配了一個以B為起始地址的存儲空間后，重定位過程就是把每個與地址有關(guān)的項都加上B即可。主要缺點如下：

①要求給每個作業(yè)分配一個連續(xù)的存儲空間，且在作業(yè)的整個執(zhí)行期間不能再移動，因而也就不能實現(xiàn)重新分配主存。不利于主存空間的充分利用。

②用戶必須事先確定所需的存儲量，若所需的存儲量超過可用存儲空間時，用戶必須考慮覆蓋結(jié)構(gòu)。

③用戶之間難以共享主存中的同一程序副本。(2)動態(tài)重定位動態(tài)重定位的主要優(yōu)點如下：①用戶作業(yè)不要求分配連續(xù)的存儲空間。②用戶作業(yè)在執(zhí)行過程中，可以動態(tài)申請存儲空間和在主存中移動。③有利于程序段的共享。動態(tài)重定位的主要缺點如下：①需要附加的硬件支持。②實現(xiàn)存儲管理的軟件算法比較復(fù)雜。6.1.3存儲管理的目的和功能目的：要盡可能地滿足用戶需求和提高主存儲器的使用效率，使主存儲器在成本、速度和規(guī)模之間獲得較好的權(quán)衡。功能：存儲分配(memoryallocation)地址變換(memorymap)

“擴充”主存容量(Memoryextension)存儲保護(memoryprotection)6.1.4存儲分配方式靜態(tài)分配要求在一個作業(yè)裝入時必須分配所需的全部存儲空間動態(tài)分配在其執(zhí)行過程中可根據(jù)需要申請附加的存儲空間。而且一個作業(yè)已占用的部分存儲空間不再需要時，可以請求歸還給系統(tǒng)。6.2實存儲管理技術(shù)6.2.1單一連續(xù)區(qū)管理存儲器在概念上被分成兩部分：一部分供操作系統(tǒng)使用；另一部分為用戶空間給用戶使用。單一連續(xù)區(qū)分配方案的優(yōu)點是：方法簡單，易于實現(xiàn)；缺點是：它僅適用于單道程序，因而不能使處理機和主存得到充分利用。6.2.2固定式和可變式分區(qū)存儲管理1．固定式分區(qū)存儲管理固定式分區(qū)的基本思想是在系統(tǒng)初始化時，把存儲空間劃分為若干個一樣大小或任意大小的空間；每個空間分配給某一個作業(yè)使用。由于這些存儲空間是在系統(tǒng)啟動時劃定的，在用戶作業(yè)裝入及運行過程中，其空間的大小和邊界是不能改變的。所以，稱這種存儲器的劃分方式為固定式分區(qū)，也稱為靜態(tài)分區(qū)。2．可變分區(qū)存儲管理隨著作業(yè)一個個被調(diào)入主存運行，并且分給它們一個相應(yīng)于作業(yè)大小的主存分區(qū)使用，直到作業(yè)完成后才釋放其所占用的主存分區(qū)。由于各作業(yè)大小和完成的時間是各不相同的，這樣經(jīng)過一段時間后，主存就由原來一個完整的分區(qū)而變成了多個分區(qū)，這些分區(qū)中有些分區(qū)被作業(yè)占用，有些分區(qū)是空閑的。已分配分區(qū)表未分配分區(qū)表2．可變分區(qū)存儲管理3．分配算法(1)最佳適應(yīng)算法(bestfit)(2)最壞適應(yīng)算法(worstfit)(3)首次適應(yīng)算法(firstfit)(4)下次適應(yīng)算法(nextfit)(5)快速適應(yīng)算法(quickfit)可變式分區(qū)分配程序流程回收區(qū)與空閑區(qū)的合并6.2.3可重定位分區(qū)存儲管理“內(nèi)存緊縮(compact)”技術(shù)可重定位分區(qū)分配算法6.2.4分區(qū)的存儲保護界限寄存器保護法保護健法在程序狀態(tài)字中則設(shè)置相應(yīng)的保護鍵開關(guān)字段。對不同的進程賦予不同的開關(guān)代碼以和被保護的存儲塊中的保護鍵匹配。保護鍵可設(shè)置成對讀、寫同時保護或只對讀、寫進行單項保護。6.3虛擬存儲系統(tǒng)的基本概念6.3.1虛擬存儲器(virtualmemory)廣義地說，只要編程序時使用的不是實際主存地址，即可認為是使用了虛擬存儲器。具體地說，虛擬存儲器是系統(tǒng)為了滿足用戶對存儲器容量的巨大需求而虛構(gòu)的一個非常大的地址空間，從而使用戶在編程序時無需擔(dān)心存儲器的不足，似乎有一個無限大的存儲器供用戶使用一樣。對于用戶，虛擬存儲系統(tǒng)指令地址部分所限定的地址空間比實際存儲空間大得多。對系統(tǒng)來說，虛擬存儲器是借助各種表格結(jié)構(gòu)體現(xiàn)的虛擬空間。6.3.2實現(xiàn)虛擬存儲器的基本原理基本辦法：利用表格為用戶構(gòu)造一個虛存空間，作為實現(xiàn)虛擬存儲管理的機構(gòu)。提供一個大容量的高速外存來存放進入虛存空間的實際信息，這是實現(xiàn)虛擬存儲器的物質(zhì)基礎(chǔ)。把主存作為用戶虛存空間中的程序和數(shù)據(jù)得以運行的緩沖區(qū)。受兩個條件的限制：指令中的地址長度的限制，因為進程訪問的虛地址應(yīng)限制在指令地址長度所能表示的范圍內(nèi)。外存儲器容量大小的限制，用戶的虛空間不能超過外存的作業(yè)存放空間。6.4分頁存儲管理6.4.1分頁存儲管理的實現(xiàn)原理1．等分主存2．用戶邏輯地址空間的分頁3．邏輯地址的表示4．主存分配原則5．頁表(pagetable)和頁表地址寄存器6.4.2簡單分頁存儲管理1．主存的分配與回收(1)頁表(PT)(2)存儲分塊表(MBT)2．分配算法當進程或作業(yè)要求分配主存塊時，首先檢查是否有足夠的空閑塊，如果沒有，則本次無法分配。如果有則首先分配設(shè)置頁表，將分到的主存塊號添入頁表中。3．地址變換4．超高速緩存6.4.3請求式分頁存儲管理1．頁表的擴充存在位(present/absent)修改位(modified)引用位(referenced)輔存地址(swapareaaddress)其它：如頁面保護位(protection)，禁止緩存位(cachedisabled)，虛擬時間(virtualtime)等。2．地址變換3．缺頁中斷處理4．調(diào)取頁面策略請求式調(diào)頁：僅當需要時才調(diào)取頁面的策略，采用請求式調(diào)頁策略的分頁系統(tǒng)稱為請求式分頁預(yù)調(diào)頁：事先調(diào)取頁面的策略6.4.4請求式調(diào)頁存儲管理的頁面置換算法1．先進先出頁面置換算法(FIFO)FIFO(firstinfirstout)算法是最簡單的頁面置換算法。這種算法的基本思想是：當需要淘汰一個頁面時，總是選擇駐留主存時間最長的頁面進行淘汰，即先進入主存的頁面先淘汰。其理由是：最早調(diào)入主存的頁面，其不再被使用的可能性最大。缺頁中斷率PFF=12/15=80％。2．最佳置換算法(OPT)最佳置換算法的基本思想是：從主存中移出永遠不再需要的頁面；如無這樣的頁面存在，則選擇最長時間不需要訪問的頁面。這種算法是貝萊迪(Belady)于1966年提出的。缺頁中斷率為8/15=53％。3．最近最久未使用頁面置換算法(LRU)這種算法的基本思想是，利用局部性原理，根據(jù)一個作業(yè)在執(zhí)行過程中過去的頁面訪問歷史來推測未來的行為。它認為過去一段時間里不曾被訪問過的頁面，在最近的將來可能也不會再被訪問。所以這種算法的實質(zhì)是：當需要淘汰一個頁面時，總是選擇在最近一段時間內(nèi)最久不用的頁面予以淘汰。缺頁中斷率為11/15=75％6.4.5頁面抖動和工作集模型1．局部性原理(localityprinciple)(1)時間局部性指某個位置量近被訪問了，那么往往很快又要被再次訪問。這一特性可通過程序中的循環(huán)，常用于程序，堆棧這類程序結(jié)構(gòu)來說明。(2)空間局部性指一旦某個位置被訪問了，那么它附近的位置也將被訪問。這一特性可通過程序中數(shù)組處理、程序代碼的執(zhí)行，以及程序員傾向于將常用的變量存放在一起等特點來說明。2．抖動(thrashing)（或稱顛簸）如果分配給進程的存儲塊數(shù)量小于進程所需要的最小值，進程的運行將很頻繁地產(chǎn)生缺頁中斷。這種頻率非常高的頁面置換現(xiàn)象稱之為抖動。如果一個進程用于頁面置換工作的系統(tǒng)開銷多于代碼執(zhí)行時間時，稱該進程是抖動的。抖動將引起嚴重的系統(tǒng)性能下降。3．工作集模型(workingset)工作集模型是基于局部性原理假設(shè)的。這種模型使用了一個參數(shù)“Δ”來定義工作窗口，其思想是檢查最近的“Δ”頁面引用。最近的“Δ”頁面引用中的頁面集就是工作集。如果一個頁面被經(jīng)常使用，它將在工作集中；如果它不再使用，它將從最后一次被引用起從工作集中去掉。4．程序結(jié)構(gòu)varA：array[1..128]ofarray[1..128]ofinteger；forj：=1to128dofori：=128to128doA[i][j]：=0；varA：array[1..128]ofarray[1..128]ofinteger;fori：=1to128doforj：=128to128doA[i][j]：=0；6.4.6頁面保護(1)擴充頁表的功能(2)存儲保護鍵技術(shù)6.4.7頁式存儲管理的優(yōu)缺點優(yōu)點：(1)由于它不要求作業(yè)或進程的程序段和數(shù)據(jù)在主存中連續(xù)存放，從而有效地解決了碎片問題。(2)請求調(diào)頁管理提供了虛擬存儲器。提高了主存的利用率，更加有利于多道程序的運行和方便用戶，特別是大作業(yè)用戶。缺點：(1)要求有相應(yīng)的硬件支持。這增加了機器成本。(2)為處理缺頁中斷，增加了處理機時間的開銷。(3)可能造成系統(tǒng)抖動，為防止系統(tǒng)抖動所采取的各種措施會增加系統(tǒng)的復(fù)雜性。(4)每個作業(yè)或進程的最后一頁內(nèi)總存有一部分空間得不到利用。這是唯一存在的內(nèi)碎片，平均為半頁大小。6.5請求分段存儲管理6.5.1段式存儲管理的基本思想把程序按內(nèi)容或過程（函數(shù)）關(guān)系分成段，每段有自己的名字。一個用戶作業(yè)或進程所包含的段對應(yīng)于一個二維的線性虛擬空間，也就是一個二維虛擬存儲器。段式管理程序以段為單位分配主存，然后通過地址映射機構(gòu)把段式虛擬地址轉(zhuǎn)換成實際的主存物理地址。6.5.2段式存儲管理的實現(xiàn)原理1．段式虛擬空間2．段式管理的主存分配與釋放段式管理的主存分配與釋放在作業(yè)或進程的執(zhí)行過程中動態(tài)進行。首先，段式管理程序為一個進入主存準備執(zhí)行的進程或作業(yè)分配部分內(nèi)存，以作為該進程的工作區(qū)和放置即將執(zhí)行的程序段。隨著進程的執(zhí)行，進程根據(jù)需要隨時申請調(diào)入新段和釋放老段。當進程要求調(diào)入某一段時，主存中有足夠的空閑區(qū)滿足該段的主存要求，可以采用和可變式分區(qū)存儲管理相同的空閑區(qū)管理方法來實現(xiàn)主存的分配和回收。對于主存中沒有足夠大的空閑區(qū)滿足調(diào)入段的要求時，如果主存中所有的空閑區(qū)總和能滿足要求，則可以使用“內(nèi)存緊縮”的方法，將所有的空閑區(qū)合并后進行分配，否則使用置換算法淘汰主存中的段后再進行分配。3．段式管理的地址變換(1)段表其中：存在位：表示該段是否裝入主存，“1”表示該段在主存，“0”表示不在主存。引用位：如果該段本次在主存中剛被訪問過，則引用位為“1”，否則為“0”。修改位：該段被修改時設(shè)置為“1”，當該段從主存中移出時，由它確定是否寫入輔存。增漲位(increased)：用于動態(tài)擴大段長，當該位為“1”時，該段可以動態(tài)增漲。(2)地址變換過程(2)地址變換過程6.5.3段的共享與保護在段表中設(shè)置一個段長值，以指明該段的長度。建立存取控制，在段表的每個表目中，除指明段長外，還增加“存取方式”項。采用存儲保護鍵。6.5.4分段與分頁的區(qū)別與聯(lián)系分頁的作業(yè)地址空間是單一的線性地址空間，而分段作業(yè)的地址空間是二維的?！绊摗笔切畔⒌摹拔锢怼眴挝?，大小固定。對于分頁活動，用戶是看不見的，而它僅僅用于對主存的管理?！岸巍切畔⒌倪壿媶挝唬此且唤M有意義的信息，其長度不定。分段是用戶可見的活動（分段可以在用戶編程序時確定，也可以在編譯程序時根據(jù)信息的性質(zhì)來劃分