概述
程式都需要被加載到記憶體中才可以運作，在遠古時代^_^，程式的記憶體隻有非常非常小的幾kb，如果要運作的程式很大，大到超過了記憶體，而且還想要運作這樣的程式，要怎麼做呢？如果在記憶體中同時運作幾個程式，如何確定某個程式不會修改别的程式的記憶體中的值呢？以上的問題總結下來基本就三大核心問題：
- 程序之間如何隔離
- 記憶體使用低效的問題
- 程式位址空間重定向的問題
這些問題作業系統都已經解決了，下面就介紹一下作業系統是如何解決這些問題的。
虛拟位址空間
在遠古時期，作業系統和應用程式都直接根據實體位址來尋址，這樣如果應用程式在程式中把某個位址給惡意修改了，那作業系統很容就會被破壞，除了這個問題之外，多個應用程式同時運作也同樣具有這樣的問題，這個問題的根源就是程式所在記憶體空間沒有隔離，那記憶體就那一塊，采用實體隔離不太現實，是以隻能采用虛拟的方式，也就是虛拟位址空間。每個程序都有一份自己獨立的位址空間，這份位址空間（虛拟位址）可以相同，但是由于虛拟位址空間和實體位址空間的映射位置不同，故不會發生多個程序同時修改同一個實體位址的問題。
由于編寫程式時，通路資料和指令的位址很多是固定的（這段話來自《程式員的自我修養》，不是很明白），而程式裝載到記憶體中時的位置是不确定的，是以就需要程式重定向，采用虛拟位址可以很好的解決這個問題，因為虛拟位址空間就不存在重定位的問題。
采用虛拟位址基本解決了上面提到的第一個和第三個問題，但是第二個問題如何解決呢？且看下一章節。
分段
舉個例子，記憶體容量大小為256MB，程式A需要200MB，程式B需要50MB，程式C需要100MB，如果現在同時運作A和B，ok。如果這個時候C也想運作，有一個辦法是把記憶體中的A先儲存到磁盤上，然後就可以騰出來空間供程式C運作，但是這樣做非常低效，因為把一個200M的資料複制到磁盤還是很浪費時間的，那有沒有比較高效的方式，起初，計算機科學家是采用分段的方式來解決這個問題。
分段實作方法如下：
(圖檔來源：清華大學作業系統公開課)
從上圖可以看出，在邏輯位址空間，程式的堆、棧、程式資料等是連續的，而映射到實際的實體記憶體的時候并不連續，而是每個段是分開的，下面看一下實際的邏輯視圖。
（圖檔來源：清華大學作業系統公開課）
這個圖很清晰的可以看出來，左邊的額1，2，3，4表示邏輯空間的段，右邊是每個段在實體空間的實際存儲。
尋址方法
上面已經明白了分段的方式，那如何進行尋址呢？這裡介紹一種硬體尋址的方法。
（圖檔來源：清華大學作業系統公開課）
上圖的總過程先介紹一下，然後再對裡面的一些細節解釋一下。
CPU内部有一個記憶體管理單元叫做MMU，裡面儲存了經常被通路的段号，當需要通路某個段中的位址的時候，cpu先去MMU中尋找對應的段号，然後去記憶體的段表中查找目前段的最大長度，之後判斷需要尋找的位址在段中的偏移是否大于限制的大小，如果小于，ok，就直接把虛拟位址的位址值加上一個固定的偏移量，圖中是1000，就獲得實體位址的值了。如果需要通路的位址的偏移量大于段的限制長度，就抛出異常，因為通路到非法的位址。
相關概念解釋如下：
MMU：中文名是記憶體管理單元，有時稱作分頁記憶體管理單元（英語：paged memory management unit，縮寫為PMMU）。它是一種負責進行中央處理器（CPU）的記憶體通路請求的計算機硬體。
段表：一般存放在記憶體中，由作業系統維護，每個程序有一個獨立的段表，是一個二維結構，第一個次元為段号，第二個次元為段内偏移量，段号是每個段的辨別，段内偏移量是該段的長度。
邏輯位址：是虛拟的，實際上并不存在，程式運作使用的位址。
實體位址：實際實體記憶體的位址，邏輯位址會和實體位址存在一個映射關系。
總結
分段的方式，在傳統的架構中還有使用，現代計算機中基本已經沒有使用了，原因是這種方式分的粒度還是太大，比如，記憶體不足的時候，把某個分段拷貝到磁盤上，需要拷貝的量還是很高，效率太低，是以要進一步細分，也就有了分頁技術，這個分的粒度更低，一般來說每一頁隻有4kb。
分頁
分頁的基本方法是人為的把位址空間等分為大小相同的頁，現代的pc機基本都是使用4kb為一頁，實體空間一頁叫做頁幀，邏輯空間的頁就叫做頁，兩者大小相同，分頁的好處是，當要運作一個程式的時候，作業系統沒有必要把該程式的全部代碼和資料加載到記憶體中，而是把需要的頁放到記憶體中，随着程式的運作，可能會需要新的資料，記憶體中不存在，這個時候就從磁盤上把那些頁讀到記憶體中，如果記憶體空間不足，就把之前用過的頁先從記憶體中存到磁盤上，把這個空間騰出來，這樣就可以解決記憶體不足的問題，舉個例子，需要運作的程式所需的空間是1GB，而實際的記憶體隻有512MB，通過剛剛講的頁面置換的方法，就可以正常運作了。
上面簡要把整個過程叙述了一下，下面具體介紹一下。
頁幀
頁幀是指實體位址中的一頁。實體位址的表示方法是使用一個二進制組（f,o）,其中f表示頁号，o表示頁内偏移量，實體位址的計算方法為：2^S * f + o，S表示表示頁内偏移量所使用的計算機位數，由于一般每一頁的大小是4kb，也就是4096個位元組，是以需要212位來表示頁内偏移量。
（圖檔來源：清華大學作業系統公開課）
舉例如下：
（圖檔來源：清華大學作業系統公開課）
這個例子中，使用的是16位位址空間，其中每一頁的大小為512byte，并不是上面說的4kb，是以頁内偏移量就是512byte，對應的位也就是9位，因為2^9 = 512，是以S = 9，根據公式就很容易計算出來實際的實體位址。
頁
頁的位址計算方法和頁幀的相同，需要注意，頁号不一定等于頁幀号，但是頁内偏移量 = 頁幀内偏移量。
這裡表示方法中有點和幀不同，就是這裡的p，在幀中這裡使用f進行表示。
頁尋址方法
程式在運作的時候其實是已知虛拟位址的，那現在的問題就是如何根據虛拟位址找到實體位址，由于頁和頁幀的頁内偏移量相同，是以這個問題就變成了尋找虛拟位址的頁号和實體位址的頁号的映射關系，儲存這個映射關系的是頁表，下面先介紹一下頁表。
頁表
先看一個典型地頁表的結構
（圖檔來源：現代作業系統）
頁框号：其實就是上面說的頁幀号
在/不在位：表示該頁幀在實體記憶體中是否存在，如果不存在，當通路這一頁的時候，會抛出一個缺頁中斷，作業系統會處理。
保護位：其實就是我們說的權限，比如linux中權限分為讀、寫、執行，最簡單的表示方法就是隻有一位，那就隻能表示兩種狀态，比如，讀和寫。
通路位：無論作業系統通路改頁是讀還是寫，都會修改該位，這個位在後面介紹頁面置換算法時非常重要。
修改位：當頁面發生寫操作的時候，需要修改該位，因為一旦該頁被修改，就變成了髒頁，如果需要和磁盤上的頁發生置換，就需要先把該頁儲存到磁盤上，如果沒有修改，其實可以直接把該頁丢棄，把記憶體空間騰出來。
高速緩存禁止位：不太明白作用
（圖檔來源：清華大學作業系統公開課）
上圖基本把尋址的過程清楚的表達出來了，根據邏輯位址的p查找頁表，然後檢視标志位，圖中隻畫出來三個标志位，分别為dirty bit（修改位）= 0，resident bit（在不在位） = 1，clock/reference bit（通路位） = 0，由于在不在位為1表示該頁在實體位址中不存在，是以如果要通路該頁會抛出一個缺頁中斷。
上面把尋址的原理介紹完之後，接下來一個重要的問題就是效率問題，上面的方式cpu每次讀取一個位址的資料，需要通路記憶體兩次，第一次通路頁表查找實體位址的位置，第二次通路實體位址取資料，這種方式是效率很低的。除了需要兩次通路記憶體的問題，還有一個空間占用的問題，假設一個64位系統，每頁大小是4kb，也就是4096 = 2^12，那還剩餘52位，除去上面介紹的在不在位、通路位、修改位等，應該還會剩餘45位，也就是說會有2^45個頁，如果每個程式一個頁表，那可想而知會有多大，最起碼cpu是裝不下。
ok，問題介紹完了，下面就看解決方案，針對兩次通路記憶體的問題，采用使用TLB的方案解決，針對頁表過大的問題，采用多級頁表或者倒排頁表解決，下面就介紹一下每種解決方案的細節。
TLB
TLB(Translation Lookaside Buffer)轉換檢測緩沖區，是存在于MMU中的一種小型硬體裝置，可以将虛拟位址直接映射到實體位址，其中包含少量的表項（一項其實就是頁表的一條記錄），一般小于256條，如下圖所示。
（圖檔來源：現代作業系統）
尋址的過程是這樣的，cpu先去TLB查找，如果命中，就直接使用TLB中的實體位址，而不用再通路記憶體，如果沒有命中，就需要去記憶體中查找，然後把查找的結果放入TLB中，但是這是TLB是滿的，需要先從中剔除一條，剔除的這條并不能直接丢棄，需要把他的通路位和修改位更新到記憶體的頁表中。以上整個過程都是通過硬體完成的，除非通路頁的時候，發現在不在位不在，才需要作業系統介入，把對應的頁從磁盤讀到記憶體中。但是在有些硬體上TLB管理是作業系統完成的，在《現代作業系統》中有介紹，當TLB中的表項大到一定程度時（比如64個表項），TLB軟體管理就會變的足夠有效，這樣就可以獲得一個簡單的MMU，這就為CPU晶片上的高速緩存及其他改善性能的設計騰出空間。
多級頁表
多級頁表，有點類似于mysql資料庫Innodb引擎的索引結構，但是比索引結構使用B+樹簡單很多，使用多級頁表并不能減少通路的時間，反而因為分級之後，查詢次數變多，性能變差，但是這樣做卻可以節省空間，是一種時間換空間的思路，至于為什麼可以節省空間，看一下下面的例子就明白了了。
假設在32位系統中，一級頁表占用10位，也就是2^10 = 1024。由于2^32 = 4GB,是以一級頁表的每個表項負責整個記憶體的4M的空間，因為4M * 1024 = 4GB，二級頁表頁占用10位，那偏移量占用12位，也就是2^12位，也就是4kb，是以每頁的大小為4kb。具體看下圖。
圖檔來源：現代作業系統
在一級頁表中也會存在一個在不在位，如果一級頁表的在不在位為不存在，那就沒有必要搞一個二級頁表和這個表項相對應，這樣就可以節省很多空間，舉個例子，程式A運作代碼段占用空間4M，資料占用4M，4M的堆棧，那在一級頁表中隻有3個表項的在不在位為存在，隻有這三個有對應的二級頁表就可以了。這就是上面說這是一種以時間換空間的做法的原因。
細心的胖友可能會問，不使用多級頁表，隻使用一個頁表可不可以做到節省空間，答案是不能，看多級頁表的1級頁表就知道，即便是這個表項沒有被使用，也要存在，并且需要一個在不在位來辨別。
倒排頁表
這個思想很牛逼，但是實作很困難，為什麼說思想很牛逼，大家看上面的實作方式，邏輯空間是不受限制的，如果記憶體是4G，那邏輯空間的尋址就是4G，如果每個程序都這樣搞，那記憶體中為了給這個虛拟空間做映射建立的頁表才會占用很多的空間。那思路能不能反過來，通過實體位址來找邏輯位址，因為實體位址隻有4G，那頁表的大小可以很容易确定下來，而且邏輯位址的大小已經沒有意義，無論邏輯位址多大，最終一定會和實體位址映射，那就一定會落到實際的4G實體記憶體中。下面看一下如何實作。
實作方式有兩種，第一種是硬體的實作方案，沒看懂，這裡就不介紹了，介紹第二種，基于散清單（hash表）實作的。
看過java中的HashMap實作原理的都知道，HashMap就是使用散清單實作的，通過搞一個數組來确定桶的位置，之後在每個桶上挂一個連結清單，倒排頁表也是這個思路，計算每個程序邏輯位址的hash值，之後确定對應的桶的位置，然後挂到桶上，桶的長度就是分頁的個數，這裡多個程序的虛拟頁可能會映射到同一個實體頁框，發生hash沖突，發生沖突最大個數也就是一頁的大小。舉個例子32位系統，2^20表示頁面的個數，2^12 = 4kb，表示一頁的大小，總記憶體大小是4GB，那對應散清單的桶的個數就是2^20個，每個桶發生hash沖突的最大值為2^12。
圖檔來源：現代作業系統
圖中是用1GB記憶體來舉例的，2^18表示頁面的個數，也就是正常頁表的表項的個數，2^12表示一頁的大小。最左邊的圖就是前面介紹的正常的頁表，最右邊的就是散清單。
總結
本文主要介紹了作業系統記憶體管理，介紹了為什麼使用虛拟位址，使用虛拟位址之後如何進行尋址，以及如何優化尋址過程，本來打算把頁面置換算法一次性介紹完，但是覺得文章寫得太長，是以就下一篇介紹。
參考：
清華大學作業系統公開課
《現代作業系統》
《程式員的自我修養》