Run-Time Storage Organization and Management (Compiler Writing) Part 4

Free-as-You-Go Storage Release

The first method is to free each block of heap storage as soon as it becomes unused. This prevents the accumulation of garbage blocks but can require more run-time checking. This method is generally implemented by means of reference counters—counters which record how many pointers to this block are still in existence. When a block is first allocated, its reference counter is set to 1. Each time another link is made pointing to this block, the reference counter is incremented; each time a link to it is broken, the reference counter is decremented. When the count reaches 0, the block is inaccessible and hence unusable. At this point it is returned to the free list. Notice that this technique completely eliminates the dangling-reference problem. The block is returned after there are no references to it in the program.

There are certain drawbacks in using this method, however. First, if the blocks that are allocated form a circular structure, their reference counts will always remain set to at least 1, and none of the blocks will ever be freed, even if all pointers from outside the circular structure to blocks in the circular list are destroyed. We then have a circle of blocks, each of which is inaccessible from the program, and yet all the blocks will remain allocated—as permanent garbage. There are solutions for this, of course. One is simply to prohibit circular or recursive structures. In a number of applications, however, a circular structure is the most natural and reasonable one to use. Another solution is to flag circular structures as such, thereby signifying that they are to receive special treatment from the point of view of storage release. A third solution is to require that circular structures always use a special list head whose reference counter counts only references from outside the circle, and that all access to blocks in the circular , structure are made through this list head. This is then a prohibition against direct accessing of any block in the circle. When a list head goes to 0, the header block and all blocks in the circle can be freed.


Another drawback to the reference-counter method is the overhead involved in maintaining the reference counts. This is a more serious objection because it can increase the execution time of the program significantly. Every processing operation will have to be checked for effects on the reference counts, and these must be updated as necessary. For example, the simple statement P = PRED (£>) can generate code to do the following assuming that P and Q are known (perhaps by declarations) to be pointer variables:

1. Access block P and decrement its reference count. Let this new reference count be t.

2. Test t for zero. If so, free block P.

3. Evaluate PRED (Q). Let the result be the address r.

4. Access block r and increment its reference count.

5. Assign the value r to the variable P.

Examination of even the simpler algorithms that may be used in the context where heap storage allocation and release are reasonable should indicate that the cost of this counter maintenance can easily become excessive.

Garbage Collection

The second method of determining when to free storage is garbage collection. This method makes use of a special routine which is invoked whenever the available storage is almost exhausted, whenever a particular request cannot be met, or, perhaps, whenever the amount of available storage has decreased beyond a certain predefined point. Normal program execution is interrupted while this routine frees garbage blocks and is resumed when the garbage collector has finished its work. The garbage-collection algorithm generally has two phases. The first phase consists of tracing all the access paths from all the program and system variables through the allocated blocks. Each block accessed in this way is marked. The second phase consists of moving through the entire segment of memory, resetting the marks of the marked blocks, and returning to the free list every allocated block that has not been marked.

This method prevents the generation of dangling references, because if there is any path of references leading to a block, the block is marked and is not freed in the second phase. Because the garbage collector must trace paths of pointers from block to block, however, it is essential that, every time the garbage collector is invoked, all list and block structures are in a stable state with pointers pointing where they should. Otherwise the garbage collector will not be able to make the proper tracing of all the reference paths, and either some garbage will remain uncollected or, more seriously, blocks still in use will be freed. Since the garbage collector can be invoked by the system at almost any point in program execution, it is required that the use of pointers be disciplined. There are certain algorithms, however, which, during their operation, temporarily distort structures—e.g., having pointers pointing up a tree instead of downward to branches. If the garbage collector is invoked while the program is executing one of these algorithms, it is quite possible that the garbage collector will meet such a distorted tree. The marking phase can then no longer mark the correct blocks, and the situation when normal execution resumes can be horrendous.

A solution to this is, of course, to use pointers responsibly, avoiding the kind of algorithm that momentarily distorts structures. Certain applications, however, could well need that type of algorithm; it may be the only way to do the required task. In this case, the algorithm should begin by disabling the garbage collector so that it cannot be invoked while the algorithm is executing. If the algorithm should ever request storage and have the request refused, however, a stalemate has developed. There is not necessarily any ready solution to this problem other than to terminate the job and rerun with more storage initially allocated to the job.

