Assemblers (4)_1

reference)

https://sepang2.tistory.com/34

Linkers and Loaders

Assembler Design Option
•2-pass assembler scans source code twice!
–First, to produce a symbol table and secondly to produce object codes.

•Is this the only way to design an assembler?
–Of course, NOT… We can make it with the 1-pass algorithm or even a multi-pass algorithm!

-> n-pass algorithm을 쓴 assembler 
–In this lecture, we will just study on the “one-pass assembler”, which scans the source code only one time

(-> avoids the overhead of an additional pass over the source program) but often must patch the object code produced during this scan.

 

One-Pass Assemblers
•Two different types
–Type I “Load-and-Go Assembler”: produces object code directly in memory for immediate execution, with no object program written out, and no loader needed.

-> object file를 만들지 않는 assembler
_Type II: produces the usual kind of object program for later execution, so object program is produced, and loader is yet needed.

-> 2-pass 어셈블러와 비슷, object program을 만들어줌

•The main problem in trying to assemble a program in one pass involves “forward references”
_Instruction operands often are symbols that have not yet been defined in the source program.

Thus, the assembler does not know what address to be inserted into the translated instruction

-> Type2의 경우 forward refernece를 해결해야만 함!

 

Fig. 2.18
•Sample program for a one-pass assembler
–It has the same logic as in Fig. 2.2 for SIC
_All data item definitions are placed ahead of instructionsthat references them in order to eliminate forward references to the data items

•However, forward references to labels on instructions cannot be eliminated as easily.
–E.g., line 15, 30, 35, 65, and 155
•How can Type 1 & 2 one-pass assemblers address this issue?

Type I One-Pass Assemblers: “Load-and-Go”
•Useful in a system that is oriented toward program development & testing.

•Programs are re-assembled nearly every time they are run.

•The load-and-go assembler produces the object code in memory rather than writing it out on secondary storage
–Efficiency of the assembly process ↑ beacuse I/O is very sollow

•How to solve forward references?
–Store undefined symbols in the SYMTAB with the address of the field that references this symbol
–When the symbol is defined later, look up the SYMTAB and modify the field with correct address

 

Fig. 2.19(a)
•Object code in memory & symbol table entries for the program in Figure 2.18 after scanning line 40

-> Type1은 리스트 형태로 필드들의 주소값을 저장해놓음.

START 1000이기에 1000부터 시작, ___는 forwaord reference랑 연관되어 있음.

Fig. 2.19(b)
•Object code in memory & symbol table entries for the program in Figure 2.18 after scanning line 160

-> Object program을 메모리에 실제로 올릴 때, 정의되지 않은 SYMBOL들을 만날 수 O

SYMBOL TABLE을 이용해 object code를 만들다

=> Type1의 forward reference를 해결하는 방법

 

Type II One-Pass Assemblers

•Writes the object program on disk

•How to solve forward references?
–Forward references are entered into lists as before.
–When the definition of a symbol is encountered, generate another Text records with correct operand address
–When loaded, correct address will be inserted by loader

-> forward reference에 대한 정보를 Text record로 저장 -> 나중에 Loader가 수정

 

Fig. 2. 20
•Object program from one-pass assembler for program in Figure 2.18
–The 2nd Text record contains the object code generated from line 10 through 40
_When the definition of ENDFIL on line 45 is encountered, the assembler generates the 3rd Text record

   ->This specifies that the value 2024 (the address of ENDFIL) is to be loaded at location 201C (the operand address field of the JEQ on line 30)

ENDFILL 정의를 만나게 되면,,,?

Load된 Object를 수정함. Object file 자체를 수정 X

 

/? 일반적인 텍스트 레코드와 특수 텍스트 레코드 구분법:

노말에는 다음 주소값이 들어가 있음, 

 

/? Assembler가 

  I/O 연산이 느리다보니 Loader가 수정함.

 

Linkers and Loaders

 

Translating and Starting a Program
•A translation hierarchy for high-level language program like C
–First compiled into an assembly language program and then assembled into an object module in machine language
–The linker combines multiple modules with library routines to resolve all references
–The loader then places the machine code into the proper memory locations for execution by the processor

