第4章存儲器管理

4.1存儲管理的功能

4.2程序的裝入和鏈接

4.3連續(xù)分配方式4.4對換4.5基本分頁存儲管理方式4.6基本分段存儲管理方式第四章

存儲器管理4.1.1

存儲器的層次結(jié)構(gòu)多級存儲器結(jié)構(gòu)：寄存器：

容量最小、速度最快高速緩存Cache：

容量遠大于寄存器，比主存小兩三個數(shù)量級內(nèi)存RAM：

cpu直接從主存儲器中取得指令和數(shù)據(jù)

磁盤：

低速、價廉、容量最大

4.1.2

存儲器管理的功能一、地址變換二、內(nèi)存分配和回收三、內(nèi)存共享和保護四、內(nèi)存擴充一、地址變換1.邏輯地址和物理地址邏輯地址（相對地址，虛地址）：用戶的程序經(jīng)過匯編或編譯后形成目標代碼，目標代碼通常采用相對地址的形式其首地址為0，其余指令中的地址都相對于首地址來編址不能用邏輯地址在內(nèi)存中讀取信息物理地址（絕對地址，實地址）：內(nèi)存中存儲單元的地址。物理地址可直接尋址。用高級語言編程時，要定義變量、函數(shù)，程序中有函數(shù)調(diào)用，有轉(zhuǎn)向等，都是以它們的名字進行的，程序員在一個“名字空間”駕御自己的程序。通常把程序員用的地址空間為名空間。源程序必須經(jīng)過編譯才能執(zhí)行。程序?qū)⒈话才懦梢粋€從地址0開始的地址空間。這就成為可以執(zhí)行的目標程序，并存入一個以.exe結(jié)尾的文件中。（編譯程序不知道以后操作系統(tǒng)將把程序裝入何處，只好從0地址開始編址。）目標程序中指令地址都是相對0編址的，使用的是相對地址、邏輯地址?？梢詧?zhí)行并不意味著就能執(zhí)行，還必須由操作系統(tǒng)調(diào)入內(nèi)存才能執(zhí)行。通常把編譯程序形成的從0開始編址的地址空間稱為作業(yè)的地址空間。(每個可執(zhí)行程序都有一個自己的地址空間。)邏輯地址(地址空間)示意圖2.重定位（地址映射）含義：將用戶程序中的邏輯地址轉(zhuǎn)換為運行時由機器直接尋址的物理地址稱為地址重定位原因：當程序裝入內(nèi)存時,操作系統(tǒng)要為該程序分配一個合適的內(nèi)存空間，由于程序的邏輯地址與分配到內(nèi)存物理地址不一致,而CPU執(zhí)行指令時，是按物理地址進行的，所以要進行地址轉(zhuǎn)換重定位方式：分為靜態(tài)重定位和動態(tài)重定位

因為多道程序系統(tǒng)中，主存將存放多道作業(yè)，而程序員在編寫程序時，不可能了解自己的程序?qū)⒎旁谥鞔嬷泻翁庍\行，不可能用絕對地址來編寫程序。(1)

靜態(tài)地址重定位在裝入一個作業(yè)時，把作業(yè)中的指令地址全部轉(zhuǎn)換為絕對地址（地址轉(zhuǎn)換工作是在作業(yè)執(zhí)行前集中一次完成的）在作業(yè)執(zhí)行過程中就無須再進行地址轉(zhuǎn)換工作

（2）動態(tài)地址重定位在程序執(zhí)行過程中，在CPU訪問內(nèi)存之前,將要訪問的程序或數(shù)據(jù)地址轉(zhuǎn)換成內(nèi)存地址.動態(tài)重定位依靠硬件地址變換機構(gòu)完成靜態(tài)地址重定位示意圖0100500mova,(500)2345邏輯地址空間裝入程序內(nèi)存空間mova,(1500)2345100011001500靜態(tài)重定位靜態(tài)重定位的優(yōu)缺點優(yōu)點：不需要硬件的支持。

缺點：程序必須占用連續(xù)的內(nèi)存空間；一旦程序裝入后不能移動，不易實現(xiàn)共享。

+

