《操作系統(tǒng)》第三章：進(jìn)程

第3章

進(jìn)程主要內(nèi)容3.1進(jìn)程的引入3.2進(jìn)程的概念3.3進(jìn)程的描述/表達(dá)描述進(jìn)程的狀態(tài)變遷、數(shù)據(jù)結(jié)構(gòu)、進(jìn)程控制塊3.4進(jìn)程操作進(jìn)程創(chuàng)建、進(jìn)程阻塞、進(jìn)程喚醒、進(jìn)程終止3.5進(jìn)程調(diào)度調(diào)度隊列、調(diào)度程序、上下文切換3.6進(jìn)程間通信基于消息傳遞、基于共享內(nèi)存3.1進(jìn)程的引入為什么要引入進(jìn)程?←

一次裝入并運(yùn)行一個“作業(yè)”←

同時裝入多個“程序”，串行執(zhí)行←

同時裝入多個程序，并發(fā)執(zhí)行，

僅當(dāng)?shù)却齀/O時切換程序執(zhí)行←

同時裝入多個程序，并發(fā)執(zhí)行，

程序切換條件：執(zhí)行的時間長

度(時間片)到orI/O等待回顧OS發(fā)展

(1)手工操作

(2)簡單批處理

(3)多道程序批

處理

(4)分時處理

(5)對稱多處理進(jìn)程概念–OS發(fā)展的需要和必然問題1:程序是如何運(yùn)行起來的？int

main(int

argc,char*argv[]){

inti,to,sum=0;to=atoi(argv[1]);

for(i=1;i<=to;i++){sum=sum+i;}

printf(“%d”,sum);}源代碼代碼段：

movax,[100]

mov

bx,[104]addax,bx……100:0//sum104:1//i可執(zhí)行程序(在磁盤上，靜態(tài)存放)程序在內(nèi)存中運(yùn)行代碼段數(shù)據(jù)段...棧(參數(shù)等)

寄存器組

CPU

3.1進(jìn)程的引入程序執(zhí)行的細(xì)節(jié)代碼段：

movax,[100]

mov

bx,[104]addax,bx……

100:0//sum104:1//iPCmovax,[100]IRax03.1進(jìn)程的引入程序執(zhí)行的細(xì)節(jié)(1)代碼段：

movax,[100]

mov

bx,[104]addax,bx……

100:0//sum104:1//iPCmov

bx,[104]IRbx10ax3.1進(jìn)程的引入程序執(zhí)行的細(xì)節(jié)(2)代碼段：

movax,[100]

mov

bx,[104]addax,bx……

100:0//sum104:1//iPCaddax,bxIRbx10ax程序執(zhí)行的關(guān)鍵在于PC的變化!13.1進(jìn)程的引入問題2:計算機(jī)中只有一個程序在執(zhí)行嗎?用戶的需求：多個用戶共享一臺計算機(jī)單個用戶利用計算機(jī)同時做多個事情使得計算機(jī)必須能夠同時執(zhí)行多個程序！3.1進(jìn)程的引入因此，這不是一個應(yīng)不應(yīng)該的問題！問題2:計算機(jī)中只有一個程序在執(zhí)行嗎?3.1進(jìn)程的引入問題3:計算機(jī)系統(tǒng)的基本特征?CPU的速度相比其他設(shè)備要快的多!中斷技術(shù)、DMA技術(shù)可以使I/O等設(shè)備工作過程幾乎脫離CPU的干預(yù)！根據(jù)I/O設(shè)備的特性，完全可以在此時讓出CPU給其他程序sum（等待I/O）(等待I/O)sum（等待I/O）（等待I/O）其他程序(等待)(等待)計算機(jī)可以同時在執(zhí)行多個程序(交替執(zhí)行)!

3.1進(jìn)程的引入問題4:一個程序vs.多個程序，效率？一次執(zhí)行

一個程序：AB101520304025CPUDEV13545DEV1CPUCPUDEV2CPUDEV2DEV2CPU一次一個程序多個程序CPU利用率40/80=50%40/45=89%DEV1利用率15/80=18.75%15/45=33%DEV2利用率25/80=31.25%25/45=56%

B

DEV2CPU

DEV1

