Relocation

Memory Management

 

 

In a multiprogramming computer the operating system resides in part of memory and the rest is used by multiple processes.

 

The task of subdividing the memory not used by the operating system among the various processes is called memory management.

Memory management requirements

· Relocation - programs not loaded into a fixed point in memory but may reside in various areas.

 

· Protection - each process should be protected against unwanted interference by other processes either accidentally or intentionally. All memory references generated by a process must be checked at run time to ensure that they only reference memory that has been allocated to that process.

 

· Sharing – Protection mechanisms must be flexible enough to allow a number of processes to access the same area of memory. For example if a number of processes are executing the same program, it is advantageous to allow each program to access the same copy of the program.

 

· Logical Organisation – Programs are normally organised into modules some of which are non modifiable and some of which contain data that may be modified. How does the operating system organise RAM which is a linear address space to reflect this logical structure.

 

· Physical Organisation – Computer memory is organises into a least two levels : main memory and secondary memory. The task of moving information between the two levels of memory should be the systems responsibility (not the programmers).

 

Relocation

How a program is loaded from disk.

 

fig1

 

The first step in the creation of an active process is to load a program into main memory and create a process image, as shown above. The actual program itself may consist of a number of compiled or assembled modules that are linked together to resolve any references between modules (see Fig 2 below).

 

The Loader places the program in memory. It may do so in three ways:

 

· Absolute Loading

· Relocatable loading

· Dynamic run-time loading

 

 

Fig2

 

Absolute Loading:

 

An absolute loader requires that a given module is always loaded into the same location in memory. Therefore any references in the program must correspond exactly to the actual memory location when the program is loaded.

 

The assignment of specific address values to memory references within a program can be done either by the programmer or at compile or assembly time. There are several disadvantages to the former approach. Firstly every programmer would have to know exactly how programs are loaded into main memory. Secondly, if any modifications are made to the program that involved insertions or deletions in the body of the program, then all addresses would have to be altered. For this reason it is preferable to allow memory references within programs to be expressed symbolically (see Fig3 below). and have those symbolic references resolved at compilation or assembly. This is illustrated below every reference to an instruction or item of data is initially represented by a symbol. In preparing the module for input to an absolute loader, the assembler or compiler will convert all these references to specific address. The absolute loader will then load the program at the addresses specified.

 

 

Fig3

 

 

Relocatable loader:

 

A huge disadvantage of binding references to specific addresses prior to loading is that the resulting load module can only be places in one region of main memory. And as normally memory is shared between a number of processes it is undesirable to state in advance into which region of memory a particular module should be loaded. It would be better to make that decision at run time. What we need is a module that can be loaded into any part of available memory.

To satisfy this requirement, the assember/compiler produces not actual main memory addresses ( absolute addresses) but addresses that are relative to some known point such as the start of the program. This is shown above in Fig3. The start of the load module is assigned the relative address 0 and all other memory references within the module are expressed relative to the beginning of the module.

With all the references expressed in relative format it is quite easy for the loader to place the module in the desired location. If the module in to be loaded beginning at location x, then the loader must simply add x to each memory reference as it loads the module into memory. To assist in this task, the load module must include information that tells the loader where the address references are and how they are to be interpreted , usually relative to the program origin but also possibly relative to some other point in the program such as current location.

 

Dynamic Run Time Loader:

 

The relocatble loader is an obvious advance over absolute loaders however in a multiprogramming environment it is still inadequate. In a multiprogramming environment there is often a need to swap process images in and out of main memory to maximise the use of the processor (or some other operational reason). To implement this it will be necessary to reload the process in different memory locations (depending what is available at the time). Thus a program once loaded may be swapped out and reloaded at a different location. This would not be possible with the relocatable loader where memory references are bound to absolute at initial load time.

The solution to this is to defer the calculation of an absolute address until it is actually needed at run time. How this works is that the load module is brought into main memory with all the memory references in relative form as in c) (Fig3) above. It is not until an instruction is actually executed that the absolute address is calculated. To ensure that this conversion of addresses takes place as fast as possible it is done by special processor hardware (Memory Management Unit).

Dynamic address calculation provides complete flexibility. A program can be loaded into any region of main ardware (Memory Management Unit).

Dynamic address calculation provides complete flexibility. A program can be loaded into any region of main memory and logical addresses converted to physical addresses on the fly.

 

 

Fig4 below shows how the address translation is achieved. When a process is assigned to the Running state, a special register called the base registeris loaded with the starting address in main memory of the process. A bounds registerwhich indicates the ending location of the program is also used. During the course of program execution, relative addresses are encountered. These include the contents of instruction registers, instruction addresses that occur in branch and call instructions and data addresses that occur in load and store instructions. Each such relative address goes through two steps of manipulation by the processor. First the value in the base address is added to the relative address to produce an absolute address. Second, the resulting address is compared to the value in the bounds register. If the address is within bounds then the instruction execution proceeds. Otherwise an interrupt indicating an error is generated.

This scheme allows programs to be swapped in and out of memory during execution and also provides a measure of protection – each process image is isolated by the contents of the base and bounds register and is safe from unwanted access by other processes.