《Linux操作系統(tǒng)原理與應(yīng)用》課件-第4章

第4章 進(jìn)程管理4.1進(jìn)程4.2進(jìn)程的運(yùn)行模式4.3進(jìn)程的描述與組織4.4進(jìn)程控制4.5進(jìn)程調(diào)度4.6進(jìn)程的互斥與同步4.7進(jìn)程通信4.8線程

4.1 進(jìn)程

進(jìn)程是現(xiàn)代操作系統(tǒng)的核心概念，它用來描述程序的執(zhí)行過程，是實(shí)現(xiàn)多任務(wù)操作系統(tǒng)的基礎(chǔ)。操作系統(tǒng)的其他所有內(nèi)容都是圍繞著進(jìn)程展開的。4.1.1 程序的順序執(zhí)行與并發(fā)執(zhí)行1. 程序的順序執(zhí)行如果程序的各操作步驟之間是依序執(zhí)行的，程序與程序之間是串行執(zhí)行的，這種執(zhí)行程序的方式就稱為順序執(zhí)行。順序執(zhí)行是單道程序系統(tǒng)中的程序的運(yùn)行方式。

程序的順序執(zhí)行具有如下特點(diǎn)：

（1）順序性：CPU嚴(yán)格按照程序規(guī)定的順序執(zhí)行，僅當(dāng)一個(gè)操作結(jié)束后，下一個(gè)操作才能開始執(zhí)行。

（2）封閉性：程序在封閉的環(huán)境中運(yùn)行，獨(dú)占全部系統(tǒng)資源。

（3）可再現(xiàn)性：程序執(zhí)行的結(jié)果與運(yùn)行的時(shí)間和速度無關(guān)，結(jié)果總是可再現(xiàn)的，即無論何時(shí)重復(fù)執(zhí)行該程序都會得到同樣的結(jié)果。

總的說來，這種執(zhí)行程序的方式簡單，且便于調(diào)試。但由于順序程序在運(yùn)行時(shí)獨(dú)占全部系統(tǒng)資源，因而系統(tǒng)資源利用率很低。

1.程序的并發(fā)執(zhí)行

單道程序、封閉式運(yùn)行是早期操作系統(tǒng)的標(biāo)志，而多道程序并發(fā)運(yùn)行是現(xiàn)代操作系統(tǒng)的基本特征。多個(gè)程序同時(shí)在系統(tǒng)中運(yùn)行，使系統(tǒng)資源得到充分利用，系統(tǒng)效率大大提高。

程序的并發(fā)執(zhí)行是指若干個(gè)程序或程序段同時(shí)運(yùn)行，它們的執(zhí)行在時(shí)間上是重疊的。

程序的并發(fā)執(zhí)行有以下特點(diǎn)：

（1）間斷性：并發(fā)程序之間因競爭資源而相互制約，導(dǎo)致程序運(yùn)行過程的間斷。

（2）沒有封閉性：當(dāng)多個(gè)程序共享系統(tǒng)資源時(shí)，一個(gè)程序的運(yùn)行受其他程序的影響，其運(yùn)行過程和結(jié)果不完全由自身決定。

（3）不可再現(xiàn)性：由于沒有了封閉性，并發(fā)程序的執(zhí)行結(jié)果與執(zhí)行的時(shí)機(jī)以及執(zhí)行的速度有關(guān)，結(jié)果往往不可再現(xiàn)。

并發(fā)執(zhí)行程序雖然可以提高系統(tǒng)的資源利用率和系統(tǒng)吞吐量，但程序的行為變得復(fù)雜和不確定。

2.并發(fā)執(zhí)行的潛在問題

程序在并發(fā)執(zhí)行時(shí)會導(dǎo)致執(zhí)行結(jié)果的不可再現(xiàn)性，這是多道程序系統(tǒng)必須解決的問題。下面的例子說明了并發(fā)執(zhí)行過程對運(yùn)行結(jié)果的影響，從中可以了解產(chǎn)生問題的原因。

設(shè)某停車場使用程序控制電子公告牌來顯示空閑車位數(shù)。空閑車位數(shù)用一個(gè)計(jì)數(shù)器C記錄。車輛入庫時(shí)執(zhí)行程序A，車輛出庫時(shí)執(zhí)行程序B，它們都要更新同一個(gè)計(jì)數(shù)器C。程序A和程序B的片段如圖4-1所示。圖4-1兩程序并發(fā)運(yùn)行，訪問計(jì)數(shù)器C

由于車輛出入庫的時(shí)間是隨機(jī)的，因此程序A與程序B的運(yùn)行時(shí)間也就是不確定的。當(dāng)出入庫同時(shí)發(fā)生時(shí)，將使兩程序在系統(tǒng)中并發(fā)運(yùn)行。它們各運(yùn)行一次后C計(jì)數(shù)器的值應(yīng)保持不變。但結(jié)果可能不是如此。圖4-2展示了并發(fā)執(zhí)行可能的結(jié)果。圖4-2并發(fā)程序的執(zhí)行時(shí)序影響執(zhí)行結(jié)果

4.1.2 進(jìn)程的概念

1. 進(jìn)程

進(jìn)程（process）是一個(gè)可并發(fā)執(zhí)行的程序在一個(gè)數(shù)據(jù)集上的一次運(yùn)行。

進(jìn)程與程序的概念既相互關(guān)聯(lián)又相互區(qū)別。程序是進(jìn)程的一個(gè)組成部分，是進(jìn)程的執(zhí)行文本，而進(jìn)程是程序的執(zhí)行過程。兩者的關(guān)系可以比喻為電影與膠片的關(guān)系：膠片是靜態(tài)的，是電影的放映素材；而電影是動態(tài)的，一場電影就是膠片在放映機(jī)上的一次“運(yùn)行”。對進(jìn)程而言，程序是靜態(tài)的指令集合，可以永久存在；而進(jìn)程是個(gè)動態(tài)的過程實(shí)體，動態(tài)地產(chǎn)生、發(fā)展和消失。

此外，進(jìn)程與程序之間也不是一一對應(yīng)的關(guān)系，表現(xiàn)在：

（1）一個(gè)進(jìn)程可以順序執(zhí)行多個(gè)程序，如同一場電影可以連續(xù)播放多部膠片一樣。

（2）一個(gè)程序可以對應(yīng)多個(gè)進(jìn)程，就像一本膠片可以放映多場電影一樣。

2. 進(jìn)程的特性

進(jìn)程與程序的不同主要體現(xiàn)在進(jìn)程有一些程序所沒有的特性。要真正理解進(jìn)程，首先應(yīng)了解它的基本性質(zhì)。進(jìn)程具有以下幾個(gè)基本特性：

（1）動態(tài)性：進(jìn)程由“創(chuàng)建”而產(chǎn)生，由“撤銷”而消亡，因“調(diào)度”而運(yùn)行，因“等待”而停頓。

（2）并發(fā)性：在同一時(shí)間段內(nèi)有多個(gè)進(jìn)程在系統(tǒng)中活動。它們宏觀上是在并發(fā)運(yùn)行，而微觀上是在交替運(yùn)行。

（3）獨(dú)立性：進(jìn)程是可以獨(dú)立運(yùn)行的基本單位，是操作系統(tǒng)分配資源和調(diào)度管理的基本對象。

（4）異步性：每個(gè)進(jìn)程都獨(dú)立地執(zhí)行，各自按照不可預(yù)知的速度向前推進(jìn)。

3. 進(jìn)程的基本狀態(tài)

進(jìn)程有如下3個(gè)基本的狀態(tài)：

（1）就緒態(tài)：進(jìn)程已經(jīng)分配到了除CPU之外的所有資源，這時(shí)的進(jìn)程狀態(tài)稱為就緒狀態(tài)。處于就緒態(tài)的進(jìn)程，一旦獲得CPU便可立即執(zhí)行。

（2）運(yùn)行態(tài)：進(jìn)程已經(jīng)獲得CPU，正在運(yùn)行，這時(shí)的進(jìn)程狀態(tài)稱為運(yùn)行態(tài)。

（3）等待態(tài)：進(jìn)程因某種資源不能滿足，或希望的某事件尚未發(fā)生而暫停執(zhí)行時(shí)，則稱它處于等待態(tài)。

4. 進(jìn)程狀態(tài)的轉(zhuǎn)換

進(jìn)程誕生之初處于就緒狀態(tài)，在其隨后的生存期間內(nèi)不斷地從一個(gè)狀態(tài)轉(zhuǎn)換到另一個(gè)狀態(tài)，最后在運(yùn)行狀態(tài)結(jié)束。圖4-3所示是一個(gè)進(jìn)程的狀態(tài)轉(zhuǎn)換圖。圖4-3進(jìn)程的狀態(tài)轉(zhuǎn)換圖

引起狀態(tài)轉(zhuǎn)換的原因如下：

運(yùn)行態(tài)→等待態(tài)：正在執(zhí)行的進(jìn)程因?yàn)榈却呈录鵁o法執(zhí)行下去，比如，進(jìn)程申請某種資源，而該資源恰好被其他進(jìn)程占用，則該進(jìn)程將交出CPU，進(jìn)入等待狀態(tài)。

等待態(tài)→就緒態(tài)：處于等待狀態(tài)的進(jìn)程，若其所申請的資源得到滿足，則系統(tǒng)將資源分配給它，并將其狀態(tài)變?yōu)榫途w態(tài)。

