複旦大學961-計算機系統基礎-第四章-連結、程序及并發程式設計

961全部内容連結

文章目錄

• 編譯系統的過程
• 靜态連結
• 目标檔案
• 符号和符号表
• 重定位和加載
• 動态連結庫
• 異常和程序
• • 異常的相關概念
  • 程序的相關概念
• 程序控制和信号
• • • • • 1.程序的建立
        • 2. 程序的終止
  • 信号
• 程序間的通信
• 程序間信号量的控制
• 信号量
• 各種并發程式設計模式
• 共享變量和線程同步
• 其他并行（發）問題

編譯系統的過程

《CSAPP》P3

一個C程式編譯分為以下幾個階段：

1. 預處理階段：預處理器（cpp，不是c++的那個cpp）根據以字元#開頭的指令，修改原始的C程式。比如hello.c中的第一行#include <stdio.h> 指令告訴預處理器讀取系統頭檔案stdio.h的内容，并把它直接插入程式文本中。結果就得到了另一個C程式，通常以 .i 作為檔案擴充名
2. 編譯階段：編譯器（ccl）将文本檔案hello.i 翻譯成文本檔案hello.s，它包含了一個彙編語言程式（就是裡面是彙編代碼）。通俗的說就是把C代碼轉成彙編代碼
3. 彙編階段：彙編器（as，編譯彙編的編譯器）将hello.s 檔案編譯成可重定位目标程式，hello.o。 該檔案是二進制檔案。其實到這已經可以執行了，隻不過可能會報錯，因為這裡面調用了printf函數，是以相同目錄下必須要有printf.o檔案才能正常執行。有點類似java的程式，在其目錄下必須有jar包一樣，要不然會報ClassNotFound
4. 連結程式：因為hello代碼調用了printf函數，是以要把printf.o檔案合并到hello.o檔案中，連結器（ld）就負責做這件事，最終會得到一個hello檔案，該檔案是一個可執行檔案。

靜态連結

《CSAPP》 P464

連結（linking） 是将各種代碼和資料片段收集并組合成為一個單一檔案的過程，這個檔案可被加載到記憶體并執行。

靜态連結器（比如Linux LD程式）以一組可重定位目标檔案和指令行參數作為輸入，生成一個完全連結的、可以加載和運作的可執行目标檔案作為輸出。連結器主要完成兩個任務：

1. 符号解析（symbol resolution）：目的是将每個符号引用正好和一個符号定義關聯起來。
2. 重定位（relocation）：編譯器生成的目标檔案的位址都是從0開始的。要把他們連結起來，總要有個先後順序，要不然到運作的時候，通路0位址誰知道是哪個目标檔案的0位址。連結器通過把每個符号定義與一個記憶體位置關聯起來，進而重定位這些節，然後修改所有對這些符号的引用，使得它們執行這個記憶體位置。連結器使用彙編器産生的重定位條目的詳細指令，不加甄别地執行這樣的重定位。

目标檔案

《CSAPP》 466

目标檔案有三種形式：

1. 可重定位目标檔案：包含二進制代碼和資料，其形式可以在編譯時與其他可重定位目标檔案結合起來，建立一個可執行目标檔案。
2. 可執行目标檔案：包含二進制代碼和資料，可以被直接複制到記憶體并執行。
3. 共享目标檔案：一種特殊類型的可重定位目标檔案，可以在加載或運作時被動态地加載進記憶體并連結。

符号和符号表

《CSAPP》P468

每個可重定位目标子產品（就是目标檔案）m都有一個符号表，它包含m定義和應用的符号資訊。在連結器的上下文中，有三種不同的符号：

1. 全局符号：子產品m定義并能被其他子產品引用的全局符号。全局連結器符号對應于非靜态的C函數和全局變量。
2. 外部符号：由其他子產品定義并被子產品m引用的全局符号。這些符号稱為外部符号，對應于在其他子產品中定義的非靜态C函數和全局變量。
3. 局部符号：隻被子產品m定義和引用的局部符号。他們對應帶static屬性的C函數和全局變量。這些符号在子產品m中任何位置都可見，但是不能被其他子產品引用。

符号解析的概念：連結器解析符号引用的方法是将每個引用與它輸入的可重定位目标檔案的符号表中的一個确定的符号定義關聯起來。

連結器連結時，若多個輸入的子產品中，存在重名的全局符号。連結器的做法為：将已經初始化的全局變量定義為強符号，未初始化的全局變量定義為弱符号。然後根據以下規則來選擇：

