通過Rust編寫操作系統之內存的分頁與管理介紹（上）

Rust是一門系統編程語言，專註於安全，尤其是並發安全，支持函數式和命令式以及泛型等編程範式的多範式語言。Rust在語法上和C 類似，但是設計者想要在保證性能的同時提供更好的內存安全。Rust最初是由Mozilla研究院的Graydon Hoare設計創造，然後在Dave Herman, Brendan Eich以及很多其他人的貢獻下逐步完善的。Rust的設計者們通過在研發Servo網站瀏覽器布局引擎過程中積累的經驗優化了Rust語言和Rust編譯器。

Rust編譯器是在MIT License 和 Apache License 2.0雙重協議聲明下的免費開源軟體。Rust已經連續三年（2016，2017，2018）在Stack Overflow開發者調查的「最受喜愛編程語言」評選項目中折取桂冠。

本文介紹了內存分頁技術，這是一種非常常見的內存管理方案，我們也將該技術用於通過 Rust 編寫操作系統中。內存分頁技術解釋了為什麼需要內存隔離、分段如何工作、虛擬內存是什麼以及分頁如何解決內存碎片（memory fragmentation）問題。另外，本文還探討了x86_64體系結構上的多級頁表布局情況，本文的完整源代碼可以在GitHub 的post-08主題中找到。

內存保護

操作系統的一個主要任務是將程序彼此隔離。例如，web瀏覽器不應該干擾文本編輯器。為了實現這個目標，操作系統利用硬體功能來確保一個進程的內存區域不被其他進程訪問。根據硬體和操作系統實現的不同，有不同的方法。

例如，一些ARM Cortex-M處理器(用於嵌入式系統)有一個內存保護單元(MPU)，它允許你定義少量具有不同訪問許可權(例如無訪問許可權、只讀限、寫入許可權)的內存區域。在每次內存訪問時，MPU都會確保該地址位於具有正確訪問許可權的區域，否則發出異常警報。通過更改每個進程切換(process switch)上的區域和訪問許可權，操作系統可以確保每個進程只訪問自己的內存，從而將進程彼此隔離。

在x86上，硬體支持兩種不同的內存保護方法：分段和分頁。

分段

分段技術早在1978年就已經被開發出來了，最初是為了增加可定址內存的數量。當時的情況是cpu只使用16位地址，這將可定址內存的數量限制為64KiB。為了使更多的64KiB可訪問，就需要引入額外的段寄存器，每個段寄存器包含一個偏移地址。CPU會在每次內存訪問時自動添加這個偏移量，以便可訪問高達1MiB的內存。

段寄存器由CPU根據內存訪問的類型自動選擇，比如獲取指令使用代碼段CS，而堆棧操作(push/pop)則使用堆棧段SS。其他指令使用數據段DS或額外段ES。後來，又增加了兩個可以自由使用的段寄存器FS和GS。

在第一版的分段技術中，段寄存器直接包含偏移量，不執行訪問控制。後來，隨著保護模式的引入，這種情況發生了改變。當CPU以此模式運行時，段描述符包含本地或全局描述符表的索引，該表除了包含偏移地址外，還包含段大小和訪問許可權。通過為每個進程載入單獨的全局或本地描述符表，將內存訪問限制在進程自己的內存區域，操作系統可以將進程彼此隔離。

通過在實際訪問之前修改內存地址，分段技術已經使用了一種幾乎無處不在的技術——虛擬內存。

虛擬內存

虛擬內存是計算機系統內存管理的一種技術。它使得應用程序認為它擁有連續的可用的內存（一個連續完整的地址空間），而實際上，它通常是被分隔成多個物理內存碎片，還有部分暫時存儲在外部磁碟存儲器上，在需要時進行數據交換。目前，大多數操作系統都使用了虛擬內存，如Windows家族的「虛擬內存」；Linux的「交換空間」等。

Windows 8/8.1 操作系統如出現開機時卡在Windows徽標頁面，無法進入系統，必須強制關機再重啟才能打開時，可適當調整虛擬內存設置解決。

