伙伴算法

伙伴算法是一種在計(jì)算機(jī)內(nèi)存管理中使用的算法，用于分配和釋放內(nèi)存。它是一種基于二叉樹的動(dòng)態(tài)內(nèi)存分配算法，可以高效地分配和合并內(nèi)存塊?；锇樗惴ㄊ且环N按照固定大小分配內(nèi)存的算法，例如，每個(gè)內(nèi)存塊的大小為2的n次冪，即1、2、4、8、16、32等等。

伙伴算法的主要思想是將可用內(nèi)存劃分成多個(gè)大小相等的內(nèi)存塊，每個(gè)內(nèi)存塊大小為2的n次冪。對(duì)于每個(gè)內(nèi)存塊，都有一個(gè)伙伴內(nèi)存塊，它的大小是相等的，但是地址不同。例如，如果有一個(gè)大小為4個(gè)字節(jié)的內(nèi)存塊，它的伙伴內(nèi)存塊大小也為4個(gè)字節(jié)，但是它的地址不同。

當(dāng)需要分配內(nèi)存時(shí)，伙伴算法將查找大小最接近請(qǐng)求大小的可用內(nèi)存塊。如果找到的內(nèi)存塊大小正好匹配請(qǐng)求大小，則將其標(biāo)記為已用，并返回指向該內(nèi)存塊的指針。如果找到的內(nèi)存塊比請(qǐng)求大小大，則將其拆分成兩個(gè)相等的伙伴內(nèi)存塊，并將其中一個(gè)標(biāo)記為已用，另一個(gè)標(biāo)記為可用。然后，繼續(xù)在較小的伙伴塊中查找可用內(nèi)存塊，直到找到大小匹配的塊或搜索完整個(gè)內(nèi)存區(qū)域。

當(dāng)需要釋放內(nèi)存時(shí)，伙伴算法將標(biāo)記為已用的內(nèi)存塊標(biāo)記為可用，并將其與其伙伴內(nèi)存塊合并。如果伙伴內(nèi)存塊也是可用的，則將它們合并成一個(gè)更大的內(nèi)存塊，直到合并到最大的內(nèi)存塊為止。在合并時(shí)，伙伴算法通過(guò)一個(gè)二叉樹來(lái)管理內(nèi)存塊，每個(gè)節(jié)點(diǎn)表示一個(gè)內(nèi)存塊，節(jié)點(diǎn)的左子節(jié)點(diǎn)是伙伴內(nèi)存塊。

伙伴算法的優(yōu)點(diǎn)是分配和釋放內(nèi)存的效率比較高，合并內(nèi)存塊的操作也比較簡(jiǎn)單。但是，由于它只能分配大小相等的內(nèi)存塊，因此可能會(huì)導(dǎo)致內(nèi)存浪費(fèi)。此外，它也可能導(dǎo)致內(nèi)存碎片的問(wèn)題。

能否避免內(nèi)存碎片？

伙伴算法無(wú)法完全避免內(nèi)存碎片，但可以減少碎片的數(shù)量和大小。

伙伴算法通過(guò)將可用內(nèi)存空間劃分為二的指數(shù)次冪大小的塊，然后以塊為單位分配和釋放內(nèi)存。分配請(qǐng)求按指數(shù)次冪進(jìn)行舍入，以便可以分配給與請(qǐng)求大小最接近但不小于請(qǐng)求大小的可用塊。如果沒有完全匹配，就將塊拆分為更小的塊，然后繼續(xù)尋找匹配項(xiàng)。當(dāng)釋放內(nèi)存時(shí)，會(huì)找到相鄰的空閑塊并合并它們，以創(chuàng)建更大的空閑塊。

盡管伙伴算法減少了碎片的數(shù)量和大小，但仍可能發(fā)生內(nèi)存碎片。例如，如果有大量小型內(nèi)存請(qǐng)求，可能會(huì)導(dǎo)致大量小塊的分配和釋放，這些小塊可能無(wú)法合并成更大的塊。此外，如果存在大小不一的塊，則無(wú)法在它們之間進(jìn)行合并。因此，伙伴算法無(wú)法消除所有內(nèi)存碎片，但可以降低其影響。

內(nèi)部碎片與外部碎片

內(nèi)部碎片指的是已分配的內(nèi)存空間中，未被使用的小塊內(nèi)存。這些內(nèi)存塊的大小小于分配的內(nèi)存大小。例如，如果分配了一個(gè) 10MB 的空間來(lái)存儲(chǔ) 1MB 的數(shù)據(jù)，則剩余的 9MB 就是內(nèi)部碎片。

外部碎片指的是已分配的內(nèi)存空間中，由于分配和釋放的順序不同導(dǎo)致的空隙，這些空隙可能很小，但無(wú)法被利用。例如，如果分配了兩個(gè) 5MB 的內(nèi)存塊，但它們之間有一個(gè) 1MB 的空隙，這個(gè)空隙就是外部碎片。

【最后一個(gè)bug】多平臺(tái)都有更新和發(fā)布，大家可以一鍵三連，關(guān)注+星標(biāo)，不錯(cuò)過(guò)精彩內(nèi)容~