計(jì)算機(jī)操作系統(tǒng)-虛擬存儲器課件

第五章虛擬存儲器5.1虛擬存儲器概述5.2請求分頁存儲管理方式5.3頁面置換算法5.4“抖動”與工作集5.5請求分段存儲管理方式習(xí)題ppt課件第五章虛擬存儲器5.1虛擬存儲器概述pp

5.1虛擬存儲器概述

第四章所介紹的各種存儲器管理方式有一個共同的特點(diǎn)，即它們都要求將一個作業(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)行，而將其它大量的作業(yè)留在外存上等待。ppt課件?5.1虛擬存儲器概述

第四章所介紹的各種5.1.1常規(guī)存儲管理方式的特征和局部性原理

1.常規(guī)存儲器管理方式的特征

我們把前一章中所介紹的各種存儲器管理方式統(tǒng)稱為傳統(tǒng)存儲器管理方式，它們?nèi)季哂腥缦聝蓚€共同的特征：

(1)一次性

(2)駐留性ppt課件5.1.1常規(guī)存儲管理方式的特征和局部性原理

1.

2.局部性原理

程序運(yùn)行時存在的局部性現(xiàn)象，很早就已被人發(fā)現(xiàn)，但直到1968年，P.Denning才真正指出：程序在執(zhí)行時將呈現(xiàn)出局部性規(guī)律，即在一較短的時間內(nèi)，程序的執(zhí)行僅局限于某個部分，相應(yīng)地，它所訪問的存儲空間也局限于某個區(qū)域。ppt課件2.局部性原理

程序運(yùn)行時存在的局部性現(xiàn)象，很早就局限性又表現(xiàn)在下述兩個方面：

(1)時間局限性。

(2)空間局限性。ppt課件局限性又表現(xiàn)在下述兩個方面：

(1)時間局限性。

3.虛擬存儲器的基本工作情況

基于局部性原理可知，應(yīng)用程序在運(yùn)行之前沒有必要將之全部裝入內(nèi)存，而僅須將那些當(dāng)前要運(yùn)行的少數(shù)頁面或段先裝入內(nèi)存便可運(yùn)行，其余部分暫留在盤上。ppt課件3.虛擬存儲器的基本工作情況

基于局部性原理可知5.1.2虛擬存儲器的定義和特征

1.虛擬存儲器的定義

當(dāng)用戶看到自己的程序能在系統(tǒng)中正常運(yùn)行時，他會認(rèn)為，該系統(tǒng)所具有的內(nèi)存容量一定比自己的程序大，或者說，用戶所感覺到的內(nèi)存容量會比實(shí)際內(nèi)存容量大得多。但用戶所看到的大容量只是一種錯覺，是虛的，故人們把這樣的存儲器稱為虛擬存儲器。ppt課件5.1.2虛擬存儲器的定義和特征

1.虛擬存儲器的

2.虛擬存儲器的特征

與傳統(tǒng)的存儲器管理方式比較，虛擬存儲器具有以下三個重要特征：

(1)多次性。

(2)對換性。

(3)虛擬性。ppt課件2.虛擬存儲器的特征

與傳統(tǒng)的存儲器管理方式比較，5.1.3虛擬存儲器的實(shí)現(xiàn)方法

1.分頁請求系統(tǒng)

1)硬件支持

主要的硬件支持有：

(1)請求分頁的頁表機(jī)制。

(2)缺頁中斷機(jī)構(gòu)。

(3)地址變換機(jī)構(gòu)。

2)實(shí)現(xiàn)請求分頁的軟件

ppt課件5.1.3虛擬存儲器的實(shí)現(xiàn)方法

1.分頁請求系統(tǒng)

2.請求分段系統(tǒng)

1)硬件支持

主要的硬件支持有：

(1)請求分段的段表機(jī)制。

(2)缺頁中斷機(jī)構(gòu)。

(3)地址變換機(jī)構(gòu)。

2)軟件支持

ppt課件2.請求分段系統(tǒng)

1)硬件支持

主要的硬件支

5.2請求分頁存儲管理方式

5.2.1請求分頁中的硬件支持

為了實(shí)現(xiàn)請求分頁，系統(tǒng)必須提供一定的硬件支持。計(jì)算機(jī)系統(tǒng)除了要求一定容量的內(nèi)存和外存外，還需要有請求頁表機(jī)制、缺頁中斷機(jī)構(gòu)以及地址變換機(jī)構(gòu)。ppt課件?5.2請求分頁存儲管理方式

5.2.1請

1.請求頁表機(jī)制

在請求分頁系統(tǒng)中需要的主要數(shù)據(jù)結(jié)構(gòu)是請求頁表，其基本作用仍然是將用戶地址空間中的邏輯地址映射為內(nèi)存空間中的物理地址。為了滿足頁面換進(jìn)換出的需要，在請求頁表中又增加了四個字段。這樣，在請求分頁系統(tǒng)中的每個頁表應(yīng)含以下諸項(xiàng)：ppt課件1.請求頁表機(jī)制

在請求分頁系統(tǒng)中需要的主要數(shù)據(jù)結(jié)

2.缺頁中斷機(jī)構(gòu)

(1)在指令執(zhí)行期間產(chǎn)生和處理中斷信號。

(2)一條指令在執(zhí)行期間可能產(chǎn)生多次缺頁中斷。ppt課件2.缺頁中斷機(jī)構(gòu)

(1)在指令執(zhí)行期間產(chǎn)生和處理圖5-1涉及6次缺頁中斷的指令ppt課件圖5-1涉及6次缺頁中斷的指令ppt課件

3.地址變換機(jī)構(gòu)

請求分頁系統(tǒng)中的地址變換機(jī)構(gòu)是在分頁系統(tǒng)地址變換機(jī)構(gòu)的基礎(chǔ)上，為實(shí)現(xiàn)虛擬存儲器，再增加了某些功能所形成的，如產(chǎn)生和處理缺頁中斷，以及從內(nèi)存中換出一頁的功能等等。圖5-2示出了請求分頁系統(tǒng)中的地址變換過程。ppt課件3.地址變換機(jī)構(gòu)

請求分頁系統(tǒng)中的地址變換機(jī)構(gòu)是在圖5-2請求分頁中的地址變換過程ppt課件圖5-2請求分頁中的地址變換過程ppt課件5.2.2請求分頁中的內(nèi)存分配

1.最小物理塊數(shù)的確定

一個顯而易見的事實(shí)是，隨著為每個進(jìn)程所分配的物理塊的減少，將使進(jìn)程在執(zhí)行中的缺頁率上升，從而會降低進(jìn)程的執(zhí)行速度。為使進(jìn)程能有效地工作，應(yīng)為它分配一定數(shù)目的物理塊，但這并不是最小物理塊數(shù)的概念。ppt課件5.2.2請求分頁中的內(nèi)存分配

1.最小物理塊數(shù)的

2.內(nèi)存分配策略

在請求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可變分配策略。在進(jìn)行置換時，也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。

1)固定分配局部置換(FixedAllocation，LocalReplacement)

