1.虛擬存儲器的基本概念

1）常規存儲器管理不足的原因：

常規存儲器管理方式的特徵:

一次性：作業在運行前一次性地全部裝入內存

駐留性：作業裝入內存後，便一直駐留在內存中，直至作業運行結束

2）局部性原理

時間局部性：被引用過一次的存儲器位置很可能在不遠的將來再被多次引用

空間局部性：如果一個存儲器位置被引用了一次，那麼程序很可能在不遠的將來引用附近的一個存儲器功能。

基於局部性原理

程序運行前，不需全部裝入內存（打破一次性）

僅裝入當前要運行的部分頁面或段即可運行

缺頁/段的情況：要訪問的頁(段) 尚未調入內存。程序應利用OS所提供的請求調頁(段)功能， 將它們調入內存，使程序繼續執行。

調入需要的頁/段時，如果內存已滿，無法再裝入新頁(段)，通過置換功能將內存中暫時不用的頁(段)調至外存，騰出足夠的內存空間。（不總駐留）

3）虛擬存儲器的定義：

所謂“虛擬存儲器”，是指具有請求調入功能和置換功能，能從邏輯上對內存容量加以擴充的一種存儲器系統。

虛擬存儲管理下

內存邏輯容量由內存容量和外存容量之和所決定

運行速度接近於內存速度

每位的成本卻接近於外存。

4）虛擬存儲器的實現

若採用連續分配方式，需申請足夠空間，再分多次裝入，造成內存資源浪費，並不能從邏輯上擴大內存容量。

虛擬的實現建立在離散分配存儲管理基礎上

方式：請求分頁/請求分段系統

細節：分頁/段機構、中斷機構、地址變換機構、軟件支持

5）虛擬存儲器的特徵

離散分配方式是基礎

多次性：一個作業被分成多次調入內存運行

對換性：允許在作業的運行過程中進行換進、換出。（進程整體對換不算虛擬）

最終體現虛擬性：能夠從邏輯上擴充內存容量，使用戶所看到的內存容量遠大於實際內存容量。

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

基本分頁 + “請求調頁”和“頁面置換”功能。

換入和換出基本單位都是長度固定的頁面

1）硬件支持

一臺具有一定容量的內/外存的計算機+ 頁表機制+ 缺頁中斷機構+ 地址轉換機構

（1）頁表基本功能不變：邏輯地址映射為物理地址

① 狀態位P ：指示該頁是否已調入內存。

② 訪問字段A ：用於記錄本頁在一段時間內被訪問的次數，或記錄本頁最近已有多長時間未被訪問。(置換時考量的參數)

③修改位M ：該頁在調入內存後是否被修改過。(關係到置換時調出的具體操作)

④ 外存地址：用於指出該頁在外存上的地址。

（2）缺頁中斷機構

每當要訪問的頁面不在內存時，便產生一缺頁中斷通知OS，OS則將所缺之頁調入內存。作為中斷，需經歷幾個步驟：

“保護CPU環境”

“分析中斷原因”

“轉入缺頁中斷處理程序”

“恢復CPU環境”等。

作為一種特殊中斷，與一般中斷有明顯區別：

①在指令執行期間產生和處理中斷信號。

② 一條指令在執行期間，可能產生多次缺頁中斷。

（3）地址變換機構

2）內存分配

（1）最小物理塊數的確定

少於此數量進程將不能運行

與計算機的硬件結構有關，取決於指令的格式、功能和尋址方式

（2）物理塊的分配策略

固定分配、局部置換

可變分配、全局置換

可變分配、局部置換

（3）物理塊的分配算法

①平均分配算法

將所有可供分配的物理塊平均分配給各進程。

缺點：未考慮各進程本身的大小，利用率不均。

②按比例分配算法

根據進程的大小按比例分配物理塊。

設系統中共有n個進程

則，每個進程能分到的物理塊數：

Si：進程i頁面數為；S：n個進程頁面數總和；m：可用物理塊總數

③考慮優先權的分配算法

