The role of relocation, the ability to execute processes independently from their physical location in memory, is central for memory management: virtually all the techniques in this field rely on the ability to relocate processes efficiently. The need for relocation is immediately evident when one considers that in a general-purpose multiprogramming environment a program cannot know in advance (before execution, i.e. at compile time) what processes will be running in memory when it is executed, nor how much memory the system has available for it, nor where it is located. Hence a program must be compiled and linked in such a way that it can later be loaded starting from an unpredictable address in memory, an address that can even change during the execution of the process itself, if any swapping occurs.
It's easy to identify the basic requirement for a (binary executable) program to be relocatable: all the references to memory it makes during its execution must not contain absolute (i.e. physical) addresses of memory cells, but must be generated relatively, i.e. as a distance, measured in number of contiguous memory words, from some known point. The memory references a program can generate are of two kinds: references to instructions ad references to data. The former kind is implied in the execution of program branches or subroutine calls: a jump machine instruction always involves the loading of the CPU program counter register with the address of the memory word containing the instruction to jump to. The executable code of a relocatable program must then contain only relative branch machine instructions, in which the address to branch to is specified as an increment (or decrement) with respect to the address of the current instruction (or to the content of a register or memory word). The latter kind comes into play when whenever program variables (including program execution variables, like a subroutine call stack) are accessed. In this case relocation is made possible by the use of indexed or increment processor addressing modes, in which the address of a memory word is computed at reference time as the sum of the content of a register plus an increment or a decrement.
As we'll see later, the memory references of a process in a multitasking environment must somehow be bounded, so to protect from unwanted interferences memory areas like the unwritable parts of the process itself, or the memory areas containing the images of other processes, etc. This is usually accomplished in hardware by comparing the address of each memory reference produced by a process with the content of one or more bound registers or memory words, so that the processor traps an exception to block the process should an illegal address be generated
In fig. 11 a scheme of the address computation involved in the memory references of a relocatable program is shown.
Figure 11: A scheme of relative address computation.