# System Programming ch3

## 執行一個 object program
- relocation
修改 object code 使其可以在不同於原先指定的記憶體載入
- linking
結合兩個或多個分開的 object program 並為他們之間提供資訊
- loading and allocation
分配記憶體空間並將目標程序帶入記憶體以供執行

## Overview
- Loader 的種類
- assemble-and-go loader
- absolute loader（bootstrap loader）
- relocating loader（relative loader）
- direct linking loader
- 設計選項
- linkage editors
- dynamic linking
- bootstrap loaders

## 各個種類的 Loader
### Assemble-and-go Loader
- 特色
- object code 在組譯後存放在記憶體中
- 單 `JUMP` 指令
- 優點
- 簡單的開發環境
- 缺點
- 每當組合語言需要執行時，都需要重新組譯一次
- 所有程式都需要用同個語言撰寫
### Absolute Loader
- 優點
- 簡單有效率
- 缺點
- 需要工程師指定實際位置
- 難以使用副程式庫
:::spoiler Absolute loader 的演算法
:::

#### Simple Bootstrap Loader
- 每當電腦開機或是重新啟動的時候，會執行一種稱為 bootstrap 的特殊 Loader
- 這個 bootstrap 通常 load 第一個要由電腦執行的程式（通常是作業系統）
- e.g. SIC bootstrap loader
- bootstrap 本身從位置 0 開始
- OS 從位置 0x80 開始
- 沒有 Head record 或控制訊息，object code 為記憶體的連續 bytes

### Relocating Loaders
- 動機
- 有效率的共享計算機更大的記憶體及使得多個獨立程序可以一起運行
- 有效的支援使用副程式庫
- 兩種重訂位的方法
- modification record
- relocation bit
- 每條指令都與一個 relocation bit 有關
- 在 Text record 中這些 relocation bit 被聚集到 bit mask 中

#### Modification record
- 用於 complex machine
- 也稱做 RLD（Relocation and Linkage Directory）
- M record
|col|content|
|-:|:-|
|1|M|
|2-7|relocation address|
|8-9|length（half byte）|
|10|flag（+/-）|
|11-17|segement name|
#### Relocation Bits
- 用於 simple machine
- Relocation bits
- 0/1：無須/需要修改
- T record
|col|content|
|-:|:-|
|1|T|
|2-7|starting address|
|8-9|length（byte）（後面指令的長度）|
|10-12|relocation bits|
|13-72|object code|
- 每個 T record 中有 12-bits 的遮罩
- 因為每個 T record 都包含少於 12 個 word
- 每個 word 用一個 relocation bit 標註是否要 modifi
- 沒被用到的 words 被設為 0
- 在重定位時修改的所有值必須與這 3-word 的片段吻合
＊＊any value that is to be modified during relocation must　coincide with one of these 3-byte segments

## Program Linking
- 目標
- 解決來自不同 control section 的 `EXTREF` 和 `EXTDEF` 的問題

### Two pass
- Pass1：assign addresses to all external symbols
- 會產生的變數
- `PROGADDR`(program load address) from OS
- `CSADDR` (control section address)
- `CSLTH` (control section length)
- `ESTAB`
- Pass2：perform the actual loading, relocation and linking
- M record
- 從 `ESTAB` 中尋找 symbol
- E record
- 轉換地址

### 提升效率的方法
用 local 搜尋取代一直在 `ESTAB` 中尋找相同的 symbol
- 為每個外部符號都賦予一個參考編號
- 參考編號在 M record 中被使用
- 01：control section 的名字
- 其他：其他外部符號

## 機器無關 Loader 的功能
### 自動程式庫搜尋
- 許多 loader 都可以自動將子程式庫的東西合併到正在 loading 的程序中
- 標準庫
- 其他庫可以通過 control statement 或給 loader 的參數指定
- 實作
- 持續追蹤在 loader 主要輸入中引用但尚未被定義的外部符號
- 在 Pass1 結束時，`ESTAB` 中還是沒有被定義的符號表示為 unresolved external symbol
- 接著 loader 搜尋指定的 library
- 用這個方法獲得的子程序可能本身包含外部引用
- 所以這個過程要一直重複直到所有 reference 都被 solved
- 允許程序員覆蓋標準子程式庫的東西
- loader 要搜索的庫通常包含彙編後的或編譯後的版本
- 為了效率
- 目錄
- 有些操作系統會將常用庫的目錄永久保存在記憶體中
- 相同的技術也使用於解析數據的外部引用

## Loader 的 option
- 許多 loader 都允許使用者指定修改標準處理的選項
- 許多 loader 都有特殊的命令語言
- 嵌入在主輸入流中
- 在原始碼中

command language 的範例
- `INCLUDE program-name`（library-name）
- 引導 loader 從 library 中讀取指定對象程序並將其視為主 loader 輸入的一部分
- `DELETE csdect-name`
- 只示 loader 從正在加載的程序集中刪除指定的 control section
- `CHANGE name1, name2`
- 將外部符號 `name1` 在程序中出現的任何位置都更改為 `name2`

INCLUDE READ(UTLIB)
INCLUDE WRITE(UTLIB)
DELETE RDREC, WRREC
CHANGE RDREC, READ
CHANGE WRREC, WRITE

- `LIBRARY MYLIB`
- 自動包含 library routines 以滿足外部引用
- 在標準 library 前就會搜尋
- `NOCALL STDDEV, PLOT, CORREL`
- 指示 loader 這些外部引用保持 unsolved
- Other

### Design options
- Linkage Editor
- 在 load time 前執行 linking
- Dynamic linking
- linking function 在 execution time 才會執行
- Bootstrap loader
- 用於運行獨立於操作系統或系統 loader 的獨立程序

#### Linkage Editor
- linkage loader
- 所有 linking 和 relocation 的操作
- 自動 library linking
- 將 linked 的程序直接加載到記憶體中執行
- linkage editor
- 產生一個 linked 的程序（通常稱為 load module 或是 an execution image）寫入一個檔案或是 library 以供後續執行
- 之後接上一個簡單的 relocating loader 可以將 linked 的程式載入到記憶體中
- 這邊 loading 只需要 one pass，無須外部符號表
- 外部參考的解析跟 library 的搜尋只會執行一次
- 在 linked version 的程式中
- 所有外部引用都為 solved，並透過 M record 或 bit mask 重定位
- 外部參考通常保留在 linked program
- 允許之後重新 link 程序以替換 control section，修改外部引用等

#### Dynamic Linking
- 將 linking 部分延後到執行時間在 link
- 子程序在第一次被使用的時候被加載到程式的其餘部分
- 允許多個正在執行的程序共享一個子程序或 library 的副本
- dl 提供只有在需要時才載入東西的能力
- 
- 必須透過作業系統的服務呼叫
1. OS 看內部的表確定該 routine 是否已被加載過
2. routine 從 library 中被加載
3. 控制從 OS 轉到被呼叫的 subroutine
4. subroutine 完成
5. 呼叫早在記憶體中的 subroutine
- 名稱與實際位置的綁定推延到執行時間才進行

#### Bootstrap Loaders
- 如果電腦為空的且閒置，則無需 relocation

<!-- This is the end of the note. -->