運(yùn)行態(tài)→就緒態(tài)：正在執(zhí)行的進(jìn)程的時(shí)間片用完了，或者有更高優(yōu)先級的進(jìn)程到來，系統(tǒng)會暫停該進(jìn)程的運(yùn)行，使其進(jìn)入就緒態(tài)，然后調(diào)度其他進(jìn)程運(yùn)行。

就緒態(tài)→運(yùn)行態(tài)：處于就緒狀態(tài)的進(jìn)程，當(dāng)被進(jìn)程調(diào)度程序選中后，即進(jìn)入CPU運(yùn)行。此時(shí)該進(jìn)程的狀態(tài)變?yōu)檫\(yùn)行態(tài)。

4.1.3 進(jìn)程控制塊

進(jìn)程由程序、數(shù)據(jù)和進(jìn)程控制塊三個(gè)基本部分組成。程序是進(jìn)程執(zhí)行的可執(zhí)行代碼，數(shù)據(jù)是進(jìn)程所處理的對象，進(jìn)程控制塊用于記錄有關(guān)進(jìn)程的各種信息。它們存在于內(nèi)存，其內(nèi)容會隨著執(zhí)行過程的進(jìn)展而不斷變化。

進(jìn)程控制塊（ProcessControlBlock，PCB）是為管理進(jìn)程而設(shè)置的一個(gè)數(shù)據(jù)結(jié)構(gòu)，用于記錄進(jìn)程的相關(guān)信息。

PCB記錄了有關(guān)進(jìn)程的所有信息，主要包括以下4方面的內(nèi)容：

1. 進(jìn)程描述信息

進(jìn)程描述信息用于記錄一個(gè)進(jìn)程的標(biāo)識信息和身份特征，如家族關(guān)系和歸屬關(guān)系等。

2. 進(jìn)程控制與調(diào)度信息進(jìn)程的運(yùn)行需要由系統(tǒng)進(jìn)行控制和調(diào)度。

3. 資源信息

進(jìn)程的運(yùn)行需要占用一些系統(tǒng)資源，必要的資源包括進(jìn)程的地址空間、要訪問的文件和設(shè)備以及要處理的信號等。進(jìn)程是系統(tǒng)分配資源的基本單位。

4. 現(xiàn)場信息

進(jìn)程現(xiàn)場也稱為進(jìn)程上下文（processcontext），包括CPU的各個(gè)寄存器的值。

4.1.4 Linux系統(tǒng)中的進(jìn)程

在Linux系統(tǒng)中，進(jìn)程也稱為任務(wù)（task），兩者的概念是一致的。

1. Linux進(jìn)程的狀態(tài)

Linux系統(tǒng)的進(jìn)程有5種基本狀態(tài)，即可執(zhí)行態(tài)、可中斷睡眠態(tài)、不可中斷睡眠態(tài)、暫停態(tài)和僵死態(tài)。狀態(tài)轉(zhuǎn)換圖如圖4-4所示。圖4-4?Linux系統(tǒng)的進(jìn)程狀態(tài)轉(zhuǎn)換圖

Linux進(jìn)程的基本狀態(tài)定義如下：

（1）可執(zhí)行態(tài)（runnable）：可執(zhí)行態(tài)包含了上述狀態(tài)圖中的運(yùn)行和就緒兩種狀態(tài)。

（2）睡眠態(tài)（sleeping）：即等待態(tài)。此時(shí)進(jìn)程正在等待某個(gè)事件或某個(gè)資源。

（3）暫停態(tài)（stopped或traced）：處于暫停態(tài)的進(jìn)程是由運(yùn)行態(tài)轉(zhuǎn)換而來的，等待某種特殊處理。

（4）僵死態(tài)（zombie）：進(jìn)程運(yùn)行結(jié)束或因某些原因被終止時(shí)，它將釋放除PCB外的所有資源。

2. Linux進(jìn)程的狀態(tài)轉(zhuǎn)換過程

Linux進(jìn)程的狀態(tài)轉(zhuǎn)換過程如下：

新創(chuàng)建的進(jìn)程處于可執(zhí)行的就緒態(tài)，等待調(diào)度執(zhí)行。

處于可執(zhí)行態(tài)的進(jìn)程在就緒態(tài)和運(yùn)行態(tài)之間輪回。就緒態(tài)的進(jìn)程一旦被調(diào)度程序選中，就進(jìn)入運(yùn)行狀態(tài)。當(dāng)進(jìn)程的時(shí)間片耗盡或有更高優(yōu)先級的進(jìn)程就緒時(shí)，調(diào)度程序?qū)⑦x擇新的進(jìn)程進(jìn)入CPU運(yùn)行。被換下的進(jìn)程將轉(zhuǎn)入就緒態(tài)，等待下一次的調(diào)度。處于此輪回的進(jìn)程在運(yùn)行與就緒之間不斷地高速切換，可謂瞬息萬變。因此，對觀察者（系統(tǒng)與用戶）來說，將此輪回概括為一個(gè)相對穩(wěn)定的可執(zhí)行態(tài)才有意義。

運(yùn)行態(tài)、睡眠態(tài)和就緒態(tài)形成一個(gè)回路。

運(yùn)行態(tài)、暫停態(tài)和就緒態(tài)也構(gòu)成一個(gè)回路。

處于運(yùn)行態(tài)的進(jìn)程執(zhí)行結(jié)束后，進(jìn)入僵死態(tài)。

3. Linux的進(jìn)程描述符

Linux系統(tǒng)用task_struct結(jié)構(gòu)來記錄進(jìn)程的信息，稱為進(jìn)程描述符，也就是進(jìn)程控制塊PCB。task_struct中的字段很多，主要包括以下內(nèi)容：

進(jìn)程標(biāo)識號（pid）：標(biāo)識該進(jìn)程的一個(gè)整數(shù)。

認(rèn)證信息（cred）：包含進(jìn)程的屬主和屬組的標(biāo)識號uid、gid。

家族關(guān)系（parent、children、sibling）：關(guān)聯(lián)父進(jìn)程、子進(jìn)程及兄弟進(jìn)程的鏈接指針。

鏈接指針（tasks）：將進(jìn)程鏈入進(jìn)程鏈表的指針。

狀態(tài)（state）：進(jìn)程當(dāng)前的狀態(tài)。

調(diào)度信息（policy、prio、se、rt）：調(diào)度使用的調(diào)度策略、優(yōu)先級和調(diào)度實(shí)體等。

記時(shí)信息（start_time、utime、stime）：進(jìn)程建立的時(shí)間以及執(zhí)行用戶代碼與系統(tǒng)代碼的累計(jì)時(shí)間。

信號信息（signal、sighand）：進(jìn)程收到的信號以及使用的信號處理程序。

退出碼（exit_code）：進(jìn)程運(yùn)行結(jié)束后的退出代碼，供父進(jìn)程查詢用。

文件系統(tǒng)信息（fs、files）：包括文件系統(tǒng)及打開文件的信息。

地址空間信息（mm）：進(jìn)程的地址空間。

硬件現(xiàn)場信息（thread）：進(jìn)程切換時(shí)保存的CPU寄存器的內(nèi)容。

運(yùn)行信息（thread_info）：有關(guān)進(jìn)程運(yùn)行環(huán)境、狀況的CPU相關(guān)信息。

4. 查看進(jìn)程的信息

查看進(jìn)程信息的命令是ps（processstatus）命令。該命令可查看記錄在進(jìn)程描述符task_struct中的幾乎所有信息。

【說明】

（1）默認(rèn)只顯示在本終端上運(yùn)行的進(jìn)程，除非指定了-e、a、x等選項(xiàng)。

（2）沒有指定顯示格式時(shí)，采用以下默認(rèn)格式，分4列顯示：

（3）指定-f選項(xiàng)時(shí)，以全格式，分8列顯示：

例4.1?ps命令用法示例。

4.2 進(jìn)程的運(yùn)行模式

4.2.1 操作系統(tǒng)的內(nèi)核操作系統(tǒng)的內(nèi)核是硬件的直接操控者，因此與硬件的架構(gòu)密切相關(guān)。對PC機(jī)來說，x86是32位PC機(jī)的硬件架構(gòu)，x86-64是在x86的基礎(chǔ)上擴(kuò)展而成的64位架構(gòu)，簡稱為x64。這兩種架構(gòu)也是目前最為流行的硬件平臺。

1. x86/x64CPU的執(zhí)行模式

CPU的基本功能就是執(zhí)行指令。通常，CPU指令集中的指令可以分為兩類，即特權(quán)指令和非特權(quán)指令。特權(quán)指令是指那些具有特殊權(quán)限的指令。這類指令可以訪問系統(tǒng)中所有寄存器、內(nèi)存單元和I/O端口，修改系統(tǒng)的關(guān)鍵設(shè)置。

2. 操作系統(tǒng)內(nèi)核

一個(gè)完整的操作系統(tǒng)由一個(gè)內(nèi)核（kernel）和一些系統(tǒng)服務(wù)程序構(gòu)成。內(nèi)核是操作系統(tǒng)的核心，它負(fù)責(zé)最基本的資源管理和硬件控制工作，為進(jìn)程提供運(yùn)行的環(huán)境。內(nèi)核在系統(tǒng)引導(dǎo)時(shí)載入并常駐內(nèi)存。它運(yùn)行在核心態(tài)，因而能夠訪問所有的系統(tǒng)資源。

