C++應(yīng)用程序性能優(yōu)化（五）——操作系統(tǒng)的內(nèi)存管理

C++應(yīng)用程序性能優(yōu)化（五）——操作系統(tǒng)的內(nèi)存管理

一、操作系統(tǒng)內(nèi)存管理簡介

長期以來，在計算機系統(tǒng)中，內(nèi)存都是一種緊缺和寶貴的資源，應(yīng)用程序必須在載入內(nèi)存后才能執(zhí)行。早期，在內(nèi)存空間不夠大時，同時運行的應(yīng)用程序的數(shù)量會受到很大的限制，甚至當某個應(yīng)用程序在某個運行時所需內(nèi)存超過物理內(nèi)存時，應(yīng)用程序就會無法運行。現(xiàn)代操作系統(tǒng)（Windows、Linux）通過引入虛擬內(nèi)存進行內(nèi)存管理，解決了應(yīng)用程序在內(nèi)存不足時不能運行的問題。
本質(zhì)上，虛擬內(nèi)存就是要讓一個程序的代碼和數(shù)據(jù)在沒有全部載入內(nèi)存時即可運行。運行過程中，當執(zhí)行到尚未載入內(nèi)存的代碼，或者要訪問還沒有載入到內(nèi)存的數(shù)據(jù)時，虛擬內(nèi)存管理器動態(tài)地將相應(yīng)的代碼或數(shù)據(jù)從硬盤載入到內(nèi)存中。而且在通常情況下，虛擬內(nèi)存管理器也會相應(yīng)地先將內(nèi)存中某些代碼或數(shù)據(jù)置換到硬盤中，為即將載入的代碼或數(shù)據(jù)騰出空間。
因為內(nèi)存和硬盤間的數(shù)據(jù)傳輸相對于代碼執(zhí)行非常慢，因此虛擬內(nèi)存管理器在保證工作正確的前提下還必須考慮效率因素，如需要優(yōu)化置換算法，盡量避免將要被執(zhí)行的代碼或訪問的數(shù)據(jù)剛被置換出內(nèi)存，而很久沒有訪問的代碼或數(shù)據(jù)卻一直駐留在內(nèi)存中。虛擬內(nèi)存管理器還需要將駐留在內(nèi)存中的各個進程的代碼數(shù)據(jù)維持在一個合理的數(shù)量上，并且根據(jù)進程性能的表現(xiàn)動態(tài)調(diào)整，使得程序運行時將涉及的磁盤IO次數(shù)降到盡可能低，以提高程序的運行性能。

二、Windows內(nèi)存管理

1、Windows虛擬內(nèi)存管理系統(tǒng)簡介

Win32虛擬內(nèi)存管理器為每一個Win32進程提供了進程私有并且基于頁的4GB（32bit）大小的線性虛擬地址空間。
進程私有即每個進程只能訪問屬于自己的內(nèi)存空間，而無法訪問屬于其它進程的地址空間，也不用擔心自己的地址空間被其它進程看到（父子進程例外，比如調(diào)試器利用父子進程關(guān)系來訪問被被調(diào)試進程的地址空間）。進程運行時用到的dll并沒有屬于自己的地址空間，而是其所屬進程的虛擬地址空間，dll的全局數(shù)據(jù)，以及通過dll函數(shù)申請的內(nèi)存都是從調(diào)用其進程的虛擬地址空間開辟的。
基于頁是指虛擬地址空間被劃分為多個稱為頁的單元，頁的大小由底層處理器決定，x86架構(gòu)處理器中頁的大小為4KB。頁是Win32虛擬內(nèi)存管理器處理的最小單元，相應(yīng)的物理內(nèi)存也被劃分為多個頁。虛擬內(nèi)存地址空間的申請和釋放，以及內(nèi)存和磁盤的數(shù)據(jù)傳輸或置換都是以頁為最小單位進行的。
4GB大小意味著進程中的地址取值范圍可以從0x00000000到0xFFFFFFFF，Win32將低區(qū)的2GB留給進程使用，高區(qū)的2GB留給系統(tǒng)使用。
Win32中用來輔助實現(xiàn)虛擬內(nèi)存的硬盤文件稱為調(diào)頁文件，可以有16個，調(diào)頁文件用來存放被虛擬內(nèi)存管理器置換出內(nèi)存的數(shù)據(jù)。當調(diào)頁文件的數(shù)據(jù)再次被進程訪問時，虛擬內(nèi)存管理器會將其從調(diào)頁文件中置換進內(nèi)存，進程可以正確對其訪問。用戶可以自己配置調(diào)頁文件，出于空間利用效率和性能的考慮，程序代碼不會被修改（包括exe和dll），所以當其所在頁被置換出內(nèi)存時，并不會被寫進調(diào)頁文件中，而是直接拋棄。當再次被需要時，虛擬內(nèi)存管理器直接從存放程序代碼的exe或dll文件中找到并調(diào)入內(nèi)存。另外，對exe和dll文件中包含的只讀數(shù)據(jù)的處理與程序代碼處理相同，不會在調(diào)頁文件中開辟空間存儲。
當進程執(zhí)行某段代碼或訪問某些數(shù)據(jù)，而代碼或數(shù)據(jù)還不在內(nèi)存中時，稱為缺頁錯誤。缺頁錯誤的原因很多，最常見的是代碼和數(shù)據(jù)被虛擬內(nèi)存管理器置換出內(nèi)存，虛擬內(nèi)存管理器會在代碼被執(zhí)行或數(shù)據(jù)被訪問前將其調(diào)入內(nèi)存。內(nèi)存置換對開發(fā)人員來說是透明的，大大簡化了開發(fā)人員的工作。但調(diào)頁錯誤涉及磁盤IO，大量的調(diào)頁錯誤會大大降低程序的總體性能，因此需要了解缺頁錯誤的主要原因和規(guī)避方法。

