計算機操作系統第二章進程管理（進程同步與互斥）2009年1個選擇、1個綜合應用題

2010年3個選擇

2011年2個選擇，1個綜合應用題

2012年2個選擇

2013年2個選擇,1個綜合應用題

2014年2個選擇，1個綜合應用題進程管理是本課程的重點章節，這部分介紹的是操作系統5大管理功能之一：處理機管理，包括進程管理和處理機調度兩大塊的內容。本章的是學習和考試的重點內容，同時也是難點。這部分除了要掌握基本的概念和基本的原理外，還要求能運用這些基本原理去分析和解決問題。

進程同步與互斥是進程管理的重點，也是操作系統學科的一個難點。具體包括:進程同步的基本概念、實現臨界區互斥的基本方法(包括軟件實現方法、硬件實現方法)、信號量(P、V操作)、管程、經典同步問題(包括生產者-消費者問題、讀者-寫者問題、哲學家進餐問題等)。我們一定要掌握P、V操作的概念、流程，以及P、V操作在同步問題、互斥問題中的應用。首先,要求掌握進程的概念，其中進程和程序這兩個概念的區別和聯系一定要搞清楚。第二,要記住進程的三個基本狀態以及它們之間相互轉換條件，一定要記住不可能從就緒狀態直接轉換到等待狀態。第三,需要理解進程控制和原語這兩個概念，掌握進程的創建、撤銷、阻塞、喚醒的條件，理解四種原語的執行過程。第四,理解什么是并發進程間的直接制約以及由直接制約所引發的進程同步，重點要掌握如何用P、V原語操作實現同步問題，要會利用P、V原語操作來解決經典的同步問題；第五,了解進程的通信方式及它們各自的特點；第六,要理解進程和線程的異同以及多線程模型；第二章進程管理2.1進程的基本概念2.2進程控制2.3進程同步2.4經典進程的同步問題2.5進程通信2.6線程基礎知識總結實戰練習綜合應用題操作系統在管理進程與線程的過程中需要完成以下工作：（1）用戶和系統進程的創建和刪除；（2）進程的調度；（3）為進程的同步、通信、死鎖處理提供機制。多道程序設計的提出

其基本思想是在主存中同時存放多個用戶的作業，使之同時處于運行狀態而共享系統資源。宏觀上是并行運行，微觀上是依次輪流并發運行的。之所以采用多道程序設計技術，是由于中斷和通道技術的出現，CPU可以把直接控制輸入/輸出的工作轉給通道。多道程序的目標、方法和主要問題（1）目標：是充分使用系統所有資源并盡可能地使它們并行工作，這種技術可把硬件的代價交叉分布在大量并行用戶之間，而使計算機系統的代價極小化。（2）方法：是一個正在運行的程序不使用某設備時，讓另一程序去使用該設備。為了發揮多道程序設計的有效性，應選擇各種不同類型的作業同時執行，讓資源處于忙碌狀態。（3）多道程序設計實現的3個問題：存儲保護、程序浮動、處理機和系統資源的管理和調度。多道程序系統所必須解決的問題（1）提出解決各種沖突的策略（2）協調并發活動的關系（3）保證數據的一致性（4）實現數據的存取控制2.1進程的基本概念2.1.1程序的順序執行及其特征：順序性、封閉性、可再現性。作業1：什么叫程序順序執行的封閉性和可再現性？封閉性：程序執行得到的最終結果由給定的初始條件決定，不受外界因素的影響。可再現性：只要輸入的初始條件相同，則無論何時重復執行該程序都會得到相同的結果。2.1.2前趨圖：有向無循環圖，DAG（DirectedAcyclicGraph），描述進程之間執行的前后關系。直接制約關系：同步間接制約關系：互斥2.1.3程序的并發執行及其特征：間斷性(制約性)、失去封閉性、不可再現性（不可重復，例：變量的共享）。2.1.4進程的定義、特征與狀態引入進程的目的：是使多個程序能并發執行，提高資源利用率和系統吞吐量。2011年32、有兩個并發執行的進程P1和P2，共享初值為1的變量x。P1對x加1，P2對x減1。加1和減1操作的指令序列分別如下所示。

//加1操作//減1操作

loadR1,x//取x到寄存器R1中loadR2,xincR1decR2storex,R1//將R1的內存存入xstorex,R2兩個操作完成后，x的值A可能為-1或3B只能為1C可能為0、1或2D可能為-1、0、1或22009年23、單處理機系統中，可并行的是(D)

I進程與進程II、處理機與設備

III、處理機與通道IV、設備與設備

A、I、II、和III

B、I、II和IV

C、I、III和IV

D、II、III和IV1、進程的定義進程的概念起于，20世紀60年代初期，MIT的MULTICS和IBM的CTSS/360。解釋多種，并不等價進程是程序的一次執行進程是可以參與并發執行的程序進程是程序與數據一道通過處理器執行時所發生的活動。所謂進程，就是一個程序在給定的空間和初始環境下，在一個處理器上執行的過程。1978年，廬山會議上：進程是具有一定獨立功能的程序關于一個數據集合的一次運行活動。以上說法本質是相近的，都強調程序的執行，即進程的動態性，與程序的本質的差異本書的理解進程的組成：進程包括程序代碼（程序段或文本段）、堆棧段（臨時數據，如函數參數、返回地址和局部變量）、數據段（包括全局變量）、堆（進行運行期間動態分配的內存）PCB：ProcessControlBlock進程表空間：PT進程圖：

