Module IV System Software(CST 305)

MODULE IV
• Linker and Loader
o Basic Loader functions
 Design of absolute loader
 Simple bootstrap Loader
o Machine dependent loader features
 Relocation
 Program Linking
• Algorithm and data structures of two pass Linking Loader
o Machine independent loader features
 Automatic Library Search
 Loader Options
o Loader Design Options.

• Linker and Loader

o Loading: Brings the object program into memory for execution.
o Relocation: Modifies the object program so that it can be loaded at an
address different from the location originally specified.
o Linking: Combines two or more separate object programs and supplies the
information needed to allow references between them.
o Loader is a system program that performs the loading function. Many
loaders also support relocation and linking.
o Linker (linkage editor) is a system program that performs the linking
operations and need a separate loader to handle relocation and loading.
o Linking Loader is a system program that having both linking and loading
capabilities.

o Basic Loader Functions

 Bringing an object program into memory.
 Starting its execution.

o Basic Loader Functions

 Allocation: Allocates the space for program in the memory, by
calculating the size of the program. Allocation is done by the
programmer.
 Linking: It resolves the symbolic references (code/data) between the
object modules by assigning all the user subroutine and library
subroutine addresses. Linking is done by the programmer.

1 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

 Relocation: There are some address dependent locations in the program,

such address constants must be adjusted according to allocated space.
Relocation is done by the assembler.
 Loading: Places all the machine instructions and data of corresponding
programs and subroutines into the memory. Loading is done by the
loader.

o Type of loaders
 Absolute loader
 Bootstrap loader
 Assemble-and-go loader
 Relocating loader (Relative loader)
 Direct linking loader

o Absolute loader
 The object code is loaded to the specified location in the memory.
 All functions are accomplished in a single pass as follows:
• The Header record of object programs is checked to verify that the
correct program has been presented for loading.
• As each Text record is read, the object code it contains is moved to
the indicated address in memory.
• When the End record is encountered, the loader jumps to the
specified address to begin execution of the loaded program.
 No linking and relocation needed.

2 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

 Example: Consider the following object program

• Each pair of bytes from the object program record must be packed
together into one byte during loading.
• Eg: Opcode for STL is 14. It is saved in object program as 2 bytes(2
characters). While loading it is converted to single byte(00010100).
• The content of the memory location for which there is no Text
record are shown as xxxx.

 Advantage:
• Simple
• Efficient(less space and loading time)
 Disadvantage:
• Programmer should specify the actual address
o If the system having small memory, only one program can run at
a time. So it does not create much difficulty to specify the
address.

3 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

o On a larger system, we are supposed to run several independent

programs. It is not easy to specify actual address while writing
programs.
• Difficult to use subroutines libraries efficiently.
o If there are multiple subroutines, the programmer must
remember the address of each and use that absolute address
explicitly in other subroutines to perform subroutine linkage.
o Solution: Write relocatable programs instead of absolute ones.

o Bootstrap Loader
 It is a special type of absolute loader.
 When a computer is first turned on or restarted, bootstrap loader is
executed.
 This bootstrap loads the operating system into memory.
 The bootstrap itself begins at address 0
 It loads the OS(from device F1) starting at address 0x80.
 The object code having no header record, end record or control
information.
 After loading the OS, the control is transferred to the instruction at
address 0x80.

 Algorithm
X = 0x80 //initial location of the OS to be loaded
Loop
{ A = GETC //read and convert from ASCII to hexadecimal digit
Save the value in the higher order 4 bits of S
A = GETC //read and convert from ASCII to hexadecimal digit
Combine the value to form one byte A = (A + S)
Store the value of A to the address in register
X=X+1
}

4 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

Algorithm for GETC

A = read one character
If A = 0x04 then jump to 0x80 //end of file
If A < 48 then GETC // ignore the character if it is < 0
A = A – 48 // convert to hexadecimal
If A < 10 then return
A=A–7
return
• Register X keeps the address of the next memory location to be
loaded.
• GETC is used to read and convert a pair of characters from device
F1.
• These 2 hexadecimal digit values are combined into a single byte by
shifting the first one left 4 bit positions and adding the second to it.
• The resulting byte is stored at the address currently in register X.

 Program

5 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

 Eg: = C “D8”

o Machine-Dependent Loader Feature

 Shortcoming of an absolute loader
