操作系統(tǒng)原理：進(jìn)程管理(二)

進(jìn)程的互斥

——你要，我也要

1、多道程序設(shè)計(jì)帶來(lái)的問(wèn)題

并發(fā)執(zhí)行的多個(gè)進(jìn)程可能產(chǎn)生互斥或同步的相互制約關(guān)系，不采取措施，可能導(dǎo)致結(jié)果的不可再現(xiàn)性。影響系統(tǒng)效率，而且還可以導(dǎo)致系統(tǒng)崩潰。3.4.1互斥的定義

1、進(jìn)程互斥

指的是對(duì)某個(gè)系統(tǒng)資源，一個(gè)進(jìn)程正在使用它，另外一個(gè)想用它的進(jìn)程就必須等待，而不能同時(shí)使用。3.4.1互斥的定義

2、進(jìn)程互斥是一種間接制約關(guān)系多道程序系統(tǒng)中進(jìn)程間存在的一種源于資源共享的制約關(guān)系，主要是由被共享資源的獨(dú)占使用性質(zhì)所決定的。并發(fā)進(jìn)程之間()彼此無(wú)關(guān)A必須同步B必須互斥C提交可能需要同步或互斥D單選題1分3、臨界資源限定進(jìn)程只能互斥地訪問(wèn)的資源（指一次僅允許一個(gè)進(jìn)程使用的資源，不允許并發(fā)訪問(wèn)）。4、臨界資源不能搶占，不可剝奪

在搶占式操作系統(tǒng)中，優(yōu)先級(jí)別高的進(jìn)程不能中途從低優(yōu)先級(jí)進(jìn)程手中把臨界資源搶來(lái)使用。一、互斥的定義在下面的敘述中,正確的是()。臨界資源是非共享資源A臨界資源是任意共享資源B臨界資源是互斥共享資源C臨界資源是同時(shí)共享資源D提交單選題1分下列資源中,()是臨界資源。打印機(jī)A非共享的資源B共享變量C共享緩沖區(qū)D提交多選題1分5、臨界資源與非臨界資源舉例（1）臨界資源

打印機(jī)、共享變量（2）可剝奪性使用的資源CPU、內(nèi)存和磁盤(pán)等。一、互斥的定義下面列出的選項(xiàng)中,不屬于可剝奪性資源的有()。CPUA內(nèi)存B磁盤(pán)C磁帶機(jī)D提交單選題1分一、互斥的定義6、臨界區(qū)

進(jìn)程中訪問(wèn)臨界資源的那段程序代碼稱(chēng)為臨界區(qū)或臨界段。7、同類(lèi)臨界區(qū)（相關(guān)臨界區(qū)）使用同一臨界資源的不同進(jìn)程中的臨界區(qū)。一、互斥的定義8、臨界區(qū)互斥訪問(wèn)臨界資源使用同一臨界資源的進(jìn)程應(yīng)互斥地進(jìn)入各自的臨界區(qū)。9、臨界區(qū)的使用原則

空則讓進(jìn)，忙則等待，等則有限，等則讓權(quán)一、互斥的定義3.4.2、互斥機(jī)制1、操作系統(tǒng)實(shí)現(xiàn)進(jìn)程的互斥、同步的機(jī)制形式（1）上鎖與開(kāi)鎖原語(yǔ)（2）信號(hào)燈機(jī)制（重點(diǎn)）（3）管程機(jī)制2、上鎖與開(kāi)鎖機(jī)制（1）特點(diǎn)

最簡(jiǎn)單的進(jìn)程互斥機(jī)制（2）互斥實(shí)現(xiàn)機(jī)制使用鎖變量W來(lái)表示某種臨界資源的狀態(tài)。

W=0表示資源空閑可用

W=1表示資源正被使用

3.4.2、互斥機(jī)制（3）上鎖原語(yǔ)：LOCK（W）

算法思想L1：如果W=1那么轉(zhuǎn)向L1;否則W=1返回1.考察鎖位的值；2.如果原來(lái)的值為0，將鎖位置1；3.如果為1，則返回第一步再次考察2、上鎖與開(kāi)鎖機(jī)制3.4.2、互斥機(jī)制算法偽代碼voidlock(鎖變量w){test:if(w為1)gototestelsew=1;/*上鎖*/}/*lock(w)*/（3）上鎖原語(yǔ)：LOCK（W）

2、上鎖與開(kāi)鎖機(jī)制3.4.2、互斥機(jī)制W=0;返回voidunlock(鎖變量w){w=0;/*開(kāi)鎖*/}/*unlock(w)*/當(dāng)進(jìn)程使用完資源后，它必須將鎖位置成“0”，稱(chēng)為開(kāi)鎖操作。（3）開(kāi)鎖原語(yǔ)：UNLOCK（W）

2、上鎖與開(kāi)鎖機(jī)制3.4.2、互斥機(jī)制3、上鎖與開(kāi)鎖原語(yǔ)實(shí)現(xiàn)進(jìn)程互斥機(jī)制方法（1）欲進(jìn)入臨界區(qū)的進(jìn)程，必須先執(zhí)行上鎖原語(yǔ)；（2）若上鎖原語(yǔ)順利通過(guò)，則進(jìn)程可進(jìn)入臨界區(qū)；（3）當(dāng)完成對(duì)臨界區(qū)資源的訪問(wèn)后再執(zhí)行開(kāi)鎖原語(yǔ)，以釋放該臨界資源。3.4.2、互斥機(jī)制例如，甲、乙兩進(jìn)程要訪問(wèn)同一類(lèi)臨界資源甲進(jìn)程：其他代碼；

LOCK（W）；甲進(jìn)程的臨界區(qū)；

UNLOCK（W）；其他代碼；乙進(jìn)程：其他代碼；

LOCK（W）；乙進(jìn)程的臨界區(qū)；

UNLOCK（W）；其他代碼；3.4.2、互斥機(jī)制4、上鎖原語(yǔ)和開(kāi)鎖原語(yǔ)實(shí)現(xiàn)互斥優(yōu)缺點(diǎn)優(yōu)點(diǎn)：簡(jiǎn)單缺點(diǎn)：處理機(jī)效率不高

因?yàn)樯湘i原語(yǔ)中的條件測(cè)試操作可能引起CPU“忙等”。3.4.2、互斥機(jī)制3.5信號(hào)量機(jī)制

荷蘭著名科學(xué)家，后來(lái)的計(jì)算機(jī)圖靈獎(jiǎng)獲得者，E.W.Dijkstra于1965年提出了用作進(jìn)程同步工具的信號(hào)量（semaphore）機(jī)制，這是一種卓有成效的進(jìn)程互斥同步工具，已被廣泛應(yīng)用于現(xiàn)代計(jì)算機(jī)系統(tǒng)中。信號(hào)量機(jī)制的基本原理兩個(gè)或多個(gè)進(jìn)程可以利用彼此間收發(fā)的簡(jiǎn)單的信號(hào)來(lái)實(shí)現(xiàn)“正確的”并發(fā)執(zhí)行，一個(gè)進(jìn)程在收到一個(gè)指定信號(hào)前，會(huì)被迫在一個(gè)確定的或者需要的地方停下來(lái)，從而保持同步或互斥。3.5信號(hào)量機(jī)制

3.5.1信號(hào)量的概念1、信號(hào)量，也叫信號(hào)燈，一般是由兩個(gè)成員組成的結(jié)構(gòu)體，是一個(gè)確定的二元組（S，Q）

（1）S是個(gè)具有非負(fù)初值的整型變量，表示該信號(hào)量的值，且S的值只能由定義在信號(hào)量上的P操作原語(yǔ)和V操作原語(yǔ)來(lái)改變；（2）Q是個(gè)初始狀態(tài)為空的隊(duì)列。2、信號(hào)量類(lèi)型是個(gè)復(fù)合類(lèi)型，其一個(gè)分量是個(gè)整型分量S，另一個(gè)分量是個(gè)等待隊(duì)列指針Q（一個(gè)是指向PCB的指針，當(dāng)多個(gè)進(jìn)程都等待同一信號(hào)量時(shí)，它們就排成一個(gè)隊(duì)列，由信號(hào)量的指針項(xiàng)指出該隊(duì)列的頭。）3.5.1信號(hào)量的概念

3、信號(hào)量通?？梢院?jiǎn)單反映出相應(yīng)資源的使用情況，它與P，V操作原語(yǔ)一起使用可實(shí)現(xiàn)進(jìn)程的同步和互斥。3.5.1信號(hào)量的概念4、信號(hào)量的整型分量S的值的物理含義

（1）當(dāng)S≥0時(shí)，表示某類(lèi)可用資源的數(shù)目，或者說(shuō)表示可以執(zhí)行P操作而不會(huì)被阻塞的進(jìn)程的數(shù)目；3.5.1信號(hào)量的概念（2）當(dāng)S＜0時(shí)，其絕對(duì)值表示因等待信號(hào)量S被阻塞在阻塞隊(duì)列中的進(jìn)程數(shù)，即系統(tǒng)中因請(qǐng)求該類(lèi)資源而被阻塞的進(jìn)程的數(shù)目（3）S的值只能由P、V操作來(lái)改變。

注意：S值負(fù)數(shù)值和非負(fù)數(shù)值代表含義不同。4、信號(hào)量的整型分量S的值的物理含義

3.5.1信號(hào)量的概念3.5.2

P、V操作原語(yǔ)1、P、V原語(yǔ)意思（1）P代表荷蘭語(yǔ)的proberen，意為“測(cè)試”；（2）V代表荷蘭語(yǔ)的verhogen，意為“增加”?，F(xiàn)在很多國(guó)外的文獻(xiàn)都使用wait和signal操作（或者down和up操作）代替P、V操作。C++中的P、V操作就用wait和signal操作。2、P（S）原語(yǔ)操作的算法描述（1）S減1；（2）若S≥0，則調(diào)用P（S）的進(jìn)程返回，繼續(xù)執(zhí)行；（3）若S<0，調(diào)用者進(jìn)程調(diào)用阻塞原語(yǔ)Block（Q），把自己插入到信號(hào)量S的阻塞隊(duì)列Q中(把相應(yīng)的PCB連入等待該信號(hào)量隊(duì)列的末尾，并放棄處理機(jī)，進(jìn)入等待)。

3.5.2

