第三章

存儲管理

(MemoryManagement)存儲器是計算機系統(tǒng)的重要組成部分，所以存儲器的管理是操作系統(tǒng)最主要的功能之一。程序的指令和數(shù)據(jù)只有被調(diào)入內(nèi)存（RAM）CPU直接訪問，程序才能夠被執(zhí)行。軟件系統(tǒng)需要的內(nèi)存容量在不斷地增加，所以內(nèi)存的容量仍然是計算機硬件中最關(guān)鍵的、且又是最緊張的“瓶頸”資源。如何對存儲器進行有效的管理，不僅直接影響到它的利用率，而且還對系統(tǒng)的性能有重大影響。存儲管理的主要對象是內(nèi)存。教學(xué)要求熟悉存儲管理目的和功能，掌握地址重定位的概念。熟悉單一連續(xù)分配、固定分區(qū)分配、動態(tài)分區(qū)分配實現(xiàn)原理；掌握可變分區(qū)分配的數(shù)據(jù)結(jié)構(gòu)和分配回收算法，熟悉可變分區(qū)零頭和拼接技術(shù)。熟練掌握分頁存儲管理原理，熟練掌握分頁存儲管理基本的地址變換機構(gòu)和具有快表的地址變換機構(gòu)。掌握分段存儲管理原理和分段地址變換機構(gòu)，掌握分頁和分段比較，熟悉分頁和分段的共享，掌握段頁式存儲管理原理和地址變換機構(gòu)。教學(xué)要求-1掌握虛擬存儲器的理論基礎(chǔ)和定義，熟悉虛擬存儲器實現(xiàn)方式和特征。掌握請求分頁的頁表機制、缺頁中斷機構(gòu)和地址變換機構(gòu)，熟悉頁面的分配和置換策略、頁面的分配的算法。熟練掌握最佳置換算法、先進先出（FIFO）置換算法、最近最久未使用置換算法LRU，熟悉Clock置換算法和頁面緩沖算法；熟悉有效訪問時間計算，了解工作集概念。掌握請求分段的段表機制、缺段中斷機構(gòu)和地址變換機構(gòu)，熟悉分段的共享和保護。存儲管理目錄-13．4虛擬存儲器管理技術(shù)3．4．1虛擬存儲器的基本概念3．4．2請求分頁存儲管理3．4．3請求分段存儲管理3．5Windows2000內(nèi)存的管理3．5．1Intelx86/Pentium系列CPU對內(nèi)存管理的硬件支持機制3．5．2Windows2000地址空間的劃分3．5．3Windows2000用戶空間內(nèi)存分配和使用3．5．4頁面調(diào)度策略3．5．5物理內(nèi)存管理3．5.6Windows2000高速緩沖管理存儲管理目錄-23．6實驗與習(xí)題3．6．1實驗一：在Windows2000下評價內(nèi)存和緩存使用3．6．2實驗2：Windows2000內(nèi)存管理API函數(shù)的使用3．6．3選擇題3．6．4問答題3．1存儲管理概述3．1．1存儲層次結(jié)構(gòu)

存儲器是處理器處理的信息的來源與歸宿，占據(jù)著重要地位。但任何一種存儲設(shè)備都無法在速度與容量兩個方面同時滿足用戶的需求。為解決速度和容量之間的矛盾，馮·諾依曼計算機系統(tǒng)中，采用了三級或更多級的存儲器來組成存儲層次結(jié)構(gòu)，高一級為CPU寄存器和高速緩存器，中間是主存(可執(zhí)行的存儲器)，最低一級為輔存。通過采用特殊的存儲技術(shù)，主存與輔存兩級可以進一步優(yōu)化成多級。在存儲層次結(jié)構(gòu)中，高層的存儲器往往是速度很快、但成本高使容量有限，而接近底部的存儲器容量很大、成本低，相對訪問速度則慢。各種存儲設(shè)備組成存儲層次結(jié)構(gòu)，如圖5－1所示。

存儲層次結(jié)構(gòu)-1存儲器的功能是保存數(shù)據(jù)，存儲器的發(fā)展方向是高速、大容量和小體積。內(nèi)存在訪問速度方面的發(fā)展：DRAM、SDRAM、SRAM等；硬盤技術(shù)在大容量方面的發(fā)展：接口標準、存儲密度等；存儲組織是指在存儲技術(shù)和CPU尋址技術(shù)許可的范圍內(nèi)組織合理的存儲結(jié)構(gòu)。其依據(jù)是訪問速度匹配關(guān)系、容量要求和價格?！凹拇嫫?內(nèi)存-外存”結(jié)構(gòu)“寄存器-緩存-內(nèi)存-外存”結(jié)構(gòu)；微機中的存儲層次組織：訪問速度越慢，容量越大，價格越便宜；最佳狀態(tài)應(yīng)是各層次的存儲器都處于均衡的繁忙狀態(tài)（如：緩存命中率正好使主存讀寫保持繁忙）；存儲層次結(jié)構(gòu)-1存儲器的功能是保存數(shù)據(jù)，存儲器的發(fā)展方向是高速、大容量和小體積。內(nèi)存在訪問速度方面的發(fā)展：DRAM、SDRAM、SRAM等；硬盤技術(shù)在大容量方面的發(fā)展：接口標準、存儲密度等；存儲組織是指在存儲技術(shù)和CPU尋址技術(shù)許可的范圍內(nèi)組織合理的存儲結(jié)構(gòu)。其依據(jù)是訪問速度匹配關(guān)系、容量要求和價格?！凹拇嫫?內(nèi)存-外存”結(jié)構(gòu)“寄存器-緩存-內(nèi)存-外存”結(jié)構(gòu)；微機中的存儲層次組織：訪問速度越慢，容量越大，價格越便宜；最佳狀態(tài)應(yīng)是各層次的存儲器都處于均衡的繁忙狀態(tài)（如：緩存命中率正好使主存讀寫保持繁忙）；存儲層次結(jié)構(gòu)圖-1高速緩存主存外存cpu可訪n+k~幾百knM~幾百Mn百M~nG存儲層次結(jié)構(gòu)圖-33．1．2存儲管理的功能

操作系統(tǒng)為了有效地管理計算機的內(nèi)存資源，應(yīng)該具備以下四大功能：內(nèi)存分配、內(nèi)存保護、地址映射、內(nèi)存擴充。1.內(nèi)存分配內(nèi)存分配的主要任務(wù)是：為每一道程序分配內(nèi)存空間，使它們“各得其所”；當程序撤消時，則收回它占用的內(nèi)存空間。分配時注意提高存儲器的利用率。2．

地址映射目標程序所訪問的地址是邏輯地址集合的地址空間，而內(nèi)存空間是內(nèi)存中物理地址的集合，在多道程序環(huán)境下，這兩者是不一致的，因此，存儲管理必須提供地址映射功能，用于把程序地址空間中的邏輯地址轉(zhuǎn)換為內(nèi)存空間中對應(yīng)的物理地址。存儲管理的功能-13。存儲保護內(nèi)存保護的任務(wù)是確保每道程序都在自己的內(nèi)存空間運行，互不干擾。保護系統(tǒng)程序區(qū)不被用戶侵犯（有意或無意的），不允許用戶程序讀寫不屬于自己地址空間的數(shù)據(jù)（系統(tǒng)區(qū)地址空間，其他用戶程序的地址空間）。

4。提高主存儲器的利用率減少不可用的存儲空間（稱為“零頭），允許多道程序動態(tài)共享主存。5。內(nèi)存擴充內(nèi)存擴充的任務(wù)是從邏輯上來擴充內(nèi)存容量，使用戶認為系統(tǒng)所擁有的內(nèi)存空間遠比其實際的內(nèi)存空間（硬件RAM）大的多。名字空間、地址空間和存儲空間-1裝配模塊雖然具有統(tǒng)一的地址空間，但是仍是以“0”作為參考地址，即是浮動的。要把它裝入內(nèi)存執(zhí)行，就要確定裝入內(nèi)存的實際物理地址，并修改程序中與地址有關(guān)的代碼，這一過程稱為地址重定位。地址空間的程序和數(shù)據(jù)經(jīng)過地址重定位處理后，就變成了可由CPU直接執(zhí)行的絕對地址程序。我們把這一地址集合稱為“絕對地址空間”或“存儲空間”。程序的名字空間、地址空間和存儲空間之間的關(guān)系如圖所示。P106圖3-2程序的名字空間、地址空間和存儲空間

