第3章 載入器和連結器.

Presentation on theme: "第3章 載入器和連結器."— Presentation transcript:

1 第3章 載入器和連結器

2 三項處理程序 載入（loading）：將目的程式置入記憶體中以便執行。
重定址（relocation）：調整目的程式，以便在不同的位址上，重新載入目的程式（參見第2.2.2節）。 連結（linking）：將兩個或多個目的程式合併在一起，並且提供目的程式之間相互參考的資訊（參見第2.3.5節）。

3 3.1 載入器的基本功能 3.1.1節討論「絕對載入器」（absolute loader）
3.1.2節介紹用於SIC/XE的簡易「絕對載入器」的範例

4 3.1.1 絕對載入器的設計 不需要執行連結和重定址的功能 首先測試表頭記錄，來驗證是否載入正確的程式（並且有足夠的記憶體）
當讀取每一筆「文字記錄」（Text record）時，會將該記錄中的目的碼移到所指定的記憶體位址上 當讀取到「結束記錄」（End record）時，載入器將會跳到所示之位址，並且開始執行所載入的程式。

5 圖3.1　絕對程式的載入: 目的程式

6 圖3.1　絕對程式的載入: 載入記憶體中的程式

7 圖3.2　絕對載入器的演算法

8 3.1.2 簡單的啟動載入器 「啟動載入器」會載入電腦首先必須執行的程式，通常就是作業系統
圖3.3展示「啟動載入器」的原始碼。開機的起始運作位址是在機器之記憶體的位址0處，而作業系統的載入位址是始於位址80處。 「啟動程式」（bootstrap）的主要迴圈會將下一個載入位址存放在X暫存器中 GETC則是從F1裝置讀入和轉換一對字元

9 圖3.3 SIC/XE的啟動載入器

10 3.2 與機器相關之載入器的特性 3.2.1節將討論不同的實作技術和使用的情境 3.2.2節是從載入器的觀點，來觀察「程式連結」
3.2.3節將討論一個典型連結載入器（和重定址）的資料結構

11 3.2.1 重定址 可以為程式重新定址的載入器，稱之為「重定址載入器」或「相對載入器」
使用修正記錄來描述當程式進行重定址時，其目的碼所需修改的部份 在組譯後的程式中，只有第15、35和65行的延伸格式指令包含實際位址。

12 圖3.4　SIC/XE程式的範例

13 圖3.5　具修改記錄而能重定址的目的程式

14 「位元遮罩」（bit mask） 重定址位元匯集起來形成的「位元遮罩」（bit mask），是跟隨在文字記錄裡的「長度指示」（length indicator）之後。 有些電腦提供「硬體重定址」（hardware relocation）的功能，以減輕載入器在執行重定址上的一些工作負擔。

15 圖3.6　標準SIC機器上的可重定址程式

16 圖3.7　依位元遮罩之可重定址的目的程式

17 3.2.2 程式連結 程式之間外部引用（external reference） 重定址與連結之間的關係
在第一個程式（PROGA）中，REF1僅僅是引用到程式中的一個標籤（label）。 REF2引用標記的處理方式也是類似。 REF3是一個立即運算元（immediate operand），其值是ENDA和LISTA的差

18 圖3.8　連結和重定址的簡單程式範例

19 圖3.8　連結和重定址的簡單程式範例

20 圖3.8　連結和重定址的簡單程式範例

21 圖3.9　對應於圖3.8的目的程式

22 圖3.9　對應於圖3.8的目的程式

23 圖3.9　對應於圖3.8的目的程式

24 圖3.10(a)　連結和載入圖3.8中的程式

25 圖3.10(b) PROGA中REF4的重定址和連結運作

26 3.2.3 連結載入器的演算法和資料結構 採用修正記錄（Modification records）來處理重定址，以使連結和重定址的功能皆是運用相同的機制。 連結載入器的主要資料結構是一個ESTAB的外部符號表，用於儲存控制段之外部符號的名稱和位址。

