1

System Software

There are two broad categories of software:

System Software
Application Software

System Software is a set of programs that manage the resources of a compute system.
System Software is a collection of system programs that perform a variety of functions.
File Editing
Resource Accounting I/O
Management
Storage, Memory Management access management.
System Software can be broadly classified into three types as:

System control programs controls the execution of programs, manage the storage &

VTUPulse.com
processing resources of the computer & perform other management & monitoring
function. The most important of these programs is the operating system. Other examples
are database management systems (DBMS) & communication monitors.

System support programs provide routine service functions to the other computer
programs & computer users: E.g. Utilities, libraries, performance monitors & job
accounting.
System development programs assists in the creation of application programs. E.g.,
language translators such as BASIC interpreter & application generators.

Application Software:
It performs specific tasks for the computer user. Application software is a program
which program written for, or, by, a user to perform a particular job.
Languages already available for microcomputers include Clout, Q & A and Savvy ret
rival (for use with Lotus 1-2-3).
The use of natural language touches on expert systems, computerized collections of the
 2

knowledge of many human experts in a given field, and artificial intelligence,

independently smart computer systems – two topics that are receiving much attention
and development and will continue to do so in the future.

VTUPulse.com
 3

1. Operating System Software

Storage Manager
Process Manager
File – System Manager I/O
Control System
Communication Manager

2. Standard System Software

Language Processor
Loaders Software
Tools

3. Application Software
Sort/Merge Package
Payroll/Accounting Package
DBMS

VTUPulse.com
General-purpose application software such as electronic spreadsheet has a wide variety
of applications. Specific – purpose application s/w such as payroll & sales analysis is
used for the application for which it is designed
Application programmer writes these programs. Application programmer writes these
programs.

Generally computer users interact with application software. Application and system
software act as interface between users & computer hardware. An application & system
software become more capable, people find computer easier to use.

The Interaction between Users, Application Software, System Software &

Computer Hardware:
 4

System Software controls the execution of the application software & provides other
support functions such as data storage. E.g. when you use an electronic spreadsheet on
the computer, MS-DOS, the computer’s Operating System, handles the storage of the
worksheet files on disk.
The language translators and the operating system are themselves programs. Their
function is to get the users program, which is

VTUPulse.com
 5

written, in a programming language to run-on the computer system.

All sucl. Programs, which help in the execution of user programs, are called system
programs (SPs). The collection of such SPs is the “System Software” of a particular
computer system.
Mast computer systems have support software, called Utility Programs, which perform
routine tasks. These programs sort data, copy data from one storage medium to another,
o/p data from a storage medium to printer & perform other tasks.

the execution at a specified starting address.

VTUPulse.com
 6

VTUPulse.com
 7

VTUPulse.com
 8

VTUPulse.com
 9

VTUPulse.com
 10

System Development Software:

System Development Software assists a programmer of user in developing & using
an application program.
E.g. Language Translators
Linkage Editors Application
generators

Language Translators:
A language translator is a computer program that converts a program written in a
procedural language such as BASIC into machine language that can be directly
executed by the computer.
Computers can execute only machine language programs. Programs written in any other
language must be translated into a machine language load module, which is suitable for
loading directly into primary storage.
Subroutine or subprograms, which are stored on the system residence device to perform
a specific standard function. E.g. if a program required the calculation of a square root,

VTUPulse.com
Programmer would not write a special program. He would simply call a square root,
subroutine to be used in the program.
Translators for a low-level programming language were assemblers

Language processors
Language Processing Activities
Language Processing activities arise due to the differences between the manner in
which a software designer describes the ideas concerning the behaviour of a software
and the manner in which these ideas are implemented in a computer system.
the interpreter is a language translator. This leads to many similarities between are

Translators and interpreters. From a practical viewpoint many differences also

exist

between translators and interpreters.

The absence of a target program implies the absence of an output interface the
interpreter. Thus the language processing activities of an interpreter cannot be separated
from its program execution activities. Hence we say that an interpreter 'executes' a
 11

program written in a PL.

VTUPulse.com
 12

Problem Oriented and Procedure Oriented Languages:

The three consequences of the semantic gap mentioned at the start of this section
are in fact the consequences of a specification gap. Software systems are poor in
quality and require large amounts of time and effort to develop due to difficulties in
bridging the specification gap. A classical solution is to develop a PL such that the
PL domain is very close or identical to the application domain.

Such PLs can only be used for specific applications; hence they are called problem-
oriented languages. They have large execution gaps, however this is acceptable because
the gap is bridged by the translator or interpreter and does not concern the software
designer.

A procedure-oriented language provides general purpose facilities required in most

application domains. Such a language is independent of specific application domains.

The fundamental language processing activities can be divided into those that bridge
the specification gap and those that bridge the execution gap. We name these activities
as
1. Program generation activities

VTUPulse.com
2. Program execution activities.

A program generation activity aims at automatic generation of a program. The source

languages specification language of an application domain and the target language is
typically a procedure oriented PL. A Program execution activity organizes the
execution of a program written in a PL on computer system. Its source language could
be a procedure-oriented language or a problem oriented language.

Program Generation
The program generator is a software system which accepts the specification of a
program to be generated, and generates a program in the target PL. In effect, the
program generator
 13

introduces a new domain between the application and PL domains we call this the
program generator domain. The specification gap is now the gap between the
application domain and the program generator domain. This gap is smaller than the gap
between the application domain and the target PL domain.
Reduction in the specification gap increases the reliability of the generated program.
Since the generator domain is close to the application domain, it is easy for the designer
or programmer to write the specification of the program to be generated.
The harder task of bridging the gap to the PL domain is performed by the generator.
This arrangement also reduces the testing effort. Proving the correctness of the pro-
gram generator amounts to proving the correctness of the transformation.
This would be performed while implementing the generator. To test an application
generated by using the generator, it is necessary to only verify the correctness of the
specification input to the program generator. This is a much simpler task than verifying
correctness of the generated program. This task can be further simplified by providing
a good diagnostic (i.e. error indication) capability in the program generator, which
would detect inconsistencies in the specification.
It is more economical to develop a program generator than to develop a problem-

VTUPulse.com
oriented language. This is because a problem- oriented language suffers a very large
execution gap between the PL domain and the execution domain whereas the program
generator has a smaller semantic gap to the target PL domain, which is the domain of a
standard procedure oriented language. The execution gap between the target PL domain
and the execution domain is bridged by the compiler or interpreter for the PL.

Program Execution
Two popular models for program execution are translation and interpretation.

Program translation
The program translation model bridges the execution gap by
translating a program written in a PL, called the source program (SP), into an equivalent
program in the machine or assembly language of the computer system, called the target
program (TP) Characteristics of the program translation model are:

A program must be translated before it can be executed.

• The translated program may be saved in a file. The saved program may be executed
 14

repeatedly.
• A program must be retranslated following modifications.

VTUPulse.com
 15

Program interpretation

The interpreter reads the source program and stores it in its memory. During
interpretation it takes a source statement, determines its meaning and performs actions
which implement it. This includes computational and input-output actions.
The CPU uses a program counter (PC) to note the address of the next instruction to be
executed. This instruction is subjected to the instruction execution cycle consisting of
the following steps:

1. Fetch the instruction.

2. Decode the instruction to determine the operation to be
performed, and also its operands.
3. Execute the instruction.
At the end of the cycle, the instruction address in PC is updated and the cycle is repeated
for the next instruction. Program interpretation can proceed in an analogous manner.

VTUPulse.com
Thus, the PC can indicate which statement of the source program is to be interpreted
next. This statement would be subjected to the interpretation cycle, which could consist
of the following steps:

Fetch the statement.

Analyze the statement and determine its meaning, viz. the computation to be
performed and its operands.

Execute the meaning of the statement.

From this analogy, we can identify the following characteristics of interpretation:
The source program is retained in the source form itself, i.e. no target program form
exists, A statement is analyzed during its interpretation.

Comparison
A fixed cost (the translation overhead) is incurred in the use of the program translation
model. If the source program is modified, the translation cost must be incurred again
 16

irrespective of the size of the modification. However, execution of the target program
is efficient since the target program is in the machine language. Use of the interpretation
model does not incur the translation overheads. This is advantageous if a program is
modified between executions, as in program testing and debugging.

VTUPulse.com
 17

FUNDAMENTALS OF LANGUAGE PROCESSING

