幾種進(jìn)程間的通信方式

管道( pipe )：

管道是一種半雙工的通信方式豺撑，數(shù)據(jù)只能單向流動(dòng)纸兔，而且只能在具有親緣關(guān)系的進(jìn)程間使用录平。進(jìn)程的親緣關(guān)系通常是指父子進(jìn)程關(guān)系盆偿。

有名管道 (named pipe) ：

有名管道也是半雙工的通信方式讯私，但是它允許無親緣關(guān)系進(jìn)程間的通信热押。

信號(hào)量( semophore ) ：

信號(hào)量是一個(gè)計(jì)數(shù)器西傀，可以用來控制多個(gè)進(jìn)程對(duì)共享資源的訪問。它常作為一種鎖機(jī)制桶癣，防止某進(jìn)程正在訪問共享資源時(shí)拥褂，其他進(jìn)程也訪問該資源。因此牙寞，主要作為進(jìn)程間以及同一進(jìn)程內(nèi)不同線程之間的同步手段饺鹃。

消息隊(duì)列( message queue ) ：

消息隊(duì)列是由消息的鏈表，存放在內(nèi)核中并由消息隊(duì)列標(biāo)識(shí)符標(biāo)識(shí)间雀。消息隊(duì)列克服了信號(hào)傳遞信息少悔详、管道只能承載無格式字節(jié)流以及緩沖區(qū)大小受限等缺點(diǎn)。

信號(hào) ( signal ) ：

信號(hào)是一種比較復(fù)雜的通信方式惹挟，用于通知接收進(jìn)程某個(gè)事件已經(jīng)發(fā)生茄螃。

共享內(nèi)存( shared memory ) ：

共享內(nèi)存就是映射一段能被其他進(jìn)程所訪問的內(nèi)存，這段共享內(nèi)存由一個(gè)進(jìn)程創(chuàng)建连锯，但多個(gè)進(jìn)程都可以訪問归苍。共享內(nèi)存是最快的 IPC 方式，它是針對(duì)其他進(jìn)程間通信方式運(yùn)行效率低而專門設(shè)計(jì)的萎庭。它往往與其他通信機(jī)制霜医，如信號(hào)兩，配合使用驳规，來實(shí)現(xiàn)進(jìn)程間的同步和通信肴敛。

套接字( socket ) ：

套接字也是一種進(jìn)程間通信機(jī)制，與其他通信機(jī)制不同的是吗购，它可用于不同主機(jī)的進(jìn)程通信医男。

死鎖

死鎖是指兩個(gè)或兩個(gè)以上的進(jìn)程在執(zhí)行過程中，由于競爭資源或者由于彼此通信而造成的一種阻塞的現(xiàn)象捻勉，若無外力作用镀梭，它們都將無法推進(jìn)下去。此時(shí)稱系統(tǒng)處于死鎖狀態(tài)或系統(tǒng)產(chǎn)生了死鎖踱启，這些永遠(yuǎn)在互相等待的進(jìn)程稱為死鎖進(jìn)程报账。

產(chǎn)生條件

雖然進(jìn)程在運(yùn)行過程中，可能發(fā)生死鎖埠偿，但死鎖的發(fā)生也必須具備一定的條件透罢，死鎖的發(fā)生必須具備以下四個(gè)[必要條件]
1****）互斥條件：指進(jìn)程對(duì)所分配到的資源進(jìn)行排它性使用，即在一段時(shí)間內(nèi)某資源只由一個(gè)進(jìn)程占用冠蒋。如果此時(shí)還有其它進(jìn)程請(qǐng)求資源羽圃，則請(qǐng)求者只能等待，直至占有資源的進(jìn)程用畢釋放抖剿。
2****）請(qǐng)求和保持條件：指進(jìn)程已經(jīng)保持至少一個(gè)資源朽寞，但又提出了新的資源請(qǐng)求识窿，而該資源已被其它進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程阻塞脑融，但又對(duì)自己已獲得的其它資源保持不放喻频。
3****）不剝奪條件：指進(jìn)程已獲得的資源，在未使用完之前吨掌，不能被剝奪半抱，只能在使用完時(shí)由自己釋放脓恕。
4****）環(huán)路等待條件：指在發(fā)生死鎖時(shí)膜宋，必然存在一個(gè)進(jìn)程——資源的環(huán)形鏈，即進(jìn)程集合{P0炼幔，P1秋茫，P2，···乃秀，Pn}中的P0正在等待一個(gè)P1占用的資源肛著；P1正在等待P2占用的資源，……跺讯，Pn正在等待已被P0占用的資源枢贿。

只要打破四個(gè)必要條件之一就能有效預(yù)防死鎖的發(fā)生：
①打破互斥條件：改造獨(dú)占性資源為虛擬資源，大部分資源已無法改造刀脏。
②打破不可搶占條件：當(dāng)一進(jìn)程占有一獨(dú)占性資源后又申請(qǐng)一獨(dú)占性資源而無法滿足局荚，則退出原占有的資源。
③打破占有且申請(qǐng)條件：采用資源預(yù)先分配策略愈污，即進(jìn)程運(yùn)行前申請(qǐng)全部資源耀态，滿足則運(yùn)行，不然就等待暂雹，這樣就不會(huì)占有且申請(qǐng)首装。
④打破循環(huán)等待條件：實(shí)現(xiàn)資源有序分配策略，對(duì)所有設(shè)備實(shí)現(xiàn)分類編號(hào)杭跪，所有進(jìn)程只能采用按序號(hào)遞增的形式申請(qǐng)資源仙逻。即破壞了環(huán)路

