段頁式存儲管理與動態(tài)地址重定位

1、段頁式存儲管理與動態(tài)地址重定位本章學(xué)習(xí)目標(biāo)本章學(xué)習(xí)目標(biāo) 存儲管理的目的和四大基本功能。 實存管理中講述了固定分區(qū)存儲管理、可變式分區(qū)存儲管理、純分頁存儲管理三種存儲管理方案的實現(xiàn)原理，內(nèi)存的分配與回收方法. 虛存管理以請求式分頁存儲管理為重點，講述其實現(xiàn)原理和動態(tài)地址重定位過程. 總結(jié)各種存儲管理方案中存在的碎片和抖動問題及解決方法 第1頁/共81頁4.1 存儲管理的功能存儲管理的功能 4.1.1 內(nèi)存的分配與回收 4.1.2 地址重定位 4.1.3 存儲保護 4.1.4 虛擬存儲器 返回首頁第2頁/共81頁圖4.1 多級存儲器體系示意圖第3頁/共81頁4.1.1 內(nèi)存的分配與回收內(nèi)存的分配與

2、回收 內(nèi)存分配按分配時機的不同，可分為兩種方式。（1）靜態(tài)存儲分配（2）動態(tài)存儲分配 返回本節(jié)第4頁/共81頁4.1.2 地址重定位地址重定位 1內(nèi)存空間（或物理空間） 2邏輯空間（如圖4.2所示） 3地址重定位（分為：靜態(tài)地址重定位和動態(tài)地址重定位） 第5頁/共81頁圖4.2 作業(yè)的名空間、邏輯地址空間和裝入后的物理空間第6頁/共81頁圖4.3 靜態(tài)地址重定位和動態(tài)地址重定位示意圖（b）采用動態(tài)重定位時內(nèi)存空 間及地址重定位示意圖（a）采用靜態(tài)重定位后的內(nèi)存空間返回本節(jié)第7頁/共81頁4.1.3 存儲保護存儲保護（1）上、下界存儲保護：上、下界保護是一種簡單的存儲保護技術(shù)。如圖4.4（a）所

3、示 （2）基址限長存儲保護：上、下界保護的一個變種是采用基址限長存儲保護。如圖4.4（b）所示。 第8頁/共81頁（a）上、下界保 （b）基址限長保護圖4.4 界限寄存器的兩種存儲保護方式返回本節(jié)第9頁/共81頁4.1.4 虛擬存儲器虛擬存儲器 虛擬存儲技術(shù)的基本思想是把有限的內(nèi)存空間與大容量的外存統(tǒng)一管理起來，構(gòu)成一個遠大于實際內(nèi)存的、虛擬的存儲器。即把兩級存儲器當(dāng)作一級存儲器來看待。 對用戶而言，感覺到系統(tǒng)提供了一個大容量的內(nèi)存，供用戶使用，但這樣大容量的內(nèi)存實際上并不存在，是一種虛擬的存儲器，因此把具有這種功能的存儲管理技術(shù)稱為虛擬存儲管理。返回本節(jié)第10頁/共81頁4.2 實存管理實存

4、管理 4.2.1 固定分區(qū)存儲管理 4.2.2 可變式分區(qū)存儲管理 4.2.3 純分頁存儲管理 4.2.4 純分段存儲管理 返回首頁第11頁/共81頁4.2.1 固定分區(qū)存儲管理固定分區(qū)存儲管理 固定分區(qū)存儲管理是實現(xiàn)多道程序設(shè)計的最簡單的一種存儲管理技術(shù)。 其基本思想是，在作業(yè)未進入內(nèi)存之前，就由操作員或操作系統(tǒng)把內(nèi)存可用空間劃分成若干個固定大小的存儲區(qū)，除操作系統(tǒng)占用一個區(qū)域外，其余區(qū)域為系統(tǒng)中多個用戶共享，因為在系統(tǒng)運行期間，分區(qū)大小、數(shù)目都不變，所以固定式分區(qū)也稱為靜態(tài)分區(qū)（如圖4.5所示）。 第12頁/共81頁圖4.5 固定式分區(qū)內(nèi)存分配示意圖（a）和（b）固定式分區(qū)說明表返回本節(jié)第