27 載入對應圖 控制區段 符號名稱 位址 長度 PROGA LISTA ENDA 4000 4040 4054 0063 PROGB LISTB
ENDB 4063 40C3 40D3 007F PROGC LISTC ENDC 40E2 4112 4124 0051

28 圖3.11(a)　第一階段連結載入器的演算法

29 圖3.11(b)　第二階段連結載入器的演算法

30 圖3.12 以圖3.8採用「引用編號」以修正程式碼的對應目的程式
圖3.12　以圖3.8採用「引用編號」以修正程式碼的對應目的程式

31 圖3.12 以圖3.8採用「引用編號」以修正程式碼的對應目的程式
圖3.12　以圖3.8採用「引用編號」以修正程式碼的對應目的程式

32 圖3.12 以圖3.8採用「引用編號」以修正程式碼的對應目的程式
圖3.12　以圖3.8採用「引用編號」以修正程式碼的對應目的程式

33 3.3 與機器無關的載入器特性 3.3.1節將討論外部引用之「自動化函式庫」（automatic library）的搜尋程序
3.3.2節展示一些載入和連結時的共同選項

34 3.3.1 自動函式庫搜尋 許多連結載入器可以自動地將「副程式函式庫」（subroutine library）中的程式，合併到載入的程式當中。 支援「自動函式庫搜尋」的連結載入器必須在其輸入檔案中，追蹤並未定義的外部符號 一個簡單的方式，是將「引用記錄」（Refer record）中並未出現於符號表的符號，登錄到符號表（ESTAB）中，並註記這些是尚未定義的符號。當遇到其定義時，則在符號表中填入該符號的位址。

35 3.3.2 載入器的選項 在一些系統上，「工作控制語言」（job control language）的選項是由作業系統來處理。
INCLUDE program-name(library-name) 指示載入器從函式庫中讀取所選定的目的程式 DELETE csect-name 可以指示載入器，由載入的程式中刪除特定名稱的控制區段。 CHANGE name 1, name2 可以將目的程式中的外部符號，由name1更改為name2。 LIBRARY MYLIB 通常在「標準系統函式庫」之前，會進行此類「使用者指定的函式庫」的搜尋。

36 3.4 載入器設計的選項 3.4.1節將討論「連結編輯器」，它在許多電腦系統中可以取代或結合「連結載入器」。
3.4.2節介紹「動態連結」，它是運用於首次呼叫副程式時，利用作業系統的機制來載入和連結副程式。 3.4.3節將討論「開機載入器」

37 3.4.1 連結編輯器 執行所有的連結和重定址的動作，包含自動函式庫的搜尋（如有指定），和載入已連結的程式到記憶體中以供執行。
如果一個程式需要執行許多次，而不想每次都重新組譯時，使用「連結編輯器」可以降低所需進行的工作。 假如事前可以知道程式之載入的實際位址，「連結編輯器」就可以執行所有的重定址動作。

38 圖3.13 使用 (a) 連結載入器和 (b) 連結編輯器處理目的程式的程序

39 連結編輯命令 INCLUDE PLANNER(PROGLIB) DELETE PROJECT {DELETE 從現行的 PLANNER}
INCLUDE PROJECT(NEWLIB) {INCLUDE 新版本) REPLACE PLANNER(PROGLIB)

40 結合適當的副程形成一個套裝程式 INCLUDE READR(FTNLIB) INCLUDE WRITER(FTNLIB)
INCLUDE BLOCK(FTNLIB) INCLUDE DEBLOCK (FTNLIB) INCLUDE ENCODE(FTNLIB) INCLUDE DECODE(FTNLIB) . SAVE FTNIO(SUBLIB)

41 3.4.2 動態連結 動態連結（dynamic linking）、動態載入（dynamic loading）或呼叫時載入（load on call） 延遲連結的功能，直到執行時間的方法：當副程式首次被呼叫時，才載入並且完成連結。 通常用於多個程式共享同一個副程式或函式庫的時候 在物件導向的系統中，動態連結經常用於引用一些軟體的物件。