內存中的進程如右圖示：棧堆數據文本數據一般包括靜態變量、動態堆和動態棧。堆用來保存動態變量，棧用來保存用戶子程序相互調用時的參數、局部變量、返回值、斷點等。2、特征動態性：最基本。并發性：獨立性：獨立運行、獨立分配資源和獨立接受調度。異步性：進程以各自獨立的，不可預先的速度向前推進。可能會造成不正確的情況出現，原因與進程占用處理器的時間、執行的速度以及外界的影響有關，都與時間有關。稱為與時間有關的錯誤。又稱競爭條件，RaceCondition結構特征：程序段、相關的數據段和PCB構成的進程實體。定義：一個程序段在一個數據段上的一次執行過程。作業2：簡述進程和程序的區別和聯系進程和程序是既有聯系又有區別的兩個概念（1）程序是指令的集合，靜態概念，進程是程序在處理機上的一次執行過程，動態概念。（2）程序是長期存在的，進程有生命周期，有創建、活動、消亡。（3）進程與程序之間不是一一對應的，即同一程序同時運行于若干不同的數據集合上，它將屬于若干個不同的進程，但一個進程只能對應一個程序。聯系：（4）程序僅是指令的有序集合，是構成進程的組成部分之一，進程則由程序、數據和進程控制塊組成，一個進程存在的目的就是執行其所對應的程序，沒有程序，進程就失去了其存在的意義。3、進程的三種基本狀態就緒狀態ready：三種情況的進程構成了就緒隊列執行狀態run(運行態)：當前進程，至少一個阻塞狀態blocked：等待狀態wait、睡眠狀態sleeped、休眠狀態。作業3：畫出三種基本狀態之間的轉換方向并標明每一種轉換的原因：這個時候，需要進行重新調度，會發生進程上下文內容的切換。這個地方考試的考法有多種形式兩個基本隊列：就緒隊列和等待隊列。隊列管理模塊：入隊和出隊。重復一下中斷處理過程（1）喚醒被阻塞的驅動程序進程。（2）保護被中斷進程的CPU環境。程序是指令在N位置時被中斷的，程序計數器中的內容為N+1，所有寄存器的內容都被保留在中斷保留區（棧）中。（3）分析中斷原因、轉入相應的設備中斷處理程序。（4）進行中斷處理。不同的設備有不同的中斷處理程序。（5）恢復被中斷進程的現場。處理機再執行本程序時，從N+1開始。恢復的內容：包括第N+1條指令的地址（IR寄存器或PC計數器）、處理機狀態字PSW(標志寄存器)、通用寄存器和段寄存器的內容注：此處與第四章中的缺頁中斷和缺段中斷相區別200926、下列選項中，降低進程優先級的合理時機是（）A進程的時間片用完B進程剛完成I/O，進入就緒隊列C進程長期處于就緒隊列中D進程從就緒態轉化為動行態2012年23、下列選項中，不可能在用戶態發生的事件是（）A系統調用B外部中斷C進程切換D缺頁24、中斷處理和子程序調用都需要壓棧以保護現場，中斷處理一定會保存而子程序調用不需要保存其內容的是（）A程序計數器B程序狀態字寄存器C通用數據寄存器D通用地址寄存器4、掛起狀態：終端用戶的請求，父進程請求，負荷調節的需要，操作系統的需要。進程狀態的轉換：5、創建狀態和終止狀態：2012年30、若某單處理器多進程系統中有多個就緒態進程，則下列關于處理機調度的敘述中錯誤的是（）A在進程結束時能進行處理機調度B創建新進程后能進行處理機調度C在進程處于臨界區時不能進行處理機調度D在系統調用完成并返回用戶態時能進行處理機調度2013年2014年26.一個進程的讀磁區操作完成后，操作系統針對該進程必做的是A.修改進程狀態為就緒態B.降低進程優先級C.進程分配用戶內存空間D.增加進程的時間片大小例1：簡述三種基本狀態之間的轉換方向及原因：絕對不會出現的是從阻塞到執行狀態的轉換。進程隊列：就緒隊列和等待隊列。入隊和出隊。例2：處于就緒隊列中的進程是由哪三種類型的進程組成的解：（1）新進程（2）因時間片用完而中斷運行的進程（3）因等待的條件發生而被喚醒的進程例3：在一個只有單處理機的操作系統中，進程有運行、就緒、等待三個基本狀態。假如某時刻操作系統中有10個進程并發執行，且CPU以非核心態情況下，試問：（1）這時刻系統中處于運行狀態的進程數最多有幾個？最少有幾個？（2）這時刻系統中處于就緒狀態的進程數最多有幾個？最少有幾個？（3）這時刻系統中處于等待狀態的進程數最多有幾個？最少有幾個？解：（1）因為系統中只有一個處理機，所以某時刻處于運行狀態的進程數最多有1個。而最少可能為0，此時其他10個進程一定全部排在各等待隊列中，在就緒隊列中沒有進程，在實際的操作系統中，此時CPU是在運行操作系統的空閑進程（SystemIdleProcess）或線程。（2）處于就緒狀態的進程數最多只有9個，不可能出現10個，因為一旦CPU有空，調度程序馬上調度；處于就緒狀態的進程數最少是0個，1個進程運行，9個進程等待，或者10個進程全部等待。（3）處于等待狀態的進程數最多有10個，等待狀態的進程最少是0個。例3：某系統在t0時刻，打印機剛剛打印完畢或者剛剛開始打印，試問該時刻系統內部發生了進程狀態變化的情況如何？2.1.5進程控制塊：任務控制塊,斷點現場保存區域，系統空間，只有操作系統才能夠對其進行存取，用戶程序不能訪問。1、PCB的作用：將程序變成可并發執行的進程，是進程存在的惟一標志。操作系統是根據PCB來對并發執行的進程進行控制和管理的。常駐內存。系統會集中存儲所有進程的PCB，構成進程表空間PT。2、PCB中的信息

(1)進程標識符：內部和外部標識。進程標識為一個整數，稱為進程號，用于區分不同的進程，用戶標識，通常也為一個整數，稱為用戶號，用于區分不同的用戶。一個進程號與唯一的用戶號相對應，而一個用戶號可對應多個進程號，即一個用戶可同時擁有多個進程。

(2)處理機狀態：通用寄存器、PC、PSW（標志寄存器）、地址映射寄存器和用戶棧指針。進程的運行環境。

(3)進程調度信息：進程狀態、進程優先級、調度的其他信息、阻塞事件。

(4)進程控制信息：程序和數據的地址、同步和通信機制、資源清單和鏈接指針。3、PCB的組織方式：鏈接和索引。作業4：試從進程管理、中斷處理、文件管理、存儲管理、設備管理的角度設計進程控制塊應包含的項目。（北京大學1999年研究生試題）解：1、從進程管理的角度考慮，PCB應包含進程標識符、進程狀態、CPU狀態信息（包括程序計數器、程序狀態字、棧指針、通用寄存器等）、進程調度信息（進程的優先數）、鏈接指針（用于將PCB鏈入各種隊列）等項信息。2、從進程通信的角度考慮，PCB中應包含消息隊列指針、實現消息隊列互斥訪問的互斥信號量、描述消息隊列中消息個數的資源信號量。3、從中斷處理的角度考慮，PCB中應包含CPU狀態信息。4、從文件管理的角度考慮，PCB中應包含用戶文件描述符表，用來登記用戶打開的各個文件，并可以通過它找到在內存的相應文件的FCB5、從存儲管理的角度考慮，應保存進程的程序、數據、堆棧在內存和外存的地址和各部分長度等信息。6、從設備管理角度考慮，應有該進程所需資源和已分配到的資源清單。進程上下文（Context）實際上是進程執行活動全過程的靜態描述。又稱進程映像。包括三個組成部分：（1）用戶級上下文。由用戶程序代碼、用戶數據段（含共享數據塊）和用戶堆棧組成的進程地址空間。（2）系統級上下文。包括進程的標識信息、現場信息、控制信息、進程環境塊，以及系統堆棧等組成的進程地址空間。（3）寄存器上下文。由程序狀態字寄存器和各類控制寄存器、地址寄存器、通用寄存器組成。ContextSwitch發生在寄存器和內存之間，依賴于內存速度，復制的寄存器的數量，是否有特殊指令等。可再入程序是指一個能被多個用戶同時調用的程序：必須是純代碼，要求調用者提供工作區。2.2進程控制作業5：原語操作的定義：是指由若干條指令組成、用來實現某個特定操作的一個過程，其執行具有原子性，即原語在執行過程中不允許被中斷，常駐內存，在核心態下運行。2.2.1進程的創建：pid=fork()、CreateProcess()(1)進程圖：描述一個進程的家族關系的有向圖。(2)引起創建進程的事件：用戶登錄，作業調度，提供服務和應用請求。(3)進程的創建：申請空白PCB，為新進程分配資源，初始化PCB，將新進程插入就緒隊列。(4)進程的創建請求系統為一個程序分配一個工作區和建立一個進程控制塊。當進程創建新進程時，有兩種執行可能：（1）父進程與子進程并發執行（2）父進程等待，直到某個或全部子進程執行完。新進程的地址空間也有兩種可能（1）子進程是父進程的復制品（具有與父進程相同的程序和數據）（2）子進程裝入另一個新程序2010年24、下列選項中，導致創建新進程的操作是（C）

I用戶登陸成功

II設備分配

III啟動程序執行A僅I和IIB僅II和IIIC僅I和IIID

I、II、III2.2.2進程的終止(撤銷):exit(status),kill(1)引起進程終止的事件：正常結束，異常結束和外界干預。(2)進程的終止過程：檢索PCB，判斷狀態，撤銷子進程，歸還資源，清空PCB。(3)進程的撤消，系統收回該進程所用的工作區，取消進程控制塊。Exit()、TerminatePorcess()父進程終止其子進程的原因（1）子進程使用了超過它所分配到的一些資源（2）分配給子進程的任務已不再需要（3）父進程退出，如果父進程終止，操作系統不允許子進程繼續。級聯終止Cascadingtermination。VMS。2.2.3進程的阻塞與喚醒sleep()和wakeup()(1)引起進程阻塞和喚醒的事件：請求系統服務，啟動某種操作，新數據尚未到達和無新工作可做。(2)進程阻塞過程：是正在執行的進程的一種主動行為。(3)進程喚醒過程：2.2.4進程的掛起與激活:交換進程(0號進程，sched)(1)進程的掛起；從內存置換到外存。(2)進程的激活過程：重新調入內存。2.3進程同步與互斥2.3.1進程同步的基本概念并發進程間的關系可以是無關的，也可以是有交往的。獨立進程或協作進程。

1、兩種制約關系：間接制約關系：互斥進程互斥是指當有若干個進程使用某一共享資源時，任何時刻最多只允許一個進程使用，而其他要使用該資源的進程必須等待，直到占用資源者釋放該資源。是進程間競爭共享資源的使用權，沒有固定的必然關系。利用公用信號量直接制約關系：同步進程同步是指并發進程之間存在一種制約關系，一個進程的執行依賴另一個進程的消息，當一個進程沒有得到另一個進程的消息時應等待，直到消息到達才被喚醒。涉及共享資源的并發進程之間有一種必然的依賴關系。利用私用信號量。作業6：進程間同步和互斥的含義各是什么？不允許兩個以上共享臨界資源的并發進程同時進入臨界區的現象稱為互斥。進程同步是指在異步環境下的一組并發進程因直接制約而相互發送消息導致的各個進程相互使用、相互等待，使得各個進程按一定的速度執行的現象稱為進程間的同步同步與互斥的混合問題：進程的互斥是進程間競爭共享資源的使用權，這種競爭沒有固定的必然關系；進程同步，涉及共享資源的并發進程之間有一種必然的依賴關系。