內(nèi)存空間

VR

BR…..動態(tài)地址重定位動態(tài)地址重定位邏輯地址空間動態(tài)地址映射的優(yōu)缺點優(yōu)點：程序占用的內(nèi)存空間是動態(tài)可變的，可以把程序從某個存儲區(qū)移到另一個區(qū)域一個程序不一定要求占用一個連續(xù)的內(nèi)存空間?？梢圆糠值匮b入程序運行。便于多個進程共享同一個程序的代碼。動態(tài)地址重定位的代價：需要硬件的支持。實現(xiàn)存儲管理的軟件算法較為復(fù)雜。4.1.2存儲管理功能一、地址變換二、內(nèi)存分配和回收三、內(nèi)存共享和保護四、內(nèi)存擴充為了有效合理地利用內(nèi)存，設(shè)計內(nèi)存的分配和回收方法時，必須考慮和確定以下幾種策略和數(shù)據(jù)結(jié)構(gòu)：1分配結(jié)構(gòu)：登記內(nèi)存的使用情況2放置策略：確定調(diào)入內(nèi)存的程序和數(shù)據(jù)在內(nèi)存中的位置，即選擇內(nèi)存空閑區(qū)的原則3

交換策略：在需要將某個程序段和數(shù)據(jù)調(diào)入內(nèi)存時如果內(nèi)存沒有足夠的空閑區(qū)，由交換策略來確定把內(nèi)存中的哪些程序段和數(shù)據(jù)段調(diào)出內(nèi)存，以便騰出足夠的空間。

二、內(nèi)存分配和回收4調(diào)入策略：決定信息裝入內(nèi)存的時機，有兩種：在用戶請求時調(diào)入，稱為請調(diào)；根據(jù)某種算法，確定系統(tǒng)將要使用的信息，并在執(zhí)行前預(yù)先調(diào)入內(nèi)存，稱為預(yù)調(diào)

5回收策略：回收時機，以及對所回收的內(nèi)存空閑區(qū)和已存在的內(nèi)存空閑區(qū)的調(diào)整4.1.2存儲管理功能一、地址變換二、內(nèi)存分配和回收三、內(nèi)存共享和保護四、內(nèi)存擴充三、內(nèi)存共享和保護內(nèi)存共享是為了更有效利用內(nèi)存內(nèi)存保護是為了保證在內(nèi)存中的多道程序只能在給定的存儲區(qū)域內(nèi)活動并互不產(chǎn)生干擾。包括：防止地址越界防止越權(quán)(對共享區(qū)有訪問權(quán))

最簡單、最常用的保護方法是上下界保護法（1）在CPU中設(shè)置一對下限寄存器和上限寄存器存放用戶作業(yè)在主存中的下限和上限地址；常用內(nèi)存保護方法下界寄存器存放程序裝入內(nèi)存后的開始地址（首址）上界寄存器存放程序裝入內(nèi)存后的末地址判別式：下界寄存器≤物理地址＜上界寄存器（2）設(shè)置一個寄存器作為基址寄存器，設(shè)置另一寄存器作為限長寄存器（指示存儲區(qū)長度）問：訪問作業(yè)的邏輯地址分別為2K、10K、20K時是否會越界？4.1.2存儲管理功能一、地址變換二、內(nèi)存分配和回收三、內(nèi)存共享和保護四、內(nèi)存擴充四、內(nèi)存擴充（虛擬存儲）通過操作系統(tǒng)利用程序執(zhí)行的局部性，在內(nèi)存和外存之間通過不斷交換信息，構(gòu)成一個容量超過內(nèi)存物理容量的由外存和內(nèi)存共同組成的虛擬存儲器。要實現(xiàn)內(nèi)存擴充，在程序執(zhí)行過程中，內(nèi)存和外存之間必須經(jīng)常地交換數(shù)據(jù)。最基本的控制數(shù)據(jù)流動的方式有：①用戶程序自己控制方式，典型的例子是覆蓋。②操作系統(tǒng)控制方式，又可進一步分為：交換方式、請調(diào)方式、預(yù)調(diào)入方式。

