操作系統(tǒng) 課件 第5章 存儲管理

第5章存儲管理5.1存儲管理概述5.2分區(qū)管理方案5.3覆蓋與交換技術(shù)5.4虛擬頁面存儲管理方案目錄CONTENTSPART5.1存儲管理概述5.1.1存儲體系

計算機(jī)系統(tǒng)中的存儲部件是需要物理實現(xiàn)的，理想存儲部件需要高速、海量和非易失的特性，因此存儲管理需要有機(jī)組合各種不同的物理存儲部件，形成其自有的體系結(jié)構(gòu)①最先進(jìn)的計算機(jī)科學(xué)技術(shù)能夠提供的存儲部件的速度，仍然明顯地慢于同級別的處理器的速度②由于成本等方面的原因，任何一種存儲部件都無法在速度與容量兩個方面同時滿足用戶的需求③為解決這些矛盾，采用如圖5-1所示的存儲體系結(jié)構(gòu)云存儲(CloudStorage)外存(SecondaryStorage)內(nèi)存(PrimaryStorage)高速緩存(Cache)寄存器(Register)容量大、速度慢、成本低容量小、速度快、成本高圖5-1存儲體系5.1.1存儲體系①寄存器：處理器中暫存信息的；少量的、非?？焖?、昂貴、通常是MB字節(jié)的數(shù)量級；②內(nèi)存RAM：中等速度、中等價格、內(nèi)容易變的、通常是GB字節(jié)的數(shù)量級；③外存磁盤：低速、價廉、內(nèi)容不易變的，通常是TB字節(jié)的數(shù)量級；④外存部件：還包括光盤、磁帶機(jī)等，總?cè)萘靠梢栽龃笾罷B或PB字節(jié)；⑤云存儲：大量外存部件有組織地組合在一起并通過高速網(wǎng)絡(luò)和用戶連接快速存儲設(shè)備和大容量存儲設(shè)備必須構(gòu)成為統(tǒng)一的整體，由操作系統(tǒng)協(xié)調(diào)這些存儲器的使用各種速度和容量的存儲器硬件，在操作系統(tǒng)協(xié)調(diào)之下形成了一種存儲器層次結(jié)構(gòu)，或稱存儲體系云存儲(CloudStorage)外存(SecondaryStorage)內(nèi)存(PrimaryStorage)高速緩存(Cache)寄存器(Register)容量大、速度慢、成本低容量小、速度快、成本高圖5-1存儲體系5.1.2存儲管理的任務(wù)程序需要有一個可以長久存放的外存空間，通常是磁盤程序能夠快速運(yùn)行必須是處理器能夠直接訪問，因此必須占用一定的內(nèi)存空間外存管理通常通過文件系統(tǒng)來實現(xiàn)內(nèi)存管理是對處理器直接訪問的內(nèi)存空間進(jìn)行管理，所謂內(nèi)存空間是由存儲單元（字節(jié)或字）組成的一維連續(xù)的地址空間，簡稱內(nèi)存空間，用來存放當(dāng)前正在運(yùn)行程序的代碼及數(shù)據(jù)，是程序中指令本身地址所指的、亦即程序計數(shù)器所指的存儲器內(nèi)存空間系統(tǒng)區(qū)存放操作系統(tǒng)常駐內(nèi)存部分，用戶不能占用這部分空間操作系統(tǒng)本身還有一部分可以被用戶使用的公共代碼和數(shù)據(jù)也存放在系統(tǒng)區(qū)用戶區(qū)用于裝入并存放用戶程序和數(shù)據(jù)，這部分的信息隨時都在發(fā)生變化內(nèi)存管理本質(zhì)是管理用戶使用空間以及協(xié)調(diào)用戶調(diào)用操作系統(tǒng)公共代碼和數(shù)據(jù)的使用5.1.2存儲管理的任務(wù)內(nèi)存管理方法內(nèi)存的分配和釋放算法虛擬存儲器的管理控制內(nèi)存和外存之間的數(shù)據(jù)流動方法地址變換技術(shù)內(nèi)存數(shù)據(jù)保護(hù)與共享技術(shù)對內(nèi)存進(jìn)行有效的管理，一般把內(nèi)存分成若干個區(qū)域在最簡單的單道、單用戶系統(tǒng)中，至少也要把它分成兩個區(qū)域：在一個區(qū)域內(nèi)存放系統(tǒng)軟件，如操作系統(tǒng)本身；而另外一個區(qū)域則用于安置用戶程序在多道、多用戶系統(tǒng)中，為了提高系統(tǒng)的利用率，需要將內(nèi)存劃分成更多的區(qū)域，以便支持多道程序5.1.2存儲管理的任務(wù)充分利用內(nèi)存，為多道程序并發(fā)執(zhí)行提供存儲基礎(chǔ)盡可能方便用戶使用系統(tǒng)能夠解決程序空間比實際內(nèi)存空間大的問題程序的長度在執(zhí)行時可以動態(tài)伸縮內(nèi)存存取速度快、效率高保證系統(tǒng)和用戶存儲空間的安全，不發(fā)生非法操作提供資源共享與通信交流通道監(jiān)控關(guān)鍵資源的使用狀況較高的性價比內(nèi)存管理要求滿足以下需求5.1.2存儲管理的任務(wù)I內(nèi)存的分配與回收一個有效的內(nèi)存分配機(jī)制，應(yīng)對用戶提出的需求予以快速響應(yīng)，為之分配相應(yīng)的內(nèi)存空間；在用戶程序不再需要它時及時回收，以供其他用戶使用。為此，應(yīng)該具有以下功能記住每個內(nèi)存區(qū)域的狀態(tài)內(nèi)存空間哪些是分配了哪些是空閑的實施分配當(dāng)用戶提出申請時，按需要進(jìn)行分配。分配方式有靜態(tài)分配和動態(tài)分配兩種回收接受用戶釋放的區(qū)域在計算機(jī)操作系統(tǒng)中，通過引入分配表格（統(tǒng)稱為內(nèi)存分配表）來管理內(nèi)存，通常采用2種組織方式實現(xiàn)上述功能，包括：①位示圖表示法：將內(nèi)存按序劃分為固定大小的區(qū)域，稱為內(nèi)存塊，用一位（Bit）表示一個內(nèi)存塊的狀態(tài)（0表示空閑，稱為空閑塊；1表示占用，稱為已用塊）②鏈表法：將已分配的內(nèi)存空間區(qū)域（一個或多個）首地址和長度組成一條記錄，并將所有已分配的記錄按序組成鏈表，形成已分配內(nèi)存鏈表。將未分配的內(nèi)存空間區(qū)域（一個或多個）首地址和長度組成一條記錄，并將所有分配的記錄按序組成鏈表，形成空閑內(nèi)存鏈表。分配時，操作系統(tǒng)查找空閑鏈表；回收時，操作系統(tǒng)合并未空閑鏈表5.1.2存儲管理的任務(wù)I內(nèi)存的分配與回收動態(tài)分配靜態(tài)分配內(nèi)存空間是在目標(biāo)程序模塊鏈接后裝入內(nèi)存時確定并分配的，并且在程序運(yùn)行過程中不允許再申請或在內(nèi)存中“搬家”，即分配工作是在程序運(yùn)行前一次性完成內(nèi)存空間是在目標(biāo)模塊裝入時或運(yùn)行時鏈接并確定分配的，但是在程序運(yùn)行過程中允許申請附加的內(nèi)存空間或在內(nèi)存中“搬家”，即分配工作可以在程序運(yùn)行前及運(yùn)行過程中逐步完成①

