計算機操作系統(tǒng)(第三章)3.5(進程的互斥與同步)

1、計算機操作系統(tǒng)第三章 進程管理_2 第三章 進程管理第2頁2022-6-18多進程對共享變量的并發(fā)訪問可能會導(dǎo)致數(shù)據(jù)的不一致！3.5.1 資源共享引起的制約3.5 3.5 進程互斥進程互斥 例1 假設(shè)有兩個并發(fā)執(zhí)行的進程P1和P2。cobegin p1; p2;coendP1: . x = x + 1; P2: . x = x + 1; 第3頁第三章 進程管理 X = X + 1 操作將被分解為幾條機器指令來實現(xiàn)，如：1 將變量x的值放入寄存器 register = x 2 把寄存器中的值加1 register = register + 13 把寄存器的值存到x中 x = register第4

2、頁第三章 進程管理 如果兩個進程的執(zhí)行順序為：P1: R1=x; R1=R1+1; x=R1; P2: R2=x; R2=R2+1; x=R2time第5頁第三章 進程管理 如果兩個進程的執(zhí)行順序為：P1: R1=x; R1=R1+1; x=R1; P2: R2=x; R2=R2+1; x=R2time第6頁第三章 進程管理 如果兩個進程的執(zhí)行順序為：P1: R1=x; R1=R1+1; x=R1; P2: R2=x; R2=R2+1; x=R2time第7頁第三章 進程管理 例2 對于生產(chǎn)者消費者問題。我們需要用一個變量(count)來記錄當前緩沖區(qū)中的數(shù)據(jù)個數(shù)。開始時，count的值設(shè)為零

3、，如果生產(chǎn)者生產(chǎn)了一個產(chǎn)品放到一個新的緩沖中，則將count的值加1，如果消費者消費了某個緩沖區(qū)中的產(chǎn)品，則將count的值減1。生產(chǎn)者消費者1.exe生產(chǎn)者進程 while (true) /* produce an item and put in nextProduced */ while (count = BUFFER_SIZE); / do nothing buffer in = nextProduced; in = (in + 1) % BUFFER_SIZE; count +; 消費者進程 while (true) while (count = 0) ; / do nothing n

4、extConsumed = bufferout; out = (out + 1) % BUFFER_SIZE; count -; /* consume the item in nextConsumed */競爭條件 count+ 指令的執(zhí)行可能被實現(xiàn)為 register1 = count register1 = register1 + 1 count = register1 count 指令的執(zhí)行可能被實現(xiàn)為 register2 = count register2 = register2 - 1 count = register2 假如初始時“count = 5” ，可能會出現(xiàn)下面的交替執(zhí)行情

5、況:S0: 生產(chǎn)者執(zhí)行 register1 = count register1 = 5S1: 生產(chǎn)者執(zhí)行 register1 = register1 + 1 register1 = 6 S2: 消費者執(zhí)行 register2 = count register2 = 5 S3: 消費者執(zhí)行 register2 = register2 - 1 register2 = 4 S4: 生產(chǎn)者執(zhí)行 count = register1 count = 6 S5: 消費者執(zhí)行 count = register2 count = 42022-6-18第三章 進程管理第12頁第13頁第三章 進程管理 進程的并發(fā)執(zhí)

6、行不僅僅是用戶程序的執(zhí)行開始時間的隨機性和提高資源利用率的結(jié)果，也是資源有限性導(dǎo)致資源的競爭與共享對進程的執(zhí)行過程進行制約所造成的一一. . 互斥的概念互斥的概念 引例：引例： 宿舍電話的使用宿舍電話的使用 打印機的使用打印機的使用 1. 臨界資源：一次僅允許一個進程使用的資源稱為臨界資源臨界資源：一次僅允許一個進程使用的資源稱為臨界資源 引例中的電話和打印機都屬于臨界資源。除此之外，還有內(nèi)引例中的電話和打印機都屬于臨界資源。除此之外，還有內(nèi)存變量、指針、數(shù)組等等也是臨界資源。存變量、指針、數(shù)組等等也是臨界資源。1.1.臨界區(qū)：臨界區(qū)： 每個進程中訪問臨界資源的那段程序段稱為臨界區(qū)（臨界段）。

