《計(jì)算機(jī)操作系統(tǒng)原理（第2版）》第3章 進(jìn)程管理

第三章進(jìn)程管理

3.1進(jìn)程的基本概念3.2進(jìn)程的描述3.3進(jìn)程狀態(tài)及其轉(zhuǎn)換3.4經(jīng)典控制3.5進(jìn)程互斥與同步3.6進(jìn)程間通信3.7線程的概念3.1進(jìn)程的基本概念3.1.1進(jìn)程的引入

1.程序的順序執(zhí)行及其特性僅當(dāng)前一操作(程序段)執(zhí)行完后，才能執(zhí)行后繼操作。例如，在進(jìn)行計(jì)算時(shí)，總須先輸入用戶的程序和數(shù)據(jù)，然后進(jìn)行計(jì)算，最后才能打印計(jì)算結(jié)果。

S1:a∶=x+y;

S2:b∶=a-5;

S3:c∶=b+1;程序順序執(zhí)行時(shí)的特征：順序性：(2)封閉性：(3)可再現(xiàn)性：2程序的并發(fā)執(zhí)行及其特征

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

在該例中存在下述前趨關(guān)系：

Ii→Ci，Ii→Ii+1,Ci→Pi,Ci→Ci+1，Pi→Pi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之間，可以并發(fā)執(zhí)行。對于具有下述四條語句的程序段：

S1:a∶=x+2

S2:b∶=y+4

S3:c∶=a+b

S4:d∶=c+b程序并發(fā)執(zhí)行時(shí)的特征：間斷性2)失去封閉性3)不可再現(xiàn)性

例如，有兩個(gè)循環(huán)程序A和B，它們共享一個(gè)變量N。程序A每執(zhí)行一次時(shí)，都要做N∶=N+1操作；程序B每執(zhí)行一次時(shí)，都要執(zhí)行Print(N)操作，然后再將N置成“0”。程序A和B以不同的速度運(yùn)行。

(1)N∶=N+1在Print(N)和N∶=0之前，此時(shí)得到的N值分別為n+1,n+1,0。

(2)N∶=N+1在Print(N)和N∶=0之后，此時(shí)得到的N值分別為n,0,1。

(3)N∶=N+1在Print(N)和N∶=0之間，此時(shí)得到的N值分別為n,n+1,0。3進(jìn)程的引入

由于程序在順序執(zhí)行時(shí)具有順序性、封閉性和可再現(xiàn)性，使程序和其執(zhí)行過程之間存在一一對應(yīng)的關(guān)系，因此程序這個(gè)靜態(tài)概念完全可以用來代替程序執(zhí)行過程中這個(gè)動(dòng)態(tài)概念。但是，程序的并發(fā)執(zhí)行破壞了程序順序執(zhí)行的特性，并產(chǎn)生了一些新的特點(diǎn)，使程序這個(gè)靜態(tài)概念不足以描述程序的執(zhí)行過程。因此，需要引入一個(gè)新的概念來描述程序的并發(fā)執(zhí)行過程，這個(gè)新的概念就是“進(jìn)程”。3.1.2進(jìn)程的定義和特征1.進(jìn)程的定義

較典型的進(jìn)程定義有：

(1)進(jìn)程是程序的一次執(zhí)行。

(2)進(jìn)程是可以和別的計(jì)算并發(fā)執(zhí)行的計(jì)算。

(3)進(jìn)程可以定義為一個(gè)數(shù)據(jù)結(jié)構(gòu)以及能在其上執(zhí)行的一個(gè)程序。

(4)進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)所發(fā)生的活動(dòng)。

(5)進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。

在引入了進(jìn)程實(shí)體的概念后，我們可以把傳統(tǒng)OS中的進(jìn)程定義為：“進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位”。2.進(jìn)程的特征結(jié)構(gòu)特征

動(dòng)態(tài)性

并發(fā)性

獨(dú)立性

異步性3.進(jìn)程與程序的聯(lián)系和區(qū)別進(jìn)程是程序的一次執(zhí)行，屬于動(dòng)態(tài)概念；而程序僅是指令的有序集合，屬于靜態(tài)概念

進(jìn)程有一個(gè)生命周期，它的存在是暫時(shí)的；而程序的存在則是永久的。