銀行家算法（適用于每種資源類型有多個(gè)實(shí)例）

為了實(shí)現(xiàn)銀行家算法，必須要有幾個(gè)數(shù)據(jù)結(jié)構(gòu)：

注：設(shè)n為系統(tǒng)進(jìn)程的個(gè)數(shù)涧尿，m為在資源類型的種類系奉。

Available：長度為m的向量。表示每種資源的現(xiàn)有實(shí)例的數(shù)量现斋。如果Available[j]=k喜最，那么資源Rj有k個(gè)實(shí)例有效。

Max：n * m矩陣庄蹋。定義每種進(jìn)程的最大需求瞬内。如果Max[i][j]=k,那么進(jìn)程Pi可以最多請(qǐng)求資源Rj的k個(gè)實(shí)例迷雪。

Allocation：n * m矩陣。定義每個(gè)進(jìn)程現(xiàn)在所分配的各種資源類型的實(shí)例數(shù)量虫蝶。如果Allocation[I,j]=k,那么進(jìn)程Pj當(dāng)前分配了k個(gè)資源Rj的實(shí)例章咧。

Need：n * m矩陣。表示每個(gè)進(jìn)程還需要的剩余的資源能真。如果Need[i][j]=k,那么進(jìn)程Pj還需要資源Rj的k個(gè)實(shí)例赁严。
注：Need[i][j] = Max[i][j] – Allocation [i][j]

為了描述方便，我們采用一些簡化的表示方法：

設(shè)X和Y為長度為n的向量粉铐，則X <= Y當(dāng)且僅當(dāng)對(duì)所有i = 1疼约，2，...蝙泼，n程剥，X[i] <= Y[i]。例如汤踏，如果X = (1,7,2,3)而Y = (0,3,2,1)织鲸，那么Y <= X。如果Y <= X且Y != X溪胶，那么Y < X搂擦。

可以將Allocation和Need的每行作為向量，并分別用Allocation i和Need i來表示哗脖，向量Allocation i表示分配給進(jìn)程Pi的資源瀑踢；向量Need i表示進(jìn)程為完成其任務(wù)可能仍然需要申請(qǐng)的額外資源。

銀行家算法可整體分成兩個(gè)部分：

1.安全性算法

確認(rèn)計(jì)算機(jī)系統(tǒng)是否處于安全狀態(tài)的算法分為如下幾步：

（1）設(shè)Work和Finish分別為長度為m和n的向量懒熙。按如下方式進(jìn)行初始化丘损，Work = Avaliable且對(duì)于i = 0,1，...工扎，n - 1徘钥，F(xiàn)inish[i] = 　　 false。

（2）查找這樣的i使其滿足

·Finish[i] = false

·Need i <= Work

如果沒有這樣的i肢娘，那么就轉(zhuǎn)到第（4）步呈础。

（3）Work = Work + Allocation i

Finish[i] = true

返回第（2）步

（4）如果對(duì)所有i，F(xiàn)inish[i] = true橱健，那么系統(tǒng)則處于安全狀態(tài)而钞。

該算法可能需要m * n^2數(shù)量級(jí)的操作以確定系統(tǒng)是否處于安全狀態(tài)。

2.資源請(qǐng)求算法

現(xiàn)在拘荡，描述如何判斷是否可安全允許請(qǐng)求的算法臼节。

設(shè)Request i為進(jìn)程Pi的請(qǐng)求向量。如果Request i[j] == k，那么進(jìn)程Pi需要資源類型Rj的實(shí)例數(shù)量為k网缝。當(dāng)進(jìn)程Pi作出資源請(qǐng)求時(shí)巨税，采取如下動(dòng)作：

（1）如果Request i <= Need i，那么轉(zhuǎn)到第（2）步粉臊。否則草添，產(chǎn)生出錯(cuò)條件，這是因?yàn)檫M(jìn)程Pi已超過了其最大請(qǐng)求扼仲。

（2）如果Request i <= Available远寸，那么轉(zhuǎn)到第（3）步。否則屠凶，Pi必須等待驰后，這是因?yàn)闆]有可用資源。

（3）假定系統(tǒng)可以分配給進(jìn)程Pi所請(qǐng)求的資源阅畴，并按如下方式修改狀態(tài)：

Available = Available - Request i;

Allocation i = Allocation i + Request i;

Need i = Need i - Request i;

如果所產(chǎn)生的資源分配狀態(tài)是安全的（通過上面的安全性算法）倡怎，那么Pi可分配到它所請(qǐng)求的資源。但是贱枣，如果新狀態(tài)不安全，則進(jìn)程Pi必須等待Request i并恢復(fù)到原來的資源分配狀態(tài)颤专。