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

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

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

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

為了提高計算機的利用率、處理速度和系統(tǒng)的吞吐量，并行處理技術(shù)和并發(fā)程序設(shè)計技術(shù)在計算機中已經(jīng)得到了廣泛應(yī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)資源，以及為了完成同一任務(wù)而相互合作，致使這些并發(fā)程序之間形成了相互制約的關(guān)系。（2）失去封閉性：程序在并發(fā)執(zhí)行時，多個程序共享系統(tǒng)中的各種資源，因此，系統(tǒng)資源的狀態(tài)將由多個程序來改變，致使程序失去了封閉性。

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

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

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

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

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

一種可行的解決問題的辦法是引入掛起（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)用來記錄進(jìn)程狀態(tài)和相關(guān)信息，控制進(jìn)程運行的數(shù)據(jù)結(jié)構(gòu)，是進(jìn)程的唯一標(biāo)識符在PCB中，主要包含如下的信息:3.1.5進(jìn)程控制塊30進(jìn)程標(biāo)識符進(jìn)程狀態(tài)調(diào)度信息程序計數(shù)器上下文數(shù)據(jù)內(nèi)存指針I(yè)/O狀態(tài)信息進(jìn)程控制是進(jìn)程管理中最基本的功能在操作系統(tǒng)中，不同功能都是通過執(zhí)行各種原語（Primitive）操作實現(xiàn)原語是由若干條指令構(gòu)成、可完成特定功能的程序段。原語是原子操作，是一個不可分割的基本單元，在執(zhí)行過程中不會被中斷。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)建一個新進(jìn)程的具體步驟：（1）系統(tǒng)為新建進(jìn)程申請一個空白的進(jìn)程控制塊，獲得一個唯一的進(jìn)程標(biāo)識符。（2）系統(tǒng)為新建進(jìn)程分配運行所需的資源，包括：內(nèi)存、處理器時間、I/O設(shè)備等。（3）進(jìn)程控制塊（PCB）初始化。（4）設(shè)置鏈接，如果就緒隊列允許新進(jìn)程插入，則將新進(jìn)程插入就緒隊列。3.2.1進(jìn)程創(chuàng)建33引起進(jìn)程終止的事件：（1）正常完成（2）運行超時（3）等待超時（4）內(nèi)存不足（5）越界錯誤（6）保護(hù)錯誤（7）算術(shù)錯誤3.2.2進(jìn)程終止34（8）

I/O錯誤（9）無效指令（10）特權(quán)指令（11）操作員或操作系統(tǒng)干涉（12）父進(jìn)程請求（13）父進(jìn)程終止終止原語的具體步驟：（1）根據(jù)需要終止進(jìn)程的進(jìn)程標(biāo)識符，從PCB集合中查找對應(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í)行過程中因等待某個事件的發(fā)生或等待某個操作的完成而不得不讓出處理器。引起進(jìn)程阻塞的主要事件有：

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

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

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

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

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

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

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

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

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

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

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

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

饑餓是指一個可運行的進(jìn)程雖然能繼續(xù)執(zhí)行，但被調(diào)度程序無限期地忽視而不能執(zhí)行的情況。舉個例子，當(dāng)有多個進(jìn)程需要打印文件時，如果系統(tǒng)分配打印機的策略是最短文件優(yōu)先，那么長文件的打印任務(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)程同步）：即為完成同一個任務(wù)的諸進(jìn)程間，因需要協(xié)調(diào)它們的工作而相互等待、相互交換信息所產(chǎn)生的直接制約關(guān)系。

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

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

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

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

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

上帝:

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

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

上帝:

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

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

上帝:

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

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

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

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

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

）

自旋鎖是專為防止多處理器并發(fā)而引入的一種鎖，它在內(nèi)核中大量應(yīng)用于中斷處理等部分，是為了解決對某項資源的互斥使用。在任何時刻最多只能有一個執(zhí)行單元獲得鎖。對于互斥鎖，如果資源已經(jīng)被占用，資源申請者只能進(jìn)入睡眠狀態(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;}自旋鎖存在的問題死鎖。試圖遞歸地獲得自旋鎖必然會引起死鎖。在遞歸程序中使用自旋鎖應(yīng)遵守下列策略：遞歸程序決不能在持有自旋鎖時調(diào)用它自己，也決不能在遞歸調(diào)用時試圖獲得相同的自旋鎖。此外如果一個進(jìn)程已經(jīng)將資源鎖定，那么，即使其它申請這個資源的進(jìn)程不停地瘋狂“自旋”,也無法獲得資源，從而進(jìn)入死循環(huán)。過多占用cpu資源。如果不加限制，由于申請者一直在循環(huán)等待，因此自旋鎖在鎖定的時候,如果不成功,不會睡眠,會持續(xù)的嘗試,單cpu的時候自旋鎖會讓其它進(jìn)程動不了.因此，一般自旋鎖實現(xiàn)會有一個參數(shù)限定最多持續(xù)嘗試次數(shù).超出后,自旋鎖放棄當(dāng)前時間片.等下一次機會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ù)目的進(jìn)程，不管是單處理機還是多處理機；簡單、容易驗證其正確性?？梢灾С诌M(jìn)程內(nèi)有多個臨界區(qū)，只需為每個臨界區(qū)設(shè)立一個布爾變量。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

while(TRUE){

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

P(empty);

產(chǎn)品送往Buffer;

V(full);

}

消費者進(jìn)程

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

while(TRUE){

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

P(empty);

P(mutex1)；

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

in=(in+1)modn；

V(mutex1);

V(full);

}消費者進(jìn)程