計(jì)算機(jī)操作系統(tǒng)第3章進(jìn)程與線程目錄3.1進(jìn)程概念3.2進(jìn)程控制3.3線程3.4互斥和同步2預(yù)備知識(shí)：前趨圖前趨圖是一個(gè)有向無(wú)環(huán)圖（DirectedAcyclicGraph,DAG）3.1進(jìn)程概念3.1.1程序的順序執(zhí)行及其特征1.程序的順序執(zhí)行通?？梢园岩粋€(gè)應(yīng)用程序分成若干個(gè)程序段，各程序段之間必須按照某種先后次序順序執(zhí)行，僅當(dāng)前一程序段（操作）執(zhí)行完后，才能執(zhí)行后繼程序段（操作）。

63.1.1程序的順序執(zhí)行及其特征1.程序的順序執(zhí)行

7圖3.1多道程序的順序執(zhí)行3.1.1程序的順序執(zhí)行及其特征2.程序順序執(zhí)行的特征（1）順序性：處理機(jī)的操作嚴(yán)格按照程序所規(guī)定的順序執(zhí)行，即每一操作必須在上一個(gè)操作結(jié)束之后開(kāi)始。（2）封閉性：程序是在封閉的環(huán)境下執(zhí)行的，即程序運(yùn)行時(shí)獨(dú)占整個(gè)系統(tǒng)資源，資源的狀態(tài)（除初始狀態(tài)外）只有本程序可以改變。（3）可再現(xiàn)性：只要程序執(zhí)行時(shí)的環(huán)境和初始條件相同，當(dāng)程序重復(fù)執(zhí)行時(shí)，不論它的執(zhí)行方式如何，是連續(xù)執(zhí)行，還是“走走停停”的執(zhí)行，其結(jié)果都是相同的。93.1.2程序的并發(fā)執(zhí)行及其特征1.程序的并發(fā)執(zhí)行

為了提高計(jì)算機(jī)的利用率、處理速度和系統(tǒng)的吞吐量，并行處理技術(shù)和并發(fā)程序設(shè)計(jì)技術(shù)在計(jì)算機(jī)中已經(jīng)得到了廣泛應(yīng)用，成為了現(xiàn)代操作系統(tǒng)的基本特征之一。

10圖3.2多道程序并發(fā)執(zhí)行3.1.2程序的并發(fā)執(zhí)行及其特征前趨圖的引入：前趨圖是一個(gè)有向無(wú)環(huán)（DirectedAcyclicGraph,DAG）考慮具有以下四條語(yǔ)句的一個(gè)程序段：

S1:a:=x+2;S2:b:=y+4;S3:c:=a+b;S4:d:=c+b;

11圖3.3四條語(yǔ)句的前趨圖S1:a:=x+2;S2:b:=y+4;S3:c:=a+b;S4:d:=c+b;S1:a:=x+2;S2:b:=y+4;S3:c:=a+b;S4:d:=c+b;3.1.2程序的并發(fā)執(zhí)行及其特征2.程序并發(fā)執(zhí)行的特征（1）間斷（異步）性：程序在并發(fā)執(zhí)行時(shí)，由于它們共享系統(tǒng)資源，以及為了完成同一任務(wù)而相互合作，致使這些并發(fā)程序之間形成了相互制約的關(guān)系。（2）失去封閉性：程序在并發(fā)執(zhí)行時(shí)，多個(gè)程序共享系統(tǒng)中的各種資源，因此，系統(tǒng)資源的狀態(tài)將由多個(gè)程序來(lái)改變，致使程序失去了封閉性。

（3）不可再現(xiàn)性：程序在并發(fā)執(zhí)行時(shí)，由于失去了封閉性，也將導(dǎo)致其失去執(zhí)行的可再現(xiàn)性。

14不可再現(xiàn)性下面是兩個(gè)并發(fā)執(zhí)行的程序A，B，描述如下已有的進(jìn)程定義：進(jìn)程是程序的一次執(zhí)行；進(jìn)程是可以和別的計(jì)算并發(fā)執(zhí)行的計(jì)算；進(jìn)程是定義在一個(gè)數(shù)據(jù)結(jié)構(gòu)上，并能夠在其上進(jìn)行操作的一個(gè)程序；進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過(guò)程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。3.1.3進(jìn)程的概念及其特征17我們將進(jìn)程定義為：進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過(guò)程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。3.1.3進(jìn)程的概念及其特征18程序和進(jìn)程之間的區(qū)別與聯(lián)系：程序是完成特定任務(wù)的一組指令的結(jié)合，可以永久保存，具有靜態(tài)性；進(jìn)程是程序在某一數(shù)據(jù)結(jié)構(gòu)上的一次執(zhí)行過(guò)程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位，具有動(dòng)態(tài)性；一個(gè)進(jìn)程可以包含多個(gè)程序，一個(gè)程序也可以被多個(gè)進(jìn)程執(zhí)行。3.1.3進(jìn)程的概念及其特征191.兩狀態(tài)模型包含運(yùn)行態(tài)（Running）和非運(yùn)行態(tài)（Notrunning）兩種進(jìn)程狀態(tài)創(chuàng)建了一個(gè)新進(jìn)程之后，它會(huì)以非運(yùn)行態(tài)加入到系統(tǒng)中，等到操作系統(tǒng)為其分派處理器當(dāng)前處于運(yùn)行態(tài)的進(jìn)程會(huì)不時(shí)地中斷，由系統(tǒng)中的分派器選擇處于非運(yùn)行狀中的某一個(gè)進(jìn)程運(yùn)行3.1.4進(jìn)程狀態(tài)20（a）

狀態(tài)變遷圖3.1.4進(jìn)程狀態(tài)21（b）

排隊(duì)圖3.1.4進(jìn)程狀態(tài)22什么在排隊(duì)是它－－PCB(processcontrolblock)進(jìn)程控制塊（描述進(jìn)程進(jìn)關(guān)信息的數(shù)據(jù)結(jié)構(gòu)）2.五狀態(tài)模型包括就緒態(tài)（Ready）、運(yùn)行態(tài)（Running）、阻塞態(tài)（Blocked）、新建態(tài)（New）和終止態(tài)（Terminate）進(jìn)程狀態(tài)描述：（1）新建態(tài)：剛剛創(chuàng)建的新進(jìn)程，通常是指進(jìn)程控制塊已經(jīng)創(chuàng)建，但還沒(méi)有加載到系統(tǒng)內(nèi)存中的進(jìn)程。（2）就緒態(tài)：進(jìn)程等待系統(tǒng)為其分派處理器，而此時(shí)處理器被其它進(jìn)程占據(jù)，所以該狀態(tài)進(jìn)程不能執(zhí)行，但已經(jīng)具備了除處理器之外的進(jìn)程執(zhí)行所需要的所有條件。3.1.4進(jìn)程狀態(tài)24（3）運(yùn)行態(tài)：進(jìn)程已獲得所需資源并占據(jù)處理器，處理器正在執(zhí)行該進(jìn)程。（4）阻塞態(tài)：也稱為等待態(tài)、掛起態(tài)或睡眠態(tài)，進(jìn)程在等待某個(gè)事情的發(fā)生而暫時(shí)不能運(yùn)行，例如等待某個(gè)I/O操作的完成。（5）終止態(tài)：進(jìn)程或者因?yàn)閳?zhí)行結(jié)束或者因?yàn)楸怀蜂N而從可執(zhí)行進(jìn)程組中退出。3.1.4進(jìn)程狀態(tài)25圖3.5五狀態(tài)模型3.1.4進(jìn)程狀態(tài)26進(jìn)程狀態(tài)間可能的轉(zhuǎn)換及原因有：新建→就緒：系統(tǒng)納入一個(gè)新進(jìn)程。就緒→運(yùn)行：進(jìn)程被調(diào)度程序選中，占據(jù)處理器而進(jìn)入運(yùn)行狀態(tài)。運(yùn)行→終止：進(jìn)程運(yùn)行結(jié)束或被撤銷則退出系統(tǒng)進(jìn)入終止態(tài)。運(yùn)行→就緒：進(jìn)程分配的占據(jù)處理器的時(shí)間片已經(jīng)用完，或者是具有更高優(yōu)先級(jí)的進(jìn)程進(jìn)入系統(tǒng)，當(dāng)前正在運(yùn)行的進(jìn)程被搶占了處理器，此時(shí)進(jìn)程從運(yùn)行態(tài)轉(zhuǎn)換到就緒態(tài)。運(yùn)行→阻塞：進(jìn)程在等待系統(tǒng)分配資源或者等待某些事件的發(fā)生，進(jìn)程讓出處理器由運(yùn)行態(tài)轉(zhuǎn)入阻塞態(tài)。阻塞→就緒：處于阻塞隊(duì)列中的進(jìn)程等待的資源可用或者等待的事件發(fā)生之后，進(jìn)程從阻塞態(tài)轉(zhuǎn)換到就緒態(tài)，等待處理器選中它運(yùn)行。27掛起狀態(tài)的引入

內(nèi)存是有限的不能容納所有的進(jìn)程，對(duì)于內(nèi)存中的多個(gè)進(jìn)程，處理器依次選中運(yùn)行，當(dāng)一個(gè)進(jìn)程正在等待I/O事件發(fā)生時(shí)，處理器轉(zhuǎn)移到另一個(gè)進(jìn)程。但是，處理器的速度比I/O要快很多，有可能內(nèi)存中所有進(jìn)程都在等待I/O事件的完成，導(dǎo)致處理器處于空閑狀態(tài)。

