C.4 Loaders

A loader is a utility program which reads an executable program file in a particular format from a secondary storage unit, puts proper bit-patterns in the memory at specified place and then initiates execution of that program. It should perform the following:

• Request allocation of memory space.
• Resolve symbolic references between object files. We have already seen this function, called linking, under “Linker”, Section C.1 and is included in the loader if it is a Direct-linking loader.
• Adjust all load address-dependent locations – address constants, pointers, even address operands in instructions – to correspond to the allocated load address. This is called relocation. Most of the modern general-purpose computers use Virtual Memory organization, which essentially eliminates these requirements. We have already seen this function under “Linker” in Section C.1.
• Physically, place the program instructions and data, which is in the format shown in Fig. C.3 on the secondary storage unit, into the main memory and create a load-map similar to Fig. C.5. Again, if the system is using Virtual Memory, then the loader prepares a “blueprint” (i.e. layout) of program memory allocation, but at the start of the program, only a small portion of the physical memory is actually made available to the program, see “Virtual Memory and Loader” in Section C.4.3.

   

  

   

  Fig. C.5 Actual process memory. Note the “free” area

C.4.1 Absolute Loader

This is the simplest of loading scheme. The loader simply reads the executable program file and puts the program “text” (instructions) and data at the specified locations. A typical absolute loader is for Intel Hex format files. The input file consists of a number of records, whose format is:

: BC AAAA TT DD DD ... … CH

where BC – two hex characters giving byte-count of this record;

AAAA – four hex characters give the load address;

TT – two characters give record type – 00 means data record, 01 means end of file record;

DD – two hex characters per data byte, maximum 16-bytes;

CH – two hex characters check-sum.

The absolute loader program is quite simple, see the pseudo-code in Fig. C.4.1.

Advantages: Simple in concept and simple to implement.

Disadvantages: The programmer is responsible for assigning all memory addresses, useful only on very simple computer systems.

C.4.2 Relocating Loader

Here, the load addresses given in the program file are relative addresses only, generally with respect to the program beginning address of 0. The operating system will allocate a load address to the loader and the loader will load the program instructions and data at places in memory with this load address as beginning. In order that the program is still valid at the actual load address, all position-dependent addresses must be modified by the loader. For example, consider a small program segment:

      in program file                  in memory
0000   JMP     0020                1000   JMP      1020
0010   0100                        1010   1100
0014       Y                       1014     Y
0020   LD      0014                1020   LD       1014
0024   ADD I   0010                1024   ADD I    1010
       ...     ...                        ...      ...
0100       X                       1100     X

The system has assigned 1000 as the load address for the program. The relocating loader will have to modify:

1. address operand in JMP instruction, to actual program start address;
2. address constant – address of variable X – is to be modified;
3. address operand in LD instruction is to be modified;
4. address operand in ADD indirect instruction is to be modified.

If the CPU of the computer system supports Position Independent Code (PIC), a major portion of these adjustments can be avoided and thus reduces the program load time. PIC is generally available as one of the addressing modes. The address operands are displacements with respect to the Instruction Pointer (Program Counter). Assuming PIC address mode in effect for all the instructions, the program will look like:

      in program file                  in memory
0000   JMP     0020                1000   JMP      0020
0010   0100                        1010   1100
0014       Y                       1014     Y
0020   LD      -6                  1020   LD       -6
0024   ADD I   -14                 1024   ADD I    -14
       ...     ...                        ...      ...
0100       X                       1100     X

Note that even with PIC, the address constant at 0010 required to be modified by the loader, as it is address-dependent data and not an instruction. The address operands within instruction will generate proper effective memory addresses, for any load address due to the PIC mode.

The problem of adjustment of address constants is resolved if the CPU has two-component addressing mode available. In this mode, an effective address (EA), i.e. the operand address sent to the memory, is made up of content of a base register and a displacement value: EA = (BASE) + Displacement. When a program is loaded in the memory, the relevant base register is also loaded with load address. For example, the program shown above will now look like:

       in program file                  in memory
0000    JMP    0020               1000   JMP     0020
0010    0100                      1010   0100
0014         Y                    1014     Y
0020    LD     -6                 1020   LD      -6
0024    ADD B I  -14              1024   ADD B I -14
        ...    ...                       ...     ...
0100         X                    1100   X

The ‘B’ flag in the ADD instruction indicates that the address constant at displacement of –14 with respect to IP is taken to be displacement with respect to the Base register. Thus, EA = (IP – 14) + (BASE) which gives the correct value 1100.

C.4.3 Virtual Memory and Loader

With infinite memory, many of the things that an loader has to do would be redundant. One of the basic tricks of any operating system is the ability to make a small amount of physical memory behave like rather large memory. This apparently large memory is known as virtual memory. The idea is that various programs running in the system (i.e. processes) are fooled into believing that they are running in a large memory, typically a few Gigabytes.

The system divides the virtual memory into easily handled pages and swaps these pages to and from a hard disk partition as the system runs. A process does not notice because this swapping is done when the process is waiting its turn for use of the CPU (see Fig. C.9).

 

Fig. C.9 Page frames in the physical memory are assigned as pages to processes. All pages of a process need not be in the physical memory simultaneously

Whenever a process needs to access particular page which is not already loaded in the physical memory, a page fault occurs, the memory management function of the operating system takes over and loads the page from the disc into an empty page frame. In case an empty page frame is not available, a page frame which was not active for the largest length of time is emptied, by copying its contents to the swap disc if required (see Fig. C.10).

 

Fig. C.10 Virtual memory management

With such an arrangement, the memory assigned to all programs always begin at location 0. The libraries are usually shared between processes and only one copy is loaded as required in the physical memory. They have to use PIC, but the user (application) programs need not.