DEV2

CPU

5060

70

80

65CPU

DEV1

DEV2

CPU

CPU

A10

15

20

3040多個程序

并發(fā)執(zhí)行：3.1進(jìn)程的引入問題5:并發(fā)過程程序如何切換？并發(fā)：一個CPU上交替的“同時”執(zhí)行多個程序

并發(fā)是指同時出發(fā)，交替執(zhí)行(和并行不同)CPU1CPU2CPU1CPU2時間

movax,[100]

mov

bx,[104]addax,bx……

程序1

movax,10

mov

bx,10addax,bx……

程序2PCPC切換指程序2在CPU上執(zhí)行3.1進(jìn)程的引入CPUCPU1問題5:并發(fā)過程程序如何切換？先保存執(zhí)行現(xiàn)場，后切換執(zhí)行現(xiàn)場!

movax,[100]

mov

bx,[104]addax,bx……

程序1

movax,10

mov

bx,10addax,bx……

程序2PCPC切換CPU2內(nèi)存物理CPUCPU2ax1010bxPCPC切換CPU1ax

11bxPCCPU1CPU2CPU13.1進(jìn)程的引入邏輯CPU3.1進(jìn)程的引入為什么要引入進(jìn)程?

需要一種統(tǒng)一的方法監(jiān)視、管理、控制處理器

中不同程序的動態(tài)執(zhí)行過程，“進(jìn)程”的概念

被引入！總結(jié)前面的內(nèi)容，可以看到：多道程序并發(fā)執(zhí)行是提高系統(tǒng)資源利用率(特

別是CPU)的有效途徑；多道程序競爭CPU進(jìn)行輪換執(zhí)行是提高多用戶

響應(yīng)速度的有效方法；計算機(jī)的客觀實(shí)際支持多道程序并發(fā)的實(shí)現(xiàn)；但“作業(yè)”、“程序”等概念不能有效描述

程序動態(tài)輪換執(zhí)行的過程；……3.2進(jìn)程的概念Multics–1964年，Bell實(shí)驗(yàn)室、MIT與GE公司共同開發(fā)Multics的設(shè)計者首次提出并使用了“進(jìn)程”的概念進(jìn)程概念讓許多事情豁然開朗!用TaskManager演示進(jìn)程的表述進(jìn)程沒有嚴(yán)格的定義，但可以通過不同的角度去描述：一個正在執(zhí)行的程序（Program）計算機(jī)中正在運(yùn)行的程序的一個實(shí)例（Instance）可以分配給處理器并由處理器執(zhí)行的一個實(shí)體（Entity）由一個順序執(zhí)行的代碼段、一個當(dāng)前狀態(tài)和一組相關(guān)系統(tǒng)

資源所刻畫的活動單元（Unit）日常生活中“進(jìn)程”例子：裝修工程：裝修隊同時承接N個家庭房屋裝修工程下棋過程：一對N的“車輪大戰(zhàn)”每盤對弈棋局

--一個進(jìn)程聶衛(wèi)平

--CPU3.2進(jìn)程的概念每個裝修工程

--一個進(jìn)程裝修隊

--CPU3.2進(jìn)程的概念（1）動態(tài)性動態(tài)特性表現(xiàn)在它因創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，因

得不到資源而暫停執(zhí)行，最后因完成或撤銷而消亡

（進(jìn)程生命周期）（2）并發(fā)性引入進(jìn)程的目的就是為了使多個程序并發(fā)執(zhí)行，以提

高資源利用率（主要CPU）（3）獨(dú)立性進(jìn)程是一個能獨(dú)立運(yùn)行的基本單位，也是系統(tǒng)進(jìn)行資

源分配和調(diào)度的基本單位（4）異步性進(jìn)程以各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)（5）靜態(tài)性（可構(gòu)造性、結(jié)構(gòu)特征）

進(jìn)程結(jié)構(gòu)=程序段+數(shù)據(jù)段+進(jìn)程控制信息進(jìn)程的5個基本特征：3.3進(jìn)程的描述與表達(dá)如何描述/表達(dá)進(jìn)程？進(jìn)程狀態(tài)及其變遷進(jìn)程的數(shù)據(jù)結(jié)構(gòu)進(jìn)程控制塊3.3進(jìn)程的描述與表達(dá)3.3.1進(jìn)程狀態(tài)及其變遷3.3進(jìn)程的描述與表達(dá)3.3.1進(jìn)程狀態(tài)及其變遷50008000120005001

