操作系統(tǒng)教程—Linux實(shí)例分析孟慶昌第4章存儲(chǔ)器管理

1、第4章 存儲(chǔ)器管理 4.1 引言 4.2 基本的內(nèi)存管理技術(shù) 4.3 對(duì)換技術(shù) 4.4 分頁(yè)技術(shù) 4.5 分段技術(shù) 4.6 虛擬存儲(chǔ)器 4.7 請(qǐng)求分頁(yè)技術(shù) 4.8 頁(yè)面置換算法 4.9 內(nèi)存塊分配算法和抖動(dòng)問(wèn)題 4.10 段式虛擬存儲(chǔ)器 4.11 段頁(yè)式結(jié)合系統(tǒng) 4.12 Linux系統(tǒng)的存儲(chǔ)管理 習(xí)題 4.1 引 言 內(nèi)存(Main Memory或Primary Memory或Real Memory)也稱主存， 是指CPU能直接存取指令和數(shù)據(jù)的存儲(chǔ)器。 磁盤、 磁鼓和磁帶等存儲(chǔ)器， 一般稱為外存或輔存（Secondary Storage）。 內(nèi)存是現(xiàn)代計(jì)算機(jī)系統(tǒng)進(jìn)行操作的中心， 如圖4-1

2、所示， CPU和I/O系統(tǒng)都要和內(nèi)存打交道。 圖4-1 內(nèi)存在計(jì)算機(jī)系統(tǒng)中的地位 4.1.1 用戶程序的主要處理階段 我們用高級(jí)語(yǔ)言編程解決某個(gè)特定的任務(wù)時(shí)， 通常先對(duì)它進(jìn)行數(shù)學(xué)抽象， 確定相應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法， 然后用高級(jí)程序設(shè)計(jì)語(yǔ)言（如PASCAL、 C語(yǔ)言等）或者匯編語(yǔ)言進(jìn)行程序設(shè)計(jì)。 這種用高級(jí)語(yǔ)言或匯編語(yǔ)言編寫的程序就稱為源程序。 從用戶的源程序進(jìn)入系統(tǒng)到相應(yīng)程序在機(jī)器上運(yùn)行， 要經(jīng)歷一系列步驟， 主要處理階段有： 編輯、 編譯、 連接、 裝入和運(yùn)行。 如圖4-2所示。圖4-2 用戶程序的主要處理階段 1. 編輯階段 用戶鍵入編輯命令， 如vi， 進(jìn)入編輯方式。 在編輯方式下用戶將所

3、編寫的源程序輸入到機(jī)器內(nèi)， 存放在相應(yīng)的文件（如filel.c）中。 這種存放源程序的文件叫做源文件。 2. 編譯階段 源程序并不能直接在機(jī)器上運(yùn)行， 因?yàn)镃PU不能識(shí)別源程序， 它僅僅認(rèn)識(shí)由規(guī)定范圍內(nèi)的一系列二進(jìn)制代碼所組成的指令和數(shù)據(jù)， 并按預(yù)定含義執(zhí)行一系列動(dòng)作。 3. 連接階段 用戶程序可以分別進(jìn)行編譯， 從而得到不同的目標(biāo)模塊。 而且用戶程序中往往要調(diào)用系統(tǒng)庫(kù)程序和應(yīng)用程序， 這些程序是預(yù)先就編譯好的。 這些目標(biāo)代碼不能簡(jiǎn)單地合并在一起， 因?yàn)楦髯苑峙涞膬?nèi)存地址可能有沖突， 并且調(diào)用者還不知道被調(diào)用模塊放在什么地方， 僅知道它的符號(hào)名稱。 4. 裝入階段 程序必須裝到內(nèi)存才能運(yùn)行。

4、這就需要裝入程序根據(jù)內(nèi)存的使用情況和分配策略， 將上述裝入模塊放入分到的內(nèi)存區(qū)中。 5. 運(yùn)行階段 為了運(yùn)行裝入內(nèi)存中的程序， 需要鍵入運(yùn)行命令。 在UNIX/Linux環(huán)境中， 可直接鍵入可執(zhí)行文件的名稱。 此時(shí)， 終端進(jìn)程創(chuàng)建一個(gè)子進(jìn)程。 當(dāng)這個(gè)進(jìn)程被調(diào)度程序選中后， CPU就去執(zhí)行該進(jìn)程的可執(zhí)行代碼。 就是說(shuō)， 該用戶程序被執(zhí)行了。 4.1.2 重定位 由于內(nèi)存地址是從統(tǒng)一的一個(gè)基址0開(kāi)始按序編號(hào)的， 就像是一個(gè)大數(shù)組那樣， 因此， 內(nèi)存空間是一維的線性空間。 用戶程序和數(shù)據(jù)裝入內(nèi)存時(shí)， 需要進(jìn)行重定位。 例如， 圖4-3表示程序A裝入內(nèi)存前后的情況。 在地址空間100號(hào)單元處有一條指令

5、“LOAD 1， 500”， 它實(shí)現(xiàn)把500號(hào)單元中的數(shù)據(jù)12345裝到寄存器1中去。 圖4-3 程序裝入內(nèi)存時(shí)的情況 1. 靜態(tài)重定位 靜態(tài)重定位是在目標(biāo)程序裝入內(nèi)存時(shí)， 由裝入程序?qū)δ繕?biāo)程序中的指令和數(shù)據(jù)的地址進(jìn)行修改， 即把程序的邏輯地址都改成實(shí)際的內(nèi)存地址。 對(duì)每個(gè)程序來(lái)說(shuō)， 這種地址變換只是在裝入時(shí)一次完成， 在程序運(yùn)行期間不再進(jìn)行重定位。 按照靜態(tài)重定位方式， 圖4-3所示的程序A裝入內(nèi)存時(shí)的情況就變成如圖4-4所示的樣子。圖4-4 靜態(tài)重定位示意圖 它的主要缺點(diǎn)是： （1） 程序的存儲(chǔ)空間只能是連續(xù)的一片區(qū)域， 而且在重定位之后就不能再移動(dòng)。 這不利于內(nèi)存空間的有效使用。 （2）

6、 各個(gè)用戶進(jìn)程很難共享內(nèi)存中的同一程序的副本。 2. 動(dòng)態(tài)重定位 動(dòng)態(tài)重定位是在程序執(zhí)行期間每次訪問(wèn)內(nèi)存之前進(jìn)行重定位。 這種變換是靠硬件地址變換機(jī)構(gòu)實(shí)現(xiàn)的。 通常采用一個(gè)重定位寄存器， 其中放有當(dāng)前正在執(zhí)行的程序在內(nèi)存空間中的起始地址， 而地址空間中的代碼在裝入過(guò)程中不發(fā)生變化。 動(dòng)態(tài)重定位的過(guò)程如圖4-5所示。 圖4-5 動(dòng)態(tài)重定位示意圖 如果用(BR)表示重定位寄存器中的內(nèi)容， 用addr表示操作對(duì)象的相對(duì)地址， 則操作對(duì)象的絕對(duì)地址就是(BR)+addr的值。 動(dòng)態(tài)重定位的主要優(yōu)點(diǎn)是： （1） 程序占用的內(nèi)存空間動(dòng)態(tài)可變， 不必連續(xù)存放在一處。 （2） 比較容易實(shí)現(xiàn)幾個(gè)進(jìn)程對(duì)同一程序副

7、本的共享使用。 4.2 基本的內(nèi)存管理技術(shù) 內(nèi)存的一部分是固定分配給操作系統(tǒng)的， 可以位于內(nèi)存最低端的RAM（隨機(jī)存取存儲(chǔ)器）中， 如圖4-6(a)所示； 也可位于內(nèi)存最高端的ROM（只讀存儲(chǔ)器）中， 如圖4-6（b）所示； 還可以讓設(shè)備驅(qū)動(dòng)程序位于內(nèi)存高端的ROM中， 而讓操作系統(tǒng)的其他部分位于低端的RAM中， 如圖4-6(c)中所示。 圖4-6 單一連續(xù)分配 4.2.2 分區(qū)法 分區(qū)分配是為支持多道程序開(kāi)發(fā)、 運(yùn)行的一種最簡(jiǎn)單的存儲(chǔ)管理方式。 在這種方式下， 要把內(nèi)存劃分成若干分區(qū)， 每個(gè)分區(qū)里容納一個(gè)作業(yè)。 按照分區(qū)的劃分方式， 可歸納為兩種常見(jiàn)的分配方法： 固定分區(qū)法和可變分區(qū)法。 圖

