Android跨進(jìn)程通信IPC整體內(nèi)容如下

• 1、Android跨進(jìn)程通信IPC之1——Linux基礎(chǔ)
• 2、Android跨進(jìn)程通信IPC之2——Bionic
• 3、Android跨進(jìn)程通信IPC之3——關(guān)于"JNI"的那些事
• 4、Android跨進(jìn)程通信IPC之4——AndroidIPC基礎(chǔ)1
• 4、Android跨進(jìn)程通信IPC之4——AndroidIPC基礎(chǔ)2
• 5、Android跨進(jìn)程通信IPC之5——Binder的三大接口
• 6、Android跨進(jìn)程通信IPC之6——Binder框架
• 7、Android跨進(jìn)程通信IPC之7——Binder相關(guān)結(jié)構(gòu)體簡介
• 8、Android跨進(jìn)程通信IPC之8——Binder驅(qū)動
• 9、Android跨進(jìn)程通信IPC之9——Binder之Framework層C++篇1
• 9、Android跨進(jìn)程通信IPC之9——Binder之Framework層C++篇2
• 10、Android跨進(jìn)程通信IPC之10——Binder之Framework層Java篇
• 11、Android跨進(jìn)程通信IPC之11——AIDL
• 12、Android跨進(jìn)程通信IPC之12——Binder補(bǔ)充
• 13、Android跨進(jìn)程通信IPC之13——Binder總結(jié)
• 14、Android跨進(jìn)程通信IPC之14——其他IPC方式
• 15、Android跨進(jìn)程通信IPC之15——感謝

由于Android系統(tǒng)是基于Linux系統(tǒng)的，所以有必要簡單的介紹下Linux的跨進(jìn)程通信，對大家后續(xù)了解Android的跨進(jìn)程通信是有幫助的，本篇的主要內(nèi)容如下：

• 1、Linux介紹
  1.1、Unix操作系統(tǒng)
  1.2、GNU
  1.3、Linux的誕生
  1.4、開源發(fā)展實(shí)驗(yàn)室和Linux基金
  1.5、Linux的全局圖
  1.6、Linux的源碼目錄結(jié)構(gòu)
• 2、內(nèi)核態(tài)與用戶態(tài)
  2.1、內(nèi)核態(tài)與用戶態(tài)簡介
  3.2、為什么要有用戶態(tài)和內(nèi)核態(tài)
  2.3、用戶態(tài)與內(nèi)核態(tài)的切換
• 3、紅黑樹
  3.1、二叉搜索樹
  3.2、紅黑樹
  3.3、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)
  3.4、樹的旋轉(zhuǎn)知識
• 4、Linux的跨進(jìn)程通信
  4.1、匿名管道(pipe)
  4.2、命名管道(FIFO)
  4.3、信號(signal)
  4.4、信號量(semaphore)
  4.5、消息隊(duì)列(message queue)
  4.6、共享內(nèi)存(share memory)

4.7、套接字(Socket)
4.8、Linux的幾種跨進(jìn)程通信的方式的比較

的旋轉(zhuǎn)知識

一、Linux介紹

說到Linux操作系統(tǒng)，不的不說下Unix系統(tǒng)

(一)、Unix操作系統(tǒng)

Unix因?yàn)槠浒踩煽浚咝?qiáng)大的特點(diǎn)在服務(wù)器領(lǐng)域得到了廣發(fā)的應(yīng)用。直到GNU/Linux流行開始前，Unix也是科學(xué)計(jì)算、大型機(jī)、超級電腦等所用操作系統(tǒng)的主流。

1、Unix的誕生

湯普遜和里奇最早是在貝爾實(shí)驗(yàn)室開發(fā)Unix，此后10年，Unix在學(xué)術(shù)機(jī)構(gòu)和大型企業(yè)中得到了廣泛的應(yīng)用，當(dāng)Unix擁有者AT&T公司以低廉甚至免費(fèi)的許可將Unix源碼授權(quán)給學(xué)術(shù)機(jī)構(gòu)做研究或教學(xué)之用，許多機(jī)構(gòu)在此源碼的基礎(chǔ)加以擴(kuò)展和優(yōu)化，形成了所謂的"Unix變種"，這種變種反過來也促進(jìn)了Unix的發(fā)展，其中最著名的變種就是BSD產(chǎn)品。BSD在后續(xù)的發(fā)展中也衍生出了3個(gè)主要分支:FresBSD、OpenBSD和NetBSD。

2、Unix名字的由來

Unix的誕生和Multics(Multiplexed Information android Computing System) 是有一定淵源的。Multics是由麻省理工學(xué)院，AT&T貝爾實(shí)驗(yàn)室和通用電氣合作進(jìn)行的操作系統(tǒng)項(xiàng)目。由于Multics的失敗，AT&T撤出了Multics投入的資源，其中一位開發(fā)者——肯.湯普遜則繼續(xù)開發(fā)軟件，并最終編寫一個(gè)太空旅行游戲，但是他發(fā)現(xiàn)游戲速度很慢，并且成本高，在丹尼斯.里奇的幫助下，湯普遜用PDP-7的匯編語言重寫了這個(gè)游戲，并讓其再DEC PDP-7上運(yùn)行起來。這次經(jīng)歷加上Multics項(xiàng)目的經(jīng)驗(yàn)，湯普遜和里奇領(lǐng)導(dǎo)一組開發(fā)者開發(fā)了一個(gè)新的多任務(wù)操作系統(tǒng)，這個(gè)系統(tǒng)包括命令解釋器和一些實(shí)用程序。1970年那部PDP-7卻只能支持兩個(gè)用戶，所以他們就開玩笑的稱他們的系統(tǒng)其實(shí)是"UNiplexed Information and Computing System"，縮寫為"UNICS"，于是這個(gè)項(xiàng)目被稱為UnICS(Uniplexed Information and Computing System)。后來，大家取其諧音這個(gè)名字就改為UNIX

3、Unix的文化

UNIX is not jus an operating system , but a way of life. (UNIX 不僅僅是一個(gè)操作系統(tǒng)，更是一種生活方式。) 經(jīng)過幾十年的發(fā)展，UNIX在技術(shù)上日臻成熟的過程中，他獨(dú)特的設(shè)計(jì)哲學(xué)和美學(xué)也深深地吸引了一大批技術(shù)人員，他們在維護(hù)、開發(fā)、使用UNIX的同時(shí)，UNIX也影響了他們的思考方式和看待世界的角度。這些人自然而然地形成了一個(gè)社團(tuán)

4、Unix的重要設(shè)計(jì)原則：

• 簡潔至上
• 提供機(jī)制而非策略

(二)、GNU

GNU又稱革奴計(jì)劃，是由查理德.斯托曼在1983年9月27日發(fā)起的，它的目標(biāo)是創(chuàng)建一套完全自由的操作系統(tǒng)。
《GNU宣言》是解釋為什么發(fā)起該計(jì)劃的文章，其中一個(gè)重要理由就是要"重現(xiàn)當(dāng)年軟件界合作互助的團(tuán)結(jié)精神"。為了保證GNU軟件可以自由地"使用、復(fù)制、修改和發(fā)布"，所有GNU軟件都有一份在禁止其他人添加任何限制的情況下授權(quán)所所有權(quán)利了給任何人的協(xié)議條款，GNU通用的公共許可證(GNU General Public License GPL)。即"反版權(quán)"(或者稱copyleft)概念。

GNU是“GNU is Not Unix”的縮寫。斯托曼宣布GNU應(yīng)當(dāng)發(fā)音為Guh-NOO以避免與new這個(gè)單詞混淆（注：Gnu在英文中原意為非洲牛羚，發(fā)音與new相同）。UNIX是一種廣泛使用的商業(yè)操作系統(tǒng)的名稱。由于GNU將要實(shí)現(xiàn)UNIX系統(tǒng)的接口標(biāo)準(zhǔn)，因此GNU計(jì)劃可以分別開發(fā)不同的操作系統(tǒng)部件。GNU計(jì)劃采用了部分當(dāng)時(shí)已經(jīng)可自由使用的軟件。不過GNU計(jì)劃也開發(fā)了大批其他的自由軟件。

(三)、Linux的誕生

1、Linux的誕生

