CH2-1進(jìn)程管理

1、1第第2 2章章 進(jìn)程管理進(jìn)程管理v 程序并發(fā)執(zhí)行時(shí)，產(chǎn)生了一些新特征，所以一般的程序是不能并程序并發(fā)執(zhí)行時(shí)，產(chǎn)生了一些新特征，所以一般的程序是不能并發(fā)執(zhí)行的。為了使程序在多道程序環(huán)境下能并發(fā)執(zhí)行，并能對(duì)并發(fā)發(fā)執(zhí)行的。為了使程序在多道程序環(huán)境下能并發(fā)執(zhí)行，并能對(duì)并發(fā)執(zhí)行的程序加以控制和描述，引入執(zhí)行的程序加以控制和描述，引入“進(jìn)程進(jìn)程”的概念。的概念。v 現(xiàn)在，現(xiàn)在，“進(jìn)程進(jìn)程”已經(jīng)成為操作系統(tǒng)乃至并發(fā)程序設(shè)計(jì)中最核心的已經(jīng)成為操作系統(tǒng)乃至并發(fā)程序設(shè)計(jì)中最核心的概念，它是對(duì)正在運(yùn)行的程序的抽象，操作系統(tǒng)的其他所有內(nèi)容都概念，它是對(duì)正在運(yùn)行的程序的抽象，操作系統(tǒng)的其他所有內(nèi)容都是圍繞著進(jìn)程展開的

2、。掌握進(jìn)程的概念對(duì)于理解操作系統(tǒng)的實(shí)質(zhì)以是圍繞著進(jìn)程展開的。掌握進(jìn)程的概念對(duì)于理解操作系統(tǒng)的實(shí)質(zhì)以及分析、設(shè)計(jì)操作系統(tǒng)都有非常重要的意義及分析、設(shè)計(jì)操作系統(tǒng)都有非常重要的意義 22.1 2.1 進(jìn)程的基本概念進(jìn)程的基本概念 2.1.1 2.1.1 程序的順序執(zhí)行及其特征程序的順序執(zhí)行及其特征 1. 1. 程序的順序執(zhí)行程序的順序執(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;(a) 程序的順序執(zhí)行(b) 三條語(yǔ)句的順序執(zhí)行I1C1P1I2C2P2S1S2S32. 2.

3、 程序順序執(zhí)行時(shí)的特征：程序順序執(zhí)行時(shí)的特征：順序性、封閉性、可再現(xiàn)性。32.1.2 2.1.2 前趨圖前趨圖 前趨圖(Precedence Graph)是一個(gè)有向無(wú)循環(huán)圖，用于描述進(jìn)程之間執(zhí)行的前后關(guān)系。圖中的每個(gè)結(jié)點(diǎn)可用于描述一個(gè)程序段或進(jìn)程，乃至一條語(yǔ)句；結(jié)點(diǎn)間的有向邊則用于表示兩個(gè)結(jié)點(diǎn)之間存在的前趨關(guān)系 “”。 =(Pi, Pj)|Pi must complete before Pj may start, 稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。在前趨圖中，把沒(méi)有前趨的結(jié)點(diǎn)稱為初始結(jié)點(diǎn)(Initial Node)，把沒(méi)有后繼的結(jié)點(diǎn)稱為終止結(jié)點(diǎn)(Final Node)。4 每個(gè)

4、結(jié)點(diǎn)還具有一個(gè)重量(Weight)，用于表示該結(jié)點(diǎn)所含有的程序量或結(jié)點(diǎn)的執(zhí)行時(shí)間。 IiCiPi和S1S2S3 P1P3P8P9P4P2P5P6P7S1S2S3(a) 具有九個(gè)結(jié)點(diǎn)的前趨圖(b) 具有循環(huán)的前趨圖52.1.3 2.1.3 程序的并發(fā)執(zhí)行及其特征程序的并發(fā)執(zhí)行及其特征 1. 1. 程序的并發(fā)執(zhí)行程序的并發(fā)執(zhí)行 圖 2-3 并發(fā)執(zhí)行時(shí)的前趨圖 P1P2P3P4I1I2I3I4C1C2C3C46在該例中存在下述前趨關(guān)系： IiCi，IiIi+1, CiPi, CiCi+1，PiPi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之間，可以并發(fā)執(zhí)行。 對(duì)于具有下

5、述四條語(yǔ)句的程序段： S1: a=x+2 S2: b=y+4 S3: c=a+b S4: d=c+b S1S2S3S42. 2. 程序并發(fā)執(zhí)行時(shí)的特征程序并發(fā)執(zhí)行時(shí)的特征 1) 間斷性 2) 失去封閉性 3) 不可再現(xiàn)性72.1.4 2.1.4 進(jìn)程的特征與狀態(tài)進(jìn)程的特征與狀態(tài) “進(jìn)程進(jìn)程”這一術(shù)語(yǔ)，在這一術(shù)語(yǔ)，在6060年代初期，首先在美國(guó)年代初期，首先在美國(guó)MITMIT的的MULTICSMULTICS系統(tǒng)系統(tǒng)和和IBMIBM公司的公司的CTSS/360CTSS/360系統(tǒng)中引入。其中能反映進(jìn)程實(shí)質(zhì)的定義有：系統(tǒng)中引入。其中能反映進(jìn)程實(shí)質(zhì)的定義有： （1 1）進(jìn)程是程序的一次執(zhí)行。）進(jìn)程是程

6、序的一次執(zhí)行。 （2 2）進(jìn)程是可以和其他計(jì)算并發(fā)執(zhí)行的計(jì)算。）進(jìn)程是可以和其他計(jì)算并發(fā)執(zhí)行的計(jì)算。 （3 3）進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理器上順序執(zhí)行時(shí)發(fā)生的活動(dòng)。）進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理器上順序執(zhí)行時(shí)發(fā)生的活動(dòng)。 （4 4）進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上的運(yùn)行過(guò)程，是系統(tǒng)進(jìn)行資源）進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上的運(yùn)行過(guò)程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。分配和調(diào)度的一個(gè)獨(dú)立單位。 （5 5）進(jìn)程是進(jìn)程實(shí)體的一次活動(dòng)。）進(jìn)程是進(jìn)程實(shí)體的一次活動(dòng)。 一、進(jìn)程的定義一、進(jìn)程的定義 8 我國(guó)我國(guó)19781978年在廬山召開的全國(guó)年在廬山召開的全國(guó)OSOS研討會(huì)上研討會(huì)上將將“進(jìn)程進(jìn)程”定義為

7、：定義為：進(jìn)程是一個(gè)具有一定獨(dú)立功能的程序關(guān)進(jìn)程是一個(gè)具有一定獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合的一次運(yùn)行活動(dòng)。于某個(gè)數(shù)據(jù)集合的一次運(yùn)行活動(dòng)。 一個(gè)程序?yàn)閷?shí)現(xiàn)不同的任務(wù)可以同時(shí)一個(gè)程序?yàn)閷?shí)現(xiàn)不同的任務(wù)可以同時(shí)有多次運(yùn)行活動(dòng)，每個(gè)運(yùn)行活動(dòng)分別有多次運(yùn)行活動(dòng)，每個(gè)運(yùn)行活動(dòng)分別作為不同的進(jìn)程作為不同的進(jìn)程9二、進(jìn)程的特性及與程序的區(qū)別二、進(jìn)程的特性及與程序的區(qū)別 1. 1. 進(jìn)程的五個(gè)特性進(jìn)程的五個(gè)特性 (1)(1)動(dòng)態(tài)性動(dòng)態(tài)性：生命周期。即它由系統(tǒng)“創(chuàng)建”而誕生，因被“調(diào)度”而執(zhí)行，因得不到資源而暫停，最后因被“撤消”而消亡。 (2)(2)并發(fā)性并發(fā)性：是指不同進(jìn)程的動(dòng)作在時(shí)間上可以重疊，即系統(tǒng)內(nèi)的多

8、個(gè)進(jìn)程是可以并發(fā)執(zhí)行的。 (3)(3)獨(dú)立性獨(dú)立性：指進(jìn)程實(shí)體是一個(gè)能獨(dú)立運(yùn)行的基本單位，同時(shí)也是系統(tǒng)中獨(dú)立獲得資源和獨(dú)立調(diào)動(dòng)的基本單位。 (4)(4)異步性異步性：指進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn) (5)(5)結(jié)構(gòu)特性結(jié)構(gòu)特性：從結(jié)構(gòu)上看，每個(gè)進(jìn)程都由程序段、數(shù)據(jù)段和一個(gè)PCB三部分組成。 2. 2. 進(jìn)程與程序的區(qū)別進(jìn)程與程序的區(qū)別 (1)(1)從定義上看，進(jìn)程是程序處理數(shù)據(jù)的過(guò)程，而程序是從定義上看，進(jìn)程是程序處理數(shù)據(jù)的過(guò)程，而程序是一組指令的有序集合；一組指令的有序集合； (2)(2)進(jìn)程具有動(dòng)態(tài)性、并發(fā)性、獨(dú)立性和異步性等，而程進(jìn)程具有動(dòng)態(tài)性、并發(fā)性、獨(dú)立性和異步性等，而程

