三、互斥與同步

1.進(jìn)程同步的基本概念

?兩種形式的制約關(guān)系：互斥與同步

?臨界資源：打印機(jī)、 磁帶機(jī)、共享變量等，都屬于臨界資源，一次只能被一個(gè)進(jìn)程使用的資源。諸進(jìn)程互斥共享臨界資源。

?臨界區(qū)：每個(gè)進(jìn)程中訪問(wèn)臨界資源的那段代碼稱為臨界區(qū)

?臨界區(qū)管理的三個(gè)要求：

(1)? 一次最多允許一個(gè)進(jìn)程停留在相關(guān)的臨界區(qū)內(nèi)；

(2)? 一個(gè)進(jìn)程不能無(wú)限止地停留在臨界區(qū)；

(3)? 一個(gè)進(jìn)程不能無(wú)限止地等待進(jìn)入在臨界區(qū)。

?同步機(jī)制應(yīng)遵循的規(guī)則：

空閑讓進(jìn)、忙則等待、有限等待、讓權(quán)等待。

2、互斥的實(shí)現(xiàn)方法

2.1標(biāo)志法

? ? ? ? ??

2.2硬件實(shí)現(xiàn)方法（TS、Swap、關(guān)中斷）

（1）利用Test-and-Set指令實(shí)現(xiàn)互斥

Boolean TS（boolean *lock）{

???????? boolean old;

???????? old =*lock;

???????? *lock=true;

???????? return old;

}?????????????????????????????????????

???????? …

???????? while TS(&lock);????? //測(cè)試lock并設(shè)置lock的值

???????? 臨界區(qū)；

???????? lock = false;

???????? ….

分析：當(dāng)TS(&lock)的值為假時(shí)，設(shè)置lock為真并結(jié)束循環(huán)。

當(dāng)TS(&lock)的值為真時(shí)，繼續(xù)循環(huán)。

（2）利用Swap指令實(shí)現(xiàn)進(jìn)程互斥

swap(boolean a,boolean b)

{

???????? boolean temp;

???????? temp=a;

???????? a=b;

???????? b=temp

}

???????? …

???????? boolean key;???

???????? key=true;

???????? do

?????????????????? swap(&lock,key);

???????? while (key);

???????? 臨界區(qū)；

???????? lock=false;

???????? …

（3）關(guān)中斷

在進(jìn)入鎖測(cè)試之前關(guān)閉中斷，直到完成鎖測(cè)試并上鎖之后才能打開中斷。進(jìn)程在臨界區(qū)執(zhí)行期間，計(jì)算機(jī)系統(tǒng)不響應(yīng)中斷，從而不會(huì)引發(fā)調(diào)度，也就不會(huì)發(fā)生進(jìn)程或線程切換。保證了對(duì)鎖的測(cè)試和關(guān)鎖操作的連續(xù)性和完整性，有效地保證了互斥。

但是，關(guān)中斷的方法存在許多缺點(diǎn)：

①濫用關(guān)中斷權(quán)力可能導(dǎo)致嚴(yán)重后果；②關(guān)中斷時(shí)間過(guò)長(zhǎng)，會(huì)影響系統(tǒng)效率，限制了處理器交叉執(zhí)行程序的能力；③關(guān)中斷方法也不適用于多CPU 系統(tǒng)，因?yàn)樵谝粋€(gè)處理器上關(guān)中斷并不能防止進(jìn)程在其它處理器上執(zhí)行相同的臨界段代碼。

2.3信號(hào)量及P、V原語(yǔ)

?解決問(wèn)題：

1）TS或SWAP指令管理臨界區(qū)，采用忙式輪詢，效率低；
2）關(guān)開中斷管理臨界區(qū)，不便交給用戶程序使用。

1. 信號(hào)量的構(gòu)思

?????? 一種可動(dòng)態(tài)定義的軟件資源：信號(hào)量

◆核心數(shù)據(jù)結(jié)構(gòu)：等待進(jìn)程隊(duì)列

◆信號(hào)量聲明：資源報(bào)到，建立隊(duì)列

◆申請(qǐng)資源的原語(yǔ)：若申請(qǐng)不到，調(diào)用進(jìn)程入隊(duì)等待。