符號源程序LoadA,data1相對目標程序（裝配模塊）LoadA,200絕對目標程序LoadA,55200名字空間地址空間相對地址/邏輯地址空間存儲空間絕對地址/物理地址空間匯編/編譯連接地址重定位裝入邏輯地址、物理地址和地址映射地址映射BA=1000LoadA200

3456

。

。

。1200物理地址空間LoadAdata1data13456源程序LoadA200

34560100200編譯連接邏輯地址空間地址重定位-1例如：LOAD1，2500這條指令是把相對地址為2500的存儲單元的內(nèi)容365裝入1號累加器。而這時內(nèi)容為365的存儲單元的實際物理地址為12500（起始地址10000+相對地址2500），所以LOAD1，2500這條指令中的直接地址碼要作相應(yīng)的修改，即改為LOAD1，12500。

P106圖3-3靜態(tài)重定位LOAD1，25003650100：2500：2600：LOAD1，1250036510000：10100：12500：12600：程序的地址空間內(nèi)存的地址空間地址重定位-3為了支持靜態(tài)重定位，連接程序在生成統(tǒng)一地址空間和裝配模塊時，還應(yīng)產(chǎn)生一個重定位項表，該表的每一項――重定位項是在程序中需要修改地址的位置，操作系統(tǒng)的裝入程序要把裝入模塊和重定位項表一起裝入內(nèi)存。程序裝入內(nèi)存中的起始地址稱為重定位因子，由裝配模塊的實際裝入起始地址得到重定位因子，然后取重定位項，把重定位項表示地址的內(nèi)容進行修改，即把重定位項表示地址的內(nèi)容加上重定位因子，從而完成指令代碼的修改。當完成重定位后，就可以啟動程序執(zhí)行。

地址重定位-5動態(tài)重定位

動態(tài)重定位是指在程序執(zhí)行過程中進行地址重定位，即在每次訪問內(nèi)存單元前才進行地址變換。動態(tài)重定位可使裝配模塊不加任何修改就裝入內(nèi)存，但是它需要硬件—重定位寄存器的支持。下圖給出了動態(tài)重定位的示意圖。 程序的目標模塊在裝入內(nèi)存時，與地址有關(guān)的指令都無須進行修改，如在圖3-4中LOAD1，2500這條指令中仍保持相對地址2500。當該指令被操作系統(tǒng)取到中央處理器指令寄存器上執(zhí)行時，操作系統(tǒng)首先把該模塊裝入的實際起始地址減去目標模塊的相對基地址（圖3-4中該模塊的基地址為0），然后將其差值10000裝入重定位寄存器。

3．2存儲器的連續(xù)分配3．2．1單一連續(xù)分配

這是一種最簡單的存儲管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)，如在8位和16位微機上CP/M和MS-DOS操作系統(tǒng)。它將內(nèi)存分為兩個區(qū)：系統(tǒng)區(qū)：僅供操作系統(tǒng)使用，通常設(shè)置在內(nèi)存的低段；用戶區(qū)：指除系統(tǒng)區(qū)以外的全部內(nèi)存空間，提供給用戶使用。這種存儲分配方式由于用在單用戶、單任務(wù)的操作系統(tǒng)中。P108圖3-5單一連續(xù)分配示例系統(tǒng)區(qū)操作系統(tǒng)用戶區(qū)用戶程序

0下限上限基址長度單一連續(xù)區(qū)存儲管理3．2．2分區(qū)存儲管理方式

分區(qū)存儲管理是能夠滿足多道程序運行的最簡單的存儲器管理方案，其基本思想是將內(nèi)存劃分成若干個連續(xù)的區(qū)域，稱為分區(qū)。每個分區(qū)只能儲存一個程序，而且程序也只能在它所駐留的分區(qū)中運行。分區(qū)存儲管理根據(jù)分區(qū)個數(shù)及分區(qū)大小的可變性分為固定式分區(qū)和可變式分區(qū)兩種。1.固定分區(qū)(FixedPartitioning)分配方式

固定分區(qū)是在作業(yè)裝入之前，內(nèi)存就被劃分成若干個分區(qū)。劃分工作可以由系統(tǒng)管理員完成，也可以由操作系統(tǒng)實現(xiàn)。然而一旦劃分完成，在系統(tǒng)運行期間不再重新劃分，即分區(qū)的個數(shù)不可變，分區(qū)的大小不可變，所以，固定式分區(qū)又稱為靜態(tài)分區(qū)。

這種分區(qū)方式一般將內(nèi)存的用戶區(qū)域劃分成大小不等的分區(qū)，以適應(yīng)不同大小的作業(yè)的需要。系統(tǒng)有一張分區(qū)說明表，每個表目說明一個分區(qū)的大小、起始地址和是否已分配的使用標志。分區(qū)說明表和內(nèi)存分配圖如下所示。

P109圖3-6固定分區(qū)分配示例區(qū)號大小起址 標志 116KB 20K 已分配 2 32KB 36K 已分配 364KB 68K 已分配 4124KB132K未分配 (a)分區(qū)說明表固定式分區(qū)實現(xiàn)技術(shù)簡單，但是內(nèi)存的利用率不高，適用于作業(yè)的大小和多少事先都比較清楚的系統(tǒng)中。它用于60年代的IBM-360的MFT操作系統(tǒng)中。0k：

20k：

36k：

68k：

132k：

256k：

內(nèi)存分配圖

操作系統(tǒng)作業(yè)A（16k）作業(yè)B（26k）作業(yè)C（56k）第1分區(qū)（16kb）第2分區(qū)（32kb）（已分配）第3分區(qū)（64kb）（已分配）4分區(qū)（124kb）（未分配）

固定分區(qū)分配-2由于每個分區(qū)的大小是固定的，所以每個提出運行的作業(yè)必須說明所需的最大內(nèi)存容量。在調(diào)度作業(yè)時，存儲管理程序根據(jù)作業(yè)所需的內(nèi)存容量，在分區(qū)說明表中找出一個足夠大的空閑分區(qū)分配給它，然后用重定位裝入程序?qū)⒋俗鳂I(yè)裝入。如果找不到，則通知作業(yè)調(diào)度模塊，選擇另外一個作業(yè)。圖3-6（b）說明了某一時刻，作業(yè)A、B、C分別被分配到1，2，3三個分區(qū)中，第四個分區(qū)尚未分配，操作系統(tǒng)則永久占據(jù)內(nèi)存低地址區(qū)20KB的空間。當一個作業(yè)結(jié)束時，系統(tǒng)又調(diào)用存儲管理程序查到分區(qū)說明表，把所占分區(qū)的使用標志修改為未分配狀態(tài)即可。

固定分區(qū)分配-3采用這種技術(shù)，雖然可以使多個作業(yè)共駐內(nèi)存，但是一個作業(yè)的大小不可能正好等于某個分區(qū)的大小，所以每個被分配的分區(qū)總有一部分被浪費，我們把這部分被浪費的存儲區(qū)稱為內(nèi)零頭或內(nèi)碎片。有時這種分配方式浪費相當嚴重，如圖3-6（b）中第3分區(qū)未分配的部分還有8KB，加上第4分區(qū)的124KB共計132KB，而且這132KB的內(nèi)存空間在物理上是一個連續(xù)的區(qū)域，這時如果有一個大小為130KB的作業(yè)申請內(nèi)存，卻被拒絕，因為分區(qū)的大小是預(yù)先劃分好的，分區(qū)說明表中指出只有第4分區(qū)未分配（大小為124K），且不能改變分區(qū)的大小。MultiprogrammingwithFixedPartitionsFixedmemorypartitionsseparateinputqueuesforeachpartitionsingleinputqueue2．可變（動態(tài)）