1991年，在赫爾辛基，Linus Toral開始寫了一個(gè)項(xiàng)目，目的是用來訪問大學(xué)里面的大型Unix服務(wù)器的虛擬終端。他專門寫了一個(gè)用于他當(dāng)時(shí)正在用的硬件的，與系統(tǒng)操作系統(tǒng)無關(guān)的程序，開發(fā)是在Minix，用的編譯器是GCC來完成的，這個(gè)項(xiàng)目后面逐漸轉(zhuǎn)變?yōu)長inux內(nèi)核。

2、Linux的誕生

Linus Torvalds本要把他的發(fā)時(shí)叫做Freax——“fread”，“free”和“x”（暗指Unix）的合成詞。在開發(fā)系統(tǒng)的前半年里，他把文件以文件名“Freax”存儲。Torvalds考慮過Linux這個(gè)名字，但是因?yàn)橛X得它過于自我本位而放棄了使用它。為便于開發(fā)，后面，他把那些文件上傳到了赫爾辛基工業(yè)大學(xué)（HUT）的FTP服務(wù)器。Torvalds在HUT負(fù)責(zé)管理那個(gè)服務(wù)器的同事，覺得“Freax”這個(gè)名字不是很好，就在不咨詢Torvalds的情況下，把項(xiàng)目的名字改成了“Linux”。但是之后，Torvalds也同意“Linux”這個(gè)名字了：“經(jīng)過多次討論，他承認(rèn)Linux這個(gè)名字更好。在0.01版本Linux的源代碼的makefile里仍然使用‘Freax’這個(gè)名字，在之后‘Linux’這個(gè)名字才被使用。所以，Linux這個(gè)名字并不是預(yù)先想好的，只是它被廣泛接受了而已”。

(四)、開源發(fā)展實(shí)驗(yàn)室和Linux基金

開源碼發(fā)展實(shí)驗(yàn)室（Open Source Development Lab）創(chuàng)立于2000年。它是一個(gè)獨(dú)立的非營利性組織。它的目標(biāo)是優(yōu)化Linux以應(yīng)用于數(shù)據(jù)中心和運(yùn)營商的領(lǐng)域。它是Linus Torvalds和Andrew Morton工作的贊助來源。2006年年中，Morton去了Google（Google也是使用Linux內(nèi)核的）；Torvalds全職為OSDL開發(fā)Linux內(nèi)核。非商業(yè)性運(yùn)營機(jī)制的資金主要來源于Red Hat，Novell，三菱，英特爾, IBM ，戴爾和惠普等幾家大公司。

2007年1月22日，OSDL和自由標(biāo)準(zhǔn)組織合并為Linux基金會，把它們的工作焦點(diǎn)集中在改進(jìn)GNU/Linux以與Windows競爭。

(五)、Linux的全局圖

下面是一幅Linux kernel map：

Linux kernel map.png

這是makeLinux網(wǎng)站提供的一幅非常經(jīng)典的Linux內(nèi)核圖，涵蓋了內(nèi)核最為核心的方法，Linux除了驅(qū)動開發(fā)外，還有很多通用子系統(tǒng)，比如CPU，memory，file system等核心模塊，即便不做底層驅(qū)動開發(fā)，掌握這些模塊對于加深理解整個(gè)系統(tǒng)運(yùn)轉(zhuǎn)還是很有幫助的。

(六)、Linux的源碼目錄結(jié)構(gòu)

二、內(nèi)核態(tài)與用戶態(tài)

這部分是臨時(shí)加進(jìn)來的，是在后面的Binder驅(qū)動里面會用到，原來是打算加到"Android跨進(jìn)程通信IPC之1——Linux基礎(chǔ)"里面，不過由于簡書的篇幅限制，我加到這里來了。

1、內(nèi)核態(tài)和用戶態(tài)的簡介

• ** 內(nèi)核態(tài) **：CPU可以訪問內(nèi)存所有數(shù)據(jù)，包括外圍設(shè)備，例如硬盤、網(wǎng)卡，CPU可以將自己從一個(gè)程序切換到另外一個(gè)程序。
• ** 用戶態(tài) **: 只能受限的訪問內(nèi)存，且不允許訪問外圍設(shè)備，占用CPU的能力被剝削，CPU資源可以被其他程序獲取。

2、為什么要有用戶態(tài)和內(nèi)核態(tài)

由于需要限制不同的程序之間的訪問能力，防止他們獲取別的程序的內(nèi)存數(shù)據(jù)，或者獲取外圍設(shè)備的數(shù)據(jù)，并發(fā)送網(wǎng)絡(luò)，CPU劃分出兩個(gè)權(quán)限等級 ----用戶態(tài) 和 內(nèi)核態(tài)。

3、用戶態(tài)與內(nèi)核態(tài)的切換

3.1 切換簡介

所有用戶程序都是運(yùn)行在用戶態(tài)的，但是有時(shí)候程序確實(shí)需要做一些內(nèi)核態(tài)的事情，例如從硬盤讀取數(shù)據(jù)，或者從鍵盤獲取輸入等。而唯一可以這這些事情的就是 操作系統(tǒng) ，所以這時(shí)候 程序 就需要先向 操作系統(tǒng) 請求，以 程序 的名字來執(zhí)行這些操作。這時(shí)候就需要一個(gè)這樣的機(jī)制：用戶態(tài) 切換到 內(nèi)核態(tài)，但是不能控制內(nèi)核態(tài)中執(zhí)行的執(zhí)行這種機(jī)制叫做** 系統(tǒng)調(diào)用 **，在CPU中的實(shí)現(xiàn)稱之為 "陷阱指令(Trap Instruction)"

3.2 系統(tǒng)調(diào)用機(jī)制流程：

• 1、用戶態(tài)程序?qū)⒁恍?shù)據(jù)值放在寄存器中，或者使用參數(shù)創(chuàng)建一個(gè)堆棧(stack frame)，以表明需要操作系統(tǒng)提供的服務(wù)。
• 2、用戶態(tài)程序執(zhí)行陷阱指令
• 3、CUP切換到內(nèi)核態(tài)，并跳到內(nèi)存指定位置的指令，這些指令是操作系統(tǒng)的一部分，他們具有內(nèi)存保護(hù)，不可被用戶態(tài)程序訪問
• 4、這些指令稱之為 陷阱 (trap) 或者新系統(tǒng)調(diào)用處理器 ( system call hanlder )。他們會讀取程序放入內(nèi)存的數(shù)據(jù)參數(shù)，并執(zhí)行程序請求的服務(wù)。
• 5、系統(tǒng)調(diào)用完成后，操作系統(tǒng)會重置CPU為用戶態(tài)并返回系統(tǒng)調(diào)用的結(jié)果。

三、紅黑樹

紅黑樹是60年代中期計(jì)算機(jī)科學(xué)界尋找一種算法復(fù)雜度穩(wěn)定，容易實(shí)現(xiàn)的數(shù)據(jù)存儲算法的產(chǎn)物。紅黑樹是常用的一種數(shù)據(jù)結(jié)構(gòu)，它使得對數(shù)據(jù)的索引，插入和刪除操作都能保持在O(lgn)的時(shí)間復(fù)雜度。在優(yōu)先級隊(duì)列、字典等實(shí)用領(lǐng)域都有廣泛地應(yīng)用，更是70年代提出的關(guān)系數(shù)據(jù)庫模型——B樹的鼻祖。當(dāng)然，相比于一般的數(shù)據(jù)結(jié)構(gòu)，紅黑樹實(shí)現(xiàn)的難度有所增加。** 關(guān)鍵是后面要講解的Binder驅(qū)動里面用到了紅黑樹 **

(一)二叉搜索樹

在具體實(shí)現(xiàn)紅黑樹之前， 必須弄清楚它的基本含義。紅黑樹本質(zhì)上是一顆二叉搜索樹，它滿足二叉搜索樹的基本性質(zhì)——即樹中的任何節(jié)點(diǎn)的值大于它的左子節(jié)點(diǎn)，且小于它的右子節(jié)點(diǎn)。

二叉搜索樹.png