7、進入?yún)^(qū)(entry section)：在進入臨界區(qū)之前，檢查可否進入臨界區(qū)的一段代碼。如果可以進入臨界區(qū)，通常設(shè)置相應(yīng)正在訪問臨界區(qū)標志退出區(qū)(exit section)：用于將正在訪問臨界區(qū)標志清除。剩余區(qū)(remainder section)：代碼中的其余部分。第三章 進程管理第14頁2022-6-182. 間接制約 間接制約：把由于共享某一公有資源而引起的在臨界區(qū)內(nèi)不允許并發(fā)進程交叉執(zhí)行的現(xiàn)象，稱為由共享公有資源而造成的對并發(fā)進程執(zhí)行速度的間接制約 直接制約：一組在異步環(huán)境下的并發(fā)進程，各自的執(zhí)行結(jié)果互為對方的執(zhí)行條件，從而限制各進程的執(zhí)行速度的過程 對于每一類，系統(tǒng)應(yīng)有相應(yīng)的分配和釋放

8、相應(yīng)公有資源的管理辦法，以制約并發(fā)進程。這就是互斥第三章 進程管理第15頁2022-6-18互斥互斥定義定義: : 一組并發(fā)進程中的一個或多個程序段，因共享某一組并發(fā)進程中的一個或多個程序段，因共享某一公有資源而導(dǎo)致它們必須以一個不允許交叉執(zhí)行一公有資源而導(dǎo)致它們必須以一個不允許交叉執(zhí)行的單位執(zhí)行。也就是說，不允許兩個以上的共享該的單位執(zhí)行。也就是說，不允許兩個以上的共享該資源的并發(fā)進程同時進入臨界區(qū)稱為互斥資源的并發(fā)進程同時進入臨界區(qū)稱為互斥。 一般情況下，作為程序段的一個過程不允許多一般情況下，作為程序段的一個過程不允許多個進程共同訪問它。個進程共同訪問它。第三章 進程管理第16頁2022

9、-6-18互斥的例子：互斥的例子：例例1：進程：進程A、B共享一臺打印機，則當一進程占用打印機后，另共享一臺打印機，則當一進程占用打印機后，另一進程若也要使用打印機，則必須等待，直至它釋放打印機。一進程若也要使用打印機，則必須等待，直至它釋放打印機。例例2：機票預(yù)訂系統(tǒng)：機票預(yù)訂系統(tǒng) A B 旅行社旅行社A查到某機座空；查到某機座空； ： ： 旅行社旅行社B查到某機座空；查到某機座空； 與其顧客商量；與其顧客商量； ： ： 旅行社旅行社A預(yù)訂該機座；預(yù)訂該機座； ： B預(yù)訂該機座；預(yù)訂該機座；第三章 進程管理第17頁2022-6-18并發(fā)進程互斥必須滿足的原則(1) 不能假設(shè)各并發(fā)進程的相對執(zhí)