Definition
Language Processing = Analysis of SP + Synthesis of TP.
Definition motivates a generic model of language processing
activities.
We refer to the collection of language processor components engaged in analyzing a
source program as the analysis phase of the language processor. Components engaged
in synthesizing a target program constitute the synthesis phase.
A specification of the source language forms the basis of source program analysis. The
specification consists of three components:
1. Lexical rules, which govern the formation of valid lexical units in the source
language.
2. Syntax rules which govern the formation of valid statements in the source language.
3. Semantic rules which associate meaning with valid statements of the language.
The analysis phase uses each component of the source language specification to
determine relevant information concerning a statement in the source program. Thus,
analysis of a source statement consists of lexical, syntax and semantic analysis.

VTUPulse.com
The synthesis phase is concerned with the construction of target language statement(s)
which have the same meaning as a source statement. Typically, this consist of two main
activities:
• Creation of data structures in the target program
• Generation of target code.
We refer to these activities as memory allocation and code generation, respectively

Lexical Analysis (Scanning)

Lexical analysis identifies the lexical units in a source statement. It then classifies the
units into different lexical classes e.g. id’s, constants etc. and enters them into different
tables. This classification may be based on the nature ofstring or on the specification of
the source language. (For example, while an integer constant is a string of digits with
an optional sign, a reserved id is an id whose name matches one of the reserved names
mentioned in the language specification.) Lexical analysis builds a descriptor, called a
token, for each lexical unit. A token contain two fields— class code, and number in
class, class code identifies the class to which a lexical unit belongs, number in class is
the entry number of the lexical unit in the relevant table.
 18

Syntax Analysis (Parsing)

Syntax analysis processes the string of tokens built by lexical analysis to determine the
statement class, e.g. assignment statement, if statement, etc. It then builds an IC which
represents

VTUPulse.com
 19

the structure of the statement. The IC is passed to semantic analysis to determine the
meaning of the statement.
Semantic analysis
Semantic analysis of declaration statements differs from the semantic analysis of
imperative statements. The former results in addition of information to the symbol table,
e.g. type, length and dimensionality of variables. The latter identifies the sequence of
actions necessary to implement the meaning of a source statement. In both cases the
structure of a source statement guides the application of the semantic rules. When
semantic analysis determines the meaning of a sub tree in the IC. It adds information a
table or adds an action to the sequence. It then modifies the IC to enable further semantic
analysis. The analysis ends when the tree has been completely processed.

“FUNDAMENTALS OF LANGUAGE SPECIFICATION

A specification of the source language forms the basis of source program analysis. In
this section, we shall discuss important lexical, syntactic and semantic features of a

VTUPulse.com
programming language.
Programming Language Grammars
The lexical and syntactic features of a programming language are specified by its
grammar. This section discusses key concepts and notions from formal language
grammars. A language L can be considered to be a collection of valid sentences.
Each sentence can be looked upon as a sequence of words, and each word as a sequence
of letters or graphic symbols acceptable in
L. A language specified in this manner is known as a. formal language. A formal
language grammar is a set of rules which precisely specify the sentences of L. It is clear
that natural languages are not formal languages due to their rich vocabulary. However,
PLs are formal languages.

Terminal symbols, alphabet and strings

The alphabet of L, denoted by the Greek symbol Z, is the collection of symbols in its
character set. We will use lower case letters a, b, c, etc. to denote symbols in Z.
A symbol in the alphabet is known as a terminal symbol (T) of L. The alphabet can be
represented using the mathematical notation of a set, e.g. Σ ≅ {a, b, ….z, 0,1 9}
Here the symbols {, ',' and} are part of the notation. We call them met symbols to
 20

differentiate them from terminal symbols. Throughout this discussion we assume that
met symbols are distinct from the terminal symbols. If this is not the case, i.e. if a
terminal symbol and a met symbol are identical, we enclose the terminal symbol in
quotes to differentiate it from the metasymbol. For

VTUPulse.com
 21

example, the set of punctuation symbols of English can be defined as {:,;’,’-,...} Where
',' denotes the terminal symbol 'comma'.
A string is a finite sequence of symbols. We will represent strings by Greek symbols-α
β γ, etc. Thus α = axy is a string over Σ . The length of a string is the Number of symbols
in it. Note that the absence of any symbol is also a string, the null string . The
concatenation operation combines two strings into a single string.
“

To evaluate an HLL program it should be converted into the Machine language. A

compiler performs another very important function. This is in terms of the diagnostics.
I.e. error – detection capability.
The important tasks of a compiler are:
Translating the HLL program input to it.
Providing diagnostic messages whenever specifications of the HLL

Compilers

VTUPulse.com
 22

VTUPulse.com
 23

• A compiler is a program that translates a sentence

a. from a source language (e.g. Java, Scheme, LATEX)

b. into a target language (e.g. JVM, Intel x86, PDF)
c. while preserving its meaning in the process
• Compiler design has a long history (FORTRAN 1958)

a. lots of experience on how to structure compilers

b. lots of existing designs to study (many freely available)
c. take CS 152: Compiler Design for some of the details. . .

VTUPulse.com
 24

VTUPulse.com
 25

VTUPulse.com
 26

VTUPulse.com
 27

VTUPulse.com
 28

VTUPulse.com
 29

VTUPulse.com
 30

VTUPulse.com
 31

VTUPulse.com
 32

VTUPulse.com
 33

VTUPulse.com
 34

VTUPulse.com
 35

Assemblers & compilers

Assembler is a translator for the lower level assembly language of computer, while

VTUPulse.com
compilers are translators for HLLs.

An assembly language is mostly peculated to a certain computer, while an HLL is

generally machined independent & thus portable.

Overview of the compilation process:

The process of compilation is:

Analysis of + Synthesis of = Translation of Source Text Target Text Program

Source text analysis is based on the grimmer of the source of the source language.

The component sub – tasks of analysis phase are:

Syntax analysis, which determine the syntactic structure of the source statement.
Semantic analysis, which determines the meaning of a statement, once its grammatical
structures become known.

The analysis phase

 36

The analysis phase of a compiler performs the following functions. Lexical analysis
Syntax analysis
Semantic analysis
Syntax analysis determines the grammatical or syntactic structure or the input statement
& represents it in an intermediate form from which semantic analysis can be performed.
A compiler must perform two major tasks:
The Analysis of a source program & the synthesis of its corresponding object program.

The analysis task deals with the decomposition of the source program into its basic parts
using these basic parts the synthesis task builds their equivalent object program
modules. A source program is a string of symbols each of which is generally a letter, a
digit or a certain special constants, keywords & operators. It is therefore desirable for
the compiler to identify these various types as classes.

VTUPulse.com
The source program is input to a lexical analyzer or scanner whose purpose is to
separate the incoming text into pieces or tokens such as constants, variable name,
keywords & operators.
In essence, the lexical analyzer performs low- level syntax analysis performs
low-level syntax analysis.
For efficiency reasons, each of tokens is given a unique internal
representation number.
TEST: If A > B then X=Y;
 37

The lexical analyzer supplies tokens to the syntax analyzer.

The syntax analyzer is much more complex then the lexical analyzer its function is
to take the source program from the lexical analyzer & determines the manner in
which it is to be decomposed into its constituent parts. That is, the syntax analyzer
determines the overall structure of the source program.
The semantic analyzer uses syntax analyzer.
The function of the semantic analyzer is to determine the meaning the meaning (or

VTUPulse.com
semantics) of the source program.
The semantic analyzer is passed on to the code generators.
At this point the intermediate form of the source language programs usually
translated to either assembly language or machine language.
The output of the code generator is passed on to a code optimizer. It’s purpose to
produce more program.

Introduction to Assemblers and Assembly

Language

Encoding instructions as binary numbers is natural and efficient for computers.

Humans, however, have a great deal of difficulty understanding and manipulating these
numbers. People read and write symbols (words) much better than long sequences of
digits. This lecture describes the process by which a human-readable program is
translated into a form that a computer can execute, provides a few hints about writing
assembly programs, and explains how to run these programs on SPIM,
 38

What is an assembler ?

A tool called an assembler translates assembly language into binary

instructions. Assemblers provide a friendlier representation than a computer’s 0s and
1s that simplifies writing and reading programs.
Symbolic names for operations and locations are one facet of this representation.
Another facet is programming facilities that increase a program’s clarity.

An assembler reads a single assembly language source file and produces an

object file containing machine instructions and bookkeeping information that helps
combine several object files into a program. Figure (1) illustrates how a program is
built. Most programs consist of several files—also called modules— that are written,
compiled, and assembled independently. A program may also use prewritten routines
supplied in a program library . A module typically contains References to subroutines
and data defined in other modules and in libraries. The code in a module cannot be
executed when it contains unresolved References to labels in other object files or

