操作系統(tǒng)OS02進程管理課件

1第二章進程管理重點：進程的定義、進程控制的基本概念。進程PCB的基本結(jié)構(gòu)，作用及進程的狀態(tài)轉(zhuǎn)換。進程同步與互斥的基本概念和解決方法。幾個經(jīng)典的進程同步與互斥問題及算法。線程的基本概念及狀態(tài)。難點：進程的同步與互斥1第二章進程管理重點：2第二章進程管理主要內(nèi)容：2.1進程的基本概念2.2進程控制2.3進程同步2.4經(jīng)典進程的同步問題2.5管程機制2.6進程通信2.7線程2第二章進程管理主要內(nèi)容：32.1.進程的基本概念2.1.1程序的順序執(zhí)行及其特征2.1.2前趨圖2.1.3程序的并發(fā)執(zhí)行及其特征2.1.4進程的特征與狀態(tài)2.1.5進程控制塊32.1.進程的基本概念2.1.1程序的順序執(zhí)行及其特征42.1.1

程序的順序執(zhí)行及特征1、程序的順序執(zhí)行

例1：數(shù)據(jù)計算時要經(jīng)過I:輸入操作C:計算操作P:打印操作:

例2：如下三條語句的執(zhí)行

S1:a:=x+y;S2:b:=a-5;S3:c:=b+1;2、特征順序性、封閉性、可再現(xiàn)性I1C1P1I2C2P2語句S1語句S2語句S342.1.1程序的順序執(zhí)行及特征1、程序的順序執(zhí)行I1C152.1.2

前趨圖1、前趨圖(PrecedenceGraph)一個有向無循環(huán)圖描述進程之間執(zhí)行的前后關系2、前趨關系“”={(Pi,Pj)|PimustcompletebeforePjmaystart}如果：(Pi,Pj)∈

，也可以寫成：PiPj則稱：Pi是Pj的直接前趨,Pj是Pi的直接后繼初始結(jié)點：沒有前趨終止結(jié)點：沒有后繼每個結(jié)點還具有一個權(quán)或重量(Weight)，表示該結(jié)點的程序量或執(zhí)行時間。P1P2P3P1P2P3√×52.1.2前趨圖1、前趨圖(PrecedenceGra6其前趨關系表示為：P={P1，P2，P3，P4，P5，P6，P7}→={（P1,P2）,（P1,P3）,（P1,P4）,（P2,P5）,（P3,P5）,（P4,P6）,（P5,P7）,（P6,P7）}P1P4P3P2P6P5P7具有7個結(jié)點的前驅(qū)圖6其前趨關系表示為：P1P4P3P2P6P5P7具有7個結(jié)點72.1.3

程序的并發(fā)執(zhí)行及其特征I1C1P1I2C2P2I3C3P3I4C4P4輸入程序計算程序打印程序1、在對一批程序進行處理時，可以并發(fā)執(zhí)行。例1：輸入、計算、打印三個程序?qū)σ慌鳂I(yè)進行處理時存在前趨關系：前驅(qū)關系：Ii→Ci，Ii→Ii+1,Ci→Pi,Ci→Ci+1，Pi→Pi+172.1.3程序的并發(fā)執(zhí)行及其特征I1C1P1I2C2P282.1.3程序的并發(fā)執(zhí)行及其特征例2：對于下述四條語句的程序段：S1：a:=x+2;S2：b:=y+4;S3：c:=a+b;S4：d:=c+b;S2S1S3S4前驅(qū)關系82.1.3程序的并發(fā)執(zhí)行及其特征例2：對于下述四條語句的9又如：三個程序的執(zhí)行順序如圖：

P1：a:=1P2：x:=a+1P3：y:=a+1

2.1.3程序的并發(fā)執(zhí)行及其特征P1P2P3前驅(qū)關系9又如：三個程序的執(zhí)行順序如圖：2.1.3程序的并發(fā)執(zhí)行及10程序并發(fā)執(zhí)行條件（Bernstein條件）將任一語句劃分為兩個變量的集合R(Si)和W(Si):

讀集R(Si)={a1，a2，……，am}

寫集W(Si)={b1，b2，……，bn}如對語句S1和S2有：

R(S1)∩W(S2)={Ф} W(S1)∩R(S2)={Φ} W(S1)∩W(S2)={Φ}成立，則語句S1和S2可并發(fā)執(zhí)行。10程序并發(fā)執(zhí)行條件（Bernstein條件）將任一語句劃分11程序并發(fā)執(zhí)行條件（Bernstein條件）例1．

語句c=a–b和w=c+1 R（c=a–b）={a,b} W（c=a–b）={c} R（w=c+1）={c} W（w=c+1）={w} R（w=c+1）∩W（c=a–b）={c}語句c=a–b和w=c+1不能并發(fā)執(zhí)行。11程序并發(fā)執(zhí)行條件（Bernstein條件）例1．

語句122、程序并發(fā)執(zhí)行時的特征間斷(異步)性：“執(zhí)行—暫?！獔?zhí)行”，一個程序可能走到中途停下來，失去原有的時序關系。失去封閉性：共享資源，受其他程序的控制邏輯的影響。如：一個程序?qū)懙酱鎯ζ髦械臄?shù)據(jù)可能被另一個程序修改，失去原有的不變特征。不可再現(xiàn)性：失去封閉性－>失去可再現(xiàn)性；外界環(huán)境在程序的兩次執(zhí)行期間發(fā)生變化，失去原有的可重復特征。122、程序并發(fā)執(zhí)行時的特征間斷(異步)性：“執(zhí)行—暫?！獔?zhí)13程序并發(fā)執(zhí)行時的不可再現(xiàn)性