• Programmer needs to specify the actual address at which it will be
loaded into memory.
• It is difficult to run several programs concurrently, sharing memory
between them.
• It is difficult to use subroutine libraries.
 Solution:
• A more complex loader that provides
o Program relocation
o Program linking
 The machine dependent loader features are
• Relocation
• Linking

 Program Relocation
• Program Relocation
o The object program is loaded into memory wherever there is
room for it.
o The actual starting address of the object program is not known
until load time.
• Relocating Loader / Relative Loader: Loaders that allow program
relocation.
• Two methods for specifying relocation as part of the object
program
o Modification records
o Relocation bits

6 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

• Modification records
o A Modification record is used to describe each part of the object
code that must be changed when the program is relocated.
o Used when a small number of relocations is required.
o Format

o Example

7 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

• Most of the instructions in this program use relative or

immediate addressing
• Lines 15, 35 and 65 are the only items whose values are
affected by program relocation.
• The object program should have one modification record
for each value that must be changed during relocation.
 The object program is

8 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

o Algorithm
Get PROGADDR from Operating System
Read a record from input file
While record_type != ‘E’ do
{
If record_type = ‘T’ do
{
Move object code from record to location PROGADDR + Specified address
}
If record_type = ‘M’ do
{
Add PROGADDR at the location (PROGADDR + Specified address)
}
Read next input record
}
o Disadvantage
 It is not well suited for use with all machine architectures. It
is not suited for standard SIC programs.

• Relocation bits
o Each instruction is associated with one relocation bit
o These relocation bits are gathered into bit masks in a Text
record.
 Relocation bit is 0: no modification is needed
 Relocation bit is 1: modification is needed.
o Used when a large number of relocations is required.
o Format

o Twelve-bit mask is used in each Text record (col:10-12)

o Each text record contains less than 12 words
o Unused words are set to 0
o For absolute loader, there are no relocation bits. Column 10-69
contains object code.
o Example: Relocatable program for standard SIC machine

9 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

10 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

 The standard SIC machine does not use relative addressing

(PC-relative, Base-relative)
 All instructions expect RSUB need relocation
 Too many modification records are required if we adopt the
1st method. So we move to relocation bit method.
 Object program is

• The underlined hexadecimal digits in the object program

represent the bit mask.
• FFC
o FFC  111111111100
o All ten words are to be modified
• E00
o E00  111000000000
o First three records are to be modified.
o Algorithm
Get PROGADDR from Operating System
Read a record from the input file
While record_type != ‘E’ do
{
If record_type = ‘T’ do
{
length = number of words in the text record
Get the mask bits (M)
for i=0 to length do
{
If Mi = 1 then
Add PROGADDR to object code and move that data to the location
(PROGADDR + Specified address)
else
Move object code from record to location PROGADDR + Specified address
}
}
Read next input record
}

11 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

 Program Linking
• The goal of program linking is to resolve the problems with external
references (EXTREF) and external definitions (EXTDEF) from
different control sections.
o EXTDEF (external definition) - The EXTDEF statement in a
control section names symbols that are defined in present control
section and may be used by other sections.
 Eg: EXTDEF LISTA, ENDA

 The Define Record is used to represent symbols in the object

program
 Syntax:

• Eg: D^LISTA ^000040^ENDA ^000054

o EXTREF (external reference) - The EXTREF statement names

symbols used in present control section and are defined
elsewhere.
 Eg: EXTREF LISTB,ENDB,LISTC,ENDC

 The Refer Record is used to represent symbols in the object

program
 Syntax:

• Eg: R^ LISTB ^ENDB ^LISTC ^ENDC

• Example: Here are the three programs named as PROGA, PROGB

and PROGC, which are separately assembled and each of which
consists of a single control section.

12 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

13 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

14 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

15 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

• LISTA, ENDA in PROGA, LISTB, ENDB in PROGB and LISTC,

ENDC in PROGC are external definitions in each of the control
sections.
• Similarly LISTB, ENDB, LISTC, ENDC in PROGA, LISTA,
ENDA, LISTC, ENDC in PROGB, and LISTA, ENDA, LISTB,
ENDB in PROGC, are external references.
• Each program contains
o Instruction operands (REF1, REF2, REF3).
o Values of data words (REF4 through REF8).
o Consider REF1 in all control sections: +LDA LISTA
 PROGA
• Here LISTA is the label in the current control section.
• The instruction is PC relative and will get the correct
object code (03201D).
 PROGB, PROGMC