1. 不允許有多個重名強符号
2. 如果有一個強符号和多個弱符号重名，則選擇強符号
3. 如果有多個弱符号重名，則任意選擇一個弱符号。

重定位和加載

《CSAPP》P478

一旦連結器完成了符号解析這一步，就把代碼中的每個符号引用和正好一個符号定義（即它的一個輸入目标子產品中的一個符号表條目）關聯起來。此時，連結器就知道它的輸入目标子產品中的代碼節和資料節的确切大小。現在就可以開始重定位步驟了，在這個步驟中，将合并輸入子產品，并為每個符号配置設定運作時的位址。

加載可執行目标檔案：

要運作可以執行目标檔案prog，在Linux Shell的指令行中輸入它的名字即可運作：

linux> ./prog
           

因為prog不是一個内置的shell指令，是以shell會認為prog是一個可執行目标檔案，然後會調用加載器（loader） 來運作它。Linux中，是通過調用execve函數來調用加載器的。加載器将可執行目标檔案中的代碼和資料從磁盤複制到記憶體中，然後通過跳轉到程式的第一個指令或入口點來運作該程式。這個将程式複制到記憶體并運作的過程叫做加載。

加載器實際是如何工作的：Linux系統中的每個程式都運作在一個程序上下文中，有自己的虛拟位址空間。當Shell運作一個程式時，父shell程序生成一個子程序，它是父程序的一個複制。子程序通過execve系統調用啟動加載器。加載器删除子程序現有的虛拟記憶體段，并建立一組新的代碼、資料、堆和棧段。新的棧和堆段被初始化為零。通過将虛拟位址空間中的頁映射到可執行檔案的頁大小的片（chunk），新的代碼和資料段被初始化為可執行檔案的内容。最後，加載器跳轉到_start位址，它最終會調用應用程式的main函數。除了一些頭部資訊，在加載過程中沒有任何從磁盤到記憶體的資料複制。直到CPU引用一個被映射的虛拟頁時才會進行複制，此時，作業系統利用他的頁面排程機制自動将頁面從磁盤傳送到記憶體。

動态連結庫

《CSAPP》P485 7.10動态連結共享庫

靜态庫的缺點：

1. 靜态庫需要顯式地将他們的程式與更新了的庫重新連結
2. 幾乎每個C程式都是用标準I/O函數，如printf。若使用靜态庫，則每個程式都要各自單獨加載printf，并為其配置設定記憶體，造成了極大地資源浪費。

共享庫（shared library） 可以解決靜态庫的問題。共享庫是一個目标子產品，在運作或加載時，可以加載到任意的記憶體位址，并和一個在記憶體中的程式連結起來。這個過程稱為動态連結（dynamic linking），該過程由動态連結器（dynamic linker） 完成。 共享庫也稱為共享目标（shared object），在linux系統中，通常以.so字尾，在windows中，以.dll為字尾。

異常和程序

異常的相關概念

《王道2021作業系統》P17 中斷和異常的概念

CPU的狀态分為核心态和使用者态：

• 核心态（核心态）：作業系統核心工作在核心态
• 使用者态：使用者程式工作在使用者态

系統不允許使用者程式實作核心态的功能，而它們又必須使用這些功能。是以，需要在核心态建立一些“門”，以便實作從使用者态進入核心态。在實際作業系統中，CPU運作上層程式時唯一進入這些“門”的途徑就是通過中斷或異常。當發生中斷或異常時，運作使用者态的CPU會立即進入核心态，這是通過硬體實作的。

中斷（Interruption）的定義：中斷也稱為外中斷，指來自CPU執行指令以外的事件的發生，如裝置發出的I/O結束中斷，告訴CPU裝置I/O操作已經完成，可以進行下一步操作了。時鐘中斷，表示一個固定的時間片已到，讓處理機處理計時、啟動定時運作的任務等。

異常（Exception）的定義 異常也稱為内中斷、例外或陷入（trap），指源自CPU執行指令内部的事件，如程式的非法操作碼、位址越界、算術溢出、虛拟系統的缺頁及專門的陷入指令等引起的事件。

《CSAPP》P504

異常的類别：

