連續(xù)分配方式，是指為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間。它主要包括單一連續(xù)分配、固定分區(qū)分配和動(dòng)態(tài)分區(qū)分配。

單一連續(xù)分配

內(nèi)存在此方式下分為系統(tǒng)區(qū)和用戶區(qū)，系統(tǒng)區(qū)僅提供給操作系統(tǒng)使用，通常在低地址部分；用戶區(qū)是為用戶提供的、除系統(tǒng)區(qū)之外的內(nèi)存空間。這種方式無(wú)需進(jìn)行內(nèi)存保護(hù)。

這種方式的優(yōu)點(diǎn)是簡(jiǎn)單、無(wú)外部碎片，可以釆用覆蓋技術(shù)，不需要額外的技術(shù)支持。缺點(diǎn)是只能用于單用戶、單任務(wù)的操作系統(tǒng)中，有內(nèi)部碎片，存儲(chǔ)器的利用率極低。

固定分區(qū)分配

固定分區(qū)分配是最簡(jiǎn)單的一種多道程序存儲(chǔ)管理方式，它將用戶內(nèi)存空間劃分為若干個(gè)固定大小的區(qū)域，每個(gè)分區(qū)只裝入一道作業(yè)。當(dāng)有空閑分區(qū)時(shí)，便可以再?gòu)耐獯娴暮髠渥鳂I(yè)隊(duì)列中,選擇適當(dāng)大小的作業(yè)裝入該分區(qū)，如此循環(huán)。

固定分區(qū)分配在劃分分區(qū)時(shí)，有兩種不同的方法：

• 分區(qū)大小相等：用于利用一臺(tái)計(jì)算機(jī)去控制多個(gè)相同對(duì)象的場(chǎng)合，缺乏靈活性。
• 分區(qū)大小不等：劃分為含有多個(gè)較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)。

為便于內(nèi)存分配，通常將分區(qū)按大小排隊(duì)，并為之建立一張分區(qū)說(shuō)明表，其中各表項(xiàng)包括每個(gè)分區(qū)的起始地址、大小及狀態(tài)（是否已分配），如圖(a)所示。當(dāng)有用戶程序要裝入時(shí)，便檢索該表，以找到合適的分區(qū)給予分配并將其狀態(tài)置為”已分配”；未找到合適分區(qū)則拒絕為該用戶程序分配內(nèi)存。存儲(chǔ)空間的分配情況如圖(b)所示。

這種分區(qū)方式存在兩個(gè)問(wèn)題：
一是程序可能太大而放不進(jìn)任何一個(gè)分區(qū)中，這時(shí)用戶不得不使用覆蓋技術(shù)來(lái)使用內(nèi)存空間；
二是主存利用率低，當(dāng)程序小于固定分區(qū)大小時(shí)，也占用了一個(gè)完整的內(nèi)存分區(qū)空間，這樣分區(qū)內(nèi)部有空間浪費(fèi)，這種現(xiàn)象稱為內(nèi)部碎片（已經(jīng)被分配出去的的內(nèi)存空間大于請(qǐng)求所需的內(nèi)存空間）。

固定分區(qū)是可用于多道程序設(shè)計(jì)最簡(jiǎn)單的存儲(chǔ)分配，無(wú)外部碎片，但不能實(shí)現(xiàn)多進(jìn)程共享一個(gè)主存區(qū)，所以存儲(chǔ)空間利用率低。固定分區(qū)分配很少用于現(xiàn)在通用的操作系統(tǒng)中，但在某些用于控制多個(gè)相同對(duì)象的控制系統(tǒng)中仍發(fā)揮著一定的作用。

動(dòng)態(tài)分區(qū)分配

動(dòng)態(tài)分區(qū)分配又稱為可變分區(qū)分配，是一種動(dòng)態(tài)劃分內(nèi)存的分區(qū)方法。這種分區(qū)方法不預(yù)先將內(nèi)存劃分，而是在進(jìn)程裝入內(nèi)存時(shí)，根據(jù)進(jìn)程的大小動(dòng)態(tài)地建立分區(qū)，并使分區(qū)的大小正好適合進(jìn)程的需要。因此系統(tǒng)中分區(qū)的大小和數(shù)目是可變的。