(DynamicPartitioning)分區(qū)分配方式

(1)可變分區(qū)概述可變分區(qū)是指在作業(yè)裝入內(nèi)存時，從可用的內(nèi)存中劃出一塊連續(xù)的區(qū)域分配給它，且分區(qū)大小正好等于該作業(yè)的大小?？勺兎謪^(qū)中分區(qū)的大小和分區(qū)的個數(shù)都是可變的，而且是根據(jù)作業(yè)的大小和多少動態(tài)地劃分，因此又稱為動態(tài)分區(qū)。這種存儲管理技術(shù)是固定式分區(qū)的改進，既可以獲得較大的靈活性，又能提高內(nèi)存的利用率?？勺兎謪^(qū)概述-1

系統(tǒng)初始化后，內(nèi)存被劃分成兩塊，一塊用于常駐的操作系統(tǒng)，另一塊則是完整的空閑區(qū)（用戶區(qū)）。對于調(diào)入的若干個作業(yè)，劃分幾個大小不等的分區(qū)給它們，隨著作業(yè)的調(diào)入和撤除，相應(yīng)的分區(qū)被劃分和釋放，原來整塊的存儲區(qū)形成空閑區(qū)和已分配區(qū)相間的局面。圖3-7（c）給出了可變式分區(qū)的示例，512KB內(nèi)存中除20KB操作系統(tǒng)外，裝入作業(yè)2、3、4、6四個，有空閑區(qū)1、2、3三個。

P110圖3-7可變式分區(qū)示例

序號P 大小 起址 狀態(tài) 1 32k 20k 空閑 2 56k 260k 空閑 3116k 396k 空閑 4 — — 空表目 5 — — 空表目 （a）空閑分區(qū)表前向指針N+200后向指針N+200N個字可用空閑區(qū)（56k）作業(yè)6（80k）空閑區(qū)（116k）空閑區(qū)（32k）作業(yè)2（64k）作業(yè)3（48k）作業(yè)4（96k）操作系統(tǒng)(20K)020K52K116K164K260K316K396K512K返回可變分區(qū)概述-2可變式分區(qū)的分配和釋放的基本思想是：在分配時，首先找到一個足夠大的空閑分區(qū)，即這個空閑區(qū)的大小比作業(yè)要求的要大，系統(tǒng)則將這個空閑分區(qū)分成兩部分：一部分成為已分配的分區(qū)，剩余的部分仍作為空閑區(qū)。在回收撤除作業(yè)所占領(lǐng)的分區(qū)時，要檢查回收的分區(qū)是否與前后空閑的分區(qū)相領(lǐng)接，若是，則加以合并，使之成為一個連續(xù)的大空間。

ExampleDynamicPartitioningOperating

SystemProcess1320KProcess2Process3224K288K64KOperating

SystemProcess1320KProcess3224K288K64KOperating

SystemProcess1320KProcess3288K64KProcess4128K96KExampleDynamicPartitioning-1Operating

System320KProcess3288K64KProcess4128K96KOperating

SystemProcess3288K64KProcess4128K96KProcess2224k96K動態(tài)/可變式分區(qū)分配-1(2)可變式分區(qū)的數(shù)據(jù)結(jié)構(gòu)

空閑區(qū)表形式空閑分區(qū)表為每個尚未分配的分區(qū)設(shè)置一個表項，包括分區(qū)的序號、大小、始址和狀態(tài)?？臻e區(qū)鏈形式為了實現(xiàn)對空閑分區(qū)的分配和鏈接，在每個分區(qū)的起始部分，設(shè)置一些用于控制分區(qū)分配的信息（如分區(qū)的大小和狀態(tài)位），以及用于鏈接其它分區(qū)的前向指針；在分區(qū)尾部，則設(shè)置了一個后向指針，為了檢索方便也設(shè)置了控制分區(qū)分配的信息。然后，通過前、后向指針將所有的分區(qū)鏈接成一個雙向鏈表。(3)可變分區(qū)分配算法

(PartitioningPlacementAlgorithm)(1)最佳適應(yīng)算法BF（BestFit）：它從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能使碎片盡量小。為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按大小從小到大進行排序，自表頭開始查找到第一個滿足要求的自由分區(qū)分配。該算法保留大的空閑區(qū)，但造成許多小的空閑區(qū)。(2)首次適應(yīng)算法FF（FirstFit）：從空閑分區(qū)表的第一個表目起查找該表，把最先能夠滿足要求的空閑區(qū)分配給作業(yè)，這種方法目的在于減少查找時間。為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按地址由低到高進行排序。該算法優(yōu)先使用低址部分空閑區(qū)，在低址空間造成許多小的空閑區(qū)，在高地址空間保留大的空閑區(qū)。可變分區(qū)分配算法-1(3)循環(huán)首次適應(yīng)算法NF(NextFit)：該算法是首次適應(yīng)算法的變種，它把空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)按地址遞增構(gòu)成一個循環(huán)鏈。在分配內(nèi)存空間時，不再每次從表頭（鏈首）開始查找，而是從上次找到的空閑區(qū)的下一個空閑區(qū)開始查找，直到找到第一個能滿足要求的的空閑區(qū)為止，并從中劃出一塊與請求大小相等的內(nèi)存空間分配給作業(yè)。該算法能使內(nèi)存中的空閑區(qū)分布得比較均勻。(4)最壞適應(yīng)法：從所有未分配的分區(qū)中挑選最大的且大于和等于作業(yè)大小的分區(qū)分給要求的作業(yè)；空閑分區(qū)按大小由大到小排序。該算法使小的空閑區(qū)減少，但造成大的空閑區(qū)不夠大。例：分配一個16KB分區(qū)采用空閑分區(qū)表結(jié)構(gòu)和首次適應(yīng)分配算法

空閑分區(qū)表數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表中的空閑分區(qū)要按地址從低到高連續(xù)排序，最后一個空閑分區(qū)中m_size為0表示以上表目空白。空閑分區(qū)表起始地址為coremap分配和釋放的基本思想是：在分配時，首先找到一個足夠大的空閑分區(qū)，即這個空閑區(qū)的大小比作業(yè)要求的要大，系統(tǒng)則將這個空閑分區(qū)分成兩部分：一部分成為已分配的分區(qū)，剩余的部分仍作為空閑區(qū)。在回收撤除作業(yè)所占領(lǐng)的分區(qū)時，要檢查回收的分區(qū)是否與前后空閑的分區(qū)相領(lǐng)接，若是，則加以合并，使之成為一個連續(xù)的大空間。m_addrm_size…..m_addrm_size=0…...m_addrm_sizem_addrm_sizem_addrm_sizem_addrm_sizeCoremapP111圖3-8采用首次適應(yīng)算法的可變分區(qū)的分配流程圖

申請分配一個u.size大小的分區(qū)從頭開始查表是否檢索完畢？本次無法分配m.size>u.size

m.size-u.size≤size？從該分區(qū)中劃出u.size大小的分區(qū)繼續(xù)檢索下一個表項將該表目以上的所有表目下移一格將該分區(qū)分配給申請者修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)

返回YNN（4）可變分區(qū)回收算法

當一個作業(yè)運行完畢釋放內(nèi)存時，系統(tǒng)根據(jù)釋放區(qū)的首地址，從空閑區(qū)說明表中找到相應(yīng)的插入點，此時可能出現(xiàn)下列四種情況（如圖3-9所示，其中F1，F(xiàn)2表示回收區(qū)的前、后空閑區(qū)）：(1)當回收區(qū)既不與F1領(lǐng)接，又不與F2領(lǐng)接時（如圖3-9（a）），應(yīng)為回收區(qū)單獨建立一項新表目，填寫回收區(qū)的起址和大小，并根據(jù)其起址，插入到空閑區(qū)說明表的適當位置。(2)當回收區(qū)只與插入點的前一個分區(qū)F1相領(lǐng)接時（如圖3-9（b）），應(yīng)將回收區(qū)與插入點的前一個分區(qū)合并，不再為回收區(qū)分配新的表目，而只需修改F1分區(qū)表目的大小即可?？勺兎謪^(qū)回收算法-1(3)當回收區(qū)只與插入點的后一個分區(qū)F2相領(lǐng)接時（如圖3-9（c）），將把兩個空閑區(qū)合并，修改F2分區(qū)的表目，把回收區(qū)的起址作為新空閑區(qū)的起址，大小為兩個分區(qū)之和。(4)當回收區(qū)與插入點的前、后兩個分區(qū)（F1和F2）都相領(lǐng)接時（如圖3-9（d）），合并三個分區(qū)，用F1表目的起址作為新空閑區(qū)的起址，修改其大小為三塊分區(qū)之和，最后取消F2的表目。圖3-7（c）內(nèi)存分配圖中作業(yè)3、2、4、6分別回收時相當于圖3-9（a）、（b）、（c）、（d）內(nèi)存回收時的情況。