2)可變分配全局置換(VariableAllocation，GlobalReplacement)

3)可變分配局部置換(VariableAllocation，LocalReplacement)

ppt課件2.內(nèi)存分配策略

在請求分頁系統(tǒng)中，可采取兩種內(nèi)存

3.物理塊分配算法

在采用固定分配策略時，如何將系統(tǒng)中可供分配的所有物理塊分配給各個進(jìn)程，可采用下述幾種算法：

(1)平均分配算法，即將系統(tǒng)中所有可供分配的物理塊平均分配給各個進(jìn)程。

(2)按比例分配算法，即根據(jù)進(jìn)程的大小按比例分配物理塊。如果系統(tǒng)中共有n個進(jìn)程，每個進(jìn)程的頁面數(shù)為Si，

則系統(tǒng)中各進(jìn)程頁面數(shù)的總和為：ppt課件3.物理塊分配算法

在采用固定分配策略時，如何將系又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個進(jìn)程所能分到的物理塊數(shù)為bi可由下式計(jì)算：

這里，bi應(yīng)該取整，它必須大于最小物理塊數(shù)。ppt課件又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個進(jìn)程所能分到的物

(3)考慮優(yōu)先權(quán)的分配算法。在實(shí)際應(yīng)用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成，應(yīng)為它分配較多的內(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í)時控制系統(tǒng)，則可能是完全按優(yōu)先權(quán)為各進(jìn)程分配其物理塊的。ppt課件(3)考慮優(yōu)先權(quán)的分配算法。在實(shí)際應(yīng)用中，為了照顧到重5.2.3頁面調(diào)入策略

為使進(jìn)程能夠正常運(yùn)行，必須事先將要執(zhí)行的那部分程序和數(shù)據(jù)所在的頁面調(diào)入內(nèi)存。現(xiàn)在的問題是：

(1)系統(tǒng)應(yīng)在何時調(diào)入所需頁面；

(2)系統(tǒng)應(yīng)從何處調(diào)入這些頁面；

(3)是如何進(jìn)行調(diào)入的。ppt課件5.2.3頁面調(diào)入策略

為使進(jìn)程能夠正常運(yùn)行，必須事

1.何時調(diào)入頁面

(1)預(yù)調(diào)頁策略。

(2)請求調(diào)頁策略。ppt課件1.何時調(diào)入頁面

(1)預(yù)調(diào)頁策略。

(2)

2.從何處調(diào)入頁面

(1)系統(tǒng)擁有足夠的對換區(qū)空間，這時可以全部從對換區(qū)調(diào)入所需頁面，以提高調(diào)頁速度。

(2)系統(tǒng)缺少足夠的對換區(qū)空間，這時凡是不會被修改的文件，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁面時，由于它們未被修改，則不必再將它們重寫到磁盤(換出)，以后再調(diào)入時，仍從文件區(qū)直接調(diào)入。但對于那些可能被修改的部分，在將它們換出時便須調(diào)到對換區(qū)，以后需要時再從對換區(qū)調(diào)入。

(3)?UNIX方式。ppt課件2.從何處調(diào)入頁面

(1)系統(tǒng)擁有足夠的對換區(qū)空

3.頁面調(diào)入過程

每當(dāng)程序所要訪問的頁面未在內(nèi)存時(存在位為“0”)，便向CPU發(fā)出一缺頁中斷，中斷處理程序首先保留CPU環(huán)境，分析中斷原因后轉(zhuǎn)入缺頁中斷處理程序。ppt課件3.頁面調(diào)入過程

每當(dāng)程序所要訪問的頁面未在內(nèi)存時

4.缺頁率

假設(shè)一個進(jìn)程的邏輯空間為n頁，系統(tǒng)為其分配的內(nèi)存物理塊數(shù)為m(m≤n)。如果在進(jìn)程的運(yùn)行過程中，訪問頁面成功(即所訪問頁面在內(nèi)存中)的次數(shù)為S，訪問頁面失敗(即所訪問頁面不在內(nèi)存中，需要從外存調(diào)入)的次數(shù)為F，則該進(jìn)程總的頁面訪問次數(shù)為A?=?S?+?F，那么該進(jìn)程在其運(yùn)行過程中的缺頁率即為ppt課件4.缺頁率

假設(shè)一個進(jìn)程的邏輯空間為n頁，系統(tǒng)為其事實(shí)上，在缺頁中斷處理時，當(dāng)由于空間不足，需要置換部分頁面到外存時，選擇被置換頁面還需要考慮到置換的代價(jià)，如頁面是否被修改過。沒有修改過的頁面可以直接放棄，而修改過的頁面則必須進(jìn)行保存，所以處理這兩種情況時的時間也是不同的。假設(shè)被置換的頁面被修改的概率是β，其缺頁中斷處理時間為ta，被置換頁面沒有被修改的缺頁中斷時間為tb，那么，缺頁中斷處理時間的計(jì)算公式為

t=β×ta+(1—β)×tbppt課件事實(shí)上，在缺頁中斷處理時，當(dāng)由于空間不足，需要置換部分頁

5.3頁面置換算法

在進(jìn)程運(yùn)行過程中，若其所要訪問的頁面不在內(nèi)存，而需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)送到磁盤的對換區(qū)中。但應(yīng)將哪個頁面調(diào)出，須根據(jù)一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面置換算法(ReplacementAlgorithms)。置換算法的好壞將直接影響到系統(tǒng)的性能。ppt課件?5.3頁面置換算法

在進(jìn)程運(yùn)行過程中，5.3.1最佳置換算法和先進(jìn)先出置換算法

1.最佳(Optimal)置換算法

最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面將是以后永不使用的，或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法通常可保證獲得最低的缺頁率。但由于人們目前還無法預(yù)知，一個進(jìn)程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時間內(nèi)不再被訪問的，因而該算法是無法實(shí)現(xiàn)的，但可以利用該算法去評價(jià)其它算法。ppt課件5.3.1最佳置換算法和先進(jìn)先出置換算法

1.最佳圖5-3利用最佳頁面置換算法時的置換圖ppt課件圖5-3利用最佳頁面置換算法時的置換圖ppt課件

2.先進(jìn)先出(FIFO)頁面置換算法

FIFO算法是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。該算法實(shí)現(xiàn)簡單，只需把一個進(jìn)程已調(diào)入內(nèi)存的頁面按先后次序鏈接成一個隊(duì)列，并設(shè)置一個指針，稱為替換指針，使它總是指向最老的頁面。但該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵谶M(jìn)程中，有些頁面經(jīng)常被訪問，比如，含有全局變量、常用函數(shù)、例程等的頁面，F(xiàn)IFO算法并不能保證這些頁面不被淘汰。ppt課件2.先進(jìn)先出(FIFO)頁面置換算法

FIFO算法圖5-4利用FIFO置換算法時的置換圖ppt課件圖5-4利用FIFO置換算法時的置換圖ppt課件5.3.2最近最久未使用和最少使用置換算法

1.?LRU(LeastRecentlyUsed)置換算法的描述