動(dòng)態(tài)分區(qū)在開(kāi)始分配時(shí)是很好的，但是之后會(huì)導(dǎo)致內(nèi)存中出現(xiàn)許多小的內(nèi)存塊。隨著時(shí)間的推移，內(nèi)存中會(huì)產(chǎn)生越來(lái)越多的外部碎片（還沒(méi)有分配出去，但是由于太小而無(wú)法分配給申請(qǐng)空間的新進(jìn)程的內(nèi)存空間空閑塊）。

克服外部碎片可以通過(guò)緊湊(Compaction)技術(shù)來(lái)解決，就是操作系統(tǒng)不時(shí)地對(duì)進(jìn)程進(jìn)行移動(dòng)和整理。但是這需要?jiǎng)討B(tài)重定位寄存器的支持，且相對(duì)費(fèi)時(shí)。緊湊的過(guò)程實(shí)際上類(lèi)似于Windows系統(tǒng)中的磁盤(pán)整理程序，只不過(guò)后者是對(duì)外存空間的緊湊。

常見(jiàn)的動(dòng)態(tài)分區(qū)的分配策略如下：

• 首次適應(yīng)(First Fit)算法：
  空閑分區(qū)以地址遞增的次序鏈接。分配內(nèi)存時(shí)順序查找，找到大小能滿足要求的第一個(gè)空閑分區(qū)。該算法傾向于優(yōu)先利用內(nèi)存中低地址的空閑部分，保留高地址部分的大空閑區(qū)，為以后到達(dá)的大作業(yè)分配大空間創(chuàng)造條件。其缺點(diǎn)在于：低地址部分由于不斷被劃分，會(huì)留下許多難以利用的小空閑分區(qū)，并且，每次都從低地址開(kāi)始檢索，將增大可用空閑區(qū)間查找的開(kāi)銷(xiāo)。

• 最佳適應(yīng)(Best Fit)算法：
  空閑分區(qū)按容量遞增形成分區(qū)鏈，找到第一個(gè)能滿足要求的空閑分區(qū)，即找到一個(gè)滿足要求且最小的空閑分區(qū)分配給作業(yè)。孤立地看，最佳適應(yīng)算法看似是最佳的，但是宏觀看并非如此，存儲(chǔ)器將留下許多難以利用的小空閑區(qū)。

• 最壞適應(yīng)(Worst Fit)算法：
  又稱最大適應(yīng)(Largest Fit)算法，空閑分區(qū)以容量遞減的次序鏈接。找到第一個(gè)能滿足要求的空閑分區(qū)，也就是挑選出最大的分區(qū)。
  該算法優(yōu)點(diǎn)是使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的幾率最小，對(duì)中小作業(yè)有利，但對(duì)大作業(yè)不利。

• 循環(huán)首次適應(yīng)(Next Fit)算法：
  又稱鄰近適應(yīng)算法，由首次適應(yīng)算法演變而成。不同之處是分配內(nèi)存時(shí)從上次查找結(jié)束的位置開(kāi)始繼續(xù)查找。該算法能使內(nèi)存中的空閑分區(qū)分布得更均勻，從而減少了查找空閑分區(qū)的開(kāi)銷(xiāo)，但這樣會(huì)缺乏大的空閑分區(qū)。

以上四種算法稱為順序搜索法，快速適應(yīng)算法又稱為分類(lèi)搜索算法：

• 快速適應(yīng)(Quick Fit)算法：
  該算法將空閑分區(qū)按照大小進(jìn)行分類(lèi)，對(duì)每一類(lèi)具有相同容量的所有空閑分區(qū)，單獨(dú)設(shè)置一個(gè)空閑分區(qū)鏈表。分類(lèi)通常常用空間大小進(jìn)行劃分，比如2KB,4KB,8KB等。僅需要根據(jù)進(jìn)程的長(zhǎng)度檢索，找到能容納它的最小空閑區(qū)鏈表，進(jìn)行分配。
  該算法優(yōu)點(diǎn)是查找效率高，能夠保留大的分區(qū)，滿足用戶對(duì)大空間的需求。缺點(diǎn)在于分區(qū)歸還主存時(shí)算法復(fù)雜，系統(tǒng)開(kāi)銷(xiāo)較大，而且存在一定的空間浪費(fèi)，是典型空間換時(shí)間的做法。