VTUPulse.com
libraries. Another tool, called a linker, combines a collection of object and library files
into an executable file , which a computer can run.

FIGURE 1: The process that produces an executable file. An assembler translates a

file of assembly language into an object file, which is linked with other files and
 39

libraries into an executable file.

1) Assembler = a program to handle all the tedious mechanical

translations

2) Allows you to use:

• symbolic opcodes
• symbolic operand values
• symbolic addresses

3) The Assembler
• keeps track of the numerical values of all symbols
• translates symbolic values into numerical values

4) Time Periods of the Various Processes in Program Development

VTUPulse.com
 40

VTUPulse.com
5) The Assembler Provides:

a. Access to all the machine’s resources by the assembled program. This includes
access to the entire instruction set of the machine.
b. A means for specifying run-time locations of program and data in memory.
c. Provide symbolic labels for the representation of constants and addresses.
d. Perform assemble-time arithmetic.

e. Provide for the use of any synthetic instructions.

f. Emit machine code in a form that can be loaded and executed.
g. Report syntax errors and provide program listings
h. Provide an interface to the module linkers and program loader.
 41

i. Expand programmer defined macro routines.

Assembler Syntax and Directives

Syntax: Label OPCODE Op1, Op2, ... ;Comment field

Pseudo-operations (sometimes called “pseudos,” or directives) are “opcodes” that

are actually instructions to the assembler and that do not result in code being
generated.

Assembler maintains several data structures

• Table that maps text of opcodes to op number and instruction format(s)

• “Symbol table” that maps defined symbols to their value

VTUPulse.com

Disadvantages of Assembly
• programmer must manage movement of data items between memory locations

and the ALU.

 42

• programmer must take a “microscopic” view of a task, breaking it down to

manipulate individual memory locations.
• assembly language is machine-specific.

• statements are not English-like (Pseudo-code)

Directives Assembler

1. Directives are commands to the Assembler

2. They tell the assembler what you want it to do, e.g.
a. Where in memory to store the code
b. Where in memory to store data
c. Where to store a constant and what its value is
d. The values of user-defined symbols

Object File Format

Assemblers produce object files. An object file on Unix contains six distinct

VTUPulse.com
sections (see Figure 3):

• The object file header describes the size and position of the other pieces of the
file.
• The text segment contains the machine language code for routines in the
source file. These routines may be unexecutable because of unresolved
references.
 43

• The data segment contains a binary representation of the data in the source
file. The data also may be incomplete because of unresolved references to
labels in other files.
• The relocation information identifies instructions and data words that depend
on absolute addresses. These references must change if portions of the program
are moved in memory.
• The symbol table associates addresses with external labels in the source file
and lists unresolved references.
• The debugging information contains a concise description of the way in
which the program was compiled, so a debugger can find which instruction
addresses correspond to lines in a source file and print the data structures in
readable form.

VTUPulse.com
The assembler produces an object file that contains a binary representation of the
program and data and additional information to help link pieces of a program. This
relocation information is necessary because the assembler does not know which
memory locations a procedure or piece of data will occupy after it is linked with the
rest of the program. Procedures and data from a file are stored in a contiguous piece
of memory, but the assembler does not know where this memory will be located. The
assembler also passes some symbol table entries to the linker. In particular, the
assembler must record which external symbols are defined in a file and what
unresolved references occur in a file.
 44

Macros
Macros are a pattern-matching and replacement facility that provide a simple
mechanism to name a frequently used sequence of instructions.

VTUPulse.com
 45

Instead of repeatedly typing the same instructions every time they are used, a
programmer invokes the macro and the assembler replaces the macro call with the
corresponding sequence of instructions. Macros, like subroutines, permit a
programmer to create and name a new abstraction for a common operation. Unlike
subroutines, however, macros do not cause a subroutine call and return when the
program runs since a macro call is replaced by the macro’s body when the program is
assembled. After this replacement, the resulting assembly is indistinguishable from the
equivalent program written without macros.

The 2-Pass Assembly Process

• Pass 1:

1. Initialize location counter (assemble-time “PC”) to 0

2. Pass over program text: enter all symbols into symbol table
a. May not be able to map all symbols on first pass
b. Definition before use is usually allowed

VTUPulse.com
3. Determine size of each instruction, map to a location

a. Uses pattern matching to relate opcode to pattern

b. Increment location counter by size
c. Change location counter in response to ORG pseudos
• Pass 2:

1. Insert binary code for each opcode and value

2. “Fix up” forward references and variable-sizes instructions
• Examples include variable-sized branch offsets and constant fields
 46

Linker & Loader

A software processor, which performs some low level processing of the programs input
to it, produces a ready to execute program form.
The basic loading function is that of locating a program in an appropriate area of the
main store of a computer when it is to be executed.

A loader often performs the two other important functions.

The loader, which accepts the program form, produced by a translator & certain other
program forms from a library to produce one ready – to – execute machine language
program.
A unit of input to the loader is known as an object program or an object module.
The process of merging many object modules to from a single machine language
program is known as linking.
The function to be performed by:
Assigning of loads the storage area to a program. Loading of a program
into the assigned area.

VTUPulse.com
Relocations of a program to execute properly from its load-time storage area.
Linking of programs with one another.
Loader, linking
software literature
loaders, linkage editors are used in

LOADER:
The loader is program, which accepts the object program decks, prepares this program
for execution by the computer and initializes the execution.
In particular the loader must perform four functions: Allocate space in
memory for the program (allocation).
Resolve symbolic references between objects decks (linking).
Adjust all address dependent locations, such as address constants, to correspond to the
allocated space (relocation).
 47

Physically place the machine instructions and data into memory (loading).

(Loaders and Linkers)

Introduction:

In this chapter we will understand the concept of linking and loading. As discussed
earlier the source program is converted to object program by assembler. The loader is
a program which takes this object program, prepares it for execution, and loads this
executable code of the source into memory for execution.
Definition of Loader:
Loader is utility program which takes object code as input prepares it for execution
and loads the executable code into the memory. Thus loader is actually responsible
for initiating the execution process.
Functions of Loader:
The loader is responsible for the activities such as allocation, linking, relocation
and loading
1) It allocates the space for program in the memory, by calculating the size of the

VTUPulse.com
program. This activity is called allocation.
2) It resolves the symbolic references (code/data) between the object modules
by assigning all the user subroutine and library subroutine addresses. This
activity is called linking.
3) There are some address dependent locations in the program, such address
constants must be adjusted according to allocated space, such activity done by
loader is called relocation.
4) Finally it places all the machine instructions and data of corresponding programs
and subroutines into the memory. Thus program now becomes ready for execution,
this activity is called loading.
Loader Schemes:
Based on the various functionalities of loader, there are various types of loaders:
1) “compile and go” loader: in this type of loader, the instruction is read line by line,
its machine code is obtained and it is directly put in the main memory at some known
address. That means the assembler runs in one part of memory and the assembled
machine instructions and data isdirectly put into their assigned memory locations. After
completion of assembly process, assign starting address of the program to the location
 48

counter. The typical example is WATFOR-77, it’s a FORTRAN compiler which uses
such “load and go” scheme. This loading scheme is also called as “assemble and go”.
Advantages:
• This scheme is simple to implement. Because assembler is placed at one part of the
memory and loader simply loads assembled machine instructions into the memory.
Disadvantages:
• In this scheme some portion of memory is occupied by assembler which is simply a
wastage of memory. As this scheme is combination of

assembler and loader activities, this combination program occupies large block of
memory.
• There is no production of .obj file, the source code is directly converted to executable
form. Hence even though there is no modification in the source program it needs to be
assembled and executed each time, which then becomes a time consuming activity.
• It cannot handle multiple source programs or multiple programs written in different
languages. This is because assembler can translate one source language to other target
language.

VTUPulse.com
• For a programmer it is very difficult to make an orderly modulator program and
also it becomes difficult to maintain such program, and the “compile and go” loader
cannot handle such programs.
• The execution time will be more in this scheme as every time program is assembled
and then executed.
2) General Loader Scheme: in this loader scheme, the source program is converted
to object program by some translator (assembler). The loader accepts these object
modules and puts machine instruction and data in an executable form at their assigned
memory. The loader occupies some portion of main memory.
Advantages:
• The program need not be retranslated each time while running it. This is because
initially when source program gets executed an object program gets generated. Of
program is not modified, then loader can make use of this object program to convert it
to executable form.
• There is no wastage of memory, because assembler is not placed in the memory,
instead of it, loader occupies some portion of the memory. And size of loader is
smaller than assembler, so more memory is available to the user.
 49

• It is possible to write source program with multiple programs and multiple