FIFO置換算法的性能之所以較差，是因?yàn)樗罁?jù)的條件是各個頁面調(diào)入內(nèi)存的時間，而頁面調(diào)入的先后并不能反映頁面的使用情況。最近最久未使用(LRU)的頁面置換算法是根據(jù)頁面調(diào)入內(nèi)存后的使用情況做出決策的。ppt課件5.3.2最近最久未使用和最少使用置換算法

1.?圖5-5

LRU頁面置換算法ppt課件圖5-5LRU頁面置換算法ppt課件

2.LRU置換算法的硬件支持

1)寄存器

為了記錄某進(jìn)程在內(nèi)存中各頁的使用情況，須為每個在內(nèi)存中的頁面配置一個移位寄存器，可表示為

R?=?Rn-1Rn-2Rn-3…R2R1R0ppt課件2.LRU置換算法的硬件支持

1)寄存器

為當(dāng)進(jìn)程訪問某物理塊時，要將相應(yīng)寄存器的Rn-1位置成1。此時，定時信號將每隔一定時間(例如100ms)將寄存器右移一位。如果我們把n位寄存器的數(shù)看作是一個整數(shù)，那么，具有最小數(shù)值的寄存器所對應(yīng)的頁面，就是最近最久未使用的頁面。ppt課件當(dāng)進(jìn)程訪問某物理塊時，要將相應(yīng)寄存器的Rn-1位置成1。圖5-6某進(jìn)程具有8個頁面時的LRU訪問情況ppt課件圖5-6某進(jìn)程具有8個頁面時的LRU訪問情況ppt課件

2)棧

可利用一個特殊的棧保存當(dāng)前使用的各個頁面的頁面號。每當(dāng)進(jìn)程訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號，而棧底則是最近最久未使用頁面的頁面號。假定現(xiàn)有一進(jìn)程，它分有五個物理塊，所訪問的頁面的頁面號序列為：

4，7，0，7，1，0，1，2，1，2，6ppt課件2)棧

可利用一個特殊的棧保存當(dāng)前使用的各個頁面的圖5-7用棧保存當(dāng)前使用頁面時棧的變化情況ppt課件圖5-7用棧保存當(dāng)前使用頁面時棧的變化情況ppt課件

3.最少使用(LeastFrequentlyUsed，LFU)置換算法

在采用LFU算法時，應(yīng)為在內(nèi)存中的每個頁面設(shè)置一個移位寄存器，用來記錄該頁面被訪問的頻率。該置換算法選擇在最近時期使用最少的頁面作為淘汰頁。ppt課件3.最少使用(LeastFrequentlyUse5.3.3Clock置換算法

1.簡單的Clock置換算法

當(dāng)利用簡單Clock算法時，只需為每頁設(shè)置一位訪問位，再將內(nèi)存中的所有頁面都通過鏈接指針鏈接成一個循

環(huán)隊(duì)列。ppt課件5.3.3Clock置換算法

1.簡單的Clock圖5-8簡單Clock置換算法的流程和示例ppt課件圖5-8簡單Clock置換算法的流程和示例ppt課件

2.改進(jìn)型Clock置換算法

在將一個頁面換出時，如果該頁已被修改過，便須將該頁重新寫回到磁盤上；但如果該頁未被修改過，則不必將它拷回磁盤。換而言之，對于修改過的頁面，在換出時所付出的開銷比未修改過的頁面大，或者說，置換代價(jià)大。在改進(jìn)型Clock算法中，除須考慮頁面的使用情況外，還須再增加一個因素——置換代價(jià)。ppt課件2.改進(jìn)型Clock置換算法

在將一個頁面換出時，5.3.4頁面緩沖算法(PageBufferingAlgorithm，PBA)

1.影響頁面換進(jìn)換出效率的若干因素

(1)頁面置換算法。

(2)寫回磁盤的頻率。

(3)讀入內(nèi)存的頻率。ppt課件5.3.4頁面緩沖算法(PageBufferingA

2.頁面緩沖算法PBA

PBA算法的主要特點(diǎn)是：①顯著地降低了頁面換進(jìn)、換出的頻率，使磁盤I/O的操作次數(shù)大為減少，因而減少了頁面換進(jìn)、換出的開銷；②正是由于換入換出的開銷大幅度減小，才能使其采用一種較簡單的置換策略，如先進(jìn)先出(FIFO)算法，它不需要特殊硬件的支持，實(shí)現(xiàn)起來非常簡單。

1)空閑頁面鏈表

2)修改頁面鏈表

ppt課件2.頁面緩沖算法PBA

PBA算法的主要特點(diǎn)是：①5.3.5訪問內(nèi)存的有效時間

與基本分頁存儲管理方式不同，在請求分頁管理方式中，內(nèi)存有效訪問時間不僅要考慮訪問頁表和訪問實(shí)際物理地址數(shù)據(jù)的時間，還必須要考慮到缺頁中斷的處理時間。ppt課件5.3.5訪問內(nèi)存的有效時間

與基本分頁存儲管理方式

5.4?“抖動”與工作集

由于請求分頁式虛擬存儲器系統(tǒng)的性能優(yōu)越，在正常運(yùn)行情況下，它能有效地減少內(nèi)存碎片，提高處理機(jī)的利用率和吞吐量，故是目前最常用的一種系統(tǒng)。但如果在系統(tǒng)中運(yùn)行的進(jìn)程太多，進(jìn)程在運(yùn)行中會頻繁地發(fā)生缺頁情況，這又會對系統(tǒng)的性能產(chǎn)生很大的影響，故還須對請求分頁系統(tǒng)的性能做簡單的分析。ppt課件?5.4?“抖動”與工作集

由于請求分頁式5.4.1多道程序度與“抖動”

1.多道程序度與處理機(jī)的利用率

由于虛擬存儲器系統(tǒng)能從邏輯上擴(kuò)大內(nèi)存，這時，只需裝入一個進(jìn)程的部分程序和數(shù)據(jù)便可開始運(yùn)行，故人們希望在系統(tǒng)中能運(yùn)行更多的進(jìn)程，即增加多道程序度，以提高處理機(jī)的利用率。但處理機(jī)的實(shí)際利用率卻如圖5-9中的實(shí)線所示。ppt課件5.4.1多道程序度與“抖動”

1.多道程序度與處圖5-9處理機(jī)的利用率ppt課件圖5-9處理機(jī)的利用率ppt課件

2.產(chǎn)生“抖動”的原因

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

發(fā)生“抖動”的根本原因是，5.4.2工作集

1.工作集的基本概念

進(jìn)程發(fā)生缺頁率的時間間隔與進(jìn)程所獲得的物理塊數(shù)有關(guān)。圖5-10示出了缺頁率與物理塊數(shù)之間的關(guān)系。ppt課件5.4.2工作集

1.工作集的基本概念

進(jìn)程發(fā)圖5-10缺頁率與物理塊數(shù)之間的關(guān)系ppt課件圖5-10缺頁率與物理塊數(shù)之間的關(guān)系ppt課件

2.工作集的定義