動態(tài)分配具有較大的靈活性，在程序運(yùn)行中需要時，操作系統(tǒng)自動將其調(diào)入內(nèi)存②

程序當(dāng)前暫不使用的信息可以不進(jìn)入內(nèi)存，這對提高內(nèi)存的利用率大有好處③

動態(tài)分配反映了程序的動態(tài)性，較之靜態(tài)分配更為合理5.1.2存儲管理的任務(wù)I內(nèi)存共享內(nèi)存共享定義共享內(nèi)容目的指兩個或多個進(jìn)程共用內(nèi)存中相同區(qū)域，多道程序動態(tài)地共享內(nèi)存，提高內(nèi)存利用率。也能共享內(nèi)存中某個區(qū)域的信息代碼共享和數(shù)據(jù)共享特別是代碼共享要求代碼必須是純代碼（運(yùn)行中不會改變）通過代碼共享節(jié)省內(nèi)存空間，提高內(nèi)存利用率通過數(shù)據(jù)共享實現(xiàn)進(jìn)程通信5.1.2存儲管理的任務(wù)I內(nèi)存保護(hù)內(nèi)存保護(hù)保護(hù)內(nèi)容目的保護(hù)系統(tǒng)程序區(qū)不被用戶有意或無意的侵犯不允許用戶程序讀寫不屬于自己程序的內(nèi)存空間多個程序共享內(nèi)存提供保障，內(nèi)存中的各道程序，只能訪問它自己的區(qū)域當(dāng)一道程序發(fā)生錯誤時，不至于影響其他程序的運(yùn)行在多道程序系統(tǒng)中，內(nèi)存中既有操作系統(tǒng)，又有許多用戶程序。為使系統(tǒng)正常運(yùn)行，避免內(nèi)存中各程序相互干擾，必須對內(nèi)存中的程序和數(shù)據(jù)進(jìn)行保護(hù)方法地址越界保護(hù)：進(jìn)程在運(yùn)行時所產(chǎn)生的地址超出其地址空間范圍，則發(fā)生地址越界權(quán)限保護(hù)：對多個進(jìn)程共享的公共區(qū)域，每個進(jìn)程都有自己的訪問權(quán)限5.1.2存儲管理的任務(wù)I“擴(kuò)充”內(nèi)存容量擴(kuò)充內(nèi)存容量目的實現(xiàn)意義用戶在編制程序時，通常不受內(nèi)存容量限制，實際運(yùn)行時受制于具體的物理計算機(jī)平臺。操作系統(tǒng)要采用一定技術(shù)來“擴(kuò)充”內(nèi)存的容量，使用戶得到比物理內(nèi)存容量大得多的內(nèi)存空間在硬件支持下，軟件、硬件相互協(xié)作，將內(nèi)存和外存結(jié)合起來統(tǒng)一使用通過這種方法擴(kuò)充內(nèi)存，使用戶在編制程序時不受內(nèi)存限制借助虛擬存儲技術(shù)或其他交換技術(shù)，達(dá)到在邏輯上擴(kuò)充內(nèi)存容量5.1.3地址轉(zhuǎn)換

存儲器以字節(jié)（每個字節(jié)為8個二進(jìn)制位）為編址單位，每個字節(jié)都有一個地址與其對應(yīng)。假定存儲器的容量為n個字節(jié)，其地址編號順序為0，1，2，…，n－1。這些地址稱為內(nèi)存的“絕對地址”，由絕對地址對應(yīng)的內(nèi)存空間稱為“物理地址空間”

在多道程序設(shè)計的系統(tǒng)中，內(nèi)存中同時存放了多個用戶程序。操作系統(tǒng)根據(jù)內(nèi)存的使用情況為用戶分配內(nèi)存空間。因此，每個用戶不能預(yù)先知道他的程序?qū)⒈淮娣诺絻?nèi)存的什么位置，用戶程序中就不能使用內(nèi)存的絕對地址。為了方便用戶，每個用戶都可認(rèn)為自己的程序和數(shù)據(jù)存放在一組“0”地址開始的連續(xù)空間中。用戶程序中使用的地址稱為“邏輯地址”，由邏輯地址對應(yīng)的內(nèi)存空間稱為“邏輯地址空間”5.1.3地址轉(zhuǎn)換I地址重定位地址重定位定義方式邏輯地址轉(zhuǎn)換成絕對地址的工作靜態(tài)重定位動態(tài)重定位

當(dāng)用戶程序請求執(zhí)行時，內(nèi)存管理要為它分配合適的內(nèi)存空間，該內(nèi)存空間的起始物理（絕對）地址是不固定的，而且起始邏輯地址與分到的起始內(nèi)存空間的物理（絕對）地址經(jīng)常不一致，且后續(xù)也如此。因此，每個邏輯地址在內(nèi)存中也沒有一個固定的物理（絕對）地址與之對應(yīng)

5.1.3地址轉(zhuǎn)換I地址重定位I靜態(tài)重定位

裝入程序前，靜態(tài)重定位把程序中的指令和數(shù)據(jù)的邏輯地址全部轉(zhuǎn)換成絕對地址后再裝入。地址轉(zhuǎn)換工作是在程序開始執(zhí)行前集中完成，所以在程序執(zhí)行過程中就無需再進(jìn)行地址轉(zhuǎn)換工作圖5-2靜態(tài)重定位

假定用戶程序的邏輯地址空間從“0”到“168”，其中第18號單元處有一條“加法”指令，該指令要求從第066號單元處取出操作數(shù)1234，然后進(jìn)行加法操作。如果內(nèi)存管理為該程序分配的內(nèi)存區(qū)域是從800號單元開始，那么，邏輯地址第18號單元在內(nèi)存中的對應(yīng)位置是818號單元，第066號單元在內(nèi)存中的對應(yīng)位置應(yīng)該是866號單元。如果不修改上述“加法”指令中的操作數(shù)地址，則處理器執(zhí)行該指令時將從內(nèi)存的066單元中去取操作數(shù)，這顯然是錯誤的，參見圖5-2案例5.1.3地址轉(zhuǎn)換I地址重定位I動態(tài)重定位

裝入程序前，不進(jìn)行地址轉(zhuǎn)換，而是直接把程序裝入到分配的內(nèi)存區(qū)域中。在程序執(zhí)行過程中，每當(dāng)執(zhí)行一條指令時都由硬件的地址轉(zhuǎn)換機(jī)構(gòu)將程序中的邏輯地址轉(zhuǎn)換成絕對地址

