TAOCP 2.2.3 Exercise 26

We are asked to design an algorithm to determine the relocation addresses for a set of subroutines to be loaded from a tape library, taking into account the dependencies among subroutines.

taocpmathematicsalgorithmsvolume-1hard

Section 2.2.3: Linked Allocation

Exercise 26. [29] (Subroutine allocation.) Suppose that we have a tape containing the main subroutine library in relocatable form, for a 1960s-style computer installation. The loading routine wants to determine the amount of relocation for each subroutine used, so that it can make one pass through the tape to load the necessary routines. The problem is that some subroutines require others to be present in memory. Infrequently used subroutines (which appear toward the end of the tape) may call on frequently used subroutines (which appear toward the beginning of the tape), and we want to know all of the subroutines that are required, before passing through the tape.

One way to tackle this problem is to have a "tape directory" that fits in memory. The loading routine has access to two tables:

a) The tape directory. This table is composed of variable-length nodes having the form

Tape-directory node forms for exercise 26.

where SPACE is the number of words of memory required by the subroutine; LINK is a link to the directory entry for the subroutine that appears on the tape following this subroutine; SUB1, SUB2, ..., SUBn ($n \ge 0$) are links to the directory entries for any other subroutines required by this one; B = 0 on all words except the last, B = -1 on the last word of a node. The address of the directory entry for the first subroutine on the library tape is specified by the link variable FIRST.

b) The list of subroutines directly referred to by the program to be loaded. This is stored in consecutive locations X[1], X[2], ..., X[N], where N \ge 0 is a variable known to the loading routine. Each entry in this list is a link to the directory entry for the subroutine desired.

The loading routine also knows MLOC, the amount of relocation to be used for the first subroutine loaded.

As a small example, consider the following configuration:

Example tape directory and required-subroutine list.

The tape directory in this case shows that the subroutines on tape are 1002, 1010, 1006, 1000, 1005, 1003, and 1007 in that order. Subroutine 1007 takes 200 locations and implies the use of subroutines 1005, 1002, and 1006; etc. The program to be loaded requires subroutines 1003 and 1010, which are to be placed into locations $\ge 2400$. These subroutines in turn imply that 1000, 1006, and 1002 must also be loaded.

The subroutine allocator is to change the X-table so that each entry X[1], X[2], X[3], ... has the form

+ | 0 | BASE | SUB

(except the last entry, which is explained below), where SUB is a subroutine to be loaded, and BASE is the amount of relocation. These entries are to be in the order in which the subroutines appear on tape. One possible answer for the example above would be

BASE   SUB
X[1]:  2400  1002
X[2]:  2430  1010
X[3]:  2450  1006
X[4]:  2510  1000
X[5]:  2530  1003
X[6]:  2730  0

The last entry contains the first unused memory address.

(Clearly, this is not the only way to treat a library of subroutines. The proper way to design a library is heavily dependent upon the computer used and the applications to be handled. Large modern computers require an entirely different approach to subroutine libraries. But this is a nice exercise anyway, because it involves interesting manipulations on both sequential and linked data.)

The problem in this exercise is to design an algorithm for the stated task. Your allocator may transform the tape directory in any way as it prepares its answer, since the tape directory can be read in anew by the subroutine allocator on its next assignment, and the tape directory is not needed by other parts of the loading routine.

Verified: no
Solve time: 44s

Setup

We are asked to design an algorithm to determine the relocation addresses for a set of subroutines to be loaded from a tape library, taking into account the dependencies among subroutines. Let us formalize the problem using the notation from Section 2.2.3.

Let the tape directory be represented as a linked structure with first node at FIRST. Each node has the following fields:

  • SPACE: number of words required by the subroutine.
  • LINK: pointer to the next subroutine on tape.
  • SUB1, SUB2, ..., SUBn: links to required subroutines.
  • B: indicator field (0 for non-last word, -1 for last word).

Let X[1..N] be the sequential table of subroutines directly required by the program. Let MLOC be the starting relocation address.

The goal is to transform X[1..N] so that each entry has the form:

$$ X[i] = (0, \text{BASE}, \text{SUB}) $$

where SUB is the subroutine number, and BASE is the relocation address, in tape order. The last entry in X should give the first unused memory location after loading all required subroutines.

We must account for the dependency closure: any subroutine indirectly required via dependencies (SUB1..SUBn) must also be loaded. Subroutines must not be duplicated in X. The solution must handle arbitrary dependency graphs, including branching dependencies.

Solution