所謂工作集，是指在某段時間間隔Δ里，進(jìn)程實(shí)際所要訪問頁面的集合。Denning指出，雖然程序只需要少量的幾頁在內(nèi)存便可運(yùn)行，但為了較少地產(chǎn)生缺頁，應(yīng)將程序的全部工作集裝入內(nèi)存中。然而我們無法事先預(yù)知程序在不同時刻將訪問哪些頁面，故仍只有像置換算法那樣，用程序的過去某段時間內(nèi)的行為作為程序在將來某段時間內(nèi)行為的近似。ppt課件2.工作集的定義

所謂工作集，是指在某段時間間隔Δ圖5-11窗口為3、4、5時進(jìn)程的工作集ppt課件圖5-11窗口為3、4、5時進(jìn)程的工作集ppt課件5.4.3“抖動”的預(yù)防方法

1.采取局部置換策略

在頁面分配和置換策略中，如果采取的是可變分配方式，則為了預(yù)防發(fā)生“抖動”，可采取局部置換策略。ppt課件5.4.3“抖動”的預(yù)防方法

1.采取局部置換策略

2.把工作集算法融入到處理機(jī)調(diào)度中

當(dāng)調(diào)度程序發(fā)現(xiàn)處理機(jī)利用率低下時，它將試圖從外存調(diào)入一個新作業(yè)進(jìn)入內(nèi)存，來改善處理機(jī)的利用率。ppt課件2.把工作集算法融入到處理機(jī)調(diào)度中

當(dāng)調(diào)度程序發(fā)現(xiàn)

3.利用“L=S”準(zhǔn)則調(diào)節(jié)缺頁率

Denning于1980年提出了“L=S”的準(zhǔn)則來調(diào)節(jié)多道程序度，其中L是缺頁之間的平均時間，S是平均缺頁服務(wù)時間，即用于置換一個頁面所需的時間。如果是L遠(yuǎn)比S大，說明很少發(fā)生缺頁，磁盤的能力尚未得到充分的利用；反之，如果是L比S小，則說明頻繁發(fā)生缺頁，缺頁的速度已超過磁盤的處理能力。只有當(dāng)L與S接近時，磁盤和處理機(jī)都可達(dá)到它們的最大利用率。理論和實(shí)踐都已證明，利用“L=S”準(zhǔn)則，對于調(diào)節(jié)缺頁率是十分有效的。ppt課件3.利用“L=S”準(zhǔn)則調(diào)節(jié)缺頁率

Denning于

4.選擇暫停的進(jìn)程

當(dāng)多道程序度偏高時，已影響到處理機(jī)的利用率，為了防止發(fā)生“抖動”，系統(tǒng)必須減少多道程序的數(shù)目。ppt課件4.選擇暫停的進(jìn)程

當(dāng)多道程序度偏高時，已影響到處

5.5請求分段存儲管理方式

5.5.1請求分段中的硬件支持

為了實(shí)現(xiàn)請求分段式存儲管理，應(yīng)在系統(tǒng)中配置多種硬件機(jī)構(gòu)，以支持快速地完成請求分段功能。與請求分頁系統(tǒng)相似，在請求分段系統(tǒng)中所需的硬件支持有段表機(jī)制、缺段中斷機(jī)構(gòu)，以及地址變換機(jī)構(gòu)。ppt課件?5.5請求分段存儲管理方式

5.5.1請

1.請求段表機(jī)制

在請求分段式管理中所需的主要數(shù)據(jù)結(jié)構(gòu)是請求段表。在該表中除了具有請求分頁機(jī)制中有的訪問字段A、修改位M、存在位P和外存始址四個字段外，還增加了存取方式字段和增補(bǔ)位。這些字段供程序在調(diào)進(jìn)、調(diào)出時參考。下面給出請求分段的段表項(xiàng)。ppt課件1.請求段表機(jī)制

在請求分段式管理中所需的主要數(shù)據(jù)

2.缺段中斷機(jī)構(gòu)

在請求分段系統(tǒng)中采用的是請求調(diào)段策略。每當(dāng)發(fā)現(xiàn)運(yùn)行進(jìn)程所要訪問的段尚未調(diào)入內(nèi)存時，便由缺段中斷機(jī)構(gòu)產(chǎn)生一缺段中斷信號，進(jìn)入OS后，由缺段中斷處理程序?qū)⑺璧亩握{(diào)入內(nèi)存。與缺頁中斷機(jī)構(gòu)類似，缺段中斷機(jī)構(gòu)同樣需要在一條指令的執(zhí)行期間產(chǎn)生和處理中斷，以及在一條指令執(zhí)行期間，可能產(chǎn)生多次缺段中斷。但由于分段是信息的邏輯單位，因而不可能出現(xiàn)一條指令被分割在兩個分段中，和一組信息被分割在兩個分段中的情況。缺段中斷的處理過程如圖5-12所示。ppt課件2.缺段中斷機(jī)構(gòu)

在請求分段系統(tǒng)中采用的是請求調(diào)段圖5-12請求分段系統(tǒng)中的中斷處理過程ppt課件圖5-12請求分段系統(tǒng)中的中斷處理過程ppt課件

3.地址變換機(jī)構(gòu)

請求分段系統(tǒng)中的地址變換機(jī)構(gòu)是在分段系統(tǒng)地址變換機(jī)構(gòu)的基礎(chǔ)上形成的。因?yàn)楸辉L問的段并非全在內(nèi)存，所以在地址變換時，若發(fā)現(xiàn)所要訪問的段不在內(nèi)存，必須先將所缺的段調(diào)入內(nèi)存，并修改段表，然后才能再利用段表進(jìn)行地址變換。為此，在地址變換機(jī)構(gòu)中又增加了某些功能，如缺段中斷的請求及處理等。圖5-13示出了請求分段系統(tǒng)的地址變換過程。ppt課件3.地址變換機(jī)構(gòu)

請求分段系統(tǒng)中的地址變換機(jī)構(gòu)是在圖5-13請求分段系統(tǒng)的地址變換過程ppt課件圖5-13請求分段系統(tǒng)的地址變換過程ppt課件5.5.2分段的共享與保護(hù)

1.共享段表

(1)共享進(jìn)程計(jì)數(shù)count。

(2)存取控制字段。

(3)段號。ppt課件5.5.2分段的共享與保護(hù)

1.共享段表

(1圖5-14共享段表項(xiàng)ppt課件圖5-14共享段表項(xiàng)ppt課件

2.共享段的分配與回收

1)共享段的分配

2)共享段的回收

ppt課件2.共享段的分配與回收

1)共享段的分配

2

3.分段保護(hù)

在分段系統(tǒng)中，由于每個分段在邏輯上是相對獨(dú)立的，因而比較容易實(shí)現(xiàn)信息保護(hù)。目前，常采用以下幾種措施來確保信息的安全。

1)越界檢查

2)存取控制檢查

3)環(huán)保護(hù)機(jī)構(gòu)

ppt課件3.分段保護(hù)

在分段系統(tǒng)中，由于每個分段在邏輯上是圖5-15環(huán)保護(hù)機(jī)構(gòu)ppt課件圖5-15環(huán)保護(hù)機(jī)構(gòu)ppt課件習(xí)題