類别	原因	異步/同步	傳回行為	解釋
中斷（interrupt）	來自I/O裝置的信号	異步	總是傳回到下一條指令
陷阱（trap）	有意的異常	同步	總是傳回到下一條指令	陷阱的用途是在使用者程式和核心之間提供一個像過程一樣的接口，叫做系統調用
故障（fault）	潛在可恢複的錯誤	同步	可能傳回到目前指令	故障由錯誤引起。當故障發生時，處理器将控制轉移給故障處理程式。若能夠修正，則傳回到引起故障的指令，進而重新執行它。若不能修複，則會引發終止
終止（abort）	不可恢複的錯誤	同步	不會傳回	終止時不可恢複的緻命錯誤造成的結果，通常是一些硬體錯誤

程序的相關概念

《CSAPP》P508

程序就是一個執行中程式的執行個體。系統中的每個程式都運作在某個程序的上下文中。上下文是由程式正确運作所需的狀态組成的。這個狀态包括存放在記憶體中的程式的代碼和資料，它的棧、通用目的寄存器的内容、程式計數器、環境變量以及打開檔案描述符的集合。

《王道2021作業系統》 P31

PCB的概念：為了使參與并發執行的程式（含資料）能獨立運作，必須為之配置一個專門的資料結構，稱為程序控制塊（Process Control Block，PCB）。系統利用PCB來描述程序的基本情況和運作狀态，進而控制和管理程序。

程序的七狀态模型：

• 建立态：程序正在被建立
• 就緒态：程序獲得了除CPU外的一切所需資源，一旦得到CPU，便可立即運作。系統中處于就緒狀态的程序有多個，通常将他們排列成一個隊列，稱為就緒隊列。
• 阻塞态：程序正在等待某一事件發生而暫停運作，如等待某資源可用（不包括CPU）或等待IO完成等。此時即使處理機空閑，該程序也不能運作。
• 運作态：程序正在CPU上運作，如果計算機隻有一個CPU，那麼同一時刻，隻能有一個程序處于運作态。
• 挂起就緒：處于就緒狀态的程序，由于記憶體不足，被暫時換出到了外存。
• 挂起阻塞：處于阻塞狀态的程序，由于記憶體不足，被暫時換出到了外存。
• 結束态：程序正在從系統消失，可能是程序正常結束或其他原因中斷退出運作。程序需要結束運作時，系統首先必須置該程序為結束态，然後再進一步處理資源釋放和回收等工作。

程序狀态之間的轉換：

• 建立->就緒：系統為程序申請PCB，記憶體等資源。申請完畢後，就會進入就緒狀态，若記憶體不足，則會進入挂起就緒狀态。
• 挂起就緒-就緒：若記憶體不足，作業系統會暫時把記憶體中不運作的程序從記憶體換出到外存。等到記憶體充足時，再換入到記憶體
• 挂起阻塞-阻塞：與“挂起就緒-就緒”一緻
• 就緒->運作：程序在就緒隊列中排隊，當輪到它時，就會獲得CPU資源，于是程序就從就緒态變為了運作态
• 運作->就緒：處于運作态的程序在時間片用完後，就得讓出CPU，給後面排隊的程序用。若該系統為可搶占系統，則還沒用完時間片的程序，就有可能被後面高優先級的程序搶占CPU。
• 運作->阻塞：若運作的程式等待某一資源發生時（比如你寫了個scanf，等待鍵盤輸入），此時該程序就會從運作态轉為阻塞态，當該事件發生後，再從阻塞态變為就緒态。若此時程序是在外存當中，則會從挂起阻塞态變為挂起就緒态。

程序控制和信号

《王道2021作業系統》P32

程序控制的主要功能是對系統中的所有程序實施有效的管理。一般把程序控制用的程式段稱為原語。原語的特點是執行期間不允許中斷，是一個不可分割的基本機關。

1.程序的建立

允許一個程序（父程序）建立另一個程序（子程序）。子程序可以繼承父程序所擁有的資源。當子程序被撤銷時，應将其從父程序那裡獲得的資源歸還給父程序。此外，撤銷父程序時，必須同時撤銷其所有子程序。

作業系統建立一個程序的過程如下（建立原語）：

1. 為新程序配置設定一個唯一的程序辨別符，并申請一個空白的PCB。若PCB申請失敗，則建立失敗
2. 為程序配置設定資源，如記憶體資源等，若資源不足，則程序暫時處于阻塞态，等待記憶體資源。
3. 初始化PCB
4. 若程序就緒隊列能夠接納新程序，則将新程序插入就緒隊列，等待被排程運作。

2. 程序的終止

引起程序的終止主要有：