8、4-7 固定分區(qū) 1. 固定分區(qū)法 “固定”包含兩個(gè)意思： 一個(gè)是內(nèi)存中分區(qū)的個(gè)數(shù)固定， 不能隨機(jī)變動(dòng)； 另一個(gè)是各分區(qū)的大小固定。 當(dāng)然各個(gè)分區(qū)的大小可以不同。 但是， 一旦在系統(tǒng)啟動(dòng)時(shí)把內(nèi)存的分區(qū)劃分好， 以后在使用過(guò)程中就不能更改了。 所以， 固定分區(qū)法是對(duì)內(nèi)存的靜態(tài)劃分。固定分區(qū)的管理方法如圖4-7所示。 圖4-8 分區(qū)說(shuō)明表 2. 可變分區(qū)法 由于用戶作業(yè)大小不可能預(yù)先規(guī)定好， 作業(yè)到來(lái)的分布也無(wú)法確定， 所以分區(qū)的大小不會(huì)總與作業(yè)大小相符。 為了解決內(nèi)存浪費(fèi)問(wèn)題， 可以把分區(qū)大小改成可變的， 就是說(shuō)， 各個(gè)分區(qū)是在相應(yīng)作業(yè)處理過(guò)程中建立的， 使其大小恰好適應(yīng)作業(yè)的大小。 這種技術(shù)稱

9、為可變分區(qū)法。 IBM的OS/360 MVT（具有可變?nèi)蝿?wù)數(shù)的多道程序設(shè)計(jì)）操作系統(tǒng)就是采用這種技術(shù)： 操作系統(tǒng)掌管一個(gè)表格， 登記每個(gè)空閑區(qū)和已分配區(qū)， 指出其大小、 位置和對(duì)各個(gè)區(qū)的存取限制等。圖4-9表示了MVT的內(nèi)存分配和作業(yè)調(diào)度示例。 圖4-9 MVT的內(nèi)存分配和作業(yè)調(diào)度 (a) 內(nèi)存初始情況和作業(yè)隊(duì)列； (b) 內(nèi)存分配和作業(yè)調(diào)度 圖4-9 MVT的內(nèi)存分配和作業(yè)調(diào)度 (a) 內(nèi)存初始情況和作業(yè)隊(duì)列； (b) 內(nèi)存分配和作業(yè)調(diào)度 1） 最先適應(yīng)算法 最先適應(yīng)算法也稱為首次適配算法。 在這種算法中， 空閑表是按位置排列的（即空閑塊地址小的， 在表中的序號(hào)也?。?。 2） 循環(huán)適應(yīng)算法

10、循環(huán)適應(yīng)算法也稱作下次適配算法。 它是對(duì)最先適應(yīng)算法的修改： 當(dāng)每次找到合適的空閑塊時(shí)， 就同時(shí)記下當(dāng)時(shí)的位置， 下次查找空閉塊時(shí)就從下一個(gè)空閑分區(qū)開(kāi)始查找， 而不是每次都從頭開(kāi)始查找。 3） 最佳適應(yīng)算法 最佳適應(yīng)算法是在滿足需要的前提下分配最小的那塊。 這種算法的空閑表是以空閑塊的大小為序、 按增量形式排列的， 即小塊在前， 大塊在后。 這種算法的優(yōu)點(diǎn)是： 產(chǎn)生的剩余塊是最小的， 平均而言， 只要查一半空閑表就能找到最佳適應(yīng)的空閑塊。 但是其缺點(diǎn)是： 不便于釋放內(nèi)存時(shí)與鄰接區(qū)的合并， 而且分割后所剩余的空閑區(qū)往往很小， 幾乎無(wú)法使用。 4） 最壞適應(yīng)算法 最壞適應(yīng)算法是最佳適應(yīng)算法的“逆”

11、， 即空閑表是以空閑塊的大小為序， 但大塊在前、 小塊在后。 3. 硬件支持 采用分區(qū)技術(shù)需要有硬件保護(hù)機(jī)構(gòu)。 通常用一對(duì)寄存器分別表示用戶程序在內(nèi)存中的上界地址值和下界地址值， 如圖4-10所示。 圖4-10 分區(qū)的硬件保護(hù) 這一對(duì)寄存器也可用另一種方式設(shè)置值， 一個(gè)表示用戶程序的最小物理地址， 稱為基址寄存器； 另一個(gè)表示用戶程序邏輯地址的范圍， 稱為限長(zhǎng)寄存器。 雖然這兩種方式都用一對(duì)寄存器進(jìn)行保護(hù)， 但兩者的重定位方式是不同的。 前者采用靜態(tài)重定位， 在匯編或裝入時(shí)進(jìn)行， 程序中的每個(gè)有效地址必須大于或等于下界值而小于上界值。 而后者需采用動(dòng)態(tài)重定位， 每個(gè)有效地址必須小于限長(zhǎng)寄存器值

12、， 而相應(yīng)物理地址是有效地址加上基址寄存器的值， 如圖4-11所示。 CDC 6600及其以后的機(jī)器都用這種方式。圖4-11 基址/限長(zhǎng)寄存器的使用 4. 分區(qū)分配的優(yōu)點(diǎn)和缺點(diǎn) 總體來(lái)說(shuō)， 分區(qū)分配的優(yōu)點(diǎn)主要是： 有利于多道程序設(shè)計(jì)； 所需硬件支持很少； 管理算法簡(jiǎn)單， 易于實(shí)現(xiàn)。 但分區(qū)分配也存在很多缺點(diǎn)， 主要有： 碎片問(wèn)題嚴(yán)重， 有些作業(yè)序列可能使內(nèi)存的利用率低于10%； 不利于大作業(yè)運(yùn)行， 當(dāng)空閑塊只有一個(gè)， 但裝不下后面的作業(yè)時(shí)， 內(nèi)存仍造成浪費(fèi)； 為容納多個(gè)作業(yè)， 需要的內(nèi)存容量更大； 已被占用的分區(qū)中可能包括從未使用過(guò)的信息， 且作業(yè)分區(qū)大小受到內(nèi)存總量的限制。 雖然可變分區(qū)比固

13、定分區(qū)的內(nèi)存利用率要高一些， 但是二者都存在碎片問(wèn)題。 怎樣使這些分散的、 較小的空閑區(qū)得到合理使用呢？ 最簡(jiǎn)單的辦法是定時(shí)或在分配內(nèi)存時(shí)把所有的碎片合并為一個(gè)連續(xù)區(qū)， 如圖4-12所示。 圖4-12 可重定位分區(qū)的緊縮 (a) 初始狀態(tài)； (b) 移動(dòng)之后； (c) 分配作業(yè)5之后圖4-13 “占兩頭、空中間” 的分區(qū)方式4.3 對(duì) 換 技 術(shù) 4.3.1 早期對(duì)換技術(shù) 對(duì)換技術(shù)是在早期分時(shí)系統(tǒng)中（如CTSS和Q-32）采用的基本內(nèi)存管理方式。 它的實(shí)現(xiàn)思想是： 除操作系統(tǒng)空間之外剩余的全部?jī)?nèi)存都分給當(dāng)前正在執(zhí)行的用戶進(jìn)程使用， 當(dāng)調(diào)度轉(zhuǎn)向下一個(gè)用戶進(jìn)程時(shí)， 當(dāng)前進(jìn)程內(nèi)存區(qū)中的內(nèi)容要寫到外存

14、（如磁盤）中去， 被選中用戶進(jìn)程的信息讀到內(nèi)存中來(lái)， 如圖4-14所示。 圖4-14 利用磁盤對(duì)換兩個(gè)進(jìn)程 4.3.2 多道程序環(huán)境下的對(duì)換 圖4-15示出多道程序環(huán)境下對(duì)換系統(tǒng)的工作情況。 最初只有進(jìn)程A在內(nèi)存， 隨后創(chuàng)建進(jìn)程B和C（或者二者從盤上換入內(nèi)存）。 在圖4-15(d)中A換出。 然后， D換入， B完成， 最后A再次換入。 由于A現(xiàn)在的位置不同于先前， 因此必須重定位或者在換入時(shí)由軟件完成， 或者在程序執(zhí)行時(shí)由硬件實(shí)現(xiàn)（這是常用方式）。圖4-15 進(jìn)程對(duì)換時(shí)內(nèi)存分配情況 4.4 分 頁(yè) 技 術(shù) 4.4.1 分頁(yè)存儲(chǔ)管理的基本概念 分頁(yè)存儲(chǔ)管理的基本方法是： (1) 邏輯空間分頁(yè)：

15、 將一個(gè)進(jìn)程的邏輯地址空間劃分成若干個(gè)大小相等的部分， 每一部分稱為頁(yè)面或頁(yè)。 每頁(yè)都有一個(gè)編號(hào)， 叫做頁(yè)號(hào)， 頁(yè)號(hào)從0開(kāi)始依次編排， 如0， 1， 2， 。 （2） 內(nèi)存空間分塊： 把內(nèi)存也劃分成與頁(yè)面相同大小的若干個(gè)存儲(chǔ)塊， 稱為內(nèi)存塊或頁(yè)框。 （3） 邏輯地址表示： 在分頁(yè)存儲(chǔ)管理方式中， 表示地址的結(jié)構(gòu)如圖4-16所示。 圖4-16 分頁(yè)技術(shù)的地址結(jié)構(gòu) 頁(yè)號(hào)p頁(yè)內(nèi)地址d31 12 11 0 它由兩個(gè)部分組成： 前一部分表示該地址所在頁(yè)面的頁(yè)號(hào)p； 后一部分表示頁(yè)內(nèi)位移d， 即頁(yè)內(nèi)地址。 圖4-16中所示兩部分構(gòu)成的地址長(zhǎng)度為32位。 其中011為頁(yè)內(nèi)地址， 即每頁(yè)的大小為4 KB； 1