1.常規(guī)存儲器管理方式具有哪兩大特征?它對系統(tǒng)性能有何影響?

2.什么是程序運(yùn)行時的時間局限性和空間局限性?

3.虛擬存儲器有哪些特征?其中最本質(zhì)的特征是什么?

4.實(shí)現(xiàn)虛擬存儲器需要哪些硬件支持?

5.實(shí)現(xiàn)虛擬存儲器需要哪幾個關(guān)鍵技術(shù)?

6.在請求分頁系統(tǒng)中，頁表應(yīng)包括哪些數(shù)據(jù)項(xiàng)?每項(xiàng)的作用是什么?ppt課件習(xí)題

1.常規(guī)存儲器管理方

7.試比較缺頁中斷機(jī)構(gòu)與一般的中斷，它們之間有何明顯的區(qū)別?

8.試說明請求分頁系統(tǒng)中的地址變換過程。

9.何謂固定分配局部置換和可變分配全局置換的內(nèi)存分配策略?

10.在請求分頁系統(tǒng)中，應(yīng)從何處將所需頁面調(diào)入內(nèi)存?

11.試說明在請求分頁系統(tǒng)中頁面的調(diào)入過程。

12.在請求分頁系統(tǒng)中，常采用哪幾種頁面置換算法?ppt課件7.試比較缺頁中斷機(jī)構(gòu)與一般的中斷，它們之間有何明顯的

13.在一個請求分頁系統(tǒng)中，采用FIFO頁面置換算法時，假如一個作業(yè)的頁面走向?yàn)?、3、2、1、4、3、5、4、3、2、1、5，當(dāng)分配給該作業(yè)的物理塊數(shù)M分別為3和4時，試計(jì)算在訪問過程中所發(fā)生的缺頁次數(shù)和缺頁率，并比較所得結(jié)果。

14.實(shí)現(xiàn)LRU算法所需的硬件支持是什么?

15.試說明改進(jìn)型Clock置換算法的基本原理。

16.影響頁面換進(jìn)換出效率的若干因素是什么?

17.頁面緩沖算法的主要特點(diǎn)是什么?它是如何降低頁面換進(jìn)、換出的頻率的?

18.在請求分頁系統(tǒng)中，產(chǎn)生“抖動”的原因是什么?ppt課件13.在一個請求分頁系統(tǒng)中，采用FIFO頁面置換算法時

19.何謂工作集?它是基于什么原理確定的?

20.當(dāng)前可以利用哪幾種方法來防止“抖動”?

21.試說明如何利用“L=S”準(zhǔn)則來調(diào)節(jié)缺頁率，以避免“抖動”的發(fā)生。

22.為了實(shí)現(xiàn)請求分段式存儲管理，應(yīng)在系統(tǒng)中增加配置哪些硬件機(jī)構(gòu)?

23.在請求段表機(jī)制中，應(yīng)設(shè)置哪些段表項(xiàng)?

24.說明請求分段系統(tǒng)中的缺頁中斷處理過程。

25.請對共享段表中的各項(xiàng)作簡要說明。

26.如何實(shí)現(xiàn)共享分段的分配和回收?ppt課件19.何謂工作集?它是基于什么原理確定的?

2第五章虛擬存儲器5.1虛擬存儲器概述5.2請求分頁存儲管理方式5.3頁面置換算法5.4“抖動”與工作集5.5請求分段存儲管理方式習(xí)題ppt課件第五章虛擬存儲器5.1虛擬存儲器概述pp

5.1虛擬存儲器概述

第四章所介紹的各種存儲器管理方式有一個共同的特點(diǎn)，即它們都要求將一個作業(yè)全部裝入內(nèi)存后方能運(yùn)行。于是，出現(xiàn)了下面這樣兩種情況：

(1)有的作業(yè)很大，其所要求的內(nèi)存空間超過了內(nèi)存總?cè)萘浚鳂I(yè)不能全部被裝入內(nèi)存，致使該作業(yè)無法運(yùn)行；

(2)有大量作業(yè)要求運(yùn)行，但由于內(nèi)存容量不足以容納所有這些作業(yè)，只能將少數(shù)作業(yè)裝入內(nèi)存讓它們先運(yùn)行，而將其它大量的作業(yè)留在外存上等待。ppt課件?5.1虛擬存儲器概述

第四章所介紹的各種5.1.1常規(guī)存儲管理方式的特征和局部性原理

1.常規(guī)存儲器管理方式的特征

我們把前一章中所介紹的各種存儲器管理方式統(tǒng)稱為傳統(tǒng)存儲器管理方式，它們?nèi)季哂腥缦聝蓚€共同的特征：

(1)一次性

(2)駐留性ppt課件5.1.1常規(guī)存儲管理方式的特征和局部性原理

1.

2.局部性原理

程序運(yùn)行時存在的局部性現(xiàn)象，很早就已被人發(fā)現(xiàn)，但直到1968年，P.Denning才真正指出：程序在執(zhí)行時將呈現(xiàn)出局部性規(guī)律，即在一較短的時間內(nèi)，程序的執(zhí)行僅局限于某個部分，相應(yīng)地，它所訪問的存儲空間也局限于某個區(qū)域。ppt課件2.局部性原理

程序運(yùn)行時存在的局部性現(xiàn)象，很早就局限性又表現(xiàn)在下述兩個方面：

(1)時間局限性。

(2)空間局限性。ppt課件局限性又表現(xiàn)在下述兩個方面：

(1)時間局限性。

3.虛擬存儲器的基本工作情況

基于局部性原理可知，應(yīng)用程序在運(yùn)行之前沒有必要將之全部裝入內(nèi)存，而僅須將那些當(dāng)前要運(yùn)行的少數(shù)頁面或段先裝入內(nèi)存便可運(yùn)行，其余部分暫留在盤上。ppt課件3.虛擬存儲器的基本工作情況

基于局部性原理可知5.1.2虛擬存儲器的定義和特征

1.虛擬存儲器的定義

當(dāng)用戶看到自己的程序能在系統(tǒng)中正常運(yùn)行時，他會認(rèn)為，該系統(tǒng)所具有的內(nèi)存容量一定比自己的程序大，或者說，用戶所感覺到的內(nèi)存容量會比實(shí)際內(nèi)存容量大得多。但用戶所看到的大容量只是一種錯覺，是虛的，故人們把這樣的存儲器稱為虛擬存儲器。ppt課件5.1.2虛擬存儲器的定義和特征

1.虛擬存儲器的

2.虛擬存儲器的特征

與傳統(tǒng)的存儲器管理方式比較，虛擬存儲器具有以下三個重要特征：

(1)多次性。

(2)對換性。

(3)虛擬性。ppt課件2.虛擬存儲器的特征

與傳統(tǒng)的存儲器管理方式比較，5.1.3虛擬存儲器的實(shí)現(xiàn)方法

1.分頁請求系統(tǒng)

1)硬件支持

主要的硬件支持有：

(1)請求分頁的頁表機(jī)制。

(2)缺頁中斷機(jī)構(gòu)。