從進(jìn)程的角度看，內(nèi)核的功能有兩個(gè)：一是支持進(jìn)程的運(yùn)行，包括為進(jìn)程分配資源，控制和調(diào)度進(jìn)程的運(yùn)行；二是為進(jìn)程提供服務(wù)，也就是提供一些內(nèi)核函數(shù)（稱為系統(tǒng)調(diào)用）供進(jìn)程調(diào)用使用。

3. Linux系統(tǒng)的內(nèi)核

圖4-5是Linux系統(tǒng)的體系結(jié)構(gòu)。系統(tǒng)分為3層：最底層是硬件層，包括了各種系統(tǒng)硬件和設(shè)備。硬件層之上是內(nèi)核，它形成了對硬件的第一層包裝。對下，它管理和控制硬件；對上，它提供系統(tǒng)服務(wù)。用戶層由系統(tǒng)的核外程序和用戶程序組成，它們都以用戶進(jìn)程的方式運(yùn)行在核心之上，為用戶提供更高層次的系統(tǒng)包裝。圖4-5?Linux系統(tǒng)的內(nèi)核結(jié)構(gòu)

Linux系統(tǒng)的內(nèi)核主要由以下成分構(gòu)成：

（1）系統(tǒng)調(diào)用接口：這是進(jìn)程與內(nèi)核的接口，進(jìn)程通過此接口調(diào)用內(nèi)核的功能。

（2）進(jìn)程管理子系統(tǒng)：負(fù)責(zé)支持、控制和調(diào)度進(jìn)程的運(yùn)行。該子系統(tǒng)包括以下模塊：

核心管理模塊kernel：管理CPU，調(diào)度和協(xié)調(diào)進(jìn)程的運(yùn)行。

進(jìn)程通信模塊ipc：實(shí)現(xiàn)進(jìn)程間的本地通信。

內(nèi)存管理模塊mm：管理內(nèi)存和進(jìn)程的地址空間。

（3）文件與I/O子系統(tǒng)：負(fù)責(zé)管理文件、設(shè)備和I/O操作。該子系統(tǒng)包括以下模塊：

文件系統(tǒng)模塊fs：為進(jìn)程提供訪問文件和設(shè)備的服務(wù)。

網(wǎng)絡(luò)通信模塊net：管理網(wǎng)絡(luò)接口設(shè)備，提供進(jìn)程間的網(wǎng)絡(luò)通信服務(wù)。

設(shè)備驅(qū)動模塊drivers：驅(qū)動設(shè)備的運(yùn)行。

（4）硬件控制接口：提供與硬件平臺的接口，負(fù)責(zé)控制硬件并響應(yīng)和處理中斷。

4.2.2 中斷與系統(tǒng)調(diào)用

由圖4-5可以看出，內(nèi)核與外界的接口是來自用戶層的系統(tǒng)調(diào)用和來自硬件層的中斷，而系統(tǒng)調(diào)用本身也是一種特殊的中斷?？梢哉f內(nèi)核是中斷驅(qū)動的，它的主要功能就體現(xiàn)在系統(tǒng)調(diào)用和中斷處理中。

1. 中斷

在現(xiàn)代系統(tǒng)中，CPU與各種設(shè)備是并發(fā)工作的。

2. 系統(tǒng)調(diào)用

一般的中斷都是源自CPU外部的事件，但還有一種特殊的中斷，其中斷源來自CPU內(nèi)部，是在CPU執(zhí)行了某個(gè)特殊指令時(shí)引發(fā)的。

系統(tǒng)調(diào)用是系統(tǒng)內(nèi)核提供給用戶進(jìn)程的一組特殊的函數(shù)。

系統(tǒng)調(diào)用是通過陷入機(jī)制實(shí)現(xiàn)的。

4.2.3 進(jìn)程的運(yùn)行模式

Linux的內(nèi)核運(yùn)行在核心態(tài)，而用戶進(jìn)程則只能運(yùn)行在用戶態(tài)。從用戶態(tài)轉(zhuǎn)換為核心態(tài)的唯一途徑是中斷（包括陷入）。一旦CPU響應(yīng)了中斷，就將CPU的狀態(tài)切換到核心態(tài)，待中斷處理結(jié)束返回時(shí)，再將CPU狀態(tài)切回到用戶態(tài)。

由于進(jìn)程在其運(yùn)行期間經(jīng)常會被中斷打斷，也經(jīng)常需要調(diào)用系統(tǒng)調(diào)用函數(shù)，因此CPU會在用戶態(tài)與核心態(tài)之間來回地切換。在進(jìn)行通常的計(jì)算和處理時(shí)，進(jìn)程運(yùn)行在用戶態(tài)。執(zhí)行系統(tǒng)調(diào)用或中斷處理程序時(shí)則進(jìn)入核心態(tài)。圖4-6描述了進(jìn)程在運(yùn)行過程中的模式切換。圖4-6用戶進(jìn)程的運(yùn)行模式切換

4.3 進(jìn)程的描述與組織

4.3.1 進(jìn)程的資源1. 進(jìn)程的地址空間進(jìn)程的一個(gè)重要構(gòu)成成分是進(jìn)程映像，即進(jìn)程所執(zhí)行的代碼、使用的數(shù)據(jù)和堆棧等。為了容納進(jìn)程映像，每個(gè)進(jìn)程都有一個(gè)自己的地址空間，這是進(jìn)程運(yùn)行的必備條件。進(jìn)程有用戶態(tài)和核心態(tài)兩種運(yùn)行模式，不同模式下可訪問的地址空間也不相同。因此進(jìn)程的地址空間被劃分為用戶空間和內(nèi)核空間兩部分，如圖4-7所示。圖4-7?Linux進(jìn)程的地址空間

2. 進(jìn)程的文件與設(shè)備

文件是信息的長久保存形式，應(yīng)用程序經(jīng)常要使用或處理文件。此外，應(yīng)用程序還需要使用設(shè)備來與外界傳輸數(shù)據(jù)。因此文件和設(shè)備都是進(jìn)程的常用資源。在Linux系統(tǒng)中設(shè)備被當(dāng)作文件來處理，因此兩者都由文件系統(tǒng)來管理。

3. 進(jìn)程的信號通信

進(jìn)程并非孤立地在運(yùn)行。它需要能夠接收和處理系統(tǒng)或其他進(jìn)程發(fā)來的信號，這些信號可能是通知它某個(gè)事件或控制命令，比如暫停運(yùn)行、終止運(yùn)行等。進(jìn)程通過設(shè)定的信號處理程序來對信號做出響應(yīng)。為實(shí)現(xiàn)信號通信，進(jìn)程需要擁有信號隊(duì)列以及信號處理程序。

4.3.2 進(jìn)程的描述結(jié)構(gòu)

如前所述，進(jìn)程描述符task_struct是進(jìn)程的PCB，它記錄了進(jìn)程的所有必要信息。task_struct結(jié)構(gòu)體中的字段較多，部分主要字段在4.1.4節(jié)中做了說明。本節(jié)重點(diǎn)描述進(jìn)程描述符與內(nèi)核棧和幾個(gè)主要資源的連接結(jié)構(gòu)，見圖4-8。圖4-8?Linux進(jìn)程的描述結(jié)構(gòu)

4.3.3 進(jìn)程的組織

管理進(jìn)程就是管理進(jìn)程的PCB。一個(gè)系統(tǒng)中通?？赡軗碛袛?shù)百乃至上千個(gè)進(jìn)程，為了有效地管理如此多的PCB，系統(tǒng)需要采用適當(dāng)?shù)姆绞綄⑺鼈兘M織在一起。通常采用的組織結(jié)構(gòu)有數(shù)組、散列表和鏈表3種方式。

Linux系統(tǒng)采用了多種方式來組織進(jìn)程的描述符task_struct，主要有以下幾種：

1. 進(jìn)程鏈表

系統(tǒng)將所有進(jìn)程的描述符鏈成一個(gè)雙向循環(huán)鏈表。

2. PID散列表

在許多情況下，內(nèi)核需要根據(jù)進(jìn)程的標(biāo)識號PID來查找進(jìn)程。

3. 進(jìn)程樹鏈表

Linux系統(tǒng)的進(jìn)程之間存在著父子和兄弟關(guān)系。

4. 可執(zhí)行隊(duì)列

為了方便進(jìn)程的調(diào)度，系統(tǒng)把所有處于可執(zhí)行狀態(tài)的進(jìn)程組織成可執(zhí)行隊(duì)列。

5. 等待隊(duì)列

進(jìn)程因不同的原因而睡眠。例如，等待磁盤操作的數(shù)據(jù)，等待某系統(tǒng)資源可用或等待固定的時(shí)間間隔。

4.4 進(jìn)程控制

進(jìn)程控制是指對進(jìn)程的生命周期進(jìn)行有效的管理，實(shí)現(xiàn)進(jìn)程的創(chuàng)建、撤銷以及進(jìn)程各狀態(tài)之間的轉(zhuǎn)換等控制功能。進(jìn)程控制的目標(biāo)是使多進(jìn)程能夠平穩(wěn)高效地并發(fā)執(zhí)行，充分共享系統(tǒng)資源。

4.4.1 進(jìn)程控制的功能

進(jìn)程控制的功能是控制進(jìn)程在整個(gè)生命周期中各種狀態(tài)之間的轉(zhuǎn)換，但不包括就緒態(tài)與運(yùn)行態(tài)之間的轉(zhuǎn)換，因?yàn)槟鞘怯蛇M(jìn)程調(diào)度來實(shí)現(xiàn)的。進(jìn)程控制的任務(wù)主要有以下幾個(gè)：