2、使用虛擬內(nèi)存

Win32中分配內(nèi)存分為兩個步驟，預留和提交。因此在進程虛擬地址空間中的頁有三種狀態(tài)：自由free、預留reserved和提交committed。
自由表示此頁尚未被分配，可以用來滿足新的內(nèi)存分配請求。
預留是指從虛擬地址空間劃出一塊區(qū)域（region，頁的整數(shù)倍），劃出后的內(nèi)存空間不能用來滿足新的內(nèi)存分配請求，而是用來供要求預留此段內(nèi)存的代碼以后使用。預留時并沒有分配物理內(nèi)存，只是增加了一個描述進程虛擬地址空間使用狀態(tài)的數(shù)據(jù)結(jié)構(gòu)（VAD，虛擬地址描述符），用來記錄此段內(nèi)存空間已經(jīng)被預留。預留操作相對較快，因為沒有真正分配物理內(nèi)存，因此預留的空間不能夠直接訪問，對預留頁的訪問會引起內(nèi)存訪問違例。
提交，如果想要得到真正的物理內(nèi)存，必須對預留的內(nèi)存進行提交。提交會從調(diào)頁文件中開辟空間，并修改VAD中的相應(yīng)項。提交時也并沒有立刻從物理內(nèi)存中分配空間，而是從磁盤的調(diào)頁文件中開辟空間，作為置換的備份空間。當代碼第一次訪問提交內(nèi)存中的數(shù)據(jù)時，系統(tǒng)發(fā)現(xiàn)并沒由真正的物理內(nèi)存，拋出缺頁操作。虛擬內(nèi)存管理器會處理缺頁錯誤，直到此時才會真正分配物理內(nèi)存，提交也可以在預留的同時進行。提交操作會從磁盤的調(diào)頁文件中開辟空間，所以比預留操作耗時。
Win32虛擬內(nèi)存管理中demand-paging策略要求不到真正訪問時不會為某虛擬地址分配真正的物理內(nèi)存。demand-paging策略一是處于性能考慮，將工作分段完成，提高總體性能；二是出于空間效率考慮，不到真正訪問時，Win32總是假定認為進程不會訪問大多數(shù)數(shù)據(jù)，因而不必要為其開辟存儲空間或?qū)⑵渲脫Q進物理內(nèi)存，以提高存儲空間的利用率。
如果某些程序?qū)?nèi)存有很大的需求，但并不是立刻需要所有內(nèi)存，則一次性從物理存儲中開辟空間滿足潛在的需求，從執(zhí)行性能和存儲空間效率上是一種浪費。由于需求只是潛在的，極有可能分配的內(nèi)存中很大一部分最后都沒有被真正利用。如果在申請時一次性為其分配所有物理存儲，會極大降低空間的利用率。
但如果完全不用預留和提交機制，只是隨需分配內(nèi)存來滿足每次的請求，則對一個會在不同時間點頻繁請求內(nèi)存的代碼來說，因為在其請求內(nèi)存的不同時間點的間隙極有可能會由其它代碼請求內(nèi)存，會導致在不同時間點頻繁請求內(nèi)存的代碼得到的內(nèi)存因為虛擬地址不連續(xù)，無法很好利用空間的locality特性，對其整體進行訪問（如遍歷）時就會增加缺頁錯誤的數(shù)量，從而降低程序性能。
預留和提交在Win32程序中都使用VirtualAlloc函數(shù)完成，預留傳入MEM_RESERVE參數(shù)，提交傳入MEM_COMMIT參數(shù)。釋放虛擬內(nèi)存時使用VirtualFree函數(shù)，根據(jù)不同的傳入?yún)?shù)，與VirtualAlloc函數(shù)對應(yīng)，可以釋放與虛擬地址區(qū)域相對應(yīng)的物理內(nèi)存，但虛擬地址區(qū)域還可以處于預留狀態(tài)，也可以連同虛擬地址區(qū)域一同釋放，則虛擬地址區(qū)域恢復為自由狀態(tài)。
線程棧和進程堆的實現(xiàn)利用了預留和提交兩步機制，Win32系統(tǒng)中，線程棧使用預留和提交兩步機制如下：
創(chuàng)建線程棧時，只是預留一個虛擬的地址區(qū)域，默認為1M（可以在CreateThread或鏈接時通過鏈接選項修改），初始時只有前兩頁是提交的。當線程棧因為函數(shù)的嵌套調(diào)用需要更多的提交頁時，虛擬內(nèi)存管理器會動態(tài)地提交線程的虛擬地址區(qū)域中的后續(xù)頁以滿足其需求，直到到達1M的上限。當?shù)竭_預留區(qū)域大小的上限（默認1M）時，虛擬內(nèi)存管理器不會增加預留區(qū)域的大小，而是在提交最后一頁時拋出一個棧溢出異常，拋出棧溢出異常時線程棧還有一頁空間可以利用，程序仍可正常運行。當程序繼續(xù)使用棧空間，用完最后一頁時，還繼續(xù)需要存儲空間，此時超過上限，會直接導致進程退出。
為了防止線程棧溢出導致整個程序退出，應(yīng)該盡量控制棧的使用大小。比如減少函數(shù)的嵌套層數(shù)，減少遞歸函數(shù)的使用，盡量不要在函數(shù)中使用較大的局部變量（大的對象可以從堆中開辟空間存放，因為堆會動態(tài)擴大，而線程棧的可用內(nèi)存區(qū)域在線程創(chuàng)建時已經(jīng)固定，在線程的整個生命期都無法擴展）。
為了防止一個線程棧的溢出導致整個程序退出，可以對可能產(chǎn)生線程棧溢出的線程體函數(shù)加異常處理，捕獲在提交最后一頁時拋出的溢出異常，并做相應(yīng)處理。