P、V操作原語(yǔ)設(shè)兩個(gè)進(jìn)程共用一個(gè)臨界資源的互斥信號(hào)量mutex,當(dāng)mutex=-1時(shí)表示()。一個(gè)進(jìn)程進(jìn)入了臨界區(qū),另一個(gè)進(jìn)程等待A沒(méi)有一個(gè)進(jìn)程進(jìn)入臨界區(qū)B兩個(gè)進(jìn)程都進(jìn)入了臨界區(qū)C兩個(gè)進(jìn)程都在等待D提交單選題1分()操作不是P操作可完成的。為進(jìn)程分配處理機(jī)A使信號(hào)量的值變小B可用于進(jìn)程的同步C使進(jìn)程進(jìn)入阻塞狀態(tài)D提交單選題1分P(s)入口S-1=>SS≥0Block(Q)

返回YN2P(S)操作的算法流程圖描述3.5.2

P、V操作原語(yǔ)當(dāng)一進(jìn)程因在記錄型信號(hào)量S上執(zhí)行P原語(yǔ)操作而被阻塞后,S的值為()。>0A<0B≥0C≤0D提交單選題1分3．V（S）原語(yǔ)操作的算法描述（1）S加1；（2）若S>0，則調(diào)用V（S）的進(jìn)程繼續(xù)執(zhí)行，返回；（說(shuō)明沒(méi)有等待該信號(hào)量的進(jìn)程）（3）若S<=0，調(diào)用者進(jìn)程調(diào)用喚醒原語(yǔ)Wakeup（Q），把等待信號(hào)量S的阻塞隊(duì)列Q中的隊(duì)首進(jìn)程移出并喚醒進(jìn)入就緒隊(duì)列，返回。

3.5.2

P、V操作原語(yǔ)V(s)入口S+1=>SS>0Wakeup(Q)

返回YN3．V（S）原語(yǔ)操作的算法描述3.5.2

P、V操作原語(yǔ)4P（S）操作和V（S）操作的物理含義

（1）P（S）操作表示“等信號(hào)”，即測(cè)試一個(gè)要等的信號(hào)是否到達(dá)；（2）V（S）操作表示“發(fā)信號(hào)”。這個(gè)信號(hào)在實(shí)現(xiàn)同步時(shí)就是“合作者的伙伴進(jìn)程已完成前趨任務(wù)”，在實(shí)現(xiàn)互斥時(shí)就是“臨界資源可用”。3.5.2

P、V操作原語(yǔ)當(dāng)一進(jìn)程因在記錄型信號(hào)量S上執(zhí)行V()操作而導(dǎo)致喚醒另一進(jìn)程后,S的值為()。>0A<0B≥0C≤0D提交單選題1分5、P（S）操作和V（S）操作的物理含義

在互斥問(wèn)題中，每執(zhí)行一次P（S）操作的含義，也可理解為進(jìn)程請(qǐng)求一個(gè)單位的S類(lèi)資源；每執(zhí)行一次V（S）操作的含義，也可理解為進(jìn)程釋放一個(gè)單位的S類(lèi)資源。3.5.2

P、V操作原語(yǔ)如果信號(hào)量的當(dāng)前值為-4,則表示系統(tǒng)中在該信號(hào)量上有()個(gè)進(jìn)程等待。4A3B5C0D提交單選題1分3.5.3用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的互斥1、在相關(guān)進(jìn)程的臨界區(qū)的前后分別施以P操作和V操作即可。這里所用信號(hào)量的初值一般為1，表示臨界資源未被占用，且其可用數(shù)目為1。如果有三個(gè)進(jìn)程共享同一互斥段,而且每次最多允許兩個(gè)進(jìn)程進(jìn)入該互斥段,則信號(hào)量的初值應(yīng)設(shè)置為()。3A1B2C0D提交單選題1分2、優(yōu)勢(shì)

用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程互斥的效率更高，因?yàn)镻操作中引入了阻塞機(jī)制，互斥進(jìn)程之間有互相通信機(jī)制，所以消除了上鎖原語(yǔ)中的CPU忙等現(xiàn)象。3.5.3用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的互斥P(S)V(S)P(S)V(S)P(S)V(S)P1P2P3互斥區(qū)3.5.3用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的互斥課堂練習(xí)1、多個(gè)進(jìn)程對(duì)信號(hào)量S進(jìn)行了5次P操作，2次V操作后，現(xiàn)在信號(hào)量的值是

-3，與信號(hào)量S相關(guān)的處于阻塞狀態(tài)的進(jìn)程有幾個(gè)？信號(hào)量的初值是多少？2、有m個(gè)進(jìn)程共享同一臨界資源，若使用信號(hào)量機(jī)制實(shí)現(xiàn)對(duì)一臨界資源的互斥訪問(wèn)，則信號(hào)量的變化范圍是（

）。

例題

一個(gè)簡(jiǎn)化的異地售票程序，假設(shè)幾乎同時(shí)兩地有兩個(gè)乘客要購(gòu)買(mǎi)同一班次的車(chē)票各一張。

以上案例如果不加控制，會(huì)導(dǎo)致什么問(wèn)題？

3.5.3用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的互斥例3.1試用P、V操作實(shí)現(xiàn)火車(chē)聯(lián)網(wǎng)訂票系統(tǒng)中北京、天津兩地的兩個(gè)終端售票進(jìn)程發(fā)售同一班次車(chē)票的過(guò)程。

3.5.3用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的互斥用P、V原語(yǔ)控制進(jìn)程互斥與同步的主要步驟：（1）分析清楚題目涉及的進(jìn)程間的制約關(guān)系。（2）設(shè)置信號(hào)量（包括信號(hào)量的個(gè)數(shù)和初值，對(duì)于同步問(wèn)題還要寫(xiě)出信號(hào)量的物理含義）。（3）給出進(jìn)程相應(yīng)程序的算法描述或流程控制，并把P、V操作加到程序的適當(dāng)處。3.5.3用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的互斥北京售票終端進(jìn)程：

①根據(jù)顧客訂票要求找到公共數(shù)據(jù)單元PK；②P（S）；③把PK的值讀到工作寄存器R1中；④根據(jù)顧客訂票數(shù)修改R1；⑤將R1的值回寫(xiě)到PK中；⑥V（S）；⑦售出顧客所訂的票，返回；

天津售票終端進(jìn)程

①根據(jù)顧客訂票要求找到公共數(shù)據(jù)單元PK；②P（S）；③把PK的值讀到工作寄存器R2中；④根據(jù)顧客訂票數(shù)修改R2；⑤將R1的值回寫(xiě)到PK中；⑥V（S）；⑦售出顧客所訂的票，返回；3.6進(jìn)程的同步(synchronism)

——你等我，我也等你

多道程序系統(tǒng)中，許多進(jìn)程之間可能存在以下兩種制約關(guān)系：源于資源共享的間接制約關(guān)系（互斥）

源于合作相互的直接制約關(guān)系（同步）

——你等我，我也等你

1、進(jìn)程互斥與同步的關(guān)系

進(jìn)程同步是指多個(gè)合作進(jìn)程在獨(dú)自并發(fā)執(zhí)行過(guò)程中的某些確定的時(shí)序點(diǎn)上“你等我，我也等你”的同步約束，進(jìn)程互斥可視為進(jìn)程同步的特例。3.6進(jìn)程的同步(synchronism)3.6.1同步的定義

1、定義

指的是兩個(gè)或多個(gè)進(jìn)程為了合作完成同一個(gè)任務(wù)，在執(zhí)行速度或某些個(gè)確定的時(shí)序點(diǎn)上必須相互協(xié)調(diào)。

當(dāng)一個(gè)進(jìn)程到達(dá)了某一確定點(diǎn)而沒(méi)有得到合作伙伴發(fā)來(lái)的“已完成某些操作”的消息時(shí)必須等待，直到該消息到達(dá)被喚醒后，才能繼續(xù)向前推進(jìn)。（1）單向同步關(guān)系

進(jìn)程之間同步關(guān)系有時(shí)也被形象地稱(chēng)為“生產(chǎn)者與消費(fèi)者”之間的關(guān)系，“產(chǎn)品”（即生產(chǎn)者進(jìn)程的輸出，亦即消費(fèi)者進(jìn)程的輸入）是它們的紐帶，它們?cè)趫?zhí)行過(guò)程中的某個(gè)或某些確定的時(shí)序點(diǎn)上有著固定的前趨后繼的同步約束，即先“生產(chǎn)”后“消費(fèi)”，這是一種“你等我”的關(guān)系。2進(jìn)程同步關(guān)系分析3.6.1同步的定義（2）雙向同步關(guān)系（互為生產(chǎn)者與消費(fèi)者）在稍微復(fù)雜一點(diǎn)的進(jìn)程同步問(wèn)題里，合作進(jìn)程間的“生產(chǎn)者與消費(fèi)者”的關(guān)系或身份是可以經(jīng)常轉(zhuǎn)換的，因此，這些合作進(jìn)程在執(zhí)行過(guò)程中就會(huì)出現(xiàn)時(shí)而你等我，時(shí)而我等你的現(xiàn)象。

不管是單向或雙向同步關(guān)系，產(chǎn)品都是信號(hào)量。

2進(jìn)程同步關(guān)系分析3.6.1同步的定義（3）相似處

進(jìn)程的互斥實(shí)際上是進(jìn)程同步的一種特殊情況；進(jìn)程的互斥和同步可以都統(tǒng)稱(chēng)為進(jìn)程同步。2進(jìn)程同步關(guān)系分析3.6.1同步的定義（4）進(jìn)程同步與互斥區(qū)別進(jìn)程互斥是進(jìn)程間競(jìng)爭(zhēng)互斥資源的使用權(quán)，這種競(jìng)爭(zhēng)沒(méi)有固定的必然聯(lián)系，哪個(gè)進(jìn)程競(jìng)爭(zhēng)到使用權(quán)就歸那個(gè)進(jìn)程使用，直到不需要使用時(shí)再歸還；進(jìn)程同步是指多個(gè)進(jìn)程為了合作完成同一個(gè)任務(wù)，在執(zhí)行速度或某些個(gè)確定的時(shí)序點(diǎn)上必須相互協(xié)調(diào)，后面進(jìn)程的執(zhí)行需要前面運(yùn)行進(jìn)程的輸出。2進(jìn)程同步關(guān)系分析3.6.1同步的定義在操作系統(tǒng)中,有一組進(jìn)程,進(jìn)程之間具有直接相互制約性。這組并發(fā)進(jìn)程之間()。必定無(wú)關(guān)A必定相關(guān)B可能相關(guān)C相關(guān)程度相同D提交單選題1分1、P、V操作配對(duì)出現(xiàn)對(duì)同一個(gè)信號(hào)量的P、V操作不能同時(shí)出現(xiàn)在同一個(gè)進(jìn)程的程序里，而是分別出現(xiàn)在一個(gè)生產(chǎn)者進(jìn)程和它的合作伙伴—消費(fèi)者進(jìn)程的代碼中。