5、13頁/共81頁4.2.2 可變式分區(qū)存儲管理可變式分區(qū)存儲管理 1空閑分區(qū)的組織形式 2內(nèi)存的分配與回收 3常用的分配算法 4可變式分區(qū)的地址重定位第14頁/共81頁圖4.6 可變式分區(qū)內(nèi)存使用情況示意圖 第15頁/共81頁1空閑分區(qū)的組織形式空閑分區(qū)的組織形式 在可變式分區(qū)存儲管理中，常把空閑區(qū)組成空閑分區(qū)表或空閑分區(qū)鏈表的形式。 空閑分區(qū)鏈表的組織是這樣的：在每個空閑分區(qū)的起始部分開辟出一個單元，存放一個鏈表指針和該分區(qū)的大小，鏈表指針指向下一個空閑分區(qū)。 第16頁/共81頁圖4.7 首次適應(yīng)算法的空閑分區(qū)鏈表組織形式 第17頁/共81頁2內(nèi)存的分配與回收內(nèi)存的分配與回收 當(dāng)某一個用戶作

6、業(yè)完成釋放所占分區(qū)時，系統(tǒng)應(yīng)進行回收。在可變式分區(qū)中，應(yīng)該檢查回收區(qū)與內(nèi)存中前后空閑區(qū)是否相鄰，若相鄰，則應(yīng)進行合并，形成一個較大的空閑區(qū)，并對相應(yīng)的鏈表指針進行修改；若不相鄰，應(yīng)將空閑區(qū)插入到空閑區(qū)鏈表的適當(dāng)位置。第18頁/共81頁3常用的分配算法常用的分配算法 （1）首次適應(yīng)算法 （2）最佳適應(yīng)算法 （3）最差適應(yīng)算法 第19頁/共81頁圖4.8 最佳適應(yīng)算法的空閑分區(qū)鏈表組織形式第20頁/共81頁圖4.9 最差適應(yīng)算法的空閑分區(qū)鏈表組織形式第21頁/共81頁圖4.10 內(nèi)存使用情況第22頁/共81頁圖4.11 用三種適應(yīng)算法處理同一作業(yè)序列第23頁/共81頁4可變式分區(qū)的地址重定位可變式

7、分區(qū)的地址重定位 可變式分區(qū)的地址重定位可采用靜態(tài)重定位，也可采用動態(tài)重定位。采用動態(tài)重定位的可變式分區(qū)管理技術(shù)，在執(zhí)行內(nèi)存分配時，如無足夠大空閑塊，應(yīng)考慮實現(xiàn)緊湊操作。其分配算法如圖4.12所示。 可變式分區(qū)的存儲保護可采用基址限長存儲保護方式。第24頁/共81頁圖4.12 采用動態(tài)重定位的可變式分區(qū)分配算法返回本節(jié)第25頁/共81頁4.2.3 純分頁存儲管理純分頁存儲管理 1純分頁存儲管理中存儲塊的分配與回收 2純分頁存儲管理的地址重定位問題 3聯(lián)想存儲器 4存儲保護返回本節(jié)第26頁/共81頁1純分頁存儲管理中存儲塊的分配與回收純分頁存儲管理中存儲塊的分配與回收 純分頁存儲管理中，存儲塊的

8、分配與回收算法比較簡單。當(dāng)作業(yè)有存儲分配請求時，可以根據(jù)邏輯地址的大小計算出需要多少存儲塊，然后將空閑塊分配給它們使用。通常有兩種記錄空閑存儲塊的方法：位圖法和鏈表法。第27頁/共81頁操作系統(tǒng)操作系統(tǒng)作業(yè)1 作業(yè)2 作業(yè)2作業(yè)1 作業(yè)2 作業(yè)1 作業(yè)2 1110100110101010（a）存儲塊使用情況 （b）存儲塊使用情況的位圖表示圖4.13 存儲塊的位圖管理法第28頁/共81頁2純分頁存儲管理的地址重定位問題純分頁存儲管理的地址重定位問題 要使不連續(xù)的、分散的用戶程序能正常運行，須采用動態(tài)地址重定位。此時，可采用重定位寄存器方式，如分頁太多，則重定位寄存器用得太多。 通?？稍趦?nèi)存中為每