按照二叉搜索樹組織數(shù)據(jù)，使得對元素的查找非?？旖?。比如上圖的中的二叉搜索樹，如果查詢值為48的節(jié)點(diǎn)，只需要遍歷4個(gè)節(jié)點(diǎn)即可完成。理論上，一顆平衡的二叉樹搜索樹的任意節(jié)點(diǎn)平均查找效率為樹的高度h，即O(lgn)。但是如果二叉搜索樹的失去平衡(元素在一側(cè))，搜索效率就退化為O(n)，因此二叉搜索樹的平衡是搜索效率的關(guān)鍵所在。為了維護(hù)樹的平衡性，數(shù)據(jù)結(jié)構(gòu)內(nèi)出現(xiàn)了各種各樣的樹，比如AVL樹通過維持任何節(jié)點(diǎn)的左右子樹的高度差 不大于1保持樹的平衡，而紅黑樹使用顏色維持樹的平衡，使二叉搜索樹的左右子樹的高度差 保持在固定的范圍。相比于其他二叉搜索樹，紅黑樹對二叉搜索樹的平衡性維持著自身的優(yōu)勢

(二) 紅黑樹

紅黑樹，顧名思義，紅黑樹的節(jié)點(diǎn)是有顏色概念的，即非紅即黑，通過顏色的語速，紅黑樹為支持著二叉搜索樹的平衡性。一個(gè)紅黑樹必須有下面5個(gè)特征

• 1、節(jié)點(diǎn)是紅色或黑色
• 2、根是黑色
• 3、所有葉子是黑色(葉子是NIL節(jié)點(diǎn))
• 4、每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色的(從每個(gè)葉子到跟的所有路徑不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))
• 5、從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

如下圖

紅黑樹圖1.png

這些特征強(qiáng)制約束了紅黑樹的關(guān)鍵性質(zhì)：從跟到葉子的最長可能路徑不多于最短可能路徑的兩倍長(特征4保證了路徑最長的情況為1紅1黑，最短的情況為全黑，再結(jié)合特征5，可以推導(dǎo)出)。結(jié)果是這個(gè)樹大致上是平衡的。因?yàn)楸热绮迦?、刪除和查找操作中，操作某個(gè)值的最壞情況的時(shí)間都要求與樹的高度成比例，這個(gè)高度上的理論上限允許紅黑樹在最壞的情況都是高效的，而不同于普通的(二叉搜索樹)

(三) 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

• 和一般的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)類似，我們用抽象數(shù)據(jù)類型表示紅黑樹的節(jié)點(diǎn)，使用指針保存節(jié)點(diǎn)之間的相互關(guān)系。
• 作為紅黑樹的節(jié)點(diǎn)，其基本屬性有：節(jié)點(diǎn)的顏色，左節(jié)點(diǎn)的指針，右節(jié)點(diǎn)的指針、父節(jié)點(diǎn)的指針、節(jié)點(diǎn)的值

如下圖

紅河書節(jié)點(diǎn).png

為了方便紅黑樹關(guān)鍵算法的實(shí)現(xiàn)，還定義了一些簡單的操作（都是內(nèi)聯(lián)函數(shù)）。

//紅黑樹節(jié)點(diǎn)
template<class T>
class rb_tree_node
{
    typedef rb_tree_node_color node_color;
    typedef rb_tree_node<T> node_type;
public:
    node_color color;//顏色
    node_type*parent;//父節(jié)點(diǎn)
    node_type*left;//左子節(jié)點(diǎn)
    node_type*right;//右子節(jié)點(diǎn)
    T value;//值
    rb_tree_node(T&v);//構(gòu)造函數(shù)
    inline node_type*brother();//獲取兄弟節(jié)點(diǎn)
    inline bool on_left();//自身是左子節(jié)點(diǎn)
    inline bool on_right();//自身是右子節(jié)點(diǎn)
    inline void set_left(node_type*node);//設(shè)置左子節(jié)點(diǎn)
    inline void set_right(node_type*node);//設(shè)置左子節(jié)點(diǎn)
};

為了表示紅黑樹節(jié)點(diǎn)的顏色，我們定義了一個(gè)簡單的枚舉類型。

//紅黑樹節(jié)點(diǎn)顏色
enum rb_tree_node_color
{
    red=false,
    black=true
};

有了節(jié)點(diǎn)，剩下的就是實(shí)現(xiàn)紅黑樹的構(gòu)造、插入、搜索、刪除等關(guān)鍵算法了。

//紅黑樹
template<class T>
class rb_tree
{
public:
    typedef rb_tree_node<T> node_type;
    rb_tree();
    ~rb_tree();
    void clear();
    void insert(T v);//添加節(jié)點(diǎn)
    bool insert_unique(T v);//添加唯一節(jié)點(diǎn)
    node_type* find(T v);//查詢節(jié)點(diǎn)
    bool  remove(T v);//刪除節(jié)點(diǎn)
    inline node_type* maximum();//最大值
    inline node_type* minimum();//最小值
    inline node_type* next(node_type*node);//下一個(gè)節(jié)點(diǎn)
    inline node_type* prev(node_type*node);//上一個(gè)節(jié)點(diǎn)
    void print();//輸出
    int height();//高度
    unsigned count();//節(jié)點(diǎn)數(shù)
    bool validate();//驗(yàn)證
    unsigned get_rotate_times();//獲取旋轉(zhuǎn)次數(shù)
private:
    node_type*root;//樹根
    unsigned rotate_times;//旋轉(zhuǎn)的次數(shù)
    unsigned node_count;//節(jié)點(diǎn)數(shù)
    void __clear(node_type*sub_root);//清除函數(shù)
    void __insert(node_type*&sub_root,node_type*parent,node_type*node);//內(nèi)部節(jié)點(diǎn)插入函數(shù)
    node_type* __find(node_type*sub_root,T v);//查詢
    inline node_type* __maximum(node_type*sub_root);//最大值
    inline node_type* __minimum(node_type*sub_root);//最小值
    void __rebalance(node_type*node);//新插入節(jié)點(diǎn)調(diào)整平衡
    void __fix(node_type*node,node_type*parent,bool direct);//刪除節(jié)點(diǎn)調(diào)整平衡
    void __rotate(node_type*node);//自動判斷類型旋轉(zhuǎn)
    void __rotate_left(node_type*node);//左旋轉(zhuǎn)    
    void __rotate_right(node_type*node);//右旋轉(zhuǎn)
    void __print(node_type*sub_root);//輸出
    int  __height(node_type*&sub_root);//高度
    bool __validate(node_type*&sub_root,int& count);//驗(yàn)證紅黑樹的合法性
};

在紅黑樹類中，定義了** 樹根(root) ** 和** 節(jié)點(diǎn)數(shù) (count) ，其中還記錄了紅黑樹插入、刪除時(shí)執(zhí)行的旋轉(zhuǎn)次數(shù) rotate_times。其中核心操作有 插入操作(insert) ， 搜索操作 (find) ， ** 刪除操作(remove) ， 遞減操作(prev) ** ——尋找比當(dāng)前節(jié)點(diǎn)較小的節(jié)點(diǎn)， 遞增操作(next) ** ——尋找比當(dāng)前節(jié)點(diǎn)比較大的節(jié)點(diǎn)， ** 最大值(maximum) ** 和 ** 最小值(minimum) ** 。** 其中驗(yàn)證操作(__ validate) ** 通過遞歸操作紅黑樹，驗(yàn)證紅黑樹的基本顏色約束，用于操縱紅黑樹驗(yàn)證紅黑樹是否保持平衡。

(四) 樹的旋轉(zhuǎn)知識

當(dāng)我們在對紅黑樹進(jìn)行插入和刪除等操作時(shí)，對樹做了修改，那么可能會違背紅黑樹的性質(zhì)。所以為了繼續(xù)保持紅黑樹的性質(zhì)，我們可以通過對節(jié)點(diǎn)進(jìn)行重新著色，以及對樹進(jìn)行相關(guān)的旋轉(zhuǎn)操作，即修改樹中某些節(jié)點(diǎn)的顏色及指針結(jié)構(gòu)，來達(dá)到對紅黑樹進(jìn)行插入和刪除結(jié)點(diǎn)等操作后，繼續(xù)保持它的性質(zhì)或平衡。

樹的旋轉(zhuǎn)，分為左旋和右旋，借助下圖來做介紹：

1、左旋

左旋.png

如上圖所示：

• 當(dāng)在某個(gè)結(jié)點(diǎn)pivot上，做左旋操作時(shí)，我們假設(shè)它的右孩子不是NIL，pivot可以為任何不是不是NIL的左孩子的結(jié)點(diǎn)。
• 左旋以pivot到y(tǒng)之間的鏈為"支軸"進(jìn)行，它使y成為該孩子樹新的根，而y的左孩子b則成為pivot的右孩子。