languages, because the source programs are first converted to object programs
always, and loader accepts these object modules to convert it to executable form.
3) Absolute Loader: Absolute loader is a kind of loader in which relocated object
files are created, loader accepts these files and places them at specified locations in the
memory. This type of loader is called absolute because no relocation information is
needed; rather it is obtained from the programmer or assembler. The starting address
of every module is known to the programmer, this corresponding starting address is
stored in the object file, then task of loader becomes very simple and that is to simply
place the executable form of the machine instructions at the locations mentioned in the
object file. In this scheme, the programmer orassembler should have knowledge of

memory management. The resolution of external references or linking of different

subroutines are the issues which need to be handled by the programmer. The
programmer should take care of two things: first thing is : specification of starting
address of each module to be used. If some modification is done in some module then
the length of that module may vary. This causes a change in the starting address of

VTUPulse.com
immediate next . modules, its then the programmer's duty to make necessary changes
in the starting addresses of respective modules.
Second thing is ,while branching from one segment to another the absolute starting
address of respective module is to be known by the programmer so that such address
can be specified at respective JMP instruction. For example
Line number
1 MAIN START 1000
..
..
..
15 JMP 5000
16 STORE ;instruction at location 2000
END
1 SUM START 5000
2
20 JMP 2000
21 END
 50

In this example there are two segments, which are interdependent. At line number 1 the
assembler directive START specifies the physical starting address that can be used
during the execution of the first segment MAIN. Then at line number 15 the JMP
instruction is given which specifies the physical starting address that can be used by the
second segment. The assembler creates the object codes for these two segments by
considering the stating addresses of these two segments. During the execution, the first
segment will be loaded at address 1000 and second segment will be loaded at address
5000 as specified by the programmer. Thus the problem of linking is manually solved
by the programmer itself by taking care of the mutually dependant dresses. As you can
notice that the control is correctly transferred to the address 5000 for invoking the other
segment, and after that at line number 20 the JMP instruction transfers the control to
the location 2000, necessarily at location 2000 the instruction STORE of line number
16 is present. Thus resolution of mutual references and linking is done by the
programmer. The task of assembler is to create the object codes

for the above segments and along with the information such as starting address of
the memory where actually the object code can be placed at the time of execution.

VTUPulse.com
The absolute loader accepts these object modules from assembler and by reading the
information about their starting addresses, it will actually place (load) them in the
memory at specified addresses.
The entire process is modeled in the following figure.
Thus the absolute loader is simple to implement in this scheme-
l) Allocation is done by either programmer or assembler 2)Linking
is done by the programmer or assembler 3)Resolution is done by
assembler
4) Simply loading is done by the loader
As the name suggests, no relocation information is needed, if at all it is required then
that task can be done by either a programmer or assembler Advantages:
1. It is simple to implement
2. This scheme allows multiple programs or the source programs written different
languages. If there are multiple programs written in different languages then the
respective language assembler will convert it to the language and a common object
file can be prepared with all the ad resolution.
3. The task of loader becomes simpler as it simply obeys the instruction regarding
 51

where to place the object code in the main memory.

4. The process of execution is efficient

Disadvantages:
1. In this scheme it is the programmer's duty to adjust all the inter segment
addresses and manually do the linking activity. For that, it is necessary for a
programmer to know the memory management.
If at all any modification is done the some segments, the starting addresses of
immediate next segments may get changed, the programmer has to take care of this
issue and he needs to update the corresponding starting addresses on any modification
in the source.
Algorithm for absolute Loader
Input: Object codes and starting address of program segments. Output: An
executable code for corresponding source program. This executable code is to be
placed in the main memory
Method: Begin
For each program segment do Begin

VTUPulse.com
Read the first line from object module to obtain information about memory location.
The starting address say S in corresponding object module is the memory location
where executale code is to be placed.

Hence Memory_location = S
Line counter = 1; as it is first line While (! end of file)
For the curent object code do Begin
1. Read next line
2. Write line into location S
3. S = S + 1
4. Line counter Line counter + 1
Subroutine Linkage: To understand the concept of subroutine linkages, first
consider the following scenario:
"In Program A a call to subroutine B is made. The subroutine B is not written in the
program segment of A, rather B is defined in some another program segment C"
Nothing is wrong in it. But from assembler's point of view while generating the code
for B, as B is not defined in the segment A, the assembler can not find the value of this
 52

symbolic reference and hence it will declare it as an error. To overcome problem, there
should be some mechanism by which the assembler should be explicitly informed that
segment B is really defined in some other segment C. Therefore whenever segment B
is used in segment A and if at all B is defined in C, then B must -be declared as an
external routine in A. To declare such subroutine asexternal, we can use the assembler
directive EXT. Thus the statement such as EXT B should be added at the beginning of
the segment A. This actually helps to inform assembler that B is defined somewhere
else. Similarly, if one subroutine or a variable is defined in the current segment and
can be referred by other segments then those should be declared by using pseudo-ops
INT. Thereby the assembler could inform loader that these are the subroutines or
variables used by other segments. This overall process of establishing the relations
between the subroutines can be conceptually called a_ subroutine linkage.
For example
MAIN START
EXT B
.
.

VTUPulse.com
.
CALL B
.
.
END
B START
 53

RET
END
At the beginning of the MAIN the subroutine B is declared as external. When a call
to subroutine B is made, before making the unconditional jump, the current content
of the program counter should be stored in the system stack maintained internally.
Similarly while returning from the subroutine B (at RET) the pop is performed to
restore the program counter of caller routine with the address of next instruction to
be executed.
Concept of relocations:
Relocation is the process of updating the addresses used in the address sensitive
instructions of a program. It is necessary that such a modification should help to
execute the program from designated area of the memory.
The assembler generates the object code. This object code gets executed after loading
at storage locations. The addresses of such object code will get specified only after
the assembly process is over. Therefore, after loading, Address of object code = Mere
address of object code + relocation constant.
There are two types of addresses being generated: Absolute address and, relative

VTUPulse.com
address. The absolute address can be directly used to map the object code in the main
memory. Whereas the relative address is only after the addition of relocation constant
to the object code address. This kind of adjustment needs to be done in case of relative
address before actual execution of the code. The typical example of relative reference
is : addresses of the symbols defined in the Label field, addresses of the data which is
defined by the assembler directive, literals, redefinable symbols. Similarly, the typical
example of absolute address is the constants which are generated by assembler are
absolute.
The assembler calculates which addresses are absolute and which addresses are
relative during the assembly process. During the assembly process the assembler
calculates the address with the help of simple expressions.
For example
LOADA(X)+5
The expression A(X) means the address of variable X. The meaning of the above
instruction is that loading of the contents of memory location which is 5 more than the
address of variable X. Suppose if the address of X is 50 then by above command we
try to get the memory location 50+5=55. Therefore as the address of variable X is
 54

relative A(X) + 5 is also relative. To calculate the relative addresses the simple
expressions are allowed. It is expected that the expression should possess at the most

VTUPulse.com
 55

addition and multiplication operations. A simple exercise can be carried out to

determine whether the given address is absolute or relative. In the expression if the
address is absolute then put 0 over there and if address is relative then put lover there.
The expression then gets transformed to sum of O's and l's. If the resultant value of the
expression is 0 then expression is absolute. And if the resultant value of the expression
is 1 then the expression is relative. If the resultant is other than 0 or 1then the expression
is illegal. For example:

In the above expression the A, Band C are the variable names. The assembler is to
c0l1sider the relocation attribute and adjust the object code by relocation constant.
Assembler is then responsible to convey the information loading of object code to the
loader. Let us now see how assembler generates code using relocation information.
Direct Linking Loaders
The direct linking loader is the most common type of loader. This type of loader is a
relocatable loader. The loader can not have the direct access to the source code. And
to place the object code in the memory there are two situations: either the address of

VTUPulse.com
the object code could be absolute which then can be directly placed at the specified
location or the address can be relative. If at all the address is relative then it is the
assembler who informs the loader about the relative addresses.
The assembler should give the following information to the loader 1)The
length of the object code segment
2) The list of all the symbols which are not defined 111 the current segment
but can be used in the current segment.
3) The list of all the symbols which are defined in the current segment but can be
referred by the other segments.
The list of symbols which are not defined in the current segment but can be used in
the current segment are stored in a data structure called USE table. The USE table
holds the information such as name of the symbol, address, address relativity.
The list of symbols which are defined in the current segment and can be referred by
the other segments are stored in a data structure called DEFINITION table. The
definition table holds the information such as symbol, address.
Overlay Structures and Dynamic Loading:
Sometimes a program may require more storage space than the available one Execution
 56

