지금까지 어셈블러에 대해 알아보았다. 어셈블러는 어셈블리어를 기계가 이해할 수 있는 object code로 변환시킨다. 이제 그 다음 과정을 위해 사용되는 linker와 loader에 대해 알아본다.

🔸Tnaslating and Starting a Program

고급 언어 프로그램의 번역 과정을 다시 살펴보자.

1. Complier: high-level language(C Program)를 low-level language(Assembly)로 변환
2. Assembler: Assembly를 기계어로 변환하여 오브젝트 생성
   • Assembly language: 기계어와 1:1대응되는 low-level 언어
3. Linker: 여러 개의 오브젝트 파일을 하나의 실행 파일로 결합하여 기계어 프로그램을 만듦
4. Loader: 실행 파일을 메모리에 올려 실행할 준비

Translation 과정을 빠르게하기 위해 일부 단계가 생략되거나 결합될 수 있지만 논리적인 4단계는 명확하다.

• 컴파일러가 object module을 직접 만들거나
• 마지막 두 단계를 수행하는 linking loader를 사용하는 등..

Separate compilation

• 프로그램은 논리적으로 관련된 서브루틴과 자료구조의 집합이 담긴 여러가지의 소스파일로 이루어져 있음
• 이 파일들은 어셈블러에 의해 object file로 만들어진다.
• 이는 하나의 소스 파일을 수정해도 다른 소스파일을 다시 assemble할 필요가 없도록 만듦

그래서 object file은 여러개가 생기게 되고, 이들을 엮어서 하나의 프로그램으로 만드는 것이 Linker의 역할이다.

🔸Linkers

• 독립적으로 어셈블된 machine language program을 결합하고, 정의되지 않은 레이블을 수정하여 executable file 생성
  • 각 object module의 relocation 정보와 symbol table 사용
  • 생성된 executable file과 object file의 유일한 차이점은 해결되지 않은 reference 존재 여부
• 주요 작업
  • 프로그램에서 사용되는 library routine 찾기 (프로그램 라이브러리(prewritten routines)를 검색)
  • 각 object module이 차지할 메모리 위치 결정하고 absolute reference를 조정하여 instruction 재배치
  • object file 간의 external reference 해결

이렇게 만들어진 program은 디스크와 같은 보조 저장 장치에 위치한다. 이 프로그램을 실행하기 위해 Loader가 필요하다.

🔸Loader

• linker가 생성한 program을 메모리로 가져와 실행을 시작
• 메모리에 할당된 프로그램은 아래와 같은 모양

Start a program 과정

1. 헤더 읽기: executable file의 헤더를 읽어 텍스트와 data segment의 크기 결정
2. 주소 공간 생성: 텍스트, data segment, stack segment를 포함할 수 있는 프로그램용 주소 공간 새로 생성
3. 명령어 및 데이터 복사: executable file에서 명령어와 데이터를 새로 생성한 주소 공간(메모리)으로 복사
4. 매개변수 복사: 메인 프로그램에 대한 매개변수가 존재하는 경우 스택에 복사
5. 레지스터 초기화: machine 레지스터를 초기화하고, 스택 포인터를 첫 번째 빈 위치로 설정
6. Start-up routine으로 점프: 스택의 매개변수를 레지스터로 복사하고 프로그램의 메인 루틴을 호출, 메인 루틴에서 반환하면 start-up루틴은 종료 시스템을 호출하여 프로그램 종료

Loader는 오직 loading만 하는 absolute loader와 linking과 relocation 기능도 지원하는 linking loader 2가지 종류를 가진다.

🔹Absolute Loader

• 가장 간단한 형태의 loader로, link나 relocation 작업을 수행하지 않음
• 모든 기능을 단일 패스로 수행
  • Header record을 확인하여 올바른 프로그램이 load되었는지, 사용 가능한 메모리에 적합한지 검증
  • Text record를 읽고 object code를 메모리의 지정된 주소로 이동
  • End record를 만나면 loader는 지정된 주소로 점프하여 load된 프로그램의 실행을 시작

object program example

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

ex) Boot Loader

정해진 위치에 올리기만 하는 Absolute loader는 일반적이지 않고 특별한 상황에서 쓰인다. 대표적인 예시로 컴퓨터를 처음 킬 때 실행되는 특수한 유형의 Boot Loader가 있다.