◆歸還資源的原語(yǔ)：若隊(duì)列中有等待進(jìn)程，需釋放。

◆信號(hào)量撤銷：資源注銷，撤銷隊(duì)列。

2. 記錄型信號(hào)量

■其數(shù)據(jù)結(jié)構(gòu)如下：

??? typedef struct semaphore{

??????? int value;????????????? //信號(hào)量值

??????? struct pcb *list;??? //信號(hào)量等待進(jìn)程隊(duì)列指針

????? }

■ 每個(gè)信號(hào)量建立一個(gè)等待進(jìn)程隊(duì)列

■ 每個(gè)信號(hào)量相關(guān)一個(gè)整數(shù)值

?正值表示資源可用的數(shù)量

?0值表示無(wú)資源且無(wú)進(jìn)程等待

?負(fù)值表示等待隊(duì)列中進(jìn)程的個(gè)數(shù)

3. ?P、V操作原語(yǔ)

　　Viod P(semaphore s){

????? s.value=s.value-1;

????? if (s.value<0) {

????????? 將該進(jìn)程插入到s.list的等待進(jìn)程隊(duì)列中；

????????? block(s.list);

????? }

??? }

??? Viod V(semaphore s){

????? s.value=s.value+1;

????? if (s.value<=0) {

????????? 從s.list的等待進(jìn)程隊(duì)列中釋放一個(gè)進(jìn)程P；

????????? wakeup(P);

????? }

??? }

2.4用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程互斥

　　semaphore mutex；

??? mutex=1；

??? …

??? process Pi{

????? …

????? P(mutex);

????? 進(jìn)程Pi進(jìn)入臨界區(qū)

????? V(mutex);

????? …

??? }

2.5用PV操作解決緩沖區(qū)問(wèn)題

（1）單緩沖區(qū)問(wèn)題

（2）M生產(chǎn)者N消費(fèi)者K個(gè)緩沖區(qū)

3、進(jìn)程通信

3.1進(jìn)程通信的類型

1. 共享存儲(chǔ)器系統(tǒng)(Shared-Memory System)

可分為以下兩種類型：

①基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式。②基于共享存儲(chǔ)區(qū)的通信方式。

2. 管道(pipe)通信系統(tǒng)

為了協(xié)調(diào)雙方的通信，管道機(jī)制必須提供以下三方面的協(xié)調(diào)能力：

①互斥②同步③確定對(duì)方是否存在

3. 消息傳遞系統(tǒng)(Message passing system)

可進(jìn)一步分成直接通信方式和間接通信方式

3.2消息傳遞通信的實(shí)現(xiàn)方式

1. 直接消息傳遞系統(tǒng)

1）直接傳遞原語(yǔ)

?????? send(P，信件)：把信件發(fā)送給進(jìn)程P

?????? receive(Q ，信件)：從進(jìn)程Q接收信件

2) 進(jìn)程的同步方式

3) 通信鏈路

2.間接消息傳遞系統(tǒng)——信箱通信

■ 發(fā)送或者接收信件通過(guò)一個(gè)信箱來(lái)進(jìn)行，該信箱有唯一標(biāo)識(shí)符。

■多個(gè)進(jìn)程共享一個(gè)信箱。

信箱通信原語(yǔ)

Send（A，信件）：把信件傳送到A信箱；
Receive（A，信件）：從A信箱中接收信件。

4、死鎖

4.1死鎖的概念

1.定義：在一組進(jìn)程發(fā)生死鎖的情況下，這組死鎖進(jìn)程中的每一個(gè)進(jìn)程，都在等待另一個(gè)死鎖進(jìn)程所占有的資源。

2.可重用性資源和消耗性資源

3.可搶占性資源和不可搶占性資源

4. 計(jì)算機(jī)系統(tǒng)中的死鎖

1）競(jìng)爭(zhēng)不可搶占性資源引起死鎖

2) 競(jìng)爭(zhēng)可消耗資源引起死鎖

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

4.2死鎖的必要條件（互斥、部分分配、不可搶占、循環(huán)等待）

4.3死鎖的防止：破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)，以避免發(fā)生死鎖。

■破壞互斥條件，把獨(dú)占型資源改造成共享型資源