伙伴系統(tǒng)

Linux內(nèi)核內(nèi)存管理中采用伙伴系統(tǒng)解決外部碎片問(wèn)題。伙伴系統(tǒng)的宗旨就是用最小的內(nèi)存塊來(lái)滿足內(nèi)核的對(duì)于內(nèi)存的請(qǐng)求。

伙伴系統(tǒng)在回收空閑分區(qū)時(shí)，需要對(duì)空閑分區(qū)進(jìn)行合并，其時(shí)間性能比前述分類(lèi)搜索差，但比順序搜索算法好，而其空間性能則遠(yuǎn)優(yōu)于分類(lèi)搜索算法，比順序搜索算法略差?；锇橄到y(tǒng)在多處理機(jī)系統(tǒng)中，仍不失為一種有效的內(nèi)存分配和釋放的方法，得到了大量的應(yīng)用。

分配過(guò)程舉例：

在最初，只有一個(gè)塊，也就是整個(gè)內(nèi)存，假如為1M大小，而允許的最小塊為64K，那么當(dāng)我們申請(qǐng)一塊200K大小的內(nèi)存時(shí)，就要先將1M的塊分裂成兩等分，各為512K，這兩分之間的關(guān)系就稱為伙伴，然后再將第一個(gè)512K的內(nèi)存塊分裂成兩等分，各位256K，將第一個(gè)256K的內(nèi)存塊分配給內(nèi)存，這樣就是一個(gè)分配的過(guò)程。下面我們結(jié)合示意圖來(lái)了解伙伴系統(tǒng)分配和回收內(nèi)存塊的過(guò)程。

• 1 初始化時(shí)，系統(tǒng)擁有1M的連續(xù)內(nèi)存，允許的最小的內(nèi)存塊為64K，圖中白色的部分為空閑的內(nèi)存塊，著色的代表分配出去了得內(nèi)存塊。

• 2 程序A申請(qǐng)一塊大小為34K的內(nèi)存，對(duì)應(yīng)的order為0，即2^0=1個(gè)最小內(nèi)存塊
  　　2.1 系統(tǒng)中不存在order 0(64K)的內(nèi)存塊，因此order 4(1M)的內(nèi)存塊分裂成兩個(gè)order 3的內(nèi)存塊(512K)
  　　2.2 仍然沒(méi)有order 0的內(nèi)存塊，因此order 3的內(nèi)存塊分裂成兩個(gè)order 2的內(nèi)存塊(256K)
  　　2.3 仍然沒(méi)有order 0的內(nèi)存塊，因此order 2的內(nèi)存塊分裂成兩個(gè)order 1的內(nèi)存塊(128K)
  　　2.4 仍然沒(méi)有order 0的內(nèi)存塊，因此order 1的內(nèi)存塊分裂成兩個(gè)order 0的內(nèi)存塊(64K)
  　　2.5 找到了order 0的內(nèi)存塊，將其中的一個(gè)分配給程序A，現(xiàn)在伙伴系統(tǒng)的內(nèi)存為一個(gè)order 0的內(nèi)存塊，一個(gè)order1的內(nèi)存塊，一個(gè)order 2的內(nèi)存塊以及一個(gè)order 3的內(nèi)存塊

• 3 程序B申請(qǐng)一塊大小為66K的內(nèi)存，對(duì)應(yīng)的order為1，即2^1=2個(gè)最小內(nèi)存塊，由于系統(tǒng)中正好存在一個(gè)order 1的內(nèi)存塊，所以直接用來(lái)分配

• 4 程序C申請(qǐng)一塊大小為35K的內(nèi)存，對(duì)應(yīng)的order為0，同樣由于系統(tǒng)中正好存在一個(gè)order 0的內(nèi)存塊，直接用來(lái)分配