所有可用物理塊分兩部分：

一部分按比例分配給各進程；

另一部分根據各進程優先權，適當地為其增加份額，分配給各進程。

3）調頁策略

（1）何時調入頁面

預調頁策略

請求調頁策略

（2）從何處調入頁面

在請求分頁系統中的外存分為：

對換區：連續存放數據，讀寫速度較快

文件區：離散分配方式，I/O速度相對慢

發生缺頁時，系統應從何處將缺頁調入內存，分成三種情況：

①系統擁有足夠的對換區空間：

進程運行前所有頁面由文件區拷貝到對換區；

運行需要的頁面全部從對換區調入內存，提高調頁速度。

②系統缺少足夠的對換區空間：

不會被修改的部分，在文件區操作（即：直接從文件區調入，換出時不用寫入文件，再調入時仍從文件區調入）

可能被修改的部分，在對換區操作。

③UNIX方式：（隨運行數據逐漸從文件區轉到對換區）

未運行的頁面從文件區調入；

曾經運行，但又被換出的頁面放在對換區，下次調入應從對換區調入。

進程請求的共享頁面可能已被其他進程調入，無需再從對換區調入。

（3）頁面調入過程

程序運行前需要裝入內存：上述的②步策略處理何處調入；

開始運行：先預調入一部分頁面；

運行中：需要的頁面不在內存時，

向CPU發出一缺頁中斷，“中斷處理程序”開始工作：

①首先保留CPU環境

②分析中斷原因後，轉入缺頁中斷處理程序。

③處理：判斷是否置換、頁表信息更新

④恢復現場，重新操作頁面。

3.頁面置換算法

1）最佳Optimal置換算法

優點：保證獲得最低的缺頁率

不足：無法實現，因為無法預知一進程將來的運行情況

作用：作為參照標準，評價其他算法。

2）先進先出FIFO置換算法

先進入的先淘汰，即選擇內存中駐留時間最久的頁面予以淘汰。

優點：實現簡單，把一進程已調入內存的頁面按先後次序組織成一個隊列，並設置一個指針(替換指針)，使它總是指向隊首最老的頁面。

不足：與進程實際運行規律不相適應（較早調入的頁往往是經常被訪問的頁，頻繁被對換造成運行性能降低）

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

不足：有時頁面過去和未來的走向之間並無必然的聯繫。

相應的需較多的硬件支持：記錄每個頁面自上次被訪問以來所經歷的時間t，淘汰時選擇頁面t值最大的；以及需要快速地知道哪一頁是最近最久未使用的頁面，用寄存器或棧。

4）CLOCK置換算法

每個頁設一個使用標誌位(use bit)，若該頁被訪問則將其置為1。

設置一個指針，從當前指針位置開始按地址先後檢查各頁，尋找use bit=0的頁面作為被置換頁。

若指針經過的頁use bit=1，修改use bit=0（暫不凋出，給被用過的頁面駐留的機會 ），指針繼續向下。到所有頁面末尾後再返回隊首檢查。

說明：

增加了一個使用位

當一頁首次加載入內存時，該位為1，當該頁被訪問時，使用位也置1

當需要進行頁替換時

第一個使用位為0的幀被替換，指針指向緩衝區的下一幀

循環掃描，遇到使用位為1的，變成0

改進CLOCK：

改進：主要考慮對沒訪問過的頁面再細分是否修改過的不同情況，減少因修改造成的頻繁I/O操作。

每頁除記錄是否用過A，還記錄是否修改的標誌M。置換時根據兩個標誌的值有4種不同情況的處理。

5）其他

（1）最少使用 (LFU, Least Frequently Used)

關鍵在次數記錄上

每頁設置訪問計數器，每當頁面被訪問時，該頁面的訪問計數器加1；缺頁中斷時，淘汰計數值最小的頁面，並將所有計數清零；

計數的實現類似LRU，用移位寄存器，但比較時不是簡單比較寄存器的值，而是比較寄存器每位的和∑Ri。

