資源簡介

The Best R&D Courses
進程的描述與控制
2.1 前趨圖和程序執行
　　在早期未配置OS的系統和單道批處理系統中，程序的執行方式是順序執行，即在內存中僅裝入
一道用戶程序，由它獨占系統中的所有資源，只有在一個用戶程序執行完成后，才允許裝入另一個
程序并執行。可見，這種方式浪費資源、系統運行效率低等缺點
The Best R&D Courses
進程的描述與控制
2.1.1 前趨圖
　　為了能更好地描述程序的順序和并發執行情況，我們先介紹用于描述程序執行先后順序的前趨
圖。所謂前趨圖(Precedence Graph)，是指一個有向無循環圖，可記為DAG(Directed Acyclic
Graph)，它用于描述進程之間執行的先后順序。圖中的每個結點可用來表示一個進程或程序段，乃
至一條語句，結點間的有向邊則表示兩個結點之間存在的偏序(Partial Order)或前趨關系
(Precedence Relation)。
The Best R&D Courses
進程的描述與控制
　　進程(或程序)之間的前趨關系可用“→”來表示，如果進程Pi和Pj存在著前趨關系，可表示為(Pi，
Pj)∈→，也可寫成Pi→Pj，表示在Pj開始執行之前Pi 必須完成。此時稱Pi是Pj的直接前趨，而稱Pj
是Pi的直接后繼。在前趨圖中，把沒有前趨的結點稱為初始結點(Initial Node)，把沒有后繼的結點
稱為終止結點(Final Node)。此外，每個結點還具有一個重量(Weight)，用于表示該結點所含有的程
序量或程序的執行
時間。
The Best R&D Courses
進程的描述與控制
　　在右圖所示的前趨圖中，存在著如下前趨關
系：
　　P1→P2，P1→P3，P1→P4，P2→P5，
P3→P5，P4→P6，P4→P7，P5→P8，P6→P8，
P7→P9，P8→P9
或表示為：
　P={P1, P2, P3, P4, P5, P6, P7, P8, P9}
　 ={(P1, P2), (P1, P3), (P1, P4), (P2, P5),
(P3, P5), (P4, P6), (P4, P7), (P5, P8), (P6,
P8), (P7, P9), (P8, P9)}
The Best R&D Courses
進程的描述與控制
　　應當注意，前趨圖中是不允許有循環的，否則必然會產生不可能實現的前趨關系。如下圖所示
的前趨關系中就存在著循環。它一方面要求在S3開始執行之前，S2必須完成，另一方面又要求在S2
開始執行之前，S3必須完成。顯然，這種關系是不可能實現的。
　　　　　　　　　S2→S3，S3→S2
The Best R&D Courses
進程的描述與控制
2.1.2 程序順序執行
　　1. 程序的順序執行
　　通常，一個應用程序由若干個程序段組成，每一個程序段完成特定的功能，它們在執行時，都
需要按照某種先后次序順序執行，僅當前一程序段執行完后，才運行后一程序段。例如，在進行計
算時，應先運行輸入程序，用于輸入用戶的程序和數據；然后運行計算程序，對所輸入的數據進行
計算；最后才是運行打印程序，打印計算結果。我們用結點(Node)代表各程序段的操作(在前圖中用
圓圈表示)，其中I代表輸入操作，C代表計算操作，P為打印操作，用箭頭指示操作的先后次序。
The Best R&D Courses
進程的描述與控制
　　這樣，上述的三個程序段間就存在著這樣的前趨關系：Ii→Ci→Pi，其執行的順序可用上面的前
趨圖描述。
　　即使是一個程序段，也可能存在著執行順序問題，下面示出了一個包含了三條語句的程序段：
　　S1: a :=x+y；
　　S2: b :=a-5；
　　S3: c :=b+1；
其中，語句S2必須在語句S1后(即a被賦值)才能執行，語句S3也只能在b被賦值后才能執行，因此，
三條語句存在著這樣的前趨關系：S1→S2→S3，應按下面前趨圖所示的順序執行。
The Best R&D Courses
進程的描述與控制
　　2. 程序順序執行時的特征
　　由上所述可以得知，在程序順序執行時，具有這樣三個特征：① 順序性：指處理機嚴格地按照
程序所規定的順序執行，即每一操作必須在下一個操作開始之前結束；② 封閉性：指程序在封閉的
環境下運行，即程序運行時獨占全機資源，資源的狀態(除初始狀態外)只有本程序才能改變它，程序
一旦開始執行，其執行結果不受外界因素影響；③ 可再現性：指只要程序執行時的環境和初始條件
相同，當程序重復執行時，不論它是從頭到尾不停頓地執行，還是“停停走走”地執行，都可獲得
相同的結果。程序順序執行時的這種特性，為程序員檢測和校正程序的錯誤帶來了很大的方便。
The Best R&D Courses
進程的描述與控制
2.1.3　程序并發執行
　　1. 程序的并發執行
　　我們通過一個常見的例子來說明程序的順序執行和并發執行。在圖2-2中的輸入程序、計算程序
和打印程序三者之間，存在著Ii→Ci→Pi這樣的前趨關系，以至對一個作業的輸入、計算和打印三個
程序段必須順序執行。但若是對一批作業進行處理時，每道作業的輸入、計算和打印程序段的執行
情況如下圖（程序并發執行時的前趨圖）所示。
The Best R&D Courses
進程的描述與控制
　　由前圖可以看出，存在前趨關系Ii→Ci，Ii→Ii+1，Ci→Pi，Ci→Ci+1，Pi→Pi+1，而Ii+1和Ci及
Pi-1是重疊的，即在Pi-1和Ci以及Ii+1之間，不存在前趨關系，可以并發執行。
　　對于具有下述四條語句的程序段：
　　S1: a :=x+2
　　S2: b :=y+4
　　S3: c :=a+b
　　S4: d :=c+b
　　右圖所示的前趨關系。可以看出：S3必須在a和b被賦值后方能執行；S4必須在S3之后執行；但
S1和S2則可以并發執行，因為它們彼此互不依賴。
The Best R&D Courses
進程的描述與控制
　　2. 程序并發執行時的特征
　　在引入了程序間的并發執行功能后，雖然提高了系統的吞吐量和資源利用率，但由于它們共享
系統資源，以及它們為完成同一項任務而相互合作，致使在這些并發執行的程序之間必將形成相互
制約的關系，由此會給程序并發執行帶來新的特征。
　　(1) 間斷性。
　　(2) 失去封閉性。
　　(3) 不可再現性。
The Best R&D Courses
進程的描述與控制
2.2 進 程 的 描 述
2.2.1 進程的定義和特征
　　1. 進程的定義
　　在多道程序環境下，程序的執行屬于并發執行，此時它們將失去其封閉性，并具有間斷性，以
及其運行結果不可再現性的特征。由此，決定了通常的程序是不能參與并發執行的，否則，程序的
運行也就失去了意義。為了能使程序并發執行，并且可以對并發執行的程序加以描述和控制，人們
引入了“進程”的概念。
The Best R&D Courses
進程的描述
　　對于進程的定義，從不同的角度可以有不同的定義，其中較典型的定義有：
　　(1) 進程是程序的一次執行。
　　(2) 進程是一個程序及其數據在處理機上順序執行時所發生的活動。
　　(3) 進程是具有獨立功能的程序在一個數據集合上運行的過程，它是系統進行資源分配和調度的
一個獨立單位。
The Best R&D Courses
進程的描述
　　2. 進程的特征
　　進程和程序是兩個截然不同的概念，除了進程具有程序所沒有的PCB結構外，還具有下面一些
特征：
　　(1) 動態性。
　　(2) 并發性。
　　(3) 獨立性。
　　(4) 異步性。
The Best R&D Courses
進程的描述
2.2.2 進程的基本狀態及轉換
　　1. 進程的三種基本狀態
　　由于多個進程在并發執行時共享系統資源，致使它們在運行過程中呈現間斷性的運行規律，所
以進程在其生命周期內可能具有多種狀態。一般而言，每一個進程至少應處于以下三種基本狀態之
一：
　　(1) 就緒(Ready)狀態。
　　(2) 執行(Running)狀態。
　　(3) 阻塞(Block)狀態。
The Best R&D Courses
進程的描述
　　2. 三種基本狀態的轉換
　　進程在運行過程中會經常發生狀態的轉換。例如，處于就緒狀態的進程，在調度程序為之分配
了處理機之后便可執行，相應地，其狀態就由就緒態轉變為執行態；正在執行的進程(當前進程)如
果因分配給它的時間片已完而被剝奪處理機暫停執行時，其狀態便由執行轉為就緒；如果因發生某
事件，致使當前進程的執行受阻(例如進程訪問某臨界資源，而該資源正被其它進程訪問時)，使之
無法繼續執行，則該進程狀態將由執行轉變為阻塞。右圖示出了進程的三種基本狀態，以及各狀態
之間的轉換關系。
The Best R&D Courses
進程的描述
　　3. 創建狀態和終止狀態
　　1) 創建狀態
　　如前所述，進程是由創建而產生。創建一個進程是個很復雜的過程，一般要通過多個步驟才能
完成：如首先由進程申請一個空白PCB，并向PCB中填寫用于控制和管理進程的信息；然后為該進
程分配運行時所必須的資源；最后，把該進程轉入就緒狀態并插入就緒隊列之中。但如果進程所需
的資源尚不能得到滿足，比如系統尚無足夠的內存使進程無法裝入其中，此時創建工作尚未完成，
進程不能被調度運行，于是把此時進程所處的狀態稱為創建狀態。
The Best R&D Courses
進程的描述
　　2) 終止狀態
　　進程的終止也要通過兩個步驟：首先，是等待操作系統進行善后處理，最后將其PCB清零，并
將PCB空間返還系統。當一個進程到達了自然結束點，或是出現了無法克服的錯誤，或是被操作系
統所終結，或是被其他有終止權的進程所終結，它將進入終止狀態。進入終止態的進程以后不能再
執行，但在操作系統中依然保留一個記錄，其中保存狀態碼和一些計時統計數據，供其他進程收集。
一旦其他進程完成了對其信息的提取之后，操作系統將刪除該進程，即將其PCB清零，并將該空白
PCB返還系統。圖2-6示出了增加了創建狀態和終止狀態后進程的五種狀態及轉換關系圖。
The Best R&D Courses
進程的描述
The Best R&D Courses
進程的描述
2.2.3 掛起操作和進程狀態的轉換
　　1. 掛起操作的引入
　　引入掛起操作的原因，是基于系統和用戶的如下需要：
　　(1) 終端用戶的需要。
　　(2) 父進程請求。
　　(3) 負荷調節的需要。
　　(4) 操作系統的需要。
The Best R&D Courses
進程的描述
　　2. 引入掛起原語操作后三個進程狀態的轉換
　　在引入掛起原語Suspend和激活原語Active后，在它們的作用下，進程將可能發生以下幾種狀
態的轉換：
　　(1) 活動就緒→靜止就緒。
　　(2) 活動阻塞→靜止阻塞。
　　(3) 靜止就緒→活動就緒。
　　(4) 靜止阻塞→活動阻塞。
The Best R&D Courses
進程的描述
　　3. 引入掛起操作后五個進程狀態的轉換
　　如右圖示出了增加了創建狀態和終止狀態后具有掛起狀態的進程狀態及轉換圖。
　　如右圖所示，引進創建和終止狀態后，在進程狀態轉換時，與前圖的進程五狀態轉換相比較，
要增加考慮下面的幾種情況：
　　(1) NULL→創建：
　　(2) 創建→活動就緒：
　　(3) 創建→靜止就緒：
　　(4) 執行→終止：
The Best R&D Courses
進程的描述
2.2.4 進程管理中的數據結構
　　1. 操作系統中用于管理控制的數據結構
　 在計算機系統中，對于每個資源和每個進程都設置了一個數據結構，用于表征其實體，我們
稱之為資源信息表或進程信息表，其中包含了資源或進程的標識、描述、狀態等信息以及一批指針。
通過這些指針，可以將同類資源或進程的信息表，或者同一進程所占用的資源信息表分類鏈接成不
同的隊列，便于操作系統進行查找。
The Best R&D Courses
進程的描述
OS管理的這些數據結構一般分為以下四類：內存表、設備表、文件表和用于進程管理的進程表，通
常進程表又被稱為進程控制塊PCB。
The Best R&D Courses
進程的描述
2. 進程控制塊PCB的作用
(1) 作為獨立運行基本單位的標志。
(2) 能實現間斷性運行方式。
(3) 提供進程管理所需要的信息。
(4) 提供進程調度所需要的信息。
(5) 實現與其它進程的同步與通信。
The Best R&D Courses
進程的描述
　　3. 進程控制塊中的信息
　　在進程控制塊中，主要包括下述四個方面的信息。
　　1) 進程標識符
　　進程標識符用于唯一地標識一個進程。一個進程通常有兩種標識符：
　　(1) 外部標識符。
　　(2) 內部標識符。
　　2) 處理機狀態
　　處理機狀態信息也稱為處理機的上下文，主要是由處理機的各種寄存器中的內容組成的。
The Best R&D Courses
進程的描述
　　3) 進程調度信息
　　在OS進行調度時，必須了解進程的狀態及有關進程調度的信息，這些信息包括：① 進程狀態，
指明進程的當前狀態，它是作為進程調度和對換時的依據；② 進程優先級，是用于描述進程使用處
理機的優先級別的一個整數，優先級高的進程應優先獲得處理機；③ 進程調度所需的其它信息，它
們與所采用的進程調度算法有關，比如，進程已等待CPU的時間總和、進程已執行的時間總和等；
④ 事件，是指進程由執行狀態轉變為阻塞狀態所等待發生的事件，即阻塞原因。
The Best R&D Courses
進程的描述
　　4) 進程控制信息
　　是指用于進程控制所必須的信息，它包括：① 程序和數據的地址，進程實體中的程序和數據的
內存或外存地(首)址，以便再調度到該進程執行時，能從PCB中找到其程序和數據；② 進程同步和
通信機制，這是實現進程同步和進程通信時必需的機制，如消息隊列指針、信號量等，它們可能全
部或部分地放在PCB中；③ 資源清單，在該清單中列出了進程在運行期間所需的全部資源(除CPU
以外)，另外還有一張已分配到該進程的資源的清單；④ 鏈接指針，它給出了本進程(PCB)所在隊列
中的下一個進程的PCB的首地址。
The Best R&D Courses
進程的描述
　　4. 進程控制塊的組織方式
　　在一個系統中，通常可擁有數十個、數百個乃至數千個PCB。為了能對它們加以有效的管理，
應該用適當的方式將這些PCB組織起來。目前常用的組織方式有以下三種。
(1) 線性方式，即將系統中所有的PCB都組織在一張線性表中，將該表的首址存放在內存的一個專用
區域中。該方式實現簡單、開銷小，但每次查找時都需要掃描整張表，因此適合進程數目不多的系
統。下圖示出了線性表的PCB組織方式。
The Best R&D Courses
進程的描述
　　(2) 鏈接方式，即把具有相同狀態進程的PCB分別通過PCB中的鏈接字鏈接成一個隊列。這樣，
可以形成就緒隊列、若干個阻塞隊列和空白隊列等。對就緒隊列而言，往往按進程的優先級將PCB
從高到低進行排列，將優先級高的進程PCB排在隊列的前面。同樣，也可把處于阻塞狀態進程的
PCB根據其阻塞原因的不同，排成多個阻塞隊列，如等待I/O操作完成的隊列和等待分配內存的隊列
等。圖2-11示出了一種鏈接隊列的組織方式。
The Best R&D Courses
進程的描述
　　(3) 索引方式，即系統根據所有進程狀態的不同，建立幾張索引表，例如，就緒索引表、阻塞索
引表等，并把各索引表在內存的首地址記錄在內存的一些專用單元中。在每個索引表的表目中，記
錄具有相應狀態的某個PCB在PCB表中的地址。下圖示出了索引方式的PCB組織。
The Best R&D Courses
進程控制
　　　　　2.3 進 程 控 制
　　進程控制是進程管理中最基本的功能，主要包括創建新進程、終止已完成的進程、將因發生異
常情況而無法繼續運行的進程置于阻塞狀態、負責進程運行中的狀態轉換等功能。如當一個正在執
行的進程因等待某事件而暫時不能繼續執行時，將其轉變為阻塞狀態，而在該進程所期待的事件出
現后，又將該進程轉換為就緒狀態等。進程控制一般是由OS的內核中的原語來實現的。
The Best R&D Courses
進程控制
2.3.1 操作系統內核
　　1. 支撐功能
　　(1) 中斷處理。
　　(2) 時鐘管理。
　　(3) 原語操作。
The Best R&D Courses
進程控制
　　2. 資源管理功能
　　(1) 進程管理。
　　(2) 存儲器管理。
　　(3) 設備管理。
The Best R&D Courses
進程控制
2.3.2 進程的創建
　　1. 進程的層次結構
　　在OS中，允許一個進程創建另一個進程，通常把創建進程的進程稱為父進程，而把被創建的進
程稱為子進程。子進程可繼續創建更多的孫進程，由此便形成了一個進程的層次結構。如在UNIX中，
進程與其子孫進程共同組成一個進程家族(組)。
The Best R&D Courses
進程控制
　　2. 進程圖
　　為了形象地描述一個進程的家族關系而引入了進程
圖(Process Graph)。所謂進程圖就是用于描述進程間
關系的一棵有向樹，如右圖所示。
The Best R&D Courses
進程控制
　　3. 引起創建進程的事件
　　為使程序之間能并發運行，應先為它們分別創建進程。導致一個進程去創建另一個進程的典型
事件有四類：
　　(1) 用戶登錄。
　　(2) 作業調度。
　　(3) 提供服務。
　　(4) 應用請求。
The Best R&D Courses
進程控制
　　4. 進程的創建(Creation of Process)
　　在系統中每當出現了創建新進程的請求后，OS便調用進程創建原語Creat按下述步驟創建一個
新進程：
　　(1) 申請空白PCB，為新進程申請獲得唯一的數字標識符，并從PCB集合中索取一個空白PCB。
　　(2) 為新進程分配其運行所需的資源，包括各種物理和邏輯資源，如內存、文件、I/O設備和
CPU時間等。
　　(3) 初始化進程控制塊(PCB)。
　　(4) 如果進程就緒隊列能夠接納新進程，便將新進程插入就緒隊列。
The Best R&D Courses
進程控制
2.3.3 進程的終止
　　1. 引起進程終止(Termination of Process)的事件
　　(1) 正常結束
　　(2) 異常結束
　　(3) 外界干預
The Best R&D Courses
進程控制
　　2. 進程的終止過程
　　如果系統中發生了要求終止進程的某事件，OS便調用進程終止原語，按下述過程去終止指定的
進程：
　　(1) 根據被終止進程的標識符，從PCB集合中檢索出該進程的PCB，從中讀出該進程的狀態；
　　(2) 若被終止進程正處于執行狀態，應立即終止該進程的執行，并置調度標志為真，用于指示該
進程被終止后應重新進行調度；
The Best R&D Courses
進程控制
　　(3) 若該進程還有子孫進程，還應將其所有子孫進程也都予以終止，以防它們成為不可控的進程；
　　(4) 將被終止進程所擁有的全部資源或者歸還給其父進程，或者歸還給系統；
　　(5) 將被終止進程(PCB)從所在隊列(或鏈表)中移出，等待其它程序來搜集信息。
The Best R&D Courses
進程控制
2.3.4 進程的阻塞與喚醒
　　1. 引起進程阻塞和喚醒的事件
　　有下述幾類事件會引起進程阻塞或被喚醒：
　　(1) 向系統請求共享資源失敗。
　　(2) 等待某種操作的完成。
　　(3) 新數據尚未到達。
　　(4) 等待新任務的到達。
The Best R&D Courses
進程控制
　　2. 進程阻塞過程
　　正在執行的進程，如果發生了上述某事件，進程便通過調用阻塞原語block將自己阻塞。可見，
阻塞是進程自身的一種主動行為。進入block過程后，由于該進程還處于執行狀態，所以應先立即停
止執行，把進程控制塊中的現行狀態由“執行”改為阻塞，并將PCB插入阻塞隊列。如果系統中設
置了因不同事件而阻塞的多個阻塞隊列，則應將本進程插入到具有相同事件的阻塞隊列。最后，轉
調度程序進行重新調度，將處理機分配給另一就緒進程，并進行切換，亦即，保留被阻塞進程的處
理機狀態，按新進程的PCB中的處理機狀態設置CPU的環境。
The Best R&D Courses
進程控制
　　3. 進程喚醒過程
　　當被阻塞進程所期待的事件發生時，比如它所啟動的I/O操作已完成，或其所期待的數據已經到
達，則由有關進程(比如提供數據的進程)調用喚醒原語wakeup，將等待該事件的進程喚醒。
wakeup執行的過程是：首先把被阻塞的進程從等待該事件的阻塞隊列中移出，將其PCB中的現行狀
態由阻塞改為就緒，然后再將該PCB插入到就緒隊列中。
The Best R&D Courses
進程同步
　　　　　2.4　進 程 同 步
　　在OS中引入進程后，一方面可以使系統中的多道程序并發執行，這不僅能有效地改善資源利用
率，還可顯著地提高系統的吞吐量，但另一方面卻使系統變得更加復雜。如果不能采取有效的措施，
對多個進程的運行進行妥善的管理，必然會因為這些進程對系統資源的無序爭奪給系統造成混亂。
致使每次處理的結果存在著不確定性，即顯現出其不可再現性。
The Best R&D Courses
進程同步
2.4.1　進程同步的基本概念
　　1. 兩種形式的制約關系
　　1) 間接相互制約關系
　　2) 直接相互制約關系
　　2. 臨界資源(Critical Resouce)
　　在第一章中我們曾經介紹過，許多硬件資源如打印機、 磁帶機等，都屬于臨界資源，諸進程間
應采取互斥方式，實現對這種資源的共享
The Best R&D Courses
進程同步
　　3. 臨界區(critical section)
　　由前所述可知，不論是硬件臨界資源還是軟件臨界資源，多個進程必須互斥地對它進行訪問。
人們把在每個進程中訪問臨界資源的那段代碼稱為臨界區(critical section)。
若能保證諸進程互斥地進入自己的臨界區，便可實現諸進程
while(true){ 對臨界資源的互斥訪問。為此，每個進程在進入臨界區之前，
進入區 應先對欲訪問的臨界資源進行檢查，看它是否正被訪問。如
臨界區 果此刻臨界資源未被訪問，進程便可進入臨界區對該資源進
退出區 行訪問，并設置它正被訪問的標志；如果此刻該臨界資源正被某進程訪問，則本進程不能進入臨界區。因此，必領在臨
剩余區 界區前面增加一段用于進行上達檢查的代碼，把這段代碼稱
} 為進入區(entry secion)。相應地，在臨界區后面也要加上一
段稱為退出區(exit section)的代碼，用于將臨界區正被訪問的
標志恢復為末被訪問的標志。進程中除上述進入區、臨界區
及退出區之外的其它部分的代碼在這里都稱為剩余區。
The Best R&D Courses
進程同步
　　4. 同步機制應遵循的規則
　　為實現進程互斥地進入自己的臨界區，可用軟件方法，更多的是在系統中設置專門的同步機構
來協調各進程間的運行。所有同步機制都應遵循下述四條準則：
　　(1) 空閑讓進。
　　(2) 忙則等待。
　　(3) 有限等待。
　　(4) 讓權等待。
The Best R&D Courses
進程同步
2.4.2 硬件同步機制
　　雖然可以利用軟件方法解決諸進程互斥進入臨界區的問題，但有一定難度，并且存在很大的局
限性，因而現在已很少采用。相應地，目前許多計算機已提供了一些特殊的硬件指令，允許對一個
字中的內容進行檢測和修正，或者是對兩個字的內容進行交換等。可利用這些特殊的指令來解決臨
界區問題。
The Best R&D Courses
進程同步
　　關中斷
　　關中斷是實現互斥的最簡單的方法之一。在進入鎖測試之前關閉中斷，直到完成鎖測試并上鎖
之后才能打開中斷。這樣，進程在臨界區執行期間，計算機系統不響應中斷，從而不會引發調度，
也就不會發生進程或線程切換。由此，保證了對鎖的測試和關鎖操作的連續性和完整性，有效地保
證了互斥。但是，關中斷的方法存在許多缺點：① 濫用關中斷權力可能導致嚴重后果；② 關中斷
時間過長，會影響系統效率，限制了處理器交叉執行程序的能力；③ 關中斷方法也不適用于多CPU
系統，因為在一個處理器上關中斷并不能防止進程在其它處理器上執行相同的臨界段代碼。
The Best R&D Courses
進程同步
2.4.3　信號量機制
　　1. 整型信號量
　　最初由Dijkstra把整型信號量定義為一個用于表示資源數目的整型量S，它與一般整型量不同，除初始
化外，僅能通過兩個標準的原子操作(Atomic Operation) wait(S)和signal(S)來訪問。很長時間以來，這
兩個操作一直被分別稱為P、V操作。
與普通整數變量的區別：對信號量的操作只有三種，即 初始化、P操作、V操作
The Best R&D Courses
進程同步
wait函數將 “檢查” 和 “上鎖” 一氣呵成，
避免了并發、異步導致的問題。但存在存在的
問題：不滿足“讓權等待”原則，會發生“忙
等”。
The Best R&D Courses
進程同步
　　2. 記錄型信號量
　　在整型信號量機制中的wait操作，只要是信號量S≤0，就會不斷地測試。因此，該機制并未遵
循“讓權等待”的準則，而是使進程處于“忙等”的狀態。記錄型信號量機制則是一種不存在“忙
等”現象的進程同步機制。但在采取了“讓權等待”的策略后，又會出現多個進程等待訪問同一臨
界資源的情況。為此，在信號量機制中，除了需要一個用于代表資源數目的整型變量value外，還應
增加一個進程鏈表指針list，用于鏈接上述的所有等待進程。
The Best R&D Courses
進程同步
The Best R&D Courses
進程同步
2.4.4　信號量的應用
　　1. 利用信號量實現進程互斥
　　為使多個進程能互斥地訪問某臨界資源，只需為該資源設置一互斥信號量mutex，并設其初始值
為1，然后將各進程訪問該資源的臨界區CS置于wait(mutex)和signal(mutex)操作之間即可。
The Best R&D Courses
進程同步
　　2. 利用信號量實現前趨關系
　　還可利用信號量來描述程序或語句之間的前趨關系。設有兩個并發執行的進程P1和P2。P1中有
語句S1；P2中有語句S2。我們希望在S1執行后再執行S2。為實現這種前趨關系，只需使進程P1和
P2共享一個公用信號量S，并賦予其初值為0，將signal(S)操作放在語句S1后面，而在S2語句前面
插入wait(S)操作，即
　　在進程P1中，用S1；signal(S)；
　　在進程P2中，用wait(S)；S2；
The Best R&D Courses
進程同步
　　由于S被初始化為0，這樣，若P2先執行必定阻塞，只有在進程P1執行完S1； signal(S)；操作
后使S增為1時，P2進程方能成功執行語句S2。同樣，我們可以利用信號量按照語句間的前趨關系
(見圖2-14)，寫出一個更為復雜的可并發執行的程序。
The Best R&D Courses
進程同步
2.4.5　管程機制
　　1．管程的定義
　　系統中的各種硬件資源和軟件資源均可用數據結構抽象地描述其資
源特性，即用少量信息和對該資源所執行的操作來表征該資源，而忽略
它們的內部結構和實現細節。
　　由上述的定義可知，管程由四部分組成：① 管程的名稱；② 局部
于管程的共享數據結構說明；③ 對該數據結構進行操作的一組過程；④
對局部于管程的共享數據設置初始值的語句。右圖是一個管程的示意圖。
The Best R&D Courses
進程同步
　　2. 條件變量
　　在利用管程實現進程同步時，必須設置同步工具，如兩個同步操作原語wait和signal。當某進程
通過管程請求獲得臨界資源而未能滿足時，管程便調用wait原語使該進程等待，并將其排在等待隊列
上，如圖2-13所示。僅當另一進程訪問完成并釋放該資源之后，管程才又調用signal原語，喚醒等待
隊列中的隊首進程。
The Best R&D Courses
進程同步
　　　 2.5　經典進程的同步問題
　　在多道程序環境下，進程同步問題十分重要，也是相當有趣的問題，因而吸引了不少學者對它
進行研究，由此而產生了一系列經典的進程同步問題，其中較有代表性的是“生產者—消費者”問
題、“讀者—寫者問題”、“哲學家進餐問題”等等。通過對這些問題的研究和學習，可以幫助我
們更好地理解進程同步的概念及實現方法。
The Best R&D Courses
進程同步
2.5.1　生產者-消費者問題
　　1. 利用記錄型信號量解決生產者-消費者問題
　　假定在生產者和消費者之間的公用緩沖池中具有n個緩沖區，這
時可利用互斥信號量mutex實現諸進程對緩沖池的互斥使用；利用信
號量empty和full分別表示緩沖池中空緩沖區和滿緩沖區的數量。又
假定這些生產者和消費者相互等效，只要緩沖池未滿，生產者便可將
消息送入緩沖池；只要緩沖池未空，消費者便可從緩沖池中取走一個
消息。
The Best R&D Courses
進程同步
　　2. 利用AND信號量解決生產者-消費者問題
　　對于生產者-消費者問題，也可利用AND信號量來解決，
即用Swait(empty，mutex)來代替wait(empty)和
wait(mutex)；用Ssignal(mutex，full)來代替signal(mutex)
和signal(full)；用Swait(full，mutex)代替wait(full)和
wait(mutex)，以及用Ssignal(mutex，empty)代替
Signal(mutex)和Signal(empty)。
The Best R&D Courses
進程同步
　　3. 利用管程解決生產
者-消費者問題
　　在利用管程方法來解
決生產者-消費者問題時，
首先便是為它們建立一個
管程，并命名為
procducerconsumer，
或簡稱為PC。其中包括
兩個過程：
　　(1) put(x)過程。
　　(2) get(x)過程。
The Best R&D Courses
進程同步
　　對于條件變量notfull和notempty，分別有兩個過程cwait和csignal對它們進行操作：
　　(1) cwait(condition)過程：當管程被一個進程占用時，其他進程調用該過程時阻塞，并掛在條
件condition的隊列上。
　　(2) csignal(condition)過程：喚醒在cwait執行后阻塞在條件condition隊列上的進程，如果這
樣的進程不止一個，則選擇其中一個實施喚醒操作；如果隊列為空，則無操作而返回。
The Best R&D Courses
進程同步
2.5.2　哲學家進餐問題
　　1. 利用記錄型信號量解決哲學家進餐問題
　　經分析可知，放在桌子上的筷子是臨界資
源，在一段時間內只允許一位哲學家使用。為
了實現對筷子的互斥使用，可以用一個信號量
表示一只筷子，由這五個信號量構成信號量數
組。
The Best R&D Courses
The Best R&D Courses
進程同步
　　2. 利用AND信號量機制解決哲學家
進餐問題
　　在哲學家進餐問題中，要求每個哲學
家先獲得兩個臨界資源(筷子)后方能進餐，
這在本質上就是前面所介紹的AND同步
問題，故用AND信號量機制可獲得最簡
潔的解法。
The Best R&D Courses
進程同步
2.5.3　讀者-寫者問題
　　利用記錄型信號量解決讀者-寫者問題
　　為實現Reader與Writer進程間在讀或寫時的互斥而設置了一個互斥信號量Wmutex。另外，再
設置一個整型變量Readcount表示正在讀的進程數目。由于只要有一個Reader進程在讀，便不允許
Writer進程去寫。因此，僅當Readcount=0，表示尚無Reader進程在讀時，Reader進程才需要執
行Wait(Wmutex)操作。若wait(Wmutex)操作成功，Reader進程便可去讀，相應地，做
Readcount+1操作。
The Best R&D Courses
The Best R&D Courses
進程通信
　　　　2.6 進 程 通 信
　　進程通信是指進程之間的信息交換。由于進程的互斥與同步，需要在進程間交換一定的信息，
故不少學者將它們也歸為進程通信，但只能把它們稱為低級進程通信。我們以信號量機制為例來說
明，它們之所以低級的原因在于：① 效率低，生產者每次只能向緩沖池投放一個產品(消息)，消費
者每次只能從緩沖區中取得一個消息；② 通信對用戶不透明，OS只為進程之間的通信提供了共享
存儲器。
The Best R&D Courses
進程通信
　　在進程之間要傳送大量數據時，應當利用OS提供的高級通信工具，該工具最主要的特點是：
　　(1) 使用方便。OS隱藏了實現進程通信的具體細節，向用戶提供了一組用于實現高級通信的命
令(原語)，用戶可方便地直接利用它實現進程之間的通信。或者說，通信過程對用戶是透明的。這樣
就大大減少了通信程序編制上的復雜性。
　　(2) 高效地傳送大量數據。用戶可直接利用高級通信命令(原語)高效地傳送大量的數據。
The Best R&D Courses
進程通信
2.6.1　進程通信的類型
　　1. 共享存儲器系統(Shared-Memory System)
　　在共享存儲器系統中，相互通信的進程共享某些數據結構或共享存儲區，進程之間能夠通過這
些空間進行通信。據此，又可把它們分成以下兩種類型：
　　(1) 基于共享數據結構的通信方式。
　　(2) 基于共享存儲區的通信方式。
The Best R&D Courses
進程通信
　　2. 管道(pipe)通信系統
　　所謂“管道”，是指用于連接一個讀進程和一個寫進程以實現它們之間通信的一個共享文件，
又名pipe文件。向管道(共享文件)提供輸入的發送進程(即寫進程)以字符流形式將大量的數據送入管
道；而接受管道輸出的接收進程(即讀進程)則從管道中接收(讀)數據。由于發送進程和接收進程是利
用管道進行通信的，故又稱為管道通信。這種方式首創于UNIX系統，由于它能有效地傳送大量數據，
因而又被引入到許多其它操作系統中。
The Best R&D Courses
進程通信
　　為了協調雙方的通信，管道機制必須提供以下三方面的協調能力：① 互斥，即當一個進程正在
對pipe執行讀/寫操作時，其它(另一)進程必須等待。② 同步，指當寫(輸入)進程把一定數量(如4 KB)
的數據寫入pipe，便去睡眠等待，直到讀(輸出)進程取走數據后再把它喚醒。當讀進程讀一空pipe
時，也應睡眠等待，直至寫進程將數據寫入管道后才將之喚醒。③ 確定對方是否存在，只有確定了
對方已存在時才能進行通信。
The Best R&D Courses
進程通信
　　3. 消息傳遞系統(Message passing system)
　　在該機制中，進程不必借助任何共享存儲區或數據結構，而是以格式化的消息 (message)為單
位，將通信的數據封裝在消息中，并利用操作系統提供的一組通信命令(原語)，在進程間進行消息傳
遞，完成進程間的數據交換。
　　基于消息傳遞系統的通信方式屬于高級通信方式，因其實現方式的不同，可進一步分成兩類：
　　(1) 直接通信方式
　　(2) 間接通信方式
The Best R&D Courses
進程通信
　　4. 客戶機-服務器系統(Client-Server system)
　　1) 套接字(Socket)
　　套接字起源于20世紀70年代加州大學伯克利分校版本的UNIX(即BSD Unix)，是UNIX 操作系
統下的網絡通信接口。一開始，套接字被設計用在同一臺主機上多個應用程序之間的通信(即進程間
的通信)，主要是為了解決多對進程同時通信時端口和物理線路的多路復用問題。隨著計算機網絡技
術的發展以及UNIX 操作系統的廣泛使用，套接字已逐漸成為最流行的網絡通信程序接口之一。
The Best R&D Courses
進程通信
　　2) 遠程過程調用和遠程方法調用
　　遠程過程(函數)調用RPC(Remote Procedure Call)，是一個通信協議，用于通過網絡連接的系
統。該協議允許運行于一臺主機(本地)系統上的進程調用另一臺主機(遠程)系統上的進程，而對程序
員表現為常規的過程調用，無需額外地為此編程。如果涉及的軟件采用面向對象編程，那么遠程過
程調用亦可稱做遠程方法調用。
The Best R&D Courses
進程通信
2.6.2　消息傳遞通信的實現方式
　　1. 直接消息傳遞系統
　　在直接消息傳遞系統中采用直接通信方式，即發送進程利用OS所提供的發送命令(原語)，直接
把消息發送給目標進程。
　　1) 直接通信原語
　　(1) 對稱尋址方式。
　　(2) 非對稱尋址方式。
The Best R&D Courses
進程通信
　　2) 消息的格式
　　在消息傳遞系統中所傳遞的消息，必須具有一定的消息格式。在單機系統環境中，由于發送進
程和接收進程處于同一臺機器中，有著相同的環境，所以消息的格式比較簡單，可采用比較短的定
長消息格式，以減少對消息的處理和存儲開銷。該方式可用于辦公自動化系統中，為用戶提供快速
的便箋式通信。但這種方式對于需要發送較長消息的用戶是不方便的。為此，可采用變長的消息格
式，即進程所發送消息的長度是可變的。對于變長消息，系統無論在處理方面還是存儲方面，都可
能會付出更多的開銷，但其優點在于方便了用戶。
The Best R&D Courses
進程通信
　　3) 進程的同步方式
　　在進程之間進行通信時，同樣需要有進程同步機制，以使諸進程間能協調通信。不論是發送進
程還是接收進程，在完成消息的發送或接收后，都存在兩種可能性，即進程或者繼續發送(或接收)或
者阻塞。
　　4) 通信鏈路
　　為使在發送進程和接收進程之間能進行通信，必須在兩者之間建立一條通信鏈路。有兩種方式
建立通信鏈路。第一種方式是：由發送進程在通信之前用顯式的“建立連接”命令(原語)請求系統為
之建立一條通信鏈路，在鏈路使用完后拆除鏈路。
The Best R&D Courses
進程通信
2.6.3　直接消息傳遞系統實例
　　消息緩沖隊列通信機制首先由美國的Hansan提出，并在RC 4000系統上實現，后來被廣泛應用
于本地進程之間的通信中。在這種通信機制中，發送進程利用Send原語將消息直接發送給接收進程；
接收進程則利用Receive原語接收消息。
　
The Best R&D Courses
線程
　　　2.7 線程(Threads)的基本概念
2.7.1 線程的引入
　　如果說，在OS中引入進程的目的是為了使多個程序能并發執行，以提高資源利用率和系統吞吐
量，那么，在操作系統中再引入線程，則是為了減少程序在并發執行時所付出的時空開銷，使OS具
有更好的并發性。
The Best R&D Courses
線程
　　1. 進程的兩個基本屬性
　　首先讓我們來回顧進程的兩個基本屬性：
　　① 進程是一個可擁有資源的獨立單位，一個進程要能獨立運行，它必須擁有一定的資源，包括
用于存放程序正文、數據的磁盤和內存地址空間，以及它在運行時所需要的I/O設備、已打開的文件、
信號量等；
The Best R&D Courses
線程
　　② 進程同時又是一個可獨立調度和分派的基本單位，一個進程要能獨立運行，它還必須是一個
可獨立調度和分派的基本單位。每個進程在系統中有唯一的PCB，系統可根據其PCB感知進程的存
在，也可以根據其PCB中的信息，對進程進行調度，還可將斷點信息保存在其PCB中。反之，再利
用進程PCB中的信息來恢復進程運行的現場。正是由于進程有這兩個基本屬性，才使進程成為一個
能獨立運行的基本單位，從而也就構成了進程并發執行的基礎。
The Best R&D Courses
線程
　　2. 程序并發執行所需付出的時空開銷
　　為使程序能并發執行，系統必須進行以下的一系列操作：
　　(1) 創建進程，系統在創建一個進程時，必須為它分配其所必需的、除處理機以外的所有資源，
如內存空間、I/O設備，以及建立相應的PCB；
　　(2) 撤消進程，系統在撤消進程時，又必須先對其所占有的資源執行回收操作，然后再撤消PCB；
　　(3) 進程切換，對進程進行上下文切換時，需要保留當前進程的CPU環境，設置新選中進程的
CPU環境，因而須花費不少的處理機時間。
The Best R&D Courses
線程
　　3. 線程——作為調度和分派的基本單位
　　如何能使多個程序更好地并發執行，同時又盡量減少系統的開銷，已成為近年來設計操作系統
時所追求的重要目標。有不少研究操作系統的學者們想到，要設法將進程的上述兩個屬性分開，由
OS分開處理，亦即并不把作為調度和分派的基本單位也同時作為擁有資源的單位，以做到“輕裝上
陣”；而對于擁有資源的基本單位，又不對之施以頻繁的切換。正是在這種思想的指導下，形成了
線程的概念。
The Best R&D Courses
線程
2.7.2 線程與進程的比較
　　1. 調度的基本單位
　　2. 并發性
　　3. 擁有資源
　　4. 獨立性
　　5. 系統開銷
　　6. 支持多處理機系統
The Best R&D Courses
線程
2.7.3 線程的狀態和線程控制塊
　　1. 線程運行的三個狀態
　　與傳統的進程一樣，在各線程之間也存在著共享資源和相互合作的制約關系，致使線程在運行
時也具有間斷性。相應地，線程在運行時也具有下述三種基本狀態：
　　(1) 執行狀態，表示線程已獲得處理機而正在運行；
　　(2) 就緒狀態，指線程已具備了各種執行條件，只須再獲得CPU便可立即執行；
　　(3) 阻塞狀態，指線程在執行中因某事件受阻而處于暫停狀態，例如，當一個線程執行從鍵盤讀
入數據的系統調用時，該線程就被阻塞。
The Best R&D Courses
線程
　　2. 線程控制塊TCB
　　如同每個進程有一個進程控制塊一樣，系統也為每個線程配置了一個線程控制塊TCB，將所有
用于控制和管理線程的信息記錄在線程控制塊中。
　　3. 多線程OS中的進程屬性
　　通常在多線程OS中的進程都包含了多個線程，并為它們提供資源。OS支持在一個進程中的多個
線程能并發執行，但此時的進程就不再作為一個執行的實體。多線程OS中的進程有以下屬性：
　　(1) 進程是一個可擁有資源的基本單位。
　　(2) 多個線程可并發執行。
　　(3) 進程已不是可執行的實體。
The Best R&D Courses
線程
　　　　2.8 線 程 的 實 現
2.8.1 線程的實現方式
　　線程已在許多系統中實現，但各系統的實現方式并不完全相同。在有的系統中，特別是一些數
據庫管理系統，如infomix所實現的是用戶級線程； 而另一些系統(如Macintosh和OS/2操作系統)所
實現的是內核支持線程；還有一些系統如Solaris操作系統，則同時實現了這兩種類型的線程。
The Best R&D Courses
線程
　　1. 內核支持線程KST(Kernel Supported Threads)
　　在OS中的所有進程，無論是系統進程還是用戶進程，都是在操作系統內核的支持下運行的，是
與內核緊密相關的。而內核支持線程KST同樣也是在內核的支持下運行的，它們的創建、阻塞、撤
消和切換等，也都是在內核空間實現的。為了對內核線程進行控制和管理，在內核空間也為每一個
內核線程設置了一個線程控制塊，內核根據該控制塊而感知某線程的存在，并對其加以控制。當前
大多數OS都支持內核支持線程。
The Best R&D Courses
線程
　　這種線程實現方式主要有四個主要優點：
　　(1) 在多處理器系統中，內核能夠同時調度同一進程中的多個線程并行執行；
　　(2) 如果進程中的一個線程被阻塞了，內核可以調度該進程中的其它線程占有處理器運行，也可
以運行其它進程中的線程；
　　(3) 內核支持線程具有很小的數據結構和堆棧，線程的切換比較快，切換開銷小；
　　(4) 內核本身也可以采用多線程技術，可以提高系統的執行速度和效率。
The Best R&D Courses
線程
　　2. 用戶級線程ULT(User Level Threads)
　　用戶級線程是在用戶空間中實現的。對線程的創建、 撤消、同步與通信等功能，都無需內核的
支持，即用戶級線程是與內核無關的。在一個系統中的用戶級線程的數目可以達到數百個至數千個。
由于這些線程的任務控制塊都是設置在用戶空間，而線程所執行的操作也無需內核的幫助，因而內
核完全不知道用戶級線程的存在。
The Best R&D Courses
線程
　　使用用戶級線程方式有許多優點：
　　(1) 線程切換不需要轉換到內核空間。
　　(2) 調度算法可以是進程專用的。
　　(3) 用戶級線程的實現與OS平臺無關，因為對于線程管理的代碼是屬于用戶程序的一部分，所
有的應用程序都可以對之進行共享。
The Best R&D Courses
線程
　　而用戶級線程方式的主要缺點則在于：
　　(1) 系統調用的阻塞問題。在基于進程機制的OS中，大多數系統調用將使進程阻塞，因此，當
線程執行一個系統調用時，不僅該線程被阻塞，而且，進程內的所有線程會被阻塞。而在內核支持
線程方式中，則進程中的其它線程仍然可以運行。
　　(2) 在單純的用戶級線程實現方式中，多線程應用不能利用多處理機進行多重處理的優點，內核
每次分配給一個進程的僅有一個CPU，因此，進程中僅有一個線程能執行，在該線程放棄CPU之前，
其它線程只能等待。
The Best R&D Courses
線程
　　3. 組合方式
　　有些OS把用戶級線程和內核支持線程兩種方式進行組合，提供了組合方式ULT/KST 線程。在
組合方式線程系統中，內核支持多個內核支持線程的建立、調度和管理，同時，也允許用戶應用程
序建立、調度和管理用戶級線程。
The Best R&D Courses
線程
The Best R&D Courses
線程
2.8.3 線程的創建和終止
　　1. 線程的創建
　　應用程序在啟動時，通常僅有一個線程在執行，人們把線程稱為“初始化線程”，它的主要功
能是用于創建新線程。在創建新線程時，需要利用一個線程創建函數(或系統調用)，并提供相應的參
數，如指向線程主程序的入口指針、堆棧的大小，以及用于調度的優先級等。在線程的創建函數執
行完后，將返回一個線程標識符供以后使用。
The Best R&D Courses
線程
　　2. 線程的終止
　　當一個線程完成了自己的任務(工作)后，或是線程在運行中出現異常情況而須被強行終止時，由
終止線程通過調用相應的函數(或系統調用)對它執行終止操作。但有些線程(主要是系統線程)，它們
一旦被建立起來之后，便一直運行下去而不被終止。在大多數的OS中，線程被中止后并不立即釋放
它所占有的資源，只有當進程中的其它線程執行了分離函數后，被終止的線程才與資源分離，此時
的資源才能被其它線程利用。
The Best R&D Courses

展開更多......

收起↑