2、右旋

右旋.png

對于樹的旋轉(zhuǎn)，能保持不變的只有原樹和搜索性質(zhì)，而原樹的紅黑性質(zhì)則不能保持，在紅黑樹的數(shù)據(jù)插入和刪除后可利用旋轉(zhuǎn)和顏色重涂來恢復(fù)樹的紅黑性質(zhì)。

這樣大家對紅黑樹就有了初步了解。這里就不詳細(xì)介紹了，如果大家有興趣，可以自行去了解。

四、Linux的跨進(jìn)程通信(IPC)概述

(一)、跨進(jìn)程通信(IPC)的目的

跨進(jìn)程通信(IPC)的目的主要如下：

• 數(shù)據(jù)傳遞
  一個(gè)進(jìn)程需要將它的數(shù)據(jù)發(fā)送給另外一個(gè)進(jìn)程，發(fā)送的數(shù)據(jù)量在一個(gè)字節(jié)到幾M字節(jié)之間
• 共享數(shù)據(jù)
  多個(gè)進(jìn)程想要操作共享數(shù)據(jù)。
• 通知事件
  一個(gè)進(jìn)程需要向另一個(gè)或一組進(jìn)程發(fā)送消息，通知它(它們)發(fā)生了某種事件(如進(jìn)程終止時(shí)要通知父進(jìn)程)
• 資源共享
  多個(gè)進(jìn)程之間共享資源。為了做到這一點(diǎn)，需要內(nèi)核提供鎖和同步機(jī)制
• 進(jìn)程控制
  有些進(jìn)程希望完全控制另一個(gè)進(jìn)程的執(zhí)行(如debug進(jìn)程)，此時(shí)控制進(jìn)程希望能夠攔截另一個(gè)進(jìn)程的所有步驟和異常，并能夠及時(shí)知道它的狀態(tài)改變。

(二)、Linux 進(jìn)程間通信(IPC)的發(fā)展

** Linux **下的跨進(jìn)程通信手段基本上是從Unix平臺上的進(jìn)程通信手段繼承而來。而對Unix發(fā)展做出大量貢獻(xiàn)的量大主力AT&T的貝爾實(shí)驗(yàn)室及BSD(加州大學(xué)伯克利分校伯克利軟件發(fā)布中心)在進(jìn)程間通信方面的側(cè)重點(diǎn)有所不同。前者對Unix早期的進(jìn)程間通信手段進(jìn)行了系統(tǒng)的改進(jìn)和擴(kuò)充，形成了"system V IPC"，通信進(jìn)程局限在單個(gè)計(jì)算機(jī)內(nèi)；而后者則跳過了這個(gè)限制，形成了基于套接字(socket)的進(jìn)程間通信機(jī)制。
** Linux **則把兩者繼承了下來。

所以可以把Linux中的進(jìn)程間通信大體分為4類

• 基于早期Unix的進(jìn)程間通信：管道和信號
• 基于System V的進(jìn)程間通信：System V消息隊(duì)列、System V 信號燈、System V 共享內(nèi)存
• 基于Socket 的進(jìn)程間通信：socket
• POSIX進(jìn)程間通信：posix 消息隊(duì)列、posix信號燈、posix共享內(nèi)存

這里說下PSOIX:

由于Unix版本的多樣性，電子電器工程協(xié)會(IEEE) 開發(fā)了一個(gè)獨(dú)立的Unix標(biāo)準(zhǔn)，這個(gè)心的ANSI Unix標(biāo)準(zhǔn)被稱為計(jì)算機(jī)環(huán)境的可移植性操作系統(tǒng)?，F(xiàn)有的大部分Unix和流行版本都是遵循POSIX標(biāo)準(zhǔn)的，而Linux從一開始就是遵循POSIX標(biāo)準(zhǔn)。

三、Linux的跨進(jìn)程通信詳解

在Linux下進(jìn)程通信有以下七種：

• 1、匿名管道(pipe)
• 2、命名管道(FIFO)
• 3、信號(signal)
• 4、信號量(semaphore)
• 5、消息隊(duì)列(message queue)
• 6、共享內(nèi)存(share memory)
• 7、套接字(Socket)

那我們就來詳細(xì)的了解下相關(guān)的內(nèi)容

(一)、匿名管道(pipe)

1、什么是匿名管道？

匿名管道(pipe)是Linux支持的最初Unix IPC形式之一，具有以下特點(diǎn)：

• 匿名管道是半雙工的，數(shù)據(jù)只能向一個(gè)方向流動；需要雙方通信時(shí)，需要建立兩個(gè)管道；
• 只能作用于父子進(jìn)程或者兄弟進(jìn)程之間(具有親緣關(guān)系的進(jìn)程)
• 單獨(dú)構(gòu)成的一種獨(dú)立的文件系統(tǒng)：匿名管道對于管道兩端的進(jìn)程而言，就是一個(gè)文件，但它不是普通文件，它不屬于某種文件系統(tǒng)，而是自理門戶，單獨(dú)構(gòu)成一種文件系統(tǒng)，去并且只存在于內(nèi)存中。
• 數(shù)據(jù)的讀出和寫入：一個(gè)進(jìn)程向管道中寫的內(nèi)容被管道另一端的進(jìn)程讀出。寫入的內(nèi)容每次都添加在管道緩沖區(qū)的末尾，并且每次都是從緩存區(qū)的頭部讀出數(shù)據(jù)。

2、匿名管道的實(shí)現(xiàn)機(jī)制

匿名管道是右內(nèi)核管理的一個(gè)緩沖區(qū)，相當(dāng)于我們放入內(nèi)存的中一個(gè)紙條。匿名管道的一端連接一個(gè)進(jìn)程的輸出。這個(gè)進(jìn)程會向管道中放入信息。匿名管道的另一端連接一個(gè)進(jìn)程的輸入，這個(gè)進(jìn)程取出被放入管道的信息。一個(gè)緩存區(qū)不需要很大，它被設(shè)計(jì)成為喚醒的數(shù)據(jù)結(jié)構(gòu)，以便管道可以被循環(huán)利用。當(dāng)管道中沒有信息的話，從管道中讀取的進(jìn)程會等待，直到另一端的進(jìn)程放入信息。當(dāng)管道被放滿信息的時(shí)候，嘗試放入信息的進(jìn)程就會等待，直到另一端的進(jìn)程取出信息。兩個(gè)進(jìn)程都終結(jié)的時(shí)候，管道也會自動消失。如下圖

image.png

從原理上，匿名管道利用fork機(jī)制建立，從而讓兩個(gè)進(jìn)程可以連接到同一個(gè)PIPE上。最開始的時(shí)候，上面的兩個(gè)箭頭都連接到同一個(gè)進(jìn)程Process 1上(連接在Process 1上的兩個(gè)箭頭)。當(dāng)fork復(fù)制進(jìn)程的時(shí)候，會將這兩個(gè)連接也復(fù)制到新的進(jìn)程(Process 2)。隨后，每個(gè)進(jìn)程關(guān)閉在自己不需要的一個(gè)連接(兩個(gè)黑色的箭頭被關(guān)閉；Process 1關(guān)閉從PIPE來的輸入連接，Process 2關(guān)閉輸出到PIPE的連接)，這樣，剩下的紅色連接就構(gòu)成了上圖的PIPE。
示例圖如下：

image.png

3、匿名管道實(shí)現(xiàn)細(xì)節(jié)

在Linux中，匿名管道的實(shí)現(xiàn)并沒有使用專門的數(shù)據(jù)結(jié)構(gòu)，而是借助了文件系統(tǒng)的file結(jié)構(gòu)，和VFS的索引節(jié)點(diǎn)inode。通過將兩個(gè)file結(jié)構(gòu)指向同一個(gè)臨時(shí)的VFS節(jié)點(diǎn)，而這個(gè)VFS索引節(jié)點(diǎn)又指向了一個(gè)物理頁面而實(shí)現(xiàn)的。如下圖

管道實(shí)現(xiàn)細(xì)節(jié).png

4、關(guān)于匿名管道的讀寫