例如:有兩個循環(huán)程序A和B，共享一個變量N。程序A每執(zhí)行一次時，都要做N:=N+1;程序B每執(zhí)行一次時，都要執(zhí)行print(N),然后將N置成0。程序A和B以不同的速度運行?？赡艹霈F(xiàn)的情況如下(某時刻變量N的值為n)：1、N:=N+1在print(N)和N:=0之前，2、N:=N+1在print(N)和N:=0之后，3、N:=N+1在print(N)和N:=0之間，得到的N值為n+1,n+1,0得到的N值為n,0,1得到的N值為n,n+1,013程序并發(fā)執(zhí)行時的不可再現(xiàn)性例如:有兩個循環(huán)程序A142.1.4進程的特征與狀態(tài)進程的特征與定義進程的三種基本狀態(tài)掛起狀態(tài)創(chuàng)建狀態(tài)和終止狀態(tài)142.1.4進程的特征與狀態(tài)進程的特征與定義15進程特征結(jié)構(gòu)特性(PCB-ProcessControlBlock)進程實體＝程序段＋相關的數(shù)據(jù)段＋PCB動態(tài)性由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，由撤銷而消亡并發(fā)性獨立性獨立運行、獨立分配資源、獨立接受調(diào)度異步性15進程特征結(jié)構(gòu)特性(PCB-ProcessControl16進程定義進程的典型定義：（1）進程是程序的一次執(zhí)行（2）進程是一個程序及其數(shù)據(jù)在處理機上順序執(zhí)行時所發(fā)生的活動（3）進程是程序在一個數(shù)據(jù)集合上運行的過程，它是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。傳統(tǒng)OS中進程定義：進程是進程實體的運行過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。16進程定義進程的典型定義：17進程與程序的區(qū)別：（如同“演出”與“劇本”）進程是動態(tài)的，程序是靜態(tài)的：程序是有序代碼的集合；進程是程序的執(zhí)行。進程更能真實地描述并發(fā)執(zhí)行，可以揭示OS的內(nèi)部特征，而程序不能。進程是暫時的，程序是永久的：進程是一個狀態(tài)變化的過程，程序可長久保存。進程與程序的組成不同：進程的組成包括程序、數(shù)據(jù)和進程控制塊（即進程狀態(tài)信息）；程序僅是代碼的有序集合。進程與程序的對應關系：通過多次執(zhí)行，一個程序可對應多個進程；通過調(diào)用關系，一個進程可涉及到多個程序的執(zhí)行。進程具有創(chuàng)建其他進程的功能，父進程創(chuàng)建子進程而形成進程樹，而程序不能。17進程與程序的區(qū)別：（如同“演出”與“劇本”）進程是動態(tài)的18進程的基本狀態(tài)三種基本狀態(tài)：就緒狀態(tài)執(zhí)行狀態(tài)阻塞狀態(tài)進程狀態(tài)轉(zhuǎn)換

阻塞狀態(tài)就緒狀態(tài)

執(zhí)行狀態(tài)調(diào)度I/O請求進程喚醒時間片到18進程的基本狀態(tài)三種基本狀態(tài)：進程狀態(tài)轉(zhuǎn)換阻塞就緒執(zhí)行191920掛起狀態(tài)引入掛起狀態(tài)的原因：終端用戶請求父進程請求:考查、修改或協(xié)調(diào)各子進程時；負荷調(diào)節(jié)的需要：緩和內(nèi)存緊張的情況；操作系統(tǒng)的需要：改善系統(tǒng)運行性能，調(diào)節(jié)負荷；增加的狀態(tài)：掛起狀態(tài)（靜止狀態(tài)）非掛起狀態(tài)（活動狀態(tài)）20掛起狀態(tài)引入掛起狀態(tài)的原因：21具有掛起狀態(tài)的進程狀態(tài)圖活動阻塞執(zhí)行狀態(tài)活動就緒靜止就緒靜止阻塞調(diào)度喚醒I/O請求激活激活掛起掛起掛起喚醒21具有掛起狀態(tài)的進程狀態(tài)圖執(zhí)行活動靜止靜止調(diào)度喚醒I/O請22創(chuàng)建狀態(tài)和終止狀態(tài)創(chuàng)建狀態(tài)創(chuàng)建一個進程過程：為一個新進程創(chuàng)建PCB，并填寫必要的管理信息把該進程轉(zhuǎn)入就緒狀態(tài)并插入就緒隊列之中引入創(chuàng)建狀態(tài)，為了保證進程的調(diào)度必須在創(chuàng)建工作完成后進行，以確保對進程控制塊操作的完整性。

22創(chuàng)建狀態(tài)和終止狀態(tài)創(chuàng)建狀態(tài)23創(chuàng)建狀態(tài)和終止狀態(tài)終止狀態(tài)進程終止過程首先，等待操作系統(tǒng)進行善后處理然后，將其PCB清零，并將PCB空間返還系統(tǒng)當一個進程到達了自然結(jié)束點，或是出現(xiàn)了無法克服的錯誤，或是被操作系統(tǒng)所終結(jié)，或是被其它有終止權(quán)的進程所終結(jié)，它將進入終止狀態(tài)。23創(chuàng)建狀態(tài)和終止狀態(tài)終止狀態(tài)24創(chuàng)建狀態(tài)和終止狀態(tài)時間片完許可釋放進程調(diào)度I/O完成I/O請求創(chuàng)建終止就緒執(zhí)行阻塞進程的五種基本狀態(tài)及轉(zhuǎn)換24創(chuàng)建狀態(tài)和終止狀態(tài)時間片完創(chuàng)建終止就緒執(zhí)行阻塞進程的五種25創(chuàng)建狀態(tài)和終止狀態(tài)（續(xù)）激活許可掛起調(diào)度掛起釋放釋放I/O請求激活掛起靜止就緒靜止阻塞活動就緒執(zhí)行活動阻塞創(chuàng)建終止許可具有創(chuàng)建、終止和掛起狀態(tài)的進程狀態(tài)圖25創(chuàng)建狀態(tài)和終止狀態(tài)（續(xù)）262.1.5進程控制塊（PCB）PCB的作用PCB中的信息PCB的組織方式262.1.5進程控制塊（PCB）PCB的作用271.PCB的作用PCB中記錄了操作系統(tǒng)所需的、用于描述進程的當前情況以及控制進程運行的全部信息。是進程存在的唯一標志。作用：使一個在多道程序環(huán)境下不能獨立運行的程序，成為一個能獨立運行的基本單位，一個能與其他進程并發(fā)執(zhí)行的進程。PCB常駐內(nèi)存，系統(tǒng)將所有的PCB組成若干鏈表或隊列，存放在OS中專門開辟的PCB區(qū)內(nèi)271.PCB的作用PCB中記錄了操作系統(tǒng)所需的、用于描述進28

2.PCB中的信息進程標識符：唯一的標識一個進程內(nèi)部標識（方便系統(tǒng)使用）外部標識（由創(chuàng)建者提供，由字母數(shù)字組成）處理機狀態(tài)：由CPU的各種寄存器中的內(nèi)容組成通用寄存器；指令計數(shù)器

；程序狀態(tài)字PSW；用戶棧指針進程控制信息pidstatusschedualcontrol處理機狀態(tài)信息進程標識符進程調(diào)度信息282.PCB中的信息進程控制信息pidstatu29進程調(diào)度信息：

進程狀態(tài)；進程優(yōu)先級；其它信息；等待事件（阻塞原因）進程控制信息：

程序和數(shù)據(jù)的地址；同步和通信機制；資源清單；鏈接指針；進程控制信息pidstatusschedualcontrol處理機狀態(tài)信息進程標識符進程調(diào)度信息2.PCB中的信息29進程調(diào)度信息：303.PCB的組織方式PCB數(shù)目一個系統(tǒng)中的PCB數(shù)目可為數(shù)十個、數(shù)百個甚至數(shù)千個鏈接方式把具有同一狀態(tài)的PCB，用其鏈接字鏈接成一個隊列就緒隊列、若干個阻塞隊列、空隊列索引方式系統(tǒng)根據(jù)所有進程的狀態(tài)建立相應的索引表就緒索引表、阻塞索引表等，索引表在內(nèi)存的首地址記錄在內(nèi)存的一些專用單元中。303.PCB的組織方式PCB數(shù)目313、PCB的組織方式（續(xù)）執(zhí)行指針就緒隊列指針阻塞隊列指針空閑隊列指針PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB911……PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9……執(zhí)行指針就緒隊列指針阻塞隊列指針3572496PCB鏈接隊列示意圖按索引方式組織PCB就緒索引表阻塞索引表313、PCB的組織方式（續(xù)）執(zhí)行指針就緒隊列指針阻塞隊列32思考題1．如果系統(tǒng)中有N個進程，運行的進程最多幾個，最少幾個；就緒進程最多幾個最少幾個；等待進程最多幾個，最少幾個？[解答]：在單處理機系統(tǒng)中，處于運行狀態(tài)的進程最多為1個，最少為0個；處于就緒進程最多為N-1個，最少為0個；處于等待的進程最多為N個，最少為0個。32思考題1．如果系統(tǒng)中有N個進程，運行的進程最多幾個，最少33思考題2.有沒有這樣的狀態(tài)轉(zhuǎn)換，為什么？ 等待—運行；就緒—等待33思考題2.有沒有這樣的狀態(tài)轉(zhuǎn)換，為什么？342.2

進程控制主要內(nèi)容：進程創(chuàng)建進程撤消進程阻塞進程喚醒進程掛起與激活342.2

進程控制主要內(nèi)容：352.2

進程控制進程控制是對系統(tǒng)中所有進程從產(chǎn)生、存在到消亡的全過程實行有效的管理和控制。

進程控制一般是由操作系統(tǒng)的內(nèi)核來實現(xiàn)，內(nèi)核在執(zhí)行操作時，往往是通過執(zhí)行各種原語操作來實現(xiàn)的。

無——有——消亡

運行——等待就緒———等待等待喚醒創(chuàng)建撤消狀態(tài)轉(zhuǎn)換352.2

進程控制進程控制是對系統(tǒng)中所有進程從產(chǎn)生、存在36內(nèi)核：加在硬件上的第一層軟件，通過執(zhí)行各種原語操作來實現(xiàn)各種控制和管理功能，具有創(chuàng)建進程、撤消進程、進程通信、資源管理的功能。原語(primitive)：由若干條指令構(gòu)成的“原子操作(atomicoperation)”過程，作為一個整體而不可分割，要么全都完成，要么全都不做。原子操作在管態(tài)下執(zhí)行，常駐內(nèi)存。原語的作用：實現(xiàn)進程的通信和控制，系統(tǒng)對進程的控制如不使用原語，就會造成其狀態(tài)的不確定性，從而達不到進程控制的目的。36內(nèi)核：加在硬件上的第一層軟件，通過執(zhí)行各種原語操作來實現(xiàn)37處理機運行時的兩種狀態(tài)用戶態(tài)（目態(tài)）時不可直接訪問受保護的OS代碼。核心態(tài)（管態(tài)）時執(zhí)行OS代碼，可以訪問全部進程空間。裸機（硬件）內(nèi)核客戶進程客戶進程進程服務器存儲器服務器文件服務器請求應答核心態(tài)用戶態(tài)37處理機運行時的兩種狀態(tài)用戶態(tài)（目態(tài)）時不可直接訪問受保護38進程樹PDPBPEPCPFPAPIPHPGPJPKPLPMPN2.2.1進程的創(chuàng)建1、進程圖是用于描述一個進程的家族關系的有向樹。結(jié)點代表進程有向邊代表父子關系進程之間的關系：父、子進程與祖先進程：PCB中設置家族關系表項繼承歸還資源：“父”創(chuàng)建“子”、“父”撤消“子”38進程樹PDPBPEPCPFPAPIPHPGPJ392、引起創(chuàng)建（create）進程的事件用戶登錄（分時系統(tǒng)）作業(yè)調(diào)度（批處理系統(tǒng)）提供服務（操作系統(tǒng)提供服務）應用請求（由現(xiàn)有進程派生）392、引起創(chuàng)建（create）進程的事件用戶登錄（分時系統(tǒng)403、進程的創(chuàng)建(Creat()原語)過程：申請空白PCB、為新進程分配資源、初始化PCB、插入就緒進程隊列HD就緒隊列指針PCB15PCB2PCB3PCB4PCB513PCB60PCB7PCB89PCB912PCB10PCB11PCB1225PCB136……空PCB隊列指針RAM程序+數(shù)據(jù)PCB80PCB68403、進程的創(chuàng)建(Creat()原語)過程：申請空白PCB412.2.2進程的終止1、引起進程終止事件正常結(jié)束（Holt指令，Logsoff）異常結(jié)束越界錯誤、保護錯、非法指令、特權(quán)指令錯、運行超時、等待超時、算術(shù)運算錯、I/O故障外界干預操作員或操作系統(tǒng)干預父進程請求父進程終止412.2.2進程的終止1、引起進程終止事件422、進程的終止過程根據(jù)被終止的進程的標識符，檢索出該進程的PCB，讀出該進程的狀態(tài)。若該進程處于執(zhí)行狀態(tài)，立即終止其執(zhí)行，置調(diào)度方式為真，指示該進程終止后應重新進行調(diào)度。若該進程有子孫進程，終止其所有子孫進程。將被終止進程所擁有的全部資源，或者歸還給其父進程，或者歸還給系統(tǒng)。將被終止進程的PCB從所在隊列中刪除。422、進程的終止過程根據(jù)被終止的進程的標識符，檢索出該進程432.2.3進程的阻塞與喚醒1、引起進程阻塞和喚醒的事件請求系統(tǒng)服務啟動某種操作新數(shù)據(jù)尚未到達無新工作可做432.2.3進程的阻塞與喚醒1、引起進程阻塞和喚醒的事件442、進程阻塞的過程進程調(diào)用阻塞原語block()把自己阻塞，阻塞是進程自身的一種主動性為。先停止進程的執(zhí)行，將PCB中的現(xiàn)行狀態(tài)由執(zhí)行改為阻塞。并將其PCB插入具有相同事件的阻塞隊列。轉(zhuǎn)調(diào)度程序進行重新調(diào)度，將處理機分配給另一就緒進程，保留被阻塞進程的處理機狀態(tài)。442、進程阻塞的過程進程調(diào)用阻塞原語block()把自己阻453、進程喚醒的過程期待事件出現(xiàn)，相關進程調(diào)用喚醒原語wakeup()把被阻塞的進程從等待該事件的阻塞隊列中移出。將其PCB中的現(xiàn)行狀態(tài)由阻塞改為就緒。將該PCB插入就緒隊列。阻塞與喚醒要匹配使用，以免造成“永久阻塞”block()和wakeup()要成對出現(xiàn)453、進程喚醒的過程期待事件出現(xiàn)，相關進程調(diào)用喚醒原語wa462.2.4進程的掛起與激活調(diào)用掛起原語suspend()檢查被掛起進程的狀態(tài)，處于活動就緒，便改為靜止就緒；處于活動阻塞，便改為靜止阻塞；若進程正在執(zhí)行，則轉(zhuǎn)向調(diào)度程序。調(diào)用激活原語active()若進程在外存則將其調(diào)入內(nèi)存，檢查進程的狀態(tài)，處于靜止就緒，便改為活動就緒；處于靜止阻塞，便改為活動阻塞。462.2.4進程的掛起與激活調(diào)用掛起原語suspend(472.3進程同步進程同步的主要任務：對多個相關進程在執(zhí)行次序上進行協(xié)調(diào)，使并發(fā)執(zhí)行的諸進程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。主要內(nèi)容：2.3.1進程同步的基本概念2.3.2信號量機制2.3.3信號量的應用472.3進程同步進程同步的主要任務：對多個相關進程在執(zhí)行482.3.1進程同步的基本概念1、兩種形式的制約關系：間接相互制約關系進程互斥：一個進程正在訪問臨界資源，另一個要訪問該資源的進程必須等待。直接相互制約關系進程同步：合作完成同一個任務的多個進程，在執(zhí)行速度或某些時序點上必須相互協(xié)調(diào)的合作關系。前進示例示例482.3.1進程同步的基本概念1、兩種形式的制約關系：前49民航售票系統(tǒng)主機A窗口B窗口C窗口D窗口每個進程執(zhí)行的操作：設x表示某航班的票數(shù)。

……ifx>0thenx:=x-1;……在某時刻x=1，有a、b兩人分別去A、B窗口買票，分析售票情況：時間片到ab49民航售票系統(tǒng)主機A窗口B窗口C窗口D窗口每個進程執(zhí)行的操50進程同步舉例：司機－售票員司機：P1while(true){

啟動車輛；正常運行；到站停車；

}售票員：P2while(true){

關門；售票；開門；

}正確運行過程While(true){（司機）啟動車輛；（售票員）關門；（司機）正常運行；（售票員）售票；（司機）到站停車；（售票員）開門；}50進程同步舉例：司機：P1售票員：P2正確運行過程512、臨界資源臨界資源：一次僅允許一個進程訪問的資源稱為臨界資源（互斥資源或共享變量）。物理設備：打印機，掃描儀例1：兩個進程A、B共享一臺打印機，若不加以控制，兩個進程的輸出結(jié)果可能交織在一起，很難區(qū)分。軟件資源：全局變量，隊列等例2：飛機訂票問題設：x代表某航班機座號，p1和p2兩個售票進程，售票工作是對全局變量x加1。512、臨界資源臨界資源：一次僅允許一個進程訪問的資源稱為臨52兩個進程共享一個變量x時，兩種可能的執(zhí)行次序：

A：p1：r1:=x；r1:=r1+1；x:=r1；p2：

r2:=x；r2:=r2+1；x:=r2；B：P1：r1:=x;r1:=r1+1；x:=r1；p2：

r2:=x;r2:=r2+1;x:=r2；設x的初值為10，兩種情況下的執(zhí)行結(jié)果：情況A：

x=10+2

情況B：x=10+152兩個進程共享一個變量x時，兩種可能的執(zhí)行次序53例3：生產(chǎn)者-消費者問題產(chǎn)品outin01n-1緩沖池in:=(in+1)modnout:=(out+1)modn53例3：生產(chǎn)者-消費者問題產(chǎn)品outin01n-1緩沖池i54例3：生產(chǎn)者-消費者問題緩沖池滿：(in+1)modn=out緩沖池空：in=out引入整型變量：counter初值：0生產(chǎn)：counter

+1；消費：counter

-1。54例3：生產(chǎn)者-消費者問題緩沖池滿：(in+1)mod55例3：生產(chǎn)者-消費者問題生產(chǎn)者消費者進程共享下面的變量：varn:integer;typeitem=…;varbuffer:array［0,1,…,n-1］ofitem;in,out:0,1,…,n-1;counter:0,1,…,n;55例3：生產(chǎn)者-消費者問題生產(chǎn)者消費者進程共享下面的變量：56例3：生產(chǎn)者-消費者程序：producer:repeat…produceaniteminnextp;…whilecounter=ndono-op;buffer[in]:=nextp;in:=(in+1)modn;counter:=counter+1;untilfalse;consumer:repeatwhilecounter=0dono-op;nextc:=buffer[out];out:=(out+1)modn;counter:=counter-1;consumertheiteminnextc;untilfalse;56例3：生產(chǎn)者-消費者程序：producer:consu57例3：生產(chǎn)者-消費者程序機器語言實現(xiàn)：生產(chǎn)者：register1:=counter;register1:=register1+1;counter:=register1;假設counter的當前值為5；并發(fā)執(zhí)行時按如下順序執(zhí)行：register1:=counter;register1:=register1+1;register2:=counter;register2:=register2-1;counter:=register1;counter:=register2;消費者：register2:=counter;register2:=register2-1;counter:=register2;(register1=5)(register1=6)(register2=5)(register2=4)(counter=6)(counter=4)程序的執(zhí)行失去了再現(xiàn)性！思考：如何解決這個問題？57例3：生產(chǎn)者-消費者程序機器語言實現(xiàn)：生產(chǎn)者：假設cou58repeatuntilfalse臨界區(qū)剩余區(qū)剩余區(qū)3、臨界區(qū)（criticalsection）臨界區(qū)：進程中訪問臨界資源的一段代碼。進入?yún)^(qū)：在進入臨界區(qū)之前，檢查可否進入臨界區(qū)的一段代碼。如果可以進入臨界區(qū)，設置相應“正在訪問臨界區(qū)”標志。退出區(qū)：用于將“正在訪問臨界區(qū)”標志清除。剩余區(qū)：代碼中的其余部分。進入?yún)^(qū)退出區(qū)循環(huán)進程58repeatuntilfalse臨界區(qū)剩余區(qū)剩余區(qū)3、593、臨界區(qū)（續(xù)）

P1：

a:=a+1print(a)互斥P2：a:=a-1print(a)互斥P3：ifa<0thena:=a+1elsea:=a-1互斥程序中的臨界區(qū)593、臨界區(qū)（續(xù)）P1：互斥P2：a:=a-1互斥604、同步機制應遵循的規(guī)則為實現(xiàn)進程互斥地進入臨界區(qū)，可用軟件或?qū)ｉT的同步機構(gòu)實來現(xiàn)同步機制。所有同步機制都應遵循四條準則：空閑讓進：無進程處于臨界區(qū)。忙則等待：已有進程處于其臨界區(qū)。有限等待：等待進入臨界區(qū)的進程不能“死等”。讓權(quán)等待：不能進入臨界區(qū)的進程，應釋放CPU（如轉(zhuǎn)換到阻塞狀態(tài)）。604、同步機制應遵循的規(guī)則為實現(xiàn)進程互斥地進入臨界區(qū)，可用612.3.2信號量機制1965年，荷蘭人Dijkstra首先提出信號量機制信號量（Semaphores）僅能被兩個原語操作wait(S)-signal(S)修改的整型變量，表示一類資源的物理實體。信號量的值表示資源數(shù)量，只能由wait(S)和signal(S)原子操作改變。612.3.2信號量機制1965年，荷蘭人Dijkstra622.3.2信號量機制信號量分類：互斥的信號量：它的wait(S)-signal(S)在同一個進程中同步的信號量：它的wait(S)-signal(S)在不同的進程中信號量機制包括：整型、記錄型、AND型、信號量集機制。622.3.2信號量機制信號量分類：631.整型信號量S是一個整型量，除初始化外僅能通過2個原子操作wait(S)和signal(S)來訪問。wait(S)和signal(S)長時間以來被稱為P、V操作-荷蘭語的proberen(test)和verhogen(increment)631.整型信號量S是一個整型量，除初始化外僅能通過2個原子641.整型信號量（續(xù)）P，V操作描述如下：VarS:int;procedure