8001120015002

8002120025003800312003500480041200450058005120055006800612006500712007500812008500912009501012010501112011(a)進(jìn)程A軌跡

(b)進(jìn)程B軌跡

(c)進(jìn)程C軌跡

5000=進(jìn)程A的程序起始地址8000=進(jìn)程B的程序起始地址12000=進(jìn)程C的程序起始地址進(jìn)程軌跡--

進(jìn)程執(zhí)行的指

令序列3.3進(jìn)程的描述與表達(dá)3.3.1進(jìn)程狀態(tài)及其變遷進(jìn)程A執(zhí)行進(jìn)程C執(zhí)行進(jìn)程A執(zhí)行（續(xù)）進(jìn)程C執(zhí)行（續(xù)）時間片到時間片到時間片到調(diào)度程序調(diào)度程序調(diào)度程序調(diào)度程序I/O請求等待時間片到進(jìn)程ABC組合軌跡

--CPU調(diào)度軌跡進(jìn)程B執(zhí)行I/O請求等待I/O請求等待時間片到時間片到調(diào)度程序時間片到調(diào)度程序3.3進(jìn)程的描述與表達(dá)進(jìn)程執(zhí)行時的間斷性，決定了進(jìn)程可能具有多種狀態(tài)運(yùn)行中的進(jìn)程至少具有以下三種基本狀態(tài)（1）就緒狀態(tài)

–在某時刻，進(jìn)程已獲得除處理機(jī)以外的所有

資源，一旦分到了處理機(jī)就可以立即執(zhí)行（2）運(yùn)行狀態(tài)

–進(jìn)程已經(jīng)獲得必要資源，并占有處理機(jī)運(yùn)行（3）阻塞狀態(tài)

–正在執(zhí)行的進(jìn)程，由于發(fā)生某事件而暫時無

法執(zhí)行下去進(jìn)程是有生命周期的，它的狀態(tài)隨著自身的推進(jìn)和外界條件的變化而發(fā)生變化可以用一個進(jìn)程狀態(tài)變化圖來說明系統(tǒng)中每個進(jìn)程可能具備的狀態(tài)，以及這些狀態(tài)發(fā)生變化的可能原因3.3.1進(jìn)程狀態(tài)及其變遷3.3進(jìn)程的描述與表達(dá)進(jìn)程三狀態(tài)變遷圖運(yùn)行態(tài)就緒態(tài)阻塞態(tài)進(jìn)程調(diào)度時間片用完事件已發(fā)生等待事件發(fā)生進(jìn)程狀態(tài)變化圖（三狀態(tài)）3.3進(jìn)程的描述與表達(dá)進(jìn)程三狀態(tài)變遷圖進(jìn)程狀態(tài)變化序列圖舉例（三狀態(tài)）進(jìn)程A進(jìn)程B進(jìn)程C分派程序運(yùn)行態(tài)就緒態(tài)阻塞態(tài)3.3進(jìn)程的描述與表達(dá)進(jìn)程五狀態(tài)變遷圖允許進(jìn)入就緒阻塞運(yùn)行進(jìn)程調(diào)度時間片用完事件已發(fā)生等待事件發(fā)生進(jìn)程狀態(tài)變化圖（五狀態(tài)）新建退出完成/終止新建狀態(tài)

–至少建立PCB，但進(jìn)程相關(guān)的其他內(nèi)容可能未調(diào)入主存退出狀態(tài)

–進(jìn)程已經(jīng)終止，但資源等待父進(jìn)程或系統(tǒng)回收事件已發(fā)生換入換出換入換出允許進(jìn)入直接換出就緒掛起阻塞掛起3.3進(jìn)程的描述與表達(dá)進(jìn)程七狀態(tài)變遷圖允許進(jìn)入就緒阻塞運(yùn)行進(jìn)程調(diào)度時間片用完事件已發(fā)生等待事件發(fā)生進(jìn)程狀態(tài)變化圖（七狀態(tài)）新建退出完成/終止中斷返回掛起狀態(tài)