9、個作業(yè)開辟一塊特定區(qū)域，建立起作業(yè)的邏輯頁與存儲塊之間的對應(yīng)表格關(guān)系，這種表常稱為頁面映像表，簡稱頁表（如圖4.144.15所示）。第29頁/共81頁圖4.14 純分頁存儲管理示意圖第30頁/共81頁圖4.15 純分頁存儲管理地址重定位實現(xiàn)過程第31頁/共81頁3聯(lián)想存儲器聯(lián)想存儲器 為了提高查表的速度，人們在分頁地址變換機構(gòu)中，加入一組高速緩沖存儲器，用來存放當(dāng)前作業(yè)的最常用的頁號和與之相應(yīng)的物理塊號。一般稱這樣的寄存器組為快表或聯(lián)想存儲器。采用聯(lián)想存儲器和內(nèi)存中頁表相結(jié)合的分頁地址變換過程如圖4.16所示。 應(yīng)用聯(lián)想存儲器和頁表相結(jié)合的方式，可有效地提高系統(tǒng)動態(tài)地址轉(zhuǎn)換的速度，是一種行之有

10、效的方法。第32頁/共81頁利用快表查找 利用頁表查找 利用頁表中查找到的頁號、塊號更新快表圖4.16 采用快表和頁表相結(jié)合的分頁地址變換過程示意圖第33頁/共81頁4存儲保護存儲保護 存儲信息保護可從兩個方面實現(xiàn): 在進行地址變換時，產(chǎn)生的頁號應(yīng)小于頁表長度，否則視為越界訪問，這類似于基址限長存儲保護； 可在頁表中增加存取控制和存儲保護的信息，對每一個存儲塊，可允許四種保護方式：禁止做任何操作，只能執(zhí)行，只能讀，能讀/寫，當(dāng)要訪問某頁時，先判斷該頁的存取控制和存儲保護信息是否允許。返回本節(jié)第34頁/共81頁4.2.4 純分段存儲管理純分段存儲管理 1分段管理的基本思想 2地址變換 3分段與分

11、頁的區(qū)別返回本節(jié)第35頁/共81頁1分段管理的基本思想分段管理的基本思想 分段存儲管理是以段為基本單位分配內(nèi)存，且每一段必須連續(xù)的內(nèi)存空間，但各段之間不要求連續(xù)。由于各段的長度不一樣，所以分配的內(nèi)存空間大小也不一樣。分段存儲管理的邏輯地址結(jié)構(gòu)如下：段號段號S段內(nèi)位移段內(nèi)位移W第36頁/共81頁2地址變換地址變換圖4.17 分段存儲管理的地址變換示意圖 第37頁/共81頁表4.1 段表段號內(nèi)存起始地址段長02105001235020210090表4.2 邏輯地址段號段內(nèi)位移04301102500第38頁/共81頁3分段與分頁的區(qū)別分段與分頁的區(qū)別（1）頁是信息的物理單位。段是信息的邏輯單位。（2

12、）分頁存儲管理的作業(yè)地址空間是一維的，而分段存儲管理的是二維的。（3）頁的大小固定且由系統(tǒng)確定，是等長的。而段的長度不定，它是由具有相對完整意義的信息長度確定。（4）分頁的優(yōu)點體現(xiàn)在內(nèi)存空間的管理上，而分段的優(yōu)點體現(xiàn)在地址空間的管理上。返回本節(jié)第39頁/共81頁4.3 虛擬存儲器管理虛擬存儲器管理 4.3.1 虛擬存儲器的概念 4.3.2 請求式分頁存儲管理與動態(tài)地址重定位 4.3.3 頁面置換算法 4.3.4 請求式分頁存儲管理性能分析舉例 4.3.5 請求式分段存儲管理與動態(tài)地址重定位 4.3.6 段頁式存儲管理與動態(tài)地址重定位 返回首頁第40頁/共81頁4.3.1 虛擬存儲器的概念虛擬存