P(S) whileS<=0dono-op；

S--; procedureV(S) S++; 缺點：若S<=0,則P操作會不斷測試，不滿足“讓權(quán)等待”,即“忙等”。P操作，意味著請求分配一個單位資源Semaphore定義V操作，意味著釋放一個單位資源641.整型信號量（續(xù)）P，V操作描述如下：P操作，意味著652.記錄型信號量遵循“讓權(quán)等待”準則。信號量包括一個代表資源數(shù)目的整型變量和一個進程鏈表。記錄型可描述如下：typesemaphore=recordvalue:integer;L:listofprocess;end資源數(shù)目進程鏈表指針，鏈接所有等待進程652.記錄型信號量遵循“讓權(quán)等待”準則。信號量包括一個代662.記錄型信號量（續(xù)）P，V操作描述如下：procedureP(S)varS:semaphore;beginS.value:=S.value-1;ifS.value<0thenblock(S.L)endprocedureV(S)varS:semaphore;beginS.value:=S.value+1;ifS.value<=0thenwakeup(S.L)end喚醒相應等待鏈表S.L中等待的第一個進程；改變其狀態(tài)為就緒狀態(tài)；并將其插入到就緒隊列將該進程狀態(tài)置為等待狀態(tài)；并將該進程的PCB插入相應的等待鏈表S.L的末尾;662.記錄型信號量（續(xù)）P，V操作描述如下：喚醒相應等待672.記錄型信號量（小結(jié)）信號量S.value的物理意義：

S.value>0：S.value表示可用資源的個數(shù)S.value=0：表示無資源可用

S.value<0：|S.value|表示等待鏈表中進程的個數(shù)信號量的使用：必須置一次且只能置一次初值；初值不能為負數(shù)；只能執(zhí)行PV操作。思考：信號量S.value初值為1，情況如何？672.記錄型信號量（小結(jié)）信號量S.value的物理意義：683.AND型信號量問題：一個進程需要同時獲取兩個或多個臨界資源，各進程分別獲得部分臨界資源，然后等待其余的臨界資源，“各不相讓”，產(chǎn)生死鎖。適用于：同時需要多種資源且每種占用一個的信號量操作?；舅枷耄簩⑦M程在整個運行過程中需要的所有資源，一次性全部的分配給進程，待進程使用完后再一起釋放。AND型信號量中P原語：SwaitAND型信號量中V原語：Ssignal683.AND型信號量問題：一個進程需要同時獲取兩個或多個693.AND型信號量（續(xù)）P，V操作描述如下：Swait(S1,S2,…,Sn)

if(S1>=1andS2>=1and…andSn>=1)thenfori:=1tondoSi:=Si-1;

endforelse將該進程放入第一個Si<1的Si等待隊列，阻塞該進程;endif693.AND型信號量（續(xù)）P，V操作描述如下：703.AND型信號量（續(xù)）Ssignal(S1,S2,…,Sn)