生產(chǎn)者生產(chǎn)產(chǎn)品之后執(zhí)行V操作，而消費(fèi)者在消費(fèi)產(chǎn)品之前用P操作。

3.6.2用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的同步2、P、V操作的出現(xiàn)位置在各個(gè)合作進(jìn)程中確定的時(shí)序點(diǎn)上。

生產(chǎn)者進(jìn)程在完成了前趨的生產(chǎn)任務(wù)后，應(yīng)立即給消費(fèi)者進(jìn)程發(fā)送一條“已完成前趨生產(chǎn)任務(wù)”的消息，執(zhí)行V操作；

后繼的消費(fèi)者進(jìn)程在消費(fèi)前，應(yīng)該執(zhí)行對(duì)同一個(gè)信號(hào)量的P操作，以測(cè)試其合作伙伴——生產(chǎn)者進(jìn)程“已完成前趨生產(chǎn)任務(wù)”的消息是否到來(lái)，如果到來(lái)就開(kāi)始消費(fèi)，否則就阻塞自己。3.6.2用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的同步3、解決進(jìn)程同步問(wèn)題的主要步驟

(1)分析題目涉及的進(jìn)程間的制約關(guān)系；(2)設(shè)置信號(hào)量（包括信號(hào)量的個(gè)數(shù)和初值及其物理含義），合作進(jìn)程間需要收發(fā)幾條消息相應(yīng)就設(shè)置幾個(gè)信號(hào)量；(3)給出進(jìn)程相應(yīng)程序的算法描述或流程控制，并把P、V操作加到程序的適當(dāng)處。3.6.2用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的同步＝》例3.2生產(chǎn)者——消費(fèi)者問(wèn)題

公用緩沖池，有n個(gè)緩沖區(qū)一組生產(chǎn)者生產(chǎn)產(chǎn)品一組消費(fèi)者取走產(chǎn)品3.6.2用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的同步4、生產(chǎn)者－消費(fèi)者問(wèn)題是相互合作進(jìn)程關(guān)系的一種抽象

輸入——計(jì)算——打印生產(chǎn)者消費(fèi)者生產(chǎn)者消費(fèi)者系統(tǒng)中使用資源的進(jìn)程——消費(fèi)者系統(tǒng)中釋放同類(lèi)資源的進(jìn)程——生產(chǎn)者3.6.2用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的同步5、生產(chǎn)者與消費(fèi)者進(jìn)程關(guān)系分析（1）生產(chǎn)者—消費(fèi)者之間的同步關(guān)系表現(xiàn)為：一旦緩沖池中所有緩沖區(qū)均裝滿(mǎn)產(chǎn)品時(shí)，生產(chǎn)者必須等待消費(fèi)者提供空緩沖區(qū)；一旦緩沖池中所有緩沖區(qū)全為空時(shí)，消費(fèi)者必須等待生產(chǎn)者提供滿(mǎn)緩沖區(qū)。

3.6.2用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的同步（2）生產(chǎn)者—消費(fèi)者之間還有互斥關(guān)系：由于緩沖池是臨界資源，所以任何進(jìn)程在對(duì)緩沖區(qū)進(jìn)行存取操作時(shí)都必須和其他進(jìn)程互斥進(jìn)行。5、生產(chǎn)者與消費(fèi)者進(jìn)程關(guān)系分析3.6.2用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的同步6、生產(chǎn)者與消費(fèi)者進(jìn)程同步與互斥實(shí)現(xiàn)（1）信號(hào)量設(shè)置

Ⅰ）同步信號(hào)量empty，初值為n，表示消費(fèi)者已把緩沖池中全部產(chǎn)品取走，有n個(gè)空緩沖區(qū)可用。

Ⅱ）同步信號(hào)量full，初值為0，表示生產(chǎn)者尚未把產(chǎn)品放入緩沖池，有0個(gè)滿(mǎn)緩沖區(qū)可用。

Ⅲ）互斥信號(hào)量mutex，初值為1，以保證同時(shí)只有一個(gè)進(jìn)程能夠進(jìn)入臨界區(qū)，訪問(wèn)緩沖池。3.6.2用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的同步生產(chǎn)者i

消費(fèi)者j生產(chǎn)出一產(chǎn)品；P（full）；P（empty）；P（mutex）；P（mutex）；從緩沖區(qū)取出一產(chǎn)品；將該產(chǎn)品放入緩沖區(qū)；V（mutex）；V（mutex）；V（empty）；V（full）；消費(fèi)該產(chǎn)品；

6、生產(chǎn)者與消費(fèi)者進(jìn)程同步與互斥實(shí)現(xiàn)3.6.2用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的同步如果將生產(chǎn)者的兩個(gè)P操作對(duì)調(diào)？生產(chǎn)者i消費(fèi)者j生產(chǎn)出一產(chǎn)品；P（full）；P（mutex）；P（mutex）；P（empty）；從緩沖區(qū)取出一產(chǎn)品；將該產(chǎn)品放入緩沖區(qū)；V（mutex）；V（mutex）；V（empty）；V（full）；消費(fèi)該產(chǎn)品；多個(gè)P操作的順序問(wèn)題？如果將消費(fèi)者的兩個(gè)P操作對(duì)調(diào)？生產(chǎn)者i

消費(fèi)者j生產(chǎn)出一產(chǎn)品；P（mutex）；P（empty）；P（full）；P（mutex）；從緩沖區(qū)取出一產(chǎn)品；將該產(chǎn)品放入緩沖區(qū)；V（mutex）；V（mutex）；V（empty）；V（full）；消費(fèi)該產(chǎn)品；分析P操作的順序（1）P操作的順序很重要，順序不當(dāng)會(huì)產(chǎn)生死鎖。Consumer：Producer：P(empty);P(mutex);oneunit-->buf;V(mutex);V(full);P(full);P(mutex);//進(jìn)入?yún)^(qū)oneunit<--buf;V(mutex);V(empty);//退出區(qū)分析P操作的順序（1）P操作的順序很重要，順序不當(dāng)會(huì)產(chǎn)生死鎖。當(dāng)full=0,mutex=1時(shí)，執(zhí)行順序：

Consumer.P(mutex);Consumer.P(full);//C阻塞，等待Producer發(fā)出的full信號(hào)

Producer.P(empty);Producer.P(mutex);//P阻塞，等待Consumer發(fā)出的mutex信號(hào)死鎖，還有其他的執(zhí)行序列可以產(chǎn)生死鎖嗎？如果一個(gè)進(jìn)程中有同步與互斥的P操作，通常將P（同步信號(hào)量）放在前面，而P（互斥信號(hào)量）放在后面。分析P操作的順序如果將兩個(gè)V操作對(duì)調(diào)？生產(chǎn)者i

消費(fèi)者j生產(chǎn)出一產(chǎn)品；P（full）；P（mutex）；P（mutex）；P（empty）；從緩沖區(qū)取出一產(chǎn)品；將該產(chǎn)品放入緩沖區(qū)；V（mutex）；V（full）；V（empty）；V（mutex）；消費(fèi)該產(chǎn)品；V操作如果有同步和互斥信號(hào)量時(shí)，順序可以隨意。

例3.3讀者——寫(xiě)者問(wèn)題1、問(wèn)題描述：（1）一組讀者與一組寫(xiě)者循環(huán)訪問(wèn)共享的同一個(gè)數(shù)據(jù)對(duì)象。（2）讀者：指能對(duì)共享數(shù)據(jù)對(duì)象讀的進(jìn)程，寫(xiě)者：指對(duì)共享數(shù)據(jù)對(duì)象只要求寫(xiě)的進(jìn)程。（3）規(guī)定：多個(gè)讀者可以同時(shí)讀這個(gè)數(shù)據(jù)對(duì)象，但決不允許多個(gè)寫(xiě)者同時(shí)對(duì)這個(gè)數(shù)據(jù)對(duì)象進(jìn)行寫(xiě)操作，也不允許讀者、寫(xiě)者同時(shí)訪問(wèn)這個(gè)數(shù)據(jù)對(duì)象。2問(wèn)題分析

讀者—寫(xiě)者問(wèn)題是共享數(shù)據(jù)對(duì)象的非合作進(jìn)程關(guān)系的一種抽象。（1）如文件管理模塊中讀文件、寫(xiě)文件等許多操作進(jìn)程之間（2）讀者—寫(xiě)者問(wèn)題是指保證一個(gè)寫(xiě)者進(jìn)程必須與其他寫(xiě)者或讀者進(jìn)程互斥地訪問(wèn)一個(gè)共享數(shù)據(jù)對(duì)象的同步問(wèn)題。

例3.3讀者——寫(xiě)者問(wèn)題3進(jìn)程互斥模型分析（1）讀者—寫(xiě)者之間的互斥關(guān)系

寫(xiě)者與寫(xiě)者的互斥、寫(xiě)者與讀者的互斥，設(shè)一個(gè)公用的初值為1的互斥信號(hào)量RW_mutex。

但是為了實(shí)現(xiàn)了讀者與讀者的共享資源，需引入一個(gè)讀者計(jì)數(shù)器變量RC，用于記錄讀者是否進(jìn)入資源，如沒(méi)有進(jìn)去，則需要互斥進(jìn)入資源，否則，可以隨意進(jìn)入，只需增加RC的值即可。

例3.3讀者——寫(xiě)者問(wèn)題（2）讀者—讀者之間的互斥關(guān)系

再設(shè)一個(gè)讀者公用的初值為1的互斥信號(hào)量R_mutex實(shí)現(xiàn)各個(gè)讀者間互斥的訪問(wèn)RC。3進(jìn)程互斥模型分析