與實際物理存儲器只有一個（單機系統(tǒng)中），且被所有進程共享不一樣，每個進程都擁有自己的虛擬存儲器，且虛擬存儲器的容量是由計算機的地址結(jié)構(gòu)和尋址方式確定的。若CPU給出的有效地址長度為18位,可以尋址范圍為:0--256k;若地址的長度為為20位,則尋址范圍為:1024k.庫匯編編譯主子1子2目標模塊鏈接程序裝入模塊庫主子1子2裝入程序內(nèi)存庫主子1子24.2

程序的裝入和鏈接圖a靜態(tài)鏈接，靜態(tài)裝入圖b動態(tài)鏈接，動態(tài)裝入引言：存儲器管理方式1連續(xù)分配方式：指為一個系統(tǒng)或用戶程序分配一個連續(xù)的空間，主要有：單一連續(xù)區(qū)管理方式分區(qū)管理方式：通?？煞譃楣潭ǚ謪^(qū)方式和可變分區(qū)方式2離散分配方式：為了減少因連續(xù)分配所產(chǎn)生的碎片，提高內(nèi)存的利用率產(chǎn)生了離散分配方式，它可將一個用戶程序離散地分配到內(nèi)存中的多個不相連接的區(qū)域中。其方式有：分頁存儲管理方式分段存儲管理方式段頁式存儲管理方式虛擬存儲管理方式：為了進一步提高內(nèi)存利用率，又形成了一種虛擬存儲管理方式。其方式有：請求分頁管理方式請求分段管理方式請求段頁式管理方式4.3連續(xù)分配方式

4.3.1單一連續(xù)分配內(nèi)存分為兩個區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。應(yīng)用程序裝入到用戶區(qū)，可使用用戶區(qū)全部空間。最簡單，適用于單用戶、單任務(wù)的OS。優(yōu)點：易于管理。缺點：不能充分利用CPU不能充分利用內(nèi)存（低了內(nèi)存的利用率）不能充分利用外設(shè)實現(xiàn)思想1、地址轉(zhuǎn)換：靜態(tài)重定位硬件支持：界限寄存器，內(nèi)容為當前可供用戶使用的內(nèi)存區(qū)域的起始地址。絕對地址=邏輯地址+界限寄存器值2、存儲保護作業(yè)執(zhí)行時，CPU對每條指令中的絕對地址進行檢查。若界限地址≤絕對地址≤內(nèi)存最大地址則可執(zhí)行，否則有地址錯誤，形成“地址越界”中斷限定作業(yè)在規(guī)定的內(nèi)存區(qū)內(nèi)執(zhí)行，避免破壞操作系統(tǒng)的信息，達到“存儲保護”的目的。3、存儲擴充：覆蓋技術(shù)，使一個大作業(yè)能在小的空間中運行固定分區(qū)——把主存分成若干個固定大小的存儲區(qū)。OS20K28K60K124K256K進程A（6K）進程B（25K）進程C（36K）4.3.2固定分區(qū)分配

分區(qū)說明表基本思想把內(nèi)存中可分配的用戶區(qū)預(yù)先劃分成若干個連續(xù)區(qū)，每個連續(xù)區(qū)的大小可以相同，也可以不同（等長或不等長分區(qū)）。分區(qū)個數(shù)固定，每個分區(qū)的大小固定

一個分區(qū)中裝入一個作業(yè)，作業(yè)在執(zhí)行過程中不會改變存放區(qū)域適用于多道程序設(shè)計系統(tǒng)固定分區(qū)性能分析在作業(yè)大小和出現(xiàn)頻率均已知的情況下，固定分區(qū)是合適的。在這種情況下分區(qū)的大小選擇與作業(yè)大小相當，這樣內(nèi)存的使用效率較高。但是若作業(yè)的大小和出現(xiàn)的頻率不知道時，勢必造成分區(qū)的大小和作業(yè)的大小相差甚遠，這樣就會造成存儲空間的浪費，從而影響整個系統(tǒng)的效率。返回1、動態(tài)分區(qū)原則：存儲空間的劃分是在裝作業(yè)時進行的。從可用的自由存儲空間內(nèi)，劃出一個大小正好等于作業(yè)大小的存儲區(qū)，并分配給這一作業(yè)。