One of the drawbacks to the garbage-collection technique is that its costs increase as the amount of free storage decreases, and yet it is at this point that one would hope for efficient and cheap release of storage. When you have little free storage left, you expect the garbage collector to be called more often, and you want its use to cost as little as possible. The reason for the inverse relationship is, of course, that when there is little free storage, there is a lot of allocated storage and hence the marking process has to trace through many blocks. Because of thj(s factor, and also perhaps to avoid the stalemate situation mentioned earlier, garbage-collection methods are sometimes implemented so that the collector is invoked Well before memory becomes completely allocated. For example, whenever the amount of free storage drops below half the total amount, the collector can be invoked intermittently. Also, to eliminate the intolerably repetitive calls to the collector that can result when memory is almost full, some systems consider the memory to be full whenever the garbage collector fails to restore the amount of free storage to a certain level. Such a condition causes the system to terminate when the next unsatisfiable request is encountered.

We now look at some of the algorithms that have been developed for garbage collection. We concentrate on the marking phase because the actual freeing phase, the sequential stepping through memory-freeing unmarked blocks, is relatively simple. For fixed-size blocks of size n, with P being the address of the block with the lowest address in the total memory segment, the address of all the r blocks that were formed out of the total memory segment is given by P + i*n, 0 £ i < r. For variable-sized blocks, with P and Q being the addresses of the first and last words of the total memory segment, the addresses of all the blocks are given by the sequence of P values formed by

tmp1A-381_thumb[2][2][2]tmp1A-382_thumb[2][2][2]

In the marking phase, the garbage collector must mark all blocks that are accessible by any path of references that begins with a program or system variable. Consequently, the collection algorithm must have access to a list of all the variables that currently contain references into the heap storage area. To access such a list either the address of each block must be maintained at ru« time, say, in the symbol table, or all pointers to allocated blocks in the heap must be readily available, say, in some contiguous area in storage at run time. Once a variable has been found that points to a block of allocated storage, that block must be marked along with all the other blocks that are accessed by pointers within the first block, and all blocks are accessed from these blocks, etc. Once all of the blocks accessible from this variable have been marked, the next variable is processed in the same way. When all the variables have been processed, the total ,memory segment is stepped through and unmarked blocks are freed.

For the convenience of the marking algorithm, we assume that blocks which contain pointers to other blocks, thus forming a list-type structure, have these pointers located so that they are re.adily accessible given the block address. They can be located in the first words of the block following the block control fields.

Block structure for garbage collection.

Figure 9-17 Block structure for garbage collection.

Therefore, we assume that block P, when allocated, has a structure of the form given in Fig. 9-17.

FREE(P) contains a value equal to 1 + the number of LINK fields, SIZE(P) is the size of block P (or the coding for the size of block P as in the binary buddy or Fibonacci allocation system), SAVE(P) is a field to be used in the marking process by which a temporary distortion of the list structure needed for traversal can be eventually undone, MARK(P) is a field initially set to false which is set true to denote that block P has been marked, and the LINK(P) fields are pointers to other blocks. Note that there need not be any such LINK fields. Observe that the LINK fields can be accessed by the addresses Q, for P < Q < P + FREE(P). The allocation technique or release method may well require additional control fields. In such cases, simply assume that the correct fields are present.

The marking algorithm that will be presented is based on one proposed by Schorr and Waite (1967). Basic to the algorithm is the strategy of following each access path until it terminates. In particular, this implies that a path is followed until there are no more LINK fields to process or until a block is examined which is already marked because it is also on some other previously marked path. As this forward path is followed, the LINK fields which we traverse are set to point to the block from which we came. This temporary distortion of the structure is, however, the factor that enables the one-way path to be retraced. The SAVE field is used to record which of the several LINK fields in a block is currently reversed. When this path is retraced, as we enter a block on the return journey, we reset the altered LINK field to its correct value and then process all the other LINK fields of that block as if they initiated subpaths. That is, we follow one to its end, reversing LINK fields, and then trace it backward, resetting LINK fields and following still further subpaths. It therefore follows that the logical structure of this algorithm involves a considerable degree of "nesting" of path fragments within path fragments. If it were not for the storage shortage, this would make an ideal candidate for a recursive treatment. The actual algorithm follows.

Procedure LINK_MARK (P). Given P, the address of a block which is directly accessible and blocks with the structure described earlier, this procedure marks block P and all blocks accessible from P. The pointers P and Q refer to the current block under process and the previous block, respectively. Local variables include t (contains the LINK field which is currently reversed) and TEMP (pointer).

tmp1A-384_thumb[2][2][2]

 

 

tmp1A-385_thumb[2][2][2]

Figure 9-18 illustrates a trace of Procedure LINK_MARK for nodes Nx, N2, N3, and N4. A snapshot of the state of each node is given when step 2 of the algorithm is executed. Notice that initially the MARK field of all nodes is false (i.e., "/ ") and at the completion of the trace all accessible nodes are marked true (i.e.,"?").

The marking procedure in Procedure LINK_MARK can be altered so as to use a stack to keep track of what nodes have been marked rather than temporarily adjusting the link fields. The stack approach simplifies the algorithm; however, extra space is required for the stack. We leave the development of the stack-oriented algorithm as an exercise for the reader at the end of this section.

Compaction

As a final topic, we briefly discuss compaction as a technique for reclaiming heap storage. Compaction works by actually moving blocks of data, etc., from one location in memory to another so as to collect all the free blocks into one large block. The allocation problem then becomes completely simplified. Allocation now consists of merely moving a pointer which points to the top of this successively shortening block of storage. Once this single block gets too small again, the compaction mechanism is again invoked to reclaim the unused storage that may now exist among allocated blocks.

There is generally no storage-release mechanism. Instead, a marking algorithm is used to mark blocks that are still in use. Then, instead of freeing each unmarked block by calling a release mechanism to put it on a free list, the compactor simply collects all unmarked blocks into one large block at one end of the memory segment, for heap storage.

Sample trace of Procedure LINK_MARK.

Figure 9-18 Sample trace of Procedure LINK_MARK.

The only real problem in this method is the redefining of pointers. This is solved by making extra passes through memory. After blocks are marked, the entire heap memory is stepped through and the new address for each marked block is determined. This new address is stored in the block itself. Then another pass over heap memory is made. On this pass, pointers that point to marked blocks are reset to point to where the marked blocks will be after compaction. This is why the new address is stored right in the block—it is easily obtainable. After all pointers have been reset, the marked blocks are moved to their new locations. An example of a compaction algorithm is the following.

Procedure COMPACT (START, STOP). Given blocks of the structure as described for garbage collection, this procedure performs a compaction of unused heap storage into one large block whose starting address is TOP and which extends from TOP to STOP, the highest address in the entire memory segment for heap storage. It is assumed that START is the address of the first word of the memory segment. The SAVE field in the marked blocks is used by the compaction routine to record the new address of each block. LOC is a pointer to various memory locations, k and t are local variables which are used during the moving of marked blocks to their new locations.

tmp1A-387_thumb[2][2][2]

 

 

 

tmp1A-388_thumb[2][2][2]

It should be noted that this compaction routine is a relatively costly process in terms of execution time because of its three passes through heap memory. However, the increased speed of allocation might well make it a reasonable option in certain circumstances. Many implementations of SNOBOL use this compaction algorithm (or a variant); so presumably, it cannot be too inefficient.

A formal trace of Procedure COMPACT is not given; however, an exercise involving a trace appears at the end of this section.

Our discussion of storage allocation and management is now completed. A number of algorithms have been presented which are typical of those that are commonly used in a translator and its run-time support system. In practice, several of these techniques are combined in one translator. It should be realized, however, that the operating environment of the language translator strongly determines which methods should be used especially when considering heap storage techniques. Parameters such as request frequency, size-of-request distribution, usage (e.g., batch or on-line), and even the charging policy of a particular computer center may affect the decision as to what techniques should be adopted.

Next post:

Previous post: