Page 1 :
INTRODUCTION, Operating System, Operating system (OS) is the lifeline of computer. You connect all the basic devices like CPU, monitor, keyboard and mouse; plug in the power supply and switch it on thinking you have everything in place. But the computer will not start or come to life unless it has an operating system installed in it because OS −, Keeps all hardware parts in a state of readiness to follow user instructions, Co-ordinates between different devices, Schedules multiple tasks as per priority, Allocates resource to each task, Enables computer to access network, Enables users to access and use application software, Besides initial booting, these are some of the functions of an operating system −, Managing computer resources like hardware, software, shared resources, etc., Allocating resources, Prevent error during software use, Control improper use of computer, One of the earliest operating systems was MS-DOS, developed by Microsoft for IBM PC. It was a Command Line Interface (CLI) OS that revolutionized the PC market. DOS was difficult to use because of its interface. The users needed to remember instructions to do their tasks. To make computers more accessible and user-friendly, Microsoft developed Graphical User Interface (GUI) based OS called Windows, which transformed the way people used computers., Assembler, Assembler is a system software that converts assembly level programs to machine level code., These are the advantages provided by assembly level programming −, Increases efficiency of the programmer as remembering mnemonics is easier, Productivity increases as number of errors decreases and hence debugging time, Programmer has access to hardware resources and hence has flexibility in writing programs customized to the specific computer, Interpreter, The major advantage of assembly level language was its ability to optimize memory usage and hardware utilization. However, with technological advancements computers had more memory and better hardware components. So ease of writing programs became more important than optimizing memory and other hardware resources., In addition, a need was felt to take programming out of a handful of trained scientists and computer programmers, so that computers could be used in more areas. This led to development of high level languages that were easy to understand due to resemblance of commands to English language., The system software used to translate high level language source code into machine level language object code line by line is called an interpreter. An interpreter takes each line of code and converts it into machine code and stores it into the object file., The advantage of using an interpreter is that they are very easy to write and they do not require a large memory space. However, there is a major disadvantage in using interpreters, i.e., interpreted programs take a long time in executing. To overcome this disadvantage, especially for large programs, compilers were developed., Compiler, System software that store the complete program, scan it, translate the complete program into object code and then creates an executable code is called a compiler. On the face of it compilers compare unfavorably with interpreters because they −, are more complex than interpreters, need more memory space, take more time in compiling source code, However, compiled programs execute very fast on computers. The following image shows the step-by-step process of how a source code is transformed into an executable code −, These are the steps in compiling source code into executable code −, Pre-processing − In this stage pre-processor instructions, typically used by languages like C and C++ are interpreted, i.e. converted to assembly level language., Lexical analysis − Here all instructions are converted to lexical units like constants, variables, arithmetic symbols, etc., Parsing − Here all instructions are checked to see if they conform to grammar rules of the language. If there are errors, compiler will ask you to fix them before you can proceed., Compiling − At this stage the source code is converted into object code., Linking − If there are any links to external files or libraries, addresses of their executable will be added to the program. Also, if the code needs to be rearranged for actual execution, they will be rearranged. The final output is the executable code that is ready to be executed., System Software & Machine Architecture, 1.0 Introduction, The subject introduces the design and implementation of system software. Software is set of instructions or programs written to carry out certain task on digital computers. It is classified into system software and application software. System software consists of a variety of programs that support the operation of a computer. Application software focuses on an application or problem to be solved. System software consists of a variety of programs that support the operation of a computer. Examples for system software are Operating system, compiler, assembler, macro processor, loader or linker, debugger, text editor, database management systems (some of them) and, software engineering tools. These software’s make it possible for the user to focus on an application or other problem to be solved, without needing to know the details of how the machine works internally., 1.1 System Software and Machine Architecture One characteristic in which most system software differs from application software is machine dependency. System software – support operation and use of computer. Application software - solution to a problem. Assembler translates mnemonic instructions into machine code. The instruction formats, addressing modes etc., are of direct concern in assembler design. Similarly, Compilers must generate machine language code, taking into account such hardware characteristics as the number and type of registers and the machine instructions available. Operating systems are directly concerned with the management of nearly all of the resources of a computing system., There are aspects of system software that do not directly depend upon the type of computing system, general design and logic of an assembler, general design and logic of a compiler and, code optimization techniques, which are independent of target machines. Likewise, the process of linking together independently assembled subprograms does not usually depend on the computer being used., 1.2 The Simplified Instructional Computer (SIC) Simplified Instructional Computer (SIC) is a hypothetical computer that includes the hardware features most often found on real machines. There are two versions of SIC, they are, standard model (SIC), and, extension version (SIC/XE) (extra equipment or extra expensive)., 1.2.1 SIC Machine Architecture, We discuss here the SIC machine architecture with respect to its Memory and Registers, Data Formats, Instruction Formats, Addressing Modes, Instruction Set, Input and Output, Memory, There are 215 bytes in the computer memory, that is 32,768 bytes , It uses Little Endian format to store the numbers, 3 consecutive bytes form a word , each location in memory contains 8-bit bytes., Registers, There are five registers, each 24 bits in length. Their mnemonic, number and use are given in the following table., Mnemonic Number Use, A 0 Accumulator; used for arithmetic operations, X 1 Index register; used for addressing, L 2 Linkage register; JSUB, PC 8 Program counter, SW 9 Status word, including CC, Data Formats, Integers are stored as 24-bit binary numbers , 2’s complement representation is used for negative values, characters are stored using their 8-bit ASCII codes, No floating- point hardware on the standard version of SIC., Instruction Formats, Opcode(8) x Address (15), All machine instructions on the standard version of SIC have the 24-bit format as shown above, Addressing Modes, Mode Indication Target address calculation, Direct x = 0 TA = address, Indexed x = 1 TA = address + (x), There are two addressing modes available, which are as shown in the above table. Parentheses are used to indicate the contents of a register or a memory location., Instruction Set, SIC provides,, load and store instructions (LDA, LDX, STA, STX, etc.)., Integer arithmetic operations: (ADD, SUB, MUL, DIV, etc.). All arithmetic operations involve register A and a word in memory, with the result being left in the register. Two instructions are provided for subroutine linkage., Comparing: COMP compares the value in register A with a word in memory, this instruction sets a condition code CC to indicate the result., conditional jump instructions: (JLT, JEQ, JGT), these instructions test the setting of CC and jump accordingly., Subroutine :JSUB jumps to the subroutine placing the return address in register L, RSUB returns by jumping to the address contained in register L., Input and Output, Input and Output are performed by transferring 1 byte at a time to or from the rightmost 8 bits of register A (accumulator)., The Test Device (TD) instruction tests whether the addressed device is ready to send or receive a byte of data., Read Data (RD), Write Data (WD) are used for reading or writing the data., Data movement and Storage Definition, LDA, STA, LDL, STL, LDX, STX ( A- Accumulator, L – Linkage Register, X – Index Register), all uses 3-byte word. LDCH, STCH associated with characters uses 1-byte. There are no memory-memory move instructions., Storage definitions, word - one-word constant, resw - one-word variable, byte - one-byte constant, resb - one-byte variable, The IBM System/360 (S/360), It is a mainframe computer system family announced by IBM on April 7, 1964. It was the first family of computers designed to cover the complete range of applications, from small to large, both commercial and scientific. The goal when creating the IBM 360 was to create a “family concept”, where for the first time a single ISA could be used with older and newer machines in the same family., The IBM 360 was historically important due to, 1. forward and backward compatibility (family concept and extensive instruction set), 2. clear separation between architecture and implementation, 3. integration of scientific and business efficiency, 4. extensive use of microprogramming, The IBM 360 family of computers created the concept of the ISA , where every machine had the same set of instructions, number of user registers, and behavior, and thus were binary compatible, The IBM 360 family of machines could run the same programs that were on separate computers earlier, but at different speeds.. System/360 was designed to be able to handle both decimal and binary formatted information, with both variable-fixed length and floatingpoint arithmetic capabilities., Extensive Use of Microprogramming, The architecture of the IBM 360 is built around microprogramming, or small programs of microinstructions. By using microprogramming, smaller and larger computers could accomplish goals of small micro programs with their own implementations and use whichever microinstructions best suited them (most efficiently, that is).. Thus, the concept of a CISC (Complex Instruction Set Computing) architecture was created., The 360/370 Instruction Set Architecture, The IBM System/360 is a 32 -bit machine with byte addressability and support for a variety of data types: byte, half word (16 bits), word (32 bits), double word (double precision real), packed decimal, and unpacked character strings. The internal state of the 360 has the following components:, 1. Sixteen 32 -bit, general-purpose registers: register 0 is special when used in an addressing mode, where a zero is always substituted., 2. Four double-precision (64 -bit) floating-point registers., 3. Program status word (PSW) holds the PC, some control flags, and the condition codes., 4. Later versions of the architecture extended this state with additional control registers., Addressing Modes and Instruction Formats The 360 has five instruction formats. Each format is associated with a single addressing mode and has a set of operations defined for that format. While some operations are defined in multiple formats, most are not., Format Length Use, Name in bytes, RR 2 Register to register transfers., RS 4 Register to storage and register from storage, RX 4 Register to indexed storage and register from indexed storage, SI 4 Storage immediate, SS 6 Storage–to–Storage. These have two variants,, eachof which we shall discuss soon., RR (register-register ), The operand fields of RR-format instructions designate two registers,, ┌────────┬────┬────┐, │Op Code │ R₁ │ R₂ │, └────────┴────┴────┘, 0 8 12 15, RR (Register–to–Register) Format, This is a two–byte instruction of the form OP R1,R2., The first byte contains the 8–bit instruction code., The second byte contains two 4–bit fields, each of which encodes a register number., This instruction format is used to process data between registers., Here are some examples., AR 6,8 1A 68 Adds the contents of register 8 to register 6., AR 10,11 1A AB Adds the contents of register 11 to register 10., AR R6,R8 1A 68 Due to the standard Equate statements we use, in our program assignments,, R6 stands for 6 and R8 for 8., RX (register-indexed), The operand fields of RX-format instructions designate one or two registers, including an index register, and a virtual storage address (coded as an implicit address or an explicit address),, ┌────────┬────┬────┬────┬────────────┐, │Op Code │ R₁ │ X₂ │ B₂ │ D₂ │, └────────┴────┴────┴────┴────────────┘, 0 8 12 16 20 31, RX (Register–Indexed Storage) Format, This is a four–byte instruction of the form OP R1,D2(X2,B2)., The first byte contains the 8–bit instruction code., The second byte contains two 4–bit fields, each of which encodes a register number., In order to illustrate this, consider the following data layout., FW1 DC F‘31’, DC F‘100’ Note that this full word is not labeled, Suppose that FW1 is at an address defined as offset X‘123’ from register 12., As hexadecimal C is equal to decimal 12, the address would be specified as C1 23., The next full word might have an address specified as C1 27, but we shall show, another way to do the same thing. The code we shall consider is, L R4,FW1 Load register 4 from the full word at FW1., The operation code is X‘58’., AL R4,FW1+4 Add the value at the next full word address., The operation code is X‘5E’., RS (register-storage ), The operand fields of RS-format instructions designate two registers, and a virtual storage address (coded as an implicit address or an explicit address)., ┌────────┬────┬────┬────┬────────────┐, │Op Code │ R₁ │ R₃ │ B₂ │ D₂ │, └────────┴────┴────┴────┴────────────┘, 0 8 12 16 20 31, RS (Register–Storage) Format Examples, These are four–byte instructions of the form OP R1,R3,D2(B2)., 1. Load Multiple Operation code = X‘98’., Suppose the label FW3 (supposedly holding three 32–bit full–words) is at an, address specified by offset X‘100’ from base register R7. Then we have, LM R5,R7,FW3 98 57 71 00, Unpacking the object code, we again find the parts., The operation code is X‘98’, which indicates a multiple register load., The next byte has value X‘57’, which indicates two registers: R5 and R7., Here it is used to represent a range of three registers: R5, R6, and R7., The last two bytes contain the address of the label FW3. The two bytes 71 00 indicate, 1) that the base address is contained in register R7, and, 2) that the displacement from the base address is X‘100’., 2. The above example with an explicit base register., LA R4,FW3 Load the address FW3 into R4, LM R5,R7,0(4) The address is displaced 0 from the, value in R4, the explicit base register, One might have an instruction of the following form, which is not equivalent to the above., LM R5,R7,12(4) The address is displaced 12 (X‘C’) from, the value in R4, SI (storage-immediate), The operand fields of SI-format instructions designate immediate data and a virtual storage address., ┌────────┬─────────┬────┬────────────┐, │Op Code │ I₂ │ B₁ │ D₁ │, └────────┴─────────┴────┴────────────┘, 0 8 16 20 31, SI (Storage Immediate) Format, This is a four–byte instruction of the form OP D1(B1),I2., The first byte contains the 8–bit instruction code., The second byte contains the 8–bit value of the second operand, which is treated as an, immediate operand. The instruction contains the value of the operand, not its address., The first operand is an address, specified in standard base register and displacement form., Two instances of the instruction are :, MVI Move Immediate, CLI Compare Immediate, Suppose that the label ASTER is associated with an address that is specified using, register R3 as a base register, with X‘6C4’ as offset., The operation code for MVI is X‘92’ and the EBCDIC for ‘*” is X‘5C’., MVI ASTER,C ‘*’ is assembled as 92 5C 36 64., SS (storage-storage), The operand fields and subfields of SS-format instructions designate two virtual storage addresses (coded as implicit addresses or explicit addresses), │Op Code │ L │ B₁ │ D₁ │ B₂ │ D₂ │, 0 8 16 20 32 36 47, Storage–to–Storage: Character Instructions, These are of the form OP D1(L,B1),D2(B2), which provide a length for only operand 1. The length is specified as an 8–bit byte., The first byte contains the operation code, say X‘D2’ for MVC or X‘D5’ for CLC., The second byte contains a value storing one less than the length of the first operand,, which is the destination for any move. Bytes 3 and 4 specify the address of the first operand, using the standard base register and displacement format. Bytes 5 and 6 specify the address of the second operand, using the standard base register and displacement format., It is quite common for both operands to use the same base register., Operations on the 360, The instructions on the 360 can be divided into classes., Four basic types of operations on data are supported:, 1. Logical operations on hits, character strings, and fired words. These are mostly RR and RX formats with a few RS instructions., 2. Decimal or character operations on strings of characters or decimal digits. These are SS format instructions., 3. Fixed-point binary arithmetic. This is supported in both RR and RX formats., 4. Floating-point arithmetic. This is supported primarily with RR and RX instructions., Assembler, Assembler is a program for converting instructions written in low-level assembly code into relocatable machine code and generating along information for the loader., It generates instructions by evaluating the mnemonics (symbols) in operation field and find the value of symbol and literals to produce machine code. Now, if assembler do all this work in one scan then it is called single pass assembler, otherwise if it does in multiple scans then called multiple pass assembler. Here assembler divide these tasks in two passes:, Pass-1 Assembler:, Define symbols and literals and remember them in symbol table and literal table respectively., Keep track of location counter, Process pseudo-operations.(pseudo means text based code ), Pass-2 Assembler:, Generate object code by converting symbolic op-code (machine code)into respective numeric op-code, Generate data for literals and look for values of symbols., Firstly, We will take a small assembly language program to understand the working in their respective passes. Assembly language statement format:, [Label] [Opcode] [operand], Example:M ADD R1, ='3', where, M - Label; ADD - symbolic opcode;, R1 - symbolic register operand; (='3') - Literal, Assembly Program:, Label Op-code operand LC value(Location counter), JOHN START 200, MOVER R1, ='3' 200, MOVEM R1, X 201, L1 MOVER R2, ='2' 202, LTORG 203, X DS 1 204, END 205, Let’s take a look on how this program is working:, START: This instruction starts the execution of program from location 200 and label with START provides name for the program.(JOHN is name for program), MOVER: It moves the content of literal(=’3′) into register operand R1., MOVEM: It moves the content of register into memory operand(X)., MOVER: It again moves the content of literal(=’2′) into register operand R2 and its label is specified as L1., LTORG: It assigns address to literals(current LC value)., DS(Data Space): It assigns a data space of 1 to Symbol X.(Data Space is a range of up to two giga bytes of contiguous virtual storage address that a program can directly manipulate through assembler instructions.)., END: It finishes the program execution., Working of Pass-1: Define Symbol and literal table with their addresses., Note: Literal address is specified by LTORG or END., Working of Pass-2:, Pass-2 of assembler generates machine code by converting symbolic machine-opcodes into their respective bit configuration(machine understandable form). It stores all machine-opcodes in MOT table (op-code table) with symbolic code, their length and their bit configuration. It will also process pseudo-ops and will store them in POT table(pseudo-op table)., Various Data bases required by pass-2:, 1. MOT table(machine opcode table), 2. POT table(pseudo opcode table), 3. Base table(storing value of base register), 4. LC ( location counter), Data Structure, The second step in our design procedure is to establish the databases that we have to work with., Pass 1 Data Structures, 1. Input source program, 2. A Location Counter (LC), used to keep track of each instruction’s location., 3. A table, the Machine-operation Table (MOT), that indicates the symbolic mnemonic, for each instruction and its length (two, four, or six bytes), 4. A table, the Pseudo-Operation Table (POT) that indicates the symbolic mnemonic and action to be taken for each pseudo-op in pass 1., 5. A table, the Symbol Table (ST) that is used to store each label and its corresponding value., 6. A table, the literal table (LT) that is used to store each literal encountered and its corresponding assignment location., 7. A copy of the input to be used by pass 2., Pass 2 Data Structures, 1. Copy of source program input to pass1., 2. Location Counter (LC), 3. A table, the Machine-operation Table (MOT), that indicates for each instruction, symbolic mnemonic, length (two, four, or six bytes), binary machine opcode and format of instruction., 4. A table, the Pseudo-Operation Table (POT), that indicates the symbolic mnemonic and action to be taken for each pseudo-op in pass 2., 5. A table, the Symbol Table (ST), prepared by pass1, containing each label and corresponding value., 6. A Table, the base table (BT), that indicates which registers are currently specified as base registers by USING pseudo-ops and what the specified contents of these registers are., 7. A work space INST that is used to hold each instruction as its various parts are being assembled together., 8. A work space, PRINT LINE, used to produce a printed listing., 9. A work space, PUNCH CARD, used prior to actual outputting for converting the assembled instructions into the format needed by the loader., 10. An output deck of assembled instructions in the format needed by the loader., Format of Data Structures, The third step in our design procedure is to specify the format and content of each of the data structures. Pass 2 requires a machine operation table (MOT) containing the name, length, binary code and format; pass 1 requires only name and length. Instead of using two different tables, we construct single (MOT). The Machine operation table (MOT) and pseudo-operation table are example of fixed tables. The contents of these tables are not filled in or altered during the assembly process., The following figure depicts the format of the machine-op table (MOT), —————————————– 6 bytes per entry ———————————–, ALGORITHM, Assembler Pass 1:, begin, read first input line, if OPCODE ='START' then, begin, save #[OPERAND] as starting address, initialize LOCCTR to starting address, write line to intermediate file, read next input line, end {if START}, else, initialize LOCCTR to 0, while OCODE != 'END' do, begin, if this is not a comment line then, begin, if there is a symbol in the LABEL field then, begin, search SYMTAB for LABEL, if found then, set error flag (duplicate symbol), else, insert (LABEL,LOCCTR) into SYMTAB, end {if symbol}, search OPTAB for OPCODE, if found then, add 3 {instruction length} to LOCCTR, else if OPCODE='WORD' then, add 3 to LOCCTR, else if OPCODE = 'RESW' then, add 3 * #[OPERAND] to LOCCTR, else if OPCODE = 'RESB' then, add #[OPERAND] to LOCCTR, else if OPCODE = 'BYTE' then, begin, find length of constant in bytes, add length to LOCCTR, end {if BYTE}, else, set error flag (invalid operation code), end {if not a comment}, write line to intermediate file, read next input line, end {while not END}, write last line to intermediate file, save (LOCCTR – starting address) as program length, end {Pass 1, ALGORITHM, Assembler Pass2:, begin, read first input line (from intermediate file), if OPCODE ='START' then, begin, write listing line, read next input line, end {if START}, write Header record to object program, initialize first Text record, while OPCODE != 'END' do, begin, if this is not a comment line then, begin, search OPTAB for OPCODE, if found then, begin, if there is a symbol in OPERAND field then, begin, search SYMTAB for OPERAND, if found then, store symbol value as operand address, else, begin, store 0 as operand address, set error flag (undefined symbol), end, end {if symbol}, else, store 0 as operand address, assemble the object code instruction, end {if opcode found}, else if OPCODE ='BYTE' or 'WORD' then, convert constant to object code, if object code will not fit into the current Text record then, begin, write Text record to object program, initialize new Text record, end, add object code to Text record, end {if not comment}, write listing line, read next input line, end(while not END), write last Text record to object program, write End record to object program, write last listing line, end{Pass 2, LOADERS, Defn:Loaderisaprogramthatplacesprogramsintomemoryandpreparesthemforexecution., FunctionsofLoader, The loader is responsible for the activities such as allocation, linking, relocation and loadingAllocation:allocatingthespaceforprograminthememory,bycalculatingthesizeoftheprogram.Linking:Itresolves thesymbolic references (code/data) between theobject, Relocation:Addressdependent locationsintheprogram,suchaddressconstantsmustbeadjustedaccordingto allocated space, Loading:Physicallyplacesallthemachineinstructionsanddataintothe memory, Loaders SchemeortypesofLoader:, Basedontheabovefourfunctionstheloaderisdividedintodifferenttypes,theyare, CompileandgoloaderorAssembleandgoloader, Generalloaderscheme, Absoluteloader, Directlinkingloader, Relocatingloader, Dynamiclinkingloader, Compile and goloader orAssemblea nd 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 onepartofmemoryandtheassembledmachineinstructionsanddataisdirectlyputintotheirassignedmemory locations. After completion of assembly process, assign starting address of the program to the location counter., Ex:WATFOR-77, Advantages, Easytoimplement,, Disadvantages, Portionofmemory iswastedbecausecombinationofassemblerandloaderactivities,thiscombinationprogramoccupieslargeblock ofmemory, Thereis noproductionof.obj file, Itcannothandlemultiplesourceprogramsor multipleprogramswritten in differentlanguages, Theexecutiontimewillbemoreinthisschemeaseverytimeprogram isassembledandthenexecuted, GeneralLoaderScheme, 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 anexecutableformattheirassignedmemory.Theloaderoccupiessomeportionofmainmemory., Advantages:, Theprogramneednotberetranslatedeachtimewhilerunning it, Thereisnowastageofmemory,becauseassemblerisnotplacedinthememory, Itis possibletowritesourceprogramwithmultipleprograms andmultiplelanguages, Absolute Loader, Absoluteloaderisakindofloaderinwhichrelocatedobjectfiles arecreated,loaderaccepts thesefiles and places them at specified locations in the memory. This type of loader is called absolutebecause norelocationinformationisneeded; ratherit isobtainedfromthe programmerorassembler., The starting address of every module is known to the programmer, this corresponding startingaddress is stored in the object file, then task of loader becomes very simple and that is to simplyplacetheexecutableformofthemachineinstructionsatthelocations mentionedintheobjectfile.Inthisschemetheprogrammerorassemblershouldhaveknowledgeofmemorymanagement.Theresolutionofexternalreferencesorlinkingofdifferentsubroutinesaretheissueswhichneedtobehandledby theprogrammer., Theprogrammershouldtakecareoftwothings:firstthingis:, Specificationofstartingaddressofeachmoduletobeused.Ifsomemodificationisdonein, somemodulethenthe lengthofthat modulemay vary. Thiscausesachangeinthestarting addressofimmediatenextmodules,itsthentheprogrammer'sdutytomakenecessarychangesinthestarting addressesof respectivemodules., Secondthingis,whilebranchingfromonesegmenttoanothertheabsolutestartingaddressofrespective module is to be known by the programmer so that such address can be specified atrespectiveJMPinstruction.Forexample, Algorithm of absolute loader, Advantages:Thustheabsoluteloaderissimpletoimplementinthis scheme, Allocationisdonebyeitherprogrammerorassembler, Linkingisdonebytheprogrammerorassembler, Resolutionisdonebyassembler, Simplyloadingisdoneby theloader, Disadvantages: In this scheme, it's 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., Write a difference between absolute loader and compile and go loader ., DirectLinkingLoaders, The direct linking loader is the most common type of loader. The loader cannot have the directaccesstothesourcecode.Theassemblershouldgivethefollowinginformationtotheloader, Thelengthoftheobjectcodesegment, Thelistofallthesymbolswhicharenotdefinedinthecurrentsegmentbutcan beusedinthecurrentsegment., The list of all the symbols which are defined in the current segment but can be referred bytheothersegments., The list of symbols which are not defined in the current segment but can be used in the currentsegment are stored in a data structure called USE table. The list of symbols which are defined inthecurrentsegmentandcanbereferredbytheothersegments arestoredinadatastructurecalledDEFINITIONtable., Thereare4typesofcardsavailableinthedirectlinkingloader.Theyare, ESD-Externalsymboldictionary, TXT-card, RLD-Relocationandlinkingdictionary, END-card, ESDcard:Itcontainsinformationaboutallsymbolsthataredefinedintheprogrambutreferencesomewhere, Itcontains:, Referencenumber, Symbolname, TypeId, Relativelocation, Length, ThereareagainESDcardsclassifiedinto3typesofmnemonics.Theyare:, SD[SegmentDefinition]:Itrefers tothesegmentdefinition, LD;Itreferstothelocaldefinition, ER:itrefers totheexternalreferencetheyareusedinthe[EXTRN]pseudoopcode, TXTCard:Itcontainsthe actualinformationare text whicharealreadytranslated., RLDCard:Thiscardcontainsinformationaboutlocationintheprogramwhosecontextsdepends on theaddressatwhich theprogramisplaced., Inthis weareused ‘+’and ‘–‘sign,whenweareusing the‘+’ signthenno needof relocation,whenweareusing ‘-‘signrelocationisnecessary., TheformatofRLD contains:, Referencenumber, Symbol, Flag, Length, Relativelocation, ENDCard:Itindicatesendoftheobjectprogram., Relocatable loaders, A relocating loader is capable of loading a program to begin anywhere in memory.The addresses produced by the compiler run from 0 to L–1. After the program has been loaded, the addresses must run from N to N +L–1. Therefore, the relocating loader adjusts, or relocates, each address in the program., Advantage is that no overhead occurs unless the procedure to be called or referenced is actually used. Disadvantage is considerable overhead & complexity because loading & linking is postponed until execution time., Overlays, Overlaying is a programming method that allows programs to be larger than the computer's main memory. ... An embedded system would normally use overlays because of the limitation of physical memory, which is internal memory for a system-on-chip, and the lack of virtual memory facilities., The concept of overlays is that whenever a process is running it will not use the complete program at the same time, it will use only some part of it. ... “The process of transferring a block of program code or other data into internal memory, replacing what is already stored”., Disadvantage –, Overlap map must be specified by programmer., Programmer must know memory requirement., Overlapped module must be completely disjoint., Programming design of overlays structure is complex and not possible in all cases., Dynamic loading, Dynamic loading is a mechanism by which a can, at , load a (or other ) into memory, retrieve the addresses of functions and variables contained in the library, execute those or access those variables, and unload the library from memory. It is one of the 3 mechanisms by which a computer program can use some other software; the other two are and . Unlike static linking and dynamic linking, dynamic loading allows a to start up in the absence of these libraries, to discover available libraries, and to potentially gain additional functionality., Advantage of dynamic loading is that an unused routine is never loaded. Dynamic loading does not require special support from the OS. Operating systems may help the programmer, however, by providing library routines to implement dynamic loading., Disadvantages: dynamic loading isn't available on all systems, 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 the segments 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