漫談操作系統的內存管理

存儲管理系統是操作系統中重要組成部分之一，它的目的是方便用戶使用和提高存儲器利用率。存儲管理的對象是主存儲器（簡稱內存或主存）。

內存是計算機中最重要的資源之一,一般情況下，物理內存是無法容納下所有的進程的。雖然物理內存的增長現在達到了好多個G，但比物理內存增長還快的是程序，而且無論物理內存如何增長，都趕不上程序增長的速度，所以操作系統如何有效的管理內存便顯得十分的重要。

1.1沒有內存抽象的年代

在沒有內存抽象的年代，早些的操作系統中，並沒有引入內存抽象的概念。程序直接訪問和操作的都是物理內存。不難想象，這種內存操作方式使得操作系統中存在多進程變得完全不可能，比如MS-DOS，你必須執行完一條指令后才能接著執行下一條。如果是多進程的話，由於直接操作物理內存地址，當一個進程給內存地址1000賦值后，另一個進程也同樣給內存地址賦值，那麼第二個進程對內存的賦值會覆蓋第一個進程所賦的值，這回造成兩條進程同時崩潰。沒有內存抽象對於內存的管理通常非常簡單，除去操作系統所用的內存之外，全部給用戶程序使用。或是在內存中多留一片區域給驅動程序使用。如圖1所示。

圖 1 沒有內存抽象時，對內存的使用

第一種情況操作系統存於RAM中，放在內存的低地址，第二種情況操作系統存在於ROM中，存在內存的高地址，一般老式的手機操作系統是這麼設計的。

如果這種情況下，想要操作系統可以執行多進程的話，唯一的解決方案就是和硬碟搞交換，當一個進程執行到一定程度時，整個存入硬碟，轉而執行其它進程，到需要執行這個進程時，再從硬碟中取回內存，只要同一時間內存中只有一個進程就行，這也就是所謂的交換（Swapping）技術。但這種技術由於還是直接操作物理內存，依然有可能引起進程的崩潰。

所以，通常來說，這種內存操作往往只存在於一些洗衣機，微波爐的晶元中，因為不可能有第二個進程去徵用內存。

1.2內存抽象

在現代的操作系統中，同一時間運行多個進程是再正常不過的了。為了解決直接操作內存帶來的各種問題，引入的地址空間(AddressSpace),這允許每個進程擁有自己的地址。這還需要硬體上存在兩個寄存器，基址寄存器(baseregister)和界址寄存器(limitregister),第一個寄存器保存進程的開始地址，第二個寄存器保存上界，防止內存溢出。

在內存抽象的情況下，當執行:mov reg1,20這時，實際操作的物理地址並不是20，而是根據基址和偏移量算出實際的物理地址進程操作，此時操作的實際地址可能是:movreg1,16245在這種情況下，任何操作虛擬地址的操作都會被轉換為操作物理地址。而每一個進程所擁有的內存地址是完全不同的，因此也使得多進程成為可能。

但此時還有一個問題，通常來說，內存大小不可能容納下所有併發執行的進程。因此，交換(Swapping)技術應運而生。這個交換和前面所講的交換大同小異,只是現在講的交換在多進程條件下。交換的基本思想是，將閑置的進程交換出內存，暫存在硬碟中，待執行時再交換回內存，比如下面一個例子，當程序一開始時，只有進程A，逐漸有了進程B和C，此時來了進程D，但內存中沒有足夠的空間給進程D，因此將進程B交換出內存，分給進程D。

圖 2交換技術

通過圖2，我們還發現一個問題，進程D和C之間的空間由於太小無法另任何進程使用，這也就是所謂的外部碎片。一種方法是通過緊湊技術(MemoryCompaction)解決，通過移動進程在內存中的地址，使得這些外部碎片空間被填滿。還有一些討巧的方法，比如內存整理軟體，原理是申請一塊超大的內存，將所有進程置換出內存，然後再釋放這塊內存，從而使得從新載入進程，使得外部碎片被消除。這也是為什麼運行完內存整理會狂讀硬碟的原因。另外，使用緊湊技術會非常消耗CPU資源，一個2G的CPU沒10ns可以處理4byte,因此多一個2G的內存進行一次緊湊可能需要好幾秒的CPU時間。

上面的理論都是基於進程所佔的內存空間是固定的這個假設，但實際情況下，進程往往會動態增長，因此創建進程時分配的內存就是個問題了，如果分配多了，會產生內部碎片，浪費了內存，而分配少了會造成內存溢出。一個解決方法是在進程創建的時候，比進程實際需要的多分配一點內存空間用於進程的增長。一種是直接多分配一點內存空間用於進程在內存中的增長，另一種是將增長區分為數據段和棧（用於存放返回地址和局部變數）,如圖3所示。

圖 3創建進程時預留空間用於增長