3、訪問虛擬內(nèi)存時的處理流程

對某虛擬內(nèi)存區(qū)域進行了預留并提交后，就可以對虛擬內(nèi)存區(qū)域中數(shù)據(jù)進行訪問。當程序?qū)δ扯蝺?nèi)存訪問時處理流程如下：

如果數(shù)據(jù)已經(jīng)在物理內(nèi)存中，虛擬地址管理器只需要將指向數(shù)據(jù)的虛擬內(nèi)存地址映射為物理地址，即可訪問到物理內(nèi)存中的數(shù)據(jù)。此時不會涉及磁盤IO，速度較快。
當?shù)谝淮卧L問一段剛剛提交的內(nèi)存中的數(shù)據(jù)時，因為并沒有真正的物理內(nèi)存分配，或者被訪問數(shù)據(jù)以前已經(jīng)被訪問過，但已經(jīng)被虛擬內(nèi)存管理器置換出物理內(nèi)存，此時會觸發(fā)缺頁錯誤。虛擬內(nèi)存管理器會處理缺頁錯誤，虛擬內(nèi)存管理器會先檢測數(shù)據(jù)是否在調(diào)頁文件中已有備份空間（exe、dll的代碼頁和只讀數(shù)據(jù)的備份空間不在調(diào)頁文件，而是exe、dll文件），如果訪問的數(shù)據(jù)在磁盤有備份空間，虛擬內(nèi)存管理器需要在物理內(nèi)存中找到合適的頁，并將存放在磁盤的備份數(shù)據(jù)置換進物理內(nèi)存。
虛擬內(nèi)存管理器首先查詢當前物理內(nèi)存中是否有空閑頁，虛擬內(nèi)存管理器維護一個名稱為頁幀數(shù)據(jù)庫（page-frame database）的數(shù)據(jù)結(jié)構(gòu)，此數(shù)據(jù)結(jié)構(gòu)是操作系統(tǒng)全局的，當Windows系統(tǒng)啟動時被初始化，用來跟蹤和記錄物理內(nèi)存中每一個頁的狀態(tài)，并用一個鏈表將所有空閑頁連接起來，當需要空閑頁時，直接查找此空閑頁鏈表，如果有，直接使用某個空閑頁；否則，根據(jù)調(diào)頁算法首先選出某個頁。虛擬內(nèi)存管理器調(diào)頁時并不是只調(diào)入一個頁，為了利用局部特性，在調(diào)入包含所需數(shù)據(jù)頁的同時，會將相鄰的幾個頁一起調(diào)入內(nèi)存，以提高程序效率。在選出某個內(nèi)存頁后，接著檢查此頁狀態(tài)，如果此頁自上次調(diào)入內(nèi)存以來尚未被修改，則直接使用此頁（代碼頁和只讀頁也可以直接使用）。如果此頁已經(jīng)被修改，則需要先將此頁的內(nèi)容寫到磁盤的調(diào)頁文件中相應(yīng)的備份頁，并隨即將此頁標記為空閑頁。此時已經(jīng)有一個空閑頁用來存放即將要訪問的數(shù)據(jù)。虛擬內(nèi)存管理器會再次檢測，此數(shù)據(jù)是否剛被申請的內(nèi)存并且第一次被訪問，如果是直接將此空閑頁清0使用即可，不必從磁盤的調(diào)頁文件中讀取相應(yīng)備份頁；如果不是，則需要將磁盤調(diào)頁文件中相應(yīng)的備份頁讀到此空閑空間中，并隨即將此頁狀態(tài)從空閑頁改為活動頁。
此時，數(shù)據(jù)已經(jīng)在物理內(nèi)存頁中，通過虛擬地址映射到物理地址即可訪問數(shù)據(jù)。
實際的數(shù)據(jù)訪問中，情形會比較復雜，比如當用戶定義了一個數(shù)組，而此數(shù)組剛好在其所在頁的下邊界，且此頁的下一頁是自由或者預留狀態(tài)（非提交，沒有真正的物理內(nèi)存）。當程序不小心向下越界訪問此數(shù)組，則首先引發(fā)缺頁錯誤。隨即虛擬內(nèi)存管理器在處理缺頁錯誤時檢測到其不在調(diào)頁文件中，即所謂的訪問違例（access violation）。訪問違例意味著要訪問的地址所在的虛擬內(nèi)存地址還沒有被提交，即沒有實際的物理存儲地址與虛擬內(nèi)存地址對應(yīng)，訪問違例會直接導致整個進程退出（crash）。
指針越界訪問的后果根據(jù)運行時實際情況而有所不同，當數(shù)組并非處于其所在頁的邊界時，越界后還在同一頁中，此時只會引起誤訪問（誤讀或誤寫，誤讀只會影響到正在執(zhí)行的代碼，誤寫則會影響其它處代碼的執(zhí)行），本頁中的其它數(shù)據(jù)，而不會導致整個進程crash。即使數(shù)組真的存在于所在頁的邊界，且越界后指針值落在其相鄰頁，但如果此相鄰頁也為提交狀態(tài)，此時仍然為誤訪問，也不會導致進程的crash。因此，同一程序的代碼中存在數(shù)組指針訪問越界錯誤，運行時有時會crash，有時不會。
MicroSoft提供了一個檢測指針越界訪問的工具pageheap，原理是強制使每次分配的內(nèi)存都位于頁的邊界，同時強制頁的相鄰頁為自由頁，此時每次越界訪問都會引起訪問違例，導致程序crash，從而使得指針越界訪問錯誤在開發(fā)階段一定會暴露出來，而不會發(fā)生某個指針越界訪問錯誤一直隱藏到發(fā)布版本，直到最終用戶訪問時才會被發(fā)現(xiàn)。