（2）頁面緩衝算法PBA(page buffering algorithm)

對FIFO算法的發展，彌補了FIFO可能造成的I/O開銷，又不需要LRU等算法的硬件支持。

仍用FIFO算法選擇被置換頁

但並不將其馬上換入外存。

系統將頁面放入兩個鏈表之一：如果頁面未被修改，就將其歸入到空閒頁面鏈表的末尾；否則將其歸入到已修改頁面鏈表。

需要調入新的物理頁面時，將新頁面內容讀入到空閒頁面鏈表的第一項所指的頁面，然後將第一項刪除（從空閒鏈表摘下）。

空閒頁面和已修改頁面，仍停留在內存中一段時間，如果這些頁面被再次訪問，只需較小開銷，而被訪問的頁面可以返還作為進程的內存頁。

當已修改頁面達到一定數目後，再將它們一起調出到外存，然後將它們歸入空閒頁面鏈表，這樣能大大減少I/O操作的次數。

6）虛擬存儲管理下訪問內存的有效時間

7）影響缺頁率的主要因素

(1)分配給作業的主存塊數:

多則缺頁率低，反之則高。

(2)頁面大小：

大則缺頁率低；反之則高。

(3)頁面調度算法：

對缺頁中斷率影響很大，但不可能找到一種最佳算法。

(4)程序編制方法：

以數組運算為例，如果每一行元素存放在一頁中，則按行處理各元素缺頁中斷率低；反之，按列處理各元素，則缺頁中斷率高。

8）抖動

（1）系統抖動：

為了提高處理機利用率，可增加多道程序併發度；

但進程數目增加過多，每個進程分配得到的物理塊太少，在某個臨界點上，會出現剛被淘汰的頁很快又需重新調入；而調入不久又被淘汰出去；出現頻繁缺頁

大部分處理器時間都用在來回的頁面調度上，這種局面稱為系統抖動或顛簸（thrashing)

（2）抖動的後果：

缺頁率急劇增加

內存有效存取時間加長，

系統吞吐量驟減；系統已基本不能完成什麼任務，而是忙於頁面對換操作，cpu雖然忙，但效率急劇下降。

（3）根本原因：

頁面淘汰算法不合理；分配給進程的物理頁面數(駐留集)太少。

（4）常用防抖動方法：

局部置換策略；

頁面調入內存前檢查各進程工作集，為缺頁率高的增加有限物理塊；

L缺頁間的平均時間=S置換一個頁面所需時間，可使磁盤和cpu達到最大利用率；

抖動發生時選擇暫停一些進程，調節多道程序度。

（5）工作集模型的原理：

操作系統跟蹤每個進程的工作集，併為進程分配大於其工作集的物理塊。

如果還有空閒物理塊，則可以再調一個進程到內存以增加多道程序數。

如果所有工作集之和增加以至於超過了可用物理塊的總數，那麼操作系統會暫停一個進程，將其頁面調出並且將其物理塊分配給其他進程，防止出現抖動現象。

（6）駐留集

駐留(常駐)集是指在當前時刻，進程實際駐留在內存當中的頁面集合。

工作集是進程在運行過程中固有的性質，而駐留集取決於系統分配給進程的物理頁面數目，以及所採用的頁面置換算法；

如果一個進程的整個工作集都在內存當中，即駐留集 <=工作集，那麼進程將很順利地運行，而不會造成太多的缺頁中斷（直到工作集發生劇烈變動，從而過渡到另一個狀態）；

當駐留集達到某個數目之後，再給它分配更多的物理頁面，缺頁率也不會明顯下降。

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

1）請求分段中的硬件支持

(1)段表機制

(2)缺段中斷機構

(3)地址變換機構

2)分段的共享和保護

(1)實現共享：共享段表

(2)共享段如何分享與回收

①共享段的分配

②共享段的回收

③分段保護

a.越界檢查

b.存取控制檢查

c.環保護機構

閱讀更多 有一天我會成功 的文章

關鍵字: 軟件 內存 局部性