1.創(chuàng)建進(jìn)程

2.撤銷進(jìn)程

3.阻塞進(jìn)程

4.喚醒進(jìn)程

4.4.2 Linux系統(tǒng)的進(jìn)程控制

在Linux系統(tǒng)中，進(jìn)程控制的功能是由內(nèi)核的進(jìn)程管理子系統(tǒng)實(shí)現(xiàn)的，用戶進(jìn)程可以通過內(nèi)核提供的系統(tǒng)調(diào)用來實(shí)現(xiàn)對進(jìn)程的控制。

1. 進(jìn)程的創(chuàng)建與映像更換

進(jìn)程不能憑空出世，它是由另一個(gè)進(jìn)程創(chuàng)建的。新創(chuàng)建的進(jìn)程稱為子進(jìn)程，創(chuàng)建子進(jìn)程的進(jìn)程稱為父進(jìn)程。

1） 創(chuàng)建進(jìn)程

創(chuàng)建一個(gè)進(jìn)程的系統(tǒng)調(diào)用是fork()，方法是按父進(jìn)程復(fù)制一個(gè)子進(jìn)程。fork()的主要操作是：為子進(jìn)程分配一個(gè)PID、內(nèi)核棧和task_struct結(jié)構(gòu)，將thread_info和task_struct用指針連接起來；將父進(jìn)程的內(nèi)核棧和task_struct結(jié)構(gòu)中的資源描述等內(nèi)容復(fù)制到子進(jìn)程的對應(yīng)結(jié)構(gòu)中；將PID和家族關(guān)系等信息填入task_struct結(jié)構(gòu)，初始化那些非繼承性的數(shù)據(jù)，如時(shí)間片、運(yùn)行統(tǒng)計(jì)數(shù)據(jù)等。至此，子進(jìn)程的描述符已建立完成（如圖4-8所示）。

fork()系統(tǒng)調(diào)用

【功能】創(chuàng)建一個(gè)新的子進(jìn)程。

【調(diào)用格式】intfork();

【返回值】

0 向子進(jìn)程返回的返回值，總為0。

>0 向父進(jìn)程返回的返回值，它是子進(jìn)程的PID。

-1 創(chuàng)建失敗。

【說明】若fork()調(diào)用成功，它向父進(jìn)程返回子進(jìn)程的PID，并向新建的子進(jìn)程返回0。

圖4-9描述了fork()系統(tǒng)調(diào)用的執(zhí)行結(jié)果圖4-9?fork()系統(tǒng)調(diào)用的執(zhí)行結(jié)果

如果程序中不考慮fork()的返回值的話，則父子進(jìn)程的行為就完全一樣了。但創(chuàng)建一個(gè)子進(jìn)程的目的是想讓它做另一件事。所以，通常的編程方法是在fork()調(diào)用后判斷fork()的返回值，分別為父進(jìn)程和子進(jìn)程設(shè)計(jì)不同的執(zhí)行分支。這樣，父子進(jìn)程執(zhí)行的雖是同一個(gè)代碼，執(zhí)行路線卻不同。圖4-10描述了用fork()創(chuàng)建子進(jìn)程的標(biāo)準(zhǔn)流程。圖4-10用fork()創(chuàng)建子進(jìn)程

例4.2一個(gè)簡單的fork_test程序。

注：程序中的getpid()是一個(gè)系統(tǒng)調(diào)用，它返回本進(jìn)程的PID。該程序運(yùn)行時(shí)，父子進(jìn)程會分別輸出自己的信息。由于是并發(fā)運(yùn)行，輸出的先后順序并不確定，因此結(jié)果可能如下所示：

2）更換進(jìn)程映像

新創(chuàng)建的子進(jìn)程執(zhí)行的是與父進(jìn)程相同的代碼。然而，通常我們需要的是讓新進(jìn)程執(zhí)行另外一個(gè)程序。

exec()系統(tǒng)調(diào)用的功能是根據(jù)參數(shù)指定的路徑名找到可執(zhí)行文件，把它裝入進(jìn)程的地址空間，覆蓋原來的進(jìn)程映像，從而形成一個(gè)不同于父進(jìn)程的全新的子進(jìn)程。

【參數(shù)】

（1）可執(zhí)行文件：以p結(jié)尾的函數(shù)用file指定，只需指定文件名，如ls；其他函數(shù)用path指定，必須是絕對路徑名，如/bin/ls。

（2）運(yùn)行參數(shù)：以execv開頭的函數(shù)用argv[]字符串?dāng)?shù)組傳遞運(yùn)行參數(shù)；以execl開頭的函數(shù)用若干個(gè)arg字符串指定運(yùn)行參數(shù)。

（3）運(yùn)行環(huán)境：以e結(jié)尾的函數(shù)使用envp[]數(shù)組來指定傳遞給應(yīng)用程序的環(huán)境變量；其他的函數(shù)沒有這個(gè)參數(shù)，它們將使用默認(rèn)的環(huán)境變量。

與一般的函數(shù)不同，exec()是“一次調(diào)用，零次返回”，因?yàn)檎{(diào)用成功后，進(jìn)程的映像已經(jīng)被替換，無處可回了。圖4-11描述了用exec()系統(tǒng)調(diào)用更換進(jìn)程映像的流程。子進(jìn)程開始運(yùn)行后，立即調(diào)用exec()，變身成功后即開始執(zhí)行新的程序了。圖4-11用exec()更換進(jìn)程的映像

例4.3一個(gè)簡單的fork-exec_test程序。

3）寫時(shí)復(fù)制技術(shù)

創(chuàng)建新進(jìn)程的效率決定了系統(tǒng)快速執(zhí)行任務(wù)的能力。傳統(tǒng)的fork()系統(tǒng)調(diào)用是將父進(jìn)程的映像復(fù)制給新的子進(jìn)程，這個(gè)操作是耗時(shí)的。如果新進(jìn)程創(chuàng)立后立即調(diào)用exec()，則剛復(fù)制進(jìn)來的進(jìn)程映像又會立刻被覆蓋掉，這顯然是非常低效的。為了優(yōu)化fork()的性能，Linux使用了“寫時(shí)復(fù)制”（copyonwrite）技術(shù)，就是當(dāng)fork()完成后并不立刻復(fù)制父進(jìn)程的映像內(nèi)容，而是讓子進(jìn)程共享父進(jìn)程的同一個(gè)副本，直到遇到有一方執(zhí)行寫入操作（即修改了映像）時(shí)才進(jìn)行復(fù)制，使父子進(jìn)程擁有各自獨(dú)立的副本。也就是說，復(fù)制操作被推遲到真正需要的時(shí)候才進(jìn)行。

2. 進(jìn)程的終止與等待

1）進(jìn)程的終止與退出碼

導(dǎo)致一個(gè)進(jìn)程終止運(yùn)行的方式有兩種：一是程序中使用退出語句主動退出，我們稱其為正常終止；另一種是被某個(gè)信號殺死，例如在進(jìn)程運(yùn)行時(shí)按Ctrl+c鍵終止其運(yùn)行，這稱為非正常終止。

用C語言編程時(shí)，可以通過以下4種方式主動退出：

（1）調(diào)用exit(status)函數(shù)來結(jié)束程序；

（2）在main()函數(shù)中用returnstatus語句結(jié)束；

（3）在main()函數(shù)中用return語句結(jié)束；

（4）程序執(zhí)行至main()函數(shù)結(jié)束。

2）終止進(jìn)程

進(jìn)程無論以哪種方式退出，最終都會調(diào)用exit()系統(tǒng)調(diào)用，終止自己的運(yùn)行。exit()系統(tǒng)調(diào)用執(zhí)行以下操作：釋放進(jìn)程所占有的資源，只保留其描述符和內(nèi)核棧；向進(jìn)程描述符中寫入進(jìn)程退出碼和一些統(tǒng)計(jì)信息；置進(jìn)程狀態(tài)為“僵死態(tài)”；如果有子進(jìn)程的話就為它們找一個(gè)新的父進(jìn)程來“領(lǐng)養(yǎng)”；通知父進(jìn)程回收自己；最后調(diào)用進(jìn)程調(diào)度程序切換進(jìn)程。

3）等待與回收進(jìn)程

僵尸進(jìn)程的最后回收工作一般由其父進(jìn)程負(fù)責(zé)。這是因?yàn)樵谠S多情況下父進(jìn)程需要了解子進(jìn)程的執(zhí)行結(jié)果?；厥眨╮eap）的主要操作是從僵尸子進(jìn)程的描述符中收集必要的信息，然后撤銷其剩余資源，即進(jìn)程描述符和內(nèi)核棧。至此子進(jìn)程徹底消失。圖4-12用wait實(shí)現(xiàn)進(jìn)程的等待

例4.4一個(gè)簡單的wait-exit_test程序。

4）子進(jìn)程的回收策略

子進(jìn)程結(jié)束后留下僵尸是為了讓父進(jìn)程采集運(yùn)行信息，只有經(jīng)父進(jìn)程回收后僵尸才能消失。如果因某種原因父進(jìn)程未能回收子進(jìn)程，就會造成僵尸積累，占用系統(tǒng)資源（主要是PID號），嚴(yán)重時(shí)會導(dǎo)致fork()失敗。這就是僵尸問題。

3. 進(jìn)程的阻塞與喚醒