of such program can be possible if all the segments are not required simultaneously to
be present in the main memory. In such

VTUPulse.com
 57

situations only those segments are resident in the memory that are actually needed at
the time of execution But the question arises what will happen if the required segment
is not present in the memory? Naturally the execution process will be delayed until the
required segment gets loaded in the memory. The overall effect of this is efficiency of
execution process gets degraded. The efficiency can then be improved by carefully
selecting all the interdependent segments. Of course the assembler can not do this task.
Only the user can specify such dependencies. The inter dependency of thesegments can
be specified by a tree like structure called static overlay structures. The overlay structure
contain multiple root/nodes and edges. Each node represents the segment. The
specification of required amount of memory is also essential in this structure. The two
segments can lie simultaneously in the main memory if they are on the same path. Let
us take an example to understand the concept. Various segments along with their
memory requirements is as shown below.

Automatic Library Search:

Previously, the library routines were available in absolute code but now the library
routines are provided in relocated form that ultimately reduces their size on the disk,

VTUPulse.com
which in turn increases the memory utilization. At execution time certain library
routines may be needed. Keeping track of which library routines are required and how
much storage is required by these routines, if at all is done by an assembler itself then
the activity of automatic library search becomes simpler and effective. The library
routines can also make an external call to other routines. The idea is to make a list of
such calls made by the routines. And if such list is made available to the linker then
linker can efficiently find the set of required routines and can link the references
accordingly.
For an efficient search of library routines it desirable to store all the calling routines
first and then the called routines. This avoids wastage of time due to winding and
rewinding. For efficient automated search of library routines even the dictionary of
such routines can be maintained. A table containing the names of library routines and
the addresses where they are actually located in relocatable form is prepared with the
help of translator and such table is submitted to the linker. Such a table is called
subroutine directory. Even if these routines have made any external calls the -
information about it is also given in subroutine directory. The linker searches the
subroutine directory, finds the address of desired library
 58

routine (the address where the routine is stored in relocated form).Then linker prepares
aload module appending the user program and necessary library routines by doing the
necessary relocation. If the library routine contains the external calls then the linker
searches the subroutine directory finds the address of such external calls, prepares the
load module by resolving the external references. Linkage Editor: The execution of
any program needs four basic functionalities and those are allocation, relocation,
linking and loading. As we have also seen in direct linking loader for execution of any
program each time these four functionalities need to be performed. But performing all
these functionalities each time is time and space consuming task. Moreover if the
program contains many subroutines or functions and the program needs to be executed
repeatedly then this activity becomes annoyingly complex .Each time for execution of
a program, the allocation, relocation linking and -loading needs to be done. Now doing
these activities each time increases the time and space complexity. Actually, there is no
need to redo all these four activities each time. Instead, if the results of some of these
activities are stored in a file then that file can be used by other activities. And
performing allocation, relocation, linking and loading can be avoided each time. The
idea is to separate out these activities in separate groups. Thus dividing the essential

VTUPulse.com
four functions in groups reduces the overall time complexity of loading process. The
program which performs allocation, relocation and linking is called binder. The binder
performs relocation, creates linked executable text and stores this text in a file in some
systematic manner. Such kind of module prepared by the binder execution is called
load module. This load module can then be actually loaded in the main memory by the
loader. This loader is also called as module loader. If the binder can produce the exact
replica of executable code in the load module then the module loader simply loads this
file into the main memory which ultimately reduces the overall time complexity. But
in this process the binder should knew the current positions of the main memory. Even
though the binder knew the main memory locations this is not the only thing which is
sufficient. In multiprogramming environment, the region of main memory available for
loading the program is decided by the host operating system. The binder should also
know which memory area is allocated to the loading program and it should modify the
relocation information accordingly. The binder
 59

which performs the linking function and produces adequate information about
allocation and relocation and writes this information along with the program code in the
file is called linkage editor. The module loader then accepts this rile as input, reads the
information stored in and based on this information about allocation and relocation it
performs the task of loading in the main memory. Even though the program is
repeatedly executed the linking is done only once. Moreover, the flexibility of allocation
and relocation helps efficient utilization of the main memory.

Direct linking: As we have seen in overlay structure certain selective subroutines can
be resident in the memory. That means it is not necessary to resident all the subroutines
in the memory for all the time. Only necessary routines can be present in the main
memory and during execution the required subroutines can be loaded in the memory.
This process of postponing linking and loading of external reference until execution is
called dynamic linking. For example suppose the subroutine main calls A,B,C,D then
it is not desirable to load A,B,C and D along with the main in the memory. Whether A,
B, C or D is called by the main or not will be known only at the time of execution.
Hence keeping these routines already before is really not needed. As the subroutines

VTUPulse.com
get executed when the program runs. Also the linking of all the subroutines has to be
performed. And the code of all the subroutines remains resident in the main memory.
As a result of all this is that memory gets occupied unnecessarily. Typically 'error
routines' are such routines which can be invoked rarely. Then one can postpone the
loading of these routines during the execution. If linking and loading of such rarely
invoked external references could be postponed until the execution time when it was
found to be absolutely necessary, then it increases the efficiency of overhead of the
loader. In dynamic linking, the binder first prepares a load module in which along with
program code the allocation and relocation information is stored. The loader simply
loads the main module in the main memory. If any external ·reference to a subroutine
comes, then the execution is suspended for a while, the loader brings the required
subroutine in the main memory and then the execution process is resumed. Thus
dynamic linking both the loading and linking is done dynamically. Advantages
1. The overhead on the loader is reduced. The required subroutine will be load in the
main memory only at the time of execution.
2. The system can be dynamically reconfigured.
Disadvantages The linking and loading need to be postponed until the execution.
 60

During the execution if at all any subroutine is needed then the

VTUPulse.com
 61

process of execution needs to be suspended until the required subroutine gets loaded
in the main memory

Bootstrap Loader: As we turn on the computer there is nothing meaningful in the main
memory (RAM). A small program is written and stored in the ROM. This program
initially loads the operating system from secondary storage to main memory. The
operating system then takes the overall control. This program which is responsible for
booting up the system is called bootstrap loader. This is the program which must be
executed first when the system is first powered on. If the program starts from the
location x then to execute this program the program counter of this machine should be
loaded with the value x. Thus the task of setting the initial value of the program counter
is to be done by machine hardware. The bootstrap loader is a very small program which
is to be fitted in the ROM. The task of bootstrap loader is to load the necessary portion
of the operating system in the main memory .The initial address at which the bootstrap
loader is to be loaded is generally the lowest (may be at 0th location) or the highest
location. . Concept of Linking: As we have discussed earlier, the execution of program
can be done with the help of following steps

VTUPulse.com
1. Translation of the program(done by assembler or compiler)
2. Linking of the program with all other programs which are needed for execution.
This also involves preparation of a program called load module.
3. Loading of the load module prepared by linker to some specified memory
location.
The output of translator is a program called object module. The linker processes these
object modules binds with necessary library routines and prepares a ready to execute
program. Such a program is called binary program. The "binary program also contains
some necessary information about allocation and relocation. The loader then load s
this program into memory for execution purpose.

Various tasks of linker are -

1. Prepare a single load module and adjust all the addresses and subroutine
references with respect to the offset location.
2. To prepare a load module concatenate all the object modules and adjust all the
operand address references as well as external references to the offset location.
3. At correct locations in the load module, copy the binary machine instructions
and constant data in order to prepare ready to execute module.
 62

The linking process is performed in two passes. Two passes are necessary because the
linker may encounter a forward reference before knowing its address. So it is necessary
to scan all the DEFINITION and USE table at least once. Linker then builds the Global
symbol table with the help of USE and DEFINITION table. In Global symbol table
name of each externally referenced symbol is included along with its address relative
to beginning of the load module. And during pass 2, the addresses of external references
are replaced by obtaining the addresses from global symbol table.

of building and maintaining an RRAG. Second, it restricts each resource request to a

single resource unit of one or more resource classes. Due to these limitations, deadlock
detection cannot be implemented merely as the determination of a graph property. For
a practical implementation, the definition can be interpreted as follows: A set of blocked
processes
D is deadlocked if there does not exist any sequence of resource allocations and
resource releases in the system whereby each process in D can complete. The OS must
determine this fact through exhaustive analysis.

