計算機系統基礎（八）虛擬儲存器
版權宣告：本文為博主原創文章，未經博主允許不得轉載。
上篇文章講了CPU在記憶體中讀取資料時，為了提高讀取速度，在中間增加了一層快取，即快取記憶體Cache。
這篇文章我們的角度下放，重點來看一下程式在執行過程中，記憶體是如何管理的。
記憶體問題
計算機出現的早期，其工作內容比較簡單，同一時間只做一個計算任務，然後輸出結果。
但隨著人類需求的提高，人們希望計算機能同時計算多個任務，提高計算機的使用率。逐漸地，多工計算機出現，但要想同時執行多個任務，那各任務之間如何分配和使用計算機資源呢？
為了解決這個問題，人類發明出操作系統，所有的計算機資源交由作業系統統一管理，各程式需要使用資源要向作業系統提出申請，作業系統按照某種規則統一分配和管理，同時保證資源的合理分配。
記憶體是一段連續的地址空間，如果多個程式同時執行，對於記憶體的時候一不小心會不會侵入了別的程式，導致執行結果產生錯誤？那麼如何合理地分配和保護記憶體資源，變得十分重要。
我們都知道，一段程式要想執行必須載入到記憶體，然後CPU從記憶體獲取指令和資料進行邏輯運算和處理，但如果一段程式執行時需要的記憶體非常大，超過了計算機的實體記憶體，這種程式還能否執行呢？
我們整理一下，針對記憶體資源遇到的問題：
- 多個程式同時執行，如何保證各程式之間記憶體資源分配合理，且資源互不干擾？
- 程式執行能否突破實體記憶體的大小？
基於這2個問題，我們來看一下，計算機是如何解決這些問題的，這其中涉及硬體與作業系統共同的協作。
記憶體分割槽和分頁
早期計算機同一時間只能執行一個程式，記憶體中僅包含作業系統和正在執行的一個使用者程式，所以記憶體管理起來很簡單，只需要劃分作業系統區域和使用者區域即可。
現代計算機採用多道程式執行方式，記憶體中包含作業系統和多個使用者程式，為了提高計算機的利用率，應當儘可能地讓使用者程式使用硬體資源然後工作。
這就需要對記憶體進行劃分和管理，劃分的區域主要是“使用者區”，而劃分的任務交由作業系統管理，這個過程叫做“儲存器管理”。
早期經常採用“交換”技術讓系統儘量多地把使用者程式調入到記憶體中，“交換“技術的實現方式主要有兩種： 分割槽和分頁 。
分割槽
分割槽方式將記憶體分為兩大區域：作業系統區、使用者區域。
然後對使用者區域再進行分割槽，主要有2種方式： 簡單固定分割槽和可變長分割槽 。
簡單固定分割槽
36046604.png?imageMogr2/thumbnail/!70p"/>
如圖，系統把”使用者區“分成若干不等的固定分割槽，當一個使用者程式調入記憶體時，分配一個最能夠容納它的最小分割槽給它。
例如，如果一個使用者程式需要196K的記憶體空間，則將256K的分割槽給它。
很明顯，每個使用者程式所需的記憶體空間不可能正好和這些分割槽大小相對應，所以這種分割槽方式會大大浪費記憶體空間。
可變長分割槽
如圖，可變長分割槽方式是根據使用者程式所需記憶體空間直接分配對應大小的空間，剛開始每個程式都能分配到自己所需的記憶體區域，但如果程式進入IO等待狀態，作業系統則將這塊空間換出到磁碟，騰出空間等待別的調入其他程式。如果此時另外一個程式被調入記憶體，但所需空間比之前換出的記憶體空間小，那麼這時就會產生 碎片 。
各程式記憶體交換的越頻繁，碎片就越多，此時記憶體的利用率下降。
這2種方式都會產生“碎片”，當然，通過移動使用者程式可以將“碎片”合併以提高記憶體利用率，但會增加CPU的額外處理時間，也增加了重定位硬體的開銷。
因此，分割槽方式不是解決多到程式執行的有效辦法，現代多工作業系統已經不再使用這種方法，我們對其有所瞭解即可。
分頁
另外一種方式就分頁，分頁具體方式如下：
- 把實體記憶體劃分成固定且很小的塊，稱為 頁框 ，每個程序也劃分為固定長的塊，稱為 頁
- 程序的程式塊裝到可用的儲存塊中，且 無須用連續 的頁框來存放
- 編寫程式不再使用實體地址，所有程式使用統一的 虛擬地址
- 作業系統提供一個 頁表 ，提供虛擬地址到實體地址的轉換
如上圖，每個使用者程序都使用虛擬地址，然後都通過頁表找到對應的實體地址，然後從記憶體中讀取資料。
但一個使用者程序想要執行，並沒有一次性地將這個程序所有需要的資料調入記憶體中，而是基於區域性性原理，採用了 ”請求分頁“ 的方式管理，即程式執行到哪裡，需要哪塊的資料，此時再把相應的資料塊裝入記憶體頁框內，大大提高記憶體的使用率。
當程式訪問的資料所在頁不在記憶體時，則發生 缺頁 ，此時，作業系統會從磁碟中將資料調入記憶體。
虛擬地址空間
採用虛擬地址這種機制，為程式設計師提供了一個極大的虛擬地址空間，它是記憶體和磁碟IO裝置的抽象。
由此帶來了3個好處：
- 每個程序都具有一致的虛擬地址空間，簡化了編寫程式的記憶體地址，方便管理
- 它把記憶體看成是磁碟的一個快取，記憶體只儲存活動的程式資料，並根據需要在磁碟和記憶體之間進行資訊交換
- 每個程序的虛擬地址空間都是私有的，可以保護各自程序不被其他程序破壞
一段程式經過編譯、彙編、連結處理後生成可執行的二進位制機器目的碼後，每個程式的目的碼都被對映到同樣的虛擬地址空間，所有使用者程序的虛擬地址空間都是一致的。
例如，在Linux上執行一個hello程式，對應的程序虛擬地址空間如下圖：
- 作業系統核心區：主要存放作業系統核心程式碼和資料以及每個程序相關資料結構
- 使用者棧：存放程式執行時過程呼叫的引數、返回值、返回地址、過程區域性變數，此區動態從高地址向低地址遞增或反向減退
- 共享庫：存放公共共享函式庫程式碼，例如
printf()函式 - 堆：存放動態申請空間，例如C語言的
malloc()函式分配變數區，從低地址向高地址增長，free()函式釋放記憶體，從高地址向低地址減退 - 讀寫資料區：存放使用者程序中的靜態全域性變數
- 只讀資料和程式碼：存放使用者程序中的程式碼和只讀資料，例如程式碼和字串
有沒有發現，這個虛擬地址空間的劃分比較有意思：
- 整個區域分為系統核心區和使用者區，分別在兩端
- 使用者區又分為動態區和靜態區，分別在兩端
- 動態區又分為棧區和堆區分，分別在兩端
- 靜態區又分為可讀寫區和只讀區，也分別在兩端
這樣的劃分，就是為了便於每個區域的訪問許可權設定，從而便於儲存保護和儲存管理。
虛擬儲存器的實現
虛擬儲存器機制與之前講的快取記憶體Cache機制很類似，快取記憶體Cache是快取了記憶體中的資料， 虛擬儲存器是在記憶體中快取了磁碟的資料 。
同樣，Cache與記憶體的對映和一致性問題，虛擬儲存器同樣要解決類似的問題：
- 對於CPU讀取資料，如果記憶體中不存在，磁碟中的資料如何分配到記憶體中？
- 對於CPU寫入資料，如何保證記憶體和磁碟資料的一致性？
虛擬儲存器是快取了磁碟的資料，如果虛擬儲存器中資料不存在，那麼需要從磁碟上讀取資料，然後放入記憶體。
由於磁碟的速度要比記憶體慢10萬倍，所以除了必要的情況，應儘量少的從磁碟反覆讀取資料。所以虛擬儲存區採用 全相聯對映 的方式，保證記憶體中儘量裝入更多的磁碟資料。
同樣，由於對於寫操作，由於寫磁碟速度很慢，所以每次寫操作不能同時寫磁碟，應該採用 回寫法 的方式，在記憶體資料發生改變時，再一次性寫入磁碟，減少磁碟操作。
虛擬儲存器採用全相聯對映方式，所以每個虛擬地址可以對映到記憶體的任何一個空閒位置，因此與Cache類似，虛擬儲存器必須有一種方法確定每個程序虛擬地址對應記憶體的位置或磁碟位置。
對映方式有3種： 分頁式、分段式和段頁式 ，下面我們來逐個分析。
分頁式虛擬儲存器
分頁式儲存器把記憶體和虛擬地址空間都劃分成 大小相等 的頁面，磁碟和記憶體按頁面為單位交換資訊。
通常把虛擬地址空間的頁面成為 虛擬頁/邏輯頁（VP） ，記憶體中的頁面成為 頁框/物理頁（PP） 。
頁表
作業系統在記憶體中給每個程序生成一個頁表，頁表中對應每個虛擬頁都有一個表項，表項內容包括 存放位置欄位、裝入位、修改位、替換控制位、存取許可權位、禁止快取位 。
它們的作用分別如下：
- 存放位置欄位：用來建立虛擬頁和物理頁之間的對映，用於虛擬地址到實體地址的轉換
- 裝入位：也稱有效位或存在位，為1表示磁碟資料已調入記憶體，位置欄位指向物理頁號。為0表示磁碟資料沒有被調入記憶體，若位置欄位為null則說明此位置空閒，若不為null則說明等待磁碟資料調入記憶體
- 修改位：標識頁面是否被修改過，在執行回寫策略時根據此欄位判斷是否需要把資料寫回磁碟
- 替換控制位：標識頁面使用情況，配合替換策略設定
- 訪問許可權位：標識頁面是可讀可寫、只讀、只可執行，用於儲存保護
- 禁止快取位：標識頁面是否可以裝入Cache，保證磁碟、記憶體、Cache資料一致性
頁表、記憶體、磁碟的對映示意圖如下：
例如，CPU執行一條指令需要訪問資料，該資料正好在虛擬頁VP1中，查詢頁表可知，VP1裝入位為1，對應的物理頁PP0，這時就可以通過地址轉換部件把將虛擬地址轉換為實體地址，然後訪問PP0的資料。
如果資料在VP6中，VP6對應的裝入位為0，表示頁面缺失，發生 “缺頁” 異常，需要作業系統進行“缺頁”異常處理程式處理。“缺頁”異常處理程式根據頁表中VP6對應的存放位置欄位，從磁碟中將資料讀出，然後找一個空閒的物理頁框存放，若記憶體中沒有空閒的頁框，則選擇一個頁面替換到磁碟上。
因為採用 寫回策略 ，所以頁面淘汰時，需要根據修改位確定是否要寫回磁碟。缺頁處理過程中需要對頁表進行相應的更新。缺頁異常處理結束後，程式回到原來發生缺頁的指令繼續執行。
對於VP0和VP4，隨著程序的動態執行，這些頁面可能就會有了具體的資料。例如，當呼叫 malloc 函式時，堆區增長，新增的堆區正好與VP4對應，則作業系統就在磁碟上分配一個儲存空間給VP4，同時把VP4頁表項中的存放位置欄位填上，對應的就是磁碟上的起始地址。之後便等待訪問到這頁資料時，再次執行上面的缺頁異常流程，讀取資料。
地址轉換
上面說完了頁表、記憶體、磁碟的對映關係和資料讀取流程，其中有個環節是需要把虛擬地址轉換為真正的實體地址，那這個過程是如何轉換的呢？
這個轉換工作由CPU中的 儲存器管理部件（MMU） 完成，具體做法如下：
- 虛擬地址分為兩部分：高位為虛擬頁號，低位為頁內偏移地址
- 實體地址也分為兩部分：高位是物理頁號，低位為頁內便宜地址
- 每個程序都有一個頁表基址暫存器，存放該程序頁表首地址
- 根據頁表基址暫存器找到對應的頁表，由虛擬地址高位部分的虛擬頁號為索引，找到頁表項
- 若裝入位為1，則取出對應的物理頁號，然後和虛擬頁內地址拼接，得到司機的實體地址
- 如裝入位為0，則交給作業系統執行“缺頁”處理
執行流程如下圖：
快表
從上述過程我們可以看出，每次訪問記憶體都需要先查頁表，然後根據規則找出實體地址，然後再訪問實際的實體地址對應的資料。
如果發生缺頁，還要進行頁表替換、頁表修改等操作，訪問記憶體的次數就更多。採用虛擬儲存器，訪問記憶體的次數增加了很多。那有沒有什麼辦法減少訪問次數，還能達到同樣的效果呢？
答案是可以的，我們可以把頁表中最活躍的幾個頁表項複製到快取記憶體Cache中，這種快取記憶體Cache中的頁表項組成的頁表稱為 快表（TLB） 。
這樣在進行地址轉換時，先檢視快表中是否命中，如果命中，則無需訪問記憶體中的頁表即可。通過這種方式可大大降低記憶體訪問的次數，提升效率。
到這裡，我們可以總結一下CPU訪問資料的完整過程：
分段式虛擬儲存器
分頁方式的虛擬儲存器優點是頁長固定，易管理，不存在碎片。但缺點是頁長與程式的邏輯大小無關。
例如，某個時刻一段程式碼有一部分在記憶體中，另外一部分則在磁碟上，不利於程式設計時的獨立性，且給儲存保護和儲存共享造成了麻煩。
所以又提出了 分段式 的儲存器。把一段程式按照類別劃分為段，例如方法、運算元、常數劃分到不同的段中，每個段都是一組相對完整的邏輯資訊。
這樣做的好處是可以按不同型別進行儲存管理，也利於多個程式組合時，對同一段邏輯可以組合複用提供了便利。
分段的方式具體如下：
- 虛擬地址由 段號 和 段內地址 組成
- 記憶體按程式中的段劃分，每個段在記憶體中的位置記錄在 段表 中
- 每個程序都有一個段表，每個段在段表中有一個 段表項 ，標識段的位置、長度、訪問許可權、使用和裝入情況
分段儲存器把虛擬地址轉換為實體地址流程如下：
分段式虛擬儲存器的優點：
- 段的劃分與程式的自然分界相對應
- 段的易於編譯、管理、修改和保護，也便於多道程式共享
- 段具有動態可變長度，允許自由排程以便利用記憶體空間
分段式虛擬儲存器的缺點：
- 段的長度不相同，起點和終點不固定，給記憶體分配帶來麻煩
- 容易在記憶體中留下零碎空間，導致空間浪費
分頁式和分段式儲存管理各有優缺點，那有什麼辦法結合兩者的優點？這就是下面要講的： 段頁式虛擬儲存器 。
段頁式虛擬儲存器
段頁式虛擬儲存器是結合了分頁式和分段式的優點，具體方式如下：
- 程式 按模組分段，段內再分頁 ，用 段表和頁表 進行兩級定位管理
- 段表中每個表項對應一個段，每個段表中包含一個指向該段頁表起始位置以及控制資訊和保護資訊
- 頁表指明該段各頁在記憶體中的位置和是否裝入、修改等狀態資訊
程式資料調入調出按頁進行，又可以按段實現共享和保護。缺點是地址對映過程需要多次查表。
每個使用者程序有一個基號，標識使用者程序，程序的段表起始地址存放在各自對應的基地暫存器中，格式如下：
邏輯地址到實體地址的轉換過程如下圖：
儲存保護
為了避免多個程式執行時互相干擾，或者某個程式不合法地訪問了其他程式的資料，我們應該對每個程式進行儲存保護，保護的物件包括 作業系統和使用者程式 。
對作業系統儲存保護主要是硬體提供支援：
- 支援至少2種執行模式：管理模式、使用者模式，作業系統在管理模式下管理各種功能，使用者程序執行在使用者模式下
- 部分CPU狀態只能由系統程序寫，使用者程序只能讀：例如段表、頁表首地址、TLB內容等
- 提供讓CPU在管理模式和使用者模式之間切換的機制：通過“異常”處理讓CPU從使用者模式切換到管理模式，異常處理完成後通過“返回”指令讓CPU回到使用者模式
對於使用者程序的保護主要分為 訪問方式保護 和 儲存區域保護 ：
- 訪問方式保護：檢查“訪問越權”，通過段表或頁表的訪問許可權位控制，例如共享區域只可讀不可寫，程式段只可執行或只讀，未授權區域不可訪問等
- 儲存區域保護：檢查“地址越界”，通過段頁的起始地址和終止地址控制
總結
虛擬儲存器相關的知識點比較多，而且比較零碎，總結如下：
- 多道程式執行時需要解決2個問題：多個程式執行如何互不干擾？程式執行能否突破實體記憶體大小？
- 針對問題提出了虛擬儲存器的方式對記憶體進行管理
- 虛擬儲存器對記憶體進行了歸類劃分，有2種方式：分割槽和分頁，現代計算機主要使用分頁方式管理
- 虛擬地址空間對程式使用記憶體進行了統一抽象管理，同時為記憶體劃分和儲存保護提供基礎
- 虛擬儲存器的實現包含分頁式、分段式、段頁式3種方式，其中段頁式結合了分段和分頁的優點
- 儲存保護的物件包含作業系統和使用者程式
- 作業系統的儲存保護主要依賴硬體，使用者程式的儲存保護f通過作業系統控制