① 電腦對於多通道內存是怎麼分配的
加8g的話，其中4g用了組成雙通道，剩餘4g是單通道，稱為非對稱雙通道。個人建議買4g的，畢竟老電腦了，加上之後變為8g讓它苦苦支持吧。
② 二級分配器的內存池有幾個空閑鏈表
模塊主要由以下部分組成。
ObjectPool 對象池
MemPool 內存池
FastMemAlloc : 高速的大內存分配
FastSmallAlloc : 快速的小內存分配。
FixMemAlloc : 小浪費空間的大內存分配。
FixSmallMemAlloc : 小浪費空間的小內存分配。基本不浪費空間。
MemState。具有統計內存狀態。（mpMemState）和檢測內存越界mpBound。
除了FastMemAlloc外，所有的分配器內存都由MemState記錄。 FastMemAlloc的內存狀態由他自己記錄，你可以調用FastMemAlloc::diagnostic()和FastMemAlloc::mpBound()來分析內存。
③ vc中如何用bitblt函數將內存點陣圖分塊
關於Bitblt函數，從內存中拷貝到內存中，下面的代碼可以給你參考：
// 取得窗口客戶區域大小
CRect WndRect ;
this->GetWindowRect ( &WndRect ) ;
this->ScreenToClient ( &WndRect ) ;
CClientDC cdc(this) ;
CDC mdc, TempDc ; // 內存DC
BITMAP BmpInfo ;
CBitmap ClientBmp, *pOldBmp ;
// 創建與設備DC兼容的內存DC
mdc.CreateCompatibleDC ( &cdc ) ;
TempDc.CreateCompatibleDC ( &cdc ) ;
// 創建與設備DC兼容的點陣圖對象
ClientBmp.CreateCompatibleBitmap ( &cdc, WndRect.right, WndRect.bottom ) ;
mdc.SelectObject ( &ClientBmp ) ;
// 依次把點陣圖貼到內存DC
for ( int i = 0; i <= 8; i++ )
{
TempDc.SelectObject ( &this->MyBmp[i].bmp ) ;
this->MyBmp[i].bmp.GetBitmap ( &BmpInfo ) ;
if ( i == 0 )
mdc.BitBlt (0, 0, WndRect.Width(), WndRect.Height(), &TempDc, 0, 0, SRCCOPY ) ;
else
mdc.TransparentBlt ( this->MyBmp[i].rect.left, \
this->MyBmp[i].rect.top, BmpInfo.bmWidth, BmpInfo.bmHeight, \
&TempDc, 0, 0, BmpInfo.bmWidth, BmpInfo.bmHeight, RGB(255,255,255) ) ;
}
// 把內存DC貼到設備DC上
cdc.BitBlt ( 0, 0, WndRect.right, WndRect.bottom, &mdc, 0, 0, SRCCOPY ) ;
// 環境清理
ClientBmp.DeleteObject () ;
mdc.DeleteDC () ;
④ 求解 內存分配(Memory Allocate) 問題
1）malloc.h 是的，VC 6.0 用 #include <stdlib.h> 就可以了。
2）寫法都對。用 malloc 或 calloc 與個人習慣 有關（各人喜歡，c語言歷史有這2函數）。realloc 用於 隨時可以 增加 動態分配 或 減小 動態分配 空間。另2個函數無此功能。
3) 加條件判斷做釋放： if ( p) free(p);
⑤ 可變分區管理內存分配演算法有那些,各有什麼有缺點
連續分配： 首次適應演算法（較快，簡單，碎片多），最大適應分配演算法（以期不留下小碎片）， 最佳適應分配演算法（慢，復雜，碎片少）。 都需要碎片整理。
離散分配：分段管理（邏輯性好），分頁管理，段頁式管理（最好，當然也復雜）。
⑥ 簡述內存管理中buddy演算法和slab機制的區別
1、Buddy演算法
linux對空閑內存空間管理採取buddy演算法，
Buddy演算法：
把內存中所有頁面按照2^n劃分，其中n=0~5，每個內存空間按1個頁面、2個頁面、4個頁面、8個頁面、16個頁面、32個頁面進行六次劃分。劃分後形成了大小不等的存儲塊，稱為頁面塊，簡稱頁塊，包含一個頁面的頁塊稱為1頁塊，包含2個頁面的稱為2頁塊，依次類推。
每種頁塊按前後順序兩兩結合成一對Buddy「夥伴」。系統按照Buddy關系把具有相同大小的空閑頁面塊組成頁塊組，即1頁塊組、2頁塊組……32頁塊組。 每個頁塊組用一個雙向循環鏈表進行管理，共有6個鏈表，分別為1、2、4、8、16、32頁塊鏈表。分別掛到free_area[] 數組上。
點陣圖數組
用於標記內存頁面使用情況，第0組每一位表示單個頁面使用情況，1表示使用，0表示空閑，第二組每一位表示比鄰的兩個頁面使用情況，一次類推。默認為10個數組，當一對Buddy的兩個頁面中有一個事空閑的，而另一個全部或部分被佔用時，該位置1.兩個頁面塊都是空閑，對應位置0.
內存分配和釋放過程
內存分配時，系統按照Buddy演算法，根據請求的頁面數在free_area[]對應的空閑頁塊組中搜索。 若請求頁面數不是2的整數次冪，則按照稍大於請求數的2的整數次冪的值搜索相應的頁面塊組。
當相應頁塊組中沒有可使用的空閑頁面塊時就查詢更大一些的頁塊組，在找到可用的頁塊後分配所需要的頁面。當某一空閑頁面被分配後，若仍有剩餘的空閑頁面，則根據剩餘頁面的大小把他們加入到相應頁面組中。
內存頁面釋放時，系統將其作為空閑頁面看待，檢查是否存在與這些頁面相鄰的其他空閑頁塊，若存在，則合為一個連續的空閑區按Buddy演算法重新分組。
2、Slab演算法
採用buddy演算法，解決了外碎片問題，這種方法適合大塊內存請求，不適合小內存區請求。如：幾十個或者幾百個位元組。Linux2.0採用傳統內存分區演算法，按幾何分布提供內存區大小，內存區以2的冪次方為單位。雖然減少了內碎片，但沒有顯著提高系統效率。
Linux2.4採用了slab分配器演算法，該演算法比傳統的分配器演算法有更好性能和內存利用率，最早在solaris2.4上使用。
Slab分配器思想
1）小對象的申請和釋放通過slab分配器來管理。
2）slab分配器有一組高速緩存，每個高速緩存保存同一種對象類型，如i節點緩存、PCB緩存等。
3）內核從它們各自的緩存種分配和釋放對象。
4）每種對象的緩存區由一連串slab構成，每個slab由一個或者多個連續的物理頁面組成。這些頁面種包含了已分配的緩存對象，也包含了空閑對象。
⑦ 二維數組[5][10]，請指出下面初始化時內存該分配多少 int **p int *p[5] int (*p)[10]
int **p 定義一個指向指針的指針，是一個指針類型。占內存4位元組
int *p[5] 定義了一個整形數組，裡面存放了5個指針類型的元素，佔5×4=20位元組
int (*p)[10] 定義了一個指向10個整形數組的指針，也是一個指針，佔4位元組
當然了，你也可以做個程序測試下：
#include <iostream>
using namespace std;
void main()
{
int **p; //在實際應用中這3個定義都要初始化
int *a[5];
int (*b)[10];
cout<<sizeof(p)<<endl;
cout<<sizeof(a)<<endl;
cout<<sizeof(b)<<endl;
}
⑧ 【我的筆記】內存管理（二）分區方法（靜態、動態、夥伴、Slab）
由操作系統或系統管理員預先將內存劃分成若干個分區。在系統運行過程中，分區的邊界不再改變。分配時，找一個空閑且足夠大的分區。如沒有合適的分區：①讓申請者等待。②先換出某分區的內容，再將其分配出去。
為申請者分配指定的分區或任選一個分區。如果沒有空閑分區，可將一個分區的內容換出。可能需要重定位。
會出現內部碎片，無法滿足大內存的需求。
可減少內部碎片。減少對大內存需求的限制。
①固定分配：只分配某種尺寸的特定分區，如分區已被使用，申請者必須等待。
可能出現不公平等待：雖有更大尺寸的空閑分區，卻必須等待。
②最佳適應分配：分配能滿足需要的最小尺寸的空閑分區，只有當所有分區都已用完時，申請者才需要等待。靈活，但可能產生較大的內部碎片。
3、靜態分區：內存利用率低，產生內部碎片；尺寸和分區數量難以確定。
1、不預先確定分區的大小和數量，將分區工作推遲到實際分配內存時進行。 Lazy
初始情況下，把所有的空閑內存看成一個大分區。分配時，按申請的尺寸，找一塊足夠大的空閑內存分區，臨時從中劃出一塊構成新分區。新分區的尺寸與申請的大小相等，不會出現內部碎片。回收時，盡可能與鄰近的空閑分區合並。在內存緊缺時，可將某個選定的分區換出。
2、會產生外部碎片，如下圖（內部碎片是指 eg：要 1M，分了 8M，產生 7M 的碎片）：
移動內存中的進程，將碎片集中起來，重新構成大的內存塊。需要運行時的動態重定位，費時。
（1）緊縮方向：向一頭緊縮，向兩頭緊縮。
（2）緊縮時機：①在釋放分區時，如果不能與空閑分區合並，則立刻進行緊縮。
好處是不存在外部碎片，壞處是費時。
②在內存分配時，如果剩餘的空閑空間總量能滿足要求但沒有一個獨立的空閑塊能滿足要求，則進行緊縮。
好處是減少緊縮次數。Lazy。
①最先適應演算法（First fit）：從頭開始，在滿足要求的第一個空閑塊中分配。
分區集中在內存的前部，大內存留在後面，便於釋放後的合並。
②最佳適應演算法（Best fit）：遍歷空閑塊，在滿足要求的最小空閑塊中分配。
留下的碎片最小，基本無法再用，需要更頻繁地緊縮。
③下一個適應演算法（Next fit）：從上次分配的位置開始，在滿足要求的下一個空閑塊中分配。
對內存的使用較平均，不容易留下大的空閑塊。
④最差適應演算法（Worst Fit）：遍歷空閑塊，在滿足要求的最大空閑塊中分配。
留下的碎片較大，但不會剩餘大內存。
最先適應演算法較優，最佳適應演算法較差。
夥伴演算法：將動態分區的大小限定為 2^k 位元組，分割方式限定為平分，分區就會變得較為規整，分割與合並會更容易，可以減少一些外部碎片。平分後的兩塊互稱夥伴。
1、
分配時可能要多次平分，釋放時可能要多次合並。舉例：
記錄大小不同的空閑頁：
示意圖：
2、
夥伴演算法是靜態分區和動態分區法的折中，比靜態分區法靈活，不受分區尺寸及個數的限制；比動態分區法規范，不易出現外部碎片。會產生內部碎片，但比靜態分區的小。
Linux、Windows、Ucore等都採用夥伴演算法管理物理內存。
一般情況下，將最小尺寸定為 2^12 位元組（1頁，4K=4096B），最大尺寸定為1024頁，11個隊列。
Linux、Windows、Ucore 等都將夥伴的最小尺寸限定為1頁。
ucore 用 page，在內存初始化函數 page_init 中為系統中的每個物理頁建立一個 page 結構。
頁塊（pageblock）是一組連續的物理頁。
5、
（1）判斷夥伴關系/尋找夥伴
最後兩行是指，B1和B2隻有第i位相反。
（2）判斷夥伴是否空閑：
ucore 用 free_area[ ]數組定義空閑頁塊隊列。
（3）確定夥伴是否在 order 隊列中：
7、
（1）解決內部碎片過大問題（eg：申請5頁，分配8頁，浪費3頁）：
ucore 在前部留下需要的頁數，釋放掉尾部各頁。每次釋放1頁，先劃分成頁塊，再逐個釋放。
（2） 解決切分與合並過於頻繁的問題：
用得較多的是單個頁。位於處理器Cache中頁稱為熱頁（hot page），其餘頁稱為冷頁（cold page）。處理器對熱頁的訪問速度要快於冷頁。
可建一個熱頁隊列（per_cpu_page），暫存剛釋放的單個物理頁，將合並工作向後推遲 Lazy。總是試圖從熱頁隊列中分配單個物理頁。分配與釋放都在熱頁隊列的隊頭進行。
（3）解決內存碎化(有足夠多的空閑頁，但是沒有大頁塊)問題：①將頁塊從一個物理位置移動到另一個物理位置，並保持移動前後邏輯地址不變（拷貝頁塊內容）；②邏輯內存管理器。
（4）滿足大內存的需求：
（5）物理內存空間都耗盡的情況：
在任何情況下，都應該預留一部分空閑的物理內存以備急需。定義兩條基準線low和high，當空閑內存量小於low時，應立刻開始回收物理內存，直到空閑內存量大於high。
（6）回收物理內存：
法一：啟動一個守護進程，專門用於回收物理內存。周期性啟動，也可被喚醒。
法二：申請者自己去回收內存。實際是由內存分配程序回收。回收的方法很多，如釋放緩沖區、頁面淘汰等。
1、
夥伴演算法最小分配內存為頁，對於更小的內存的管理 --> Slab 演算法
內和運行過程中經常使用小內存（小於1頁）eg：建立數據結構、緩沖區
內核對小內存的使用極為頻繁、種類繁多、時機和數量難以預估。所以難以預先分配，只能動態地創建和撤銷
2、
Slab 向夥伴演算法申請大頁塊（批發），將其劃分成小對象分配出去（零售）；將回收的小對象組合成大頁塊後還給夥伴演算法。
Slab 採用等尺寸靜態分區法，將頁塊預先劃分成一組大小相等的小塊，稱為內存對象。
具有相同屬性的多個Slab構成一個Cache，一個Cache管理一種類型（一類應該是指一個大小）的內存對象。當需要小內存時，從預建的Cache中申請內存對象，用完之後再將其還給Cache。當Cache中缺少對象時，追加新的Slab；當物理內存緊缺時，回收完全空閑的Slab。
Slab 演算法的管理結構：
① Cache 管理結構：管理Slab，包括Slab的創建和銷毀。
② Slab 管理結構：管理內存對象，包括小對象的分配與釋放。
（Cache結構和Slab結構合作，共同實現內存對象的管理）
3、
（1）描述各個內存對象的使用情況
可以用點陣圖標識空閑的內存對象。也可以將一個Slab中的空閑內存對象組織成隊列，並在slab結構中記錄隊列的隊頭。
早期的Linux在每個內存對象的尾部都加入一個指針，用該指針將空閑的內存對象串聯成一個真正的隊列。（對象變長、不規范，空間浪費）
改進：將指針集中在一個數組中，用數組內部的鏈表模擬內存對象隊列。
再改進：將數組中的指針換成對象序號，利用序號將空閑的內存對象串成隊列。序號數組是動態創建的。
序號數組可以位於 Slab 內部，也可以位於 Slab 外部
（2）一個Cache會管理多個Slab，可以將所有Slab放在一個隊列中。
Ucore為每個Cache准備了兩個slab結構隊列：全滿的和不滿的。Linux為每個Cache准備了三個slab結構隊列：部分滿的、完全滿的和完全空閑的。
Linux允許動態創建Cache，Ucore不許。Ucore預定了對象大小，分別是32、64、128、256、512、1K、2K（4K、8K、16K、32K、64K、128K）。為每一種大小的對象預建了Cache。
（3）Slab是動態創建的，當Cache中沒有空閑的內存對象時，即為其創建一個新的Slab。
Slab所需要的內存來自夥伴演算法，大小是 2^page_order 個連續頁。
4、小對象的尺寸
如按處理器一級緩存中緩存行（Cache Line）的大小（16、32位元組）取齊，可使對象的開始位置都位於緩存行的邊界處。
在將頁塊劃分成內存對象的過程中，通常會剩餘一小部分空間，位於所有內存對象之外，稱為外部碎片。
Slab演算法選用碎片最小的實現方案。
5、
（1）對象分配 kmalloc
① 根據size確定一個Cache。
② 如果Cache的slabs_notfull為空，則為其創建一個新的Slab。
③ 選中slabs_notfull中第一個Slab，將隊頭的小對象分配出去，並調整隊列。
④ 對象的開始地址是：objp = slabp->s_mem + slabp->free * cachep->objsize;
（2）對象釋放 kfree
① 算出對象所在的頁號，找到它的 Page 結構。
② 根據 Page 找到所屬的 Cache 和 Slab。
③ 算出對象序號：objnr = (objp - slabp->s_mem) / cachep->objsize;
④將序號插入Slab的free隊列。
⑤整Slab所屬隊列。
⑨ 求C++實現的幾個內存分配演算法源代碼。
http://wenku..com/view/2869ce80ec3a87c24028c46f.html
這裡面有C語言實現的上面的兩種演算法，如果運行不了的話，你可以改改，如果運行成功了的話，你可以根據這個來寫出另一個演算法的代碼。
⑩ [編程知識]如何分配內存 內存碎片處理技術
內存碎片是一個很棘手的問題。如何分配內存決定著內存碎片是否會、何時會、如何會成為一個問題。 即使在系統中事實上仍然有許多空閑內存時，內存碎片還會最終導致出現內存用完的情況。一個不斷產生內存碎片的系統，不管產生的內存碎片多麼小，只要時間足夠長，就會將內存用完。這種情況在許多嵌入式系統中，特別是在高可用性系統中是不可接受的。有些軟體環境，如 OSE 實時操作系統已經備有避免內存碎片的良好工具，但個別程序員做出的選擇仍然會對最終結果形成影響。 「碎片的內存」描述一個系統中所有不可用的空閑內存。這些資源之所以仍然未被使用，是因為負責分配內存的分配器使這些內存無法使用。這一問題通常都會發生，原因在於空閑內存以小而不連續方式出現在不同的位置。由於分配方法決定內存碎片是否是一個問題，因此內存分配器在保證空閑資源可用性方面扮演著重要的角色。 編譯時間與運行時間 在許多情況下都會出現內存分配問題。程序員可以通過編譯程序和鏈接程序，為結構、並集、數組和標量（用作局部變數、靜態變數或全局變數）方面的數據分配內存，程序員還可以在運行時間使用諸如 malloc()調用命令動態地分配內存。當用編譯程序和鏈接程序完成內存分配功能時，就不會出現內存碎片，因為編譯程序了解數據壽命。掌握可供使用的數據壽命，好處在於可以使數據以後進先出的方式疊加起來。這樣就可以使內存分配程序工作效率更高，而不會出現內存碎片。一般來說，運行時間內的內存分配是不可疊加的。內存分配在時間上是獨立的，從而使得碎片問題難以解決。 圖1，內存碎片的幾種形式。 內存分配程序浪費內存的基本方式有三種：即額外開銷、內部碎片以及外部碎片（圖 1）。內存分配程序需要存儲一些描述其分配狀態的數據。這些存儲的信息包括任何一個空閑內存塊的位置、大小和所有權，以及其它內部狀態詳情。一般來說，一個運行時間分配程序存放這些額外信息最好的地方是它管理的內存。內存分配程序需要遵循一些基本的內存分配規則。例如，所有的內存分配必須起始於可被 4、8 或 16 整除（視處理器體系結構而定）的地址。內存分配程序把僅僅預定大小的內存塊分配給客戶，可能還有其它原因。當某個客戶請求一個 43 位元組的內存塊時，它可能會獲得 44位元組、48位元組 甚至更多的位元組。由所需大小四捨五入而產生的多餘空間就叫內部碎片。 外部碎片的產生是當已分配內存塊之間出現未被使用的差額時，就會產生外部碎片。例如，一個應用程序分配三個連續的內存塊，然後使中間的一個內存塊空閑。內存分配程序可以重新使用中間內存塊供將來進行分配，但不太可能分配的塊正好與全部空閑內存一樣大。倘若在運行期間，內存分配程序不改變其實現法與四捨五入策略，則額外開銷和內部碎片在整個系統壽命期間保持不變。雖然額外開銷和內部碎片會浪費內存，因此是不可取的，但外部碎片才是嵌入系統開發人員真正的敵人，造成系統失效的正是分配問題。 定義內存碎片的方法有幾種，其中最常用的是： 這一方法適用於外部碎片，但可以修改這一公式使之包括內部碎片，辦法是把內部碎片加入到分母中。內存碎片是一個介於 0 和 1 之間的分數。一個碎片為 1(100%)的系統就是把內存全用完了。如果所有空閑內存都在一個內存塊（最大內存塊）中，碎片為 0%。當所有空閑內存的四分之一在最大內存塊中時，碎片為 75%。例子如下：一個系統有 5M 位元組的空閑內存，當它可用來分配的最大內存塊為 50 k 位元組時，其內存碎片為99%。這個 99%內存碎片實例來自開發嵌入式軟實時系統期間出現的一種真實情況。當這種碎片程度發生一秒後，系統就崩潰了。該系統在碎片率達到 99% 之前，已經進行了約兩周的連續現場測試。這種情況是如何發生的？為什麼會發現得如此晚？當然，系統都經過測試，但測試很少超過兩個小時。交付前的最後壓力測試持續了一個周末。在這樣短的測試周期內未必會產生內存碎片的後果，所以就發生了內存碎片需要多長時間才會達到臨界值，這一問題很難回答。對某些應用來說，在某些情況下，系統會在用完內存前達到一種穩定狀態。而對於另一些應用來說，系統則不會及時達到穩定狀態（圖 2）。只要消除不確定性因素和風險因素，不產生碎片的內存分配程序（圖 3）就能快速達到一種穩定狀態，從而有助於開發人員夜晚安穩睡覺。在開發數月甚至數年不再重新啟動的長期運行系統時，快速收斂到穩定狀態是一個重要因素。在比系統連續運行周期短的時間內，對系統進行適當的測試，這是必不可少的。 圖2，這一案例研究把最先適合內存分配程序用於一個嵌入系統項目。系統在現場測試中連續運行了兩周，然後碎片率達到 99%。圖3，一個不產生碎片的內存分配程序一旦試驗應用程序的全部，它就能達到穩定狀態。 很難確定哪種內存分配演算法更勝一籌，因為每種演算法在不同的應用中各有所長（表 1）。最先適合內存分配演算法是最常用的一種。它使用了四個指針：MSTART 指向被管理內存的始端；MEND 指向被管理內存的末尾；MBREAK 指向 MSTART 和 MEND 之間已用內存的末端； PFREE 則指向第一個空閑內存塊（如果有的話）。 在系統開始運行時，PFREE 為 NULL，MBREAK 指向 MSTART。當一個分配請求來到時，分配程序首先檢查 PFREE有無空閑內存塊。由於 PFREE 為 NULL，一個具有所請求存儲量加上管理標題的內存塊就脫離 MBREAK ，然後MBREAK就更新。這一過程反復進行，直至系統使一個內存塊空閑，管理標題包含有該存儲塊的存儲量為止。此時，PFREE 通過頭上的鏈接表插入項被更新為指向該內存塊，而塊本身則用一個指向舊 PFREE 內容的指針進行更新，以建立一個鏈接表。下一次出現分配請求時，系統就會搜索空閑內存塊鏈接表，尋找適合請求存儲量的第一個空閑內存塊。一旦找到合適的內存塊，它將此內存塊分成兩部分，一部分返還給系統，另一部分則送回給自由表。 最先適合內存分配演算法實現起來簡單，而且開始時很好用。但是，經過一段時間後，會出現如下的情況：當系統將內存交給自由表時，它會從自由表的開頭部分去掉大內存塊，插入剩餘的小內存塊。最先適合演算法實際上成了一個排序演算法，即把所有小內存碎片放在自由表的開頭部分。因此，自由表會變得很長，有幾百甚至幾千個元素。因此，內存分配變得時間很長又無法預測，大內存塊分配所花時間要比小內存塊分配來得長。另外，內存塊的無限制拆分使內存碎片程度很高。有些實現方法在使內存空閑時會將鄰近的空閑內存塊連接起來。這種方法多少有些作用，而最先適合演算法與時間共處演算法(time co-location)和空間共處演算法(spatial co-location)不同，它在使內存塊空閑時，無法提高相鄰內存塊同時空閑的概率。 最佳適合與最差適合分配程序 最佳適合演算法在功能上與最先適合演算法類似，不同之處是，系統在分配一個內存塊時，要搜索整個自由表，尋找最接近請求存儲量的內存塊。這種搜索所花的時間要比最先適合演算法長得多，但不存在分配大小內存塊所需時間的差異。最佳適合演算法產生的內存碎片要比最先適合演算法多，因為將小而不能使用的碎片放在自由表開頭部分的排序趨勢更為強烈。由於這一消極因素，最佳適合演算法幾乎從來沒有人採用過。 最差適合演算法也很少採用。最差適合演算法的功能與最佳適合演算法相同，不同之處是，當分配一個內存塊時，系統在整個自由表中搜索與請求存儲量不匹配的內存快。這種方法比最佳適合演算法速度快，因為它產生微小而又不能使用的內存碎片的傾向較弱。始終選擇最大空閑內存塊，再將其分為小內存塊，這樣就能提高剩餘部分大得足以供系統使用的概率。 夥伴(buddy)分配程序與本文描述的其它分配程序不同，它不能根據需要從被管理內存的開頭部分創建新內存。它有明確的共性，就是各個內存塊可分可合，但不是任意的分與合。每個塊都有個朋友，或叫「夥伴」，既可與之分開，又可與之結合。夥伴分配程序把內存塊存放在比鏈接表更先進的數據結構中。這些結構常常是桶型、樹型和堆型的組合或變種。一般來說，夥伴分配程序的工作方式是難以描述的，因為這種技術隨所選數據結構的不同而各異。由於有各種各樣的具有已知特性的數據結構可供使用，所以夥伴分配程序得到廣泛應用。有些夥伴分配程序甚至用在源碼中。夥伴分配程序編寫起來常常很復雜，其性能可能各不相同。夥伴分配程序通常在某種程度上限制內存碎片。 固定存儲量分配程序有點像最先空閑演算法。通常有一個以上的自由表，而且更重要的是，同一自由表中的所有內存塊的存儲量都相同。至少有四個指針：MSTART 指向被管理內存的起點，MEND 指向被管理內存的末端，MBREAK 指向 MSTART 與 MEND 之間已用內存的末端，而 PFREE[n] 則是指向任何空閑內存塊的一排指針。在開始時，PFREE[*] 為 NULL，MBREAK 指針為 MSTART。當一個分配請求到來時，系統將請求的存儲量增加到可用存儲量之一。然後，系統檢查 PFREE[ 增大後的存儲量 ] 空閑內存塊。因為 PFREE[ 增大後的存儲量 ] 為 NULL，一個具有該存儲量加上一個管理標題的內存塊就脫離 MBREAK，MBREAK 被更新。 這些步驟反復進行，直至系統使一個內存塊空閑為止，此時管理標題包含有該內存塊的存儲量。當有一內存塊空閑時，PFREE[ 相應存儲量 ] 通過標題的鏈接表插入項更新為指向該內存塊，而該內存塊本身則用一個指向 PFREE[ 相應存儲量 ] 以前內容的指針來更新，以建立一個鏈接表。下一次分配請求到來時，系統將 PFREE[ 增大的請求存儲量 ] 鏈接表的第一個內存塊送給系統。沒有理由搜索鏈接表，因為所有鏈接的內存塊的存儲量都是相同的。 固定存儲量分配程序很容易實現，而且便於計算內存碎片，至少在塊存儲量的數量較少時是這樣。但這種分配程序的局限性在於要有一個它可以分配的最大存儲量。固定存儲量分配程序速度快，並可在任何狀況下保持速度。這些分配程序可能會產生大量的內部內存碎片，但對某些系統而言，它們的優點會超過缺點。 減少內存碎片 內存碎片是因為在分配一個內存塊後，使之空閑，但不將空閑內存歸還給最大內存塊而產生的。最後這一步很關鍵。如果內存分配程序是有效的，就不能阻止系統分配內存塊並使之空閑。即使一個內存分配程序不能保證返回的內存能與最大內存塊相連接（這種方法可以徹底避免內存碎片問題），但你可以設法控制並限制內存碎片。所有這些作法涉及到內存塊的分割。每當系統減少被分割內存塊的數量，確保被分割內存塊盡可能大時，你就會有所改進。 這樣做的目的是盡可能多次反復使用內存塊，而不要每次都對內存塊進行分割，以正好符合請求的存儲量。分割內存塊會產生大量的小內存碎片，猶如一堆散沙。以後很難把這些散沙與其餘內存結合起來。比較好的辦法是讓每個內存塊中都留有一些未用的位元組。留有多少位元組應看系統要在多大程度上避免內存碎片。對小型系統來說，增加幾個位元組的內部碎片是朝正確方向邁出的一步。當系統請求1位元組內存時，你分配的存儲量取決於系統的工作狀態。 如果系統分配的內存存儲量的主要部分是 1 ～ 16 位元組，則為小內存也分配 16 位元組是明智的。只要限制可以分配的最大內存塊，你就能夠獲得較大的節約效果。但是，這種方法的缺點是，系統會不斷地嘗試分配大於極限的內存塊，這使系統可能會停止工作。減少最大和最小內存塊存儲量之間內存存儲量的數量也是有用的。採用按對數增大的內存塊存儲量可以避免大量的碎片。例如，每個存儲量可能都比前一個存儲量大 20%。在嵌入式系統中採用「一種存儲量符合所有需要」對於嵌入式系統中的內存分配程序來說可能是不切實際的。這種方法從內部碎片來看是代價極高的，但系統可以徹底避免外部碎片，達到支持的最大存儲量。 將相鄰空閑內存塊連接起來是一種可以顯著減少內存碎片的技術。如果沒有這一方法，某些分配演算法（如最先適合演算法）將根本無法工作。然而，效果是有限的，將鄰近內存塊連接起來只能緩解由於分配演算法引起的問題，而無法解決根本問題。而且，當內存塊存儲量有限時，相鄰內存塊連接可能很難實現。 有些內存分配器很先進，可以在運行時收集有關某個系統的分配習慣的統計數據，然後，按存儲量將所有的內存分配進行分類，例如分為小、中和大三類。系統將每次分配指向被管理內存的一個區域，因為該區域包括這樣的內存塊存儲量。較小存儲量是根據較大存儲量分配的。這種方案是最先適合演算法和一組有限的固定存儲量演算法的一種有趣的混合，但不是實時的。 有效地利用暫時的局限性通常是很困難的，但值得一提的是，在內存中暫時擴展共處一地的分配程序更容易產生內存碎片。盡管其它技術可以減輕這一問題，但限制不同存儲量內存塊的數目仍是減少內存碎片的主要方法。 現代軟體環境業已實現各種避免內存碎片的工具。例如，專為分布式高可用性容錯系統開發的 OSE 實時操作系統可提供三種運行時內存分配程序：內核 alloc()，它根據系統或內存塊池來分配；堆 malloc()，根據程序堆來分配； OSE 內存管理程序 alloc_region，它根據內存管理程序內存來分配。 從 許多方面來看，Alloc就是終極內存分配程序。它產生的內存碎片很少，速度很快，並有判定功能。你可以調整甚至去掉內存碎片。只是在分配一個存儲量後，使之空閑，但不再分配時，才會產生外部碎片。內部碎片會不斷產生，但對某個給定的系統和八種存儲量來說是恆定不變的。 Alloc 是一種有八個自由表的固定存儲量內存分配程序的實現方法。系統程序員可以對每一種存儲量進行配置，並可決定採用更少的存儲量來進一步減少碎片。除開始時以外，分配內存塊和使內存塊空閑都是恆定時間操作。首先，系統必須對請求的存儲量四捨五入到下一個可用存儲量。就八種存儲量而言，這一目標可用三個 如果 語句來實現。其次，系統總是在八個自由表的表頭插入或刪除內存塊。開始時，分配未使用的內存要多花幾個周期的時間，但速度仍然極快，而且所花時間恆定不變。 堆malloc() 的內存開銷（8 ～ 16 位元組/分配）比 alloc小，所以你可以停用內存的專用權。malloc() 分配程序平均來講是相當快的。它的內部碎片比alloc()少，但外部碎片則比alloc()多。它有一個最大分配存儲量，但對大多數系統來說，這一極限值足夠大。可選的共享所有權與低開銷使 malloc() 適用於有許多小型對象和共享對象的 C++ 應用程序。堆是一種具有內部堆數據結構的夥伴系統的實現方法。在 OSE 中，有 28 個不同的存儲量可供使用，每種存儲量都是前兩種存儲量之和，於是形成一個斐波那契（Fibonacci）序列。實際內存塊存儲量為序列數乘以 16 位元組，其中包括分配程序開銷或者 8 位元組/分配（在文件和行信息啟用的情況下為 16 位元組）。 當你很少需要大塊內存時，則OSE內存管理程序最適用。典型的系統要把存儲空間分配給整個系統、堆或庫。在有 MMU 的系統中，有些實現方法使用 MMU 的轉換功能來顯著降低甚至消除內存碎片。在其他情況下，OSE 內存管理程序會產生非常多的碎片。它沒有最大分配存儲量，而且是一種最先適合內存分配程序的實現方法。內存分配被四捨五入到頁面的偶數——典型值是 4 k 位元組。（T111）