前文提到的存儲器管理方式有一個共同的特點，即它們都要求將一個作業(yè)全部裝入內存后方能運行。

但有兩種特殊情況：

• 有的作業(yè)很大，其所要求的內存空間超過了內存總容量，作業(yè)不能全部被裝入內存，致使該作業(yè)無法運行；

• 有大量作業(yè)要求運行，但由于內存容量不足以容納所有這些作業(yè)，只能將少數(shù)作業(yè)裝入內存讓它們先運行，而將其它大量的作業(yè)留在外存上等待。

1.?虛擬存儲器概述

1.1 常規(guī)存儲管理方式的特征

傳統(tǒng)存儲器管理方式，它們全都具有如下兩個共同的特征：

一次性：

• 指作業(yè)必須一次性地全部裝入內存后方能開始運行。

• 在傳統(tǒng)存儲器管理方式中，無一例外地要求先將作業(yè)全部裝入內存后方能運行。正是這一特征導致了大作業(yè)無法在小內存中運行，以及無法進一步提高系統(tǒng)的多道程序度，直接限制了對處理機的利用率和系統(tǒng)的吞吐量的提高。

• 事實上，許多作業(yè)在運行時，并非需要用到全部程序和數(shù)據(jù)，如果一次性地裝入其全部程序和數(shù)據(jù)，顯然也是對內存空間的一種浪費。

駐留性 ：

• 指作業(yè)被裝入內存后，整個作業(yè)都一直駐留在內存中，其中任何部分都不會被換出，直至作業(yè)運行結束。

• 盡管運行中的進程會因O等原因而被阻塞，可能處于長期等待狀態(tài)，或者有的程序模塊在運行過一次后就不再需要(運行)了，它們都仍將駐留在內存中，繼續(xù)占用寶貴的內存資源。

一次性及駐留性特征使得許多在程序運行中不用或暫時不用的程序(數(shù)據(jù))占據(jù)了大量的內存空間，而一些需要運行的作業(yè)又無法裝入運行，顯然，這是在浪費寶貴的內存資源。

1.2 常規(guī)存儲管理方式的局部性原理

程序在執(zhí)行時將呈現(xiàn)出局部性規(guī)律，即在一較短的時間內，程序的執(zhí)行僅局限于某個部分，相應地，它所訪問的存儲空間也局限于某個區(qū)域。

局限性又表現(xiàn)在下述兩個方面：

• 時間局限性。

  如果程序中的某條指令被執(zhí)行，則不久以后該指令可能再次執(zhí)行;如果某數(shù)據(jù)被訪問過，則不久以后該數(shù)據(jù)可能再次被訪問。

  產生時間局限性的典型原因是在程序中存在著大量的循環(huán)操作。

• 空間局限性。

  一旦程序訪問了某個存儲單元，在不久之后，其附近的存儲單元也將被訪問。

  即程序在一段時間內所訪問的地址可能集中在一定的范圍之內，其典型情況便是程序的順序執(zhí)行。

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

應用程序在運行之前沒有必要將之全部裝入內存，而僅須將那些當前要運行的少數(shù)頁面或段先裝入內存便可運行，其余部分暫留在盤上。

• 程序在運行時如果它所要訪問的頁(段)已調入內存，便可繼續(xù)執(zhí)行下去；

• 但如果程序所要訪問的頁(段)尚未調入內存(稱為缺頁或缺段)，便發(fā)出缺頁(段)中斷請求，此時OS將利用請求調頁(段)功能將它們調入內存，以使進程能繼續(xù)執(zhí)行下去。

• 如果此時內存已滿，無法再裝入新的頁(段)，OS 還須再利用頁(段)的置換功能，將內存中暫時不用的頁(段)調至盤上，騰出足夠的內存空間后，再將要訪問的頁(段)調入內存，使程序繼續(xù)執(zhí)行下去。

• 這樣，便可使一個大的用戶程序在較小的內存空間中運行，也可在內存中同時裝入更多的進程，使它們并發(fā)執(zhí)行。

1.4 虛擬存儲器的定義和特征

虛擬存儲器的定義：

• 指具有請求調入功能和置換功能，能從邏輯上對內存容量加以擴充的一種存儲器系統(tǒng)。

• 其邏輯容量由內存容量和外存容量之和所決定，其運行速度接近于內存速度，而每位的成本卻又接近于外存。

• 虛擬存儲技術是一種性能非常優(yōu)越的存儲器管理技術，故被廣泛地應用于大、中、小型機器和微型機中。

虛擬存儲器的特征：

• 多次性。

  多次性是相對于傳統(tǒng)存儲器管理方式的一次性而言的，是指一個作業(yè)中的程序和數(shù)據(jù)無需在作業(yè)運行時一次性地全部裝入內存，而是允許被分成多次調入內存運行。

  即只需將當前要運行的那部分程序和數(shù)據(jù)裝入內存即可開始運行。

  以后每當要運行到尚未調入的那部分程序時，再將它調入。

  正是由于虛擬存儲器的多次性特征，才使它具有從邏輯上擴大內存的功能。

  無疑，多次性是虛擬存儲器最重要的特征，它是任何其它的存儲管理方式所不具有的。因此,我們也可以認為虛擬存儲器是具有多次性特征的存儲器管理系統(tǒng)

• 對換性。

  對換性是相對于傳統(tǒng)存儲器管理方式的常駐性而言，是指一個作業(yè)中的程序和數(shù)據(jù)，無須在作業(yè)運行時一直常駐內存，而是允許在作業(yè)的運行過程中進行換進、換出。

  即在進程運行期間，允許將那些暫不使用的代碼和數(shù)據(jù)從內存調至外存的對換區(qū)(換出)，待以后需要時再將它們從外存調至內存(換進)。甚至還允許將暫時不運行的進程調至外存，待它們重又具備運行條件時再調入內存。

  換進和換出能有效地提高內存利用率可見，虛擬存儲器具有對換性特征，也正是由于這一特征，才使得虛擬存儲器得以正常運行。

  如果虛擬存儲器不具有換出功能，即不能把那些在存儲器中暫時不運行的進程或頁面(段)換至外存，不僅不能充分地利用內存，而且還會使在換入時，因無足夠的內存空間，而經(jīng)常以失敗告終。

• 虛擬性。

  虛擬性是指能夠從邏輯上擴充內存容量，使用戶所看到的內存容量遠大于實際內存容量。

  這樣，就可以在小的內存中運行大的作業(yè)，或者能提高多道程序度。它不僅能有效地改善內存的利用率，還可提高程序執(zhí)行的并發(fā)程度，從而可以增加系統(tǒng)的吞吐量。

  這是虛擬存儲器所表現(xiàn)出來的最重要的特征，也是實現(xiàn)虛擬存儲器的最重要的目標。正是由于它具有這一特征，才使得虛擬存儲器目前已成為在大、中、小及微機上最廣泛采用的存儲管理方式。

1.5 虛擬存儲器的實現(xiàn)方法

分頁請求系統(tǒng)：

• 硬件支持。

  主要的硬件支持有：

  • 請求分頁的頁表機制。

  • 缺頁中斷機構。

  • 地址變換機構。

• 實現(xiàn)請求分頁的軟件。

  用于實現(xiàn)請求調頁的軟件和實現(xiàn)頁面置換的軟件

請求分段系統(tǒng)：

• 硬件支持。

  主要的硬件支持有：

  • 請求分段的段表機制。

  • 缺頁中斷機構。

  • 地址變換機構。

• 軟件支持。

  用于實現(xiàn)請求調段的軟件和實現(xiàn)段置換的軟件。

2. 請求分頁存儲管理方式

2.1 請求分頁中的硬件支持

計算機系統(tǒng)除了要求一定容量的內存和外存外，還需要有請求頁表機制、缺頁中斷機構以及地址變換機構。

請求頁表機制：

• 在請求分頁系統(tǒng)中需要的主要數(shù)據(jù)結構是請求頁表，其基本作用仍然是將用戶地址空間中的邏輯地址映射為內存空間中的物理地址。

• 為了滿足頁面換進換出的需要，在請求頁表中又增加了四個字段。

缺頁中斷機構：

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

• 一條指令在執(zhí)行期間可能產生多次缺頁中斷。

地址變換機構：

• 請求分頁系統(tǒng)中的地址變換機構是在分頁系統(tǒng)地址變換機構的基礎上，為實現(xiàn)虛擬存儲器，再增加了某些功能所形成的。

• 如產生和處理缺頁中斷，以及從內存中換出一頁的功能等等。

2.2 請求分頁中的內存分配

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

• 最小物理塊數(shù)是指能保證進程正常運行所需的最小物理塊數(shù)，當系統(tǒng)為進程分配的物理塊數(shù)少于此值時，進程將無法運行。

• 至于進程應獲得的最少物理塊數(shù)，與計算機的硬件結構有關，取決于指令的格式、功能和尋址方式。

• 隨著為每個進程所分配的物理塊的減少，將使進程在執(zhí)行中的缺頁率上升，從而會降低進程的執(zhí)行速度。為使進程能有效地工作，應為它分配一定數(shù)目的物理塊。

內存分配策略：

• 在請求分頁系統(tǒng)中，可采取兩種內存分配策略，即固定和可變分配策略。

• 在進行置換時，也可采取兩種策略，即全局置換和局部置換。

• 三種適用的策略：

  • 固定分配局部置換(Fixed Allocation，Local Replacement)

    固定分配：指為每個進程分配一組固定數(shù)目的物理塊，在進程運行期間不再改變。

    局部置換：指如果進程在運行中發(fā)現(xiàn)缺頁，則只能從分配給該進程的“個頁面中選出一頁換出，然后再調入一頁，以保證分配給該進程的內存空間不變。

  • 可變分配全局置換(Variable Allocation，Global Replacement)

    可變分配：指先為每個進程分配一定數(shù)目的物理塊，在進程運行期回、可據(jù)情況做適當?shù)脑黾踊驕p少。

    全局置換：指如果進程在運行中發(fā)現(xiàn)頁，則將OS保留的空閑物理塊(一般組織為一個空閑物理塊隊列)取出一塊分配給該進程，或者以所有進程的全部物理塊為標的，選擇一塊換出，然后將所缺之更調入。

  • 可變分配局部置換(Variable Allocation，Local Replacement)

    基于進程的類型或根據(jù)程序員的要求，為每個進程分配一定數(shù)目的物理塊；

    但當某進程發(fā)現(xiàn)缺貞時，只允許從該進程在內存的頁面中選擇一頁換出，這樣就不會影響其它進程的運行。

物理塊分配算法：

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

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

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

假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個進程所能分到的物理塊數(shù)為bi可由下式計算：

bi應該取整，它必須大于最小物理塊數(shù)。

• 考慮優(yōu)先權的分配算法：

  在實際應用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成，應為它分配較多的內存空間。

  通常采取的方法是把內存中可供分配的所有物理塊分成兩部分：

  • 一部分按比例地分配給各進程；另一部分則根據(jù)各進程的優(yōu)先權進行分配，為高優(yōu)先進程適當?shù)卦黾悠湎鄳蓊~。

  在有的系統(tǒng)中，如重要的實時控制系統(tǒng)，則可能是完全按優(yōu)先權為各進程分配其物理塊的。

2.3 頁面調入策略

何時調入頁面：

• 預調頁策略。

  如果進程的許多頁是存放在外存的一個連續(xù)區(qū)域中，一次調入若干個相鄰的頁會比一次調入一頁更高效些。

  但如果調入的一批頁面中的大多數(shù)都未被訪問，則又是低效的。

  于是便考慮采用一種以預測為基礎的預調頁策略，將那些預計在不久之后便會被訪問的頁面預先調入內存。

• 請求調頁策略。

  當進程在運行中需要訪問某部分程序和數(shù)據(jù)時，若發(fā)現(xiàn)其所在的頁面不在內存，便立即提出請求，由OS將其所需頁面謂入內存。

  由請求調頁策略所確定調入的頁是一定會被訪問的，再加之請求調頁策略比較易于實現(xiàn)。

  故在目前的虛擬存儲器中，大多采用此策略。

  但這種策略每次僅調入一頁，故須花費較大的系統(tǒng)開銷，增加了磁盤 IO 的啟動頻率。