4、虛擬地址到物理地址的映射

在確保訪問的數(shù)據(jù)已經(jīng)在物理內(nèi)存中后，還需要先將虛擬地址轉(zhuǎn)換為物理地址，即地址映射，才能訪問數(shù)據(jù)。
Win32通過一個兩層表結(jié)構(gòu)來實現(xiàn)地址映射，因為4GB虛擬地址空間為每個進程私有，每個進程都維護一套自己的層次結(jié)構(gòu)用來實現(xiàn)其地址映射。第一層表為頁目錄（page directory），實際就是一個內(nèi)存頁（4KB=4096Byte），以4個字節(jié)為單元分為1024項，每一項稱為頁目錄項（PDE，page directory entry）；第二層表為頁表（page table），共有1024個頁表。頁目錄中每一個頁目錄項對應(yīng)一個頁表，每一個頁表也占一個內(nèi)存頁。頁表的4KB也被分為1024項，每項4個字節(jié)，稱為頁表項（PTE，page table entry）。每一個頁表項都指向物理內(nèi)存中的某個頁幀。

Win32提供了4GB（32bit）大小的虛擬地址空間，因此每個虛擬地址都是一個32位的整數(shù)值，由三部分組成，前10bit為頁目錄下標，用于定位在頁目錄的1024項的某一項，根據(jù)定位到的某一項的值可以找到第二層頁表中的某一個頁表；后續(xù)10bit為頁表下標，用于定位頁表的1024項中的某一項，其值可以找到物理內(nèi)存中的某一個頁，此頁包含此虛擬地址所代表的數(shù)據(jù)；后12bit為字節(jié)下標，用于定位物理頁中特定的字節(jié)位置，12位剛好可以定位一個頁中的任意位置的字節(jié)。