1. 실행할 첫 번째 프로그램을 로드(보통 OS를 로드함)
2. HW로직이 ROM의 0 주소에 해당하는 프로그램(boot loader)를 읽음
   • ROM은 제조업체에서 설치하며, bootstrap program(boot loader)과 하드웨어를 제어하는 기타 루틴(ex.BIOS)를 포함

• NO relocation, No linking

Pros & Cons

장점

• 1pass로 수행되기에 단순성과 효율성을 가짐

단점

• 프로그래머는 프로그램이 메모리에 로드될 실제 주소를 지정해야 함
  • 더 크거나 advanced된 기계에서는 불가능
  • 근데 프로그래머가 메모리 계산을 잘 한다면,, 효율적일 수도 있음
• 모든 서브루틴에 사전에 할당된 절대 주소가 필요
  • 서브루틴 라이브러리를 효율적으로 사용하기 어려움
• 여러 프로그램을 함께 실행할 수 없음

🔹Linking Loader

• SIC/XE 시스템 및 대부분의 최신 컴퓨터에서 사용하기 적합한 더 복잡한 loader
• 단순 loading기능 뿐만 아니라, relocation, linking 기능을 수행
  • 모듈 간 reference를 해결하는데 유용

Loader에서 relocation이 구현되는 방식은 기계의 특성에 따라 다르다.(Machine-dependant feature) 재배치 지정 방식은 Modification record또는 Relocation bit을 사용하는 2가지가 존재한다.

Relocation w. Modification record

SIC/XE에서 수정이 필요한 instruction은 모두 immediate addressing으로 나타나있고, 이의 address field는 해당 Symbol(RDREC, WRREC)이 프로그램 시작 주소에서 얼마나 떨어져있는가를 나타내고 있다. 하지만 해당 Symbol의 절대적인 주소는 현재 address field값에 프로그램 시작 주소(COPY)를 더한 값이다. 그래서 Modification record에서 해당 address field에 프로그램 시작 주소를 더하라고 나타낸다.

• 위와 같이 relative 또는 immediate addressing을 사용하는 SIC/XE 시스템에 적절한 Relocation 방법으로, SIC 버전 시스템에는 적절하지 않음
  • 그 이유는 SIC는 모든 주소값이 direct addressing이므로, 모든 instruction이 재배치를 해야함
  • 이에 따라 모든 instruction에 대한 modification record가 필요
    → 많은 modification record로 object program의 크기가 2배 이상이 되며 비효율적

이러한 SIC에서의 relocation 문제를 해결하기 위해 Bit mask 방식을 사용한다.

Relocation w. Bit mask⭐

주로 direct addressing을 사용하고, fixed instruction format을 가지는 machine에서 machine(SIC)에서 유용하다.

• 기존 modification record는 [수정할 주소, 길이] 형태를 가짐
  • fixed instruction format이라면 길이를 나타낼 필요X
  • 주소 필드 대신 비트벡터를 사용
• Relocation Bit
  • 1: 프로그램의 시작 주소를 주소 필드에 추가하여 재배치를 수행해야함을 나타냄
  • 0: 수정이 필요하지 않음
• 위처럼 모든 instruction에 bit를 표시하고, 이를 나열하여 16진수로 나타냄
• 첫번째 T record에서 object code의 길이를 표현하는 열 이후의 ‘EFC’는 ‘1111 1111 1100’으로 나열된 bit mask를 나타냄
  • ‘1111 1111 1100’의 가장 왼쪽비트부터 첫번째 instruction의 relocation bit가 됨

🔸Example

프로그램은 관련된 모든 Control section들이 linking으로 결합된 logical entity이다. 하지만 loader의 관점에서는 프로그램이라는 개념이 없고, link되고 재배치되고 load될 control section들이 존재할 뿐이다. EXTDEF & EXTREF로 정의된 symbol들의 정보는 linker에게 잘 알려줘야하고, 이를 통해 loader가 재배치할 수 있도록 해야한다.

1. Assembly → Object code

아래 각 코드들은 다른 CS(PROGA, PROGB, PROGC)에 속해있다. 각 섹션별로 LIST와 END symbol이 정의되어있고, 섹션에 상관없이 REF1~REF8은 모두 동일한 reference를 사용한다. 주목해야 할 것은 3개의 CS에서 동일한 reference가 적혀있지만 이들을 다루는 방법은 섹션마다 다르다는 것이다.