從何處調入頁面：

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

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

• UNIX方式。

頁面調入過程：

• 每當程序所要訪問的頁面未在內存時(存在位為“0”)，便向CPU發(fā)出一缺頁中斷，中斷處理程序首先保留CPU環(huán)境，分析中斷原因后轉入缺頁中斷處理程序。

• 該程序通過查找頁表得到該頁在外存的物理塊后，如果此時內存能容納新頁，則啟動磁盤IO，將所缺之頁調入內存，然后修改頁表。

• 如果內存已滿，則須先按照某種置換算法，從內存中選出一頁準備換出:如果該頁未被修改過(修改位為“0”)，可不必將該頁寫回磁盤；

• 但如果此頁已被修改(修改位為“”)，則必須將它寫回磁盤，然后再把所缺的頁調入內存，并修改頁表中的相應表項，置其存在位為“1"，并將此頁表項寫入快表中。

• 在缺頁調入內存后，利用修改后的頁表形成所要訪問數(shù)據(jù)的物理地址，再去訪問內存數(shù)據(jù)。整個頁面的調入過程對用戶是透明的。

缺頁率：

• 假設一個進程的邏輯空間為n頁，系統(tǒng)為其分配的內存物理塊數(shù)為m(m≤n)。

• 如果在進程的運行過程中，訪問頁面成功(即所訪問頁面在內存中)的次數(shù)為S，訪問頁面失敗(即所訪問頁面不在內存中，需要從外存調入)的次數(shù)為F，則該進程總的頁面訪問次數(shù)為A?=?S?+?F，那么該進程在其運行過程中的缺頁率即為：

事實上，在缺頁中斷處理時，當由于空間不足，需要置換部分頁面到外存時，選擇被置換頁面還需要考慮到置換的代價，如頁面是否被修改過。沒有修改過的頁面可以直接放棄，而修改過的頁面則必須進行保存，所以處理這兩種情況時的時間也是不同的。

假設被置換的頁面被修改的概率是β，其缺頁中斷處理時間為ta，被置換頁面沒有被修改的缺頁中斷時間為tb，那么，缺頁中斷處理時間的計算公式為：

3. 頁面置換算法

在進程運行過程中，若其所要訪問的頁面不在內存，而需把它們調入內存，但內存已無空閑空間時，為了保證該進程能正常運行，系統(tǒng)必須從內存中調出一頁程序或數(shù)據(jù)送到磁盤的對換區(qū)中。但應將哪個頁面調出，須根據(jù)一定的算法來確定。

通常，把選擇換出頁面的算法稱為頁面置換算法(Page-Replacement Algorithms)。置換算法的好壞將直接影響到系統(tǒng)的性能。

3.1 最佳(Optimal)置換算法

最佳置換算法是由Belady于1966年提出的一種理論上的算法。

• 其所選擇的被淘汰頁面將是以后永不使用的，或許是在最長(未來)時間內不再被訪問的頁面。

• 采用最佳置換算法通常可保證獲得最低的缺頁率。

• 由于人們目前還無法預知，一個進程在內存的若干個頁面中，哪一個頁面是未來最長時間內不再被訪問的，因而該算法是無法實現(xiàn)的，但可以利用該算法去評價其它算法。

3.2 先進先出(FIFO)頁面置換算法

FIFO算法是最早出現(xiàn)的置換算法。

• 該算法總是淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面予以淘汰。

• 該算法實現(xiàn)簡單，只需把一個進程已調入內存的頁面按先后次序鏈接成一個隊列，并設置一個指針，稱為替換指針，使它總是指向最老的頁面。

• 但該算法與進程實際運行的規(guī)律不相適應，因為在進程中，有些頁面經(jīng)常被訪問，比如，含有全局變量、常用函數(shù)、例程等的頁面，FIFO算法并不能保證這些頁面不被淘汰。

3.3 最近最久未使用(LRU)置換算法

FIFO置換算法的性能之所以較差，是因為它所依據(jù)的條件是各個頁面調入內存的時間，而頁面調入的先后并不能反映頁面的使用情況。

• 最近最久未使用(LRU)的頁面置換算法是根據(jù)頁面調入內存后的使用情況做出決策的。

LRU置換算法的硬件支持：

• 寄存器：

  為了記錄某進程在內存中各頁的使用情況，須為每個在內存中的頁面配置一個移位寄存器，可表示為： R?=?Rn-1Rn-2Rn-3 … R2R1R0

進程訪問某物理塊時，要將相應寄存器的Rn-1位置成1。此時，定時信號將每隔一定時間(例如100 ms)將寄存器右移一位。如果我們把n位寄存器的數(shù)看作是一個整數(shù)，那么，具有最小數(shù)值的寄存器所對應的頁面，就是最近最久未使用的頁面。

• 棧：

  可利用一個特殊的棧保存當前使用的各個頁面的頁面號。

  每當進程訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號，而棧底則是最近最久未使用頁面的頁面號。

3.4 最少使用(LFU)置換算法

在采用LFU算法時，應為在內存中的每個頁面設置一個移位寄存器，用來記錄該頁面被訪問的頻率。

• 該置換算法選擇在最近時期使用最少的頁面作為淘汰頁。

3.5 Clock置換算法

簡單的Clock置換算法：

• 當利用簡單Clock算法時，只需為每頁設置一位訪問位，再將內存中的所有頁面都通過鏈接指針鏈接成一個循環(huán)隊列。

改進型Clock置換算法：

• 在將一個頁面換出時，如果該頁已被修改過，便須將該頁重新寫回到磁盤上；但如果該頁未被修改過，則不必將它拷回磁盤。

• 對于修改過的頁面，在換出時所付出的開銷比未修改過的頁面大，或者說，置換代價大。

• 在改進型Clock算法中，除須考慮頁面的使用情況外，還須再增加一個因素——置換代價。

3.6 頁面緩沖算法(PBA)

影響頁面換進換出效率的若干因素：

• 頁面置換算法。

• 寫回磁盤的頻率。

• 讀入內存的頻率。

頁面緩沖算法PBA：

• PBA算法的主要特點是：

  • 顯著地降低了頁面換進、換出的頻率，使磁盤I/O的操作次數(shù)大為減少，因而減少了頁面換進、換出的開銷；

  • 正是由于換入換出的開銷大幅度減小，才能使其采用一種較簡單的置換策略，如先進先出(FIFO)算法，它不需要特殊硬件的支持，實現(xiàn)起來非常簡單。

為了顯著降低頁面換進、換出的頻率，在內存中設置了如下兩個鏈表：

• 空閑頁面鏈表。

• 修改頁面鏈表。

3.7 訪問內存的有效時間

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

4. “抖動”與工作集

由于請求分頁式虛擬存儲器系統(tǒng)的性能優(yōu)越，在正常運行情況下，它能有效地減少內存碎片，提高處理機的利用率和吞吐量，故是目前最常用的一種系統(tǒng)。

但如果在系統(tǒng)中運行的進程太多，進程在運行中會頻繁地發(fā)生缺頁情況，這又會對系統(tǒng)的性能產生很大的影響，故還須對請求分頁系統(tǒng)的性能做簡單的分析。

4.1 多道程序度與“抖動”

多道程序度與處理機的利用率：

• 由于虛擬存儲器系統(tǒng)能從邏輯上擴大內存，這時，只需裝入一個進程的部分程序和數(shù)據(jù)便可開始運行，故人們希望在系統(tǒng)中能運行更多的進程。

• 即增加多道程序度，以提高處理機的利用率。

產生“抖動”的原因：

• 發(fā)生“抖動”的根本原因是同時在系統(tǒng)中運行的進程太多，由此分配給每一個進程的物理塊太少，不能滿足進程正常運行的基本要求，致使每個進程在運行時，頻繁地出現(xiàn)缺頁，必須請求系統(tǒng)將所缺之頁調入內存。

• 這會使得在系統(tǒng)中排隊等待頁面調進/調出的進程數(shù)目增加。

• 顯然，對磁盤的有效訪問時間也隨之急劇增加，造成每個進程的大部分時間都用于頁面的換進/換出，而幾乎不能再去做任何有效的工作，從而導致發(fā)生處理機的利用率急劇下降并趨于0的情況，稱此時的進程是處于“抖動”狀態(tài)。

4.2 工作集

工作集的基本概念：

• 進程發(fā)生缺頁率的時間間隔與進程所獲得的物理塊數(shù)有關。

• 關于工作集的理論是1968年由Denning提出并推廣的。

• Denning認為：基于程序運行時的局部性原理得知，程序在運行期間，對頁面的訪問是不均勻的，在一段時間內僅局限于較少的頁面，在另一段時間內，又可能僅局限于對另一些較少的頁面進行訪問。

• 這些面被稱為活躍頁面。如果能夠預知程序在某段時間間隔內要訪問哪些頁面，并將它們內存，將會大大降低缺頁率，從而可顯著地提高處理機的利用率。

工作集的定義：

• 工作集指在某段時間間隔Δ里，進程實際所要訪問頁面的集合。

• Denning指出，雖然程序只需要少量的幾頁在內存便可運行，但為了較少地產生缺頁，應將程序的全部工作集裝入內存中。

• 然而我們無法事先預知程序在不同時刻將訪問哪些頁面，故仍只有像置換算法那樣，用程序的過去某段時間內的行為作為程序在將來某段時間內行為的近似。

4.3 “抖動”的預防方法

采取局部置換策略：

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

• 根據(jù)這種策略，當某進程發(fā)生缺頁時，只能在分配給自己的內存空間內進行置換，不允許從其它進程去獲得新的物理塊。

• 這樣，即使該進程發(fā)生了“抖動”，也不會對其它進程產生影響，于是可把該進程“抖動”所造成的影響限制在較小的范圍內。

• 該方法雖然簡單易行，但效果不是很好，因為在某進程發(fā)生“抖動”后，它還會長期處在磁盤IO的等待隊列中，使隊列的長度增加，這會延長其它進程缺頁中斷的處理時間，也就是延長了其它進程對磁盤的訪問時間。

把工作集算法融入到處理機調度中：

• 當調度程序發(fā)現(xiàn)處理機利用率低下時，它將試圖從外存調入一個新作業(yè)進入內存，改善處理機的利用率。

• 如果在調度中融入了工作集算法，則在調度程序從外存調入作業(yè)之前，必須先檢查每個進程在內存的駐留頁面是否足夠多。

• 如果都已足夠多，此時便可以從外存調入新的作業(yè)，不會因新作業(yè)的調入而導致缺頁率的增加；反之，如果有些進程的內存頁面不足，則應首先為那些缺頁率居高的作業(yè)增加新的物理塊，此時將不再調入新的作業(yè)。

利用“L=S”準則調節(jié)缺頁率：

• Denning于1980年提出了L=S的準則來調節(jié)多道程序度，其中L是缺頁之間的平均時間，S是平均缺頁服務時間，即用于置換一個頁面所需的時間。

• 如果是L遠比S大，說明很少發(fā)生缺頁，磁盤的能力尚未得到充分的利用；反之，如果是L比S小，則說明頻繁發(fā)生缺頁，缺頁的速度已超過磁盤的處理能力。只有當L與S接近時，磁盤和處理機都可達到它們的最大利用率。

• 理論和實踐都已證明，利用L=S準則，對于調節(jié)缺頁率是十分有效的

選擇暫停的進程：

• 當多道程序度偏高時，已影響到處理機的利用率，為了防止發(fā)生“抖動”，系統(tǒng)必須減少多道程序的數(shù)目。

• 此時應基于某種原則選擇暫停某些當前活動的進程，將它們調出到磁盤上，以便把騰出的內存空間分配給缺頁率發(fā)生偏高的進程。

• 系統(tǒng)通常都是采取與調度程序一致的策略，即首先選擇暫停優(yōu)先級最低的進程，若需要，再選擇優(yōu)先級較低的進程，當內存還顯擁擠時，還可進一步選擇暫停一個并不十分重要、但卻較大的進程，以便能釋放出較多的物理塊，或者暫停剩余執(zhí)行時間最多的進程等。