(3)地址變換機(jī)構(gòu)。

2)實(shí)現(xiàn)請求分頁的軟件

ppt課件5.1.3虛擬存儲器的實(shí)現(xiàn)方法

1.分頁請求系統(tǒng)

2.請求分段系統(tǒng)

1)硬件支持

主要的硬件支持有：

(1)請求分段的段表機(jī)制。

(2)缺頁中斷機(jī)構(gòu)。

(3)地址變換機(jī)構(gòu)。

2)軟件支持

ppt課件2.請求分段系統(tǒng)

1)硬件支持

主要的硬件支

5.2請求分頁存儲管理方式

5.2.1請求分頁中的硬件支持

為了實(shí)現(xiàn)請求分頁，系統(tǒng)必須提供一定的硬件支持。計(jì)算機(jī)系統(tǒng)除了要求一定容量的內(nèi)存和外存外，還需要有請求頁表機(jī)制、缺頁中斷機(jī)構(gòu)以及地址變換機(jī)構(gòu)。ppt課件?5.2請求分頁存儲管理方式

5.2.1請

1.請求頁表機(jī)制

在請求分頁系統(tǒng)中需要的主要數(shù)據(jù)結(jié)構(gòu)是請求頁表，其基本作用仍然是將用戶地址空間中的邏輯地址映射為內(nèi)存空間中的物理地址。為了滿足頁面換進(jìn)換出的需要，在請求頁表中又增加了四個字段。這樣，在請求分頁系統(tǒng)中的每個頁表應(yīng)含以下諸項(xiàng)：ppt課件1.請求頁表機(jī)制

在請求分頁系統(tǒng)中需要的主要數(shù)據(jù)結(jié)

2.缺頁中斷機(jī)構(gòu)

(1)在指令執(zhí)行期間產(chǎn)生和處理中斷信號。

(2)一條指令在執(zhí)行期間可能產(chǎn)生多次缺頁中斷。ppt課件2.缺頁中斷機(jī)構(gòu)

(1)在指令執(zhí)行期間產(chǎn)生和處理圖5-1涉及6次缺頁中斷的指令ppt課件圖5-1涉及6次缺頁中斷的指令ppt課件

3.地址變換機(jī)構(gòu)

請求分頁系統(tǒng)中的地址變換機(jī)構(gòu)是在分頁系統(tǒng)地址變換機(jī)構(gòu)的基礎(chǔ)上，為實(shí)現(xiàn)虛擬存儲器，再增加了某些功能所形成的，如產(chǎn)生和處理缺頁中斷，以及從內(nèi)存中換出一頁的功能等等。圖5-2示出了請求分頁系統(tǒng)中的地址變換過程。ppt課件3.地址變換機(jī)構(gòu)

請求分頁系統(tǒng)中的地址變換機(jī)構(gòu)是在圖5-2請求分頁中的地址變換過程ppt課件圖5-2請求分頁中的地址變換過程ppt課件5.2.2請求分頁中的內(nèi)存分配

1.最小物理塊數(shù)的確定

一個顯而易見的事實(shí)是，隨著為每個進(jìn)程所分配的物理塊的減少，將使進(jìn)程在執(zhí)行中的缺頁率上升，從而會降低進(jìn)程的執(zhí)行速度。為使進(jìn)程能有效地工作，應(yīng)為它分配一定數(shù)目的物理塊，但這并不是最小物理塊數(shù)的概念。ppt課件5.2.2請求分頁中的內(nèi)存分配

1.最小物理塊數(shù)的

2.內(nèi)存分配策略

在請求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可變分配策略。在進(jìn)行置換時，也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。

1)固定分配局部置換(FixedAllocation，LocalReplacement)

2)可變分配全局置換(VariableAllocation，GlobalReplacement)

3)可變分配局部置換(VariableAllocation，LocalReplacement)

ppt課件2.內(nèi)存分配策略

在請求分頁系統(tǒng)中，可采取兩種內(nèi)存

3.物理塊分配算法

在采用固定分配策略時，如何將系統(tǒng)中可供分配的所有物理塊分配給各個進(jìn)程，可采用下述幾種算法：

(1)平均分配算法，即將系統(tǒng)中所有可供分配的物理塊平均分配給各個進(jìn)程。

(2)按比例分配算法，即根據(jù)進(jìn)程的大小按比例分配物理塊。如果系統(tǒng)中共有n個進(jìn)程，每個進(jìn)程的頁面數(shù)為Si，

則系統(tǒng)中各進(jìn)程頁面數(shù)的總和為：ppt課件3.物理塊分配算法

在采用固定分配策略時，如何將系又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個進(jìn)程所能分到的物理塊數(shù)為bi可由下式計(jì)算：

這里，bi應(yīng)該取整，它必須大于最小物理塊數(shù)。ppt課件又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個進(jìn)程所能分到的物

(3)考慮優(yōu)先權(quán)的分配算法。在實(shí)際應(yīng)用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成，應(yīng)為它分配較多的內(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í)時控制系統(tǒng)，則可能是完全按優(yōu)先權(quán)為各進(jìn)程分配其物理塊的。ppt課件(3)考慮優(yōu)先權(quán)的分配算法。在實(shí)際應(yīng)用中，為了照顧到重5.2.3頁面調(diào)入策略

為使進(jìn)程能夠正常運(yùn)行，必須事先將要執(zhí)行的那部分程序和數(shù)據(jù)所在的頁面調(diào)入內(nèi)存?，F(xiàn)在的問題是：

(1)系統(tǒng)應(yīng)在何時調(diào)入所需頁面；

(2)系統(tǒng)應(yīng)從何處調(diào)入這些頁面；

(3)是如何進(jìn)行調(diào)入的。ppt課件5.2.3頁面調(diào)入策略

為使進(jìn)程能夠正常運(yùn)行，必須事

1.何時調(diào)入頁面

(1)預(yù)調(diào)頁策略。

(2)請求調(diào)頁策略。ppt課件1.何時調(diào)入頁面

(1)預(yù)調(diào)頁策略。

(2)

2.從何處調(diào)入頁面

(1)系統(tǒng)擁有足夠的對換區(qū)空間，這時可以全部從對換區(qū)調(diào)入所需頁面，以提高調(diào)頁速度。

(2)系統(tǒng)缺少足夠的對換區(qū)空間，這時凡是不會被修改的文件，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁面時，由于它們未被修改，則不必再將它們重寫到磁盤(換出)，以后再調(diào)入時，仍從文件區(qū)直接調(diào)入。但對于那些可能被修改的部分，在將它們換出時便須調(diào)到對換區(qū)，以后需要時再從對換區(qū)調(diào)入。

(3)?UNIX方式。ppt課件2.從何處調(diào)入頁面

(1)系統(tǒng)擁有足夠的對換區(qū)空

3.頁面調(diào)入過程

每當(dāng)程序所要訪問的頁面未在內(nèi)存時(存在位為“0”)，便向CPU發(fā)出一缺頁中斷，中斷處理程序首先保留CPU環(huán)境，分析中斷原因后轉(zhuǎn)入缺頁中斷處理程序。ppt課件3.頁面調(diào)入過程