假設(shè)在程序中訪問一個指針（虛擬地址），指針值為0X2A8E317F，虛擬地址到物理地址的映射過程如下：

0X2A8E317F的二進制為0010 1010 1000 1110 0011 0001 0111 1111，將其分為三部分，前10bit為00 1010 1010，用于定位頁目錄中的頁目錄項，因為頁目錄項為4個字節(jié)，定位前將00 1010 1010左移2bit，得到10 1010 1000（0X2A8），使用0X2A8作為下標找到對應(yīng)的頁目錄項，此頁目錄項指向一個頁表。使用后續(xù)10bit即00 1110 0011定位此頁表中的頁表項，00 1110 0011左移2bit后為11 1000 1100（0X38B），使用0X38B作為下標找到此頁表中對應(yīng)的頁表項。找到的頁表項指向真正的內(nèi)存。最后使用最后12bit即0001 0111 1111（0X17F），定位頁內(nèi)的數(shù)據(jù)，即為此指針指向的數(shù)據(jù)。
Win32總是假定數(shù)據(jù)已經(jīng)在物理內(nèi)存中，并進行地址映射。頁表項中有一位用于標記包含此數(shù)據(jù)的頁是否在物理內(nèi)存頁中，當取得頁表項時，檢測此位，如果在，進行地址映射；如果不在，拋出缺頁錯誤，此時此頁表項中包含了此數(shù)據(jù)是否在調(diào)頁文件中，如果不在，則訪問違例；如果在，此頁表項可以查出此數(shù)據(jù)頁是否在調(diào)頁文件中，以及此數(shù)據(jù)頁在調(diào)頁文件中的起始位置，然后將此數(shù)據(jù)頁從磁盤中調(diào)入物理內(nèi)存中，再繼續(xù)進行地址映射過程。為了實現(xiàn)虛擬地址空間各進程私有，每個進程都有自己的頁目錄項和頁表結(jié)構(gòu)，對不同進程而言，頁目錄中的頁目錄項，以及頁表中的頁表項都是不同的，因此相同的指針（虛擬地址）被不同的進程映射到的物理地址也是不同的，即不同進程間傳遞指針是沒有意義的。

5、虛擬內(nèi)存空間使用狀態(tài)記錄

Win32虛擬內(nèi)存管理器使用另一個數(shù)據(jù)結(jié)構(gòu)來記錄和維護每個進程的4GB虛擬地址空間的使用及狀態(tài)信息，即虛擬地址描述符樹（VAD，Virtua Address Discriptor）。每一個進程都有自己的VAD集合，VAD集合被組織成一個自平衡二叉樹，以提高查找的效率。另外由于只有預留或提交的內(nèi)存塊才會有VAD，自由的內(nèi)存塊沒有VAD（即不在VAD樹結(jié)構(gòu)中的虛擬地址塊就是自由的）。
（1）當程序申請一塊新內(nèi)存時，虛擬內(nèi)存管理器執(zhí)行訪問VAD，找到兩個相鄰VAD，只要小的VAD的上限與大的VAD的下限之間的差值滿足所申請的內(nèi)存塊的大小需求，即可使用二者之間的虛擬內(nèi)存。
（2）當?shù)谝辉L問提交的內(nèi)存時，虛擬內(nèi)存管理器總是假定要訪問的數(shù)據(jù)所在數(shù)據(jù)頁已經(jīng)在物理內(nèi)存中，并進行虛擬地址到物理地址映射。當找到相應(yīng)的頁目錄項后發(fā)現(xiàn)頁目錄項并沒有指向一個合法的頁表，虛擬內(nèi)存管理器就會查找進程的VAD樹，找到包含該地址的VAD，并根據(jù)VAD中的信息，比如內(nèi)存塊大小、范圍，以及在調(diào)頁文件中的起始位置，隨需生成相應(yīng)的頁表項。然后從剛才發(fā)生缺頁錯誤的位置繼續(xù)進行地址映射。因此，一個虛擬內(nèi)存頁被提交時，除了在調(diào)頁文件中開辟一個備份頁外，不會生成指向它的頁表項的頁表，也不會填充指向它的頁表項，更不會開辟真正的物理內(nèi)存頁，而是直到第一次訪問提交頁時才會隨需地從VAD中取得包含該頁的整個區(qū)域的信息，生成相應(yīng)頁表，并填充相應(yīng)頁的頁表項。
（3）當能夠訪問預留的內(nèi)存時，虛擬地址管理器進行虛擬地址到物理地址的映射，找到相應(yīng)的頁目錄項后發(fā)現(xiàn)頁目錄項并沒有指向一個合法的頁表，虛擬地址管理器就會查找進程的VAD樹，找到包含該地址的VAD，此時發(fā)現(xiàn)此段內(nèi)存塊只是預留的，而沒有提交，即沒有對應(yīng)物理內(nèi)存，直接拋出訪問違例，進程退出。
（4）當訪問自由的內(nèi)存時，虛擬地址內(nèi)存管理器進行虛擬地址到物理地址的映射，找到相應(yīng)的頁目錄項后發(fā)現(xiàn)頁目錄項并沒有指向一個合法的頁表，虛擬地址管理器就會查找進程的VAD樹，發(fā)現(xiàn)并沒有VAD包含此虛擬地址，發(fā)現(xiàn)此虛擬地址所在的虛擬內(nèi)存頁是自由狀態(tài)，直接拋出訪問違例，進程退出。

