1、第1章 存儲(chǔ)器管理4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器應(yīng)容量大,便宜,速度跟上處理器4.1.1 多級(jí)存儲(chǔ)器結(jié)構(gòu)通常有三層，細(xì)分為六層，如圖4-1，越往上，速度越快，容量越小，價(jià)格越貴。寄存器和主存又稱可執(zhí)行存儲(chǔ)器，進(jìn)程可直接用指令訪問(wèn)，輔存只能用I/O訪問(wèn)。4.1.2 主存儲(chǔ)器與寄存器 1.主存儲(chǔ)器-內(nèi)存，保存進(jìn)程運(yùn)行時(shí)的程序和數(shù)據(jù)。CPU與外圍設(shè)備交換的信息一般也依托于主存儲(chǔ)器地址空間。為緩和訪存速度遠(yuǎn)低于CPU執(zhí)行指令的速度，在計(jì)算機(jī)系統(tǒng)中引入了寄存器和高速緩存。2.寄存器-與CPU協(xié)調(diào)工作，用于加速存儲(chǔ)器的訪問(wèn)速度，如用寄存器存放操作數(shù)，或用地址寄存器加快地址轉(zhuǎn)換速度等。4.1.3 高速緩存和

2、磁盤(pán)緩存 1.高速緩存-根據(jù)程序執(zhí)行的局部性原理將主存中一些經(jīng)常訪問(wèn)的信息(程序、數(shù)據(jù)、指令等)存放在高速緩存中，減少訪問(wèn)主存儲(chǔ)器的次數(shù)，可大幅度提高程序執(zhí)行速度。2.磁盤(pán)緩存-將頻繁使用的一部分磁盤(pán)數(shù)據(jù)和信息，暫時(shí)存放在磁盤(pán)緩存中，可減少訪問(wèn)磁盤(pán)的次數(shù)。它依托于固定磁盤(pán)，提供對(duì)主存儲(chǔ)器存儲(chǔ)空間的擴(kuò)充，即利用主存中的存儲(chǔ)空間，來(lái)暫存從磁盤(pán)中讀/寫(xiě)入的信息。4.2 程序的裝入和鏈接多道程序運(yùn)行，需先創(chuàng)建進(jìn)程。而創(chuàng)建進(jìn)程第一步是將程序和數(shù)據(jù)裝入內(nèi)存。將源程序變?yōu)榭稍趦?nèi)存中執(zhí)行的程序，通常都要經(jīng)過(guò)以下幾個(gè)步驟：編譯-若干個(gè)目標(biāo)模塊；鏈接-鏈接目標(biāo)模塊和庫(kù)函數(shù)，形成裝入模塊；裝入-將裝入模塊裝入內(nèi)存。

3、圖 4-2 對(duì)用戶程序的處理步驟4.2.1 程序的裝入無(wú)需連接的單目標(biāo)模塊裝入（理解裝入方式）1. 絕對(duì)裝入方式(Absolute Loading Mode) -只適用單道程序環(huán)境如果知道程序的內(nèi)存位置，編譯將產(chǎn)生絕對(duì)地址的目標(biāo)代碼，按照絕對(duì)地址將程序和數(shù)據(jù)裝入內(nèi)存。由于程序的邏輯地址與實(shí)際內(nèi)存地址完全相同，故不須對(duì)程序和數(shù)據(jù)的地址進(jìn)行修改。絕對(duì)地址：可在編譯時(shí)給出或由程序員直接賦予。若由程序員直接給出，不利于程序或數(shù)據(jù)修改，因此，通常是在程序中采用符號(hào)地址，然后在編譯或匯編時(shí)轉(zhuǎn)換為絕對(duì)地址。2. 可重定位裝入方式(Relocation Loading Mode) -適于多道程序環(huán)境多道程序環(huán)