• Here LISTA is a reference to an external symbol.
• We will not get the correct object code. Simply set the
address field to 0.
• Also place a modification record in the object program.
It instructs the loader to add the value of the symbol
LISTA to this address field when the program is linked.

o Consider REF2: REF2 +LDT LISTB+4

 PROGA, PROGC
• Store the value of constant in the address field(00004)
• There should be one modification record which instructs
the loader to add to this field the value of LISTB.
 PROGB
• LISTB is the label in the current control section.
• The instruction is PC relative and the will get the object
code (772027).

o Consider REF4: REF4 WORD ENDA-LISTA+LISTC

 PROGA
• Here LISTA and ENDA are the labels in the current
control section.
• LISTC is a reference to an external symbol.

16 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

• The object code is the value of ENDA-LISTA (000014),

which is a temporary value.
• Place a modification record for LISTC
• While loading the starting address of
o PROGA is 4000
o PROGB is 4063
o PROGC is 40E2
• Starting address of REF4 in PROGA is 4054(beginning
address of PROGA + 0054)

 PROGB
• Here LISTA, ENDA and LISTC are the references to
external symbols
• Put 000000 as object code.
• Place modification records for LISTA, ENDA and
LISTC

 PROGC
• Here LISTA and ENDA are the references to external
symbols
• LISTC is the labels in the current control section.
• The object code is the value of LISTC (000030). While
loading PROGC the address of LISTC may change. So
place a modification record for PROGC.
• Place two more modification records for LISTA and
ENDA

17 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

• The program in memory after relocation, linking and loading

18 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

o Algorithm and Data Structures for a Linking Loader

 Input: set of object programs (control sections) that are to be linked
together.
 A linking loader usually makes two passes over its input
• Pass 1: Assigns addresses to all external symbols.
• Pass 2: Performs the actual relocation, linking and loading.
 Data structure used is External Symbol Table (ESTAB). The fields are
• Control sections name
• Name each external symbol
• Address of each external symbol
 Two other important variables are:
• PROGADDR (program load address)
o The beginning address in memory where the linked program is
to be loaded.
o Its value is supplied to the loader by the OS.
• CSADDR (control section address)
o The starting address assigned to the control section currently
being scanned by the loader
 A hashed organization is used for this table

 Pass 1
• The loader is concerned only with Header and Define records in the
control sections
• The beginning load address for the linked program (PROGADDR)
is obtained from the OS. This becomes the starting address
(CSADDR) for the first control section in the input sequence.
• The control section name from Header record is entered into
ESTAB, with value given by CSADDR. All external symbols
appearing in the Define record for the control section are also
entered into ESTAB. Their addresses are obtained by adding the
value specified in the Define record to CSADDR.
• When the End record is read, the control section length CSLTH is
added to CSADDR. This calculation gives the starting address for
the next control section in sequence.
• At the end of Pass 1, ESTAB contains all external symbols defined
in the set of control sections together with the address assigned to
each.
• Pass 1 optionally generate load map

19 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

 Pass 2
• As each Text record is read, the object code is moved to the
specified address + CSADDR.
• When a Modification record is encountered, the symbol whose value
is to be used for modification is looked up in ESTAB.
• This value is then added to or subtracted from the indicated location
in memory.
• The last step performed by the loader is usually the transferring of
control to the loaded program to begin execution.
o The End record for each control section may contain the address
of the first instruction in that control section to be executed. Our
loader takes this as the transfer point to begin execution.
o If more than one control section specifies a transfer address, the
loader arbitrarily uses the last one encountered.
o If no control section contains a transfer address, the loader uses
the beginning of the linked program (i.e., PROGADDR) as the
transfer point.
o Normally, a transfer address would be placed in the End record
for a main program, but not for a subroutine.

20 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

Pass 1 Linking Loader Algorithm

Get PROGADDR from OS
CSADDR = PROGADDR \\ for the 1st control section
While not end of input do
{
Read the next input record \\ header record for the control section
CSLTH = control section length
Search ESTAB for the control section name
If found then
Set error flag
Else
Enter control section name and CSADDR into ESTAB
While record_type != ‘E’ do
{
Read the next input record
If record_type = ‘D’ then
{
For each symbol in the record do
{
Search ESTAB for symbol name
If found then
Set error flag
Else
Enter symbol and (CSADDR + indicated address) into ESTAB
}
}
}
CSADDR = CSADDR + CSLTH //starting address of the next control section
}