一種可行的解決問(wèn)題的辦法是引入掛起（Suspend）的概念。3.1.4進(jìn)程狀態(tài)28圖3.6引入掛起的進(jìn)程狀態(tài)轉(zhuǎn)換模型3.1.4進(jìn)程狀態(tài)29進(jìn)程控制塊（Processcontrolblock,PCB）是操作系統(tǒng)用來(lái)記錄進(jìn)程狀態(tài)和相關(guān)信息，控制進(jìn)程運(yùn)行的數(shù)據(jù)結(jié)構(gòu)，是進(jìn)程的唯一標(biāo)識(shí)符在PCB中，主要包含如下的信息:3.1.5進(jìn)程控制塊30進(jìn)程標(biāo)識(shí)符進(jìn)程狀態(tài)調(diào)度信息程序計(jì)數(shù)器上下文數(shù)據(jù)內(nèi)存指針I(yè)/O狀態(tài)信息進(jìn)程控制是進(jìn)程管理中最基本的功能在操作系統(tǒng)中，不同功能都是通過(guò)執(zhí)行各種原語(yǔ)（Primitive）操作實(shí)現(xiàn)原語(yǔ)是由若干條指令構(gòu)成、可完成特定功能的程序段。原語(yǔ)是原子操作，是一個(gè)不可分割的基本單元，在執(zhí)行過(guò)程中不會(huì)被中斷。3.2進(jìn)程控制31引起進(jìn)程創(chuàng)建的事件：（1）批處理作業(yè)

（2）用戶登錄

（3）提供服務(wù)

（4）進(jìn)程派生3.2.1進(jìn)程創(chuàng)建32創(chuàng)建一個(gè)新進(jìn)程的具體步驟：（1）系統(tǒng)為新建進(jìn)程申請(qǐng)一個(gè)空白的進(jìn)程控制塊，獲得一個(gè)唯一的進(jìn)程標(biāo)識(shí)符。（2）系統(tǒng)為新建進(jìn)程分配運(yùn)行所需的資源，包括：內(nèi)存、處理器時(shí)間、I/O設(shè)備等。（3）進(jìn)程控制塊（PCB）初始化。（4）設(shè)置鏈接，如果就緒隊(duì)列允許新進(jìn)程插入，則將新進(jìn)程插入就緒隊(duì)列。3.2.1進(jìn)程創(chuàng)建33引起進(jìn)程終止的事件：（1）正常完成（2）運(yùn)行超時(shí)（3）等待超時(shí)（4）內(nèi)存不足（5）越界錯(cuò)誤（6）保護(hù)錯(cuò)誤（7）算術(shù)錯(cuò)誤3.2.2進(jìn)程終止34（8）

I/O錯(cuò)誤（9）無(wú)效指令（10）特權(quán)指令（11）操作員或操作系統(tǒng)干涉（12）父進(jìn)程請(qǐng)求（13）父進(jìn)程終止終止原語(yǔ)的具體步驟：（1）根據(jù)需要終止進(jìn)程的進(jìn)程標(biāo)識(shí)符，從PCB集合中查找對(duì)應(yīng)的進(jìn)程，從中讀出該進(jìn)程的狀態(tài)。（2）若被終止進(jìn)程正處在執(zhí)行狀態(tài)，則應(yīng)立即終止該進(jìn)程的執(zhí)行，并設(shè)置相應(yīng)的調(diào)度信息，用于指示該進(jìn)程被終止后應(yīng)重新進(jìn)行調(diào)度。（3）將被終止進(jìn)程所擁有的所有資源歸還給其父進(jìn)程，或者歸還給系統(tǒng)。3.2.2進(jìn)程終止35（3）若被終止進(jìn)程還擁有子孫進(jìn)程，則將其所有子孫進(jìn)程一并終止。（4）歸還PCB所占據(jù)的空間。3.2.2進(jìn)程終止361.進(jìn)程阻塞進(jìn)程阻塞是指進(jìn)程在執(zhí)行過(guò)程中因等待某個(gè)事件的發(fā)生或等待某個(gè)操作的完成而不得不讓出處理器。引起進(jìn)程阻塞的主要事件有：

（1）請(qǐng)求系統(tǒng)服務(wù)。（2）啟動(dòng)某種操作。（3）新數(shù)據(jù)尚未到達(dá)。（4）無(wú)新工作可做。3.2.3進(jìn)程阻塞和喚醒37阻塞原語(yǔ)（Blockprimitive）的具體步驟：

（1）正在執(zhí)行的進(jìn)程立即終止執(zhí)行，把PCB中的進(jìn)程狀態(tài)由執(zhí)行改為阻塞，并將處理機(jī)狀態(tài)寫入PCB中。（2）將PCB插入阻塞隊(duì)列中，等到事件的發(fā)生或操作的完成。（3）系統(tǒng)將處理機(jī)重新分派給另一就緒進(jìn)程，按照新進(jìn)程的處理機(jī)狀態(tài)更新處理機(jī)環(huán)境，就緒進(jìn)程開(kāi)始執(zhí)行。（4）當(dāng)被阻塞進(jìn)程等待的事件發(fā)生或者等待的操作完成時(shí)，則操作系統(tǒng)會(huì)通過(guò)喚醒原語(yǔ)將等待該事件的進(jìn)程喚醒。3.2.3進(jìn)程阻塞和喚醒382.進(jìn)程喚醒當(dāng)被阻塞進(jìn)程等待的事件發(fā)生，如等待的I/O操作已完成，或者等待的操作完成時(shí)，則操作系統(tǒng)會(huì)通過(guò)喚醒原語(yǔ)將等待該事件的進(jìn)程喚醒。喚醒原語(yǔ)（Wakeupprimitive）的具體步驟：（1）根據(jù)進(jìn)程標(biāo)識(shí)符從等待該事件的阻塞隊(duì)列中找到需要喚醒的進(jìn)程PCB。（2）將PCB中的進(jìn)程狀態(tài)阻塞改成就緒，并將該進(jìn)程插入到就緒隊(duì)列中。3.2.3進(jìn)程阻塞和喚醒391.進(jìn)程掛起當(dāng)系統(tǒng)中出現(xiàn)了引起掛起的事件，如內(nèi)存資源不足時(shí)，操作系統(tǒng)將利用掛起原語(yǔ)將處于阻塞狀態(tài)的進(jìn)程掛起。掛起原語(yǔ)（Suspendprimitive）的具體步驟：（1）根據(jù)進(jìn)程標(biāo)示符，在PCB集合中找到需要掛起的進(jìn)程。（2）檢查掛起進(jìn)程的狀態(tài)。3.2.4進(jìn)程掛起和激活402.進(jìn)程激活激活，對(duì)應(yīng)于掛起，是讓被掛起的進(jìn)程重新活躍起來(lái)，也就是把進(jìn)程從外存調(diào)入到內(nèi)存中。當(dāng)系統(tǒng)中出現(xiàn)了引起激活的事件時(shí)，操作系統(tǒng)會(huì)利用激活原語(yǔ)將掛起進(jìn)程激活。激活原語(yǔ)（Activeprimitive）的具體步驟：（1）根據(jù)進(jìn)程標(biāo)示符，在PCB集合中找到需要激活的進(jìn)程。（2）檢查激活進(jìn)程的狀態(tài)。3.2.4進(jìn)程掛起和激活41早期的計(jì)算機(jī)操作系統(tǒng)中，進(jìn)程既是資源分配的基本單位，又是調(diào)度的基本單位操作系統(tǒng)發(fā)展至今，進(jìn)程在調(diào)度中會(huì)存在許多問(wèn)題，增加了調(diào)度的難度和開(kāi)銷例如：現(xiàn)代操作系統(tǒng)很重要的一方面是進(jìn)程的并發(fā)執(zhí)行，然而進(jìn)程的并發(fā)執(zhí)行使得進(jìn)程調(diào)度的開(kāi)銷日益增大，系統(tǒng)效率明顯降低3.3線程42進(jìn)程包含兩方面的特點(diǎn)：

（1）資源所有權(quán)，進(jìn)程是一個(gè)可擁有資源的獨(dú)立單位。（2）調(diào)度，進(jìn)程同時(shí)又是一個(gè)可獨(dú)立調(diào)度和分派的基本單位。一個(gè)進(jìn)程沿著通過(guò)一個(gè)或多個(gè)程序的一條執(zhí)行路徑執(zhí)行。執(zhí)行中可能與其它進(jìn)程的執(zhí)行過(guò)程交替進(jìn)行，所以，一個(gè)進(jìn)程具有一個(gè)執(zhí)行狀態(tài)和一個(gè)分派的優(yōu)先級(jí)，同時(shí)又是一個(gè)能被操作系統(tǒng)調(diào)度和分派的實(shí)體。3.3.1線程簡(jiǎn)介43在操作系統(tǒng)中引入進(jìn)程的目的，是為了使多個(gè)程序能并發(fā)執(zhí)行，以提高資源利用率和系統(tǒng)吞吐量。在操作系統(tǒng)中再引入線程，則是為了減少程序在并發(fā)執(zhí)行時(shí)所付出的時(shí)空開(kāi)銷，使操作系統(tǒng)具有更好的并發(fā)性。通常把調(diào)度和分派的基本單位稱做線程或輕量級(jí)進(jìn)程（Lightweightprocess,LWP）,而把資源分配的基本單位稱做進(jìn)程或者任務(wù)。3.3.1線程簡(jiǎn)介441.多線程概念進(jìn)程在任一時(shí)刻只有一個(gè)執(zhí)行控制流，通常將這種結(jié)構(gòu)的進(jìn)程稱為單線程進(jìn)程（Singlethreadedprocess）。多線程進(jìn)程（Multiplethreadedprocess）——同一進(jìn)程中設(shè)計(jì)出多條控制流，并且滿足：（1）多控制流之間可以并行執(zhí)行；

（2）多控制流切換不需通過(guò)進(jìn)程調(diào)度；（3）多控制流之間可以通過(guò)內(nèi)存直接通信聯(lián)系，從而降低通信開(kāi)銷。3.3.2多線程45圖3.7進(jìn)程和線程3.3.2多線程46比如每下載一個(gè)文件可以單獨(dú)開(kāi)一個(gè)線程2.多線程環(huán)境下的進(jìn)程和線程（1）多線程環(huán)境下的進(jìn)程在多線程環(huán)境中，進(jìn)程被定義為資源分配的基本單位，與進(jìn)程相關(guān)的有：存放進(jìn)程映象的虛擬地址空間受保護(hù)地對(duì)處理器、其他進(jìn)程、文件和I/O資源的訪問(wèn)3.3.2多線程47（2）多線程環(huán)境下的線程一個(gè)進(jìn)程內(nèi)包含一個(gè)或者多個(gè)線程，每個(gè)線程都包含：線程執(zhí)行狀態(tài)當(dāng)線程處于非運(yùn)行狀態(tài)時(shí)，有一個(gè)受保護(hù)的線程上下文，用于存儲(chǔ)現(xiàn)場(chǎng)信息一個(gè)執(zhí)行堆棧容納每個(gè)線程的局部變量的存儲(chǔ)空間與進(jìn)程內(nèi)的其它線程共享訪問(wèn)進(jìn)程的內(nèi)存空間和資源3.3.2多線程48線程的主要特性：（1）并發(fā)性（2）共享性（3）動(dòng)態(tài)性（4）結(jié)構(gòu)性3.3.2多線程49圖3.8單線程和多線程環(huán)境下的進(jìn)程模型3.3.2多線程503.線程狀態(tài)線程的關(guān)鍵狀態(tài)有：運(yùn)行態(tài)、就緒態(tài)和阻塞態(tài)與線程狀態(tài)轉(zhuǎn)換相關(guān)的操作：派生阻塞解除阻塞結(jié)束3.3.2多線程51進(jìn)程與線程的區(qū)別:進(jìn)程和線程的主要差別在于它們是不同的操作系統(tǒng)資源管理方式。進(jìn)程有獨(dú)立的地址空間，一個(gè)進(jìn)程崩潰后，在保護(hù)模式下不會(huì)對(duì)其它進(jìn)程產(chǎn)生影響，而線程只是一個(gè)進(jìn)程中的不同執(zhí)行路徑。線程有自己的堆棧和局部變量，但線程之間沒(méi)有單獨(dú)的地址空間，一個(gè)線程死掉就等于整個(gè)進(jìn)程死掉，所以多進(jìn)程的程序要比多線程的程序健壯，但在進(jìn)程切換時(shí)，耗費(fèi)資源較大，效率要差一些。但對(duì)于一些要求同時(shí)進(jìn)行并且又要共享某些變量的并發(fā)操作，只能用線程，不能用進(jìn)程。進(jìn)程與線程的區(qū)別:1)簡(jiǎn)而言之,一個(gè)程序至少有一個(gè)進(jìn)程,一個(gè)進(jìn)程至少有一個(gè)線程.2)線程的劃分尺度小于進(jìn)程，使得多線程程序的并發(fā)性高。3)進(jìn)程在執(zhí)行過(guò)程中擁有獨(dú)立的內(nèi)存單元，而多個(gè)線程共享內(nèi)存，從而極大地提高了程序的運(yùn)行效率。4)從邏輯角度來(lái)看，多線程的意義在于一個(gè)應(yīng)用程序中，有多個(gè)執(zhí)行部分可以同時(shí)執(zhí)行。但操作系統(tǒng)并沒(méi)有將多個(gè)線程看做多個(gè)獨(dú)立的應(yīng)用，來(lái)實(shí)現(xiàn)進(jìn)程的調(diào)度和管理以及資源分配。例如：下載一個(gè)文件可以開(kāi)多個(gè)線程。線程和進(jìn)程的優(yōu)缺點(diǎn):線程和進(jìn)程在使用上各有優(yōu)缺點(diǎn)：線程執(zhí)行開(kāi)銷小，但不利于資源的管理和保護(hù)；而進(jìn)程正相反。線程適合于在對(duì)稱多處理機(jī)系統(tǒng)機(jī)器上運(yùn)行，而進(jìn)程則可以跨機(jī)器遷移。引入線程帶來(lái)的主要好處：主要好處：(1)在進(jìn)程內(nèi)創(chuàng)建、終止線程比創(chuàng)建、終止進(jìn)程要快；(2)同一進(jìn)程內(nèi)的線程間切換比進(jìn)程間的切換要快,尤其是用戶級(jí)線程間的切換。深入理解進(jìn)程就是一個(gè)程序運(yùn)行的時(shí)候被CPU抽象出來(lái)的，一個(gè)程序運(yùn)行后被抽象為一個(gè)進(jìn)程，但是線程是從一個(gè)進(jìn)程里面分割出來(lái)的，由于CPU處理進(jìn)程的時(shí)候是采用時(shí)間片輪轉(zhuǎn)的方式，所以要把一個(gè)大個(gè)進(jìn)程給分割成多個(gè)線程。例如：網(wǎng)際快車中文件分成100部分10個(gè)線程文件就被分成了10份來(lái)同時(shí)下載1-10占一個(gè)線程11-20占一個(gè)線程,依次類推,線程越多,文件就被分的越多,同時(shí)下載當(dāng)然速度也就越快。深入理解進(jìn)程是程序在計(jì)算機(jī)上的一次執(zhí)行活動(dòng)。當(dāng)你運(yùn)行一個(gè)程序，你就啟動(dòng)了一個(gè)進(jìn)程。顯然，程序只是一組指令的有序集合，它本身沒(méi)有任何運(yùn)行的含義，只是一個(gè)靜態(tài)實(shí)體。而進(jìn)程則不同，它是程序在某個(gè)數(shù)據(jù)集上的執(zhí)行，是一個(gè)動(dòng)態(tài)實(shí)體。它因創(chuàng)建而產(chǎn)生，因調(diào)度而運(yùn)行，因等待資源或事件而被處于等待狀態(tài)，因完成任務(wù)而被撤消，反映了一個(gè)程序在一定的數(shù)據(jù)集上運(yùn)行的全部動(dòng)態(tài)過(guò)程。進(jìn)程是操作系統(tǒng)分配資源的單位。在Windows下，進(jìn)程又被細(xì)化為線程，也就是一個(gè)進(jìn)程下有多個(gè)能獨(dú)立運(yùn)行的更小的單位。線程(Thread)是進(jìn)程的一個(gè)實(shí)體，是CPU調(diào)度和分派的基本單位深入理解線程和進(jìn)程的關(guān)系

線程是屬于進(jìn)程的，線程運(yùn)行在進(jìn)程空間內(nèi)，同一進(jìn)程所產(chǎn)生的線程共享同一內(nèi)存空間，當(dāng)進(jìn)程退出時(shí)該進(jìn)程所產(chǎn)生的線程都會(huì)被強(qiáng)制退出并清除。線程可與屬于同一進(jìn)程的其它線程共享進(jìn)程所擁有的全部資源，但是其本身基本上不擁有系統(tǒng)資源，只擁有一點(diǎn)在運(yùn)行中必不可少的信息(如程序計(jì)數(shù)器、一組寄存器和棧)。深入理解

在同一個(gè)時(shí)間里，同一個(gè)計(jì)算機(jī)系統(tǒng)中如果允許兩個(gè)或兩個(gè)以上的進(jìn)程處于運(yùn)行狀態(tài)，這便是多任務(wù)。現(xiàn)代的操作系統(tǒng)幾乎都是多任務(wù)操作系統(tǒng)，能夠同時(shí)管理多個(gè)進(jìn)程的運(yùn)行。多任務(wù)帶來(lái)的好處是明顯的，比如你可以邊聽(tīng)mp3邊上網(wǎng)，與此同時(shí)甚至可以將下載的文檔打印出來(lái)，而這些任務(wù)之間絲毫不會(huì)相互干擾。就是說(shuō)只有一顆心，要讓它一心多用，同時(shí)運(yùn)行多個(gè)進(jìn)程，就必須使用并發(fā)技術(shù)。深入理解-并發(fā)技術(shù)時(shí)間片輪轉(zhuǎn)進(jìn)程調(diào)度算法在操作系統(tǒng)的管理下，所有正在運(yùn)行的進(jìn)程輪流使用CPU，每個(gè)進(jìn)程允許占用CPU的時(shí)間非常短(比如10毫秒)，這樣用戶根本感覺(jué)不出來(lái)CPU是在輪流為多個(gè)進(jìn)程服務(wù)，就好象所有的進(jìn)程都在不間斷地運(yùn)行一樣。但實(shí)際上在任何一個(gè)時(shí)間內(nèi)有且僅有一個(gè)進(jìn)程占有CPU。如果一臺(tái)計(jì)算機(jī)有多個(gè)CPU，情況就不同了，如果進(jìn)程數(shù)小于CPU數(shù)，則不同的進(jìn)程可以分配給不同的CPU來(lái)運(yùn)行，這樣，多個(gè)進(jìn)程就是真正同時(shí)運(yùn)行的，這便是并行。但如果進(jìn)程數(shù)大于CPU數(shù)，則仍然需要使用并發(fā)技術(shù)。1.線程實(shí)現(xiàn)（1）用戶級(jí)線程（Userlevelthread,ULT）

線程管理的所有工作都由應(yīng)用程序完成，內(nèi)核意識(shí)不到線程的存在。3.3.3線程實(shí)現(xiàn)與線程模型61用戶級(jí)線程方式優(yōu)點(diǎn)：因?yàn)樗芯€程的管理數(shù)據(jù)結(jié)構(gòu)都在該進(jìn)程的用戶空間中，因此，線程切換不需要轉(zhuǎn)換到內(nèi)核空間，從而節(jié)省了模式切換的開(kāi)銷。調(diào)度算法可以是基于不同進(jìn)程量身定做。不同進(jìn)程可以根據(jù)自身需要，為自己量身定做適合自身的調(diào)度算法對(duì)線程進(jìn)行管理和調(diào)度。用戶級(jí)線程的實(shí)現(xiàn)與操作系統(tǒng)平臺(tái)無(wú)關(guān)，即可以在任何操作系統(tǒng)中運(yùn)行。3.3.3線程實(shí)現(xiàn)與線程模型62用戶級(jí)線程方式缺點(diǎn)：許多系統(tǒng)調(diào)用會(huì)引起阻塞，當(dāng)用戶級(jí)線程執(zhí)行一個(gè)系統(tǒng)調(diào)用時(shí)，不僅該線程會(huì)被阻塞，而且該線程所在進(jìn)程內(nèi)的所有線程都會(huì)被阻塞。但是，如果在內(nèi)核級(jí)線程方式中，一個(gè)線程被阻塞，進(jìn)程中的其它線程仍然可以運(yùn)行。在純粹的用戶級(jí)線程實(shí)現(xiàn)方式中，多線程應(yīng)用不能利用多處理機(jī)技術(shù)進(jìn)行多重處理。內(nèi)核一次只為每個(gè)進(jìn)程分配一個(gè)處理器，即進(jìn)程每次只有一個(gè)線程處于運(yùn)行狀態(tài)，其它線程此時(shí)只能等待。3.3.3線程實(shí)現(xiàn)與線程模型63（2）內(nèi)核級(jí)線程（Kernellevelthread,KLT）

線程管理的所有工作都是由內(nèi)核完成，應(yīng)用程序并沒(méi)有參與其中。即無(wú)論是用戶進(jìn)程中的線程，還是系統(tǒng)進(jìn)程中的線程，他們的創(chuàng)建、終止和切換等也是依靠?jī)?nèi)核，在內(nèi)核空間實(shí)現(xiàn)的。3.3.3線程實(shí)現(xiàn)與線程模型64內(nèi)核級(jí)線程方式優(yōu)點(diǎn)：內(nèi)核能夠同時(shí)為同一進(jìn)程中的多個(gè)線程分配多個(gè)處理器，即能讓多個(gè)線程并行執(zhí)行。如果進(jìn)程中的一個(gè)線程被阻塞了，內(nèi)核可以為該進(jìn)程中的其它線程分派處理器資源使其運(yùn)行，當(dāng)然也可以調(diào)度其它進(jìn)程中的線程運(yùn)行。內(nèi)核本身也可以采用多線程技術(shù)，可以提高系統(tǒng)的執(zhí)行速度和效率。3.3.3線程實(shí)現(xiàn)與線程模型65內(nèi)核級(jí)線程方式缺點(diǎn)：因?yàn)榫€程調(diào)度和管理是在內(nèi)核實(shí)現(xiàn)，而用戶進(jìn)程的線程卻是在用戶態(tài)下運(yùn)行。因此在進(jìn)行線程與同一進(jìn)程內(nèi)其它線程切換時(shí)，需要從用戶態(tài)轉(zhuǎn)到內(nèi)核態(tài)進(jìn)行，從而導(dǎo)致較大的系統(tǒng)開(kāi)銷。3.3.3線程實(shí)現(xiàn)與線程模型66（3）組合方式

同一個(gè)進(jìn)程內(nèi)的多個(gè)線程可以同時(shí)在多處理器上并行執(zhí)行，而且一個(gè)線程被阻塞時(shí)，同一進(jìn)程內(nèi)的其它線程可以調(diào)度運(yùn)行，并不需要阻塞整個(gè)進(jìn)程。所以，組合方式多線程機(jī)制能夠結(jié)合KLT和ULT兩者的優(yōu)點(diǎn)，并克服了其各自的不足。3.3.3線程實(shí)現(xiàn)與線程模型67圖3.9線程實(shí)現(xiàn)方式3.3.3線程實(shí)現(xiàn)與線程模型682.線程模型（1）多對(duì)一模型3.3.3線程實(shí)現(xiàn)與線程模型69圖3.10多對(duì)一模型（2）一對(duì)一模型3.3.3線程實(shí)現(xiàn)與線程模型70圖3.11一對(duì)一模型（3）多對(duì)多模型3.3.3線程實(shí)現(xiàn)與線程模型71圖3.12多對(duì)多模型操作系統(tǒng)設(shè)計(jì)中的核心問(wèn)題是關(guān)于進(jìn)程和線程的管理：采用多道程序設(shè)計(jì)技術(shù)管理單處理器系統(tǒng)中的多個(gè)進(jìn)程采用多處理技術(shù)管理多處理器系統(tǒng)中的多個(gè)進(jìn)程采用分布式處理技術(shù)管理多臺(tái)分布式計(jì)算機(jī)系統(tǒng)中的多個(gè)進(jìn)程并發(fā)是上述管理問(wèn)題實(shí)現(xiàn)的基礎(chǔ)，也是操作系統(tǒng)設(shè)計(jì)的核心3.4互斥和同步72并發(fā)涉及的術(shù)語(yǔ)：（1）臨界區(qū)（Criticalsection）（2）競(jìng)爭(zhēng)（Competition）（3）同步（Synchronization）（4）互斥（Mutualexclusion）（5）死鎖（Deadlock）（6）饑餓（Starvation）3.4.1并發(fā)原理73臨界區(qū)（Criticalsection）每個(gè)進(jìn)程中訪問(wèn)臨界資源的那段代碼稱為臨界區(qū)（CriticalSection）（臨界資源是一次僅允許一個(gè)進(jìn)程使用的共享資源）。每次只準(zhǔn)許一個(gè)進(jìn)程進(jìn)入臨界區(qū)，進(jìn)入后不允許其他進(jìn)程進(jìn)入。不論是硬件臨界資源，還是軟件臨界資源，多個(gè)進(jìn)程必須互斥地對(duì)它進(jìn)行訪問(wèn)。Critical：關(guān)鍵的;批評(píng)的，愛(ài)挑剔的;嚴(yán)重的;極重要的;進(jìn)程進(jìn)入臨界區(qū)的調(diào)度原則是：1、如果有若干進(jìn)程要求進(jìn)入空閑的臨界區(qū)，一次僅允許一個(gè)進(jìn)程進(jìn)入。2、任何時(shí)候，處于臨界區(qū)內(nèi)的進(jìn)程不可多于一個(gè)。如已有進(jìn)程進(jìn)入自己的臨界區(qū)，則其它所有試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待。3、進(jìn)入臨界區(qū)的進(jìn)程要在有限時(shí)間內(nèi)退出，以便其它進(jìn)程能及時(shí)進(jìn)入自己的臨界區(qū)。4、如果進(jìn)程不能進(jìn)入自己的臨界區(qū)，則應(yīng)讓出CPU，避免進(jìn)程出現(xiàn)“忙等”現(xiàn)象。競(jìng)爭(zhēng)（Competition）多個(gè)線程或者進(jìn)程在讀寫一個(gè)共享數(shù)據(jù)時(shí)結(jié)果依賴于它們執(zhí)行的相對(duì)時(shí)間，這種情形叫做競(jìng)爭(zhēng)。競(jìng)爭(zhēng)條件發(fā)生在當(dāng)多個(gè)進(jìn)程或者線程在讀寫數(shù)據(jù)時(shí)，其最終的的結(jié)果依賴于多個(gè)進(jìn)程的指令執(zhí)行順序。例如：假設(shè)兩個(gè)進(jìn)程P1和P2共享了變量a。在某一執(zhí)行時(shí)刻，P1更新a為1，在另一時(shí)刻，P2更新a為2。因此兩個(gè)任務(wù)競(jìng)爭(zhēng)地寫變量a。在這個(gè)例子中，競(jìng)爭(zhēng)的“失敗者”(最后更新的進(jìn)程）決定了變量a的最終值。多個(gè)進(jìn)程并發(fā)訪問(wèn)和操作同一數(shù)據(jù)且執(zhí)行結(jié)果與訪問(wèn)的特定順序有關(guān)，稱為競(jìng)爭(zhēng)條件。同步（Synchronization）

同步是指在多道程序環(huán)境下，進(jìn)程是并發(fā)執(zhí)行的，不同進(jìn)程之間存在著不同的相互制約關(guān)系。我們把異步環(huán)境下的一組并發(fā)進(jìn)程因直接制約而互相發(fā)送消息、進(jìn)行互相合作、互相等待，使得各進(jìn)程按一定的速度執(zhí)行的過(guò)程稱為進(jìn)程間的同步。互斥（Mutualexclusion）兩個(gè)或兩個(gè)以上的進(jìn)程，不能同時(shí)進(jìn)入關(guān)于同一組共享變量的臨界區(qū)域，否則可能發(fā)生與時(shí)間有關(guān)的錯(cuò)誤，這種現(xiàn)象被稱作進(jìn)程互斥。

exclusion:拒絕，杜絕;排除，驅(qū)逐;（或事物）被排斥在外的人;排外主義;死鎖(deadlock)

死鎖是指兩個(gè)或兩個(gè)以上的進(jìn)程在執(zhí)行過(guò)程中，由于競(jìng)爭(zhēng)資源或者由于彼此通信而造成的一種阻塞的現(xiàn)象，若無(wú)外力作用，它們都將無(wú)法推進(jìn)下去。此時(shí)執(zhí)行程序中兩個(gè)或多個(gè)線程發(fā)生永久堵塞（等待），每個(gè)線程都在等待被其他線程占用并堵塞了的資源。例如，線程A和線程Ｂ都需要訪問(wèn)記錄1和2，如果線程A鎖住了記錄1并等待記錄2，而線程B鎖住了記錄2并等待記錄1，這樣兩個(gè)線程就發(fā)生了死鎖現(xiàn)象。Deadlock:僵局;停頓，停滯;沒(méi)有彈簧的鎖;成僵局;饑餓（Starvation）

饑餓是指一個(gè)可運(yùn)行的進(jìn)程雖然能繼續(xù)執(zhí)行，但被調(diào)度程序無(wú)限期地忽視而不能執(zhí)行的情況。舉個(gè)例子，當(dāng)有多個(gè)進(jìn)程需要打印文件時(shí)，如果系統(tǒng)分配打印機(jī)的策略是最短文件優(yōu)先，那么長(zhǎng)文件的打印任務(wù)將由于短文件的源源不斷到來(lái)而被無(wú)限期推遲，導(dǎo)致最終的饑餓甚至餓死。

1.兩種制約關(guān)系（1）直接相互制約關(guān)系------進(jìn)程同步（2）間接相互制約關(guān)系------進(jìn)程互斥3.4.1并發(fā)原理811、進(jìn)程之間兩種形式的制約關(guān)系系統(tǒng)中諸進(jìn)程之間在邏輯上存在著兩種制約關(guān)系：直接制約關(guān)系（進(jìn)程同步）：即為完成同一個(gè)任務(wù)的諸進(jìn)程間，因需要協(xié)調(diào)它們的工作而相互等待、相互交換信息所產(chǎn)生的直接制約關(guān)系。

間接制約關(guān)系（進(jìn)程互斥）：是進(jìn)程共享獨(dú)占型資源而必須互斥執(zhí)行的間接制約關(guān)系。同步與互斥比較同步互斥進(jìn)程-進(jìn)程進(jìn)程-資源-進(jìn)程時(shí)間次序上受到某種限制競(jìng)爭(zhēng)到某一物理資源時(shí)不允許進(jìn)程工作相互清楚對(duì)方的存在及作用，交換信息不一定清楚其它進(jìn)程情況往往指有幾個(gè)進(jìn)程共同完成一個(gè)任務(wù)往往指多個(gè)任務(wù)多個(gè)進(jìn)程間相互制約例：生產(chǎn)與消費(fèi)之間，作者與讀者之間例：交通十字路口互斥與同步所謂互斥，是指散步在不同進(jìn)程之間的若干程序片斷(臨界區(qū))，當(dāng)某個(gè)進(jìn)程運(yùn)行其中一個(gè)程序片段時(shí)，其它進(jìn)程就不能運(yùn)行它們之中的任一程序片段，只能等到該進(jìn)程運(yùn)行完這個(gè)程序片段后才可以運(yùn)行。所謂同步，是指散步在不同進(jìn)程之間的若干程序片斷，它們的運(yùn)行必須嚴(yán)格按照規(guī)定的某種先后次序來(lái)運(yùn)行，這種先后次序依賴于要完成的特定的任務(wù)。

顯然，同步是一種更為復(fù)雜的互斥，而互斥是一種特殊的同步?；コ馀c同步互斥是兩個(gè)線程之間不可以同時(shí)運(yùn)行，他們會(huì)相互排斥，必須等待一個(gè)線程運(yùn)行完畢，另一個(gè)才能運(yùn)行，而同步也是不能同時(shí)運(yùn)行，但他是必須要安照某種次序來(lái)運(yùn)行相應(yīng)的線程。

互斥：是指某一資源同時(shí)只允許一個(gè)訪問(wèn)者對(duì)其進(jìn)行訪問(wèn)，具有唯一性和排它性。但互斥無(wú)法限制訪問(wèn)者對(duì)資源的訪問(wèn)順序，即訪問(wèn)是無(wú)序的。

同步：是指在互斥的基礎(chǔ)上（大多數(shù)情況），通過(guò)其它機(jī)制實(shí)現(xiàn)訪問(wèn)者對(duì)資源的有序訪問(wèn)。在大多數(shù)情況下，同步已經(jīng)實(shí)現(xiàn)了互斥，特別是所有寫入資源的情況必定是互斥的。少數(shù)情況是指可以允許多個(gè)訪問(wèn)者同時(shí)訪問(wèn)資源。為什么就買一個(gè)燒餅妻子對(duì)正要上班出門丈夫說(shuō)：“晚上回來(lái)時(shí)買兩個(gè)燒餅，如果看到賣西瓜的，就買一個(gè)?！?/p>

轉(zhuǎn)眼到了下午下班，丈夫回到家把一個(gè)燒餅放到桌上，妻子怒問(wèn)：”為什么就買一個(gè)燒餅？！“丈夫答曰：”因?yàn)槲铱吹搅速u西瓜的?！耙?yàn)樗煞蚴浅绦騿T.程序員的愿望有一天，一個(gè)程序員見(jiàn)到了上帝.

上帝:

小伙子,我可以滿足你一個(gè)愿望.程序員:

我希望中國(guó)國(guó)家隊(duì)能再次打進(jìn)世界杯.

上帝:

這個(gè)啊!這個(gè)不好辦啊,你還說(shuō)下一個(gè)吧!程序員:

那好!我的下一個(gè)愿望是每天都能休息6個(gè)小時(shí)以上.

上帝:

還是讓中國(guó)國(guó)家打進(jìn)世界杯.3.4.1并發(fā)原理重點(diǎn)部分難點(diǎn)部分AND2.臨界區(qū)和臨界資源進(jìn)程間競(jìng)爭(zhēng)資源產(chǎn)生如下的幾個(gè)控制問(wèn)題（1）互斥（2）死鎖（3）饑餓3.4.1并發(fā)原理90一次只允許一個(gè)進(jìn)程使用的資源稱為臨界資源(CriticalResource)，如打印機(jī)、繪圖機(jī)、變量、數(shù)據(jù)等，進(jìn)程之間采取互斥方式式實(shí)現(xiàn)對(duì)臨界資源的共享，從而實(shí)現(xiàn)并行程序的封閉性。引起不可再現(xiàn)性是因?yàn)閷?duì)臨界資源沒(méi)有進(jìn)行互斥訪問(wèn)。在每個(gè)進(jìn)程中，訪問(wèn)臨界資源的那一段代碼稱為臨界區(qū)（CriticalSection），簡(jiǎn)稱CS區(qū)。

例：有兩個(gè)進(jìn)程A和B，它們共享一個(gè)變量X，且兩個(gè)進(jìn)程按以下方式對(duì)變量X進(jìn)行訪問(wèn)和修改，其中R1和R2為處理機(jī)中的兩個(gè)寄存器(或變量)。A:R1=X;R1=R1+1;X=R1;B:R2=X;R2=R2+1;X=R2;

A與B均對(duì)X加1，即X加2。臨界區(qū)臨界區(qū)產(chǎn)生錯(cuò)誤的原因：不加控制地訪問(wèn)共享變量X對(duì)臨界區(qū)需要進(jìn)行保護(hù)（互斥訪問(wèn)）結(jié)果X只加了1A:R1=X;B:R2=X;A:R1=R1+1;X=R1;B:R2=R2+1;X=R2;如果按另一順序?qū)ψ兞窟M(jìn)行修改為了保證臨界資源的正確使用，可以把臨界資源的訪問(wèn)過(guò)程分成以下幾部分：進(jìn)入?yún)^(qū)臨界區(qū)退出區(qū)剩余區(qū)進(jìn)入?yún)^(qū)：增加在臨界區(qū)前面的一段代碼，用于檢查欲訪問(wèn)的臨界資源此刻是否被訪問(wèn)。退出區(qū)：增加在臨界區(qū)后面的一段代碼，用于將臨界資源的訪問(wèn)標(biāo)志恢復(fù)為未被訪問(wèn)標(biāo)志。臨界區(qū)：進(jìn)程訪問(wèn)臨界資源的那段代碼。剩余區(qū)：進(jìn)程中除了進(jìn)入?yún)^(qū)、臨界區(qū)及退出區(qū)之外的其余代碼。多個(gè)進(jìn)程共享臨界區(qū)，需遵循如下的調(diào)度原則：空閑讓進(jìn):當(dāng)無(wú)進(jìn)程處于臨界區(qū)時(shí)，表明臨界資源處于空閑狀態(tài)，應(yīng)允許一個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)，以有效地利用臨界資源。忙則等待:當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時(shí)，表明臨界資源正在被訪問(wèn)，因而其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證對(duì)臨界資源的互斥訪問(wèn)。有限等待:對(duì)要求訪問(wèn)臨界資源的進(jìn)程，應(yīng)保證在有限時(shí)間內(nèi)能進(jìn)入自己的臨界區(qū)，以免陷入死等狀態(tài)。讓權(quán)等待:當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入忙等。95同步機(jī)制解決臨界區(qū)（互斥）問(wèn)題的幾類方法軟件方法用編程解決。重點(diǎn)：信號(hào)量及P-V操作硬件方法用硬件指令解決。1.關(guān)中斷訪問(wèn)共享資源的最簡(jiǎn)單的方法是關(guān)中斷：一個(gè)任務(wù)在對(duì)共享資源進(jìn)行訪問(wèn)前將中斷關(guān)閉，然后執(zhí)行訪問(wèn)共享資源的關(guān)鍵段落代碼，訪問(wèn)共享資源結(jié)束后再打開(kāi)終端。3.4.2硬件同步971.關(guān)中斷while(true){/*關(guān)中斷*//*臨界區(qū)*//*開(kāi)中斷*//*其余部分*/}缺點(diǎn)：3.4.2硬件同步98關(guān)中斷的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：簡(jiǎn)單。缺點(diǎn)：

1.代價(jià)高，效率低：限制了處理器交替執(zhí)行各進(jìn)程的能力。

2.不能用于多處理器：關(guān)中斷不能保證互斥。

3.影響系統(tǒng)的實(shí)時(shí)。為了減輕對(duì)系統(tǒng)實(shí)時(shí)性的不利影響，訪問(wèn)共享資源的關(guān)鍵段落代碼必須盡量簡(jiǎn)短，絕對(duì)不允許在關(guān)鍵段落代碼中包含有可能使自己掛起的系統(tǒng)服務(wù)函數(shù)；否則將使系統(tǒng)死機(jī)。由于關(guān)中斷直接影響系統(tǒng)的實(shí)時(shí)性，因此只能用于對(duì)簡(jiǎn)單共享資源的短暫訪問(wèn)。由此可以得出，關(guān)中斷方法常用于對(duì)全局變量和小規(guī)模全局?jǐn)?shù)據(jù)結(jié)構(gòu)的訪問(wèn)。2.TestAndSet指令（自旋鎖

）

自旋鎖是專為防止多處理器并發(fā)而引入的一種鎖，它在內(nèi)核中大量應(yīng)用于中斷處理等部分，是為了解決對(duì)某項(xiàng)資源的互斥使用。在任何時(shí)刻最多只能有一個(gè)執(zhí)行單元獲得鎖。對(duì)于互斥鎖，如果資源已經(jīng)被占用，資源申請(qǐng)者只能進(jìn)入睡眠狀態(tài)。但是自旋鎖不會(huì)引起調(diào)用者睡眠，如果自旋鎖已經(jīng)被別的執(zhí)行單元保持，調(diào)用者就一直循環(huán)在那里看是否該自旋鎖的保持者已經(jīng)釋放了鎖，"自旋"一詞就是因此而得名。3.4.2硬件同步1002.TestAndSet指令（自旋鎖

）TestAndSet指令描述如下：booleanTestAndSet(boolean*lock){

booleantemp=*lock;

*lock=TRUE;

returntemp;}3.4.2硬件同步101實(shí)參值為真，則返回真，不改變實(shí)參的值。實(shí)參值為假，則返回假，同時(shí)改變實(shí)值的值為真。TestAndSet指令實(shí)現(xiàn)互斥的示例如下：lock=FALSE;

……do{while(TestAndSet(&lock));

//donothing不做任何事

//criticalsection臨界區(qū)

lock=FALSE;表示空閑

//remaindersection其他代碼}while(TRUE);3.4.2硬件同步102booleanTestAndSet(boolean*lock){

booleantemp=*lock;

*lock=TRUE;

returntemp;}自旋鎖存在的問(wèn)題死鎖。試圖遞歸地獲得自旋鎖必然會(huì)引起死鎖。在遞歸程序中使用自旋鎖應(yīng)遵守下列策略：遞歸程序決不能在持有自旋鎖時(shí)調(diào)用它自己，也決不能在遞歸調(diào)用時(shí)試圖獲得相同的自旋鎖。此外如果一個(gè)進(jìn)程已經(jīng)將資源鎖定，那么，即使其它申請(qǐng)這個(gè)資源的進(jìn)程不停地瘋狂“自旋”,也無(wú)法獲得資源，從而進(jìn)入死循環(huán)。過(guò)多占用cpu資源。如果不加限制，由于申請(qǐng)者一直在循環(huán)等待，因此自旋鎖在鎖定的時(shí)候,如果不成功,不會(huì)睡眠,會(huì)持續(xù)的嘗試,單cpu的時(shí)候自旋鎖會(huì)讓其它進(jìn)程動(dòng)不了.因此，一般自旋鎖實(shí)現(xiàn)會(huì)有一個(gè)參數(shù)限定最多持續(xù)嘗試次數(shù).超出后,自旋鎖放棄當(dāng)前時(shí)間片.等下一次機(jī)會(huì)3.Swap指令Swap指令為對(duì)換指令，定義如下：voidSwap(boolean*a,boolean*b){Booleantemp=*a;*a=*b;*b=temp;}3.4.2硬件同步104功能：將a,b指針指向的值互換使用Swap指令實(shí)現(xiàn)互斥的示例如下：Lock=false：//全局變量；do{data=TRUE;//局部變量while(data==TRUE)Swap(&lock,&data);//criticalsection臨界區(qū)lock=FALSE;//remindersection其他部分}while(TRUE);3.4.2硬件同步105硬件實(shí)現(xiàn)的優(yōu)點(diǎn)與缺點(diǎn)：硬件方法的優(yōu)點(diǎn)：適用于任意數(shù)目的進(jìn)程，不管是單處理機(jī)還是多處理機(jī)；簡(jiǎn)單、容易驗(yàn)證其正確性?？梢灾С诌M(jìn)程內(nèi)有多個(gè)臨界區(qū)，只需為每個(gè)臨界區(qū)設(shè)立一個(gè)布爾變量。

硬件方法的缺點(diǎn)：進(jìn)程等待進(jìn)入臨界區(qū)時(shí)要耗費(fèi)處理機(jī)時(shí)間，不能實(shí)現(xiàn)讓權(quán)等待。從等待進(jìn)程中隨機(jī)選擇一個(gè)進(jìn)入臨界區(qū)，有的進(jìn)程可能一直選不上，從而導(dǎo)致“饑餓”現(xiàn)象。

PV操作在操作系統(tǒng)中，PV操作是進(jìn)程管理中的難點(diǎn)。我國(guó)讀者常常不明白這一同步機(jī)制為什么叫PV操作，原來(lái)這是狄克斯特拉用荷蘭文定義的，因?yàn)樵诤商m文中，通過(guò)叫passeren，釋放叫vrijgeven，PV操作因此得名。這是在計(jì)算機(jī)術(shù)語(yǔ)中不是用英語(yǔ)表達(dá)的極少數(shù)的例子之一。P就是請(qǐng)求資源，V就是釋放資源。PV操作的含義PV操作由P操作原語(yǔ)和V操作原語(yǔ)組成（原語(yǔ)是不可中斷的過(guò)程），對(duì)信號(hào)量進(jìn)行操作，具體定義如下：

P（S）：①將信號(hào)量S的值減1，即S=S-1；②如果S≥0，則該進(jìn)程繼續(xù)執(zhí)行；否則該進(jìn)程置為等待狀態(tài)，排入等待隊(duì)列。

V（S）：①將信號(hào)量S的值加1，即S=S+1；②如果S>0，則該進(jìn)程繼續(xù)執(zhí)行；否則釋放隊(duì)列中第一個(gè)等待信號(hào)量的進(jìn)程。信號(hào)燈

所謂信號(hào)燈，實(shí)際上就是用來(lái)控制進(jìn)程狀態(tài)的一個(gè)代表某一資源的存儲(chǔ)單元。例如，P1和P2是分別將數(shù)據(jù)送入緩沖B和從緩沖B讀出數(shù)據(jù)的兩個(gè)進(jìn)程。對(duì)P1和P2可定義兩個(gè)信號(hào)量S1和S2，初值分別為1和0。進(jìn)程P1在向緩沖B送入數(shù)據(jù)前執(zhí)行P操作P（S1），在送入數(shù)據(jù)后執(zhí)行V操作V（S2）。進(jìn)程P2在從緩沖B讀取數(shù)據(jù)前先執(zhí)行P操作P（S2），在讀出數(shù)據(jù)后執(zhí)行V操作V（S1）。當(dāng)P1往緩沖B送入一數(shù)據(jù)后信號(hào)量S1之值變?yōu)?，在該數(shù)據(jù)讀出后S1之值才又變?yōu)?，因此在前一數(shù)未讀出前后一數(shù)不會(huì)送入，從而保證了P1和P2之間的同步。什么是信號(hào)量信號(hào)量值與相應(yīng)資源的使用情況有關(guān)。當(dāng)它的值大于0時(shí)，表示當(dāng)前可用資源的數(shù)量；當(dāng)它的值小于0時(shí)，其絕對(duì)值表示等待使用該資源的進(jìn)程個(gè)數(shù)。注意，信號(hào)量的值僅能由PV操作來(lái)改變。信號(hào)量信號(hào)量S≥0時(shí)，S表示可用資源的數(shù)量。執(zhí)行一次P操作意味著請(qǐng)求分配一個(gè)單位資源，因此S的值減1；當(dāng)S<0時(shí)，表示已經(jīng)沒(méi)有可用資源，請(qǐng)求者必須等待別的進(jìn)程釋放該類資源，它才能運(yùn)行下去。而執(zhí)行一個(gè)V操作意味著釋放一個(gè)單位資源，因此S的值加1；若S≤0，表示有某些進(jìn)程正在等待該資源，因此要喚醒一個(gè)等待狀態(tài)的進(jìn)程，使之運(yùn)行下去。實(shí)現(xiàn)進(jìn)程互斥的一般模型是：使用PV操作實(shí)現(xiàn)進(jìn)程互斥時(shí)應(yīng)該注意的是：

（1）每個(gè)程序中用戶實(shí)現(xiàn)互斥的P、V操作必須成對(duì)出現(xiàn)，先做P操作，進(jìn)臨界區(qū)，后做V操作，出臨界區(qū)。若有多個(gè)分支，要認(rèn)真檢查其成對(duì)性。

（2）P、V操作應(yīng)分別緊靠臨界區(qū)的頭尾部，臨界區(qū)的代碼應(yīng)盡可能短，不能有死循環(huán)。

（3）信號(hào)量S用于互斥，互斥信號(hào)量的初值一般為1。簡(jiǎn)單理解P，V操作

臨界區(qū)門前有棵樹(shù)，用來(lái)掛紅燈（信號(hào)量，初始為１）P操作：進(jìn)程想進(jìn)臨界區(qū)的門，先得上樹(shù)取下盞燈（調(diào)用一次P）取燈（S＝S－1）有燈（S＞=0），進(jìn)程進(jìn)入臨界區(qū)沒(méi)燈(S＜0)，進(jìn)程只好在門外邊（臨界區(qū)外）排隊(duì)等V操作：得燈的進(jìn)程繼續(xù)運(yùn)行，運(yùn)行完了要出門（調(diào)用一次V）馬上還回一盞燈（S＝S＋1）如果沒(méi)有進(jìn)程在等（S＞0），繼續(xù)運(yùn)行如果有進(jìn)程在等（S＜＝0），放個(gè)進(jìn)程進(jìn)去（臨界區(qū)）后，繼續(xù)運(yùn)行難點(diǎn)解析

V原語(yǔ)的主要操作是：（1）信號(hào)量（sem）加1；（2）若相加結(jié)果大于零，則進(jìn)程繼續(xù)執(zhí)行；（3）若相加結(jié)果小于或等于零，則喚醒一阻塞在該信號(hào)量上的進(jìn)程，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。疑問(wèn)1：以V原語(yǔ)的1、2步來(lái)做，Sem不就永遠(yuǎn)大于0，那進(jìn)程不就一直循環(huán)執(zhí)行成為死循環(huán)了？疑問(wèn)2：信號(hào)量大于0那就表示有臨界資源可供使用，為什么不喚醒進(jìn)程？疑問(wèn)3：信號(hào)量小于0應(yīng)該是說(shuō)沒(méi)有臨界資源可供使用，為什么還要喚醒進(jìn)程？Semaphoren.臂板信號(hào)系統(tǒng);

vt.&vi.發(fā)出信號(hào)，打旗語(yǔ);信號(hào)量大于１時(shí)有2個(gè)某類資源，四個(gè)進(jìn)程A、B、C、D要用該類資源，最開(kāi)始Sem=2，當(dāng)A進(jìn)入，Sem=1，當(dāng)B進(jìn)入Sem=0,表明該類資源剛好用完。

當(dāng)C進(jìn)入時(shí)Sem=-1,表明有一個(gè)進(jìn)程被阻塞了，D進(jìn)入，Sem=-2。當(dāng)A用完該類資源時(shí)，進(jìn)行V操作，Sem=-1，釋放該類資源，而這時(shí)Sem<0,表明有進(jìn)程阻塞在該類資源上，于是喚醒一個(gè)。疑問(wèn)4：如果是互斥信號(hào)量的話，應(yīng)該設(shè)置信號(hào)量Sen=1，但是當(dāng)有5個(gè)進(jìn)程都訪問(wèn)的話，最后在該信號(hào)量的鏈表里會(huì)有4個(gè)在等待，也是說(shuō)S=-4，那么第一個(gè)進(jìn)程執(zhí)行了V操作使S加1，釋放了資源，下一個(gè)應(yīng)該能夠執(zhí)行，但喚醒的這個(gè)進(jìn)程在執(zhí)行P操作時(shí)因S〈0,也還是執(zhí)行不了,這是怎么回事呢？答：當(dāng)一個(gè)進(jìn)程阻塞了的時(shí)候，它已經(jīng)執(zhí)行過(guò)了P操作，并卡在臨界區(qū)那個(gè)地方。當(dāng)喚醒它時(shí)就立即進(jìn)入它自己的臨界區(qū)，并不需要執(zhí)行P操作了，當(dāng)執(zhí)行完了臨界區(qū)的程序后，就執(zhí)行V操作。疑問(wèn)5：

Sem的絕對(duì)值表示等待的進(jìn)程數(shù)，同時(shí)又表示臨界資源，這到底是怎么回事？？答：當(dāng)信號(hào)量Sem小于0時(shí),其絕對(duì)值表示系統(tǒng)中因請(qǐng)求該類資源而被阻塞的進(jìn)程數(shù)目.S大于0時(shí)表示可用的臨界資源數(shù)。注意在不同情況下所表達(dá)的含義不一樣。當(dāng)?shù)扔?時(shí)，表示剛好用完。桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果，也可向盤中放香蕉，兒子專等吃盤中的香蕉，女兒專等吃盤中的蘋果。規(guī)定當(dāng)盤空時(shí)一次只能放一只水果供吃者使用，請(qǐng)用P，V原語(yǔ)實(shí)現(xiàn)爸爸、兒子、女兒三個(gè)并發(fā)進(jìn)程的同步。桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果和香蕉，兒子專等吃盤中的香蕉，女兒專等吃盤中的蘋果。Vardish,apple,banana:Semaphore:=1,0,0;Main(){cobeginFather();son();daugher();Coend}Father(){while(true){p(dish);if放的是蘋果v(apple);elseV(banana)}}son(){while(true){p(banana);從盤子取香蕉；v(dish);

吃香蕉；}}daugher(){while(true){p(apple);從盤子取蘋果；v(dish);

吃蘋果；}}//dish—互斥使用盤子；apple—盤中蘋果數(shù)；banana—盤中香蕉數(shù)例題（1）V（S1）V（S2）P（S1）V（S3）V（S4）（2）P（S2）V（S5）（3）P（S3）P（S4）P（S5）1.整型信號(hào)量

Dijkstra把整型信號(hào)量s定義成一個(gè)用于表示資源數(shù)目的整型變量。進(jìn)程通過(guò)信號(hào)量傳送信號(hào)，利用兩個(gè)特殊的操作發(fā)送和接收信號(hào)。

signal(s)：通過(guò)信號(hào)量s傳送信號(hào)

wait(s)：通過(guò)信號(hào)量接收信號(hào)

如果相應(yīng)的信號(hào)仍然沒(méi)有發(fā)送，則進(jìn)程被掛起，直到發(fā)送完為止。3.4.3信號(hào)量機(jī)制122wait()操作定義如下voidwait(s){while(s<=0);//donothings--;}signal()操作定義如下voidsignal(s){s++;}3.4.3信號(hào)量機(jī)制1232.記錄型信號(hào)量整型信號(hào)量機(jī)制沒(méi)有滿足讓權(quán)等待的原則，可能使進(jìn)程處于饑餓的忙等狀態(tài)。假設(shè)s為一個(gè)記錄型數(shù)據(jù)結(jié)構(gòu)，其中一個(gè)分量為整形量value，另一個(gè)為信號(hào)量隊(duì)列queue。value通常是一個(gè)具有非負(fù)初值的整型變量，queue是一個(gè)初始狀態(tài)為空的進(jìn)程隊(duì)列，當(dāng)一個(gè)進(jìn)程必須等待信號(hào)量時(shí)，就加入到進(jìn)程隊(duì)列中去。3.4.3信號(hào)量機(jī)制124wait和signal操作定義如下：wait(s)：信號(hào)量s減l，若結(jié)果小于0，則調(diào)用wait(s)的進(jìn)程被設(shè)置成等待信號(hào)量s的狀態(tài)。signal(s)：將信號(hào)量s加1，若結(jié)果不大于0，則釋放一個(gè)等待信號(hào)量s的進(jìn)程。3.4.3信號(hào)量機(jī)制126分析得出以下結(jié)論：

（1）若信號(hào)量s.value值為正，則該值表示在對(duì)進(jìn)程進(jìn)行阻塞之前對(duì)信號(hào)量s可以實(shí)施的wait()操作個(gè)數(shù)，即系統(tǒng)中某類資源實(shí)際可用數(shù)目；（2）若信號(hào)量s.value值為負(fù)，則其絕對(duì)值表示阻塞隊(duì)列s.queue中等待的進(jìn)程個(gè)數(shù)；（3）每次wait()操作，意味著進(jìn)程請(qǐng)求一個(gè)單位的該類資源，使系統(tǒng)中可供分配的該類資源數(shù)減少一個(gè)，每次signal()操作，表示執(zhí)行進(jìn)程釋放一個(gè)單位資源，使系統(tǒng)中可供分配的該類資源數(shù)增加一個(gè)。3.4.3信號(hào)量機(jī)制1273.二元信號(hào)量假設(shè)s為一個(gè)記錄型數(shù)據(jù)結(jié)構(gòu)，其中一個(gè)分量為value，它僅能取值0和1，另一個(gè)分量為信號(hào)量隊(duì)列queue。一個(gè)二元信號(hào)量的值只能是0或者13.4.3信號(hào)量機(jī)制128P-V同步缺點(diǎn)：對(duì)于共享變量及信號(hào)量變量的操作將被分散于各個(gè)進(jìn)程中，有幾個(gè)缺點(diǎn)：（１）易讀性差，因?yàn)橐私鈱?duì)于一組共享變量及信號(hào)量的操作是否正確，則必須通讀整個(gè)系統(tǒng)或者并發(fā)程序（２）不利于修改和維護(hù)，因?yàn)槌绦虻木植啃院懿?，所以任一組變量或一段代碼的修改都可能影響全局（３）正確性難以保證，因?yàn)椴僮飨到y(tǒng)或并發(fā)程序通常很大，要保證這樣一個(gè)復(fù)雜的系統(tǒng)沒(méi)有邏輯錯(cuò)誤是很難的管程的引入