5. 請求分段存儲管理方式

5.1 請求分段中的硬件支持

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

請求段表機制：

• 在請求分段式管理中所需的主要數(shù)據(jù)結構是請求段表。在該表中除了具有請求分頁機制中有的訪問字段A、修改位M、存在位P和外存始址四個字段外，還增加了存取方式字段和增補位。這些字段供程序在調進、調出時參考。

缺段中斷機構：

• 在請求分段系統(tǒng)中采用的是請求調段策略。

• 每當發(fā)現(xiàn)運行進程所要訪問的段尚未調入內存時，便由缺段中斷機構產生一缺段中斷信號，進入OS后，由缺段中斷處理程序將所需的段調入內存。

• 與缺頁中斷機構類似，缺段中斷機構同樣需要在一條指令的執(zhí)行期間產生和處理中斷，以及在一條指令執(zhí)行期間，可能產生多次缺段中斷。

• 但由于分段是信息的邏輯單位，因而不可能出現(xiàn)一條指令被分割在兩個分段中，和一組信息被分割在兩個分段中的情況。

地址變換機構：

• 請求分段系統(tǒng)中的地址變換機構是在分段系統(tǒng)地址變換機構的基礎上形成的。

• 因為被訪問的段并非全在內存，所以在地址變換時，若發(fā)現(xiàn)所要訪問的段不在內存，必須先將所缺的段調入內存，并修改段表，然后才能再利用段表進行地址變換。

• 為此，在地址變換機構中又增加了某些功能，如缺段中斷的請求及處理等。

5.2 分段的共享與保護

共享段表：

為了實現(xiàn)分段共享，可在系統(tǒng)中配置一張共享段表，所有各共享段都在共享段表中占有一表項。

在表項的上面記錄了共享段的段號、段長、內存始址、狀態(tài)(存在)位、外存始址以及共享計數(shù)等信息。接下去就是記錄了共享此分段的每個進程的情況。

• 共享進程計數(shù)count。

  非共享段僅為一個進程所需要。當進程不再需要該段時，可立即釋放該段，并由系統(tǒng)回收該段所占用的空間。而共享段是為多個進程所需要的，為記錄有多少進程正在共享該分段,須設置共享進程計數(shù)count。當某進程不再需要而釋放它時，系統(tǒng)并不立即回收該段所占內存區(qū)，而是檢查count是否為0，若不是0，則表示還有進程需要它，僅當所有共享該段的進程全都不再需要它時，此時count為0，才由系統(tǒng)回收該段所占內存區(qū)。

• 存取控制字段。

  對于一個共享段，應為不同的進程賦予不同的存取權限。例如，對于文件主，通常允許他讀和寫;而對其它進程，則可能只允許讀，甚至只允許執(zhí)行。

• 段號。

  對于一個共享段，在不同的進程中可以具有不同的段號，每個進程可用自已進程的段號去訪問該共享段。

共享段的分配：

• 共享段的分配由于共享段是供多個進程所共享的，因此，對共享段的內存分配方法，與非共享段的內存分配方法有所不同。

• 在為共享段分配內存時，對第一個請求使用該共享段的進程，由系統(tǒng)為該共享段分配一物理區(qū)，再把共享段調入該區(qū)，同時將該區(qū)的始址填入請求進程的段表的相應項中，還須在共享段表中增加一表項，填寫請求使用該共享段的進程名、段號和存取控制等有關數(shù)據(jù)，把count置為1。

• 當又有其它進程需要調用該共享段時，由于該共享段已被調入內存，故此時無須再為該段分配內存，而只需在調用進程的段表中增加一表項，填寫該共享段的物理地址。

• 在共享段的段表中增加一個表項，填上調用進程的進程名、該共享段在本進程中的段號、存取控制等，再執(zhí)行count=count+1操作，以表明有兩個進程共享該段。

• 以后，凡有進程需要訪問此共享段的，都按上還方式在共享段的段表中增加一個表項。

共享段的回收：

• 當共享此段的某進程不再需要該段時，應將該段釋放，包括撤消在該進程段表中共享段所對應的表項，以及執(zhí)行count=count-1操作。

• 若結果為0，則須由系統(tǒng)回收該共享段的物理內存，以及取消在共享段表中該段所對應的表項，表明此時已沒有進程使用該段否則(減1結果不為0)，只是取消調用者進程在共享段表中的有關記錄。

分段保護：

• 越界檢查。

  越界檢查是利用地址變換機構來完成的。

  • 在地址變換機構中設置了段表寄存器用于存放段表始址和段表長度信息。

  • 在進行地址變換時，首先將邏輯地址空間的段號與段表長度進行比較，如果段號等于或大于段表長度，將發(fā)出地址越界中斷信號。

  • 此外，還在段表中為每個段設置有段長字段，在進行地址變換時，還要檢查段內地址是否等于或大于段長，若大于段長，將產生地址越界中斷信號，從而保證了每個進程只能在自己的地址空間內運行。

• 存取控制檢查。

  存取控制檢查是以段為基本單位進行的。

  • 在段表的每個表項中都設置了一個“存取控制”字段，用于規(guī)定對該段的訪問方式。

  • 通常的訪問方式有:

    只讀，即只允許進程對該段中的程序或數(shù)據(jù)進行讀訪問:

    只執(zhí)行，即只允許進程調用該段去執(zhí)行，但不準讀該段的內容，更不允許對該目執(zhí)行寫操作:

    讀/寫，即允許進程對該段進行讀/寫訪問。

  對于共享段面言，存取控制就顯得尤為重要，因而對不同的進程應賦予不同的讀寫權限。

  這時，既要保證信息的安全性，又要滿足運行需要。

例如，對于一個企業(yè)的財務賬目，應該只允許會計人員進行讀或寫，允許領導及有關人員去讀。而對于一般人員，則既不準讀，更不能寫。值得一提的是，這里所介紹的存取控制檢查是基于硬件實現(xiàn)的，它能較好地保證信息的安全，因為攻擊者很難對存取控制字段進行修改。

• 環(huán)保護機構。

  這是一種功能較完善的保護機制。在該機制中規(guī)定：低編號的環(huán)具有高優(yōu)先權。

  OS核心處于0號環(huán)內；某些重要的實用程序和操作系統(tǒng)服務占居中間環(huán)；而一般的應用程序，則被安排在外環(huán)上。

  在環(huán)系統(tǒng)中，程序的訪問和遇用應道循以下規(guī)則：

  • 一個程序可以訪問駐留在相同環(huán)或較低特權環(huán)(外環(huán))中的數(shù)據(jù)；

  • 一個程序可以調用駐留在相同環(huán)或較高特權環(huán)(內環(huán))中的服務。

6. 補充

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

  常規(guī)存儲器管理方式具有兩大特征，即一次性和駐留性。這兩個特征對系統(tǒng)性能產生了顯著的影響。

  兩大特征

  1. 一次性：指作業(yè)或進程必須一次性全部裝入內存后才能開始運行。這意味著，在程序執(zhí)行之前，所有需要的代碼和數(shù)據(jù)都必須被加載到內存中。

  2. 駐留性：指在作業(yè)或進程裝入內存后，會一直保持駐留在內存中，直到作業(yè)或進程結束。這意味著，即使某些程序或數(shù)據(jù)在程序運行過程中暫時不需要，它們也會繼續(xù)占用內存空間。

  對系統(tǒng)性能的影響

  1. 內存資源浪費：

     • 由于一次性特征，如果程序很大，而可用內存不足以容納整個程序，那么程序將無法運行。這會導致內存資源的浪費，因為即使程序的部分代碼或數(shù)據(jù)在運行時并不需要，也必須全部加載到內存中。

     • 由于駐留性特征，一些在程序運行過程中暫時不需要的程序或數(shù)據(jù)會繼續(xù)占用內存空間，而一些需要運行的作業(yè)又無法再裝進運行，這同樣會導致內存資源的浪費。

  2. 系統(tǒng)性能下降：

     • 當內存資源被大量占用時，系統(tǒng)的整體性能可能會受到影響。例如，如果內存不足，系統(tǒng)可能會頻繁地進行磁盤I/O操作，以交換內存中的數(shù)據(jù)，這會導致程序運行速度的下降。

     • 同時，由于內存資源的浪費，系統(tǒng)可能無法同時運行多個程序或進程，這也會限制系統(tǒng)的并發(fā)性和多任務處理能力。

  綜上所述，常規(guī)存儲器管理方式的一次性和駐留性特征雖然簡化了內存管理的復雜性，但也帶來了內存資源浪費和系統(tǒng)性能下降的問題。因此，在現(xiàn)代操作系統(tǒng)中，通常采用更加靈活的存儲器管理方式，如虛擬內存、分頁存儲管理等，以更好地利用內存資源并提高系統(tǒng)性能。

• 什么是程序運行時的時間局限性和空間局限性?

  程序運行時的時間局限性和空間局限性是計算機科學中的兩個重要概念，它們描述了程序在執(zhí)行過程中訪問指令和存儲單元的特性。

  時間局限性

  時間局限性指的是，如果程序中的某條指令被執(zhí)行，那么在不久的將來，該指令可能會再次被執(zhí)行。同樣地，如果某個存儲單元被訪問，那么在不久的將來，該存儲單元也可能再次被訪問。這種重復訪問的特性通常是由于程序中存在大量的循環(huán)操作所導致的。在循環(huán)結構中，某些指令或存儲單元會被反復執(zhí)行或訪問，因此它們具有較高的時間局部性。

  空間局限性

  空間局限性則是指，一旦程序訪問了某個存儲單元，那么在不久的將來，其附近的存儲單元也可能被訪問。這意味著，程序在一段時間內所訪問的地址可能會集中在一定的范圍內。這種特性通常是由于程序的順序執(zhí)行所導致的。在順序執(zhí)行的過程中，程序往往會按照一定的順序訪問存儲單元，因此相鄰的存儲單元具有較高的空間局部性。

  影響與意義

  時間局限性和空間局限性對于程序設計和優(yōu)化具有重要意義。了解這些特性可以幫助我們更好地設計存儲結構和算法，以提高程序的執(zhí)行效率和性能。例如，在緩存設計中，可以利用時間局部性和空間局部性來預測哪些數(shù)據(jù)或指令可能會被頻繁訪問，并將它們存儲在緩存中以提高訪問速度。此外，在操作系統(tǒng)中的虛擬內存管理中，頁面置換算法也考慮了時間局限性和空間局限性，以決定哪些頁面應該被保留在內存中，哪些頁面應該被置換出去。

  綜上所述，程序運行時的時間局限性和空間局限性是描述程序訪問指令和存儲單元特性的重要概念。它們對于程序設計和優(yōu)化具有重要意義，可以幫助我們更好地利用存儲資源和提高程序的執(zhí)行效率。

