操作系統(tǒng),原理,徐宗元OS-第三章課件

第三章

存儲(chǔ)管理

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

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

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

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

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

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

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

3456

。

。

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

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

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

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

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

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

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

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

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

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

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

P109圖3-6固定分區(qū)分配示例區(qū)號(hào)大小起址 標(biāo)志 116KB 20K 已分配 2 32KB 36K 已分配 364KB 68K 已分配 4124KB132K未分配 (a)分區(qū)說(shuō)明表固定式分區(qū)實(shí)現(xiàn)技術(shù)簡(jiǎn)單，但是內(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由于每個(gè)分區(qū)的大小是固定的，所以每個(gè)提出運(yùn)行的作業(yè)必須說(shuō)明所需的最大內(nèi)存容量。在調(diào)度作業(yè)時(shí)，存儲(chǔ)管理程序根據(jù)作業(yè)所需的內(nèi)存容量，在分區(qū)說(shuō)明表中找出一個(gè)足夠大的空閑分區(qū)分配給它，然后用重定位裝入程序?qū)⒋俗鳂I(yè)裝入。如果找不到，則通知作業(yè)調(diào)度模塊，選擇另外一個(gè)作業(yè)。圖3-6（b）說(shuō)明了某一時(shí)刻，作業(yè)A、B、C分別被分配到1，2，3三個(gè)分區(qū)中，第四個(gè)分區(qū)尚未分配，操作系統(tǒng)則永久占據(jù)內(nèi)存低地址區(qū)20KB的空間。當(dāng)一個(gè)作業(yè)結(jié)束時(shí)，系統(tǒng)又調(diào)用存儲(chǔ)管理程序查到分區(qū)說(shuō)明表，把所占分區(qū)的使用標(biāo)志修改為未分配狀態(tài)即可。

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

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

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

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

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

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

ExampleDynamicPartitioningOperating

SystemProcess1320KProcess2Process3224K288K64KOperating

SystemProcess1320KProcess3224K288K64KOperating

SystemProcess1320KProcess3288K64KProcess4128K96KExampleDynamicPartitioning-1Operating

System320KProcess3288K64KProcess4128K96KOperating

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

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

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

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

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

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

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

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

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

作業(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對(duì)于前圖所示的可變式分區(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回收前后序號(hào)P 大小 起址 狀態(tài) 1 32k 20k 空閑 2 56k 260k 空閑 3116k 396k 空閑 4 — — 空表目 5 — — 空表目 （a）空閑分區(qū)表序號(hào)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回收前后序號(hào)P 大小 起址 狀態(tài) 1 32k 20k 空閑 2 56k 260k 空閑 3116k 396k 空閑 4 — — 空表目 5 — — 空表目 （a）空閑分區(qū)表序號(hào)P大小起址狀態(tài) 1 96k20k空閑 2 56k260k空閑 3 116k396k空閑 4 ——空表目 5 ——空表目 空閑分區(qū)表空閑區(qū)1（96k）可變分區(qū)回收算法-6作業(yè)4回收前后序號(hào)P 大小 起址 狀態(tài) 1 32k 20k 空閑 2 56k 260k 空閑 3116k 396k 空閑 4 — — 空表目 5 — — 空表目 （a）空閑分區(qū)表序號(hào)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回收前后序號(hào)P 大小 起址 狀態(tài) 1 32k 20k 空閑 2 56k 260k 空閑 3116k 396k 空閑 4 — — 空表目 5 — — 空表目 （a）空閑分區(qū)表序號(hào)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)不斷地分配和回收中，必定會(huì)出現(xiàn)一些不連續(xù)的小的空閑區(qū)，稱為外零頭或外碎片。雖然可能所有零頭的總和超過某一個(gè)作業(yè)的要求，但是由于不連續(xù)而無(wú)法分配。解決零頭的方法是拼接或緊湊（Compaction），即向一個(gè)地址方向（例如向低地址端）移動(dòng)已分配的作業(yè)，使那些零散的小空閑區(qū)在另一方向連成一片。分區(qū)的拼接技術(shù)，一方面是要求能夠?qū)ψ鳂I(yè)進(jìn)行重定位，另一方面系統(tǒng)在拼接時(shí)要耗費(fèi)較多的時(shí)間。采用拼接技術(shù)的可變分區(qū)又稱可重定位分區(qū)。