16、231位為頁(yè)號(hào)， 表示地址空間中最多可容納1 MB個(gè)頁(yè)面。 對(duì)于特定機(jī)器來(lái)說(shuō)， 其地址結(jié)構(gòu)是一定的。 如果給定的邏輯地址是A， 頁(yè)面的大小為L(zhǎng)， 則頁(yè)號(hào)p和頁(yè)內(nèi)地址d可按下式求得： p=INTA/L d=A MOD L （4） 內(nèi)存分配原則： 在分頁(yè)情況下， 系統(tǒng)以塊為單位把內(nèi)存分給進(jìn)程， 并且一個(gè)進(jìn)程的若干頁(yè)可分別裝入物理上不相鄰的內(nèi)存塊中。 進(jìn)程的每個(gè)頁(yè)面對(duì)應(yīng)一個(gè)內(nèi)存塊， 如圖4-17所示。圖4-17 分頁(yè)存儲(chǔ)管理系統(tǒng) （5） 頁(yè)表： 在分頁(yè)系統(tǒng)中允許將進(jìn)程的各頁(yè)面離散地裝入內(nèi)存的任何空閑塊中， 這樣一來(lái)就出現(xiàn)進(jìn)程的頁(yè)號(hào)連續(xù)、 而塊號(hào)不連續(xù)的情況。 怎樣找到每個(gè)頁(yè)面在內(nèi)存中對(duì)應(yīng)的物理塊呢？

17、 為此， 系統(tǒng)又為每個(gè)進(jìn)程設(shè)立一張頁(yè)面映像表， 簡(jiǎn)稱頁(yè)表。 如圖4-17中所示。 從圖4-17中的頁(yè)表可知， 頁(yè)號(hào)3對(duì)應(yīng)內(nèi)存的10#塊。 （6） 內(nèi)存塊表： 操作系統(tǒng)管理整個(gè)內(nèi)存， 它必須知道物理存儲(chǔ)的情況， 即哪些塊已經(jīng)分出去了， 哪些塊還是空閑的， 總共有多少塊， 等等。 4.4.2 分頁(yè)系統(tǒng)中的地址映射 通常， 頁(yè)表都放在內(nèi)存中。 當(dāng)進(jìn)程要訪問(wèn)某個(gè)邏輯地址中的數(shù)據(jù)時(shí)， 分頁(yè)地址映像硬件自動(dòng)按頁(yè)面大小將CPU得到的有效地址（相對(duì)地址）分成兩部分： 頁(yè)號(hào)和頁(yè)內(nèi)地址（p, d）。 如圖4-16所示。分頁(yè)系統(tǒng)的地址轉(zhuǎn)換機(jī)構(gòu)如圖4-18所示。 圖4-18 分頁(yè)中的地址轉(zhuǎn)換過(guò)程 4.4.3 快表和頁(yè)

18、表構(gòu)造 1. 快表 在內(nèi)存中放置頁(yè)表也帶來(lái)存取速度下降的矛盾。 因?yàn)榇嫒∫粋€(gè)數(shù)據(jù)（或一條指令）至少要訪問(wèn)兩次內(nèi)存： 一次是訪問(wèn)頁(yè)表， 確定存取對(duì)象的物理地址； 另一次是根據(jù)這個(gè)物理地址存取數(shù)據(jù)（或指令）。 解決這個(gè)問(wèn)題的常用辦法是使用專用的、 高速小容量的聯(lián)想存儲(chǔ)器（TLB， Translation Lookaside Buffer）， 每個(gè)聯(lián)想存儲(chǔ)器包括兩個(gè)部分： 鍵號(hào)和值， 鍵號(hào)是當(dāng)前進(jìn)程正在使用的某個(gè)頁(yè)面號(hào)， 值是該頁(yè)面所對(duì)應(yīng)的物理塊號(hào)。圖4-19示出帶有快表的分頁(yè)系統(tǒng)中地址轉(zhuǎn)換過(guò)程。 圖4-19 利用快表實(shí)現(xiàn)地址轉(zhuǎn)換 2. 頁(yè)表構(gòu)造 1） 多級(jí)頁(yè)表 在上面介紹中每個(gè)進(jìn)程只用一個(gè)頁(yè)表來(lái)實(shí)

19、現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換。 在邏輯地址空間較小的情況下這是可行的。 但現(xiàn)代大多數(shù)計(jì)算機(jī)系統(tǒng)都支持非常大的地址空間， 如232264， 此時(shí)若只用一級(jí)頁(yè)表的話， 就使得頁(yè)表很大。兩級(jí)頁(yè)表方式下邏輯地址結(jié)構(gòu)如圖4-20所示。圖4-20 兩級(jí)頁(yè)表的地址結(jié)構(gòu) 具有兩級(jí)頁(yè)表結(jié)構(gòu)的系統(tǒng)中地址轉(zhuǎn)換的方法是： 利用外層頁(yè)號(hào)p1檢索外層頁(yè)表， 從中找到相應(yīng)內(nèi)層頁(yè)表的基址； 再利用p2作為該內(nèi)層頁(yè)表的索引， 找到該頁(yè)面在內(nèi)存的塊號(hào)； 用該塊號(hào)和頁(yè)內(nèi)地址d拼接起來(lái)就形成訪問(wèn)內(nèi)存的物理地址了， 如圖4-21所示。 圖4-21 具有兩級(jí)頁(yè)表的地址轉(zhuǎn)換機(jī)構(gòu) 外層頁(yè)表要有242項(xiàng)， 即244字節(jié)。 為此， 把外層頁(yè)表再

20、分頁(yè)， 于是得到三級(jí)頁(yè)表結(jié)構(gòu)。 三級(jí)頁(yè)表的地址結(jié)構(gòu)如圖4-22所示。圖4-22 三級(jí)頁(yè)表的地址結(jié)構(gòu) 2） 倒置頁(yè)表 上述進(jìn)程的頁(yè)表都是以頁(yè)號(hào)為索引去搜索頁(yè)表， 即頁(yè)表是按虛擬地址排序的。 隨著64位虛擬地址空間在處理器上的應(yīng)用， 使得內(nèi)存空間顯得很小。 在此情況下， 按邏輯頁(yè)號(hào)為序構(gòu)造頁(yè)表， 則頁(yè)表會(huì)非常大。 為了減少頁(yè)表占用過(guò)多內(nèi)存空間， 可以采用倒置頁(yè)表（Inverted Page Table）。 倒置頁(yè)表的構(gòu)造恰與普通頁(yè)表相反， 它是按內(nèi)存塊號(hào)排序， 每個(gè)內(nèi)存塊占有一個(gè)表項(xiàng)。 每個(gè)表項(xiàng)包括存放在該內(nèi)存塊中頁(yè)面的虛擬頁(yè)號(hào)和擁有該頁(yè)面的進(jìn)程標(biāo)識(shí)符。 這樣， 系統(tǒng)中只有一個(gè)頁(yè)表， 每個(gè)內(nèi)存塊對(duì)

21、應(yīng)惟一的表項(xiàng)。 圖4-23示出倒置頁(yè)表的操作過(guò)程。 圖4-23 倒置頁(yè)表 4.4.4 頁(yè)的共享和保護(hù) 在多道程序系統(tǒng)中， 數(shù)據(jù)共享很重要。 尤其在一個(gè)大型分時(shí)系統(tǒng)中， 往往有若干用戶同時(shí)運(yùn)行相同的程序（如編輯程序、 編譯程序）。 很顯然， 更有效的辦法是共享頁(yè)面， 避免同時(shí)在內(nèi)存中有同一頁(yè)面的兩個(gè)副本。 共享的方法是使這些相關(guān)進(jìn)程的邏輯空間中的頁(yè)面指向相同的內(nèi)存塊（該塊中放有共享程序或數(shù)據(jù)）。 圖4-24示出了三個(gè)進(jìn)程共享5#內(nèi)存塊中文本數(shù)據(jù)的情況。圖4-24 頁(yè)面的共享 4.5 分 段 技 術(shù) 4.5.1 分段存儲(chǔ)管理的基本概念 1. 分段 通常， 一個(gè)用戶程序是由若干相對(duì)獨(dú)立的部分組成的，