1. 正常結束：程序正常運作完畢退出
2. 異常結束：程序報錯，導緻程序終止。如指針越界，算術運算錯，IO故障等
3. 外界幹預：外界請求，讓程序終止運作。如 kill -9 ，父程序終止等。

程序終止的過程（撤銷原語）：

1. 根據被終止程序的辨別符，檢索PCB，從中讀出該程序的狀态
2. 若該程序處于執行狀态，則立即終止該程序的執行，并讓出CPU資源。
3. 若該程序存在子程序，則将其所有子程序終止
4. 将該程序所擁有的全部資源，歸還給其父程序，若沒有父程序，則歸還給作業系統

信号

《CSAPP》P526

信号就是一條小消息，它通知程序系統中發生了一個某種類型的事件。信号提供了一種機制，通知使用者程序發生了這些異常。比如，如果一個程序試圖除以0，那麼核心就給它發送一個SIGFPE信号。

傳送一個信号到目的程序由兩個不同的步驟組成：

1. 發送信号：核心通過更新目的程序上下文中的某個狀态，發送一個信号給目的程序。一般有兩種情況：①核心檢測到了一個系統事件，如 ÷0 錯誤。②一個程序調用了kill函數，顯式的要求核心發送一個信号給目的程序。比如經典的 kill -9 就是給目的程序發送一個信号，讓它強行終止。
2. 接受程序：當目的程序被核心強迫以某種方式對信号的發送做出反應時，它就接受了信号。程序可以忽略這個信号，終止或者執行信号處理程式來捕獲這個信号。

程序間的通信

《王道2021作業系統》 P35

程序通信是指程序之間的資訊交換。主要有三種方式：

1. 共享存儲：在通信的程序之間存在一塊可直接通路的共享空間（如前面提到的記憶體映射技術，mmap）。通過對這片共享空間進行讀寫操作實作程序之間的資訊交換。
2. 消息傳遞：程序間的資料交換以消息（Message）為機關。有兩種通信方式：①直接通信方式，發送程序直接把消息發送給接受程式。②間接通信方式：把消息發送到消息中間件（MQ）上，接受程序從消息中間件取得消息
3. 管道通信：管道指用于連接配接一個讀程序和一個寫程序以實作他們之間的通信的一個共享檔案，又名pipe檔案。寫程序以字元流形式将大量資料寫入管道，然後讀程序從管道讀出資料

程序間信号量的控制

《王道2021作業系統》P80

為了協調程序之間的互相制約關系，引入了程序同步的概念。

包括以下三個概念：

1. 臨界資源：系統中有些資源，可以被共享，但是同一時間隻能有一個程序使用，這種資源稱為臨界資源。如列印機，變量資料等。對臨界資源的通路，必須互斥進行，通路臨界資源的代碼稱為臨界區。
2. 同步：同步也稱為直接制約關系，是指為了完成某種任務而建立的兩個或多個程序。這些程序因為需要在某些位置上協調它們的工作次序而等待、傳遞資訊所産生的制約關系。程序間的直接制約關系源于它們的合作。 如，A程序通過緩沖區向B程序發送資料。若緩沖區為空，則B必須等待A向緩沖區寫入資料。若緩沖區滿，則A必須等待B讀出緩沖區的内容。
3. 互斥：互斥也稱為間接制約關系。當一個程序進入臨界區使用臨界資源時，其他程序若想使用該臨界資源就必須等待。需要遵循以下幾個原則：①空閑讓進：若臨界資源空閑，可以允許一個程序使用。②忙則等待：若臨界資源正在被占用，則其他程序就需要等待。③有限等待：應保證等待的程序能在一定時間内使用到臨界資源。④讓權等待：等待的程序應把CPU讓出來。

信号量

《王道2021作業系統》P84

信号量機制是用來解決互斥和同步問題的。可以把信号量了解為一個變量S，它隻被兩個标準的原語wait(S)和signal(S)通路，也可記為“P操作”和“V操作”。

信号量有以下幾種：

1.整型信号量：信号量是一個整型變量，用于表示該資源剩餘數量。對應的wait和signal代碼為：

wait(S) {
	while(S<=0);  // 如果S<=0，即沒有可用的臨界資源，則不斷卡在while不斷等待
	S=S-1  // 當有鄰接資源時，占用一個臨界資源
}
signal(S) {
	S=S+1  // 使用完臨界資源，釋放臨界資源
}
           

