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 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