fori:=1tondoSi:=Si+1; 從Si等待隊列中取出所有進程，放入就緒隊列;endfor703.AND型信號量（續(xù)）Ssignal(S1,S2,714.信號量集問題：一次需要N個某類臨界資源時，就要進行N次P操作，低效又可能死鎖。適用于：同時需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個臨界值時的處理?；舅枷耄涸贏ND型信號量機制的基礎上進行擴充，進程對信號量Si設下限值為ti（用于信號量的判斷，即需滿足Si>=ti，表示資源數(shù)量低于ti時，便不予分配），需求值為di（用于信號量的增減，即Si=Si–di或Si=Si+di）。714.信號量集問題：一次需要N個某類臨界資源時，就要進行724.信號量集（續(xù)）P，V操作如下：Swait(S1,t1,d1,…,Sn,tn,dn)

if(S1>=t1and…andSn>=tn)thenfori:=1;tondo

Si:=Si-di; endforelse將該進程放入第一個Si<ti的Si等待隊列，阻塞該進程;endifSsignal(S1,d1,…,Sn,dn)

fori:=1;tondo

Si:=Si+di;

從Si等待隊列中取出所有進程，放入就緒隊列;endfor724.信號量集（續(xù)）P，V操作如下：734.信號量集（小結(jié)）一般“信號量集”的幾種特殊情況：Swait(S,d,d)表示每次申請d個資源，當少于d個時，便不分配。Swait(S,1,1)表示一般的記錄型信號量或互斥信號量。Swait(S,1,0)作為一個可控開關當S>=1時，允許多個進程進入臨界區(qū)。當S=0時，禁止任何進程進入臨界區(qū)。734.信號量集（小結(jié)）一般“信號量集”的幾種特殊情況：74信號量機制總結(jié)：類型需求資源特點實現(xiàn)特點P:對于信號量S，當S<t時，不分配，否則一次分配d個資源；其中t為下限值；V:一次釋放d個資源。AND型信號量機制的擴充多個某類資源，多類多個不同類資源，每類1個1個1個P:當S>0,S=S-1V:S=S+1忙等讓權(quán)等待typesemaphore=recordvalue:integer;L:listofprocess;end將進程在整個運行過程中需要的所有資源，一次性全部地分配給進城，待進程使用完后再一起釋放。防止產(chǎn)生死鎖信號量集AND型信號量整型信號量記錄型信號量74信號量機制總結(jié)：類型需求資源特點實現(xiàn)特點P:對于信號量S752.3.3信號量的應用1.利用信號量實現(xiàn)進程互斥例如：兩個進程都使用一臺打印機可描述如下：Varmutex:semaphore:=1;//定義信號量beginparbegin

process1;//進程1

process2;//進程2parendend752.3.3信號量的應用1.利用信號量實現(xiàn)進程互斥76例如：兩個進程都使用一臺打印機進程1：process1:begin repeat

wait(mutex);

使用打印機；

signal(mutex); remaindersectionuntilfalse;end//臨界區(qū)//進入?yún)^(qū)//退出區(qū)返回76例如：兩個進程都使用一臺打印機process1:be77process2:beginrepeat

wait(mutex);

使用打印機；

signal(mutex);remaindersectionuntilfalse;end1.利用信號量實現(xiàn)進程互斥（續(xù)2）例如：兩個進程都使用一臺打印機進程2如下：//臨界區(qū)//進入?yún)^(qū)//退出區(qū)返回77process2:begin1.利用信號量實現(xiàn)進程782.利用信號量實現(xiàn)前趨關系設有兩個并發(fā)執(zhí)行的進程P1，P2。P1中有語句S1，P2中有語句S2。要求在S1后執(zhí)行S2。即：S1S2為實現(xiàn)這種前趨關系，使進程P1和P2一個共享的信號量S，初值S＝0。

PV描述：

在P1中：

在P2中：

S1；

wait(S)；

signal(S)；

S2；782.利用信號量實現(xiàn)前趨關系設有兩個并發(fā)執(zhí)行的進程P1，P79S2S1S3S4S5S6S1;

signal(a);signal(b);

wait(a);

S2;signal(c);signal(d);

wait(b);

S3;signal(e);wait(c);

S4;signal(f);wait(d);

S5;signal(g);wait(e);wait(f);wait(g);S6;

abcdefg每一對前趨關系用一個共享信號量表示，并賦初值0，設初值a,b,c,d,e,f,g:=0,0,0,0,0,0,0;語句執(zhí)行順序如下：S1S2S3S5S4S679S2S1S3S4S5S6S1;wait(a);wai80每一對前趨關系用一個共享信號量表示，并賦初值0，設初值a,b,c,d,e,f,g:=0,0,0,0,0,0,0;完整的程序如下：Vara,b,c,d,e,f,g:semaphore=0,0,0,0,0,0,0;begin parbegin beginS1；signal(a);signal(b);end;

begin

wait(a);S2;signal(c);signal(d);end;

begin

wait(b);S3;signal(e);end;

begin

wait(c);S4;signal(f);end;

begin

wait(d);S5;signal(g);end;

begin

wait(e);wait(f);wait(g);S6;end;

parendend80每一對前趨關系用一個共享信號量表示，并賦初值0，設初值812.4經(jīng)典進程的同步問題2.4.1生產(chǎn)者－消費者問題2.4.2哲學家進餐問題2.4.3讀者－寫者問題812.4經(jīng)典進程的同步問題2.4.1生產(chǎn)者－消費者問題822.4.1生產(chǎn)者－消費者問題1.利用記錄型信號量解決生產(chǎn)者－消費者問題公用信號量mutex：初值為1，用于實現(xiàn)臨界區(qū)互斥。生產(chǎn)者私用信號量empty：初值為n，指示空緩沖塊數(shù)目。消費者私用信號量full：初值為0，指示滿緩沖塊數(shù)目。整型量in和out初值均為0，in指示首空緩沖塊序號，out指示首滿緩沖塊序號。822.4.1生產(chǎn)者－消費者問題1.利用記錄型信號量解決生831.利用記錄型信號量解決生產(chǎn)者－消費者問題Varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,…,n-1]ofitem;in,out:integer:=0,0;begin parbegin