22、 各自完成不同的功能。 如上所述， 為了編程和使用的方便， 我們希望把自己的程序按照邏輯關(guān)系加以組織， 即劃分成若干段， 并按照這些段來(lái)分配內(nèi)存。 所以， 段是一組邏輯信息的集合。 例如， 有主程序段MAIN、 子程序段P、 數(shù)據(jù)段D和棧段S等。 如圖4-25所示。 圖4-25 分段地址空間 2. 程序的地址結(jié)構(gòu) 由于整個(gè)作業(yè)的地址空間分成多個(gè)段， 所以， 邏輯地址要用兩個(gè)成分來(lái)表示： 段號(hào)s和段內(nèi)地址d。 就是說(shuō)， 在分段存儲(chǔ)情況下， 作業(yè)的邏輯地址空間是二維的。 分段系統(tǒng)中所用的地址結(jié)構(gòu)如圖4-26所示。 圖4-26 分段技術(shù)的地址結(jié)構(gòu) 3. 內(nèi)存分配 在分段存儲(chǔ)管理中內(nèi)存以段為單位進(jìn)行分

23、配， 每個(gè)段單獨(dú)占用一塊連續(xù)的內(nèi)存分區(qū)。 各分區(qū)的大小由對(duì)應(yīng)段的大小決定。 這有些類似于動(dòng)態(tài)分區(qū)分配方式。 但是二者是不同的： 在分段存儲(chǔ)管理系統(tǒng)中， 一個(gè)作業(yè)或進(jìn)程可以有多個(gè)段， 這些段可以離散地放入內(nèi)存的不同的分區(qū)中。 4. 段表和段表地址寄存器 同分頁(yè)一樣， 為了能找出每個(gè)邏輯段所對(duì)應(yīng)的物理內(nèi)存中分區(qū)的位置， 系統(tǒng)為每個(gè)進(jìn)程建立了一個(gè)段映射表， 簡(jiǎn)稱“段表”。 每個(gè)段在段表中占有一項(xiàng)。 段表項(xiàng)中一般應(yīng)包含以下內(nèi)容： 段號(hào)、 段的長(zhǎng)度、 段在內(nèi)存中的起始地址（又稱“基址”）等。 5. 分頁(yè)和分段的主要區(qū)別 分頁(yè)和分段存儲(chǔ)管理系統(tǒng)有很多相似之處， 例如， 二者在內(nèi)存中都不是整體連續(xù)的， 都要

24、通過(guò)地址映射機(jī)構(gòu)將邏輯地址映射到物理內(nèi)存中。 但二者在概念上完全不同， 主要有以下幾點(diǎn)： （1） 頁(yè)是信息的物理單位。 (2) 頁(yè)的大小是由系統(tǒng)固定的， 即由機(jī)器硬件把邏輯地址劃分成頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分。 (3) 分頁(yè)的作業(yè)地址空間是一維的， 地址編號(hào)從0開(kāi)始順次遞增， 一直排到末尾。 因而只需用一個(gè)地址編號(hào)(如10000）就可確定地址空間中的惟一地址。 4.5.2 地址轉(zhuǎn)換 段地址轉(zhuǎn)換與分頁(yè)地址轉(zhuǎn)換的過(guò)程基本相同， 其大致過(guò)程如圖4-27所示。 (1) CPU計(jì)算出來(lái)的有效地址分成兩個(gè)部分： 段號(hào)s和段內(nèi)地址d。 (2) 系統(tǒng)將該進(jìn)程段表地址寄存器中的內(nèi)容B(表示段表的內(nèi)存地址)與段號(hào)s相加

25、， 得到查找該進(jìn)程段表中相應(yīng)表項(xiàng)的索引值。 圖4-27 分段地址轉(zhuǎn)換 (3) 將段內(nèi)地址d與段長(zhǎng)m進(jìn)行比較。 如果d不小于m， 則表示地址越界， 系統(tǒng)發(fā)出地址越界中斷， 進(jìn)而終止程序執(zhí)行； 如果d小于m， 則表示地址合法， 從而將段內(nèi)地址d與該段的內(nèi)存始址s相加， 得到所要訪問(wèn)單元的內(nèi)存地址。 4.5.3 段的共享和保護(hù) 分段管理的一個(gè)優(yōu)點(diǎn)是提供了對(duì)代碼或數(shù)據(jù)進(jìn)行有效地共享。 為了共享某個(gè)段， 只需在各個(gè)作業(yè)的段表中登記一項(xiàng)， 使它們的基地址都指向同一個(gè)物理單元， 如圖4-28所示。 圖4-28 分段系統(tǒng)中段的共享 段的保護(hù)措施有以下幾種： (1) 存取控制。 （2） 段表本身可起保護(hù)作用。

26、（3） 段表地址寄存器中段表長(zhǎng)L起保護(hù)作用。 （4） 保護(hù)環(huán)。 4.6 虛 擬 存 儲(chǔ) 器 4.6.1 虛擬存儲(chǔ)器概念 作業(yè)在執(zhí)行之前要全部裝入內(nèi)存， 這種限制往往是不合理的， 會(huì)造成內(nèi)存的浪費(fèi)。 因?yàn)椋?（1） 程序中往往含有不會(huì)被執(zhí)行的代碼， 如對(duì)不常見(jiàn)的錯(cuò)誤進(jìn)行處理的代碼。 （2） 一般為數(shù)組、 隊(duì)列、 表格等數(shù)據(jù)結(jié)構(gòu)分配的內(nèi)存空間要大于它們的實(shí)際需要。 （3） 一個(gè)程序的某些任選功能和特殊性能很少被使用， 例如把某些行中所有的字符都轉(zhuǎn)換成大寫字符的正文編輯命令。 這樣做會(huì)帶來(lái)很多好處， 起碼有以下兩點(diǎn)： （1） 用戶編制程序時(shí)可不必考慮內(nèi)存容量的限制， 只要按照實(shí)際問(wèn)題的需要來(lái)確定合適

27、的算法和數(shù)據(jù)結(jié)構(gòu)， 從而簡(jiǎn)化了程序設(shè)計(jì)的任務(wù)。 （2） 由于每個(gè)進(jìn)程只有一部分裝入內(nèi)存， 因而占用的內(nèi)存空間就較少， 在一定容量的內(nèi)存中就可同時(shí)裝入更多的進(jìn)程， 也相應(yīng)地增加了CPU的利用率和系統(tǒng)的吞吐量。 4.6.2 虛擬存儲(chǔ)器特征 對(duì)于虛擬存儲(chǔ)器這一基本概念我們應(yīng)從以下幾個(gè)方面進(jìn)行理解， 這些也是虛擬存儲(chǔ)器所具有的基本特征。 (1) 虛擬擴(kuò)充。 虛擬存儲(chǔ)器不是物理上擴(kuò)大內(nèi)存空間， 而是邏輯上擴(kuò)充了內(nèi)存容量。 (2) 部分裝入。 每個(gè)進(jìn)程不是全部一次性地裝入內(nèi)存， 而是分成若干部分。 (3) 離散分配。 一個(gè)進(jìn)程分成多個(gè)部分， 沒(méi)有全部裝入內(nèi)存。 (4) 多次對(duì)換。 在一個(gè)進(jìn)程運(yùn)行期間， 它

28、所需的全部程序和數(shù)據(jù)要分成多次調(diào)入內(nèi)存。 4.7 請(qǐng)求分頁(yè)技術(shù) 4.7.1 請(qǐng)求分頁(yè)的基本思想 在簡(jiǎn)單分頁(yè)存儲(chǔ)管理系統(tǒng)中， 每個(gè)進(jìn)程的地址空間是連續(xù)的， 而映像到存儲(chǔ)空間后就不一定連續(xù)。 就是說(shuō)， 頁(yè)號(hào)連續(xù)而相應(yīng)的塊號(hào)不連續(xù)。 利用這種辦法， 有效地解決了內(nèi)存碎片問(wèn)題， 從而更好地支持多道程序設(shè)計(jì)， 提高了內(nèi)存和CPU的利用率。 4.7.2 硬件支持及缺頁(yè)處理 1. 頁(yè)表機(jī)制 如上所述， 分頁(yè)系統(tǒng)中地址映射是通過(guò)頁(yè)表實(shí)現(xiàn)的。 在請(qǐng)求分頁(yè)系統(tǒng)中， 頁(yè)表項(xiàng)不僅要包含該頁(yè)在內(nèi)存的基址， 還要含有下列信息： （1） 頁(yè)表的每一項(xiàng)增加一個(gè)狀態(tài)位， 用來(lái)指示該頁(yè)面是否在內(nèi)存中。 （2） 頁(yè)表項(xiàng)中還要記載該