每當(dāng)程序所要訪問的頁面未在內(nèi)存時

4.缺頁率

假設(shè)一個進(jìn)程的邏輯空間為n頁，系統(tǒng)為其分配的內(nèi)存物理塊數(shù)為m(m≤n)。如果在進(jìn)程的運(yùn)行過程中，訪問頁面成功(即所訪問頁面在內(nèi)存中)的次數(shù)為S，訪問頁面失敗(即所訪問頁面不在內(nèi)存中，需要從外存調(diào)入)的次數(shù)為F，則該進(jìn)程總的頁面訪問次數(shù)為A?=?S?+?F，那么該進(jìn)程在其運(yùn)行過程中的缺頁率即為ppt課件4.缺頁率

假設(shè)一個進(jìn)程的邏輯空間為n頁，系統(tǒng)為其事實(shí)上，在缺頁中斷處理時，當(dāng)由于空間不足，需要置換部分頁面到外存時，選擇被置換頁面還需要考慮到置換的代價(jià)，如頁面是否被修改過。沒有修改過的頁面可以直接放棄，而修改過的頁面則必須進(jìn)行保存，所以處理這兩種情況時的時間也是不同的。假設(shè)被置換的頁面被修改的概率是β，其缺頁中斷處理時間為ta，被置換頁面沒有被修改的缺頁中斷時間為tb，那么，缺頁中斷處理時間的計(jì)算公式為

t=β×ta+(1—β)×tbppt課件事實(shí)上，在缺頁中斷處理時，當(dāng)由于空間不足，需要置換部分頁

5.3頁面置換算法

在進(jìn)程運(yùn)行過程中，若其所要訪問的頁面不在內(nèi)存，而需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)送到磁盤的對換區(qū)中。但應(yīng)將哪個頁面調(diào)出，須根據(jù)一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面置換算法(ReplacementAlgorithms)。置換算法的好壞將直接影響到系統(tǒng)的性能。ppt課件?5.3頁面置換算法

在進(jìn)程運(yùn)行過程中，5.3.1最佳置換算法和先進(jìn)先出置換算法

1.最佳(Optimal)置換算法

最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面將是以后永不使用的，或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法通常可保證獲得最低的缺頁率。但由于人們目前還無法預(yù)知，一個進(jìn)程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時間內(nèi)不再被訪問的，因而該算法是無法實(shí)現(xiàn)的，但可以利用該算法去評價(jià)其它算法。ppt課件5.3.1最佳置換算法和先進(jìn)先出置換算法

1.最佳圖5-3利用最佳頁面置換算法時的置換圖ppt課件圖5-3利用最佳頁面置換算法時的置換圖ppt課件

2.先進(jìn)先出(FIFO)頁面置換算法

FIFO算法是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。該算法實(shí)現(xiàn)簡單，只需把一個進(jìn)程已調(diào)入內(nèi)存的頁面按先后次序鏈接成一個隊(duì)列，并設(shè)置一個指針，稱為替換指針，使它總是指向最老的頁面。但該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵谶M(jìn)程中，有些頁面經(jīng)常被訪問，比如，含有全局變量、常用函數(shù)、例程等的頁面，F(xiàn)IFO算法并不能保證這些頁面不被淘汰。ppt課件2.先進(jìn)先出(FIFO)頁面置換算法

FIFO算法圖5-4利用FIFO置換算法時的置換圖ppt課件圖5-4利用FIFO置換算法時的置換圖ppt課件5.3.2最近最久未使用和最少使用置換算法

1.?LRU(LeastRecentlyUsed)置換算法的描述

FIFO置換算法的性能之所以較差，是因?yàn)樗罁?jù)的條件是各個頁面調(diào)入內(nèi)存的時間，而頁面調(diào)入的先后并不能反映頁面的使用情況。最近最久未使用(LRU)的頁面置換算法是根據(jù)頁面調(diào)入內(nèi)存后的使用情況做出決策的。ppt課件5.3.2最近最久未使用和最少使用置換算法

1.?圖5-5

LRU頁面置換算法ppt課件圖5-5LRU頁面置換算法ppt課件

2.LRU置換算法的硬件支持

1)寄存器

為了記錄某進(jìn)程在內(nèi)存中各頁的使用情況，須為每個在內(nèi)存中的頁面配置一個移位寄存器，可表示為

R?=?Rn-1Rn-2Rn-3…R2R1R0ppt課件2.LRU置換算法的硬件支持

1)寄存器

為當(dāng)進(jìn)程訪問某物理塊時，要將相應(yīng)寄存器的Rn-1位置成1。此時，定時信號將每隔一定時間(例如100ms)將寄存器右移一位。如果我們把n位寄存器的數(shù)看作是一個整數(shù)，那么，具有最小數(shù)值的寄存器所對應(yīng)的頁面，就是最近最久未使用的頁面。ppt課件當(dāng)進(jìn)程訪問某物理塊時，要將相應(yīng)寄存器的Rn-1位置成1。圖5-6某進(jìn)程具有8個頁面時的LRU訪問情況ppt課件圖5-6某進(jìn)程具有8個頁面時的LRU訪問情況ppt課件

2)棧

可利用一個特殊的棧保存當(dāng)前使用的各個頁面的頁面號。每當(dāng)進(jìn)程訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號，而棧底則是最近最久未使用頁面的頁面號。假定現(xiàn)有一進(jìn)程，它分有五個物理塊，所訪問的頁面的頁面號序列為：

4，7，0，7，1，0，1，2，1，2，6ppt課件2)棧

可利用一個特殊的棧保存當(dāng)前使用的各個頁面的圖5-7用棧保存當(dāng)前使用頁面時棧的變化情況ppt課件圖5-7用棧保存當(dāng)前使用頁面時棧的變化情況ppt課件

3.最少使用(LeastFrequentlyUsed，LFU)置換算法

在采用LFU算法時，應(yīng)為在內(nèi)存中的每個頁面設(shè)置一個移位寄存器，用來記錄該頁面被訪問的頻率。該置換算法選擇在最近時期使用最少的頁面作為淘汰頁。ppt課件3.最少使用(LeastFrequentlyUse5.3.3Clock置換算法

1.簡單的Clock置換算法

當(dāng)利用簡單Clock算法時，只需為每頁設(shè)置一位訪問位，再將內(nèi)存中的所有頁面都通過鏈接指針鏈接成一個循

環(huán)隊(duì)列。ppt課件5.3.3Clock置換算法

1.簡單的Clock圖5-8簡單Clock置換算法的流程和示例ppt課件圖5-8簡單Clock置換算法的流程和示例ppt課件

2.改進(jìn)型Clock置換算法

在將一個頁面換出時，如果該頁已被修改過，便須將該頁重新寫回到磁盤上；但如果該頁未被修改過，則不必將它拷回磁盤。換而言之，對于修改過的頁面，在換出時所付出的開銷比未修改過的頁面大，或者說，置換代價(jià)大。在改進(jìn)型Clock算法中，除須考慮頁面的使用情況外，還須再增加一個因素——置換代價(jià)。ppt課件2.改進(jìn)型Clock置換算法

在將一個頁面換出時，5.3.4頁面緩沖算法(PageBufferingAlgorithm，PBA)

1.影響頁面換進(jìn)換出效率的若干因素

(1)頁面置換算法。

(2)寫回磁盤的頻率。

(3)讀入內(nèi)存的頻率。ppt課件5.3.4頁面緩沖算法(PageBufferingA

2.頁面緩沖算法PBA

PBA算法的主要特點(diǎn)是：①顯著地降低了頁面換進(jìn)、換出的頻率，使磁盤I/O的操作次數(shù)大為減少，因而減少了頁面換進(jìn)、換出的開銷；②正是由于換入換出的開銷大幅度減小，才能使其采用一種較簡單的置換策略，如先進(jìn)先出(FIFO)算法，它不需要特殊硬件的支持，實(shí)現(xiàn)起來非常簡單。

1)空閑頁面鏈表

2)修改頁面鏈表

