虛擬分頁存儲管理

① 基本分頁存儲管理

假設是按位元組編址

考慮支持多道程序的兩種連續分配方式

原因：連續分配要求進程佔有的必須是一塊連續的內存區域
能否講一個進程分散地裝入到許多不相鄰的分區，便可充分利用內存

基本分頁存儲管理的思想：把內存分為一個個相等的小分區，再按照分區大小把進程拆分成一個個小部分

頁框/頁幀：內存空間分成的一個個大小相等的分區（比如4KB）
頁框號：頁框的編號，從0開始，從低地址開始

頁/頁面：用戶進程的地址空間分為和頁框大小相等的一個個區域
頁號梁李彎：頁/頁面的編號，從0開始

進程的最後一個頁面可能沒有一個頁框那麼大，頁框不能太大，否則可能產生過大的內部碎片

操作系統以頁框為單位為各個進程分配內存空間。進程的每個頁面分別放入一個頁框中，也就是說，進程的頁面與內存的頁框有一一對應的關系
每個頁面不必連續存放，也不必按照先後順序，可以放到不相鄰的各個頁框中

進程在內存中連續存放時，通過動態重定位實現邏輯地址到物理地址的轉換。在裝入模塊之後，內存中指令使用的依然是邏輯地擾早址，直到指令執行的時候才會進行地址轉換。系統會設置一個重定位寄存器，用來存放裝入模塊存放的起始位置，重定位寄存器橡悶中的值加上邏輯地址就是該邏輯地址實際對應的物理地址

如果採用分頁技術

頁框大小為4KB，地址空間為4GB的系統
頁號為前20位，頁內偏移量為後12位

頁表：為了能知道進程的每個頁面在內存中存放的位置，操作系統要為每個進程建立一張頁表

一個進程對應一張頁表
進程的每一頁對應一個頁表項
每個頁表項由頁號和頁框號組成
頁表記錄進程頁面和實際存放的頁框之間的對應關系

每個頁表項的長度是相同的，頁號是隱含的
各頁表項會按順序連續存放在內存中，如果該頁表在內存中的起始地址是X，4GB/4KB系統的頁框有

用於實現邏輯地址到物理地址轉換的一組硬體機構

通常會在系統中設置一個頁表寄存器(PTR)，存放頁表在內存中的起始地址F和頁表長度M（M個頁表項）
進程未執行時，頁表的起始地址和頁表長度放在進程式控制制塊(PCB)中，當進程被調度時，操作系統內核會把他們放到頁表寄存器中

基本分頁存儲管理中地址是一維的，即只要給出一個邏輯地址，系統就可以自動計算出頁號、偏移量，不需要顯式告訴系統偏移量是多少

理論上，頁表項長度為3即可表示內存塊號的范圍，但是為了方便頁表查詢，會讓頁面恰好能裝得下整數個頁表項，令每個頁表項佔4位元組
4KB頁面，可以放4096/3 =1365個頁表項，有4096%3 =1B的碎片，訪問1365及之後的頁表項時，還要考慮前面的頁框中的碎片，才能得到頁表項的物理地址，比較麻煩

進程頁表通常存放在連續的頁框中，這樣就能用統一的計算方式得到想要得到的頁表項存儲的位置

地址變換過程中有兩次訪存操作：查詢頁表、訪問目標內存單元

局部性原理

如果這個程序將程序對應的指令存放在10號內存塊，將程序中定義的變數存放在23號內存塊，當這個程序執行時，會很頻繁地反問10、23號內存塊

時間局部性：如果執行了程序中的某條指令，那麼不久後這條指令很有可能被再次執行；如果某個數據被訪問過，不久之後該數據很有可能再次被訪問（因為程序存在大量循環）
空間局部性：一旦程序訪問了某個存儲單元，在不久之後，其附近的存儲單元也很有可能被訪問（因為很多數據在內存中連續存放）

基本地址變換機構中，每次要訪問一個邏輯地址，都要查詢頁表，由於局部性原理，可能連續多次查詢同一個頁表項

快表：又稱聯想寄存器（TLB），是一種訪問速度比內存塊很多的高速緩存，用來存放當前訪問的若干頁表項，以加速地址變換的過程。內存中的頁表常稱為慢表

引入快表後地址的變換過程

一般來說，快表的命中率可以達到90%以上

單級頁表存在的問題

對問題1

可將頁表進行分組，使每個內存塊剛好可以放入一個分組。為離散分配的頁表再建立一張頁表，稱為頁目錄表，或外層頁表
各級頁表的大小不能超過一個頁面

針對兩級頁表

對問題2

可以在需要訪問頁面時，才把頁面調入內存（虛擬存儲技術），可以在頁表項中增加一個標志位，用於表示該頁面是否已經調入內存
若想訪問的頁面不在內存中，會產生缺頁中斷（內中斷），然後將目標頁面從外存調入內存
之後的文章會有展開

兩級頁表訪存次數分析：如果沒有TLB，第一次訪存是訪問內存中的頁目錄表，第二次訪存是訪問內存中的二級頁表，第三次訪存是訪問目標內存單元

② 採用頁式虛擬存儲管理方式頁大小為8KB，主存塊大小為64B，為什麼物理地址的頁內偏移量不等於主存塊大小

物理地址的頁偏移量等於對應虛擬地址的頁偏移量，虛擬地址的頁偏移量與頁大小有關，這里頁大小8KB，2的13次方，所以頁偏移量為13位。

③ 儲存管理中,分頁式虛擬儲存管理的頁面淘汰演算法有

儲存管理中，分頁式虛擬儲存管理的頁面淘汰鏈森演算法有先進先出法，最近最少使用頁面陸櫻先淘汰，最優淘汰演算法。最優淘汰演算法(OPT)：系統預測作業今後要訪問的頁面，淘汰頁是將來不被訪問的頁面或者在最長時間早喚叢後才被訪問的頁面。它保證有最少的缺頁率，但它實現困難，只能通過理論分析用來衡量其它演算法的優劣。

④ 分頁式虛擬存儲系統中，頁面大小與可能產生的缺頁中斷次數____。 A.成正比 B.成反比 C.無關 D.成固定比例

分頁式虛擬存儲系統中，頁面大小與可能產生的缺頁中斷次數成固定比例；答案選擇D；

若執行的程序佔用內存很大或很多，則會導致內存消耗殆盡。為解決該問題，Windows中運用了虛擬內存技術，即勻出一部分硬碟空間來充當內存使用。當內存耗盡時，電腦就會自動調用硬碟來充當內存，以緩解內存的緊張。

調度方式

調度方式有分頁式、段式、段頁式3種。頁式調度是將邏輯和物理地址空間都分成固定大小的頁。主存按頁順序編號，而每個獨立編址的程序空間有自己的頁號順序，通過調度輔存中程序的各頁可以離散裝入主存中不同的頁面位置，並可據表一一對應檢索。

頁表對程序員來說是透明的，地址變換快，調入操作簡單；缺點是各頁不是程序的獨立模塊，不便於實現程序和數據的保護。段式調度是按程序的邏輯結構劃分地址空間，段的長度是隨意的，並且允許伸長，它的優點是消除了內存零頭，易於實現存儲保護，便於程序動態裝配；缺點是調入操作復雜。

將這兩種方法結合起來便構成段頁式調度。在段頁式調度中把物理空間分成頁，程序按模塊分段，每個段再分成與物理空間頁同樣小的頁面。段頁式調度綜合了段式和頁式的優點。其缺點是增加了硬體成本，軟體也較復雜。大型通用計算機系統多數採用段頁式調度

⑤ 頁式虛擬存儲管理,過小的頁會引起什麼問題

會引起內存變小。在頁式虛擬存儲管理系統中，頁面的大小是由計算機系統的地址結構所決定的，一般由軟硬體共同決定。對於某一種系統一般採用一種大小穗簡的頁面，也有部分現代操蘆皮作系統採用雙頁面系統的。在確定地址結構時，若選擇的頁面較小，一方面可使內碎片減小，並減少了內碎猜嘩褲片的總空間，有利於提高內存利用率。另一方面，也會使每個進程要求較多的頁面，從而導致頁表過長，佔用大量內存。此外還會降低頁面換進換出的效率。

⑥ 內存擴充之虛擬存儲技術

傳統存儲管理

特徵

時間局部性：如果執行了程序中的某條指令，那麼不久後這條指令很有可能再次執行；如果某個數據被訪問過，不久之後該數據很可能再次被訪問（因為程序中存在大量循環）
空間局部性：一旦程序訪問了某個存儲單元，在不久之後，其附近的存儲單元很有可能被訪問（因為很多數據在內存中是連續存放的，並且程序的指令也是順序地在內存中存放的

寄存器
高速緩存
內存
外存（如磁碟、磁帶等）

越往上容量越小，訪問速度越快，成本越高
越往下容量越大，訪問速度越慢，成本越低

高速緩存技術的思想：將近期會頻繁訪問到的數據放到更高速的存儲器中，暫時用不到的數據放在更低速存儲器中
快表機構就是將近期常訪問的頁表項副本放到更高速的cache中

基於局部性原理，在程序裝入時，可以將程序中很快就會用到的部分裝入內存，暫時用不到的部分留在外存，就可以讓程序開始執行
在程序執行過程中，當所訪問的信息不在內存時，由操作系統負責將所需信息從外存調入內存，然後繼續執行程序
若內存空間不夠，由操作系統將內存中暫時用不到的信息換出到外存

因此，在操作系統的管理下，在用戶看來似乎有一個比實際內存大得多的內存，這就是虛擬內存
操作系統虛擬性的一個體現，實際的物理內存大小沒有變，只是在邏輯上進行了擴充

虛擬內存的最大容量是由計算機的地址結構（CPU定址范圍）確定的
虛擬內存的實際容量 = min(內存外存容量之和，CPU定址范圍)

虛擬內存有以下三個主要特徵

虛擬內存技術，允許一個作業多次調入內存。如果採用連續分配方式，會不方便實現。因此，虛擬內存的實現需要建立在離散分配的內存管理方式基礎上

傳統的非連續分配存儲管理
基本分頁存儲管理
基本分段存儲管理
基本段頁式存儲管理

虛擬內存的實現
請求分頁存儲管理
請求分段存儲管理
請求段頁式存儲管理

主要區別：在程序執行過程中，當所訪問的信息不在內存時，由操作系統負責將所需信息從外存調入內存，然後繼續執行程序。若內存空間不夠，由操作系統負責將內存中暫時用不到的信息換出到外存
操作系統要提供請求調頁/段功能、頁面/段置換功能

請求分頁存儲管理和基本分頁存儲管理的主要區別

頁表機制
頁表項：內存塊號、狀態位、訪問欄位、修改位、外存地址，頁號時隱含的
內存塊號是頁面在內存中對應的頁框號，如果狀態位為0，則內存塊號為無
狀態位表示是否已被調入內存
訪問欄位記錄最近被訪問過幾次，或者上次訪問時間，由此操作系統能夠提供置換演算法
修改位記錄頁面被調入內存後是否被修改過，如果沒有，就不需要浪費時間寫回外存
外存地址是頁面在外存中的存放位置

缺頁中斷機構
在請求分頁系統中，每當要訪問的頁面不在內存時，便會產生一個缺頁中斷，然後由操作系統的缺頁中斷處理程序處理中斷（內中斷）
此時缺頁的進程阻塞，放入阻塞隊列，調頁完成後再將其喚醒，放回就緒隊列
如果內存中有空閑塊，則為進程分配一個空閑塊，將所缺頁面裝入該塊，並修改頁表中相應的頁表項
如果內存中沒有空閑塊，則由頁面置換演算法選擇一個頁面淘汰，若該頁面在內存期間被修改過，則要將其寫回外存，為修改過的頁面不用寫回外存
一條指令再執行期間可能產生多次缺頁中斷（ A to B）

新增的步驟

頁面的換入、換出需要磁碟IO，會有較大的開銷，因此好的頁面置換演算法應該追求更少的缺頁率

缺頁中斷≠頁面置換
發生缺頁中斷會發生調頁，只有內存塊滿了才發生頁面置換

最佳置換演算法OPT：每次淘汰以後永不使用或最長時間內不再被訪問的頁面
理想化的演算法，很難實現

先進先出演算法FIFO：每次淘汰最先進入內存的頁面
實現：把調入內存的頁面根據調入的先後順序排成隊列，頁面置換時換出隊頭頁面，新調入的頁面排到隊尾
優點：實現簡單
缺點1：belady異常，為進程分配的物理塊數增大時，缺頁次數不減反增的異常現象。只有FIFO會產生belady異常。
缺點2：演算法與進程實際運行時的規律不適應，因為先調入的頁面有可能最經常被訪問，因此演算法性能差

最近最久未使用置換演算法LRU：淘汰最近最久未使用的頁面
實現方法：賦予每個頁面對應的頁表項中，用訪問欄位記錄該頁面自上次被訪問以來所經歷的時間t
優點：性能最接近OPT
缺點：實現困難、開銷大

時鍾置換演算法CLOCK/NRU

簡單NRU：為每一個頁表項設置一個訪問位，再將內存中的頁面都通過連接指針連成一個循環隊列，當某頁被訪問時，訪問位為1，只需檢查頁的訪問位。如果為0，就將該頁換出，否則將其改為0，暫不換出，繼續向後掃描，若第一輪掃描都是1，將這也頁面的訪問位改為0後，進行第二輪掃描，第二輪掃描中一定會有訪問位為0的頁面，將其換出。因此最多經過兩輪掃描