4、境下，編譯程序不能預(yù)知目標(biāo)模塊在內(nèi)存的位置。目標(biāo)模塊的起始地址是0，其它地址也都是相對(duì)于0計(jì)算的。此時(shí)應(yīng)采用可重定位裝入方式，根據(jù)內(nèi)存情況，將模塊裝入到內(nèi)存的適當(dāng)位置，如圖4-3 作業(yè)裝入內(nèi)存時(shí)的情況 。3. 動(dòng)態(tài)運(yùn)行時(shí)裝入方式(Dynamic Run-time Loading) -適于多道程序環(huán)境可重定位裝入方式并不允許程序運(yùn)行時(shí)在內(nèi)存中移動(dòng)位置。但是，在運(yùn)行過(guò)程中它在內(nèi)存中的位置可能經(jīng)常要改變，此時(shí)就應(yīng)采用動(dòng)態(tài)運(yùn)行時(shí)裝入方式。動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序真正執(zhí)行時(shí)才進(jìn)行。因此，裝入內(nèi)存后的所有地址都

5、仍是相對(duì)地址。問(wèn)題：程序裝入內(nèi)存后修改地址的時(shí)機(jī)是什么？4.3 連續(xù)分配方式4.3.3 動(dòng)態(tài)分區(qū)分配根據(jù)進(jìn)程需要?jiǎng)討B(tài)分配內(nèi)存1. 分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu) (1) 空閑分區(qū)表用若干表目記錄每個(gè)空閑分區(qū)的分區(qū)序號(hào)、分區(qū)始址及分區(qū)的大小等數(shù)據(jù)項(xiàng)。(2) 空閑分區(qū)鏈-為實(shí)現(xiàn)對(duì)空閑分區(qū)的分配和鏈接，在每分區(qū)起始部分，設(shè)置前向指針，尾部則設(shè)置一后向指針。為檢索方便，在分區(qū)前、后向指針中，重復(fù)設(shè)置狀態(tài)位和分區(qū)大小表目。當(dāng)分區(qū)被分配后，把狀態(tài)位由“0”改為“1”時(shí)，前、后向指針失去意義。圖 4-5 空閑鏈結(jié)構(gòu)2. 分區(qū)分配算法（P123）1）首次適應(yīng)算法(first-fit)空閑分區(qū)鏈以地址遞增次序鏈接每次按分

6、區(qū)鏈的次序從頭查找，找到符合要求的第一個(gè)分區(qū)。2) 循環(huán)首次適應(yīng)算法FF算法的變種從上次找到的空閑分區(qū)位置開(kāi)始循環(huán)查找，找到后，修改起始查找指針。3) 最佳適應(yīng)算法空閑分區(qū)按容量從小到大排序把能滿足要求的、最小的空閑分區(qū)分配給作業(yè)4) 最壞適應(yīng)算法空閑分區(qū)按容量從大到小排序挑選最大的空閑區(qū)分給作業(yè)使用；5) 快速適應(yīng)算法根據(jù)容量大小設(shè)立多個(gè)空閑分區(qū)鏈表3. 分區(qū)分配操作1.分配內(nèi)存請(qǐng)求分區(qū)u.size; 空閑分區(qū)m.size; m.size-u.sizesize，說(shuō)明多余部分太小, 不再切割，將整個(gè)分區(qū)分配給請(qǐng)求者；否則從該分區(qū)中劃分一塊請(qǐng)求大小的內(nèi)存空間，余下部分仍留在空閑分區(qū)鏈。如圖4-6

7、 內(nèi)存分配流程。2.回收內(nèi)存(1) 回收區(qū)與插入點(diǎn)的前一空閑分區(qū)F1相鄰：合并，修改F1大小。(2) 回收區(qū)與后一空閑分區(qū)F2相鄰：合并，修改首地址和大小。 (3) 回收區(qū)同時(shí)與前、后兩個(gè)分區(qū)鄰接：合并，修改F1大小，取消F2。(4) 回收區(qū)不鄰接：新建表項(xiàng)，填寫(xiě)首地址和大小，并插入鏈表。如圖 圖 4-6 內(nèi)存分配流程4.3.6 可重定位分區(qū)分配1 動(dòng)態(tài)重定位的引入例：在內(nèi)存中有四個(gè)互不鄰接的小分區(qū)，容量分別為10KB、30KB、14KB和26KB。若現(xiàn)有一作業(yè)要獲得40KB的內(nèi)存空間，因連續(xù)空間不足作業(yè)無(wú)法裝入。可采用的一種解決方法是：通過(guò)移動(dòng)內(nèi)存中作業(yè)的位置，以把原來(lái)多個(gè)分散的小分區(qū)拼接成