racecondition競爭條件：多個內核進程同時活動，會發生競爭條件。如打開文件的內核數據結構，內存分配的數據結構，維護進程列表及處理中斷處理程序的數據結構。非搶占內核式的系統中不會導致競爭條件，搶占內核的系統可能會導致競爭條件。搶占內核比非搶占內核更受歡迎。WindowsXP和Windows2000為非搶占式內核，傳統的Unix和Linux2.6以前的內核也是非搶占式的。Linux2.6以后，商用Unix、Solaris是搶占內核2、臨界資源：一次只允許一個進程使用的資源。打印機、磁帶機、消息緩沖隊列、變量、數組、緩沖區等。又稱獨享資源。3、臨界區：實現互斥的方法：軟件和硬件方法1965年Dijkstra(狄克斯特拉)提出的臨界段設計原則4、同步機制的規則：空閑讓進，忙則等待，有限等待和讓權等待。（在單處理機系統中是必須的，在多處理機系統中不是必須的）2010年27、進程P0和P1的共享變量定義及其初值為（A）Booleanflag[2];

Intturn=0;Flag[0]=false;flag[1]=false;若進程P0和P1訪問臨界資源的類C代碼實現如下：VoidP0(){while(true){flag[0]=true;turn=1;While(flag[1]&&turn==1);

臨界區；

Flag[0]=false;}VoidP1(){while(true){flag[1]=true;turn=0;While(flag[0]&&turn==0);

臨界區；

Flag[1]=false;}}則并發執行進程P0和P1時產生的情況是（D）A不能保證進程互斥進入臨界區，會出現“饑餓”現象B不能保證進程互斥進入臨界區，不會出現“饑餓”現象C能保證進程互斥進入臨界區，會出現“饑餓”現象D能保證進程互斥進入臨界區，不會出現“饑餓”現象實現同步的幾種方法1、禁止中斷：只適合單處理器環境，會出現餓死。2、TestAndSetLock指令：不可分的原子操作,可適用于多處理器環境。忙等待，可能會死鎖BooleanTestAndSet(booleanlocked){if(locked)returntrue;else{locked=true;returnfalse;}}TSL算法Enter_region:TSLREGISTER,LOCK復制樂到寄存器并將鎖設為1 CMPREGISTER,#0JNEenter_region若不是0,說明鎖已被設置，所以循環

RET返回調用者，進入了臨界區Leave_region: MOVELOCK,#0在鎖中存入0RET返回調用者3、Swap指令

booleanvoidSwap(boolean

a,booleanb){booleantemp;temp=b;b=a;a=temp;}Swap算法Do{key=TRUE;swap(&lock,&key);criticalsection;lock=FALSE;remaindersection;}while(TRUE);4、Dekker算法和Peterson算法：基于軟件的兩個進程間的通信。

Bakery算法，用于N個進程間的通信Peterson解法#defineFALSE0#defineTRUE1#defineN2;進程數量Intturn;現在輪到誰Intinterested[N];所有值初始化為0,即FALSE；Voidenter_region(intprocess);進程是0或1{intother;其他進程號

other=1-process;另一方進程

interested[process]=TRUE;表明所感興趣的

turn=process;設置標志

while(turn==process&&interested[other]==TRUE)；

}Voidleave_region(intprocess)進程：誰離開？

{interested[process]==FALSE;}表示離開臨界區Peterson算法中Pi的結構Do{flag[i]=TRUE;turn=j;while(flag[j]&&turn=j);

臨界區；

flag[i]=FALSE;

剩余區；

}while(TRUE);互斥-軟件的忙等待方法-1算法1intflag[2]={0,0}Cobegin voidP0(void) { while(1){

while(flag[1]==1); flag[0]=1; ……;//P0的臨界區代碼

flag[0]=0; …….;//P0的非臨界區代碼

} } voidP1(void) { while(1){

while(flag[0]==1); flag[1]=1; ……;//P1的臨界區代碼

flag[1]=0; …….;//P1的非臨界區代碼

} }Coend互斥-軟件的忙等待方法-2算法2intturn=0;Cobegin voidP0(void) { while(1){

while(turn!=0); ……;//P0的臨界區代碼

turn=1; …….;//P0的非臨界區代碼

} } voidP1(void) { while(1){

while(turn!=1

); ……;//P1的臨界區代碼

turn=0; …….;//P1的非臨界區代碼

} }Coend1.P0每小時進一次而P1每小時進入1000次2.若某進程發生意外永遠不能運行…..互斥-軟件的忙等待方法-3Peterson1981為了防止二進程為進入臨界區而無限期等待，又設置變量turn，表示不允許進入臨界區的編號，每個進程在先設置自己標志后再設置turn標志，不允許另一個進程進入，這時再同時檢測另一個進程狀態標志和不允許進入標志，這樣可以保證當二個進程同時要求進入臨界區時，只允許一個進程進入臨界區。僅適用于兩個進程互斥互斥-軟件的忙等待方法-3算法3Intflag[2]={0,0}Intturn=0;Cobegin voidP0(void) { while(1){

flag[0]=1; //P0申請進入臨界區

turn=1;

while(flag[1]==1&&turn==1);//等待獲準進入

……;//P0的臨界區代碼

flag[0]=0; //聲明退出臨界區

…….;//P0的非臨界區代碼

} } voidP1(void) { while(1){

flag[1]=1; //P1申請進入臨界區

turn=0; while(flag[0]==1&&turn==0);//等待獲準進入

……;//P0的臨界區代碼

flag[1]=0; //聲明退出臨界區

…….;//P1的非臨界區代碼

} }Coend互斥-硬件支持1-禁止中斷提高臨界區代碼執行中斷優先級這種方法在UNIX和WindowsNT中都使用，它是在單機系統中有效地實現互斥的一種方法。因為在傳統操作系統中，打斷進程對臨界區代碼的執行只有中斷請求、中斷被接受后，系統有可能還調用其它進程進入臨界區，并修改此全局數據庫。所以用提高臨界區中斷優先級方法就可以屏蔽了其它中斷，保證了臨界段的執行不被打斷，從而實現了互斥。禁止中斷舉例VoidPi(void){ while(1){ disable_interrupts; ……; //臨界區代碼

enable_interrupts; ……; //非臨界區代碼

}}在多處理機情況下，用提高臨界段代碼執行的中斷優先級方法是無法保證互斥的，因為在一個處理機上提高中斷優先級并不能阻止其它處理器上的中斷，所以必須采用其它方法。互斥-硬件支持2-特殊機器指令1Test-and-Set處理機指令對于同一主存塊訪問要求，即使兩個處理機同時提出，存儲控制邏輯也只能讓其中之一先訪問，但在一個處理機的兩個存儲周期間卻可以插入另一個處理機的存儲周期。現在用一條指令來完成檢測和修改兩個功能，這樣中斷和插入另一處理機的存儲周期均不可能，所以不會影響此公用變量數據的完整性。Test-and-Set的語義intTest_and_Set(inttarget){

inttemp; temp=target; target=1; returntemp;}Test-and-Set的應用//lock為被測試變量,初值為0,互斥進程Pi(i=1,2...n)調用TSvoidPi(void){ while(1){

