第二章進程管理

教學內容

2.1進程的引入2.2進程的描述

2.3進程控制

2.4進程的同步與互斥

2.5信號量機制

2.6進程同步問題舉例

2.7管程

2.8進程的高級通信

2.9信號通信機制

2.10線程

22.1進程的引入

2.1.1程序的順序執行1．程序的順序執行

程序是人們要計算機完成特定功能的一些指令序列，是一個按嚴格次序、順序執行的操作序列，是一個靜態的概念。我們把一個具有獨立功能的程序獨占處理機，直到最后結束的過程稱為程序的順序執行。如：有一個程序，要求先輸入數據，再做相應的計算，最后輸出結果并用打印機打印。分別用I、C、P代表以上3個程序段，這樣，上述3個程序段的執行順序為：

I→C→P。

32.1進程的引入

2．程序順序執行時的特征（1）順序性。處理機的操作嚴格按照程序所規定的順序執行，即只有前一個程序段完成才執行下一個程序段，上一條指令完成再去執行下一條指令。（2）封閉性。程序是在封閉環境下運行的。程序運行時獨占全機資源，資源的狀態除初始狀態外，只有該程序本身才能改變它。程序執行的最終結果由給定的初始條件決定，不受外界因素的影響。（3）可再現性。順序執行的最終結果可再現。也就是說它與執行速度及執行的時刻無關，只要輸入的初始條件相同，無論何時重復執行該程序，結果都是相同的。42.1.2程序的并發執行及其特征1．并發執行的概念

所謂程序的并發性，是指多道程序在同一時間間隔內同時發生。程序的并發執行可總結為：一組在邏輯上互相獨立的程序或程序段在執行過程中，其執行時間在客觀上互相重疊，即一個程序段的執行尚未結束，另一個程序段的執行已經開始的一種執行方式。5C12．程序并發執行時的特征（1）間斷性程序在并發執行時，由于它們共享系統資源，以及為完成同一項任務而相互合作，致使這些并發執行的程序之間，形成了相互制約的關系。相互制約將導致并發程序具有“執行——暫停——執行”這種間斷性的活動規律。6I1I2I3C1C2C3P1P2P3I4C4圖2-2程序的并發執行I1I2I3C2C3P1P2P3I4C4（2）失去封閉性程序在并發執行時，是多個程序共享系統中的各種資源，因而這些資源的狀態將由多個運行的程序來改變，致使程序的運行失去了封閉性。例如，當處理機被某個程序占有時，另一程序必須等待。（3）不可再現性

在并發環境下，同一個程序執行多次，執行的結果可能不同。例如，有兩個循環程序A和B，它們共享一個變量N，初值為0。程序A（）：程序B（）：{do{doN=N+1;print(N);While(1)While(1)}}

程序A和程序B以不同的速度運行，出現的結果可能不同。例如，當程序A和程序B運行的速度相近時，打印的結果為1、2、3、…；而當程序A的執行速度是程序B的2倍時，打印的結果可能是2、4、6…。7引入進程的意義

從上例來看，程序在并發執行時，由于失去了封閉性，其計算結果與并發程序的執行速度有關，從而使程序失去了可再現性，程序經過多次執行后，雖然執行時的環境和初始條件相同，但得到的結果卻各不相同。所以，從上面的討論看，由于程序的順序性、間斷性和不可再現性，用程序作為描述其執行過程以及共享資源的基本單位是不合適的。這就需要一個既能描述程序的執行過程，又能用來共享資源的基本單位，這個基本單位被稱為進程。82.1.3進程的定義與特征1．進程的定義進程是操作系統中最基本、最重要的概念之一。人們對進程下過許多定義。現列舉其中的幾種：（1）進程是程序的一次執行。（2）進程是可以和別的進程并發執行的計算。（3）進程就是一個程序在給定活動空間和初始條件下，在一個處理機上的執行過程。（4）進程是程序在一個數據集合上的運行過程，它是系統進行資源分配和調度的一個獨立單位。（5）進程是動態的，有生命周期的活動。內核可以創建一個進程，最終將由內核終止該進程使其消亡。綜上觀點定義為：“并發執行的程序在一個數據集合上的執行過程”【運行著的程序】9進程和程序之間的關系

進程和程序是兩個完全不同的概念，但又有密切的聯系。程序是規定的工作流程，進程則是實際的工作過程。它們之間的主要區別是：（1）程序是靜態的概念，而進程則是程序的一次執行過程。它是動態的概念。（2）進程是一個能獨立運行的單位，能與其它進程并發執行；而程序是不能作為一個獨立運行的單位而并發執行的。（3）程序和進程無一一對應的關系。（4）各個進程在并發執行過程中會產生相互制約關系，而程序本身是靜態的，不存在這種異步特征。102．進程的特征從進程與程序的區別可以看出，進程具有如下特征：（1）動態性動態性是進程最基本的特性。進程由創建而產生，由調度而執行，因得不到資源而暫停執行，以及因撤消而消亡。（2）并發性這是指多個進程實體，同存于內存中，能在一段時間段內同時執行。并發性是進程的重要特征，同時也是操作系統的重要特征。提高并發性，可以提高系統的效率。（3）獨立性進程是一個能獨立運行的基本單位，同時也是系統中獨立獲得資源和獨立調度的基本單位。（4）異步性這是指進程按各自獨立的、不可預知的速度向前推進；或者說，進程按異步方式運行。（5）結構特征從結構上看，進程實體是由程序段、數據段及進程控制塊三部分組成，也稱這三部分為進程映像。11條件外部條件CPU運行滿足滿足不運行阻塞

就緒

滿足2.1.4進程的基本狀態及轉換2.1.4進程的基本狀態及轉換

進程的動態性由它的狀態及狀態轉換來體現的。1．進程的三個基本狀態