P112圖3-9內(nèi)存回收時的情況

作業(yè)Y回收區(qū)作業(yè)X

F1

F1

回收區(qū)作業(yè)Y

F2

F1

回收區(qū)

F2作業(yè)Y

回收區(qū)

F2作業(yè)X作業(yè)Y

A

B

C

D可變分區(qū)回收算法-3對于前圖所示的可變式分區(qū)內(nèi)存分配圖，下列四種情況分別如下圖所示：

作業(yè)4回收區(qū)作業(yè)2空閑區(qū)1

空閑區(qū)1

回收區(qū)作業(yè)3

空閑區(qū)2

回收區(qū)空閑區(qū)3

回收區(qū)

空閑區(qū)2作業(yè)3作業(yè)6

A

B

C

D作業(yè)3回收作業(yè)2回收作業(yè)4回收作業(yè)6回收可變分區(qū)回收算法-4作業(yè)3回收前后序號P 大小 起址 狀態(tài) 1 32k 20k 空閑 2 56k 260k 空閑 3116k 396k 空閑 4 — — 空表目 5 — — 空表目 （a）空閑分區(qū)表序號P大小起址狀態(tài) 1 32k20k空閑

2

48k116k空閑

3 56k260k空閑 4 116k396k空閑 5 ——空表目 空閑分區(qū)表空閑區(qū)2（56k）作業(yè)6（80k）空閑區(qū)3（116k）空閑區(qū)1（32k）作業(yè)2（64k）作業(yè)3（48k）

回收區(qū)作業(yè)4（96k）操作系統(tǒng)(20K)020K52K116K164K260K316K396K512K空閑區(qū)3（56k）作業(yè)6（80k）空閑區(qū)4（116k）空閑區(qū)1（32k）作業(yè)2（64k）空閑區(qū)2（48k）作業(yè)4（96k）操作系統(tǒng)(20K)020K52K116K164K260K316K396K512K回收前

回收后空閑區(qū)2（56k）作業(yè)6（80k）空閑區(qū)3（116k）作業(yè)3（48k）作業(yè)4（96k）操作系統(tǒng)(20K)020K116K164K260K316K396K512K空閑區(qū)2（56k）作業(yè)6（80k）空閑區(qū)3（116k）空閑區(qū)1（32k）作業(yè)2（64k）

回收區(qū)作業(yè)3（48k）

作業(yè)4（96k）操作系統(tǒng)(20K)020K52K116K164K260K316K396K512K回收前

回收后可變分區(qū)回收算法-5作業(yè)2回收前后序號P 大小 起址 狀態(tài) 1 32k 20k 空閑 2 56k 260k 空閑 3116k 396k 空閑 4 — — 空表目 5 — — 空表目 （a）空閑分區(qū)表序號P大小起址狀態(tài) 1 96k20k空閑 2 56k260k空閑 3 116k396k空閑 4 ——空表目 5 ——空表目 空閑分區(qū)表空閑區(qū)1（96k）可變分區(qū)回收算法-6作業(yè)4回收前后序號P 大小 起址 狀態(tài) 1 32k 20k 空閑 2 56k 260k 空閑 3116k 396k 空閑 4 — — 空表目 5 — — 空表目 （a）空閑分區(qū)表序號P大小起址狀態(tài) 1 32k20k空閑 2 152k164k

空閑 3 116k396k空閑 4 ——空表目 5 ——空表目 空閑分區(qū)表空閑區(qū)2（56k）作業(yè)6（80k）空閑區(qū)3（116k）空閑區(qū)1（32k）作業(yè)2（64k）作業(yè)3（48k）

作業(yè)4（96k）

回收區(qū)操作系統(tǒng)(20K)020K52K116K164K260K316K396K512K空閑區(qū)2（152k）作業(yè)6（80k）空閑區(qū)3（116k）空閑區(qū)1（32k）作業(yè)2（64k）作業(yè)3（48k）操作系統(tǒng)(20K)020K52K116K164K316K396K512K回收前

回收后可變分區(qū)回收算法-7作業(yè)6回收前后序號P 大小 起址 狀態(tài) 1 32k 20k 空閑 2 56k 260k 空閑 3116k 396k 空閑 4 — — 空表目 5 — — 空表目 （a）空閑分區(qū)表序號P大小起址狀態(tài) 1 32k20k空閑 2 252k260k空閑

3 ——空表目

4 ——空表目 5 ——空表目 空閑分區(qū)表作業(yè)6（80k）空閑區(qū)4（116k）空閑區(qū)2（56k）作業(yè)6-80k回收區(qū)空閑區(qū)3（116k）空閑區(qū)1（32k）作業(yè)2（64k）作業(yè)3（48k）

作業(yè)4（96k）操作系統(tǒng)(20K)020K52K116K164K260K316K396K512K空閑區(qū)2（252k）空閑區(qū)1（32k）作業(yè)2（64k）作業(yè)3（48k）作業(yè)4（96k）操作系統(tǒng)(20K)020K52K116K164K260K512K回收前

回收后可變分區(qū)回收算法-8后空閑區(qū)

不

D不

A鄰

B鄰

C前空閑區(qū)

不鄰不鄰表目

加一

//減一后空閑區(qū)首址/

/

-size

撤消后空閑區(qū)大小/

/

+size

撤消前空閑區(qū)首址

/

/

/

/前空閑區(qū)大小

/+size/+size+后空閑區(qū)大小(5)可變分區(qū)零頭和拼接技術(shù)

可變分區(qū)也有零頭問題。在系統(tǒng)不斷地分配和回收中，必定會出現(xiàn)一些不連續(xù)的小的空閑區(qū)，稱為外零頭或外碎片。雖然可能所有零頭的總和超過某一個作業(yè)的要求，但是由于不連續(xù)而無法分配。解決零頭的方法是拼接或緊湊（Compaction），即向一個地址方向（例如向低地址端）移動已分配的作業(yè)，使那些零散的小空閑區(qū)在另一方向連成一片。分區(qū)的拼接技術(shù)，一方面是要求能夠?qū)ψ鳂I(yè)進行重定位，另一方面系統(tǒng)在拼接時要耗費較多的時間。采用拼接技術(shù)的可變分區(qū)又稱可重定位分區(qū)。

動態(tài)重定位分區(qū)分配例

20k28k88k132k182ko.s作業(yè)1(8k)(16k)作業(yè)3(24k)(24k)作業(yè)(20k)作業(yè)4(50k)(74k)64k112k256k(a)初始狀態(tài)20k202ko.s1324作業(yè)5(80k)(54k)122k(c)分配作業(yè)5之后(b)移動之后(即浮動)20k28k72ko.s1(8k)3(24k)2(20k)4(50k)(134k)52k122k256k作業(yè)580k(6)分區(qū)的存儲保護