信號(hào)量機(jī)制的引入解決了進(jìn)程同步的描述問(wèn)題，但信號(hào)量的大量同步操作分散在各個(gè)進(jìn)程中不便于管理，還有可能導(dǎo)致系統(tǒng)死鎖。如：生產(chǎn)者消費(fèi)者問(wèn)題中將P、V顛倒可能死鎖。

Dijkstra于1971年提出：把所有進(jìn)程對(duì)某一種臨界資源的同步操作都集中起來(lái)，構(gòu)成一個(gè)所謂的秘書進(jìn)程。凡要訪問(wèn)該臨界資源的進(jìn)程，都需先報(bào)告秘書，由秘書來(lái)實(shí)現(xiàn)諸進(jìn)程對(duì)同一臨界資源的互斥使用。1.管程的定義

管程是由一個(gè)或多個(gè)過(guò)程、一個(gè)初始化序列和數(shù)據(jù)組成的軟件模塊，是一種程序設(shè)計(jì)語(yǔ)言結(jié)構(gòu)成分，具有和信號(hào)量同等的表達(dá)能力。進(jìn)程可以通過(guò)調(diào)用管程實(shí)現(xiàn)對(duì)資源的請(qǐng)求和釋放。

百度百科：管程(英語(yǔ)：Monitors，也稱為監(jiān)視器)定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行的一組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)。3.4.4管程132管程的基本思想

將共享變量和對(duì)它們的操作集中在一個(gè)模塊中，操作系統(tǒng)或并發(fā)程序就由這樣的模塊構(gòu)成。這樣模塊之間聯(lián)系清晰，便于維護(hù)和修改，易于保證正確性。管程的主要特點(diǎn)：共享性：一個(gè)進(jìn)程通過(guò)調(diào)用管程的一個(gè)過(guò)程進(jìn)入管程，管程中的移出過(guò)程可被所有要調(diào)用管程的過(guò)程的進(jìn)程所共享。安全性：管程的局部數(shù)據(jù)變量只能被管程的過(guò)程訪問(wèn)，任何其它外部過(guò)程都不能訪問(wèn)，一個(gè)管程的過(guò)程也不能訪問(wèn)任何非局部于它的變量?；コ庑裕涸谌我粫r(shí)刻，只能有一個(gè)進(jìn)程能夠進(jìn)入管程執(zhí)行，調(diào)用管程的其它任何進(jìn)程都將被阻塞，只能等待直到當(dāng)前訪問(wèn)進(jìn)程退出管程。3.4.4管程1342.管程的條件變量在管程的調(diào)用過(guò)程中，存在如下的現(xiàn)象：一個(gè)進(jìn)程調(diào)用了管程，并且它在管程中處于阻塞或掛起狀態(tài)，當(dāng)進(jìn)程解除阻塞或掛起的條件滿足后才能恢復(fù)執(zhí)行。引入條件變量（Conditionvariables）的同步機(jī)制，以及對(duì)應(yīng)的兩個(gè)原語(yǔ)操作cwait和csignal。3.4.4管程135cwait和csignal操作意義：

（1）cwait(c)操作：正在調(diào)用管程過(guò)程的進(jìn)程因條件c沒(méi)有滿足而被阻塞或者掛起，則調(diào)用cwait操作將自己插入到條件變量c的等待進(jìn)程隊(duì)列中。與此同時(shí)，被阻塞進(jìn)程釋放管程，直到條件c發(fā)生改變，其它進(jìn)程可以調(diào)用管程。（2）csignal(c)操作：正在調(diào)用管程的進(jìn)程檢測(cè)到條件c發(fā)生了改變，則調(diào)用csignal操作重新喚醒一個(gè)因條件c而被阻塞或者掛起的進(jìn)程。如果等待進(jìn)程隊(duì)列中有多個(gè)進(jìn)程，則選擇其中一個(gè)喚醒，否則繼續(xù)執(zhí)行原進(jìn)程。3.4.4管程1361.生產(chǎn)者-消費(fèi)者問(wèn)題（1）問(wèn)題描述

假設(shè)有n個(gè)生產(chǎn)者和m個(gè)消費(fèi)者，連接在一個(gè)有k個(gè)公用緩沖區(qū)的有界緩沖上，pi表示生產(chǎn)者進(jìn)程，cj表示消費(fèi)者進(jìn)程。

滿足：只要緩沖區(qū)未滿，生產(chǎn)者pi即可將生產(chǎn)的產(chǎn)品放入空閑緩沖區(qū)中只要緩沖區(qū)不為空，消費(fèi)者進(jìn)程cj就可從緩沖區(qū)從取走并消耗產(chǎn)品在任何時(shí)刻，要么是一個(gè)生產(chǎn)者訪問(wèn)緩沖區(qū)，要么是一個(gè)消費(fèi)者在訪問(wèn)緩沖區(qū)3.4.5經(jīng)典同步問(wèn)題138有1個(gè)生產(chǎn)者和1個(gè)消費(fèi)者，一個(gè)有1個(gè)公用緩沖區(qū)生產(chǎn)者進(jìn)程

while(TRUE){

生產(chǎn)一個(gè)產(chǎn)品;

P(empty);

產(chǎn)品送往Buffer;

V(full);

}

消費(fèi)者進(jìn)程

while(True){

P(full);

從Buffer取出一個(gè)產(chǎn)品;

V(empty);

消費(fèi)該產(chǎn)品;

}定義兩個(gè)同步信號(hào)量：

empty——表示緩沖區(qū)是否為空，初值為1。

full——表示緩沖區(qū)中是否為滿，初值為0。

有1個(gè)生產(chǎn)者和1個(gè)消費(fèi)者，一個(gè)有n個(gè)公用緩沖區(qū)生產(chǎn)者進(jìn)程while(TRUE){生產(chǎn)一個(gè)產(chǎn)品;P(empty);產(chǎn)品送往buffer（in）；in=(in+1)modn；V(full);}消費(fèi)者進(jìn)程while(TRUE){P(full);從buffer（out）中取出產(chǎn)品；out=(out+1)modn；V(empty);消費(fèi)該產(chǎn)品;}定義兩個(gè)同步信號(hào)量：empty——表示緩沖區(qū)是否為空，初值為n。full——表示緩沖區(qū)中是否為滿，初值為0。設(shè)緩沖區(qū)的編號(hào)為1～n-1，定義兩個(gè)指針in和out，分別是生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程使用的指針，指向下一個(gè)可用的緩沖區(qū)。有多個(gè)生產(chǎn)者（互斥）和多個(gè)消費(fèi)者（互斥），一個(gè)有n個(gè)公用緩沖區(qū)在這個(gè)問(wèn)題中，不僅生產(chǎn)者與消費(fèi)者之間要同步，而且各個(gè)生產(chǎn)者之間、各個(gè)消費(fèi)者之間還必須互斥地訪問(wèn)緩沖區(qū)。定義四個(gè)信號(hào)量：empty——表示緩沖區(qū)是否為空，初值為n。full——表示緩沖區(qū)中是否為滿，初值為0。mutex1——生產(chǎn)者之間的互斥信號(hào)量，初值為1。mutex2——消費(fèi)者之間的互斥信號(hào)量，初值為1。設(shè)緩沖區(qū)的編號(hào)為1～n-1，定義兩個(gè)指針in和out，分別是生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程使用的指針，指向下一個(gè)可用的緩沖區(qū)。有多個(gè)生產(chǎn)者（互斥）和多個(gè)消費(fèi)者（互斥），一個(gè)有n個(gè)公用緩沖區(qū)生產(chǎn)者進(jìn)程

while(TRUE){

生產(chǎn)一個(gè)產(chǎn)品;

P(empty);

P(mutex1)；

產(chǎn)品送往buffer（in）；

in=(in+1)modn；

V(mutex1);

V(full);

}消費(fèi)者進(jìn)程