例3.3讀者——寫(xiě)者問(wèn)題4讀者寫(xiě)者互斥模型的原語(yǔ)實(shí)現(xiàn)（1）所用信號(hào)量和其他變量設(shè)置如下：互斥信號(hào)量RW_mutex，初值為1，用于實(shí)現(xiàn)寫(xiě)者與其他寫(xiě)者或讀者互斥地訪問(wèn)共享的數(shù)據(jù)對(duì)象?；コ庑盘?hào)量R_mutex，初值為1，用于實(shí)現(xiàn)諸讀者互斥地訪問(wèn)讀者計(jì)數(shù)器變量。整型變量RC，初值為0，用于對(duì)讀者進(jìn)行記數(shù)。3.6.2用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的同步（2）用信號(hào)量機(jī)制解決讀者—寫(xiě)者問(wèn)題的算法描述如下：

讀者

寫(xiě)者P（R_mutex）；

P（RW_mutex）；若RC=0則P（RW_mutex）；對(duì)數(shù)據(jù)對(duì)象進(jìn)行寫(xiě)操作；RC加1；

V（RW_mutex）；V（R_mutex）；讀數(shù)據(jù)對(duì)象；P（R_mutex）；RC減1；若RC=0則V（RW_mutex）；

V（R_mutex）；4讀者寫(xiě)者互斥模型的原語(yǔ)實(shí)現(xiàn)例3.4試用用信號(hào)量機(jī)制描述兩人下象棋的過(guò)程1、問(wèn)題描述

兩人下象棋的過(guò)程可以概括為：一開(kāi)始只能是“紅先黑后”，以后兩人要循環(huán)輪流走子，直至某一方獲勝或雙方和棋為止。這是個(gè)只有一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者的生產(chǎn)者——消費(fèi)者問(wèn)題，是個(gè)典型的“你等我，我也等你”的問(wèn)題。紅方是總的前趨任務(wù)——生產(chǎn)者進(jìn)程，黑方是總的后繼任務(wù)——消費(fèi)者進(jìn)程，但由于下棋過(guò)程必須輪流走子，所以紅黑雙方的生產(chǎn)者消費(fèi)者身份會(huì)輪流改變。棋盤(pán)則是生產(chǎn)者與消費(fèi)者共享的緩沖。

2、二人對(duì)弈過(guò)程是的同步過(guò)程的原語(yǔ)實(shí)現(xiàn)（1）信號(hào)量設(shè)置如下同步信號(hào)量hong

，初值為1，表示黑方已走子,開(kāi)始時(shí)可使紅方先行不受阻。

同步信號(hào)量hei

，初值為0，表示紅方尚未走子，開(kāi)始時(shí)可使黑方先行受阻。3.6.2用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的同步進(jìn)程之間存在哪幾種相互制約關(guān)系？各是什么原因引起的？下列活動(dòng)分別屬于哪種制約關(guān)系？（1）若干同學(xué)去圖書(shū)館借書(shū)。（2）兩隊(duì)舉行籃球比賽。（3）流水線生產(chǎn)的各道工序。（4）商品生產(chǎn)和消費(fèi)。作答正常使用主觀題需2.0以上版本雨課堂可為此題添加文本、圖片、公式等解析，且需將內(nèi)容全部放在本區(qū)域內(nèi)。正常使用需3.0以上版本進(jìn)程間存在著兩種相互制約的關(guān)系：直接制約關(guān)系（即同步問(wèn)題）和間接制約關(guān)系（即互斥問(wèn)題）。同步問(wèn)題是存在邏輯關(guān)系的進(jìn)程之間相互等待產(chǎn)生的制約關(guān)系，互斥問(wèn)題是相互無(wú)邏輯關(guān)系的進(jìn)程間競(jìng)爭(zhēng)使用相同的資源所發(fā)生的制約關(guān)系。

（1）屬于互斥關(guān)系，因?yàn)闀?shū)的個(gè)數(shù)是有限的，一本書(shū)只能借給一個(gè)同學(xué)。

（2）屬于互斥關(guān)系，籃球只有一個(gè)，兩隊(duì)都要爭(zhēng)奪。

（3）屬于同步關(guān)系，各道工序的開(kāi)始都依賴(lài)前道工序的完成。

（4）屬于同步關(guān)系，商品沒(méi)生產(chǎn)出來(lái)，消費(fèi)無(wú)法進(jìn)行，商品未消費(fèi)完，生產(chǎn)也無(wú)需進(jìn)行。答案解析答案解析主觀題10分（2）用信號(hào)量機(jī)制描述的二人下象棋過(guò)程如下黑方：P（hei）；

若被紅方將死，則投子認(rèn)負(fù)，結(jié)束；若同意與紅方作和，則結(jié)束；否則，根據(jù)棋局思考后走一子；V（hong）；紅方：P（hong）；

若被黑方將死，則投子認(rèn)負(fù)，結(jié)束；若同意與黑方作和，則結(jié)束；否則，根據(jù)棋局思考后走一子；V（hei）；2、二人對(duì)弈過(guò)程是的同步過(guò)程的原語(yǔ)實(shí)現(xiàn)例3.5某小型超級(jí)市場(chǎng)，可容納50人同時(shí)購(gòu)物。入口處有籃子，每個(gè)購(gòu)物者可拿一只籃子入內(nèi)購(gòu)物。出口處結(jié)帳，并歸還籃子（出、入口禁止多人同時(shí)通過(guò)）。試用信號(hào)量和P、V操作寫(xiě)出購(gòu)物者的同步算法。這是個(gè)典型的進(jìn)程互斥問(wèn)題互斥經(jīng)典模型—超市模型P、V原語(yǔ)實(shí)現(xiàn)步驟1、所用信號(hào)量設(shè)置如下：（1）互斥信號(hào)量S，初值為50，用以保證最多可以有50個(gè)購(gòu)物者同時(shí)進(jìn)入超市。（2）互斥信號(hào)量mutex，初值為1，用以保證同時(shí)只能有一個(gè)購(gòu)物者進(jìn)程進(jìn)入出入口拿起籃子或者結(jié)帳后放下籃子。3.6.2用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的同步購(gòu)物者i進(jìn)程（解法一）P（S）；

P（mutex）；

從入口處進(jìn)超市，并取一只籃子；V（mutex）；進(jìn)超市內(nèi)選購(gòu)商品；P（mutex）到出口結(jié)帳，并歸還籃子；V（mutex）從出口離開(kāi)超市；V（S）；

↓結(jié)束.2、用購(gòu)物過(guò)程的算法描述如下購(gòu)物者i進(jìn)程（解法二）P（S）；

P（mutex1）；

從入口處進(jìn)超市，并取一只籃子；V（mutex1）；進(jìn)超市內(nèi)選購(gòu)商品；P（mutex2）到出口結(jié)帳，并歸還籃子；V（mutex2）從出口離開(kāi)超市；V（S）；

↓結(jié)束.2、用購(gòu)物過(guò)程的算法描述如下經(jīng)典模型—生產(chǎn)者與消費(fèi)者變形模型例3.6問(wèn)題描述：

桌上有個(gè)只能盛得下一個(gè)水果的空盤(pán)子。爸爸可向盤(pán)中放蘋(píng)果或桔子，兒子專(zhuān)等吃盤(pán)中的桔子，女兒專(zhuān)等吃盤(pán)中的蘋(píng)果。規(guī)定：當(dāng)盤(pán)子空時(shí)，一次只能放入一個(gè)水果供吃者取用。試用信號(hào)量和P、V操作實(shí)現(xiàn)爸爸、兒子和女兒這三個(gè)循環(huán)進(jìn)程之間的同步。本題屬于生產(chǎn)者——消費(fèi)者問(wèn)題模型的變形，相當(dāng)于一個(gè)能生產(chǎn)兩種產(chǎn)品的生產(chǎn)者（爸爸）向兩個(gè)消費(fèi)者（兒子和女兒）提供產(chǎn)品的同步問(wèn)題。因此，可參考生產(chǎn)者與消費(fèi)者問(wèn)題的解法。

2、問(wèn)題分析經(jīng)典模型—生產(chǎn)者與消費(fèi)者變形模型3用P、V原語(yǔ)實(shí)現(xiàn)同步（1）所用信號(hào)量設(shè)置如下

同步信號(hào)量empty，初值為1，表示盤(pán)子是空的，即兒子或女兒已把盤(pán)中的水果取走。

同步信號(hào)量orange，初值為0，表示爸爸尚未把桔子放入盤(pán)中同步信號(hào)量apple，初值為0，表示爸爸尚未把蘋(píng)果放入盤(pán)中

經(jīng)典模型—生產(chǎn)者與消費(fèi)者變形模型（2）使用信號(hào)量機(jī)制的三個(gè)進(jìn)程的同步描述如下

爸爸進(jìn)程（P）：兒子進(jìn)程（C1）：

女兒進(jìn)程（C2）：P（empty）；

P（orange）；

P（apple）；將水果放入盤(pán)中；

從盤(pán)中取出桔子；

從盤(pán)中取出蘋(píng)果；若放入的是桔子，

V（empty）；

V（empty）；則V（orange）；吃桔子；

吃蘋(píng)果；否則，V（apple)；3用P、V原語(yǔ)實(shí)現(xiàn)同步經(jīng)典模型—生產(chǎn)者與消費(fèi)者變形模型經(jīng)典模型-獨(dú)木橋模型（單向雙工）例3.7設(shè)A、B兩點(diǎn)之間是一段東西向的單行車(chē)道，現(xiàn)在要設(shè)計(jì)一個(gè)AB路段自動(dòng)管理系統(tǒng)，管理規(guī)則如下：當(dāng)AB間有車(chē)輛在行駛時(shí)同方向的車(chē)可以同時(shí)駛?cè)階B段，但另一方向的車(chē)必須在AB段外等待；當(dāng)AB段之間無(wú)車(chē)輛行駛時(shí)，到達(dá)AB段的任一方向的車(chē)都可進(jìn)入AB段，但不能從兩個(gè)方向同時(shí)駛?cè)?，即只能有一個(gè)方向的車(chē)駛?cè)?；?dāng)某方向在AB段行駛的車(chē)輛駛出了AB段且暫無(wú)車(chē)輛進(jìn)入AB段時(shí)，應(yīng)讓另一方向等待的車(chē)輛進(jìn)入AB段行駛。試用信號(hào)量和P、V操作管理AB路段車(chē)輛的行駛。