改進NRU：如果淘汰的頁面沒有被修改過，就不需要執行IO操作，只有淘汰的頁面被修改過時，才需要寫回外存。因此，同時考慮最近有無訪問和有無修改，在其他條件相同時，優先淘汰沒有修改過的頁面，避免IO操作
第一輪：找到第一個訪問位和修改位都為0的頁面進行替換，如果沒有找到進行下一輪掃描
第二輪：查找第一個訪問位為0，修改位為1的頁面進行替換，本輪將所有被掃描過的訪問位設置為0，如果沒有進行下一輪掃描
第三輪：查找0，0替換否則下一輪
第四輪：查找0，1替換
最多會進行四輪掃描

駐留集：請求分頁管理中給進程分配的物理塊的集合
在採用了虛擬存儲技術的系統中，駐留集大小一般小於進程的總大小
駐留集太小，導致缺頁頻繁，系統要花大量時間處理缺頁，實際用於進程推進的時間很少
駐留集太大，會導致多道程序並發度下降，資源利用率降低

固定分配：操作系統為每個進程分配一組固定數目的物理塊，在進程運行期間不再改變
可變分配：先為每個進程分配一定數目的物理塊，在進程運行期間，可根據情況作適當的增加或減少

局部置換：發生缺頁時只能選進程自己的物理地址塊進行置換
全局置換：可以將操作系統保留的空閑物理塊分配給缺頁進程，也可以將別的進程持有的物理塊置換到外存，再分配給缺頁進程

不存在固定分配全局置換的策略，因為全局置換意味著一個進程擁有的物理塊數量必然改變
其他三種組合存在

固定分配局部置換：系統為每個進程分配一定數量的物理塊，在整個運行期間都不改變。若進程在運行中發生缺頁，並且需要進行頁面置換，則只能從該進程在內存中的頁面中選出一頁換出，然後再調入需要的頁面
缺點：很難在剛開始就確定應為每個進程分配多少個物理地址塊才算合理（採用這種策略的系統可以根據進程大小、優先順序、或是根據程序員給出的參數來確定為一個進程分配的內存塊數

可變分配全局置換：剛開始會為進程分配一定數量的物理塊。操作系統會保持一個空閑物理塊隊列，當某進程發生缺頁時，從空閑物理塊中取出一塊分給該進程；若無空閑物理塊，則選擇一個未鎖定的頁面換出到外存，再將該物理塊分配給缺頁的進程。採用這種策略時，只要某進程發生缺頁，都將獲得新的物理塊，僅當空閑物理塊用完時，系統才選擇一個未鎖定的頁面調出。被選擇調出的頁面可能是系統中任何一個進程的頁面，因此這個被選中的進程擁有的物理塊會減少，缺頁率會增加
只要缺頁就給該進程分配新的物理塊

可變分配局部置換：剛開始會為每個進程分配一定數量的物理塊，當某進程發生缺頁時，只允許從該進程自己的物理塊中選出一個進行頁面置換。如果進程在運行過程中頻繁缺頁，系統會為該進程多分配幾個物理塊，直至該進程缺頁率趨於適當程度；反之，如果缺頁率太低，就是當減少分配給該進程的內存塊數
要根據發生缺頁的頻率來動態增加或減少進程的物理塊

何時調入頁面

從何處調入頁面
對換區：讀寫速度更快，採用連續分配方式
文件區：讀寫速度更慢，採用離散分配方式

抖動/顛簸現象：剛剛換出的頁面馬上要換入內存，剛剛換入的頁面馬上要換出外存，這種頻繁的頁面調度行為稱為抖動/顛簸
主要原因是進程頻繁訪問的頁面數目高於可用的物理塊數（分配給進程的物理塊不夠）

為進程分配物理塊太少會使進程發生抖動現象，為進程分配的物理塊太多會降低系統的並發度降低某些資源的利用率。因此提出了「工作集」的概念
工作集：在某段時間間隔里，進程實際訪問頁面的集合
駐留集：請求分頁存儲管理中給進程分配的內存塊的集合
駐留集不能小於工作集，否則進程運行過程中將頻繁缺頁

⑦ linux為什麼主要採用分頁機制來實現虛擬存儲管理