29、頁(yè)面在外存的地址（又稱文件地址）， 以便在發(fā)生缺頁(yè)情況下， 操作系統(tǒng)能很快地在外存上找到該頁(yè)面， 換入內(nèi)存。 （3） 在頁(yè)表中還要增加一些位， 用于記錄該頁(yè)的使用情況（如最近被引用過(guò)沒(méi)有， 該頁(yè)的內(nèi)容在內(nèi)存中修改過(guò)沒(méi)有等）， 幫助操作系統(tǒng)做出頁(yè)面替換的決定。 頁(yè)號(hào) 內(nèi)存塊號(hào) 改變位 狀態(tài)位 引用位 外存地址 2. 缺頁(yè)中斷機(jī)構(gòu) 在硬件方面， 還要增加對(duì)缺頁(yè)中斷進(jìn)行響應(yīng)的機(jī)構(gòu)。 一旦發(fā)現(xiàn)所訪問(wèn)的頁(yè)面不在內(nèi)存， 能立即產(chǎn)生中斷信號(hào)， 隨后轉(zhuǎn)入缺頁(yè)中斷處理程序進(jìn)行相應(yīng)處理。 缺頁(yè)中斷的處理過(guò)程是由硬件和軟件共同實(shí)現(xiàn)的。 其相互關(guān)系如圖4-29所示。圖4-29 指令執(zhí)行步驟與缺頁(yè)中斷處理過(guò)程 4.7.

30、3 請(qǐng)求分頁(yè)的優(yōu)缺點(diǎn) 分頁(yè)技術(shù)的一個(gè)非常重要的性質(zhì)是把存儲(chǔ)器的用戶觀點(diǎn)和實(shí)際的物理存儲(chǔ)器清晰地區(qū)分開(kāi)。 用戶編制程序時(shí)認(rèn)為存儲(chǔ)器是一片連續(xù)的空間， 其中只包括這一個(gè)程序。 而實(shí)際上， 用戶程序被分散到物理存儲(chǔ)器中， 其中還有其他程序。 二者之間的差別是通過(guò)地址轉(zhuǎn)換機(jī)構(gòu)（即映像硬件）統(tǒng)一起來(lái)的。 映像對(duì)用戶來(lái)說(shuō)是隱蔽的， 它受操作系統(tǒng)控制。 請(qǐng)求分頁(yè)除了具有簡(jiǎn)單分頁(yè)的優(yōu)點(diǎn)之外， 還有下列優(yōu)點(diǎn)： （1） 提供多個(gè)大容量的虛擬存儲(chǔ)器。 （2） 更有效地利用了內(nèi)存。 （3） 多道程序度更高了。 它除了硬件成本增加， 用于對(duì)換與置換的時(shí)間與空間的開(kāi)銷增大， 以及有內(nèi)部碎片等缺點(diǎn)外， 還添加了以下缺點(diǎn)：

31、（1） 對(duì)缺頁(yè)中斷的處理要占用較多的存儲(chǔ)空間和CPU時(shí)間； （2） 如每個(gè)進(jìn)程的地址空間過(guò)大， 或進(jìn)入系統(tǒng)的進(jìn)程數(shù)過(guò)多， 則會(huì)發(fā)生系統(tǒng)抖動(dòng)。 4.7.4 請(qǐng)求分頁(yè)的性能 請(qǐng)求分頁(yè)對(duì)計(jì)算機(jī)系統(tǒng)的性能可能產(chǎn)生重要影響。 為說(shuō)明這個(gè)問(wèn)題， 我們計(jì)算一下請(qǐng)求分頁(yè)系統(tǒng)的有效存取時(shí)間。 對(duì)多數(shù)計(jì)算機(jī)系統(tǒng)來(lái)說(shuō)， 內(nèi)存存取時(shí)間ma一般為10200 ns， 只要不出現(xiàn)缺頁(yè)中斷， 有效存取時(shí)間就等于內(nèi)存存取時(shí)間。 如果發(fā)生了缺頁(yè)中斷， 則首先必須從外存中讀入該頁(yè)， 然后才能進(jìn)行內(nèi)存存取。 令p表示缺頁(yè)中斷的概率（0p1）， 簡(jiǎn)稱缺頁(yè)率， 它等于缺頁(yè)次數(shù)與全部訪問(wèn)內(nèi)存次數(shù)之比。 我們希望p與0越接近越好， 這樣就僅

32、有很少的缺頁(yè)中斷發(fā)生。 有效存取時(shí)間是： 有效存取時(shí)間=（1-p）ma+p缺頁(yè)處理時(shí)間 為了算出有效存取時(shí)間， 必須知道處理缺頁(yè)中斷所需的時(shí)間。 缺頁(yè)導(dǎo)致以下的一系列動(dòng)作（設(shè)當(dāng)前進(jìn)程為A）： （1） 捕俘進(jìn)入操作系統(tǒng)。 （2） 保存A的各寄存器和進(jìn)程狀態(tài)信息。 （3） 確定該中斷是缺頁(yè)引起的。 （4） 檢查對(duì)該頁(yè)的訪問(wèn)是合法的， 并確定該頁(yè)在磁盤上的地址。 （5） 將該頁(yè)從磁盤讀到空閑塊中： 在設(shè)備隊(duì)列中等待， 直至該請(qǐng)求得到服務(wù)； 等待設(shè)備尋道和/或旋轉(zhuǎn)延遲時(shí)間； 開(kāi)始傳送該頁(yè)到空閑塊。 （6） 在等待時(shí)間內(nèi)， 可把CPU分給其他進(jìn)程（由CPU調(diào)度程序執(zhí)行）， 例如B。 （7） 收到來(lái)自磁盤

33、的中斷（I/O完成）。 （8） 為正在運(yùn)行的進(jìn)程B保存寄存器和程序狀態(tài)。 （9） 確定該中斷是來(lái)自磁盤的I/O中斷。 （10） 調(diào)整頁(yè)表和其他表格， 說(shuō)明所需頁(yè)面已在內(nèi)存。 （11） 等待重新把CPU分給進(jìn)程A。 （12） 恢復(fù)該進(jìn)程各寄存器、 進(jìn)程狀態(tài)和新的頁(yè)表， 然后重新開(kāi)始被中斷的指令。 并不是在所有情況下都需要上述各步， 但以下三個(gè)主要工作是必須要做的： （1） 處理缺頁(yè)中斷； （2） 調(diào)入該頁(yè)； （3） 重新啟動(dòng)該進(jìn)程。 如果把平均缺頁(yè)服務(wù)時(shí)間取為25 ms， 內(nèi)存存取時(shí)間取為100 ns， 那么 有效存取時(shí)間=（1-p）100+p25 ms =(1-p)100+25 000 000

34、p =100+24 999 900p 可以看出， 有效存取時(shí)間直接正比于缺頁(yè)的比率。 如果缺頁(yè)率為千分之一， 則有效存取時(shí)間是25 s， 計(jì)算機(jī)速度因請(qǐng)頁(yè)而降低到原來(lái)的1/250。 如果期望下降率不超過(guò)10%， 則有： 110100+25 000 000p 10 25 000 000p p 0.000 000 4 4.7.5 頁(yè)面置換 由圖4-29可以看出， 如果被訪問(wèn)的頁(yè)不在內(nèi)存時(shí)， 則產(chǎn)生缺頁(yè)中斷。 操作系統(tǒng)進(jìn)行中斷處理， 把該頁(yè)從外存調(diào)入內(nèi)存。 那么新調(diào)進(jìn)的頁(yè)到底放在什么地方呢？ 如果內(nèi)存中有空閑塊， 則可把該頁(yè)裝入任何空閑塊中， 調(diào)整頁(yè)表項(xiàng)及存儲(chǔ)分塊表。 如果當(dāng)前內(nèi)存空間已裝滿， 那么

35、該頁(yè)放到哪里去呢？ 此時(shí)必須先淘汰已在內(nèi)存的一頁(yè)， 騰出空間， 再把所需頁(yè)面裝入。 其工作流程如圖4-30所示。 它主要包括以下幾個(gè)步驟： （1） 在磁盤上尋找所需頁(yè)面。 （2） 尋找空閑塊： 如果有空閑塊， 就用它； 否則， 就利用頁(yè)面置換算法選擇一個(gè)替換的塊； 把該塊寫到磁盤上， 并相應(yīng)地修改頁(yè)表和存儲(chǔ)塊表。 （3） 把所需頁(yè)面讀入內(nèi)存（剛剛得到的空閑塊）， 修改頁(yè)表和存儲(chǔ)塊表。 （4） 重新啟動(dòng)該用戶進(jìn)程。 圖4-30 頁(yè)面置換過(guò)程 4.8 頁(yè)面置換算法 為減少數(shù)據(jù)的數(shù)量， 我們要注意到下面兩件事。 第一， 對(duì)于給定的頁(yè)面大?。ㄍǔＳ捎布蛘呦到y(tǒng)來(lái)確定）， 我們僅考慮其頁(yè)號(hào)， 不關(guān)心完整

36、的地址。 第二， 如果對(duì)面頁(yè)p進(jìn)行了訪問(wèn)， 那么隨后立即進(jìn)行的對(duì)p的訪問(wèn)不會(huì)缺頁(yè)。 這樣， 如果我們追蹤特定程序， 記下下述地址序列：0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611,0102, 0103, 0104, 0101, 0610, 0102, 0103, 0104, 0101,0609, 0102, 0105 若每頁(yè)100個(gè)字節(jié)， 則頁(yè)面走向縮減為： 1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1圖4-31 缺頁(yè)量與塊數(shù)的關(guān)系圖 4.8.1 先入先出法（FIFO） 對(duì)給定的頁(yè)面走向， 有三個(gè)內(nèi)存塊最初是空的（如

