內(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ù)也可以合并。