• 虛擬存儲器有哪些特征? 其中最本質的特征是什么?

  虛擬存儲器具有多個顯著特征，這些特征共同定義了其功能和性能。以下是虛擬存儲器的主要特征及其最本質特征的探討：

  虛擬存儲器的特征

  1. 虛擬性：

     • 虛擬性是指虛擬存儲器能夠從邏輯上擴充內存容量，使用戶所看到的內存容量遠大于實際的物理內存容量。

     • 這是虛擬存儲器所表現(xiàn)出的最重要的特征，也是其設計的主要目標之一。

  2. 離散性：

     • 離散性是指內存分配時采用離散分配的方式，即內存空間被劃分為多個小的、獨立的存儲單元（如頁或段），這些單元可以獨立地被分配和釋放。

     • 離散分配方式避免了連續(xù)分配方式可能導致的內存碎片問題，提高了內存的利用率。

  3. 多次性：

     • 多次性是指一個作業(yè)或進程可以被分成多次調入內存運行。

     • 在程序運行時，只將當前需要運行的那部分程序和數(shù)據(jù)裝入內存，以后再需要時再從外存調入。

     • 這種多次性特征使得程序可以更加靈活地利用內存資源，提高了系統(tǒng)的并發(fā)性和多任務處理能力。

  4. 對換性：

     • 對換性是指允許在作業(yè)或進程運行過程中進行內存和外存之間的數(shù)據(jù)交換。

     • 當內存中的某些頁面或段暫時不需要時，可以將它們換出到外存中，以釋放內存空間給其他需要的作業(yè)或進程。

     • 當需要這些頁面或段時，再從外存中調入內存。

  最本質的特征

  關于虛擬存儲器最本質的特征，存在不同的觀點。一種觀點認為，離散性是虛擬存儲器最本質的特征，因為離散分配方式使得內存空間可以被更加靈活地利用，避免了連續(xù)分配方式可能導致的內存碎片問題。另一種觀點則認為，虛擬性是虛擬存儲器最本質的特征，因為虛擬性使得用戶能夠看到一個比實際物理內存容量大得多的邏輯內存空間，從而提高了系統(tǒng)的靈活性和可擴展性。

  從虛擬存儲器的定義和功能來看，虛擬性確實是一個非常重要的特征。它使得系統(tǒng)能夠為用戶提供更大的內存空間，而無需增加實際的物理內存。然而，離散性也是虛擬存儲器實現(xiàn)的基礎之一，沒有離散性就不可能實現(xiàn)虛擬存儲器。因此，可以說虛擬性和離散性都是虛擬存儲器的重要特征，而其中最本質的特征可能取決于具體的定義和視角。

  綜上所述，虛擬存儲器具有虛擬性、離散性、多次性和對換性等特征。這些特征共同定義了虛擬存儲器的功能和性能，并使得虛擬存儲器成為現(xiàn)代操作系統(tǒng)中不可或缺的一部分。

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

  實現(xiàn)虛擬存儲器需要以下硬件支持：

  1. 足夠容量的外存：

     • 外存（如硬盤、SSD等）是虛擬存儲器的重要組成部分，用于存放當前未調入內存的程序和數(shù)據(jù)。

     • 當需要時，可以從外存中調入數(shù)據(jù)到內存，以滿足程序的運行需求。

  2. 一定容量的內存：

     • 內存是程序運行時的主要存儲空間，用于存放當前正在執(zhí)行的程序和數(shù)據(jù)。

     • 在虛擬存儲器系統(tǒng)中，內存需要能夠容納一部分程序和數(shù)據(jù)，以便程序能夠正常運行。

  3. 地址變換機構：

     • 地址變換機構是實現(xiàn)虛擬存儲器中的虛擬地址到物理地址映射的關鍵硬件。

     • 它負責將程序中的虛擬地址轉換為實際的物理地址，以便從內存中正確地讀取或寫入數(shù)據(jù)。

     • 在現(xiàn)代計算機系統(tǒng)中，地址變換機構通常通過頁表或段表等數(shù)據(jù)結構來實現(xiàn)。

  4. 請求分頁/分段系統(tǒng)：

     • 請求分頁/分段系統(tǒng)是實現(xiàn)虛擬存儲器的軟件部分，但也需要硬件的支持。

     • 在請求分頁系統(tǒng)中，硬件需要提供頁表機制、缺頁中斷機制和地址變換機構等。

     • 在請求分段系統(tǒng)中，硬件則需要提供段表機制、缺段中斷機制和地址變換機構等。

  綜上所述，實現(xiàn)虛擬存儲器需要足夠容量的外存、一定容量的內存、地址變換機構以及請求分頁/分段系統(tǒng)的硬件支持。這些硬件支持共同構成了虛擬存儲器的基礎，使得系統(tǒng)能夠為用戶提供更大的內存空間，提高系統(tǒng)的靈活性和可擴展性。

• 實現(xiàn)虛擬存儲器需要哪幾個關鍵技術?

  實現(xiàn)虛擬存儲器需要以下幾個關鍵技術：

  1. 分頁技術：

     • 分頁技術是將物理內存和虛擬內存劃分為固定大小的頁（或稱為塊）。程序在執(zhí)行時，只需將當前需要運行的頁調入內存，其余頁則保留在外存中。

     • 分頁技術使得程序可以在不需要全部加載到內存中的情況下運行，從而提高了內存的利用率。

  2. 頁面置換算法：

     • 頁面置換算法用于在內存不足時，決定哪些頁需要從內存中置換出去，以便為新的頁騰出空間。

     • 常見的頁面置換算法包括FIFO（先進先出）、LRU（最近最少使用）、LFU（最不經(jīng)常使用）和Clock算法等。

     • 頁面置換算法的選擇對系統(tǒng)的性能有很大影響，需要根據(jù)具體的應用場景進行選擇。

  3. 頁面映射：

     • 頁面映射技術用于建立虛擬地址與物理地址之間的映射關系。

     • 在程序運行時，CPU會產生虛擬地址，頁面映射機制將這些虛擬地址轉換為物理地址，以便程序能夠正確地訪問內存。

     • 頁面映射通常通過頁表來實現(xiàn)，頁表是一個數(shù)據(jù)結構，它記錄了每個虛擬頁面對應的物理頁面地址。

  4. 內存保護：

     • 內存保護技術用于保護不同進程的內存空間，防止進程間的干擾。

     • 通過設置頁面屬性、用戶權限等方式，可以確保每個進程只能訪問其自己的內存空間，而不能訪問其他進程的內存空間。

     • 內存保護技術有助于提高系統(tǒng)的安全性和穩(wěn)定性。

  5. 頁面共享：

     • 頁面共享技術允許多個進程共享同一個物理內存頁。

     • 通過頁面共享，可以減少內存開銷，提高內存的利用率。

     • 頁面共享技術特別適用于需要運行多個相同或相似程序的場景。

  6. 缺頁中斷處理：

     • 當CPU訪問的頁面不在物理內存中時，會觸發(fā)缺頁中斷。

     • 缺頁中斷處理程序負責從外存中調入所需的頁面到內存中，并更新頁表。

     • 缺頁中斷處理是實現(xiàn)虛擬存儲器不可或缺的一部分，它確保了程序在需要時能夠訪問到所需的頁面。

  綜上所述，實現(xiàn)虛擬存儲器需要分頁技術、頁面置換算法、頁面映射、內存保護、頁面共享以及缺頁中斷處理等關鍵技術。這些技術共同構成了虛擬存儲器的基礎，使得系統(tǒng)能夠為用戶提供更大的內存空間，提高系統(tǒng)的靈活性和可擴展性。

• 在請求分頁系統(tǒng)中，頁表應包括哪些數(shù)據(jù)項? 每項的作用是什么?

  在請求分頁系統(tǒng)中，頁表是內存管理的重要數(shù)據(jù)結構，用于記錄虛擬頁面對應的物理頁面信息。頁表通常包含以下數(shù)據(jù)項，每項都有其特定的作用：

  1. 頁號：

     • 頁號用于標識虛擬內存中的頁面。

     • 在頁表中，頁號是唯一的，用于區(qū)分不同的虛擬頁面。

  2. 物理塊號（或頁框號）：

     • 物理塊號用于標識物理內存中的頁面或塊。

     • 它與頁號相對應，表示虛擬頁面在物理內存中的位置。

  3. 狀態(tài)位P：

     • 狀態(tài)位P用于指示該頁是否已調入內存。

     • 當P=1時，表示該頁已調入內存；當P=0時，表示該頁未調入內存，需要從外存中調入。

     • 狀態(tài)位P為系統(tǒng)提供了頁面是否存在的信息，有助于系統(tǒng)快速定位頁面。

  4. 訪問字段A：

     • 訪問字段A用于記錄本頁在一段時間內被訪問的次數(shù)，或記錄本頁最近已有多長時間未被訪問。

     • 這個字段供選擇換出頁面時參考，有助于系統(tǒng)實現(xiàn)頁面置換算法，如LRU算法。

  5. 修改位M：

     • 修改位M表示該頁在調入內存后是否被修改過。

     • 當M=1時，表示該頁已被修改；當M=0時，表示該頁未被修改。

     • 修改位M在置換頁面時非常重要，因為如果頁面被修改過，在置換時需要將其寫回外存，以保證外存中所保留的始終是最新副本。

  6. 外存地址：

     • 外存地址用于指出該頁在外存上的地址。

     • 當頁面未調入內存時，系統(tǒng)可以根據(jù)外存地址從外存中調入該頁。

     • 外存地址是頁面調入和置換過程中的重要參考信息。

  綜上所述，頁表中的這些數(shù)據(jù)項共同構成了虛擬存儲器的基礎，使得系統(tǒng)能夠高效地管理內存，提高內存的利用率和系統(tǒng)的性能。每個數(shù)據(jù)項都有其特定的作用，共同支持著請求分頁系統(tǒng)的正常運行。

• 試比較缺頁中斷機構與一般的中斷，它們之間有何明顯的區(qū)別?

  缺頁中斷與一般的中斷在計算機系統(tǒng)中有明顯的區(qū)別。以下是對這兩者的詳細比較：

  一、定義與產生時機

  1. 缺頁中斷：

     • 在請求分頁系統(tǒng)中，每當所要訪問的頁面不在內存時，便產生一缺頁中斷。

     • 缺頁中斷是在指令執(zhí)行期間，發(fā)現(xiàn)所要訪問的指令或數(shù)據(jù)不在內存時產生和處理的。也就是說，它可能在一條指令執(zhí)行的過程中多次發(fā)生（如指令跨越多個頁面，且這些頁面都不在內存時）。

  2. 一般中斷：

     • 一般中斷是指計算機運行過程中，出現(xiàn)某些意外情況需主機干預時，機器能自動停止正在運行的程序并轉入處理新情況的程序。

     • 一般中斷通常是在一條指令執(zhí)行完畢后，當硬件中斷裝置發(fā)現(xiàn)有中斷請求時才去響應與處理。

  二、處理過程與結果

  1. 缺頁中斷：

     • 缺頁中斷處理時，除了需要保護現(xiàn)場之外，還需要判斷內存中是否有足夠的空間存儲所需的頁，然后再把所需頁調進來使用。

     • 處理完畢后，由于原指令尚未執(zhí)行完（因為所需頁面之前不在內存），所以返回到原指令去重新執(zhí)行。

  2. 一般中斷：

     • 一般中斷處理時，主要任務是保護現(xiàn)場、分析中斷原因、執(zhí)行相應的中斷處理程序。

     • 處理完畢后，返回到被中斷進程的下一條指令去執(zhí)行（因為上一條指令已經(jīng)執(zhí)行完畢），或者根據(jù)系統(tǒng)需要重新調度，去執(zhí)行別的進程程序。

  三、特殊性與影響

  1. 缺頁中斷：

     • 缺頁中斷是一種特殊的中斷，因為它與內存管理緊密相關，是虛擬存儲器實現(xiàn)的關鍵機制之一。

     • 頻繁的缺頁中斷可能會導致系統(tǒng)性能下降，因為每次缺頁都需要從外存中調入頁面，這會增加I/O操作的次數(shù)和時間。

  2. 一般中斷：

     • 一般中斷是計算機系統(tǒng)中常見的現(xiàn)象，用于處理各種異常情況或外部事件。

     • 一般中斷對系統(tǒng)性能的影響取決于中斷的類型和頻率，以及中斷處理程序的復雜性和執(zhí)行時間。

  綜上所述，缺頁中斷與一般的中斷在定義與產生時機、處理過程與結果以及特殊性與影響等方面都存在明顯的區(qū)別。這些區(qū)別使得缺頁中斷成為虛擬存儲器實現(xiàn)中的關鍵機制，而一般中斷則是計算機系統(tǒng)中處理異常情況或外部事件的重要手段。

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

  請求分頁系統(tǒng)中的地址變換過程涉及將程序的邏輯地址（或稱為虛擬地址）轉換為物理地址，以便CPU能夠正確地訪問內存。以下是該過程的詳細步驟：

  1. 分解邏輯地址：

     • 首先，系統(tǒng)需要將程序的邏輯地址分解為頁號（P）和頁內偏移量（w）。邏輯地址通常由兩部分組成：高位的頁號和低位的頁內偏移量。

  2. 查找頁表：

     • 接著，系統(tǒng)使用頁號作為索引，在頁表中查找對應的頁表項。頁表是一個數(shù)據(jù)結構，它記錄了每個邏輯頁面在物理內存中的位置（即物理塊號）以及其他相關信息。

  3. 檢查中斷位：

     • 在找到對應的頁表項后，系統(tǒng)需要檢查該頁的中斷位（也稱為存在位或有效位）。如果中斷位為1，表示該頁已在內存中，可以繼續(xù)進行下一步的地址變換。如果中斷位為0，表示該頁不在內存中，此時會產生缺頁中斷，系統(tǒng)需要暫停當前進程，從外存中調入所需的頁面，并更新頁表。

  4. 更新頁表項（如適用）：

     • 如果產生了缺頁中斷并成功調入了頁面，系統(tǒng)需要更新頁表項中的相關信息，如物理塊號、訪問位、修改位等。

  5. 計算物理地址：

     • 在確認頁面已在內存中后，系統(tǒng)可以使用頁表項中的物理塊號和頁內偏移量來計算物理地址。物理地址的計算公式通常為：物理地址 = 物理塊號 × 頁面大小 + 頁內偏移量。

  6. （可選）快表查找：

     • 在一些現(xiàn)代計算機系統(tǒng)中，為了提高地址變換的速度，通常會設置一個快表（也稱為TLB或轉換后備緩沖器）?？毂硎且粋€小型的緩存，用于存儲最近訪問過的頁表項。在進行地址變換時，系統(tǒng)可以先嘗試在快表中查找對應的頁表項。如果找到，則可以直接使用快表中的信息進行地址變換，而無需訪問主存中的頁表。這樣可以大大減少訪問主存的次數(shù)，提高系統(tǒng)的性能。

  綜上所述，請求分頁系統(tǒng)中的地址變換過程是一個復雜而關鍵的過程，它涉及多個步驟和組件的協(xié)同工作。通過這個過程，系統(tǒng)能夠將程序的邏輯地址轉換為物理地址，從而實現(xiàn)虛擬存儲器的功能。

