計(jì)算機(jī)操作系統(tǒng)第5章

1、1 1第五章 虛 擬 存 儲(chǔ) 器第五章第五章 虛虛 擬擬 存存 儲(chǔ)儲(chǔ) 器器5.1 虛擬存儲(chǔ)器概述5.2 請(qǐng)求分頁(yè)存儲(chǔ)管理方式5.3 頁(yè)面置換算法5.4 “抖動(dòng)”與工作集5.5 請(qǐng)求分段存儲(chǔ)管理方式習(xí)題2 2第五章 虛 擬 存 儲(chǔ) 器5.1 虛擬存儲(chǔ)器概述第四章所介紹的各種存儲(chǔ)器管理方式有一個(gè)共同的特點(diǎn)，即它們都要求將一個(gè)作業(yè)全部裝入內(nèi)存后方能運(yùn)行。于是，出現(xiàn)了下面這樣兩種情況：(1) 有的作業(yè)很大，其所要求的內(nèi)存空間超過了內(nèi)存總?cè)萘?，作業(yè)不能全部被裝入內(nèi)存，致使該作業(yè)無法運(yùn)行；(2) 有大量作業(yè)要求運(yùn)行，但由于內(nèi)存容量不足以容納所有這些作業(yè)，只能將少數(shù)作業(yè)裝入內(nèi)存讓它們先運(yùn)行，而將其它大量的作

2、業(yè)留在外存上等待。3 3第五章 虛 擬 存 儲(chǔ) 器5.1.1 常規(guī)存儲(chǔ)管理方式的特征和局部性原理1. 常規(guī)存儲(chǔ)器管理方式的特征我們把前一章中所介紹的各種存儲(chǔ)器管理方式統(tǒng)稱為傳統(tǒng)存儲(chǔ)器管理方式，它們?nèi)季哂腥缦聝蓚€(gè)共同的特征：(1) 一次性(2) 駐留性 4 4第五章 虛 擬 存 儲(chǔ) 器2. 局部性原理程序運(yùn)行時(shí)存在的局部性現(xiàn)象，很早就已被人發(fā)現(xiàn)，但直到1968年，P.Denning才真正指出：程序在執(zhí)行時(shí)將呈現(xiàn)出局部性規(guī)律，即在一較短的時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分，相應(yīng)地，它所訪問的存儲(chǔ)空間也局限于某個(gè)區(qū)域。 5 5第五章 虛 擬 存 儲(chǔ) 器局限性又表現(xiàn)在下述兩個(gè)方面：(1) 時(shí)間局限性

3、。(2) 空間局限性。 6 6第五章 虛 擬 存 儲(chǔ) 器3. 虛擬存儲(chǔ)器的基本工作情況 基于局部性原理可知，應(yīng)用程序在運(yùn)行之前沒有必要將之全部裝入內(nèi)存，而僅須將那些當(dāng)前要運(yùn)行的少數(shù)頁(yè)面或段先裝入內(nèi)存便可運(yùn)行，其余部分暫留在盤上。 7 7第五章 虛 擬 存 儲(chǔ) 器5.1.2 虛擬存儲(chǔ)器的定義和特征1. 虛擬存儲(chǔ)器的定義當(dāng)用戶看到自己的程序能在系統(tǒng)中正常運(yùn)行時(shí)，他會(huì)認(rèn)為，該系統(tǒng)所具有的內(nèi)存容量一定比自己的程序大，或者說，用戶所感覺到的內(nèi)存容量會(huì)比實(shí)際內(nèi)存容量大得多。但用戶所看到的大容量只是一種錯(cuò)覺，是虛的，故人們把這樣的存儲(chǔ)器稱為虛擬存儲(chǔ)器。8 8第五章 虛 擬 存 儲(chǔ) 器2. 虛擬存儲(chǔ)器的特征與

4、傳統(tǒng)的存儲(chǔ)器管理方式比較，虛擬存儲(chǔ)器具有以下三個(gè)重要特征：(1) 多次性。(2) 對(duì)換性。(3) 虛擬性。 9 9第五章 虛 擬 存 儲(chǔ) 器5.1.3 虛擬存儲(chǔ)器的實(shí)現(xiàn)方法1. 分頁(yè)請(qǐng)求系統(tǒng)1) 硬件支持主要的硬件支持有：(1) 請(qǐng)求分頁(yè)的頁(yè)表機(jī)制。(2) 缺頁(yè)中斷機(jī)構(gòu)。(3) 地址變換機(jī)構(gòu)。2) 實(shí)現(xiàn)請(qǐng)求分頁(yè)的軟件10 10第五章 虛 擬 存 儲(chǔ) 器2. 請(qǐng)求分段系統(tǒng)1) 硬件支持主要的硬件支持有：(1) 請(qǐng)求分段的段表機(jī)制。(2) 缺頁(yè)中斷機(jī)構(gòu)。(3) 地址變換機(jī)構(gòu)。2) 軟件支持11 11第五章 虛 擬 存 儲(chǔ) 器5.2 請(qǐng)求分頁(yè)存儲(chǔ)管理方式5.2.1 請(qǐng)求分頁(yè)中的硬件支持為了實(shí)現(xiàn)請(qǐng)求分

5、頁(yè)，系統(tǒng)必須提供一定的硬件支持。計(jì)算機(jī)系統(tǒng)除了要求一定容量的內(nèi)存和外存外，還需要有請(qǐng)求頁(yè)表機(jī)制、缺頁(yè)中斷機(jī)構(gòu)以及地址變換機(jī)構(gòu)。12 12第五章 虛 擬 存 儲(chǔ) 器1. 請(qǐng)求頁(yè)表機(jī)制在請(qǐng)求分頁(yè)系統(tǒng)中需要的主要數(shù)據(jù)結(jié)構(gòu)是請(qǐng)求頁(yè)表，其基本作用仍然是將用戶地址空間中的邏輯地址映射為內(nèi)存空間中的物理地址。為了滿足頁(yè)面換進(jìn)換出的需要，在請(qǐng)求頁(yè)表中又增加了四個(gè)字段。這樣，在請(qǐng)求分頁(yè)系統(tǒng)中的每個(gè)頁(yè)表應(yīng)含以下諸項(xiàng)：13 13第五章 虛 擬 存 儲(chǔ) 器2. 缺頁(yè)中斷機(jī)構(gòu)(1) 在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)。(2) 一條指令在執(zhí)行期間可能產(chǎn)生多次缺頁(yè)中斷。14 14第五章 虛 擬 存 儲(chǔ) 器圖5-1 涉及6次缺

6、頁(yè)中斷的指令15 15第五章 虛 擬 存 儲(chǔ) 器3. 地址變換機(jī)構(gòu)請(qǐng)求分頁(yè)系統(tǒng)中的地址變換機(jī)構(gòu)是在分頁(yè)系統(tǒng)地址變換機(jī)構(gòu)的基礎(chǔ)上，為實(shí)現(xiàn)虛擬存儲(chǔ)器，再增加了某些功能所形成的，如產(chǎn)生和處理缺頁(yè)中斷，以及從內(nèi)存中換出一頁(yè)的功能等等。圖5-2示出了請(qǐng)求分頁(yè)系統(tǒng)中的地址變換過程。16 16第五章 虛 擬 存 儲(chǔ) 器圖5-2請(qǐng)求分頁(yè)中的地址變換過程17 17第五章 虛 擬 存 儲(chǔ) 器5.2.2 請(qǐng)求分頁(yè)中的內(nèi)存分配1. 最小物理塊數(shù)的確定一個(gè)顯而易見的事實(shí)是，隨著為每個(gè)進(jìn)程所分配的物理塊的減少，將使進(jìn)程在執(zhí)行中的缺頁(yè)率上升，從而會(huì)降低進(jìn)程的執(zhí)行速度。為使進(jìn)程能有效地工作，應(yīng)為它分配一定數(shù)目的物理塊，但這并