1、原語(yǔ)互斥實(shí)現(xiàn)步驟(1）所用信號(hào)量和其他變量設(shè)置如下Ⅰ）整型變量Car_A，初值為0，用于對(duì)從A點(diǎn)（東）駛?cè)階B段的車(chē)輛進(jìn)行記數(shù)。Ⅱ）整型變量Car_B，初值為0，用于對(duì)從B點(diǎn)（西）駛?cè)階B段的車(chē)輛進(jìn)行記數(shù)。Ⅲ）互斥信號(hào)量mutex，初值為1，

用于實(shí)現(xiàn)不同方向的第一輛車(chē)互斥駛?cè)階B路段。經(jīng)典模型-獨(dú)木橋模型（單向雙工）(1）所用信號(hào)量和其他變量設(shè)置如下Ⅳ）互斥信號(hào)量ma，初值為1，用于實(shí)現(xiàn)東西向的車(chē)互斥地訪問(wèn)計(jì)數(shù)器變量Car_A。Ⅴ）互斥信號(hào)量mb，初值為1，用于實(shí)現(xiàn)西東向的車(chē)互斥地訪問(wèn)計(jì)數(shù)器變量Car_B。2、原語(yǔ)互斥實(shí)現(xiàn)步驟經(jīng)典模型-獨(dú)木橋模型（單向雙工）通過(guò)AB路段向西行駛的車(chē)輛iP（ma）；

若Car_A=0則

P（mutex）；

Car_A加1；

V（ma）；

車(chē)輛從A點(diǎn)通過(guò)AB路段到達(dá)B點(diǎn)；P（ma）；

Car_A減1；

Car_A=0則

V（mutex）；V(ma)；（2）算法描述通過(guò)AB路段向東行駛的車(chē)輛jP（mb）；若Car_B=0則

P（mutex）；Car_B加1；V（mb）；車(chē)輛從B點(diǎn)通過(guò)AB路段到達(dá)A點(diǎn)P（mb）；Car_B減1；

Car_B=0則V(mutex)；V（mb）；3.8哲學(xué)家進(jìn)餐問(wèn)題（信號(hào)量聯(lián)合問(wèn)題）（1）問(wèn)題描述五個(gè)哲學(xué)家一生都在思考和進(jìn)餐中度過(guò)，他們圍坐在一個(gè)圓桌周?chē)?，每人面前放了一份美味的餐點(diǎn)，兩份相鄰的餐盤(pán)中間都放了一根筷子，哲學(xué)家需要把自己左右兩側(cè)的兩個(gè)筷子分別拿起才能進(jìn)餐。哲學(xué)家的行為模式就是平時(shí)思考，餓了就分別拿起兩側(cè)的筷子，若兩次都能成功，即獲得了兩根筷子時(shí)，該哲學(xué)家就可以進(jìn)餐了。當(dāng)他吃飽后，為了不讓其他人挨餓，需要馬上將兩根筷子分別放下，注意，這里并沒(méi)有對(duì)拿起和放下筷子的次序做強(qiáng)制規(guī)定。例3.8哲學(xué)家進(jìn)餐問(wèn)題2、問(wèn)題分析（1）一種最直接的解法是強(qiáng)制每個(gè)哲學(xué)家都先拿起左邊的筷子，成功后再去拿起右邊的筷子。（2）缺點(diǎn)是可能會(huì)產(chǎn)生嚴(yán)重的“饑餓”現(xiàn)象。若五個(gè)哲學(xué)家同時(shí)拿起左筷子，此時(shí)桌子上沒(méi)有一根未用的筷子，每個(gè)哲學(xué)家都在等待其右邊的鄰居進(jìn)餐完畢后釋放筷子給自己。那么所有的哲學(xué)家將僵持并永久等待下去，導(dǎo)致長(zhǎng)期饑餓。例3.9理發(fā)師問(wèn)題1、問(wèn)題描述：在理發(fā)店中有一位理發(fā)師、一把理發(fā)椅和n把供顧客等待的等待位。若沒(méi)有顧客，理發(fā)師便在理發(fā)椅上睡覺(jué)。當(dāng)?shù)谝粋€(gè)顧客到來(lái)時(shí)，他必須先叫醒理發(fā)師為其服務(wù)。當(dāng)理發(fā)師正在為顧客服務(wù)時(shí)，新到來(lái)的顧客將查看是否有空閑的等待位，若有就坐下等待，若無(wú)就離開(kāi)理發(fā)店。理發(fā)師在為當(dāng)前顧客服務(wù)完時(shí)要查看是否有等待的顧客，若有就繼續(xù)服務(wù)，若無(wú)就馬上睡去。2、問(wèn)題分析與解決（1）設(shè)置三個(gè)信號(hào)量customers，用來(lái)記錄等待理發(fā)的顧客數(shù)(不包括正在理發(fā)的顧客)；barbers，記錄正在等候顧客的理發(fā)師數(shù)，其值應(yīng)為0或1，如果有多個(gè)理發(fā)師，則值可設(shè)為n；3.9理發(fā)師問(wèn)題2、問(wèn)題分析與解決（1）設(shè)置三個(gè)信號(hào)量此外還應(yīng)設(shè)置一個(gè)變量waiting，它也是記錄等待的顧客數(shù)，是customers的一個(gè)副本。設(shè)置waiting的原因是customers是一個(gè)信號(hào)量，無(wú)法修改其自己的當(dāng)前值。當(dāng)一個(gè)顧客進(jìn)入理發(fā)店后，首先做的就是檢查等候的顧客數(shù)量waiting，若該數(shù)量少于等待位數(shù)，顧客坐下等待，否則離開(kāi)；mutex，用于理發(fā)師和顧客互斥訪問(wèn)waiting值。3.9理發(fā)師問(wèn)題3.9理發(fā)師問(wèn)題P、V原語(yǔ)實(shí)現(xiàn)進(jìn)程同步與互斥的實(shí)質(zhì)實(shí)現(xiàn)進(jìn)程的同步互斥實(shí)際就是給進(jìn)程的并發(fā)執(zhí)行增加一定的限制，以保證被訪問(wèn)的共享數(shù)據(jù)的完整性和進(jìn)程執(zhí)行結(jié)果的可再現(xiàn)性。1、用信號(hào)量機(jī)制解進(jìn)程同步與互斥的三個(gè)步驟（1）分析進(jìn)程間的制約關(guān)系（2）設(shè)置信號(hào)量（3）實(shí)施P、V操作。

第一步是基礎(chǔ)、關(guān)鍵，第三步是核心。P、V原語(yǔ)實(shí)現(xiàn)進(jìn)程同步與互斥的實(shí)現(xiàn)總結(jié)三個(gè)進(jìn)程P1、P2、P3互斥使用一個(gè)包含N（N>0）個(gè)單元的緩沖區(qū)。P1每次用produce（）生成一個(gè)正整數(shù)并用put（）送入緩沖區(qū)某一空單元中；P2每次用getodd（）從該緩沖區(qū)中取出一個(gè)奇數(shù)并用countodd（）統(tǒng)計(jì)奇數(shù)個(gè)數(shù)；P3每次用geteven（）從該緩沖區(qū)中取出一個(gè)偶數(shù)并用counteven（）統(tǒng)計(jì)偶數(shù)個(gè)數(shù)。請(qǐng)用信號(hào)量機(jī)制實(shí)現(xiàn)這三個(gè)進(jìn)程的同步與互斥活動(dòng)，并說(shuō)明所定義的信號(hào)量的含義。要求用偽代碼描述。

作答正常使用主觀題需2.0以上版本雨課堂可為此題添加文本、圖片、公式等解析，且需將內(nèi)容全部放在本區(qū)域內(nèi)。正常使用需3.0以上版本定義資源信號(hào)量empty、even、odd，用于控制生產(chǎn)者與消費(fèi)者之間的同步，其中，empty表示空緩沖區(qū)的數(shù)目，even表示緩沖區(qū)中偶數(shù)的個(gè)數(shù)，odd表示緩沖區(qū)中奇數(shù)的個(gè)數(shù)；

定義互斥信號(hào)量mutex，用于實(shí)現(xiàn)進(jìn)程對(duì)緩沖區(qū)的互斥訪問(wèn)。semahporeempty=N,even=0,odd=0,mutex=1;答案解析答案解析主觀題10分（1）相同點(diǎn)：P、V操作總是配對(duì)出現(xiàn)的。（2）不同點(diǎn)P、V在互斥問(wèn)題中總是出現(xiàn)在同一個(gè)進(jìn)程的代碼中，且緊緊夾著臨界區(qū)；在同步問(wèn)題中，卻是分別出現(xiàn)在兩個(gè)合作進(jìn)程的代碼中，需要等消息的一方用P操作，相應(yīng)的對(duì)同一信號(hào)量的V操作則在發(fā)出此消息的另一方中。2、進(jìn)程同步與互斥在P、V形式上的異同P、V原語(yǔ)實(shí)現(xiàn)進(jìn)程同步與互斥的實(shí)現(xiàn)總結(jié)互斥與同步習(xí)題和解決1、有兩個(gè)用戶(hù)進(jìn)程A和B，在運(yùn)行過(guò)程中都要使用系統(tǒng)中的一臺(tái)打印機(jī)輸出計(jì)算結(jié)果。試說(shuō)明A、B兩進(jìn)程之間存在什么樣的制約關(guān)系？為保證這兩個(gè)進(jìn)程能正確地打印出各自的結(jié)果，請(qǐng)用信號(hào)量和P、V操作寫(xiě)出各自的有關(guān)申請(qǐng)、使用打印機(jī)的代碼。要求給出信號(hào)量的含義和初值。解：

(1)A、B兩進(jìn)程之間存在互斥的制約關(guān)系。因?yàn)榇蛴C(jī)屬于臨界資源，必須一個(gè)進(jìn)程使用完之后另一個(gè)進(jìn)程才能使用?；コ馀c同步習(xí)題和解決（2）mutex：用于互斥的信號(hào)量，初值為1。進(jìn)程A

進(jìn)程B...

…P(mutex)

P(mutex)

申請(qǐng)打印機(jī)

申請(qǐng)打印機(jī)使用打印機(jī)

使用打印機(jī)

V(mutex)

V(mutex)

…

…

互斥與同步習(xí)題和解決2、有一個(gè)閱覽室，共有100個(gè)座位，讀者進(jìn)入時(shí)必須先在一張登記表上登記，該表為每一座位列一表目，包括座號(hào)和讀者姓名等，讀者離開(kāi)時(shí)要消掉登記的信息，試問(wèn)：