運(yùn)行中的進(jìn)程若需要等待一個(gè)特定事件的發(fā)生而不能繼續(xù)運(yùn)行下去，則主動放棄CPU，進(jìn)入睡眠態(tài)。等待的事件可能是一段時(shí)間、從磁盤上讀出的文件數(shù)據(jù)、來自鍵盤的輸入或是某個(gè)硬件事件。進(jìn)程通過調(diào)用內(nèi)核函數(shù)來阻塞自己。阻塞進(jìn)程的操作步驟是：建立一個(gè)等待隊(duì)列的節(jié)點(diǎn)，填入本進(jìn)程的信息，將它鏈入相應(yīng)的等待隊(duì)列中；將進(jìn)程的狀態(tài)置為睡眠態(tài)，調(diào)用進(jìn)程調(diào)度程序；進(jìn)程調(diào)度程序?qū)⑵鋸目蓤?zhí)行隊(duì)列中刪去，并選擇其他進(jìn)程運(yùn)行。具體的實(shí)現(xiàn)策略通常還有些優(yōu)化，比如進(jìn)程在即將改變狀態(tài)前先檢測等待條件，如果條件滿足則不必進(jìn)入睡眠態(tài)。

被喚醒的進(jìn)程通常還要判斷一下該事件是否滿足自己的等待條件，比如結(jié)束的子進(jìn)程是否是自己所等待的子進(jìn)程。如果是等待的事件則進(jìn)行處理，然后繼續(xù)運(yùn)行；不是則再次睡眠，等待下一次喚醒。處于可中斷睡眠態(tài)的進(jìn)程也可以被信號喚醒。被信號喚醒稱為“偽”喚醒，即喚醒并非因?yàn)榈却氖录l(fā)生。偽喚醒的進(jìn)程在處理完信號后可能會改變狀態(tài)，也可能會再次睡眠。

4.4.3 Shell命令的執(zhí)行過程

Shell程序的功能是執(zhí)行Shell命令。執(zhí)行命令的主要方式是創(chuàng)建一個(gè)子進(jìn)程，讓這個(gè)子進(jìn)程來執(zhí)行命令的映像文件。因此，Shell進(jìn)程是所有在其下執(zhí)行的命令的父進(jìn)程。圖4-13示意了Shell執(zhí)行命令的流程，從中可以看到一個(gè)進(jìn)程從誕生到消失的整個(gè)過程。圖4-13?Shell命令的執(zhí)行過程

4.5 進(jìn)程調(diào)度

4.5.1 進(jìn)程調(diào)度的基本原理1. 進(jìn)程調(diào)度的功能進(jìn)程調(diào)度的功能是按照一定的策略把CPU分配給就緒進(jìn)程，使它們輪流地使用CPU運(yùn)行。進(jìn)程調(diào)度實(shí)現(xiàn)了進(jìn)程就緒態(tài)與運(yùn)行態(tài)之間的轉(zhuǎn)換。進(jìn)程調(diào)度的功能由內(nèi)核中的進(jìn)程調(diào)度程序?qū)崿F(xiàn)。當(dāng)正運(yùn)行的進(jìn)程因某種原因放棄CPU時(shí)，進(jìn)程調(diào)度程序就會被調(diào)用。

調(diào)度操作包括以下兩項(xiàng)內(nèi)容：

（1）選擇進(jìn)程：即按一定的調(diào)度算法，從就緒進(jìn)程隊(duì)列中選一個(gè)進(jìn)程。

（2）切換進(jìn)程：為換下的進(jìn)程保留現(xiàn)場，為選中的進(jìn)程恢復(fù)現(xiàn)場，使其運(yùn)行。

2. 進(jìn)程調(diào)度的算法

進(jìn)程調(diào)度的算法用于實(shí)現(xiàn)對CPU資源的分配策略，也就是決定什么時(shí)刻讓什么進(jìn)程運(yùn)行。調(diào)度算法是系統(tǒng)效率的關(guān)鍵，它直接決定著系統(tǒng)最本質(zhì)的性能指標(biāo)，如響應(yīng)速度、吞吐量等。進(jìn)程調(diào)度算法的目標(biāo)首先是要充分發(fā)揮CPU的處理能力，滿足進(jìn)程對CPU的需求。此外還要盡量做到公平對待每個(gè)進(jìn)程，使它們都能得到合理的運(yùn)行機(jī)會。

常用的調(diào)度算法有：

（1）先進(jìn)先出法：按照進(jìn)程在可執(zhí)行隊(duì)列中的先后次序來調(diào)度。

（2）短進(jìn)程優(yōu)先法：按照進(jìn)程的長短，優(yōu)先調(diào)度短進(jìn)程運(yùn)行。

（3）時(shí)間片輪轉(zhuǎn)法：進(jìn)程按規(guī)定的時(shí)間片輪流使用CPU。

（4）優(yōu)先級調(diào)度法：為每個(gè)進(jìn)程設(shè)置優(yōu)先級，調(diào)度時(shí)優(yōu)先選擇優(yōu)先級高的進(jìn)程運(yùn)行，使緊迫的任務(wù)可以優(yōu)先得到處理。

3. 進(jìn)程調(diào)度的時(shí)機(jī)

引發(fā)進(jìn)程調(diào)度的情況可歸納為下面幾種：

（1）當(dāng)前進(jìn)程放棄CPU，轉(zhuǎn)入睡眠、暫?；蚪┧缿B(tài)；

（2）當(dāng)前進(jìn)程讓出CPU，轉(zhuǎn)入就緒態(tài)；

（3）當(dāng)前進(jìn)程的時(shí)間片用盡；

（4）有更高優(yōu)先級的進(jìn)程就緒。

4.5.2 Linux系統(tǒng)的進(jìn)程調(diào)度

Linux系統(tǒng)的進(jìn)程調(diào)度簡潔而高效。尤其是新版內(nèi)核采用的新調(diào)度算法，在高負(fù)載、多CPU及桌面系統(tǒng)中都執(zhí)行得極為出色。

1. 進(jìn)程調(diào)度的信息

Linux的進(jìn)程描述符中記錄了與進(jìn)程調(diào)度相關(guān)的信息，主要有：

（1）調(diào)度策略（policy）：對進(jìn)程的調(diào)度算法，決定了調(diào)度程序應(yīng)如何調(diào)度該進(jìn)程。Linux將進(jìn)程分為實(shí)時(shí)進(jìn)程與普通（非實(shí)時(shí)）進(jìn)程兩類，分別采用不同的調(diào)度策略。

（2）實(shí)時(shí)優(yōu)先級（rt_priority）：實(shí)時(shí)進(jìn)程的優(yōu)先級，標(biāo)志實(shí)時(shí)進(jìn)程優(yōu)先權(quán)的高低，取值范圍為0（最低）~99（最高）。實(shí)時(shí)進(jìn)程此項(xiàng)為1~99，非實(shí)時(shí)進(jìn)程此項(xiàng)為0。

（3）靜態(tài)優(yōu)先級（static_prio）：進(jìn)程的基本優(yōu)先級。

（4）動態(tài)優(yōu)先級（prio）：進(jìn)程調(diào)度使用的實(shí)際優(yōu)先級。它是對靜態(tài)優(yōu)先級的調(diào)整。

（5）時(shí)間片（time_slice）：進(jìn)程當(dāng)前剩余的時(shí)間。

2. 進(jìn)程調(diào)度的機(jī)制

1）調(diào)度策略

Linux進(jìn)程調(diào)度的宗旨是及時(shí)地響應(yīng)實(shí)時(shí)進(jìn)程，公平地響應(yīng)普通進(jìn)程。在調(diào)度策略上，實(shí)時(shí)進(jìn)程的優(yōu)先級要高于普通進(jìn)程。因此系統(tǒng)中只要有實(shí)時(shí)進(jìn)程就緒，內(nèi)核就會調(diào)度它們運(yùn)行，直至全部完成。對普通進(jìn)程，內(nèi)核采用的是均衡的調(diào)度策略，力圖使所有進(jìn)程都能公平地獲得執(zhí)行機(jī)會。

2）調(diào)度程序

Linux的主調(diào)度程序是schedule()函數(shù)。schedule()是調(diào)度的入口，每當(dāng)需要切換進(jìn)程時(shí)都要調(diào)用這個(gè)函數(shù)。schedule()的工作就是選擇下一個(gè)要運(yùn)行的進(jìn)程，然后切換現(xiàn)場，讓選中的進(jìn)程運(yùn)行。選擇進(jìn)程的工作是通過調(diào)用具體的調(diào)度程序完成的。Linux提供了兩個(gè)具體調(diào)度程序，即用于實(shí)時(shí)進(jìn)程的RT調(diào)度器和用于普通進(jìn)程的CFS調(diào)度器。選擇的順序是先RT后CFS，即如果有可調(diào)度的實(shí)時(shí)進(jìn)程就調(diào)用RT調(diào)度器，選擇一個(gè)實(shí)時(shí)進(jìn)程，否則就調(diào)用CFS調(diào)度器，選擇一個(gè)普通進(jìn)程。

3）調(diào)度實(shí)體與隊(duì)列

調(diào)度程序的操作對象并不是進(jìn)程描述符本身，而是包含在進(jìn)程描述符中的稱為調(diào)度實(shí)體的結(jié)構(gòu)變量。調(diào)度實(shí)體中包含了調(diào)度算法所需的所有信息，它代表進(jìn)程參與調(diào)度。實(shí)時(shí)進(jìn)程的調(diào)度實(shí)體是rt，普通進(jìn)程的調(diào)度實(shí)體是se。