圖5-3指出了動態(tài)重定位的過程。程序裝入到從地址1000開始的內(nèi)存中，從程序起始位于100的地方有一條指令LOAD1,500，意思為將地址500中的數(shù)據(jù)裝入到寄存器1，執(zhí)行時該指令時，需要將該數(shù)據(jù)所在的邏輯地址500與基址寄存器BR（BaseRegister）中的1000相加，得到1500，再去讀取內(nèi)存1500中數(shù)據(jù)并將其放入寄存器1圖5-3動態(tài)重定位案例背景-2：北京大學(xué)圖書館PART5.2分區(qū)管理方案分區(qū)管理分區(qū)管理定義基本思想方式能滿足多道程序運(yùn)行的最簡單的存儲管理方案把內(nèi)存劃分成若干個連續(xù)區(qū)域，稱為分區(qū)每個分區(qū)裝入一個運(yùn)行程序固定分區(qū)可變分區(qū)5.2.1固定分區(qū)固定分區(qū)基本思想內(nèi)存分配表

把內(nèi)存劃分成若干個大小固定的分區(qū)，在系統(tǒng)運(yùn)行期間便不再重新劃分不同程序的存儲要求，各分區(qū)的大小可以不同程序運(yùn)行時必須提供對內(nèi)存資源的最大申請量是一張分區(qū)說明表，按順序每個分區(qū)在分區(qū)說明表中對應(yīng)一個表項內(nèi)容包括分區(qū)序號、分區(qū)大小、分區(qū)起始地址以及使用狀態(tài)（空閑或占用）

一個程序在運(yùn)行時，先要根據(jù)其對內(nèi)存的需求量，按一定的分配策略在分區(qū)說明表中查找空閑分區(qū)。若找到能合乎需要的分區(qū)，就將該分區(qū)分配給程序，并將該分區(qū)置為占用狀態(tài)。當(dāng)程序完成時釋放這塊分區(qū)內(nèi)存，由系統(tǒng)回收，并在分區(qū)說明表中將回收的分區(qū)重新置為空閑狀態(tài)，若有上下鄰空閑分區(qū)，還需要進(jìn)行合并5.2.1固定分區(qū)圖5-4固定分區(qū)示例在圖5-4中，通過分區(qū)說明表可以看到，區(qū)號為1的分區(qū)大小為8K，起始地址為16K，狀態(tài)為占用，實際是被進(jìn)程A占用；區(qū)號為2的分區(qū)大小為16K，起始地址為24K，狀態(tài)為空閑；區(qū)號為3的分區(qū)大小為32K，起始地址為40K，狀態(tài)為占用，實際是被進(jìn)程B占用；如此等等

固定分區(qū)方案都不能充分利用內(nèi)存。因為一個程序的大小，不可能剛好等于某個分區(qū)的大小。所以很難避免內(nèi)存空間的浪費(fèi)，這種存在于分區(qū)內(nèi)部不可再利用的內(nèi)存空間稱之為內(nèi)碎片

固定分區(qū)方案靈活性差，可接納程序的大小受到了分區(qū)大小的嚴(yán)格限制案例5.2.2可變分區(qū)I基本思想可變分區(qū)基本思想1基本思想2系統(tǒng)不預(yù)先劃分固定分區(qū)裝入程序時劃分內(nèi)存分區(qū)，使程序分配的分區(qū)的大小等于該程序的需求量分區(qū)的個數(shù)是可變的、不確定的當(dāng)有程序要求裝入內(nèi)存運(yùn)行時，系統(tǒng)從該空閑區(qū)中劃分出一塊與程序大小相同的區(qū)域進(jìn)行分配當(dāng)系統(tǒng)運(yùn)行一段時間后，隨著一系列的內(nèi)存分配和回收。原來的一整塊大空閑區(qū)形成了若干占用區(qū)和空閑區(qū)相間的布局5.2.2可變分區(qū)I基本思想系統(tǒng)為程序D分配一塊內(nèi)存分區(qū)，此時內(nèi)存中剩下了兩塊較小的空閑區(qū)，一塊空閑區(qū)大小為10K,另一塊空閑區(qū)大小為24K。程序E大小為40K，比這兩塊空閑區(qū)大，程序E的需要不能滿足圖5-5可變分區(qū)

某一時刻內(nèi)存空間的布局情況，此時內(nèi)存裝入了A、B、C三個程序，一塊空閑區(qū)大小為10K，另一塊空閑區(qū)大小為94K。此時，又有程序D和程序E請求裝入，程序D大小為70K；表示程序A（大小為16K）和C（大小為30K）已完成，系統(tǒng)回收了它們的占用區(qū)。從程序A回收了16K與原有的10K的空閑區(qū)合并，形成一個26K的空閑區(qū)；從程序C回收了30K，形成一個26K的空閑區(qū)，這樣在內(nèi)存中形成了三塊空閑區(qū)，大小分別是26K、30K和24K，它們的總?cè)萘侩m然遠(yuǎn)大于程序E（大小為40K）的需求量，但每塊空閑區(qū)的單獨容量均小于程序E的容量，故系統(tǒng)仍不能為程序E實施分配（a）（b）（c）5.2.2可變分區(qū)I緊縮技術(shù)

內(nèi)存經(jīng)過一段時間的分配回收后，會存在很多很小的空閑塊。它們每一塊都很小，不足以滿足程序分配內(nèi)存的要求，但其總和卻可以滿足程序的分配要求，這些空閑塊很像碎片，這種操作系統(tǒng)知曉的（在內(nèi)存分配鏈表中有記錄），可以分配但區(qū)域很小的空閑空間稱為外碎片。圖5-6內(nèi)存緊縮

解決外碎片問題的辦法是在適當(dāng)時刻進(jìn)行碎片整理，通過移動內(nèi)存中的程序，把所有空閑碎片合并成一個連續(xù)的大空閑區(qū)，這種方法稱之為“內(nèi)存緊縮”，又稱為“緊縮技術(shù)”，或“壓縮技術(shù)”5.2.2可變分區(qū)I緊縮技術(shù)

進(jìn)程E需要40K的空間，在內(nèi)存中，有三塊空閑的外碎片，大小分別是26K、30K和24K，它們的總?cè)萘?0K雖然遠(yuǎn)大于進(jìn)程E（大小為40K）的需求量，但每塊空閑區(qū)的單獨容量均小于進(jìn)程E的容量，由于普通程序的裝入要求程序的地址空間保持連續(xù)，不得離散，系統(tǒng)仍不能為進(jìn)程E實施分配，參見圖5-6（a）。采用緊縮技術(shù)之后，在內(nèi)存中的進(jìn)程B和進(jìn)程D被移動到內(nèi)存的一端，三塊碎片被拼接為一個大的空閑區(qū)，其容量為80K，參見圖5-6（b）圖5-7緊縮技術(shù)方案的比較圖5-6內(nèi)存緊縮緊縮技術(shù)為進(jìn)程E的運(yùn)行創(chuàng)造了條件，進(jìn)程E被分配了40K空間，還剩下一塊40K的空閑區(qū)5.2.2可變分區(qū)I緊縮技術(shù)緊縮技術(shù)價值注意問題集中分散的空閑區(qū)，提高內(nèi)存的利用率，便于進(jìn)程動態(tài)擴(kuò)充內(nèi)存緊縮技術(shù)會增加系統(tǒng)的開銷，也增大了系統(tǒng)運(yùn)行時間移動是有條件的，不是任何在內(nèi)存中的進(jìn)程都能隨時移動盡可能減少需要移動的進(jìn)程數(shù)和信息量5.2.2可變分區(qū)I可變分區(qū)的實現(xiàn)