匿名管道的實(shí)現(xiàn)的源代碼在fs/pipe.c中，在pipe.c中有很多函數(shù)，其中有兩個(gè)函數(shù)比較重要，即匿名管道pipe_read()讀函數(shù)和匿名管道寫函數(shù)pipe_write()。匿名管道寫函數(shù)通過將字節(jié)復(fù)制到VFS索引節(jié)點(diǎn)指向物理內(nèi)存而寫入數(shù)據(jù)，而匿名管道讀函數(shù)則通過復(fù)制物理內(nèi)存而讀出數(shù)據(jù)。當(dāng)然，內(nèi)核必須利用一定的 同步機(jī)制 對管道的訪問，為此內(nèi)核使用了 鎖 、等待隊(duì)列、和 信號。

當(dāng)寫入進(jìn)程向匿名管道中寫入時(shí)，它利用標(biāo)準(zhǔn)的庫函數(shù)write()，系統(tǒng)根據(jù)庫函數(shù)傳遞的文件描述符，可找到該文件的file結(jié)構(gòu)。file結(jié)構(gòu)中制定了用來進(jìn)行寫操作的函數(shù)(即寫入函數(shù))地址，于是，內(nèi)核調(diào)用該函數(shù)完成寫操作。寫入函數(shù)在向內(nèi)存中寫入數(shù)據(jù)之前，必須首先檢查VFS索引節(jié)點(diǎn)中的信息，同時(shí)滿足如下條件時(shí)，才能進(jìn)行實(shí)際的內(nèi)存復(fù)制工作：

• 內(nèi)存中有足夠的空間可以容納所有要寫入的數(shù)據(jù)。
• 內(nèi)存沒有被讀程序鎖定。

如果同時(shí)滿足上述條件，寫入函數(shù)首先會鎖定內(nèi)存，然后從寫進(jìn)程的地址空間中復(fù)制數(shù)據(jù)到內(nèi)存。否則，寫進(jìn)程就休眠在VFS索引節(jié)點(diǎn)的等待隊(duì)列中，接下來，內(nèi)核將調(diào)用調(diào)度程序，而調(diào)度程序會選擇其他進(jìn)程運(yùn)行。寫進(jìn)程實(shí)際處于可中斷的等待狀態(tài)，當(dāng)內(nèi)存中有足夠的空間可以容納寫入數(shù)據(jù)，或內(nèi)存被解鎖時(shí)，讀取進(jìn)程會喚醒寫入進(jìn)程，這時(shí)，寫入進(jìn)程將接受到信號。當(dāng)數(shù)據(jù)寫入內(nèi)存之后，內(nèi)存被解鎖，而所有休眠在索引節(jié)點(diǎn)的讀取進(jìn)程會被喚醒。

匿名管道的讀取過程和寫入過程類型。但是，進(jìn)程可以在沒有數(shù)據(jù)或者內(nèi)存被鎖定時(shí)立即返回錯(cuò)誤信息，而不是阻塞該進(jìn)程，這一來于文件或管道的打開模式。反之，進(jìn)程可以休眠在索引節(jié)點(diǎn)的等待隊(duì)列中等待寫入進(jìn)程寫入數(shù)據(jù)。當(dāng)所有的進(jìn)程完成了管道操作之后，管道的索引節(jié)點(diǎn)被丟棄，而共享數(shù)據(jù)頁被釋放。

PS:有些同學(xué)可能不清楚VFS，我這里就簡單介紹下；

VFS(virtual File System/虛擬文件系統(tǒng)):是Linux文件系統(tǒng)對外的接口。任何要使用文件系統(tǒng)的程序都必須經(jīng)由這層接口來使用它。它是采用標(biāo)準(zhǔn)的Unix系統(tǒng)調(diào)用讀寫位于不同物理介質(zhì)上的不同文件系統(tǒng)。VFS是一個(gè)可以讓open()、read()、write()等系統(tǒng)調(diào)用不用關(guān)系底層的存儲介質(zhì)和文件系統(tǒng)類型就可以工作的粘合層。在Linux中，VFS采用的是面向?qū)ο蟮木幊谭椒ā?/p>

(二)、命名管道(FIFO/named PIPE)

在上面，我們介紹了匿名管道(pipe)，我們知道了如何匿名管道在進(jìn)程之間傳遞數(shù)據(jù)，同時(shí)也是看到了這個(gè)方式的一個(gè)缺陷，就是這些就進(jìn)程都是由一個(gè)共同的祖先進(jìn)程啟動，這給我們在不相關(guān)的進(jìn)程之間交換數(shù)據(jù)帶來了不方便。這里我將會介紹另一種通信方式——命名管道，來解決不相關(guān)進(jìn)程之間的問題。

1、什么是命名管道?

• 命名管道也被稱為FIFO或者named pipe，它是一種特殊類型的文件，它在文件系統(tǒng)中以文件名的形式存在，但是它的行為卻和之前所講的匿名管道類似。
• FIFO(First in, First out) 為一種特殊的文件類型，它在文件系統(tǒng)中有對應(yīng)的路徑。當(dāng)一個(gè)進(jìn)程以讀(r)的方式打開該文件，而另一個(gè)進(jìn)程以寫(w)的方式打開該文件，那么內(nèi)核就會在兩個(gè)進(jìn)程之間建立管道，所以FIFO實(shí)際上也由內(nèi)核管理，不與硬盤打交道。之所以叫FIFO，因?yàn)楣艿辣举|(zhì)上是一個(gè)** 先進(jìn)先出的隊(duì)列數(shù)據(jù)結(jié)構(gòu) ，最早放入的數(shù)據(jù)被最先讀出來，從而保證信息交流的順序。FIFO只是借用了文件系統(tǒng)(file system，命名管道是一種特殊類型的文件，因?yàn)長inux中所有事物都是文件，它是在文件系統(tǒng)中以文件名的形式存在。)來為管道命名。寫模式的進(jìn)程向FIFO中寫入，而讀模式的進(jìn)程從FIFO文件中讀出。當(dāng)刪除FIFO文件時(shí)，管道連接也隨之小時(shí)。FIFO的好處在于我們可以通過 文件的路徑來識別管道，從而讓沒有親緣關(guān)系的進(jìn)程之間建立連接 **。

2、命名管道的讀寫規(guī)則：

• 1、從FIFO中讀取數(shù)據(jù)的約定：如果一個(gè)進(jìn)程為了從FIFO中讀取數(shù)據(jù)而阻塞打開了FIFO，那么該進(jìn)程內(nèi)的讀操作 為設(shè)置了阻塞標(biāo)志的讀操作。
• 2、從FIFO中寫入數(shù)據(jù)的約定：如果一個(gè)進(jìn)程為了想FIFO中寫入數(shù)據(jù)而阻塞打開了FIFO，那么該進(jìn)程內(nèi)的寫操作 為設(shè)置了阻塞標(biāo)志的寫操作。

3、命名管道的安全問題：

大家想一下，只使用一個(gè)FIFO文件，如果有多個(gè)進(jìn)程同時(shí)向同一個(gè)FIFO文件寫數(shù)據(jù)，而只有一個(gè)讀FIFO進(jìn)程在同一個(gè)FIFO文件讀取數(shù)據(jù)時(shí)，會發(fā)生怎么樣的情況呢，會發(fā)生數(shù)據(jù)塊的相互交錯(cuò)是很正常的？而且個(gè)人認(rèn)為多個(gè)不同進(jìn)程向一個(gè)FIFO讀取進(jìn)程發(fā)送數(shù)據(jù)是很正常的情況。

為了解決這個(gè)問題，就是讓寫操作原子化，怎么才能使寫操作原子化呢？答案其實(shí)很簡單：系統(tǒng)規(guī)定，在一個(gè)以O(shè)_WRONLY(即阻塞方式)打開的FIFO中，如果寫入的數(shù)據(jù)長度小于等于PIPE_BUF，那么或者寫入全部字節(jié)，或者一個(gè)字節(jié)都不寫入。如果所有的寫請求都是發(fā)往一個(gè)阻塞的FIFO的，并且每個(gè)寫請求的數(shù)據(jù)長度小于等于PIPE_BUF字節(jié)，系統(tǒng)就可以確保數(shù)據(jù)絕不會交錯(cuò)在一起。

(三)、信號(Signal)

1、什么是信號？