• 각 CS에서 local reference의 주소 계산은 가능하니 object code에 잘 적으면 됨
• external reference는 각 CS에서는 바로 알 수 없으니 format4 instruction으로 전환하여 0으로 채워둠
  • 그리고 modification record가 적힐 것이고 이걸 보고 loader가 수정해서 절대 주소를 찾아낼 것임
• 모르는게 있더라도, 아는 것들은 다 적어야함 → 어셈블러는 자기가 아는거까지 처리!
  
  

2. Object code → Object program

위에서 어셈블리 코드를 object code로 변환하였고, 이를 합쳐 만든 object program은 아래와 같다. modification record에 주의하여 살펴본다.

• 재배치 과정에서 외부 symbol들의 절대 주소로 수정하게 됨 → 그래서 local symbol의 상대 주소가 object code에 적혀있다면 해당 CS의 시작 주소를 더해서 절대주소로 통일해줘야함
• 근데 “ENDA-LISTA”같은 식이면 시작주소 각각 더해줘봤자 다시 빠져서 의미가 없는 계산이 되므로 굳이 modification record에 적지 않음 (빨간 글씨!)
  
  

3. Relocation

Modification record에 따라 address field를 수정하여 재배치해주는 과정은 아래와 같다.

ex) PROGA의 REF4

4. Load Memory

Modification record까지 적용된 후, 이것들이 메모리에 올라갔을 때의 모습은 아래와 같다.

• REF4~8은 3개의 CS에서 동일한 값을 가짐
• 하지만, REF1~3처럼 instruction의 operand에 외부참조가 있는 경우에는 CS들이 어디에 로드되는지에 따라 다른 값이 나타남 ?정확히 이해 안됨..상대주소라서?

🔸Algorithm & Data structures for Linking Loader

Linking loader는 Modification Record들 사용하여 linking과 relocation까지 동시에 해결하기 때문에 더 복잡한 알고리즘을 가진다.

• Absolute loader와 다르게 input에 대해 2pass를 이용
  • input: 여러 CS 집합

Pass1: 모든 external symbol에 주소 할당

• PROGADDR를 CSADDR에 넣어 각 CS(모듈)의 위치를 결정
  • PROGADDR: 링크된 프로그램이 메모리에 로드될 때의 시작주소
    • OS가 메모리에서 어디가 비어있는지 확인하고 알려줌
  • CSADDR: loader에 의해 스캔된 현재 각 CS에 할당된 시작 주소
• external symbol table(ESTAB) 생성
  • CS 시작 주소, symbol 이름, symbol의 절대 주소 저장

Pass2: 실제 loading, relocation, linking 수행

• Modification record의경우, ESTAB를 이용하여 주소를 찾고 이를 통해 절대 주소 수정
• 로드된 프로그램에 control을 넘김

🔸Dynamic Linking

지금까지 다룬 linking은 일반적으로 static linking이다. 이는 프로그램 실행 전에 모든 object code를 load&linking하여 메모리에 올린다. Dynamic linking은 프로그램 실행 도중에 object code가 필요할 때, 그때 해당 코드를 load&linking하는 것이다. 과정은 아래와 같다 (a-b-c-d-e)

• Dynamic linking에서 object code는 dynamic link library(DLL)에 저장됨

1. user program이 ‘ERRHANDL’ 서브루틴을 사용하고 싶은데, 아직 라이브러리에 있다. 그래서 OS의 Dynamic loader로 점프하여 요청한다.
2. Dynamic loader는 라이브러리에서 해당 서브루틴을 찾아 메모리에 load 해준다.
3. Dynamic loader는 load된 서브루틴으로 점프하여 실행한다.
4. return address에 따라 dynamic loader로 다시 돌아가고 user program으로 다시 돌아간다. (jump back 2번)

• 해당 서브루틴을 다시 호출하는 경우에는 load 과정이 필요 없다.

장점: 시간 및 메모리 공간 절약

• 사용되지 않을 라이브러리를 로드할 필요가 없으므로
• 여러 프로그램이 하나의 서브루틴/라이브러리의 복사본을 공유할 수 있음