采用可變分區(qū)方式管理時，硬件設(shè)置兩個專用的控制寄存器：基址寄存器和限長寄存器，限長寄存器用來存放程序所占分區(qū)的長度，基址寄存器用來存放程序所占分區(qū)的起始地址圖5-8可變分區(qū)地址轉(zhuǎn)換5.2.2可變分區(qū)I可變分區(qū)的實現(xiàn)必須設(shè)置某種數(shù)據(jù)結(jié)構(gòu)用以記錄內(nèi)存分配的情況，確定某種分配策略并且實施內(nèi)存的分配與回收可以利用前述已分配內(nèi)存鏈表和空閑內(nèi)存鏈表來管理可變分區(qū)圖5-9已分配區(qū)表和空閑區(qū)表

已分配內(nèi)存鏈表也稱為已分配區(qū)表，記錄已裝入的程序在內(nèi)存中占用分區(qū)的起始地址和長度，用標(biāo)志位指出占用分區(qū)的程序名。另一個是空閑內(nèi)存鏈表，也稱為空閑區(qū)表，記錄內(nèi)存中可供分配的空閑區(qū)的起始地址和長度，用標(biāo)志位指出該分區(qū)是未分配的空閑區(qū)。由于已占用分區(qū)和空閑區(qū)的個數(shù)不定，因此，兩張表格中都應(yīng)設(shè)置適當(dāng)?shù)目諜谀?，分別用以登記新內(nèi)存分配表項，如圖5-9所示案例5.2.2可變分區(qū)I可變分區(qū)的實現(xiàn)當(dāng)接到內(nèi)存申請時，順序查找空閑區(qū)表，找到第一個滿足申請長度的空閑區(qū)，將其分割并分配當(dāng)接到內(nèi)存申請時，查找分區(qū)說明表，找到第一個能滿足申請長度的最小空閑區(qū)，將其分割并分配當(dāng)接到內(nèi)存申請時，查找分區(qū)說明表，找到能滿足申請要求的最大的空閑區(qū)最先適應(yīng)算法最優(yōu)適應(yīng)算法最壞適應(yīng)算法操作系統(tǒng)查找和分配空閑區(qū)的三種分配算法

5.2.2可變分區(qū)I分區(qū)的回收一個歸還區(qū)可能有上鄰空閑區(qū)，也可以有下鄰空閑區(qū)，或既有上鄰又有下鄰空閑區(qū)，或既無上鄰又無下鄰空閑區(qū)。假定進(jìn)程歸還的分區(qū)起始地址為S，長度為L。一般情況下應(yīng)考慮如下四種可能性程序執(zhí)行結(jié)束后，系統(tǒng)要回收已使用完畢的分區(qū)，將其記錄在空閑區(qū)表中。在收回空間時，應(yīng)首先檢查是否有與歸還區(qū)相鄰的空閑區(qū)，即檢查相鄰的空閑區(qū)表中標(biāo)志為“未分配”的欄目，以確定是否有相鄰空閑區(qū)，若有，則應(yīng)合并成一個空閑區(qū)登記回收分區(qū)的上鄰分區(qū)是空閑的，需要將兩個空閑區(qū)合并成一個更大的空閑區(qū)，然后修改空閑區(qū)表

回收分區(qū)的下鄰分區(qū)是空閑的，需要將兩個空閑區(qū)合并成一個更大的空閑區(qū)，然后修改空閑區(qū)表回收分區(qū)的上鄰和下鄰分區(qū)都是空閑的，需要將三個空閑區(qū)合并成一個更大的空閑區(qū)，然后修改空閑區(qū)表回收分區(qū)的上鄰和下鄰分區(qū)都不是空閑的，則直接將空閑分區(qū)記錄在空閑區(qū)表中12345.2.2可變分區(qū)I分區(qū)的保護(hù)保護(hù)方法一：系統(tǒng)設(shè)置界限寄存器，界限寄存器可以是上、下界寄存器或基址、限長寄存器。通常系統(tǒng)設(shè)置一對界限寄存器，用來存放現(xiàn)行進(jìn)程的內(nèi)存界限。在進(jìn)程的PCB中保存界限值，當(dāng)輪到該進(jìn)程執(zhí)行時，將界限值作為進(jìn)程現(xiàn)場的一部分恢復(fù)。在進(jìn)程執(zhí)行過程產(chǎn)生的每一個訪問內(nèi)存的地址，硬件都自動將其與界限寄存器的值進(jìn)行比較，若發(fā)生地址越界，便產(chǎn)生保護(hù)性地址越界中斷，參見圖5-12保護(hù)方法二：保護(hù)鍵方法，即為每個分區(qū)分配一個保護(hù)鍵，相當(dāng)于一把鎖。同時為每個進(jìn)程分配一個相應(yīng)的保護(hù)鍵，相當(dāng)于一把鑰匙，存放在程序狀態(tài)字中。每當(dāng)訪問內(nèi)存時，都要檢查鑰匙和鎖是否匹配，若不匹配，將發(fā)出保護(hù)性中斷圖5-12界限寄存器保護(hù)5.2.3分區(qū)管理方案的優(yōu)缺點通過分區(qū)管理，內(nèi)存真正成為了共享資源，提高了系統(tǒng)的吞吐量和縮短了周轉(zhuǎn)時間。分區(qū)內(nèi)存管理算法比較簡單，實現(xiàn)起來比較容易，內(nèi)存額外開銷較少，內(nèi)存保護(hù)措施簡單內(nèi)存利用率，可變分區(qū)的內(nèi)存利用率比固定分區(qū)高內(nèi)存使用仍不充分，并且存在著較為嚴(yán)重的外碎片問題不能實現(xiàn)對內(nèi)存的“擴(kuò)充”，程序的存儲要求仍然受到物理存儲器實際內(nèi)存容量的限制分區(qū)管理要求運(yùn)行程序一次全部裝入內(nèi)存之后，才能開始運(yùn)行優(yōu)點缺點背景-3：西門華表PART5.3覆蓋與交換技術(shù)5.3.1覆蓋技術(shù)覆蓋技術(shù)定義實現(xiàn)方式意義程序的若干程序段，或幾個程序的某些部分共享某一個存儲空間把程序劃分為若干個功能上相對獨立的程序段，按照其自身的邏輯結(jié)構(gòu)使那些不會同時執(zhí)行的程序段共享同一塊內(nèi)存區(qū)域。未執(zhí)行的程序段先保存在磁盤上，當(dāng)有關(guān)程序段的前一部分執(zhí)行結(jié)束后，把后續(xù)程序段調(diào)入內(nèi)存，覆蓋前面的程序段打破需要將一個程序的全部信息裝入內(nèi)存后程序才能運(yùn)行的限制邏輯上擴(kuò)充了內(nèi)存空間，從而在某種程度上實現(xiàn)了在小容量內(nèi)存上運(yùn)行較大程序的功能5.3.1覆蓋技術(shù)