42 圖3.14　使用動態連結來載入和呼叫副程式

43 圖3.14　使用動態連結來載入和呼叫副程式

44 3.4.3 啟動載入器 當第一次載入程式時，可以明確指定絕對位址。通常這個程式是作業系統，它將佔用記憶體中的特定位址。
絕對載入器」是永遠常駐在唯讀記憶體裡（ROM）中。 利用一個內建的硬體機制（或一個非常短的ROM程式），讀取一些設備上固定長度的記錄，將其置於記憶體的固定位置。

45   3.5 實作範例 3.5.1 MS-DOS連結器 3.5.2 SunOS連結器 3.5.3 Cray MPP連結器

46 3.5.1 MS-DOS連結器 大部分MS-DOS的編譯器（compiler）和組譯器（包含MASM）可以產生目的模組，它是不可執行的機器語言程式。 MS-DOS LINK是一種「連結編輯器」，它可以結合一個或多個目的模組，以產生一個的完整可執行程式。

47 圖3.15　MS-DOS目的模組

48 記錄型態 THEADR記錄可以指出目的模組的名稱 PUBDFF記錄包含了一些定義於此目的模組之外部符號的列表
SEGDEF記錄描述目的模組中的一些區段 LEDATA記錄包含了由原始程式所轉譯的指令和資料 FIXUPP記錄是用於解決外部引用

49 二階段LINK 第一階段所建構的符號表中，每個區段（使用LNAMES、SEGDEF和GRPDEF記錄）和每個外部符號（使用EXTDKF和PUBDEF記錄）都會有一個對應的位址。 在第二階段中，LINK會由目的模組中取出已轉譯的指令和資料，並在記憶體中建構一個可執行程式的影像檔。

50 3.5.2 SunOS連結器 二種不同的連結器 「連結編譯器」（link-editor）
編譯一個程式，將一個或多個組譯器和編譯器所產生的目的模組，組合形成一個輸出模組 「執行時間連結器」（run-time linker） 可以在執行時，繫結動態的可執行程式，並且分享物件。

51 「連結編譯器」輸出模組 重定址的目的模組（relocatable object module）：可供進ㄧ步的連結編譯處理。
靜態可執行的模組（static executable module）：所有符號引用皆已繫結（bound），並準備執行。 動態可執行的模組（dynamic executable module）：在執行時有些符號引用尚需要繫結。 分享物件（shared object）：在執行時可以提供服務，以繫結一個或多個動態可執行的模組。

52 執行時連結器 連結器可以決定動態可執行程式所需的分享物件，並且確保這些物件都會引入進來。此外也檢查那些分享物件，以偵測和處理其它分享物件上之任何額外的相依關係 程序呼叫（procedure call）的繫結通常是延遲到程式執行之時。在連結編輯期間，全域程序的呼叫將轉換成程序連結表的引用。 「懶惰的繫結」（lazy/binding）

53 3.5.3 Cray MPP連結器 一個T3E系統中包含了大量的處理元件（PEs）。
每一個PE皆有其所屬的本地記憶體。此外，任何一個PE都可以存取所有其他PEs的記憶體（有時候稱之為遠端記憶體）。 一個T3E系統通常會為ㄧ個應用程式分配數個PEs ，稱之為一個分割（partition）

54 圖3.16　在PEs間共享資料的範例 假設程式中包含一個迴圈，以處理陣列中的256個元素。PE0可以執行此迴圈的中註標（subscript）為1到16的部份，PE1可以執行迴圈中註標為17到32的部份，以此類推。

55 T3E系統 當載入一個程式後，每個PE會取得一份程式的可執行碼、私有資料和部分的分享資料。
MPP連結器會根據目的程式，將程式碼或資料區塊組織成為一些列表。 每個列表中的區塊都會集合在一起，並且分配給每個區塊一個位址，以及執行重定址和連結的動作。

56 圖3.17　載入T3E程式到多個PE上