8、一個(gè)大分區(qū)的方法，稱為“拼接”或“緊湊。由于用戶程序在內(nèi)存中位置的變化，在每次“緊湊”后，都必須對(duì)移動(dòng)了的程序或數(shù)據(jù)進(jìn)行重定位。圖 4-8 緊湊的示意4.3.7 對(duì)換（即中級(jí)調(diào)度）1. 對(duì)換(Swapping)的引入“活動(dòng)阻塞”進(jìn)程占用內(nèi)存空間；外存上的就緒作業(yè)不能進(jìn)入內(nèi)存運(yùn)行。所謂“對(duì)換”，是指把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠的內(nèi)存空間；再把已具備運(yùn)行條件的進(jìn)程或所需要的程序和數(shù)據(jù)，調(diào)入內(nèi)存。對(duì)換是提高內(nèi)存利用率的有效措施。根據(jù)對(duì)換單位可分為：進(jìn)程對(duì)換、頁(yè)面對(duì)換和分段對(duì)換。為了能實(shí)現(xiàn)對(duì)換，系統(tǒng)應(yīng)具備以下三方面功能：對(duì)換空間的管理、進(jìn)程的換出與換入

9、 2. 進(jìn)程的換出與換入(1)進(jìn)程的換出選擇阻塞且優(yōu)先級(jí)最低的進(jìn)程，將它的程序和數(shù)據(jù)傳送到磁盤(pán)對(duì)換區(qū)上。回收該進(jìn)程所占用的內(nèi)存空間，并對(duì)該進(jìn)程的進(jìn)程控制塊做相應(yīng)的修改。 (2)進(jìn)程的換入找出“就緒” 但已換出到磁盤(pán)上時(shí)間最久的進(jìn)程作為換入進(jìn)程，將之換入，直至已無(wú)可換入的進(jìn)程。4.4 基本分頁(yè)存儲(chǔ)管理方式前面的連續(xù)分配方案會(huì)形成許多“碎片”，“緊湊”方法可以解決碎片但開(kāi)銷大。是否允許進(jìn)程離散裝入？離散單位不同，稱分頁(yè)式存儲(chǔ)和分段式存儲(chǔ)。不具備對(duì)換功能稱為“基本分頁(yè)式”，支持虛擬存儲(chǔ)器功能稱為“請(qǐng)求基本分頁(yè)式”。4.4.1 頁(yè)面與頁(yè)表1. 頁(yè)面1) 頁(yè)面和物理塊-將進(jìn)程的邏輯地址空間分成若干個(gè)大小

10、相等的片，稱為頁(yè)面，并為各頁(yè)編號(hào)。相應(yīng)地把內(nèi)存空間分成與頁(yè)面相同大小的若干個(gè)存儲(chǔ)塊，稱為物理塊，也同樣編號(hào)。分配時(shí)，將進(jìn)程中的頁(yè)裝入到物理塊中，最后一頁(yè)經(jīng)常裝不滿一塊而形成 “頁(yè)內(nèi)碎片”。 2) 頁(yè)面大小-頁(yè)面的大小應(yīng)選擇適中。頁(yè)面太小，內(nèi)存碎片減小，利用率高；但頁(yè)表過(guò)長(zhǎng)，占大量?jī)?nèi)存。頁(yè)面較大，頁(yè)表長(zhǎng)度小；但頁(yè)內(nèi)碎片大。因此，頁(yè)面的大小應(yīng)選擇得適中，且頁(yè)面大小應(yīng)是2的冪，通常為512 B8 KB。2. 地址結(jié)構(gòu) 分頁(yè)地址中的地址結(jié)構(gòu)如下： 31 12 11 0頁(yè)號(hào)P位移量W 它含有兩部分：頁(yè)號(hào)P(1231位,最多有1M頁(yè))和頁(yè)內(nèi)位移量W(011位,每頁(yè)的大小4KB) ；對(duì)某特定機(jī)器，其地址結(jié)構(gòu)