1 分頁機制
在虛擬內存中，頁表是個映射表的概念, 即從進程能理解的線性地址(linear address)映射到存儲器上的物理地址(phisical address).
很顯然，這個頁表是需要常駐內存的東西, 以應對頻繁的查詢映射需要(實際上，現代支持VM的處理器都有一個叫TLB的硬體級頁表緩存部件，本文不討論）。
1.1 為什麼使用多級頁表來完成映射

但是為什麼要使用多級頁表來完成映射呢?
用來將虛擬地址映射到物理地址的數據結構稱為頁表, 實現兩個地址空間的關聯最容易的方式是使用數組, 對虛擬地址空間中的每一頁, 都分配一個數組項. 該數組指向與之關聯的頁幀, 但這會引發一個問題, 例如, IA-32體系結構使用4KB大小的頁, 在虛擬地址空間為4GB的前提下, 則需要包含100萬項的頁表. 這個問題在64位體系結構下, 情況會更加糟糕. 而每個進程都需要自身的頁表, 這回導致系統中大量的所有內存都用來保存頁表.
設想一個典型的32位的X86系統，它的虛擬內存用戶空間(user space)大小為3G, 並且典型的一個頁表項(page table entry, pte)大小為4 bytes，每一個頁(page)大小為4k bytes。那麼這3G空間一共有(3G/4k=)786432個頁面，每個頁面需要一個pte來保存映射信息，這樣一共需要786432個pte!
如何存儲這些信息呢？一個直觀的做法是用數組來存儲，這樣每個頁能存儲(4k/4=)1K個，這樣一共需要(786432/1k=)768個連續的物理頁面(phsical page)。而且，這只是一個進程，如果要存放所有N個進程，這個數目還要乘上N! 這是個巨大的數目，哪怕內存能提供這樣數量的空間，要找到連續768個連續的物理頁面在系統運行一段時間後碎片化的情況下，也是不現實的。
為減少頁表的大小並容許忽略不需要的區域, 計算機體系結構的涉及會將虛擬地址分成多個部分. 同時虛擬地址空間的大部分們區域都沒有使用, 因而頁沒有關聯到頁幀, 那麼就可以使用功能相同但內存用量少的多的模型: 多級頁表

但是新的問題來了, 到底採用幾級頁表合適呢?
1.2 32位系統中2級頁表
從80386開始, intel處理器的分頁單元是4KB的頁, 32位的地址空間被分為3部分

單元
描述

頁目錄表Directory 最高10位
頁中間表Table 中間10位
頁內偏移 最低12位
即頁表被劃分為頁目錄表Directory和頁中間表Tabl兩個部分
此種情況下, 線性地址的轉換分為兩步完成.
第一步, 基於兩級轉換表(頁目錄表和頁中間表), 最終查找到地址所在的頁幀
第二步, 基於偏移, 在所在的頁幀中查找到對應偏移的物理地址
使用這種二級頁表可以有效的減少每個進程頁表所需的RAM的數量. 如果使用簡單的一級頁表, 那將需要高達220個頁表, 假設每項4B, 則共需要佔用220?4B=4MB的RAM來表示每個進程的頁表. 當然我們並不需要映射所有的線性地址空間(32位機器上線性地址空間為4GB), 內核通常只為進程實際使用的那些虛擬內存區請求頁表來減少內存使用量.
1.3 64位系統中的分頁
正常來說, 對於32位的系統兩級頁表已經足夠了, 但是對於64位系統的計算機, 這遠遠不夠.
首先假設一個大小為4KB的標准頁. 因為1KB覆蓋210個地址的范圍, 4KB覆蓋212個地址, 所以offset欄位需要12位.
這樣線性地址空間就剩下64-12=52位分配給頁中間表Table和頁目錄表Directory. 如果我們現在決定僅僅使用64位中的48位來定址(這個限制其實已經足夠了, 2^48=256TB, 即可達到256TB的定址空間). 剩下的48-12=36位被分配給Table和Directory欄位. 即使我們現在決定位兩個欄位各預留18位, 那麼每個進程的頁目錄和頁表都包含218個項, 即超過256000個項.
基於這個原因, 所有64位處理器的硬體分頁系統都使用了額外的分頁級別. 使用的級別取決於處理器的類型

平台名稱
頁大小
定址所使用的位數
分頁級別數
線性地址分級

alpha 8KB 43 3 10 + 10 + 10 + 13
ia64 4KB 39 3 9 + 9 + 9 + 12
ppc64 4KB 41 3 10 + 10 + 9 + 12
sh64 4KB 41 3 10 + 10 + 9 + 12
x86_64 4KB 48 4 9 + 9 + 9 + 9 + 12