第6章 存儲(chǔ)管理

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

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

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

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

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

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