分區(qū)的存儲保護是用戶程序只能訪問自己的用戶分區(qū)，不能訪問系統(tǒng)分區(qū)和其它程序的分區(qū)。分區(qū)存儲保護常用方法是界地址法或界限寄存器。分區(qū)的存儲保護-1系統(tǒng)設(shè)置一對上、下界寄存器，每當選中某個作業(yè)運行時，先將它的界地址裝入這對寄存器中，作業(yè)運行時形成的每一個訪問存儲器的地址都要同這兩個寄存器的內(nèi)容進行比較，若超過這個指定范圍，就產(chǎn)生越界中斷。系統(tǒng)也可以設(shè)置一對基址、限長寄存器，此時基址寄存器還起著重定位寄存器的作用，運行進程所在分區(qū)的始址和大小分別裝入基址和限長寄存器。界限寄存器用硬件實現(xiàn)，它是存儲管理部件MMU的一部分，采用基址、限長寄存器的地址變換和存儲保護的存儲管理部件MMU見圖3－10所示。

P112圖3-10分區(qū)的地址變換和存儲保護

界限寄存器重定位寄存器(基址)+CPU<內(nèi)存地址錯邏輯地址YN物理地址3．3存儲器的離散分配

連續(xù)分配會形成許多“碎片”，為了減少碎片提高存儲器的利用率而引入了離散分配方式,它將一個用戶的程序劃分成若干個大小相等的頁再離散地分配到內(nèi)存的多個不相鄰的區(qū)域中。3．3．1純分頁(Paging)存儲管理方式1．分頁存儲管理原理

分頁存儲管理是將一個進程的地址空間劃分成若干個大小相等的片，稱為頁面或頁，相應(yīng)地，將內(nèi)存空間劃分成與頁相同大小的若干個塊，稱為（物理）塊或頁框。在為進程分配內(nèi)存時，將進程中的若干頁離散地裝入不相鄰接的物理塊中。

分頁存儲管理原理－1由于頁面的大小一般取2的冪次個字節(jié)，通常在512B到4KB之間，所以內(nèi)存空間劃分后不存在“外碎片”。由于每塊物理塊可離散地分配給進程的一頁，這樣不斷地分配，直到剩余的物理塊數(shù)不能滿足一個進程的要求為止。而對每個進程只有最后一頁經(jīng)常裝不滿一塊，平均產(chǎn)生半頁“頁內(nèi)碎片”。由此可知，分頁存儲管理解決了“碎片”問題，提高了存儲器的利用率。純分頁存儲管理是指一個進程的所有頁全部裝入內(nèi)存的物理塊中才能運行。分頁存儲管理原理-1分頁系統(tǒng)的地址結(jié)構(gòu)如圖3-11所示，它由兩部分組成：前一部分為頁號P；后一部分為頁內(nèi)位移量W，即頁內(nèi)地址。圖中的地址長度為16位，其中0～9位為頁內(nèi)地址（每頁的大小為1KB），10～15位為頁號，所以允許地址空間的大小最多為64個頁。

頁號P位移量W1510902．頁表

在將進程的每一頁離散地分配到內(nèi)存的各個物理塊中后，系統(tǒng)為了保證進程的正確運行，即能在內(nèi)存中找到該進程每個頁面所對應(yīng)的物理塊，系統(tǒng)需為每頁配一個重定位寄存器，由于重定位寄存器是硬件，在頁面數(shù)很多時實現(xiàn)困難。為此，系統(tǒng)在內(nèi)存為每個進程建立了一張頁面映射表，簡稱頁表（如圖3-12所示）。每個頁在頁表中占一個表項，記錄該頁在內(nèi)存中對應(yīng)的物理塊號（頁號可以省略）。進程在執(zhí)行時，通過查找頁表，就可以找到每頁所對應(yīng)的物理塊號。可見，頁表的作用是實現(xiàn)從頁號到物理塊號的地址映射。

頁表-13．地址變換機構(gòu)

地址變換機構(gòu)的基本任務(wù)是利用硬件實現(xiàn)查頁表把用戶程序中的邏輯地址變換成內(nèi)存中的物理地址。為了實現(xiàn)地址變換功能，在系統(tǒng)中設(shè)置頁表寄存器，用來存放頁表的始址和頁表的長度。在進程未執(zhí)行時，每個進程對應(yīng)的頁表的始址和長度存放在進程的PCB中，當該進程被調(diào)度時，就將它們裝入頁表寄存器。地址變換機構(gòu)－1

在進行地址變換時，系統(tǒng)將邏輯地址截成頁號和頁內(nèi)地址二部分，將頁號與頁表長度進行比較，如果頁號大于等于頁表寄存器中的頁表長度，則訪問越界，產(chǎn)生越界中斷。如未出現(xiàn)越界，則根據(jù)頁表寄存器中的頁表始址和頁號計算出該頁在頁表項中的位置，查頁表得到該頁的物理塊號，將物理塊號與邏輯地址中頁內(nèi)地址二者拼接成物理地址，這樣便完成了從邏輯地址到物理地址的變換。

地址變換機構(gòu)-2圖3-13說明了分頁系統(tǒng)的地址變換機構(gòu)，地址變換機構(gòu)是由硬件完成，包括自動地查內(nèi)存的頁表。圖中舉例說明CPU指令寄存器在執(zhí)行Load1,2500指令時，地址變換機構(gòu)自動地完成了邏輯地址2500到物理地址5572的變換，將地址為5572內(nèi)存的數(shù)據(jù)讀入，送入寄存器1。完成從邏輯地址到物理地址的變換的地址變換機構(gòu)又稱為存儲管理部件MMU，它由硬件完成，并由于超大規(guī)模集成電路的發(fā)展，MMU已集成到CPU集成塊中。

P114圖3-13分頁系統(tǒng)的地址變換機構(gòu)

塊號5塊內(nèi)地址452

頁號2頁內(nèi)地址452頁表始址頁表長度﹥

245越界中斷頁表寄存器CPU指令寄存器LOAD1,2500邏輯地址2500頁號塊號

012物理地址55725*1024+452每頁1KB(1024)地址變換機構(gòu)圖-100001000010000010116-bitLogicalAddress25006-bitpage#10-bitOffset00001001110001000001010111000100

16-bitPhysicalAddress5572分頁存儲管理邏輯地址到物理地址地址變換的計算假設(shè)頁長為1KB(1024字節(jié))，邏輯地址為2500(十進制)。利用頁表把邏輯地址變換成物理地址計算步驟如下：(1)將虛地址分離成頁號P和頁內(nèi)地址d：頁號P＝（邏輯地址／頁大?。┤≌剑?500/1024）取整＝2頁內(nèi)地址d＝邏輯地址mod頁大小=2500mod1024=452(2)根據(jù)頁號查頁表，由頁表項讀出塊號：由頁號P＝2查頁表得塊號為5(3)塊號和頁內(nèi)地址構(gòu)成物理地址：物理地址＝塊號×頁大?。搩?nèi)地址=5*1024+452=5572

分頁存儲管理邏輯地址到物理地址地址變換的計算-1十六進制－－邏輯地址09C4H1KB1024400H∵C00H＞09C4H＞800H

頁號22KB2048800H頁內(nèi)地址＝邏輯地址－該頁頭地址3KB3072C00H＝09C4H－800H＝1C4H4KB40961000H查頁表頁號2塊號55KB51201400H物理地址＝該塊頭地址+頁內(nèi)地址6KB61441800H

=

1400H+1C4H=15C4H

ThepositionandfunctionoftheMMU4．快表

如果頁表存放在內(nèi)存中，則每次訪問內(nèi)存時，都要先訪問內(nèi)存中的頁表，然后根據(jù)所形成的物理地址再訪問內(nèi)存。這樣CPU存一個數(shù)據(jù)必須訪問兩次內(nèi)存，從而使計算機的處理速度降低了1/2。為了提高地址變換的速度，在地址變換機構(gòu)中增設(shè)了一個具有按內(nèi)容查找、并行查詢功能的特殊的高速緩沖存儲器，稱為“聯(lián)想存儲器(AssosiativeMemory)”或“快表”，或稱為“關(guān)聯(lián)存儲器(TLB,TranslationLook-asideBuffer)”，用以存放當前訪問的那些頁表項，每個頁表項包括頁號和相應(yīng)的塊號（頁號不能省略）。快表-1