• To speed up the translation process, some

steps are skipped or combined, but these
are the logical 4 phases that programs go
through:
_Some compilers produce object modules directly, and some systems use linking loaders that perform the last two steps

 

 

 

 

 

 

Linkers (1/2)
•Separate compilation

-> program을 짤 때, 여러 source file을 만들 수 있음. 이 file들이 object file로 독립적으로 번역된다.

-> 여러 개의 source file 중 하나를 수정하면, 수정된 것만 다시 compile 하면 되기에 장점!
_Splitting a program across many files, each of which contains a logically related collection of subroutines and data structures that form a module in a larger program
_A file, also called a module, can be compiled and assembled without knowledge of what is in the other files, so changes to one module do not require recompiling the entire program
_Separate compilation necessitates the additional step of linking to combine object files from separate modules and fix their unresolved references

Linker는 object file들을 묶어주는 역할 및 unresolved references를 처리

Linkers (2/2)

•Linker
_A system program that combines independently assembled machine language programs, and resolves all undefined labels into an executable file (by using the relocation information and symbol table in each object module)
_The linker produces an executable file that can be run on a computer. Typically, this file has the same format as an object file, except that it contains no unresolved references

•In summary, a linker performs 3 tasks:
–Searches the program libraries(= prewritten routines) to find library routines used by the program
_Determines the memory locations that each object module will occupy and relocates its instructions by adjusting absolute references (=program relocation features)
–Resolves external references among object files

• 프로그램에서 사용하는 라이브러리 루틴을 찾기 위해 프로그램 라이브러리(=미리 작성된 루틴)를 검색
• 각 객체 모듈이 점유할 메모리 위치를 결정하고 절대 참조를 조정하여 명령을 재배치
• 개체 파일 간의 외부 참조 해결

 

Loader (1/2)

-> Linker가 실행 파일을 만들어주면 이를 메모리에 올리고 실행시킴.
•A program produced by the linker can be run (i.e., executable). Before being run, the program resides in a file on secondary storage, such as a disk. The loader in an operating system brings a program into memory and starts it running
•Thus, to start a program, the loader performs the following steps:

 

1.Read the executable file’s header to determine the size of the text and data segments
2.Creates a new address space (for the program) large enough for the text and data segments, along with a stack segment
3.Copies the instructions and data from the executable file into the new address space (i.e., memory)
4.Copies the parameters (if any) to the main program onto the stack
5.Initializes the machine registers and sets the stack pointer to the first free location
6.Jumps to a start-up routine that copies the parameters from the stack to registers and calls the main routine of the program. When returning from the main routine, the start-up routine terminates the program with the exit system call

1. 실행 파일의 헤더를 읽고 텍스트 및 데이터 세그먼트의 크기를 결정한다.
2. 스택 세그먼트와 함께 텍스트 및 데이터 세그먼트에 대해 충분히 큰 새 주소 공간(프로그램용)을 생성한다.
3. 실행 파일의 명령(text segment)과 데이터(data segment)를 새 주소 공간(메모리)으로 복사한다.
4. 매개변수(있는 경우에)를 기본 프로그램의 스택에 복사한다.
5. machine register를 초기화하고 스택 포인터를 첫번째 여유 위치로 설정한다.
6. 스택에서 레지스터로 매개변수를 복사하고 프로그램의 메인 루틴을 호출하는 시작 루틴으로 점프한다. 메인 루틴에서 돌아올 때(returning) 시작 루틴은 종료 시스템 호출(exit system call)로 프로그램을 종료한다.

Loader (2/2)

•Loader
–A system program of performing the loading function, which places an object program in main memory for execution

•Many loaders also support relocation and linking.

재배치는 object program에서 절대 주소를 수정한다. 연결은 둘이상의 분리된 object program을 결합한다.
–Relocation modifies the absolute addresses in the object program.
–Linking combines two or more separate object programs.

로더가 오직 loading만을 수행한다면 absolute loader, 재배치나 연결 기능도 수행한다면 linking loader로 분류할 수 있다.
•Two kinds of a loader:
–Absolute loader
–Linking loader

 

