操作系统-并发性：互斥与同步
操作系統(tǒng)設(shè)計(jì)中的核心問題是進(jìn)程和線程的管理
那么關(guān)于進(jìn)程和線程的管理涉及到的問題就包括：
要處理好上面所說的問題，就不得不提到并發(fā)，并發(fā)是所有問題的基礎(chǔ)，也是操作系統(tǒng)設(shè)計(jì)的基礎(chǔ)。并發(fā)包括很多設(shè)計(jì)問題，其中有進(jìn)程間通信、資源共享與競爭（如內(nèi)存、文件、I/O訪問）、多個(gè)進(jìn)程活動(dòng)的同步以及給進(jìn)程分配處理器時(shí)間等。我們將會(huì)看到這些問題不僅會(huì)出現(xiàn)在多處理器環(huán)境和分布式處理器環(huán)境中，也會(huì)出現(xiàn)在單處理器的多道程序設(shè)計(jì)系統(tǒng)中。
并發(fā)會(huì)在以下三種不同的上下文中出現(xiàn)：
在接下來的描述中，你將會(huì)看到以下內(nèi)容：
同時(shí)，本章通過兩個(gè)經(jīng)典的并發(fā)問題（1. 生產(chǎn)者/消費(fèi)者問題 2.讀者/寫者問題）來說明并發(fā)的概念，并對(duì)本書中使用的解決并發(fā)的各種方法進(jìn)行比較。
在介紹并發(fā)之前，我們先來看看關(guān)于并發(fā)的關(guān)鍵術(shù)語。
5.1 并發(fā)的原理
在單處理器多道程序設(shè)計(jì)系統(tǒng)中，進(jìn)程會(huì)被交替地執(zhí)行，因而表現(xiàn)出一種并發(fā)執(zhí)行的外部特征。即使不能實(shí)現(xiàn)真正的并行處理，并且在進(jìn)程間來回切換也需要一定的開銷，交替執(zhí)行在處理效率和程序結(jié)構(gòu)上還是會(huì)帶來很多好處。在多處理器系統(tǒng)中，不僅可以交替執(zhí)行進(jìn)程，而且可以重疊執(zhí)行進(jìn)程。
從表面上看，交替和重疊代表了完全不同的執(zhí)行模式和不同的問題。實(shí)際上，這兩種技術(shù)都可視為并發(fā)處理的一個(gè)實(shí)例，并且都代表了同樣的問題。在單處理器情況下，問題源于多道程序設(shè)計(jì)系統(tǒng)的一個(gè)基本特性：進(jìn)程的相對(duì)執(zhí)行速度不可預(yù)測，它取決于其他進(jìn)程的活動(dòng)、操作系統(tǒng)處理中斷的方式以及操作系統(tǒng)的調(diào)度策略。這就帶來了下列困難：
上述所有困難在多處理器系統(tǒng)中都有具體的表現(xiàn)，因?yàn)樵谶@樣的系統(tǒng)中進(jìn)程執(zhí)行的相對(duì)速度也是不可預(yù)測的。多處理器系統(tǒng)還必須處理多個(gè)進(jìn)程同時(shí)執(zhí)行所引發(fā)的問題，從根本上說，這些問題和單處理器系統(tǒng)中的是相同的，隨著討論的深入，這些問題將逐漸明了。
5.1.1 競爭條件
競爭條件發(fā)生在多個(gè)進(jìn)程或線程讀寫數(shù)據(jù)時(shí)，其最終結(jié)果取決于多個(gè)進(jìn)程的指令執(zhí)行順序。考慮下面兩個(gè)簡單的例子。
在第一個(gè)例子中，假設(shè)兩個(gè)進(jìn)程P1和P2共享全局變量a。在Pl執(zhí)行的某一時(shí)刻，它將a的值更新為1，在P2執(zhí)行的某一時(shí)刻，它將a的值更新為2。因此，兩個(gè)任務(wù)競爭更新變量a。在本例中，競爭的“失敗者”（即最后更新全局變量a的進(jìn)程）決定了變量a的最終值。
在第二個(gè)例子中，考慮兩個(gè)進(jìn)程P3和P4共享全局變量b和c，且初始值為b=1，c=2。在某一執(zhí)行時(shí)刻，P3執(zhí)行賦值語句b=b+c，在另一執(zhí)行時(shí)刻，P4執(zhí)行賦值語句c=b+c。兩個(gè)進(jìn)程更新不同的變量，但兩個(gè)變量的最終值取決于兩個(gè)進(jìn)程執(zhí)行賦值語句的順序。若P3首先執(zhí)行賦值語句，則最終值為b=3，c=5；若P4首先執(zhí)行賦值語句，則最終值為b=4，c=3。
總結(jié)為一句話的話，就是上面關(guān)于并發(fā)的關(guān)鍵術(shù)語中所說的：多個(gè)線程或進(jìn)程在讀寫一個(gè)共享數(shù)據(jù)時(shí)，結(jié)果依賴于它們執(zhí)行的相對(duì)時(shí)間的情形
操作系統(tǒng)必須保證一個(gè)進(jìn)程的功能和輸出結(jié)果必須與執(zhí)行速度無關(guān)（相對(duì)于其他并發(fā)進(jìn)程的執(zhí)行速度）。這是本章的主題。為理解如何解決與執(zhí)行速度無關(guān)的問題，我們首先需要考慮進(jìn)程間的交互方式。
5.1.2 進(jìn)程的交互
我們可以根據(jù)進(jìn)程相互之間知道對(duì)方是否存在的程度，對(duì)進(jìn)程間的交互方式進(jìn)行分類。下表列出了三種可能的感知程度及每種感知程度的結(jié)果。
- 進(jìn)程之間相互不知道對(duì)方的存在：這是一些獨(dú)立的進(jìn)程，它們不會(huì)一起工作。關(guān)于這種情況的最好例子是多個(gè)獨(dú)立進(jìn)程的多道程序設(shè)計(jì)，可以是批處理作業(yè)，也可以是交互式會(huì)話，或者是兩者的混合。盡管這些進(jìn)程不會(huì)一起工作，但操作系統(tǒng)需要知道它們對(duì)資源的競爭情況。例如，兩個(gè)無關(guān)的應(yīng)用程序可能都想訪問同一個(gè)磁盤、文件或打印機(jī)。操作系統(tǒng)必須控制對(duì)它們的訪問。
- 進(jìn)程間接知道對(duì)方的存在：這些進(jìn)程并不需要知道對(duì)方的進(jìn)程ID，但它們共享某些對(duì)象，如一個(gè)I/0緩沖區(qū)。這類進(jìn)程在共享同一個(gè)對(duì)象時(shí)會(huì)表現(xiàn)出合作行為（cooperation）。
- 進(jìn)程直接知道對(duì)方的存在：這些進(jìn)程可通過進(jìn)程ID互相通信，以合作完成某些活動(dòng)。同樣，這類進(jìn)程表現(xiàn)出合作行為。
實(shí)際條件并不總是像表5.2中給出的那么清晰，例如幾個(gè)進(jìn)程可能既表現(xiàn)出競爭，又表現(xiàn)出合作。然而，對(duì)操作系統(tǒng)而言，分別檢查表中的每一項(xiàng)并確定它們的本質(zhì)是必要的。接下來，我們將對(duì)上面三項(xiàng)關(guān)系進(jìn)行一一的闡述。
進(jìn)程間的資源競爭：
當(dāng)并發(fā)進(jìn)程競爭使用同一資源時(shí)，它們之間會(huì)發(fā)生沖突。我們可以把這種情況簡單描述如下：兩個(gè)或更多的進(jìn)程在它們的執(zhí)行過程中需要訪問一個(gè)資源，每個(gè)進(jìn)程并不知道其他進(jìn)程的存在，且每個(gè)進(jìn)程也不受其他進(jìn)程的影響。每個(gè)進(jìn)程都不影響它所用資源的狀態(tài)，這類資源包括IVO設(shè)備、存儲(chǔ)器、處理器時(shí)間和時(shí)鐘。
競爭進(jìn)程間沒有任何信息交換，但一個(gè)進(jìn)程的執(zhí)行可能會(huì)影響到競爭進(jìn)程的行為。特別是當(dāng)兩個(gè)進(jìn)程都期望訪問同一個(gè)資源時(shí)，如果操作系統(tǒng)把這個(gè)資源分配給一個(gè)進(jìn)程，那么另一個(gè)進(jìn)程就必須等待。因此，被拒絕訪問的進(jìn)程的執(zhí)行速度就會(huì)變慢。一種極端情況是，被阻塞的進(jìn)程永遠(yuǎn)不能訪問這個(gè)資源，因此該進(jìn)程永遠(yuǎn)不能成功結(jié)束運(yùn)行。
競爭進(jìn)程面臨三個(gè)控制問題。首先需要互斥（mutual exclusion）。假設(shè)兩個(gè)或更多的進(jìn)程需要訪問一個(gè)不可共享的資源，如打印機(jī)。在執(zhí)行過程中，每個(gè)進(jìn)程都給該IVO設(shè)備發(fā)命令，接收狀態(tài)信息，發(fā)送數(shù)據(jù)和接收數(shù)據(jù)。我們把這類資源稱為臨界資源（critical resource），使用臨界資源的那部分程序稱為程序的臨界區(qū)（critical section）。一次只允許有一個(gè)程序在臨界區(qū)中，這一點(diǎn)非常重要。由于不清楚詳細(xì)要求，我們不能僅僅依靠操作系統(tǒng)來理解和增強(qiáng)這個(gè)限制。例如在打印機(jī)的例子中，我們希望任何一個(gè)進(jìn)程在打印整個(gè)文件時(shí)都擁有打印機(jī)的控制權(quán)，否則在打印結(jié)果中就會(huì)穿插著來自競爭進(jìn)程的打印內(nèi)容。
實(shí)施互斥產(chǎn)生了兩個(gè)額外的控制問題。
死鎖（deadlock）。例如，考慮兩個(gè)進(jìn)程P1和P2，以及兩個(gè)資源R1和R2，假設(shè)每個(gè)進(jìn)程為執(zhí)行部分功能都需要訪問這兩個(gè)資源，那么就有可能出現(xiàn)下列情況：操作系統(tǒng)把R1分配給P2，把R2分配給P1，每個(gè)進(jìn)程都在等待另一個(gè)資源，且在獲得其他資源并完成功能前，誰都不會(huì)釋放自己已擁有的資源，此時(shí)這兩個(gè)進(jìn)程就會(huì)發(fā)生死鎖。
饑餓（starvation）。假設(shè)有三個(gè)進(jìn)程（P1、P2和P3），每個(gè)進(jìn)程都周期性地訪問資源R。考慮這種情況，即P1擁有資源，P2和P3都被延遲，等待這個(gè)資源。當(dāng)P1退出其臨界區(qū)時(shí)，P2和P3都允許訪問R，假設(shè)操作系統(tǒng)把訪問權(quán)授予P3，并在P3退出臨界區(qū)之前P1又要訪問該臨界區(qū)，若在P3結(jié)束后操作系統(tǒng)又把訪問權(quán)授予P1，且接下來把訪問權(quán)輪流授予P1和P3，那么即使沒有死鎖，P2也可能被無限地拒絕訪問資源。
由于操作系統(tǒng)負(fù)責(zé)分配資源，競爭的控制不可避免地涉及操作系統(tǒng)。此外，進(jìn)程自身需要能夠以某種方式表達(dá)互斥的需求，如在使用前對(duì)資源加鎖，但任何一種解決方案都涉及操作系統(tǒng)的某些支持，如提供鎖機(jī)制。
進(jìn)程間通過共享合作
通過共享進(jìn)行合作的情況，包括進(jìn)程間在互相并不確切知道對(duì)方的情況下進(jìn)行交互。例如，多個(gè)進(jìn)程可能訪問一個(gè)共享變量、共享文件或數(shù)據(jù)庫，進(jìn)程可能使用并修改共享變量而不涉及其他進(jìn)程，但卻知道其他進(jìn)程也可能訪問同一個(gè)數(shù)據(jù)。因此，這些進(jìn)程必須合作，以確保它們共享的數(shù)據(jù)得到正確管理。控制機(jī)制必須確保共享數(shù)據(jù)的完整性。
由于數(shù)據(jù)保存在資源（設(shè)備或存儲(chǔ)器）中，因此再次涉及有關(guān)互斥、死鎖和饑餓等控制問題。唯一的區(qū)別是可以按兩種不同的模式（讀和寫）訪問數(shù)據(jù)項(xiàng)，并且只有寫操作必須保證互斥。
但是，除這些問題之外還有一個(gè)新要求：數(shù)據(jù)一致性。舉個(gè)簡單的例子，考慮一個(gè)關(guān)于記賬的應(yīng)用程序，這個(gè)程序中可能會(huì)更新各個(gè)數(shù)據(jù)項(xiàng)。假設(shè)兩個(gè)數(shù)據(jù)項(xiàng)a和b保持著相等關(guān)系a=b，也就是說，為保持這一關(guān)系，任何一個(gè)程序如果修改了其中一個(gè)變量，也必須修改另一個(gè)變量。現(xiàn)在來看下面兩個(gè)進(jìn)程：
P1:a=a+1;b=b+1; P2:b=2*b;a=2*a;如果最初狀態(tài)是一致的，則單獨(dú)執(zhí)行每個(gè)進(jìn)程會(huì)使共享數(shù)據(jù)仍然保持一致狀態(tài)。現(xiàn)在考慮下面的并發(fā)執(zhí)行，兩個(gè)進(jìn)程在每個(gè)數(shù)據(jù)項(xiàng)（a和b）上都考慮到了互斥(也就是修改a或者b變量的時(shí)候不會(huì)被打斷)：
a=a+1;b=2*b;b=b+1;a=2*a;按照這一執(zhí)行順序，結(jié)果不再保持條件a=b。例如，開始時(shí)有a=b=1，在這個(gè)執(zhí)行序列結(jié)束時(shí)有a=4和b=3。為避免這個(gè)問題，可以把每個(gè)進(jìn)程中的整個(gè)代碼序列聲明為一個(gè)臨界區(qū)。
因此，在通過共享進(jìn)行合作的情況下，臨界區(qū)的概念非常重要。但是，在這種情況下，若使用臨界區(qū)來保護(hù)數(shù)據(jù)的完整性，則沒有確定的資源或變量可作為參數(shù)。此時(shí)，可以把參數(shù)視為一個(gè)在并發(fā)進(jìn)程間共享的標(biāo)識(shí)符，用于標(biāo)識(shí)必須互斥的臨界區(qū)（也就是需要互斥的代碼序列）。
作為簡單的理解，可以認(rèn)為進(jìn)程間的資源競爭是資源互斥，而共享合作則是代碼序列互斥。前者自然是操作系統(tǒng)的責(zé)任，而后者則需要代碼體現(xiàn)希望互斥的訴求，并且操作系統(tǒng)能明白這種訴求。
進(jìn)程間通過通信合作：
在前面兩種情況下，每個(gè)進(jìn)程都有自己獨(dú)立的環(huán)境，不包括其他進(jìn)程，進(jìn)程間的交互是間接的，并且都存在共享。在競爭情況下，它們?cè)诓恢榔渌M(jìn)程存在的情況下共享資源；在第二種情況下，它們共享變量，每個(gè)進(jìn)程并未明確地知道其他進(jìn)程的存在，它只知道需要維護(hù)數(shù)據(jù)的完整性。當(dāng)進(jìn)程通過通信進(jìn)行合作時(shí)，各個(gè)進(jìn)程都與其他進(jìn)程進(jìn)行連接。通信提供同步和協(xié)調(diào)各種活動(dòng)的方法。
典型情況下，通信可由各種類型的消息組成，發(fā)送消息和接收消息的原語由程序設(shè)計(jì)語言提供，或由操作系統(tǒng)的內(nèi)核提供。如最linux操作系統(tǒng)中的ctrl+c的停止進(jìn)程消息。
由于在傳遞消息的過程中進(jìn)程間未共享任何對(duì)象，因而這類合作不需要互斥，但仍然存在死鎖和饑餓問題。例如，有兩個(gè)進(jìn)程可能都被阻塞，每個(gè)都在等待來自對(duì)方的通信，這時(shí)發(fā)生死鎖。作為饑餓的例子，考慮三個(gè)進(jìn)程P1、P2和P3，它們都有如下特性：P1不斷地試圖與P2或P3通信，P2和P3都試圖與P1通信，如果P1和P2不斷地交換信息，而P3一直被阻塞，等待與P1通信，由于P1一直是活動(dòng)的，因此雖不存在死鎖，但P3處于饑餓狀態(tài)。
5.1.3 互斥的要求
要提供對(duì)互斥的支持，必須滿足以下要求：
滿足這些互斥條件的方法有多種。第一種方法是讓并發(fā)執(zhí)行的進(jìn)程承擔(dān)這一責(zé)任，這類進(jìn)程（不論是系統(tǒng)程序還是應(yīng)用程序）需要與另一個(gè)進(jìn)程合作，而不需要程序設(shè)計(jì)語言或操作系統(tǒng)提供任何支持來實(shí)施互斥。我們把這類方法稱為軟件方法。盡管這種方法已被證明會(huì)增加開銷并存在缺陷，但通過分析這類方法，可以更好地理解并發(fā)處理的復(fù)雜性。第二種方法涉及專用機(jī)器指令，這種方法的優(yōu)點(diǎn)是可以減少開銷，但卻很難成為一種通用的解決方案，詳見5.2節(jié)。第三種方法是在操作系統(tǒng)或程序設(shè)計(jì)語言中提供某種級(jí)別的支持，5.3節(jié)到5.5節(jié)將介紹這類方法中最重要的三種方法。
5.2 互斥：硬件的支持
5.2.1 中斷禁用
在單處理器機(jī)器中，并發(fā)進(jìn)程不能重疊，只能交替。此外，一個(gè)進(jìn)程在調(diào)用一個(gè)系統(tǒng)服務(wù)或被中斷前，將一直運(yùn)行。因此，為保證互斥，只需保證一個(gè)進(jìn)程不被中斷即可，這種能力可通過系統(tǒng)內(nèi)核為啟用和禁用中斷定義的原語來提供。進(jìn)程可通過如下方法實(shí)施互斥：
while（true）{/*禁用中斷*/;/*臨界區(qū)*/;/*啟用中斷*/;/*其余部分*/; }由于臨界區(qū)不能被中斷，故可以保證互斥。但是，這種方法的代價(jià)非常高。由于處理器被限制得只能交替執(zhí)行程序，因此執(zhí)行的效率會(huì)明顯降低。另一個(gè)問題是，這種方法不能用于多處理器體系結(jié)構(gòu)中。 當(dāng)一個(gè)計(jì)算機(jī)系統(tǒng)包括多個(gè)處理器時(shí)，通常就可能有一個(gè)以上的進(jìn)程同時(shí)執(zhí)行，在這種情況下，禁用中斷并不能保證互斥。
5.2.2 專用機(jī)器指令
在多處理器配置中，幾個(gè)處理器共享對(duì)內(nèi)存的訪問。在這種情況下，不存在主/從關(guān)系，處理器間的行為是無關(guān)的，表現(xiàn)出一種對(duì)等關(guān)系，處理器之間沒有支持互斥的中斷機(jī)制。
在硬件級(jí)別上，對(duì)存儲(chǔ)單元的訪問排斥對(duì)相同單元的其他訪問。因此，處理器的設(shè)計(jì)者人員提出了一些機(jī)器指令，用于保證兩個(gè)動(dòng)作的原子性，如在一個(gè)取指周期中對(duì)一個(gè)存儲(chǔ)器單元的讀和寫或讀和測試。在這個(gè)指令執(zhí)行的過程中，任何其他指令訪問內(nèi)存都將被阻止，而且這些動(dòng)作在一個(gè)指令周期中完成。
5.3 信號(hào)量
現(xiàn)在討論提供并發(fā)性的操作系統(tǒng)和程序設(shè)計(jì)語言的機(jī)制。表5.3總結(jié)了一般常用的并發(fā)機(jī)制。本節(jié)首先討論信號(hào)量，后續(xù)兩節(jié)分別討論管程和消息傳遞。表中其他機(jī)制這里不做說明。
在解決并發(fā)進(jìn)程問題的過程中，第一個(gè)重要的進(jìn)展是1965年Dijkstra的論文。Dijkstra參與了一個(gè)操作系統(tǒng)的設(shè)計(jì)，這個(gè)操作系統(tǒng)設(shè)計(jì)為一組合作的順序進(jìn)程，并為支持合作提供了有效且可靠的機(jī)制。只要處理器和操作系統(tǒng)使這些機(jī)制可用，它們就可以很容易地被用戶進(jìn)程使用。
基本原理如下：
兩個(gè)或多個(gè)進(jìn)程可以通過簡單的信號(hào)進(jìn)行合作，可以強(qiáng)迫一個(gè)進(jìn)程在某個(gè)位置停止，直到它接收到一個(gè)特定的信號(hào)。任何復(fù)雜的合作需求都可通過適當(dāng)?shù)男盘?hào)結(jié)構(gòu)得到滿足。為了發(fā)信號(hào)，需要使用一個(gè)稱為信號(hào)量的特殊變量。要通過信號(hào)量s傳送信號(hào)，進(jìn)程須執(zhí)行原語semsigna1（s）；要通過信號(hào)量s接收信號(hào)，進(jìn)程須執(zhí)行原語semwait（s）；若相應(yīng)的信號(hào)仍未發(fā)送，則阻塞進(jìn)程，直到發(fā)送完為I止。
為達(dá)到預(yù)期效果，可把信號(hào)量視為一個(gè)值為整數(shù)的變量，整數(shù)值上定義了三個(gè)操作：
除了這三個(gè)操作外，沒有任何其他方法可以檢查或操作信號(hào)量。
對(duì)這三個(gè)操作的解釋如下：開始時(shí)，信號(hào)量的值為零或正數(shù)。若值為正數(shù)，則它等于發(fā)出semwait
操作后可立即繼續(xù)執(zhí)行的進(jìn)程的數(shù)量。若值為零（要么由于初始化，要么由于有等于信號(hào)量初值的進(jìn)程已在等待），則發(fā)出semwait操作的下一個(gè)進(jìn)程會(huì)被阻塞，此時(shí)該信號(hào)量的值變?yōu)樨?fù)值。之后，每個(gè)后續(xù)的semwait操作都會(huì)使信號(hào)量的負(fù)值更大。該負(fù)值等于正在等待解除阻塞的進(jìn)程的數(shù)量。在信號(hào)量為負(fù)值的情形下，每個(gè)semsigna1操作都會(huì)將等待進(jìn)程中的一個(gè)進(jìn)程解除阻塞。
這里給出信號(hào)量定義的三個(gè)重要結(jié)論：
- 通常，在進(jìn)程對(duì)信號(hào)量減1之前，無法提前知道該信號(hào)量是否會(huì)被阻塞。
- 當(dāng)進(jìn)程對(duì)一個(gè)信號(hào)量加1之后，會(huì)喚醒另一個(gè)進(jìn)程，兩個(gè)進(jìn)程繼續(xù)并發(fā)運(yùn)行。而在一個(gè)單處理器系統(tǒng)中，同樣無法知道哪個(gè)進(jìn)程會(huì)立即繼續(xù)運(yùn)行。
- 向信號(hào)量發(fā)出信號(hào)后，不需要知道是否有另一個(gè)進(jìn)程正在等待，被解除阻塞的進(jìn)程數(shù)要么沒有，要么是為1。
圖5.3給出了關(guān)于信號(hào)量原語更規(guī)范的定義。semwait和semsignal原語被假設(shè)是原子操作。
圖5.4定義了稱為二元信號(hào)量（binary semaphore）的更嚴(yán)格的形式。二元信號(hào)量的值只能是0或1，可由下面三個(gè)操作定義：
關(guān)于二元信號(hào)量
操作，受阻的進(jìn)程會(huì)被喚醒；若沒有進(jìn)程受阻，則值設(shè)置為1。
理論上，二元信號(hào)量更易于實(shí)現(xiàn)，且可以證明它和普通信號(hào)具有同樣的表達(dá)能力（見習(xí)題5.16）。
為了區(qū)分這兩種信號(hào)，非二元信號(hào)量也常稱為計(jì)數(shù)信號(hào)量（counting semaphore）或一般信號(hào)量（general semaphore）。
與二元信號(hào)量相關(guān)的一個(gè)概念是互斥鎖（mutex）。互斥是一個(gè)編程標(biāo)志位，用來獲取和釋放一個(gè)對(duì)象。當(dāng)需要的數(shù)據(jù)不能被分享或處理，進(jìn)而導(dǎo)致在系統(tǒng)中的其他地方不能同時(shí)執(zhí)行時(shí)，互斥被設(shè)置為鎖定（一般為0），用于阻塞其他程序使用數(shù)據(jù)。當(dāng)數(shù)據(jù)不再需要或程序運(yùn)行結(jié)束時(shí)，互斥被設(shè)定為非鎖定。二元信號(hào)量和互斥量的關(guān)鍵區(qū)別在于，為互斥量加鎖（設(shè)定值為0）的進(jìn)程和為互斥量解鎖（設(shè)定值為1）的進(jìn)程必須是同一個(gè)進(jìn)程。相比之下，可能由某個(gè)進(jìn)程對(duì)二元信號(hào)量進(jìn)行加鎖操作，而由另一個(gè)進(jìn)程為其解鎖。
阻塞在信號(hào)量上的進(jìn)程調(diào)度問題：
不論是計(jì)數(shù)信號(hào)量還是二元信號(hào)量，都需要使用隊(duì)列來保存于信號(hào)量上等待的進(jìn)程。這就產(chǎn)生了一個(gè)問題：進(jìn)程按照什么順序從隊(duì)列中移出？最公平的策略是先進(jìn)先出（FIFO）：被阻塞時(shí)間最久的進(jìn)程最先從隊(duì)列釋放。采用這一策略定義的信號(hào)量稱為強(qiáng)信號(hào)量（strong semaphore），而沒有規(guī)定進(jìn)程從隊(duì)列中移出順序的信號(hào)量稱為弱信號(hào)量（weak semaphore）。圖5.5是一個(gè)關(guān)于強(qiáng)信號(hào)量操作的例子。其中進(jìn)程A、B和C依賴于進(jìn)程D的結(jié)果，在初始時(shí)刻（1），A正在運(yùn)行，B、C和D就緒，信號(hào)量為1，表示D的一個(gè)結(jié)果可用。當(dāng)A執(zhí)行一條semwait指令后，信號(hào)量減為0，A能繼續(xù)執(zhí)行，隨后它加入就緒隊(duì)列；然后在時(shí)刻（2），B正在運(yùn)行，最終執(zhí)行一條semwait指令，并被阻塞；在時(shí)刻（3），允許D運(yùn)行；在時(shí)刻（4），當(dāng)D完成一個(gè)新結(jié)果后，它執(zhí)行一條semsigna1指令，允許B移到就緒隊(duì)列中；在時(shí)刻（5），D加入就緒隊(duì)列，C開始運(yùn)行，當(dāng)它執(zhí)行semwait指令時(shí)被阻塞。類似地，在時(shí)刻（6），A和B運(yùn)行，且被阻塞在這個(gè)信號(hào)量上，允許D恢復(fù)執(zhí)行。當(dāng)D有一個(gè)結(jié)果后，執(zhí)行一條semsigna1指令，把C移到就緒隊(duì)列中，隨后的D循環(huán)將解除A和B的阻塞狀態(tài)。
對(duì)于下節(jié)將要講述的互斥算法（見圖5.6），強(qiáng)信號(hào)量保證不會(huì)饑餓，而弱信號(hào)量則無法保證。
這里將采用強(qiáng)信號(hào)量，因?yàn)樗鼈兏奖?#xff0c;且是操作系統(tǒng)提供的典型信號(hào)量形式。
5.3.1 使用信號(hào)量進(jìn)行互斥
圖5.6給出了一種使用信號(hào)量s解決互斥問題的方法。設(shè)有n個(gè)進(jìn)程，用數(shù)組P（i）表示，所有進(jìn)程都需要訪問共享資源。每個(gè)進(jìn)程進(jìn)入臨界區(qū)前執(zhí)行semwait（s），若s的值為負(fù)，則進(jìn)程被阻塞；若值為1，則s被減為0，進(jìn)程立即進(jìn)入臨界區(qū)；由于s不再為正，因而其他任何進(jìn)程都不能進(jìn)入臨界區(qū)。
信號(hào)量一般初始化為1，這樣第一個(gè)執(zhí)行semwait（s）的進(jìn)程可立即進(jìn)入臨界區(qū)，并把s的值置為0。接著任何試圖進(jìn)入臨界區(qū)的其他進(jìn)程，都將發(fā)現(xiàn)第一個(gè)進(jìn)程忙，因此被阻塞，把s的值置為-1。可以有任意數(shù)量的進(jìn)程試圖進(jìn)入，每個(gè)不成功的嘗試都會(huì)使s的值減1，當(dāng)最初進(jìn)入臨界區(qū)的進(jìn)程離開時(shí)，s增1，一個(gè)被阻塞的進(jìn)程（如果有的話）被移出等待隊(duì)列，置于就緒態(tài)。這樣，當(dāng)操作系統(tǒng)下一次調(diào)度時(shí)，它就可以進(jìn)入臨界區(qū)。如下圖所示：
圖5.7顯示了三個(gè)進(jìn)程使用圖5.6所示互斥協(xié)議后的一種執(zhí)行順序。在該例中，三個(gè)進(jìn)程（A、B、C）訪問一個(gè)受信號(hào)量lock保護(hù)的共享資源。進(jìn)程A執(zhí)行semwait（1ock）；由于信號(hào)量在本次semwait操作時(shí)值為1，因而A可以立即進(jìn)入臨界區(qū)，并把信號(hào)量的值置為0；當(dāng)A在臨界區(qū)中時(shí)，B和C都執(zhí)行一個(gè)semwait操作并被阻塞；當(dāng)A退出臨界區(qū)并執(zhí)行時(shí)，隊(duì)列中的第一個(gè)進(jìn)程B現(xiàn)在可以進(jìn)入臨界區(qū)。
圖5.6中的程序也可公平地處理一次允許多個(gè)進(jìn)程進(jìn)入臨界區(qū)的需求。這個(gè)需求可通過把信號(hào)量初始化成某個(gè)特定值來實(shí)現(xiàn)。因此，在任何時(shí)候，s.count的值都可解釋如下：
- s.count ≥ 0：s.count 是可執(zhí)行semwait（s）而不被阻塞的進(jìn)程數(shù)【期間無semsignal（s）
執(zhí)行】。這種情形允許信號(hào)量支持同步與互斥。 - s.count < 0：s.count的大小是阻塞在s.queue隊(duì)列中的進(jìn)程數(shù)。
5.3.2 生產(chǎn)者/消費(fèi)者問題
現(xiàn)在分析并發(fā)處理中最常見的一類問題：生產(chǎn)者（producer）/消費(fèi)者（consumer）問題。這個(gè)訪問通常描述如下：有一個(gè)或多個(gè)生產(chǎn)者生產(chǎn)某種類型的數(shù)據(jù)（記錄、字符），并放置在緩沖區(qū)中；
有一個(gè)消費(fèi)者從緩沖區(qū)中取數(shù)據(jù)，每次取一項(xiàng)；系統(tǒng)保證避免對(duì)緩沖區(qū)的重復(fù)操作，即在任何時(shí)候只有一個(gè)主體（生產(chǎn)者或消費(fèi)者）可訪問緩沖區(qū)。問題是要確保這種情況：當(dāng)緩存己滿時(shí)，生產(chǎn)者不會(huì)繼續(xù)向其中添加數(shù)據(jù)；當(dāng)緩存為空時(shí)，消費(fèi)者不會(huì)從中移走數(shù)據(jù)。我們將討論該問題的多種解決方案，以證明信號(hào)量的能力和缺陷。
首先假設(shè)緩沖區(qū)是無限的，且是一個(gè)線性的元素?cái)?shù)組。用抽象的術(shù)語，可以定義如下的生產(chǎn)者和消費(fèi)者函數(shù)：
producer： while（true）{/*生產(chǎn)v*/;b[in]=v;in++; }consumer： while（true）{while（in<=out）/*不做任何事*/;w=b[out];out++;/*消費(fèi)w*/; }圖5.8顯示了緩沖區(qū)b的結(jié)構(gòu)。生產(chǎn)者可以按自己的步調(diào)產(chǎn)生項(xiàng)目并保存在緩沖區(qū)中。每次，緩沖區(qū)中的索引（in）增1。消費(fèi)者以類似的方法繼續(xù)，但必須確保它不會(huì)從一個(gè)空緩沖區(qū)中讀取數(shù)據(jù)，因此，消費(fèi)者在開始進(jìn)行之前應(yīng)該確保生產(chǎn)者已經(jīng)生產(chǎn)（即：in>out）。
現(xiàn)在用二元信號(hào)量來實(shí)現(xiàn)這個(gè)系統(tǒng)，圖5.9是第一次嘗試。這里不處理索引in和out，而用整型變量n
（=in-out）簡單地記錄緩沖區(qū)中數(shù)據(jù)項(xiàng)的個(gè)數(shù)。信號(hào)量s用于實(shí)施互斥，信號(hào)量delay用于迫使消費(fèi)者在緩沖區(qū)為空時(shí)等待（semwait）。
這種方法看上去很直觀。生產(chǎn)者可以在任何時(shí)候自由地向緩沖區(qū)中增加數(shù)據(jù)項(xiàng)。它在添加數(shù)據(jù)前執(zhí)行semwaitB（s），之后執(zhí)行 semsignalB（s），以阻止消費(fèi)者或任何其他生產(chǎn)者在添加操作過程中訪問緩沖區(qū)。同時(shí)，當(dāng)生產(chǎn)者在臨界區(qū)中時(shí)，將n的值增1。若n=1，則在本次添加之前緩沖區(qū)為空，生產(chǎn)者執(zhí)行semsigna1B（delay）以通知消費(fèi)者這個(gè)事實(shí)。消費(fèi)者最初就使用 semwaitB（delay）等待生產(chǎn)出第一個(gè)項(xiàng)目，然后在自己的臨界區(qū)中取到這一項(xiàng)并將n減1。如果生產(chǎn)者總能保持在消費(fèi)者之前工作（一種普通情況），即n將總為正，則消費(fèi)者很少會(huì)被阻塞在信號(hào)量delay上。因此，生產(chǎn)者和消費(fèi)者都可以正常運(yùn)行。
但這個(gè)程序仍有缺陷。當(dāng)消費(fèi)者消耗盡緩沖區(qū)中的數(shù)據(jù)項(xiàng)時(shí)，需重置信號(hào)量delay，因此它被迫等待到生產(chǎn)者向緩沖區(qū)中放置更多的數(shù)據(jù)項(xiàng)，這正是語句if(n==0)semwaitB（delay）的目的。考慮表5.4中的情況，在第14行，消費(fèi)者執(zhí)行semwaitB操作失敗。但是消費(fèi)者確實(shí)用盡了緩沖區(qū)并把n置為0（第8行），然而生產(chǎn)者在消費(fèi)者測試到這一點(diǎn)（第14行）之前將n增1，結(jié)果導(dǎo)致semsigna1B
和前面的semwaitB不匹配。第20行的n值為-1，表示消費(fèi)者已經(jīng)消費(fèi)了緩沖區(qū)中不存在的一項(xiàng)。僅把消費(fèi)者臨界區(qū)中的條件語句移出也不能解決問題，因?yàn)檫@將導(dǎo)致死鎖（如在表5.4的第8行后）。
解決這個(gè)問題的方法是引入一個(gè)輔助變量，我們可以在消費(fèi)者的臨界區(qū)中設(shè)置這個(gè)變量供以后使用，如圖5.10所示。仔細(xì)跟蹤這個(gè)邏輯過程，可以確認(rèn)不會(huì)再發(fā)生死鎖。
使用一般信號(hào)量（也稱為計(jì)數(shù)信號(hào)量），可得到一種更清晰的解決方法，如圖5.11所示。變量n為信號(hào)量，其值等于緩沖區(qū)中的項(xiàng)數(shù)。假設(shè)在抄錄這個(gè)程序時(shí)發(fā)生了錯(cuò)誤，操作semsigna1B（s）和semsigna1B（n）被互換，這就要求生產(chǎn)者在臨界區(qū)中執(zhí)行semsigna1B（n）操作時(shí)不會(huì)被消費(fèi)者或另一個(gè)生產(chǎn)者打斷。這會(huì)影響程序嗎？不會(huì)，因?yàn)闊o論何種情況，消費(fèi)者在繼續(xù)進(jìn)行之前必須在兩個(gè)信號(hào)量上等待。
現(xiàn)在假設(shè)semwait（n）和semwait（s）操作偶然被顛倒，這時(shí)會(huì)產(chǎn)生嚴(yán)重甚至致命的錯(cuò)誤。如果緩沖區(qū)為空（n.count=0）時(shí)消費(fèi)者曾進(jìn)入過臨界區(qū)，那么任何一個(gè)生產(chǎn)者都不能繼續(xù)向緩沖區(qū)中添加數(shù)據(jù)項(xiàng)，系統(tǒng)發(fā)生死鎖。這是一個(gè)體現(xiàn)信號(hào)量的微妙之處和進(jìn)行正確設(shè)計(jì)的困難之處的較好示例。
最后，我們給生產(chǎn)者/消費(fèi)者問題增加一個(gè)新的實(shí)際約束，即緩沖區(qū)是有限的。緩沖區(qū)被視為一個(gè)循環(huán)存儲(chǔ)器，如圖5.12所示，指針值必須表達(dá)為按緩沖區(qū)的大小取模，并總是保持下面的關(guān)系：
生產(chǎn)者和消費(fèi)者函數(shù)可表示成如下形式（變量in和out初始化為0，n代表緩沖區(qū)的大小）：
圖5.13給出了使用一般信號(hào)量的解決方案，其中增加了信號(hào)量e來記錄空閑空間的數(shù)量。
5.3.3 信號(hào)量的實(shí)現(xiàn)
如前所述，semwait和semsignal操作必須作為原子原語實(shí)現(xiàn)。一種顯而易見的方法是用硬件或固件實(shí)現(xiàn)。如果沒有這些方案，那么還有很多其他方案。問題的本質(zhì)是互斥：任何時(shí)候只有一個(gè)進(jìn)程可用semwait或semsigna1操作控制一個(gè)信號(hào)量。因此，可以使用任何一種軟件方案，如Dekker
算法或Peterson算法，這必然伴隨著處理開銷。
另一種選擇是使用一種硬件支持實(shí)現(xiàn)互斥的方案。例如，圖5.14（a）顯示了使用compare&swap
指令的實(shí)現(xiàn)。其中，信號(hào)量是圖5.3中的結(jié)構(gòu)，但還包括一個(gè)新整型分量s.flag。誠然，這涉及某種形式的忙等待，但semsait和semsignal操作都相對(duì)較短，因此所涉及的忙等待時(shí)間量非常小。對(duì)于單處理器系統(tǒng)，在semwait或semsignal操作期間是可以禁用中斷的，如圖5.14（b）所示。這些操作的執(zhí)行時(shí)間相對(duì)很短，因此這種方法是合理的。
5.4 管程
信號(hào)量為實(shí)施互斥和進(jìn)程間的合作，提供了一種原始但功能強(qiáng)大且靈活的工具。但是，如圖5.9所示，使用信號(hào)量設(shè)計(jì)一個(gè)正確的程序是很困難的，難點(diǎn)在于semwait和semsignal操作可能分布在整個(gè)程序中，而很難看出信號(hào)量上的這些操作所產(chǎn)生的整體效果。管程是一種程序設(shè)計(jì)語言結(jié)構(gòu)，它提供的功能與信號(hào)量相同，但更易于控制。管程結(jié)構(gòu)在很多程序設(shè)計(jì)語言中都得以實(shí)現(xiàn)，包括并發(fā) Pascal、Pascal-Plus、Modula-2、Modula-3和Java。它還被作為一個(gè)程序庫實(shí)現(xiàn)。這就允許我們用管程鎖定任何對(duì)象，對(duì)類似于鏈表之類的對(duì)象，可以用一個(gè)鎖鎖住整個(gè)鏈表，也可每個(gè)表用一個(gè)鎖，還可為表中的每個(gè)元素用一個(gè)鎖。
首先介紹Hoare的方案，然后對(duì)它進(jìn)行改進(jìn)。
5.4.1 使用信號(hào)的管程
管程是由一個(gè)或多個(gè)過程、一個(gè)初始化序列和局部數(shù)據(jù)組成的軟件模塊，其主要特點(diǎn)如下：
前兩個(gè)特點(diǎn)讓人聯(lián)想到面向?qū)ο筌浖袑?duì)象的特點(diǎn)。的確，面向?qū)ο蟛僮飨到y(tǒng)或程序設(shè)計(jì)語言很容易把管程作為一種具有特殊特征的對(duì)象來實(shí)現(xiàn)。
通過給進(jìn)程強(qiáng)加規(guī)定，管程可以提供一種互斥機(jī)制：管程中的數(shù)據(jù)變量每次只能被一個(gè)進(jìn)程訪問。因此，可以把一個(gè)共享數(shù)據(jù)結(jié)構(gòu)放在管程中，從而對(duì)它進(jìn)行保護(hù)。如果管程中的數(shù)據(jù)代表某些資源，那么管程為訪問這些資源提供了互斥機(jī)制。
要進(jìn)行并發(fā)處理，管程必須包含同步工具。例如，假設(shè)一個(gè)進(jìn)程調(diào)用了管程，且當(dāng)它在管程中時(shí)必須被阻塞，直到滿足某些條件。這就需要一種機(jī)制，使得該進(jìn)程不僅被阻塞，而且能釋放這個(gè)管程，以便某些其他的進(jìn)程可以進(jìn)入。以后，當(dāng)條件滿足且管程再次可用時(shí)，需要恢復(fù)該進(jìn)程并允許它在阻塞點(diǎn)重新進(jìn)入管程。
管程通過使用**條件變量（condition variable）**來支持同步，這些條件變量包含在管程中，并且只有在管程中才能被訪問。有兩個(gè)函數(shù)可以操作條件變量：
- cwait（c）：調(diào)用進(jìn)程的執(zhí)行在條件c上阻塞，管程現(xiàn)在可被另一個(gè)進(jìn)程使用。
- csignal（c）：恢復(fù)執(zhí)行在cwait之后因某些條件而被阻塞的進(jìn)程。若有多個(gè)這樣的進(jìn)程，選擇其中一個(gè)；若沒有這樣的進(jìn)程，什么也不做。
圖5.15給出了一個(gè)管程的結(jié)構(gòu)。盡管一個(gè)進(jìn)程可以通過調(diào)用管程的任何一個(gè)過程進(jìn)入管程，但我們?nèi)钥梢暪艹逃幸粋€(gè)入口點(diǎn)，保證一次只有一個(gè)進(jìn)程可以進(jìn)入。其他試圖進(jìn)入管程的進(jìn)程被阻塞并加入等待管程可用的進(jìn)程隊(duì)列中。當(dāng)一個(gè)進(jìn)程在管程中時(shí)，它可能會(huì)通過發(fā)送cwait（x）把自己暫時(shí)阻塞在條件x上，隨后它被放入等待條件改變以重新進(jìn)入管程的進(jìn)程隊(duì)列中，在cwait（x）調(diào)用的下一條指令開始恢復(fù)執(zhí)行。
若在管程中執(zhí)行的一個(gè)進(jìn)程發(fā)現(xiàn)條件變量x發(fā)生了變化，則它發(fā)送csignal（x），通知相應(yīng)的條件隊(duì)列條件已改變。
5.5 消息傳遞
進(jìn)程交互時(shí)，必須滿足兩個(gè)基本要求：同步和通信。為實(shí)施互斥，進(jìn)程間需要同步；為實(shí)現(xiàn)合作，進(jìn)程間需要交換信息。提供這些功能的一種方法是消息傳遞。消息傳遞還有一個(gè)優(yōu)點(diǎn)，即它可在分布式系統(tǒng)、共享內(nèi)存的多處理器系統(tǒng)和單處理器系統(tǒng)中實(shí)現(xiàn)。
消息傳遞系統(tǒng)有多種形式(在很多軟件編程的書中都會(huì)提到的進(jìn)程間的通信)，本節(jié)簡述這類系統(tǒng)的典型特征。消息傳遞的實(shí)際功能以一對(duì)原語的形式提供：
send(destination,message) receive(source,message)這是進(jìn)程間進(jìn)行消息傳遞所需的最小操作集。一個(gè)進(jìn)程以消息（message）的形式給另一個(gè)指定的目標(biāo)（destination）進(jìn)程發(fā)送信息；進(jìn)程通過執(zhí)行 receive原語接收信息，receive原語中指明發(fā)送消息的源進(jìn)程（source）和消息（message）。
表5.5中列出了與消息傳遞系統(tǒng)相關(guān)的一些設(shè)計(jì)問題，本節(jié)的其他部分將依次分析這些問題。
5.5.1 同步
兩個(gè)進(jìn)程間的消息通信隱含著某種同步的信息：只有當(dāng)一個(gè)進(jìn)程發(fā)送消息后，接收者才能接收消息。
此外，一個(gè)進(jìn)程發(fā)出send或receive原語后，我們需要確定會(huì)發(fā)生什么。
考慮send原語。首先，一個(gè)進(jìn)程執(zhí)行send原語時(shí)有兩種可能：要么發(fā)送進(jìn)程被阻塞直到這個(gè)消息被目標(biāo)進(jìn)程接收到，要么不阻塞。類似地，一個(gè)進(jìn)程發(fā)出receive原語后，也有兩種可能：
因此，發(fā)送者和接收者都可阻塞或不阻塞。通常有三種組合，但任何一個(gè)特定系統(tǒng)通常只實(shí)現(xiàn)一種或兩種組合：
- 阻塞send，阻塞receive：發(fā)送者和接收者都被阻塞，直到完成信息的投遞。這種情況有時(shí)也稱為會(huì)合（rendezvous），它考慮到了進(jìn)程間的緊密同步。
- 無阻塞send，阻塞receive：盡管發(fā)送者可以繼續(xù)，但接收者會(huì)被阻塞直到請(qǐng)求的消息到達(dá)。這可能是最有用的一種組合，它允許一個(gè)進(jìn)程給各個(gè)目標(biāo)進(jìn)程盡快地發(fā)送一條或多條消息。在繼續(xù)工作前必須接收到消息的進(jìn)程將被阻塞，直到該消息到達(dá)。例如，一個(gè)服務(wù)器進(jìn)程給其他進(jìn)程提供服務(wù)或資源。
- 無阻塞send，無阻塞 receive：不要求任何一方等待。
對(duì)大多數(shù)并發(fā)程序設(shè)計(jì)任務(wù)來說，無阻塞send是最自然的。例如，無阻塞send用于請(qǐng)求一個(gè)輸出操作（如打印），它允許請(qǐng)求進(jìn)程以消息的形式發(fā)出請(qǐng)求，然后繼續(xù)。無阻塞send有一個(gè)潛在的危險(xiǎn)：錯(cuò)誤會(huì)導(dǎo)致進(jìn)程重復(fù)產(chǎn)生消息。由于對(duì)進(jìn)程沒有阻塞的要求，這些消息可能會(huì)消耗系統(tǒng)資源，包括處理器時(shí)間和緩沖區(qū)空間，進(jìn)而損害其他進(jìn)程和操作系統(tǒng)。同時(shí)，無阻塞send增加了程序員的負(fù)擔(dān)，由于必須確定消息是否收到，因而進(jìn)程必須使用應(yīng)答消息，以證實(shí)收到了消息。
對(duì)大多數(shù)并發(fā)程序設(shè)計(jì)任務(wù)來說，阻塞receive原語是最自然的。通常，請(qǐng)求一個(gè)消息的進(jìn)程都需要這個(gè)期望的信息才能繼續(xù)執(zhí)行下去，但若消息丟失（在分布式系統(tǒng)中很可能發(fā)生這種情況），或者一個(gè)進(jìn)程在發(fā)送預(yù)期的消息之前失敗，則接收進(jìn)程會(huì)無限期地阻塞。這個(gè)問題可以使用無阻塞receive
來解決。但該方法的危險(xiǎn)是，若消息在一個(gè)進(jìn)程已執(zhí)行與之匹配的receive之后發(fā)送，則該消息將被丟失。其他可能的方法是允許一個(gè)進(jìn)程在發(fā)出receive之前檢測是否有消息正在等待，或允許進(jìn)程在receive原語中確定多個(gè)源進(jìn)程。若一個(gè)進(jìn)程正在等待從多個(gè)源進(jìn)程發(fā)來的消息，且只要有一個(gè)消息到達(dá)就可以繼續(xù)下去時(shí)，則后一種方法非常有用。
5.5.2 尋址
顯然，在send原語中確定哪個(gè)進(jìn)程接收消息很有必要。類似地，大多數(shù)實(shí)現(xiàn)允許接收進(jìn)程指明消息的來源。
在send和receive原語中確定目標(biāo)或源進(jìn)程的方案分為兩類：直接尋址和間接尋址。對(duì)于直接尋址（direct addressing），send原語包含目標(biāo)進(jìn)程的標(biāo)識(shí)號(hào)，而receive原語有兩種處理方式。一種是要求進(jìn)程顯式地指定源進(jìn)程，因此該進(jìn)程必須事先知道希望得到來自哪個(gè)進(jìn)程的消息，這種方式對(duì)于處理并發(fā)進(jìn)程間的合作非常有效。另一種是不可能指定所期望的源進(jìn)程，例如打印機(jī)服務(wù)器進(jìn)程將接受來自各個(gè)進(jìn)程的打印請(qǐng)求，對(duì)這類應(yīng)用使用隱式尋址更為有效。此時(shí)，receive原語的source參數(shù)保存接收操作執(zhí)行后的返回值。
另一種常用的方法是間接尋址（indirect addressing）。此時(shí)，消息不直接從發(fā)送者發(fā)送到接收者，而是發(fā)送到一個(gè)共享數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)由臨時(shí)保存消息的隊(duì)列組成，這些隊(duì)列通常稱為信箱（mailbox）。因此，兩個(gè)通信進(jìn)程中，一個(gè)進(jìn)程給合適的信箱發(fā)送消息，另一個(gè)進(jìn)程從信箱中獲取這些消息。
間接尋址通過解除發(fā)送者和接收者之間的耦合關(guān)系，可更靈活地使用消息。發(fā)送者和接收者之間的關(guān)系可以是一對(duì)一、多對(duì)一、一對(duì)多或多對(duì)多（見圖5.18）。一對(duì)一（one-to-one）關(guān)系允許在兩個(gè)進(jìn)程間建立專用的通信鏈接，隔離它們間的交互，避免其他進(jìn)程的錯(cuò)誤干擾；多對(duì)一（many-to-one）關(guān)系對(duì)客戶服務(wù)器間的交互非常有用，一個(gè)進(jìn)程給許多其他進(jìn)程提供服務(wù)，這時(shí)信箱常稱為一個(gè)端口（port）；一對(duì)多（one-to-many）關(guān)系適用于一個(gè)發(fā)送者和多個(gè)接收者，它對(duì)于在一組進(jìn)程間廣播一條消息或某些信息的應(yīng)用程序非常有用。多對(duì)多（many-to-many）關(guān)系可讓多個(gè)服務(wù)進(jìn)程對(duì)多個(gè)客戶進(jìn)程提供服務(wù)。
進(jìn)程和信箱的關(guān)聯(lián)既可以是靜態(tài)的，也可以是動(dòng)態(tài)的。端口常常靜態(tài)地關(guān)聯(lián)到一個(gè)特定的進(jìn)程上，也就是說，端口被永久地創(chuàng)建并指定到該進(jìn)程。一對(duì)一關(guān)系就是典型的靜態(tài)和永久性關(guān)系。當(dāng)有很多發(fā)送者時(shí)，發(fā)送者和信箱間的關(guān)聯(lián)可以是動(dòng)態(tài)的，基于這一目的可使用諸如 connect和disconnect之類的原語。
一個(gè)相關(guān)的問題是信箱的所有權(quán)問題。對(duì)于端口來說，信箱的所有都通常是接收進(jìn)程，并由接收進(jìn)程創(chuàng)建。因此，撤銷一個(gè)進(jìn)程時(shí)，其端口也會(huì)隨之銷毀。對(duì)于通用的信箱，操作系統(tǒng)可提供一個(gè)創(chuàng)建信箱的服務(wù)，這樣信箱就可視為由創(chuàng)建它的進(jìn)程所有，這時(shí)它們也同該進(jìn)程一起終止；或視為由操作系統(tǒng)所有，這時(shí)銷毀信箱需要一個(gè)顯式命令。
5.5.3 消息格式
消息的格式取決于消息機(jī)制的目標(biāo)，以及該機(jī)制是運(yùn)行在一臺(tái)計(jì)算機(jī)上還是運(yùn)行在分布式系統(tǒng)中。對(duì)某些操作系統(tǒng)而言，設(shè)計(jì)者會(huì)優(yōu)先選用定長的短消息來減小處理和存儲(chǔ)的開銷。需要傳遞大量數(shù)據(jù)時(shí)，可將數(shù)據(jù)放到一個(gè)文件中，然后讓消息引用該文件。更為靈活的一種方法是使用變長消息。
圖5.19給出了操作系統(tǒng)支持的變長消息的典型格式。該消息分為兩部分：包含相關(guān)信息的消息頭和包含實(shí)際內(nèi)容的消息體。消息頭包含消息源和目標(biāo)的標(biāo)識(shí)符、長度域及判定各種消息類型的類型域，還可能含有一些額外的控制信息，例如創(chuàng)建消息鏈表的指針域、記錄源和目標(biāo)之間所傳
遞消息的數(shù)量、順序和序號(hào)，以及一個(gè)優(yōu)先級(jí)域。
5.5.4 排隊(duì)原則
最簡單的排隊(duì)原則是先進(jìn)先出，但當(dāng)某些消息比其他消息更緊急時(shí)，僅有這一原則是不夠的。
一個(gè)替代原則是允許指定消息的優(yōu)先級(jí)，即根據(jù)消息的類型來指定或由發(fā)送者指定；另一個(gè)替代原則是允許接收者檢查消息隊(duì)列并選擇下一次接收哪個(gè)消息。
5.5.5 使用消息來實(shí)現(xiàn)互斥
圖5.20給出了用于實(shí)施互斥的消息傳遞方式。假設(shè)使用阻塞 receive原語和無阻塞 send原語，且一組并發(fā)進(jìn)程共享一個(gè)信箱box，該信箱可供所有進(jìn)程在發(fā)送和接收消息時(shí)使用，并初始化為一個(gè)無內(nèi)容的消息。希望進(jìn)入臨界區(qū)的進(jìn)程首先試圖接收一條消息，若信箱為空，則阻塞該進(jìn)程；一旦進(jìn)程獲得消息，它就執(zhí)行其臨界區(qū)，然后把該消息放回信箱。因此，消息函數(shù)可視為在進(jìn)程之間傳遞的一個(gè)令牌。
上面的解決方案假設(shè)有多個(gè)進(jìn)程并發(fā)地執(zhí)行接收操作，因此
- 若有一條消息，則它僅傳遞給一個(gè)進(jìn)程，而其他進(jìn)程被阻塞。
- 若消息隊(duì)列為空，則所有進(jìn)程被阻塞；一條消息可用時(shí)，僅激活一個(gè)阻塞進(jìn)程活，并得到這條消息。
這些假設(shè)實(shí)際上對(duì)所有消息傳遞機(jī)制都為真。
作為使用消息傳遞的另一個(gè)例子，圖5.21給出了解決有界緩沖區(qū)生產(chǎn)者/消費(fèi)者問題的一種方法。
使用消息傳遞最基本的互斥能力，該問題可通過類似于圖5.13的算法結(jié)構(gòu)解決。圖5.21利用了消息傳遞的能力，除了傳遞信號(hào)之外，它還傳遞數(shù)據(jù)。它使用了兩個(gè)信箱。當(dāng)生產(chǎn)者產(chǎn)生數(shù)據(jù)后，數(shù)據(jù)將作為消息發(fā)送到信箱mayconsume，只要該信箱中有一條消息，消費(fèi)者就可開始消費(fèi)。從此之后mayconsume用做緩沖區(qū)，緩沖區(qū)中的數(shù)據(jù)被組織成消息隊(duì)列，緩沖區(qū)的大小由全局變量 capacity確定。信箱mayproduce最初填滿空消息，空消息的數(shù)量等于信箱的容量，每次生產(chǎn)使得mayproduce中的消息數(shù)減少，每次消費(fèi)使得mayproduce中的消息數(shù)增多。
這種方法非常靈活，可以有多個(gè)生產(chǎn)者和消費(fèi)者，只要它們都訪問這兩個(gè)信箱即可。系統(tǒng)甚至可以是分布式系統(tǒng)，所有生產(chǎn)者進(jìn)程和mayproduce信箱在一個(gè)站點(diǎn)上，所有消費(fèi)者進(jìn)程和mayconsume信箱在另一個(gè)站點(diǎn)上。
5.6 讀者/寫者問題
在設(shè)計(jì)同步和并發(fā)機(jī)制時(shí)，若能與一個(gè)著名的問題關(guān)聯(lián)，檢測該問題的解決方案對(duì)原問題是否有效，則這種方法是非常有用的。很多文獻(xiàn)中都有一些頻繁出現(xiàn)的重要問題，它們不僅是普遍性的設(shè)計(jì)問題，而且具有教育價(jià)值。前面介紹的生產(chǎn)者/消費(fèi)者問題就是這樣一個(gè)問題，本節(jié)介紹另一個(gè)經(jīng)典問題：讀者/寫者問題。
讀者/寫者問題定義如下：存在一個(gè)多個(gè)進(jìn)程共享的數(shù)據(jù)區(qū)，該數(shù)據(jù)區(qū)可以是一個(gè)文件或一塊內(nèi)存空間，甚至可以是一組寄存器；有些進(jìn)程（reader）只讀取這個(gè)數(shù)據(jù)區(qū)中的數(shù)據(jù)，有些進(jìn)程（writer）
只往數(shù)據(jù)區(qū)中寫數(shù)據(jù)。此外，還必須滿足以下條件：
也就是說，讀進(jìn)程不需要排斥其他讀進(jìn)程，而寫進(jìn)程需要排斥其他所有進(jìn)程，包括讀進(jìn)程和寫進(jìn)程。
在繼續(xù)介紹之前，首先讓我們區(qū)分這個(gè)問題和另外兩個(gè)問題：一般互斥問題和生產(chǎn)者/消費(fèi)者問題。在讀者/寫者問題中，讀進(jìn)程不會(huì)向數(shù)據(jù)區(qū)中寫數(shù)據(jù)，寫進(jìn)程不會(huì)從數(shù)據(jù)區(qū)中讀數(shù)據(jù)。更一般的情況是，允許任何進(jìn)程讀寫數(shù)據(jù)區(qū)，此時(shí)可以把該進(jìn)程中訪問數(shù)據(jù)區(qū)的部分聲明為一個(gè)臨界區(qū)，并強(qiáng)行實(shí)施一般互斥問題的解決方法。之所以關(guān)注這種更受限制的情況，是因?yàn)閷?duì)這種情況可以有更有效的解決方案，一般問題的低效方法由于速度過慢而很難被人們接受。 例如，假設(shè)共享區(qū)是一個(gè)圖書館目錄，普通用戶可通過讀目錄來查找一本書，一位或多位圖書管理員可以修改目錄。在一般解決方案中，每次對(duì)目錄的訪問都可視為訪問一個(gè)臨界區(qū)，并且用戶每次只能讀一個(gè)目錄，這將會(huì)帶來無法忍受的延遲。同時(shí)，避免寫進(jìn)程間互相干擾非常重要，此外還要求在寫的過程中禁止讀操作，以避免訪問到不正確的信息。
生產(chǎn)者/消費(fèi)者問題是否可視為只有一個(gè)寫進(jìn)程（生產(chǎn)者）和一個(gè)讀進(jìn)程（消費(fèi)者）的特殊讀者/寫者問題呢？答案是不能。生產(chǎn)者不僅僅是一個(gè)寫進(jìn)程，它必須讀取隊(duì)列指針，以確定向哪里寫下一項(xiàng)，還必須確定緩沖區(qū)是否已滿。類似地，消費(fèi)者也不僅僅是一個(gè)讀進(jìn)程，它必須調(diào)整隊(duì)列指針以顯示它已從緩沖區(qū)中移走了一個(gè)單元。
現(xiàn)在開始分析讀者/寫者問題的兩種解決方案。
5.6.1 讀者優(yōu)先
圖5.22是使用信號(hào)量的一種解決方案，它給出了一個(gè)讀進(jìn)程和一個(gè)寫進(jìn)程的實(shí)例，該方案無須修改就可用于多個(gè)讀進(jìn)程和寫進(jìn)程的情況。寫進(jìn)程非常簡單，信號(hào)量wsem用于實(shí)施互斥，只要一個(gè)寫進(jìn)程正在訪問共享數(shù)據(jù)區(qū)，其他寫進(jìn)程和讀進(jìn)程就都不能訪問它。讀進(jìn)程也使用wsem實(shí)施互斥，但為了允許多個(gè)讀進(jìn)程，沒有讀進(jìn)程正在讀時(shí)，第一個(gè)試圖讀的讀進(jìn)程需要在wsem上等待。當(dāng)至少已有一個(gè)讀進(jìn)程在讀時(shí)，隨后的讀進(jìn)程無須等待，可以直接進(jìn)入。全局變量 readcount用于記錄讀進(jìn)程的數(shù)量，信號(hào)量x用于確保 readcount被正確地更新。
5.6.2 寫者優(yōu)先
在前面的解決方案中，讀進(jìn)程具有優(yōu)先權(quán)。一個(gè)讀進(jìn)程開始訪問數(shù)據(jù)區(qū)時(shí)，只要至少有一個(gè)讀進(jìn)程正在讀，就為讀進(jìn)程保留對(duì)這個(gè)數(shù)據(jù)區(qū)的控制權(quán)，因此寫進(jìn)程有可能處于饑餓狀態(tài)。
圖5.23給出了另一種解決方案，它保證在一個(gè)寫進(jìn)程聲明想寫時(shí)，不允許新的讀進(jìn)程訪問該數(shù)據(jù)區(qū)。對(duì)于寫進(jìn)程，在已有定義的基礎(chǔ)上還必須增加下列信號(hào)量和變量：
- 信號(hào)量rsem：至少有一個(gè)寫進(jìn)程準(zhǔn)備訪問數(shù)據(jù)區(qū)時(shí)，用于禁止所有的讀進(jìn)程。
- 變量writecount：控制rsem的設(shè)置。
- 信號(hào)量y：控制writecount的更新。
對(duì)于讀進(jìn)程，還需要一個(gè)額外的信號(hào)量。在rsem上不允許建造長隊(duì)列，否則寫進(jìn)程將無法跳過這個(gè)隊(duì)列，因此只允許一個(gè)讀進(jìn)程在rsem上排隊(duì)，而所有其他讀進(jìn)程在等待rsem前，在信號(hào)量z上排隊(duì)。表5.6概括了這些可能性。
圖5.24給出了另一種解決方案，這種方案賦予寫進(jìn)程優(yōu)先權(quán)，并通過消息傳遞來實(shí)現(xiàn)。在這種情況下，有一個(gè)訪問共享數(shù)據(jù)區(qū)的控制進(jìn)程，其他要訪問這個(gè)數(shù)據(jù)區(qū)的進(jìn)程給控制進(jìn)程發(fā)送請(qǐng)求消息，若請(qǐng)求得到同意，則會(huì)收到應(yīng)答消息“OK”，并通過“finished”消息表示訪問完成。控制進(jìn)程備有三個(gè)信箱，每個(gè)信箱存放一種它可能接收到的消息。
要賦予寫進(jìn)程優(yōu)先權(quán)，控制進(jìn)程就要先服務(wù)于寫請(qǐng)求消息，后服務(wù)于讀請(qǐng)求消息。此外，必須實(shí)施互斥。要實(shí)現(xiàn)互斥，需要使用變量count，它被初始化為一個(gè)大于可能的讀進(jìn)程數(shù)的最大值。
在該例中，我們?nèi)∑渲禐?00。控制器的動(dòng)作可總結(jié)如下： - 若count>0，則無讀進(jìn)程正在等待，可能有也可能沒有活動(dòng)的讀進(jìn)程。要清除活動(dòng)讀進(jìn)程，首先要服務(wù)于所有“finished”消息，然后服務(wù)于寫請(qǐng)求，再服務(wù)于讀請(qǐng)求。
- 若count=0，則唯一未解決的請(qǐng)求是寫請(qǐng)求。允許該寫進(jìn)程繼續(xù)執(zhí)行并等待“finished”消息。
- 若count<0，則一個(gè)寫進(jìn)程已發(fā)出一條請(qǐng)求，且正在等待消除所有活動(dòng)的讀進(jìn)程。因此，只有“finished”消息將得到服務(wù)。
5.7 小結(jié)
現(xiàn)代操作系統(tǒng)的核心是多道程序設(shè)計(jì)、多處理器和分布式處理器，這些方案和操作系統(tǒng)設(shè)計(jì)技術(shù)的基礎(chǔ)都是并發(fā)。當(dāng)多個(gè)進(jìn)程并發(fā)執(zhí)行時(shí)，不論是在多處理器系統(tǒng)的情況下，還是在單處理器多道程序系統(tǒng)中，都會(huì)出現(xiàn)沖突和合作的問題。
并發(fā)進(jìn)程可按多種方式進(jìn)行交互。互相之間不知道對(duì)方的進(jìn)程可能需要競爭使用資源，如處理器時(shí)間或?qū)/O設(shè)備的訪問。進(jìn)程間由于共享訪問一個(gè)公共對(duì)象，如一塊內(nèi)存空間或一個(gè)文件，可能間接知道對(duì)方，這類交互中產(chǎn)生的重要問題是互斥和死鎖。
互斥指的是，對(duì)一組并發(fā)進(jìn)程，一次只有一個(gè)進(jìn)程能夠訪問給定的資源或執(zhí)行給定的功能。互斥技術(shù)可用于解決諸如資源爭用之類的沖突，也可以用于進(jìn)程間的同步，使得它們能夠合作。后一種情況的例子是生產(chǎn)者/消費(fèi)者模型（這里使用了模型這個(gè)名詞，意義為問題模型，在日后編程的時(shí)候，你可能會(huì)經(jīng)常遇到這些類似的問題），在該模型中，一個(gè)進(jìn)程向緩沖區(qū)中放數(shù)據(jù)，另一個(gè)或更多的進(jìn)程從緩沖區(qū)中取數(shù)據(jù)。
支持互斥的第一種方法是使用專用機(jī)器指令，這種方法能降低開銷，但由于使用了忙等待，效率較低。
支持互斥的另一種方法是在操作系統(tǒng)中提供相應(yīng)的功能，其中最常見的兩種技術(shù)是信號(hào)量和消息機(jī)制。信號(hào)量用于在進(jìn)程間發(fā)信號(hào)，能很容易地實(shí)施一個(gè)互斥協(xié)議。消息對(duì)實(shí)施互斥很有用，還為進(jìn)程間的通信提供了一種有效的方法。
《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀總結(jié)
以上是生活随笔為你收集整理的操作系统-并发性：互斥与同步的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 操作系统-线程
- 下一篇： 操作系统-并发：死锁和饥饿