在快表的輸入寄存器輸入頁號后，輸入頁號與快表中的各頁表項中的頁號同時比較，如有相同，快表的輸出寄存器輸出相應(yīng)的塊號，如都不相同，快表的輸出寄存器不輸出?？毂泶嫒∷俣瓤?，但由于成本的原因，快表不可能做得很大，大程序的頁表項不可能全部放在快表中。為此，把各進程的頁表仍放在內(nèi)存的系統(tǒng)區(qū)中，而系統(tǒng)增加的快表用以存放正在運行進程的、當前常用的部分頁面的頁號和相應(yīng)的塊號。

P115圖3-14具有快表的地址變換機構(gòu)

012

245越界中斷邏輯地址頁表寄存器頁號塊號塊號頁號快表物理地址頁表

頁號頁內(nèi)地址頁表始址頁表長度﹥塊號塊內(nèi)地址

輸入寄存器021425快表-2

此時地址變換過程為：CPU給出邏輯地址并將邏輯地址截成頁號和頁內(nèi)地址二部分后，地址變換機構(gòu)先將頁號送入快表的輸入寄存器，確定所需要的頁是否在快表中。若是，則直接讀出該頁所對應(yīng)的物理塊號，與邏輯地址中頁內(nèi)地址二者拼接成物理地址；若在快表中未找到對應(yīng)的頁表項，則需再訪問內(nèi)存中的頁表，找到后，把從頁表中讀出的頁表項存入快表中的一個寄存器單元中，以取代一個舊的頁表項，同時將此物理塊號與邏輯地址中頁內(nèi)地址二者拼接成物理地址，并訪問主存。圖3-14說明了具有快表的地址變換機構(gòu)?？毂?3

由于成本的原因，快表不可能做得很大，通常只能存放16~512個頁表項。例如，在Intel80486中有32個。這對中、小型作業(yè)來說，已可能把全部頁表項放入快表中；但對于大型作業(yè)來說，則只能將一部分頁表放入快表中。

由于對程序和數(shù)據(jù)的訪問往往帶有局限性，所以快表的命中率可以達到80%～99%。例如，假設(shè)檢索聯(lián)想存儲器的時間T(聯(lián)想)為20ns，訪問內(nèi)存的時間T(內(nèi)存)為100ns，訪問聯(lián)想存儲器的的命中率p為90%?？毂?4當快表命中時CPU存取內(nèi)存一個數(shù)據(jù)的時間為T1＝檢索快表時間＋訪問內(nèi)存數(shù)據(jù)時間=T(快表)+T(內(nèi)存)＝20＋100＝120ns。當快表不命中時CPU存取內(nèi)存一個數(shù)據(jù)的時間為T2＝檢索快表時間＋檢索內(nèi)存中的頁表時間＋訪問內(nèi)存數(shù)據(jù)時間=T(快表)+T(內(nèi)存)+T(內(nèi)存)＝20＋100＋100＝220ns。則CPU存取內(nèi)存一個數(shù)據(jù)的平均時間為

T=T1*命中率+T2*（1－命中率）=T1*ρ+T2*(1-ρ)=120*0.9+220*0.1=130ns。訪問時間增加為(T-T(內(nèi)存))∕T(內(nèi)存)=(130-100)∕100=30%。如果不引入快表，其訪問將延長一倍（達200ns）。

3．3．2分段(Segmentation)存儲管理方式1．分段存儲管理的引入從固定分區(qū)到可變分區(qū)，進而又發(fā)展到分頁系統(tǒng)的原因都是為了提高內(nèi)存的利用率，然而分段存儲管理的引入，是為了滿足用戶需要。分頁存儲管理時的進程地址空間結(jié)構(gòu)都是線性的，這要求對各段源程序編譯成目標程序后還要靜態(tài)鏈接，例如圖3-15把四個源程序段編譯后的目標程序段：主程序段main（15KB）、子程序段X（5KB）、數(shù)據(jù)段D（6KB）、堆棧段S（7KB）按線性空間的一維地址順序排列起來，再分成8頁，每頁為4KB。P116圖3-15

分頁系統(tǒng)的作業(yè)地址空間分段存儲管理的引入-2這時一個頁面中可能裝有兩個不同子程序段的指令代碼，例如第3頁裝有main和X兩個不同段的指令代碼，如這2段存取方式不同，則這一頁的存取方式無法確定。因此，通過頁面共享來達到共享一個邏輯上完整的子程序或數(shù)據(jù)塊是不可能的。另外，從減少CPU開銷和存儲空間浪費的角度來看，靜態(tài)鏈接是不合適的。為了為用戶提供一個方便靈活的程序設(shè)計環(huán)境需引入段式存儲管理，每個段是一組完整的邏輯信息，分段存儲管理有便于編程、便于共享和保護、可動態(tài)鏈接、可動態(tài)增長等特點。2．分段系統(tǒng)的基本原理

在分段存儲管理方式中，作業(yè)的地址空間按邏輯信息完整性被劃分為若干個段，每個段都有自己的名字，編譯后都是從零開始編址的一段連續(xù)的地址空間，段的長度由相應(yīng)邏輯信息組的長度決定，因而各段長度是不等的。分段系統(tǒng)的地址結(jié)構(gòu)如圖3-16所示，邏輯地址由段號和段內(nèi)地址兩部分組成。在該地址結(jié)構(gòu)中，允許一個作業(yè)最多有64K個段，每個段的最大長度為64KB。圖3-17中一個作業(yè)有四個段：主程序段MAIN、15KB長、段號為0，子程序段X、5KB長、段號為1，數(shù)據(jù)段D、6KB長、段號為2，堆棧段S、7KB長、段號為3。

P116圖3-16分段系統(tǒng)的地址結(jié)構(gòu)

段號段內(nèi)地址31161503．段表

在分段式存儲管理系統(tǒng)中，為每個段分配一個連續(xù)的分區(qū)，而進程中的各個段可以離散地分配到內(nèi)存中不同的分區(qū)中。類同分頁式存儲管理，在分段式存儲管理系統(tǒng)中為每個進程建立一張段映射表，簡稱為“段表”。每個段在表中占有一表項，在其中記錄了該段在內(nèi)存中的起始地址（又稱為“基址”）和段的長度，在圖3-17中，上述作業(yè)的四個段分別分配到內(nèi)存中起始地址為40K、120K、160K、200K四個不同的分區(qū)中。進程在執(zhí)行中，通過查段表來找到每個段所對應(yīng)的內(nèi)存區(qū)?？梢姡伪韺崿F(xiàn)了從邏輯段到物理內(nèi)存區(qū)的映射。

內(nèi)存空間040k：80k：120k：150k：P116圖3-17利用段表實現(xiàn)地址映射

作業(yè)空間

