工作原理
虛擬存儲器是由硬體和作業系統自動實現存儲信息調度和管理的。它的工作過程包括6個步驟:①中央處理器訪問主存的邏輯地址分解成組號a和組內地址b,並對組號a進行地址變換,即將邏輯組號a作為索引,查地址變換表,以確定該組信息是否存放在主存內。
②如該組號已在主存內,則轉而執行④;如果該組號不在主存內,則檢查主存中是否有空閒區,如果沒有,便將某個暫時不用的組調出送往輔存,以便將這組信息調入主存。
③從輔存讀出所要的組,並送到主存空閒區,然後將那個空閒的物理組號a和邏輯組號a登錄在地址變換表中。
④從地址變換表讀出與邏輯組號a對應的物理組號a。
⑤從物理組號a和組內位元組地址b得到物理地址。
⑥根據物理地址從主存中存取必要的信息。
虛實地址
1、實地址與虛地址用戶編製程序時使用的地址稱為虛地址或邏輯地址,其對應的存儲空間稱為虛存空間或邏輯地址空間;而計算機物理記憶體的訪問地址則稱為實地址或物理地址,其對應的存儲空間稱為物理存儲空間或主存空間。程式進行虛地址到實地址轉換的過程稱為程式的再定位。
2、虛存的訪問過程
虛存空間的用戶程式按照虛地址編程並存放在輔存中。程式運行時,由地址變換機構依據當時分配給該程式的實地址空間把程式的一部分調入實存。每次訪存時,首先判斷該虛地址所對應的部分是否在實存中:如果是,則進行地址轉換並用實地址訪問主存;否則,按照某種算法將輔存中的部分程式調度進記憶體,再按同樣的方法訪問主存。由此可見,每個程式的虛地址空間可以遠大於實地址空間,也可以遠小於實地址空間。前一種情況以提高存儲容量為目的,後一種情況則以地址變換為目的。後者通常出現在多用戶或多任務系統中:實存空間較大,而單個任務並不需要很大的地址空間,較小的虛存空間則可以縮短指令中地址欄位的長度。
異構體系
從虛存的概念可以看出,主存-輔存的訪問機制與cache-主存的訪問機制是類似的。這是由cache存儲器、主存和輔存構成的三級存儲體系中的兩個層次。cache和主存之間以及主存和輔存之間分別有輔助硬體和輔助軟硬體負責地址變換與管理,以便各級存儲器能夠組成有機的三級存儲體系。cache和主存構成了系統的記憶體,而主存和輔存依靠輔助軟硬體的支持構成了虛擬存儲器。在三級存儲體系中,cache-主存和主存-輔存這兩個存儲層次有許多相同點:
(1)出發點相同:二者都是為了提高存儲系統的性能價格比而構造的分層存儲體系,都力圖使存儲系統的性能接近高速存儲器,而價格和容量接近低速存儲器。
(2)原理相同:都是利用了程式運行時的局部性原理把最近常用的信息塊從相對慢速而大容量的存儲器調入相對高速而小容量的存儲器。
但cache-主存和主存-輔存這兩個存儲層次也有許多不同之處:
(1)側重點不同:cache主要解決主存與CPU的速度差異問題;而就性能價格比的提高而言,虛存主要是解決存儲容量問題,另外還包括存儲管理、主存分配和存儲保護等方面。
(2)數據通路不同:CPU與cache和主存之間均有直接訪問通路,cache不命中時可直接訪問主存;而虛存所依賴的輔存與CPU之間不存在直接的數據通路,當主存不命中時只能通過調頁解決,CPU最終還是要訪問主存。
(3)透明性不同:cache的管理完全由硬體完成,對系統程式設計師和應用程式員均透明;而虛存管理由軟體(作業系統)和硬體共同完成,由於軟體的介入,虛存對實現存儲管理的系統程式設計師不透明,而只對應用程式員透明(段式和段頁式管理對應用程式員“半透明”)。
(4)未命中時的損失不同:由於主存的存取時間是cache的存取時間的5~10倍,而主存的存取速度通常比輔存的存取速度快上千倍,故主存未命中時系統的性能損失要遠大於cache未命中時的損失。虛存機制要解決的關鍵問題
(1)調度問題:決定哪些程式和數據應被調入主存。
(2)地址映射問題:在訪問主存時把虛地址變為主存物理地址(這一過程稱為內地址變換);在訪問輔存時把虛地址變成輔存的物理地址(這一過程稱為外地址變換),以便換頁。此外還要解決主存分配、存儲保護與程式再定位等問題。
(3)替換問題:決定哪些程式和數據應被調出主存。
(4)更新問題:確保主存與輔存的一致性。
在作業系統的控制下,硬體和系統軟體為用戶解決了上述問題,從而使應用程式的編程大大簡化。
頁式調度
1、頁式虛存地址映射頁式虛擬存儲系統中,虛地址空間被分成等長大小的頁,稱為邏輯頁;主存空間也被分成同樣大小的頁,稱為物理頁。相應地,虛地址分為兩個欄位:高欄位為邏輯頁號,低欄位為頁內地址(偏移量);實存地址也分兩個欄位:高欄位為物理頁號,低欄位為頁內地址。通過頁表可以把虛地址(邏輯地址)轉換成物理地址。
在大多數系統中,每個進程對應一個頁表。頁表中對應每一個虛存頁面有一個表項,表項的內容包含該虛存頁面所在的主存頁面的地址(物理頁號),以及指示該邏輯頁是否已調入主存的有效位。地址變換時,用邏輯頁號作為頁表內的偏移地址索引頁表(將虛頁號看作頁表數組下標)並找到相應物理頁號,用物理頁號作為實存地址的高欄位,再與虛地址的頁內偏移量拼接,就構成完整的物理地址。現代的中央處理機通常有專門的硬體支持地址變換。
2、轉換後援緩衝器
由於頁表通常在主存中,因而即使邏輯頁已經在主存中,也至少要訪問兩次物理存儲器才能實現一次訪存,這將使虛擬存儲器的存取時間加倍。為了避免對主存訪問次數的增多,可以對頁表本身實行二級快取,把頁表中的最活躍的部分存放在高速存儲器中,組成快表。這個專用於頁表快取的高速存儲部件通常稱為轉換後援緩衝器(TLB)。保存在主存中的完整頁表則稱為慢表。
3、內頁表和外頁表
頁表是虛地址到主存物理地址的變換表,通常稱為內頁表。與內頁表對應的還有外頁表,用於虛地址與輔存地址之間的變換。當主存缺頁時,調頁操作首先要定位輔存,而外頁表的結構與輔存的定址機制密切相關。例如對磁碟而言,輔存地址包括磁碟機號、磁頭號、磁軌號和扇區號等。
段式調度
段是按照程式的自然分界劃分的長度可以動態改變的區域。通常,程式設計師把子程式、運算元和常數等不同類型的數據劃分到不同的段中,並且每個程式可以有多個相同類型的段。在段式虛擬存儲系統中,虛地址由段號和段內地址(偏移量)組成。虛地址到實主存地址的變換通過段表實現。每個程式設定一個段表,段表的每一個表項對應一個段。每個表項至少包含下面三個欄位:(1)有效位:指明該段是否已經調入實存。
(2)段起址:指明在該段已經調入實存的情況下,該段在實存中的首地址。
(3)段長:記錄該段的實際長度。設定段長欄位的目的是為了保證訪問某段的地址空間時,段內地址不會超出該段長度導致地址越界而破壞其他段。
段表本身也是一個段,可以存在輔存中,但一般駐留在主存中。
段式虛擬存儲器有許多優點:
①段的邏輯獨立性使其易於編譯、管理、修改和保護,也便於多道程式共享。
②段長可以根據需要動態改變,允許自由調度,以便有效利用主存空間。
段式虛擬存儲器也有一些缺點:
①因為段的長度不固定,主存空間分配比較麻煩。
②容易在段間留下許多外碎片,造成存儲空間利用率降低。
③由於段長不一定是2的整數次冪,因而不能簡單地像分頁方式那樣用虛地址和實地址的最低若干二進制位作為段內偏移量,並與段號進行直接拼接,必須用加法操作通過段起址與段內偏移量的求和運算求得物理地址。因此,段式存儲管理比頁式存儲管理方式需要更多的硬體支持。
段頁式調度
段頁式虛擬存儲器是段式虛擬存儲器和頁式虛擬存儲器的結合。實存被等分成頁。每個程式則先按邏輯結構分段,每段再按照實存的頁大小分頁,程式按頁進行調入和調出操作,但可按段進行編程、保護和共享。它把程式按邏輯單位分段以後,再把每段分成固定大小的頁。程式對主存的調入調出是按頁面進行的,但它又可以按段實現共享和保護,兼備頁式和段式的優點。缺點是在映象過程中需要多次查表。在段頁式虛擬存儲系統中,每道程式是通過一個段表和一組頁表來進行定位的。段表中的每個表目對應一個段,每個表目有一個指向該段的頁表起始地址及該段的控制保護信息。由頁表指明該段各頁在主存中的位置以及是否已裝入、已修改等狀態信息。如果有多個用戶在機器上運行,多道程式的每一道需要一個基號,由它指明該道程式的段表起始地址。虛擬地址格式如下:
基號 | 段號 | 頁號 | 頁內地址 |
變換算法
虛擬存儲器地址變換基本上有3種形虛擬存儲器工作過程式:全聯想變換、直接變換和組聯想變換。任何邏輯空間頁面能夠變換到物理空間任何頁面位置的方式稱為全聯想變換。每個邏輯空間頁面只能變換到物理空間一個特定頁面的方式稱為直接變換。組聯想變換是指各組之間是直接變換,而組內各頁間則是全聯想變換。替換規則用來確定替換主存中哪一部分,以便騰空部分主存,存放來自輔存要調入的那部分內容。常見的替換算法有4種。①隨機算法:用軟體或硬體隨機數產生器確定替換的頁面。
②先進先出:先調入主存的頁面先替換。
③近期最少使用算法:替換最長時間不用的頁面。
④最優算法:替換最長時間以後才使用的頁面。這是理想化的算法,只能作為衡量其他各種算法優劣的標準。