進程A（8K）進程D（124K）進程B（16K）進程C（64K）…OS進程A進程B進程C進程DOS進程A進程B進程COS進程A進程BOS進程A4.3.3動態(tài)分區(qū)分配OSA（8K）24K空閑區(qū)B（16K）C完成（64K）空閑區(qū)D（124K）OSA（8K）8K空閑區(qū)B（16K）E（50K）D（124K）14K空閑區(qū)F（16K）OSA（8K）8K空閑區(qū)空閑區(qū)16KE（50K）D（124K）空閑合并124+14=138K進程E（50K）進程F（16K）進入內(nèi)存進程B（16K）進程D（124K）完成

內(nèi)存分配變化過程2.

動態(tài)分區(qū)時的分配與回收（1）使用的數(shù)據(jù)結(jié)構(gòu)（空閑分區(qū)表）

可用表、自由鏈、請求表（2）常用分區(qū)分配算法

①最先適應(yīng)法：空閑區(qū)按地址順序從小到大登記。依次檢查空閑區(qū)表目，把第一個找到能容納申請要求的內(nèi)存區(qū)分配給申請者。

②最佳適應(yīng)算法：空閑區(qū)按其大小遞增的順序組成可用表。把找到的第一個滿足要求的空閑區(qū)分配。

③最壞適應(yīng)算法：按空閑區(qū)按其大小遞減的順序組成空閑區(qū)可用表或自由鏈，每次分配最大的空閑區(qū)。④循環(huán)適應(yīng)算法：每次從上一次查詢停止的位置繼續(xù)向下尋找滿足要求的空閑區(qū)。最先適應(yīng)法(first-fit)：該算法的分配和釋放的時間性能較好，較大的空閑分區(qū)可以被保留在內(nèi)存高端。但隨著低端分區(qū)不斷劃分而產(chǎn)生較多小分區(qū)，每次分配時查找時間開銷會增大。最佳適應(yīng)法(best-fit)：從個別來看，外碎片較小，但從整體來看，會形成較多外碎片。較大的空閑分區(qū)可以被保留。最壞適應(yīng)法(worst-fit)：基本不留下小空閑分區(qū)，但大作業(yè)的要求往往難以滿足。循環(huán)適應(yīng)法（next-fit）：分區(qū)分布均勻，但會缺少較大分區(qū)。例：有作業(yè)序列：作業(yè)A要求18K；作業(yè)B要求25K，作業(yè)C要求30K。系統(tǒng)中空閑區(qū)按三種算法組成的空閑區(qū)隊列經(jīng)分析可知：最佳適應(yīng)法對這個作業(yè)序列是合適的，而其它兩種對該作業(yè)序列是不合適的。（3）分區(qū)回收系統(tǒng)回收分區(qū)的主要步驟：1檢查回收分區(qū)是否與空閑區(qū)鄰接，如鄰接則加以合并；2修改說明表碎片問題由于空閑區(qū)的大小與申請內(nèi)存的大小相等的情況是很少的，絕大多數(shù)情況是從一個空閑區(qū)中切去一塊，剩下的部分作為一個空閑區(qū)仍留在空閑區(qū)表中，隨著時間的推移，空閑區(qū)的發(fā)展趨勢是越來越小，直至不能滿足任何用戶要求。這種不能被任何用戶使用的極小的空閑區(qū)稱為碎片。碎片的出現(xiàn)造成了存儲空間的浪費。碎片問題的解決合并（見分區(qū)回收）移動(緊湊)通過在內(nèi)存移動程序，將所有小的空閑區(qū)域合并為大的空閑區(qū)域，使分散的空閑區(qū)集中起來，以容納新的作業(yè)。

緊湊的示意

分區(qū)存儲管理的優(yōu)缺點

l

優(yōu)點：(1)多個程序共享內(nèi)存，有助于多道程序設(shè)計。(2)要求的硬件支持少，管理算法簡單，實現(xiàn)容易。l

