Re: Data management algorithm needed
Date: Sun, 06 Jan 2002 18:38:11 -0800
Message-ID: <pan.2002.01.06.18.38.08.850.8513_at_yahoooo.com>
In article <3C38EA70.380D218E_at_no_spam_today_thanks.com>, "Chris" <spamfree_at_no_spam_today_thanks.com> wrote:
> Why is allocating space in blocks of 2**i faster?
I had to look this up, but it's fairly simple: Blocks can be split and merged to produce blocks of different sizes on demand. For instance if a 64-page block is needed, a block of 128 pages can be split and the extra space can be added to the 64-page free list. Likewise, free lists (maintained for each size block) are scanned and adjacent same-size blocks are merged to form bigger blocks of contiguous memory.
I suppose this approach is one way to reduce fragmentation, although I haven't studied it very closely.
Finer-grained malloc's are handled by a different algorithm, for obvious space efficiency reasons.
Some keywords to search on are:
Kmalloc algorithm
Buddy Algorithm
Received on Mon Jan 07 2002 - 03:38:11 CET