–引入主存←→外存的交換機(jī)制，虛擬存儲管理的基礎(chǔ)思考：必須換出先換誰？允許換入先換誰？3.3進(jìn)程的描述與表達(dá)對單個進(jìn)程，操作系統(tǒng)建立“進(jìn)程映像”進(jìn)行描述和表達(dá)，必須包含3部分內(nèi)容：一段可執(zhí)行的程序（代碼）程序所需的相關(guān)數(shù)據(jù)（變量、

棧、堆、緩沖區(qū)等）程序執(zhí)行的上下文環(huán)境（PCB）對所有進(jìn)程的管理，操作系統(tǒng)建立特定數(shù)據(jù)結(jié)構(gòu)：進(jìn)程索引表–進(jìn)程目錄進(jìn)程映像存儲區(qū)進(jìn)程鏈表隊列上下文數(shù)據(jù)程序（代碼）進(jìn)程A3.3.2進(jìn)程的數(shù)據(jù)結(jié)構(gòu)3.3進(jìn)程的描述與表達(dá)上下文數(shù)據(jù)程序（代碼）進(jìn)程A上下文數(shù)據(jù)程序（代碼）進(jìn)程Bbhij進(jìn)程表主存儲器bhi…其他寄存器基址寄存器界限寄存器程序計數(shù)器PC進(jìn)程索引處理器寄存器組典型的全局進(jìn)程數(shù)據(jù)結(jié)構(gòu)3.3進(jìn)程的描述與表達(dá)進(jìn)程控制塊PCB：程序執(zhí)行的上下文環(huán)境為了描述和控制進(jìn)程的運(yùn)行，系統(tǒng)為每個進(jìn)程定義了一個數(shù)據(jù)結(jié)構(gòu)—進(jìn)程控制塊（PCB）系統(tǒng)創(chuàng)建一個進(jìn)程，就是由系統(tǒng)為某個程序（包含數(shù)據(jù)段）設(shè)置一個PCB；進(jìn)程執(zhí)行完成時，由系統(tǒng)收回其PCB，該進(jìn)程便消亡了系統(tǒng)將根據(jù)PCB而感知進(jìn)程的存在，故PCB是進(jìn)程存在的唯一標(biāo)志通過PCB可以訪問到進(jìn)程的所有信息3.3.3進(jìn)程控制塊PCBPCB–ProcessControlBlock，是一個線性的數(shù)據(jù)結(jié)構(gòu)

用來描述和記錄進(jìn)程的動態(tài)變化信息，是進(jìn)程的靈魂3.3進(jìn)程的描述與表達(dá)進(jìn)程控制塊PCB的內(nèi)容：不同操作系統(tǒng)中，PCB的內(nèi)容不盡相同，但通常包括：（1）進(jìn)程標(biāo)識符－

確認(rèn)進(jìn)程的唯一標(biāo)識(PID)（2）進(jìn)程當(dāng)前狀態(tài)－

進(jìn)程調(diào)度程序分配處理機(jī)的依據(jù)（3）進(jìn)程隊列指針－

記錄PCB鏈表中下一個PCB的地址（4）程序地址范圍－

開始地址與結(jié)束地址（地址空間）（5）進(jìn)程優(yōu)先級－

反映進(jìn)程要求CPU的緊迫程度（6）CPU現(xiàn)場保護(hù)區(qū)－

記錄讓出處理機(jī)時的CPU現(xiàn)場信息（7）通信信息－

記錄與其他的進(jìn)程的信息交換情況（8）家族聯(lián)系－

記錄父進(jìn)程的PID（9）占有資源清單－

打開文件列表、所需資源及已分配資源清單3.4進(jìn)程操作進(jìn)程操作的職責(zé)是對進(jìn)程生命周期中的狀態(tài)變遷實(shí)施有效的管理進(jìn)程操作的主要功能包括：進(jìn)程的創(chuàng)建進(jìn)程的撤銷進(jìn)程的阻塞進(jìn)程的喚醒進(jìn)程掛起等屬于進(jìn)程調(diào)度的事情進(jìn)程操作功能一般是由操作系統(tǒng)的內(nèi)核來實(shí)現(xiàn)的進(jìn)程操作功能是通過執(zhí)行各種原語來實(shí)現(xiàn)的