6、進程工作集

因為頻繁的調(diào)頁操作引起的磁盤IO會大大降低程序的運行效率，因此對每一個進程，虛擬內(nèi)存管理器都會將一定量的內(nèi)存頁駐留在物理內(nèi)存中，并跟蹤其執(zhí)行的性能指標，并動態(tài)調(diào)整駐留的內(nèi)存頁數(shù)量。Win32中駐留在物理內(nèi)存中的內(nèi)存頁稱為進程的工作集（working set），進程的工作集可以通過任務(wù)管理器查看，內(nèi)存使用列即為工作集大小。
工作集是會動態(tài)變化的，進程初始時只有很少的代碼頁和數(shù)據(jù)頁被調(diào)入物理內(nèi)存。當執(zhí)行到未被調(diào)入內(nèi)存的代碼或訪問到尚未調(diào)入內(nèi)存的數(shù)據(jù)時，相應(yīng)代碼頁或數(shù)據(jù)頁會被調(diào)入物理內(nèi)存，工作集也會隨之增加。但工作集不能無限增加，系統(tǒng)為每個進程設(shè)定了一個最小工作集和最大工作集，當工作集達到最大工作集大小，進程需要再次調(diào)入新頁到物理內(nèi)存時，虛擬內(nèi)存管理器會架構(gòu)原來工作集中某些內(nèi)存頁先置換出物理內(nèi)存，然后再將需要調(diào)入的新頁調(diào)入內(nèi)存。
因為工作集的頁駐留在物理內(nèi)存中，對工作集頁的訪問不會涉及磁盤IO，因此速度非?？臁Ｈ绻L問的代碼或數(shù)據(jù)不在工作集中，會引發(fā)額外的磁盤IO，從而降低程序的執(zhí)行效率。極端情況下會出現(xiàn)所謂的顛簸或抖動（thrashing），即程序的大部分執(zhí)行時間都花在調(diào)頁操作上，而不是執(zhí)行代碼上。
虛擬內(nèi)存管理器在調(diào)頁時，不僅僅只是調(diào)入需要的頁，同時還將其附近的頁一起調(diào)入內(nèi)存中，對于開發(fā)人員，如果要提高程序的運行效率需要考慮如下：
（1）對代碼李碩，盡量編寫緊湊代碼，最理想情形是工作集不會達到最大閾值，在每次調(diào)入新頁時，就不需要置換已經(jīng)載入的內(nèi)存頁，因為根據(jù)locality特性，以前執(zhí)行的代碼和訪問的數(shù)據(jù)在后面有很大可能會被再次執(zhí)行好訪問，因此程序執(zhí)行時，缺頁錯誤會大大降低，即減少磁盤IO。從進程任務(wù)管理器也可以查看一個進程從開始時到當前時刻共發(fā)生的缺頁錯誤次數(shù)。即使不能達到理想情形，緊湊的代碼往往意味著接下來執(zhí)行的代碼更大可能就在當前頁或相鄰頁。根據(jù)時間locality特性，程序80%的時間花費在20%代碼上，如果能將耗時的20%代碼盡量緊湊且排在一起，會大大提高程序的整體性能。
（2）對數(shù)據(jù)來說，盡量將那些會一起訪問的數(shù)據(jù)（如鏈表）放在一起，當訪問數(shù)據(jù)時，數(shù)據(jù)在同一頁或相鄰頁，只需要一次調(diào)頁操作就可以完成。如果數(shù)據(jù)分散在分散在多個頁（多個頁不相鄰），每次對數(shù)據(jù)的整體訪問都會引發(fā)大量的缺頁錯誤，從而降低性能。利用Win32提供的預留和提交兩步機制，可以為一同訪問的數(shù)據(jù)預留一大塊空間，此時并沒有分配實際存儲空間，而是在后續(xù)執(zhí)行過程中生成數(shù)據(jù)時格局需要提交內(nèi)存，既不浪費存儲空間（物理內(nèi)存和磁盤的調(diào)頁文件存儲空間），又能利用locality特性。