11、是一定的。若給定一個(gè)邏輯地址空間中的地址為A，頁(yè)面的大小為L(zhǎng)，則頁(yè)號(hào)P和頁(yè)內(nèi)地址d可按下式求得：3. 頁(yè)表-實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射 4.4.2 地址變換機(jī)構(gòu)任務(wù)：將邏輯地址轉(zhuǎn)換為物理地址；頁(yè)內(nèi)地址變換:因頁(yè)內(nèi)地址與物理地址一一對(duì)應(yīng), 可直接轉(zhuǎn)換；頁(yè)號(hào)變換：頁(yè)表可實(shí)現(xiàn)從邏輯地址中頁(yè)號(hào)到內(nèi)存中物理塊號(hào)的變換；1基本的地址變換機(jī)構(gòu)a. 頁(yè)表功能可由一組專門(mén)的寄存器實(shí)現(xiàn)(原理)； b. 頁(yè)表大多駐留內(nèi)存，系統(tǒng)中只設(shè)置一頁(yè)表寄存器來(lái)存放頁(yè)表在內(nèi)存的始址和頁(yè)表長(zhǎng)度(實(shí)際操作)； c. 進(jìn)程未執(zhí)行時(shí)，頁(yè)表始址和長(zhǎng)度存放在PCB中。執(zhí)行時(shí)才將這兩個(gè)數(shù)據(jù)裝入頁(yè)表寄存器中(過(guò)程)。圖 4-12 分頁(yè)系統(tǒng)的

12、地址變換機(jī)構(gòu)2. 具有快表的地址變換機(jī)構(gòu) a. 僅用頁(yè)表寄存器時(shí)，CPU每存取一數(shù)據(jù)要兩次訪問(wèn)內(nèi)存(頁(yè)表-地址變換-數(shù)據(jù))；b. 為提高地址變換速度，可在地址變換機(jī)構(gòu)中增設(shè)一具有并行查尋能力的特殊高速緩沖寄存器用以存放當(dāng)前訪問(wèn)的那些頁(yè)表項(xiàng)，稱為“快表”。 c. -在CPU給出邏輯地址，將頁(yè)號(hào)P送入快表 -頁(yè)號(hào)匹配，讀物理塊號(hào)后送物理地址寄存器 -無(wú)匹配頁(yè)號(hào)，再訪問(wèn)內(nèi)存中頁(yè)表，把從頁(yè)表項(xiàng)中讀出的物理塊號(hào)送地址寄存器；同時(shí)，再將此頁(yè)表項(xiàng)存入到快表中。 -如快表已滿，則OS須找到一換出頁(yè)表項(xiàng)換出。為什么增加“快表”？為了提高地址變換速度，可在地址變換機(jī)構(gòu)中增設(shè)一個(gè)具有并行查尋能力的特殊高速緩沖寄存器

13、，又稱為“聯(lián)想寄存器”(Associative Memory)，或稱為“快表“快表”有何缺點(diǎn)？圖 4-13 具有快表的地址變換機(jī)構(gòu)4.5 基本分段存儲(chǔ)管理方式4.5.1 分段存儲(chǔ)管理方式的引入（為什么引入）推動(dòng)內(nèi)存從固定分配到動(dòng)態(tài)分配直到分頁(yè)存儲(chǔ)，主要?jiǎng)恿κ莾?nèi)存利用率，而引入分段存儲(chǔ)管理方式，主要是為了滿足用戶和程序員的下述一系列需要：1)方便編程-把作業(yè)按邏輯關(guān)系劃分為若干段，每段有自己的名字和長(zhǎng)度，并從0開(kāi)始編址。LOAD 1,A|; STORE 1,B|2) 信息共享-段是信息的邏輯單位。為實(shí)現(xiàn)共享，存儲(chǔ)管理應(yīng)與用戶程序分段的組織方式相適應(yīng)。 3) 信息保護(hù)-對(duì)信息的邏輯單位進(jìn)行保護(hù)，應(yīng)