原語是由若干條機(jī)器指令構(gòu)成的，用于完成某一特定功能的一段

程序原語在執(zhí)行期間不可分割，所以原語操作具有原子性3.4進(jìn)程操作3.4.1進(jìn)程創(chuàng)建

進(jìn)程創(chuàng)建是由創(chuàng)建原語實(shí)現(xiàn)的當(dāng)需要進(jìn)程時，就可以建立一個新進(jìn)程被創(chuàng)建的進(jìn)程稱為子進(jìn)程，建立進(jìn)程的進(jìn)程稱為父進(jìn)程創(chuàng)建原語的主要功能是為被創(chuàng)建進(jìn)程形成一個PCB，并

填入相應(yīng)的初始值進(jìn)程創(chuàng)建主要操作過程：（1）先向系統(tǒng)申請一個空閑PCB結(jié)構(gòu)；（2）再根據(jù)父進(jìn)程所提供的參數(shù)將子進(jìn)程的PCB初始化；（3）將此PCB插入就緒隊列（或就緒掛起/創(chuàng)建隊列）；（4）最后返回一個進(jìn)程的標(biāo)識號。典型進(jìn)程創(chuàng)建系統(tǒng)調(diào)用fork()3.4進(jìn)程操作3.4.2進(jìn)程撤銷進(jìn)程撤銷是由撤銷原語實(shí)現(xiàn)的一個進(jìn)程在完成其任務(wù)后，應(yīng)予以撤銷，以便及時釋放

其所占用的各類資源撤銷操作可采用兩種撤銷策略：一種策略是只撤銷一個具有指定標(biāo)識符的進(jìn)程另一種策略是撤銷指定進(jìn)程及其子孫進(jìn)程3.4進(jìn)程操作3.4.2進(jìn)程撤銷進(jìn)程撤銷的主要操作過程：（1）先從PCB集合中找到被撤銷進(jìn)程的PCB；（2）若被撤銷進(jìn)程正處于運(yùn)行狀態(tài)，則應(yīng)立即停止該進(jìn)程

的執(zhí)行，設(shè)置調(diào)度標(biāo)志，以便進(jìn)程撤銷后將處理機(jī)會

給其他進(jìn)程；（3）對后一種撤銷策略，若被撤銷進(jìn)程有子孫進(jìn)程，還應(yīng)

將該進(jìn)程的子孫進(jìn)程予以撤銷；（4）對于被撤銷進(jìn)程所占有的資源，或者歸還給父進(jìn)程，

或者歸還給系統(tǒng)；（5）最后撤銷它的PCB典型進(jìn)程撤銷系統(tǒng)調(diào)用exit()3.4進(jìn)程操作3.4.3進(jìn)程阻塞與喚醒

阻塞原語的作用是將進(jìn)程由執(zhí)行狀態(tài)轉(zhuǎn)為阻塞狀態(tài)喚醒原語的作用則是將進(jìn)程由阻塞狀態(tài)變?yōu)榫途w狀態(tài)阻塞操作阻塞一個進(jìn)程的過程：（1）由于該進(jìn)程正處于執(zhí)行狀態(tài)，故應(yīng)先中斷處理機(jī)和保

存該進(jìn)程的CPU現(xiàn)場；（2）然后將該進(jìn)程插入到等待該事件的隊列中；（3）再從就緒進(jìn)程隊列中選擇一個進(jìn)程投入運(yùn)行對處于阻塞狀態(tài)的進(jìn)程，當(dāng)該進(jìn)程期待的事件出現(xiàn)或

完成時，由發(fā)現(xiàn)者進(jìn)程調(diào)用喚醒原語將阻塞進(jìn)程喚醒，使其進(jìn)入就緒狀態(tài)喚醒時機(jī)和喚醒者？典型進(jìn)程阻塞系統(tǒng)調(diào)用sleep()、wait()典型進(jìn)程喚醒系統(tǒng)調(diào)用wakeup()（P/V操作）3.4進(jìn)程操作3.4.3進(jìn)程阻塞與喚醒