缺點：(1)內(nèi)存利用率仍然不高。存在著嚴重的碎小空閑區(qū)(碎片)不能利用的問題，影響了內(nèi)存的利用率。(2)作業(yè)或進程的大小受分區(qū)大小控制，除非配合采用覆蓋和交換技術(shù)。(3)難以實現(xiàn)各分區(qū)間的信息共享

4.4對換對換的引入就是系統(tǒng)根據(jù)需要把主存中暫時不運行的某個(或某些)作業(yè)部分或全部移到外存，而把外存中的某個(或某些)作業(yè)移到相應(yīng)的主存區(qū)，并使其投入運行。交換技術(shù)是利用外存來邏輯地擴充主存對換空間的管理對換區(qū)，空閑分區(qū)表或分區(qū)鏈，采用連續(xù)分配方式，進程的換出和換入換出過程 選擇處于阻塞狀態(tài)且優(yōu)先級最低的進程作為換出進程，換出后收回內(nèi)存空間，修改進程的PCB相關(guān)信息換入過程 找出“就緒”狀態(tài)并已經(jīng)換出的進程，將其中換出時間最久的進程作為換入進程，將其換入直到已無可換入的進程和無可換出的進程4.5基本分頁存儲管理方式

4.5.1頁面與頁表

1．內(nèi)存空間、進程地址空間分頁

邏輯頁面（頁）：將一個進程的地址空間劃分成若干個大小相等的區(qū)域，稱為邏輯頁面

物理頁面（物理塊、頁框）：將內(nèi)存空間劃分成與頁相同大小的若干個物理塊，稱為塊或頁框。頁面的大小應(yīng)選擇適中，通常是2的冪，例512B～8KB。

在為進程分配內(nèi)存時，將進程中的若干頁分別裝入多個不相鄰接的塊中。2．地址結(jié)構(gòu)分頁地址中的地址結(jié)構(gòu)如下：

它含有兩部分：前一部分為頁號P，后一部分為位移量W(或稱為頁內(nèi)地址)。圖中的地址長度為32位，其中0～11位為頁內(nèi)地址，即每頁的大小為4KB；12～31位為頁號，地址空間最多允許有1M頁。

若給定一個邏輯地址空間中的地址為A，頁面大小為L，則頁號P和頁內(nèi)地址w可按下式求得：

P=int(A/L)

W=A%L其中，int是取整函數(shù)，%是取余運算。例：系統(tǒng)頁面大小為１KB，設(shè)A＝1201B，則P=？,W=？（0,1201）

3．頁表系統(tǒng)為每個進程建立一張頁面映射表，簡稱頁表。頁表保存于內(nèi)存。每個邏輯頁在頁表中占一個表項，記錄該頁在內(nèi)存中對應(yīng)的物理塊號。進程在執(zhí)行時，通過查找頁表，就可以找到每頁所對應(yīng)的物理塊號。可見，頁表的作用是實現(xiàn)從頁號到物理塊號的地址映射頁表的作用

作業(yè)2(0頁)操作系統(tǒng)作業(yè)2(1頁)作業(yè)3(0頁)作業(yè)1(0頁)作業(yè)1(1頁)作業(yè)2(2頁)051601224708作業(yè)1作業(yè)2作業(yè)31KB2KB001KB2KB03KB1KB0邏輯地址空間頁表物理地址空間頁號塊號1KB2KB3KB4KB5KB6KB7KB8KB9KB10KB分頁存儲管理基本原理等分主存：把主存劃分成相同大小的存儲塊。用戶邏輯地址空間的分頁：邏輯地址空間劃分成與物理頁大小相同的部分。邏輯地址的表示：虛擬地址A=>（p,d）, p--頁面號；d--相對地址（頁內(nèi)地址） 頁面大小L，則p=int(A/L)；d=A%L主存分配原則：系統(tǒng)以物理頁為單位把主存分給作業(yè)或進程，并且分給一個作業(yè)或進程的物理頁不一定是相鄰和連續(xù)的。4.5.2地址變換機構(gòu)1．基本的地址變換機構(gòu)