7、不是最小物理塊數(shù)的概念。18 18第五章 虛 擬 存 儲(chǔ) 器2. 內(nèi)存分配策略在請(qǐng)求分頁(yè)系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可變分配策略。在進(jìn)行置換時(shí)，也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。1) 固定分配局部置換(Fixed Allocation，Local Replacement)2) 可變分配全局置換(Variable Allocation，Global Replacement)3) 可變分配局部置換(Variable Allocation，Local Replacement)19 19第五章 虛 擬 存 儲(chǔ) 器3. 物理塊分配算法在采用固定分配策略時(shí)

8、，如何將系統(tǒng)中可供分配的所有物理塊分配給各個(gè)進(jìn)程，可采用下述幾種算法：(1) 平均分配算法，即將系統(tǒng)中所有可供分配的物理塊平均分配給各個(gè)進(jìn)程。 (2) 按比例分配算法，即根據(jù)進(jìn)程的大小按比例分配物理塊。如果系統(tǒng)中共有n個(gè)進(jìn)程，每個(gè)進(jìn)程的頁(yè)面數(shù)為Si，則系統(tǒng)中各進(jìn)程頁(yè)面數(shù)的總和為：n1iiSS2020第五章 虛 擬 存 儲(chǔ) 器又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個(gè)進(jìn)程所能分到的物理塊數(shù)為bi可由下式計(jì)算：這里，bi應(yīng)該取整，它必須大于最小物理塊數(shù)。mSSbii21 21第五章 虛 擬 存 儲(chǔ) 器(3) 考慮優(yōu)先權(quán)的分配算法。在實(shí)際應(yīng)用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成，應(yīng)為它分配較多

9、的內(nèi)存空間。通常采取的方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)進(jìn)行分配，為高優(yōu)先進(jìn)程適當(dāng)?shù)卦黾悠湎鄳?yīng)份額。在有的系統(tǒng)中，如重要的實(shí)時(shí)控制系統(tǒng)，則可能是完全按優(yōu)先權(quán)為各進(jìn)程分配其物理塊的。2222第五章 虛 擬 存 儲(chǔ) 器5.2.3 頁(yè)面調(diào)入策略為使進(jìn)程能夠正常運(yùn)行，必須事先將要執(zhí)行的那部分程序和數(shù)據(jù)所在的頁(yè)面調(diào)入內(nèi)存?，F(xiàn)在的問題是：(1) 系統(tǒng)應(yīng)在何時(shí)調(diào)入所需頁(yè)面；(2) 系統(tǒng)應(yīng)從何處調(diào)入這些頁(yè)面；(3) 是如何進(jìn)行調(diào)入的。2323第五章 虛 擬 存 儲(chǔ) 器1. 何時(shí)調(diào)入頁(yè)面(1) 預(yù)調(diào)頁(yè)策略。(2) 請(qǐng)求調(diào)頁(yè)策略。 2424第五章

10、 虛 擬 存 儲(chǔ) 器2. 從何處調(diào)入頁(yè)面(1) 系統(tǒng)擁有足夠的對(duì)換區(qū)空間，這時(shí)可以全部從對(duì)換區(qū)調(diào)入所需頁(yè)面，以提高調(diào)頁(yè)速度。(2) 系統(tǒng)缺少足夠的對(duì)換區(qū)空間，這時(shí)凡是不會(huì)被修改的文件，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁(yè)面時(shí)，由于它們未被修改，則不必再將它們重寫到磁盤(換出)，以后再調(diào)入時(shí)，仍從文件區(qū)直接調(diào)入。但對(duì)于那些可能被修改的部分，在將它們換出時(shí)便須調(diào)到對(duì)換區(qū)，以后需要時(shí)再?gòu)膶?duì)換區(qū)調(diào)入。(3) UNIX方式。 2525第五章 虛 擬 存 儲(chǔ) 器3. 頁(yè)面調(diào)入過程每當(dāng)程序所要訪問的頁(yè)面未在內(nèi)存時(shí)(存在位為“0”)，便向CPU發(fā)出一缺頁(yè)中斷，中斷處理程序首先保留CPU環(huán)境，分析中斷原因后轉(zhuǎn)入缺

