虛擬存儲實現思路

在實際運行過程，把有關作業的全部信息都裝入主存儲器后，作業執行時實際上不是同時使用全部信息的，有些部分運行一遍便再也不用,甚至有些部分在作業執行的整個過程中都不會被使用到(如錯誤處理部分)。進程在運行時不用的，或暫時不用的，或某種條件下才用的程序和數據,全部駐留于內存中是對寶貴的主存資源的一種浪費，大大降低了主存利用率。
于是，提出了這樣的問題：作業提交時，先全部進入輔助存儲器,作業投入運行時,能否不把作業的全部信息同時裝入主存儲器，而是將其中當前使用部分先裝入主存儲器，其余暫時不用的部分先存放在作為主存擴充的輔助存儲器中，待用到這些信息時，再由系統自動把它們裝入到主存儲器中,這就是虛擬存儲器的基本思路。

虛擬存儲器定義

具有部分裝入和部分對換功能,能從邏輯上對內存容量進行大幅度擴充,使用方便的一種存儲器系統。
虛擬存儲器是基于程序局部性原理上的一種假想的而不是物理存在的存儲器，允許用戶程序以邏輯地址來尋址，而不必考慮物理上可獲得的內存大小，這種將物理空間和邏輯空間分開編址但又統一管理和使用的技術為用戶編程提供了極大方便。此時，用戶作業空間稱虛擬地址空間，其中的地址稱虛地址

分頁式虛擬存儲系統

基本原理

分頁式虛擬存儲系統是將作業信息的副本存放在磁盤這一類輔助存儲器中，當作業被調度投入運行時，并不把作業的程序和數據全部裝入主存，而僅僅裝入立即使用的那些頁面，至少要將作業的第一頁信息裝入主存，在執行過程中訪問到不在主存的頁面時，再把它們動態地裝入。用得較多的分頁式虛擬存儲管理是請頁式(demand Paging),當需要執行某條指令或使用某個數據，而發現它們并不在主存時，產生一個缺頁中斷，系統從輔存中把該指令或數據所在的頁面調入內存。
請頁式虛擬存儲在執行過程中，必然會發生某些頁面不在內存中的情況，針對這種情況，處理方法是擴充頁表的內容,增加駐留標志位和頁面輔存的地址等信息,擴充后的頁表如下所示：

• 駐留標志位(又稱中斷位)用來指出對應頁是否已經裝入主存，如果某頁所對應欄的駐留標志位為１，則表示該頁已經在主存；若駐留標志位為 0，此時產生一個缺頁中斷信號，可以根據輔存地址知道該頁在輔助存儲器中的位址,將這個頁面調入主存。
  在作業執行中訪問某頁時，硬件的地址轉換機構查頁表：
  
• 若該頁對應駐留標志為1，則按分頁實存管理給出的辦法進行地址轉換，得到絕對地址。
• 若該頁駐留標志為0，則由硬件發出一個缺頁中斷，表示該頁不在主存。操作系統必須處理這個缺頁中斷針對缺頁中斷的具體處理方法是先查看主存是否有空閑塊，若有則按該頁在輔助存儲器中的地址將這個頁面找出且裝入主存，在頁表中填上它占用的塊號且修改標志位。若主存已沒有空閑塊，則必須先淘汰已在主存中的某一頁，再將所需的頁面裝入，對頁表和主存分配表作相應的修改
• 為了提高系統效率，可在頁表中增加標志位，其它標志包括修改位（Modified ）、引用 位（ Renferenced ）、禁止緩存位和訪問位，用來跟蹤頁的使用情況。當一個頁被修改后，硬件自動設置修改位，一旦修改位被設置，當該頁被調出主存時必須重新被寫回輔存;若一頁在執行過程中沒有被修改過，那么不必重新寫回到存儲器中。引用位則在該頁被引用時設置，無論是讀或寫，它的值被用來幫助操作系統進行頁面淘汰。禁止緩存位可以禁止該頁被緩存，這一特性對于那些正在與外設進行數據交換的頁面時非常重要。訪問位則限定了該頁允許什么樣的訪問權限如可讀、可寫和可執

頁面裝入策略

　請頁式調度

請頁式調度是僅當需要訪問程序和數據時，才把所在頁面裝入主存。那么當某個進程第一次執行時，開始會有許多缺頁中斷，隨著越來越多的頁面裝入主存，根據局部性原理,大多數未來訪問的程序和數據都在最近被裝入主存的頁面中，一段時間之后,缺頁中斷就會下降到很低的水平,程序進入相對平穩階段。這種策略的主要缺點是處理缺頁中斷和調頁的系統開銷較大，由于每次僅調一頁 ,增加了磁盤 I/O 次數。

