[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 small—usually 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