producer；

consumer；

parendendnext831.利用記錄型信號量解決生產(chǎn)者－消費者問題Varmut841.利用記錄型信號量解決生產(chǎn)者－消費者問題（生產(chǎn)者進程）producer:begin repeat produceanitemnextp;

wait(empty);wait(mutex);buffer(in):=nextp;in:=(in+1)modn;

signal(mutex);signal(full);untilfalse;end順序不能顛倒，否則死鎖！return841.利用記錄型信號量解決生產(chǎn)者－消費者問題（生產(chǎn)者進程）851.利用記錄型信號量解決生產(chǎn)者－消費者問題（消費者進程）consumer:beginrepeat

wait(full); wait(mutex);

nextc:＝buffer(out);out:=(out+1)modn;

signal(mutex); signal(empty);consumetheiteminnextc;untilfalse;end順序不能顛倒，否則死鎖！return851.利用記錄型信號量解決生產(chǎn)者－消費者問題（消費者進程）862.4.1生產(chǎn)者－消費者問題利用AND信號量解決生產(chǎn)者－消費者問題用SP(empty,mutex)來代替P(empty)和P(mutex)用SV(mutex,full)來代替V(mutex)和V(full)用SP(full,mutex)來代替P(full)和P(mutex)用SV(mutex,empty)來代替V(mutex)和V(empty)862.4.1生產(chǎn)者－消費者問題利用AND信號量解決生產(chǎn)者872.利用AND信號量解決生產(chǎn)者－消費者問題Varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,…,n-1]ofitem;in,out:integer:=0,0;beginparbegin

producer；

consumer；parendendnext872.利用AND信號量解決生產(chǎn)者－消費者問題Varmut882.利用AND信號量解決生產(chǎn)者－消費者問題(生產(chǎn)者進程)producer:begin repeat produceanitemnextp;

Swait(empty,mutex); buffer(in):=nextp; in:=(in+1)modn;