• 何謂固定分配局部置換和可變分配全局置換的內存分配策略?

  固定分配局部置換和可變分配全局置換是內存分配策略中的兩種重要方式，它們各自具有不同的特點和應用場景。

  固定分配局部置換

  1. 定義：

     • 固定分配是指為每個進程分配一組固定數(shù)目的物理塊（或稱為頁面框），在進程運行期間這些物理塊的數(shù)量不再改變。

     • 局部置換是指如果進程在運行中發(fā)現(xiàn)缺頁（即所需的頁面不在內存中），則只能從分配給該進程的這些物理塊中選出一頁換出（即移出內存），然后再調入一頁，以保證分配給該進程的內存空間總量不變。

  2. 特點：

     • 優(yōu)點：實現(xiàn)相對簡單，因為物理塊的數(shù)量是固定的，不需要動態(tài)調整。

     • 缺點：難以確定每個進程應分配多少物理塊。如果分配的物理塊太少，可能導致頻繁的缺頁中斷和性能下降；如果分配的物理塊太多，則可能浪費內存資源。

  3. 應用場景：

     • 適用于對內存需求相對穩(wěn)定、變化不大的進程。

  可變分配全局置換

  1. 定義：

     • 可變分配是指先為每個進程分配一定數(shù)目的物理塊，在進程運行期間，這些物理塊的數(shù)量可以根據(jù)情況做適當?shù)脑黾踊驕p少。

     • 全局置換是指如果進程在運行中發(fā)現(xiàn)缺頁，則從操作系統(tǒng)（OS）所保留的空閑物理塊隊列中取出一塊分配給該進程，或者以所有進程的全部物理塊為標的，選擇一塊換出（即選擇一個進程的一個頁面移出內存），然后將所缺之頁調入。

  2. 特點：

     • 優(yōu)點：能夠根據(jù)進程的實際需求動態(tài)調整物理塊的數(shù)量，提高了內存的利用率和系統(tǒng)的靈活性。

     • 缺點：實現(xiàn)相對復雜，需要維護一個空閑物理塊隊列，并在缺頁時執(zhí)行全局置換算法。此外，全局置換可能導致某些進程的物理塊數(shù)量減少，進而增加其缺頁率。

  3. 應用場景：

     • 適用于對內存需求變化較大的進程，或者需要高效利用內存資源的系統(tǒng)。

  綜上所述，固定分配局部置換和可變分配全局置換是兩種不同的內存分配策略，它們各自具有優(yōu)缺點和適用的場景。在實際應用中，需要根據(jù)系統(tǒng)的具體需求和進程的特點來選擇合適的策略。

• 在請求分頁系統(tǒng)中，應從何處將所需頁面調入內存?

  在請求分頁系統(tǒng)中，當發(fā)生缺頁中斷時，系統(tǒng)需要從某個位置將所需的頁面調入內存。具體應從何處調入，取決于系統(tǒng)的具體情況和配置。以下是幾種可能的來源：

  1. 對換區(qū)（或稱為交換區(qū)）：

     • 當系統(tǒng)擁有足夠的對換區(qū)空間時，可以優(yōu)先從對換區(qū)調入所需頁面。這是因為對換區(qū)通常采用連續(xù)分配方式，磁盤I/O速度相對較高，可以加快頁面的調入速度。

     • 在進程運行前，可以將與該進程有關的文件從文件區(qū)拷貝到對換區(qū)，以便在需要時快速調入。

     • 對于曾經(jīng)運行過但被換出的頁面，如果它們被保存在對換區(qū)中，那么下次需要時可以從對換區(qū)直接調入。

  2. 文件區(qū)：

     • 當系統(tǒng)缺少足夠的對換區(qū)空間時，或者某些頁面未被修改過（即修改位為0），可以直接從文件區(qū)調入所需頁面。

     • 文件區(qū)通常采用離散分配方式，磁盤I/O速度可能相對較低，但仍然是頁面調入的一個重要來源。

     • 對于那些不會被修改的文件頁面，或者已經(jīng)被換出且未被修改過的頁面，可以直接從文件區(qū)調入。

  3. UNIX系統(tǒng)特有的方式：

     • 在UNIX系統(tǒng)中，如果某進程請求的頁面有可能已調入內存（例如，通過頁面共享機制），則可以直接使用而不再調入。

     • 對于未運行過的頁面，通常從文件區(qū)調入。

     • 對于曾經(jīng)運行過但被換出的頁面，如果它們被保存在對換區(qū)中，則下次需要時從對換區(qū)調入；如果它們未被保存在對換區(qū)中但仍在文件區(qū)中，則從文件區(qū)調入。

  綜上所述，在請求分頁系統(tǒng)中，所需頁面的調入來源可以是對換區(qū)、文件區(qū)或者（在UNIX系統(tǒng)中）已調入內存的共享頁面。具體選擇哪個來源取決于系統(tǒng)的配置、頁面的修改狀態(tài)以及頁面的使用情況。

• 試說明在請求分頁系統(tǒng)中頁面的調入過程。

  在請求分頁系統(tǒng)中，頁面的調入過程是一個關鍵步驟，它確保了當程序需要訪問某個不在內存中的頁面時，系統(tǒng)能夠自動地從外存中調入該頁面。以下是該過程的詳細說明：

  一、缺頁中斷的產生

  1. 當程序試圖訪問一個不在內存中的頁面時，硬件會檢測到這一錯誤，并向CPU發(fā)出一個缺頁中斷。

  2. CPU響應缺頁中斷，并暫停當前程序的執(zhí)行，同時保存當前的環(huán)境（如寄存器內容、程序計數(shù)器等），以便在調入頁面后能夠繼續(xù)執(zhí)行。

  二、缺頁中斷的處理

  1. 保護CPU環(huán)境：中斷處理程序首先會保護CPU的當前環(huán)境，防止在處理缺頁中斷時破壞程序的執(zhí)行狀態(tài)。

  2. 分析中斷原因：接著，中斷處理程序會分析缺頁中斷的原因，確認是由于頁面未調入內存導致的。

  3. 轉入缺頁中斷處理程序：一旦確認是缺頁中斷，系統(tǒng)會轉入專門的缺頁中斷處理程序來處理這一事件。

  三、頁面的調入

  1. 查找頁表：缺頁中斷處理程序會查找頁表，確定缺頁的頁號，并獲取該頁在外存上的物理塊號（或地址）。

  2. 檢查內存狀態(tài)：

     • 如果此時內存有足夠的空閑空間來容納新頁面，系統(tǒng)會直接啟動磁盤I/O操作，將所缺頁面從外存調入內存。

     • 如果內存已滿，系統(tǒng)則需要按照某種置換算法（如LRU、FIFO等）從內存中選出一頁準備換出。

  3. 頁面置換：

     • 如果被選中的頁面未被修改過（即修改位為0），則可以直接將該頁面從內存中移除，無需寫回外存。

     • 如果被選中的頁面已被修改過（即修改位為1），則必須先將該頁面寫回外存，以更新外存中的數(shù)據(jù)。

  4. 調入新頁面：

     在成功置換出舊頁面（如果需要的話）后，系統(tǒng)會啟動磁盤I/O操作，將所缺頁面從外存調入內存，并更新頁表中的相應表項。

     • 將新頁面的物理塊號寫入頁表。

     • 將新頁面的存在位設置為1，表示該頁面已調入內存。

     • 如果系統(tǒng)有快表（TLB），還需要更新快表中的相應表項。

  四、恢復程序執(zhí)行

  1. 在成功調入新頁面后，系統(tǒng)會利用修改后的頁表形成所要訪問的物理地址，并恢復之前保存的CPU環(huán)境。

  2. 然后，系統(tǒng)會繼續(xù)執(zhí)行之前被暫停的程序，從產生缺頁中斷的下一條指令開始執(zhí)行。

  整個頁面的調入過程對用戶是透明的，用戶無需關心頁面是如何被調入內存的。系統(tǒng)通過缺頁中斷和頁面置換等機制，確保了程序的連續(xù)執(zhí)行和內存的有效利用。

