13.3: The List of Available Space for Variable-Length Records

When dealing with variable-size records, which is the usual situation, storage management is complex because of fragmentation. The fragmentation problem is as follows. When all records being allocated dynamically are the same size, then as long as unused storage finds its way to the list of available space, it can be reused. However, it is possible with variable-size records that storage for a large record is needed but is not immediately in existence. Suppose each available block of consecutive elements of storage is kept on the list of available space as an individual record, with a field of each record used to store its length. It is possible for records of length 10, 15, 3, 20, and 45 to appear on the list when a record of length 65 must be created, but no individual record is large enough to be allocated for it. However, a total of 93 elements is unused. This is the external fragmentation problem. Enough storage is unused to satisfy the need, but no record currently on the list of available space is, by itself, large enough to be used. The problem may be resolved by invoking a compaction procedure, which moves the field values in used nodes to contiguous elements of memory at one end of the heap. All unused elements then also become contiguous and can represent a node large enough that the needed storage can be taken.

Figure 13.1 A Heap Containing the Available Space List (AV), a List (L), and a Binary Tree (T) and Nodes Labeled 1, 2, or 3 to Show Status

Figure 13.2 The Heap of Example 13.4 (Figure13.1) after Compaction

Example 13.5

Suppose the compaction procedure is applied to the heap of Example 13.4, which was illustrated in Figure 13.1. The result may be visualized as in Figure 13.2. n

Compaction, like garbage collection, is a time-consuming process that the programmer or computer system should only invoke infrequently. To overcome this, it is possible to organize the list of available space in an attempt to minimize fragmentation and thus the need for compaction. However, in limiting fragmentation the program should not spend too much computer time determining which node to allocate each time a request is made. Organizing the list of available space and using a reasonable policy to select the node to be allocated helps to reduce fragmentation. However, additional time is required to search the list to select the node to be allocated and to place a reclaimed node in proper position on the list to maintain its organization.

Fragmentation can also be reduced by creating larger nodes, by adding the freed storage to storage adjacent to it that is already free. This process is called coalescing. These policies and ways of organizing must be addressed by designers of compilers or operating systems and by programmers when they create storage management schemes for their own use.

Recall that the more structured or organized the data, the faster the access to required information. At the same time a price must be paid to maintain the organization. The primary considerations for a storage management scheme are the time to satisfy a request for a new node, the time to insert a node on the list of available space, the storage utilization, and the likelihood of satisfying a request. How well these characteristics turn out for a particular storage management scheme depends on the sequence of requests and returns. Mathematical analysis is generally not possible, and simulation must be used to evaluate different schemes. To provide some idea of the trade-offs and possibilities, three fundamental organizations for the available space list and appropriate allocation and reclamation policies are presented next.

13.3.1 Two-Way Circular Lists

13.3.2 The Buddy System

13.3.3 Indexing Methods