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

63.1.1程序的順序執行及其特征1.程序的順序執行

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

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

10圖3.2多道程序并發執行3.1.2程序的并發執行及其特征前趨圖的引入：前趨圖是一個有向無環（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程序的并發執行及其特征2.程序并發執行的特征（1）間斷（異步）性：程序在并發執行時，由于它們共享系統資源，以及為了完成同一任務而相互合作，致使這些并發程序之間形成了相互制約的關系。（2）失去封閉性：程序在并發執行時，多個程序共享系統中的各種資源，因此，系統資源的狀態將由多個程序來改變，致使程序失去了封閉性。

（3）不可再現性：程序在并發執行時，由于失去了封閉性，也將導致其失去執行的可再現性。

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

狀態變遷圖3.1.4進程狀態21（b）

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

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

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

（2）用戶登錄

（3）提供服務

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

上帝:

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

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

上帝:

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

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

上帝:

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

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

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

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

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

）

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

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

booleantemp=*lock;

*lock=TRUE;

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

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

//donothing不做任何事

//criticalsection臨界區

lock=FALSE;表示空閑

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

booleantemp=*lock;

*lock=TRUE;

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

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

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

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

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

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

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

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

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

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

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

vt.&vi.發出信號，打旗語;信號量大于１時有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，那么第一個進程執行了V操作使S加1，釋放了資源，下一個應該能夠執行，但喚醒的這個進程在執行P操作時因S〈0,也還是執行不了,這是怎么回事呢？答：當一個進程阻塞了的時候，它已經執行過了P操作，并卡在臨界區那個地方。當喚醒它時就立即進入它自己的臨界區，并不需要執行P操作了，當執行完了臨界區的程序后，就執行V操作。疑問5：

Sem的絕對值表示等待的進程數，同時又表示臨界資源，這到底是怎么回事？？答：當信號量Sem小于0時,其絕對值表示系統中因請求該類資源而被阻塞的進程數目.S大于0時表示可用的臨界資源數。注意在不同情況下所表達的含義不一樣。當等于0時，表示剛好用完。桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果，也可向盤中放香蕉，兒子專等吃盤中的香蕉，女兒專等吃盤中的蘋果。規定當盤空時一次只能放一只水果供吃者使用，請用P，V原語實現爸爸、兒子、女兒三個并發進程的同步。桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果和香蕉，兒子專等吃盤中的香蕉，女兒專等吃盤中的蘋果。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—盤中蘋果數；banana—盤中香蕉數例題（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定義成一個用于表示資源數目的整型變量。進程通過信號量傳送信號，利用兩個特殊的操作發送和接收信號。

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

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

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

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

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

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

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

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

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

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

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

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

while(TRUE){

生產一個產品;

P(empty);

產品送往Buffer;

V(full);

}

消費者進程

while(True){

P(full);

從Buffer取出一個產品;

V(empty);

消費該產品;

}定義兩個同步信號量：

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

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

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

while(TRUE){

生產一個產品;

P(empty);

P(mutex1)；

產品送往buffer（in）；

in=(in+1)modn；

V(mutex1);

V(full);

}消費者進程