9、序不具有這些特性；序不具有這些特性； (3)(3)從進(jìn)程結(jié)構(gòu)特性上看，它包含程序（以及數(shù)據(jù)和從進(jìn)程結(jié)構(gòu)特性上看，它包含程序（以及數(shù)據(jù)和PCBPCB）；）； (4)(4)進(jìn)程和程序并非一一對(duì)應(yīng)。進(jìn)程和程序并非一一對(duì)應(yīng)。 11 在操作系統(tǒng)中引入在操作系統(tǒng)中引入“進(jìn)程進(jìn)程”概念的主要目的是概念的主要目的是（ ）。）。 A. A. 改善用戶編程環(huán)境改善用戶編程環(huán)境 B. B. 描述程序動(dòng)態(tài)執(zhí)行過(guò)程的性質(zhì)描述程序動(dòng)態(tài)執(zhí)行過(guò)程的性質(zhì) C. C. 使程序與計(jì)算過(guò)程一一對(duì)應(yīng)使程序與計(jì)算過(guò)程一一對(duì)應(yīng) D. D. 提高程序的運(yùn)行速度提高程序的運(yùn)行速度12三、進(jìn)程的基本狀態(tài)及其轉(zhuǎn)換三、進(jìn)程的基本狀態(tài)及其轉(zhuǎn)換 1 1

10、進(jìn)程的三種基本狀態(tài)進(jìn)程的三種基本狀態(tài) （1 1）就緒（）就緒（ReadyReady）狀態(tài)：）狀態(tài)：當(dāng)進(jìn)程已分配到除當(dāng)進(jìn)程已分配到除CPUCPU以外的所有必要以外的所有必要的資源，只要能再獲得處理器，便可立即執(zhí)行的資源，只要能再獲得處理器，便可立即執(zhí)行 （2 2）執(zhí)行（）執(zhí)行（RunningRunning）狀態(tài)）狀態(tài)：當(dāng)進(jìn)程已獲得處理器，其程序正在處當(dāng)進(jìn)程已獲得處理器，其程序正在處理器上執(zhí)行，理器上執(zhí)行， （3 3）阻塞（）阻塞（BlockedBlocked）狀態(tài)：）狀態(tài)：正在執(zhí)行的進(jìn)程，由于等待某事件發(fā)正在執(zhí)行的進(jìn)程，由于等待某事件發(fā)生而無(wú)法執(zhí)行時(shí)，便放棄處理器而處于暫停狀態(tài)。生而無(wú)法執(zhí)行時(shí)，

11、便放棄處理器而處于暫停狀態(tài)。 在不少系統(tǒng)中，又增加了兩種基本狀態(tài)：在不少系統(tǒng)中，又增加了兩種基本狀態(tài)： 新建（新建（NewNew）狀態(tài)）狀態(tài) 終止（終止（TerminatedTerminated）狀態(tài)）狀態(tài) 13引入新建態(tài)和終止?fàn)顟B(tài)的原因：引入新建態(tài)和終止?fàn)顟B(tài)的原因： 由于由于OSOS在建立一個(gè)新進(jìn)程時(shí)，通常分為在建立一個(gè)新進(jìn)程時(shí)，通常分為2 2步：第一步是為步：第一步是為新登錄的用戶程序（分時(shí)系統(tǒng)）創(chuàng)建進(jìn)程，并為他分配新登錄的用戶程序（分時(shí)系統(tǒng)）創(chuàng)建進(jìn)程，并為他分配資源，此時(shí)進(jìn)程即處于資源，此時(shí)進(jìn)程即處于新建態(tài)新建態(tài)。第二步是把新創(chuàng)建的進(jìn)。第二步是把新創(chuàng)建的進(jìn)程送入就緒隊(duì)列，一旦進(jìn)程進(jìn)入就緒

12、隊(duì)列，它便由新建程送入就緒隊(duì)列，一旦進(jìn)程進(jìn)入就緒隊(duì)列，它便由新建態(tài)變?yōu)榫途w狀態(tài)。態(tài)變?yōu)榫途w狀態(tài)。 一個(gè)結(jié)束了的進(jìn)程，其退出系統(tǒng)的過(guò)程也分為兩步：第一個(gè)結(jié)束了的進(jìn)程，其退出系統(tǒng)的過(guò)程也分為兩步：第一步是將該進(jìn)程從就緒隊(duì)列中移出，使之成為一個(gè)不可一步是將該進(jìn)程從就緒隊(duì)列中移出，使之成為一個(gè)不可能再運(yùn)行的進(jìn)程，相應(yīng)的進(jìn)程處于能再運(yùn)行的進(jìn)程，相應(yīng)的進(jìn)程處于終止?fàn)顟B(tài)終止?fàn)顟B(tài)。此時(shí)系統(tǒng)。此時(shí)系統(tǒng)并不立即撤銷它，而是將它暫時(shí)留在系統(tǒng)中，以便其它并不立即撤銷它，而是將它暫時(shí)留在系統(tǒng)中，以便其它進(jìn)程去收集該進(jìn)程的有關(guān)信息。進(jìn)程去收集該進(jìn)程的有關(guān)信息。 14創(chuàng)建創(chuàng)建就緒就緒執(zhí)行執(zhí)行終止終止阻塞阻塞接納接納完成完成

13、I/OI/O完成完成或等待的或等待的事件發(fā)生事件發(fā)生I/OI/O請(qǐng)求或請(qǐng)求或等待某事件等待某事件2 2進(jìn)程三種基本狀態(tài)間的轉(zhuǎn)換進(jìn)程三種基本狀態(tài)間的轉(zhuǎn)換進(jìn)程調(diào)度進(jìn)程調(diào)度時(shí)間片完時(shí)間片完153.3.掛起狀態(tài)掛起狀態(tài) 在有的系統(tǒng)中，為了暫時(shí)緩和內(nèi)存的緊張狀態(tài)，或?yàn)榱苏{(diào)節(jié)系統(tǒng)負(fù)荷，又引入了掛起功能。即暫時(shí)掛起一部分進(jìn)程，把它們從內(nèi)存臨時(shí)換出到輔存，使它們暫時(shí)和系統(tǒng)脫離聯(lián)系，起到平滑系統(tǒng)操作負(fù)荷的目的。 這樣，就需要把進(jìn)程的就緒狀態(tài)進(jìn)一步細(xì)分為活動(dòng)就緒活動(dòng)就緒狀態(tài)狀態(tài)（未被掛起的就緒進(jìn)程）和靜止就緒狀態(tài)靜止就緒狀態(tài)（被掛起的就緒進(jìn)程）兩種。把進(jìn)程的阻塞狀態(tài)也細(xì)分為活動(dòng)活動(dòng)阻塞狀態(tài)阻塞狀態(tài)（未被掛起的阻塞

14、進(jìn)程）和靜止阻塞狀態(tài)靜止阻塞狀態(tài)（被掛起的阻塞進(jìn)程）。 16活動(dòng)就緒靜止就緒執(zhí)行掛起激活釋放掛起活動(dòng)阻塞靜止阻塞掛起激活釋放請(qǐng)求I/O具有掛起狀態(tài)的進(jìn)程狀態(tài)轉(zhuǎn)換圖具有掛起狀態(tài)的進(jìn)程狀態(tài)轉(zhuǎn)換圖172.1.5 2.1.5 進(jìn)程控制塊進(jìn)程控制塊PCBPCB PCB PCB ( Process Control Block )( Process Control Block )是系統(tǒng)為了描述和控制進(jìn)是系統(tǒng)為了描述和控制進(jìn)程的運(yùn)行而為進(jìn)程定義的一種數(shù)據(jù)結(jié)構(gòu)。程的運(yùn)行而為進(jìn)程定義的一種數(shù)據(jù)結(jié)構(gòu)。 它是進(jìn)程實(shí)體的一部分，它是進(jìn)程實(shí)體的一部分，是進(jìn)程存在的唯一標(biāo)志是進(jìn)程存在的唯一標(biāo)志，也是，也是操作系統(tǒng)中最重要的

15、結(jié)構(gòu)體類型的數(shù)據(jù)結(jié)構(gòu)。操作系統(tǒng)中最重要的結(jié)構(gòu)體類型的數(shù)據(jù)結(jié)構(gòu)。 PCBPCB中存放著操作系統(tǒng)所需的用于描述進(jìn)程的當(dāng)前情況中存放著操作系統(tǒng)所需的用于描述進(jìn)程的當(dāng)前情況以及控制進(jìn)程運(yùn)行的全部信息。以及控制進(jìn)程運(yùn)行的全部信息。181 1PCBPCB的作用的作用（1 1）標(biāo)識(shí)進(jìn)程的存在：標(biāo)識(shí)進(jìn)程的存在：系統(tǒng)創(chuàng)建進(jìn)程時(shí)，就為之創(chuàng)建一個(gè)系統(tǒng)創(chuàng)建進(jìn)程時(shí)，就為之創(chuàng)建一個(gè)PCBPCB；進(jìn)；進(jìn)程結(jié)束時(shí)，系統(tǒng)又回收其程結(jié)束時(shí)，系統(tǒng)又回收其PCBPCB，進(jìn)程便隨之消亡，進(jìn)程便隨之消亡。 （2 2）為系統(tǒng)提供可并發(fā)執(zhí)行的獨(dú)立單位為系統(tǒng)提供可并發(fā)執(zhí)行的獨(dú)立單位：PCBPCB使一個(gè)在多道程使一個(gè)在多道程序環(huán)境下不能獨(dú)立運(yùn)行

16、的程序成為一個(gè)能獨(dú)立運(yùn)行的基本單位，一個(gè)序環(huán)境下不能獨(dú)立運(yùn)行的程序成為一個(gè)能獨(dú)立運(yùn)行的基本單位，一個(gè)能與其他進(jìn)程并發(fā)執(zhí)行的進(jìn)程。沒(méi)有為之建立能與其他進(jìn)程并發(fā)執(zhí)行的進(jìn)程。沒(méi)有為之建立PCBPCB的程序是不能并發(fā)的程序是不能并發(fā)執(zhí)行的。執(zhí)行的。 （3 3）為系統(tǒng)控制和管理進(jìn)程提供所需的一切信息為系統(tǒng)控制和管理進(jìn)程提供所需的一切信息。 192 2PCBPCB中的信息中的信息 （1 1）進(jìn)程標(biāo)識(shí)符）進(jìn)程標(biāo)識(shí)符( (內(nèi)部：數(shù)字，系統(tǒng)；外部：字符，內(nèi)部：數(shù)字，系統(tǒng)；外部：字符， 用戶用戶) )： （2 2）處理器狀態(tài)）處理器狀態(tài)：通用寄存器、指令計(jì)數(shù)器、通用寄存器、指令計(jì)數(shù)器、PSWPSW，用戶棧指針；用

17、戶棧指針； （3 3）進(jìn)程調(diào)度信息：）進(jìn)程調(diào)度信息：進(jìn)程的現(xiàn)行狀態(tài)、進(jìn)程優(yōu)先級(jí)、進(jìn)程的現(xiàn)行狀態(tài)、進(jìn)程優(yōu)先級(jí)、 與進(jìn)程有關(guān)的其他信息、事件即阻塞原因；與進(jìn)程有關(guān)的其他信息、事件即阻塞原因； （4 4）進(jìn)程控制信息：）進(jìn)程控制信息：進(jìn)程相應(yīng)的程序和數(shù)據(jù)地址：進(jìn)程相應(yīng)的程序和數(shù)據(jù)地址： 進(jìn)程同步與通信機(jī)制：進(jìn)程資源清單：進(jìn)程所進(jìn)程同步與通信機(jī)制：進(jìn)程資源清單：進(jìn)程所在在PCBPCB的鏈接字的鏈接字 。 203.PCB3.PCB的組織方式的組織方式 PCBPCB的組織方式指的是把具有相同狀態(tài)的若干的組織方式指的是把具有相同狀態(tài)的若干進(jìn)程按照某種原則適當(dāng)組織在一起的一種形式。進(jìn)程按照某種原則適當(dāng)組織在一

18、起的一種形式。 因?yàn)橐驗(yàn)镻CBPCB是系統(tǒng)中最重要也是被頻繁訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)，是系統(tǒng)中最重要也是被頻繁訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)，系統(tǒng)中的許多模塊，如調(diào)度程序、資源分配程序、中斷系統(tǒng)中的許多模塊，如調(diào)度程序、資源分配程序、中斷處理程序以及監(jiān)督和分析程序等，特別是運(yùn)行頻率很高處理程序以及監(jiān)督和分析程序等，特別是運(yùn)行頻率很高的進(jìn)程分派程序，都要對(duì)它進(jìn)行讀或?qū)懖僮?，所以的進(jìn)程分派程序，都要對(duì)它進(jìn)行讀或?qū)懖僮?，所以PCBPCB常常駐內(nèi)存的系統(tǒng)區(qū)中，系統(tǒng)將所有的駐內(nèi)存的系統(tǒng)區(qū)中，系統(tǒng)將所有的PCBPCB以數(shù)組形式連續(xù)存以數(shù)組形式連續(xù)存放組織成若干個(gè)鏈表（或隊(duì)列），存放在操作系統(tǒng)中專放組織成若干個(gè)鏈表（或隊(duì)列），存放在

19、操作系統(tǒng)中專門開辟的門開辟的PCBPCB區(qū)內(nèi)。區(qū)內(nèi)。 21空閑空閑PCB隊(duì)列頭指針隊(duì)列頭指針阻塞進(jìn)程隊(duì)列頭指針阻塞進(jìn)程隊(duì)列頭指針就緒進(jìn)程隊(duì)列頭指針就緒進(jìn)程隊(duì)列頭指針執(zhí)行進(jìn)程指針執(zhí)行進(jìn)程指針PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9430879015.1 1）鏈接方式）鏈接方式 系統(tǒng)按照進(jìn)程的狀態(tài)將進(jìn)程的系統(tǒng)按照進(jìn)程的狀態(tài)將進(jìn)程的PCBPCB組組成隊(duì)列，將同一狀態(tài)的成隊(duì)列，將同一狀態(tài)的PCBPCB用鏈接字用鏈接字鏈接成一個(gè)隊(duì)列，從而形成就緒隊(duì)鏈接成一個(gè)隊(duì)列，從而形成就緒隊(duì)列、阻塞隊(duì)列、運(yùn)行隊(duì)列等。列、阻塞隊(duì)列、運(yùn)行隊(duì)列等。 222) 2) 索引方式：索引方式：系統(tǒng)按

20、照進(jìn)程的狀態(tài)分別建立就緒索引表、阻塞索系統(tǒng)按照進(jìn)程的狀態(tài)分別建立就緒索引表、阻塞索 引表等。引表等。 執(zhí)行指針就緒索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7阻塞索引表就緒表指針阻塞表指針3) 3) 線性表方式線性表方式 不論進(jìn)程的狀態(tài)如何，將所有的不論進(jìn)程的狀態(tài)如何，將所有的PCBPCB連續(xù)地存放在內(nèi)存的系統(tǒng)區(qū)。連續(xù)地存放在內(nèi)存的系統(tǒng)區(qū)。這種方式適用于系統(tǒng)中進(jìn)程數(shù)目不多的情況。這種方式適用于系統(tǒng)中進(jìn)程數(shù)目不多的情況。232.2 2.2 進(jìn)程控制進(jìn)程控制v 進(jìn)程控制是進(jìn)程管理中最基本的功能；進(jìn)程控制是進(jìn)程管理中最基本的功能；v 進(jìn)程控制一般是由進(jìn)程控制一般是由OSOS的內(nèi)核來(lái)

21、實(shí)現(xiàn)的。的內(nèi)核來(lái)實(shí)現(xiàn)的。v 原語(yǔ)操作：原語(yǔ)操作： 本身是由若干條指令構(gòu)成、用于完成特定功能的一個(gè)過(guò)程。本身是由若干條指令構(gòu)成、用于完成特定功能的一個(gè)過(guò)程。為了保證操作的正確性，原語(yǔ)在執(zhí)行期間是不允許分割的，也就是為了保證操作的正確性，原語(yǔ)在執(zhí)行期間是不允許分割的，也就是說(shuō)，原語(yǔ)的執(zhí)行不能被中斷。說(shuō)，原語(yǔ)的執(zhí)行不能被中斷。 ：一個(gè)操作中的所有動(dòng)作。與一般過(guò)程的區(qū)別：要么全：一個(gè)操作中的所有動(dòng)作。與一般過(guò)程的區(qū)別：要么全作，要么全不作。即：原子操作是不可分割的，在管態(tài)下執(zhí)行，常作，要么全不作。即：原子操作是不可分割的，在管態(tài)下執(zhí)行，常駐內(nèi)存。駐內(nèi)存。 原語(yǔ)的作用是為了實(shí)現(xiàn)進(jìn)程的通信和控制，習(xí)題對(duì)進(jìn)

22、原語(yǔ)的作用是為了實(shí)現(xiàn)進(jìn)程的通信和控制，習(xí)題對(duì)進(jìn)程的控制如不適用原語(yǔ)，就會(huì)造成其這臺(tái)的不確定性，程的控制如不適用原語(yǔ)，就會(huì)造成其這臺(tái)的不確定性，從而達(dá)不到進(jìn)程控制的目的。從而達(dá)不到進(jìn)程控制的目的。241.進(jìn)程創(chuàng)建原語(yǔ)Creat()引起創(chuàng)建進(jìn)程的事件：引起創(chuàng)建進(jìn)程的事件： 用戶登錄用戶登錄 作業(yè)調(diào)度作業(yè)調(diào)度 提供服務(wù)提供服務(wù) 應(yīng)用請(qǐng)求應(yīng)用請(qǐng)求（進(jìn)程自身創(chuàng)建）（進(jìn)程自身創(chuàng)建）進(jìn)程創(chuàng)建的主要步驟：進(jìn)程創(chuàng)建的主要步驟： 申請(qǐng)空白申請(qǐng)空白PCBPCB 為新進(jìn)程分配資源為新進(jìn)程分配資源 初始化初始化PCBPCB的內(nèi)容的內(nèi)容 將新進(jìn)程插入就緒隊(duì)列將新進(jìn)程插入就緒隊(duì)列系統(tǒng)內(nèi)核系統(tǒng)內(nèi)核創(chuàng)建創(chuàng)建252.進(jìn)程撤銷原語(yǔ)

23、Terminate()引起撤銷進(jìn)程的事件：引起撤銷進(jìn)程的事件： 正常結(jié)束正常結(jié)束 異常結(jié)束異常結(jié)束 外界干擾外界干擾進(jìn)程撤銷的過(guò)程：進(jìn)程撤銷的過(guò)程： 檢索進(jìn)程當(dāng)前的狀態(tài)，結(jié)檢索進(jìn)程當(dāng)前的狀態(tài)，結(jié)束并置調(diào)度標(biāo)志，撤銷其束并置調(diào)度標(biāo)志，撤銷其所有的子進(jìn)程，歸還資源，所有的子進(jìn)程，歸還資源，移出隊(duì)列。移出隊(duì)列。v應(yīng)由父進(jìn)程調(diào)用進(jìn)程撤銷原語(yǔ)來(lái)撤銷，以便及時(shí)的釋放其應(yīng)由父進(jìn)程調(diào)用進(jìn)程撤銷原語(yǔ)來(lái)撤銷，以便及時(shí)的釋放其所占的資源。所占的資源。263.進(jìn)程阻塞原語(yǔ)Block()引起進(jìn)程阻塞的事件：引起進(jìn)程阻塞的事件： 請(qǐng)求系統(tǒng)服務(wù)請(qǐng)求系統(tǒng)服務(wù) 啟動(dòng)某種操作啟動(dòng)某種操作 新數(shù)據(jù)尚未到達(dá)新數(shù)據(jù)尚未到達(dá) 無(wú)新工作可

24、作無(wú)新工作可作進(jìn)程堵塞的過(guò)程：進(jìn)程堵塞的過(guò)程： 發(fā)現(xiàn)堵塞事件，調(diào)用阻塞發(fā)現(xiàn)堵塞事件，調(diào)用阻塞原語(yǔ)把自己阻塞，停止進(jìn)原語(yǔ)把自己阻塞，停止進(jìn)程的執(zhí)行，修改程的執(zhí)行，修改PCBPCB的的，將其插入到自己，將其插入到自己的堵塞隊(duì)列。最后轉(zhuǎn)調(diào)度的堵塞隊(duì)列。最后轉(zhuǎn)調(diào)度程序，將處理器分配給另程序，將處理器分配給另一個(gè)就緒進(jìn)程一個(gè)就緒進(jìn)程。v進(jìn)程的阻塞是進(jìn)程自身的一進(jìn)程的阻塞是進(jìn)程自身的一種主動(dòng)行為種主動(dòng)行為274.進(jìn)程喚醒原語(yǔ)Wakeup()引起進(jìn)程喚醒的事件：引起進(jìn)程喚醒的事件： 當(dāng)被阻塞進(jìn)程所期待的事當(dāng)被阻塞進(jìn)程所期待的事件出現(xiàn)時(shí)，或者所期待的件出現(xiàn)時(shí)，或者所期待的數(shù)據(jù)已經(jīng)到達(dá)。由該有關(guān)數(shù)據(jù)已經(jīng)到達(dá)。由

25、該有關(guān)進(jìn)程調(diào)用進(jìn)程喚醒原語(yǔ)，進(jìn)程調(diào)用進(jìn)程喚醒原語(yǔ)，將等待該資源而阻塞的一將等待該資源而阻塞的一個(gè)進(jìn)程喚醒成個(gè)進(jìn)程喚醒成進(jìn)程喚醒的過(guò)程：進(jìn)程喚醒的過(guò)程： 把被阻塞進(jìn)程從等待該把被阻塞進(jìn)程從等待該事件的阻塞隊(duì)列中移出，事件的阻塞隊(duì)列中移出，將其將其PCBPCB的現(xiàn)行狀態(tài)，由的現(xiàn)行狀態(tài)，由阻塞改為就緒，再將該阻塞改為就緒，再將該進(jìn)程插入到進(jìn)程插入到PCBPCB就緒隊(duì)列就緒隊(duì)列中。中。285.掛起原語(yǔ)Suspend( ): 當(dāng)出現(xiàn)了引起掛起的事件時(shí)，如為了暫時(shí)緩和內(nèi)存當(dāng)出現(xiàn)了引起掛起的事件時(shí)，如為了暫時(shí)緩和內(nèi)存的緊張狀態(tài)，用戶進(jìn)程請(qǐng)求將自己掛起或者當(dāng)父進(jìn)程請(qǐng)的緊張狀態(tài)，用戶進(jìn)程請(qǐng)求將自己掛起或者當(dāng)父進(jìn)

26、程請(qǐng)求將自己的某個(gè)子進(jìn)程掛起時(shí)，系統(tǒng)將利用掛起原語(yǔ)求將自己的某個(gè)子進(jìn)程掛起時(shí)，系統(tǒng)將利用掛起原語(yǔ)suspend( )suspend( )將制定的進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起。將制定的進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起。 6.激活原語(yǔ)Active( ): 將進(jìn)程從外存調(diào)入內(nèi)存，檢查該進(jìn)程的狀態(tài)，改為將進(jìn)程從外存調(diào)入內(nèi)存，檢查該進(jìn)程的狀態(tài)，改為相應(yīng)的活動(dòng)狀態(tài)相應(yīng)的活動(dòng)狀態(tài)( (只能由其它進(jìn)程調(diào)用只能由其它進(jìn)程調(diào)用) )29 多道程序的并發(fā)執(zhí)行改善了資源利用率、提高了系統(tǒng)多道程序的并發(fā)執(zhí)行改善了資源利用率、提高了系統(tǒng)吞吐量，但由于進(jìn)程的異步性，給系統(tǒng)帶來(lái)了新的問(wèn)題，吞吐量，但由于進(jìn)程的異步性，給系統(tǒng)帶來(lái)了

27、新的問(wèn)題，如資源共享、進(jìn)程合作等問(wèn)題，使的進(jìn)程間的制約成為如資源共享、進(jìn)程合作等問(wèn)題，使的進(jìn)程間的制約成為可能?？赡?。 進(jìn)程之間的關(guān)系包括：競(jìng)爭(zhēng)關(guān)系進(jìn)程之間的關(guān)系包括：競(jìng)爭(zhēng)關(guān)系( (互斥互斥) )、協(xié)作關(guān)系、協(xié)作關(guān)系( (同步同步) )；進(jìn)程間數(shù)據(jù)傳送方法；進(jìn)程間數(shù)據(jù)傳送方法( (通信通信) )；資源資源( (臨界區(qū)臨界區(qū)) )競(jìng)競(jìng)爭(zhēng)的兩個(gè)控制問(wèn)題：死鎖、饑餓等。爭(zhēng)的兩個(gè)控制問(wèn)題：死鎖、饑餓等。 重點(diǎn)和難點(diǎn)：重點(diǎn)和難點(diǎn)：信號(hào)量與信號(hào)量與P P、V V操作；死鎖操作；死鎖。30多道程序設(shè)計(jì)帶來(lái)的問(wèn)題多道程序設(shè)計(jì)帶來(lái)的問(wèn)題 ： 并發(fā)執(zhí)行的多個(gè)進(jìn)程可能產(chǎn)生互斥或同步的相互制并發(fā)執(zhí)行的多個(gè)進(jìn)程可能產(chǎn)生

28、互斥或同步的相互制約關(guān)系，不采取措施，可能導(dǎo)致結(jié)果的不可再現(xiàn)性。影約關(guān)系，不采取措施，可能導(dǎo)致結(jié)果的不可再現(xiàn)性。影響系統(tǒng)效率，而且還可以導(dǎo)致系統(tǒng)崩潰。響系統(tǒng)效率，而且還可以導(dǎo)致系統(tǒng)崩潰。 為此為此，現(xiàn)代操作系統(tǒng)都在內(nèi)核中設(shè)有進(jìn)程的互斥，現(xiàn)代操作系統(tǒng)都在內(nèi)核中設(shè)有進(jìn)程的互斥同步機(jī)制，以控制并發(fā)執(zhí)行的諸進(jìn)程能有效的共享資源同步機(jī)制，以控制并發(fā)執(zhí)行的諸進(jìn)程能有效的共享資源和相互合作，同時(shí)使并發(fā)程序的執(zhí)行仍具有可再現(xiàn)性。和相互合作，同時(shí)使并發(fā)程序的執(zhí)行仍具有可再現(xiàn)性。2.3 2.3 進(jìn)程同步進(jìn)程同步312.3.1 2.3.1 進(jìn)程同步的基本概念進(jìn)程同步的基本概念 進(jìn)程的同步進(jìn)程的同步synchroni

29、smsynchronism你等我，我也等你你等我，我也等你 多道程序系統(tǒng)中，系統(tǒng)中可能有許多進(jìn)程，在這些進(jìn)程多道程序系統(tǒng)中，系統(tǒng)中可能有許多進(jìn)程，在這些進(jìn)程之間可能存在以下兩種關(guān)系：之間可能存在以下兩種關(guān)系： 1 1. .資源共享關(guān)系資源共享關(guān)系 2.2.相互合作關(guān)系相互合作關(guān)系 這實(shí)際上都是一種合作進(jìn)程在獨(dú)自并發(fā)執(zhí)行過(guò)程中的某這實(shí)際上都是一種合作進(jìn)程在獨(dú)自并發(fā)執(zhí)行過(guò)程中的某些確定的時(shí)序點(diǎn)些確定的時(shí)序點(diǎn)( (協(xié)調(diào)點(diǎn)協(xié)調(diào)點(diǎn)) )上上“你等我，我也等你你等我，我也等你”的同步約的同步約束束321.1.資源共享關(guān)系資源共享關(guān)系 多個(gè)進(jìn)程之間彼此無(wú)關(guān)，他們并不知道其它進(jìn)程的存多個(gè)進(jìn)程之間彼此無(wú)關(guān)，他們

30、并不知道其它進(jìn)程的存在。例如在分時(shí)系統(tǒng)中，系統(tǒng)分別為每個(gè)用戶（終端）在。例如在分時(shí)系統(tǒng)中，系統(tǒng)分別為每個(gè)用戶（終端）建立一個(gè)進(jìn)程。但這些進(jìn)程既然同處于一個(gè)系統(tǒng)中，也建立一個(gè)進(jìn)程。但這些進(jìn)程既然同處于一個(gè)系統(tǒng)中，也就必然存在著資源共享的關(guān)系，如共享就必然存在著資源共享的關(guān)系，如共享CPUCPU和和I/OI/O設(shè)備等。設(shè)備等。此時(shí)，進(jìn)程的主要任務(wù)，是保證各個(gè)進(jìn)程能互斥地訪問(wèn)此時(shí)，進(jìn)程的主要任務(wù)，是保證各個(gè)進(jìn)程能互斥地訪問(wèn)臨界資源。所以，系統(tǒng)中的資源應(yīng)該不允許用戶進(jìn)程直臨界資源。所以，系統(tǒng)中的資源應(yīng)該不允許用戶進(jìn)程直接使用，而應(yīng)該由系統(tǒng)同一分配。例如：在僅有一臺(tái)打接使用，而應(yīng)該由系統(tǒng)同一分配。例如：

31、在僅有一臺(tái)打印機(jī)的系統(tǒng)中，兩個(gè)進(jìn)程提出打印請(qǐng)求。印機(jī)的系統(tǒng)中，兩個(gè)進(jìn)程提出打印請(qǐng)求。2.2.相互合作關(guān)系相互合作關(guān)系 例如輸入進(jìn)程、計(jì)算進(jìn)程、打印進(jìn)程三者之間就是相例如輸入進(jìn)程、計(jì)算進(jìn)程、打印進(jìn)程三者之間就是相互合作的關(guān)系?；ズ献鞯年P(guān)系。 33一、同步的定義一、同步的定義 進(jìn)程同步：進(jìn)程同步：指的是兩個(gè)或多個(gè)進(jìn)程為了合作完成同一個(gè)指的是兩個(gè)或多個(gè)進(jìn)程為了合作完成同一個(gè)任務(wù)，在執(zhí)行速度或某些個(gè)確定的時(shí)序點(diǎn)上必須相互協(xié)任務(wù)，在執(zhí)行速度或某些個(gè)確定的時(shí)序點(diǎn)上必須相互協(xié)調(diào)，即一個(gè)進(jìn)程的執(zhí)行依賴于另一個(gè)進(jìn)程調(diào)，即一個(gè)進(jìn)程的執(zhí)行依賴于另一個(gè)進(jìn)程其合作伙其合作伙伴的消息，當(dāng)一個(gè)進(jìn)程到達(dá)了某一確定點(diǎn)而沒(méi)有得到

32、合伴的消息，當(dāng)一個(gè)進(jìn)程到達(dá)了某一確定點(diǎn)而沒(méi)有得到合作伙伴發(fā)來(lái)的作伙伴發(fā)來(lái)的“已完成某些操作已完成某些操作”的消息時(shí)必須等待，的消息時(shí)必須等待，直到該消息到達(dá)被喚醒后，才能繼續(xù)向前推進(jìn)。直到該消息到達(dá)被喚醒后，才能繼續(xù)向前推進(jìn)。v進(jìn)程同步是多道程序系統(tǒng)中進(jìn)程之間存在的一種主要源于進(jìn)程同步是多道程序系統(tǒng)中進(jìn)程之間存在的一種主要源于進(jìn)程間合作的制約關(guān)系，也稱進(jìn)程間合作的制約關(guān)系，也稱直接制約關(guān)系直接制約關(guān)系。 34 直接制約關(guān)系：進(jìn)程間的相互聯(lián)系是有意進(jìn)程間的相互聯(lián)系是有意識(shí)的安排的，直接作用只發(fā)生在相交進(jìn)程間。識(shí)的安排的，直接作用只發(fā)生在相交進(jìn)程間。 間接制約關(guān)系：進(jìn)程間要通過(guò)某種中介發(fā)進(jìn)程間要通

33、過(guò)某種中介發(fā)生聯(lián)系，是無(wú)意識(shí)安排的，可發(fā)生在相交進(jìn)程生聯(lián)系，是無(wú)意識(shí)安排的，可發(fā)生在相交進(jìn)程之間，也可發(fā)生在無(wú)關(guān)進(jìn)程之間之間，也可發(fā)生在無(wú)關(guān)進(jìn)程之間 。35二、互斥的定義二、互斥的定義 所謂所謂，指的是對(duì)某個(gè)系統(tǒng)資源，一個(gè)進(jìn)，指的是對(duì)某個(gè)系統(tǒng)資源，一個(gè)進(jìn)程正在使用它，另外一個(gè)想用它的進(jìn)程就必須等程正在使用它，另外一個(gè)想用它的進(jìn)程就必須等待，而不能同時(shí)使用待，而不能同時(shí)使用 。 進(jìn)程互斥是多道程序系統(tǒng)中進(jìn)程間存在的一種源進(jìn)程互斥是多道程序系統(tǒng)中進(jìn)程間存在的一種源于資源共享的制約關(guān)系，也稱于資源共享的制約關(guān)系，也稱間接制約關(guān)系間接制約關(guān)系，主，主要是由被共享資源的使用性質(zhì)所決定的。要是由被共享資源

34、的使用性質(zhì)所決定的。36 這種限定進(jìn)程只能互斥地訪問(wèn)它的資源叫這種限定進(jìn)程只能互斥地訪問(wèn)它的資源叫臨界資源（臨界資源（指一次僅允許一個(gè)進(jìn)程使用的資源 ）。 臨界資源限定了使用者只能互斥地使用它。臨界資源限定了使用者只能互斥地使用它。 操作系統(tǒng)也不能中途從搶先者手中把臨界資源搶來(lái)給其他操作系統(tǒng)也不能中途從搶先者手中把臨界資源搶來(lái)給其他進(jìn)程用。因此，臨界資源也是不可剝奪性資源。進(jìn)程用。因此，臨界資源也是不可剝奪性資源。例：例：計(jì)算機(jī)計(jì)算機(jī)系統(tǒng)中可剝奪性使用的資源主要有系統(tǒng)中可剝奪性使用的資源主要有CPUCPU、內(nèi)存內(nèi)存和和磁盤磁盤等。等。三、臨界資源和臨界區(qū)三、臨界資源和臨界區(qū)37程 序 段1程

35、序 段2程 序 段n共 享 變量38：進(jìn)程中訪問(wèn)臨界資源的那段程序代碼稱為臨界：進(jìn)程中訪問(wèn)臨界資源的那段程序代碼稱為臨界區(qū)或臨界段。區(qū)或臨界段。使用同一臨界資源的不同進(jìn)程中的臨界區(qū)稱為使用同一臨界資源的不同進(jìn)程中的臨界區(qū)稱為區(qū)區(qū)或或。為實(shí)現(xiàn)對(duì)臨界資源的互斥訪問(wèn)，應(yīng)保證諸進(jìn)程為實(shí)現(xiàn)對(duì)臨界資源的互斥訪問(wèn)，應(yīng)保證諸進(jìn)程地進(jìn)地進(jìn)入各自的臨界區(qū)。入各自的臨界區(qū)。 但無(wú)論采用何種方法，都應(yīng)但無(wú)論采用何種方法，都應(yīng)遵循臨界區(qū)的使用原則遵循臨界區(qū)的使用原則，即，即“空則讓進(jìn)，忙則等待，等則有限，等則讓權(quán)空則讓進(jìn)，忙則等待，等則有限，等則讓權(quán)”。 39進(jìn)程同步和互斥間的關(guān)系：進(jìn)程同步和互斥間的關(guān)系：相似處：相似

36、處：進(jìn)程的互斥實(shí)際上是進(jìn)程同步的一種特殊進(jìn)程的互斥實(shí)際上是進(jìn)程同步的一種特殊 情況；情況； 進(jìn)程的互斥和同步統(tǒng)稱為進(jìn)程同步。進(jìn)程的互斥和同步統(tǒng)稱為進(jìn)程同步。差別：差別：是進(jìn)程間共享資源的使用權(quán)是進(jìn)程間共享資源的使用權(quán) ，這種競(jìng)爭(zhēng)沒(méi)，這種競(jìng)爭(zhēng)沒(méi)有固定的必然聯(lián)系，哪個(gè)進(jìn)程競(jìng)爭(zhēng)到使用權(quán)就歸那個(gè)進(jìn)程有固定的必然聯(lián)系，哪個(gè)進(jìn)程競(jìng)爭(zhēng)到使用權(quán)就歸那個(gè)進(jìn)程使用，直到不需要使用時(shí)再歸還；而使用，直到不需要使用時(shí)再歸還；而則涉及共享則涉及共享資源的并發(fā)進(jìn)程間有一種必然的聯(lián)系，當(dāng)進(jìn)程必須同步時(shí)，資源的并發(fā)進(jìn)程間有一種必然的聯(lián)系，當(dāng)進(jìn)程必須同步時(shí)，即使無(wú)進(jìn)程在使用共享資源時(shí)，那么尚未得到同步消息的即使無(wú)進(jìn)程在使用共享

37、資源時(shí)，那么尚未得到同步消息的進(jìn)程也不能去使用這個(gè)資源。進(jìn)程也不能去使用這個(gè)資源。402.3.2 2.3.2 信號(hào)量機(jī)制信號(hào)量機(jī)制 荷蘭著名科學(xué)家，后來(lái)的計(jì)算機(jī)圖靈獎(jiǎng)獲得荷蘭著名科學(xué)家，后來(lái)的計(jì)算機(jī)圖靈獎(jiǎng)獲得者，者，E.W.DijkstraE.W.Dijkstra于于19651965年提出了用作進(jìn)程同年提出了用作進(jìn)程同步工具的步工具的信號(hào)量信號(hào)量（semaphoresemaphore）機(jī)制機(jī)制，這是一種，這是一種卓有成效的進(jìn)程互斥同步工具，已被廣泛應(yīng)用卓有成效的進(jìn)程互斥同步工具，已被廣泛應(yīng)用于現(xiàn)代計(jì)算機(jī)系統(tǒng)中。于現(xiàn)代計(jì)算機(jī)系統(tǒng)中。 兩個(gè)信號(hào)量操作原語(yǔ)，即兩個(gè)信號(hào)量操作原語(yǔ)，即P P，V V操作

38、。操作。 41信號(hào)量機(jī)制的基本原理是：信號(hào)量機(jī)制的基本原理是： v兩個(gè)或多個(gè)進(jìn)程可以利用彼此間收發(fā)的簡(jiǎn)單的信號(hào)來(lái)實(shí)兩個(gè)或多個(gè)進(jìn)程可以利用彼此間收發(fā)的簡(jiǎn)單的信號(hào)來(lái)實(shí)現(xiàn)現(xiàn)“正確的正確的”并發(fā)執(zhí)行，一個(gè)進(jìn)程在收到一個(gè)指定信號(hào)并發(fā)執(zhí)行，一個(gè)進(jìn)程在收到一個(gè)指定信號(hào)前，會(huì)被迫在一個(gè)確定的或者需要的地方停下來(lái)，從而前，會(huì)被迫在一個(gè)確定的或者需要的地方停下來(lái)，從而保持同步或互斥。保持同步或互斥。42一、信號(hào)量的概念一、信號(hào)量的概念 信號(hào)量信號(hào)量，也叫，也叫信號(hào)燈信號(hào)燈，一般是由兩個(gè)成員組成的數(shù)據(jù)結(jié)，一般是由兩個(gè)成員組成的數(shù)據(jù)結(jié)構(gòu)，是一個(gè)確定的二元組構(gòu)，是一個(gè)確定的二元組（S S，Q Q）S S是個(gè)具有非負(fù)初值

39、的是個(gè)具有非負(fù)初值的整型變量整型變量，表示該信號(hào)量的值，表示該信號(hào)量的值，且且S S的值只能由定義在信號(hào)量上的的值只能由定義在信號(hào)量上的P P操作原語(yǔ)和操作原語(yǔ)和V V操作原操作原語(yǔ)來(lái)改變；語(yǔ)來(lái)改變；Q Q是個(gè)初始狀態(tài)為是個(gè)初始狀態(tài)為空的空的等待隊(duì)列指針等待隊(duì)列指針 （一個(gè)是指向（一個(gè)是指向PCBPCB的指針，當(dāng)多個(gè)進(jìn)程都等待同一信號(hào)量時(shí)，它們就排成的指針，當(dāng)多個(gè)進(jìn)程都等待同一信號(hào)量時(shí)，它們就排成一個(gè)隊(duì)列，由信號(hào)量的指針項(xiàng)指出該隊(duì)列的頭）。一個(gè)隊(duì)列，由信號(hào)量的指針項(xiàng)指出該隊(duì)列的頭）。43另一定義：另一定義：v信號(hào)量類型是個(gè)復(fù)合類型，其一個(gè)分量是個(gè)整型分量信號(hào)量類型是個(gè)復(fù)合類型，其一個(gè)分量是個(gè)整

40、型分量S S，另一個(gè)分量是個(gè)等待隊(duì)列指針另一個(gè)分量是個(gè)等待隊(duì)列指針Q Q （一個(gè)是指向（一個(gè)是指向PCBPCB的指的指針，當(dāng)多個(gè)進(jìn)程都等待同一信號(hào)量時(shí)，它們就排成一個(gè)針，當(dāng)多個(gè)進(jìn)程都等待同一信號(hào)量時(shí)，它們就排成一個(gè)隊(duì)列，由信號(hào)量的指針項(xiàng)指出該隊(duì)列的頭。）隊(duì)列，由信號(hào)量的指針項(xiàng)指出該隊(duì)列的頭。） 44* * *信號(hào)量整型分量信號(hào)量整型分量S S的值的物理含義：的值的物理含義： v當(dāng)當(dāng)S0S0時(shí)，表示某類可用資源的數(shù)目，或者說(shuō)表示可以時(shí)，表示某類可用資源的數(shù)目，或者說(shuō)表示可以執(zhí)行執(zhí)行P P操作而不會(huì)被阻塞的進(jìn)程的數(shù)目；操作而不會(huì)被阻塞的進(jìn)程的數(shù)目；v當(dāng)當(dāng)S S0 0時(shí)，其絕對(duì)值表示信號(hào)量時(shí)，其絕對(duì)

41、值表示信號(hào)量S S的阻塞隊(duì)列中的進(jìn)程的阻塞隊(duì)列中的進(jìn)程數(shù)，即系統(tǒng)中因請(qǐng)求該類資源而被阻塞的進(jìn)程的數(shù)目，數(shù)，即系統(tǒng)中因請(qǐng)求該類資源而被阻塞的進(jìn)程的數(shù)目，亦即被信號(hào)燈擋住的進(jìn)程數(shù)目，這些進(jìn)程需要?jiǎng)e的進(jìn)程亦即被信號(hào)燈擋住的進(jìn)程數(shù)目，這些進(jìn)程需要?jiǎng)e的進(jìn)程發(fā)出相應(yīng)的信號(hào)燈來(lái)喚醒。發(fā)出相應(yīng)的信號(hào)燈來(lái)喚醒。 v另外，另外，S S的值只能由的值只能由P P、V V操作來(lái)改變。操作來(lái)改變。 45二、二、P P、V V操作原語(yǔ)操作原語(yǔ) 通常通常P P操作意味著請(qǐng)求一個(gè)資源，在一定條件下，操作意味著請(qǐng)求一個(gè)資源，在一定條件下， P P操作代表掛起進(jìn)程操作；操作代表掛起進(jìn)程操作；通常通常V V操作意味著釋放一個(gè)資源，

42、在一定條件下，操作意味著釋放一個(gè)資源，在一定條件下， V V操作代表喚醒被掛起進(jìn)程的操作；操作代表喚醒被掛起進(jìn)程的操作； 原語(yǔ)是操作系統(tǒng)內(nèi)核中執(zhí)行時(shí)不可中斷的過(guò)程，即原語(yǔ)是操作系統(tǒng)內(nèi)核中執(zhí)行時(shí)不可中斷的過(guò)程，即原子操作。信號(hào)量機(jī)制中，除賦值外，信號(hào)量?jī)H能由原子操作。信號(hào)量機(jī)制中，除賦值外，信號(hào)量?jī)H能由原語(yǔ)對(duì)其進(jìn)行操作。原語(yǔ)對(duì)其進(jìn)行操作。 信號(hào)量通?？梢院?jiǎn)單反映出相應(yīng)資源的使用情況，它信號(hào)量通?？梢院?jiǎn)單反映出相應(yīng)資源的使用情況，它與與P P，V V操作原語(yǔ)一起使用可實(shí)現(xiàn)進(jìn)程的同步和互斥。操作原語(yǔ)一起使用可實(shí)現(xiàn)進(jìn)程的同步和互斥。 461.1.定義在信號(hào)量定義在信號(hào)量S S上的上的P(S)P(S)原

43、語(yǔ)操作的算法描述為：原語(yǔ)操作的算法描述為： 1 1）S S減減1 1； 2 2）若）若S0S0，則調(diào)用，則調(diào)用P P（S S）的進(jìn)）的進(jìn)程返回，繼續(xù)執(zhí)行程返回，繼續(xù)執(zhí)行; ; 3 3）若）若S0SSS0 Block(Q) 返回YN472.2.定義在信號(hào)量定義在信號(hào)量S S上的上的V(S)V(S)原語(yǔ)操作的算法描述為：原語(yǔ)操作的算法描述為： （1 1）S S加加1 1；（2 2）若）若S0 S0 ，則調(diào)用，則調(diào)用V V（S S）的進(jìn)程繼續(xù)執(zhí)行，返回；的進(jìn)程繼續(xù)執(zhí)行，返回；（3 3）若）若S0 SS S0 Wakeup(Q) 返回YN48注意注意P P（S S）操作和）操作和V V（S S）操作的

44、物理含義：）操作的物理含義： P P（S S）操作表示）操作表示“等信號(hào)等信號(hào)”，即測(cè)試一個(gè)要等的信號(hào)是，即測(cè)試一個(gè)要等的信號(hào)是否到達(dá)；否到達(dá)；V V（S S）操作表示）操作表示“發(fā)信號(hào)發(fā)信號(hào)”。這個(gè)信號(hào)在實(shí)現(xiàn)同步時(shí)就。這個(gè)信號(hào)在實(shí)現(xiàn)同步時(shí)就是是“合作者的伙伴進(jìn)程已完成前趨任務(wù)合作者的伙伴進(jìn)程已完成前趨任務(wù)”，在實(shí)現(xiàn)互斥，在實(shí)現(xiàn)互斥時(shí)就是時(shí)就是“臨界資源可用臨界資源可用”。另外，在互斥問(wèn)題中，每執(zhí)行一次另外，在互斥問(wèn)題中，每執(zhí)行一次P P（S S）操作的含義，）操作的含義，也可理解為進(jìn)程請(qǐng)求一個(gè)單位的也可理解為進(jìn)程請(qǐng)求一個(gè)單位的S S類資源；每執(zhí)行一次類資源；每執(zhí)行一次V V（S S）操作的含