37、圖4-32所示）。 前面三個(gè)頁(yè)面訪問(wèn)（7， 0， 1）導(dǎo)致缺頁(yè)， 被放入這三塊中。 下面的訪問(wèn)（2）要置換頁(yè)面7， 因?yàn)樗亲钕冗M(jìn)入的。 接著是對(duì)頁(yè)面0的訪問(wèn)， 由于它已在內(nèi)存， 所以不發(fā)生缺頁(yè)。 這樣順次地做下去， 就產(chǎn)生如圖4-32所示的情況。 每出現(xiàn)一次缺頁(yè)， 我們就示出置換后的情況， 總共有15次缺頁(yè)。圖4-32 FIFO頁(yè)面置換 FIFO頁(yè)面置換算法容易理解和進(jìn)行程序設(shè)計(jì)。 然而它的性能并非總是好的。 這種算法只是在按線性順序訪問(wèn)地址空間時(shí)才是理想的， 否則效率不高。 因?yàn)槟切┏１辉L問(wèn)的頁(yè)， 往往在主存中也停留得最久， 結(jié)果它們因變“老”而不得不被置換出去。 大家可分析一下頁(yè)面走向是

38、下述情況時(shí)（三個(gè)內(nèi)存塊可用）： 1， 2， 3， 4， 1， 2 5， 1， 2， 3， 4， 5 頁(yè)面置換的過(guò)程。 FIFO的另一個(gè)缺點(diǎn)是， 它有一種異?，F(xiàn)象， 即在增加存儲(chǔ)塊的情況下， 反而使缺頁(yè)中斷率增加了， 如圖4-33所示。 當(dāng)然， 導(dǎo)致這種異?，F(xiàn)象的頁(yè)面走向?qū)嶋H上是很少見(jiàn)的。 圖4-33 關(guān)于一個(gè)頁(yè)面走向的FIFO置換算法的缺頁(yè)曲線 4.8.2 最優(yōu)置換算法（OPT） 最優(yōu)置換（Optimal Replacement）是1966年由Belady在理論上提出的一種算法。 其實(shí)質(zhì)是： 當(dāng)調(diào)入新的一頁(yè)而必須預(yù)先置換某個(gè)老頁(yè)時(shí)， 所選擇的老頁(yè)應(yīng)是將來(lái)不再被使用， 或者是在最遠(yuǎn)的將來(lái)才被訪問(wèn)

39、。 采用這種頁(yè)面置換算法， 保證有最少的缺頁(yè)率。 例如， 對(duì)于上面給定的頁(yè)面走向來(lái)說(shuō)， 最優(yōu)頁(yè)面置換算法僅出現(xiàn)9次缺頁(yè)中斷， 如圖4-34所示。圖4-34 最優(yōu)頁(yè)面置換 4.8.3 最久未使用算法（LRU） 最優(yōu)置換算法在實(shí)際中行不通， 但可以找到與它接近的算法。 回想一下， FIFO算法和OPT算法之間的主要差別是， FIFO算法利用頁(yè)面進(jìn)入內(nèi)存后的時(shí)間長(zhǎng)短作為置換依據(jù)， 而OPT算法的依據(jù)是將來(lái)使用頁(yè)面的時(shí)間。 如果以最近的過(guò)去作為不久將來(lái)的近似， 那么就可以把過(guò)去最長(zhǎng)一段時(shí)間里不曾被使用的頁(yè)面置換掉。 它的實(shí)質(zhì)是， 當(dāng)需要置換一頁(yè)時(shí)， 選擇在最近一段時(shí)間里最久沒(méi)有使用過(guò)的頁(yè)面予以置換。

40、這種算法就稱為最久未使用算法（LRU）， 如圖4-35所示。圖4-35 LRU頁(yè)面置換算法 LRU算法是與每個(gè)頁(yè)面最后使用的時(shí)間有關(guān)的。 當(dāng)必須置換一個(gè)頁(yè)面時(shí)， LRU算法選擇過(guò)去一段時(shí)間里最久未被使用的頁(yè)面。 這就是OPT算法在時(shí)間上向后看， 而不是向前看的情況。 在圖4-35的示例中， 應(yīng)用LRU算法產(chǎn)生12次缺頁(yè)。 其中前面5次缺頁(yè)情況是與OPT算法一樣的。 LRU算法是經(jīng)常采用的頁(yè)面置換算法， 并被認(rèn)為是相當(dāng)好的， 但是存在如何實(shí)現(xiàn)它的問(wèn)題。 LRU算法需要實(shí)際硬件的支持。 其問(wèn)題是怎么確定最后使用時(shí)間的順序， 對(duì)此有兩種可行的辦法： （1） 計(jì)數(shù)器。 最簡(jiǎn)單的情況是使每個(gè)頁(yè)表項(xiàng)對(duì)應(yīng)一

41、個(gè)使用時(shí)間字段， 并給CPU增加一個(gè)邏輯時(shí)鐘或計(jì)數(shù)器。 （2） 棧。 用一個(gè)棧保留頁(yè)號(hào)。 每當(dāng)訪問(wèn)一個(gè)頁(yè)面時(shí)， 就把它從棧中取出放在棧頂上。 這樣一來(lái)， 棧頂總是放有目前使用最多的頁(yè)， 而棧底放著目前最少使用的頁(yè)（如圖4-36所示）。 圖4-36 利用棧記錄目前訪問(wèn)最多的頁(yè)面 圖4-37 LRU近似算法 4.8.4 第二次機(jī)會(huì)算法（SCR） 第二次機(jī)會(huì)算法的基本思想是與FIFO相同的， 但是有所改進(jìn)， 避免把經(jīng)常使用的頁(yè)面置換出去。 第二次機(jī)會(huì)算法可視為一個(gè)環(huán)形隊(duì)列。 用一個(gè)指針指示哪一頁(yè)是下面要淘汰的。 當(dāng)需要一個(gè)存儲(chǔ)塊時(shí)， 指針就前進(jìn)， 直至找到訪問(wèn)位是0的頁(yè)。 隨著指針的前進(jìn)， 把訪問(wèn)位

42、就清為0， 如圖4-38所示。 圖4-38 第二次機(jī)會(huì)置換算法 (a) 開(kāi)始時(shí)； (b) 選中時(shí)4.9 內(nèi)存塊分配算法和抖動(dòng)問(wèn)題 4.9.1 內(nèi)存塊分配算法 一旦選定了置換算法， 我們就可以考慮內(nèi)存管理的靈活性。 帶虛擬存儲(chǔ)器的最簡(jiǎn)單的情況是單用戶系統(tǒng)。 整個(gè)內(nèi)存， 除操作系統(tǒng)占用的空間之外， 余下部分全部給一個(gè)用戶程序。 1. 最少內(nèi)存塊數(shù) 分配給進(jìn)程的內(nèi)存塊數(shù)目是受到限制的， 分配的總塊數(shù)不能超出可用塊的總量（除非存在頁(yè)共享的情況）。 另一方面， 每個(gè)進(jìn)程也需要有起碼最少的塊數(shù)。 2. 固定分配和可變分配 請(qǐng)求分頁(yè)系統(tǒng)支持虛擬存儲(chǔ)器。 在這種系統(tǒng)中沒(méi)有必要、 也不可能在一個(gè)進(jìn)程運(yùn)行之前就把

43、它的所有頁(yè)面都裝入內(nèi)存。 （1） 固定分配策略是分配給進(jìn)程的內(nèi)存塊數(shù)是固定的， 并在最初裝入時(shí)（即進(jìn)程創(chuàng)建時(shí)）確定塊數(shù)。 （2） 可變分配策略允許分給進(jìn)程的內(nèi)存塊數(shù)隨進(jìn)程的活動(dòng)而改變。 3. 全局置換與局部置換 內(nèi)存塊分配的另一個(gè)重要問(wèn)題是頁(yè)面置換范圍。 多個(gè)進(jìn)程競(jìng)爭(zhēng)內(nèi)存塊時(shí)， 可以把頁(yè)面置換分成兩種主要類型： 全局置換和局部置換。 全局置換允許一個(gè)進(jìn)程從全體存儲(chǔ)塊的集合中選取置換塊， 盡管該塊當(dāng)前已分給其他進(jìn)程， 但還是能強(qiáng)行剝奪。 而局部置換是每個(gè)進(jìn)程只能從分給它的一組塊中選擇置換塊。 采用局部置換策略， 分給進(jìn)程的塊數(shù)是不能變更的。 4. 內(nèi)存塊分配算法 為每個(gè)進(jìn)程分配內(nèi)存塊的算法主要有