Basic Loader Functions

•Absolute Loader (Loading function만 수행하는 Loader)
–The simplest loader with neitherlinking norprogram relocation operations

•All functions are accomplished in a single pass.

 

헤더 레코드를 확인하여 로드를 위해 올바른 프로그램이 제공되었고 사용 가능한 메모리 공간에 할당할 수 있는지 확인한다. 그리고 텍스트 레코드를 읽을 때 포함된 object code가 메모리의 표시된 주소로 이동된다. END 레코드에 다다르면 로더가 지정된 주소(프로그램의 시작 주소)로 점프하여 로드된 프로그램의 실행을 시작

_Header record is checked to verify that the correct program has been presented for loading and that it will fit into the available memory (collect한 프로그램 파일인지를 확인, 프로그램 파일의 크기를 담을 수 있는 메모리 공간 여부 확인)
–As each Text record is read, the object code it contains is moved to the indicated address in memory

(읽어서 메모리에 올림)
_When the End record is encountered, the loader jumps to the specified address to begin execution of the loaded program

(여기에는 첫 실행할 instruction의 주소값이 있으므로 이를 읽어 점프하면 실행시킬 수 있는 것.)

 

 

우선 H record를 확인하여 주소 1000부터 시작함을 확인하고 107A만큼의 공간이 있는가 판단한다. T record를 거치면서 해당 object code가 메모리로 이동하고 E record를 만나게 되면 시작 주소 1000으로 점프하여 프로그램의 실행을 시작하는 것이다. 해당 과정을 거쳐 메모리에 프로그램이 로드되면 메모리의 모습은 아래와 같을 것이다.

 

Fig. 3.1 Loading of Absolute Program
•(b) The program loaded in memory

Absolute는 program relocation X, 따라서 정해진 주소에서부터 시작

Fig. 3.2 Absolute Loader Algorithm

Boot Loader (Bootstrap loader)

 

해당 로더는 컴퓨터를 처음 켜질 때 실행되는 특수한 유형의 로더이다. 우선 실행할 첫 번째 프로그램(보통 OS)을 로드한다. 그리고 HW 로직이 ROM의 주소 0의 프로그램을 읽는다. ROM은 제조업체에서 설치하는데 ROM에는 부트스트랩 프로그램(부트 로더)과 하드웨어를 제어하는 기타 루틴(ex. BIOS)이 포함되어 있다. absolute loader와 유사하게 재배치&연결을 수행하지 않는다.

•A special type of absolute loaders, executed when a computer is first turned on.
–Loads the first program to be executed (usually, an operating system)
•The h/w logic reads a program from address 0 of ROM (Read only Memory)
–ROM is installed by the manufacturer
–ROM contains bootstrapping program (boot loader) and some other routines that controls h/w (e.g., BIOS)

 -> 요즘에는 ROM보다 Flash Meomory 사용, Long term memory보다 빠르기 때문

•No relocation & no linking

 

 

Absolute Loader: Pros & Cons
•Pros
–Simplicity & Efficiency (1-pass로 프로그램을 올릴 수 있으므로)

•Cons
_Programmers must specify (when the program is assembled) the actual (starting) address at which the program will be loaded into memory. (프로그램이 크면 어떤 주소를 할당해야하는지 프로그래머가 잘 고민해야함)
->Not possible with larger and more advanced machines
–All subroutines must have pre-assigned absolute addresses. (서브 루틴의 시작주소 또한 다 정해져야 함, 여러 라이브러리들이 같은 주소를 가지면 동시에 가져올 수 없음 memory overlab은 안되므로!)
->Makes it difficult to use subroutine libraries efficiently
–Cannot run several programs together

 

Machine-Dependent Loader Features
•Linking Loader
–More complex loader, suitable for use on a SIC/XE system and on most modern computers
–Program relocation, linking, and simple loading functions

•Relocation
–The way relocation is implemented in a loader is dependent onmachine characteristics.
–Two methods for specifying relocation as part of the object program -> use of “Modification record” and “Relocation bit”