預調式調度

預調式調度由操作系統預測進程將要使用的那些頁面,在使用入之前預先調入主存,每次調入若干個頁面,而不是像請頁式那樣僅調一個頁面。由于進程的頁面大多數連續存放在輔存儲中器，一次調入多個頁面能減少磁盤I/O啟動次數,節省了尋道和搜索時間。但是如果調入的一批頁面中多數未被使用,則效率就很低了，可見預調頁要建立在預測的基礎上，目前所用預調頁的成功率在 50%左右。

頁面清除策略

清除策略是與裝入策略相對的，它要考慮何時把一個修改過的頁面寫回輔存儲器。

請頁式清除

請頁式清除是僅當一頁選中被替換,且之前它又被修改過,才把這個頁面寫回輔助存儲器

預清除

預清除方法對更改過的頁面，在需要之前就把它們都放回輔助存儲器,因此可以成批進行。

頁面分配策略

分頁式虛擬存儲系統排除了主存儲器實際容量的約束，能使更多的作業同時多道運行，從而提高了系統的效率，但缺頁中斷的處理要付出相當的代價，由于頁面的調入、調出要增加I/O的負擔而且影響系統效率，因此應盡可能的減少缺頁中斷的次數
在請頁式系統中,可采用兩種策略分配頁框給進程：固定分配和可變分配

固定分配

如果進程生命周期中,保持頁框數固定不變,稱頁面分配為固定分配;通常在進程創建時,根據進程類型和程序員的要求決定頁框數,只要有一個缺頁中斷產生,進程就會有一頁被替換。

可變分配

如果進程生命周期中,分得的頁框數可變,稱頁面分配為可變分配;當進程執行的某一階段缺頁率較高,說明進程程序目前的局部性較差，系統可多分些頁框以降低缺頁率，反之說明進程程序目前的局部性較好,可以減少分給進程的頁框數。

對比

固定分配策略缺少靈活性，而可變分配的性能會更好些,被許多操作系統所采用。采用可變分配策略的困難在于操作系統要經常監視活動進程的行為和進程缺頁中斷率的情況,這會增加操作系統的開銷。

頁面替換策略

實現虛擬存儲器能給用戶提供一個容量很大的存儲器，但當主存空間已裝滿而又要裝入新頁時，必須按一定的算法把已在主存的一些頁調出去，這個工作稱頁面替換

如果頁面替換算法的作用范圍是整個系統，稱為全局頁面替換算法,它可以在可運行進程之間動態地分配頁框。如果頁面替換算法的作用范圍局限于本進程，稱為局部頁面替換算法,它實際上需要為每個進程分配固定的頁框。

淘汰算法

用來確定應該淘汰哪頁的算法,稱淘汰算法。

算法的選擇是很重要的，選用了一個不適合的算法，就會出現這樣的現象：
剛被淘汰的頁面又立即要用，因而又要把它調入，而調入不久再被淘汰，淘汰不久再被調入。如此反復 ，使得整個系統的頁面調度非常頻繁以至于大部時間都化在來回調度頁面上。這種現象叫做 “抖動”(Thrashing)，又稱“顛簸”，一個好的調度算法應減少和避免抖動現象。

缺頁中斷率

假定作業 p 共計n頁，而系統分配給它的主存塊只有 m 塊（m,n均為正整數，且１≤m≤n），即最多主存中只能容納該作業的m頁。如果作業p在運行中成功的訪問次數為s（即所訪問的頁在主存中）， 不成功的訪問次數為F（即缺頁中斷次數），則總的訪問次數Ａ為：
A = S + F
又定義：
f = F / A
則稱 f 為缺頁中斷率。影響缺頁中斷率 f 的因素有：
1. 主存頁框數。作業分得的主存塊數多，則缺頁中斷率就低，反之，缺頁中斷率就高。
2. 頁面大小。如果劃分的頁面大，則缺頁中斷率就低，否則缺頁中斷率就高
3. 頁面替換算法。
4. 程序特性。程序編制的方法不同，對缺頁中斷的次數有很大影響,程序的局部性要好

頁面替換算法

一個理想的替換算法是：當要調入一頁而必須淘汰一個舊頁時，所淘汰的頁應該是以后不再訪問的頁或距現在最長時間后再訪問的頁。這樣的調度算法使缺頁中斷率為最低。然而這樣的算法是無法實現的因為在程序運行中無法對以后要使用的頁面作出精確的斷言。不過，這個理論上的算法可以用來作為衡量各種具體算法的標準。

下面介紹幾種實用的頁面調度算法:

隨機頁面替換算法