信號是比較復(fù)雜的通信方式，用于通知接受進(jìn)程有某種事件發(fā)生，除了用于進(jìn)程間通信外，進(jìn)程還可以發(fā)送信號給進(jìn)程本身；Linux除了支持Unix早期信號語義函數(shù)sigal外，還支持語義服務(wù)Posix.1標(biāo)準(zhǔn)的信號函數(shù)sigaction(實(shí)際上，該函數(shù)是基于BSD的，BSD為了實(shí)現(xiàn)可靠信號機(jī)制，有能夠統(tǒng)一對外接口，用sigaction函數(shù)重新實(shí)現(xiàn)了signal函數(shù))

2、信號的種類

如下圖:

信號種類.png

每種信號類型都有對應(yīng)的信號處理程序(也叫信號的操作)，就好像每個(gè)中斷都有一個(gè)中斷服務(wù)例程一樣。大多數(shù)信號的默認(rèn)操作是結(jié)束接受信號的進(jìn)程；然而一個(gè)進(jìn)程通?？梢哉埱笙到y(tǒng)采取某些代替的操作，各種代替操作是：

• 忽略信號。隨著這一選項(xiàng)的設(shè)置，進(jìn)程將忽略信號的出現(xiàn)。有兩個(gè)信號不可以被忽略：SIGKILL，它將結(jié)束進(jìn)程：SIGSTOP，它是作業(yè)控制機(jī)制的一部分，將掛起作業(yè)的執(zhí)行。
• 恢復(fù)信號的默認(rèn)操作
• 執(zhí)行一個(gè)預(yù)先安排的信號處理函數(shù)。進(jìn)程可以登記特殊的信號處理函數(shù)。當(dāng)進(jìn)程收到信號時(shí)，信號處理函數(shù)將像中斷服務(wù)例程一樣被調(diào)用，當(dāng)從信號處理函數(shù)返回時(shí)，控制被返回給主程序，并且繼續(xù)正常執(zhí)行。

但是，信號和中斷有所不同。中斷的響應(yīng)和處理都發(fā)生在內(nèi)核空間，而信號的響應(yīng)發(fā)生在內(nèi)核空間，信號處理程序的執(zhí)行卻發(fā)生在用戶空間。
那么什么時(shí)候檢測和響應(yīng)信號？通常發(fā)生在兩種情況下：

• 當(dāng)前進(jìn)程由于系統(tǒng)調(diào)用、中斷或異常而進(jìn)入內(nèi)核空間以后，從內(nèi)核空間返回到用戶空間前戲
• 當(dāng)前進(jìn)程在內(nèi)核進(jìn)入睡眠以后剛被喚醒的時(shí)候，由于檢測到信號的存在而提前返回到用戶空間

3、信號的本質(zhì)

信號是在軟件層次上對中斷機(jī)制的一種模擬，在原理上，一個(gè)進(jìn)程收到一個(gè)信號與處理器收到一個(gè)中斷請求可以說是一樣的。信號是異步的，一個(gè)進(jìn)程不必通過任何操作來等待信號的到達(dá)，事實(shí)上，進(jìn)程也不知道信號到底什么時(shí)候到達(dá)。

信號是進(jìn)程間通信機(jī)制中唯一的異步通信機(jī)制，可以看作是異步通知，通知接收信號的進(jìn)程有哪些事情發(fā)生了。信號機(jī)制經(jīng)過POSIX實(shí)時(shí)擴(kuò)展后，功能更加強(qiáng)大，除了基本通知功能外，還可以傳遞附加信息。

4、信號來源

信號事件的發(fā)生有兩個(gè)來源：硬件來源(比如我們按下鍵盤或者其他硬件故障)；潤健來源，最常用發(fā)送信號的系統(tǒng)函數(shù)是kill，raise,alarm和setitimer以及sigqueue函數(shù)，軟件來源還包括一些非法運(yùn)算等操作。

5、關(guān)于信號處理機(jī)制的原理(內(nèi)核角度)

內(nèi)核給一個(gè)進(jìn)程發(fā)送中斷信號，是在進(jìn)程所在的進(jìn)程表項(xiàng)的信號域設(shè)置對應(yīng)于該信號的位。這里要補(bǔ)充的是，如果信號發(fā)送給一個(gè)正在睡眠的進(jìn)程，那么要看該進(jìn)程進(jìn)入睡眠的優(yōu)先級，如果進(jìn)程睡眠在可被中斷的優(yōu)先級上，則喚醒正在睡眠的進(jìn)程；否則僅設(shè)置進(jìn)程表中信號域相應(yīng)的位，而不是喚醒進(jìn)程。這一點(diǎn)比較重要，因?yàn)檫M(jìn)程檢查是否收到信號的時(shí)機(jī)是：一個(gè)進(jìn)程在即將從內(nèi)核態(tài)返回到用戶態(tài)時(shí)；或者，在一個(gè)進(jìn)程進(jìn)入或離開一個(gè)適當(dāng)?shù)牡驼{(diào)度優(yōu)先級睡眠狀態(tài)時(shí)。

內(nèi)核處理一個(gè)進(jìn)程吸收的信號的時(shí)機(jī)是在一個(gè)進(jìn)程從內(nèi)核態(tài)返回用戶態(tài)時(shí)。所以，當(dāng)一個(gè)進(jìn)程在內(nèi)核態(tài)下運(yùn)行時(shí)，軟中斷信號并不立即起作用，要等到將返回用戶態(tài)時(shí)才處理。進(jìn)程只有處理完信號才會返回用戶態(tài)，進(jìn)程在用戶態(tài)下不會有未處理完的信號。

內(nèi)核處理一個(gè)進(jìn)程收到的軟中斷信號是在該進(jìn)程的上下文中。因此，進(jìn)程必須處于運(yùn)行狀態(tài)。如果進(jìn)程收到一個(gè)要捕捉的信號，那么進(jìn)程從內(nèi)核態(tài)返回用戶態(tài)時(shí)執(zhí)行用戶定義的函數(shù)。而且執(zhí)行用戶定義的函數(shù)的方法很巧妙，內(nèi)核是在用戶棧上創(chuàng)建一個(gè)新的層，該層中將返回地址的值設(shè)置成用戶定義的處理函數(shù)的地址，這樣進(jìn)程從內(nèi)核返回彈出棧頂時(shí)就返回到用戶定義的函數(shù)出，從函數(shù)返回再彈出棧頂時(shí)，才返回原先進(jìn)入內(nèi)核的地方，接著原來的地方繼續(xù)運(yùn)行。這樣做的原因是用戶定義的處理函數(shù)不能切不允許在內(nèi)核態(tài)下執(zhí)行。

6、信號的生命周期

信號的生命周期.png

(四)、信號量(semaphore)

1、什么是信號量

信號量又稱為信號燈，它用來協(xié)調(diào)不用進(jìn)程間的數(shù)據(jù)對象，而最主要的應(yīng)用是共享內(nèi)存方式的進(jìn)程間通信。本質(zhì)上，信號量時(shí)一個(gè)計(jì)數(shù)器，他用來記錄某個(gè)資源(如共享內(nèi)存)的存取狀況。信號量的使用，主要是用來保護(hù)共享資源，使得資源在一個(gè)時(shí)刻只有一個(gè)進(jìn)程(線程)所擁有。

信號量的值為正的時(shí)候，說明它空閑。所有的線程可以鎖定而使用它。若為0，說明它被占用，測試的線程要進(jìn)入睡眠隊(duì)列中，等待被喚醒。

2、信號量的注意事項(xiàng)

• 為了防止出現(xiàn)因多個(gè)程序同時(shí)訪問一個(gè)共享資源而引發(fā)的一系列問題，我們需要這一種方法，它可以通過生成并使用令牌來授權(quán)，在任一時(shí)刻只能由一個(gè)執(zhí)行線程訪問代碼的臨界區(qū)域
• 臨界區(qū)域是指執(zhí)行數(shù)據(jù)更新的代碼需要獨(dú)占式地執(zhí)行。而信號量就可以提供這樣的一種訪問機(jī)制，讓一個(gè)臨界區(qū)同一時(shí)間只有一個(gè)線程在訪問它，也就說信號量臨界區(qū)是指執(zhí)行數(shù)據(jù)更新的代碼需要獨(dú)占式地執(zhí)行。而信號量就可以提供這樣的一種訪問機(jī)制，讓一個(gè)臨界區(qū)同一時(shí)間只有一個(gè)線程在訪問它，也就說信號量是用來協(xié)調(diào)進(jìn)程對共享資源的訪問。
• 信號量時(shí)一個(gè)特殊的變量，程序?qū)ζ湓L問都是原子操作，且只允許對它進(jìn)行等待(即P-信號變量)和發(fā)送(即V信號變量)信息操作。
• 最簡單的信號量只能取0和1的變量，這也是信號量最常見的一種形式，叫做二進(jìn)制信號量。而可以取多個(gè)正整數(shù)的信號量被稱為通用信號量