21 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

Pass 2 Linking Loader Algorithm

CSADDR = PROGADDR \\ for the 1st control section
EXECADDR = PROGADDR
While not end of input do
{
Read the next input record \\ header record for the control section
CSLTH = control section length
While record_type != ‘E’ do
{
Read the next input record
If record_type = ‘T’ then
{
If the object code is in character form then
Convert it into internal representation
Move the object code from record to location (CSADDR + specified address)
}
Else if record_type = ‘M’ then
{
Search ESTAB for modification symbol name
If found then
Add or subtract the symbol value at location (CSADDR + specified address)
Else
Set error flag
}
}
If an address is specified in End record then
EXECADDR = CSADDR + specified address
CSADDR = CSADDR + CSLTH
}
Jump to location given by EXECADDR to start execution of the program

 We can make the linking loader algorithm more efficient by

• Assigning a reference number to each external symbol referred to in
a control section
o 01: control section name
o 02~: external reference symbols
• Use this reference number (instead of the symbol name) in
Modification records
• Advantage of this reference-number mechanism:
o It avoids multiple searches of ESTAB for the same symbol
during the loading of a control section.

22 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

 Search of ESTAB for each external symbol can be

performed once and the result is stored in a table indexed by
the reference number.
 The values for code modification can then be obtained by
simply indexing into the table.

• The object program will be as follows

23 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

o MACHINE-INDEPENDENT LOADER FEATURES

 Loading and linking are OS service functions.
 Following are the machine-independent loader features
• Automatic Library Search
• Loader Options

 Automatic Library Search(Automatic Library Call)

• This feature allows a programmer to use standard subroutines
without explicitly including them in the program to be loaded.
• This feature allows the programmer to use subroutines from one or
more libraries (eg: mathematical or statistical routines).
• These subroutines are automatically retrieved from a library, linked
with main program and loaded as they are needed during linking.
• The programmer needs to mention these subroutine names as
external references in the source program.
• Steps:
o Linking loaders that support automatic library search must keep
track of external symbols that are referred to in the primary input
to the loader.
o At the end of Pass 1, the symbols in ESTAB that remain
undefined represent unresolved external references.

24 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

o The loader searches the library or libraries specified for routines

that contain the definitions of these symbols, and processes the
subroutines found by this search exactly as if they had been part
of the primary input stream.
o The subroutines fetched from a library in this way may
themselves contain external references. It is therefore necessary
to repeat the library search process until all references are
resolved.
o If unresolved external references remain after the library search
is completed, these must be treated as errors.
• It also allows the programmer to override standard subroutines.
o Example
 Suppose the main program refers to a standard subroutine
SQRT.
 A programmer wanted to use a different version of SQRT by
including it as input to the loader.
 By the end of Pass1 of the loader, SQRT would already be
defined, so it would not be included in any library search.
• The libraries to be searched by the loader ordinarily contain
assembled or compiled versions of the subroutines (i.e., object
programs)
• In most cases a special file structure is used for the libraries. This
structure contains a directory that gives the name of each routine and
a pointer to its address within the file.
• Some operating systems can keep the directory for commonly used
libraries permanently in memory.
• The same technique applies equally well to the resolution of external
references to data items

 Loader Options
• Many loaders allow the user to specify options that modify the
standard processing.
• Many loaders have a special command language that is used to
specify loader options.
• Different ways to provide these control statements
o A separate input file to the loader that contains such control
statements.
o These statements are embedded in the primary input stream
between object programs
25 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

o Include these statements in source program, and the assembler

retains these commands as a part of the object program.
• Loader option 1: Allows the selection of alternative sources of
input.
o Command: INCLUDE program-name (library-name)
Direct the loader to read the designated object program from a
library and treat it as if it were part of the primary loader input.
• Loader option 2: Allows the user to delete or change external
symbols or entire control sections.
o Command: DELETE csect-name
Instruct the loader to delete the named control section(s) from
the set of programs being loaded.
o Command: CHANGE name1, name2
The external symbol name1 to be changed to name2.
o Example: Suppose we have a main program COPY and two
subroutines RDREC and WRREC, each of these are separate
control sections. Suppose that READ and WRITE are the two
utility subroutines which perform the functions as RDREC and
WRREC. The following commands allow the main program
COPY to use these utility subroutines.

 It direct the loader to include control sections READ and

