目錄
1. 什麼是實體記憶體
2. 使用實體記憶體有什麼缺點？
3. 什麼是虛拟記憶體？
4. 虛拟記憶體如何映射到實體記憶體
5. 什麼是分頁記憶體管理？
6. 什麼是缺頁中斷？
7. 頁面置換算法都有哪些？
8. 什麼是分段記憶體管理？
01
什麼是實體記憶體？
我們常說的實體記憶體大小就是指記憶體條的大小，一般買電腦時都會看下記憶體條是多大容量的，話說如果記憶體條大小是100G，那這100G就都能夠被使用嗎？不一定的，更多的還是要看CPU位址總線的位數，如果位址總線隻有20位，那麼它的尋址空間就是1MB，即使可以安裝100G的記憶體條也沒有意義，也隻能視實體記憶體大小為1MB。
02
使用實體記憶體有什麼缺點？
這種方式下每個程式都可以直接通路實體記憶體，有兩種情況：
1.系統中隻有一個程序在運作：如果使用者程式可以操作實體位址空間的任意位址，它們就很容易在不經意間破壞了作業系統，使系統出現各種奇奇怪怪的問題；
2.系統有多個程序同時在運作：如圖，理想情況下可以使程序A和程序B各占實體記憶體的一邊，兩者互不幹擾，但這隻是理想情況下，誰能確定程式沒有bug呢，程序B在背景正常運作着，程式員在調試程序A時有可能就會誤操作到程序B正在使用的實體記憶體，導緻程序B運作出現異常，兩個程式操作了同一位址空間，第一個程式在某一位址空間寫入某個值，第二個程式在同一位址又寫入了不同值，這就會導緻程式運作出現問題，是以直接使用實體記憶體會使所有程序的安全性得不到保證。
如何解決上述問題？
可以考慮為存儲器創造新的抽象概念：位址空間，位址空間為程式創造了一種抽象的記憶體，是程序可用于尋址記憶體的一套位址集合，同時每個程序都有一套自己的位址空間，一個程序的位址空間獨立于其它程序的位址空間。
如何為程式創造獨立的位址空間？
最簡單的辦法就是把每個程序的位址空間分别映射到實體記憶體的不同部分。這樣就可以保證不同程序使用的是獨立的位址空間。
實作
給每個程序提供一個基址A和界限B，程序内使用的空間為x，則對應的實體位址為A + x，同時需要保證A + x < B，如果通路的位址超過的界限，需要産生錯誤并中止通路。為了達到目的CPU配置了兩個特殊硬體寄存器：基址寄存器和界限寄存器，當一個程序運作時，程式的起始實體位址和長度會分别裝入到基址寄存器和界限寄存器裡，程序通路記憶體，在每個記憶體位址送到記憶體之前，都會先加上基址寄存器的内容。
缺點：每次通路記憶體都需要進行加法和比較運算，比較運算很快，但是加法運算由于進位傳遞事件的問題，在沒有使用特殊電路的情況下會顯得很慢。
此外，每個程序運作都會占據一定的實體記憶體，如果實體記憶體足夠大到可以容納許多個程序同時運作還好，但現實中實體記憶體的大小是有限的，可能會出現記憶體不夠用的情況，怎麼辦？
方法一：如果是因為程式太大，大到超過了記憶體的容量，可以采用手動覆寫技術，隻把需要的指令和資料儲存在記憶體中。
方法二：如果是因為程式太多，導緻超過了記憶體的容量，可以采用自動交換技術，把暫時不需要執行的程式移動到外存中。
覆寫技術
把程式按照自身邏輯結構，劃分成多個功能互相獨立的程式子產品，那些不會同時執行的子產品可以共享到同一塊記憶體區域，按時間順序來運作：
将常用功能需要的代碼和資料常駐在記憶體中；
将不常用的功能劃分成功能互相獨立的程式子產品，平時放到外存中，在需要的時候将對應的子產品加載到記憶體中；
那些沒有調用關系的子產品平時不需要裝入到記憶體，它們可以共用一塊記憶體區，需要時加載到記憶體，不需要時換出到外存中；
如圖：
交換技術
多個程式同時運作，可以将暫時不能運作的程式送到外存，獲得更多的空閑記憶體，作業系統将一個程序的整個位址空間内容換出到外存中，再将外存中某個程序的整個位址空間資訊換入到記憶體中，換入換出内容的大小是整個程式的位址空間。
交換技術在實作上有很多困難：
需要确定什麼時候發生交換：簡單的辦法是可以在記憶體空間不夠用時換出一些程式；
交換區必須足夠大：多個程式運作時，交換區（外存）必須足夠大，大到可以存放所有程式所需要的位址空間資訊；
程式如何換入：一個程式被換出後又重新換入，換入的記憶體位置可能不會和上一次程式所在的記憶體位置相同，這就需要動态位址映射機制。
覆寫技術和交換技術的比較
覆寫隻能發生在那些互相之間沒有調用關系的程式子產品之間，是以程式員必須給出程式内的各個子產品之間的邏輯覆寫結構。
交換技術是以在記憶體中的程式大小為機關來進行的，它不需要程式員給出各個子產品之間的邏輯覆寫結構。
通俗來說：覆寫發生在程式的内部，交換發生在程式與程式之間。
但是這兩種技術都有缺點：
覆寫技術：需要程式員自己把整個程式劃分為若幹個小的功能子產品，并确定各個子產品之間的覆寫關系，增加了程式員的負擔，很少有程式員擅長這種技術；
交換技術：以程序作為交換的機關，需要把程序的整個位址空間都換進換出，增加了處理器的開銷，還需要足夠大的外存。
那有沒有更好的解決上述問題的方法呢？答案是虛拟記憶體技術。
03
什麼是虛拟記憶體？
虛拟記憶體，那就是虛拟出來的記憶體，它的基本思想就是確定每個程式擁有自己的位址空間，位址空間被分成多個塊，每一塊都有連續的位址空間，同時實體空間也分成多個塊，塊大小和虛拟位址空間的塊大小一緻，作業系統會自動将虛拟位址空間映射到實體位址空間，程式所關注的隻是虛拟記憶體，請求的也是虛拟記憶體，其實真正使用的是實體記憶體。
虛拟記憶體技術有覆寫技術的功能，但它不是把程式的所有内容都放在記憶體中，因而能夠運作比目前的空閑記憶體空間還要大的程式。它比覆寫技術做的更好，整個過程由作業系統自動來完成，無需程式員的幹涉；
虛拟記憶體技術有交換技術的功能，能夠實作程序在記憶體和外存之間的交換，因而獲得更多的空閑記憶體空間。它比交換技術做的更好，它隻對程序的部分内容在記憶體和外存之間進行交換。
虛拟記憶體技術的具體實作：
虛拟記憶體技術一般是在頁式管理（下面介紹）的基礎上實作
在裝入程式時，不必将其全部裝入到記憶體，而隻需将目前需要執行的部分頁面裝入到記憶體，就可讓程式開始執行；
在程式執行過程中，如果需執行的指令或通路的資料尚未在記憶體（稱為缺頁）。則由處理器通知作業系統将相應的頁面調入到記憶體，然後繼續執行程式；
另一方面，作業系統将記憶體中暫時不使用的頁面調出儲存在外存上，進而騰出更多空閑空間存放将要裝入的程式以及将要調入的頁面。
虛拟記憶體技術的特點：
大的使用者空間：通過把實體記憶體與外存相結合，提供給使用者的虛拟記憶體空間通常大于實際的實體記憶體，即實作了兩者的分離。如32位的虛拟位址理論上可以通路4GB，而可能計算機上僅有256M的實體記憶體，但硬碟容量大于4GB；
部分交換：與交換技術相比較，虛拟存儲的調入和調出是對部分虛拟位址空間進行的；
連續性：程式可以使用一系列相鄰連續的虛拟位址來映射實體記憶體中不連續的大記憶體緩沖區；
安全性：不同程序使用的虛拟位址彼此隔離。一個程序中的代碼無法更改正在由另一程序或作業系統使用的實體記憶體。
04
虛拟記憶體如何映射到實體記憶體？
如圖，CPU裡有一個記憶體管理單元（Memory Management Unit），簡稱MMU，虛拟記憶體不是直接送到記憶體總線，而是先給到MMU，由MMU來把虛拟位址映射到實體位址，程式隻需要管理虛拟記憶體就好，映射的邏輯自然有其它子產品自動處理。
作業系統如何表示的記憶體被占用還是空閑？
05
分頁記憶體管理
将虛拟位址空間分成若幹個塊，每個塊都有固定的大小，實體位址空間也被劃分成若幹個塊，每個塊也都有固定的大小，實體位址空間的塊和虛拟位址空間的塊大小相等，虛拟位址空間這些塊就被稱為頁面，實體位址空間這些塊被稱為幀。
關于分頁這裡有個問題，頁面的大小是多少合适呢？頁面太大容易産生空間浪費，程式假如隻使用了1個位元組卻被配置設定了10M的頁面，這豈不是極大的浪費，頁面太小會導緻頁表（下面介紹）占用空間過大，是以頁面需要折中選擇合适的大小，目前大多數系統都使用4KB作為頁的大小。
上面關于虛拟記憶體如何映射到實體記憶體程式喵隻介紹了MMU，但是MMU是如何工作的還沒有介紹，MMU通過頁表這個工具将虛拟位址轉換為實體位址。32位的虛拟位址分成兩部分（虛拟頁号和偏移量），MMU通過頁表找到了虛拟頁号對應的實體頁号，實體頁号+偏移量就是實際的實體位址。
具體如圖：
圖隻表示了頁表的大體功能，頁表的結構其實還很複雜，下面會具體介紹。
頁表的目的就是虛拟頁面映射為實體記憶體的頁框，頁表可以了解為一個數學函數，函數的輸入是虛拟頁号，函數的輸出是實體頁号，通過這個函數可以把虛拟頁面映射到實體頁号，進而确定實體位址。不同機器的頁表結構不同，通常頁表的結構如下：
頁框号：最主要的一項，頁表最主要的目的就是找到實體頁号；
有效位：1表示有效，表示該表項是有效的，如果為0，表示該表項對應的虛拟頁面現在不在記憶體中，通路該頁面會引起缺頁中斷，缺頁中斷後會去實體空間找到一個可用的頁框填回到頁表中；
保護位：表示一個頁允許什麼類型的通路，可讀可寫還是可執行；
修改位：該位反應了頁面的狀态，在作業系統重新配置設定頁框時有用，在寫入一頁時由硬體自動設定該位，重新配置設定頁框時，如果一個頁面已經被修改過，則必須把它這個髒頁寫回磁盤，如果沒有被修改過，表示該頁是幹淨的，它在磁盤上的副本依然是有效的，直接丢棄該頁面即可。
通路位：該位主要用于幫助作業系統在發生缺頁中斷時選擇要被淘汰的頁面，不再使用的頁面顯然比正在使用的頁面更适合被淘汰，該位在頁面置換算法中發揮重要作用。
高速緩存禁止位：該位用于禁止該頁面被高速緩存。
如何加快位址映射速度？
每次通路記憶體都需要進行虛拟位址到實體位址的映射，每次映射都需要通路一次頁表，所有的指令執行都必須通過記憶體，很多指令也需要通路記憶體中的操作數，是以每條指令執行基本都會進行多次頁表查詢，為了程式運作速度，指令必須要在很短的時間内執行完成，而頁表查詢映射不能成為指令執行的瓶頸，是以需要提高頁表查詢映射的速度。
如何才能提高速度呢？可以為頁表提供一個緩存，通過緩存進行映射比通過頁表映射速度更快，這個緩存是一個小型的硬體裝置，叫快表（TLB），MMU每次進行虛拟位址轉換時，首先去TLB中查找，找到了有效的實體頁框則直接傳回，如果沒有找到則進行正常的頁表通路，頁表中找到後則更新TLB，從TLB中淘汰一個表項，然後用新找到的表項替代它，這樣下次相同的頁面過來時可以直接命中TLB找到對應的實體位址，速度更快，不需要繼續去通路頁表。
這裡之是以認為TLB能提高速度主要依靠程式局部性原理，程式局部性原理是指程式在執行過程中的一個較短時間，所執行的指令位址和要通路的資料通常都局限在一塊區域内，這裡可分為時間局部性和空間局部性：
時間局部性：一條指令的一次執行和下次執行，一個資料的一次通路和下次通路都集中在一個較短時間内；
空間局部性：目前指令和鄰近的幾條指令，目前通路的資料和鄰近的幾個資料都集中在一個較小區域内。
關于程式局部性原理的詳細介紹和應用可以看我之前的文章：
《如何利用CPU Cache寫出高性能代碼，看這些圖就夠了！》
通過TLB可以加快虛拟位址到實體位址的轉換速度，還有個問題，現在都是64位作業系統啦，有很大的虛拟位址空間，虛拟位址空間大那對應的頁表也會非常大，又加上多個程序多個頁表，那計算機的大部分空間就都被拿去存放頁表，有沒有更好的辦法解決頁表大的問題呢？答案是多級頁表。
tips：頁表為什麼大？32位環境下，虛拟位址空間有4GB，一個頁大小是4KB，那麼整個頁表就需要100萬頁，而每個頁表項需要4個位元組，那整個頁表就需要4MB的記憶體空間，又因為每個程序都有一個自己的頁表，多個程序情況下，這簡直就是災難。
如圖，以一個32位虛拟位址的二級頁表為例，将32位虛拟位址劃分為10位的PT1域，10位的PT2域，以及12位的offset域，當一個虛拟位址被送入MMU時，MMU首先提取PT1域并把其值作為通路第一級頁表的索引，之後提取PT2域把把其值作為通路第二級頁表的索引，之後再根據offset找到對應的頁框号。
32位的虛拟位址空間下：每個頁面4KB，且每條頁表項占4B：
一級頁表：程序需要1M個頁表項（4GB / 4KB = 1M, 2^20個頁表項），即頁表（每個程序都有一個頁表）占用4MB（1M * 4B = 4MB）的記憶體空間。
二級頁表：一級頁表映射4MB（2^22）、二級頁表映射4KB，則需要1K個一級頁表項（4GB / 4MB = 1K, 2^10個一級頁表項）、每個一級頁表項對應1K個二級頁表項（4MB / 4KB = 1K），這樣頁表占用4.004MB（1K * 4B + 1K * 1K * 4B = 4.004MB）的記憶體空間。
二級頁表占用空間看着貌似變大了，為什麼還說多級頁表省記憶體呢？
每個程序都有4GB的虛拟位址空間，而顯然對于大多數程式來說，其使用到的空間遠未達到4GB，何必去映射不可能用到的空間呢？
也就是說，一級頁表覆寫了整個4GB虛拟位址空間，但如果某個一級頁表的頁表項沒有被用到，也就不需要建立這個頁表項對應的二級頁表了，即可以在需要時才建立二級頁表。做個簡單的計算，假設隻有20%的一級頁表項被用到了，那麼頁表占用的記憶體空間就隻有0.804MB（1K*4B+0.2*1K*1K*4B=0.804MB），對比單級頁表的4M是不是一個巨大的節約？
那麼為什麼不分級的頁表就做不到這樣節約記憶體呢？我們從頁表的性質來看，儲存在主存中的頁表承擔的職責是将虛拟位址翻譯成實體位址。假如虛拟位址在頁表中找不到對應的頁表項，計算機系統就不能工作了。是以頁表一定要覆寫全部虛拟位址空間，不分級的頁表就需要有1M個頁表項來映射，而二級頁表則最少隻需要1K個頁表項（此時一級頁表覆寫到了全部虛拟位址空間，二級頁表在需要時建立）。
二級頁表其實可以不在記憶體中：其實這就像是把頁表當成了頁面。當需要用到某個頁面時，将此頁面從磁盤調入到記憶體；當記憶體中頁面滿了時，将記憶體中的頁面調出到磁盤，這是利用到了程式運作的局部性原理。我們可以很自然發現，虛拟記憶體位址存在着局部性，那麼負責映射虛拟記憶體位址的頁表項當然也存在着局部性了！這樣我們再來看二級頁表，根據局部性原理，1024個第二級頁表中，隻會有很少的一部分在某一時刻正在使用，我們豈不是可以把二級頁表都放在磁盤中，在需要時才調入到記憶體？
我們考慮極端情況，隻有一級頁表在記憶體中，二級頁表僅有一個在記憶體中，其餘全在磁盤中（雖然這樣效率非常低），則此時頁表占用了8KB（1K*4B+1*1K*4B=8KB），對比上一步的0.804MB，占用空間又縮小了好多倍！（這裡參考的下面知乎連結中大佬的回答）
06 什麼是缺頁中斷？
缺頁中斷就是要通路的頁不在主存中，需要作業系統将頁調入主存後再進行通路，此時會暫時停止指令的執行，産生一個頁不存在的異常，對應的異常處理程式就會從選擇一頁調入到記憶體，調入記憶體後之前的異常指令就可以繼續執行。
缺頁中斷的處理過程如下：
- 如果記憶體中有空閑的實體頁面，則配置設定一實體頁幀r，然後轉第4步，否則轉第2步；
- 選擇某種頁面置換算法，選擇一個将被替換的實體頁幀r，它所對應的邏輯頁為q，如果該頁在記憶體期間被修改過，則需把它寫回到外存；
- 将q所對應的頁表項進行修改，把駐留位置0；
- 将需要通路的頁p裝入到實體頁面r中；
- 修改p所對應的頁表項的内容，把駐留位置1，把實體頁幀号置為x；
- 重新運作被中斷的指令。
07
頁面置換算法都有哪些？
當缺頁中斷發生時，需要調入新的頁面到記憶體中，而記憶體已滿時，選擇記憶體中哪個實體頁面被置換是個學問，由此引入了多種頁面置換算法，緻力于盡可能減少頁面的換入換出次數（缺頁中斷次數）。盡量把未來不再使用的或短期内較少使用的頁面換出，通常在程式局部性原理指導下依據過去的統計資料來進行預測。
最優頁面置換算法：當一個缺頁中斷發生時，對于儲存在記憶體當中的每一個邏輯頁面，計算在它的下一次通路之前，還需等待多長時間，從中選擇等待時間最長的那個，作為被置換的頁面。注意這隻是一種理想情況，在實際系統中是無法實作的，因為作業系統不可能預測未來，不知道每一個頁面要等待多長時間以後才會再次被通路。該算法可用作其它算法的性能評價的依據（在一個模拟器上運作某個程式，并記錄每一次的頁面通路情況，在第二遍運作時即可使用最優算法）。
先進先出算法：最先進入的頁面最先被淘汰，這種算法很簡單，就不過多介紹啦。
最近最久未使用算法：傳說中的LUR算法，當發生缺頁中斷時，選擇最近最久沒有使用過的頁面淘汰，該算法會給每個頁面一個字段，用于記錄自上次通路以來所經曆的時間T，當需要淘汰一個頁面時，選擇已有頁面中T值最大的頁面進行淘汰。
第二次機會頁面置換算法：先進先出算法的更新版，隻是在先進先出算法的基礎上做了一點點改動，因為先進先出算法可能會把經常使用的頁面置換出去，該方法會給這些頁面多一次機會，給頁面設定一個修改位R，每次淘汰最老頁面時，檢查最老頁面的R位，如果R位是0，那麼代表這個頁面又老又沒有被二次使用過，直接淘汰，如果這個頁面的R位是1，表示該頁面被二次通路過，将R位置0，并且把該頁面放到連結清單的尾端，像該頁面是最新進來的一樣，然後繼續按這種方法淘汰最老的頁面。
時鐘頁面置換算法：第二次機會頁面算法的更新版，盡管二次機會頁面算法是比較合理的算法，但它需要在連結清單中經常移動頁面，效率比較低，時鐘頁面置換算法如圖，該算法把所有的頁面都儲存在一個類似時鐘的環形連結清單中，一個表針指向最老的頁面，當發生缺頁中斷時，算法首先檢查表針指向的頁面，如果它的R位是0就淘汰該頁面，并且把新的頁面插入這個位置，然後表針移動到下一個位置，如果R位是1就将R位置0并把表針移動到下一個位置，重複這個過程直到找到一個R位是0的頁面然後淘汰。
時鐘頁面置換算法
最不常用算法：當發生缺頁中斷時，選擇通路次數最少的那個頁面去淘汰。該算法可以給每個頁面設定一個計數器，被通路時，該頁面的通路計數器+1，在需要淘汰時，選擇計數器值最小的那個頁面。
這裡有個問題：一個頁面如果在開始的時候通路次數很多，但之後就再也不用了，那它可能永遠都不會淘汰，但它又确實需要被淘汰，怎麼辦呢？可以定期把減少各個頁面計數器的值，常見的方法是定期将頁面計數器右移一位。
tips：最不常用算法（LFU）和最近最久未使用算法（LRU）的差別：LRU考察的是最久未通路，時間越短越好，而LFU考察的是通路的次數或頻度，通路次數越多越好。
工作集頁面置換算法
介紹該算法時首先介紹下什麼是工作集。
工作集是指一個程序目前正在使用的頁面的集合，可以用二進制函數W(t, s)表示：
t表示目前的執行時刻）s表示工作集視窗，表示一個固定的時間段
W(t, s)表示在目前時刻t之前的s時間段中所有通路頁面所組成的集合
不同時間下的工作集會有所變化，如圖：
程序開始執行後随着通路新頁面逐漸建立較穩定的工作集
當記憶體通路的局部性區域的位置大緻穩定時(隻通路那幾個頁面 沒有大的改變時) 工作集大小也大緻穩定
局部性區域的位置改變時(程序前一項事情做完 去做下一項事情時) 工作集快速擴張和快速收縮過渡到下一個穩定值
工作集置換算法主要就是換出不在工作集中的頁面，示例如圖：
- 第0次通路e：缺頁，裝入e
- 第1次通路d：缺頁，裝入d
- 第2次通路a：缺頁，裝入a
- 第3次通路c：缺頁，裝入c
- 第4次通路c：命中，時間視窗【1-4】，淘汰e
- 第5次通路d：命中，時間視窗【2-5】
- 第6次通路b：缺頁，時間視窗【3-6】，淘汰a，裝入b
- 第7次通路c：命中，時間視窗【4-7】
- 第8次通路e：缺頁，時間視窗【5-8】，裝入e
- 第9次通路c：命中，時間視窗【6-9】，淘汰d，裝入c
- 第10次通路e：命中，時間視窗【7-10】，淘汰b
- 第11次通路a：缺頁，時間視窗【8-11】，裝入a
- 第12次通路d：缺頁，時間視窗【9-12】，裝入d
工作集時鐘頁面置換算法
在工作集頁面置換算法中，當缺頁中斷發生後，需要掃描整個頁表才能直到頁面的狀态，進而才能确定被淘汰的是哪個頁面，是以比較耗時，是以引入了工作集時鐘頁面算法。與時鐘算法改進了先進先出算法類似，工作集頁面置換算法+時鐘算法=工作集時鐘頁面置換算法。避免了每次缺頁中斷都需要掃描整個頁表的開銷。
08
什麼是分段記憶體管理？
關于分段記憶體管理我們平時見的最多的應該就是Linux可執行程式的代碼段資料段之類的啦，要了解分段最好的方式就是了解它的曆史。分段起源于8086CPU，那時候程式通路記憶體還是直接給出相應單元的實體位址，為了友善多道程式并發執行，需要支援對各個程式進行重定位，如果不支援重定位，涉及到記憶體通路的地方都需要将位址寫死，進而把某個程式加載到實體記憶體的固定區間。通過分段機制，程式中隻需要使用段的相對位址，然後更改段的基址，就友善對程式進行重定位。而且8086CPU的位址線寬度是20位，可尋址範圍可以達到1MB，但是它們的寄存器都是16位，直接使用1個16位寄存器不可能訪存達到1MB，是以引入了段，引入了段寄存器，段寄存器左移4位+偏移量就可以生成20位的位址，進而達到1MB的尋址範圍。
以如今的科技水準，其實已經不再需要這種段移位加偏移的方式來訪存，分段更多的是一種曆史包袱，沒有多大實際作用，而且我們經常見到的可執行程式中代碼段資料段這些更多是為了在邏輯上能夠更清晰有序的構造程式的組織結構。Linux實際上沒有使用分段而隻使用了分頁管理，這樣會更加簡單，現在的分段其實更多是為了使邏輯更加清晰。一個公司，為了友善管理都會劃分為好多個部門，這其實和分段邏輯相似，沒有什麼實體意義但是邏輯更加清晰。