進程通常至少有三種基本狀態：（1）就緒狀態（ready）進程運行所需的外部條件滿足，但因為其它進程已占用CPU，所以暫時不能運行。（2）執行狀態(running)

外部條件滿足，進程已獲得CPU，其程序正在執行。在單處理機系統中，只有一個進程處于執行狀態。（3）阻塞狀態(blocked)

進程因資源無法滿足而等待資源，暫時不能運行的狀態，稱為阻塞狀態，也稱為等待狀態。系統中處于阻塞狀態的進程可能有多個，通常將它們排成一個隊列，也有的系統則根據阻塞原因的不同將這些進程排成多個隊列。132．進程狀態的轉換就緒==》執行

對于處于就緒狀態的進程，在調度程序為之分配了處理機之后，該進程便可執行。相應地，它由就緒狀態轉變為執行狀態。執行==》就緒

正在執行的進程（執行狀態）也稱為當前進程，如果因分配給它的時間片已用完而被暫停執行時，該進程便由執行狀態又回到就緒狀態；執行==》阻塞

一個處在執行狀態的進程，如果因等待資源而使進程的執行受阻，使之無法繼續執行，該進程將由執行狀態轉變為阻塞狀態。阻塞==》就緒

一個處于阻塞狀態的進程，當它所需的外部事件滿足，它應由阻塞狀態變為就緒狀態。14進程創建資源滿足如I/O請求滿足就緒狀態阻塞狀態執行狀態結束進程等待資源如I/O請求執行完或撤銷

進程基本狀態轉換圖PCB3．引入掛起狀態時的進程狀態掛起激活

除了上述3種基本狀態以外，很多系統中又引入了掛起狀態。

所謂掛起狀態，實際上就是一種靜止的狀態。一個進程被掛起后，不管它是否在就緒狀態，系統都不分配給它處理機。

處于掛起狀態的進程要想重新進入到活動狀態，必須被激活（即轉換為活動狀態），然后才有可能執行。因此在引入掛起狀態后，進程之間的狀態轉換除了四種基本狀態轉換以外，又增加了以下幾種：（1）活動就緒—掛起—靜止就緒。（2）活動阻塞—掛起—靜止阻塞。（3）靜止就緒—激活—活動就緒。（4）靜止阻塞—激活—活動阻塞。16執行外部事件滿足外掛起激活掛起掛激活活動就緒靜止就緒活動阻塞靜止阻塞調度圖2-2具有掛起狀態的進程狀態轉換等部事件外待起部條件滿足完成或撤消172.1.5Linux進程的狀態

Linux系統的一個任務總體上有以下幾種狀態：（1）TASK-RUNNING狀態

:執行和就緒兩種狀態（2）TASK-INTERRUPTIBLE狀態:可中斷的等待狀態。

（3）TASK-UNINTERRUPTIBLE狀態:不可中斷等待狀態。

（4）TASK-ZOMBIE狀態，僵死狀態。由于某些原因進程被終止，這個進程所占有的資源全部釋放之后，還保存著PCB信息，這種占有PCB但已被撤消的進程就處于僵死狀態。（5）TASK-STOPPED狀態，暫停狀態。

18P12.2進程的描述

進程的活動是通過在CPU上執行一系列程序和對相應數據進行操作來體現的。程序和操作的數據是進程存在的實體。程序和數據是靜態的，無法反映出其動態性，還需要一個數據結構來描述進程的動態性（當前的狀態、本身的特性等）。這種數據結構稱為進程控制塊PCB

（ProcessControlBlock）。所以，進程實體通常是由程序、數據集合和進程控制塊PCB這三部分構成，也稱為“進程映象”。進程控制塊PCB程序部分數據集合20圖2-4進程的一般組成模型2.2.1進程控制塊PCB

PCB集中反映一個進程的動態特征，當系統創建了一個新進程時，就為它建立一個PCB；當進程終止后，系統回收其PCB，該進程在系統中就不存在了。所以，PCB是進程存在的惟一標志。可以按照功能將PCB分成四個組成部分：

進程標識符

處理機狀態

進程調度信息

進程控制信息。211．進程標識符進程標識符用于惟一地標識一個進程。一個進程通常有兩種標識符：進程內部標識符。進程外部標識符。（1）進程內部標識符。在所有的操作系統中，為每一個進程賦予一個惟一的數字標識符，它通常是一個進程的序號。設置內部標識符主要是為了方便系統使用。（2）進程外部標識符。它由創建者提供，通常是由字母、數字組成，往往由用戶（進程）在訪問該進程時使用。為了描述進程的家族關系，還應設置父進程標識及子進程標識。222．處理機狀態：

處理機狀態信息主要由處理機的各種寄存器中的內容組成。處理機在運行時，許多信息都放在寄存器中。當處理機被中斷時，這些信息都必須保存在PCB中，以便在該進程重新執行時能從斷點繼續執行。處理機的寄存器包括通用寄存器、指令計數器、程序狀態字PSW、用戶棧指針。233．進程調度信息

PCB中還存放一些與進程調度和進程對換有關的信息。（1）進程狀態。

指明進程當前的狀態，作為進程調度和對換的依據。（2）進程優先級。

進程使用處理機的優先級別的整數，優先級高的進程應優先獲得CPU。（3）進程調度所需要的其它信息。

與所采用的進程調度算法有關，如進程已等待CPU的時間、進程已運行的時間等。

（4）事件或阻塞原因。指進程由執行狀態轉變為阻塞狀態所需要等待發生的事件。

244．進程控制信息

進程控制信息包括：（1）程序和數據的地址:

進程的程序和數據所在的內存或外存地址，以便再調度到該進程執行時，能從PCB中找到其程序和數據。（2）進程同步和通信機制:

實現進程同步和進程通信時必需的機制，如消息隊列指針、信號量等，它們可能全部或部分地放在PCB中。

（3）資源清單:

是一張列出了除CPU以外、進程所需的全部資源及已經分配到該進程的資源清單。（4）鏈接指針:

本進程PCB所在隊列的下一個進程PCB的首地址。

252.2.2進程控制塊的組織方式各進程的PCB有如下幾種組織方式：

線性方式鏈接方式索引方式。1．線性方式將各進程的PCB依次放入一個表中，結構如下圖所示。PCB1PCB2PCB3……PCBn-1PCBn26優點：線性方式最簡單、最容易實現。缺點：限定了系統中同時存在的進程的最大數目；

為選擇合理的進程投入運行，經常要對整個表進行掃描，降低了調度效率。

2．鏈接方式

鏈接方式是經常采用的方式。其原理是：按照進程的不同狀態分別將其放在不同的隊列。Linux操作系統就是應用這種進程控制塊組織方式。就緒隊列指針PCBPCBPCB0運行隊列指針PCB0阻塞隊列1指針PCBPCBPCB0PCB阻塞隊列2指針PCBPCB0273．索引方式系統根據所有進程的狀態建立幾張索引表。如就緒索引表、阻塞索引表等。并把各索引表在內存的首地址記錄在內存的一些專用單元中。在每個索引表的表目中，記錄具有相應狀態的某個PCB在PCB表中的地址。阻塞索引表就緒索引表執行指針就緒表指針阻塞表指針PCB1PCB2PCB3PCB4PCB5PCB6PCB7圖2-7PCB索引結構示意圖282.2.3Linux進程的PCB

Linux系統中的進程稱為任務。該系統的進程控制塊PCB用一個稱為task-struct的結構體來描述，Linux系統PCB包含以下信息：1．進程描述信息（1）進程標識號（pid，processidentifier）（2）用戶和組標識（userandgroupidentifier）（3）連接信息（Links）2．進程控制信息（1）進程當前狀態（2）調度信息（3）記時信息（4）通信信息293．進程資源信息

記錄了與該進程有關的存儲器的各種地址和資料、文件系統以及打開文件的信息等等。4．CPU現場信息

每個進程運行時都要使用處理器的寄存器以及堆棧等資源。當一個進程被掛起時，所有有關處理處理器的內容都要保存到task_struct結構中。當進程恢復運行時，所有保存的內容再裝入到處理器中。302.3進程控制

進程和處理機管理的一個重要任務是進程控制。

所謂進程控制，就是系統使用具有特定功能的程序段來創建、撤消進程以及完成進程各狀態間的轉換，從而達到多進程高效率并發執行和協調、實現資源共享的目的。

系統在運行時分為兩種狀態：即核心態和用戶態。核心態也叫系統態或管態，是指CPU在運行操作系統的核心模塊；用戶態也稱用態，是指CPU正在運行用戶的程序。31

原語的概念：把系統態下執行的某些具有特定功能的程序段稱為原語，原語的特點是不可被中斷。

系統在創建、撤消一個進程以及要改變進程的狀態時，都要調用相應的程序段來完成這些功能。用于進程控制的原語有創建原語、撤消原語、阻塞原語和喚醒原語等。陷入用戶態核心態2.3.1進程的家族關系

操作系統通過內核原語來實現進程控制。在系統初始化完成后，系統就可創建進程。

創建者稱為父進程，被創建的新進程稱為子進程，子進程又可以創建自己的子進程，從而形成一棵有向的進程家族樹。

子進程與父進程之間的關系:

子進程的許多屬性都是從父進程繼承來的，子進程與父進程的區別是形成自己獨立的屬性。子進程可以從父進程繼承的屬性包括：用戶標識符、環境變量、打開文件、文件系統的當前目錄、已經連接的共享存儲區和信號處理處理例程入口表等。子進程不能從父進程繼承的屬性包括：進程標識符和父進程標識符等。進程創建資源滿足如I/O請求滿足就緒狀態阻塞狀態執行狀態結束進程等待資源如I/O請求執行完或撤銷2.3.2進程的創建與終止1．進程的創建fork.c

在多道程序環境下，為使程序運行，必須為他創建進程。系統發現要求創建進程的事件請求后，便通過調用創建原語Creat()創建進程。其步驟如下：（1）申請空白PCB。為新進程申請獲得惟一的進程標識符，并從PCB集合中索取一個空白PCB。（2）為新進程分配資源。包括新創建進程的程序、數據及用戶棧所需的內存空間。（3）初始化進程控制塊。初始化標識信息，如進程標識符；處理機狀態信息，使程序計數器指向程序的入口地址，使棧指針指向棧頂；處理機控制信息，將新建進程的狀態設置為就緒狀態（活動就緒或靜止就緒狀態）；進程的優先級等。（4）將新建進程插入就緒態隊列。352.3.2進程的創建與終止2．進程的終止過程

系統檢測到要求進程終止事件，操作系統調用進程終止原語，終止本進程的執行。操作過程如下：（1）根據被終止進程的標識符，從PCB隊列中檢索出該進程的PCB，從中讀出該進程的狀態。（2）若被終止進程正處于執行狀態，應立即終止該進程的執行，該進程被終止后應重新進行進程調度。（3）檢查該進程有無子孫進程，若有，則應將其所有子孫進程終止。（4）釋放終止的進程所占有的資源，將其歸還它的父進程或者系統。（5）將被終止的進程從它的PCB隊列中移出。362.3.3進程的阻塞與喚醒

進程狀態的轉換需要通過進程之間的同步或通信機構來實現，也可直接使用“阻塞原語”和“喚醒原語”來實現。

阻塞原語在一個進程期待某一事件發生，但發生條件還不滿足時，被該進程自己調用來阻塞自己，并轉換為等待狀態。