44、三種： 等分法、 比例法和優(yōu)先權(quán)法。 1） 等分法 為每個(gè)進(jìn)程分配存儲(chǔ)塊的最簡(jiǎn)單的辦法是平分， 即若有m塊、 n個(gè)進(jìn)程， 則每個(gè)進(jìn)程分m/n塊（其值向下取整）。 2） 比例法 設(shè)進(jìn)程pi的地址空間大小為si， 則全部進(jìn)程的總地址空間為 S=si 若可用塊的總數(shù)是m， 則分給進(jìn)程pi的塊數(shù)是ai, ai近似等于 當(dāng)然， ai必須是整數(shù)， 大于所需最少塊數(shù)， 且總 數(shù)不超過(guò)m。 3） 優(yōu)先權(quán)法 應(yīng)注意到， 在上面兩種算法中沒(méi)有考慮優(yōu)先級(jí)問(wèn)題， 即把高優(yōu)先級(jí)進(jìn)程和低優(yōu)先級(jí)進(jìn)程一樣對(duì)待。 4.9.2 抖動(dòng)（Thrashing）問(wèn)題 置換算法的優(yōu)劣， 直接影響到系統(tǒng)的效率。 若選用算法不合適， 可能會(huì)出

45、現(xiàn)這種現(xiàn)象： 剛被置換出去的頁(yè)， 很快又要訪問(wèn)它， 因而要把它重新調(diào)入； 可是調(diào)入不久又再次被置換出去， 這樣再訪問(wèn)、 再調(diào)入， 如此反復(fù)， 使得整個(gè)系統(tǒng)的頁(yè)面替換非常頻繁， 以致大部分的機(jī)器時(shí)間都花在來(lái)回進(jìn)行的頁(yè)面調(diào)度上， 只有一小部分時(shí)間用于進(jìn)程的實(shí)際運(yùn)算。 這種局面就稱為系統(tǒng)“抖動(dòng)”。 產(chǎn)生抖動(dòng)的原因是系統(tǒng)中多道程序度過(guò)高， 進(jìn)程運(yùn)行缺頁(yè)率嚴(yán)重。 一般情況下， 在多道程序度較小時(shí)， 隨著它的增加， CPU利用率會(huì)緩慢增加。 當(dāng)?shù)竭_(dá)最大值以后， 多道程序度進(jìn)一步增大， 就出現(xiàn)了抖動(dòng)， 導(dǎo)致CPU利用率急劇下降， 如圖4-39所示。圖4-39 CPU利用率與多道程序度的關(guān)系 防止抖動(dòng)發(fā)生或者

46、限制抖動(dòng)影響的方法有多種， 但一般都基于調(diào)節(jié)多道程序度。 （1） 采用局部置換策略。 （2） 利用工作集策略防止抖動(dòng)（詳見(jiàn)4.9.3節(jié)）。 （3） 掛起某些進(jìn)程。 當(dāng)出現(xiàn)CPU利用率很低、 而磁盤I/O非常頻繁的情況時(shí)， 就可能因?yàn)槎嗟莱绦蚨忍叨斐啥秳?dòng)。 （4） 采用缺頁(yè)頻度法（PFF， Page Fault Frequency)。 4.9.3 工作集 局部化可分為兩類： 時(shí)間局部化和空間局部化。 時(shí)間局部化是指一旦某條指令或數(shù)據(jù)被訪問(wèn)了， 它常常很快又被再次訪問(wèn)。 這是大多數(shù)程序所具有的性質(zhì)， 例如程序中的循環(huán)部分、 常用的變量和函數(shù)等。 空間局部化指的是一旦某個(gè)位置被訪問(wèn)到， 那么它附

47、近的位置也可能很快要用到。 Denning于1968年提出了工作集理論來(lái)研究和描述這種局部性。 所謂工作集， 就是一個(gè)進(jìn)程在某一小段時(shí)間內(nèi)訪問(wèn)頁(yè)面的集合。 如用WS(ti)表示在ti - ti之間所訪問(wèn)的不同頁(yè)面， 那么它就是進(jìn)程在時(shí)間ti的工作集， 如圖4-40所示。圖4-40 工作集模型 工作集最重要的性質(zhì)是它的大小。 工作集越小， 則程序局部性越好。 如果我們計(jì)算出系統(tǒng)中每個(gè)進(jìn)程的工作集大小WSSi， 那么 4.10 段式虛擬存儲(chǔ)器 4.10.1 基本工作過(guò)程 在段式虛存系統(tǒng)中， 一個(gè)進(jìn)程的所有分段的副本都保存在外存上。 當(dāng)它運(yùn)行時(shí)， 首先把當(dāng)前需要的一段或幾段裝入內(nèi)存， 其他段僅在調(diào)用

48、時(shí)才裝入。 其過(guò)程一般是： 當(dāng)所訪問(wèn)的段不在內(nèi)存時(shí)， 便產(chǎn)生缺段中斷， 操作系統(tǒng)接到中斷信號(hào)后， 進(jìn)行相應(yīng)處理， 按類似于申請(qǐng)分區(qū)的方式， 在內(nèi)存中找到一塊足夠大的分區(qū)， 以便放入所需分段。 采用段式虛存系統(tǒng)， 可以便于動(dòng)態(tài)連接， 就是說(shuō)只有用到某個(gè)分段時(shí)， 才連接它， 從而避免不必要的連接。 為支持動(dòng)態(tài)連接要附加兩個(gè)硬件設(shè)施： 間接編址和連接故障指示位。 這是MULTICS系統(tǒng)中采用的方法。 間接編址是指令中地址部分， 它不是存取數(shù)據(jù)的直接地址， 而是間接地址， 即存放這個(gè)直接地址的那個(gè)單元的地址。 包含該直接地址的字稱為間接字。 連接故障指示位設(shè)在間接字中， 用于表示所訪問(wèn)的段號(hào)是否已連接

49、上。 間接編址與直接編址的區(qū)別如圖4-41所示。圖4-41 直接編址與間接編址 (a) 直接編址； (b) 間接編址 4.10.2 連接中斷處理 如圖4-42(a)所示， 程序MAIN中有一條指令LOAD*1， 3|100， 這是間接編址形式， 它從本段的100號(hào)單元中得到間接字。 由于連接位置為1， 因此產(chǎn)生連接中斷信號(hào)。 于是操作系統(tǒng)得到控制， 執(zhí)行連接中斷處理程序， 根據(jù)間接字中的地址3|108， 找到段X。 文件系統(tǒng)可以根據(jù)這個(gè)段名找到它的全部信息， 然后為X段分配一個(gè)段號(hào)， 例如4(按段表的序號(hào))。 再根據(jù)Y找到它的位移量， 例如200， 然后修改間接 字， 將連接位清0， 其中地址

50、部分改為連接后的直接地址， 即4|200。 這時(shí)連接工作完成。 控制重新轉(zhuǎn)向被中斷的指令LOAD*1， 3 | 100， 繼續(xù)執(zhí)行下去。 連接后的情況如圖4-42(b)所示。 圖4-42 段的動(dòng)態(tài)連接 (a) 指令執(zhí)行之前； (b) X段連接之后 4.10.3 段式虛擬存儲(chǔ)的優(yōu)點(diǎn)和缺點(diǎn) 從上面分析可以看出， 采用分段技術(shù)有利于用戶對(duì)程序地址空間的了解， 便于對(duì)各個(gè)程序段的共享和保護(hù)。 此外， 段式虛擬存儲(chǔ)系統(tǒng)還有下列優(yōu)點(diǎn)： (1) 允許用戶地址空間大于實(shí)際內(nèi)存空間， 為多道程序運(yùn)行提供了有力的支持。 (2) 便于動(dòng)態(tài)連接， 從而可避免靜態(tài)連接所造成的某些時(shí)間和空間的浪費(fèi)。 但段式虛擬存儲(chǔ)仍有不

51、少缺點(diǎn)， 除具有與請(qǐng)頁(yè)式系統(tǒng)相同的缺點(diǎn)(如提高硬件成本， 增加軟件的時(shí)間、 空間開(kāi)銷以及系統(tǒng)復(fù)雜性等)外， 還有以下缺點(diǎn)： (1) 在外存中管理可變尺寸的分段有不少困難； (2) 每個(gè)分段的大小受內(nèi)存容量的限制； (3) 對(duì)分段的置換， 有可能造成系統(tǒng)抖動(dòng)。 4.11 段頁(yè)式結(jié)合系統(tǒng) 分頁(yè)和分段方式各有優(yōu)點(diǎn)和缺點(diǎn)， 將二者結(jié)合起來(lái)可以取長(zhǎng)補(bǔ)短， 提高性能。 最常用的方式是段頁(yè)式， 其基本思想是： （1） 程序地址表示由三部分組成： 段號(hào)s、 頁(yè)號(hào)p和頁(yè)內(nèi)位移d， 即v=(s, p， d)。 這樣， 面向用戶的地址空間是段式劃分, 而面向物理實(shí)現(xiàn)的地址空間是頁(yè)式劃分。 (2) 地址轉(zhuǎn)換過(guò)程是：