假設(shè)進(jìn)程1的程序正文由A，B，C，D，E，F(xiàn)，等6個程序段組成。它們之間的調(diào)用關(guān)系如圖5-13（a）所示。其中，程序段A只調(diào)用程序段B和C，程序段B只調(diào)用程序段F，而程序段C只調(diào)用D和E。即B不會調(diào)用C，C也不會調(diào)用B。因此，程序段B和程序段C就無須同時在內(nèi)存中?？砂磮D5-13（b）分配程序段的調(diào)入?？梢?，雖然該程序正文段所需要的內(nèi)存空間是：A（20K）＋B（50K）＋F（30K）＋C（30K）＋D（20K）＋E（40K）＝190K，但是，在采用了覆蓋技術(shù)后，只需要110K內(nèi)存空間就行了圖5-13覆蓋示例

案例5.3.1交換技術(shù)交換技術(shù)定義實現(xiàn)方式意義又稱對換技術(shù)。在分時系統(tǒng)中，用戶的進(jìn)程需要的內(nèi)存總量比系統(tǒng)中實際內(nèi)存的總量要多，這就需要在磁盤上保存那些在內(nèi)存放不下的進(jìn)程。在需要運(yùn)行這些進(jìn)程時，再將它們裝入內(nèi)存進(jìn)程從內(nèi)存移到磁盤，并再移回內(nèi)存稱為交換系統(tǒng)可以將那些不在運(yùn)行中的進(jìn)程或其一部分調(diào)出內(nèi)存，暫時存放在外存上的一個后備存儲區(qū)中，以騰出內(nèi)存空間給當(dāng)前需要內(nèi)存空間的進(jìn)程，后者可能需要從外存換入內(nèi)存，以后再將換出的進(jìn)程調(diào)入內(nèi)存繼續(xù)執(zhí)行盡可能達(dá)到“足夠快地交換進(jìn)程，以使當(dāng)CPU調(diào)度程序想重新調(diào)度CPU時，總有進(jìn)程在內(nèi)存中處于就緒（準(zhǔn)備執(zhí)行）狀態(tài)”的理想狀態(tài)，從而提高內(nèi)存利用率5.3.2交換技術(shù)I相關(guān)考慮問題①

換出進(jìn)程的選擇

在使用交換技術(shù)時，換出進(jìn)程的選擇是非常重要的問題，如果處理不當(dāng)，將會造成整個系統(tǒng)效率低下。在分時系統(tǒng)中，一般情況下可以根據(jù)時間片輪轉(zhuǎn)法或基于優(yōu)先數(shù)的調(diào)度算法來選擇要換出的進(jìn)程。系統(tǒng)在選擇換出進(jìn)程時，希望換出的進(jìn)程是短時間內(nèi)不會立刻投入運(yùn)行的②

交換時機(jī)的確定

一般情況下可以在內(nèi)存空間不夠或有不夠的危險時，換出內(nèi)存中的部分進(jìn)程到外存，以釋放所需內(nèi)存。也可以當(dāng)系統(tǒng)發(fā)現(xiàn)一個進(jìn)程長時間不運(yùn)行時就將該進(jìn)程換出5.3.2交換技術(shù)I相關(guān)考慮問題③

交換空間的分配圖5-14磁盤交換空間的管理

在一些系統(tǒng)中，當(dāng)進(jìn)程在內(nèi)存中時，不再為它分配磁盤空間。當(dāng)它被換出時，必須為它分配磁盤交換空間，如圖5-14（b）。每次交換，進(jìn)程都可能被換到磁盤的不同地方，這種管理交換區(qū)的方法與管理內(nèi)存的方法相同。在另外一些系統(tǒng)中，進(jìn)程一旦創(chuàng)建，就分配給它磁盤上的交換空間，如圖5-14（a）。無論何時進(jìn)程被換出，它都被換到已經(jīng)為它分配的空間，而不是每次換到不同的空間。當(dāng)進(jìn)程結(jié)束時，交換空間被回收。圖5-14說明了上述二種情形5.3.2交換技術(shù)I相關(guān)考慮問題④

換入進(jìn)程換回內(nèi)存時位置的確定

換出后再換入內(nèi)存的進(jìn)程，位置是否一定要在換出前的原來位置上。受絕對地址產(chǎn)生時的限制，如果進(jìn)程中引用的地址都是絕對地址，那么再次被換入內(nèi)存的進(jìn)程一定要在原來的位置上。如果進(jìn)程中引用的地址是相對地址，在裝入內(nèi)存可再進(jìn)行地址重定位，那么再次被換入內(nèi)存的進(jìn)程就可以不在原來的位置上背景-4：未名湖PART5.4虛擬頁式存儲管理方案5.4.1虛擬存儲技術(shù)虛擬存儲技術(shù)基本思想實現(xiàn)方式本質(zhì)利用大容量的外存來擴(kuò)充內(nèi)存，產(chǎn)生一個比有限的實際內(nèi)存空間大得多的、邏輯的虛擬內(nèi)存空間，以便能夠有效地支持多道程序系統(tǒng)的實現(xiàn)和大型程序運(yùn)行的需要，從而增強(qiáng)系統(tǒng)的處理能力由操作系統(tǒng)在硬件支持下把兩級存儲器（內(nèi)存和外存）統(tǒng)一實施管理，達(dá)到“擴(kuò)充”內(nèi)存的目的，呈現(xiàn)給用戶的是一個遠(yuǎn)遠(yuǎn)大于物理內(nèi)存容量的編程空間。操作系統(tǒng)把程序當(dāng)前使用的部分保留在物理內(nèi)存，而把其他部分保存在磁盤上，并在需要時在內(nèi)存和磁盤之間動態(tài)交換虛擬存儲器的容量也是有限制的，主要是受地址空間字長和外存容量所限5.4.1虛擬存儲技術(shù)實現(xiàn)虛擬存儲器需要以下的硬件支持硬件支持系統(tǒng)有容量足夠大的外存系統(tǒng)有一定容量的內(nèi)存最主要的是，硬件提供實現(xiàn)虛-實地址映射的機(jī)制5.4.1虛擬存儲技術(shù)

當(dāng)進(jìn)程開始運(yùn)行時，先將一部分程序裝入內(nèi)存，另一部分暫時留在外存；當(dāng)要執(zhí)行的指令不在內(nèi)存時，由系統(tǒng)自動完成將它們從外存調(diào)入內(nèi)存的工作；當(dāng)沒有足夠的內(nèi)存空間時，系統(tǒng)自動選擇部分內(nèi)存空間，將其中原有的內(nèi)容交換到磁盤上，并釋放這些內(nèi)存空間供其他進(jìn)程使用虛擬存儲器的工作原理

傳統(tǒng)的交換技術(shù)中，交換到外存上的對象一般都是進(jìn)程，也就是說交換技術(shù)是以進(jìn)程為單位進(jìn)行；而虛擬存儲——如虛擬頁式存儲管理方案——一般是以頁為交換單位與交換技術(shù)原理上的區(qū)別5.4.1虛擬存儲技術(shù)