13、儲器的概念 虛擬存儲器就是為用戶提供了一個存儲容量比實際主存大得多的存儲器。 用戶在編程時可以不考慮實際內(nèi)存的大小，認為自己編寫多大程序就有多大的虛擬存儲器對應(yīng)。每個用戶可以在自己的邏輯地址空間中編程，在各自的虛擬存儲器上運行。 采用虛擬存儲管理技術(shù)，提供存儲擴充的功能。 返回本節(jié)第41頁/共81頁4.3.2 請求式分頁存儲管理與動態(tài)地址重定位請求式分頁存儲管理與動態(tài)地址重定位 先把內(nèi)存空間劃分成大小相等的塊，將用戶邏輯地址空間劃分成與塊相等的頁，每頁可裝入到內(nèi)存中任一塊中，這都類似于純分頁式存儲管理。在請求式分頁存儲管理的地址重定位時，可能會出現(xiàn)所需頁面不在主存的情況，如圖4.18所示是請求

14、式分頁存儲管理的存儲映像。 請求式分頁存儲管理中的地址重定位和缺頁中斷處理過程如圖4.19所示。 第42頁/共81頁圖4.18 請求式分頁存儲管理示意圖第43頁/共81頁圖4.19 請求式分頁存儲管理缺頁中斷處理過程示意圖返回本節(jié)第44頁/共81頁4.3.3 頁面置換算法頁面置換算法 1最優(yōu)算法（OPT算法） 2先進先出算法（FIFO算法） 3最久未使用頁面置換算法（LRU算法） 4LRU近似算法第45頁/共81頁1最優(yōu)算法（最優(yōu)算法（OPT算法）算法） 最理想的頁面置換算法是：從內(nèi)存中移出以后不再使用的頁面；如無這樣的頁面，則選擇以后最長時間內(nèi)不需要訪問的頁。這就是最優(yōu)算法的思想。第46頁/

15、共81頁2先進先出算法（先進先出算法（FIFO算法）算法） 這種算法的基本思想是：總是先淘汰那些駐留在內(nèi)存時間最長的頁面，即先進入內(nèi)存的頁面先被置換掉。理由是：最先進入內(nèi)存的頁面不再被訪問的可能性最大。這種算法實現(xiàn)起來比較簡單。如圖4.20所示 第47頁/共81頁圖4.20 先進先出算法存儲分塊表構(gòu)造 第48頁/共81頁3最久未使用頁面置換算法（最久未使用頁面置換算法（LRU算法）算法） 這種算法的基本思想是，如果某一頁被訪問了，那么它很可能馬上又被訪問；反之，如果某一頁很長時間沒有被訪問，那么最近也不太可能會被訪問。這種算法考慮了程序設(shè)計的局部性原理。其實質(zhì)是，當(dāng)需要置換一頁時，選擇在最近一

16、段時間最久未使用的頁面予以淘汰。第49頁/共81頁4LRU近似算法近似算法 這種算法，只要在存儲分塊表（或頁表）中設(shè)一個“引用位”，當(dāng)存儲分塊表中的某一頁被訪問時，該位由硬件自動置1，并由頁面管理軟件周期性把所有引用位置0。這樣，在一個時間周期T內(nèi)，某些被訪問過的頁面其引用位為1，而未被訪問過的頁面其引用位為0。 根據(jù)引用位的狀態(tài)來判別各頁面最近的使用情況。當(dāng)需要置換一頁面時，選擇其引用位為0的頁，如圖4.214.22所示的算法。第50頁/共81頁圖4.21 LRU近似算法流程第51頁/共81頁圖4.22 LRU近似算法舉例返回本節(jié)第52頁/共81頁4.3.4 請求式分頁存儲管理性能分析舉例請