要淘汰的頁面是由一個隨機數產生程序所產生的隨機數來確定,選擇一個不常使用的頁面會使系統性能較好,但這種調度算法做不到這一點,雖很簡單但效率卻低，一般不采用。

先進先出頁面替換算法（ FIFO ）

先進先出調度算法是一種低開銷的頁面替換算法，基于程序總是按線性順序來訪問物理空間這一假設。這種算法總是淘汰最先調入主存的那一頁，或者說在主存中駐留時間最長的那一頁（常駐的除外）
這種算法較易實現，但效率不高，因為在主存中駐留時間最長的頁面未必是最長時間以后才使用的
頁面。也就是說，如果某一個頁面要不斷地和經常地被使用，采用FIFO算法,在一定的時間以后就會變成駐留時間最長的頁，這時若把它淘汰了，可能立即又要用，必須重新調入

最近最少用頁面替換算法（ LRU，least Recently used ）

最近最少用調度算法是一種通用的有效算法，被操作系統、數據庫管理系統和專用文件系統廣泛采用。該算法淘汰的頁面是在最近一段時間里較久未被訪問的那一頁。它是根據程序執行時所具有的局部性來考慮的，即那些剛被使用過的頁面，可能馬上還要被使用，而那些在較長時間里未被使用的頁面，一般說可能不會馬上使用到。

第二次機會頁面替換算法

FIFO 算法可能會把經常使用的頁面淘汰掉，可以對 FIFO 算法進行改進,把FIFO算法與頁表中的”引用位”結合起來使用,算法可實現如下：
首先檢查FIFO中的隊首頁面(這是最早進入主存的頁面),如果它的”引用位”是0,那么這個頁面既老又沒有用，選擇該頁面淘汰;如果它的”引用位”是 1,說明雖然它進入主存較早，但最近仍在使用。于是把它的”引用位”清成0,并把這個頁面移到隊尾，把它看作是一個新調入的頁。這一算法稱為第二次機會(second chance)算法,其含義是最先進入主存的頁面，如果最近還在被使用的話,仍然有機會作為像一個新調入頁面一樣留在主存中。

時鐘頁面替換算法 (Clock Policy)

如果利用標準隊列機制構造FIFO隊列，第二次機會頁面調度算法將可能產生頻繁地出隊入隊，實現代價較大。因此，往往采用循環隊列機制構造頁面隊列，這樣就形成了一個類似于鐘表面的環形表，隊列指針則相當于鐘表面上的表針，指向要淘汰的頁面，這就是時鐘頁面替換算法的得名
算法的實現要點：
1. 一個頁面首次裝入主存時，其”引用位”置 0。
2. 在主存中的任何一個頁面被訪問時, 其”引用位”置 1。
3. 淘汰頁面時,存儲管理從指針當前指向的頁面開始掃描循環隊列，把所遷到的”引用位”是 1 的頁面的”引用位”清成 0,并跳過這個頁面; 把所遷到的”引用位”是0的頁面淘汰掉,指針推進一步。

最不常用頁面替換算法（LFU ：Least Erequently used ）

如果對應每一頁設置一個計數器，每當訪問一頁時，就使它對應的計數器加１。過一定時間 t 后 ，將所有計數器全部清０。當發生缺頁中斷時，可選擇計數值最小的對應頁面淘汰，顯然它是在最近一段時間里最不常用的頁面。這種算法實現不難，但代價太高而且選擇多大的 t 最適宜也是個難題。

下面是針對幾個頁面替換算法的效率對比圖：

寫時復制(copy-on-write)

寫時復制(copy-on-write)是存儲管理用來節省物理內存(頁框)的一種頁面級優化技術,已被unix 和 Windows等許多操作系統所采用，它能減少主存頁面內容的復制操作,減少相同內容頁面在主存的副本數目。

當兩個進程(如父子進程)共享一個頁面時,并不是立即為每個進程各建一個頁面副本,而是把該頁面定義為只讀方式,讓諸進程共享。當其中某個進程要修改頁面內容執行寫操作時,會產生一個”寫時復制”中斷,操作系統處理這個中斷信號,為該進程分配一個空閑頁框,復制頁面的一個副本,且修改相應的頁表項,當進程重新執行寫頁面操作時指令被順利執行。

下圖是寫時復制前的示意圖

當進行寫時復制操作時，示意圖如下所示：

可見操作系統采用寫時復制技術后,就可以延遲到修改時才對共享頁面做出副本,從而.節省了大量頁面復制操作和副本占用空間。

總結

以上是生活随笔為你收集整理的操作系统存储管理之虚拟存储与分页式虚拟存储系统的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。