一個(gè)進(jìn)程可以執(zhí)行一個(gè)或幾個(gè)程序，一個(gè)程序可產(chǎn)生多個(gè)進(jìn)程。3.2.1進(jìn)程控制塊

進(jìn)程控制塊(PCB)作為進(jìn)程實(shí)體的一個(gè)重要組成部分，包含了進(jìn)程的所有描述信息和控制信息，是系統(tǒng)對進(jìn)程實(shí)施管理的唯一依據(jù)和系統(tǒng)能夠感知到進(jìn)程存在的唯一標(biāo)識(shí)。進(jìn)程控制塊和進(jìn)程之間存在一一對應(yīng)的關(guān)系。當(dāng)系統(tǒng)創(chuàng)建一個(gè)進(jìn)程時(shí)，必須為其建立相應(yīng)的進(jìn)程控制塊；當(dāng)系統(tǒng)撤銷一個(gè)進(jìn)程時(shí)，又必須收回其進(jìn)程控制塊。由于進(jìn)程控制塊的重要性，幾乎所有的多道操作系統(tǒng)都是將其全部或部分駐留在內(nèi)存的。3.2進(jìn)程的描述

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

(1)進(jìn)程標(biāo)識(shí)符。進(jìn)程標(biāo)識(shí)符也稱為進(jìn)程進(jìn)程名或進(jìn)程內(nèi)部名，是操作系統(tǒng)為每一個(gè)進(jìn)程所賦予的唯一內(nèi)部標(biāo)識(shí)，通常是一個(gè)進(jìn)程的序號(hào)，不同進(jìn)程的標(biāo)識(shí)符不允許相同。系統(tǒng)每創(chuàng)建一個(gè)進(jìn)程時(shí)，都要給它分配一個(gè)空閑的進(jìn)程控制塊，并為之分配一個(gè)唯一的標(biāo)識(shí)符。

(2)用戶標(biāo)識(shí)符。用戶標(biāo)識(shí)符也稱為進(jìn)程用戶名或進(jìn)程外部名，是進(jìn)程創(chuàng)建者為了增強(qiáng)進(jìn)程名的可讀性為進(jìn)程提供的一個(gè)名字

(3)家族聯(lián)系。在樹狀結(jié)構(gòu)的進(jìn)程系統(tǒng)中，進(jìn)程之間存在家族關(guān)系。因此，其進(jìn)程控制塊中應(yīng)有相應(yīng)的項(xiàng)來描述它們之間的家族聯(lián)系。通常，進(jìn)程的家族聯(lián)系是通過一個(gè)進(jìn)程指向其父進(jìn)程或子進(jìn)程的指針來實(shí)現(xiàn)的。

在PCB中還存放一些與進(jìn)程調(diào)度和進(jìn)程對換有關(guān)的信息，包括：①進(jìn)程狀態(tài)，指明進(jìn)程的當(dāng)前狀態(tài)，作為進(jìn)程調(diào)度和對換時(shí)的依據(jù)；②進(jìn)程優(yōu)先級，用于描述進(jìn)程使用處理機(jī)的優(yōu)先級別的一個(gè)整數(shù)，優(yōu)先級高的進(jìn)程應(yīng)優(yōu)先獲得處理機(jī)；③進(jìn)程調(diào)度所需的其它信息，它們與所采用的進(jìn)程調(diào)度算法有關(guān)，比如，進(jìn)程已等待CPU的時(shí)間總和、進(jìn)程已執(zhí)行的時(shí)間總和等；④事件，是指進(jìn)程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所等待發(fā)生的事件，即阻塞原因。2.進(jìn)程調(diào)度信息

當(dāng)一個(gè)進(jìn)程因?yàn)槟硞€(gè)事件而不能在CPU上繼續(xù)執(zhí)行時(shí)，必須將自己的CPU現(xiàn)場信息保存在該進(jìn)程的進(jìn)程控制塊內(nèi)，以便其重新獲得CPU再次運(yùn)行時(shí)能夠恢復(fù)這些現(xiàn)場信息。通常這些被保護(hù)的CPU現(xiàn)場信息也稱為進(jìn)程上下文，主要包括：①通用寄存器信息。通用寄存器是用戶程序可以直接訪問的寄存器，包括數(shù)據(jù)寄存器和段寄存器。②程序狀態(tài)字(PSW)信息。PSW包含著程序的狀態(tài)信息，如條件碼、執(zhí)行方式、中斷屏蔽標(biāo)志等。③指令計(jì)數(shù)器(IC)信息。IC用于存放要訪問的下一條指令的地址。④用戶堆棧指針。用戶堆棧指針用于存放過程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地址。3.進(jìn)程上下文

