Carnegie Mellon
Implicit List: Finding a Free Block
Firstfit:
Search list from beginning, choose first free block that fits:
p = start;
while ((p < end) &&
\\ not passed end
\\ already allocated
\\ too small
\\ goto next block (word addressed)
((*p & 1) ||
(*p <= len)))
p = p + (*p & -2);
Can take linear time in total number of blocks (allocated and free) In practice it can cause “splinters” at beginning of list
Nextfit:
Like first fit, but search list starting where previous search finished
Should often be faster than first fit: avoids re-scanning unhelpful blocks Some research suggests that fragmentation is worse
Bestfit:
Search the list, choose the best free block: fits, with fewest bytes left over Keeps fragments small—usually helps fragmentation
Will typically run slower than first fit
1
Carnegie Mellon
Implicit List: Allocating in Free Block Allocating in a free block: splitting
Since allocated space might be smaller than free space, we might want to split the block
p
4
4
6
2
addblock(p, 4)
4
4
4
2
2
void addblock(ptr p, int len) {
int newsize = len;
int oldsize = *p & -2;
*p = newsize | 1;
// mask out low bit
// set new length
// set length in remaining
// part of block
}
if (newsize < oldsize)
*(p+newsize) = oldsize - newsize;
2