（1）為描述讀者的動(dòng)作，應(yīng)編寫(xiě)幾個(gè)程序，設(shè)置幾個(gè)進(jìn)程？

（2）試用PV操作描述讀者進(jìn)程之間的同步關(guān)系?；コ馀c同步例題讀者的動(dòng)作都是一樣的：登記進(jìn)入閱覽室，閱讀，撤消登記離開(kāi)閱覽室，因此可寫(xiě)一個(gè)程序，設(shè)n(n≥100)個(gè)進(jìn)程。分析讀者共享的資源有閱覽室的座位和登記表，因此諸個(gè)讀者進(jìn)程之間有兩種互斥制約關(guān)系，需設(shè)2個(gè)信號(hào)量來(lái)實(shí)現(xiàn)：seat：用于實(shí)現(xiàn)諸讀者對(duì)閱覽室的空閑座位的互斥競(jìng)爭(zhēng)，初值為100；mutex：用于實(shí)現(xiàn)諸讀者對(duì)登記表的互斥訪問(wèn)，初值為1。

分析解：(1)可寫(xiě)一個(gè)程序，設(shè)n(n≥100)個(gè)進(jìn)程

(2)讀者進(jìn)程readeri(i=1,2,3,……)描述如下：P（seat）;

/*申請(qǐng)空座位*/

P（mutex）;

/*申請(qǐng)登記*/

登記；

V（mutex）

/*允許其他讀者登記*/

閱讀；

P（mutex）;

/*申請(qǐng)撤消登記*/

撤消登記；

V（mutex）；

/*允許其他讀者撤消登記*/V（seat）；

/*釋放座位，允許他人進(jìn)入*/互斥與同步例題有一個(gè)倉(cāng)庫(kù)可以存放A、B兩種物品，每次只能存入一件物品（A或B）。存儲(chǔ)空間足夠大，只是要求–n<(A的件數(shù)–B的件數(shù))<m,其中n和m是正整數(shù)。試用存入A、存入B和P、V操作，描述物品A和物品B的入庫(kù)過(guò)程。作答正常使用主觀題需2.0以上版本雨課堂主觀題10分今有三個(gè)并發(fā)進(jìn)程R，M，P，它們共享了一個(gè)可循環(huán)使用的緩沖區(qū)B，緩沖區(qū)B共有N個(gè)單元。進(jìn)程R負(fù)責(zé)從輸入設(shè)備讀信息，每讀一個(gè)字符后，把它存放在緩沖區(qū)B的一個(gè)單元中；進(jìn)程M負(fù)責(zé)處理讀入的字符，若發(fā)現(xiàn)讀入的字符中有空格符，則把它改成“，”；進(jìn)程P負(fù)責(zé)把處理后的字符取出并打印輸出。當(dāng)緩沖區(qū)單元中的字符被進(jìn)程P取出后，則又可用來(lái)存放下一次讀入的字符。請(qǐng)用PV操作為同步機(jī)制寫(xiě)出它們能正確并發(fā)執(zhí)行的程序。作答正常使用主觀題需2.0以上版本雨課堂主觀題10分[課堂作業(yè)]1、用P.V操作解決司機(jī)與售票員的問(wèn)題2、用P.V操作解決下圖之同步問(wèn)題:getcopyputfstg思考與作業(yè)3、寫(xiě)出下列進(jìn)程趨勢(shì)圖中各進(jìn)程之間同步關(guān)系S1S4S2S3S5S6

3.7進(jìn)程通信(communication)3.7.1進(jìn)程通信方式3.7.2消息緩沖機(jī)制3.7.3郵箱通信3.7.4進(jìn)程通信實(shí)例－管道1、簡(jiǎn)介（1）進(jìn)程之間的信息交換稱(chēng)為進(jìn)程通信。（2）合作進(jìn)程間所交換的信息量，少則是一個(gè)狀態(tài)或數(shù)據(jù)，多則成千上萬(wàn)字節(jié)的。（3）按通信所交換的數(shù)據(jù)量多少進(jìn)程通信分為低級(jí)和高級(jí)兩種方式。

3.7.1進(jìn)程通信方式低級(jí)通信高級(jí)通信2、通信方式劃分（1）按照通信量大小劃分

3.7.1進(jìn)程通信方式低級(jí)通信：在進(jìn)程間交換數(shù)據(jù)量少的進(jìn)程通信方式。一般只傳送一個(gè)和幾個(gè)字節(jié)的信息，達(dá)到控制進(jìn)程執(zhí)行速度的作用（例如進(jìn)程的同步與互斥）。信號(hào)量機(jī)制就是一種低級(jí)通信方式，它作為同步工具是卓有成效的，但作為通信工具則不夠理想。2、通信方式劃分（1）按照通信量大小劃分

3.7.1進(jìn)程通信方式低級(jí)通信：在進(jìn)程間交換數(shù)據(jù)量少的進(jìn)程通信方式。缺點(diǎn)：傳輸效率低；通信對(duì)用戶(hù)不透明2、通信方式劃分（1）按照通信量大小劃分

3.7.1進(jìn)程通信方式高級(jí)通信

用戶(hù)可以直接利用操作系統(tǒng)所提供的一組通信命令，高效地傳送大量數(shù)據(jù)的一種通信方式。優(yōu)點(diǎn)：傳輸效率高。通信過(guò)程對(duì)用戶(hù)是透明的2、通信方式劃分（1）按照通信量大小劃分

3.7.1進(jìn)程通信方式=>共享存儲(chǔ)器系統(tǒng)包括共享內(nèi)存變量（如信號(hào)量機(jī)制）和共享內(nèi)存區(qū)兩種通信方式。=>消息傳遞系統(tǒng)包括消息緩沖和信箱兩種通信方式。=>管道通信方式2、通信方式劃分（2）根據(jù)通信實(shí)施的方式和數(shù)據(jù)存取的方式