(MAIN）=00段表

15K段號段長基址（X）=10

017K

（D）=2208K3（S）=3010K15K40K7K80K8K120K10K150K（MAIN）=015K（X）=17K（D）=28K

（S）=310K4．地址變換機構(gòu)

為了實現(xiàn)從邏輯地址到物理地址的變換功能，系統(tǒng)中設(shè)置了段表寄存器，用于存放段表始址和段表長度。在進行地址變換時，系統(tǒng)將邏輯地址截成段號S與段內(nèi)地址d，將邏輯地址中的段號S與段表長度TL進行比較。若S≥TL，表示段號太大，訪問越界，于是產(chǎn)生越界中斷信號；若未越界，則根據(jù)段表的始址和該段的段號，計算出該段對應(yīng)段表項的位置，從中讀出該段在內(nèi)存中的起始地址，然后再檢查段內(nèi)地址d是否超過該段的段長SL。若超過，即d≥SL，同樣發(fā)出越界中斷信號；若未越界，則將該段的基址與段內(nèi)地址d相加，得要訪問的內(nèi)存物理地址。圖3-18給出了分段系統(tǒng)的地址變換過程。

P117圖3-18分段系統(tǒng)地址變換機構(gòu)

段號段長SL基址段表始址段表長度

TL段號S位移量d2100﹥15K40K7K80K8K120K10K50K

物理地址120k+100邏輯地址越界中斷段表寄存器0123地址變換機構(gòu)圖-116-bitLogicalAddress4-bitSegment#12-bitOffset0001001011110000ProcessSegmentTable

16-bitPhysicalAddress0010001100010000000000000000+LengthBase地址變換機構(gòu)圖(地址映射及存儲保護機制)

Cl

Cb+段號S段內(nèi)地址d比較比較b+d比較段表快表物理地址段表始址寄存器段表長度寄存器邏輯地址地址越界d>=1地址越界地址越界lbSlbSegmentationHardware5．共享

段是信息的邏輯單位,因此分段系統(tǒng)的一個突出的優(yōu)點是易于實現(xiàn)段的共享。即允許若干個進程共享一個或多個段，而且對段的保護也十分簡單。在分頁系統(tǒng)中，雖然也能實現(xiàn)程序和數(shù)據(jù)的共享，但遠不如分段系統(tǒng)來得方便。分段系統(tǒng)中，每個進程的段表中設(shè)置一個段表項。圖是分段系統(tǒng)中共享editor編輯程序的示意圖。共享-1

在實現(xiàn)段共享時，需要用到可重入代碼(ReentrantCode)又稱為“純代碼”(PureCode)。它是一種允許多個進程同時訪問的代碼，是一種不允許任何進程對其進行修改的代碼。但在每個進程中，配以局部數(shù)據(jù)區(qū)，將在執(zhí)行中可能改變的部分，拷貝到該數(shù)據(jù)區(qū)，這樣，程序在執(zhí)行時，只對該數(shù)據(jù)區(qū)(屬于該進程私有)中的內(nèi)容進行修改，而不去改變共享的代碼，這時的可共享代碼即成為可重入代碼。P118圖3-19分段系統(tǒng)中實現(xiàn)段共享

段表段長基址

1608040240

editor

DATA1

editor

DATA2段長基址1608040380

editorDATA1

DATA2進程1進程2

802402803804206．分頁和分段的主要區(qū)別

分頁和分段的主要區(qū)別-1

3．3．3段頁式存儲管理

分頁和分段存儲管理方式都各有其優(yōu)缺點。如果對兩種存儲管理方式“各取所長”后，則可以形成一種新的存儲管理方式的系統(tǒng)——段頁式系統(tǒng)。它以分頁的方式管理內(nèi)存，具有分頁系統(tǒng)能有效地提高內(nèi)存利用率的優(yōu)點；又以分段的方式管理用戶的邏輯地址空間，具有分段系統(tǒng)能很好地滿足用戶需要的長處，顯然是一種比較有效的存儲管理方式。1．基本原理

段頁式系統(tǒng)的基本原理是將內(nèi)存空間劃分成相同大小相同的若干個塊，將用戶程序先按邏輯完整性分為若干個段，并為每個段賦予一個段名，再把每個段劃分成若干個與塊大小相同的頁，將進程中的若干頁離散裝入不相鄰接的塊中。圖3-20中示出了一個作業(yè)地址空間結(jié)構(gòu)，該作業(yè)有四個段，頁面大小為4K，四個段的頁面數(shù)分別為4、2、2、2，總頁面數(shù)為10頁，此時每一頁都屬于邏輯上完整的一個段。在段頁式系統(tǒng)中，其地址結(jié)構(gòu)由段號、段內(nèi)頁號和頁內(nèi)地址三部分組成，作業(yè)地址空間的結(jié)構(gòu)如圖3-21所示。

基本原理-1

在段頁式系統(tǒng)中，為了實現(xiàn)從邏輯地址到物理地址的變換，系統(tǒng)中必需同時配置段表和頁表。由于將段中的頁進行離散地分配，段表中的內(nèi)容不再是段的內(nèi)存始址和段長，而是頁表始址和頁表長度。下圖說明了利用段表和頁表進行地址映射的過程。段號（S）段內(nèi)頁號（P）頁內(nèi)地址（W）P119圖3-20段頁式系統(tǒng)的作業(yè)地址空間P119圖3-22利用段表和頁表實現(xiàn)地址映射段號狀態(tài)頁表大小頁表始址01112130段表段表大小段表始址頁號狀態(tài)存儲塊號01112130

頁

表頁號狀態(tài)存儲塊號0111

頁表2．地址變換過程在段頁式系統(tǒng)中，有一個段表寄存器，存放段表始址和段長TL。在進行地址變換時，系統(tǒng)將邏輯地址截成段號S、段內(nèi)頁號P與頁內(nèi)地址W，先用段號S與段長TL進行比較。若S≥TL，表示段號太大，訪問越界，于是產(chǎn)生越界中斷信號；若S＜TL，表示未越界，于是利用段表始址和段號求出該段對應(yīng)的段表項在段表中的位置，從中得到該段的頁表始址，并利用邏輯地址中的段內(nèi)頁號P來獲得對應(yīng)頁的頁表項在頁表中位置，從中讀出該頁所在的物理塊號b，再用塊號b和頁內(nèi)地址W拼成物理地址。圖3-23說明了段頁式系統(tǒng)中的地址變換機構(gòu)。地址變換過程-1在段頁式系統(tǒng)中，為了獲得一條指令或數(shù)據(jù)，需三次訪問內(nèi)存：第一次訪問內(nèi)存中的段表，從中取得頁表始址；第二次訪問內(nèi)存中的頁表，從中取出該頁所在的物理塊號，并將該塊號與頁內(nèi)地址一起形成指令或數(shù)據(jù)的物理地址；第三次訪問才是真正根據(jù)所得的物理地址取出指令或數(shù)據(jù)。顯然，這使訪問內(nèi)存的次數(shù)增加了近兩倍。為了提高執(zhí)行的速度，在地址變換機構(gòu)中增設(shè)一高速緩沖寄存器。每次訪問它時，都同時利用段號和頁號去檢索高速緩存。P120圖3-23段頁式系統(tǒng)的地址變換機構(gòu)

+

段表0123

頁表0123段表始址段表長度

+段號（S）段內(nèi)頁號（P）頁內(nèi)地址（W）﹥塊號b

塊內(nèi)地址越界中斷段表寄存器CPU邏輯地址物理地址

b頁表始址3．4虛擬存儲器管理技術(shù)前面所介紹的各種存儲器管理方式，有一個共同的特點，即要求將一個作業(yè)全部裝入內(nèi)存才能運行。如果有的作業(yè)很大，其所要求的內(nèi)存空間超過了內(nèi)存總?cè)萘?，作業(yè)就不能全部被裝入內(nèi)存，致使該作業(yè)無法運行；有時大量作業(yè)要求運行，但由于內(nèi)存容量不足以容納所有這些作業(yè)，只能將少數(shù)作業(yè)裝入內(nèi)存讓它們先運行，而將其它大量的作業(yè)留在外存上等待。顯而易見的一種解決方法，是從物理上增加內(nèi)存容量，但這往往會受到機器自身的限制，而且無疑要增加系統(tǒng)成本，因此這種方法是受到一定限制的；另一種方法是從邏輯上擴充內(nèi)存容量，這正是虛擬存儲技術(shù)所要解決的主要問題。

3．4．1虛擬存儲器的基本概念

1．局部性原理(principleoflocality)實際上有許多作業(yè)在每次運行時，并非用到其全部程序，那么是否可以僅把作業(yè)的一部分裝入內(nèi)存就能運行呢？回答是可以的，我們先來研究虛擬存儲器系統(tǒng)實現(xiàn)的理論基礎(chǔ)：程序執(zhí)行的局部性規(guī)律。早在1968年P(guān)．Denning就指出過，程序在執(zhí)行時將呈現(xiàn)出局部性規(guī)律，即在一段時間內(nèi)，程序的執(zhí)行僅局限于某個部分；相應(yīng)地，它所訪問的存儲空間也局限于某個區(qū)域內(nèi)。局部性原理-1那么程序為什么會出現(xiàn)局部性規(guī)律呢？原因可以歸結(jié)為以下幾點：程序在執(zhí)行時，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外，大多數(shù)仍是順序執(zhí)行的。子程序調(diào)用將會使程序的執(zhí)行由一部分內(nèi)存區(qū)域轉(zhuǎn)至另一部分區(qū)域。但在大多數(shù)情況下，過程調(diào)用的深度都不超過5。程序中存在許多循環(huán)結(jié)構(gòu)，循環(huán)體中的指令被多次執(zhí)行。程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理，如對連續(xù)的存儲空間——數(shù)組的訪問，往往局限于很小的范圍內(nèi)。局部性原理-2