17、求式分頁存儲管理性能分析舉例 1程序設(shè)計的質(zhì)量 2頁面的大小 3分配的內(nèi)存塊數(shù) 4頁面置換算法性能（如圖4.244.24所示） 第53頁/共81頁圖4.23 FIFO算法性能分析（m=3） 圖4.24 FIFO算法性能分析（m=4）第54頁/共81頁圖4.25 LRU算法性能分析（m=3）第55頁/共81頁圖4.26 LRU算法性能分析（m=4） 返回本節(jié)第56頁/共81頁4.3.5 請求式分段存儲管理與動態(tài)地址重定位請求式分段存儲管理與動態(tài)地址重定位 1程序的邏輯地址結(jié)構(gòu) 2段表 3請求式分段動態(tài)地址變換過程 4請求式分段存儲管理的優(yōu)、缺點第57頁/共81頁圖4.27 分段的邏輯地址空間第5

18、8頁/共81頁1程序的邏輯地址結(jié)構(gòu)程序的邏輯地址結(jié)構(gòu) 請求式分段存儲管理的邏輯地址結(jié)構(gòu)由段號s和段內(nèi)位移量d組成，如下圖所示。用戶邏輯地址空間的大小，由組成段號和段內(nèi)位移量的二進制位數(shù)來決定。段號(s)段內(nèi)位移量(d)23 16 15 0第59頁/共81頁2段表段表 為了實現(xiàn)動態(tài)地址變換和存儲保護，系統(tǒng)要為每一個作業(yè)建立一張段表。段表中的每一個表目對應(yīng)著作業(yè)地址空間的一個程序段，其一般格式為：段號段長狀態(tài)位引用位改變位RWEA起始地址第60頁/共81頁3請求式分段動態(tài)地址變換過程請求式分段動態(tài)地址變換過程圖4.28 請求式分段動態(tài)地址變換第61頁/共81頁4請求式分段存儲管理的優(yōu)、缺點請求式分

19、段存儲管理的優(yōu)、缺點 請求式分段存儲管理有如下優(yōu)點： （1）可提供大容量的虛存 （2）允許動態(tài)增加段的長度 （3）便于段的動態(tài)鏈接 （4）便于實現(xiàn)程序段的共享 （5）便于實現(xiàn)存儲保護第62頁/共81頁 請求分段存儲管理的缺點是進行地址變換和實現(xiàn)緊湊操作要花費處理機時間，為管理各分段要設(shè)立若干表格，需提供額外的存儲空間，而且也會像請求分頁存儲管理一樣出現(xiàn)系統(tǒng)抖動現(xiàn)象。返回本節(jié)第63頁/共81頁4.3.6 段頁式存儲管理與動態(tài)地址重定位段頁式存儲管理與動態(tài)地址重定位（1）作業(yè)地址空間進行段式管理。（2）每段內(nèi)再分成若干大小固定的頁，每段都從零開始為自己的各頁依次編寫連續(xù)的頁號。（3）對內(nèi)存空間的管

20、理仍然和分頁存儲管理一樣，將其分成若干個和頁面大小相同的物理塊。（4）作業(yè)的邏輯地址包括3個部分：段號、頁號和頁內(nèi)位移。（5）為實現(xiàn)地址變換，段頁式系統(tǒng)設(shè)立了段表和頁表。第64頁/共81頁圖4.29 段表、頁表和內(nèi)存的關(guān)系 返回本節(jié)第65頁/共81頁4.4 碎片與抖動問題碎片與抖動問題 分區(qū)存儲管理分為固定式分區(qū)和可變式分區(qū)存儲管理兩種。對于固定式分區(qū)存儲管理來說，其分區(qū)大小是固定的，而一個作業(yè)的大小不可能與固定的分區(qū)大小剛好相等，所以容易產(chǎn)生內(nèi)碎片問題，即已分配給某作業(yè)的固定分區(qū)中有作業(yè)使用不到的空閑內(nèi)存區(qū)域。而可變式分區(qū)存儲管理較好地解決了內(nèi)碎片問題，一個作業(yè)需要多大內(nèi)存就分配給它多大內(nèi)存