Ssignal(mutex,full);untilfalse;endreturn882.利用AND信號量解決生產(chǎn)者－消費者問題(生產(chǎn)者進程)892.利用AND信號量解決生產(chǎn)者－消費者問題(消費者進程）consumer:begin;repeat

Swait(full,mutex);nextc:＝buffer(out);out:=(out+1)modn;

Ssignal(mutex,empty);consumetheiteminnextc;untilfalse;endreturn892.利用AND信號量解決生產(chǎn)者－消費者問題(消費者進程）902.4.2哲學家進餐問題問題描述有五位哲學家圍坐一張圓桌進餐，圓桌上有五個盤子和五只筷子.哲學家的生活方式：交替的進行進餐和思考。進餐條件：拿取靠近他的左、右兩只筷子方能進餐。902.4.2哲學家進餐問題問題描述911.利用記錄型信號量解決哲學家進餐問題分析：筷子是臨界資源，在一段時間內(nèi)只允許一位哲學家使用。為了實現(xiàn)對筷子的互斥使用，可以用一個信號量表示一只筷子，由這五個信號量構(gòu)成信號量數(shù)組。Varchopstick:array[0,…,4]ofsemaphore;911.利用記錄型信號量解決哲學家進餐問題分析：筷子是臨界資92所有的信號量初始化為1，第i位哲學家的活動描述為：repeat

P(chopstick[i]);

P(chopstick[(i+1)mod5]);eat;

V(chopstick[i]);

V(chopstick[(i+1)mod5]);think;untilfalse;分析：可能存在什么問題？92所有的信號量初始化為1，第i位哲學家的活動描述為：931.利用記錄型信號量解決哲學家進餐問題五位哲學家同時拿起左邊的筷子將會引起死鎖。幾種解決辦法：至多只允許四位哲學家同時去拿左邊的筷子。僅當哲學家的左右兩只筷子均可用時，才允許拿起筷子進餐。規(guī)定奇數(shù)號的哲學家先拿左邊的筷子，偶數(shù)的哲學家先拿右邊的筷子。（作業(yè)）931.利用記錄型信號量解決哲學家進餐問題五位哲學家同時拿起94至多只允許四位哲學家同時去拿左邊的筷子第i位哲學家的活動描述：

while(true){

P(Sm)

P(chopstick[i]);

P(chopstick[(i+1)%5]); …… eating; ……

V(chopstick[i]);

V(chopstick[(i+1)%5]);

V(Sm) …… thinking;}//Sm限制同時進餐的人數(shù)，初值4，且Sm<=494至多只允許四位哲學家同時去拿左邊的筷子第i位哲學家的活動952.利用AND信號量解決哲學家進餐問題要求每個哲學家同時獲得兩只筷子后才能進餐Varchopstick:array[0,…,4]ofsemaphore:=(1,1,1,1,1);processi//第i位哲學家的活動描述為：repeatthink;SP(chopstick[(i+1)mod5],chopstick[i]);eat;SV(chopstick[(i+1)mod5],chopstick[i]);untilfalse;952.利用AND信號量解決哲學家進餐問題要求每個哲學家同時962.4.3讀者—寫者問題有兩組并發(fā)進程：讀者、寫者，共享一組數(shù)據(jù)區(qū)要求：允許多個讀者同時執(zhí)行讀操作不允許讀者、寫者同時操作（讀寫互斥）不允許多個寫者同時操作（只能一人寫）962.4.3讀者—寫者問題有兩組并發(fā)進程：讀者、寫者，共971.利用記錄型信號量解決讀者－寫者問題實現(xiàn)寫和讀進程或者多個寫進程互斥的信號量wmutex。正在讀的進程數(shù)目readcount，初始化為0。readcount是可被多個讀進程訪問的臨界資源，設置互斥信號量rmutex。971.利用記錄型信號量解決讀者－寫者問題實現(xiàn)寫和讀進程或者981.利用記錄型信號量解決讀者－寫者問題Varrmutex,wmutex:semaphore:=1,1;readcount:integer:=0;beginparbegin

Writer:begin

//寫進程 …

end

Reader:begin//讀進程 …

endparendend981.利用記錄型信號量解決讀者－寫者問題Varrmute991.利用記錄型信號量解決讀者－寫者問題Reader:begin//讀進程repeat

readcount:=readcount+1;

reading;

readcount:=readcount-1

untilfalse;endP(rmutex);V(rmutex);P(rmutex);V(rmutex);ifreadcount=0then P(wmutex);ifreadcount=0then V(wmutex);991.利用記錄型信號量解決讀者－寫者問題Reader:b1001.利用記錄型信號量解決讀者－寫者問題

//寫進程Writer:beginrepeatP(wmutex);writing;V(wmutex);untilfalse;end1001.利用記錄型信號量解決讀者－寫者問題//寫進程1012.利用信號量集機制解決讀者－寫者問題增加限制，只允許RN個讀者同時讀，引入一個信號量L，并賦初值RN。寫互斥信號量mx。VarRNinteger;L,mx:semaphore:=RN,1;beginparbegin reader://讀進程

writer://寫進程parendend1012.利用信號量集機制解決讀者－寫者問題增加限制，只允許1022.利用信號量集機制解決讀者－寫者問題//讀進程reader:beginrepeatSP(L,1,1);SP(mx,1,0);reading;SV(L,1);untilfalse;end1022.利用信號量集機制解決讀者－寫者問題//讀進程1032.利用信號量集機制解決讀者－寫者問題//寫進程writer:beginrepeatSP(mx,1,1;L,RN,0);writing;SV(mx,1);untilfalse;end1032.利用信號量集機制解決讀者－寫者問題//寫進程104例1：進程同步問題有一個信箱只能存放一封信，只要信箱為空，進程A就不斷產(chǎn)生信件并送入信箱，只要信箱中有信件，進程B就不斷從信箱中取出信進行處理。初始時，信箱為空。試用P、V操作表達進程A、B之間的關系。分析：共享資源：信箱（狀態(tài)：full/empty）；信號量：full，empty；初值：0，1。104例1：進程同步問題有一個信箱只能存放一封信，只要信箱為105例1：進程同步問題Varempty,full:semaphore=1,0;begin A:begin repeat

P(empty);

放一封信;

V(full); untilfalse;end

B:begin repeat

P(full);

取一封信; V(empty); untilfalse;endend105例1：進程同步問題Varempty,full:sem106例2：進程同步問題一個鐵籠子，每次只能放入一個動物，獵人向籠子放入老虎，農(nóng)民向籠子放入豬；動物園等待取籠中的老虎，飯店等待取籠中的豬。請用P、V操作寫出能同步執(zhí)行的程序。分析：進程：puttiger,putpig,gettiger,getpig;共享資源：籠子、老虎、豬；信號量：cage，tiger，pig；初值分別為：1，0，0。106例2：進程同步問題一個鐵籠子，每次只能放入一個動物，獵107例2：進程同步問題Varcage,tiger,pig:semaphore=1,0,0;beginputtiger:begin//放老虎repeat

P(cage);

將老虎放入籠中;

V(tiger);untilfalse;endputpig:begin//放豬repeat

P(cage);

將豬放入籠中;

V(pig);untilfalse;end107例2：進程同步問題Varcage,tiger,pig108例2：進程同步問題(續(xù))gettiger:begin//取老虎repeat

P(tiger);

從籠中取出老虎;

V(cage);untilfalse;end

getpig:begin//取豬repeat

P(pig);

從籠中取出豬;

V(cage);untilfalse;endend

108例2：進程同步問題(續(xù))gettiger:begi1092.3.4管程機制管程的提出采用PV同步機制來編寫并發(fā)程序，對于共享變量及信號量變量的操作將被分散于各個進程中。給系統(tǒng)管理帶來麻煩，而且還會因同步操作的使用不當導致系統(tǒng)死鎖。1092.3.4管程機制管程的提出110管程機制利用共享數(shù)據(jù)結(jié)構(gòu)抽象地表示系統(tǒng)中的共享資源，而把對該共享數(shù)據(jù)實施的操作定義為一組過程，如資源的請求(request)和釋放(release)過程。進程對共享資源的申請、釋放和其他操作，都是通過這組過程對共享的數(shù)據(jù)結(jié)構(gòu)的操作來實現(xiàn)的，這組過程還可以根據(jù)資源的情況，或接受或阻塞進程的訪問，確保每次僅有一個進程使用共享資源，這樣就可以統(tǒng)一管理對共享資源的所有訪問，實現(xiàn)進程互斥。代表共享資源的數(shù)據(jù)結(jié)構(gòu)，以及由該共享數(shù)據(jù)結(jié)構(gòu)實施操作的一組過程所組成的資源管理程序，共同構(gòu)成了一個操作系統(tǒng)的資源管理模塊，我們稱之為管程。110管程機制利用共享數(shù)據(jù)結(jié)構(gòu)抽象地表示系統(tǒng)中的共享資源，而111管程的定義一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程所執(zhí)行(在該數(shù)據(jù)結(jié)構(gòu)上)的一組操作,這組操作能同步進程和改變管程中的數(shù)據(jù)。這些數(shù)據(jù)及操作對進程是透明的，局部于管程的數(shù)據(jù)結(jié)構(gòu)只能被該管程的過程訪問。111管程的定義一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程所執(zhí)1121.管程的定義管程由四部分組成管程的名稱。局限于管程的共享變量說明。對該數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程。對局部于管程的數(shù)據(jù)設置初始值的語句。variabledeclarationsprocedureinitializationcodemonitor注意：任何進程訪問共享資源，只能通過調(diào)用管程中的過程（管程名.過程名）,而管程每次只允許一個進程進入管程，從而實現(xiàn)進程互斥1121.管程的定義管程由四部分組成variabledec113管程的語法描述：typemonitor-name=MONITOR；//名稱<共享變量說明>；//共享變量define<(能被其他模塊引用的)過程名列表>use<(要調(diào)用的本模塊外定義的)過程名列表>

procedure<過程名>(<形式參數(shù)列表>);begin …. end; …一組過程function<函數(shù)名>(<形式參數(shù)列表>):值類型;begin … end;…begininitializationcode;變量初始化end