WRITE from the library UTLIB
 Delete the control section RDREC and WRREC
 All external references to RDREC is changed to refer to
symbol READ
 All external references to WRREC is changed to refer to
symbol WRITE
• Loader option 3: Involves the automatic inclusion of library
routines to satisfy external references.
o Command: LIBRARY MYLIB
Such user-specified libraries are normally searched before the
standard system libraries. This allows the user to use special
versions of the standard routines.

26 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

o Suppose the main function of a program is used to gather and

sort data. The program also performs an analysis of data using
the routines STDDEV, PLOT and CORREL from a statistical
library. Suppose this statistical analysis is not performed in a
particular execution, use the following command.
NOCALL STDDEV, PLOT, CORREL
This instructs the loader that these external references are to
remain unresolved. This avoids the overhead of loading and
linking the unneeded routines, and saves the memory space that
would otherwise be required.
• Loader option 4: It is possible to specify that no eternal references
be resolved by library search. This means that an error will result if
the program attempts to make such an external references during
execution. This option is useful when programs are to be linked but
not executed immediately.
• Loader option 5: Can control output from loader
o A load map may be generated during loading process
o Through control statements the user can specify whether or not
such a map is to be printed at all.
o If a map is desired, the level of detail can be selected.
 Ex: the map may include control section name and address
only
• Loader option 6: Ability to specify the location at which execution
is to begin (Overriding any information given in the object
program).
• Loader option 7: To control whether or not the loader should
attempt to execute the program if errors are detected during the load
operation.
o Ex: unresolved eternal references.

27 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

O LOADER DESIGN OPTIONS

 Linking loader:
• The source program is assembled or compiled, producing an object
program which may contain several control sections.
• A linking loader performs all linking and relocation operations,
including automatic library search if specified, and loads the linked
program directly into memory for execution.

• Disadvantage: The linking loader searches the libraries and resolves

external references every time the program is executed.
• Advantage:
o When the program is used so infrequently, it is not worthwhile
to store the assembled version in a library. In such cases it is
more efficient to use linking loader.
o It is used in a program development and testing environment
• There are two alternatives design options:
o Linkage Editor
o Dynamic Linking

• Linkage Editor
o Which perform linking prior to load time
o It produces a linked version of the program (load module or
executable image), which is written to a file or library for later
execution.
o A simple relocating loader can be used to load the linked version
of program into memory for execution.

28 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

o The Linkage Editor performs relocation of all control sections

relative to the start of the linked program.
o The only object code modification necessary is the addition of
an actual load address to relative values within the program.
o Relocation is indicated by some mechanisms such as
Modification Records or Bit Masks.
o Advantage:
 The loading can be accomplished in one pass with no
external symbol table required. This involves much less
overhead than using a linking loader
 Reduce the time: If Resolution of external references and
library searching are only performed once. It will reduces the
load time.
o One variant: If the actual address at which the program will be
loaded is known in advance, the linkage editor can perform all of
the needed relocation. The result is a linked program that is an
exact image of the way the program will appear in memory
during execution. In this case only an absolute loader is needed
to load object code into memory.
o Linkage editors can perform many useful functions
 The linkage editor can be used to replace the subroutines in
the linked version
• Eg: Suppose PLANNER is a program that uses a large
number of subroutines. One subroutine among them is
PROJECT. We can write a new version of PROJECT to
improve its efficiency. After the new version of

29 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

PROJECT is assembled, the linkage editor can be used to

replace this subroutine in the linked version of all the
other subroutines. Use the following code for this
purpose.

 Linkage editors can also be used to build packages of

subroutines or other control sections that are generally used
together.

• Suppose there are few closely related subroutines in the

directory FTNLIB. The above command sequence
combines these subroutines from the directory FTNLIB
and produces a linked module called FTNIO. It is then
insert in to the directory SUBLIB. Thus the search of
SUBLIB before FTNLIB would retrieve FTNIO instead
of the separate routines.

• Dynamic Linking (Dynamic Loading or Load on call)

o The linking function is performed at execution time.
o A subroutine is loaded and linked to the rest of the program
when it is first called
o Dynamic linking provides the ability to load the routines only
when they are needed
o Advantage:
 Allow several executing programs to share one copy of a
subroutine or library
 Allow to share one object by several programs:
• In object-oriented system, it allows the implementation
of the object and its methods to be determined at the time
the program is run.