該機制未遵循“讓權等待”原則。等待的程式會在while那裡一直占用CPU

2.記錄型信号量：在整型信号量的基礎上，增加連結清單L，讓所有等待的程序都連結起來。同時使用block和wakeup函數代替while。解決“忙等”現象，代碼如下：

typedef struct{
	int value;
	struct process *L;
} semaphore;

wait(semaphore S){
	S.value--;
	if(S.value<0){
		add this process to S.L;
		block(S.L);
	}
}

signal(semaphore S){
	S.value++;
	if(S.value<=0) {
		remove a process P from S.L;
		wakeup(P);
	}
}
           

3.利用信号量來實作互斥

semaphore S=1; //初始化信号量
P1(){
	...
	P(S);
	程序1的臨界區;
	V(S);
}
P2(){
	...
	P(S);
	程序2的臨界區;
	V(S);
}
           

該代碼利用信号量，保證同一時間隻有一個程序在通路臨界資源。

各種并發程式設計模式

《CSAPP》P682

1. 基于程序的并發程式設計：在父程序中接受用戶端連接配接請求，然後建立一個新的子程序來為每個新用戶端提供服務。這個缺點很明顯，相當于為每個使用者開辟一個子程序，那要是同時有十萬個使用者，那伺服器就炸了
2. I/O多路複用：基本思想為：使用select函數，要求核心挂起程序，隻有在一個或多個I/O事件發生後，才将控制傳回給應用程式。也就是單個線程通過記錄跟蹤每一個Sock(I/O流)的狀态來同時管理多個I/O流。 它的優點為：①它比基于程序的設計給了程式員更多對程式行為的控制。②所有請求都是運作在一個程序上下文中的，是以可以共享該程序的全部位址空間，請求之間共享資料更容易。它的缺點為：編碼複雜
3. 基于線程的并發程式設計：線程（Thread）就是運作在程序上下文中的邏輯流。它是上述兩種方法的混合。程序可以建立多個線程來應對多個請求。線程由核心自動排程。每個線程都有它自己的線程上下文，包括唯一的線程ID、棧、程式計數器等。一個程序裡的所有線程都可以共享其程序的整個虛拟空間。

共享變量和線程同步

《CSAPP》P698

共享變量的概念：若一個變量被多個線程同時引用，則該變量就是共享的。在Java中，多個線程同時去讀寫一個全局變量，那麼這個全局變量就是一個共享變量。

線程同步：若一個共享變量同時被多個線程引用，那麼就可能存在并發問題。即一個線程對變量的修改可能會覆寫另一個線程對該變量的修改。 要解決該問題，可以使用線程同步，即使用信号量（P,V操作），來限制變量同一時間隻能被一個線程通路。在Java中，可以使用sychronized來為共享變量增加同步信号。

其他并行（發）問題

《CSAPP》P716

1. 線程安全：函數有線程安全的和線程不安全的兩種。如在Java中，HashMap是線程不安全的，HashTable是線程安全的。這個主要是函數的實作方式決定的。 若多個線程操作線程安全的對象，那麼這個對象的結果一定是正确的。若多個線程操作同一個線程不安全的對象，那麼最終可能會産生錯誤的結果。
2. 可重入函數：可重入函數是線程安全的函數。若一個函數體中，沒有使用共享變量，那麼它就是可重入函數。可重入函數還分為顯式可重入和隐式可重入。①顯式可重入：fun(int a)，該函數很明顯用的一定是本地變量，那麼這個函數就是顯式可重入的。②隐式可重入：fun(int *p)，因為該函數接收是一個指針類型，是以若調用它的函數傳遞的是一個本地變量，那麼這個函數就是可重入函數，若是傳了一個共享變量，那麼該函數就是線程不安全的，那麼就是一個不可重入函數。是以這種情況的函數稱為隐式可重入。
3. 競争：若一個程式的正确性必須依賴線程之間的嚴格順序執行，那麼這個線程就會發生競争。比如，必須線程A先執行到第5行代碼，線程B才能執行第十行代碼，否則結果就會不正确。 發生競争是因為沒有做到該條準則：多線程的程式必須對任何可行的軌迹都正确工作。
4. 死鎖：死鎖是指一組線程被阻塞了，等待一個永遠也不會為真的條件。一般發生死鎖都是因為代碼寫的有問題。如果每個線程都是以一種順序獲得互斥鎖并以相反順序釋放，那麼這個程式就是無死鎖的。