3.7.1進(jìn)程通信方式3.7.2高級(jí)通信方式主從式會(huì)話式消息或郵箱機(jī)制共享存儲(chǔ)區(qū)方式1、主從式通信方式（1）特點(diǎn)：主進(jìn)程可以自由使用從進(jìn)程資源或數(shù)據(jù)從進(jìn)程的動(dòng)作受到主進(jìn)程的控制主進(jìn)程和從進(jìn)程的關(guān)系固定（2）典型例子：終端控制進(jìn)程和終端進(jìn)程3.7.2高級(jí)通信方式2、會(huì)話式通信方式定義：通信進(jìn)程雙方成為使用進(jìn)程和服務(wù)進(jìn)程，使用進(jìn)程調(diào)用服務(wù)進(jìn)程提供的服務(wù)兩進(jìn)程在通信時(shí)有固定連接關(guān)系典型案例用戶(hù)進(jìn)程和磁盤(pán)管理進(jìn)程通信3.7.2高級(jí)通信方式3、消息或郵箱機(jī)制（1）消息：表示通信進(jìn)程之間大信息量的交換（2）消息組成：發(fā)送進(jìn)程名、接受進(jìn)程名、數(shù)據(jù)和有關(guān)數(shù)據(jù)操作圖3.16消息的組成3.7.2高級(jí)通信方式（3）通信特點(diǎn)只要存在空緩沖區(qū)或郵箱，發(fā)送進(jìn)程就可以通信發(fā)送進(jìn)程與接收進(jìn)程沒(méi)有直接連接關(guān)系，接收進(jìn)程可以接受多個(gè)發(fā)送進(jìn)程消息3、消息或郵箱機(jī)制3.7.2高級(jí)通信方式（3）通信特點(diǎn)發(fā)送和接收進(jìn)程之間存在緩沖區(qū)或郵箱用來(lái)存放被傳送消息圖3.17緩沖區(qū)或郵箱通信結(jié)構(gòu)3、消息或郵箱機(jī)制3.7.2高級(jí)通信方式4、共享存儲(chǔ)區(qū)通信（1）特點(diǎn)通信進(jìn)程之間交互信息時(shí)通過(guò)對(duì)同一共享數(shù)據(jù)區(qū)的操作達(dá)到通信目的，共享區(qū)屬于每一進(jìn)程在通信中不需要移動(dòng)數(shù)據(jù)。3.7.2高級(jí)通信方式3.7.3消息緩沖機(jī)制1、發(fā)送進(jìn)程：在自己內(nèi)存空間設(shè)置發(fā)送緩沖區(qū)，把欲發(fā)送消息填入其中，最后使用發(fā)送進(jìn)程將消息發(fā)送出去2、接收進(jìn)程：在自己的內(nèi)存中設(shè)置相應(yīng)的接收區(qū)，再調(diào)用接受進(jìn)程接受消息3、特點(diǎn)：（1）發(fā)送進(jìn)程和接收進(jìn)程使用不同的緩沖區(qū)用來(lái)存放和發(fā)送消息（2）發(fā)送進(jìn)程建立消息存儲(chǔ)區(qū)，接收進(jìn)程建立消息接收區(qū)3.7.3消息緩沖機(jī)制3、特點(diǎn)：（3）發(fā)送進(jìn)程與接收進(jìn)程不用共享數(shù)據(jù)緩沖區(qū)，因此不存在互斥問(wèn)題，只要各自緩沖區(qū)有資源即可（4）發(fā)送進(jìn)程必須告訴接受進(jìn)程消息已經(jīng)發(fā)出，所以?xún)烧咧g存在同步關(guān)系3.7.3消息緩沖機(jī)制4、消息緩沖機(jī)制正常通信條件在發(fā)送進(jìn)程把消息寫(xiě)入緩沖區(qū)和把緩沖區(qū)掛入消息隊(duì)列時(shí)，應(yīng)禁止其他進(jìn)程對(duì)該緩沖區(qū)消息隊(duì)列的訪問(wèn)；同理，接收進(jìn)程正從消息隊(duì)列中取消息時(shí)，也應(yīng)禁止其他進(jìn)程對(duì)該隊(duì)列的訪問(wèn)；接收緩沖區(qū)消息隊(duì)列無(wú)消息時(shí)，接收進(jìn)程不能接受任何消息3.7.3消息緩沖機(jī)制PCB......Send(R,M)......SIZE:消息長(zhǎng)度TEXT:消息正文......消息鏈指針............Receive(pid,N)......SIZE:消息長(zhǎng)度TEXT:消息正文......M:N:接受進(jìn)程R發(fā)送進(jìn)程S消息消息消息......5消息緩沖通信模型3.7.4郵箱通信1定義：發(fā)送進(jìn)程申請(qǐng)建立一與接收進(jìn)程鏈接的郵箱2特點(diǎn)發(fā)送進(jìn)程將消息發(fā)送給郵箱，接收進(jìn)程取出郵箱中消息郵箱作為發(fā)送進(jìn)程和接收進(jìn)程共有的私有數(shù)據(jù)結(jié)構(gòu)，在互斥的條件下可以實(shí)現(xiàn)通信問(wèn)題：如何實(shí)現(xiàn)發(fā)送進(jìn)程與接受進(jìn)程的制約關(guān)系？3.7.4郵箱通信3進(jìn)程之間正常通信應(yīng)滿(mǎn)足條件：發(fā)送進(jìn)程發(fā)送消息時(shí)，郵箱中至少有一個(gè)空格能存放消息接收進(jìn)程接收消息時(shí)，郵箱中至少有一個(gè)消息存在3.7.4郵箱通信4郵箱通信結(jié)構(gòu)圖圖3.18郵箱通信結(jié)構(gòu)3.7.4郵箱通信3.7.4郵箱通信3.7.5管道(pipe)1、管道是一條在進(jìn)程間以字節(jié)流方式傳送的通信通道。2、它由OS核心的緩沖區(qū)（通常幾十KB）來(lái)實(shí)現(xiàn)，是單向的；常用于命令行所指定的輸入輸出重定向和管道命令。（先進(jìn)先出的，一個(gè)進(jìn)程寫(xiě)，一個(gè)進(jìn)程讀）3、在使用管道前要建立相應(yīng)的管道，然后才可使用。4、管道機(jī)制中的同步與互斥管道機(jī)制必須提供三方面的協(xié)調(diào)努力：互斥：當(dāng)一個(gè)進(jìn)程正在對(duì)PIPE進(jìn)行讀寫(xiě)時(shí)，另一個(gè)必須等待（一次只有一個(gè)進(jìn)程可以訪問(wèn)）同步：當(dāng)寫(xiě)進(jìn)程把一定量的數(shù)據(jù)（如4KB）寫(xiě)入PIPE后（創(chuàng)建后，大小是固定字節(jié)的），便睡眠等待，直到讀進(jìn)程取走數(shù)據(jù)后再喚醒它；當(dāng)讀進(jìn)程讀一個(gè)空PIPE時(shí)，也應(yīng)睡眠等待，直到寫(xiě)進(jìn)程將消息寫(xiě)入管道為止，才將它喚醒。3.7.5管道(pipe)4、管道機(jī)制中的同步與互斥管道機(jī)制必須提供三方面的協(xié)調(diào)努力：對(duì)方是否存在。只有已確定對(duì)方存在時(shí)，方能進(jìn)行通信。3.7.5管道(pipe)5.UNIX管道（1）通過(guò)pipe系統(tǒng)調(diào)用創(chuàng)建無(wú)名管道，得到兩個(gè)文件描述符，分別用于寫(xiě)和讀。intpipe(intfildes[2]);文件描述符fildes[0]為讀端，fildes[1]為寫(xiě)端；通過(guò)系統(tǒng)調(diào)用write和read進(jìn)行管道的寫(xiě)和讀；3.7.5管道(pipe)5.UNIX管道通過(guò)pipe系統(tǒng)調(diào)用創(chuàng)建無(wú)名管道，得到兩個(gè)文件描述符，分別用于寫(xiě)和讀。進(jìn)程間雙向通信，通常需要兩個(gè)管道；只適用于父子進(jìn)程之間或父進(jìn)程安排的各個(gè)子進(jìn)程之間（只有相關(guān)進(jìn)程可以共享無(wú)名管道）；3.7.5管道(pipe)命名管道服務(wù)器支持多客戶(hù)：為每個(gè)管道實(shí)例建立單獨(dú)線程或進(jìn)程。（1）CreateNamedPipe在服務(wù)器端創(chuàng)建并返回一個(gè)命名管道句柄；（2）ConnectNamedPipe在服務(wù)器端等待客戶(hù)進(jìn)程的請(qǐng)求；6.Windows管道3.7.5管道(pipe)（3）CallNamedPipe從管道客戶(hù)進(jìn)程建立與服務(wù)器的管道連接；（4）ReadFile、WriteFile（用于阻塞方式）、ReadFileEx、WriteFileEx（用于非阻塞方式）用于命名管道的讀寫(xiě)；6.Windows管道3.7.5管道(pipe)圖3.21管道通信7.UNIX管道編程3.7.5管道(pipe)例1：用c語(yǔ)言編寫(xiě)一個(gè)程序，建立一個(gè)管道pipe，同時(shí)父進(jìn)程生成一個(gè)子進(jìn)程，子進(jìn)程向pipe中寫(xiě)入一個(gè)字符串，父進(jìn)程從pipe中讀取該字符串7.UNIX管道編程7.UNIX管道編程例2：編寫(xiě)一程序，建立一個(gè)管道。同時(shí)，父進(jìn)程生成子進(jìn)程P1，P2，這兩個(gè)子進(jìn)程分別向管道寫(xiě)入各自的字符串，父進(jìn)程讀出他們。圖3.22父進(jìn)程和子進(jìn)程P1，P2通信例子7.UNIX管道編程3.8死鎖問(wèn)題——你不讓?zhuān)乙膊蛔?/p>

在多道程序系統(tǒng)中，多個(gè)進(jìn)程并發(fā)運(yùn)行，共享資源，從而提高了資源的利用率。但是若對(duì)資源的管理和使用不當(dāng)，在一定條件下會(huì)導(dǎo)致系統(tǒng)發(fā)生一種隨機(jī)性故障――死鎖。在一些系統(tǒng)中，比如實(shí)時(shí)控制系統(tǒng)，系統(tǒng)一旦發(fā)生死鎖將導(dǎo)致災(zāi)難性的后果。死鎖問(wèn)題是E.W.Dijkstra在1965年研究銀行家算法時(shí)首次提出的，以后又由Havender、Lyach等人研究并發(fā)展。3.8.1.死鎖的定義1、相關(guān)概念

（1）死鎖（Deadlock）：是指兩個(gè)或兩個(gè)以上的進(jìn)程在執(zhí)行過(guò)程中，因爭(zhēng)奪資源而造成的一種互相等待的現(xiàn)象，若無(wú)外力作用，它們都將無(wú)法推進(jìn)下去。稱(chēng)此時(shí)系統(tǒng)處于死鎖狀態(tài)或系統(tǒng)產(chǎn)生了死鎖。3.8.1.死鎖的定義1、概念（2）死鎖進(jìn)程

這些永遠(yuǎn)在互相等待的進(jìn)程為死鎖進(jìn)程。（3）死鎖后果

所占用的資源或者需要它們進(jìn)行某種合作的其它進(jìn)程就會(huì)相繼陷入死鎖，最終可能導(dǎo)致整個(gè)系統(tǒng)處于癱瘓狀態(tài)。

2、死鎖原因計(jì)算機(jī)系統(tǒng)中，如果系統(tǒng)的資源分配策略不當(dāng)，或者更常見(jiàn)的是程序員寫(xiě)的程序有錯(cuò)誤等，則會(huì)導(dǎo)致進(jìn)程因競(jìng)爭(zhēng)資源不當(dāng)（往往與進(jìn)程的推進(jìn)速度有關(guān)）而產(chǎn)生死鎖的現(xiàn)象。

3.8.1死鎖的定義3、死鎖案例（1）文件打印

將一個(gè)大文件由磁帶拷貝至打印機(jī)，進(jìn)程需要同時(shí)訪問(wèn)磁帶驅(qū)動(dòng)器和打印機(jī)，并且不允許其他進(jìn)程這時(shí)訪問(wèn)它們。在只有一個(gè)進(jìn)程的系統(tǒng)中，該進(jìn)程可以要求任何它所需要的資源，然后進(jìn)行工作。但是，在一個(gè)多道程序系統(tǒng)中，就有可能出現(xiàn)嚴(yán)重的問(wèn)題。3.8.1死鎖的定義A、B兩個(gè)進(jìn)程準(zhǔn)備打印一個(gè)大的磁帶文件ABR1R2打印機(jī)磁帶機(jī)3、死鎖案例（1）文件打印3.8.1死鎖的定義（2）哲學(xué)家就餐問(wèn)題有5個(gè)哲學(xué)家，圍坐在圓桌旁，他們的生活方式是交替地進(jìn)行思考和進(jìn)餐；圓桌上間隔地?cái)[放著5把叉子和5個(gè)裝有通心粉的盤(pán)子，規(guī)定第i號(hào)哲學(xué)家固定坐在第i把椅子上（i=0,1,2,3,4），且每個(gè)哲學(xué)家必須兩手分別拿起他左右兩旁的那兩把叉子，才能吃通心粉；假定通心粉的數(shù)量足夠5個(gè)哲學(xué)家用的。3、死鎖案例

假設(shè)這5把叉子與椅子相應(yīng)也按逆時(shí)針?lè)较驈?開(kāi)始連續(xù)編號(hào)，即第i號(hào)哲學(xué)家左邊擺著第i號(hào)叉子，右邊擺著第((i+1)mod5)號(hào)叉子，這里的mod代表模運(yùn)算，即整除取余。顯然，在這個(gè)問(wèn)題中叉子是哲學(xué)家進(jìn)餐競(jìng)爭(zhēng)的臨界資源，5把叉子應(yīng)分別用一個(gè)初值為1的信號(hào)量表示，這5個(gè)信號(hào)量構(gòu)成一個(gè)信號(hào)量數(shù)組S。（2）哲學(xué)家就餐問(wèn)題3、死鎖案例則第i號(hào)哲學(xué)家的進(jìn)餐過(guò)程描述如下哲學(xué)家（i＝0，1，2，3，4）思考；P(S[i]);拿起左邊的叉子；P(S[(i＋1)mod5])；拿起右邊的叉子；吃通心粉；放下左邊的叉子；V(S[i]);放下右邊的叉子；V(S[(i＋1)mod5])；（該算法可能會(huì)死鎖）

死鎖經(jīng)典案例—哲學(xué)家就餐問(wèn)題