• 在請求分頁系統(tǒng)中，常采用哪幾種頁面置換算法?

  在請求分頁系統(tǒng)中，常用的頁面置換算法主要有以下幾種：

  1. 最佳（Optimal，OPT）置換算法：

     • 原理：選擇在將來最長時間內不再被訪問的頁面淘汰出去。

     • 優(yōu)點：可保證獲得最低的缺頁中斷率，是一種理想化的置換算法，性能最好。

     • 缺點：要求操作系統(tǒng)能知道進程“將來”頁面的使用情況，但這是不可能實現(xiàn)的，因為程序的執(zhí)行是不可預測的。

  2. 先進先出（First In First Out，FIFO）置換算法：

     • 原理：總是淘汰最先進入內存的頁面。該算法實現(xiàn)簡單，只需把一個進程已調入內存的頁面，按先后次序鏈接成一個隊列，并設置一個指針（稱為替換指針），使它總是指向最老頁面。

     • 優(yōu)點：實現(xiàn)簡單。

     • 缺點：與進程實際運行的規(guī)律不相適應，沒有考慮到動態(tài)變化情況。對于某一特定的頁面走向，先進先出算法會出現(xiàn)缺頁中斷率隨著被分配的內存塊增加反而上升的反?，F(xiàn)象，即Belady現(xiàn)象。

  3. 最近最久未使用（Least Recently Used，LRU）置換算法：

     • 原理：選擇最近的過去中最久未訪問的頁面淘汰出去。

     • 優(yōu)點：考慮了頁面調入內存后的使用情況，具有較好的性能。

     • 缺點：要快速地找出最近最久未被使用的頁面，需要花費巨大的系統(tǒng)開銷，往往需要較多的硬件支持。因此，在實際系統(tǒng)中往往使用其近似算法。

  4. CLOCK置換算法：

     • 原理：也被稱為最近未使用（Not Recently Used，NUR）置換算法，是LRU算法的近似算法。它根據(jù)訪問位和修改位的檢查結果，按照特定的順序（如未被訪問且未被修改、未被訪問但被修改、已被訪問但未被修改、已被訪問且被修改）淘汰頁面。

     • 優(yōu)點：實現(xiàn)相對簡單，且能夠在一定程度上模擬LRU算法的行為。

     • 缺點：性能略低于LRU算法，但通常優(yōu)于FIFO算法。

  綜上所述，這些頁面置換算法各有優(yōu)缺點，適用于不同的應用場景。在實際系統(tǒng)中，需要根據(jù)具體需求和資源情況選擇合適的算法。

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

  實現(xiàn)LRU（Least Recently Used）算法所需的硬件支持主要包括寄存器和棧（或類似的硬件結構）。以下是詳細的解釋：

  1. 寄存器：

     • 寄存器在LRU算法中用于記錄某進程在內存中各頁的使用情況。具體來說，寄存器可以保存頁面的訪問時間戳或某種形式的“最近使用”標記。

     • 當進程訪問某個頁面時，系統(tǒng)會更新該頁面在寄存器中的時間戳或標記，以反映其最近的使用情況。

     • 寄存器具有較快的訪問速度，能夠高效地支持LRU算法的實現(xiàn)。

  2. 棧：

     • 棧在LRU算法中用于保存當前使用的各個頁面的頁面號。棧的特點是后進先出（LIFO），這與LRU算法的思想在某種程度上是相似的，因為最近使用的頁面往往會被頻繁訪問，并因此而被保留在棧頂。

     • 當進程訪問某個頁面時，如果該頁面不在棧中，則將其頁面號壓入棧頂；如果頁面已在棧中，則將其從棧中移除并重新壓入棧頂，以更新其“最近使用”的標記。

     • 當需要置換頁面時，可以從棧底（即最久未使用的頁面）選擇頁面進行置換。

  需要注意的是，雖然棧在概念上與LRU算法有一定的契合度，但在實際實現(xiàn)中，由于棧的操作（如壓棧、彈棧）相對簡單，而LRU算法需要更復雜的訪問歷史記錄和比較操作，因此通常不會直接使用棧來實現(xiàn)LRU算法。相反，更常見的是使用數(shù)組、鏈表或哈希表等數(shù)據(jù)結構來模擬LRU算法的行為。

  此外，現(xiàn)代計算機系統(tǒng)中還可能采用專門的硬件結構（如LRU緩存標簽）來支持LRU算法的實現(xiàn)，以提高算法的性能和效率。這些硬件結構通常與處理器的緩存系統(tǒng)緊密結合，能夠快速地識別并置換最久未使用的緩存行。

  綜上所述，實現(xiàn)LRU算法所需的硬件支持主要包括寄存器和棧（或類似的硬件結構），但具體實現(xiàn)方式可能因系統(tǒng)架構和性能需求而有所不同。

• 試說明改進型Clock置換算法的基本原理。

  改進型Clock置換算法的基本原理是在傳統(tǒng)的Clock置換算法基礎上，增加了一個考慮因素——置換代價。具體來說，它引入了一個修改位（M位），用于指示頁面是否被修改過。在選擇淘汰頁面時，改進型Clock算法會優(yōu)先考慮那些既未使用過又未被修改過的頁面，因為這些頁面在置換出內存時不需要寫回磁盤，從而降低了置換代價。

  以下是改進型Clock置換算法的基本步驟：

  1. 初始化：

     • 為每個頁面設置一個訪問位（A位）和一個修改位（M位）。

     • 訪問位（A位）：用于記錄頁面是否被訪問過，每次訪問頁面時將其置為1。

     • 修改位（M位）：用于記錄頁面是否被修改過，如果頁面被修改過則置為1，否則為0。

  2. 循環(huán)掃描：

     • 從一個起始位置開始，循環(huán)掃描內存中的頁面。

     • 在每次掃描過程中，根據(jù)頁面的A位和M位來判斷是否滿足置換條件。

  3. 選擇淘汰頁面：

     • 首選淘汰頁面：尋找A=0且M=0的頁面，即最近既未被訪問又未被修改的頁面。這樣的頁面是最佳淘汰頁，因為它們在置換出內存時不需要寫回磁盤。

     • 次選淘汰頁面：如果找不到A=0且M=0的頁面，則尋找A=0且M=1的頁面，即最近未被訪問但被修改過的頁面。這樣的頁面雖然不是最佳淘汰頁，但在必要時也可以被置換出內存。在置換出之前，需要將其內容寫回磁盤。

  4. 更新訪問位：

     • 在每次成功置換頁面后，需要將新調入的頁面訪問位A置為1，表示該頁面已被訪問過。

     • 同時，將掃描過的所有頁面的訪問位A都置為0（這一步在首次掃描時可能不執(zhí)行，具體取決于算法的實現(xiàn)）。

  5. 重復掃描：

     • 如果在一次掃描過程中沒有找到合適的淘汰頁面，則繼續(xù)從起始位置開始重復掃描，直到找到滿足條件的頁面為止。

  6. 置換頁面：

     • 一旦找到滿足條件的淘汰頁面，就將其內容置換出內存，并將新調入的頁面寫入內存中的相應位置。

  7. 更新修改位：

     • 如果新調入的頁面是從磁盤中讀取的，并且其內容在內存中發(fā)生了修改，則需要將其修改位M置為1。

  通過引入修改位M并考慮置換代價，改進型Clock置換算法能夠在保證較低缺頁率的同時，減少頁面置換時的磁盤I/O操作，從而提高系統(tǒng)的整體性能。

• 影響頁面換進換出效率的若干因素是什么?

  影響頁面換進換出效率的因素主要包括以下幾個方面：

  1. 頁面置換算法：

     • 頁面置換算法是影響頁面換進換出效率的最重要因素。不同的置換算法會導致不同的缺頁率和頁面置換開銷。

     • 常見的置換算法如LRU（最近最少使用）、FIFO（先進先出）、OPT（最佳）以及Clock算法等，它們各有優(yōu)缺點，適用于不同的應用場景。

     • LRU算法通常能夠獲得較低的缺頁率，但實現(xiàn)起來較為復雜，需要額外的硬件支持。FIFO算法實現(xiàn)簡單，但可能導致較高的缺頁率。OPT算法理論上最優(yōu)，但無法實現(xiàn)，因為它需要預知未來的頁面訪問情況。Clock算法則是一種折中的選擇，它結合了LRU和FIFO的特點，實現(xiàn)相對簡單且性能較好。

  2. 寫回磁盤的頻率：

     • 寫回磁盤的頻率也是影響頁面換進換出效率的重要因素。如果每次頁面被置換出內存時都立即寫回磁盤，那么磁盤I/O操作的次數(shù)將非常頻繁，從而增加頁面置換的開銷。

     • 為了減少磁盤I/O操作的次數(shù)，可以在系統(tǒng)中建立一個已修改換出頁面鏈表。當頁面被置換出內存時，如果它已被修改過，則將其掛在鏈表上而不是立即寫回磁盤。只有當鏈表中的頁面數(shù)量達到一定值時，再將它們一起寫回到磁盤上。這樣可以顯著減少磁盤I/O操作的次數(shù)，提高頁面換進換出的效率。

  3. 讀入內存的頻率：

     • 讀入內存的頻率同樣對頁面換進換出效率有重要影響。如果頻繁地從磁盤中讀取頁面到內存中，那么磁盤I/O操作的次數(shù)也會相應增加，從而降低頁面換進換出的效率。

     • 為了減少讀入內存的頻率，可以利用已修改換出頁面鏈表中的頁面。當需要訪問某個頁面時，如果它已經(jīng)在鏈表中存在，那么可以直接從鏈表中獲取而不需要從磁盤中讀取。這樣可以減少磁盤I/O操作的次數(shù)，提高頁面換進的效率。

  4. 頁面大小：

     • 頁面大小也會影響頁面換進換出的效率。較大的頁面可以減少頁面置換的次數(shù)，因為每次置換可以覆蓋更多的數(shù)據(jù)。但是，較大的頁面也可能導致更高的內部碎片率，因為不是所有的頁面都能被完全填滿。

     • 因此，在選擇頁面大小時需要權衡利弊，根據(jù)具體的應用場景和系統(tǒng)需求來確定合適的頁面大小。

  5. 進程所分配的物理塊的數(shù)目：

     • 進程所分配的物理塊的數(shù)目也會影響頁面換進換出的效率。如果分配給進程的物理塊數(shù)目較少，那么進程在運行過程中更容易發(fā)生缺頁中斷，從而增加頁面置換的頻率和開銷。

     • 相反，如果分配給進程的物理塊數(shù)目較多，那么進程在運行過程中發(fā)生缺頁中斷的概率就會降低，頁面置換的頻率和開銷也會相應減少。但是，過多的物理塊分配也可能導致內存資源的浪費和內部碎片的增加。

  6. 程序固有特性：

     • 程序的固有特性也會對頁面換進換出的效率產生影響。例如，如果程序具有局部性原理（即程序在一段時間內通常只訪問一個局部區(qū)域內的數(shù)據(jù)），那么頁面置換的頻率和開銷就會相對較低。

     • 相反，如果程序的數(shù)據(jù)訪問模式比較隨機或不規(guī)則，那么頁面置換的頻率和開銷就會相對較高。

  綜上所述，影響頁面換進換出效率的因素是多方面的，包括頁面置換算法、寫回磁盤的頻率、讀入內存的頻率、頁面大小、進程所分配的物理塊的數(shù)目以及程序的固有特性等。在實際應用中，需要根據(jù)具體的應用場景和系統(tǒng)需求來綜合考慮這些因素，并采取相應的優(yōu)化措施來提高頁面換進換出的效率。

• 頁面緩沖算法的主要特點是什么? 它是如何降低頁面換進、換出的頻率的?

  頁面緩沖算法（Page Buffering Algorithm）的主要特點及其降低頁面換進、換出頻率的機制可以歸納如下：

  主要特點

  1. 顯著降低頁面換進、換出頻率：頁面緩沖算法通過優(yōu)化頁面置換策略，顯著減少了頁面在內存和磁盤之間的頻繁交換，從而降低了系統(tǒng)開銷。

  2. 減少磁盤I/O操作次數(shù)：由于頁面換進、換出頻率的降低，磁盤I/O操作的次數(shù)也相應減少，這有助于提高系統(tǒng)的整體性能。

  3. 采用簡單置換策略：由于頁面緩沖算法能夠顯著降低頁面置換的開銷，因此可以采用較為簡單的置換策略，如先進先出（FIFO）算法等，這些策略實現(xiàn)起來相對簡單且不需要特殊硬件的支持。

  4. 優(yōu)化內存分配策略：頁面緩沖算法通常與可變分配和局部置換策略相結合，以更好地管理內存資源并降低頁面置換的頻率。

  降低頁面換進、換出頻率的機制

  1. 空閑頁面鏈表：

     • 頁面緩沖算法在內存中設置了一個空閑頁面鏈表，用于管理空閑的物理塊。

     • 當有進程發(fā)生缺頁時，系統(tǒng)可以從空閑頁面鏈表中分配一個物理塊給該進程。

     • 如果某個頁面需要被置換出內存，但尚未被修改，則可以將該頁面所在的物理塊重新掛回空閑頁面鏈表的末尾，以便后續(xù)再次使用。

  2. 修改頁面鏈表：

     • 頁面緩沖算法還設置了一個修改頁面鏈表，用于管理已被修改但尚未寫回磁盤的頁面。

     • 當一個頁面被修改后，它會被加入到修改頁面鏈表中。

     • 系統(tǒng)會定期或根據(jù)需要將修改頁面鏈表中的頁面寫回磁盤，從而降低已修改頁面被頻繁置換出內存并寫回磁盤的開銷。

  3. 頁面置換策略：

     • 頁面緩沖算法采用各種頁面置換策略來優(yōu)化頁面置換過程。

     • 這些策略包括但不限于先進先出（FIFO）、最近最少使用（LRU）、最不常用（LFU）等。

     • 通過選擇合適的頁面置換策略，系統(tǒng)可以更有效地管理內存資源并降低頁面置換的頻率。

  4. 預測和預加載：

     • 一些高級的頁面緩沖算法還使用預測算法來嘗試預測未來的頁面訪問模式。

     • 根據(jù)預測結果，系統(tǒng)可以預先加載可能會被訪問的頁面到內存中，從而降低缺頁率并減少頁面換進、換出的頻率。

  綜上所述，頁面緩沖算法通過優(yōu)化頁面置換策略、管理空閑和修改頁面鏈表以及采用預測和預加載技術等方式，顯著降低了頁面換進、換出的頻率并減少了磁盤I/O操作的次數(shù)。這些特點使得頁面緩沖算法在提高系統(tǒng)整體性能方面具有重要作用。

