第 3 章載入器和連結器 基本的載入器功能 機器相關的載入器功能 機器無關的載入器功能 載入器設計選項
執行一個目的程式, 所需採取的相關步驟 : 載入 (Loading) : 配置記憶體位置, 將目的程式載入記憶體中, 以便執行 重定位 (Relocation) : 調整目的程式中在載入記憶體時需要修改的位址 連結 (Linking) : 合併兩個以上的的目的程式, 並且提供其間相互參考的資訊 載入程式 (Loader) : 載入欲執行的程式 重定位 連結 連結編修程式 (linkage editor)
3.1 基本載入程式功能 將一個目的程式載入至記憶體中, 並且開始執行 內容 3.1.1 討論 絕對載入器 (absolute loader) 3.1.2 介紹用於 SIC/XE 的簡易 絕對載入器 的範例
3.1 基本載入程式功能 3.1.1 絕對載入器的設計 不需要執行連結和重定址的功能 首先測試表頭記錄, 來驗證是否載入正確的程式 ( 並且有足夠的記憶體 ) 當讀取每一筆 文字記錄 (Text record) 時, 會將該記錄中的目的碼移到所指定的記憶體位址上 當讀取到 結束記錄 (End record) 時, 載入器將會跳到所示之位址, 並且開始執行所載入的程式
圖 3.1(a) 絕對程式的載入 : 目的程式
圖 3.2 絕對載入器演算法 Begin read Header record verify program name and length read first Text record while record type is not E do begin {if object code is in character form, convert into internal representation} move object code to specified location in memory read next object program record end Jump to address specified in End record end
3.1 基本載入程式功能 3.1.2 簡單的啟動載入器 啟動載入器 會載入電腦首先必須執行的程式, 通常就是作業系統 圖 3.3 展示 啟動載入器 的原始碼 開機的起始運作位址是在機器之記憶體的位址 0 處, 而作業系統的載入位址是始於位址 80 處 啟動程式 (bootstrap) 的主要迴圈會將下一個載入位址存放在 X 暫存器中 GETC 則是從 F1 裝置讀入和轉換一對字元
圖 3.1(b) 絕對程式的載入 : 程式載至記憶體中
圖 3.3 SIC/XE 的啟動載入器
BOOT START 0 BOOTSTRAP LOADER FOR SIC.. THIS BOOTSTRAP READS CODE FROM DEVICE F1 AND ENTERS IT INTO. MEMORY STARTING AT ADDRESS 80 (HEX). AFTER ALL OF THE CODE. HAS BEEN ENTERED INTO MEMORY, THE BOOTSTRAP EXECUTES A. JUMP TO ADDRESS 80 TO BEGIN EXECUTION OF THE PROGRAM... REGISTER X = NEXT ADDRESS TO BE LOADED. LDA ZERO CLEAR REGISTER A TO ZERO LDX HEX80 INITIALIZE REGISTER X TO HEX 80LOOP JSUB GETC READ HEX DIGIT MUL K16 SHIFT DIGIT VALUE LEFT 4 BITS STA TEMP SAVE SHIFTED DIGIT VALUE JSUB GETC GET NEXT HEX DIGIT ADD TEMP COMBINE DIGITS TO FORM ONE BYTE STCH 0,X STORE AT ADDRESS IN REGISTER X TIX ZERO ADD 1 TO ADDRESS BEING LOADED J LOOP LOOP UNTIL END OF INPUT
. SUBROUTINE TO READ ONE CHARACTER AND CONVERT IT. FROM ASCII CODE TO.HEX DIGIT VALUE. THE CONVERTED HEX DIGIT. VALUE IS RETURNED IN REGISTER A. WHEN AN END-OF-FILE IS READ,. CONTROL IS TRANSFERRED TO THE STARTING ADDRESS (HEX 80). GETC TD INPUT TEST INPUT DEVICE JEQ GETC LOOP UNTIL READY RD INPUT READ CHARACTER COMP HEX04 IF CHARACTER IS HEX 04 (EOF), JEQ 80 JUMP TO START OF PROGRAM COMP HEX30 COMPARE TO HEX 30 (CHAR '0') JLT GETC SKIP CHARACTERS LESS THAN '0' SUB HEX30 SUBTRACT HEX 30 FROM ASCII CODE COMP K10 IF RESULT < 10, CONVERSION IS JLT RETURN COMPLETE. OTHERWISE, SUBTRACT SUB K7 7 MORE (FOR 'A' THROUGH 'F') RETURN RSUB RETURN TO CALLER
HEX04 BYTE X'000004 HEX30 BYTE X'000030 HEX80 BYTE X'000080 ZERO WORD 0 K7 WORD 7 K10 WORD 10 K16 WORD 16 INPUT BYTE X'F1 TEMP RESW 1 END BOOT
3.2 與機器相關之載入器特色 3.2.1 將討論不同的實作技術和使用的情境 3.2.2 是從載入器的觀點, 來觀察 程式連結 3.2.3 將討論一個典型連結載入器 ( 和重定址 ) 的資料結構
可以為程式重新定址的載入器, 稱之為 重定址載入器 (relocating loader) 或 相對載入器 (relative loader) 動機 3.2 與機器相關之載入器特色 3.2.1 重定址 當有數個程式 ( 個別獨立 ) 希望同時執行時, 可以有效率的分享機器上較大的記憶體 有效的支援副程式函式庫 (subroutine libraries) 的使用 兩種重定位 (relocation) 的方法 修改紀錄 (modification record) (Fig. 3.4, 3.5) 重定位位元 (relocation bit) (Fig. 3.6, 3.7)
3.2 與機器相關之載入器特色 3.2.1 重定址 (modification record) 對於架構複雜的機器 使用修正記錄來描述當程式進行重定址時, 其目的碼所需修改的部份 在組譯後的程式中, 只有第 15 35 和 65 行的延伸格式指令包含實際位址
圖 3.4 SIC/XE 程式範例
圖 3.4 SIC/XE 程式範例
圖 3.5 使用修正記錄完成重定位之目的程式
3.2.1 重定址 (modification record) 應用於簡單架構的機器 主要採直接定址且具固定指令格式 重定位位元 (Relocation bit) 位元遮罩 (bit mask)- 0: no modification is necessary 1: modification is needed 重定址位元匯集起來形成的位元遮罩, 是跟隨在文字記錄裡的長度指示之後 沒有使用到的字組之位元設定為 0 有些電腦提供硬體重定址 (hardware relocation) 的功能, 以減輕載入器在執行重定址上的一些工作負擔 組譯時設定為相對使用者記憶體位址, 執行時才轉換成實際位址
圖 3.6 標準 SIC 機器之可重定位程式
圖 3.6 標準 SIC 機器之可重定位程式
圖 3.6 標準 SIC 機器之可重定位程式
圖 3.7 使用位元罩遮的重定位目的程式 此遮罩位元以 word 為單位, 因此需換行寫輸出碼
3.1 基本載入程式功能 解決在不同控制區塊中和 EXTREF 與 EXTDEF 有關的問題 (Fig 3.8), 相同運算式相異處理方式 在 PROGA 中 REF1 僅僅是引用到程式中的一個標籤 (label) 以程式計數器相對定址處理無需重定址或連結 REF2 引用外部標記及一常數 常數直接放入運算元 3.2.2 程式連結 外部標記以修正記錄指引載入器連結程式時將 LISTB 的值加到此項位址欄位 REF3 是一個立即運算元 (immediate operand), 其值是 ENDA 和 LISTA 的差
在 PROGB 中 REF1 引用一個外部標記 (label) 以修正記錄指引載入器連結程式時將 LISTA 的值加到此項位址欄位 REF2 引用程式中的一個標籤及一常數 標記以程式計數器相對定址處理無需重定址或連結 REF3 是一個立即運算元 (immediate operand), 其值是外部標記 ENDA 和 LISTA 的差 以修正記錄指引載入器連結程式時將 ENDA 與 LISTA 的值加入與減掉到此項位址欄位 在 PROGC 中 依上例處理
圖 3.8 連結和重定位的簡單程式範例
圖 3.8 連結和重定位的簡單程式範例
圖 3.8 連結和重定位的簡單程式範例
圖 3.9 對應於圖 3.8 的目的程式
圖 3.9 對應於圖 3.8 的目的程式
圖 3.9 對應於圖 3.8 的目的程式
圖 3.10(a) 連結與載入圖 3.8 中的程式
圖 3.10(a) PROGA REF4 重新定位流程
3.2 與機器相關之載入器特色 3.2.3 連結載入器的演算法和資料結構 採用修正記錄 (Modification records) 來處理重定址, 以使連結和重定址的功能皆是運用相同的機制 連結載入器 (linking loader) 的主要資料結構是一個 ESTAB 的外部符號表, 用於儲存控制段之外部符號的名稱和位址
Two Passes Logic 第一回合 : 指定位址給所有的外部符號 (external symbols) 第二回合 : 執行實際的 loading, relocation, and linking ESTAB (external symbol table) 控制區段符號名稱位址長度 PROGA LISTA ENDA 4000 4040 4054 0063 PROGB LISTB ENDB 4063 40C3 40D3 007F PROGC LISTC ENDC 40E2 4112 4124 0051
圖 3.11(a) 連結與載入程式第一回合 Control section name and address EXTDEF Symbol and its address
圖 3.11(b) 第二回合連結與載入之演算法
圖 3.12 對應於圖 3.8 的目的程式, 引用編號來修改程式 引用編號避免重複搜尋外部符號
圖 3.12 對應於圖 3.8 的目的程式, 引用編號來修改程式
圖 3.12 對應於圖 3.8 的目的程式, 引用編號來修改程式
圖 3.12 對應於圖 3.8 的目的程式, 引用編號來修改程式
3.3 與機器無關之載入器特色 3.3.1 討論外部引用之 自動化函式庫 (automatic library) 的搜尋程序 3.3.2 展示一些載入和連結時的共同選項
3.3 與機器無關之載入器特色 3.3.1 自動函式庫搜尋 只需宣告副程式許多連結載入器可以自動地將 副程式函式庫 (subroutine library) 中的程式, 合併到載入的程式當中 支援 自動函式庫搜尋 的連結載入器必須在其輸入檔案中, 追蹤並未定義的外部符號 一個簡單的方式, 是將 引用記錄 (Refer record) 中並未出現於符號表的符號, 登錄到符號表 (ESTAB) 中, 並註記這些是尚未定義的符號 當遇到其定義時, 則在符號表中填入該符號的位址 外部擷取的副程式亦可能有外部引用因此需重複進行函式庫搜尋 ( 或無法繼續進行為止 ) 一般函式庫搜尋相當於在一特殊目錄上進行搜尋, 此目錄提供所有副程式名稱與位址指標
3.4 載入器設計選項 3.4.1 討論 連結編輯器 (linkage editor), 它在許多電腦系統中可以取代或結合 連結載入器 只進行程式連結寫入檔案副程式不立即執行程式, 載入時只需重定位 3.4.2 介紹 動態連結 (dynamic linking), 它是運用於首次呼叫副程式時, 利用作業系統的機制來載入和連結副程式 3.4.3 將討論 開機載入器 (bootstrap loader) 可載入作業系統或與作業系統無關的獨立程式
3.3 與機器無關之載入器特色 在一些系統上, 工作控制語言 (job control language) 的選項是由作業系統來處理 INCLUDE program-name (library-name) 指示載入器從函式庫中讀取所選定的目的程式 DELETE csect-name 可以指示載入器, 由載入的程式中刪除特定名稱的控制區段 CHANGE name 1, name2 可以將目的程式中的外部符號, 由 name1 更改為 name2 LIBRARY MYLIB 3.3.2 載入器選項 通常在 標準系統函式庫 之前, 會進行此類 使用者指定的函式庫 的搜尋
3.4 載入器設計選項 3.4.1 連結編輯器 執行所有的連結和重定址的動作, 包含自動函式庫的搜尋 ( 如有指定 ), 和載入已連結的程式到記憶體中以供執行 如果一個程式需要執行許多次, 而不想每次都重新組譯時, 使用 連結編輯器 可以降低所需進行的工作 解決所有外部引用的問題已供載入器重新定址 外部引用的相關茲燻能需保留在載入器以便可以重新連結 假如事前可以知道程式之載入的實際位址, 連結編輯器 就可以執行所有的重定址動作
連結編輯程式命令 INCLUDE PLANNER(PROGLIB) DELETE PROJECT {DELETE 從現行的 PLANNER} INCLUDE PROJECT(NEWLIB) {INCLUDE 新版本 ) REPLACE PLANNER(PROGLIB)
圖 3.13 處理目的程式 連結載入程式 連結編輯程式
結合適當的副程式併為一套程式 INCLUDE READR(FTNLIB) INCLUDE WRITER(FTNLIB) INCLUDE BLOCK(FTNLIB) INCLUDE DEBLOCK (FTNLIB) INCLUDE ENCODE(FTNLIB) INCLUDE DECODE(FTNLIB)... SAVE FTNIO(SUBLIB)
3.4 載入器設計選項 3.4.2 動態連結 連結載入 (linking loader)- 載入時再孰行連結動作 動態連結 (dynamic linking) 動態載入 (dynamic loading) 或呼叫時載入 (load on call) 延遲連結的功能, 直到執行時間的方法 : 當副程式首次被呼叫時, 才載入並且完成連結 通常用於多個程式共享同一個副程式或函式庫的時候 在物件導向的系統中, 動態連結經常用於引用一些軟體的物件 比如物件與其方法實現決定於城市執行的時間
圖 3.14 動態連結之副程式載入與呼叫 動態載入器從使用者或系統函式庫載入副程式 依所需副程式名稱提供動態載入器
圖 3.14 動態連結之副程式載入與呼叫 控制權游動太載入器轉移至副程式 副程式執行完後歸還控制權給載入器再轉移給使用者程式 副程式執行完若需再次執行可以直接執行不必重複載入程式
3.4 載入器設計選項 3.4.3 啟動載入器 當第一次載入程式時, 可以明確指定絕對位址 通常這個程式是作業系統, 它將佔用記憶體中的特定位址 絕對載入器 一般是永遠常駐在唯讀記憶體裡 (ROM) 中 利用一個內建的硬體機制 ( 或一個非常短的 ROM 程式 ), 讀取一些設備上固定長度的記錄, 將其置於記憶體的固定位置 在讀取完成後, 控制權轉移至儲存此記錄的記憶體位址, 此記錄具有將絕對程式載入的機器指令 第一筆或前幾筆紀錄通常稱為啟動載入器 (bootstrap loader)