當(dāng)進(jìn)程運(yùn)行中，內(nèi)外存交換的單元以固定大小的頁進(jìn)行時，稱為頁式。頁式是面向系統(tǒng)的技術(shù)，而并不考慮程序的結(jié)構(gòu)，軟硬件系統(tǒng)怎么方便就怎么來，因此，程序的代碼、數(shù)據(jù)、堆棧是不加區(qū)別地均以頁的方式進(jìn)行分塊。為了計算機(jī)映射的方便，頁的大小通常是2的冪次方。虛擬頁式存儲技術(shù)的工作原理

當(dāng)進(jìn)程運(yùn)行中，內(nèi)外存交換的單元以程序的結(jié)構(gòu)特征分類進(jìn)行時，稱為段式。段式是面向用戶的技術(shù)，考慮程序的組織結(jié)構(gòu)，對代碼段、數(shù)據(jù)段、堆棧段等分別處理，便于進(jìn)行保護(hù)和共享。但是，因為段的大小不固定，所以段式結(jié)構(gòu)除了有段號，還需要有段長的變量，這增加了計算機(jī)系統(tǒng)的復(fù)雜度。虛擬段式存儲技術(shù)的工作原理5.4.2虛擬頁式存儲管理虛擬頁式存儲管理發(fā)展實現(xiàn)方式首先由英國曼徹斯特大學(xué)提出，并在該校的Atlas計算機(jī)上使用。該技術(shù)近年來已廣泛用于微機(jī)系統(tǒng)中，支持頁式存儲管理的硬件部件通常稱為“存儲管理部件”（MMU：MemoryManagementUnit）存儲管理部件首先把內(nèi)存分成大小相等的許多塊，把每個塊稱為“物理頁面”或“頁框”，物理頁面是進(jìn)行內(nèi)存空間分配的物理單位。同時，要求程序中的邏輯地址也進(jìn)行分頁，頁的大小與物理頁面的大小一致。此時“邏輯地址”可被稱為虛擬地址。這樣，就可把程序信息按頁存放到物理頁面中。于是，頁式存儲器提供編程使用的虛擬地址由兩部分組成：虛擬頁號和頁內(nèi)地址格式5.4.3物理內(nèi)存的分配與回收

頁式存儲管理分配內(nèi)存空間以物理頁面為單位，由于物理頁面的大小是固定的，所以只要在內(nèi)存分配表中具有可以指出哪些物理頁面已經(jīng)分配、哪些物理頁面尚未分配以及當(dāng)前剩余的空閑物理頁面數(shù)等三種不同的標(biāo)識即可圖5-15頁式存儲管理的內(nèi)存分配表

簡單的內(nèi)存分配表可以用一張“位示圖”構(gòu)成。假設(shè)內(nèi)存的可分配區(qū)域被分成256個物理頁面，則可用字長為32位的8個字作為“位示圖”。位示圖中的每一位與一個物理頁面對應(yīng)，每一位的值可以是0或1，0表示對應(yīng)的物理頁面為空閑，1表示已占用。在位示圖中再增加一個字節(jié)記錄當(dāng)前剩余的總空閑物理頁面數(shù)，如圖5-15所示。初始化時系統(tǒng)在位示圖中把操作系統(tǒng)占用物理頁面所對應(yīng)的位置成1，其余位均置0，剩余空閑物理頁面數(shù)為可分配的空閑物理頁面總數(shù)案例5.4.3物理內(nèi)存的分配與回收圖5-15頁式存儲管理的內(nèi)存分配表在進(jìn)行內(nèi)存分配時，先查看空閑物理頁面數(shù)是否能滿足程序要求。若不能滿足，則不進(jìn)行分配，程序就不能裝入內(nèi)存；若能滿足，則根據(jù)需求從位示圖中找出一些為0的位，把這些位置成1，并從空閑頁面數(shù)中減去本次分配的頁面數(shù)，然后按照找到的位計算出對應(yīng)的物理頁面號當(dāng)找到一個為0的位后，根據(jù)它所在的字號、位號，按如下公式就可計算出對應(yīng)的塊號物理頁面號＝字號×字長＋位號把程序裝入到這些物理頁面中，并為該程序建立頁表。當(dāng)程序執(zhí)行結(jié)束時，則應(yīng)收回它所占用的物理頁面。根據(jù)歸還的物理頁面號計算出該物理頁面在位示圖中對應(yīng)的位置，將占用標(biāo)志修改成0，再把回收的物理頁面數(shù)加入到空閑物理頁面數(shù)中假定歸還塊的塊號為i，則在位示圖中對應(yīng)的位置為5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁式存儲管理的地址轉(zhuǎn)換為了實現(xiàn)頁式存儲管理，系統(tǒng)要提供一對硬件的頁表控制寄存器頁表始址寄存器頁表長度址寄存器另外：需要高速緩沖存儲器頁表始址寄存器，用于保存正在運(yùn)行進(jìn)程的頁表在內(nèi)存的首地址，當(dāng)進(jìn)程被調(diào)度程序選中投入運(yùn)行時，系統(tǒng)將其頁表首地址從進(jìn)程控制塊中取出送入該寄存器頁表長度寄存器，用于保存正在運(yùn)行進(jìn)程的頁表的長度，當(dāng)進(jìn)程被選中運(yùn)行時，系統(tǒng)將它從進(jìn)程控制塊中取出送入該寄存器

頁表指出該程序虛擬地址中的頁號與所占用的物理頁面號之間的對應(yīng)關(guān)系。頁表的長度由程序擁有的頁面數(shù)而定，故每個程序的頁表長度可能是不同的

頁表又是硬件進(jìn)行地址轉(zhuǎn)換的依據(jù)，每執(zhí)行一條指令時按虛擬地址中的頁號查頁表。若頁表中無此頁號，則產(chǎn)生一個“地址錯”的程序性中斷事件。若頁表中有此頁號，則可得到對應(yīng)的物理頁面號，按計算公式可轉(zhuǎn)換成訪問的內(nèi)存的物理地址5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁式存儲管理的地址轉(zhuǎn)換需要強(qiáng)調(diào)的是，物理頁面號又稱為頁幀或頁框號根據(jù)二進(jìn)制乘法運(yùn)算的性質(zhì)，一個二進(jìn)制數(shù)乘以2n結(jié)果實際上是將該數(shù)左移n位。所以，實際上是把物理頁面號作為絕對地址的高位地址，而頁內(nèi)地址作為它的低地址部分。地址轉(zhuǎn)換關(guān)系如圖

圖5-16頁式存儲管理的地址轉(zhuǎn)換關(guān)系物理地址的計算公式為：物理地址=物理頁面號×塊長＋頁內(nèi)地址5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁表項●物理頁面號；頁面在內(nèi)存中時所對應(yīng)的物理頁面號●有效位：又稱駐留位、存在位，表示該頁是在內(nèi)存還是在磁盤●訪問位：訪問位表示該頁在內(nèi)存期間是否被訪問過●修改位：修改位表示該頁在內(nèi)存中是否被修改過●保護(hù)位：是否能讀/寫其中，訪問位和修改位可以用來決定置換哪個頁面，具體由頁面置換算法決定