解決死鎖方法1：使用互斥信號(hào)量哲學(xué)家（i＝0，1，2，3，4）思考；P(mutex);P(S[i]);拿起左邊的叉子；P(S[i＋1]mod5)；拿起右邊的叉子；吃通心粉；放下左邊的叉子；V(S[i]);放下右邊的叉子；V(S[i＋1]mod5)；V(mutex)死鎖經(jīng)典案例—哲學(xué)家就餐問(wèn)題有何缺點(diǎn)解決死鎖方法2：AND型信號(hào)量機(jī)制AND同步機(jī)制的基本思想是：將進(jìn)程在整個(gè)運(yùn)行過(guò)程中需要的所有資源，一次性全部地分配給進(jìn)程，等到進(jìn)程使用完畢后再一起釋放。也就是說(shuō)，對(duì)若干個(gè)臨界資源的分配，采取原子操作的方式：要么全部分配給進(jìn)程，要么一個(gè)也不分配。由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。聯(lián)合型信號(hào)量機(jī)制就是采用臨界資源的靜態(tài)分配用于解決死鎖問(wèn)題。哲學(xué)家（i＝0，1，2，3，4）思考；P(S[i]andS[i＋1]mod5)；拿起左邊的叉子；拿起右邊的叉子；吃通心粉；放下左邊的叉子；V(S[i]);放下右邊的叉子；V(S[i＋1]mod5)；//臨界資源的全部分配解決死鎖方法2：AND型信號(hào)量機(jī)制（1）競(jìng)爭(zhēng)臨界資源當(dāng)系統(tǒng)中供多個(gè)進(jìn)程共享的臨界資源（如打印機(jī)、公用隊(duì)列等）的數(shù)目不能滿(mǎn)足諸進(jìn)程的需要時(shí)，會(huì)引起諸進(jìn)程對(duì)資源的競(jìng)爭(zhēng)而產(chǎn)生死鎖。這個(gè)問(wèn)題在多道程序系統(tǒng)中是無(wú)法避免的。3.8.2產(chǎn)生死鎖的原因（2）進(jìn)程推進(jìn)順序不當(dāng)

進(jìn)程在運(yùn)行過(guò)程中，請(qǐng)求和釋放臨界資源的順序不當(dāng)，也同樣會(huì)導(dǎo)致死鎖的產(chǎn)生。這個(gè)問(wèn)題在多道程序系統(tǒng)中是可以解決的。（解決死鎖主要圍繞該問(wèn)題展開(kāi)）3.8.2產(chǎn)生死鎖的原因造成死鎖的原因是()。內(nèi)存容量太小A系統(tǒng)進(jìn)程數(shù)量太多,系統(tǒng)資源分配不當(dāng)BCPU速度太慢C進(jìn)程推進(jìn)順序不合適D外存容量太小E提交多選題1分兩個(gè)進(jìn)程爭(zhēng)奪同一個(gè)資源()。一定死鎖A不一定死鎖B不死鎖C以上說(shuō)法都不對(duì)D提交單選題1分一、競(jìng)爭(zhēng)資源引起死鎖

1．資源的分類(lèi)：可剝奪和非剝奪性資源

可剝奪性資源：CPU和主存

不可剝奪性資源：磁帶機(jī)、打印機(jī)等當(dāng)系統(tǒng)把這類(lèi)資源分配給某進(jìn)程后，再不能強(qiáng)行收回，只能在進(jìn)程用完后自動(dòng)釋放。2．競(jìng)爭(zhēng)非剝奪性資源

兩個(gè)進(jìn)程分別準(zhǔn)備打印一個(gè)非常大的磁帶文件（雙方都擁有部分資源，同時(shí)在請(qǐng)求對(duì)方已占有的資源。）打印機(jī)R1磁帶機(jī)R2P1P2一、競(jìng)爭(zhēng)資源引起死鎖

二、進(jìn)程推進(jìn)順序不當(dāng)引起死鎖

資源少也未必一定產(chǎn)生死鎖。如兩個(gè)人過(guò)獨(dú)木橋，如果兩個(gè)人都要先過(guò)，在獨(dú)木橋上僵持不肯后退，必然會(huì)因競(jìng)爭(zhēng)資源產(chǎn)生死鎖；但是，如果兩個(gè)人上橋前先看一看有無(wú)對(duì)方的人在橋上，當(dāng)無(wú)對(duì)方的人在橋上時(shí)自己才上橋，那么問(wèn)題就解決了。所以，如果程序設(shè)計(jì)得不合理，造成進(jìn)程推進(jìn)的順序不當(dāng)，也會(huì)出現(xiàn)死鎖。思考題1、一個(gè)OS有20個(gè)進(jìn)程，競(jìng)爭(zhēng)使用65個(gè)同類(lèi)資源，申請(qǐng)方式是逐個(gè)進(jìn)行的，一旦某個(gè)進(jìn)程獲得它所需要的全部資源，則立即歸還所有資源。每個(gè)進(jìn)程最多使用三個(gè)資源。若僅考慮這類(lèi)資源，該系統(tǒng)有無(wú)可能產(chǎn)生死鎖，為什么？思考題：答：不可能。因?yàn)樗梨i產(chǎn)生的原因有兩點(diǎn)：系統(tǒng)資源不足或推進(jìn)順序不當(dāng)，在本題中，進(jìn)程所需的最大資源數(shù)為60，而系統(tǒng)共有該類(lèi)資源65個(gè)，其資源數(shù)已足夠系統(tǒng)內(nèi)各進(jìn)程使用。1．互斥條件多個(gè)并發(fā)進(jìn)程只能互斥訪問(wèn)臨界資源。為了保證并發(fā)執(zhí)行的封閉性和正確性，互斥條件必須保持。

2．占有并請(qǐng)求條件（部分分配）已分配到了一些臨界資源的進(jìn)程可以申請(qǐng)新的資源。

3.8.3產(chǎn)生死鎖的必要條件3．不可剝奪條件進(jìn)程所獲得的資源在未使用完畢之前，資源申請(qǐng)者不能強(qiáng)行地從資源占有者手中奪取資源，而只能由該資源的占有者進(jìn)程自行釋放。

4．循環(huán)等待條件鏈中的每一個(gè)進(jìn)程都在等待相鄰進(jìn)程所占用的資源。3.8.3產(chǎn)生死鎖的必要條件如果發(fā)現(xiàn)系統(tǒng)有()的進(jìn)程隊(duì)列就說(shuō)明系統(tǒng)有可能發(fā)生死鎖了。互斥A可剝奪B循環(huán)等待C同步D提交單選題1分3.8.4死鎖的解決辦法1、死鎖的預(yù)防（靜態(tài)）2、死鎖的避免（動(dòng)態(tài)）

3、

死鎖的檢測(cè)和恢復(fù)

4、

鴕鳥(niǎo)算法

這種辦法是在系統(tǒng)運(yùn)行之前就采取措施，即在系統(tǒng)設(shè)計(jì)時(shí)確定資源分配算法，消除發(fā)生死鎖的任何可能性。該方法雖然比較保守、資源利用率低，但因簡(jiǎn)單明了并且安全可靠，仍被廣泛采用。一、死鎖的預(yù)防（防止）（靜態(tài)法）3.8.4死鎖的解決辦法

產(chǎn)生死鎖的四個(gè)必要條件中，互斥條件由臨界資源的互斥特性所決定的，不僅不能改變，相反還應(yīng)加以保證，因此實(shí)際上只有三種方法。一、死鎖的預(yù)防（防止）（靜態(tài)法）1．靜態(tài)資源分配法（摒棄“占有并請(qǐng)求條件”）系統(tǒng)規(guī)定每一個(gè)進(jìn)程在開(kāi)始運(yùn)行前，都必須一次性地申請(qǐng)其在整個(gè)運(yùn)行過(guò)程所需的全部資源。此時(shí)，若系統(tǒng)有足夠的資源，便把進(jìn)程想要的全部資源一次性地分配給它；若不能全部滿(mǎn)足進(jìn)程的資源請(qǐng)求，則一個(gè)資源也不分給它。這樣，進(jìn)程在運(yùn)行過(guò)程中就不會(huì)再提出資源請(qǐng)求，從而破壞了占有與請(qǐng)求條件。一、死鎖的預(yù)防（防止）（靜態(tài)法）靜態(tài)資源分配法的優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：簡(jiǎn)單、安全、易實(shí)現(xiàn)。缺點(diǎn)：（1）資源被嚴(yán)重浪費(fèi)（2）進(jìn)程延遲運(yùn)行。一、死鎖的預(yù)防（防止）（靜態(tài)法）2．摒棄“不可剝奪條件”進(jìn)程在需要資源時(shí)必須得到滿(mǎn)足，否則就放棄已經(jīng)占有的資源。即：一個(gè)已經(jīng)保持了某些資源的進(jìn)程，當(dāng)它再提出新的資源要求而不能立即得到滿(mǎn)足時(shí)，必須釋放它已經(jīng)保持的所有資源，待以后再需要時(shí)再重新申請(qǐng)。一、死鎖的預(yù)防（防止）（靜態(tài)法）2．摒棄“不可剝奪條件”實(shí)現(xiàn)起來(lái)比較復(fù)雜，且要付出很大的代價(jià)。進(jìn)程的周轉(zhuǎn)時(shí)間較長(zhǎng)，系統(tǒng)開(kāi)銷(xiāo)大。一、死鎖的預(yù)防（防止）（靜態(tài)法）3．有序資源使用法（摒棄“循環(huán)等待條件”）

系統(tǒng)中的所有資源按類(lèi)都被賦予一個(gè)唯一的編號(hào)，每個(gè)進(jìn)程只能按編號(hào)的升序申請(qǐng)資源。即對(duì)同一個(gè)進(jìn)程而言，它一旦申請(qǐng)了一個(gè)編號(hào)為i的資源，就不允許再申請(qǐng)編號(hào)比i小的資源了，因此，破壞了循環(huán)等待條件。一、死鎖的預(yù)防（防止）（靜態(tài)法）3．有序資源使用法（摒棄“循環(huán)等待條件”）

（1）優(yōu)點(diǎn)：安全且資源利用率比靜態(tài)資源分配法有所提高，因?yàn)樗鼘?shí)際是一種半動(dòng)態(tài)的資源分配法。（2）缺點(diǎn)：實(shí)現(xiàn)較困難，因?yàn)殡y給出合適的資源編號(hào)，不便于系統(tǒng)增添新設(shè)備，不便于用戶(hù)編程，且仍有一定的資源浪費(fèi)現(xiàn)象。一、死鎖的預(yù)