3、信號量的原理

由于信號量只能進(jìn)行兩種操作即"等待"和"發(fā)送"，即P(sv)和V(sv)，他們的行為是這樣：

• P(sv):如果sv的值大于零，就給它減1；如果它的值為零，就掛起該進(jìn)程的執(zhí)行
• V(sv):如果有其他進(jìn)程因等待sv而被掛起，就讓它恢復(fù)運(yùn)行，如果沒有進(jìn)程因等待sv而掛起，就給它加1。

舉個(gè)例子，就是兩個(gè)進(jìn)程共享信號量sv，一旦其中一個(gè)進(jìn)程執(zhí)行了P(sv)操作，他將得到信號量，并可以進(jìn)如臨界區(qū)，使sv減1。而第二個(gè)進(jìn)程將被阻止進(jìn)入臨界區(qū)，因?yàn)楫?dāng)它試圖執(zhí)行P(sv)時(shí)，sv為0，它會掛起以等待第一個(gè)進(jìn)程離開臨界區(qū)并執(zhí)行(sv)釋放信號。

3、信號量的分類

Linux提供兩種信號量

• 內(nèi)核信號量：由內(nèi)核控制路徑使用
• 用戶態(tài)進(jìn)程使用的信號量：這種信號量又分為POSIX信號量和SYSTEM V信號量

POSIX辛信號量又分為有名信號量和無名信號量

• 有名信號量：其值保存在文件中，所以它可以用于線程也可以用于進(jìn)程間同步
• 無名信號量：其值保存在內(nèi)存。

POSIX信號量和SYSTEM V信號量的比較

• 對POSIX來說，信號量是個(gè)非負(fù)數(shù)。常用于線程間同步
  而SYSTEM V信號量則是一個(gè)或者多個(gè)信號量集合，他對應(yīng)的是一個(gè)信號量的結(jié)構(gòu)體，這個(gè)結(jié)構(gòu)體為SYSTEM V IPC服務(wù)的，信號量只不過是它的一部分。常用語進(jìn)程間同步。
• POSIX信號量的引用頭文件是<semaphore,h>，而SYSTEM V信號量的引用頭文件是<sys/sem.h>

• 從使用的角度，System V信號量是簡單的。比如，POSIX信號量的創(chuàng)建和初始化PV操作就很方便。

(五)、消息隊(duì)列(message)

1、消息隊(duì)列也稱為報(bào)文隊(duì)列：

消息隊(duì)列也成為報(bào)文隊(duì)列，消息隊(duì)列是隨內(nèi)核持續(xù)的，只有在內(nèi)核重其或者顯示刪除一個(gè)消息隊(duì)列時(shí)，該消息隊(duì)列才會真正刪除系統(tǒng)中記錄消息隊(duì)列的數(shù)據(jù)結(jié)構(gòu)體 struct ipc_ids_msg_ids位于內(nèi)核中，系統(tǒng)中所有消息隊(duì)列都可以在結(jié)構(gòu)msg_ids中找到訪問入口。

2、消息隊(duì)列的原理及注意事項(xiàng)：

• 消息隊(duì)列其實(shí)就是一個(gè)消息的鏈表，每個(gè)消息都有一個(gè)隊(duì)列頭，稱為struct_msg_queue，這個(gè)隊(duì)列頭描述了消息隊(duì)列的key值，用戶ID，組ID等信息，但它存于內(nèi)核中而結(jié)構(gòu)體struct msqid_ds能夠返回或設(shè)置消息隊(duì)列的信息，這個(gè)結(jié)構(gòu)體位于用戶空間中，與msg_queue結(jié)構(gòu)相似的消息隊(duì)列允許一個(gè)或多個(gè)進(jìn)程向它寫入或讀取消息，消息隊(duì)列是消息的鏈表。
• 消息是按消息類型訪問，進(jìn)程必須指定消息類型來讀取消息，同樣，當(dāng)向消息隊(duì)列中寫入消息事業(yè)必須給出消息的類型，如果讀隊(duì)列使用消息的類型為0，則讀取隊(duì)列中的第一條消息。
• 內(nèi)核空間的結(jié)構(gòu)體msg_queue描述了對應(yīng)key值消息隊(duì)列的情況，而對應(yīng)用戶空間的msqid_ds這個(gè)結(jié)構(gòu)體，因此，可以操作msgid_ds這個(gè)結(jié)構(gòu)體來操作消息隊(duì)列。

(六)、共享內(nèi)存(share memory)

共享內(nèi)存是進(jìn)程間通信中最簡單的方式之一。

1、什么是共享內(nèi)存?

共享內(nèi)存是系統(tǒng)處于多個(gè)進(jìn)程之間通訊的考慮，而預(yù)留的一塊內(nèi)存區(qū)。共享內(nèi)存允許兩個(gè)或更多的進(jìn)程訪問同一塊內(nèi)存，就如同malloc()函數(shù)向不同進(jìn)程返回了指向同一個(gè)物理內(nèi)存區(qū)域的指針。當(dāng)一個(gè)進(jìn)程改變了這塊地址中的內(nèi)容的時(shí)候，其他進(jìn)程都會覺察到這個(gè)更改。

2、關(guān)于共享內(nèi)存

• 當(dāng)一個(gè)程序加載進(jìn)內(nèi)存后，它就被分成叫做頁的塊。通信將存在內(nèi)存的兩個(gè)頁之間或者兩個(gè)獨(dú)立的進(jìn)程之間?？傊?，當(dāng)一個(gè)程序想和另外一個(gè)程序通信的時(shí)候，那內(nèi)存將會為這兩個(gè)程序生成一塊公共的內(nèi)存區(qū)域。這塊被兩個(gè)進(jìn)程分享的內(nèi)存區(qū)域叫做共享內(nèi)存。
• 由于所有進(jìn)程共享同一塊內(nèi)存，共享內(nèi)存在各種進(jìn)程間通信方式中具有最高的效率。訪問共享內(nèi)存區(qū)域和訪問進(jìn)程獨(dú)有的內(nèi)存區(qū)域一樣快，并不需要通過系統(tǒng)調(diào)用或者其他需要切入內(nèi)核的過程來完成。同時(shí)它也也避免了對數(shù)據(jù)的跟中不必要的復(fù)制。
• 如果沒有共享內(nèi)存的概念，那一個(gè)進(jìn)程不能存取另外一個(gè)進(jìn)程的內(nèi)存部分，因而導(dǎo)致共享數(shù)據(jù)或者通信失效。因?yàn)橄到y(tǒng)內(nèi)核沒有對訪問共享內(nèi)存進(jìn)行同步，開發(fā)者必須提供自己的同步措施。
• 解決了這些問題的常用方法是是通過信號量進(jìn)行同步。不過通常我們程序只有一個(gè)進(jìn)程訪問了共享內(nèi)存，因此在集中展示了共享內(nèi)存機(jī)制的同時(shí)，我們避免了讓代碼被同步邏輯搞的混亂不堪。

為了簡化共享數(shù)據(jù)的完整性和避免同時(shí)存取數(shù)據(jù)，內(nèi)核提供了一種專門存取共享內(nèi)存資源的機(jī)制。這稱為互斥體或者M(jìn)utex對象。

3、Mutex對象

例如，在數(shù)據(jù)被寫入前不允許進(jìn)程從共享內(nèi)存中讀取信息、不允許兩個(gè)進(jìn)程同時(shí)向一個(gè)共享內(nèi)存地址寫入數(shù)據(jù)等。

當(dāng)一個(gè)基礎(chǔ)想和兩一個(gè)進(jìn)程通信的時(shí)候，它將按以下順序運(yùn)行：

• 1、獲取Mutex對象，鎖定共享區(qū)域
• 2、將要通信的數(shù)據(jù)寫入共享區(qū)域
• 3、釋放Mutex對象

當(dāng)一個(gè)進(jìn)程從這個(gè)區(qū)域讀取數(shù)據(jù)的時(shí)候，它將重復(fù)同樣的步驟，只是將第二步變成讀取。