• 在請求分頁系統(tǒng)中，產生“抖動”的原因是什么?

  在請求分頁系統(tǒng)中，產生“抖動”（Thrashing）的原因主要是由于以下幾個方面的因素相互作用：

  一、CPU利用率和多道程序度的矛盾

  • 為了提高CPU的利用率，系統(tǒng)可能會嘗試提高多道程序度，即同時運行更多的進程。

  • 然而，單純提高多道程序度會導致每個進程分配到的物理塊數(shù)減少，進而增加缺頁率。

  • 高缺頁率會導致CPU頻繁地處于等待頁面調入的狀態(tài)，從而降低CPU的利用率。

  • 系統(tǒng)調度程序為了再次提高CPU利用率，可能會繼續(xù)增加多道程序度，形成惡性循環(huán)。

  二、物理塊數(shù)不足

  • 分配給進程的物理塊數(shù)太少，不能滿足進程正常運行的基本要求。

  • 這會導致進程在運行過程中頻繁地出現(xiàn)缺頁中斷，必須請求系統(tǒng)將所缺之頁調入內存。

  三、頁面淘汰算法不合理

  • 如果頁面淘汰算法不夠合理，可能會導致剛被換出的頁面很快又被訪問，需要重新調入。

  • 這種頻繁的頁面置換會占用大量的系統(tǒng)時間，導致系統(tǒng)性能急劇下降。

  四、系統(tǒng)資源競爭

  • 在多進程環(huán)境中，各個進程之間會競爭有限的內存資源。

  • 當多個進程同時發(fā)生缺頁中斷時，系統(tǒng)會陷入頻繁的頁面置換中，進一步加劇抖動現(xiàn)象。

  五、具體表現(xiàn)

  • 抖動現(xiàn)象發(fā)生時，系統(tǒng)的大部分時間都用于頁面的調進換出，而幾乎不能完成任何有效的工作。

  • 這會導致處理機的利用率急劇下降并趨于0，系統(tǒng)性能嚴重受損。

  綜上所述，抖動現(xiàn)象是請求分頁系統(tǒng)中一個嚴重的問題，它主要由CPU利用率和多道程序度的矛盾、物理塊數(shù)不足、頁面淘汰算法不合理以及系統(tǒng)資源競爭等因素共同作用而產生。為了避免抖動現(xiàn)象的發(fā)生，系統(tǒng)需要合理分配物理塊數(shù)、選擇合適的頁面淘汰算法以及優(yōu)化進程調度策略等。

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

  工作集（Working Set）是指在某段時間間隔內，進程實際所要訪問的頁面集合。這個概念在操作系統(tǒng)中的虛擬內存管理中具有重要意義。

  工作集的定義

  工作集描述了進程在特定時間段內頻繁訪問的頁面集合。這些頁面通常是進程運行所必需的，因此將它們保留在內存中可以提高系統(tǒng)的性能。工作集的大小可以根據(jù)時間的變化而動態(tài)調整，以適應進程的運行需求。

  工作集確定的原理

  工作集的確定基于局部性原理。局部性原理指出，程序在運行過程中往往會表現(xiàn)出一種趨勢，即它們傾向于在一段時間內重復訪問同一組頁面。這種趨勢可以分為時間局部性和空間局部性：

  1. 時間局部性：如果某個頁面在最近被訪問過，那么在未來的一段時間內，該頁面很有可能再次被訪問。

  2. 空間局部性：如果某個頁面被訪問，那么與該頁面相鄰的頁面（在內存中的位置相近）在不久的將來也很有可能被訪問。

  基于局部性原理，操作系統(tǒng)可以預測進程未來的頁面訪問模式，并據(jù)此確定工作集的大小。具體來說，系統(tǒng)可以通過跟蹤進程在過去一段時間內的頁面訪問情況，來確定哪些頁面是頻繁訪問的，并將這些頁面納入工作集。

  工作集的應用

  工作集的概念在操作系統(tǒng)中有多種應用，包括：

  1. 頁面置換算法：許多頁面置換算法（如Clock算法、LRU算法等）都會考慮工作集的大小。當內存中的頁面數(shù)量超過物理塊的限制時，這些算法會根據(jù)工作集的大小和頁面的訪問情況來決定哪些頁面應該被置換出內存。

  2. 內存分配：操作系統(tǒng)可以根據(jù)進程的工作集大小來為其分配內存。如果進程的工作集較小，那么可以為其分配較少的物理塊；如果工作集較大，則需要為其分配更多的物理塊。

  3. 性能優(yōu)化：通過監(jiān)控和分析進程的工作集，操作系統(tǒng)可以發(fā)現(xiàn)潛在的內存瓶頸，并采取相應的優(yōu)化措施來提高系統(tǒng)的性能。

  綜上所述，工作集是操作系統(tǒng)中用于描述進程在特定時間段內頻繁訪問的頁面集合的概念。它的確定基于局部性原理，并廣泛應用于頁面置換算法、內存分配和性能優(yōu)化等方面。

• 當前可以利用哪幾種方法來防止“抖動”?

  在請求分頁系統(tǒng)中，為了防止“抖動”（Thrashing）現(xiàn)象的發(fā)生，可以采取以下幾種方法：

  一、采取局部置換策略

  如果頁面采用可變分配方式，則可以限制某進程從其他進程獲取物理塊，把抖動限制在該進程內。當某進程發(fā)生缺頁時，它只能在分配給自己的內存空間內進行置換，不允許從其他進程那里獲得新的物理塊。這種方法可以防止一個進程占用過多物理塊而導致其他進程頻繁缺頁。

  二、把工作集算法融入處理機調度中

  工作集是指進程在某一時間間隔內實際要訪問的頁面集合。把工作集算法融入處理機調度中，可以在調度程序從外存調入新作業(yè)之前，先檢查每個進程在內存的駐留頁面是否足夠多。如果都已足夠多，此時便可以從外存調入新的作業(yè)，而不會因新作業(yè)的調入而導致缺頁率的增加。反之，如果有些進程的內存頁面不足，則應首先為那些缺頁率高的作業(yè)增加新的物理塊，此時將不再調入新的作業(yè)。

  三、利用L=S準則調節(jié)缺頁率

  L是缺頁之間的平均時間，S是平均缺頁服務時間，即置換一個頁面所需的時間。當L與S接近時，磁盤和處理機都可達到它們的最大利用率。理論和實踐都已證明，利用L=S準則對于調節(jié)缺頁率是十分有效的。通過調整系統(tǒng)參數(shù)，使得L和S盡可能接近，可以降低缺頁率，從而減少頁面置換的頻率，防止抖動現(xiàn)象的發(fā)生。

  四、選擇性暫停進程

  當多道程序度偏高時，已影響到處理機的利用率，為了防止發(fā)生抖動，系統(tǒng)必須減少多道程序的數(shù)目。此時可以基于某種原則選擇暫停某些當前活動的進程，將它們調出到磁盤上，以便把騰出的內存空間分配給缺頁率高的進程。這種方法通過動態(tài)調整進程的數(shù)量和內存分配，來保持系統(tǒng)的穩(wěn)定性和高效性。

  綜上所述，為了防止抖動現(xiàn)象的發(fā)生，可以從局部置換策略、工作集算法融入處理機調度、利用L=S準則調節(jié)缺頁率以及選擇性暫停進程等方面入手。這些方法各有優(yōu)缺點，在實際應用中需要根據(jù)系統(tǒng)的具體情況和需求進行選擇和調整。

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

  “L=S”準則是Dening于1980年提出的一種用于調節(jié)多道程序度的方法，其中L是缺頁之間的平均時間，S是平均缺頁服務時間，即用于置換一個頁面所需的時間。利用“L=S”準則調節(jié)缺頁率以避免“抖動”的發(fā)生，可以從以下幾個方面進行說明：

  一、L與S的關系及其對系統(tǒng)性能的影響

  1. L遠大于S：

     • 這種情況下，說明很少發(fā)生缺頁，磁盤的能力尚未得到充分的利用。

     • 系統(tǒng)可能處于空閑狀態(tài)或進程對內存的需求較低。

  2. L遠小于S：

     • 這種情況下，說明頻繁發(fā)生缺頁，缺頁的速度已超過磁盤的處理能力。

     • 系統(tǒng)可能處于過載狀態(tài)，導致處理機頻繁等待頁面調入，從而降低系統(tǒng)性能。

     • 這就是“抖動”現(xiàn)象的典型表現(xiàn)。

  3. L接近S：

     • 這種情況下，磁盤和處理機都可達到它們的最大利用率。

     • 系統(tǒng)性能處于最佳狀態(tài)，既不會因缺頁而頻繁等待，也不會因磁盤空閑而浪費資源。

  二、利用“L=S”準則調節(jié)缺頁率的策略

  1. 動態(tài)調整多道程序度：

     • 從系統(tǒng)啟動開始，每當要創(chuàng)建新進程或要為現(xiàn)有進程分配新空閑塊時，就計算L值和S值。

     • 若L>S，則表明系統(tǒng)有足夠的資源來處理更多的進程，可以進行新進程的創(chuàng)建或空閑塊的分配。

     • 當L值接近S值時，應謹慎添加新進程或分配空閑塊，以免導致缺頁率上升和“抖動”的發(fā)生。

  2. 優(yōu)化頁面置換算法：

     • 根據(jù)“L=S”準則，選擇合適的頁面置換算法以優(yōu)化內存使用。

     • 例如，當L接近S時，可以選擇LRU（最近最少使用）算法等能有效利用內存訪問模式的算法。

  3. 調整內存分配策略：

     • 根據(jù)進程的內存需求和系統(tǒng)資源情況，動態(tài)調整進程的內存分配。

     • 對于內存需求較大的進程，可以分配更多的物理塊以減少缺頁率；對于內存需求較小的進程，則可以適當減少其物理塊分配以節(jié)省資源。

  三、避免“抖動”發(fā)生的具體措施

  1. 監(jiān)控L與S的變化：

     • 實時監(jiān)控系統(tǒng)中的L與S值，以及它們之間的比值關系。

     • 當發(fā)現(xiàn)L值迅速下降并接近S值時，應立即采取措施進行干預。

  2. 減少進程數(shù)量：

     • 當多道程序度過高導致系統(tǒng)性能下降時，可以通過減少進程數(shù)量來降低缺頁率。

     • 例如，可以選擇性地暫停一些優(yōu)先級較低的進程或釋放一些不再需要的進程資源。

  3. 增加內存資源：

     • 如果系統(tǒng)經(jīng)常處于“抖動”狀態(tài)且無法通過調整多道程序度或優(yōu)化頁面置換算法來解決問題時，可以考慮增加系統(tǒng)的內存資源。

     • 這可以通過添加物理內存或擴展虛擬內存來實現(xiàn)。

  綜上所述，利用“L=S”準則調節(jié)缺頁率以避免“抖動”的發(fā)生需要綜合考慮多道程序度、頁面置換算法、內存分配策略以及系統(tǒng)資源情況等多個因素。通過動態(tài)調整這些參數(shù)和策略，可以保持系統(tǒng)的穩(wěn)定性和高效性。