歸根結底，虛擬內存背後的思想是從底層物理存儲設備抽象出內存地址。首先執行轉換步驟，而不是直接訪問存儲設備。對於分段來說，轉換步驟是添加活動段的偏移地址。假設一個程序在偏移量0x1111000的段中訪問內存地址0x1234000，則經過轉換，實際訪問的地址是0x2345000。

為了區分這兩種地址類型，轉換前的地址稱為虛擬地址，轉換後的地址稱為物理地址。這兩種地址的一個重要區別是，物理地址是惟一的，並且總是指向相同的、不同的內存位置。另一方面，虛擬地址依賴於轉換功能。所以很有可能，兩個不同的虛擬地址完全有可能指向同一個物理地址。同樣，相同的虛擬地址在使用不同的轉換功能時可以引用不同的物理地址。

如下所示，使用這個屬性的一個示例是，並行運行相同的程序兩次：

在這個示例中，相同的程序運行兩次，但卻使用了不同的轉換功能。第一個示例的段偏移量為100，因此它的虛擬地址0-150被轉換為物理地址100 - 250。第二個示例的段偏移量為300，因此它的虛擬地址0-150被轉換為物理地址300 - 450。這允許兩個程序運行相同的代碼並使用相同的虛擬地址，但不會相互干擾。

另一個優點是，程序現在可以放在任意物理內存位置，即使它們使用完全不同的虛擬地址。因此，操作系統可以利用全部可用內存而無需重新編譯程序。

內存碎片

內存分配有靜態分配和動態分配兩種， 靜態分配在程序編譯鏈接時分配的大小和使用壽命就已經確定，而應用上要求操作系統可以提供給進程運行時申請和釋放任意大小內存的功能，這就是內存的動態分配。

因此動態分配將不可避免會產生內存碎片的問題，那麼什麼是內存碎片？內存碎片即「碎片的內存」描述一個系統中所有不可用的空閑內存，這些碎片之所以不能被使用，是因為負責動態分配內存的分配演算法使得這些空閑的內存無法使用，這一問題的發生，原因在於這些空閑內存以小且不連續方式出現在不同的位置。因此這個問題的或大或小取決於內存管理演算法的實現上。

虛擬地址和物理地址的區別使得分段功能顯得異常強大，然而，分段卻存在著碎片化的問題。例如，假設我們想運行上面看到的程序的第三個副本：

即使有足夠多的空閑內存可用，也不可能不重疊地將程序的第三個示例映射到虛擬內存。問題是我們需要連續的內存，而不能使用小的空閑塊。

解決這種碎片問題的一種方法是暫停執行，將內存中已使用部分整合到起，更新轉換後，然後重新執行。

現在，就有足夠的連續空間來啟動程序的第三個示例了。

不過，這種碎片整理過程的缺點是需要複製大量內存，這會降低性能。在內存變得過於碎片化之前，還需要定期執行此操作。這使得性能變得不可預測，因為程序會在隨機時間暫停，並且可能變得無響應。

碎片問題是大多數系統不再使用分段的原因之一，實際上，x86上的64位模式甚至不再支持分段。而是使用分頁，這完全避免了碎片問題。

分頁

分頁的思想是將虛擬內存空間和物理內存空間都劃分為固定大小的小塊，此時虛擬內存空間的塊稱為頁，物理地址空間的塊稱為幀。每個頁面都可以單獨映射到一個幀，這使得在非連續物理幀之間，分割出更大的內存區域成為可能。

如果我們回顧一下碎片內存空間的示例，就會發現使用分頁的優勢。

在本文的示例中，我們有一個50位元組的頁面大小，這意味著我們的每個內存區域都被分為三個頁面。每個頁面都單獨映射到一個幀，因此連續的虛擬內存區域可以映射到非連續的物理幀，這允許我們在不執行任何碎片整理之前啟動程序的第三個示例。

隱藏的碎片

與分段相比，分頁會造成大量小的、固定大小的內存區域，而不像分段那樣，是一些大的、可變大小的區域。因為每個幀都有相同的大小，所以沒有太小而不能使用的幀，因此不會發生碎片。

