建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
C++應(yīng)用程序性能優(yōu)化（五）——操作系統(tǒng)的內(nèi)存管理
一、操作系統(tǒng)內(nèi)存管理簡(jiǎn)介
長(zhǎng)期以來(lái)，在計(jì)算機(jī)系統(tǒng)中，內(nèi)存都是一種緊缺和寶貴的資源，應(yīng)用程序必須在載入內(nèi)存后才能執(zhí)行。早期，在內(nèi)存空間不夠大時(shí)，同時(shí)運(yùn)行的應(yīng)用程序的數(shù)量會(huì)受到很大的限制，甚至當(dāng)某個(gè)應(yīng)用程序在某個(gè)運(yùn)行時(shí)所需內(nèi)存超過(guò)物理內(nèi)存時(shí)，應(yīng)用程序就會(huì)無(wú)法運(yùn)行?，F(xiàn)代操作系統(tǒng)（Windows、Linux）通過(guò)引入虛擬內(nèi)存進(jìn)行內(nèi)存管理，解決了應(yīng)用程序在內(nèi)存不足時(shí)不能運(yùn)行的問(wèn)題。
本質(zhì)上，虛擬內(nèi)存就是要讓一個(gè)程序的代碼和數(shù)據(jù)在沒(méi)有全部載入內(nèi)存時(shí)即可運(yùn)行。運(yùn)行過(guò)程中，當(dāng)執(zhí)行到尚未載入內(nèi)存的代碼，或者要訪問(wèn)還沒(méi)有載入到內(nèi)存的數(shù)據(jù)時(shí)，虛擬內(nèi)存管理器動(dòng)態(tài)地將相應(yīng)的代碼或數(shù)據(jù)從硬盤(pán)載入到內(nèi)存中。而且在通常情況下，虛擬內(nèi)存管理器也會(huì)相應(yīng)地先將內(nèi)存中某些代碼或數(shù)據(jù)置換到硬盤(pán)中，為即將載入的代碼或數(shù)據(jù)騰出空間。
因?yàn)閮?nèi)存和硬盤(pán)間的數(shù)據(jù)傳輸相對(duì)于代碼執(zhí)行非常慢，因此虛擬內(nèi)存管理器在保證工作正確的前提下還必須考慮效率因素，如需要優(yōu)化置換算法，盡量避免將要被執(zhí)行的代碼或訪問(wèn)的數(shù)據(jù)剛被置換出內(nèi)存，而很久沒(méi)有訪問(wèn)的代碼或數(shù)據(jù)卻一直駐留在內(nèi)存中。虛擬內(nèi)存管理器還需要將駐留在內(nèi)存中的各個(gè)進(jìn)程的代碼數(shù)據(jù)維持在一個(gè)合理的數(shù)量上，并且根據(jù)進(jìn)程性能的表現(xiàn)動(dòng)態(tài)調(diào)整，使得程序運(yùn)行時(shí)將涉及的磁盤(pán)IO次數(shù)降到盡可能低，以提高程序的運(yùn)行性能。
創(chuàng)新互聯(lián)建站主要從事網(wǎng)站設(shè)計(jì)、成都網(wǎng)站設(shè)計(jì)、網(wǎng)頁(yè)設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)德陽(yáng),10余年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專(zhuān)業(yè),歡迎來(lái)電咨詢(xún)建站服務(wù):028-86922220
二、Windows內(nèi)存管理
1、Windows虛擬內(nèi)存管理系統(tǒng)簡(jiǎn)介
Win32虛擬內(nèi)存管理器為每一個(gè)Win32進(jìn)程提供了進(jìn)程私有并且基于頁(yè)的4GB（32bit）大小的線性虛擬地址空間。
進(jìn)程私有即每個(gè)進(jìn)程只能訪問(wèn)屬于自己的內(nèi)存空間，而無(wú)法訪問(wèn)屬于其它進(jìn)程的地址空間，也不用擔(dān)心自己的地址空間被其它進(jìn)程看到（父子進(jìn)程例外，比如調(diào)試器利用父子進(jìn)程關(guān)系來(lái)訪問(wèn)被被調(diào)試進(jìn)程的地址空間）。進(jìn)程運(yùn)行時(shí)用到的dll并沒(méi)有屬于自己的地址空間，而是其所屬進(jìn)程的虛擬地址空間，dll的全局?jǐn)?shù)據(jù)，以及通過(guò)dll函數(shù)申請(qǐng)的內(nèi)存都是從調(diào)用其進(jìn)程的虛擬地址空間開(kāi)辟的。
基于頁(yè)是指虛擬地址空間被劃分為多個(gè)稱(chēng)為頁(yè)的單元，頁(yè)的大小由底層處理器決定，x86架構(gòu)處理器中頁(yè)的大小為4KB。頁(yè)是Win32虛擬內(nèi)存管理器處理的最小單元，相應(yīng)的物理內(nèi)存也被劃分為多個(gè)頁(yè)。虛擬內(nèi)存地址空間的申請(qǐng)和釋放，以及內(nèi)存和磁盤(pán)的數(shù)據(jù)傳輸或置換都是以頁(yè)為最小單位進(jìn)行的。
4GB大小意味著進(jìn)程中的地址取值范圍可以從0x00000000到0xFFFFFFFF，Win32將低區(qū)的2GB留給進(jìn)程使用，高區(qū)的2GB留給系統(tǒng)使用。
Win32中用來(lái)輔助實(shí)現(xiàn)虛擬內(nèi)存的硬盤(pán)文件稱(chēng)為調(diào)頁(yè)文件，可以有16個(gè)，調(diào)頁(yè)文件用來(lái)存放被虛擬內(nèi)存管理器置換出內(nèi)存的數(shù)據(jù)。當(dāng)調(diào)頁(yè)文件的數(shù)據(jù)再次被進(jìn)程訪問(wèn)時(shí)，虛擬內(nèi)存管理器會(huì)將其從調(diào)頁(yè)文件中置換進(jìn)內(nèi)存，進(jìn)程可以正確對(duì)其訪問(wèn)。用戶(hù)可以自己配置調(diào)頁(yè)文件，出于空間利用效率和性能的考慮，程序代碼不會(huì)被修改（包括exe和dll），所以當(dāng)其所在頁(yè)被置換出內(nèi)存時(shí)，并不會(huì)被寫(xiě)進(jìn)調(diào)頁(yè)文件中，而是直接拋棄。當(dāng)再次被需要時(shí)，虛擬內(nèi)存管理器直接從存放程序代碼的exe或dll文件中找到并調(diào)入內(nèi)存。另外，對(duì)exe和dll文件中包含的只讀數(shù)據(jù)的處理與程序代碼處理相同，不會(huì)在調(diào)頁(yè)文件中開(kāi)辟空間存儲(chǔ)。
當(dāng)進(jìn)程執(zhí)行某段代碼或訪問(wèn)某些數(shù)據(jù)，而代碼或數(shù)據(jù)還不在內(nèi)存中時(shí)，稱(chēng)為缺頁(yè)錯(cuò)誤。缺頁(yè)錯(cuò)誤的原因很多，最常見(jiàn)的是代碼和數(shù)據(jù)被虛擬內(nèi)存管理器置換出內(nèi)存，虛擬內(nèi)存管理器會(huì)在代碼被執(zhí)行或數(shù)據(jù)被訪問(wèn)前將其調(diào)入內(nèi)存。內(nèi)存置換對(duì)開(kāi)發(fā)人員來(lái)說(shuō)是透明的，大大簡(jiǎn)化了開(kāi)發(fā)人員的工作。但調(diào)頁(yè)錯(cuò)誤涉及磁盤(pán)IO，大量的調(diào)頁(yè)錯(cuò)誤會(huì)大大降低程序的總體性能，因此需要了解缺頁(yè)錯(cuò)誤的主要原因和規(guī)避方法。
2、使用虛擬內(nèi)存
Win32中分配內(nèi)存分為兩個(gè)步驟，預(yù)留和提交。因此在進(jìn)程虛擬地址空間中的頁(yè)有三種狀態(tài)：自由free、預(yù)留reserved和提交committed。
自由表示此頁(yè)尚未被分配，可以用來(lái)滿(mǎn)足新的內(nèi)存分配請(qǐng)求。
預(yù)留是指從虛擬地址空間劃出一塊區(qū)域（region，頁(yè)的整數(shù)倍），劃出后的內(nèi)存空間不能用來(lái)滿(mǎn)足新的內(nèi)存分配請(qǐng)求，而是用來(lái)供要求預(yù)留此段內(nèi)存的代碼以后使用。預(yù)留時(shí)并沒(méi)有分配物理內(nèi)存，只是增加了一個(gè)描述進(jìn)程虛擬地址空間使用狀態(tài)的數(shù)據(jù)結(jié)構(gòu)（VAD，虛擬地址描述符），用來(lái)記錄此段內(nèi)存空間已經(jīng)被預(yù)留。預(yù)留操作相對(duì)較快，因?yàn)闆](méi)有真正分配物理內(nèi)存，因此預(yù)留的空間不能夠直接訪問(wèn)，對(duì)預(yù)留頁(yè)的訪問(wèn)會(huì)引起內(nèi)存訪問(wèn)違例。
提交，如果想要得到真正的物理內(nèi)存，必須對(duì)預(yù)留的內(nèi)存進(jìn)行提交。提交會(huì)從調(diào)頁(yè)文件中開(kāi)辟空間，并修改VAD中的相應(yīng)項(xiàng)。提交時(shí)也并沒(méi)有立刻從物理內(nèi)存中分配空間，而是從磁盤(pán)的調(diào)頁(yè)文件中開(kāi)辟空間，作為置換的備份空間。當(dāng)代碼第一次訪問(wèn)提交內(nèi)存中的數(shù)據(jù)時(shí)，系統(tǒng)發(fā)現(xiàn)并沒(méi)由真正的物理內(nèi)存，拋出缺頁(yè)操作。虛擬內(nèi)存管理器會(huì)處理缺頁(yè)錯(cuò)誤，直到此時(shí)才會(huì)真正分配物理內(nèi)存，提交也可以在預(yù)留的同時(shí)進(jìn)行。提交操作會(huì)從磁盤(pán)的調(diào)頁(yè)文件中開(kāi)辟空間，所以比預(yù)留操作耗時(shí)。
Win32虛擬內(nèi)存管理中demand-paging策略要求不到真正訪問(wèn)時(shí)不會(huì)為某虛擬地址分配真正的物理內(nèi)存。demand-paging策略一是處于性能考慮，將工作分段完成，提高總體性能；二是出于空間效率考慮，不到真正訪問(wèn)時(shí)，Win32總是假定認(rèn)為進(jìn)程不會(huì)訪問(wèn)大多數(shù)數(shù)據(jù)，因而不必要為其開(kāi)辟存儲(chǔ)空間或?qū)⑵渲脫Q進(jìn)物理內(nèi)存，以提高存儲(chǔ)空間的利用率。
如果某些程序?qū)?nèi)存有很大的需求，但并不是立刻需要所有內(nèi)存，則一次性從物理存儲(chǔ)中開(kāi)辟空間滿(mǎn)足潛在的需求，從執(zhí)行性能和存儲(chǔ)空間效率上是一種浪費(fèi)。由于需求只是潛在的，極有可能分配的內(nèi)存中很大一部分最后都沒(méi)有被真正利用。如果在申請(qǐng)時(shí)一次性為其分配所有物理存儲(chǔ)，會(huì)極大降低空間的利用率。
但如果完全不用預(yù)留和提交機(jī)制，只是隨需分配內(nèi)存來(lái)滿(mǎn)足每次的請(qǐng)求，則對(duì)一個(gè)會(huì)在不同時(shí)間點(diǎn)頻繁請(qǐng)求內(nèi)存的代碼來(lái)說(shuō)，因?yàn)樵谄湔?qǐng)求內(nèi)存的不同時(shí)間點(diǎn)的間隙極有可能會(huì)由其它代碼請(qǐng)求內(nèi)存，會(huì)導(dǎo)致在不同時(shí)間點(diǎn)頻繁請(qǐng)求內(nèi)存的代碼得到的內(nèi)存因?yàn)樘摂M地址不連續(xù)，無(wú)法很好利用空間的locality特性，對(duì)其整體進(jìn)行訪問(wèn)（如遍歷）時(shí)就會(huì)增加缺頁(yè)錯(cuò)誤的數(shù)量，從而降低程序性能。
預(yù)留和提交在Win32程序中都使用VirtualAlloc函數(shù)完成，預(yù)留傳入MEM_RESERVE參數(shù)，提交傳入MEM_COMMIT參數(shù)。釋放虛擬內(nèi)存時(shí)使用VirtualFree函數(shù)，根據(jù)不同的傳入?yún)?shù)，與VirtualAlloc函數(shù)對(duì)應(yīng)，可以釋放與虛擬地址區(qū)域相對(duì)應(yīng)的物理內(nèi)存，但虛擬地址區(qū)域還可以處于預(yù)留狀態(tài)，也可以連同虛擬地址區(qū)域一同釋放，則虛擬地址區(qū)域恢復(fù)為自由狀態(tài)。
線程棧和進(jìn)程堆的實(shí)現(xiàn)利用了預(yù)留和提交兩步機(jī)制，Win32系統(tǒng)中，線程棧使用預(yù)留和提交兩步機(jī)制如下：
創(chuàng)建線程棧時(shí)，只是預(yù)留一個(gè)虛擬的地址區(qū)域，默認(rèn)為1M（可以在CreateThread或鏈接時(shí)通過(guò)鏈接選項(xiàng)修改），初始時(shí)只有前兩頁(yè)是提交的。當(dāng)線程棧因?yàn)楹瘮?shù)的嵌套調(diào)用需要更多的提交頁(yè)時(shí)，虛擬內(nèi)存管理器會(huì)動(dòng)態(tài)地提交線程的虛擬地址區(qū)域中的后續(xù)頁(yè)以滿(mǎn)足其需求，直到到達(dá)1M的上限。當(dāng)?shù)竭_(dá)預(yù)留區(qū)域大小的上限（默認(rèn)1M）時(shí)，虛擬內(nèi)存管理器不會(huì)增加預(yù)留區(qū)域的大小，而是在提交最后一頁(yè)時(shí)拋出一個(gè)棧溢出異常，拋出棧溢出異常時(shí)線程棧還有一頁(yè)空間可以利用，程序仍可正常運(yùn)行。當(dāng)程序繼續(xù)使用?？臻g，用完最后一頁(yè)時(shí)，還繼續(xù)需要存儲(chǔ)空間，此時(shí)超過(guò)上限，會(huì)直接導(dǎo)致進(jìn)程退出。
為了防止線程棧溢出導(dǎo)致整個(gè)程序退出，應(yīng)該盡量控制棧的使用大小。比如減少函數(shù)的嵌套層數(shù)，減少遞歸函數(shù)的使用，盡量不要在函數(shù)中使用較大的局部變量（大的對(duì)象可以從堆中開(kāi)辟空間存放，因?yàn)槎褧?huì)動(dòng)態(tài)擴(kuò)大，而線程棧的可用內(nèi)存區(qū)域在線程創(chuàng)建時(shí)已經(jīng)固定，在線程的整個(gè)生命期都無(wú)法擴(kuò)展）。
為了防止一個(gè)線程棧的溢出導(dǎo)致整個(gè)程序退出，可以對(duì)可能產(chǎn)生線程棧溢出的線程體函數(shù)加異常處理，捕獲在提交最后一頁(yè)時(shí)拋出的溢出異常，并做相應(yīng)處理。
3、訪問(wèn)虛擬內(nèi)存時(shí)的處理流程
對(duì)某虛擬內(nèi)存區(qū)域進(jìn)行了預(yù)留并提交后，就可以對(duì)虛擬內(nèi)存區(qū)域中數(shù)據(jù)進(jìn)行訪問(wèn)。當(dāng)程序?qū)δ扯蝺?nèi)存訪問(wèn)時(shí)處理流程如下：
如果數(shù)據(jù)已經(jīng)在物理內(nèi)存中，虛擬地址管理器只需要將指向數(shù)據(jù)的虛擬內(nèi)存地址映射為物理地址，即可訪問(wèn)到物理內(nèi)存中的數(shù)據(jù)。此時(shí)不會(huì)涉及磁盤(pán)IO，速度較快。
當(dāng)?shù)谝淮卧L問(wèn)一段剛剛提交的內(nèi)存中的數(shù)據(jù)時(shí)，因?yàn)椴](méi)有真正的物理內(nèi)存分配，或者被訪問(wèn)數(shù)據(jù)以前已經(jīng)被訪問(wèn)過(guò)，但已經(jīng)被虛擬內(nèi)存管理器置換出物理內(nèi)存，此時(shí)會(huì)觸發(fā)缺頁(yè)錯(cuò)誤。虛擬內(nèi)存管理器會(huì)處理缺頁(yè)錯(cuò)誤，虛擬內(nèi)存管理器會(huì)先檢測(cè)數(shù)據(jù)是否在調(diào)頁(yè)文件中已有備份空間（exe、dll的代碼頁(yè)和只讀數(shù)據(jù)的備份空間不在調(diào)頁(yè)文件，而是exe、dll文件），如果訪問(wèn)的數(shù)據(jù)在磁盤(pán)有備份空間，虛擬內(nèi)存管理器需要在物理內(nèi)存中找到合適的頁(yè)，并將存放在磁盤(pán)的備份數(shù)據(jù)置換進(jìn)物理內(nèi)存。
虛擬內(nèi)存管理器首先查詢(xún)當(dāng)前物理內(nèi)存中是否有空閑頁(yè)，虛擬內(nèi)存管理器維護(hù)一個(gè)名稱(chēng)為頁(yè)幀數(shù)據(jù)庫(kù)（page-frame database）的數(shù)據(jù)結(jié)構(gòu)，此數(shù)據(jù)結(jié)構(gòu)是操作系統(tǒng)全局的，當(dāng)Windows系統(tǒng)啟動(dòng)時(shí)被初始化，用來(lái)跟蹤和記錄物理內(nèi)存中每一個(gè)頁(yè)的狀態(tài)，并用一個(gè)鏈表將所有空閑頁(yè)連接起來(lái)，當(dāng)需要空閑頁(yè)時(shí)，直接查找此空閑頁(yè)鏈表，如果有，直接使用某個(gè)空閑頁(yè)；否則，根據(jù)調(diào)頁(yè)算法首先選出某個(gè)頁(yè)。虛擬內(nèi)存管理器調(diào)頁(yè)時(shí)并不是只調(diào)入一個(gè)頁(yè)，為了利用局部特性，在調(diào)入包含所需數(shù)據(jù)頁(yè)的同時(shí)，會(huì)將相鄰的幾個(gè)頁(yè)一起調(diào)入內(nèi)存，以提高程序效率。在選出某個(gè)內(nèi)存頁(yè)后，接著檢查此頁(yè)狀態(tài)，如果此頁(yè)自上次調(diào)入內(nèi)存以來(lái)尚未被修改，則直接使用此頁(yè)（代碼頁(yè)和只讀頁(yè)也可以直接使用）。如果此頁(yè)已經(jīng)被修改，則需要先將此頁(yè)的內(nèi)容寫(xiě)到磁盤(pán)的調(diào)頁(yè)文件中相應(yīng)的備份頁(yè)，并隨即將此頁(yè)標(biāo)記為空閑頁(yè)。此時(shí)已經(jīng)有一個(gè)空閑頁(yè)用來(lái)存放即將要訪問(wèn)的數(shù)據(jù)。虛擬內(nèi)存管理器會(huì)再次檢測(cè)，此數(shù)據(jù)是否剛被申請(qǐng)的內(nèi)存并且第一次被訪問(wèn)，如果是直接將此空閑頁(yè)清0使用即可，不必從磁盤(pán)的調(diào)頁(yè)文件中讀取相應(yīng)備份頁(yè)；如果不是，則需要將磁盤(pán)調(diào)頁(yè)文件中相應(yīng)的備份頁(yè)讀到此空閑空間中，并隨即將此頁(yè)狀態(tài)從空閑頁(yè)改為活動(dòng)頁(yè)。
此時(shí)，數(shù)據(jù)已經(jīng)在物理內(nèi)存頁(yè)中，通過(guò)虛擬地址映射到物理地址即可訪問(wèn)數(shù)據(jù)。
實(shí)際的數(shù)據(jù)訪問(wèn)中，情形會(huì)比較復(fù)雜，比如當(dāng)用戶(hù)定義了一個(gè)數(shù)組，而此數(shù)組剛好在其所在頁(yè)的下邊界，且此頁(yè)的下一頁(yè)是自由或者預(yù)留狀態(tài)（非提交，沒(méi)有真正的物理內(nèi)存）。當(dāng)程序不小心向下越界訪問(wèn)此數(shù)組，則首先引發(fā)缺頁(yè)錯(cuò)誤。隨即虛擬內(nèi)存管理器在處理缺頁(yè)錯(cuò)誤時(shí)檢測(cè)到其不在調(diào)頁(yè)文件中，即所謂的訪問(wèn)違例（access violation）。訪問(wèn)違例意味著要訪問(wèn)的地址所在的虛擬內(nèi)存地址還沒(méi)有被提交，即沒(méi)有實(shí)際的物理存儲(chǔ)地址與虛擬內(nèi)存地址對(duì)應(yīng)，訪問(wèn)違例會(huì)直接導(dǎo)致整個(gè)進(jìn)程退出（crash）。
指針越界訪問(wèn)的后果根據(jù)運(yùn)行時(shí)實(shí)際情況而有所不同，當(dāng)數(shù)組并非處于其所在頁(yè)的邊界時(shí)，越界后還在同一頁(yè)中，此時(shí)只會(huì)引起誤訪問(wèn)（誤讀或誤寫(xiě)，誤讀只會(huì)影響到正在執(zhí)行的代碼，誤寫(xiě)則會(huì)影響其它處代碼的執(zhí)行），本頁(yè)中的其它數(shù)據(jù)，而不會(huì)導(dǎo)致整個(gè)進(jìn)程crash。即使數(shù)組真的存在于所在頁(yè)的邊界，且越界后指針值落在其相鄰頁(yè)，但如果此相鄰頁(yè)也為提交狀態(tài)，此時(shí)仍然為誤訪問(wèn)，也不會(huì)導(dǎo)致進(jìn)程的crash。因此，同一程序的代碼中存在數(shù)組指針訪問(wèn)越界錯(cuò)誤，運(yùn)行時(shí)有時(shí)會(huì)crash，有時(shí)不會(huì)。
MicroSoft提供了一個(gè)檢測(cè)指針越界訪問(wèn)的工具pageheap，原理是強(qiáng)制使每次分配的內(nèi)存都位于頁(yè)的邊界，同時(shí)強(qiáng)制頁(yè)的相鄰頁(yè)為自由頁(yè)，此時(shí)每次越界訪問(wèn)都會(huì)引起訪問(wèn)違例，導(dǎo)致程序crash，從而使得指針越界訪問(wèn)錯(cuò)誤在開(kāi)發(fā)階段一定會(huì)暴露出來(lái)，而不會(huì)發(fā)生某個(gè)指針越界訪問(wèn)錯(cuò)誤一直隱藏到發(fā)布版本，直到最終用戶(hù)訪問(wèn)時(shí)才會(huì)被發(fā)現(xiàn)。
4、虛擬地址到物理地址的映射
在確保訪問(wèn)的數(shù)據(jù)已經(jīng)在物理內(nèi)存中后，還需要先將虛擬地址轉(zhuǎn)換為物理地址，即地址映射，才能訪問(wèn)數(shù)據(jù)。
Win32通過(guò)一個(gè)兩層表結(jié)構(gòu)來(lái)實(shí)現(xiàn)地址映射，因?yàn)?GB虛擬地址空間為每個(gè)進(jìn)程私有，每個(gè)進(jìn)程都維護(hù)一套自己的層次結(jié)構(gòu)用來(lái)實(shí)現(xiàn)其地址映射。第一層表為頁(yè)目錄（page directory），實(shí)際就是一個(gè)內(nèi)存頁(yè)（4KB=4096Byte），以4個(gè)字節(jié)為單元分為1024項(xiàng)，每一項(xiàng)稱(chēng)為頁(yè)目錄項(xiàng)（PDE，page directory entry）；第二層表為頁(yè)表（page table），共有1024個(gè)頁(yè)表。頁(yè)目錄中每一個(gè)頁(yè)目錄項(xiàng)對(duì)應(yīng)一個(gè)頁(yè)表，每一個(gè)頁(yè)表也占一個(gè)內(nèi)存頁(yè)。頁(yè)表的4KB也被分為1024項(xiàng)，每項(xiàng)4個(gè)字節(jié)，稱(chēng)為頁(yè)表項(xiàng)（PTE，page table entry）。每一個(gè)頁(yè)表項(xiàng)都指向物理內(nèi)存中的某個(gè)頁(yè)幀。
Win32提供了4GB（32bit）大小的虛擬地址空間，因此每個(gè)虛擬地址都是一個(gè)32位的整數(shù)值，由三部分組成，前10bit為頁(yè)目錄下標(biāo)，用于定位在頁(yè)目錄的1024項(xiàng)的某一項(xiàng)，根據(jù)定位到的某一項(xiàng)的值可以找到第二層頁(yè)表中的某一個(gè)頁(yè)表；后續(xù)10bit為頁(yè)表下標(biāo)，用于定位頁(yè)表的1024項(xiàng)中的某一項(xiàng)，其值可以找到物理內(nèi)存中的某一個(gè)頁(yè)，此頁(yè)包含此虛擬地址所代表的數(shù)據(jù)；后12bit為字節(jié)下標(biāo)，用于定位物理頁(yè)中特定的字節(jié)位置，12位剛好可以定位一個(gè)頁(yè)中的任意位置的字節(jié)。
假設(shè)在程序中訪問(wèn)一個(gè)指針（虛擬地址），指針值為0X2A8E317F，虛擬地址到物理地址的映射過(guò)程如下：
0X2A8E317F的二進(jìn)制為0010 1010 1000 1110 0011 0001 0111 1111，將其分為三部分，前10bit為00 1010 1010，用于定位頁(yè)目錄中的頁(yè)目錄項(xiàng)，因?yàn)轫?yè)目錄項(xiàng)為4個(gè)字節(jié)，定位前將00 1010 1010左移2bit，得到10 1010 1000（0X2A8），使用0X2A8作為下標(biāo)找到對(duì)應(yīng)的頁(yè)目錄項(xiàng)，此頁(yè)目錄項(xiàng)指向一個(gè)頁(yè)表。使用后續(xù)10bit即00 1110 0011定位此頁(yè)表中的頁(yè)表項(xiàng)，00 1110 0011左移2bit后為11 1000 1100（0X38B），使用0X38B作為下標(biāo)找到此頁(yè)表中對(duì)應(yīng)的頁(yè)表項(xiàng)。找到的頁(yè)表項(xiàng)指向真正的內(nèi)存。最后使用最后12bit即0001 0111 1111（0X17F），定位頁(yè)內(nèi)的數(shù)據(jù)，即為此指針指向的數(shù)據(jù)。
Win32總是假定數(shù)據(jù)已經(jīng)在物理內(nèi)存中，并進(jìn)行地址映射。頁(yè)表項(xiàng)中有一位用于標(biāo)記包含此數(shù)據(jù)的頁(yè)是否在物理內(nèi)存頁(yè)中，當(dāng)取得頁(yè)表項(xiàng)時(shí)，檢測(cè)此位，如果在，進(jìn)行地址映射；如果不在，拋出缺頁(yè)錯(cuò)誤，此時(shí)此頁(yè)表項(xiàng)中包含了此數(shù)據(jù)是否在調(diào)頁(yè)文件中，如果不在，則訪問(wèn)違例；如果在，此頁(yè)表項(xiàng)可以查出此數(shù)據(jù)頁(yè)是否在調(diào)頁(yè)文件中，以及此數(shù)據(jù)頁(yè)在調(diào)頁(yè)文件中的起始位置，然后將此數(shù)據(jù)頁(yè)從磁盤(pán)中調(diào)入物理內(nèi)存中，再繼續(xù)進(jìn)行地址映射過(guò)程。為了實(shí)現(xiàn)虛擬地址空間各進(jìn)程私有，每個(gè)進(jìn)程都有自己的頁(yè)目錄項(xiàng)和頁(yè)表結(jié)構(gòu)，對(duì)不同進(jìn)程而言，頁(yè)目錄中的頁(yè)目錄項(xiàng)，以及頁(yè)表中的頁(yè)表項(xiàng)都是不同的，因此相同的指針（虛擬地址）被不同的進(jìn)程映射到的物理地址也是不同的，即不同進(jìn)程間傳遞指針是沒(méi)有意義的。
5、虛擬內(nèi)存空間使用狀態(tài)記錄
Win32虛擬內(nèi)存管理器使用另一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)記錄和維護(hù)每個(gè)進(jìn)程的4GB虛擬地址空間的使用及狀態(tài)信息，即虛擬地址描述符樹(shù)（VAD，Virtua Address Discriptor）。每一個(gè)進(jìn)程都有自己的VAD集合，VAD集合被組織成一個(gè)自平衡二叉樹(shù)，以提高查找的效率。另外由于只有預(yù)留或提交的內(nèi)存塊才會(huì)有VAD，自由的內(nèi)存塊沒(méi)有VAD（即不在VAD樹(shù)結(jié)構(gòu)中的虛擬地址塊就是自由的）。
（1）當(dāng)程序申請(qǐng)一塊新內(nèi)存時(shí)，虛擬內(nèi)存管理器執(zhí)行訪問(wèn)VAD，找到兩個(gè)相鄰VAD，只要小的VAD的上限與大的VAD的下限之間的差值滿(mǎn)足所申請(qǐng)的內(nèi)存塊的大小需求，即可使用二者之間的虛擬內(nèi)存。
（2）當(dāng)?shù)谝辉L問(wèn)提交的內(nèi)存時(shí)，虛擬內(nèi)存管理器總是假定要訪問(wèn)的數(shù)據(jù)所在數(shù)據(jù)頁(yè)已經(jīng)在物理內(nèi)存中，并進(jìn)行虛擬地址到物理地址映射。當(dāng)找到相應(yīng)的頁(yè)目錄項(xiàng)后發(fā)現(xiàn)頁(yè)目錄項(xiàng)并沒(méi)有指向一個(gè)合法的頁(yè)表，虛擬內(nèi)存管理器就會(huì)查找進(jìn)程的VAD樹(shù)，找到包含該地址的VAD，并根據(jù)VAD中的信息，比如內(nèi)存塊大小、范圍，以及在調(diào)頁(yè)文件中的起始位置，隨需生成相應(yīng)的頁(yè)表項(xiàng)。然后從剛才發(fā)生缺頁(yè)錯(cuò)誤的位置繼續(xù)進(jìn)行地址映射。因此，一個(gè)虛擬內(nèi)存頁(yè)被提交時(shí)，除了在調(diào)頁(yè)文件中開(kāi)辟一個(gè)備份頁(yè)外，不會(huì)生成指向它的頁(yè)表項(xiàng)的頁(yè)表，也不會(huì)填充指向它的頁(yè)表項(xiàng)，更不會(huì)開(kāi)辟真正的物理內(nèi)存頁(yè)，而是直到第一次訪問(wèn)提交頁(yè)時(shí)才會(huì)隨需地從VAD中取得包含該頁(yè)的整個(gè)區(qū)域的信息，生成相應(yīng)頁(yè)表，并填充相應(yīng)頁(yè)的頁(yè)表項(xiàng)。
（3）當(dāng)能夠訪問(wèn)預(yù)留的內(nèi)存時(shí)，虛擬地址管理器進(jìn)行虛擬地址到物理地址的映射，找到相應(yīng)的頁(yè)目錄項(xiàng)后發(fā)現(xiàn)頁(yè)目錄項(xiàng)并沒(méi)有指向一個(gè)合法的頁(yè)表，虛擬地址管理器就會(huì)查找進(jìn)程的VAD樹(shù)，找到包含該地址的VAD，此時(shí)發(fā)現(xiàn)此段內(nèi)存塊只是預(yù)留的，而沒(méi)有提交，即沒(méi)有對(duì)應(yīng)物理內(nèi)存，直接拋出訪問(wèn)違例，進(jìn)程退出。
（4）當(dāng)訪問(wèn)自由的內(nèi)存時(shí)，虛擬地址內(nèi)存管理器進(jìn)行虛擬地址到物理地址的映射，找到相應(yīng)的頁(yè)目錄項(xiàng)后發(fā)現(xiàn)頁(yè)目錄項(xiàng)并沒(méi)有指向一個(gè)合法的頁(yè)表，虛擬地址管理器就會(huì)查找進(jìn)程的VAD樹(shù)，發(fā)現(xiàn)并沒(méi)有VAD包含此虛擬地址，發(fā)現(xiàn)此虛擬地址所在的虛擬內(nèi)存頁(yè)是自由狀態(tài)，直接拋出訪問(wèn)違例，進(jìn)程退出。
6、進(jìn)程工作集
因?yàn)轭l繁的調(diào)頁(yè)操作引起的磁盤(pán)IO會(huì)大大降低程序的運(yùn)行效率，因此對(duì)每一個(gè)進(jìn)程，虛擬內(nèi)存管理器都會(huì)將一定量的內(nèi)存頁(yè)駐留在物理內(nèi)存中，并跟蹤其執(zhí)行的性能指標(biāo)，并動(dòng)態(tài)調(diào)整駐留的內(nèi)存頁(yè)數(shù)量。Win32中駐留在物理內(nèi)存中的內(nèi)存頁(yè)稱(chēng)為進(jìn)程的工作集（working set），進(jìn)程的工作集可以通過(guò)任務(wù)管理器查看，內(nèi)存使用列即為工作集大小。
工作集是會(huì)動(dòng)態(tài)變化的，進(jìn)程初始時(shí)只有很少的代碼頁(yè)和數(shù)據(jù)頁(yè)被調(diào)入物理內(nèi)存。當(dāng)執(zhí)行到未被調(diào)入內(nèi)存的代碼或訪問(wèn)到尚未調(diào)入內(nèi)存的數(shù)據(jù)時(shí)，相應(yīng)代碼頁(yè)或數(shù)據(jù)頁(yè)會(huì)被調(diào)入物理內(nèi)存，工作集也會(huì)隨之增加。但工作集不能無(wú)限增加，系統(tǒng)為每個(gè)進(jìn)程設(shè)定了一個(gè)最小工作集和最大工作集，當(dāng)工作集達(dá)到最大工作集大小，進(jìn)程需要再次調(diào)入新頁(yè)到物理內(nèi)存時(shí)，虛擬內(nèi)存管理器會(huì)架構(gòu)原來(lái)工作集中某些內(nèi)存頁(yè)先置換出物理內(nèi)存，然后再將需要調(diào)入的新頁(yè)調(diào)入內(nèi)存。
因?yàn)楣ぷ骷捻?yè)駐留在物理內(nèi)存中，對(duì)工作集頁(yè)的訪問(wèn)不會(huì)涉及磁盤(pán)IO，因此速度非常快。如果訪問(wèn)的代碼或數(shù)據(jù)不在工作集中，會(huì)引發(fā)額外的磁盤(pán)IO，從而降低程序的執(zhí)行效率。極端情況下會(huì)出現(xiàn)所謂的顛簸或抖動(dòng)（thrashing），即程序的大部分執(zhí)行時(shí)間都花在調(diào)頁(yè)操作上，而不是執(zhí)行代碼上。
虛擬內(nèi)存管理器在調(diào)頁(yè)時(shí)，不僅僅只是調(diào)入需要的頁(yè)，同時(shí)還將其附近的頁(yè)一起調(diào)入內(nèi)存中，對(duì)于開(kāi)發(fā)人員，如果要提高程序的運(yùn)行效率需要考慮如下：
（1）對(duì)代碼李碩，盡量編寫(xiě)緊湊代碼，最理想情形是工作集不會(huì)達(dá)到最大閾值，在每次調(diào)入新頁(yè)時(shí)，就不需要置換已經(jīng)載入的內(nèi)存頁(yè)，因?yàn)楦鶕?jù)locality特性，以前執(zhí)行的代碼和訪問(wèn)的數(shù)據(jù)在后面有很大可能會(huì)被再次執(zhí)行好訪問(wèn)，因此程序執(zhí)行時(shí)，缺頁(yè)錯(cuò)誤會(huì)大大降低，即減少磁盤(pán)IO。從進(jìn)程任務(wù)管理器也可以查看一個(gè)進(jìn)程從開(kāi)始時(shí)到當(dāng)前時(shí)刻共發(fā)生的缺頁(yè)錯(cuò)誤次數(shù)。即使不能達(dá)到理想情形，緊湊的代碼往往意味著接下來(lái)執(zhí)行的代碼更大可能就在當(dāng)前頁(yè)或相鄰頁(yè)。根據(jù)時(shí)間locality特性，程序80%的時(shí)間花費(fèi)在20%代碼上，如果能將耗時(shí)的20%代碼盡量緊湊且排在一起，會(huì)大大提高程序的整體性能。
（2）對(duì)數(shù)據(jù)來(lái)說(shuō)，盡量將那些會(huì)一起訪問(wèn)的數(shù)據(jù)（如鏈表）放在一起，當(dāng)訪問(wèn)數(shù)據(jù)時(shí)，數(shù)據(jù)在同一頁(yè)或相鄰頁(yè)，只需要一次調(diào)頁(yè)操作就可以完成。如果數(shù)據(jù)分散在分散在多個(gè)頁(yè)（多個(gè)頁(yè)不相鄰），每次對(duì)數(shù)據(jù)的整體訪問(wèn)都會(huì)引發(fā)大量的缺頁(yè)錯(cuò)誤，從而降低性能。利用Win32提供的預(yù)留和提交兩步機(jī)制，可以為一同訪問(wèn)的數(shù)據(jù)預(yù)留一大塊空間，此時(shí)并沒(méi)有分配實(shí)際存儲(chǔ)空間，而是在后續(xù)執(zhí)行過(guò)程中生成數(shù)據(jù)時(shí)格局需要提交內(nèi)存，既不浪費(fèi)存儲(chǔ)空間（物理內(nèi)存和磁盤(pán)的調(diào)頁(yè)文件存儲(chǔ)空間），又能利用locality特性。
三、Linux內(nèi)存管理
1、Linux內(nèi)存管理機(jī)制簡(jiǎn)介
Linux的內(nèi)存管理主要分為兩部分，一部分負(fù)責(zé)物理內(nèi)存的申請(qǐng)與釋放，物理內(nèi)存的申請(qǐng)與釋放的最小單位為頁(yè)，在IA32中，頁(yè)的大小為4KB；另一部分負(fù)責(zé)處理虛擬內(nèi)存，虛擬內(nèi)存的主要操作包括虛擬地址空間與物理地址空間的映射，物理內(nèi)存頁(yè)與磁盤(pán)頁(yè)之間的置換等。
2、Linux進(jìn)程的內(nèi)存布局
一個(gè)32位Linux進(jìn)程的地址空間為4GB，其中高位1GB，即0XC0000000--0XFFFFFFFF，為內(nèi)核空間，低位3GB，即0X00000000--0XBFFFFFFF為用戶(hù)地址空間。用戶(hù)地址空間進(jìn)一步被分為程序代碼區(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)用程序的機(jī)器代碼，運(yùn)行過(guò)程中代碼不能修改，因此代碼區(qū)內(nèi)存為只讀，且大小固定。數(shù)據(jù)區(qū)中存放應(yīng)用程序的全局?jǐn)?shù)據(jù)，靜態(tài)數(shù)據(jù)和常量字符串，數(shù)據(jù)區(qū)大小也是固定的。
堆從未初始化數(shù)據(jù)區(qū)開(kāi)始，向上端動(dòng)態(tài)增長(zhǎng)，增長(zhǎng)過(guò)程中虛擬地址值變大；棧從高位地址開(kāi)始，向下動(dòng)態(tài)增長(zhǎng)，虛擬地址值變小。
堆是應(yīng)用程序在運(yùn)行過(guò)程中動(dòng)態(tài)申請(qǐng)的內(nèi)存空間，如通過(guò)malloc/new動(dòng)態(tài)生成對(duì)象或開(kāi)辟內(nèi)存空間時(shí)，最終會(huì)調(diào)用系統(tǒng)調(diào)用brk來(lái)動(dòng)態(tài)調(diào)整數(shù)據(jù)區(qū)的大小。當(dāng)申請(qǐng)的動(dòng)態(tài)內(nèi)存區(qū)域使用完畢，需要開(kāi)發(fā)者明確使用相應(yīng)的free/delete對(duì)申請(qǐng)的動(dòng)態(tài)內(nèi)存空間進(jìn)行釋放，free/delete最終也會(huì)使用brk系統(tǒng)調(diào)用調(diào)整數(shù)據(jù)區(qū)的大小。
棧是用來(lái)存放函數(shù)的傳入?yún)?shù)、臨時(shí)變量以及返回地址等數(shù)據(jù)，不需要通過(guò)malloc/new開(kāi)辟空間，棧的增長(zhǎng)與縮減是因?yàn)楹瘮?shù)的調(diào)用與返回，不需要開(kāi)發(fā)人員操作，沒(méi)有內(nèi)存泄漏的危險(xiǎn)。
初始化數(shù)據(jù)區(qū)存放的是編譯期就能夠知道由程序設(shè)定初始值的全局變量及靜態(tài)變量等，其初始值必須保存在最終生成的二進(jìn)制文件中，并且在程序運(yùn)行時(shí)會(huì)原封不動(dòng)地將此區(qū)域映射到進(jìn)程的初始化數(shù)據(jù)區(qū)。如果一個(gè)全局變量或靜態(tài)變量在源代碼中沒(méi)有被賦初始值，在程序啟動(dòng)后，在第一次被賦值前，其初始值為0，本質(zhì)上是有初始值的，其初始值為0。但當(dāng)最終生成二進(jìn)制文件時(shí)，未初始化數(shù)據(jù)區(qū)不會(huì)占據(jù)對(duì)應(yīng)變量總大小的區(qū)域，而是只用一個(gè)值進(jìn)行標(biāo)識(shí)其未初始化數(shù)據(jù)區(qū)的總大小。如一個(gè)程序的代碼指令有100KB，所有初始化數(shù)據(jù)總大小為100KB，所有未初始化數(shù)據(jù)總大小為150KB，則在最終生成的二進(jìn)制文件中代碼區(qū)有100KB，接著是100KB的初始化數(shù)據(jù)區(qū)，然后是4字節(jié)的大小空間，用于標(biāo)記未初始化數(shù)據(jù)區(qū)大小，其值為150X1024，用于節(jié)省磁盤(pán)空間。但在進(jìn)程虛擬地址空間中，對(duì)應(yīng)未初始化數(shù)據(jù)區(qū)的大小必須是150KB，因?yàn)樵诔绦蜻\(yùn)行時(shí)，程序必須真正能夠訪問(wèn)到變量中的每一個(gè)，即當(dāng)程序啟動(dòng)時(shí)，當(dāng)檢測(cè)到二進(jìn)制文件中未初始化數(shù)據(jù)區(qū)的值為150X1024，則系統(tǒng)會(huì)開(kāi)辟出150KB大小的區(qū)域作為進(jìn)程的未初始化數(shù)據(jù)區(qū)并同時(shí)使用0對(duì)其進(jìn)行初始化。
3、Linux物理內(nèi)存管理
物理內(nèi)存是用來(lái)存放代碼指令與供代碼指令操作的數(shù)據(jù)的最終場(chǎng)所，因此物理內(nèi)存的管理是內(nèi)存管理系統(tǒng)極其重要的任務(wù)。Linux使用頁(yè)分配器（page allocator）來(lái)管理物理內(nèi)存，頁(yè)分配器負(fù)責(zé)分配和回收所有的物理內(nèi)存頁(yè)（物理內(nèi)存的分配與回收的最小單位為4KB大小的頁(yè)）。
頁(yè)分配器的核心算法稱(chēng)為兄弟堆算法（buddy-heap algorithm），算法思想是每個(gè)物理內(nèi)存區(qū)域都會(huì)有一個(gè)與之相鄰的所謂兄弟區(qū)域，當(dāng)兩個(gè)區(qū)域被回收后，會(huì)被合并成為一個(gè)區(qū)域。如果被合并區(qū)域的相鄰區(qū)域也被回收后，會(huì)被進(jìn)一步合并為更大的區(qū)域。當(dāng)有物理內(nèi)存請(qǐng)求到來(lái)時(shí)，頁(yè)分配器會(huì)首先檢測(cè)是否有大小與之一致的區(qū)域。如果有，直接使用找到的匹配區(qū)域滿(mǎn)足請(qǐng)求；如果沒(méi)有，則找到更大的一個(gè)區(qū)域，并繼續(xù)劃分，直到分出的區(qū)域能夠滿(mǎn)足請(qǐng)求。為了配合兄弟堆算法，必須有鏈表來(lái)記錄自由的物理內(nèi)存區(qū)域，對(duì)于每個(gè)相同大小的自由區(qū)域，會(huì)有一個(gè)鏈表將其連接，每種大小的區(qū)域都會(huì)有一個(gè)鏈表對(duì)其進(jìn)行管理。自由區(qū)域的大小都是2的冪。
當(dāng)有一個(gè)8KB大小的內(nèi)存請(qǐng)求到來(lái)，當(dāng)前最小可供分配的區(qū)域?yàn)?4KB，此時(shí)64KB會(huì)被劃分為兩個(gè)32KB，繼而將低位的32KB繼續(xù)劃分為兩個(gè)16KB大小的區(qū)域，再將最低位的16KB大小區(qū)域劃分為兩個(gè)8KB大小的區(qū)域，然后分配高位的8KB區(qū)域滿(mǎn)足請(qǐng)求。
4、Linux虛擬內(nèi)存管理
虛擬內(nèi)存管理器的主要任務(wù)是維護(hù)應(yīng)用程序的虛擬地址空間使用信息，如哪些區(qū)域已經(jīng)被使用（映射），是否有磁盤(pán)文件作為備份存儲(chǔ)。如果有，每個(gè)區(qū)域?qū)?yīng)在磁盤(pán)的哪個(gè)區(qū)域，另外一個(gè)重要功能就是調(diào)頁(yè)，如程序訪問(wèn)某些尚未調(diào)至物理內(nèi)存的數(shù)據(jù)時(shí)，虛擬內(nèi)存管理器負(fù)責(zé)定位數(shù)據(jù)，并將其置換進(jìn)物理內(nèi)存。如果物理內(nèi)存此時(shí)沒(méi)有自由頁(yè)，還需要將物理內(nèi)存中的某些頁(yè)先置換出去。
用來(lái)維護(hù)應(yīng)用程序的虛擬地址空間使用信息的數(shù)據(jù)結(jié)構(gòu)是vm_area_struct。每個(gè)vm_area_struct結(jié)構(gòu)體都描述了一個(gè)進(jìn)程虛擬地址空間中被分配的區(qū)域，當(dāng)vm_area_struct個(gè)數(shù)不超過(guò)32個(gè)時(shí)，被連接成為一個(gè)鏈表；當(dāng)超過(guò)32個(gè)時(shí)，所有的vm_area_struct會(huì)被組織為一棵自平衡二叉樹(shù)，利于提高查詢(xún)速度。當(dāng)程序通過(guò)某個(gè)指針訪問(wèn)某個(gè)數(shù)據(jù)時(shí)，系統(tǒng)會(huì)查詢(xún)vm_area_struct樹(shù)，如果發(fā)現(xiàn)指針沒(méi)有落在任何一個(gè)vm_area_struct所表示的區(qū)域內(nèi)，則判定指針?biāo)淼牡刂窙](méi)有被分配，即非法的指針訪問(wèn)。
5、虛擬地址映射為物理地址
當(dāng)通過(guò)程序的指針訪問(wèn)某個(gè)數(shù)據(jù)時(shí)，因?yàn)橹羔槺举|(zhì)是一個(gè)虛擬地址值，因此虛擬地址值必須被轉(zhuǎn)化為物理地址值，才能真正訪問(wèn)其所指代的數(shù)據(jù)。
Linux使用三層映射策略將一個(gè)虛擬地址映射為一個(gè)物理地址。與Windows相比，多了Middle層，當(dāng)對(duì)于IA32體系，Middle層沒(méi)有用，因此Linux與Windows相同。
分享題目：C++應(yīng)用程序性能優(yōu)化（五）——操作系統(tǒng)的內(nèi)存管理
URL分享：http://www.dlmjj.cn/article/gggcci.html