4、內(nèi)存模型

要使用一塊共享內(nèi)存

• 進(jìn)程必須首先分配它
• 隨后需要訪問這個(gè)共享內(nèi)存塊的每一個(gè)進(jìn)程都必須將這個(gè)共享內(nèi)存綁定到自己的地址空間中。
• 當(dāng)完成通信之后，所有進(jìn)程都脫離共享內(nèi)存，并且由一個(gè)進(jìn)程釋放該共享內(nèi)存塊。

在/proc/sys/kernel/目錄下，記錄著共享內(nèi)存的一些限制，如一個(gè)共享內(nèi)存區(qū)的最大字節(jié)數(shù)shmmax，系統(tǒng)范圍內(nèi)最大的共享內(nèi)存區(qū)標(biāo)志符數(shù)shmmni等。

5、Linux系統(tǒng)內(nèi)存模型

• 在Linux系統(tǒng)中，每個(gè)進(jìn)程的虛擬內(nèi)存是被分為許多頁面的。這些內(nèi)存頁面中包含了實(shí)際的數(shù)據(jù)。每個(gè)進(jìn)程都會維護(hù)一個(gè)從內(nèi)存地址到虛擬內(nèi)存頁面之間的映射關(guān)系。盡管每個(gè)進(jìn)程都有自己的內(nèi)存地址，不同的進(jìn)程可以同時(shí)將同一個(gè)頁面頁面映射到自己的地址空間，從而達(dá)到共享內(nèi)存的目的。
• 分配一個(gè)新的共享內(nèi)存塊會創(chuàng)建新的內(nèi)存頁面。因?yàn)樗羞M(jìn)程都希望共享對同一塊內(nèi)存的訪問，只應(yīng)由一個(gè)進(jìn)程創(chuàng)建一塊新的共享內(nèi)存。再次分配一塊已經(jīng)存在的內(nèi)存塊不會創(chuàng)建新的頁面，而只是會返回一個(gè)標(biāo)示該內(nèi)存塊的標(biāo)識符。
• 一個(gè)進(jìn)程如需使用這個(gè)共享內(nèi)存塊，則首先需要將它綁定到自己的地址空間中。
• 這樣會創(chuàng)建一個(gè)從進(jìn)程本身虛擬地址到共享頁面的映射關(guān)系。當(dāng)對共享內(nèi)存的使用結(jié)束之后，這個(gè)映射關(guān)系將被刪除。
• 當(dāng)再也沒有京城需要使用這個(gè)共享內(nèi)存塊的時(shí)候，必須有一個(gè)(有且只有一個(gè))進(jìn)程負(fù)責(zé)釋放這個(gè)被共享的內(nèi)存頁面。
• 所有共享內(nèi)存塊的大小必須是系統(tǒng)頁面大小的整數(shù)倍。系統(tǒng)頁面大小指的是系統(tǒng)中單個(gè)內(nèi)存頁面包含的字節(jié)數(shù)。在Linux系統(tǒng)中，內(nèi)存頁面大小是4KB，不過您仍然應(yīng)高通過調(diào)用getPageSize獲取這個(gè)值。

6、Linux共享內(nèi)存的實(shí)現(xiàn)步驟

共享內(nèi)存的實(shí)現(xiàn)分為兩個(gè)步驟:

• 創(chuàng)建共享內(nèi)存，使用shmget函數(shù)
• 映射共享內(nèi)存，將這段創(chuàng)建的共享內(nèi)存映射到具體的進(jìn)程空間中，使用shmat函數(shù)

(七)、套接字(socket)

套接字也是一種進(jìn)程間通信機(jī)制，與其他通信機(jī)制不同的是，它可用于不同機(jī)器間的進(jìn)程通信。
更為一般的進(jìn)程間通信機(jī)制，可用于不同機(jī)器之間的進(jìn)程間通信。起初是右Unix系統(tǒng)的BSD分之開發(fā)出來的，但是現(xiàn)在一般可以移植其他類Unix系統(tǒng)上。比如Linux和System V的變種都支持套接字。

(八) Linux的幾種跨進(jìn)程通信的方式的比較

1、效率比較

PS：無連接是指無需調(diào)用某種行動是OPEN，就有發(fā)送消息的能力流控制，如果系統(tǒng)資源短缺或者不能接受更多的消息，則發(fā)送進(jìn)程能進(jìn)進(jìn)行流量控制。

2、優(yōu)缺點(diǎn)比較

• 匿名管道(pipe)：速度慢，容量有限，只有父子進(jìn)程能通訊
• 有名管道(FIFO)： 任務(wù)進(jìn)程都能通訊，但速度慢
• 消息隊(duì)列(message queue)：容量收到系統(tǒng)限制，且要注意第一次讀的時(shí)候，要考慮上一次沒有讀完數(shù)據(jù)問題。
• 信號量：不能傳遞復(fù)雜消息，只能用來同步
• 共享內(nèi)存區(qū)：能夠容易控制容量，速度快，但要保持同步，比如一個(gè)進(jìn)程在寫的時(shí)候，另一個(gè)進(jìn)程要注意讀寫的問題。相當(dāng)于線程中的線程安全，當(dāng)然，共享內(nèi)存區(qū)同樣可以做線程間通訊，不過沒有這個(gè)必要，線程間本來就已經(jīng)共享了同一進(jìn)程內(nèi)的一塊內(nèi)存

3、使用場景

• 如果用戶傳遞的信息較少或是需要通過信號來出發(fā)某些行為，上面提到的軟中斷限號機(jī)制不失為一種簡潔有效的一種進(jìn)程間通信方式。但若是進(jìn)程間要求傳遞的信息量比較大或者進(jìn)程間存在交換數(shù)據(jù)的要求，那就需要考慮別的通信方式。
• 匿名管道簡單方便，但局限于單向通信的工作方式，并且只能創(chuàng)建它的進(jìn)程及其子孫進(jìn)程之間實(shí)現(xiàn)管道的共享。

• 有名管道雖然可以提供給任意關(guān)系的進(jìn)程使用，但是由于其長期存在于系統(tǒng)之中，使用不當(dāng)容易出錯(cuò)。所以不建議初級開發(fā)者使用。

• 消息緩存可以不再局限于父子進(jìn)程，而允許任意進(jìn)程間通過共享消息隊(duì)列來實(shí)現(xiàn)進(jìn)程間通信，并由系統(tǒng)調(diào)用函數(shù)來實(shí)現(xiàn)消息發(fā)送和接受方之間的同步，從而使得用戶在使用消息緩沖進(jìn)行通信時(shí)不再需要考慮同步問題，使用方便，但是信息的復(fù)制需要額外的消耗CPU的時(shí)間，不適宜信息量大或操作頻繁的場合。
• 共享內(nèi)存針對消息緩存的缺點(diǎn)而改進(jìn)，利用了內(nèi)存緩存區(qū)直接交換信息，無需復(fù)制，快捷、信息量大的是其優(yōu)點(diǎn)。但是共享內(nèi)存的通信方式是通過將共享內(nèi)存緩存直接附加到進(jìn)程的虛擬地址空間中來實(shí)現(xiàn)的。因此這些進(jìn)程之間的讀寫操作的同步問題操作系統(tǒng)無法實(shí)現(xiàn)。必須由各進(jìn)程利用其它同步工具解決。另外， 由于內(nèi)存實(shí)體存在于計(jì)算機(jī)系統(tǒng)中，所以只能由處于同一個(gè)計(jì)算機(jī)系統(tǒng)中的其它進(jìn)程共享，不方便網(wǎng)絡(luò)通信。

補(bǔ)充一點(diǎn):
共享內(nèi)存塊提供了在任意數(shù)量的進(jìn)程之間進(jìn)行高效雙向通信的機(jī)制。每個(gè)使用者都可以讀取寫入數(shù)據(jù)，但是所有程序之間必須達(dá)成并遵守一定的協(xié)議，以防止諸如在讀取信息之前覆寫內(nèi)存空間等競爭狀態(tài)的出現(xiàn)。不行的是，Linux無法嚴(yán)格保證提供對共享內(nèi)存塊的獨(dú)占訪問，同時(shí)，多個(gè)使用共享內(nèi)存塊的進(jìn)程之間必須協(xié)調(diào)使用同一個(gè)鍵值。