所以局限性表現(xiàn)為：

時間局限性：如果程序中的某條指令一旦執(zhí)行，則不久的將來該指令可能再次被執(zhí)行；如果某個存儲單元被訪問，則不久以后該存儲單元可能再次被訪問。產(chǎn)生時間局限性的典型原因是在程序中存在著大量的循環(huán)操作?？臻g局限性：一旦程序訪問了某個存儲單元，則在不久的將來，其附近的存儲單元也最有可能被訪問。即程序在一段時間內(nèi)所訪問的地址，可能集中在一定的范圍內(nèi)，其典型原因是程序是順序執(zhí)行的。2。虛擬存儲器的定義

根據(jù)局部性原理，一個作業(yè)在運行之前，沒有必要把全部作業(yè)裝入內(nèi)存，而僅將那些當前要運行的那部分頁面或段，先裝入內(nèi)存便可啟動運行，其余部分暫時留在磁盤上。程序在運行時如果它所要訪問的頁（段）已調(diào)入內(nèi)存，便可繼續(xù)執(zhí)行下去；但如果程序所要訪問的頁（段）尚未調(diào)入內(nèi)存（稱為缺頁或缺段），此時程序應(yīng)利用操作系統(tǒng)所提供的請求調(diào)頁（段）功能，將它們調(diào)入內(nèi)存，以使進程能繼續(xù)執(zhí)行下去。虛擬存儲器的定義-1如果此時內(nèi)存已滿，無法再裝入新的頁（段），則還須再利用頁（段）的置換功能，將內(nèi)存中暫時不用的頁（段）調(diào)出至磁盤上，騰出足夠的內(nèi)存空間后，再將所要訪問的頁（段）調(diào)入內(nèi)存，使程序繼續(xù)執(zhí)行下去。這樣，便可使一個大的用戶程序在較小的內(nèi)存空間中運行；也可使內(nèi)存中同時裝入更多的進程并發(fā)執(zhí)行。從用戶角度看，該系統(tǒng)所具有的內(nèi)存容量，將比實際內(nèi)存容量大得多，人們把這樣的存儲器稱為虛擬存儲器。虛擬存儲器的定義-2虛擬存儲器是采用請求調(diào)入和置換功能，將內(nèi)存和外存統(tǒng)一管理，達到把作業(yè)的一部分裝入內(nèi)存便可運行，給用戶提供的一個比內(nèi)存容量大的一維的邏輯地址空間。外存內(nèi)存虛擬存儲器邏輯地址虛擬存儲器的定義-3

虛擬存儲器的邏輯容量由內(nèi)存和外存容量之和、計算機的地址結(jié)構(gòu)二者所決定，其運行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存。實現(xiàn)虛擬存儲技術(shù)的物質(zhì)基礎(chǔ)是：一是有相當容量的輔助存儲器以存放所有并發(fā)作業(yè)的地址空間；二是有一定容量的內(nèi)存來存放運行作業(yè)的部分程序；三是有動態(tài)地址轉(zhuǎn)換機構(gòu)，實現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換。可見，虛擬存儲技術(shù)是一種性能非常優(yōu)越的存儲器管理技術(shù)，故被廣泛地應(yīng)用于大、中、小型機器和微型機中。虛擬存儲器實現(xiàn)方式請求分頁系統(tǒng)：

它是在分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能和頁面置換功能所形成的頁式虛擬存儲系統(tǒng)。它允許只裝入若干頁（而非全部程序）的用戶程序和數(shù)據(jù)，就可以啟動運行，以后再通過調(diào)頁功能和頁面置換功能，陸續(xù)把將要運行的頁面調(diào)入內(nèi)存，同時把暫不運行的頁面置換到外存上，置換時以頁面為單位。虛擬存儲器實現(xiàn)方式-1請求分段系統(tǒng)：它是在分段系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)段和分段置換功能所形成的段式虛擬存儲系統(tǒng)。它允許只裝入若干段（而非全部段）的用戶程序和數(shù)據(jù)，就可以啟動運行，以后再通過調(diào)段功能和置換功能將不運行的段調(diào)出，同時調(diào)入將要運行的段，置換以段為單位。請求段頁式系統(tǒng)：它是在段頁式系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁和頁面置換功能所形成的段頁式虛擬存儲系統(tǒng)。3。虛擬存儲器的特征離散性：指在內(nèi)存分配時采用離散的分配方式，它是虛擬存儲器的最基本的特征。多次性：指一個作業(yè)被分成多次調(diào)入內(nèi)存運行，即在作業(yè)運行時沒有必要將其全部裝入，只須將當前要運行的那部分程序和數(shù)據(jù)裝入內(nèi)存即可。多次性是虛擬存儲器最重要的特征。對換性：指允許在作業(yè)的運行過程中在內(nèi)存和外存的對換區(qū)之間換進、換出。虛擬性：指能夠從邏輯上擴充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠大于實際內(nèi)存容量。3．4．2請求分頁存儲管理

請求分頁存儲管理方式是在純分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能、頁面置換功能所形成的頁式虛擬存儲系統(tǒng)，它是目前常用的一種虛擬存儲器的方式。它允許只裝人若干頁(而非全部頁)的用戶程序和數(shù)據(jù)，便可啟動運行。以后，再通過調(diào)頁功能及頁面置換功能，陸續(xù)地把即將要運行的頁面調(diào)入內(nèi)存，同時把暫不運行的頁面換出到外存上，置換時以頁面為單位。

3．4．2請求分頁存儲管理

1。請求分頁中的硬件支持為了能實現(xiàn)請求調(diào)頁和置換功能，系統(tǒng)必須提供必要的硬件支持：擴充的頁表機制和缺頁中斷機構(gòu)。

（1）請求分頁的頁表機制它是在純分頁的頁表機制上形成的，由于只將應(yīng)用程序的一部分調(diào)入內(nèi)存，還有一部分仍在磁盤上，故需在頁表中再增加若干項，供程序(數(shù)據(jù))在換進、換出時參考。在請求分頁系統(tǒng)中的每個頁表項如圖所示。

頁號物理塊號狀態(tài)位P訪問字段A修改位M外存地址請求分頁中的硬件支持-1其中各字段說明如下：狀態(tài)位（中斷位P）：用于指示該頁是否已調(diào)入內(nèi)存，供程序訪問時參考。訪問字段A：用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)，或最近已有多長時間未被訪問，提供給置換算法選擇換出頁面時參考。修改位M：表示該頁在調(diào)入內(nèi)存后是否被修改過。由于內(nèi)存中的每一頁都在外存上保留一份副本，因此，若未被修改，在置換該頁時就不需將該頁寫回到外存上，以減少系統(tǒng)的開銷和啟動磁盤的次數(shù)；若已被修改，則必須將該頁重寫到外存上，以保證外存中所保留的始終是最新副本。外存(輔存)地址：用于指出該頁在外存上的地址，通常是物理塊號，供調(diào)入該頁時使用

(2)缺頁中斷機構(gòu)在請求分頁系統(tǒng)中，每當所要訪問的頁面不在內(nèi)存時，便要產(chǎn)生一缺頁中斷，請求OS將所缺頁調(diào)入內(nèi)存。與一般中斷的主要區(qū)別在于：缺頁中斷在指令執(zhí)行期間產(chǎn)生和處理中斷信號，而一般中斷在一條指令執(zhí)行完后檢查和處理中斷信號。缺頁中斷返回到該指令的開始重新執(zhí)行該指令，而一般中斷返回到該指令的下一條指令執(zhí)行。一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。(3)地址變換機構(gòu)

請求分頁系統(tǒng)中的地址變換機構(gòu)，是在分頁系統(tǒng)的地址變換機構(gòu)的基礎(chǔ)上，再為實現(xiàn)虛擬存儲器