注意：

（1）一個進(jìn)程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)，是該進(jìn)程自己

調(diào)用阻塞原語去完成的（2）而進(jìn)程由阻塞狀態(tài)到就緒狀態(tài)，是另一個發(fā)現(xiàn)者進(jìn)程

調(diào)用喚醒原語實(shí)現(xiàn)的，一般這個發(fā)現(xiàn)者進(jìn)程與被喚醒

進(jìn)程是合作的并發(fā)進(jìn)程（通過使用信號量的P/V操作）Linuxfork()3.4進(jìn)程操作intmain()

{

pid_t

pid;

pid=fork();/*forkachildprocess*/

if(pid<0)/*erroroccurred*/

{printf("Forkfailed!\n");

exit(-1);

}

elseif(pid==0)/*childprocess*/

{

execlp("/bin/ls",“l(fā)s",NULL);

}

else/*parentprocess*/

{wait(NULL);/*watingthechildprocesstocomplete*/

printf("Thechildprocesscomplete!\n");

exit(0);

}

}3.5進(jìn)程調(diào)度3.5.1進(jìn)程隊列為了管理和調(diào)度進(jìn)程，操作系統(tǒng)將具有相同屬性或特征的進(jìn)程保存到隊列數(shù)據(jù)結(jié)構(gòu)中—進(jìn)程隊列進(jìn)程隊列通常以鏈表隊列形式實(shí)現(xiàn)進(jìn)程隊列的元素是PCB（Linux稱Task_struct）進(jìn)程隊列的分類：按進(jìn)程狀態(tài)：就緒、阻塞、運(yùn)行、創(chuàng)建、終止按進(jìn)程等待的設(shè)備：磁盤、鍵盤按進(jìn)程等待的事件：鼠標(biāo)雙擊、鼠標(biāo)右鍵按進(jìn)程等待的信號量進(jìn)程鏈表隊列結(jié)構(gòu)運(yùn)行態(tài)就緒態(tài)阻塞態(tài)進(jìn)程控制塊…3.5進(jìn)程調(diào)度進(jìn)程隊列實(shí)現(xiàn)示意圖PCB1RegistersPCB6RegistersHeadTail磁盤等待隊列PCB4RegistersPCB8RegistersPCB7RegistersHeadTail就緒隊列3.5進(jìn)程調(diào)度3.5進(jìn)程調(diào)度單一的阻塞隊列允許進(jìn)入就緒隊列分派CPU釋放超時（時間片到）等待事件阻塞隊列事件發(fā)生3.5進(jìn)程調(diào)度多條阻塞隊列允許進(jìn)入就緒隊列分派CPU釋放超時（時間片到）事件1等待事件1隊列事件1發(fā)生事件2等待事件2隊列事件2發(fā)生事件n等待事件n隊列事件n發(fā)生···3.5進(jìn)程調(diào)度3.5.2調(diào)度程序調(diào)度種類：長期調(diào)度程序（作業(yè)調(diào)度程序）：

從磁盤緩沖池中選擇進(jìn)程；中期調(diào)度程序：

內(nèi)外存“交換”進(jìn)程短期調(diào)度程序（CPU調(diào)度程序）：

選擇就緒態(tài)的進(jìn)程并為其分配CPU調(diào)度情況1：因等待某些事件而讓出CPUsum(等待文件輸出)(等待文件輸出)PCB1RegistersPCB6RegistersHeadTail磁盤等待隊列PCB4RegistersPCB8RegistersPCB7RegistersHeadTail就緒隊列物理CPUPCB6RegistersPCB4Registers3.5進(jìn)程調(diào)度PCB4RegistersPCB8RegistersPCB7RegistersHeadTail就緒隊列物理CPUPCB7RegistersPCB4Registers調(diào)度情況2：規(guī)定的時間片到了

調(diào)度情況3：出現(xiàn)了優(yōu)先級更高的進(jìn)程3.5進(jìn)程調(diào)度PCB4RegistersPCB8RegistersPCB7RegistersHeadTail就緒隊列物理CPUPCB7RegistersPCB4Registers調(diào)度情況4：進(jìn)程的任務(wù)完成了，自動終止退出