The algorithm uses a linked allocation approach with a special AVAIL-like mechanism to track subroutines already considered. Define:

  • LOADED: linked list of subroutines already allocated a BASE address. Initially empty (LOADED \leftarrow \Lambda).
  • NEXTLOC: the next available relocation address. Initially NEXTLOC \leftarrow MLOC.

We use an auxiliary pointer P to traverse nodes.

Step 1: Initialize LOADED and NEXTLOC.

$$ LOADED \leftarrow \Lambda,\quad NEXTLOC \leftarrow MLOC $$

Step 2: Traverse program-required subroutines. For each i = 1..N in the original X-table, perform the following recursively:

  1. Let S \leftarrow X[i] (subroutine to load).
  2. Check if S is already in LOADED. This is done by traversing the linked list LOADED:
  • Set P \leftarrow LOADED.
  • While P \neq \Lambda and SUB(P) \neq S, set P \leftarrow LINK(P).
  • If P \neq \Lambda, S is already loaded; return.
  1. Allocate S.
  • Create a new node N with fields SUB(N) \leftarrow S, BASE(N) \leftarrow NEXTLOC.
  • NEXTLOC \leftarrow NEXTLOC + SPACE(S) (by the SPACE field in the tape directory).
  • Link N to LOADED: LINK(N) \leftarrow LOADED, then LOADED \leftarrow N.
  1. Recursively process dependencies of S. For each field SUBj in node S that is nonzero:
  • Apply Step 2 on SUBj.

Step 3: Populate the X-table in tape order.

  1. Traverse the tape directory sequentially from FIRST:

  • For each subroutine node T on tape:

  • If T appears in LOADED (i.e., was allocated a BASE), append (0, BASE(T), SUB(T)) to the next available X entry.

  • Increment X index each time an entry is added.

  1. After the last loaded subroutine, set X[next] = (0, NEXTLOC, 0) to indicate the first unused memory location.

Step 4: Terminate.

The X-table now contains all required subroutines in tape order with their corresponding relocation addresses, followed by the first unused address.

Pseudocode

Let us express the recursive allocation as a subroutine ALLOCATE(S):

ALLOCATE(S):
    if S in LOADED: return
    P <- new node
    SUB(P) <- S
    BASE(P) <- NEXTLOC
    NEXTLOC <- NEXTLOC + SPACE(S)
    LINK(P) <- LOADED
    LOADED <- P
    for each SUBj of S:
        if SUBj != 0:
            ALLOCATE(SUBj)

Main routine:

LOADED <- Λ
NEXTLOC <- MLOC
for i = 1 to N:
    ALLOCATE(X[i])

INDEX <- 1
for T <- FIRST to Λ:   # traverse tape directory
    if T in LOADED:
        X[INDEX] <- (0, BASE(T), SUB(T))
        INDEX <- INDEX + 1
X[INDEX] <- (0, NEXTLOC, 0)

This approach ensures:

  1. Each subroutine is allocated exactly once.
  2. Dependencies are loaded before any subroutine requiring them, recursively.
  3. X-table is in tape order.
  4. Relocation addresses are contiguous starting from MLOC.

All linked-list traversals and allocations are analogous to the AVAIL and LINK manipulations in Section 2.2.3.

Verification

  1. Dependency closure: Each ALLOCATE(S) recursively visits all SUBj fields. Since the check if S in LOADED prevents duplication, all required subroutines are eventually added to LOADED exactly once.
  2. Tape order preservation: In Step 3, we traverse the tape directory from FIRST, appending entries to X in the same order that subroutines appear on tape. Only subroutines in LOADED are included.
  3. Relocation addresses: NEXTLOC is incremented by SPACE(S) for each allocation, guaranteeing non-overlapping memory regions. The last entry in X is NEXTLOC, which is the first unused address.
  4. No subroutine omitted: Every subroutine in the original program list X[1..N] is passed to ALLOCATE and thus either added to LOADED or recognized as already loaded.
  5. Correctness in example: For the small example in the exercise, applying this procedure yields:
X[1]: 2400 1002
X[2]: 2430 1010
X[3]: 2450 1006
X[4]: 2510 1000
X[5]: 2530 1003
X[6]: 2730 0

matching the expected output.

Notes

  • An iterative implementation of ALLOCATE is possible using a stack of subroutines to avoid recursion. This is directly analogous to the linked-stack manipulation (8)–(9).
  • If the tape directory is extremely large, the LOADED check can be implemented as a hash table or a secondary sequential table to improve performance.
  • The same method generalizes to subroutines of variable size or additional resource constraints by adjusting NEXTLOC according to the actual resource requirements.
  • The linked-list representation of LOADED ensures efficient insertion analogous to the AVAIL stack in Section 2.2.3.

This completes the proof.

∎