11、頁(yè)中斷處理程序。 2626第五章 虛 擬 存 儲(chǔ) 器4. 缺頁(yè)率假設(shè)一個(gè)進(jìn)程的邏輯空間為n頁(yè)，系統(tǒng)為其分配的內(nèi)存物理塊數(shù)為m(mn)。如果在進(jìn)程的運(yùn)行過程中，訪問頁(yè)面成功(即所訪問頁(yè)面在內(nèi)存中)的次數(shù)為S，訪問頁(yè)面失敗(即所訪問頁(yè)面不在內(nèi)存中，需要從外存調(diào)入)的次數(shù)為F，則該進(jìn)程總的頁(yè)面訪問次數(shù)為A=S+F，那么該進(jìn)程在其運(yùn)行過程中的缺頁(yè)率即為AFf 2727第五章 虛 擬 存 儲(chǔ) 器事實(shí)上，在缺頁(yè)中斷處理時(shí)，當(dāng)由于空間不足，需要置換部分頁(yè)面到外存時(shí)，選擇被置換頁(yè)面還需要考慮到置換的代價(jià)，如頁(yè)面是否被修改過。沒有修改過的頁(yè)面可以直接放棄，而修改過的頁(yè)面則必須進(jìn)行保存，所以處理這兩種情況時(shí)的時(shí)間

12、也是不同的。假設(shè)被置換的頁(yè)面被修改的概率是，其缺頁(yè)中斷處理時(shí)間為ta，被置換頁(yè)面沒有被修改的缺頁(yè)中斷時(shí)間為tb，那么，缺頁(yè)中斷處理時(shí)間的計(jì)算公式為t=ta+(1)tb2828第五章 虛 擬 存 儲(chǔ) 器5.3 頁(yè)面置換算法在進(jìn)程運(yùn)行過程中，若其所要訪問的頁(yè)面不在內(nèi)存，而需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時(shí)，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)送到磁盤的對(duì)換區(qū)中。但應(yīng)將哪個(gè)頁(yè)面調(diào)出，須根據(jù)一定的算法來確定。通常，把選擇換出頁(yè)面的算法稱為頁(yè)面置換算法(Page-Replacement Algorithms)。置換算法的好壞將直接影響到系統(tǒng)的性能。2929第五章 虛 擬 存

13、儲(chǔ) 器5.3.1 最佳置換算法和先進(jìn)先出置換算法1. 最佳(Optimal)置換算法最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁(yè)面將是以后永不使用的，或許是在最長(zhǎng)(未來)時(shí)間內(nèi)不再被訪問的頁(yè)面。采用最佳置換算法通?？杀ＷC獲得最低的缺頁(yè)率。但由于人們目前還無法預(yù)知，一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁(yè)面中，哪一個(gè)頁(yè)面是未來最長(zhǎng)時(shí)間內(nèi)不再被訪問的，因而該算法是無法實(shí)現(xiàn)的，但可以利用該算法去評(píng)價(jià)其它算法。 3030第五章 虛 擬 存 儲(chǔ) 器圖5-3利用最佳頁(yè)面置換算法時(shí)的置換圖31 31第五章 虛 擬 存 儲(chǔ) 器2. 先進(jìn)先出(FIFO)頁(yè)面置換算法FIFO算法是最早出現(xiàn)的

14、置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單，只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使它總是指向最老的頁(yè)面。但該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵谶M(jìn)程中，有些頁(yè)面經(jīng)常被訪問，比如，含有全局變量、常用函數(shù)、例程等的頁(yè)面，F(xiàn)IFO算法并不能保證這些頁(yè)面不被淘汰。3232第五章 虛 擬 存 儲(chǔ) 器圖5-4 利用FIFO置換算法時(shí)的置換圖3333第五章 虛 擬 存 儲(chǔ) 器5.3.2 最近最久未使用和最少使用置換算法1. LRU(Least Recently Used)置換算法的描述FIFO置換

15、算法的性能之所以較差，是因?yàn)樗罁?jù)的條件是各個(gè)頁(yè)面調(diào)入內(nèi)存的時(shí)間，而頁(yè)面調(diào)入的先后并不能反映頁(yè)面的使用情況。最近最久未使用(LRU)的頁(yè)面置換算法是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況做出決策的。 3434第五章 虛 擬 存 儲(chǔ) 器圖5-5LRU頁(yè)面置換算法3535第五章 虛 擬 存 儲(chǔ) 器2. LRU置換算法的硬件支持1) 寄存器為了記錄某進(jìn)程在內(nèi)存中各頁(yè)的使用情況，須為每個(gè)在內(nèi)存中的頁(yè)面配置一個(gè)移位寄存器，可表示為R=Rn-1Rn-2Rn-3 R2R1R03636第五章 虛 擬 存 儲(chǔ) 器當(dāng)進(jìn)程訪問某物理塊時(shí)，要將相應(yīng)寄存器的Rn-1位置成1。此時(shí)，定時(shí)信號(hào)將每隔一定時(shí)間(例如100 ms)將寄

16、存器右移一位。如果我們把n位寄存器的數(shù)看作是一個(gè)整數(shù)，那么，具有最小數(shù)值的寄存器所對(duì)應(yīng)的頁(yè)面，就是最近最久未使用的頁(yè)面。 3737第五章 虛 擬 存 儲(chǔ) 器圖5-6 某進(jìn)程具有8個(gè)頁(yè)面時(shí)的LRU訪問情況3838第五章 虛 擬 存 儲(chǔ) 器2) ?？衫靡粋€(gè)特殊的棧保存當(dāng)前使用的各個(gè)頁(yè)面的頁(yè)面號(hào)。每當(dāng)進(jìn)程訪問某頁(yè)面時(shí)，便將該頁(yè)面的頁(yè)面號(hào)從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁(yè)面的編號(hào)，而棧底則是最近最久未使用頁(yè)面的頁(yè)面號(hào)。假定現(xiàn)有一進(jìn)程，它分有五個(gè)物理塊，所訪問的頁(yè)面的頁(yè)面號(hào)序列為：4，7，0，7，1，0，1，2，1，2，63939第五章 虛 擬 存 儲(chǔ) 器圖5-7用棧保存當(dāng)前使用頁(yè)

17、面時(shí)棧的變化情況4040第五章 虛 擬 存 儲(chǔ) 器3. 最少使用(Least Frequently Used，LFU)置換算法在采用LFU算法時(shí)，應(yīng)為在內(nèi)存中的每個(gè)頁(yè)面設(shè)置一個(gè)移位寄存器，用來記錄該頁(yè)面被訪問的頻率。該置換算法選擇在最近時(shí)期使用最少的頁(yè)面作為淘汰頁(yè)。 41 41第五章 虛 擬 存 儲(chǔ) 器5.3.3 Clock置換算法1. 簡(jiǎn)單的Clock置換算法當(dāng)利用簡(jiǎn)單Clock算法時(shí)，只需為每頁(yè)設(shè)置一位訪問位，再將內(nèi)存中的所有頁(yè)面都通過鏈接指針鏈接成一個(gè)循環(huán)隊(duì)列。 4242第五章 虛 擬 存 儲(chǔ) 器圖5-8簡(jiǎn)單Clock置換算法的流程和示例4343第五章 虛 擬 存 儲(chǔ) 器2. 改進(jìn)型Cl

18、ock置換算法在將一個(gè)頁(yè)面換出時(shí)，如果該頁(yè)已被修改過，便須將該頁(yè)重新寫回到磁盤上；但如果該頁(yè)未被修改過，則不必將它拷回磁盤。換而言之，對(duì)于修改過的頁(yè)面，在換出時(shí)所付出的開銷比未修改過的頁(yè)面大，或者說，置換代價(jià)大。在改進(jìn)型Clock算法中，除須考慮頁(yè)面的使用情況外，還須再增加一個(gè)因素置換代價(jià)。 4444第五章 虛 擬 存 儲(chǔ) 器5.3.4 頁(yè)面緩沖算法(Page Buffering Algorithm，PBA)1. 影響頁(yè)面換進(jìn)換出效率的若干因素(1) 頁(yè)面置換算法。(2) 寫回磁盤的頻率。(3) 讀入內(nèi)存的頻率。 4545第五章 虛 擬 存 儲(chǔ) 器2. 頁(yè)面緩沖算法PBAPBA算法的主要特點(diǎn)是

19、： 顯著地降低了頁(yè)面換進(jìn)、換出的頻率，使磁盤I/O的操作次數(shù)大為減少，因而減少了頁(yè)面換進(jìn)、換出的開銷； 正是由于換入換出的開銷大幅度減小，才能使其采用一種較簡(jiǎn)單的置換策略，如先進(jìn)先出(FIFO)算法，它不需要特殊硬件的支持，實(shí)現(xiàn)起來非常簡(jiǎn)單。 1) 空閑頁(yè)面鏈表2) 修改頁(yè)面鏈表4646第五章 虛 擬 存 儲(chǔ) 器5.3.5 訪問內(nèi)存的有效時(shí)間與基本分頁(yè)存儲(chǔ)管理方式不同，在請(qǐng)求分頁(yè)管理方式中，內(nèi)存有效訪問時(shí)間不僅要考慮訪問頁(yè)表和訪問實(shí)際物理地址數(shù)據(jù)的時(shí)間，還必須要考慮到缺頁(yè)中斷的處理時(shí)間。 4747第五章 虛 擬 存 儲(chǔ) 器5.4 5.4 “抖動(dòng)”與工作集 由于請(qǐng)求分頁(yè)式虛擬存儲(chǔ)器系統(tǒng)的性能優(yōu)越

20、，在正常運(yùn)行情況下，它能有效地減少內(nèi)存碎片，提高處理機(jī)的利用率和吞吐量，故是目前最常用的一種系統(tǒng)。但如果在系統(tǒng)中運(yùn)行的進(jìn)程太多，進(jìn)程在運(yùn)行中會(huì)頻繁地發(fā)生缺頁(yè)情況，這又會(huì)對(duì)系統(tǒng)的性能產(chǎn)生很大的影響，故還須對(duì)請(qǐng)求分頁(yè)系統(tǒng)的性能做簡(jiǎn)單的分析。4848第五章 虛 擬 存 儲(chǔ) 器5.4.1 多道程序度與“抖動(dòng)”1. 多道程序度與處理機(jī)的利用率 由于虛擬存儲(chǔ)器系統(tǒng)能從邏輯上擴(kuò)大內(nèi)存，這時(shí)，只需裝入一個(gè)進(jìn)程的部分程序和數(shù)據(jù)便可開始運(yùn)行，故人們希望在系統(tǒng)中能運(yùn)行更多的進(jìn)程，即增加多道程序度，以提高處理機(jī)的利用率。但處理機(jī)的實(shí)際利用率卻如圖5-9中的實(shí)線所示。 4949第五章 虛 擬 存 儲(chǔ) 器圖5-9 處理機(jī)

21、的利用率5050第五章 虛 擬 存 儲(chǔ) 器2. 產(chǎn)生“抖動(dòng)”的原因發(fā)生“抖動(dòng)”的根本原因是，同時(shí)在系統(tǒng)中運(yùn)行的進(jìn)程太多，由此分配給每一個(gè)進(jìn)程的物理塊太少，不能滿足進(jìn)程正常運(yùn)行的基本要求，致使每個(gè)進(jìn)程在運(yùn)行時(shí)，頻繁地出現(xiàn)缺頁(yè)，必須請(qǐng)求系統(tǒng)將所缺之頁(yè)調(diào)入內(nèi)存。這會(huì)使得在系統(tǒng)中排隊(duì)等待頁(yè)面調(diào)進(jìn)/調(diào)出的進(jìn)程數(shù)目增加。顯然，對(duì)磁盤的有效訪問時(shí)間也隨之急劇增加，造成每個(gè)進(jìn)程的大部分時(shí)間都用于頁(yè)面的換進(jìn)/換出，而幾乎不能再去做任何有效的工作，從而導(dǎo)致發(fā)生處理機(jī)的利用率急劇下降并趨于0的情況。我們稱此時(shí)的進(jìn)程是處于“抖動(dòng)”狀態(tài)。51 51第五章 虛 擬 存 儲(chǔ) 器5.4.2 工作集1. 工作集的基本概念進(jìn)程發(fā)