當等待隊列中的進程所等待的事件發生時，等待該事件的進程都將被喚醒。喚醒一個進程有兩種方法，一種是由系統進程喚醒，另一種是由事件發生進程喚醒。

37

實現進程的執行狀態到阻塞狀態的原語為阻塞原語；由阻塞狀態到就緒狀態轉換的原語分為喚醒原語

。入口保存該進程的CPU現場字置該進程的狀態為阻塞阻塞進程PCB進入等待隊列轉到進程調度入口從等待隊列取被喚醒進程將被喚醒進程置為就緒態被喚醒進程插入就緒隊列轉到進程調度或返回阻塞原語喚醒原語就緒--

運行運行

就緒進程創建資源滿足如I/O請求滿足就緒狀態阻塞狀態執行狀態結束進程等待資源如I/O請求執行完或撤銷2.3.4Linux系統調用

在Linux系統中，系統向用戶提供了一些對進程進行控制的系統調用。常用的有：1．fork()系統調用

fork.c

Linux利用fork()系統調用創建一個新進程。

fork()系統調用的格式是：

intfork()；

通常情況下，設返回值為intpid，調用格式為：pid=fork();fork()是通過復制來創建子進程的，子進程繼承父進程的上下文，是父進程的一個副本，與父進程使用同一段代碼。在該系統調用之后，兩個代碼相同的進程并發執行。

fork系統調出錯可能基于以下兩方面的原因：一是當前進程數量已達到系統規定的最大值，二是系統內存不足。40通常情況下，設返回值為intpid，調用格式為：pid=fork();其中，返回值pid意義如下：pid=0：創建子進程成功，表示從子進程返回，即

CPU正在運行該子進程。pid>0：創建子進程成功，表示從父進程返回，

pid的值為新創建的子進程標識號。pid=-1：創建失敗。用進程的家族關系main(){fork();fork();fork();printf(“S”);}SSSSSSSSacb例：編寫一段程序，使用系統調用fork()創建兩個子進程。當此程序運行時，在系統中有一個父進程和兩個子進程活動。讓每一個進程在屏幕上顯示一個字符：父進程顯示字符“a”，子進程分別顯示字符“b”和“c”。試觀察記錄屏幕上的顯示結果，并分析原因。acbmain(){intp1,p2;while((p1=fork())==-1);if(p1==0){printf(“%c”,”b”);exit();}else{while((p2=fork())==-1);if(p2==0){printf(“%c”,”c”);exit();}else(printf(“%c”,”a”);wait();wait();exit();}}}abcabccbaP2P1P2.3.4Linux系統調用

2．Exec系統調用利用exec系統調用執行另一個程序。在Linux系統中，當由fork()系統調用創建一個子進程后，可再利用exec()系統調用執行另一個程序。3．exit()系統調用對于一般的用戶進程，在其任務完成后應被盡快撤消。

Linux系統用exit()系統調用來實現進程的自我終止。通常，父進程在創建子進程時，應在進程的末尾寫一條exit()，使子進程自我終止。4．wait系統調用將調用進程掛起，直至其子進程因暫停或終止而發來軟中斷信號為止。45#include<stdio.h>main(){intp1,p2;while((p1=fork())==-1);/*創建進程p1，創建成功后退出*/if(p1==0)/*CPU運行P1*/{putchar(‘b’);exit();}else{while((p2=fork())==-1);/*創建子進程p2，創建成功后退出*/if(p2==0){putchar(‘c’);exit();}else{putchar(‘a’);wait();wait();exit();}/*父進程執行*/}}abc2.4進程的同步與互斥

進程的并發提高了系統效率，也同時導致了資源的競爭與共享。必須控制好進程的同步與互斥。2.4.1臨界資源的概念1．臨界資源

兩個或兩個以上的進程不能同時使用的資源為臨界資源。

臨界資源可能是一些獨占設備，如打印機、磁帶機等；也可能是一些共享變量、表格、鏈表等。47一個飛機訂票系統有兩個終端T1和T2，執行下面的并發進程:

intn; /*系統中剩余票的數量，若n>0則可賣票*/voidmain(){intn=100;parbegin(T1,T2);}并發進程T2的執行序列如下：

（2）進程T2的定義

voidT2(){do{read(n);if(n>=1){賣一張票；

n:=n-1;write(n);}}while(true);}}并發進程T1的執行序列如下：（1）進程T1的定義

voidT1(){do{read(n);if（n>=1）

{賣一張票；n:=n-1;write(n);}while(true);}}共享變量n就是本程序的臨界資源！2．臨界區

不論硬件臨界資源，還是軟件臨界資源，多個進程必須互斥地訪問臨界資源。臨界區:

每個進程中訪問臨界資源的那段代碼稱為臨界區。進入區:

在臨界區前面增加一段用于進行檢查是否正被其他進程訪問的的代碼，把這段代碼稱為進入區，進入區設置訪問標志；退出區:

在臨界區后面再加一段用于退出臨界區的代碼，稱為退出區，退出區取消訪問標志。剩余區:

進程中除去上述各區外，其它部分的代碼，稱為剩余區。49進入;----互斥臨界區退出;----同步2．臨界區因此，一個訪問臨界資源的進程描述如下：repeat

進入區；檢查是否有進程使用臨界資源，有則阻塞自己，無則設置標志臨界區；使用臨界資源

退出區；使用完臨界資源后釋放臨界資源，設置未使用標志，其他進程使用剩余區；其他代碼untilfalse;512.4.2

進程的互斥與同步1．同步與互斥的概念

進程互斥是指多個進程不能同時使用同一個臨界資源CR，即兩個或兩個以上進程必須互斥地使用臨界資源，或不能同時進入臨界區CS。