45、義，也可理解為進(jìn)程釋放一個(gè)單位的）操作的含義，也可理解為進(jìn)程釋放一個(gè)單位的S S類類資源。資源。 49 P,V操作是兩個(gè)過(guò)程，由他們兩個(gè)來(lái)控制一個(gè)信號(hào)S，假設(shè)S是紅燈的個(gè)數(shù)。 每個(gè)進(jìn)程進(jìn)入臨界區(qū)前都要先執(zhí)行P操作。退出臨界區(qū)時(shí)執(zhí)行V操作。用下面的比喻很容易理解: 臨界區(qū)門前有棵樹（S） 用來(lái)掛紅燈 進(jìn)程想進(jìn)CPU的門 先得上樹取盞燈（調(diào)用一次P操作） 取下一個(gè)去敲門(S=S-1) 如果樹上沒(méi)燈取(S0) 樹說(shuō)欠你一盞燈(S為負(fù)時(shí)) 沒(méi)轍只好外邊排隊(duì)等( Wait (S) 得燈進(jìn)程續(xù)運(yùn)行 運(yùn)行完了要出門（調(diào)用一次V操作） 馬上還回一盞燈(S=S+1) 若有進(jìn)程在催債(S0) 放個(gè)進(jìn)去事完成( R

46、elease (S)50 P、V操作也都是配對(duì)出現(xiàn)，但對(duì)操作也都是配對(duì)出現(xiàn)，但對(duì)同一個(gè)信號(hào)量同一個(gè)信號(hào)量的的P、V操作卻不是操作卻不是同時(shí)出現(xiàn)在每一個(gè)進(jìn)程的程序里，而是分別出現(xiàn)在同時(shí)出現(xiàn)在每一個(gè)進(jìn)程的程序里，而是分別出現(xiàn)在一個(gè)進(jìn)程和它的合一個(gè)進(jìn)程和它的合作伙伴的代碼中作伙伴的代碼中。 而且而且P、V操作的出現(xiàn)位置都在各個(gè)合作進(jìn)程中確定的時(shí)序點(diǎn)，即操作的出現(xiàn)位置都在各個(gè)合作進(jìn)程中確定的時(shí)序點(diǎn)，即一個(gè)生產(chǎn)者進(jìn)程在完成了前趨的生產(chǎn)任務(wù)后，應(yīng)立即給合作伙伴一個(gè)生產(chǎn)者進(jìn)程在完成了前趨的生產(chǎn)任務(wù)后，應(yīng)立即給合作伙伴消費(fèi)者進(jìn)程發(fā)送一條消費(fèi)者進(jìn)程發(fā)送一條“已完成前趨生產(chǎn)任務(wù)已完成前趨生產(chǎn)任務(wù)”的消息，這要執(zhí)行

47、的消息，這要執(zhí)行V操作；操作；而后繼的消費(fèi)者進(jìn)程在消費(fèi)前，應(yīng)該執(zhí)行對(duì)同一個(gè)信號(hào)量的而后繼的消費(fèi)者進(jìn)程在消費(fèi)前，應(yīng)該執(zhí)行對(duì)同一個(gè)信號(hào)量的P操作，以操作，以測(cè)試其合作伙伴測(cè)試其合作伙伴生產(chǎn)者進(jìn)程生產(chǎn)者進(jìn)程“已完成前趨生產(chǎn)任務(wù)已完成前趨生產(chǎn)任務(wù)”的消息是否的消息是否到來(lái)，如果到來(lái)就開始消費(fèi)，否則就阻塞自己。到來(lái)，如果到來(lái)就開始消費(fèi)，否則就阻塞自己。 三、用三、用P P、V V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的同步操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的同步51解答這類進(jìn)程同步問(wèn)題的主要步驟也是三大步：解答這類進(jìn)程同步問(wèn)題的主要步驟也是三大步： (1)(1)分析清楚題目涉及的進(jìn)程間的制約關(guān)系；分析清楚題目涉及的進(jìn)程間的制約關(guān)系； (2)(

48、2)設(shè)置信號(hào)量（包括信號(hào)量的個(gè)數(shù)和初值及其物理含設(shè)置信號(hào)量（包括信號(hào)量的個(gè)數(shù)和初值及其物理含義），合作進(jìn)程間需要收發(fā)幾條消息相應(yīng)就設(shè)置幾個(gè)信義），合作進(jìn)程間需要收發(fā)幾條消息相應(yīng)就設(shè)置幾個(gè)信號(hào)量，同步信號(hào)量的初值一般為號(hào)量，同步信號(hào)量的初值一般為0 0； (3)(3)給出進(jìn)程相應(yīng)程序的算法描述或流程控制，并把給出進(jìn)程相應(yīng)程序的算法描述或流程控制，并把P P、V V操作加到程序的適當(dāng)處。操作加到程序的適當(dāng)處。 52例例3.13.1有兩個(gè)進(jìn)程有兩個(gè)進(jìn)程P1P1和和P2P2，P1P1的功能是計(jì)算的功能是計(jì)算x=a+bx=a+b的值，的值，a a和和b b是常量（在是常量（在P1P1的前面代碼中能得到）

49、；的前面代碼中能得到）； P2P2的功能的功能是計(jì)算是計(jì)算y=x+1y=x+1的值。的值。P1 P2 x=a+b; y=x+1; P1 P2 P(S);x=a+b; y=x+1;V(S); 53例例3.23.2 生產(chǎn)者生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 公用緩沖池，公用緩沖池，有有n個(gè)緩沖區(qū)個(gè)緩沖區(qū)一組生產(chǎn)者生產(chǎn)產(chǎn)品一組生產(chǎn)者生產(chǎn)產(chǎn)品一組消費(fèi)者取走產(chǎn)品一組消費(fèi)者取走產(chǎn)品54生產(chǎn)者消費(fèi)者問(wèn)題是相互合作進(jìn)程關(guān)系生產(chǎn)者消費(fèi)者問(wèn)題是相互合作進(jìn)程關(guān)系的一種抽象的一種抽象 輸入輸入計(jì)算計(jì)算打印打印 生產(chǎn)者生產(chǎn)者 消費(fèi)者消費(fèi)者 生產(chǎn)者生產(chǎn)者 消費(fèi)者消費(fèi)者系統(tǒng)中使用資源的進(jìn)程系統(tǒng)中使用資源的進(jìn)程消費(fèi)者消費(fèi)者系統(tǒng)中釋放

50、同類資源的進(jìn)程系統(tǒng)中釋放同類資源的進(jìn)程生產(chǎn)者生產(chǎn)者55問(wèn)題分析： 生產(chǎn)者生產(chǎn)者消費(fèi)者之間的同步關(guān)系表現(xiàn)為：消費(fèi)者之間的同步關(guān)系表現(xiàn)為：一旦一旦緩沖池中所有緩沖區(qū)均裝滿產(chǎn)品時(shí)，生產(chǎn)者必須緩沖池中所有緩沖區(qū)均裝滿產(chǎn)品時(shí)，生產(chǎn)者必須等待消等待消費(fèi)者提供空緩沖區(qū)費(fèi)者提供空緩沖區(qū)；一旦緩沖池中所有緩沖區(qū)全為空時(shí)，；一旦緩沖池中所有緩沖區(qū)全為空時(shí)，消費(fèi)者必須消費(fèi)者必須等待生產(chǎn)者提供滿緩沖區(qū)等待生產(chǎn)者提供滿緩沖區(qū)。 生產(chǎn)者生產(chǎn)者消費(fèi)者之間還有互斥關(guān)系：消費(fèi)者之間還有互斥關(guān)系：由于緩沖池由于緩沖池是臨界資源，所以任何進(jìn)程在對(duì)緩沖區(qū)進(jìn)行存取操作時(shí)是臨界資源，所以任何進(jìn)程在對(duì)緩沖區(qū)進(jìn)行存取操作時(shí)都必須和其他進(jìn)程互

51、斥進(jìn)行。都必須和其他進(jìn)程互斥進(jìn)行。 56問(wèn)題解答： 所用信號(hào)量設(shè)置如下：所用信號(hào)量設(shè)置如下： ）同步信號(hào)量同步信號(hào)量empty，初值為，初值為n，表示消費(fèi)者已把緩，表示消費(fèi)者已把緩沖池中全部產(chǎn)品取走，有沖池中全部產(chǎn)品取走，有n個(gè)空緩沖區(qū)可用。個(gè)空緩沖區(qū)可用。 ）同步信號(hào)量同步信號(hào)量full，初值為，初值為0，表示生產(chǎn)者尚未把產(chǎn)品，表示生產(chǎn)者尚未把產(chǎn)品放入緩沖池，有放入緩沖池，有0個(gè)滿緩沖區(qū)可用。個(gè)滿緩沖區(qū)可用。 ）互斥信號(hào)量互斥信號(hào)量mutex，初值為，初值為1，以保證同時(shí)只有一，以保證同時(shí)只有一個(gè)進(jìn)程能夠進(jìn)入臨界區(qū)，訪問(wèn)緩沖池。個(gè)進(jìn)程能夠進(jìn)入臨界區(qū)，訪問(wèn)緩沖池。 57用信號(hào)量機(jī)制解決生產(chǎn)者用

52、信號(hào)量機(jī)制解決生產(chǎn)者消費(fèi)者問(wèn)題的消費(fèi)者問(wèn)題的算法描述如下：算法描述如下： 生產(chǎn)出一產(chǎn)品； P（full）； P（empty）； P（mutex）； P（mutex）； 從緩沖區(qū)取出一產(chǎn)品； 將該產(chǎn)品放入緩沖區(qū)； V（mutex）； V（mutex）； V（empty）； V（full）； 消費(fèi)該產(chǎn)品； 58小結(jié):用信號(hào)量機(jī)制解這類題的三個(gè)步驟 （1）分析進(jìn)程間的制約關(guān)系）分析進(jìn)程間的制約關(guān)系 （2）設(shè)置信號(hào)量）設(shè)置信號(hào)量 （3）實(shí)施）實(shí)施P、V操作。操作。 第一步是基礎(chǔ)、關(guān)鍵，第三步是核心。第一步是基礎(chǔ)、關(guān)鍵，第三步是核心。 掌握實(shí)現(xiàn)進(jìn)程互斥與進(jìn)程同步的第三步在形式上差異：即掌握實(shí)現(xiàn)進(jìn)程互斥與

53、進(jìn)程同步的第三步在形式上差異：即P、V操作總是操作總是配對(duì)配對(duì)出現(xiàn)的。出現(xiàn)的。 但但P,VP,V在在互斥問(wèn)題互斥問(wèn)題中總是出現(xiàn)在同一個(gè)進(jìn)程的代碼中，且緊中總是出現(xiàn)在同一個(gè)進(jìn)程的代碼中，且緊緊夾著臨界區(qū)；而在緊夾著臨界區(qū)；而在同步問(wèn)題同步問(wèn)題中，卻是分別出現(xiàn)在兩個(gè)合中，卻是分別出現(xiàn)在兩個(gè)合作進(jìn)程的代碼中，需要等消息的一方用作進(jìn)程的代碼中，需要等消息的一方用P操作，相應(yīng)的對(duì)同操作，相應(yīng)的對(duì)同一信號(hào)量的一信號(hào)量的V操作則在發(fā)出此消息的另一方中。操作則在發(fā)出此消息的另一方中。 59三、用三、用P P、V V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的互斥操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的互斥 用用P P、V V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的互斥也一樣簡(jiǎn)單

54、，只需在相關(guān)操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的互斥也一樣簡(jiǎn)單，只需在相關(guān)進(jìn)程的臨界區(qū)的前后分別施以進(jìn)程的臨界區(qū)的前后分別施以P P操作和操作和V V操作即可，即在相操作即可，即在相關(guān)進(jìn)程的程序里由關(guān)進(jìn)程的程序里由P P操作和操作和V V操作原語(yǔ)緊夾著臨界區(qū)，就能操作原語(yǔ)緊夾著臨界區(qū)，就能保證這些進(jìn)程互斥地進(jìn)入各自的臨界區(qū)。保證這些進(jìn)程互斥地進(jìn)入各自的臨界區(qū)。這里所用信號(hào)量的初值一般為這里所用信號(hào)量的初值一般為1 1，表示臨界資源未被占用，表示臨界資源未被占用，且其可用數(shù)目為且其可用數(shù)目為1 1。 用用P P、V V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程互斥的效率更高一些，因?yàn)椴僮髟Z(yǔ)實(shí)現(xiàn)進(jìn)程互斥的效率更高一些，因?yàn)镻 P操操作中引入了阻塞機(jī)制，所以消除了作