22、生缺頁(yè)率的時(shí)間間隔與進(jìn)程所獲得的物理塊數(shù)有關(guān)。圖5-10示出了缺頁(yè)率與物理塊數(shù)之間的關(guān)系。 5252第五章 虛 擬 存 儲(chǔ) 器圖5-10 缺頁(yè)率與物理塊數(shù)之間的關(guān)系5353第五章 虛 擬 存 儲(chǔ) 器2. 工作集的定義所謂工作集，是指在某段時(shí)間間隔里，進(jìn)程實(shí)際所要訪問頁(yè)面的集合。Denning指出，雖然程序只需要少量的幾頁(yè)在內(nèi)存便可運(yùn)行，但為了較少地產(chǎn)生缺頁(yè)，應(yīng)將程序的全部工作集裝入內(nèi)存中。然而我們無法事先預(yù)知程序在不同時(shí)刻將訪問哪些頁(yè)面，故仍只有像置換算法那樣，用程序的過去某段時(shí)間內(nèi)的行為作為程序在將來某段時(shí)間內(nèi)行為的近似。 5454第五章 虛 擬 存 儲(chǔ) 器圖5-11 窗口為3、4、5時(shí)進(jìn)程

23、的工作集5555第五章 虛 擬 存 儲(chǔ) 器5.4.3 “抖動(dòng)”的預(yù)防方法1. 采取局部置換策略在頁(yè)面分配和置換策略中，如果采取的是可變分配方式，則為了預(yù)防發(fā)生“抖動(dòng)”，可采取局部置換策略。 5656第五章 虛 擬 存 儲(chǔ) 器2. 把工作集算法融入到處理機(jī)調(diào)度中當(dāng)調(diào)度程序發(fā)現(xiàn)處理機(jī)利用率低下時(shí)，它將試圖從外存調(diào)入一個(gè)新作業(yè)進(jìn)入內(nèi)存，來改善處理機(jī)的利用率。 5757第五章 虛 擬 存 儲(chǔ) 器3. 利用“L=S”準(zhǔn)則調(diào)節(jié)缺頁(yè)率Denning于1980年提出了“L=S”的準(zhǔn)則來調(diào)節(jié)多道程序度，其中L是缺頁(yè)之間的平均時(shí)間，S是平均缺頁(yè)服務(wù)時(shí)間，即用于置換一個(gè)頁(yè)面所需的時(shí)間。如果是L遠(yuǎn)比S大，說明很少發(fā)生

24、缺頁(yè)，磁盤的能力尚未得到充分的利用；反之，如果是L比S小，則說明頻繁發(fā)生缺頁(yè)，缺頁(yè)的速度已超過磁盤的處理能力。只有當(dāng)L與S接近時(shí)，磁盤和處理機(jī)都可達(dá)到它們的最大利用率。理論和實(shí)踐都已證明，利用“L=S”準(zhǔn)則，對(duì)于調(diào)節(jié)缺頁(yè)率是十分有效的。5858第五章 虛 擬 存 儲(chǔ) 器4. 選擇暫停的進(jìn)程當(dāng)多道程序度偏高時(shí)，已影響到處理機(jī)的利用率，為了防止發(fā)生“抖動(dòng)”，系統(tǒng)必須減少多道程序的數(shù)目。 5959第五章 虛 擬 存 儲(chǔ) 器 5.5 請(qǐng)求分段存儲(chǔ)管理方式5.5.1 請(qǐng)求分段中的硬件支持為了實(shí)現(xiàn)請(qǐng)求分段式存儲(chǔ)管理，應(yīng)在系統(tǒng)中配置多種硬件機(jī)構(gòu)，以支持快速地完成請(qǐng)求分段功能。與請(qǐng)求分頁(yè)系統(tǒng)相似，在請(qǐng)求分段系