三、Linux內(nèi)存管理

1、Linux內(nèi)存管理機制簡介

Linux的內(nèi)存管理主要分為兩部分，一部分負責物理內(nèi)存的申請與釋放，物理內(nèi)存的申請與釋放的最小單位為頁，在IA32中，頁的大小為4KB；另一部分負責處理虛擬內(nèi)存，虛擬內(nèi)存的主要操作包括虛擬地址空間與物理地址空間的映射，物理內(nèi)存頁與磁盤頁之間的置換等。

2、Linux進程的內(nèi)存布局

一個32位Linux進程的地址空間為4GB，其中高位1GB，即0XC0000000--0XFFFFFFFF，為內(nèi)核空間，低位3GB，即0X00000000--0XBFFFFFFF為用戶地址空間。用戶地址空間進一步被分為程序代碼區(qū)、數(shù)據(jù)區(qū)（包括初始化數(shù)據(jù)區(qū)DATA和未初始化數(shù)據(jù)區(qū)BSS）、堆和棧。程序代碼區(qū)占據(jù)最低端，往上是初始化數(shù)據(jù)區(qū)DATA和未初始化數(shù)據(jù)區(qū)BSS。代碼區(qū)存放應(yīng)用程序的機器代碼，運行過程中代碼不能修改，因此代碼區(qū)內(nèi)存為只讀，且大小固定。數(shù)據(jù)區(qū)中存放應(yīng)用程序的全局數(shù)據(jù)，靜態(tài)數(shù)據(jù)和常量字符串，數(shù)據(jù)區(qū)大小也是固定的。
堆從未初始化數(shù)據(jù)區(qū)開始，向上端動態(tài)增長，增長過程中虛擬地址值變大；棧從高位地址開始，向下動態(tài)增長，虛擬地址值變小。
堆是應(yīng)用程序在運行過程中動態(tài)申請的內(nèi)存空間，如通過malloc/new動態(tài)生成對象或開辟內(nèi)存空間時，最終會調(diào)用系統(tǒng)調(diào)用brk來動態(tài)調(diào)整數(shù)據(jù)區(qū)的大小。當申請的動態(tài)內(nèi)存區(qū)域使用完畢，需要開發(fā)者明確使用相應(yīng)的free/delete對申請的動態(tài)內(nèi)存空間進行釋放，free/delete最終也會使用brk系統(tǒng)調(diào)用調(diào)整數(shù)據(jù)區(qū)的大小。
棧是用來存放函數(shù)的傳入?yún)?shù)、臨時變量以及返回地址等數(shù)據(jù)，不需要通過malloc/new開辟空間，棧的增長與縮減是因為函數(shù)的調(diào)用與返回，不需要開發(fā)人員操作，沒有內(nèi)存泄漏的危險。
初始化數(shù)據(jù)區(qū)存放的是編譯期就能夠知道由程序設(shè)定初始值的全局變量及靜態(tài)變量等，其初始值必須保存在最終生成的二進制文件中，并且在程序運行時會原封不動地將此區(qū)域映射到進程的初始化數(shù)據(jù)區(qū)。如果一個全局變量或靜態(tài)變量在源代碼中沒有被賦初始值，在程序啟動后，在第一次被賦值前，其初始值為0，本質(zhì)上是有初始值的，其初始值為0。但當最終生成二進制文件時，未初始化數(shù)據(jù)區(qū)不會占據(jù)對應(yīng)變量總大小的區(qū)域，而是只用一個值進行標識其未初始化數(shù)據(jù)區(qū)的總大小。如一個程序的代碼指令有100KB，所有初始化數(shù)據(jù)總大小為100KB，所有未初始化數(shù)據(jù)總大小為150KB，則在最終生成的二進制文件中代碼區(qū)有100KB，接著是100KB的初始化數(shù)據(jù)區(qū)，然后是4字節(jié)的大小空間，用于標記未初始化數(shù)據(jù)區(qū)大小，其值為150X1024，用于節(jié)省磁盤空間。但在進程虛擬地址空間中，對應(yīng)未初始化數(shù)據(jù)區(qū)的大小必須是150KB，因為在程序運行時，程序必須真正能夠訪問到變量中的每一個，即當程序啟動時，當檢測到二進制文件中未初始化數(shù)據(jù)區(qū)的值為150X1024，則系統(tǒng)會開辟出150KB大小的區(qū)域作為進程的未初始化數(shù)據(jù)區(qū)并同時使用0對其進行初始化。