VTUPulse.com
Deadlock analysis is performed by simulating the completion of a running process. In
the simulation it is assumed that a running process completes without making additional
resource requests. On completion, the process releases all resources allocated to it.
These resources are allocated to a blocked process only if the process can enter the
running state. The simulation terminates in one of two situations—either all blocked
processes become running and complete, or some set B of blocked processes cannot be
allocated their requested resources. In the former case no deadlock exists in the system
at the time when deadlock analysis is performed, while in the latter case processes in B
are deadlocked.
Deadlock Resolution
Given a set of deadlocked processes D, deadlock resolution implies breaking the
deadlock to ensure progress for some processes {pi} £ D. This can be achieved by
satisfying the resource request of a process pi in one of two ways:
1. Terminate some processes {pj} e D to free the resources required by
pi. (We call each pj a victim of deadlock resolution.)
2. Add a new unit of the resource requested by pi.
Note that deadlock resolution only ensures some progress for pi. It does not guarantee
 63

that a pi would run to completion. That would depend on the behaviour of processes
after resolution.

VTUPulse.com
 64

(Loaders and Linkers)

Introduction:
In this chapter we will understand the concept of linking and loading. As discussed
earlier the source program is converted to object program by assembler. The loader is
a program which takes this object program, prepares it for execution, and loads this
executable code of the source into memory for execution.
Definition of Loader:

VTUPulse.com
Loader is utility program which takes object code as input prepares it for execution
and loads the executable code into the memory. Thus loader is actually responsible
for initiating the execution process.
Functions of Loader:
The loader is responsible for the activities such as allocation, linking, relocation
and loading
1) It allocates the space for program in the memory, by calculating the size of the
program. This activity is called allocation.
2) It resolves the symbolic references (code/data) between the object modules by
assigning all the user subroutine and library subroutine addresses. This activity
is called linking.
3) There are some address dependent locations in the program, such address
constants must be adjusted according to allocated space, such activity done by
loader is called relocation.
4) Finally it places all the machine instructions and data of corresponding programs
and subroutines into the memory. Thus program now becomes ready for execution,
this activity is called loading.
 65

Loader Schemes:
Based on the various functionalities of loader, there are various types of loaders:
1) “compile and go” loader: in this type of loader, the instruction is read line by line,
its machine code is obtained and it is directly put in the main memory at some known
address. That means the assembler runs in one part of memory and the assembled
machine instructions and data isdirectly put into their assigned memory locations. After
completion of assembly process, assign starting address of the program to the location
counter. The typical example is WATFOR-77, it’s a FORTRAN compiler

VTUPulse.com
 66

which uses such “load and go” scheme. This loading scheme is also called as
“assemble and go”.
Advantages:
• This scheme is simple to implement. Because assembler is placed at one part of the
memory and loader simply loads assembled machine instructions into the memory.
Disadvantages:
• In this scheme some portion of memory is occupied by assembler which is simply a
wastage of memory. As this scheme is combination of assembler and loader activities,
this combination program occupies large block of memory.
• There is no production of .obj file, the source code is directly converted to executable
form. Hence even though there is no modification in the source program it needs to be
assembled and executed each time, which then becomes a time consuming activity.
• It cannot handle multiple source programs or multiple programs written in different
languages. This is because assembler can translate one source language to other target
language.
• For a programmer it is very difficult to make an orderly modulator program and
also it becomes difficult to maintain such program, and the “compile and go” loader

VTUPulse.com
cannot handle such programs.
• The execution time will be more in this scheme as every time program is assembled
and then executed.
2) General Loader Scheme: in this loader scheme, the source program is converted
to object program by some translator (assembler). The loader accepts these object
modules and puts machine instruction and data in an executable form at their assigned
memory. The loader occupies some portion of main memory.
Advantages:
• The program need not be retranslated each time while running it. This is because
initially when source program gets executed an object program gets generated. Of
program is not modified, then loader can make use of this object program to convert it
to executable form.
• There is no wastage of memory, because assembler is not placed in the memory,
instead of it, loader occupies some portion of the memory. And size of loader is
smaller than assembler, so more memory is available to the user.
• It is possible to write source program with multiple programs and multiple
 67

languages, because the source programs are first converted to object programs
always, and loader accepts these object modules to convert it to executable form.
3) Absolute Loader: Absolute loader is a kind of loader in which relocated object
files are created, loader accepts these files and places

VTUPulse.com
 68

them at specified locations in the memory. This type of loader is called absolute
because no relocation information is needed; rather it is obtained from the programmer
or assembler. The starting address of every module is known to the programmer, this
corresponding starting address is stored in the object file, then task of loader becomes
very simple and that is to simply place the executable form of the machine instructions
at the locations mentioned in the object file. In this scheme, the programmer
orassembler should have knowledge of memory management. The resolution of
external references or linking of different subroutines are the issues which need to be
handled by the programmer. The programmer should take care of two things: first thing
is : specification of starting address of each module to be used. If some modification is
done in some module then the length of that module may vary. This causes a change
in the starting address of immediate next . modules, its then the programmer's duty to
make necessary changes in the starting addresses of respective modules.
Second thing is ,while branching from one segment to another the absolute starting
address of respective module is to be known by the programmer so that such address
can be specified at respective JMP instruction. For example
Line number

VTUPulse.com
1 MAIN START 1000
..
..
..
15 JMP 5000
16 STORE ;instruction at location 2000
END
1 SUM START 5000
2
20 JMP 2000
21 END
In this example there are two segments, which are interdependent. At line number 1 the
assembler directive START specifies the physical starting address that can be used
during the execution of the first segment MAIN. Then at line number 15 the JMP
instruction is given which specifies the physical starting address that can be used by the
second segment. The assembler creates the object codes for these two segments by
considering the stating addresses of these two segments. During the execution, the first
 69

segment will be loaded at address 1000 and second segment will be loaded at address
5000 as specified by the programmer. Thus the problem of linking is manually solved
by the programmer itself by taking care of

VTUPulse.com
 110

the mutually dependant dresses. As you can notice that the control is correctly
transferred to the address 5000 for invoking the other segment, and after that at line
number 20 the JMP instruction transfers the control to the location 2000, necessarily
at location 2000 the instruction STORE of line number 16 is present. Thus resolution
of mutual references and linking is done by the programmer. The task of assembler is
to create the object codes
for the above segments and along with the information such as starting address of
the memory where actually the object code can be placed at the time of execution.
The absolute loader accepts these object modules from assembler and by reading the
information about their starting addresses, it will actually place (load) them in the
memory at specified addresses.
The entire process is modeled in the following figure.
Thus the absolute loader is simple to implement in this scheme-
l) Allocation is done by either programmer or assembler 2)Linking
is done by the programmer or assembler 3)Resolution is done by
assembler
4) Simply loading is done by the loader

VTUPulse.com
As the name suggests, no relocation information is needed, if at all it is required then
that task can be done by either a programmer or assembler Advantages:
1. It is simple to implement
2. This scheme allows multiple programs or the source programs written different
languages. If there are multiple programs written in different languages then the
respective language assembler will convert it to the language and a common object
file can be prepared with all the ad resolution.
3. The task of loader becomes simpler as it simply obeys the instruction regarding
where to place the object code in the main memory.
4. The process of execution is efficient

Disadvantages:
1. In this scheme it is the programmer's duty to adjust all the inter segment
addresses and manually do the linking activity. For that, it is necessary for a
programmer to know the memory management.
If at all any modification is done the some segments, the starting addresses of
immediate next segments may get changed, the programmer has to take care of this
 110

issue and he needs to update the corresponding starting addresses on any modification
in the source.
Algorithm for absolute Loader
Input: Object codes and starting address of program segments.

VTUPulse.com
 111

Output: An executable code for corresponding source program. This executable

code is to be placed in the main memory
Method: Begin
For each program segment do Begin
Read the first line from object module to obtain information about memory location.
The starting address say S in corresponding object module is the memory location
where executale code is to be placed.
Hence Memory_location = S
Line counter = 1; as it is first line While (! end of file)
For the curent object code do Begin
1. Read next line
2. Write line into location S
3. S = S + 1
4. Line counter Line counter + 1
Subroutine Linkage: To understand the concept of subroutine linkages, first
consider the following scenario:
"In Program A a call to subroutine B is made. The subroutine B is not written in the

VTUPulse.com
program segment of A, rather B is defined in some another program segment C"
Nothing is wrong in it. But from assembler's point of view while generating the code
for B, as B is not defined in the segment A, the assembler can not find the value of this
symbolic reference and hence it will declare it as an error. To overcome problem, there
should be some mechanism by which the assembler should be explicitly informed that
segment B is really defined in some other segment C. Therefore whenever segment B
is used in segment A and if at all B is defined in C, then B must -be declared as an
external routine in A. To declare such subroutine asexternal, we can use the assembler
directive EXT. Thus the statement such as EXT B should be added at the beginning of
the segment A. This actually helps to inform assembler that B is defined somewhere
else. Similarly, if one subroutine or a variable is defined in the current segment and
can be referred by other segments then those should be declared by using pseudo-ops
INT. Thereby the assembler could inform loader that these are the subroutines or
variables used by other segments. This overall process of establishing the relations
between the subroutines can be conceptually called a_ subroutine linkage.
For example
MAIN START
 112