■采用剝奪式調(diào)度方法可以破壞不可搶占條件

■破壞部分分配條件，一次性為進(jìn)程分配所有應(yīng)使用的資源。

■破壞循環(huán)等待條件，使運(yùn)行期間不存在進(jìn)程循環(huán)等待現(xiàn)象。

*主要方法：

1. 靜態(tài)分配法

■開始運(yùn)行之前，必須一次性地申請(qǐng)其在整個(gè)運(yùn)行過(guò)程中所需的全部資源。破壞了部分分配條件。

■層次分配法

■ 在層次分配策略下，資源被分成多個(gè)層次；

■ 一個(gè)進(jìn)程得到某一層的一個(gè)資源后，他只能在申請(qǐng)?jiān)谳^高層次的資源；

■當(dāng)一個(gè)進(jìn)程要釋放一個(gè)資源時(shí)，必須先釋放所占用的較高層次的資源；

■當(dāng)一個(gè)進(jìn)程獲得了某一層的一個(gè)進(jìn)程后，它想再申請(qǐng)改層中的另一個(gè)資源，那么，必須先釋放改層中的已占有資源。

■不可能形成循環(huán)回路，故阻止了循環(huán)等待的出現(xiàn)。

4.4死鎖的避免（銀行家算法：借錢給有償還能力的客戶）

1.銀行家算法（單一資源）

假設(shè)系統(tǒng)有三個(gè)進(jìn)程P，Q，R，系統(tǒng)只有一類資源共10個(gè)，目前分配情況如下：

安全序列：{Q，P，R}

2.銀行家算法（多個(gè)資源）

假定系統(tǒng)中有五個(gè)進(jìn)程{P0, P1, P2, P3, P4}和三類資源{A, B, C}，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖所示，給出一個(gè)安全序列。

?(1)從題目中，可以提取出Max矩陣和Allocation，用二個(gè)矩陣相減得到Need矩陣：

(2)用Avaliable向量與Need矩陣各行比較，找出比Avaliable向量小的行：

（3? 3? 2）>(1? 2? 2)和（3? 3 ?2）>(0 ?1 ?1)

對(duì)應(yīng)的二個(gè)進(jìn)程分別為P1和P3，我們選擇P1加入安全序列。

(3)釋放P1所占有的資源，即把P1進(jìn)程對(duì)應(yīng)的Allocation矩陣中的一行與Avaliable向量相加：

（3? 3 ?2）+（2 ?0 ?0）=（5 ?3? 2）= ?Avaliable

(4)在Need矩陣中去掉P1對(duì)應(yīng)的行

(5)重復(fù)第（2）步，最后得到一個(gè)安全序列：{P1，P3，P4，P2，P0}?

故系統(tǒng)是安全的。

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

如果在系統(tǒng)中，既不采取死鎖預(yù)防措施，也未配有死鎖避免算法，系統(tǒng)很可能會(huì)發(fā)生死鎖。在這種情況下，系統(tǒng)應(yīng)當(dāng)提供兩個(gè)算法：

① 死鎖檢測(cè)算法。該方法用于檢測(cè)系統(tǒng)狀態(tài)，以確定系統(tǒng)中是否發(fā)生了死鎖。

② 死鎖解除算法。當(dāng)認(rèn)定系統(tǒng)中已發(fā)生了死鎖，利用該算法可將系統(tǒng)從死鎖狀態(tài)中解脫出來(lái)。

1. 死鎖的檢測(cè)
為了能對(duì)系統(tǒng)中是否已發(fā)生了死鎖進(jìn)行檢測(cè)，在系統(tǒng)中必須：① 保存有關(guān)資源的請(qǐng)求和分配信息；② 提供一種算法，它利用這些信息來(lái)檢測(cè)系統(tǒng)是否已進(jìn)入死鎖狀態(tài)。
1) 資源分配圖

2) 等待圖：

2. 死鎖的解除
1)終止進(jìn)程的方法：終止所有死鎖進(jìn)程、逐個(gè)終止進(jìn)程

2)校驗(yàn)點(diǎn)：執(zhí)行過(guò)程中定時(shí)設(shè)置校驗(yàn)點(diǎn)。從校驗(yàn)點(diǎn)開始重新執(zhí)行。