3、Linux物理內(nèi)存管理

物理內(nèi)存是用來存放代碼指令與供代碼指令操作的數(shù)據(jù)的最終場所，因此物理內(nèi)存的管理是內(nèi)存管理系統(tǒng)極其重要的任務(wù)。Linux使用頁分配器（page allocator）來管理物理內(nèi)存，頁分配器負責分配和回收所有的物理內(nèi)存頁（物理內(nèi)存的分配與回收的最小單位為4KB大小的頁）。
頁分配器的核心算法稱為兄弟堆算法（buddy-heap algorithm），算法思想是每個物理內(nèi)存區(qū)域都會有一個與之相鄰的所謂兄弟區(qū)域，當兩個區(qū)域被回收后，會被合并成為一個區(qū)域。如果被合并區(qū)域的相鄰區(qū)域也被回收后，會被進一步合并為更大的區(qū)域。當有物理內(nèi)存請求到來時，頁分配器會首先檢測是否有大小與之一致的區(qū)域。如果有，直接使用找到的匹配區(qū)域滿足請求；如果沒有，則找到更大的一個區(qū)域，并繼續(xù)劃分，直到分出的區(qū)域能夠滿足請求。為了配合兄弟堆算法，必須有鏈表來記錄自由的物理內(nèi)存區(qū)域，對于每個相同大小的自由區(qū)域，會有一個鏈表將其連接，每種大小的區(qū)域都會有一個鏈表對其進行管理。自由區(qū)域的大小都是2的冪。
當有一個8KB大小的內(nèi)存請求到來，當前最小可供分配的區(qū)域為64KB，此時64KB會被劃分為兩個32KB，繼而將低位的32KB繼續(xù)劃分為兩個16KB大小的區(qū)域，再將最低位的16KB大小區(qū)域劃分為兩個8KB大小的區(qū)域，然后分配高位的8KB區(qū)域滿足請求。

4、Linux虛擬內(nèi)存管理

虛擬內(nèi)存管理器的主要任務(wù)是維護應(yīng)用程序的虛擬地址空間使用信息，如哪些區(qū)域已經(jīng)被使用（映射），是否有磁盤文件作為備份存儲。如果有，每個區(qū)域?qū)?yīng)在磁盤的哪個區(qū)域，另外一個重要功能就是調(diào)頁，如程序訪問某些尚未調(diào)至物理內(nèi)存的數(shù)據(jù)時，虛擬內(nèi)存管理器負責定位數(shù)據(jù)，并將其置換進物理內(nèi)存。如果物理內(nèi)存此時沒有自由頁，還需要將物理內(nèi)存中的某些頁先置換出去。
用來維護應(yīng)用程序的虛擬地址空間使用信息的數(shù)據(jù)結(jié)構(gòu)是vm_area_struct。每個vm_area_struct結(jié)構(gòu)體都描述了一個進程虛擬地址空間中被分配的區(qū)域，當vm_area_struct個數(shù)不超過32個時，被連接成為一個鏈表；當超過32個時，所有的vm_area_struct會被組織為一棵自平衡二叉樹，利于提高查詢速度。當程序通過某個指針訪問某個數(shù)據(jù)時，系統(tǒng)會查詢vm_area_struct樹，如果發(fā)現(xiàn)指針沒有落在任何一個vm_area_struct所表示的區(qū)域內(nèi)，則判定指針所代表的地址沒有被分配，即非法的指針訪問。

5、虛擬地址映射為物理地址

當通過程序的指針訪問某個數(shù)據(jù)時，因為指針本質(zhì)是一個虛擬地址值，因此虛擬地址值必須被轉(zhuǎn)化為物理地址值，才能真正訪問其所指代的數(shù)據(jù)。
Linux使用三層映射策略將一個虛擬地址映射為一個物理地址。與Windows相比，多了Middle層，當對于IA32體系，Middle層沒有用，因此Linux與Windows相同。