25、統(tǒng)中所需的硬件支持有段表機(jī)制、缺段中斷機(jī)構(gòu)，以及地址變換機(jī)構(gòu)。6060第五章 虛 擬 存 儲(chǔ) 器1. 請(qǐng)求段表機(jī)制在請(qǐng)求分段式管理中所需的主要數(shù)據(jù)結(jié)構(gòu)是請(qǐng)求段表。在該表中除了具有請(qǐng)求分頁(yè)機(jī)制中有的訪問字段A、修改位M、存在位P和外存始址四個(gè)字段外，還增加了存取方式字段和增補(bǔ)位。這些字段供程序在調(diào)進(jìn)、調(diào)出時(shí)參考。下面給出請(qǐng)求分段的段表項(xiàng)。61 61第五章 虛 擬 存 儲(chǔ) 器2. 缺段中斷機(jī)構(gòu)在請(qǐng)求分段系統(tǒng)中采用的是請(qǐng)求調(diào)段策略。每當(dāng)發(fā)現(xiàn)運(yùn)行進(jìn)程所要訪問的段尚未調(diào)入內(nèi)存時(shí)，便由缺段中斷機(jī)構(gòu)產(chǎn)生一缺段中斷信號(hào)，進(jìn)入OS后，由缺段中斷處理程序?qū)⑺璧亩握{(diào)入內(nèi)存。與缺頁(yè)中斷機(jī)構(gòu)類似，缺段中斷機(jī)構(gòu)同樣需要

26、在一條指令的執(zhí)行期間產(chǎn)生和處理中斷，以及在一條指令執(zhí)行期間，可能產(chǎn)生多次缺段中斷。但由于分段是信息的邏輯單位，因而不可能出現(xiàn)一條指令被分割在兩個(gè)分段中，和一組信息被分割在兩個(gè)分段中的情況。缺段中斷的處理過程如圖5-12所示。 6262第五章 虛 擬 存 儲(chǔ) 器圖5-12 請(qǐng)求分段系統(tǒng)中的中斷處理過程6363第五章 虛 擬 存 儲(chǔ) 器3. 地址變換機(jī)構(gòu)請(qǐng)求分段系統(tǒng)中的地址變換機(jī)構(gòu)是在分段系統(tǒng)地址變換機(jī)構(gòu)的基礎(chǔ)上形成的。因?yàn)楸辉L問的段并非全在內(nèi)存，所以在地址變換時(shí)，若發(fā)現(xiàn)所要訪問的段不在內(nèi)存，必須先將所缺的段調(diào)入內(nèi)存，并修改段表，然后才能再利用段表進(jìn)行地址變換。為此，在地址變換機(jī)構(gòu)中又增加了某些功

27、能，如缺段中斷的請(qǐng)求及處理等。圖5-13示出了請(qǐng)求分段系統(tǒng)的地址變換過程。6464第五章 虛 擬 存 儲(chǔ) 器圖5-13 請(qǐng)求分段系統(tǒng)的地址變換過程6565第五章 虛 擬 存 儲(chǔ) 器5.5.2 分段的共享與保護(hù)1. 共享段表(1) 共享進(jìn)程計(jì)數(shù)count。(2) 存取控制字段。(3) 段號(hào)。 6666第五章 虛 擬 存 儲(chǔ) 器圖5-14 共享段表項(xiàng)6767第五章 虛 擬 存 儲(chǔ) 器2. 共享段的分配與回收1) 共享段的分配2) 共享段的回收6868第五章 虛 擬 存 儲(chǔ) 器3. 分段保護(hù)在分段系統(tǒng)中，由于每個(gè)分段在邏輯上是相對(duì)獨(dú)立的，因而比較容易實(shí)現(xiàn)信息保護(hù)。目前，常采用以下幾種措施來確保信息的安全。1) 越界檢查2) 存取控制檢查3) 環(huán)保護(hù)機(jī)構(gòu)6969第五章 虛 擬 存 儲(chǔ) 器圖5-15 環(huán)保護(hù)機(jī)構(gòu)7070第五章 虛 擬 存 儲(chǔ) 器1、虛擬存儲(chǔ)器