21、。 返回首頁第66頁/共81頁 解決碎片問題的比較好的方法是采用分頁技術(shù)，在純分頁存儲管理系統(tǒng)中，因存儲區(qū)劃分成固定大小的塊，而用戶作業(yè)也劃分成與塊相等的若干頁，每個作業(yè)調(diào)入內(nèi)存時，除最后一個頁面可能有頁內(nèi)碎片出現(xiàn)外，其余頁不存在碎片問題，一般來說，平均每個作業(yè)可能有半頁的內(nèi)碎片。 純分頁存儲管理技術(shù)較為有效地利用了內(nèi)存空間。 第67頁/共81頁 避免抖動現(xiàn)象最根本的方法是控制多道程序的道數(shù)，使得每個用戶作業(yè)都有足夠的內(nèi)存空間可供使用。但作業(yè)的個數(shù)又不能太少，否則，會影響處理機的利用率。最好是使處理機利用率較高，又不致于使系統(tǒng)發(fā)生抖動，這是一個很難解決的問題，牽扯到程序的局部性問題，并需借助于

22、工作集模型。第68頁/共81頁 對請求式分段存儲管理系統(tǒng)而言，它考慮了編程時的邏輯結(jié)構(gòu)，把程序分成若干段，以段為單位調(diào)入內(nèi)存運行。這樣，在內(nèi)存分配和回收時，類似于可變式分區(qū)操作，容易造成外部碎片問題。而在實現(xiàn)段的調(diào)入、調(diào)出問題上，又類似于請求式分頁存儲管理，可能造成系統(tǒng)的抖動現(xiàn)象，所以請求式分段存儲管理系統(tǒng)是比較復(fù)雜的。返回本節(jié)第69頁/共81頁本章小結(jié)本章小結(jié) 存儲管理的研究對象主要是中央處理器能直接訪問的主存儲器，其目的一方面是為了在多道程序環(huán)境下，提高主存資源的利用率；另一方面也方便用戶對主存儲器這一關(guān)鍵性資源的使用。第70頁/共81頁 請求式分頁存儲管理的性能可從程序設(shè)計的質(zhì)量、頁面的

23、大小、分配的內(nèi)存塊數(shù)和頁面置換算法的性能等幾個角度來考慮。 請求式分頁存儲管理提供了大容量的虛存，更有效地利用了內(nèi)存，方便了用戶。缺點是為了處理缺頁中斷，增加了處理機開銷，而且可能出現(xiàn)抖動問題，降低系統(tǒng)的效率。第71頁/共81頁 總之，存儲管理技術(shù)是在不斷發(fā)展著的，隨著現(xiàn)代技術(shù)的日新月異，大規(guī)模、超大規(guī)模集成技術(shù)的飛躍發(fā)展，也隨著人們對計算機應(yīng)用的不斷深入，必會對存儲管理提出更多新的問題，存儲管理技術(shù)也必將在新技術(shù)的帶動下，得到進一步的發(fā)展、完善，為人們更好地、更有效地使用計算機提供幫助。第72頁/共81頁4.1.1 內(nèi)存的分配與回收內(nèi)存的分配與回收 內(nèi)存分配按分配時機的不同，可分為兩種方式。（1）靜態(tài)存儲分配（2）動態(tài)存儲分配 返回本節(jié)第73頁/共81頁圖4.3 靜態(tài)地址重定位和動態(tài)地址重定位示意圖（b）采用動態(tài)重定位時內(nèi)存空 間及地址重定位示意圖（a）采用靜態(tài)重定位后的內(nèi)存空間返回本節(jié)第74頁/共81頁4.2.1 固定分區(qū)存儲管理固定分區(qū)存儲管理 固定分區(qū)存儲管理是實現(xiàn)多道程序設(shè)計的最簡單的一種存儲管理技術(shù)。 其基本思想是，在作業(yè)未進入內(nèi)存之前，就由操作員或操作系統(tǒng)把內(nèi)存可用空間劃分成若干個固定大小的存儲區(qū)，除操作系統(tǒng)占用一個區(qū)域外，其余區(qū)域為系統(tǒng)中多個