Java Reference
In-Depth Information
Tag
Size
Llink
Rlink
Tag
Size
+
k
k
+
k
Tag
Size Tag
(a)
(b)
Figure12.12 Blocks as seen by the memory manager. Each block includes
additional information such as freelist link pointers, start and end tags, and a size
field. (a) The layout for a free block. The beginning of the block contains the tag
bit field, the block size field, and two pointers for the freelist. The end of the block
contains a second tag field and a second block size field. (b) A reserved block of
k bytes. The memory manager adds to these k bytes an additional tag bit field and
block size field at the beginning of the block, and a second tag field at the end of
the block.
P
F
S
k
k
+
Figure12.13 Adding block F to the freelist. The word immediately preceding
the start of F in the memory pool stores the tag bit of the preceding block P. If P
is free, merge F into P. We find the end of F by using F's size field. The word
following the end of F is the tag field for block S. If S is free, merge it into F.
because 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
block, as illustrated by Figure 12.13. Here, the memory manager first checks the
unit of memory immediately preceding block F to see if the preceding block (call
it P) is also free. If it is, then the memory unit before P's tag bit stores the size
of P, thus indicating the position for the beginning of the block in memory. P can
then simply have its size extended to include block F. If block P is not free, then
we just add block F to the freelist. Finally, we also check the bit following the end
of block F. If this bit indicates that the following block (call it S) is free, then S is
removed from the freelist and the size of F is extended appropriately.
Search WWH ::




Custom Search