• 5 程序D申請(qǐng)一塊大小為67K的內(nèi)存，對(duì)應(yīng)的order為1
  　　5.1 系統(tǒng)中不存在order 1的內(nèi)存塊，于是將order 2的內(nèi)存塊分裂成兩塊order 1的內(nèi)存塊
  　　5.2 找到order 1的內(nèi)存塊，進(jìn)行分配

• 6 程序B釋放了它申請(qǐng)的內(nèi)存，即一個(gè)order 1的內(nèi)存塊

• 7 程序D釋放了它申請(qǐng)的內(nèi)存
  　　7.1 一個(gè)order 1的內(nèi)存塊回收到內(nèi)存當(dāng)中
  　　7.2由于該內(nèi)存塊的伙伴也是空閑的，因此兩個(gè)order 1的內(nèi)存塊合并成一個(gè)order 2的內(nèi)存塊

• 8 程序A釋放了它申請(qǐng)的內(nèi)存，即一個(gè)order 0的內(nèi)存塊

• 9 程序C釋放了它申請(qǐng)的內(nèi)存
  　　9.1 一個(gè)order 0的內(nèi)存塊被釋放
  　　9.2 兩個(gè)order 0伙伴塊都是空閑的，進(jìn)行合并，生成一個(gè)order 1的內(nèi)存塊
  　　9.3 兩個(gè)order 1伙伴塊都是空閑的，進(jìn)行合并，生成一個(gè)order 2的內(nèi)存塊
  　　9.4 兩個(gè)order 2伙伴塊都是空閑的，進(jìn)行合并，生成一個(gè)order 3的內(nèi)存塊
  　　9.5 兩個(gè)order 3伙伴塊都是空閑的，進(jìn)行合并，生成一個(gè)order 4的內(nèi)存塊

內(nèi)存對(duì)換

1 對(duì)換的引入

在多道程序環(huán)境下，內(nèi)存中可能存在多個(gè)被阻塞的進(jìn)程，占用大量?jī)?nèi)存空間，而多個(gè)作業(yè)在外存上無(wú)法進(jìn)入內(nèi)存，系統(tǒng)吞吐量下降，資源利用率低。

為解決這一問(wèn)題，在操作系統(tǒng)中增設(shè)了對(duì)換操作。對(duì)換是指把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)調(diào)到外存上，以便騰出足夠的內(nèi)存空間，把已具備運(yùn)行條件的進(jìn)程從賦存移入內(nèi)存。

如果對(duì)換是以整個(gè)進(jìn)程為單位的，便稱之為“整體對(duì)換”或“進(jìn)程對(duì)換”，這種對(duì)換被廣泛應(yīng)用于分時(shí)系統(tǒng)中，其目的是為了解決內(nèi)存緊張問(wèn)題，提高內(nèi)存利用率。如果對(duì)換是以“頁(yè)”或“段”為單位進(jìn)行的，則分別稱之為“頁(yè)面對(duì)換”或“分段對(duì)換”，又統(tǒng)稱為“部分對(duì)換”。“部分對(duì)換”的目的是為了支持虛擬存儲(chǔ)系統(tǒng)。

2 對(duì)換空間的管理

在具有對(duì)換功能的OS中，通常把外存分為文件區(qū)和對(duì)換區(qū)。前者用戶存放文件，后者用于存放從內(nèi)存中換出的進(jìn)程。通常，為提高文件的存儲(chǔ)空間的利用率，文件區(qū)采用離散分配方式。為提高進(jìn)程在對(duì)換區(qū)換入和換出的速度，對(duì)換區(qū)采用連續(xù)分配方式，較少考慮外存中的碎片問(wèn)題。

為了對(duì)對(duì)換區(qū)中的空閑盤(pán)塊進(jìn)行管理，在系統(tǒng)中應(yīng)配置相應(yīng)的空閑分區(qū)表或空閑分區(qū)鏈，以記錄外存中的使用情況。對(duì)換區(qū)的內(nèi)存分配與回收方式與連續(xù)分配方式相同。