• 為了實現(xiàn)請求分段式存儲管理，應在系統(tǒng)中增加配置哪些硬件機構?

  為了實現(xiàn)請求分段式存儲管理，應在系統(tǒng)中增加配置以下硬件機構：

  一、請求段表機制

  請求段表是請求分段式存儲管理中的主要數(shù)據(jù)結構。它除了包含請求分頁機制中的訪問字段A、修改位M、存在位P和外存始址等字段外，還增加了存取方式字段和增補位。這些字段供程序在調進、調出時參考。具體來說：

  • 存取方式字段：用于標識本分段的存取屬性，如只執(zhí)行、只讀或允許讀/寫。

  • 訪問字段A：記錄該段被訪問的頻繁程度，用于優(yōu)化頁面置換算法。

  • 修改位M：表示該段在調入內存后是否被修改過，供置換頁面時參考。

  • 存在狀態(tài)位P：指示該段是否已調入內存，供程序訪問時參考。

  • 增補位：這是請求分段式管理中所特有的字段，用于表示本段在運行過程中是否做過動態(tài)增長。

  • 外存始址：指示本段在外存中的起始地址，即起始盤塊號。

  二、缺段中斷機構

  在請求分段系統(tǒng)中，采用的是請求調段策略。每當發(fā)現(xiàn)運行進程所要訪問的段尚未調入內存時，便由缺段中斷機構產生一缺段中斷信號。進入操作系統(tǒng)后，由缺段中斷處理程序將所需的段調入內存。與缺頁中斷機構類似，缺段中斷機構同樣需要在一條指令的執(zhí)行期間產生和處理中斷，并且在一條指令執(zhí)行期間可能產生多次缺段中斷。但由于分段是信息的邏輯單位，因此不可能出現(xiàn)一條指令被分割在兩個分段中或一組信息被分割在兩個分段中的情況。

  三、地址變換機構

  請求分段系統(tǒng)中的地址變換機構是在分段系統(tǒng)地址變換機構的基礎上形成的。因為被訪問的段并非全在內存，所以在地址變換時，若發(fā)現(xiàn)所要訪問的段不在內存，必須先將所缺的段調入內存，并修改段表，然后才能再利用段表進行地址變換。為此，在地址變換機構中又增加了某些功能，如缺段中斷的請求及處理等。

  綜上所述，為了實現(xiàn)請求分段式存儲管理，系統(tǒng)中需要增加配置請求段表機制、缺段中斷機構和地址變換機構等硬件機構。這些機構共同協(xié)作，使得系統(tǒng)能夠高效地管理內存資源，滿足進程的內存需求。

• 在請求段表機制中，應設置哪些段表項?

  在請求段表機制中，應設置的段表項主要包括以下幾項：

  1. 段名：用于唯一標識一個段，方便系統(tǒng)進行管理和訪問。

  2. 段長：表示段的長度，即段在內存中所占用的空間大小。這個信息對于內存分配和地址變換都是必要的。

  3. 段基址：也稱為段的起始地址，表示段在內存中的起始位置。結合段長，可以確定段在內存中的范圍。

  4. 存取方式：標識本段的存取屬性，如只執(zhí)行、只讀或允許讀/寫等。這有助于系統(tǒng)對段的訪問進行權限控制。

  5. 訪問字段A：記錄該段被訪問的頻繁程度。這個信息可以用于優(yōu)化頁面置換算法，提高內存利用率。

  6. 修改位M：表示該段在進入內存后是否已被修改過。這對于頁面的置換和內存的一致性維護非常重要。

  7. 存在位P：指示該段是否已調入內存。當進程訪問一個段時，系統(tǒng)可以通過檢查存在位來判斷該段是否在內存中，從而決定是否需要進行缺段中斷處理。

  8. 增補位：表示本段在運行過程中是否做過動態(tài)增長。這對于動態(tài)內存管理非常重要，因為系統(tǒng)需要知道一個段是否可能會增長，以便為其預留足夠的空間。

  9. 外存始址：表示本段在外存的起始地址，即起始盤塊號。這對于段的換入換出操作是必要的，因為系統(tǒng)需要知道如何從外存中讀取或寫入段的數(shù)據(jù)。

  這些段表項共同構成了請求段表機制的核心數(shù)據(jù)結構，為系統(tǒng)的內存管理和進程訪問提供了必要的支持和保障。

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

  在請求分段系統(tǒng)中，缺頁中斷處理是一個關鍵過程，它允許系統(tǒng)在需要時動態(tài)地將缺失的段或頁面調入內存。以下是缺頁中斷處理過程的詳細說明：

  一、缺頁中斷的產生

  1. 當進程執(zhí)行到某條指令，需要訪問某個段或頁面時，系統(tǒng)會首先檢查該段或頁面是否已在內存中。

  2. 如果發(fā)現(xiàn)所需段或頁面不在內存中（即存在位P為0），則會產生一個缺頁中斷。

  二、缺頁中斷的處理

  缺頁中斷的處理過程與一般的中斷處理類似，但也有一些特殊之處。以下是處理過程的詳細步驟：

  1. 保護CPU現(xiàn)場：

     • 當缺頁中斷發(fā)生時，系統(tǒng)會暫停當前進程的執(zhí)行，并保存當前CPU的上下文環(huán)境（如寄存器值、程序計數(shù)器等），以便在中斷處理完畢后能夠恢復執(zhí)行。

  2. 分析中斷原因：

     • 系統(tǒng)會檢查中斷原因，確認是由于缺頁而產生的中斷。

  3. 轉入缺頁中斷處理程序：

     • 根據(jù)中斷原因，系統(tǒng)會轉入缺頁中斷處理程序。該程序負責查找缺失的段或頁面，并將其調入內存。

  4. 查找并調入缺失段或頁面：

     • 缺頁中斷處理程序會首先查找請求段表，確定缺失段或頁面的外存地址。

     • 然后，系統(tǒng)會通過I/O操作，從外存中讀取缺失段或頁面的數(shù)據(jù)，并將其調入內存。

     • 如果內存已滿，系統(tǒng)還需要選擇一個不再需要的段或頁面進行置換。

  5. 修改段表或頁表：

     • 在缺失段或頁面被調入內存后，系統(tǒng)需要更新段表或頁表，將存在位P設置為1，并更新其他相關字段（如訪問字段A、修改位M等）。

  6. 恢復CPU現(xiàn)場并繼續(xù)執(zhí)行：

     • 在完成上述步驟后，系統(tǒng)會恢復之前保存的CPU上下文環(huán)境。

     • 然后，系統(tǒng)會重新執(zhí)行導致缺頁中斷的那條指令，此時該指令所需的段或頁面已經(jīng)調入內存，因此可以成功執(zhí)行。

  三、缺頁中斷處理的特殊性

  與一般的中斷處理相比，缺頁中斷處理具有以下特殊性：

  1. 在指令執(zhí)行期間產生和處理：缺頁中斷是在指令執(zhí)行期間產生的，并且需要在指令執(zhí)行期間進行處理。這要求系統(tǒng)能夠快速響應缺頁中斷，并盡快將缺失的段或頁面調入內存。

  2. 一條指令可能產生多次缺頁中斷：由于分段是信息的邏輯單位，因此一條指令可能會訪問多個段或頁面。如果其中某些段或頁面不在內存中，就會產生多次缺頁中斷。這要求系統(tǒng)能夠高效地處理多次缺頁中斷，以提高程序的執(zhí)行效率。

  3. 缺頁中斷返回時執(zhí)行原指令：與一般的中斷返回時執(zhí)行下一條指令不同，缺頁中斷返回時需要重新執(zhí)行導致缺頁中斷的那條指令。這是因為該指令在缺頁中斷發(fā)生時尚未成功執(zhí)行，因此需要重新執(zhí)行以確保程序的正確性。

  綜上所述，請求分段系統(tǒng)中的缺頁中斷處理過程是一個復雜而關鍵的過程，它允許系統(tǒng)在需要時動態(tài)地將缺失的段或頁面調入內存，從而確保程序的正確執(zhí)行和系統(tǒng)的穩(wěn)定性。

• 請對共享段表中的各項作簡要說明。

  共享段表是實現(xiàn)分段共享的重要數(shù)據(jù)結構，在系統(tǒng)中配置一張共享段表，所有共享段都在共享段表中占有一表項。共享段表中的各項內容對于管理共享段至關重要，以下是對各項的簡要說明：

  1. 段號：

     • 用于唯一標識一個共享段。

     • 不同的進程可以各用不同的段號去共享同一個段。

  2. 段長：

     • 表示共享段的長度，即該段在內存中所占用的空間大小。

     • 用于進行越界檢查，確保訪問的地址不越出段界。

  3. 內存起始地址：

     • 指示共享段在內存中的起始位置。

     • 結合段長，可以確定共享段在內存中的范圍。

  4. 存在位：

     • 表示該共享段是否已調入內存。

     • 當存在位為1時，表示該段已在內存中；當存在位為0時，表示該段尚未調入內存。

  5. 共享進程計數(shù)（count）：

     • 記錄當前有多少個進程正在共享該段。

     • 當一個進程開始共享該段時，count加1；當一個進程不再需要該段而釋放它時，count減1。

     • 僅當count為0時，系統(tǒng)才回收該段的物理內存，并取消在共享段表中該段所對應的表項。

  6. 存取控制字段：

     • 用于規(guī)定對該共享段的訪問方式。

     • 常見的訪問方式包括只讀、只執(zhí)行、讀/寫等。

     • 對于不同的進程，可以賦予不同的存取權限，以確保信息的安全性和滿足運行需要。

  7. 其他信息：

     • 根據(jù)需要，共享段表還可以包含其他信息，如外存起始地址（用于在需要時從外存調入該段）、段的屬性（如是否可動態(tài)增長）、段的類型（如代碼段、數(shù)據(jù)段等）等。

  共享段表通過記錄上述信息，實現(xiàn)了對共享段的有效管理和控制。它使得系統(tǒng)能夠跟蹤哪些段正在被共享、哪些進程正在共享這些段以及這些段的存取權限等關鍵信息，從而確保了系統(tǒng)的穩(wěn)定性和安全性。

• 如何實現(xiàn)共享分段的分配和回收?

  共享分段的分配和回收是實現(xiàn)分段共享的關鍵過程。以下是這兩個過程的詳細說明：

  一、共享分段的分配

  1. 首次分配：

     • 當?shù)谝粋€進程請求共享某個分段時，系統(tǒng)會為該分段分配一個物理內存區(qū)域。

     • 將該物理內存區(qū)域的起始地址填入請求進程的段表中。

     • 在共享段表中為該分段增加一項，記錄該分段的基本信息（如段號、段長、內存起始地址等）以及共享該分段的進程信息（如進程名、進程號、存取控制權限等）。

     • 設置共享進程計數(shù)（count）為1，表示當前有一個進程正在共享該分段。

  2. 后續(xù)分配：

     • 當其他進程也需要共享該分段時，由于該分段已被調入內存，系統(tǒng)無需再為其分配物理內存區(qū)域。

     • 只需在調用進程的段表中增加一項，記錄該分段的物理地址。

     • 在共享段表中，更新該分段的信息，增加調用進程的進程名和存取控制權限等。

     • 將共享進程計數(shù)（count）加1，表示又有一個進程開始共享該分段。

  二、共享分段的回收

  1. 釋放分段：

     • 當某個進程不再需要共享某個分段時，會執(zhí)行釋放操作。

     • 系統(tǒng)會撤銷該進程段表中與該分段對應的表項。

     • 在共享段表中，將該分段的共享進程計數(shù)（count）減1。

  2. 回收內存：

     • 如果共享進程計數(shù)（count）減為0，表示沒有任何進程在共享該分段。

     • 此時，系統(tǒng)會回收該分段所占用的物理內存區(qū)域。

     • 同時，在共享段表中刪除該分段的表項，表示該分段已被完全回收。

  3. 注意事項：

     • 在共享分段被多個進程共享時，應盡量避免淘汰該分段，以保證系統(tǒng)的穩(wěn)定性和性能。

     • 對于共享分段，應嚴格控制其存取權限，以確保信息的安全性和完整性。

  通過上述過程，系統(tǒng)實現(xiàn)了對共享分段的有效分配和回收。這有助于提高內存利用率、保證系統(tǒng)的穩(wěn)定性和安全性，并滿足多個進程對同一分段進行共享的需求。