14、分段管理。4) 動(dòng)態(tài)增長(zhǎng)-分段存儲(chǔ)能解決數(shù)據(jù)段使用過(guò)程中動(dòng)態(tài)增長(zhǎng)。 5) 動(dòng)態(tài)鏈接-運(yùn)行過(guò)程中動(dòng)態(tài)調(diào)入以段為單位的目標(biāo)程序。4.5.2 分段系統(tǒng)的基本原理 1. 分段作業(yè)劃分為若干段，如圖4-16，每個(gè)段用段號(hào)來(lái)代替段名，地址空間連續(xù)。段的長(zhǎng)度由邏輯信息長(zhǎng)度決定，因而各段長(zhǎng)度不等。其邏輯地址由段號(hào)(段名)和段內(nèi)地址所組成，結(jié)構(gòu)如下： 31 16 15 0段號(hào)段內(nèi)地址該地址結(jié)構(gòu)中，允許一個(gè)作業(yè)最多有64K個(gè)段，每個(gè)段的最大長(zhǎng)度為64KB。編譯程序能自動(dòng)根據(jù)源程序產(chǎn)生若干個(gè)段。2. 段表每個(gè)段一個(gè)連續(xù)分區(qū)，各段可以離散存入不同分區(qū)。為每個(gè)進(jìn)程建立一張段映射表(段表),其中每段占一個(gè)表項(xiàng)，記錄該段在

15、內(nèi)存中的始址(又稱為“基址”)和段長(zhǎng)度。常將段表放在內(nèi)存中。圖 4-16 利用段表實(shí)現(xiàn)地址映射 3. 分頁(yè)和分段的主要區(qū)別(1) 頁(yè)是信息的物理單位，分頁(yè)是為提高內(nèi)存的利用率，是為滿足系統(tǒng)管理的需要。段則是信息的邏輯單位，分段是為了能更好地滿足用戶的需要。 (2) 頁(yè)的大小固定且分頁(yè)由系統(tǒng)硬件實(shí)現(xiàn)；而段的長(zhǎng)度不固定，通常由編譯程序根據(jù)信息的性質(zhì)來(lái)劃分。(3) 分頁(yè)的作業(yè)地址空間是一維的，程序只需一個(gè)地址記憶符；而分段的作業(yè)地址空間是二維的，程序員既需給出段名，又需給出段內(nèi)地址。4.5.3 信息共享可重入代碼(純代碼):允許多個(gè)進(jìn)程同時(shí)訪問(wèn)的代碼。絕對(duì)不允許可重入代碼在執(zhí)行中改變,因此，不允許任

16、何進(jìn)程修改它。4.5.4 段頁(yè)式存儲(chǔ)管理方式1. 基本原理-將分段(滿足用戶需求)和分頁(yè)(內(nèi)存利用率高)結(jié)合，先將用戶程序分成若干個(gè)段，再把每個(gè)段分成若干個(gè)頁(yè),圖4-20給出作業(yè)地址空間結(jié)構(gòu) ，作業(yè)有三個(gè)段，頁(yè)面大小4KB。圖 4-20 作業(yè)地址空間和地址結(jié)構(gòu)圖 4-21 利用段表和頁(yè)表實(shí)現(xiàn)地址映射4.6 虛擬存儲(chǔ)器的基本概念前面各種存儲(chǔ)器管理方式共同點(diǎn)：它們要求將一個(gè)作業(yè)全部裝入內(nèi)存后方能運(yùn)行，于是出現(xiàn)了下面這樣兩種情況：(1) 有的作業(yè)很大，其所要求的內(nèi)存空間超過(guò)了內(nèi)存總?cè)萘浚鳂I(yè)不能全部被裝入內(nèi)存，致使該作業(yè)無(wú)法運(yùn)行。(2) 有大量作業(yè)要求運(yùn)行，但由于內(nèi)存容量不足以容納所有這些作業(yè)，只能