表面上起來，是不會發生什麼碎片問題的。但其實還是有一些隱藏的碎片，也就是所謂的內部碎片。發生內部碎片是因為並非每個內存區域都是頁面大小的精確倍數。

內部碎片的產生：因為所有的內存分配必須起始於可被 4、8 或 16 整除（視處理器體系結構而定）的地址或者因為MMU的分頁機制的限制，決定內存分配演算法僅能把預定大小的內存塊分配給客戶。假設當某個客戶請求一個 43 位元組的內存塊時，因為沒有適合大小的內存，所以它可能會獲得 44位元組、48位元組等稍大一點的位元組，因此由所需大小四捨五入而產生的多餘空間就叫內部碎片。

內部碎片雖然無法避免，且仍然會浪費內存，但不需要進行碎片整理，並且可以預測碎片數量(每個內存區域平均有半頁)。

頁表

我們看到，每個潛在的數百萬個頁面都被單獨映射到一個幀，而這個映射信息需要存儲在某個地方。分段為每個活動的內存區域使用單獨的段選擇器寄存器。而分頁則是不可能實現這個的，因為頁面比寄存器多得多，分頁使用名為page table的表結構來存儲映射信息。

對於上面的示例，頁表應該是這樣的：

我們看到每個程序示例都有自己的頁表，指向當前活動表的指針存儲在一個特殊的CPU寄存器中。在x86上，這個寄存器稱為CR3。操作系統的任務是在運行每個程序示例之前，用指向正確頁表的指針載入該寄存器。

在每次內存訪問時，CPU從寄存器中讀取表指針，並在表中查找被訪問頁面的映射幀。這完全是在硬體中完成的，並且對運行中的程序完全透明。為了加快轉換過程，許多CPU架構都有一個特殊的緩存，它可以記住最後一次轉換的結果。

根據體系結構的不同，頁表條目還可以在標誌欄位中存儲訪問許可權等屬性。在上面的示例中，「r/w」標誌使頁面可讀又可寫。

多級頁表

我們剛才看到的簡單頁表在較大的地址空間中存在一個問題：浪費內存。例如，假設一個程序使用四個虛擬頁面0、1_000_000、1_000_050和1_000_100(我們使用_作為千位分隔符)。

它只需要4個物理幀，但是頁表有超過100萬個條目。我們不能省略空條目，因為這樣CPU就不能再直接跳轉到轉換過程中的正確條目，例如，不能再保證第四個頁面使用第四個條目。

為了減少內存的浪費，我們可以使用一個兩級頁表（ two-level page table），為不同的地址區域使用不同的頁表。另一個名為level 2 頁表的附加表則包含地址區域和(level 1)頁表之間的映射。

下面舉一個示例來解釋，讓我們定義每個1級頁表負責一個大小為10_000的區域。然後，上面的示例映射將存在以下表：

第0頁屬於第一個10_000位元組區域，因此它使用2級頁表的第一個條目。此條目指向1級頁表T1，指定頁0指向第0幀。

頁1_000_000、1_000_050和1_000_100都屬於第100個10_000位元組區域，因此它們使用2級頁表的第100個條目。該條目指向不同的1級頁表T2，該表將這三個頁面映射到幀100、150和200。注意，1級表中的頁地址不包括區域偏移量，因此，例如第1_000_050頁的條目僅為50。

現在，我們在2級表中仍然有100個空條目，但是比之前的100萬個空條目要少得多。其原因是，我們不需要為10_000到1_000_000之間的未映射內存區域創建1級頁表。

兩級頁表的原理可以擴展到三級，四級或更多級，然後頁表寄存器指向最高級別的表，該表指向下一個較低級別的表，依此類推。然後，1級頁表指向映射的幀，該原則一般稱為多級或分層頁表。

既然我們已經知道分頁和多級頁表是如何工作的，看一下如何在x86_64架構中實現分頁（我們假設CPU在64位模式下運行）。

本文我們對分段和分頁的優缺點進行了介紹後，還是決定用分頁技術對編寫操作系統。下篇文章，我會接著介紹分頁的具體使用過程和其中所遇到的問題。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！