EXT B
.
.

VTUPulse.com
 113

.
CALL B
.
.
END
B START
.
.
RET
END
At the beginning of the MAIN the subroutine B is declared as external. When a call
to subroutine B is made, before making the unconditional jump, the current content
of the program counter should be stored in the system stack maintained internally.
Similarly while returning from the subroutine B (at RET) the pop is performed to
restore the program counter of caller routine with the address of next instruction to
be executed.
Concept of relocations:

VTUPulse.com
Relocation is the process of updating the addresses used in the address sensitive
instructions of a program. It is necessary that such a modification should help to
execute the program from designated area of the memory.
The assembler generates the object code. This object code gets executed after loading
at storage locations. The addresses of such object code will get specified only after
the assembly process is over. Therefore, after loading, Address of object code = Mere
address of object code + relocation constant.
There are two types of addresses being generated: Absolute address and, relative
address. The absolute address can be directly used to map the object code in the main
memory. Whereas the relative address is only after the addition of relocation constant
to the object code address. This kind of adjustment needs to be done in case of relative
address before actual execution of the code. The typical example of relative reference
is : addresses of the symbols defined in the Label field, addresses of the data which is
defined by the assembler directive, literals, redefinable symbols. Similarly, the typical
example of absolute address is the constants which are generated by assembler are
absolute.
The assembler calculates which addresses are absolute and which addresses are
 114

relative during the assembly process. During the assembly process the assembler
calculates the address with the help of simple expressions.
For example
LOADA(X)+5

VTUPulse.com
 115

The expression A(X) means the address of variable X. The meaning of the above
instruction is that loading of the contents of memory location which is 5 more than the
address of variable X. Suppose if the address of X is 50 then by above command we
try to get the memory location 50+5=55. Therefore as the address of variable X is
relative A(X) + 5 is also relative. To calculate the relative addresses the simple
expressions are allowed. It is expected that the expression should possess at the most
addition and multiplication operations. A simple exercise can be carried
out to determine whether the given address is absolute or relative. In the expression if
the address is absolute then put 0 over there and if address is relative then put lover
there. The expression then gets transformed to sum of O's and l's. If the resultant value
of the expression is 0 then expression is absolute. And if the resultant value of the
expression is 1 then the expression is relative. If the resultant is other than 0 or 1then
the expression is illegal. For example:

In the above expression the A, Band C are the variable names. The assembler is to
c0l1sider the relocation attribute and adjust the object code by relocation constant.

VTUPulse.com
Assembler is then responsible to convey the information loading of object code to the
loader. Let us now see how assembler generates code using relocation information.
Direct Linking Loaders
The direct linking loader is the most common type of loader. This type of loader is a
relocatable loader. The loader can not have the direct access to the source code. And
to place the object code in the memory there are two situations: either the address of
the object code could be absolute which then can be directly placed at the specified
location or the address can be relative. If at all the address is relative then it is the
assembler who informs the loader about the relative addresses.
The assembler should give the following information to the loader 1)The
length of the object code segment
2) The list of all the symbols which are not defined 111 the current segment
but can be used in the current segment.
3) The list of all the symbols which are defined in the current segment but can be
referred by the other segments.
The list of symbols which are not defined in the current segment but can be used in
the current segment are stored in a data structure called USE table. The USE table
 116

holds the information such as name of the symbol, address, address relativity.

VTUPulse.com
 117

The list of symbols which are defined in the current segment and can be referred by
the other segments are stored in a data structure called DEFINITION table. The
definition table holds the information such as symbol, address.
Overlay Structures and Dynamic Loading:
Sometimes a program may require more storage space than the available one Execution
of such program can be possible if all the segments are not required simultaneously to
be present in the main memory. In such situations only those segments are resident in
the memory that are actually needed at the time of execution But the question arises
what will happen if the required segment is not present in the memory? Naturally the
execution process will be delayed until the required segment gets loaded in the memory.
The overall effect of this is efficiency of execution process gets degraded. The
efficiency can then be improved by carefully selecting all the interdependent segments.
Of course the assembler can not do this task. Only the user can specify such
dependencies. The inter dependency of thesegments can be specified by a tree like
structure called static overlay structures. The overlay structure contain multiple
root/nodes and edges. Each node represents the segment. The specification of required
amount of memory is also essential in this structure. The two segments can lie

VTUPulse.com
simultaneously in the main memory if they are on the same path. Let us take an example
to understand the concept. Various segments along with their memory requirements is
as shown below.

Automatic Library Search:

Previously, the library routines were available in absolute code but now the library
routines are provided in relocated form that ultimately reduces their size on the disk,
which in turn increases the memory utilization. At execution time certain library
routines may be needed. Keeping track of which library routines are required and how
much storage is required by these routines, if at all is done by an assembler itself then
the activity of automatic library search becomes simpler and effective. The library
routines can also make an external call to other routines. The idea is to make a list of
such calls made by the routines. And if such list is made available to the linker then
linker can efficiently find the set of required routines and can link the references
accordingly.
For an efficient search of library routines it desirable to store all the calling routines
first and then the called routines. This avoids wastage of time due to winding and
rewinding. For efficient automated search of
 118

library routines even the dictionary of such routines can be maintained. A table
containing the names of library routines and the addresses where they are actually
located in relocatable form is prepared with the help of translator and such table is
submitted to the linker. Such a table is called subroutine directory. Even if these
routines have made any external calls the -information about it is also given in
subroutine directory. The linker searches the subroutine directory, finds the address of
desired library routine (the address where the routine is stored in relocated form).Then
linker prepares aload module appending the user program and necessary library
routines by doing the necessary relocation. If the library routine contains the external
calls then the linker searches the subroutine directory finds the address of such external
calls, prepares the load module by resolving the external references. Linkage Editor:
The execution of any program needs four basic functionalities and those are allocation,
relocation, linking and loading. As we have also seen in direct linking loader for
execution of any program each time these four functionalities need to be performed.
But performing all these functionalities each time is time and space consuming task.
Moreover if the program contains many subroutines or functions and the program needs
to be executed repeatedly then this activity becomes annoyingly complex .Each time

VTUPulse.com
for execution of a program, the allocation, relocation linking and -loading needs to be
done. Now doing these activities each time increases the time and space complexity.
Actually, there is no need to redo all these four activities each time. Instead, if the
results of some of these activities are stored in a file then that file can be used by other
activities. And performing allocation, relocation, linking and loading can be avoided
each time. The idea is to separate out these activities in separate groups. Thus dividing
the essential four functions in groups reduces the overall time complexity of loading
process. The program which performs allocation, relocation and linking is called
binder. The binder performs relocation, creates linked executable text and stores this
text in a file in some systematic manner. Such kind of module prepared by the binder
execution is called load module. This load module can then be actually loaded in the
main memory by the loader. This loader is also called as module loader. If the binder
can produce the exact replica of executable code in the load module then the module
loader simply loads this file into the main memory which ultimately reduces the overall
time
 119

complexity. But in this process the binder should knew the current positions of the main
memory. Even though the binder knew the main memory locations this is not the only
thing which is sufficient. In multiprogramming environment, the region of main
memory available for loading the program is decided by the host operating system. The
binder should also know which memory area is allocated to the loading program and it
should modify the relocation information accordingly. The binder which performs the
linking function and produces adequate information about allocation and relocation and
writes this information along with the program code in the file is called linkage editor.
The module loader then accepts this rile as input, reads the information stored in and
based on this information about allocation and relocation it performs the task of loading
in the main memory. Even though the program is repeatedly executed the linking is
done only once. Moreover, the flexibility of allocation and relocation helps efficient
utilization of the main memory.

Direct linking: As we have seen in overlay structure certain selective subroutines can
be resident in the memory. That means it is not necessary to resident all the subroutines
in the memory for all the time. Only necessary routines can be present in the main