17、將少數(shù)作業(yè) 裝入內(nèi)存讓它們先運(yùn)行，而將其它大量的作業(yè)留在外存上等待。4.5.1 虛擬存儲(chǔ)器的引入1. 常規(guī)存儲(chǔ)器管理方式的特征(1) 一次性。將作業(yè)全部裝入內(nèi)存后方能運(yùn)行，此外有許多作業(yè)在每次運(yùn)行時(shí)，并非其全部程序和數(shù)據(jù)都要用到。一次性裝入，造成了對(duì)內(nèi)存空間的浪費(fèi)。(2) 駐留性。作業(yè)裝入內(nèi)存后一直駐留，直至運(yùn)行結(jié)束。盡管因故等待或很少運(yùn)行，都仍將繼續(xù)占用寶貴的內(nèi)存資源。現(xiàn)在要研究的問(wèn)題是：一次性及駐留性在程序運(yùn)行時(shí)是否必需。2. 局部性原理早在1968年， Denning.P就曾指出： (1) 程序執(zhí)行時(shí)，除了少部分的轉(zhuǎn)移和過(guò)程調(diào)用指令外，在大多數(shù)情況下仍是順序執(zhí)行的。(2) 過(guò)程調(diào)用將會(huì)使

18、程序的執(zhí)行軌跡由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域，但經(jīng)研究看出，過(guò)程調(diào)用的深度在大多數(shù)情況下都不超過(guò)5。(3) 程序中存在許多循環(huán)結(jié)構(gòu)，這些雖然只由少數(shù)指令構(gòu)成， 但是它們將多次執(zhí)行。(4) 程序中還包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理， 如對(duì)數(shù)組進(jìn)行操作，它們往往都局限于很小的范圍內(nèi)。局限性主要表現(xiàn)在下述兩個(gè)方面：(1) 時(shí)間局限性由于循環(huán)操作的存在。如果程序中的指令或數(shù)據(jù)一旦執(zhí)行，則不久以后可能再次訪問(wèn)。(2) 空間局限性由于程序的順序執(zhí)行。程序在一段時(shí)間內(nèi)所訪問(wèn)的地址，可能集中在一定的范圍之內(nèi)。3. 虛擬存儲(chǔ)器定義 -基于局部性原理程序運(yùn)行前，僅須將要運(yùn)行的少數(shù)頁(yè)面或段裝入內(nèi)存便可啟動(dòng)，運(yùn)行時(shí)，如果需要訪

19、問(wèn)的頁(yè)(段)尚未調(diào)入內(nèi)存(缺頁(yè)或缺段)，用OS提供請(qǐng)求調(diào)頁(yè)(段)功能調(diào)入。如果此時(shí)內(nèi)存已滿，則還須再利用頁(yè)(段)的置換功能，將內(nèi)存中暫時(shí)不用的頁(yè)(段)調(diào)至外存，騰出足夠的內(nèi)存空間后，再將要訪問(wèn)的頁(yè)(段)調(diào)入。所謂虛擬存儲(chǔ)器，是指具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上擴(kuò)充內(nèi)存容量的一種存儲(chǔ)器系統(tǒng)。其邏輯容量由內(nèi)存容量和外存容量之和所決定，其運(yùn)行速度接近于內(nèi)存，成本接近于外存。4.6.3 虛擬存儲(chǔ)器的特征1) 多次性-一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行，最初裝入部分程序和數(shù)據(jù)，運(yùn)行中需要時(shí)，再將其它部分調(diào)入。 2) 對(duì)換性-允許在作業(yè)的運(yùn)行過(guò)程中進(jìn)行換進(jìn)、換出。換進(jìn)和換出能有效地提高內(nèi)存利用率。3)