while(Test_and_Set(lock)) ; .....; //Pi臨界區代碼

lock=0; //退出臨界區

.....; //Pi非臨界區代碼

}}互斥-硬件支持2-特殊機器指令2swap處理機指令,語義如下:voidswap(inta,intb){

inttemp; temp=a; a=b; b=temp;}

Swap的應用//lock為公用變量,初值為0(表臨界資源空閑)//keyi為進程Pi的對應變量,初值為0表示不要求進入臨界區voidPi(void){ while(1){

keyi=1;

while(keyi!=0)

swap(lock,keyi); .....; //Pi臨界區代碼

lock=0; //退出臨界區

.....; //Pi非臨界區代碼

}}2.3.2信號量機制

1、整型信號量：P、V操作

wait(s):whiles<=0donothing;s=s-1;信號量的值不可能取負值。

signal(s):s=s+1;又稱簡單信號量，二元信號量，二進制信號量，互斥鎖。缺點：忙等待方式busywaiting,自旋鎖（優點：不進行上下文切換，常用于多處理系統）2、記錄型信號量：

structsemaphore{

int:value;

structprocess*L;}s;wait(s):s.value=s.value-1;ifs.value<0thenblock(s.L);信號量的遞減和測試次序的互換，其值可取負值。

signal(s):s.value=s.value+1;ifs.value<=0thenwakeup(s.L);又稱計數信號量，資源信號量，用來控制m個進程訪問某一類n個臨界資源。作業7:記錄型信號量的物理含義例：設有n個進程共享一個程序段，對于如下兩種情況：（1）如果每次只允許一個進程進入該程序段。（2）如果每次最多允許m個進程（m<n）同時進入該程序段。試問：所采用的信號量初值是否相同？信號量值的變化范圍如何？2010年25、設與某資源相關聯的信號量初值為3，當前值為1，若M表示該資源的可用個數，N表示等待該資源的進程數，則M，N分別是（B）A

0,1B

1,0C

1,2D

2,02.3.3信號量的應用

1、實現對臨界資源的互斥

2、實現前趨關系例：設有六個進程P1、P2、P3、P4、P5、P6，它們有如圖所示的并發關系。試用P、V操作實現這些進程間的同步。P1P3P2P4P5P62.3.4管程機制(一般了解)