10、行速度。即各并發(fā)進程享有平等的、獨立的競爭共有資源的權(quán)利，且在不采取任何措施的條件下，在臨界區(qū)內(nèi)任一指令結(jié)束時，其他并發(fā)進程可以進入臨界區(qū)。 (2) 并發(fā)進程中的某個進程不在臨界區(qū)時，它不阻止其他進程進入臨界區(qū)。(空閑讓進） (3) 并發(fā)進程中的若干個進程申請進入臨界區(qū)時，只能允許一個進程進入 (4) 并發(fā)進程中的某個進程申請進入臨界區(qū)時開始，應(yīng)在有限時間內(nèi)得以進入臨界區(qū)準則準則(1)，(2)，(3)是保證各并發(fā)進程享有平等的、獨立的競爭是保證各并發(fā)進程享有平等的、獨立的競爭和使用公有資源的權(quán)利，且保證每一時刻至多只有一個進程在和使用公有資源的權(quán)利，且保證每一時刻至多只有一個進程在臨界區(qū)。而準

11、則臨界區(qū)。而準則(4)則是并發(fā)進程不發(fā)生死鎖（將在后面講述）則是并發(fā)進程不發(fā)生死鎖（將在后面講述）的重要保證。的重要保證。第三章 進程管理第18頁2022-6-18 進入臨界區(qū)的準則：進入臨界區(qū)的準則： (1)(1)每次至多有一個進程處于臨界區(qū)；每次至多有一個進程處于臨界區(qū)； (2)(2)當有若干個進程欲進入臨界區(qū)時，應(yīng)在有限當有若干個進程欲進入臨界區(qū)時，應(yīng)在有限 的時間內(nèi)使其進入；的時間內(nèi)使其進入； (3)(3)進程在臨界區(qū)內(nèi)僅逗留有限的時間進程在臨界區(qū)內(nèi)僅逗留有限的時間。第三章 進程管理第19頁2022-6-183.5.2 互斥的加鎖實現(xiàn) 人們可能認為只需把臨界區(qū)中的各個過程按不同的時間排

12、列調(diào)用就行了，但由于用戶程序執(zhí)行開始的隨機性，要求該組并發(fā)進程中的每個進程事先知道其他并發(fā)進程與系統(tǒng)的動作。不可能把臨界區(qū)中的各個過程按不同的時間排列調(diào)用。因此，互斥的實現(xiàn)必須通過加鎖的方式進行解決。1、互斥的實現(xiàn) 當某個進程進入臨界區(qū)之后，它將鎖上臨界區(qū)，直到它退出臨界區(qū)時為止。并發(fā)進程在申請進入臨界區(qū)時，首先測試該臨界區(qū)是否是上鎖的。如果該臨界區(qū)已被鎖住，則該進程要等到該臨界區(qū)開鎖之后才有可能獲得臨界區(qū)。第三章 進程管理第20頁2022-6-18 二二. . 用鎖實現(xiàn)互斥用鎖實現(xiàn)互斥 1.1.鎖和上鎖鎖和上鎖、開鎖操作開鎖操作 解決進程互斥的最簡單的辦法是加鎖。解決進程互斥的最簡單的辦法是

13、加鎖。 在系統(tǒng)中為在系統(tǒng)中為每個臨界資源設(shè)置一個鎖位，每個臨界資源設(shè)置一個鎖位， 0 0 表示資源可用表示資源可用， 1 1 表示資源已被占用（不可用）。表示資源已被占用（不可用）。 同時同時, ,系統(tǒng)要提供上鎖原語和開鎖原語，供進程在使系統(tǒng)要提供上鎖原語和開鎖原語，供進程在使用臨界資源之前和使用完臨界資源之后使用。用臨界資源之前和使用完臨界資源之后使用。第三章 進程管理第21頁2022-6-18 2 2. .用上鎖原語和開鎖原語實現(xiàn)進程互斥用上鎖原語和開鎖原語實現(xiàn)進程互斥 上鎖原語上鎖原語 進入臨界區(qū)進入臨界區(qū)csb 開鎖原語開鎖原語進程進程B 上鎖原語上鎖原語 進入臨界區(qū)進入臨界區(qū)csa

14、開鎖原語開鎖原語進程進程A第三章 進程管理第22頁2022-6-18main ( ) ppa ( ) ppb ( ) int w=0; : : cobegin lock(w); lock(w); ppa(); CSa; CSb; ppb(); unlock(w); unlock(w); coend : : 第三章 進程管理第23頁2022-6-.3信號量和信號量和P P，V V原語原語1.1.信號量（信號量（Semaphore)Semaphore)（信號燈）（信號燈）第三章 進程管理第24頁2022-6-18信號量：除賦初值外僅能由同步原語（P、V操作）對其操作的整型變量，