在進(jìn)程開始運(yùn)行之前，不是裝入全部頁面，而是裝入一個或零個頁面，之后根據(jù)進(jìn)程運(yùn)行的需要，動態(tài)裝入其他頁面；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時，則根據(jù)某種算法淘汰某個頁面，以便裝入新的頁面

在虛擬頁式存儲管理中，頁表項的設(shè)計如下5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁表當(dāng)系統(tǒng)支持32位的虛擬地址空間時，若頁面大小為4KB，則頁表將包含1M個表項。假設(shè)每個表項由4個字節(jié)組成，那么僅僅是為了存儲頁表就要為每個進(jìn)程分配4MB的物理地址空間。假設(shè)用戶地址空間為2GB，頁面大小為4KB，則一個進(jìn)程最多可以有219頁。若用4個字節(jié)表示一頁的物理頁號，則頁表本身就占用2MB，即需要512個頁面存放，我們稱存放頁表的頁面為頁表頁。一般來說，頁表頁可以不連續(xù)存放，因此，需要對頁表頁的地址進(jìn)行索引。一個簡單的解決辦法就是分級，例如采用兩級頁表，即頁面大小為4KB的32位機(jī)器，虛擬地址可被劃分為10位頁目錄、10位頁表和12位的頁內(nèi)偏移圖5-17二級頁表結(jié)構(gòu)

多級頁表：大多數(shù)現(xiàn)代計算機(jī)系統(tǒng)都支持很大的地址空間，由此帶來的結(jié)果是頁表本身也變得很大大多數(shù)32位的操作系統(tǒng)中采用二級頁表，即由頁表頁和頁目錄一起構(gòu)成進(jìn)程頁表。圖5-17表示了二級頁表結(jié)構(gòu)。其中，第一級表示頁目錄，保存頁表頁的地址；第二級表示頁表頁，保存物理頁面號案例5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁表散列頁表：當(dāng)?shù)刂房臻g大于32位時，一種常見的方法是使用以頁號為散列值的散列頁表。其中每個表項都包含一個鏈表，該鏈表中元素的散列值都指向同一個位置。這樣，散列頁表中的每個表項都包含三個字段虛擬頁號所映射的頁框號指向鏈表中下一個元素的指針由虛擬頁號得到散列值查找散列頁表，并將此頁號與鏈表中的第一個元素的字段（a）進(jìn)行比較。如果匹配，則相應(yīng)的頁框號（字段（b））就可用于形成物理地址。如果不匹配，則沿鏈表依次尋找相匹配的表項將上述方法稍作改變而得到的集群頁表更適用于64位的地址空間。它與雜湊頁表相似，不過其中每個表項代表了多個（例如16個）頁面而不是一個。這樣，一個頁表項就存儲了多個物理頁框的映射信息。對于散布于整個地址空間的不連續(xù)內(nèi)存訪問來說，這種集群頁表非常有效使用的算法5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁表

通常，每個進(jìn)程都有與之相關(guān)的頁表，進(jìn)程正在使用的每個頁面在頁表中都有一個表項。進(jìn)程根據(jù)頁面的虛擬地址對其進(jìn)行訪問，因此這種表示方法是很自然的。但是這種方法也有其缺點，即每個頁表都含有上百萬個表項，僅僅為了記錄內(nèi)存的使用情況就消耗了大量物理內(nèi)存。

為了解決這個問題，我們可以使用反置頁表。因此，整個系統(tǒng)中只存在一個頁表，并且每個頁框?qū)?yīng)其中一個表項。由于一方面系統(tǒng)中只有一個頁表，而另一方面系統(tǒng)中又存在著多個映射著物理內(nèi)存的地址空間，因此需要在反置頁表中存放地址空間標(biāo)志符。這樣就保證了一個特定進(jìn)程的邏輯頁面可以映射到相應(yīng)的物理頁框上。64位的UltraSPARC和PowerPC都是使用反置頁表的實例

盡管這種方法減少了為存放每個頁表所使用的內(nèi)存數(shù)量，但卻增加了內(nèi)存訪問時的查表時間。由于反置頁表是按照物理地址排序的，而在使用時卻是按照虛擬地址查找，因此有可能為了尋找相匹配的表項而遍歷全表反置頁表：每個物理頁框?qū)?yīng)一個表項。每個表項包含與該頁框相對應(yīng)的虛擬頁面地址，以及擁有該頁面進(jìn)程的信息案例5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁表整個系統(tǒng)中只存在一個頁表，并且每個頁框?qū)?yīng)其中一個表項保證了一個特定進(jìn)程的邏輯頁面可以映射到相應(yīng)的物理頁框上增加了內(nèi)存訪問時的查表時間。由于反置頁表是按照物理地址排序的，而在使用時卻是按照虛擬地址查找，因此有可能為了尋找相匹配的表項而遍歷全表優(yōu)點缺點反置頁表：每個物理頁框?qū)?yīng)一個表項。每個表項包含與該頁框相對應(yīng)的虛擬頁面地址，以及擁有該頁面進(jìn)程的信息5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I轉(zhuǎn)換檢測緩沖區(qū)(TLB)提高存取速度，有兩種方法圖5-18帶有TLB的頁式存儲管理地址映射過程一種是在地址映射機(jī)制中增加一組高速寄存器保存頁表，這需要大量的硬件開銷，在經(jīng)濟(jì)上不可行另一種方法是在地址映射機(jī)制中增加一個小容量的聯(lián)想寄存器（相聯(lián)存儲器），它由高速緩沖存儲器組成5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I轉(zhuǎn)換檢測緩沖區(qū)(TLB)TLB內(nèi)容的更新原理如下：

當(dāng)某一用戶程序需要存取數(shù)據(jù)時，根據(jù)該數(shù)據(jù)所在的邏輯頁號在TLB中找出對應(yīng)的物理頁面號，然后拼接頁內(nèi)地址，以形成物理地址；如果在TLB中沒有相應(yīng)的邏輯頁號，則地址映射仍然通過內(nèi)存中的頁表進(jìn)行；在得到物理頁面號后需將該頁框號填到TLB的空閑單元中；若TLB中沒有空閑單元，則根據(jù)淘汰算法淘汰某一行，再填入新得到的頁框號

實際上，查找TLB和查找內(nèi)存頁表是并行進(jìn)行的，一旦發(fā)現(xiàn)TLB中有與所查頁號一致的邏輯頁號就停止查找內(nèi)存頁表，而直接利用TLB中的邏輯頁號

假定訪問內(nèi)存的時間為200毫微秒，訪問高速緩沖存儲器的時間為40毫微秒，高速緩沖存儲器為16個單元時，查TLB的命中率為90％。于是，按虛擬地址轉(zhuǎn)換成絕對地址進(jìn)行存取的平均訪問時間為（200＋40）×90％＋（200＋200）×10％＝256（毫微秒）不使用TLB需兩次訪問內(nèi)存的時間：200×2＝400毫微秒?？梢娛褂肨LB與不使用TLB相比，訪問時間下降了36％案例5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I缺頁異常處理

