chap lists and arrays revisited figure doubly linked list of free blocks as seen by the memory manager shaded areas represent allocated memory unshaded areas are part of the freelist tag sizellink rlink tag size size tag (atag (bfigure blocks as seen by the memory manager each block includes additional information such as freelist link pointersstart and end tagsand size field (athe layout for free block the beginning of the block contains the tag bit fieldthe block size fieldand two pointers for the freelist the end of the block contains second tag field and second block size field (ba reserved block of bytes the memory manager adds to these bytes an additional tag bit field and block size field at the beginning of the blockand second tag field at the end of the block be discussed below if the block contains exactly words (plus space for the tag and size fields)then it is removed from the freelist if the block (of size kis large enoughthen the remaining words are reserved as block on the freelistin the current location when block is freedit must be merged into the freelist if we do not care about merging adjacent free blocksthen this is simple insertion into the doubly linked list of free blocks howeverwe would like to merge adjacent blocksbecause this allows the memory manager to serve requests of the largest possible size merging is easily done due to the tag and size fields stored at the ends of each blockas illustrated by figure herethe memory manager first checks the unit of memory immediately preceding block to see if the preceding block (call it pis also free if it isthen the memory unit before ' tag bit stores the size of pthus indicating the position for the beginning of the block in memory can