52、每個(gè)進(jìn)程有一個(gè)段表， 每段都有單獨(dú)的一個(gè)頁(yè)表。 每段受段表項(xiàng)中段長(zhǎng)度的限制， 這樣頁(yè)表不必全部填滿， 實(shí)際需要多少就開(kāi)辟多少表項(xiàng)。 另外， 每段的最后一頁(yè)不一定是滿的， 平均起來(lái)每段有半頁(yè)大小的內(nèi)部碎片。 利用段號(hào)去查段表， 得到該段的頁(yè)表的起始地址； 利用這個(gè)地址和頁(yè)號(hào)去查頁(yè)表， 得到相應(yīng)的塊號(hào)。 最后， 塊號(hào)和頁(yè)內(nèi)位移拼接在一起， 形成訪問(wèn)內(nèi)存地址， 如圖4-43所示。圖4-43 段頁(yè)式系統(tǒng)的地址轉(zhuǎn)換機(jī)構(gòu)4.12 Linux系統(tǒng)的存儲(chǔ)管理 4.12.1 Linux的多級(jí)頁(yè)表 在x86平臺(tái)的Linux系統(tǒng)中， 地址碼采用32位， 因而每個(gè)進(jìn)程的虛存空間可達(dá)4 GB。 Linux內(nèi)核將這4 G

53、B的空間分為兩部分： 最高地址的1 GB是“系統(tǒng)空間”， 供內(nèi)核本身使用； 而較低地址的3 GB是各個(gè)進(jìn)程的“用戶空間”。 系統(tǒng)空間由所有進(jìn)程共享。 雖然理論上每個(gè)進(jìn)程的可用用戶空間都是3 GB， 但實(shí)際的存儲(chǔ)空間大小要受到物理存儲(chǔ)器(包括內(nèi)存以及磁盤交換區(qū)或交換文件)的限制。 進(jìn)程的虛存空間如圖4-44所示。圖4-44 Linux進(jìn)程的虛存空間 由于Linux系統(tǒng)中頁(yè)面的大小為4 KB， 因此進(jìn)程虛存空間要?jiǎng)澐譃? M個(gè)頁(yè)面。 如果直接用頁(yè)表描述這種映射關(guān)系， 那么每個(gè)進(jìn)程的頁(yè)表就要有1 M個(gè)表項(xiàng)。 很顯然， 用大量的內(nèi)存資源來(lái)存放頁(yè)表的辦法是不可取的。 為此， Linux系統(tǒng)采用三級(jí)頁(yè)表的

54、方式， 如圖4-45所示。 圖4-45 三級(jí)頁(yè)表地址映射示意圖 把一個(gè)線性地址映射成物理地址就分為以下四步： (1) 以線性地址中最高位段作為下標(biāo)在PGD中找到相應(yīng)的表項(xiàng)， 該表項(xiàng)指向相應(yīng)的PMD。 (2) 以線性地址中第二個(gè)位段作為下標(biāo)在PMD中找到相應(yīng)的表項(xiàng)， 該表項(xiàng)指向相應(yīng)的PT。 (3) 以線性地址中第三個(gè)位段作為下標(biāo)在PT中找到相應(yīng)的表項(xiàng)， 該表項(xiàng)指向相應(yīng)的物理頁(yè)面(即該物理頁(yè)面的起始地址)。 (4) 線性地址中的最低位段是在物理頁(yè)面內(nèi)的相對(duì)位移量， 此位移量與該物理頁(yè)面的起始地址相加就得到相應(yīng)的物理地址。 4.12.2 內(nèi)存頁(yè)的分配與釋放 當(dāng)一個(gè)進(jìn)程開(kāi)始運(yùn)行時(shí)， 系統(tǒng)要為其分配一些

55、內(nèi)存頁(yè)； 而當(dāng)該進(jìn)程結(jié)束運(yùn)行時(shí)， 要釋放其所占用的內(nèi)存頁(yè)。 一般來(lái)說(shuō)， Linux系統(tǒng)采用兩種方法來(lái)管理內(nèi)存頁(yè)： 位圖和鏈表。 利用位圖可以記錄內(nèi)存單元的使用情況。 用一個(gè)二進(jìn)制位(bit)記錄一個(gè)內(nèi)存頁(yè)的使用情況： 如果該內(nèi)存頁(yè)是空閑的， 則對(duì)應(yīng)的位是1； 如果該內(nèi)存頁(yè)已經(jīng)分配出去， 則對(duì)應(yīng)的位是0。 Linux系統(tǒng)的物理內(nèi)存頁(yè)分配采用鏈表和位圖相結(jié)合的方法， 如圖4-46所示。 圖中數(shù)組free_area的每一項(xiàng)描述某一種內(nèi)存頁(yè)組(即由相鄰的空閑內(nèi)存頁(yè)構(gòu)成的組)的使用狀態(tài)信息。 其中， 頭一個(gè)元素描述孤立出現(xiàn)的單個(gè)內(nèi)存頁(yè)的信息， 第二個(gè)元素描述以兩個(gè)連續(xù)內(nèi)存頁(yè)為一組的頁(yè)組的信息， 而第三個(gè)

56、元素描述以四個(gè)內(nèi)存頁(yè)為一組的頁(yè)組的信息， 以此類推， 頁(yè)組中內(nèi)存頁(yè)的數(shù)量依次按2的倍數(shù)遞增。 圖4-46 空閑內(nèi)存的組織示意圖 4.12.3 內(nèi)存交換 當(dāng)系統(tǒng)中出現(xiàn)內(nèi)存不足時(shí)， Linux內(nèi)存管理子系統(tǒng)就需要釋放一些內(nèi)存頁(yè)， 從而增加系統(tǒng)中空閑內(nèi)存頁(yè)的數(shù)量。 此任務(wù)是由內(nèi)核的交換守護(hù)進(jìn)程kswapd完成的。 kswapd有自己的進(jìn)程控制塊task_struct結(jié)構(gòu)， 它與其他進(jìn)程一樣受內(nèi)核的調(diào)度。 為了決定是否需要回收一些內(nèi)存頁(yè)， 系統(tǒng)中設(shè)置兩個(gè)量分別表示上限值和下限值。 如果空閑的內(nèi)存頁(yè)數(shù)量大于上限值， 則交換守護(hù)進(jìn)程就不做任何事情， 而進(jìn)入睡眠狀態(tài)； 如果系統(tǒng)中的空閑內(nèi)存頁(yè)數(shù)量低于上限值，

57、 甚至低于下限值， 則交換進(jìn)程將用以下三種辦法減少系統(tǒng)正在使用的內(nèi)存頁(yè)數(shù)： (1) 減少緩沖區(qū)和頁(yè)高速緩存的大小。 如果不再需要這些緩存中包含的某些頁(yè)面， 則釋放它們， 使之成為空閑的內(nèi)存頁(yè)。 (2) 把System V的共享內(nèi)存頁(yè)(實(shí)際是一種進(jìn)程間通信機(jī)制)交換到交換文件， 從而釋放出物理內(nèi)存。 (3) 將頁(yè)面換出物理內(nèi)存或者直接拋棄它們。 習(xí) 題 1. 說(shuō)明邏輯地址和物理地址之間的區(qū)別。 2. 什么是連接？ 它的作用是什么？ 3. 什么是重定位？ 它分為哪幾類？ 它們之間的差別是什么？ 4. 什么是地址空間和存儲(chǔ)空間？ 這兩種空間的隔離對(duì)多道程序設(shè)計(jì)有什么作用？ 它們之間是用什么方法轉(zhuǎn)換的

58、？ 5. 存儲(chǔ)管理的功能主要包括哪些方面？ 6. 解釋下列分區(qū)分配算法： （1） 最先適應(yīng)算法； （2） 最佳適應(yīng)算法。 7. 設(shè)一個(gè)邏輯地址空間有8頁(yè)， 每頁(yè)1024個(gè)字節(jié)， 映像到有32塊的物理內(nèi)存上。 （1） 邏輯地址需要用多少位表示？ （2） 物理地址需要用多少位表示？ 8. 假設(shè)一個(gè)分頁(yè)系統(tǒng)的頁(yè)表存放在內(nèi)存中： （1） 如果一次內(nèi)存訪問(wèn)需要花費(fèi)1.2 s， 那么存取一次數(shù)據(jù)至少要多少時(shí)間？ （2） 如果我們?cè)黾?個(gè)聯(lián)想存儲(chǔ)器， 其命中率可達(dá)75%， 那么有效內(nèi)存訪問(wèn)時(shí)間是多少（若在聯(lián)想存儲(chǔ)器中找到該頁(yè)表項(xiàng)， 則認(rèn)為在聯(lián)想存儲(chǔ)器中查找時(shí)間為0）？ 9. 說(shuō)明內(nèi)部碎片和外部碎片之間的不同。 10. 什么是虛擬存儲(chǔ)器？ 引入虛擬存儲(chǔ)器的主要目的是什么？ 虛擬存儲(chǔ)器有何特征？ 11.