管程的定義管程的特性：模塊化、抽象數據類型、信息掩蔽。管程和進程的區別：2.4經典進程的同步問題2.4.1生產者和消費者問題：是相互合作進程關系的一種抽象，是有限緩沖區問題BoundedBuffer,常用來說明同步原語的能力。有多種變型,多種不同情況。同步進程之間存在著哪些同步關系:(1)所有進程間互斥訪問公用緩沖池:mutex=1(2)生產者速度快時，緩沖池滿，生產者等待。(先消費，后生產）:empty=n(3)消費者速度快時，緩沖池空，消費者等待。（先生產，后消費）:full=0注意：P、V操作的位置順序，一般先同步，后互斥。ProducerConsumerRepeatRepeat

生產一個消息;P(full);P(empty);P(mutex);P(mutex)取消息；

投放消息;V(mutex);V(mutex);V(empty);V(full);Untilfalse;Untilfalse1、一個生產者和一個消費者，利用一個緩沖區。例1：今有三個并發進程R、M、P，它們共享了一個可循環使用的緩沖區B，緩沖區B共有N個單元。進程R負責從輸入設備讀信息，每讀一個字符后，把它存入到緩沖區B的一個單元中。進程M負責處理讀入的字符，若發現讀入的字符中有空格符，則把它改成“，”。進程P負責把處理后的字符取出并打印輸出。當緩沖區單元中的字符被進程P取出后，則又可用來存放下一次讀入的字符。請用P、V操作為同步機制寫出它們能正確并發執行的程序。（南京大學1997年研究生試題）解：本題中，三個并發進程R、M、P共享了一個可循環使用的緩沖區B，進程R負責從輸入設備讀字符并存入緩沖單元中，進程M負責將讀入字符中的空格符改成“，”，進程P負責處理后字符的打印輸出。為此，應設置四個信號mutex、empty、full1、full2。mutex用于實現對緩沖區的互斥訪問，其初值為1。empty表示緩沖區中可用單元數目，其初值為N。full1表示已讀入字符個數，其初值為0。full2表示已處理字符個數，其初值為0。為描述方便起見，還應設置三個指針in、out1、out2。in指向下一個可用緩沖單元。out1指向下一個待處理字符。out2指向下一個待輸出字符。它們并發執行的同步機制描述如下：semaphoreempty=N;semaphorefull1=0;semaphorefull2=0;semaphoremutex=1;charbuffer[N];

intin=0,out1=0,out2=0;main(){cobeginR();M();P();

coend}R(){while(true){charx;

讀入一個字符到x;p(empty);p(mutex);buffer[in]=x;in=(in+1)%N;v(mutex);v(full1);}}M(){charx;while(true){p(full1);p(mutex);x=buffer[out1];if(x==“”){x=“,”;buffer[out1]=x;}out1=(out1+1)%N;v(mutex);v(full2);}}P(){charx;while(true){p(full2);p(mutex);x=buffer[out2];out2=(out2+1)%N;v(mutex);v(empty);

輸出字符x;}}例2：PA、PB、PC例3：一個數據采集系統，有數據采樣進程和數據處理進程及數據輸出進程。采樣進程把采到的數據送入Buf1中，由數據處理進程取出處理并于Buf2中，然后由數據輸出進程將其從Buf2中輸出，試給出三個進程同步的算法。2、一個生產者和一個消費者，利用n個緩沖區的問題：增加了互斥的關系3、多個生產者和多個消費者，利用n個緩沖區，每個消息只能被消費一次。書上的原問題。4、一類生產者和多類消費者。爸爸、兒子和女兒5、多類生產者和多類消費者。爸爸、媽媽、兒子和女兒以上情況，每個消費均只被消費一次。6、每個消息可被消費m次。以上討論的都是生產者和消費者之間的同步關系。7、生產者和生產者之間也存在同步關系。倉庫問題。倉庫變型8、歸結進程為一系列操作序列，在不同的操作之間尋找同步關系。

司機和售票員

南天

少林寺

考場

閱覽室2009年綜合應用題45、三個進程P1、P2、P3互斥使用一個包含N(N>0)個單元的緩沖區。P1每次用produce()生成一個正整數并用put()送入緩沖區某一空單元中；P2每次用getodd()從該緩沖區中取出一個奇數并用countodd()統計奇數個數；P3每次用geteven()從該緩沖區中取出一個偶數并counteven()統計偶數個數。請用信號量機制實現這三個進程的同步與互斥活動，并說明所定義信號量的含義。要求用偽代碼描述。答案：定義信號量S1控制P1與P2之間的同步；S2控制P1與P3之間的同步；empty控制生產者與消費者之間的同步；mutex控制進程間互斥使用緩沖區。程序如下：

Vars1=0,s2=0,empty=N,mutex=1;

ParbeginP1:beginX=produce();/*生成一個數*/P(empty);/*判斷緩沖區是否有空單元*/P(mutex);/*緩沖區是否被占用*/put(x);Ifx%2==0V(s2);/*如果是偶數，向P3發出信號*/elseV(s1);/*如果是奇數，向P2發出信號*/V(mutex);/*使用完緩沖區，釋放*/

P2：beginP(s1);/*收到P1發來的信號，已產生一個奇數*/P(mutex);/*緩沖區是否被占用*/

Getodd();

Countodd():=coutodd()+1;V(mutex);/*釋放緩沖區*/V(empty);/*向P1發信號，多出一個空單元*/End.

P3:beginP(s2);/*收到P1發來的信號，已產生一個偶數*/P(mutex);/*緩沖區是否被占用*/

Geteven();

Counteven():=counteven()+1;V(mutex);/*釋放緩沖區*/V(empty);/*向P1發信號，多出一個空單元*/End.Parend.2013年201447（8分）系統中有多個生產者進程和多個消費者進程，共享一個能存放1000件產品的環形緩沖區（初始為空）。當緩沖區未滿時，生產者進程可以放入其生產的一件產品，否則等待；當緩沖區未空時，消費者進程可以從緩沖區取走一件產品，否則等待。要求一個消費者進程從緩沖區連續取走10件產品后，其他消費者進程才可以取產品。請使用信號量的P、V(wait()、signal())操作實現進程間的互斥與同步，要求寫出完整的過程，并說明所用信號量的含義和初值。semaphoreempty=1000;空緩沖數semaphorefull=0;非空緩沖數semaphoremutex1=1;實現生產者之間的互斥semaphoremutex2=1;實現消費者之間的互斥intin=0;intout=0;生產者進程

while(TRUE){produce;p(empty);p(mutex1)putanitemintobuf[in];in=(in+1)modn;v(mutex1);v(full);}消費者進程

while(TRUE){p(mutex2);for(inti=0;i<10;i++){p(full);getanitemfrombuf[out];

out=(out+1)modn;v(empty);}v(mutex2)consume;}2.4.2讀者和寫者問題：一直用來測試幾乎所有新的同步原語。多個用戶共享數據庫系統的建模問題。有多種不同的策略，都與優先級有關。

1、讀者優先：第一讀者-寫者問題，寫者可能饑餓。

2、排隊策略或先來先服務

3、寫者優先：第二讀者-寫者問題，讀者可能饑餓。第一和第二讀者-作者問題是并行計算的模擬。這兩個問題描述的是有許多線程必須同時訪問共享的內存地址，有的要讀，有的要寫。在通常的限制條件下，在一個進程正在寫入的時候，其它的進程不能讀，也不能寫那個共享的內存塊。

4、某個進程即是寫者又是讀者的問題例：設有P1,P2,P3三個進程共享某一資源F，P1對F只讀不寫，P2對F只寫不讀，P3對F先讀后寫。當一個進程寫F時，其他進程對F不能進行讀寫，但多個進程同時讀F是允許的。試用P、V操作正確實現P1,P2,P3的同步互斥。要求：（1）正常運行時不產生死鎖（2）使用F的并發度要高。（北京大學1996年研究生試題）解：本題實際上是一個讀者和寫者問題，P1是一個讀者，P2是一個寫者，為了使F的并發度較高，將P3先看成讀者，當其完成讀操作后，再將其看成寫者。定義如下變量：

intreadcount=0;semaphorermutex=1,mutex=1;P1(){While(1){P(rmutex);If(readcount==0)P(mutex);

Readcount++;V(rmutex);

讀F；

P（rmutex）;

Readcount--;If(readcount==0)V(mutex);V(rmutex);}}P2(){While(1){P(mutex);

寫F；

V（mutex）;}}P3(){While(1){P(rmutex);If(readcount==0)P(mutex);

Readcount++;V(rmutex);

讀F；

P(rmutex);

Readcount--;If(readcount==0)V(mutex);V(rmutex);P(mutex);

寫F；

V\(mutex);}}2.4.3哲學家進餐問題：在1971年，著名的計算機科學家艾茲格·迪科斯徹（Edsger

Wybe

Dijkstra）提出了一個同步問題，即假設有五臺計算機都試圖訪問五份共享的磁帶驅動器。稍后，這個問題被托尼·霍爾重新表述為哲學家就餐問題。這個問題可以用來解釋死鎖和資源耗盡。

是一個并發控制問題，在多個進程之間分配多個資源且不會出現死鎖和饑餓的問題。方法：

1、同時允許四個哲學家提出進餐要求

2、同時去拿起兩邊的筷子

3、使用非對稱解決方法，奇數號哲學家先拿左邊的筷子，偶數號哲學家先拿右邊的筷子注意：沒有死鎖的解決方案并不能消除餓死的可能性。2.4.4理發師嗜睡問題“熟睡的理發師問題”是用來描述多個操作系統進程之間的，一個經典的進程之間的通信及同步問題。“一個熟睡的理發師問題”一個理發店由一個有N張椅子的等候室和一個放有一張理發椅的理發室組成。若沒有要理發的顧客，則理發師就去睡覺，若一個顧客走進理發店且所有的椅子都被占用了，則該顧客就離開理發店，若理發師正在為人理發，則該顧客就找一張空椅子坐下等待，若理發師在睡覺，則顧客就喚醒他。試用信號量設計一個協調理發師和顧客的程序。（西安電子科技大學2000年研究生試題）count

=

0

barber=0

mutex=1

seats=N

//所有的椅子數量

理發師（線程/進程）

While(true){

//持續不斷地循環

P（count）

//試圖為一位顧客服務，如果沒有他就睡覺

P（mutex）

//這時他被叫醒，要修改空椅子的數量

seats++

//一張椅子空了出來

V（barber）

//理發師準備理發

V（mutex）

//我們不想再死鎖在椅子上

理發

//這時理發師在理發

｝

顧客（線程/進程）

while(true)

｛

//持續不斷地循環

P（mutex）

//想坐到一張椅子上

if

(seats>0)

{

//如果還有空著的椅子的話

seats--

//顧客坐到一張椅子上了

V（count）

//通知理發師，有一位顧客來了

V（mutex）

//不會死鎖到椅子上

P（barber）

//該這位顧客理發了，如果他還在忙，那么他就等著

有顧客在理發

//這時顧客在理發

}else

｛

//沒有空著的椅子

V（mutex）

//不要忘記釋放被鎖定的椅子

//顧客沒有理發就走了

｝

｝

2011年綜合應用題

（北京大學2000）45、(8分)某銀行提供1個服務窗口和10個供顧客等待的座位。顧客到達銀行時，若有空座位，則到取號機上領取一個號，等待叫號。取號機每次僅允許一位顧客使用。當營業員空閑時，通過叫號選取一位顧客，并為其服務。顧客和營業員的活動過程描述如下：Cobegin{process顧客_i{

從取號機獲取一個號碼；等待叫號；獲取服務；

}process營業員

{while(TRUE){

叫號；為客戶服務

}}}coend請添加必要的信號量和P、V(或wait()、signal())操作，實現上述過程中的互斥與同步。要求寫出完整的過程，說明信號量的含義并賦值。解：Semaphoremutex=1;互斥使用取號機Semaphoreempty=10;空座位的數量Semaphorefull=0;已占座位的數量Semaphoreservice=0;等待叫號Cobegin{process顧客I{p(empty)p(mutex)

從取號機獲取一個號碼；

v(mutex)V(full)p(service)等待叫號；

獲取服務；

}

process營業員

{while(TRUE){p(full)v(empty)v(service)叫號；為客戶服務

}}}coend算法二semaphoreseats=10;有10個座位的資源信號量mutex=1,取號機互斥信號量havecustom=0;顧客與營業員同步，無顧客時營業員休息process顧客

{p(seats);等空位

p(mutex);申請使用取號機從取號機上取號；

v(mutex);取號完畢

v(havecustom);通知營業員有新顧客到來等待營業員叫號；

v(seats);離開座位接受服務

}Process營業員

{while(true){p(havecustom);沒有顧客則休息叫號；為顧客服務；

}}算法三Semaphoremax=n+1;表示理發店可以容納的總人數Semaphorechair=n;空閑的椅子Semaphorebarber=1;表示理發椅空閑Semaphorefinished=0;表示一次理發結束Semaphoreready=0;表示客人準備就緒Customer:while(true){p(max);p(chair);p(barber);

去理發椅理發；

v(chair);v(ready);

理發；

p(finished);v(max);}Barber:while(true){p(ready);

理發；

v(finished);v(barber);}算法四解：本題中，顧客進程和理發師進程之間存在著多種同步關系：（1）只有在理發椅空閑時，顧客才能坐到理發椅上等待理發師理發，否則顧客便必須等待；只有當理發椅上有顧客時，理發師才可以開始理發，否則他也必須等待。這種同步關系類似于單緩沖（理發椅）的生產者和消費者問題中的同步關系，故可以通過信號量empty(初值為1)和full(初值為0)來控制。（2）理發師為顧客理發時，顧客必須等待理發的完成，并在理發完成后由理發師喚醒他，這可單獨使用一個信號量cut來控制，初值為0。（3）顧客理完發后必須向理發師付費，并等理發師收費后顧客才能離開；而理發師則需等待顧客付費，并在收費后喚醒顧客以允許他離開，這可分別通過兩個信號量payment和receipt來控制，初值都為0。（4）等候室中的N張沙發是顧客進程競爭的資源，故還需為它們設置了一個資源信號量sofa，初值為n（5）為了控制顧客的人數，使顧客能在所有的沙發都被占用時離開理發店，還必須設置一個整型變量count來對理發店中的顧客進行計數，該變量將被多個顧客進程互斥地訪問并修改，這可通過一個互斥信號量mutex來實現，初值為1Guestbeginwait(mutex);if(count>N)thenbeginsignal(muetx);

離開理發店;endelsebegin

count=count+1;if(count>1)thenbeginwait(sofa);

在沙發中就座;wait(empty);

從沙發上起來;signal(sofa);endelse/*count=1*/wait(empty);

在理發椅上就座;signal(full);wait(cut);理發；付費；

signal(payment);wait(receipt);

從理發椅上起來;signal(empty);wait(mutex);count=count-1;signal(mutex);

離開理發店;endendbarber:beginrepeatwait(full);

替顧客理發;signal(cut);wait(payment);

收費;signal(receipt);untilfalse;endparendend2.4.5“吸煙者”問題三個煙鬼的問題。這也是計算機領域的并發問題，最早是1971年S.S.Patil講述的。假設一個系統有3個吸煙者（smoker）進程和一個供貨商（Agent）進程。每個吸煙者依次輪流地制造香煙并吸掉它。但是，制造一支香煙需要3種材料—煙、紙、火柴。一個吸煙者進程有紙，另一個有煙，第三個有火柴。供貨商進程可以無限地提供這3種材料。供貨商將這這兩種材料一起放在桌上，持有另一種材料的吸煙者即可制造一支香煙并吸掉它。當此吸煙者抽香煙時，它發出一個信號通知供貨商進程，供貨商馬上給出另外兩種材料，如此循環往復。試編寫一個程序使供貨商和吸煙者同步執行。解法：semaphoresmoker[3]＝0;三個吸煙者semaphorematerial[3]＝0;三種原料,第i吸煙者，擁有第i材料，還需要i+1和i+2號材料semaphoreagent＝1;供應商intturn=0;輪到誰Main()Cobegin{AgentWhile(1){P(agent);

放原料；

V(smoker[turn]);V(material[(turn+1)%3]);V(material[(turn+2)%3]);turn=(turn+1)%3}Smoker_iWhile(1){P(smoker[i]);P(material[(i+1)%3]);P(material[(i+2)%3]);

制作香煙；吸煙；

V(agent);}}coend;這個問題是想模擬一個軟件程序中的四個角色，只使用了一部分同步前提條件。在PATIL的講解中，只有一個同步前提條件是：信號標（semaphore），四個程序都不允許有條件地“跳轉”，只能有一種由信號標操作提供的有條件的“等待”。觀點

PATIL的觀點是想證明Edsger

Dijstra的信號標方法作用有限。他用“三個煙鬼的問題”來證明這一點，即這種情況下信號標不能解決問題。但是，PATIL為自己的辯解添加了兩個限制條件：

1、

代碼不能修改。

2、

解決方案不能使用有條件的語句或使用信號標數組。如果加上這兩個限制條件，三個煙鬼的問題沒有辦法解決了。Downey曾其撰寫的《信號標的小冊子》里表示，第一個限制條件是有意義的。因為如果代碼代表的是一個操作系統，每來一個新的應用程序都要修改它不但不合理，也是不可能的。但是，就像DavidParnas指出的那樣，第二個限制條件讓重大的問題無法解決。使用條件語句cobegin經銷商煙草擁有者紙擁有者火柴擁有者beginbegin

begin

beginp(s);p(Sad);p(Sbd);p(Scd);放原料；取紙和火柴；取煙草和火柴；取紙和煙草；if(紙和火柴)v(s);v(s);v(s);v(Sad);吸煙；吸煙；吸煙；elseendend

endif(煙草和火柴)v(Sbd);elsev(Scd);end變型1抽煙問題：有一個煙草代理和三個抽煙者。抽煙者若要抽煙，必須具有煙葉、煙紙和火柴。三個抽煙者中，一人缺煙葉、一人缺煙紙、一人缺火柴。煙草代理會源源不斷地分別供應煙葉、煙紙和火柴，并將它們放在桌上。如果放的是煙葉，則缺煙葉的抽煙者拾起煙葉，制作香煙，然后抽煙；其他類推。試用信號量同步煙草代理和三個抽煙者。解法：semaphoresmoker[3]＝0;三個吸煙者semaphorematerial[3]＝0;三種原料semaphoreagent＝1;供應商intturn=0;輪到誰AgentWhile(1){P(agent);

放原料；

V(smoker[turn]);V(material[(turn+1)%3]);

制作香煙；吸煙；

turn=(turn+1)%3}Smoker_iWhile(1){P(smoker[i]);P(material[(i+1)%3]);

制作香煙；吸煙；

V(agent);}變型2有一間酒吧里有3個音樂愛好者隊