ppt課件2.頁面緩沖算法PBA

PBA算法的主要特點(diǎn)是：①5.3.5訪問內(nèi)存的有效時間

與基本分頁存儲管理方式不同，在請求分頁管理方式中，內(nèi)存有效訪問時間不僅要考慮訪問頁表和訪問實(shí)際物理地址數(shù)據(jù)的時間，還必須要考慮到缺頁中斷的處理時間。ppt課件5.3.5訪問內(nèi)存的有效時間

與基本分頁存儲管理方式

5.4?“抖動”與工作集

由于請求分頁式虛擬存儲器系統(tǒng)的性能優(yōu)越，在正常運(yùn)行情況下，它能有效地減少內(nèi)存碎片，提高處理機(jī)的利用率和吞吐量，故是目前最常用的一種系統(tǒng)。但如果在系統(tǒng)中運(yùn)行的進(jìn)程太多，進(jìn)程在運(yùn)行中會頻繁地發(fā)生缺頁情況，這又會對系統(tǒng)的性能產(chǎn)生很大的影響，故還須對請求分頁系統(tǒng)的性能做簡單的分析。ppt課件?5.4?“抖動”與工作集

由于請求分頁式5.4.1多道程序度與“抖動”

1.多道程序度與處理機(jī)的利用率

由于虛擬存儲器系統(tǒng)能從邏輯上擴(kuò)大內(nèi)存，這時，只需裝入一個進(jìn)程的部分程序和數(shù)據(jù)便可開始運(yùn)行，故人們希望在系統(tǒng)中能運(yùn)行更多的進(jìn)程，即增加多道程序度，以提高處理機(jī)的利用率。但處理機(jī)的實(shí)際利用率卻如圖5-9中的實(shí)線所示。ppt課件5.4.1多道程序度與“抖動”

1.多道程序度與處圖5-9處理機(jī)的利用率ppt課件圖5-9處理機(jī)的利用率ppt課件

2.產(chǎn)生“抖動”的原因

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

發(fā)生“抖動”的根本原因是，5.4.2工作集

1.工作集的基本概念

進(jìn)程發(fā)生缺頁率的時間間隔與進(jìn)程所獲得的物理塊數(shù)有關(guān)。圖5-10示出了缺頁率與物理塊數(shù)之間的關(guān)系。ppt課件5.4.2工作集

1.工作集的基本概念

進(jìn)程發(fā)圖5-10缺頁率與物理塊數(shù)之間的關(guān)系ppt課件圖5-10缺頁率與物理塊數(shù)之間的關(guān)系ppt課件

2.工作集的定義

所謂工作集，是指在某段時間間隔Δ里，進(jìn)程實(shí)際所要訪問頁面的集合。Denning指出，雖然程序只需要少量的幾頁在內(nèi)存便可運(yùn)行，但為了較少地產(chǎn)生缺頁，應(yīng)將程序的全部工作集裝入內(nèi)存中。然而我們無法事先預(yù)知程序在不同時刻將訪問哪些頁面，故仍只有像置換算法那樣，用程序的過去某段時間內(nèi)的行為作為程序在將來某段時間內(nèi)行為的近似。ppt課件2.工作集的定義

所謂工作集，是指在某段時間間隔Δ圖5-11窗口為3、4、5時進(jìn)程的工作集ppt課件圖5-11窗口為3、4、5時進(jìn)程的工作集ppt課件5.4.3“抖動”的預(yù)防方法

1.采取局部置換策略

在頁面分配和置換策略中，如果采取的是可變分配方式，則為了預(yù)防發(fā)生“抖動”，可采取局部置換策略。ppt課件5.4.3“抖動”的預(yù)防方法

1.采取局部置換策略

2.把工作集算法融入到處理機(jī)調(diào)度中

當(dāng)調(diào)度程序發(fā)現(xiàn)處理機(jī)利用率低下時，它將試圖從外存調(diào)入一個新作業(yè)進(jìn)入內(nèi)存，來改善處理機(jī)的利用率。ppt課件2.把工作集算法融入到處理機(jī)調(diào)度中

當(dāng)調(diào)度程序發(fā)現(xiàn)

3.利用“L=S”準(zhǔn)則調(diào)節(jié)缺頁率

Denning于1980年提出了“L=S”的準(zhǔn)則來調(diào)節(jié)多道程序度，其中L是缺頁之間的平均時間，S是平均缺頁服務(wù)時間，即用于置換一個頁面所需的時間。如果是L遠(yuǎn)比S大，說明很少發(fā)生缺頁，磁盤的能力尚未得到充分的利用；反之，如果是L比S小，則說明頻繁發(fā)生缺頁，缺頁的速度已超過磁盤的處理能力。只有當(dāng)L與S接近時，磁盤和處理機(jī)都可達(dá)到它們的最大利用率。理論和實(shí)踐都已證明，利用“L=S”準(zhǔn)則，對于調(diào)節(jié)缺頁率是十分有效的。ppt課件3.利用“L=S”準(zhǔn)則調(diào)節(jié)缺頁率

Denning于

4.選擇暫停的進(jìn)程

當(dāng)多道程序度偏高時，已影響到處理機(jī)的利用率，為了防止發(fā)生“抖動”，系統(tǒng)必須減少多道程序的數(shù)目。ppt課件4.選擇暫停的進(jìn)程

當(dāng)多道程序度偏高時，已影響到處

5.5請求分段存儲管理方式

5.5.1請求分段中的硬件支持

為了實(shí)現(xiàn)請求分段式存儲管理，應(yīng)在系統(tǒng)中配置多種硬件機(jī)構(gòu)，以支持快速地完成請求分段功能。與請求分頁系統(tǒng)相似，在請求分段系統(tǒng)中所需的硬件支持有段表機(jī)制、缺段中斷機(jī)構(gòu)，以及地址變換機(jī)構(gòu)。ppt課件?5.5請求分段存儲管理方式

5.5.1請

1.請求段表機(jī)制

在請求分段式管理中所需的主要數(shù)據(jù)結(jié)構(gòu)是請求