1)基本任務(wù)：利用頁表把程序中的邏輯地址變換成物理地址。2)硬件支持：在系統(tǒng)中設(shè)置頁表寄存器，用來存放頁表的始址和頁表的長度。（其值來源于進程的PCB）3)地址映射過程：首先系統(tǒng)將頁號與頁表長度進行比較，如果頁號大于頁表寄存器中的頁表長度，則訪問越界，產(chǎn)生越界中斷。如未出現(xiàn)越界，則根據(jù)頁表寄存器中的頁表始址和頁號計算出該頁在頁表項中的位置，得到該頁的物理塊號。與此同時，將邏輯地址中的頁內(nèi)地址與得到的物理塊號一起形成實際物理地址分頁系統(tǒng)的地址變換機構(gòu)

例1：作業(yè)地址空間共有7個頁，每頁的相對地址為0~1023，1024~2047，2048~3071，…，6144~6150。其對應(yīng)的主存塊在頁表中已列出。分別為5，7，9，15，13，10，16共7塊。假定頁表在主存始址為500。若該程序從第0頁開始運行，且現(xiàn)程序計數(shù)器內(nèi)容為：練習14.……..109…0硬件動態(tài)地址轉(zhuǎn)換機構(gòu)工作如下：

1、把該作業(yè)的頁表始址（500）和頁表長度（7）放入控制寄存器中。2、將程序計數(shù)器內(nèi)容的頁號部分（0）與控制寄存器中的頁表長度（7）相比較，若頁號<頁表長度時轉(zhuǎn)3，否則產(chǎn)生地址越界，終止程序運行。

3、按控制寄存器中的頁表始址找到頁表，在頁表中查邏輯頁對應(yīng)的物理頁號（5）

4、把主存塊號5與程序計數(shù)器中的頁內(nèi)位移相拼接，從而得到該操作所在主存的物理地址：5×1024+100=5220

5、按地址5220訪問內(nèi)存，完成指定操作。練習解答例2：已知某分頁系統(tǒng)，主存容量為64k，頁面大小為1k，對一個4頁大的作業(yè)，第0、1、2、3頁被分配到內(nèi)存的2、4、6、7塊中。求：將十進制的邏輯地址1023、2500、4500轉(zhuǎn)換成物理地址。解:(1)1023/1K，得到頁號為0，頁內(nèi)地址1023。又對應(yīng)的物理塊號為2，故物理地址為2*1k+1023=3071(2)2500/1K，得到頁號為2，頁內(nèi)地址452。又對應(yīng)的物理塊號為6，故物理地址為6*1k+452=6596(3)4500/1K，得到頁號為4，頁內(nèi)地址404。因為頁號不小于頁表長度，故產(chǎn)生越界中斷。若頁的大小為4K，則地址轉(zhuǎn)換機構(gòu)將邏輯地址0轉(zhuǎn)換成的物理地址為＿＿＿。在一個頁式存儲管理系統(tǒng)中，頁表內(nèi)容如下所示：

復(fù)習：

2．具有快表的地址變換機構(gòu)

“兩次訪內(nèi)”問題:CPU存取一個數(shù)據(jù)，需兩次訪問內(nèi)存。第1次訪存取物理塊號、第2次取數(shù)。使計算機的處理速度降低近1/2。解決方法：增設(shè)“快表”一組高速緩沖存儲器，稱為“聯(lián)想存儲器”或“快表”，用以存放當前訪問的那些頁表項

引入快表的性能分析

引入快表之后的地址變換過程引入快表的性能分析假定訪問主存的時間為200ns，訪問高速緩沖存儲器的時間為40ns，假設(shè)查快表的命中率為90%。將邏輯地址轉(zhuǎn)換成實際物理地址進行存取的平均訪問時間為：

（200+40）*90%+（200+200）*10%=256（ns）。不使用快表需兩次訪問主存的時間：200*2=400ns?？梢娛褂每毂砼c不使用快表相比，訪問時間下降了36%。引入“快表”后的地址變換過程