兩個邏輯上完全獨立、毫無關系的進程，由于競爭同一個資源而相互制約，就稱為進程的互斥。

如系統只有一臺打印機，兩個進程都要使用。為了保證打印結果的正確和方便使用，只能一個進程用完打印機后，另一個進程才能使用。

進程同步，是指有協作關系的進程之間，要不斷地調整它們之間的相對速度或執行過程，以保證臨界資源的合理利用和進程的順利執行。實現進程同步的機制稱為進程同步機制。如兩個進程合作使用同一個緩沖區。設進程A負責往緩沖區中輸入數據，進程B負責從同一緩沖區中輸出數據。當進程A將數據輸滿緩沖區，則只有當進程B將該數據讀出后，進程A才能繼續使用該緩沖區，否則將造成數據丟失。此時，進程A和進程B之間就形成了同步關系。532．同步機制應遵循的規則為實現進程互斥地進入自己的臨界區，所有同步機制都應遵循下列準則：（1）空閑讓進：并發進程中某個進程不在臨界區時，不阻止其他進程進入臨界區。（2）忙則等待：并發進程中的若干個進程申請進入臨界區時，只允許一個進程進入。當已有進程進入臨界區時，其他申請進入臨界區的進程必須等待，以保證對臨界資源的互斥訪問。（3）有限等待：

保證等待有限時間，不能無限期等待，陷入“等死”狀態。（4）讓權等待：當進程不能進入自己的臨界區時，應立即釋放處理機，以免進程陷入“忙等”狀態。54實現同步互斥的方法硬件方法軟件方法2.4.3實現進程同步的軟件方法

1981年，G.L.Peterson提出了一個簡單的算法來解決進程互斥進入臨界區的問題。這種方法描述為：為每個進程設置一個標志，當標志值為true時，表示此進程要求進入臨界區，另外，再設置一個指示器turn，用來標識由哪個進程可以進入臨界區，即當turn=＝i時，表示進程pi可以進入臨界區。以下是Peterson算法的描述。56bolinside[2]={false,false};eum[0,1]turn;cobegin

processP0(){inside[0]=true;turn=1;while(inside[1]&&turn==1);

臨界區；

iside[0]=false;}processP1(){inde[1]=true;turn=0while(inside[0]&&turn==1);

臨界區；

iside[1]=false;}coend2.4.4實現進程同步的硬件機制許多計算機已經提供了一些特殊的硬件指令，允許對一個字中的內容進行檢測和修改正，或者是對兩個字的內容進行交換等。可利用這些特殊的指令來解決臨界區問題。下面是實現對臨界區管理的硬件方法。1．關中斷

實現互斥最簡單的方法是在進程進入臨界區時關中斷，進程退出臨界區時開中斷。中斷被關后，時鐘中斷也被屏蔽，進程上下文切換都是由中斷事件引起的，這樣進程的執行就不會被打斷，因此采用關中斷、開中斷的方法就可確保并發進程互斥地進入臨界區。2．測試并設置指令使用硬件所提供的“測試并設置”機器指令TS(TestandSet)，實現進程之間的互斥。該指令是一條原語，需獨立執行，可把這條指令看作函數，它的返回值和參數都是布爾類型。當TS(&x)測到x值為true時，置x=false，且根據所測試到的x值形成條件碼。3．對換指令對換指令swap用于交換兩個字的內容。2.5信號量機制2.5.1信號量的概念信號量（Semaphore），也叫做信號燈，它是在信號量同步機制中用于實現進程的同步和互斥的有效數據結構。

可以為每類資源設置一個信號量。

它有多種類型的數據結構，即：整型信號量、記錄型信號量、ＡＮＤ型信號量及信號量集等。

申請和釋放臨界資源的兩個原語操作：

P操作--wait操作；進入區

V操作--signal操作；退出區

P、V操作的操作對象是信號量61semaphores1=2,s2=3;AND型信號量

P(S1,S2);P(S1);P(S2);V(S1,S2);V(S1);V(S2);信號量集

P(S1,T1,D1;S2,T2,D2);P(S1,2,1;S2,3,2;S3,1,1);P(S1,2,0;S2,3,2);1．整型信號量

整型信號量的數值表示當前系統中可用的該類臨界資源的數量。如設置整型信號量s，則s的值意義為：s>0，則s的值表示系統中空閑的該類臨界資源的個數；s=0，則表示系統中該類臨界資源剛好全部被占用，而且沒有進程在等待該臨界資源；s<0，則s的絕對值表示系統中的進程等待該類臨界資源的個數；63申請、進入臨界區Wait(s)【P(S)】互斥

釋放、退出臨界區Signal(s)【V(s)】同步

P(s)或者Wait(s)：While(s<=0)

進程等待；

s=s-1;注：S表示資源信號量64Signal(s)【V(s)】

s=s+1;注：S表示資源信號量2．記錄型信號量

記錄型信號量的數據結構由兩部分構成。定義記錄型信號量類型，有如下描述：

structsemaphore{

ints;structPCB*queue;}semaphore；65

定義記錄型信號量Ｓ，則：s的值value表示系統中可用的該類臨界資源的數量;

queue為進程鏈表指針，指向等待該類資源的PCB隊列是Wati(S)-p(s)s=s-1申請到資源本進程繼續本進程入阻塞隊列s≥0否轉進程調度

2.5.2信號量的申請與釋放66wait(S){S.value=s.value-1;ifS.value≥0

本進程繼續；

Else{

將本進程放入阻塞態隊列；轉進程調度;}}是signal(S)-v(s)s=s+1喚醒一阻塞態進程s≤0否釋放該類資源本進程繼續

設變量Ｓ為記錄型信號量:

V(S)、signal（Ｓ）操作的流程如下圖所示：67voidsignal(S){S.value=s.value+1;

ifs≤0then

喚醒指針queue所指的阻塞態進程；

}2.5.3利用信號量實現進程的同步和互斥

可以用wait(s)和signal(s)操作處理飛機買票問題。對臨界資源n設一互斥信號量S，將原進程T1及T2做如下修改：進程：semaphoreS=1；T1()進程：T2(){{

P(s)；

P(s)；

read(n);read(n);ifn>=1ifn>=1{n:=n-1;{n:=n-1;write(n);write(n);

V(s)；V(s)；賣一張票；｝賣一張票；｝

}}利用P、V操作可以實現進程之間的同步。關于這類問題的應用有兩種類型：一種是對于臨界資源，在使用之前申請，使用之后釋放，我們給這類資源設一個互斥信號量即可；第二種類型是利用信號量控制進程之間運行的順序，這時需要根據實際情況設置多于一個信號量，對同一個信號量的P、V操作在不同的進程之間進行。2.6進程同步問題舉例

692.6.1

兩個簡單的例子

例1．系統中有多個進程，共同使用一臺打印機。寫出這些進程并發執行時，同步使用打印機的程序段。70解：同步使用打印機的程序段為：semaphores=1;／＊定義打印機信號量并賦初值＊／voidmain(){parbegin(P1，P2，……,Pn);}Pi()(i=1,2,3,……n){……P(S);

打印，V(S);……}在這個例子中，多個進程隨機使用打印機信號量，使用之前先申請，使用之后釋放該信號量。。2.6.1

兩個簡單的例子

例2．有一個緩沖區，供多個進程共享。這些進程中有生產者進程和消費者進程。寫出多個進程共同使用同一個緩沖區時實現進程同步的程序。71緩沖區用來臨時存放數據，在使用緩沖區時應該注意:對一個緩沖區，數據的寫入和提取應當是交替執行的，否則會發生錯誤：數據丟失或數據重復。緩沖區Bufproducerconsumer1024Binout73consumer(){while(1){P(full);P(mutex);從緩沖區取數據；V(empty);V(mutex);……}}{while(1){P(empty);P(mutex);往緩沖區存放數據；V(full);V(mutex);……}}解：同步使用一個緩沖區的程序段為：semaphoreempty=n,full=0，mutex=1;／＊定義信號量并賦初值＊／

voidmain(){parbegin(producer,consumer);}注意：在該程序中，對同一個信號量的P、V操作是在兩個不同進程之間進行的，這樣可以保證讀進程和寫進程交替使用該緩沖區。例：P1--P2---P3producer()2.6.1生產者—消費者問題

1．問題的描述

有一批生產者進程在生產產品，并將這些產品提供給消費者進程去消費。生產者進程與消費者進程能并發執行，在兩者之間設置了一個具有n個緩沖區的緩沖池.

生產者進程將它所生產的產品放入一個緩沖區中；消費者進程可從一個緩沖區中取走產品去消費。規定消費者進程不能到一個空緩沖區中去取產品；生產者進程不能將產品放入一個已裝滿產品且尚未被取走的緩沖區中。74012……i………n-2n-1

用一個數組表示上述具有n（0，1，…，n-1）個緩沖區的緩沖池。設一個輸入指針in，表示下一個可存放產品的緩沖區，每當生產者進程生產一個產品并放入該緩沖區后，in:=in+1；設一個輸出指針out，表示下一個可從中取得產品的緩沖區，每當消費者進程從此取走一個產品后，out:=out+1。考慮此處的緩沖池構成了循環緩沖，故當輸入或輸出指針加1時表示為in:=(in+1)%n；out:=(out+1)%n。當(in+1)%n=out時，表示緩沖池滿；當in=out時則表示緩沖池空。75inout

用整型變量counter表示該緩沖池中滿緩沖區的個數，顯然，每當生產者進程向緩沖池中存放一個產品后，counter加1；每當消費者進程從緩沖區中取走一件產品后，counter減1;

假設初始情況下緩沖池為空，即counter＝０。為在生產者—消費者問題中實現各進程的同步，可設下列信號量：（假設初始情況下沒有進程使用緩沖池，且緩沖池中各緩沖區都是空的。）

mutex：互斥使用緩沖池信號量，由于初始情況下無進程使用緩沖池，故初值mutex=１；

empty：表示緩沖池中空閑的緩沖區數目，由于初始情況下所有緩沖區為空，故初值empty=n；

full：表示緩沖池中有產品的緩沖區的數目，由于初始情況下沒有緩沖區存放產品，故初值full＝０。76算法及程序：semaphore

mutex=1,empty=n,full=0;

＊定義信號量并賦初值＊／

messagebuffer[n];

intin=0,out=0;

／＊定義存取指針的初始位置＊／

voidmain(){parbegin(proceducer,consumer);}生產者進程voidprocedure(){do{生產一件產品;

…P(mutex);P(empty);將產品放入緩沖區buffer[in];in=(in+1)%n;

V(mutex);

V(full);

}while(true);}77fullempty消費者進程：voidconsumer(){do{

P(full);

P(mutex);

從緩沖區buffer[out]中取走一件產品;out=(out+1)%n;

V(mutex);

V(empty);

消費這件產品;}while(true);}78fullempty臨界資源：

緩沖池、空閑區、存貨區；對應信號量：

緩沖池==》mutex

空閑區==》empty

存貨區==》full信號量初值：mutex=1；

empty=n；

full=0;

79fullempty生產者進程

生產一件產品;

…

P(empty);

P(mutex);

將產品放入緩沖區

in=(in+1)%n;

V(mutex);

V(full);消費者進程：

P(full);

P(mutex);

從存放緩沖區中取走一件產品;out=(out+1)%n;

V(mutex);

V(empty);

消費這件產品;

4．在生產者—消費者問題中應注意：

（１）在每個程序中用于實現互斥的P(mutex)和V(mutex)必須成對地出現。（２）對資源信號量empty和full的P和V操作，同樣需要成對地出現，但它們分別處于不同的進程中，這樣保證生產者進程和消費者進程的同步及交替執行。（３）在每個進程中，兩個P操作順序不能顛倒，而signal操作的次序是無關緊要的。802.6.3讀者—寫者問題

1．問題的提出

一文件Ｆ可以被多個并發進程共享，將這些訪問該文件的分為讀進程和寫進程。試用P、V操作解決各進程間的同步問題。81共享文件F寫進程W讀進程R1讀進程Rn…圖2-13讀者—寫者問題

設讀進程為reader，寫進程為writer。822．問題的分析寫進程WSemaphorewmutex=1;W—W互斥W----R互斥W與所有R互斥intcounter=0;If（第一個)P(wmutex);readfile……If(最后一個）V(wmutex);Reader(){P(rmutex);if(counter==0)P(wmutex);counter++;V(rmutex);讀文件;P(rmutex);counter--;if(counter==0)V(wmutex);V(rmutex);離開;}寫進程W共享文件F讀進程R1讀進程Rn…R---W互斥R---R同時intcounter=0;Semaphorewmutex=1,rmutex=1;Reader(){if(counter==0)P(wmutex);counter++;讀文件;counter--;if(counter==0)V(wmutex);離開;}Reader(){if(counter==0)P(wmutex);counter++;讀文件;counter--;if(counter==0)V(wmutex);離開;}設如下變量及信號量：計數器:intreadcount=0;（1）臨界資源：共享文件F和整型變量readcount

（2）信號量：共享文件F對應信號量為wmutex；整形變量readcount對應信號量rmutex；

（3）信號量初值：wmutex=1;

rmutex=1。853．算法及程序

讀者—寫者問題可描述如下：intreadcount=0;semaphorermutex=1,wmutex=1;voidmain(){parbegin(reader,writer);}86讀者進程：voidreader(){

P(rmutex);if(readcount==0)P(wmutex);

readcount++;

V(rmutex);

…

進行讀操作;…

P(rmutex);

readcount--;

if(readcount==0)V(wmutex);V(rmutex);}

87寫者進程：voidwriter(){……

P(wmutex);

執行寫操作;

V(wmutex);}884．注意事項及提示（1）對于寫進程，共享文件是臨界資源；而對于讀進程，該文件不是臨界資源。（2）整型變量readcount是臨界資源，所以在使用前后要對其信號量rmutex進行P、V操作。南北橋2.6.4哲學家進餐問題1．問題的提出

設有5個哲學家圍坐在一張圓桌前吃飯。桌上有5只筷子，在每人之間放一只。哲學家要吃飯時，只有分別從左、右兩邊都拿到筷子時，才能吃飯。如果筷子已在他人手上，則該哲學家必須等待到他人吃完后才能拿到筷子；任何一個哲學家在自己未拿到兩只筷子吃飯之前，決不放下自己手里的筷子。試描述5位哲學家吃飯的進程。90圖2-14哲學家就餐問題0101semaphorechop=5;Pi(){……

P(chop);P(chop);

吃；

V(chop);

V(chop);}

2．問題分析

放在桌子上的每根筷子是臨界資源，在一段時間內只允許一位哲學家使用。

為了實現對筷子的互斥使用，可以為每一只筷子設置一個信號量，由這五個信號量構成信號量數組：semaphorechopstick[5];

設初始條件下，所有哲學家都未吃，故所有信號量均被初始化為1。3．實現方法

假設每一位哲學家拿筷子的方法都是：先拿起左邊的筷子，再拿起右邊的筷子。

925個哲學家就餐問題

臨界資源：5只筷子

信號量：每只筷子一個信號量semaphorechopstick[5]={1,1,1,1,1};

則第i位哲學家的活動可描述為：

93

semaphore

chopstick［5］={1,1,1,1,1};

//5個互斥信號量viodmain(){parbegin(P0(),P1(),P2(),P3(),P4());}94

Pi()/*i=0,1,2,3,4*/{while(1){{P(chopstick［i］);P(chopstick［(i+1)%5］);

eating;

…

V(chopstick［i］);

V(chopstick［(i+1)%5］);

thinking;}}95

Pi()/*i=0,1,2,3,4*/{while(1)

{P(S);

P(chopstick［i);P(chopstick［(i+1)%5］］);}

eating;

…

V(chopstick［i］);

V(chopstick［(i+1)%5］);

V(S);

thinking;}}Semaphores=4;

以上算法存在一個問題：假設5個哲學家同時拿起左邊的筷子，那么再去拿右邊的筷子時，就會產生死鎖。下面給出幾種解決方法。（1）至多只允許有四位哲學家同時去拿左邊的筷子，最終能保證至少有一位哲學家能夠進餐，并在用畢時能釋放出他用過的兩只筷子，從而使更多的哲學家能夠進餐。（2）僅當哲學家的左、右兩只筷子均可用時，才允許他拿起筷子進餐。（3）規定奇數號哲學家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數號哲學家則相反。最后總會有一位哲學家能獲得兩只筷子而進餐。具體程序段參看實訓教材。974．不產生死鎖的哲學家就餐問題算法補充例題1

某銀行提供1個服務窗口和10個供顧客等待的座位。顧客到達銀行時，若有空座位，則從取號機上取一個號，等待叫號。取號機每次僅允許一個顧客使用。當營業員空閑時，通過叫號選取一位顧客，并為其服務。顧客和營業員的活動過程描述如下：顧客進程{從取號機取一個號碼；等待叫號；獲取服務；}營業員進程{叫號；為客戶服務；}請添加必要的信號量和P、V操作，實現上述過程中的互斥和同步。要求寫出完整的過程，說明信號量的含義并賦初值。分析

（1）臨界資源等待的座位，互斥的，一個座位一個人取號機，互斥使用服務窗口，營業員與顧客同步使用

（2）信號量等待的座位：seets

取號機：mutex

服務窗口：haveCustom顧客與營業員同步

（3）初值

seets=10,//有10個坐位的資源信號量

mutex=1,//取號機互斥信號量

haveCustom=0;//顧客與營業員同步，無顧客時營業員休息

解：semaphoreseets=10,//有10個坐位的資源信號量mutex=1,//取號機互斥信號量haveCustom=0;//顧客與營業員同步，無顧客時營業員休息

process顧客

{

P(seets);//等空位

P(mutex);//申請使用取號機

從取號機上取號;

V(mutex);//取號完畢

V(haveCustom);//通知營業員有新顧客到來，等待營業員叫號;

V(seets);//離開坐位接受服務；}

process營業員

{while(True)

{P(haveCustom);//沒有顧客則休息叫號;

為顧客服務;}}補充例題2

假定系統有三個并發進程read,move和print共享緩沖器B1和B2。進程read負責從輸入設備上讀信息，每讀出一個記錄后把它存放到緩沖器B1中。進程move從緩沖器B1中取出一記錄，加工后存入緩沖器B2。進程print將B2中的記錄取出打印輸出。緩沖器B1和B2每次只能存放一個記錄。要求三個進程協調完成任務，使打印出來的與讀入的記錄的個數，次序完全一樣。請用P、V操作，寫出它們的并發程序。readPrintmoveB1B2分析（1）并發進程：

read,move和print（2）臨界資源緩沖器B1：read、move互斥使用，又相互協作緩沖器B2：move、print互斥使用，又相互協作（3）信號量緩沖器B1信號量：

s1:read、move互斥使用

empty1、full1read、move同步緩沖器B2信號量：

s2:move和print互斥使用

empty2、full2move和print同步

（4）初值

empty1=m、empty2=n;緩沖區數量

full1=0、full2=0;控制同步

s1=1、s2=1控制互斥其同步描述如下：intempty1=m;/*也可定義為其他信號量類型*/intempty2=n;intfull1=0;intfull2=0;ints1=1;ints2=1;main(){ PA(); PB(); PC();}read(){從設備讀一批數據；

p(empty1);

P(S1);

將數據存入緩沖池B1；

V(S1);

v(full1);}move(){

P(full1);P(S1);

從緩沖池B1中取出數據；

V(S1);

V(empty1);/*前半部分結束*/

將數據進程加工；

P(empty2);P(S2);

將數據存入緩沖池B2；

V(S2);

V(full2);}print(){

P(full2);P(S2);

從緩沖區2中取出數據；

V(S2);

V(empty2);

打印數據；}readPrintmoveB1B2補充例題3在一輛公共汽車上，司機和售票員各行其職，司機負責開車和到站停車；售票員負責售票和開、關門，當售票員關好車門后，司機才能繼續開車行駛。試用P、V操作實現司機與售票員之間的同步。分析（1）并發進程：

司機進程driver和售票員進程busman

（2）臨界資源：車輛啟動與車門開關（3）信號量：

S1：是否允許司機啟動汽車的變量

S2：是否允許售票員開門的變量

（4）初值

S1=0：不得啟動汽車

S2=0：不得開門driver()//司機進程

{

P(S1);//請求啟動汽車

啟動汽車;正常行車；到站停車；

V(S2);//釋放開門變量，相當于通知售票員可以開門

}busman()//售票員進程

{關車門;

V(S1)；//釋放開車變量，相當于通知司機可以開車售票到站

P(S2)；//請求開門開車門；上下乘客；

}Semaphores1=0;

Semaphore

s2=0;main(){ driver(); busman();}

補充例題4一家四人父、母、兒子、女兒圍桌而坐；桌上有一個水果盤；（1）當水果盤空時，父親可以放香蕉或者母親可以放蘋果，但盤中已有水果時，就不能放，父母等待。當盤中有香蕉時，女兒可吃香蕉，否則，女兒等待；當盤中有蘋果時，兒子可吃，否則，兒子等待。分析（1）并發進程：

父親、母親、兒子、女兒

（2）臨界資源：盤子（3）信號量：

SE(空盤子)；

SA（放了蘋果的盤子）；

SB(放了香蕉的盤子)

（4）初值

SE=1(空盤子)；

SA=0（放了蘋果的盤子）；

SB=0(放了香蕉的盤子)SemaphoreSE=1；SA=0;SB=0;main(){ 父親();

母親();

兒子();

女兒();}

父親(){

P(SE)

放香蕉

V(SB)//通知女兒)母親（）{

P(SE)

放蘋果

V(SA)//通知兒子}兒子（）{

P(SA)拿蘋果

V(SE)}女兒（）{

P(SB)拿香蕉

V(SE)}（2）把（1）改為：兒子要吃蘋果時，請母親放蘋果，女兒要吃香蕉時，請父親放香蕉，（還是盤子為空時才可以放）。父親(){

P(SF)P(SE)

放香蕉

V(SB)//通知女兒)母親（）{

P(SM)P(SE)

放蘋果

V(SA)//通知兒子}兒子（）{

V(SM)P(SA)拿蘋果V(SE)}女兒（）{

V(SF)P(SB)拿香蕉V(SE)}再增加兩個信號量：SF=0，女兒請求吃香蕉；,SM=0兒子請求吃蘋果2.7管程

在進程能夠共享內存的前提下，如果能集中和封裝針對一個共享資源的所有訪問，即把相關的共享變量及操作集中在一起統一控制和管理，就可以方便地管理和使用