調(diào)度程序所使用的最基本的數(shù)據(jù)結(jié)構(gòu)是可執(zhí)行隊(duì)列（runqueue），也稱為就緒隊(duì)列。

4）調(diào)度方式

調(diào)度的方式分為主動調(diào)度與搶占調(diào)度兩種。主動調(diào)度就是由進(jìn)程直接調(diào)用schedule()函數(shù)，主動放棄CPU；搶占調(diào)度是由內(nèi)核調(diào)用schedule()函數(shù)，強(qiáng)制切換進(jìn)程。搶占調(diào)度又分為周期性搶占與優(yōu)先級搶占。周期性搶占是在每個(gè)時(shí)鐘節(jié)拍中判斷是否需要切換進(jìn)程，如果需要就通知內(nèi)核重新調(diào)度。優(yōu)先級搶占是當(dāng)有高優(yōu)先級的進(jìn)程就緒時(shí)，內(nèi)核將中斷當(dāng)前進(jìn)程，調(diào)度更高優(yōu)先級的進(jìn)程運(yùn)行。

5）內(nèi)核搶占方式

上述的搶占機(jī)制屬于用戶級的搶占，特點(diǎn)是切換操作都是在用戶態(tài)下發(fā)生的。多數(shù)操作系統(tǒng)（包括2.4版內(nèi)核之前的Linux）都只支持這種搶占機(jī)制。在這樣的系統(tǒng)中，內(nèi)核代碼會一直運(yùn)行到完成，其間不允許重新調(diào)度。假如一個(gè)中斷處理的過程中又嵌套了其他的中斷處理，則要在全部處理都執(zhí)行完后返回用戶空間時(shí)才允許進(jìn)程調(diào)度，這顯然會延長系統(tǒng)對高優(yōu)先級進(jìn)程的響應(yīng)時(shí)間。

3. 實(shí)時(shí)進(jìn)程的調(diào)度

實(shí)時(shí)進(jìn)程的調(diào)度原則是嚴(yán)格按優(yōu)先級進(jìn)行調(diào)度，在同一優(yōu)先級上則采用先進(jìn)先出或輪轉(zhuǎn)法進(jìn)行調(diào)度。所有的實(shí)時(shí)進(jìn)程都由RT調(diào)度器（RealtimeScheduler）進(jìn)行調(diào)度。

1）實(shí)時(shí)進(jìn)程的可執(zhí)行隊(duì)列

實(shí)時(shí)進(jìn)程的可執(zhí)行隊(duì)列采用rt_rq結(jié)構(gòu)描述，其中包括了實(shí)時(shí)調(diào)度所需的各種信息。

2）實(shí)時(shí)進(jìn)程的調(diào)度策略

實(shí)時(shí)進(jìn)程的調(diào)度策略包括先進(jìn)先出法（SCHED_FIFO）、時(shí)間片輪轉(zhuǎn)法（SCHED_RR）和最后期限法（SCHED_DEADLINE）。以前兩種最為常用。

（1）先進(jìn)先出法（First-In，F(xiàn)irst-Out，F(xiàn)IFO）：調(diào)度程序依次選擇當(dāng)前最高優(yōu)先級的FIFO類型的進(jìn)程，調(diào)度其運(yùn)行。

（2）輪轉(zhuǎn)法（RoundRobin，RR）：RR調(diào)度算法的基本思想是給每個(gè)實(shí)時(shí)進(jìn)程分配一個(gè)時(shí)間片，然后按照它們的優(yōu)先級加入到相應(yīng)的優(yōu)先級隊(duì)列中。

嚴(yán)格地說，這兩種實(shí)時(shí)都屬于軟實(shí)時(shí)，也就是統(tǒng)計(jì)意義上的實(shí)時(shí)，并不能提供像實(shí)時(shí)Linux系統(tǒng)那樣精確的響應(yīng)時(shí)間保證。相比之下，F(xiàn)IFO算法更為簡單，但在一些特殊情況下有欠公平。比如，一個(gè)很短的進(jìn)程排在了一個(gè)很長的進(jìn)程之后，它可能要花費(fèi)很多的時(shí)間來等待。因此，F(xiàn)IFO適用于那些每次運(yùn)行時(shí)間較短的實(shí)時(shí)進(jìn)程。RR算法在追求響應(yīng)速度的同時(shí)還兼顧到公平性，因而適合于那些運(yùn)行時(shí)間較長的實(shí)時(shí)進(jìn)程。

3）實(shí)時(shí)調(diào)度的實(shí)施

當(dāng)一個(gè)實(shí)時(shí)進(jìn)程就緒時(shí)，內(nèi)核將根據(jù)它的優(yōu)先級將其放入相應(yīng)隊(duì)列的尾部。如果該進(jìn)程的優(yōu)先級高于當(dāng)前進(jìn)程的優(yōu)先級，內(nèi)核將調(diào)用schedule()函數(shù)進(jìn)行搶占，否則就排在隊(duì)中等待調(diào)度機(jī)會。每次調(diào)度時(shí)，若schedule()函數(shù)發(fā)現(xiàn)有實(shí)時(shí)進(jìn)程就緒，它就會調(diào)用RT調(diào)度器的pick_next_task_rt()函數(shù)，選擇下一個(gè)要運(yùn)行的實(shí)時(shí)進(jìn)程，令其運(yùn)行。

4. 普通進(jìn)程的調(diào)度

普通進(jìn)程的調(diào)度策略是普通（SCHED_NORMAL）調(diào)度法。在新內(nèi)核中，普通調(diào)度法就是完全公平調(diào)度法CFS。

1）調(diào)度策略的公平性

相比實(shí)時(shí)進(jìn)程，普通進(jìn)程的調(diào)度更加強(qiáng)調(diào)公平性。

2）CFS的調(diào)度原理

CFS調(diào)度法的要點(diǎn)之一是將CPU的使用權(quán)按比例分配給各就緒進(jìn)程，據(jù)此算出各進(jìn)程在一個(gè)調(diào)度周期內(nèi)應(yīng)運(yùn)行的時(shí)間。分配的依據(jù)是進(jìn)程的負(fù)載權(quán)重（loadweight）。每個(gè)進(jìn)程都有一個(gè)負(fù)載權(quán)重，這個(gè)權(quán)重是根據(jù)進(jìn)程的靜態(tài)優(yōu)先級計(jì)算而來的。

3）CFS的可執(zhí)行隊(duì)列

CFS調(diào)度器的可執(zhí)行隊(duì)列用cfs_rq結(jié)構(gòu)描述，包含了隊(duì)列本身以及隊(duì)列的屬性信息和統(tǒng)計(jì)數(shù)據(jù)，如當(dāng)前進(jìn)程數(shù)目、總權(quán)重、當(dāng)前最小vruntime值等。

當(dāng)一個(gè)進(jìn)程轉(zhuǎn)入就緒狀態(tài)后，內(nèi)核將其插入紅黑樹中的適當(dāng)位置；當(dāng)一個(gè)進(jìn)程被選中運(yùn)行時(shí)，它的節(jié)點(diǎn)就被從樹中摘去。每次出入隊(duì)操作都要對紅黑樹進(jìn)行平衡調(diào)整，并相應(yīng)地更新隊(duì)列的統(tǒng)計(jì)數(shù)據(jù)。

4）CFS調(diào)度的實(shí)施

當(dāng)一個(gè)普通進(jìn)程就緒時(shí)，CFS調(diào)度器根據(jù)它的vruntime值將其插入紅黑樹中。對于睡眠后被喚醒的進(jìn)程來說，它的vruntime值的增長通常會落后于其他進(jìn)程，因此它會被插入到前面的位置，得到優(yōu)先調(diào)度的機(jī)會。每次調(diào)度時(shí)，若沒有實(shí)時(shí)進(jìn)程，schedule()函數(shù)就會調(diào)用CFS調(diào)度器的pick_next_task_fair()函數(shù)，從紅黑樹中選出下一個(gè)要運(yùn)行進(jìn)程，令其運(yùn)行。

4.5.3 Linux系統(tǒng)的進(jìn)程切換

當(dāng)schedule()選中一個(gè)新的進(jìn)程后，下一步就是調(diào)用context_switch()函數(shù)，完成進(jìn)程的切換。切換操作包括兩個(gè)步驟：一是切換進(jìn)程的地址空間；二是切換進(jìn)程的執(zhí)行環(huán)境，包括內(nèi)核棧和CPU硬件環(huán)境。

切換地址空間就是為CPU安裝上新進(jìn)程的地址空間，使其訪問新的進(jìn)程映像。

1. 進(jìn)程的執(zhí)行環(huán)境

進(jìn)程在運(yùn)行時(shí)，CPU中各寄存器的值就構(gòu)成了進(jìn)程的執(zhí)行環(huán)境。進(jìn)程切換時(shí)，執(zhí)行環(huán)境也要跟著改變。在切換點(diǎn)上的執(zhí)行環(huán)境的值就稱為進(jìn)程的現(xiàn)場。調(diào)度程序需要為換下的進(jìn)程保存完整的現(xiàn)場，這樣當(dāng)進(jìn)程再次獲得運(yùn)行機(jī)會時(shí)才能夠恢復(fù)原狀繼續(xù)執(zhí)行。

對于不同的體系架構(gòu)，CPU寄存器的配置也不同。表4-1列出了x86和x64CPU的主要寄存器的名稱與用途。