進(jìn)程控制信息包括：①程序和數(shù)據(jù)的地址，是指進(jìn)程的程序和數(shù)據(jù)所在的內(nèi)存或外存地(首)址，以便再調(diào)度到該進(jìn)程執(zhí)行時(shí)，能從PCB中找到其程序和數(shù)據(jù)；②進(jìn)程同步和通信機(jī)制，指實(shí)現(xiàn)進(jìn)程同步和進(jìn)程通信時(shí)必需的機(jī)制，如消息隊(duì)列指針、信號(hào)量等，它們可能全部或部分地放在PCB中；③資源清單，是一張列出了除CPU以外的、進(jìn)程所需的全部資源及已經(jīng)分配到該進(jìn)程的資源的清單；④鏈接指針，它給出了本進(jìn)程(PCB)所在隊(duì)列中的下一個(gè)進(jìn)程的PCB的首地址。4.進(jìn)程控制信息3.2.2進(jìn)程控制塊的組織方式

1)鏈接方式2)索引方式3.3.1進(jìn)程的基本狀態(tài)就緒(Ready)狀態(tài)2)執(zhí)行狀態(tài)3)阻塞狀態(tài)3.3進(jìn)程的狀態(tài)及其轉(zhuǎn)換

3.3.2進(jìn)程基本狀態(tài)的轉(zhuǎn)換進(jìn)程狀態(tài)的轉(zhuǎn)換

活動(dòng)就緒→靜止就緒。(2)活動(dòng)阻塞→靜止阻塞。(3)靜止就緒→活動(dòng)就緒。(4)靜止阻塞→活動(dòng)阻塞。掛起狀態(tài)引入掛起狀態(tài)的原因

終端用戶的請求。(2)父進(jìn)程請求。(3)負(fù)荷調(diào)節(jié)的需要。(4)操作系統(tǒng)的需要。3.4進(jìn)程控制3.4.1進(jìn)程控制機(jī)制

為了實(shí)現(xiàn)對進(jìn)程的有效控制，操作系統(tǒng)必須建立一套控制機(jī)制，用于創(chuàng)建新進(jìn)程、撤銷執(zhí)行結(jié)束的進(jìn)程以及實(shí)現(xiàn)進(jìn)程狀態(tài)的轉(zhuǎn)換。這套機(jī)制屬于操作系統(tǒng)的內(nèi)核，常駐內(nèi)存，其執(zhí)行過程通常是由一些原語來完成的。原語(primitive)，是指由若干條機(jī)器指令組成的，用于完成一定功能的一個(gè)過程，并且該過程的執(zhí)行是不可打斷的。原語和一般過程的主要區(qū)別在于，原語是原子操作。原子操作是指該操作一個(gè)不可分割的基本單位，要么全都執(zhí)行，要么全不執(zhí)行，中間不允許插入任何其他操作。3.4.2進(jìn)程控制原語進(jìn)程創(chuàng)建原語

(1)進(jìn)程創(chuàng)建的原因和方式。在操作系統(tǒng)中，進(jìn)程的創(chuàng)建方式有兩種，一種是由系統(tǒng)創(chuàng)建，另一種是由父進(jìn)程創(chuàng)建。導(dǎo)致系統(tǒng)創(chuàng)建進(jìn)程的原因主要有3個(gè)：①作業(yè)調(diào)度②用戶登錄③提供服務(wù)由父進(jìn)程創(chuàng)建是指由執(zhí)行狀態(tài)的用戶進(jìn)程根據(jù)自身需要?jiǎng)?chuàng)建相應(yīng)的子進(jìn)程。在這種創(chuàng)建方式中，父進(jìn)程與其創(chuàng)建的子進(jìn)程之間存在隸屬關(guān)系和資源繼承關(guān)系，實(shí)際上是一種樹狀結(jié)構(gòu)的家族關(guān)系。