在CPU給出有效地址后，地址變換機構(gòu)自動地將頁號送入高速緩存，確定所需要的頁是否在快表中。若是，則直接讀出該頁所對應(yīng)的物理塊號，送入物理地址寄存器；若在快表中未找到對應(yīng)的頁表項，則需再訪問內(nèi)存中的頁表，找到后，把從頁表中讀出的頁表項存入快表，以取代一個舊的頁表項。具有快表的地址變換機構(gòu)

4.5.3兩級和多級頁表解決大頁表占用大的連續(xù)存儲空間的問題CPU具有32位地址時,使用232邏輯地址空間的分頁系統(tǒng),規(guī)定頁面4KB時,每個進程頁表的表項有1M個,若表項占用4個字節(jié),則每個進程需要占用4MB連續(xù)內(nèi)存空間存放頁表多級頁表概念：頁表也進行分頁，內(nèi)存僅存放當前使用的頁表,暫時不用部分放在磁盤上,待用到時再調(diào)入具體做法：把整個頁表進行分頁,分成一張張小頁表(稱為頁表頁),小頁表的大小與頁框相同，為進行索引查找,應(yīng)該為這些小頁表建一張頁目錄表基本分頁存儲管理 為離散分配的頁表再建一張頁表，稱為：外層頁表或頁目錄表外層頁表頁表增設(shè)外層頁表寄存器，存放外層頁表的始址外層頁號 外層頁內(nèi)地址 頁內(nèi)地址31222112110兩級頁表結(jié)構(gòu)

兩級頁表的地址變換機構(gòu) 二級頁表地址變換需三次訪問主存：一次訪問頁目錄、一次訪問頁表頁、一次訪問指令或數(shù)據(jù)，訪問時間加了兩倍外層頁號 外層頁內(nèi)地址 頁內(nèi)地址外部頁表寄存器＋＋外部頁表 頁表 物理地址2．多級頁表對于32位的機器，采用兩級頁表結(jié)構(gòu)是合適的；但對于64位的機器，采用兩級頁表是否仍可適用的問題，須做以下簡單分析。如果頁面大小仍采用4KB即212B，那么還剩下52位，假定仍按物理塊的大小(212位)來劃分頁表，則將余下的42位用于外層頁號。此時在外層頁表中可能有4096G個頁表項，要占用16384GB的連續(xù)內(nèi)存空間。這樣的結(jié)果顯然是不能令人接受的，因此必須采用多級頁表，將外層頁表再進行分頁，也就是將各分頁離散地裝入到不相鄰接的物理塊中，再利用第2級的外層頁表來映射它們之間的關(guān)系。

4.5基本分頁存儲管理方式4.5.4反置頁表一、反置頁表

用反置頁表，為每一個物理頁設(shè)一個表項，表項中放進程號和頁號，系統(tǒng)只維護一張反置頁表。由于物理存儲空間小于邏輯存儲空間，所以使用反置頁表減少了頁表占用的內(nèi)存空間。二、反置頁表的尋址邏輯地址=進程號+頁號+頁內(nèi)偏移地址尋址過程：根據(jù)進程號和頁號找到物理塊號物理地址=物理塊首址+頁內(nèi)偏移地址

基本分頁的特點優(yōu)點：存在頁內(nèi)碎片，但碎片相對較小，內(nèi)存利用率較高實現(xiàn)了離散分配，消除了程序浮動；缺點：需要專門的硬件支持，尤其“快表”；內(nèi)存訪問的效率下降。頁式：按內(nèi)存物理頁大小將進程空間分頁（用戶不可見），內(nèi)存空間等長段式:

按程序邏輯結(jié)構(gòu)將進程空間分段（用戶可見），內(nèi)存空間不等長4.6基本分段存儲管理方式基本分段管理思想的引入基本原理地址變換分段與分頁的主要區(qū)別段頁式存儲管理方式4.6基本分段存儲管理方式

4.6.1分段存儲管理方式的引入1)方便編程通常，用戶把自己的作業(yè)按照邏輯關(guān)系劃分為若干個段，每個段都是從0開始編址，并有自己的名字和長度。因此，希望要訪問的邏輯地址是由段名(段號)和段內(nèi)偏移量(段內(nèi)地址)決定的。例如，下述的兩條指令便是使用段名和段內(nèi)地址：LOADl，[A]|〈D〉；STORE1，[B]|〈C〉；其中，前一條指令的含義是將分段A中D單元內(nèi)的值讀入寄存器1；后一條指令的含義是將寄存器1的內(nèi)容存入B分段的C單元中。