具體地說，在x86系統(tǒng)中，進(jìn)程的執(zhí)行環(huán)境由以下兩部分構(gòu)成：

1）程序相關(guān)的執(zhí)行環(huán)境

與程序執(zhí)行相關(guān)的寄存器包括通用寄存器、段寄存器、指令寄存器和標(biāo)志寄存器。這些寄存器給出了程序運(yùn)行所需的指令、數(shù)據(jù)、地址和狀態(tài)等信息，它們的內(nèi)容隨著指令的執(zhí)行而變化。我們稱這部分環(huán)境為程序執(zhí)行環(huán)境。

2）硬件相關(guān)的執(zhí)行環(huán)境

與CPU運(yùn)行相關(guān)的寄存器包括控制寄存器、調(diào)試寄存器以及一些有關(guān)浮點(diǎn)計(jì)算及CPU模式設(shè)定的寄存器。此外還有一些CPU所使用的系統(tǒng)表和數(shù)據(jù)區(qū)，如段描述符表GDT和LDT、中斷向量表IDT和任務(wù)段TSS。這些表的地址保存在系統(tǒng)地址寄存器中。我們稱這部分環(huán)境為硬件執(zhí)行環(huán)境。

2. 進(jìn)程現(xiàn)場的保存與恢復(fù)

1）程序執(zhí)行環(huán)境的切換

程序執(zhí)行環(huán)境的切換發(fā)生在進(jìn)程的運(yùn)行模式轉(zhuǎn)換時(shí)。當(dāng)進(jìn)程因中斷或系統(tǒng)調(diào)用進(jìn)入核心態(tài)時(shí)，它的用戶態(tài)程序現(xiàn)場被保存在內(nèi)核棧中，CPU切換到核心態(tài)的程序執(zhí)行環(huán)境；當(dāng)返回用戶態(tài)時(shí)，內(nèi)核棧中保存的程序現(xiàn)場被恢復(fù)到CPU，進(jìn)程又回到用戶態(tài)程序執(zhí)行環(huán)境。

2）進(jìn)程的切換

進(jìn)程切換發(fā)生在進(jìn)程重新調(diào)度時(shí)。由于調(diào)度程序運(yùn)行在核心態(tài)，所以此時(shí)新舊兩進(jìn)程的程序現(xiàn)場都已在各自的內(nèi)核棧中，進(jìn)程切換時(shí)只要切換內(nèi)核棧和硬件現(xiàn)場即可。硬件現(xiàn)場切換后，在返回用戶態(tài)時(shí)程序現(xiàn)場也被恢復(fù)，則整個(gè)CPU的執(zhí)行環(huán)境都換為新進(jìn)程的了。

3. 進(jìn)程的切換過程

如上所述，switch_to()要做的操作是切換內(nèi)核棧和CPU硬件現(xiàn)場。使CPU平穩(wěn)地從一個(gè)執(zhí)行環(huán)境過渡到另一個(gè)執(zhí)行環(huán)境是個(gè)復(fù)雜的過程，這里只簡單說明主要的步驟。

以下是switch_to()執(zhí)行用B換下A的主要操作步驟：

（1）將后面操作要用到的寄存器（eflags、ebp）的值壓入A的內(nèi)核棧中。

（2）將內(nèi)核棧指針esp寄存器的值保存到A的thread中，將B的thread中保存的esp值設(shè)置到esp寄存器中，這樣就完成了內(nèi)核棧的切換。由于CPU是通過內(nèi)核棧中的thread_info來訪問當(dāng)前進(jìn)程的描述符task_struct的，所以此時(shí)的當(dāng)前進(jìn)程已變?yōu)锽了。

（3）將A的thread中的eip值設(shè)為一個(gè)特定的“標(biāo)記1”地址。

（4）將B的thread中的eip值壓入棧中。由于之前B也是被switch_to()換下的，所以這個(gè)eip值就是在那次切換的第（3）步設(shè)置的“標(biāo)記1”地址。

（5）CPU跳轉(zhuǎn)到_switch_to()函數(shù)入口，開始執(zhí)行硬件環(huán)境的切換。

（6）返回指令從棧中彈出返回地址到eip寄存器。

如果B是一個(gè)新創(chuàng)建的進(jìn)程，則建立時(shí)在它的thread中設(shè)置的eip值是fork()返回點(diǎn)處的指令地址，這是進(jìn)程首次運(yùn)行的起點(diǎn)地址。因此切換操作的第（6）步執(zhí)行的是這個(gè)地址處的指令，它跳過了第（6）步中的出棧操作，直接進(jìn)入schedule()的結(jié)束處理階段，然后恢復(fù)現(xiàn)場返回用戶空間。此處的恢復(fù)現(xiàn)場操作實(shí)際上是為B建立起初始運(yùn)行環(huán)境，用的是父進(jìn)程創(chuàng)建它時(shí)復(fù)制在其內(nèi)核棧中的程序現(xiàn)場。隨后B就開始了它的首次運(yùn)行。

4.6 進(jìn)程的互斥與同步

4.6.1 進(jìn)程間的制約關(guān)系并發(fā)進(jìn)程彼此間會產(chǎn)生相互制約的關(guān)系。進(jìn)程之間的制約關(guān)系有兩種方式：一是進(jìn)程的同步，即相關(guān)進(jìn)程為協(xié)作完成同一任務(wù)而引起的直接制約關(guān)系；二是進(jìn)程的互斥，即進(jìn)程間因競爭系統(tǒng)資源而引起的間接制約關(guān)系。

1. 臨界資源與臨界區(qū)

臨界資源（criticalresource）是一次僅允許一個(gè)進(jìn)程使用的資源。

臨界區(qū)（criticalregion）是程序中訪問臨界資源的程序片段。

在4.1.1節(jié)中描述了一個(gè)停車場車位計(jì)數(shù)器的例子（見圖4-1）。當(dāng)A、B兩個(gè)進(jìn)程同時(shí)修改計(jì)數(shù)器C時(shí)就會發(fā)生更新錯(cuò)誤，因此C是一個(gè)臨界資源，而進(jìn)程A和B中訪問C的程序段就稱為臨界區(qū)，如圖4-14所示。圖4-14臨界資源與臨界區(qū)

2. 進(jìn)程的互斥與同步機(jī)制

因共享臨界資源導(dǎo)致錯(cuò)誤的發(fā)生，其原因在于多個(gè)進(jìn)程訪問該資源的操作穿插進(jìn)行。要避免這種錯(cuò)誤，關(guān)鍵是要用某種方式來阻止多個(gè)進(jìn)程同時(shí)訪問臨界資源，這就是互斥。

進(jìn)程的互斥（mutex）就是禁止多個(gè)進(jìn)程同時(shí)進(jìn)入各自的訪問同一臨界資源的臨界區(qū)，以保證對臨界資源的排它性使用。

訪問緩沖區(qū)是一個(gè)典型的進(jìn)程同步問題。

3. 互斥與同步的實(shí)現(xiàn)方法

實(shí)現(xiàn)進(jìn)程互斥與同步的手段有多種，在現(xiàn)代操作系統(tǒng)中用得較多的有原子操作、互斥鎖和信號量。原子操作是用特定匯編語言實(shí)現(xiàn)的操作，它的操作過程受硬件的支持，具有不可分割性。原子操作主要用于實(shí)現(xiàn)資源的計(jì)數(shù)?；コ怄i機(jī)制是通過給資源加/解鎖的方式來實(shí)現(xiàn)互斥訪問資源，主要用于數(shù)據(jù)的保護(hù)。信號量是一種比互斥鎖更為靈活的機(jī)制，主要用于進(jìn)程的同步。

4.6.2 信號量同步機(jī)制

信號量是最早出現(xiàn)的進(jìn)程同步機(jī)制，因其簡捷有效而被廣泛地用來解決各種同步問題。

1. 信號量與P、V操作

信號量（semaphore）是一個(gè)整型變量s，它為某個(gè)臨界資源而設(shè)置，表示該資源的可用數(shù)目。

信號量是一種特殊的變量，它僅能被兩個(gè)標(biāo)準(zhǔn)的操作來訪問和修改。這兩個(gè)操作分別稱為P操作和V操作。

2. 用P、V操作實(shí)現(xiàn)進(jìn)程互斥

設(shè)進(jìn)程A和進(jìn)程B都要訪問臨界資源C。為實(shí)現(xiàn)互斥訪問，需要為臨界資源C設(shè)置一個(gè)信號量s，初值設(shè)為1。當(dāng)進(jìn)程運(yùn)行到臨界區(qū)開始處時(shí)，先要做P(s)操作，申請資源s。當(dāng)進(jìn)程運(yùn)行到臨界區(qū)結(jié)束處時(shí)，要做V(s)操作，釋放資源s。進(jìn)程A和進(jìn)程B的執(zhí)行過程如圖4-15所示。圖4-15用P、V操作實(shí)現(xiàn)進(jìn)程的互斥

3. 用P、V操作實(shí)現(xiàn)進(jìn)程同步

設(shè)兩進(jìn)程為協(xié)作完成某一項(xiàng)工作，需要共享一個(gè)緩沖區(qū)。先是一個(gè)進(jìn)程C往緩沖區(qū)中寫數(shù)據(jù)，然后另一個(gè)進(jìn)程D從緩沖區(qū)中讀取數(shù)據(jù)，如此循環(huán)直至處理完畢。緩沖區(qū)屬于臨界資源，為使這兩個(gè)進(jìn)程能夠協(xié)調(diào)步調(diào)，串行地訪問緩沖區(qū)，需用P、V操作來同步兩進(jìn)程。這種工作模式稱為生產(chǎn)者-消費(fèi)者模式。