(2)進(jìn)程創(chuàng)建原語的描述。無論是由系統(tǒng)創(chuàng)建還是父進(jìn)程創(chuàng)建，創(chuàng)建者都需要調(diào)用進(jìn)程創(chuàng)建原語來創(chuàng)建新的進(jìn)程。進(jìn)程創(chuàng)建原語的主要工作是要為被創(chuàng)建的進(jìn)程建立一個(gè)進(jìn)程控制塊。2.進(jìn)程撤銷原語引起進(jìn)程撤銷的原因：①進(jìn)程正常終止②進(jìn)程異常終止③父進(jìn)程要求撤銷某一子孫進(jìn)程(2)進(jìn)程撤銷原語的描述。無論是哪種原因引起的進(jìn)程撤銷，都需要調(diào)用撤銷原語來完成撤銷工作。進(jìn)程撤銷原語的主要工作是釋放被撤銷進(jìn)程所占用的全部資源和進(jìn)程控制塊結(jié)構(gòu)本身。3.進(jìn)程阻塞原語進(jìn)程阻塞原語的作用是將一個(gè)進(jìn)程由執(zhí)行狀態(tài)變?yōu)樽枞麪顟B(tài)。當(dāng)一個(gè)處于執(zhí)行狀態(tài)的進(jìn)程需要等待某一事件發(fā)生時(shí)，自己調(diào)用阻塞原語阻塞自己，以便讓出CPU。進(jìn)程阻塞原語的主要處理過程是：首先中斷當(dāng)前進(jìn)程的CPU，并將其現(xiàn)場保存到進(jìn)程控制塊中；然后置該進(jìn)程狀態(tài)為“阻塞”，并插入阻塞隊(duì)列；隨后再激活進(jìn)程調(diào)度程序，重新分配CPU4.進(jìn)程喚醒原語進(jìn)程喚醒原語的作用是將一個(gè)處于阻塞狀態(tài)的進(jìn)程由阻塞狀態(tài)變?yōu)榫途w狀態(tài)。當(dāng)一個(gè)處于阻塞狀態(tài)的進(jìn)程所等待的事件發(fā)生時(shí)，將由發(fā)現(xiàn)者進(jìn)程調(diào)用進(jìn)程喚醒原語將其喚醒。進(jìn)程喚醒原語的主要操作是：將被喚醒進(jìn)程從阻塞隊(duì)列中移出，狀態(tài)改為“就緒”，并插入就緒隊(duì)列。3.5進(jìn)程互斥與同步3.5.1互斥的概念1.臨界資源臨界資源是指一次僅允許一個(gè)進(jìn)程使用的資源。在多進(jìn)程系統(tǒng)中，諸進(jìn)程之間除了競爭CPU外，還會(huì)競爭各種臨界資源。許多物理設(shè)備都屬于臨界資源，如輸入設(shè)備，打印機(jī)等。只有當(dāng)一個(gè)進(jìn)程使用完釋放后，才允許另一個(gè)進(jìn)程使用這些資源。

看一個(gè)例子，設(shè)有兩個(gè)并發(fā)進(jìn)程P1和P2共享變量count，進(jìn)程P1或P2的功能是每執(zhí)行完某些操作后，將count的值取出來加1，R1和R2是工作寄存器。當(dāng)P1和P2按如下順序執(zhí)行時(shí)：

P1：R1=count;R1=R1+1;count=R1;P2：R2=count;R2=R2+1;count=R2;

其結(jié)果使count增加了2，這是正確的。但由于P1和P2是兩個(gè)并發(fā)過程，如果對它們的執(zhí)行不加限制，則有可能出現(xiàn)不同的執(zhí)行順序。

例如按下面對順序執(zhí)行P1：R1=count;P2：R2=count;P1：R1=R1+1;count=R1;P2：R2=R2+1;count=R2;

雖然P1和P2都各自對count做了一次加1操作，但count的值最后卻僅增加了1。顯然，這種錯(cuò)誤與執(zhí)行順序有關(guān)，因此也稱其為與執(zhí)行順序有關(guān)的錯(cuò)誤。產(chǎn)生這種錯(cuò)誤的主要原因是沒有將變量count按臨界資源處理。2.臨界區(qū)