Page 1 of 6
Unit-3 Editors, Linkers and Loaders
Editors
• An Editor is a software tool which is mainly used for program entry and editing.
• Followings are different types of editors:
• Line editors
• Stream editors
• Screen editors
• Word processors
• Structure editors
• These editors differ in the scope of edit operations, support for WYSIWYG, sophisticated formatting and awareness of the structure of a document.
Line Editors
• The scope of an edit operation is limited to a line of text.
• The line is assigned a serial number or some context for unique identification.
• The primary advantage is: simplicity.
• The disadvantage is: Requires more efforts to process the entire text because the same edit operation must be repeated for each line.
Stream Editors
• Views the entire text as a stream of characters (i.e. a single string).
• Thus, the scope of the edit operation is not limited to just a line.
• The text pointer is used to indicate a context in the text.
• Line and stream editors maintain multiple representations of text.
• One representation (the display form) shows the text as a sequence of lines.
• The other representation is used to perform the edit operations behind the scenes. This form contains explicit newline and other edit characters like tabs.
Screen Editors
• A line or stream editor does not support WYSIWYG.
• A screen editor uses displays the text in the manner it would appear if printed.
• The editor displays a screenful of text at a time.
• The user can move the cursor over the screen, position it directly at the point of editing & proceed with editing.
• Thus, the effect of editing can be seen on the screen immediately.
• Example s: Notepad and any other simple text editor.
Word Processors
• They are document editors with additional features for producing well-formatted hard copy.
• Exclusive features include support for moving a word/line/paragraph from one place to another, merging of text and searching & replacement of words. (Notepad vs. Word…)
• Many word processors also support spell-check.
• Most popular among authors, office personnel and computer professionals. MS Word, Pagemaker are examples of word processors.
Structure Editors
• A structure editor has awareness of the structure of a document.
• This awareness is helpful in browsing through a document.
• E.g. if a programmer changes name of a function in a program file, all function calls will also be updated accordingly.
• A special class of structure editors, called syntax directed editors are used in programming environment.
• Examples are editors available in MS Visual Studio and NetBeans IDE.
Design of an editor
• The editor works in two modes: Data and Command.
• There are four main functions in editing:
• Travelling, Editing, Viewing and Display
• Travelling means movement of editing context to a new position within the text.
• Viewing means formatting the text in the way the user wants.
• Display maps the text under view into the physical characteristics of the display device being used. (It manages display of text on the output device.)
• Consider the structure of an editor in next slide:
• As shown here, the command processor causes the Editing manager, the Travelling Manager and the Viewing manager.
• The Editing buffer temporarily stores recently edited text and the Viewing buffer stores recently shown views of the text.
• The Editing filter and the Viewing filter operate on a new portion of the test to update the contents of the buffers.
• Most editors also support an undo function to cancel one or more of previous edit operations.
Translated, linked and load time addresses
• Origin of the program is the memory address of the first word of the target program.
• The origin should be either specified or it would have to be assumed.
• This origin may be changed before the program reaches execution. The origin assigned by Translator (assumed by default or allocated as per user’s START or ORIGIN statement) is called the translated origin of a program.
• The translator uses the value of translated origin to allocate memory for the symbols (i.e. variables) declared in a program.
• This results into assignment of a translation time address tsymb to each symbol ‘symb’ in the program.
• The execution start address or simply the start address of a program is the address of the instruction from which its execution must begin (may be specified with END directive).
• The start address specified by the translator is the translated start address of the program.
• The linker or loader may change the origin of a program for one of two reasons:
• More than one object modules have the same translated origin.
• An Os may require that a program should execute from a specific area of the memory.
• The change in the origin of a program leads to changes in its execution start address and in the addresses assigned to the symbols defined in it.
Program Relocation
• Let AA be the set of absolute addresses of instructions/data used in the instructions of a program P.
• AA would be a nonempty set if the program P expects some of its instructions and data to occupy memory words with specific addresses.
• Such a program is called an address sensitive program. It contains one or more of the following:
1. An address sensitive instruction : An instruction that uses an address ai included in set AA.
2. An address constant : A data word that contains an address ai included in set AA.
• Program relocation is the action of modifying the addresses used in the address sensitive instructions of a program such that the program can execute correctly from the designated (i.e. newly assigned) area of memory.
• If linked origin = translated origin, relocation is not required.
• If linked origin ≠ translated origin, relocation must be performed by the linker.
• If load origin ≠ linked origin, relocation must be performed by the loader.
Performing relocation
• Let the translated and linked origins of program P be To and Lo respectively.
• Consider a symbol (i.e. a variable or a constant) v in P. Let v’s translation time address be tv and linked address be tb.
• The relocation factor of P is defined as follows:
relocation_factor = Lo - To ….(1)
Note that relocation_factor can be +ve, -ve or zero.
• Consider a statement which use v as an operand. The translator puts the address tv in the instruction generated for this statement. Now,
tv = To + dv ...(2)
where dv is the offset of v in P.
• After program P has been relocated to the linked origin i.e. Lo , we have
Lv = Lo + dv
Substituting Lo = relocation_factor + To from (1) in above equation, we have
Lv = relocation_factor + To + dv
Substituting To + dv = tv from (2) in above equation, we get
Lv = relocation_factor + tv …(3)
• Let IP be the set of instructions in program P that require relocation. As per (3), relocation of P can be performed by computing the relocation factor for P and adding it to the translation time address(es) used in every instruction included in IP.
Linking
• Consider an application program AP consisting of a set of program units SP = {Pi }
• A program unit Pi interacts with another program unit Pj by using addresses of Pj ‘s instructions and data in its own instructions.
• For such interactions to work correctly, Pj and Pi must contain public definitions and external references.
• Public definition: a symbol pub_symb defines in a program unit which may be referenced (i.e. used) in other program units.
• External reference: a reference to (or a use of) a symbol ext_symb which is not defined in the given program.
EXTRN and ENTRY statements
• The ENTRY statement lists the public definitions of a program unit.
• The EXTRN statement lists the symbols which are used in the given program unit but not defined within the same program unit.
• Linking is the process of binding an external reference to the correct link-time address.
• Consider an assembly program given in the next slide. The ENTRY statement indicates that TOTAL has a public definition. The EXTRN statement indicates that MAX and ALPHA are external references.
• The assembler does not know the address of an external symbol. Hence it puts zeros in the address fields of the instructions which refer MAX and ALPHA.
• If the EXTRN statement did not exist, the assembler would have given errors for MAX and ALPHA.
Binary Program
A binary program is a machine language program comprising a set of program units SP such that for every Pi in SP
1. Pi has been relocated to the memory area whose staring address matches its linked origin and
2. Each external reference in Pi has been resolved.
Loading
• Loading is the process of putting the program in the main memory for execution.
• Loader is the software which performs this task.
• There are two types of loaders:
1. Absolute Loader (No relocation)
2. Relocating Loader (Performs relocation)
Absolute Loaders
• An absolute loader loads a binary program in memory for execution.
• The binary program is stored in a file. Such a program contains:
– A header record
– A sequence of binary image records.
• The absolute loader notes the load origin and the length of the program mentioned in the header record.
• It then enters a loop that reads a binary image record and moves the code contained in it to the memory area starting on the address mentioned in the binary image record.
• At the end it transfers control to the execution start address of the program.
• Use of absolute loaders is limited to loading of programs that either have load origin=linked origin or are self-relocating.
• Many of the components of an OS have this property, so the OS uses an absolute loader to load these components as and when needed. Mostly used by OS.
Bootstrap loader
The OS system has to be loaded in memory when a computer’s power is switched on. It involves loading of several programs in memory. Because the computer’s memory does not contain any program or data at the time of start up- the task of loading the OS is performed by a special-purpose loader called the bootstrap loader.
Relocating Loaders
• A relocating loader loads a binary program in memory, relocates it and passes control to it for execution.
• The binary program is stored in a file. Such a program contains:
– A header record
– A sequence of binary image records.
– A relocating table ( containing linked addresses of address sensitive instructions in the program)
• The header record and the binary image records differ from those used for absolute loaders in that they contain linked addresses rather than load time addresses.
• The relocating loader is invoked with the name of the file that contains the program and the address of the memory area where that program is to be loaded. i.e. its load origin.
• The relocating loader performs relocation by computing the relocation factor. It then computes the load address of an instruction that requires relocation, and relocates it by the relocation factor to the operand address used in it.
Program Execution
Execution of a program written in a programming language is achieved in the following four steps:
1. Translation: A program is translated into a target program.
2. Linking: The code of a target program is combined with codes of those programs and library functions that the target programs calls.
3. Relocation: A program may have been coded or translate with the idea of executing it in a specific area of memory. However, the OS may have used that memory area for another purpose. So it may allocate a different memory area for the program’s execution.
Relocation is the action of changing the memory addresses used in the code so that it can execute correctly in the allocated memory area.
4. Loading: The program is loaded in a specific memory area for execution.
The following diagram shows program execution.
Data flow Control flow
• The translator generates a program called the object module for the program.
• The linker performs linking and relocation to produce a ready-to-execute program called a binary program.
• The loader loads a binary program in memory for execution.
• The object module(s) and binary programs can be stored in files so that they can be used repeatedly.