當預留的空間不夠滿足增長時，操作系統首先會看相鄰的內存是否空閑，如果空閑則自動分配，如果不空閑，就將整個進程移到足夠容納增長的空間內存中，如果不存在這樣的內存空間，則會將閑置的進程置換出去。

當允許進程動態增長時，操作系統必須對內存進行更有效的管理，操作系統使用如下兩種方法之一來得知內存的使用情況，分別為（1）點陣圖(bitmap)與（2）鏈表。

使用點陣圖，將內存劃為多個大小相等的塊，比如一個32K的內存1K一塊可以劃為32塊，則需要32位（4位元組）來表示其使用情況，使用點陣圖將已經使用的塊標為1，位使用的標為0.而使用鏈表，則將內存按使用或未使用分為多個段進行鏈接，這個概念如圖4所示。

圖 4點陣圖和鏈表表示內存的使用情況

使用鏈表中的P表示進程，從0-2是進程，H表示空閑，從3-4表示是空閑。使用點陣圖表示內存簡單明了，但一個問題是當分配內存時必須在內存中搜索大量的連續0的空間，這是十分消耗資源的操作。相比之下，使用鏈表進行此操作將會更勝一籌。還有一些操作系統會使用雙向鏈表，因為當進程銷毀時，鄰接的往往是空內存或是另外的進程。使用雙向鏈表使得鏈表之間的融合變得更加容易。

還有，當利用鏈表管理內存的情況下，創建進程時分配什麼樣的空閑空間也是個問題。通常情況下有如下幾種演算法來對進程創建時的空間進行分配。

• 臨近適應演算法---從當前位置開始，搜索第一個能滿足進程要求的內存空間

• 最佳適應演算法---搜索整個鏈表，找到能滿足進程要求最小內存的內存空間

• 最大適應演算法---找到當前內存中最大的空閑空間

• 首次適應演算法---從鏈表的第一個開始，找到第一個能滿足進程要求的內存空間

  

1.3虛擬內存(Virtual Memory)

虛擬內存是現代操作系統普遍使用的一種技術。前面所講的抽象滿足了多進程的要求，但很多情況下，現有內存無法滿足僅僅一個大進程的內存要求(比如很多遊戲，都是10G+的級別)。在早期的操作系統曾使用覆蓋(overlays)來解決這個問題，將一個程序分為多個塊，基本思想是先將塊0加入內存，塊0執行完后，將塊1加入內存。依次往複，這個解決方案最大的問題是需要程序員去程序進行分塊，這是一個費時費力讓人痛苦不堪的過程。後來這個解決方案的修正版就是虛擬內存。

虛擬內存別稱虛擬存儲器（VirtualMemory）。電腦中所運行的程序均需經由內存執行，若執行的程序佔用內存很大或很多，則會導致內存消耗殆盡。為解決該問題，Windows中運用了虛擬內存技術。當內存耗盡時，電腦就會自動調用硬碟來充當內存，以緩解內存的緊張。若計算機運行程序或操作所需的隨機存儲器(RAM)不足時，則Windows會用虛擬存儲器進行補償。它將計算機的RAM和硬碟上的臨時空間組合。當RAM運行速率緩慢時，它便將數據從RAM移動到稱為「分頁文件」的空間中。將數據移入分頁文件可釋放RAM，以便完成工作。一般而言，計算機的RAM容量越大，程序運行得越快。若計算機的速率由於RAM可用空間匱乏而減緩，則可嘗試通過增加虛擬內存來進行補償。

虛擬內存的基本思想是，每個進程有用獨立的邏輯地址空間，內存被分為大小相等的多個塊,稱為頁(Page).每個頁都是一段連續的地址。對於進程來看,邏輯上貌似有很多內存空間，其中一部分對應物理內存上的一塊(稱為頁框，通常頁和頁框大小相等)，還有一些沒載入在內存中的對應在硬碟上，如圖5所示。

圖 5虛擬內存和物理內存以及磁碟的映射關係

由圖5可以看出，虛擬內存實際上可以比物理內存大。當訪問虛擬內存時，會訪問MMU（內存管理單元）去匹配對應的物理地址（比如圖5的0，1，2），而如果虛擬內存的頁並不存在於物理內存中（如圖5的3,4），會產生缺頁中斷，從磁碟中取得缺的頁放入內存，如果內存已滿，還會根據某種演算法將磁碟中的頁換出。而虛擬內存和物理內存的匹配是通過頁表實現，頁表存在MMU中，頁表中每個項通常為32位，既4byte,除了存儲虛擬地址和頁框地址之外，還會存儲一些標誌位，比如是否缺頁，是否修改過，防寫等。可以把MMU想象成一個接收虛擬地址項返回物理地址的方法。

因為頁表中每個條目是4位元組，現在的32位操作系統虛擬地址空間會是2的32次方，即使每頁分為4K，也需要2的20次方*4位元組=4M的空間，為每個進程建立一個4M的頁表並不明智。因此在頁表的概念上進行推廣，產生二級頁表,二級頁表每個對應4M的虛擬地址，而一級頁表去索引這些二級頁表，因此32位的系統需要1024個二級頁表，雖然頁表條目沒有減少，但內存中可以僅僅存放需要使用的二級頁表和一級頁表，大大減少了內存的使用。

