內(nèi)存必須容納操作系統(tǒng)和各種用戶進(jìn)程,因此應(yīng)該盡可能有效的分配內(nèi)存的各個(gè)部分。
內(nèi)存通常分為兩個(gè)區(qū)域,一個(gè)用于駐留操作系統(tǒng),另一個(gè)用于用戶進(jìn)程。操作系統(tǒng)可以位于低內(nèi)存,也可以位于高內(nèi)存,影響這一決定的主要因素是中斷向量的位置,由于中斷向量通常位于低內(nèi)存,因此程序員通常將操作系統(tǒng)頁放在低內(nèi)存。
內(nèi)存映射與保護(hù)
在說內(nèi)存分配之前,先說說內(nèi)存映射與保護(hù)的問題,通過采用重定位寄存器和界限地址寄存器,可以實(shí)現(xiàn)這種保護(hù)。
重定位寄存器含有最小的物理地址值,界限地址寄存器含有邏輯地址的范圍值(例如:重定位=100050, 界限=74500)。有了重定位寄存器和界限地址寄存器,每個(gè)邏輯地址必須小于界限地址寄存器。MMU動(dòng)態(tài)的將邏輯地址加上重定位寄存器的值后映射成物理地址,映射后的物理地址再交送內(nèi)存單元。
當(dāng)CPU調(diào)度器選擇一個(gè)進(jìn)程來執(zhí)行時(shí),作為上下文切換工作的一部分,調(diào)度程序會(huì)用正確的值來初始化重定位寄存器和界限地址寄存器。由于CPU所產(chǎn)生的每一地址都需要與寄存器進(jìn)行核對(duì),所以可以保證操作系統(tǒng)和其他用戶程序和數(shù)據(jù)不受該進(jìn)程的運(yùn)行所影響。
內(nèi)存分配
現(xiàn)在我們就來討論一下內(nèi)存分配,最簡單的內(nèi)存分配方式之一就是將內(nèi)存分為多個(gè)固定大小的分區(qū)(parttiion)。每個(gè)分區(qū)只能容納一個(gè)進(jìn)程,因此,多道程序的程度會(huì)受到分區(qū)數(shù)所限制。如果使用這種多分區(qū)方法,當(dāng)一個(gè)分區(qū)空閑的時(shí)候,可以從輸入隊(duì)列中選擇一個(gè)進(jìn)程,以調(diào)入到空閑分區(qū),當(dāng)進(jìn)程終止時(shí),其分區(qū)可以被其他進(jìn)程所使用。這種方法最初為IBM OS/360 操作系統(tǒng)所使用,不過現(xiàn)在已經(jīng)不再使用了。
下面來介紹可變分區(qū)方案。在可變分區(qū)方案里,操作系統(tǒng)有一個(gè)表,用于記錄哪些內(nèi)存可用和哪些內(nèi)存已經(jīng)被使用,在一開始,所有的內(nèi)存都可用于用戶進(jìn)程,因此可以作為一大塊可用內(nèi)存,稱為孔(hole)。當(dāng)有新進(jìn)程需要內(nèi)存時(shí),為該進(jìn)程查找足夠大的孔,如果找到,可以從該進(jìn)程分配所需的內(nèi)存,孔內(nèi)未分配的內(nèi)存可以下次再用。
隨著進(jìn)程進(jìn)入系統(tǒng),它們將被加入到輸入隊(duì)列,操作系統(tǒng)根據(jù)所有進(jìn)程的內(nèi)存需要和現(xiàn)有可用內(nèi)存情況來決定哪些進(jìn)程可以分配內(nèi)存。當(dāng)進(jìn)程分配到空間時(shí),它就裝入內(nèi)存,并開始競爭CPU,當(dāng)進(jìn)程終止的時(shí)候,它將釋放內(nèi)存,該內(nèi)存可以被操作系統(tǒng)分配給輸入隊(duì)列中的其他進(jìn)程。
在任意的時(shí)候,有一組可用孔(塊)大小列表和輸入隊(duì)列,操作系統(tǒng)根據(jù)調(diào)度算法來對(duì)輸入隊(duì)列進(jìn)行排序,內(nèi)存不斷地分配給進(jìn)程,直到下一個(gè)進(jìn)程的內(nèi)存需求不能滿足為止,這時(shí)沒有足夠大的可用孔來裝入進(jìn)程。操作系統(tǒng)可以等到有足夠大的空間。或者往下掃描輸入隊(duì)列以確定是否有其他內(nèi)存需求較小的進(jìn)程可以被滿足。
通常,一組不同大小的孔分散在內(nèi)存中,當(dāng)新進(jìn)程需要內(nèi)存時(shí),系統(tǒng)為該進(jìn)程查找足夠大的孔,如果孔太大,那么就分為兩塊:一塊分配新進(jìn)程,另一塊還回到集合。當(dāng)進(jìn)程終止時(shí),它將釋放其內(nèi)存,該內(nèi)存將還給孔集合,如果新孔與其他孔相鄰,那么將這些孔合并成大孔,這時(shí),系統(tǒng)可以檢查是否有進(jìn)程在等待內(nèi)存空間,新合并的內(nèi)存空間是否滿足等待進(jìn)程。
分配方法
上面講的這種方法是通用動(dòng)態(tài)存儲(chǔ)分配問題的一種情況(根據(jù)一組空閑孔來分配大小為 n 的請(qǐng)求)。這個(gè)問題有許多解決方法,從一組可用孔中選擇一個(gè)空閑的最常用方法有首次適應(yīng)(first-fit)、最佳適應(yīng)(best-fit)、最差適應(yīng)(worst-fit)。
- 首席適應(yīng):分配第一個(gè)足夠大的孔,查找可以從頭開始,也可以從上次首次適應(yīng)結(jié)束時(shí)開始,一旦找到足夠大的空閑空間孔,就可以停止。
- 最佳適配: 分配最小的足夠大的孔,必須查找整個(gè)列表,除非列表按大小排序,這種方法可以產(chǎn)生最小剩余孔。
- 最差適應(yīng): 分配最大的孔,同樣,必須查找整個(gè)列表,除非列表按大小排序,這種方法可以產(chǎn)生最大剩余孔,該孔可能比最佳適應(yīng)方法產(chǎn)生的比較剩余孔更為有用。
碎片
首次適應(yīng)方法和最佳適應(yīng)方法都有外部碎片問題,隨著進(jìn)程的裝入和移出內(nèi)存,空閑內(nèi)存被分為小片段,當(dāng)所有總的可用內(nèi)存之和可以滿足請(qǐng)求,但并不連續(xù)時(shí),這就出現(xiàn)了外部碎片的問題。這個(gè)問題可能很嚴(yán)重。在最壞的情況下,每兩個(gè)進(jìn)程之間就有空閑塊(或浪費(fèi))。如果這些內(nèi)存塊是一整塊,那么就可以再運(yùn)行多個(gè)進(jìn)程。
在首次適應(yīng)和最佳適應(yīng)之間的選擇可能會(huì)影響碎片的量(對(duì)一些系統(tǒng)來說首次適應(yīng)更好,對(duì)另一些系統(tǒng)最佳適應(yīng)更好)。另一個(gè)影響因素是從空閑塊的哪端開始分配(頂端還是末端)。不管使用哪種算法,外部碎片始終是個(gè)問題。
根據(jù)內(nèi)存空間總的大小和平均進(jìn)程大小的不同,外部碎片的重要程度頁頁不同,例如,對(duì)采用首次適應(yīng)方法的統(tǒng)計(jì)說明。不管使用什么優(yōu)化,假定有N個(gè)可分配塊,那么可能有0.5N個(gè)外部為外部碎片。即1/3的內(nèi)存可能不能使用。這一特性稱為50%規(guī)則。
一種解決外部碎片的問題的方法是緊縮(compaction),緊縮的目的是移動(dòng)內(nèi)存內(nèi)容,以便所有空間合并成一整塊。但緊縮并非總是可能的。如果重定位是靜態(tài)的,并且在匯編時(shí)或裝入市進(jìn)行的,那么就不能緊縮。緊縮僅在重定位是動(dòng)態(tài)并在運(yùn)行時(shí)可采用。如果地址被動(dòng)態(tài)重定位,可以首先移動(dòng)程序和數(shù)據(jù),然后再根據(jù)新基地址的值來改變基地址寄存器,如果能采用緊縮,還需要評(píng)估其開銷,最簡單的合并算法是簡丹的將所有進(jìn)程移動(dòng)到內(nèi)存的一端,而將所有的孔移到內(nèi)存的另一端,以便生成一個(gè)大的空閑塊,這種方案開銷較大。
另一種可能解決碎片問題的方法是允許物理地址空間為非連續(xù)。這樣只要有物理內(nèi)存就可以為進(jìn)程分配,這種方案有兩種互補(bǔ)的實(shí)現(xiàn)技術(shù): 分頁和分段,這兩種技術(shù)也可以合并。