當(dāng)發(fā)生缺頁異常時，操作系統(tǒng)必須在內(nèi)存中尋找一個新的物理頁面（頁框）來進(jìn)行分配，若沒有空閑的頁框，則選擇一個裝有信息的物理頁面將其信息移出內(nèi)存，以便為即將調(diào)入的頁面讓出空間圖5-19缺頁異常處理流程圖

如果要移走的頁面在內(nèi)存期間已經(jīng)被修改過，就必須把它寫回磁盤以更新該頁在磁盤上的副本。如果該頁沒有被修改過，那么它在磁盤上的副本仍然是有效的，則不需要寫回，調(diào)入的頁面直接覆蓋被淘汰的頁面圖5-19缺頁異常處理流程圖5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I缺頁異常處理①根據(jù)執(zhí)行指令中的邏輯地址查頁表的有效位，判斷該頁是否在內(nèi)存②該頁標(biāo)志為“0”，形成缺頁異常。保留現(xiàn)場。中斷裝置通過交換PSW讓操作系統(tǒng)的缺頁中斷處理程序占用處理器③操作系統(tǒng)處理缺頁異常，尋找一個空閑的物理頁面④若有空閑頁，則把磁盤上讀出的信息裝入該頁面中⑤修改頁表及內(nèi)存分配表，表示該頁已在內(nèi)存⑥如果內(nèi)存中無空閑頁，則按某種算法選擇一個已在內(nèi)存的頁面，把它暫時調(diào)出內(nèi)存。若在執(zhí)行中該頁面已被修改過，則要把該頁信息重新寫回到磁盤上（否則不必重新寫回磁盤）。當(dāng)一頁被暫時調(diào)出內(nèi)存后，讓出的內(nèi)存空間用來存放當(dāng)前需要使用的頁面。頁面被調(diào)出或裝入之后都要對頁表及內(nèi)存分配表作修改⑦恢復(fù)現(xiàn)場，重新執(zhí)行被中斷的指令。當(dāng)重新執(zhí)行該指令時，由于要訪問的頁面已被裝入內(nèi)存，所以可正常執(zhí)行下去整個缺頁處理過程如下5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁面調(diào)度策略頁面調(diào)度策略調(diào)入策略置頁策略置換策略虛擬存儲器的調(diào)入策略決定了什么時候?qū)⒁粋€頁面由外存調(diào)入內(nèi)存之中當(dāng)線程產(chǎn)生缺頁時，內(nèi)存管理器還必須確定將調(diào)入的虛擬頁放在物理內(nèi)存的何處。用于確定最佳位置的一組規(guī)則稱為“置頁策略”。選擇頁框應(yīng)使CPU、內(nèi)存和高速緩存不必要的震蕩最小，因此WindowsServer2003需要考慮CPU內(nèi)存高速緩存的大小如果缺頁發(fā)生時物理內(nèi)存已滿，“置換策略”被用于確定哪個物理頁面必須從內(nèi)存中移出為新的頁面騰出空位。在虛擬頁式存儲管理方案中，存在有兩種頁面分配策略，即固定和可變分配策略5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁面調(diào)度策略調(diào)入策略請求調(diào)頁預(yù)調(diào)頁只調(diào)入發(fā)生缺頁時所需的頁面。這種調(diào)入策略實現(xiàn)簡單，但容易產(chǎn)生較多的缺頁異常，造成對外存I/O次數(shù)多，時間開銷過大，容易產(chǎn)生顛簸現(xiàn)象在發(fā)生缺頁需要調(diào)入某頁時，一次調(diào)入該頁以及相鄰的幾個頁。這種策略提高了調(diào)頁的I/O效率，減少了I/O次數(shù)。但由于這是一種基于局部性原理的預(yù)測，若調(diào)入的頁在以后很少被訪問，則造成浪費(fèi)。這種方式常在程序裝入時使用

虛擬存儲器的調(diào)入策略決定了什么時候?qū)⒁粋€頁面由外存調(diào)入內(nèi)存之中。在虛擬頁式管理中有兩種常用調(diào)入策略5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁面調(diào)度策略置換策略固定分配局部置換

可變分配全局置換

可變分配局部置換

根據(jù)進(jìn)程的類型，為每一進(jìn)程分配固定的頁數(shù)的內(nèi)存空間，在整個運(yùn)行期間都不再改變。采用該策略時，如果進(jìn)程在運(yùn)行中出現(xiàn)缺頁，則只能從分配給該進(jìn)程的頁面中選出一個換出，然后再調(diào)入一頁，以保證分配給該進(jìn)程的內(nèi)存空間總數(shù)不變采用這種策略時，先為系統(tǒng)中的每一進(jìn)程分配一定數(shù)量的內(nèi)存空間，操作系統(tǒng)本身也保持一個空閑物理頁面的隊列。當(dāng)某進(jìn)程發(fā)生缺頁時，由系統(tǒng)的空閑物理頁面隊列中取出物理頁面分配給該進(jìn)程。但當(dāng)空閑物理頁面隊列中的物理頁面用完時，操作系統(tǒng)才從所有內(nèi)存中按規(guī)定的置換算法選擇一頁調(diào)出。該頁可能是系統(tǒng)中任意一個進(jìn)程的頁同樣基于進(jìn)程的類型，為每一進(jìn)程分配一定數(shù)目的內(nèi)存空間。但當(dāng)某進(jìn)程發(fā)生缺頁時，只允許從分配給該進(jìn)程的頁面中選出一頁換出，這樣就不影響其他進(jìn)程的運(yùn)行。如果進(jìn)程在運(yùn)行的過程中，頻繁的發(fā)生缺頁，則系統(tǒng)再為該進(jìn)程增加分配若干物理頁面，直到進(jìn)程的缺頁率降低到適當(dāng)程度為止

如果缺頁發(fā)生時物理內(nèi)存已滿，“置換策略”被用于確定哪個物理頁面必須從內(nèi)存中移出為新的頁面騰出空位。在虛擬頁式存儲管理方案中，存在有兩種頁面分配策略，即固定和可變分配策略5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁面置換算法

每次發(fā)生缺頁時，當(dāng)然可以隨機(jī)選擇一個頁面置換。但是如果一個經(jīng)常使用的頁被置換出去，很有可能它很快又要被調(diào)入內(nèi)存，帶來不必要的額外開銷。所以選擇不常使用的頁面會使系統(tǒng)性能好得多

頁面置換算法的優(yōu)劣將會影響虛擬存儲系統(tǒng)的性能，進(jìn)而影響整個系統(tǒng)的性能。下面將介紹幾個主要的頁面置換算法

如果剛被調(diào)出的頁面又立即要用，因而又要把它裝入，而裝入不久又被選中調(diào)出，調(diào)出不久又被裝入，如此反復(fù)，使調(diào)度非常頻繁。這種現(xiàn)象稱為“抖動”或稱“顛簸”該算法淘汰以后不再需要的，或者在最長時間以后才會用到的頁面。