20、虛擬性-從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到遠(yuǎn)大于實(shí)際內(nèi)存容量。這是虛擬存儲(chǔ)器最重要的特征和最重要的目標(biāo)。4) 離散性-是以上三個(gè)特性的基礎(chǔ)，在內(nèi)存分配時(shí)采用離散分配的方式。備注：虛擬性是以多次性和對(duì)換性為基礎(chǔ)的，而多次性和對(duì)換性又必須建立在離散分配的基礎(chǔ)上。4.7 請(qǐng)求分頁(yè)存儲(chǔ)管理方式 4.6.1 請(qǐng)求分頁(yè)中的硬件支持-頁(yè)表、缺頁(yè)中斷和地址變換請(qǐng)求分頁(yè)系統(tǒng)是在分頁(yè)的基礎(chǔ)上，增加了“請(qǐng)求調(diào)頁(yè)”和“頁(yè)面置換”功能，每次調(diào)入和換出基本單位都是長(zhǎng)度固定的頁(yè)，實(shí)現(xiàn)比請(qǐng)求分段簡(jiǎn)單。1頁(yè)表機(jī)制-將用戶地址空間中的邏輯地址變換為內(nèi)存空間中的物理地址，因只將部分調(diào)入內(nèi)存，需增設(shè)若干項(xiàng)。在請(qǐng)求分頁(yè)系統(tǒng)中的每個(gè)頁(yè)表

21、項(xiàng)如下所示：頁(yè)號(hào) 物理塊號(hào) 狀態(tài)位P 訪問(wèn)字段A 修改位M外存地址 (1) 狀態(tài)位P：該頁(yè)是否已調(diào)入內(nèi)存，供訪問(wèn)時(shí)參考。(2) 訪問(wèn)字段A：記錄一段時(shí)間內(nèi)本頁(yè)被訪問(wèn)的頻率，供選擇換出頁(yè)時(shí)參考。(3) 修改位M：頁(yè)在調(diào)入內(nèi)存后是否被修改過(guò)，供置換頁(yè)面時(shí)參考。(4) 外存地址：指出該頁(yè)在外存上的地址，即物理塊號(hào)，供調(diào)入該頁(yè)時(shí)參考。4.7.2 內(nèi)存分配策略和分配算法1. 最小物理塊數(shù)的確定（*）是指能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)，當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將無(wú)法運(yùn)行。進(jìn)程應(yīng)獲得的最少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)。對(duì)于某些簡(jiǎn)單的機(jī)器，所需的最少物理塊數(shù)為2，分別用于存放指令和數(shù)

22、據(jù)，間接尋址時(shí)至少要有三塊。對(duì)于某些功能較強(qiáng)的機(jī)器，因其指令本身、源地址和目標(biāo)地址都可能跨兩個(gè)頁(yè)面，至少要為每個(gè)進(jìn)程分配6個(gè)物理塊，以裝入這些頁(yè)面。2. 物理塊的分配策略 請(qǐng)求分頁(yè)系統(tǒng)的兩種內(nèi)存分配策略：即固定和可變分配策略；兩種置換策略：即全局置換和局部置換。可組合出以下三種策略。1) 固定分配局部置換(Fixed Allocation, Local Replacement)-每進(jìn)程分配一定數(shù)目的物理塊，在整個(gè)運(yùn)行期間都不再改變，換入換出都限于這些物理塊。每個(gè)進(jìn)程物理塊難以確定，太多太少都不好2) 可變分配全局置換(Variable Allocation, Global Replacemen

23、t) -每進(jìn)程分配一定數(shù)目的物理塊，OS保持一空閑物理塊隊(duì)列。進(jìn)程缺頁(yè)時(shí)，摘下一空閑塊，并將該頁(yè)裝入。3) 可變分配局部置換(Variable Allocation, Local Replacemen)每進(jìn)程分配一定數(shù)目的物理塊。進(jìn)程缺頁(yè)時(shí)，只允許從該進(jìn)程內(nèi)存頁(yè)中選出一頁(yè)換出。若缺頁(yè)中斷頻繁，再為該進(jìn)程分配若干物理塊，直至缺頁(yè)率減少；若缺頁(yè)率特低，則減少該進(jìn)程的物理塊數(shù)，應(yīng)保證缺頁(yè)率無(wú)明顯增加。3. 物理塊分配算法1) 平均分配算法將所有可供分配的物理塊，平均分配給各個(gè)進(jìn)程。 例如，有100個(gè)物理塊，5個(gè)進(jìn)程，每進(jìn)程可分20個(gè)物理塊。未考慮到各進(jìn)程本身的大小。 2) 按比例分配算法根據(jù)進(jìn)程的大

