操作系統(tǒng)第3章

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

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

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

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

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

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

11圖3.3四條語句的前趨圖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í)行時，由于它們共享系統(tǒng)資源，以及為了完成同一任務而相互合作，致使這些并發(fā)程序之間形成了相互制約的關系。（2）失去封閉性：程序在并發(fā)執(zhí)行時，多個程序共享系統(tǒng)中的各種資源，因此，系統(tǒng)資源的狀態(tài)將由多個程序來改變，致使程序失去了封閉性。

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

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

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

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

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

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

（2）用戶登錄

（3）提供服務

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

顯然，同步是一種更為復雜的互斥，而互斥是一種特殊的同步?；コ馀c同步互斥是兩個線程之間不可以同時運行，他們會相互排斥，必須等待一個線程運行完畢，另一個才能運行，而同步也是不能同時運行，但他是必須要安照某種次序來運行相應的線程。

互斥：是指某一資源同時只允許一個訪問者對其進行訪問，具有唯一性和排它性。但互斥無法限制訪問者對資源的訪問順序，即訪問是無序的。

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

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

上帝:

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

我希望中國國家隊能再次打進世界杯.

上帝:

這個啊!這個不好辦啊,你還說下一個吧!程序員:

那好!我的下一個愿望是每天都能休息6個小時以上.

上帝:

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

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

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

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

2.不能用于多處理器：關中斷不能保證互斥。

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

）

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

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

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

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

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

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

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

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

（3）信號量S用于互斥，互斥信號量的初值一般為1。簡單理解P，V操作

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

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

vt.&vi.發(fā)出信號，打旗語;信號量大于１時有2個某類資源，四個進程A、B、C、D要用該類資源，最開始Sem=2，當A進入，Sem=1，當B進入Sem=0,表明該類資源剛好用完。

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

Sem的絕對值表示等待的進程數(shù)，同時又表示臨界資源，這到底是怎么回事？？答：當信號量Sem小于0時,其絕對值表示系統(tǒng)中因請求該類資源而被阻塞的進程數(shù)目.S大于0時表示可用的臨界資源數(shù)。注意在不同情況下所表達的含義不一樣。當?shù)扔?時，表示剛好用完。桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果，也可向盤中放香蕉，兒子專等吃盤中的香蕉，女兒專等吃盤中的蘋果。規(guī)定當盤空時一次只能放一只水果供吃者使用，請用P，V原語實現(xiàn)爸爸、兒子、女兒三個并發(fā)進程的同步。桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果和香蕉，兒子專等吃盤中的香蕉，女兒專等吃盤中的蘋果。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.整型信號量

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

signal(s)：通過信號量s傳送信號

wait(s)：通過信號量接收信號

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

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

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

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

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

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

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

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

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

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

while(TRUE){

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

P(empty);

產(chǎn)品送往Buffer;

V(full);

}

消費者進程

while(True){

P(full);

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

V(empty);

消費該產(chǎn)品;

}定義兩個同步信號量：

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

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

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

while(TRUE){

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

P(empty);

P(mutex1)；

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

in=(in+1)modn；

V(mutex1);

V(full);

}消費者進程