15、其值與其所代表的資源使用情況有關(guān)。信號量的物理意義： 當其值0代表可用資源的數(shù)量 當其值 0 0 時，表示綠燈，進程執(zhí)行。時，表示綠燈，進程執(zhí)行。( (表示系統(tǒng)擁有的表示系統(tǒng)擁有的資源個數(shù)資源個數(shù)) s 0 0 時，表示紅燈，進程停止執(zhí)行。時，表示紅燈，進程停止執(zhí)行。( ( |s|表示等待表示等待某資源的進程個數(shù)某資源的進程個數(shù)) ) 注意：創(chuàng)建信號燈時，應(yīng)準確說明信號燈 s 的意義和初值 (這個初值絕不能為負值)。main ( ) pa ( ) pb ( ) pc ( ) int mutex=1; : : : cobegin p(mutex); p(mutex); p(mutex); pa(

16、 ); CSa; CSb; CSc; pb( ); v(mutex); v(mutex); v(mutex); pc( ); : : : coend 信號燈信號燈mutex的取值范圍：的取值范圍：-2、-1、0、1第三章 進程管理第30頁2022-6-18思考：信號量的值有什么含義？ 信號量的值可以大于1嗎？ P/V原語的使用方法 進程在進入臨界區(qū)之前，執(zhí)行P操作（申請資源）進程在退出臨界區(qū)之后，執(zhí)行V操作（歸還資源）第三章 進程管理第32頁 3.6.1. 3.6.1. 同步的概念同步的概念 互斥的概念來自于諸進程對獨占使用資源（設(shè)備）的互斥的概念來自于諸進程對獨占使用資源（設(shè)備）的競爭，同步

17、來源于多個進程的合作。在人類社會中競爭與競爭，同步來源于多個進程的合作。在人類社會中競爭與合作是永恒的。合作是永恒的。 同步同步：所謂同步就是并發(fā)進程在一些關(guān)鍵點上可能需：所謂同步就是并發(fā)進程在一些關(guān)鍵點上可能需要相互等待與互通消息，這樣的相互制約關(guān)系稱為進程同要相互等待與互通消息，這樣的相互制約關(guān)系稱為進程同步。步。3.6 進程同步進程同步第三章 進程管理第33頁2022-6-18直接制約：一組在異步環(huán)境下的并發(fā)進程，各自的執(zhí)行結(jié)果互為對方的執(zhí)行條件，從而限制各進程的執(zhí)行速度的過程異步環(huán)境主要指各并發(fā)進程的執(zhí)行起始時間的隨機性和執(zhí)行速度的獨立性直接制約的進程互相給對方進程發(fā)送執(zhí)行條件已經(jīng)具備

18、的信號，只要收到了制約進程發(fā)來的信號便開始執(zhí)行，而在未收到制約進程發(fā)來的信號時便進入等待狀態(tài) 進程間的同步：把異步環(huán)境下的一組并發(fā)進程，因直接制約而互相發(fā)送消息而進行互相合作、互相等待，使得各進程按一定的速度執(zhí)行的過程。 合作進程：具有同步關(guān)系的一組并發(fā)進程稱為合作進程，合作進程間互相發(fā)送的信號稱為消息或事件第三章 進程管理第34頁2022-6-18同步機制應(yīng)遵循的準則 空閑則入：其他進程均不處于臨界區(qū)； 忙則等待：已有進程處于其臨界區(qū)； 有限等待：等待進入臨界區(qū)的進程不能死等； 讓權(quán)等待：不能進入臨界區(qū)的進程，應(yīng)釋放CPU（如轉(zhuǎn)換到阻塞狀態(tài)）3.6.2 私用信號量 一般來說，也可以把各進程之

19、間發(fā)送的消息作為信號量看待。與進程互斥時不同的是，這里的信號量只與制約進程及被制約進程有關(guān)而不是與整組并發(fā)進程有關(guān)。因此，稱該信號量為私用信號量（Private Semaphvre）。一個進程Pi的私用信號量Semi是從制約進程發(fā)送來的進程Pi的執(zhí)行條件所需要的消息。與私用信號量相對應(yīng)，稱互斥時使用的信號量為公用信號量。第三章 進程管理第36頁2022-6-183.6.3 用，原語操作實現(xiàn)同步用P、V原語不但可以實現(xiàn)對共享資源的互斥訪問，還可以實現(xiàn)對共享變量的加1（V操作）和減1操作（P操作） 有了私用信號量的概念，可以使用，原語操作實現(xiàn)進程間的同步。利用，原語實現(xiàn)進程同步的方法與利用wait

20、和signal過程時相同，也是分為三步。首先為各并發(fā)進程設(shè)置私用信號量，然后為私用信號量賦初值，最后利用，原語和私用信號量規(guī)定各進程的執(zhí)行順序。圖3.13 緩沖區(qū)隊列第三章 進程管理第37頁2022-6-18例：設(shè)進程PA和PB通過緩沖區(qū)隊列傳遞數(shù)據(jù)（如圖3.13）。PA為發(fā)送進程，PB為接收進程。PA發(fā)送數(shù)據(jù)時調(diào)用發(fā)送過程deposit(data)，PB接收數(shù)據(jù)時調(diào)用過程remove(data)。且數(shù)據(jù)的發(fā)送和接收過程滿足如下條件：(1) 在PA至少送一塊數(shù)據(jù)入一個緩沖區(qū)之前，PB不可能從緩沖區(qū)中取出數(shù)據(jù)（假定數(shù)據(jù)塊長等于緩沖區(qū)長度）；(2) PA往緩沖隊列發(fā)送數(shù)據(jù)時，至少有一個緩沖區(qū)是空的

21、；(3) 由PA發(fā)送的數(shù)據(jù)塊在緩沖隊列中按先進先出（FIFO）方式排列。描述發(fā)送過程deposit(data)和接收過程remove(data)。第三章 進程管理第38頁2022-6-18 解：由題意可知，進程PA調(diào)用的過程deposit(data)和進程PB調(diào)用的過程remove(data)必須同步執(zhí)行，因為過程 deposit(data)的執(zhí)行結(jié)果是過程remove(data)的執(zhí)行條件，而當緩沖隊列全部裝滿數(shù)據(jù)時，remove(data)的執(zhí)行結(jié)果又是deposit(data)的執(zhí)行條件，滿足同步定義。從而，按以下三步描述過程deposit(data)和remove(data)：(1)

22、設(shè)Bufempty為進程PA的私用信號量，Buffull 為進程PB的私用信號量；(2) 令Bufempty的初始值為n（n 為緩沖隊列的緩沖區(qū)個數(shù)），Buffull 的初始值為0；(3) 描述：第三章 進程管理第39頁2022-6-18PA: deposit(data):begin local xP(Bufempty)；按FIFO方式選擇一個空緩沖區(qū)Buf(x)；Buf(x) dataBuf(x)置滿標記（Buffull）endPB: remove(data):Begin local x （Buffull）；按FIFO方式選擇一個裝滿數(shù)據(jù)的緩沖區(qū)Buf(x)data Buf(x)Buf(x)

23、置空標記 （Bufempty）end這里，局這里，局部變量部變量x用用來指明緩來指明緩沖區(qū)的區(qū)沖區(qū)的區(qū)號，給號，給Buf(x)置置標志位是標志位是為了便于為了便于區(qū)別和搜區(qū)別和搜索空緩沖索空緩沖區(qū)及非空區(qū)及非空緩沖區(qū)。緩沖區(qū)。第三章 進程管理第40頁2022-6-18PB: remove(data):Begin local x （Buffull）；按FIFO方式選擇一個裝滿數(shù)據(jù)的緩沖區(qū)Buf(x)data Buf(x)Buf(x)置空標記 （Bufempty）end這里，局部變量x用來指明緩沖區(qū)的區(qū)號，給Buf(x)置標志位是為了便于區(qū)別和搜索空緩沖區(qū)及非空緩沖區(qū)。PA: deposit(da

24、ta):begin local xP(Bufempty)；按FIFO方式選擇一個空緩沖區(qū)Buf(x)；Buf(x) dataBuf(x)置滿標記（Buffull）end第41頁進程的交互關(guān)系：可以按照相互感知的程度來分類相互感知的程度交互關(guān)系一個進程對其他進程的影響潛在的控制問題相互不感知(完全不了解其它進程的存在)競爭(competition)一個進程的操作對其他進程的結(jié)果無影響互斥，死鎖（可釋放的資源），饑餓間接感知(雙方都與第三方交互，如共享資源)通過共享進行協(xié)作 一個進程的結(jié)果依賴于從其他進程獲得的信息互斥，死鎖（可釋放的資源），饑餓，數(shù)據(jù)一致性直接感知(雙方直接交互，如通信)通過通信

25、進行協(xié)作 一個進程的結(jié)果依賴于從其他進程獲得的信息死鎖，饑餓互斥：互斥：指多個進程不能同時使用同一個資源；死鎖：死鎖：指多個進程互不相讓，都得不到足夠的資源；饑餓：饑餓：指一個進程一直得不到資源（其他進程可能輪流占用資源）經(jīng)典進程同步問題3.6.3生產(chǎn)者消費者問題(the producer-consumer problem)問題描述：若干進程通過有限的共享緩沖區(qū)交換數(shù)據(jù)。其中，生產(chǎn)者進程不斷寫入，而消費者進程不斷讀出；共享緩沖區(qū)共有N個；任何時刻只能有一個進程可對共享緩沖區(qū)進行操作。共享緩沖區(qū)生產(chǎn)指針消費指針Producer 1Producer 2.Producer MConsumer 1Co

26、nsumer 2.Consumer N滿空指針移動方向第43頁 采用信號量機制：full是滿數(shù)目，初值為0，empty是空數(shù)目，初值為N。實際上，full和empty是同一個含義：full + empty = Nmutex用于訪問緩沖區(qū)時的互斥，初值是1 每個進程中各個P操作的次序是重要的：先檢查資源數(shù)目，再檢查是否互斥否則可能死鎖(為什么？) 采用AND信號量集：Swait(empty, mutex), Ssignal(full, mutex), ConsumerProducerP(empty);P(mutex);/進入?yún)^(qū) one unit - buffer;V(mutex);V(full)

27、;/退出區(qū)P(full);P(mutex);/進入?yún)^(qū) one unit - buffer;V(mutex);V(empty);/退出區(qū)第44頁flash演示演示: 生產(chǎn)者、消費者生產(chǎn)者、消費者生產(chǎn)者、消費者問題生產(chǎn)者、消費者問題有多個生產(chǎn)者不斷重復(fù)以下過程：有多個生產(chǎn)者不斷重復(fù)以下過程： 生產(chǎn)一產(chǎn)品生產(chǎn)一產(chǎn)品 放入緩沖單元放入緩沖單元有多個消費者不斷重復(fù)以下動作：有多個消費者不斷重復(fù)以下動作： 從緩沖中取出一個產(chǎn)品從緩沖中取出一個產(chǎn)品 把產(chǎn)品消費掉把產(chǎn)品消費掉問題：問題： 1. 如何防止兩個生產(chǎn)者同時將產(chǎn)品放入同一個單元？如何防止兩個生產(chǎn)者同時將產(chǎn)品放入同一個單元？ 2. 如何防止兩消費者同時從同一個單元中取產(chǎn)品？