24、小按比例分配物理塊。共n個(gè)進(jìn)程，每進(jìn)程頁(yè)面數(shù)為si，則頁(yè)面數(shù)的總和為：設(shè)可用的物理塊為m，每進(jìn)程分到的物理塊數(shù)為bi，有：3) 考慮優(yōu)先權(quán)的分配算法為了照顧重要、緊迫的作業(yè)盡快完成，為它分配較多的空間。通常采取：把可供分配的物理塊分成兩部分：一部分按比例分給各進(jìn)程；另一部分根據(jù)優(yōu)先權(quán)分給各進(jìn)程。有的系統(tǒng)是完全按優(yōu)先權(quán)來(lái)分配。4.7.3 調(diào)頁(yè)策略1. 何時(shí)調(diào)入頁(yè)面1) 預(yù)調(diào)頁(yè)策略(缺頁(yè)前) ：頁(yè)面存放連續(xù)，用預(yù)測(cè)法一次調(diào)入多個(gè)相鄰頁(yè)，預(yù)測(cè)成功率僅為50。2) 請(qǐng)求調(diào)頁(yè)策略(缺頁(yè)時(shí))：運(yùn)行中，發(fā)現(xiàn)不在內(nèi)存，立即請(qǐng)求，由OS調(diào)入。2. 從何處調(diào)入頁(yè)面請(qǐng)求分頁(yè)系統(tǒng)中外存分為兩部分：文件區(qū)和對(duì)換區(qū)。這樣

25、，當(dāng)發(fā)生缺頁(yè)請(qǐng)求時(shí)，系統(tǒng)應(yīng)從何處將缺頁(yè)調(diào)入內(nèi)存：(1) 系統(tǒng)擁有足夠的對(duì)換區(qū)，可以全部從對(duì)換區(qū)調(diào)入所需頁(yè)面。在進(jìn)程運(yùn)行前，須將有關(guān)的文件拷貝到對(duì)換區(qū)。(2) 系統(tǒng)缺少足夠的對(duì)換區(qū)，這時(shí)凡是不會(huì)被修改的文件，都直接從文件區(qū)調(diào)入，由于它們未被修改而不必?fù)Q出。但對(duì)于可能被修改的部分，換出時(shí)調(diào)到對(duì)換區(qū)，以后需要時(shí)，再?gòu)膶?duì)換區(qū)調(diào)入。(3) UNIX方式。凡是未運(yùn)行過(guò)的頁(yè)面，都應(yīng)從文件區(qū)調(diào)入；曾運(yùn)行過(guò)但已換出的頁(yè)面，放在對(duì)換區(qū)，下次應(yīng)從對(duì)換區(qū)調(diào)入。4.8 頁(yè)面置換算法當(dāng)進(jìn)程運(yùn)行時(shí)，所訪問(wèn)的頁(yè)面不在內(nèi)存而需要將他們調(diào)入內(nèi)存，但內(nèi)存無(wú)空閑時(shí)，需要選擇一頁(yè)面換出到對(duì)換區(qū)，選擇算法即頁(yè)面置換算法。算法評(píng)價(jià)：頁(yè)面置換頻率低，調(diào)出頁(yè)面將不會(huì)或很少訪問(wèn)。4.8.1 最佳置換算法和先進(jìn)先出置換算法1. 最佳(Optimal)置換算法由Belady于1966年提出的一種理論上的算法。原理：其所選擇的被淘汰頁(yè)面，將是以后永不使用的， 或是在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。特點(diǎn)：通常可獲得最低的缺頁(yè)率，但由于進(jìn)程運(yùn)行不可預(yù)知而無(wú)法實(shí)現(xiàn)，用來(lái)評(píng)價(jià)其他算法。假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的頁(yè)面號(hào)引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1進(jìn)程運(yùn)行時(shí)，先將7，0，1三頁(yè)裝入內(nèi)存。當(dāng)進(jìn)程要訪問(wèn)頁(yè)面2時(shí)，