同步的方法如下：

將緩沖區(qū)看作兩個(gè)臨界資源：一個(gè)是可讀緩沖區(qū)，也就是“滿”緩沖區(qū)；另一個(gè)是可寫緩沖區(qū)，也就是“空”緩沖區(qū)。分別為它們設(shè)置一個(gè)信號量。s1是可讀緩沖區(qū)資源的信號量。s1=1時(shí)表示可讀緩沖區(qū)數(shù)為1，s1=0時(shí)表示沒有可讀緩沖區(qū)；s2是可寫緩沖區(qū)資源的信號量。s2=1時(shí)表示可寫緩沖區(qū)數(shù)為1，s2=0時(shí)表示沒有可寫的緩沖區(qū)。s1的初值為0，s2的初值為1。

進(jìn)程C和進(jìn)程D的執(zhí)行過程如圖4-16所示。圖4-16用P、V操作實(shí)現(xiàn)進(jìn)程的同步

4.6.3 Linux的信號量機(jī)制

在Linux系統(tǒng)中存在兩種信號量的實(shí)現(xiàn)機(jī)制：一種是針對系統(tǒng)的臨界資源設(shè)置的，是由內(nèi)核使用的信號量，另一種是供用戶進(jìn)程使用的。

4.6.4 死鎖問題

死鎖（deadlock）是指系統(tǒng)中若干個(gè)進(jìn)程相互“無知地”等待對方所占有的資源而無限地處于等待狀態(tài)的一種僵持局面，其現(xiàn)象是若干個(gè)進(jìn)程均停頓不前，且無法自行恢復(fù)。

死鎖的根本原因是系統(tǒng)資源有限，而多個(gè)并發(fā)進(jìn)程因競爭資源而相互制約。相互制約的進(jìn)程需要彼此等待，在極端情況下，就可能出現(xiàn)死鎖。圖4-17示意了可能引發(fā)死鎖的一種運(yùn)行情況。圖4-17可能導(dǎo)致死鎖的資源使用方式

分析死鎖的原因，可以歸納出產(chǎn)生死鎖的4個(gè)必要條件：

（1）資源的獨(dú)占使用：資源由占有者獨(dú)占，不允許其他進(jìn)程同時(shí)使用。

（2）資源的非搶占式分配：資源一旦分配就不能被剝奪，直到占用者使用完畢釋放。

（3）對資源的保持和請求：進(jìn)程因請求資源而被阻塞時(shí)，對已經(jīng)占有的資源保持不放。

（4）對資源的循環(huán)等待：每個(gè)進(jìn)程已占用一些資源，而又等待別的進(jìn)程釋放資源。

解決死鎖的方案就是破壞死鎖產(chǎn)生的必要條件之一，方法有：

（1）預(yù)防：對資源的用法進(jìn)行適當(dāng)?shù)南拗啤?/p>

（2）檢測：在系統(tǒng)運(yùn)行中隨時(shí)檢測死鎖的條件，并設(shè)法避開。

（3）恢復(fù)：死鎖發(fā)生時(shí)，設(shè)法以最小的代價(jià)退出死鎖狀態(tài)。

預(yù)防是指采取某種策略，改變資源的分配和控制方式，使死鎖的條件無法產(chǎn)生。但這種做法會導(dǎo)致系統(tǒng)的資源也無法得到充分的利用。檢測是指對資源的使用情況進(jìn)行監(jiān)視，遇到有可能引發(fā)死鎖的情況就采取措施避開。這種方法需要大量的系統(tǒng)開銷，通常會以降低系統(tǒng)的運(yùn)行效率為代價(jià)。因此，現(xiàn)在的系統(tǒng)大都采取恢復(fù)的方法，就是在死鎖發(fā)生后，檢測死鎖發(fā)生的位置和原因，用外力撤銷一個(gè)或幾個(gè)進(jìn)程，或重新分配資源，使系統(tǒng)從死鎖狀態(tài)中恢復(fù)過來。

4.7 進(jìn)程通信

4.7.1 進(jìn)程通信的方式進(jìn)程間的通信有多種方式，大致可以分為信號量、信號、管道、消息和共享內(nèi)存幾類。從通信的功能來分，進(jìn)程通信方式可以分為低級通信和高級通信兩類。低級通信只是傳遞少量的數(shù)據(jù)，用于通知對方某個(gè)事件；高級通信則可以用來在進(jìn)程之間傳遞大量的信息。低級通信方式有信號量和信號，高級通信方式有消息、管道和共享內(nèi)存等。

按通信的同步方式來分，進(jìn)程通信又分為同步通信與異步通信兩類。同步通信是指通信雙方進(jìn)程共同參與整個(gè)通信過程，步調(diào)協(xié)調(diào)地發(fā)送和接收數(shù)據(jù)。這就像打電話，雙方必須同時(shí)在線，同步交談。異步通信則不同，通信雙方的聯(lián)系比較松散，通信的發(fā)送方不必考慮對方的狀態(tài)，發(fā)送完就繼續(xù)運(yùn)行。接收方也不關(guān)心發(fā)送方的狀態(tài)，在自己適合的時(shí)候接收數(shù)據(jù)。異步通信方式就如同發(fā)送電子郵件，不必關(guān)心對方何時(shí)接收。管道和共享內(nèi)存等都屬于同步通信，而信號、消息則屬于異步通信。

Linux系統(tǒng)支持以下幾種IPC機(jī)制：

（1）信號量（semaphore）：信號量分為內(nèi)核信號量與IPC信號量，分別用于核心態(tài)與用戶態(tài)進(jìn)程的同步與互斥。

（2）信號（signal）：信號是進(jìn)程間可互相發(fā)送的控制信息，一般只是幾個(gè)字節(jié)的數(shù)據(jù)，用于通知進(jìn)程有某個(gè)事件發(fā)生。

（3）管道（pipe）：管道是連接兩個(gè)進(jìn)程的一個(gè)數(shù)據(jù)傳輸通路，一個(gè)進(jìn)程向管道寫數(shù)據(jù)，另一個(gè)進(jìn)程從管道讀數(shù)據(jù)，實(shí)現(xiàn)兩進(jìn)程之間同步傳遞字節(jié)流。

（4）消息隊(duì)列（messagequeue）：消息是結(jié)構(gòu)化的數(shù)據(jù)，消息隊(duì)列是由消息鏈接而成的鏈?zhǔn)疥?duì)列。

（5）共享內(nèi)存（shared-memory）：共享內(nèi)存通信方式就是在內(nèi)存中開辟一段存儲區(qū)，將這個(gè)區(qū)映射到多個(gè)進(jìn)程的地址空間中，使得多個(gè)進(jìn)程共享這個(gè)內(nèi)存區(qū)。

4.7.2 Linux信號通信原理

信號是來自UNIX系統(tǒng)的最古老的IPC機(jī)制之一，用于在進(jìn)程之間傳遞控制信號。信號屬于低級通信，因簡單有效而得到廣泛使用，任何一個(gè)進(jìn)程都具有接收和處理信號的能力。

1. 信號的概念

信號是一組正整數(shù)常量，進(jìn)程之間通過傳送信號來通信，通知進(jìn)程發(fā)生了某事件。

Linux系統(tǒng)定義了32個(gè)常規(guī)信號，另外還有32個(gè)擴(kuò)展信號。表4-2列出了常用的信號及其用途和默認(rèn)處理方式。用kill-l命令可以列出系統(tǒng)的全部可用信號。

2. Linux的信號描述結(jié)構(gòu)

Linux系統(tǒng)用于信號管理的主要數(shù)據(jù)結(jié)構(gòu)是信號描述符signal_struct、信號處理描述符sighand_struct以及信號隊(duì)列結(jié)構(gòu)sigpending，描述結(jié)構(gòu)如圖4-18所示。圖4-18?Linux進(jìn)程的信號描述結(jié)構(gòu)

3. 信號的處理過程

一個(gè)信號從出現(xiàn)到處理完畢需要經(jīng)歷兩個(gè)階段：一個(gè)是信號產(chǎn)生（generation）階段，即形成待處理的信號；另一個(gè)是信號交付（deliver）階段，就是將產(chǎn)生的信號交付處理。

1）信號的產(chǎn)生

信號產(chǎn)生的過程可分為發(fā)出、發(fā)送和通知幾個(gè)步驟。

2）信號的交付

信號的交付過程包括檢測、提取與處理幾個(gè)步驟。

4. 信號的處理方式

信號的處理方式分為以下3種：

（1）忽略（ignore）：不做任何處理；

（2）默認(rèn)（default）：調(diào)用內(nèi)核的默認(rèn)處理函數(shù)來處理信號；

（3）捕獲（catch）：執(zhí)行進(jìn)程自己設(shè)置的信號處理函數(shù)。

5. 信號的應(yīng)用

進(jìn)程使用kill()等系統(tǒng)調(diào)用來發(fā)信號，控制進(jìn)程的運(yùn)行。終端用戶可以用kill命令來達(dá)到同樣的目的。kill命令是對kill()系統(tǒng)調(diào)用的命令級封裝，它可以向指定的進(jìn)程發(fā)信號。對前臺進(jìn)程還可以用鍵盤按