30 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

 Load the routines only when they are needed:

• Suppose a program contains subroutines that correct
errors in the input data during execution. If such errors
are rare, this subroutine may not be used for all
executions. Dynamic linking provides the ability to load
the routines only when they are needed. This will save
time and memory space.
 Avoid to load the entire library for each execution
• Suppose a program uses a library that contains large
number of subroutines. The exact routine can not be
predicted until the program examines its input. Dynamic
linking loads the required subroutines instead of entire
library for each execution.
o Dynamic loading must be called via an operating system service
requests (Load-and-call services)
 OS examines its internal tables to determine whether or not
the routine is already loaded
 If not present
• Routine is loaded from library
• Control is passed from OS to the called subroutine
• Subroutine is finished
 Else
• Control is passed to a subroutine which is already in
memory

31 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

 Fig (a): The user program contains a JSUB instruction

referring to an external symbol. The program makes a load-
and-call service request to OS. The parameter of this request
is the symbolic name of the routine to be called.
 Fig (b): OS examines its internal tables to determine whether
or not the routine is already loaded. If necessary, the routine
is loaded from the specified user or system libraries.
 Fig (c): Control is then passed from OS to the routine being
called
 Fig (d): When the called subroutine completes it processing,
it returns to its caller (i.e., OS). OS then returns control to
the program that issued the request.
 Fig (e): If a subroutine is still in memory, a second call to it
may not require another load operation. Control may simply
be passed from the dynamic loader to the called routine.
 This subroutine should retain in memory for later use as long
as there is enough space. If the program requires more space,
it may remove from memory.
o Binding of the name to an actual address is delayed from load
time until execution time

 Bootstrap Loaders
• Given an idle computer with no program in memory, how do we get
things started?
• With the machine empty and idle there is no need for program
relocation.
• We can specify the absolute address for which the OS is first loaded.
• An absolute loader is used to accomplish this task.

32 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

• Different options:
o Required an operator to enter the object code for an absolute
loader into memory using switches on the computer console.
 Disadvantage: Inconvenient and error prone
• The absolute loader program may permanently resident in a ROM.
o When some hardware signal occurs (the operator pressing a
system start switch), the machine begins to execute this ROM
program.
o There are 2 options
 The program is executed directly in the ROM
 The program is copied from ROM to main memory and
executed there.
o Disadvantage:
 Some systems do not have such read only storage
 It is inconvenient to change the ROM program, if the
modification in the absolute loader is required.
• Have a built in hardware function (or a short ROM program) that
reads a fixed length record from some device into memory at a fixed
location.
o This device may be selected via console switches.
o After the read operation is complete, control is automatically
transferred to the address in memory where the record was
stored.
o This record contains machine instructions that load the absolute
program that follows.
o The first record is generally referred to as bootstrap loader
o This first record causes the reading of others, and these in turn
can cause the reading of still more records – hence the term
boots trap.
o Such a loader is added to the beginning of all object programs.
o This includes the OS itself and all stand-alone programs that are
to be run without an OS.

33 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck
Module IV System Software(CST 305)

Previous Year University Questions

1. What are the basic loader functions?
2. Give the algorithm for an absolute loader
3. Outline the need and functions of a bootstrap loader.
4. Given an idle computer with no programs in memory, how do we get things
started?

5. Define a modification record along with its structure

6. What is the use of bitmask in program relocation? Illustrate with example
7. Describe the data structures used for the linking loader algorithm. Give the
algorithm for pass 1 of the linking loader.
8. Describe the structure and the use of the ESTAB data structure used in the two
pass linking loader
9. Which are the data structures used during the operation of a linking loader?
Write the algorithm for Pass 2 of a Linking Loader
[Link] the algorithm for pass 2 of a linking loader.
[Link] the data structures used, state and explain two pass algorithm for a linking
loader.

[Link] notes on machine independent loader features.

[Link] any one machine independent loader feature.
[Link] the different machine dependent and machine independent features of a
loader. Explain any two machine independent features
[Link] is Automatic Library Search?

[Link] notes on the different loader design options.

[Link] a help of neat diagram explain what is a linkage editor?
[Link] between linking loaders and linkage editors
[Link] is Dynamic Linking? Explain with example.
[Link] the process of dynamic linking.

34 CS KTU LECTURES
Reference Book: System Software: An Introduction to System Programming, Leland L Beck