動(dòng)態(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)移動(dòng)之后(即浮動(dòng))20k28k72ko.s1(8k)3(24k)2(20k)4(50k)(134k)52k122k256k作業(yè)580k(6)分區(qū)的存儲(chǔ)保護(hù)

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

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

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

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

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

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

頁(yè)號(hào)P位移量W1510902．頁(yè)表

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

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

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

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

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

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

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

頁(yè)號(hào)2頁(yè)內(nèi)地址452頁(yè)表始址頁(yè)表長(zhǎng)度﹥

245越界中斷頁(yè)表寄存器CPU指令寄存器LOAD1,2500邏輯地址2500頁(yè)號(hào)塊號(hào)

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

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

分頁(yè)存儲(chǔ)管理邏輯地址到物理地址地址變換的計(jì)算-1十六進(jìn)制－－邏輯地址09C4H1KB1024400H∵C00H＞09C4H＞800H

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

=

1400H+1C4H=15C4H

ThepositionandfunctionoftheMMU4．快表

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

在快表的輸入寄存器輸入頁(yè)號(hào)后，輸入頁(yè)號(hào)與快表中的各頁(yè)表項(xiàng)中的頁(yè)號(hào)同時(shí)比較，如有相同，快表的輸出寄存器輸出相應(yīng)的塊號(hào)，如都不相同，快表的輸出寄存器不輸出?？毂泶嫒∷俣瓤欤捎诔杀镜脑?，快表不可能做得很大，大程序的頁(yè)表項(xiàng)不可能全部放在快表中。為此，把各進(jìn)程的頁(yè)表仍放在內(nèi)存的系統(tǒng)區(qū)中，而系統(tǒng)增加的快表用以存放正在運(yùn)行進(jìn)程的、當(dāng)前常用的部分頁(yè)面的頁(yè)號(hào)和相應(yīng)的塊號(hào)。

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

012

245越界中斷邏輯地址頁(yè)表寄存器頁(yè)號(hào)塊號(hào)塊號(hào)頁(yè)號(hào)快表物理地址頁(yè)表

頁(yè)號(hào)頁(yè)內(nèi)地址頁(yè)表始址頁(yè)表長(zhǎng)度﹥塊號(hào)塊內(nèi)地址

輸入寄存器021425快表-2

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

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

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

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

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

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

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

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

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

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

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

作業(yè)空間

(MAIN）=00段表

15K段號(hào)段長(zhǎng)基址（X）=10

017K

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

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

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

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

段號(hào)段長(zhǎng)SL基址段表始址段表長(zhǎng)度

TL段號(hào)S位移量d2100﹥15K40K7K80K8K120K10K50K

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

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

Cl

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

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

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

段表段長(zhǎng)基址

1608040240

editor

DATA1

editor

DATA2段長(zhǎng)基址1608040380

editorDATA1

DATA2進(jìn)程1進(jìn)程2

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

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

3．3．3段頁(yè)式存儲(chǔ)管理

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

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

基本原理-1

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

頁(yè)

表頁(yè)號(hào)狀態(tài)存儲(chǔ)塊號(hào)0111

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

+

段表0123

頁(yè)表0123段表始址段表長(zhǎng)度

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

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

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

3．4．1虛擬存儲(chǔ)器的基本概念

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

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

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

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

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

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

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

3．4．2請(qǐng)求分頁(yè)存儲(chǔ)管理

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

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

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

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

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