[SOLVED] CS Carnegie Mellon

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 smallusually helps fragmentation Will typically run slower than first fit1 Carnegie MellonImplicit 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 blockp4462addblock(p, 4) 44422 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