基本概念
內(nèi)存是現(xiàn)在計(jì)算機(jī)運(yùn)行的核心。CPU可以直接訪問的通用存儲(chǔ)只有內(nèi)存和處理器的內(nèi)置寄存器。機(jī)器指令可以用內(nèi)存地址作為參數(shù)薛躬,但是磁盤地址不可以。
在訪問速度上僧界,寄存器的內(nèi)容一般都可以在一個(gè)時(shí)鐘周期解釋并執(zhí)行完侨嘀。但是對于內(nèi)存,可能需要多個(gè)時(shí)鐘周期捂襟。所以為了訪問速度上能更加快速咬腕,一般會(huì)有高速緩存。
在系統(tǒng)安全上葬荷,首先涨共,用戶的進(jìn)程不能影響操作系統(tǒng)的執(zhí)行; 在多用戶系統(tǒng)上,還應(yīng)該保護(hù)不同的進(jìn)程之間不能互相影響宠漩。所以一般會(huì)有專門的硬件方式來進(jìn)行保護(hù)举反。
為了進(jìn)程之間不會(huì)相互影響,首先扒吁,我們需要確保每個(gè)進(jìn)程都有一個(gè)單獨(dú)的內(nèi)存空間火鼻。單獨(dú)的進(jìn)程內(nèi)存空間可以保護(hù)進(jìn)程不互相影響。
為了分開內(nèi)存空間雕崩,我們需要能夠確定一個(gè)進(jìn)程可以訪問的合法地址的范圍魁索;并且確保該進(jìn)程只能訪問這些合法地址。 一般通過兩個(gè)寄存器來實(shí)現(xiàn)盼铁, 基地址寄存器和界限地址寄存器粗蔚。
如下圖,如果基地址是300040捉貌,而界限寄存器為120900支鸡,那么程序可以合法訪問到的地址為300040 ~ 420939的所包含的地址。
地址綁定
一般的趁窃,進(jìn)程在執(zhí)行時(shí)牧挣,會(huì)先從磁盤被調(diào)入內(nèi)存,而且根據(jù)內(nèi)存的管理醒陆,有可能在執(zhí)行的時(shí)候瀑构,被換出到磁盤上。但是磁盤的內(nèi)容會(huì)被調(diào)入到物理內(nèi)存的哪個(gè)地方刨摩,這個(gè)就是后面要討論的內(nèi)存分配機(jī)制寺晌。
大多數(shù)系統(tǒng)允許用戶進(jìn)程放在屋里內(nèi)存中的任意位置。也就是說澡刹,物理內(nèi)存的地址是從000000開始的呻征,但是用戶進(jìn)程的地址不必也是000000。
實(shí)際上罢浇,在用戶程序被執(zhí)行前陆赋,會(huì)有很多的步驟沐祷,這些步驟中對地址會(huì)有不同的表示方法。
- 編譯:在程序中攒岛,一般我們不用地址來表示赖临,比如C語言都是按照符號來表示的,在編譯的時(shí)候灾锯,它是一堆符號地址兢榨,編譯器將這些符號地址綁定到可重定向的地址,比如:從本模塊的第 14個(gè)字節(jié)開始顺饮。
- 加載:在上面編譯后吵聪,生成了可重定向地址,那么在加載時(shí)领突,加載器或者鏈接器會(huì)把這些可重定向地址 加上自己在地址空間的基地址暖璧,從而形成絕對地址。
- 執(zhí)行:進(jìn)程在執(zhí)行的時(shí)候君旦,從地址空間中映射到計(jì)算機(jī)的物理地址上澎办。具體映射方法需要先了解下邏輯地址空間和物理地址空間。
邏輯地址空間和物理地址空間
在程序執(zhí)行的時(shí)候金砍,從程序中加載的地址局蚀,稱為邏輯地址。它是一個(gè)照片恕稠,我可以用手指出哪里是這個(gè)人的眼睛琅绅,耳朵,鼻子鹅巍,但是這只是在照片的位置千扶。這個(gè)人本人的肉體才是真正存在的東西。物理地址就好比這個(gè)人的肉體骆捧,是一個(gè)實(shí)際存在的東西澎羞。
加載時(shí)的地址綁定方法生成一個(gè)相同的邏輯地址和物理地址。然而敛苇,執(zhí)行時(shí)妆绞,邏輯地址和物理內(nèi)存上的地址不一定是一樣的。后面內(nèi)存分配會(huì)講到枫攀。
動(dòng)態(tài)加載和動(dòng)態(tài)鏈接
動(dòng)態(tài)加載指的是一個(gè)進(jìn)程只有在執(zhí)行的時(shí)候才被加載括饶,而不是一次性把所有的進(jìn)程全部放進(jìn)內(nèi)存中。
動(dòng)態(tài)鏈接類似于動(dòng)態(tài)加載来涨。但是這里不是加載和是鏈接图焰,會(huì)延遲到運(yùn)行。動(dòng)態(tài)鏈接這里鏈接的一般稱為動(dòng)態(tài)鏈接庫蹦掐。它是系統(tǒng)庫楞泼,一般會(huì)駐留在內(nèi)存中驰徊,供所有的用戶程序使用。
它的原理是:當(dāng)程序中有動(dòng)態(tài)鏈接堕阔,在二進(jìn)制文件中,每個(gè)庫程序的引用都會(huì)有個(gè)存根(stub)颗味。存根是一小段代碼超陆,用來指出如何定位適當(dāng)?shù)膬?nèi)存駐留庫程序,以及不在內(nèi)存時(shí)浦马,如何加載时呀。
動(dòng)態(tài)鏈接庫的好處是,一個(gè)庫的更新晶默,所有使用它的程序都會(huì)自動(dòng)使用新的版本谨娜。
交換
最后一個(gè)基本概念是交換(swap)。進(jìn)程可以暫時(shí)從內(nèi)存交換到備份存儲(chǔ)中磺陡,當(dāng)再次執(zhí)行的時(shí)候趴梢,再調(diào)回到內(nèi)存中。
標(biāo)準(zhǔn)交換
這種交換和概念定義的一樣币他,一般備份存儲(chǔ)為磁盤坞靶。
這種交換的上下文切換時(shí)間相當(dāng)高,假設(shè)用戶進(jìn)程大小為100MB,并且磁盤的傳輸速度為50M/s蝴悉, 那么換人和換成分別需要2s,加起來可能需要4s彰阴。
交換也受到其他因素的約束,如果我們想要換出一個(gè)進(jìn)程拍冠,那么確保該進(jìn)程是完全處于空閑的尿这。特別需要關(guān)注等待I/O。當(dāng)需要換出一個(gè)進(jìn)程以釋放內(nèi)存時(shí)庆杜,該進(jìn)程可能正在等待I/O操作射众。
然而如果I/O異步訪問用戶內(nèi)存的I/O緩沖區(qū),那么該進(jìn)程就不能被換出欣福。假定由于設(shè)備忙责球,I/O操作正在排隊(duì)等待。如果我們需要換出P1進(jìn)程而執(zhí)行P2進(jìn)程拓劝,那么I/O操作可能試圖使用現(xiàn)在已經(jīng)屬于進(jìn)程P2的內(nèi)存雏逾。
解決的辦法有兩種:
- 不能換出等待處理I/O的進(jìn)程
- I/O操作的執(zhí)行只能操作系統(tǒng)的緩沖池。
只有在進(jìn)程進(jìn)入時(shí)郑临,操作系統(tǒng)緩沖才能與進(jìn)程之間進(jìn)行數(shù)據(jù)遷移栖博。但是這增加了開銷。
移動(dòng)設(shè)備的交換
雖然用于PC和服務(wù)器的大多數(shù)操作系統(tǒng)都支持一些交換厢洞。但是移動(dòng)設(shè)備通常不支持任何形式的交換仇让。
移動(dòng)設(shè)備通常是閃存(U盤典奉,內(nèi)存卡)而不是更大空間的硬盤。所以這是不支持交換的一個(gè)原因之一丧叽。還有一些原因就是卫玖,閃存和內(nèi)存之間的數(shù)據(jù)交換的吞吐量差。
蘋果的IOS系統(tǒng)踊淳,當(dāng)空閑內(nèi)存降低到一定的閾值時(shí)假瞬,不是采用交換,而是要求應(yīng)用程序資源放棄分配的內(nèi)存迂尝,只讀數(shù)據(jù)可以從系統(tǒng)中刪除脱茉,以后如有必要再從閃存中重新加載。它修改的數(shù)據(jù)不會(huì)被刪除,然而, 操作系統(tǒng)可以終止任意的未能釋放足夠多內(nèi)存的用戶程序趣钱。
Android系統(tǒng)不支持交換。而當(dāng)沒有足夠內(nèi)存的時(shí)候榜田,系統(tǒng)可以終止任何進(jìn)程。但是他在刪除前會(huì)把應(yīng)用程序的狀態(tài)寫入到閃存签财,以便后面快速啟動(dòng)串慰。
由于這些限制,所以移動(dòng)的程序員應(yīng)該小心分配內(nèi)存唱蒸,避免有資源泄露邦鲫。
內(nèi)存分配
我們通常需要把多個(gè)進(jìn)程同時(shí)放在內(nèi)存中,因此我們需要進(jìn)程內(nèi)存分配神汹。一般內(nèi)存分為兩個(gè)區(qū)域:一個(gè)用于駐留在操作系統(tǒng)中庆捺,另一個(gè)用于用戶進(jìn)程。操作系統(tǒng)可以放在高位置屁魏,也可以放在低內(nèi)存滔以,影響這一決定的通常為中斷向量的位置。一般PC是放在低內(nèi)存位置的氓拼。
分區(qū)
內(nèi)存分配最簡單的分配方式就是:將內(nèi)存分為多個(gè)固定大小的分區(qū)你画。每個(gè)分區(qū)可以包含一個(gè)進(jìn)程,因此桃漾,多道程序設(shè)計(jì)的受限于分區(qū)數(shù)坏匪。使用這種多分區(qū)方法,那么當(dāng)一個(gè)分區(qū)空閑時(shí)撬统,可以從進(jìn)程的就輸入隊(duì)列中選擇一個(gè)進(jìn)程适滓,加載到空閑分區(qū)。雖然這種方案在現(xiàn)在的操作系統(tǒng)中已經(jīng)不用恋追,但是它的思想為后面很多內(nèi)存分配提供了思想凭迹。
除此之外罚屋,還有一個(gè)可變分區(qū)方案,它的主要思想是:
操作系統(tǒng)有一個(gè)表嗅绸,用于記錄哪些內(nèi)存可用脾猛,哪些內(nèi)存已經(jīng)使用。
開始朽砰,所有的內(nèi)存都有可用于用戶進(jìn)程尖滚,因此可以看做是一個(gè)很大的內(nèi)存。隨著進(jìn)程進(jìn)入系統(tǒng)瞧柔,操作系統(tǒng)根據(jù)所有進(jìn)程的內(nèi)存需要和現(xiàn)有的內(nèi)存情況,決定哪些系統(tǒng)可分配內(nèi)存睦裳。
在任何時(shí)候造锅,都有一個(gè)可用塊大小的列表和一個(gè)輸入隊(duì)列。操作系統(tǒng)根據(jù)調(diào)度算法來對輸入隊(duì)列進(jìn)行排序廉邑。內(nèi)存不斷地分配給進(jìn)程哥蔚,直到下一個(gè)進(jìn)程的內(nèi)存需求不能滿足為止,這時(shí)沒有足夠大的可用塊來加載進(jìn)程蛛蒙〔诠浚或者繼續(xù)往下掃描,輸入隊(duì)列牵祟,看看有沒有其他內(nèi)存需求比較小的進(jìn)程可以被滿足深夯。
動(dòng)態(tài)存儲(chǔ)分配問題
通常,按上面的分配算法诺苹,可用的內(nèi)存塊分散在內(nèi)存里的不同大小的孔(這里既是一個(gè)一個(gè)小的內(nèi)存塊)的集合咕晋。當(dāng)進(jìn)程需要內(nèi)存時(shí),系統(tǒng)為該進(jìn)程查找足夠大的空收奔,如果孔太大掌呜,那么就分為兩塊:一塊分配給內(nèi)存,另一塊還給孔集合坪哄。當(dāng)進(jìn)程終止時(shí)质蕉,他將釋放內(nèi)存,該內(nèi)存將還給孔集合翩肌。
如果新孔與其他孔相鄰模暗,那么將這個(gè)孔合并成一個(gè)大孔。這是系統(tǒng)繼續(xù)檢測摧阅,有沒有符合要求的處于等待的進(jìn)程汰蓉。
這種分配方法被稱為動(dòng)態(tài)存儲(chǔ)分配問題。 這種方法在我們程序設(shè)計(jì)中有很多的例子棒卷,比如(C++STL的內(nèi)存分配顾孽,memory cache)祝钢。
這種方法有許多變種,其中根據(jù)從一組可用的孔中選擇一個(gè)空閑孔的最為常用的方法包括: 首次適應(yīng)若厚, 最優(yōu)適應(yīng)拦英,最差適應(yīng)。
- 首次適應(yīng):分配首個(gè)足夠大的空测秸。查找從頭開始疤估,也可以從上次首次適應(yīng)結(jié)束的時(shí)候開始,尋找一個(gè)足夠大的空閑孔霎冯,分配個(gè)進(jìn)程铃拇。
- 最優(yōu)適應(yīng): 分配足夠小的孔,只要可以滿足進(jìn)程的內(nèi)存需求沈撞。需要查找整個(gè)列表慷荔,所以可能要求,列表按大小進(jìn)程排序缠俺,以便更快速的找到最小滿足的孔显晶。
- 最差適應(yīng): 分配最大的孔。這個(gè)和最優(yōu)相對壹士,也要查找整個(gè)列表磷雇。
經(jīng)過模擬顯示:首次適應(yīng)和最優(yōu)適應(yīng)的執(zhí)行效果和空間利用方面都要優(yōu)于最差適應(yīng)。
碎片
外部碎片:根據(jù)上面的三種算法躏救,隨著進(jìn)程的加載到內(nèi)存和從內(nèi)存退出唯笙,空閑內(nèi)存空間被分為小的片段。當(dāng)總的可用內(nèi)存紙盒可以滿足請求但并不連續(xù)時(shí)落剪,他不能分配給進(jìn)程睁本。這些 不連續(xù)的內(nèi)存塊就成了碎片了。
內(nèi)部碎片: 假設(shè)有一個(gè)1800字節(jié)的碎片忠怖,并采取上面的算法進(jìn)行分配呢堰,進(jìn)程需要1798 的內(nèi)存。那么分配完了以后凡泣,就剩下兩個(gè)字節(jié)枉疼,這兩個(gè)字節(jié)也需要維護(hù),但是維護(hù)的代價(jià)比他本身的價(jià)值要大的多鞋拟,所以在分配的時(shí)候骂维,把這兩個(gè)字節(jié)也分配給進(jìn)程,那么這兩個(gè)字節(jié)就在進(jìn)程內(nèi)部形成了碎片贺纲。
在清理內(nèi)存碎片的時(shí)候航闺,我們有兩種解決方案:
- 把所有的進(jìn)程的移到內(nèi)存的一端,把孔移到另一端,但是這種代價(jià)太高潦刃。
- 允許進(jìn)程的邏輯地址空間不是連續(xù)的; 從而讓代碼和數(shù)據(jù)分離侮措,進(jìn)程在使用的時(shí)候,當(dāng)物理內(nèi)存可用,就允許進(jìn)程分配內(nèi)存, 然后根據(jù)不同的基地址寄存器和界限寄存器來控制和保護(hù)進(jìn)程的內(nèi)存乖杠。 也就是分段和分頁技術(shù)分扎。