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