2)信息共享:共享的實現(xiàn)以是信息的邏輯單位為基礎(chǔ)

3)信息保護4)動態(tài)增長5)動態(tài)鏈接4.6.2分段系統(tǒng)的基本原理1.分段

一個用戶程序可劃分為若干段（如一個主程序、一個或幾個子程序、數(shù)據(jù)段等），每個段在邏輯上是完整的（是一個獨立的功能模塊），都有自己的名字，且都有一段連續(xù)的地址空間。地址組成：段號段內(nèi)地址3116150例：01kCALL[X]|<Y>LOADL,[A]|6STOREL,[B]|<C>分段MAIN(主程)Y:

0640分段X（子程）6：

分段A（數(shù)組）05000300分段B2．段表

在系統(tǒng)中為每個進程建立一張段映射表，簡稱為“段表”。進程在執(zhí)行中，通過查段表來找到每個段所對應(yīng)的內(nèi)存區(qū)?？梢?，段表實現(xiàn)了從邏輯段到物理內(nèi)存區(qū)的映射。(1)段長(或稱段的容量)。該段的長度，即其字節(jié)數(shù)，在虛存和實存中段長是一樣的。(2)主存起始地址。該段裝入主存內(nèi)的起始地址。(3)存取控制權(quán)限。為了實現(xiàn)段的保護，規(guī)定各段的存取權(quán)限。例如，執(zhí)行E：執(zhí)行一個程序或子程序，不允許讀或?qū)?；讀R：允許讀，不允許寫或執(zhí)行；寫W：允許寫，不允許讀或執(zhí)行。除此之外，還可以是上述三種權(quán)限的組合，當存取要求違反了段的存取權(quán)限，則發(fā)生保護中斷。利用段表實現(xiàn)地址映射

(main)=030k(x)=120k(D)=215k040k80k120k

3．地址變換機構(gòu)

段表寄存器:用于存放段表始址和段表長度。

越界訪問控制:邏輯地址的段號與段表長度比較；段內(nèi)地址與段表中保存的段長比較。

分段系統(tǒng)的地址變換過程

段表始址段表長度（4）段表寄存器≤153705物理地址段號3105邏輯地址越界中斷段表基址段長150K35K500K9K300K20K100K42K3210段號內(nèi)存150*1024=153600153600+105=153705練習：對于如下所示的段表，請將邏輯地址（0，137），（1，4000），（2，3600），（5，230）轉(zhuǎn)換成物理地址。解:(1)段號0<段表長，且137<段長10k，故段號、段內(nèi)地址全部合法。得物理地址為50k+137=51337解:(2)段號1<段表長，段號合法。4000>段長3k，因此產(chǎn)生越界中斷。解:(3)段號2<段表長，且3600<段長5k，故段號、段內(nèi)地址全部合法。得物理地址為70k+3600=75280解:(4)段號5＝段表長，故段號不合法。產(chǎn)生越界中斷。

4．分頁和分段的主要區(qū)別由上所述不難看出，分頁和分段系統(tǒng)有許多相似之處。比如，兩者都采用離散分配方式，且都要通過地址映射機構(gòu)來實現(xiàn)地址變換。但在概念上兩者完全不同，主要表現(xiàn)在下述三個方面。(1)頁是信息的物理單位，分頁是為實現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存的利用率?；蛘哒f，分頁僅僅是由于系統(tǒng)管理的需要而不是用戶的需要。段則是信息的邏輯單位，它含有一組其意義相對完整的信息。分段的目的是為了能更好地滿足用戶的需要。(2)頁的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分為頁號和頁內(nèi)地址兩部分，是由機器硬件實現(xiàn)的，因而在系統(tǒng)中只能有一種大小的頁面；而段的長度卻不固定，決定于用戶所編寫的程序，通常由編譯程序在對源程序進行編譯時，根據(jù)信息的性質(zhì)來劃分。(3)分頁的