VTUPulse.com
memory and during execution the required subroutines can be loaded in the memory.
This process of postponing linking and loading of external reference until execution is
called dynamic linking. For example suppose the subroutine main calls A,B,C,D then
it is not desirable to load A,B,C and D along with the main in the memory. Whether A,
B, C or D is called by the main or not will be known only at the time of execution.
Hence keeping these routines already before is really not needed. As the subroutines
get executed when the program runs. Also the linking of all the subroutines has to be
performed. And the code of all the subroutines remains resident in the main memory.
As a result of all this is that memory gets occupied unnecessarily. Typically 'error
routines' are such routines which can be invoked rarely. Then one can postpone the
loading of these routines during the execution. If linking and loading of such rarely
invoked external references could be postponed until the execution time when it was
found to be absolutely necessary, then it increases the efficiency of overhead of the
loader. In dynamic linking, the binder first prepares a load module in which along with
program code the allocation and relocation information is stored. The loader simply
loads the main module in the main memory. If any external ·reference to a subroutine
comes, then the execution is suspended for a while, the loader brings the required
subroutine in the main memory and then the execution process is
 120

resumed. Thus dynamic linking both the loading and linking is done
dynamically. Advantages
1. The overhead on the loader is reduced. The required subroutine will be load in the
main memory only at the time of execution.
2. The system can be dynamically reconfigured.
Disadvantages The linking and loading need to be postponed until the execution.
During the execution if at all any subroutine is needed then the process of execution
needs to be suspended until the required subroutine gets loaded in the main memory

Bootstrap Loader: As we turn on the computer there is nothing meaningful in the main
memory (RAM). A small program is written and stored in the ROM. This program
initially loads the operating system from secondary storage to main memory. The
operating system then takes the overall control. This program which is responsible for
booting up the system is called bootstrap loader. This is the program which must be
executed first when the system is first powered on. If the program starts from the
location x then to execute this program the program counter of this machine should be
loaded with the value x. Thus the task of setting the initial value of the program counter

VTUPulse.com
is to be done by machine hardware. The bootstrap loader is a very small program which
is to be fitted in the ROM. The task of bootstrap loader is to load the necessary portion
of the operating system in the main memory .The initial address at which the bootstrap
loader is to be loaded is generally the lowest (may be at 0th location) or the highest
location. . Concept of Linking: As we have discussed earlier, the execution of program
can be done with the help of following steps
1. Translation of the program(done by assembler or compiler)
2. Linking of the program with all other programs which are needed for execution.
This also involves preparation of a program called load module.
3. Loading of the load module prepared by linker to some specified memory
location.
The output of translator is a program called object module. The linker processes these
object modules binds with necessary library routines and prepares a ready to execute
program. Such a program is called binary program. The "binary program also contains
some necessary information about allocation and relocation. The loader then load s
this program into memory for execution purpose.

Various tasks of linker are -

 121

1. Prepare a single load module and adjust all the addresses and subroutine
references with respect to the offset location.
2. To prepare a load module concatenate all the object modules and adjust all the
operand address references as well as external references to the offset location.
3. At correct locations in the load module, copy the binary machine instructions
and constant data in order to prepare ready to execute module.
The linking process is performed in two passes. Two passes are necessary because the
linker may encounter a forward reference before knowing its address. So it is necessary
to scan all the DEFINITION and USE table at least once. Linker then builds the Global
symbol table with the help of USE and DEFINITION table. In Global symbol table
name of each externally referenced symbol is included along with its address relative
to beginning of the load module. And during pass 2, the addresses of external references
are replaced by obtaining the addresses from global symbol table.

VTUPulse.com
 1

FUNDAMENTALS OF LANGUAGE PROCESSING

Definition
Language Processing = Analysis of SP + Synthesis of TP.
Definition motivates a generic model of language processing
activities.
We refer to the collection of language processor components engaged in analyzing a
source program as the analysis phase of the language processor. Components engaged
in synthesizing a target program constitute the synthesis phase.
A specification of the source language forms the basis of source program analysis. The
specification consists of three components:
1. Lexical rules, which govern the formation of valid lexical units in the source
language.
2. Syntax rules which govern the formation of valid statements in the source language.
3. Semantic rules which associate meaning with valid statements of the language.
The analysis phase uses each component of the source language specification to
determine relevant information concerning a statement in the source program. Thus,
analysis of a source statement consists of lexical, syntax and semantic analysis.

VTUPulse.com
The synthesis phase is concerned with the construction of target language statement(s)
which have the same meaning as a source statement. Typically, this consist of two main
activities:
• Creation of data structures in the target program
• Generation of target code.
We refer to these activities as memory allocation and code generation, respectively

Lexical Analysis (Scanning)

Lexical analysis identifies the lexical units in a source statement. It then classifies the
units into different lexical classes e.g. id’s, constants etc. and enters them into different
tables. This classification may be based on the nature of string or on the specification
of the source language. (For example, while an integer constant is a string of digits with
an optional sign, a reserved id is an id whose name matches one of the reserved names
mentioned in the language specification.) Lexical analysis builds a descriptor, called a
token, for each lexical unit. A token contain two fields— class code, and number in
class, class code identifies the class to which a lexical unit belongs, number in class is
the entry number of the lexical unit in the relevant table.
 2

Syntax Analysis (Parsing)

Syntax analysis processes the string of tokens built by lexical analysis to determine the
statement class, e.g. assignment statement, if statement, etc. It then builds an IC which
represents

VTUPulse.com
 3

the structure of the statement. The IC is passed to semantic analysis to determine the
meaning of the statement.
Semantic analysis
Semantic analysis of declaration statements differs from the semantic analysis of
imperative statements. The former results in addition of information to the symbol table,
e.g. type, length and dimensionality of variables. The latter identifies the sequence of
actions necessary to implement the meaning of a source statement. In both cases the
structure of a source statement guides the application of the semantic rules. When
semantic analysis determines the meaning of a sub tree in the IC. It adds information a
table or adds an action to the sequence. It then modifies the IC to enable further semantic
analysis. The analysis ends when the tree has been completely processed.

“FUNDAMENTALS OF LANGUAGE SPECIFICATION

A specification of the source language forms the basis of source program analysis. In
this section, we shall discuss important lexical, syntactic and semantic features of a

VTUPulse.com
programming language.
Programming Language Grammars
The lexical and syntactic features of a programming language are specified by its
grammar. This section discusses key concepts and notions from formal language
grammars. A language L can be considered to be a collection of valid sentences.
Each sentence can be looked upon as a sequence of words, and each word as a sequence
of letters or graphic symbols acceptable in
L. A language specified in this manner is known as a. formal language. A formal
language grammar is a set of rules which precisely specify the sentences of L. It is clear
that natural languages are not formal languages due to their rich vocabulary. However,
PLs are formal languages.
Terminal symbols, alphabet and strings
The alphabet of L, denoted by the Greek symbol Z, is the collection of symbols in its
character set. We will use lower case letters a, b, c, etc. to denote symbols in Z.
A symbol in the alphabet is known as a terminal symbol (T) of L. The alphabet can be
represented using the mathematical notation of a set, e.g. Σ ≅ {a, b, ….z, 0,1 9}
Here the symbols {, ',' and} are part of the notation. We call them met symbols to
differentiate them from terminal symbols. Throughout this discussion we assume that
 4

met symbols are distinct from the terminal symbols. If this is not the case, i.e. if a
terminal symbol and a met symbol are identical, we enclose the terminal symbol in
quotes to differentiate it from the metasymbol. For example, the set of punctuation
symbols of English can be defined as {:,;’,’-,...} Where ',' denotes the terminal symbol
'comma'.

VTUPulse.com
 5

A string is a finite sequence of symbols. We will represent strings by Greek symbols-α

β γ, etc. Thus α = axy is a string over Σ . The length of a string is the Number of symbols
in it. Note that the absence of any symbol is also a string, the null string . The
concatenation operation combines two strings into a single string.
To evaluate an HLL program it should be converted into the Machine language. A
compiler performs another very important function. This is in terms of the diagnostics.

I.e. error – detection capability.

The important tasks of a compiler are:
Translating the HLL program input to it.
Providing diagnostic messages whenever specifications of the HLL

Compilers

VTUPulse.com
 6

• A compiler is a program that translates a sentence

a. from a source language (e.g. Java, Scheme, LATEX)

b. into a target language (e.g. JVM, Intel x86, PDF)
c. while preserving its meaning in the process
• Compiler design has a long history (FORTRAN 1958)

VTUPulse.com
 7

a. lots of experience on how to structure compilers

b. lots of existing designs to study (many freely available)

VTUPulse.com
 8

VTUPulse.com
 9

VTUPulse.com
 10

VTUPulse.com
 11

VTUPulse.com
 12

VTUPulse.com
 13

VTUPulse.com
 14

VTUPulse.com
 15

VTUPulse.com
 16

VTUPulse.com
 17

VTUPulse.com
 18

VTUPulse.com
VTUPulse.com