1.4頁面替換演算法

因為在計算機系統中，讀取少量數據硬碟通常需要幾毫秒，而內存中僅僅需要幾納秒。一條CPU指令也通常是幾納秒，如果在執行CPU指令時，產生幾次缺頁中斷，那性能可想而知，因此盡量減少從硬碟的讀取無疑是大大的提升了性能。而前面知道，物理內存是極其有限的，當虛擬內存所求的頁不在物理內存中時，將需要將物理內存中的頁替換出去，選擇哪些頁替換出去就顯得尤為重要，如果演算法不好將未來需要使用的頁替換出去，則以後使用時還需要替換進來，這無疑是降低效率的，讓我們來看幾種頁面替換演算法。

Ø最佳置換演算法(Optimal Page ReplacementAlgorithm)

最佳置換演算法是由Belady於1966年提出的一種理論上的演算法。其所選擇的被淘汰頁面將是以後永不使用的，或許是在最長(未來)時間內不再被訪問的頁面。採用最佳置換演算法通常可保證獲得最低的缺頁率。但由於人們目前還無法預知，一個進程在內存的若干個頁面中，哪一個頁面是未來最長時間內不再被訪問的，因而該演算法是無法實現的，但可以利用該演算法去評價其它演算法。

Ø最近不常使用演算法(Not Recently Used ReplacementAlgorithm)

這種演算法給每個頁一個標誌位，R表示最近被訪問過，M表示被修改過。定期對R進行清零。這個演算法的思路是首先淘汰那些未被訪問過R=0的頁，其次是被訪問過R=1,未被修改過M=0的頁，最後是R=1,M=1的頁。

　FIFO置換演算法的性能之所以較差，是因為它所依據的條件是各個頁面調入內存的時間，而頁面調入的先後並不能反映頁面的使用情況。最近最久未使用(LRU)的頁面置換演算法是根據頁面調入內存后的使用情況做出決策的。

Ø先進先出頁面置換演算法(First-In,First-Out Page ReplacementAlgorithm)

FIFO演算法是最早出現的置換演算法。該演算法總是淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面予以淘汰。該演算法實現簡單，只需把一個進程已調入內存的頁面按先後次序鏈接成一個隊列，並設置一個指針，稱為替換指針，使它總是指向最老的頁面。但該演算法與進程實際運行的規律不相適應，因為在進程中，有些頁面經常被訪問，比如，含有全局變數、常用函數、常式等的頁面，FIFO演算法並不能保證這些頁面不被淘汰。

Ø改進型FIFO演算法(Second Chance Page ReplacementAlgorithm)

這種演算法是在FIFO的基礎上，為了避免置換出經常使用的頁，增加一個標誌位R，如果最近使用過將R置1，當頁將會淘汰時，如果R為1，則不淘汰頁，將R置0.而那些R=0的頁將被淘汰時，直接淘汰。這種演算法避免了經常被使用的頁被淘汰。

Ø時鐘替換演算法(Clock Page Replacement Algorithm)

雖然改進型FIFO演算法避免置換出常用的頁，但由於需要經常移動頁，效率並不高。因此在改進型FIFO演算法的基礎上，將隊列首位相連形成一個環路，當缺頁中斷產生時，從當前位置開始找R=0的頁，而所經過的R=1的頁被置0，並不需要移動頁。如圖6所示。

圖6時鐘置換演算法

Ø最久未使用演算法(LRU Page Replacement Algorithm)

LRU演算法的思路是淘汰最近最長未使用的頁。這種演算法性能比較好，但實現起來比較困難。

表格 1演算法的簡單比較

上面幾種演算法或多或少有一些局部性原理的思想。局部性原理分為時間和空間上的局部性

1，時間上，最近被訪問的頁在不久的將來還會被訪問。

2，空間上，內存中被訪問的頁周圍的頁也很可能被訪問。

總之，虛擬存儲器作為現代操作系統中存儲器管理的一項重要技術，實現了內存擴充功能。但該功能並非是從物理上實際的擴大內存的容量，而是從邏輯上實現對內存容量的擴充，讓用戶所感覺到的內存容量比實際的內存容量大的多。於是便可以讓比內存空間更大的程序運行，或者讓更多的用戶程序併發運行，這樣既可以滿足了用戶的需求，改善了系統的性能。

需要滿足的功能有：

（1）為應用程序分配內存空間；

（2）檢測內存的使用情況；

（3）顯示每個虛擬內存區域的特性；

（4）內存區域的保護；

（5）內存空間的回收。

文章參考自cnblogs宋沄劍

如果喜歡的話，歡迎大家關注，感謝大家的支持，小編會繼續努力推出更好的文章~~