What is boundary tag method?

Sol: Boundary tags are data structures on the boundary between blocks in the heap from which memory is allocated. The use of such tags allow blocks of arbitrary size to be used as shown in the Fig. 2.1.

FREE

USED

FREE

Fig. 2.1

Suppose 'n ' bytes of memory are to be allocated from a large area, in contiguous blocks of varying size, and that no form of compaction or rearrangement of the allocated segments will be used.

To reserve a block of 'n ' bytes of memory, a free space of size 'n' or larger must be located. If we could locate a large size memory, then the allocation process will divide it into an allocated space, and a new smaller free space. Suppose free space is subdivided in this manner several times, and some of the allocated regions are "released" (after usei. e . , deallocated).

If we try to reserve more memory; even though there is a large contiguous chunk of free space, the memory manager perceives it as two smaller segments and so may falsely conclude that it has insufficient free space to satisfy a large request.

For optimal use of the memory, adjacent free segments must be combined. For maximum availability, they must be combined as soon as possible. The task of identifying and merging adjacent free segments should be done when a segment is released, called the boundary tag method. The method consistently applied to ensure that there would never be two adjacent free segments. This guarantees the largest available free space short of compacting the string space.