分布式和并行計算

1 引言

這一章中，我們跳轉(zhuǎn)到協(xié)調(diào)多個計算機(jī)和處理器的問題。首先，我們會觀察分布式系統(tǒng)。它們是互相連接的獨(dú)立計算機(jī)，需要互相溝通來完成任務(wù)。它們可能需要協(xié)作來提供服務(wù)，共享數(shù)據(jù)，或者甚至是儲存太大而不能在一臺機(jī)器上裝下的數(shù)據(jù)。我們會看到，計算機(jī)可以在分布式系統(tǒng)中起到不同作用，并且了解各種信息，計算機(jī)需要交換它們來共同工作。

接下來，我們會考慮并行計算。并行計算是這樣，當(dāng)一個小程序由多個處理器使用共享內(nèi)存執(zhí)行時，所有處理器都并行工作來使任務(wù)完成得更快。并發(fā)(或并行)引入了新的挑戰(zhàn)，并且我們會開發(fā)新的機(jī)制來管理并發(fā)程序的復(fù)雜性。

2 分布式系統(tǒng)

分布式系統(tǒng)是自主的計算機(jī)網(wǎng)絡(luò)，計算機(jī)互相通信來完成一個目標(biāo)。分布式系統(tǒng)中的計算機(jī)都是獨(dú)立的，并且沒有物理上共享的內(nèi)存或處理器。它們使用消息來和其它計算機(jī)通信，消息是網(wǎng)絡(luò)上從一臺計算機(jī)到另一臺計算機(jī)傳輸?shù)囊欢涡畔?。消息可以用于溝通許多事情：計算機(jī)可以讓其它計算機(jī)來執(zhí)行一個帶有特定參數(shù)的過程，它們可以發(fā)送和接受數(shù)據(jù)包，或者發(fā)送信號讓其它計算機(jī)執(zhí)行特定行為。

分布式系統(tǒng)中的計算機(jī)具有不同的作用。計算機(jī)的作用取決于系統(tǒng)的目標(biāo)，以及計算機(jī)自身的硬件和軟件屬性。分布式系統(tǒng)中，有兩種主要方式來組織計算機(jī)，一種叫客戶端-服務(wù)端架構(gòu)(C/S 架構(gòu))，另一種叫做對等網(wǎng)絡(luò)架構(gòu)(P2P 架構(gòu))。

2.1 C/S 系統(tǒng)

C/S 架構(gòu)是一種從中心來源分發(fā)服務(wù)的方式。只有單個服務(wù)端提供服務(wù)，多臺客戶端和服務(wù)器通信來消耗它的產(chǎn)出。在這個架構(gòu)中，客戶端和服務(wù)端都有不同的任務(wù)。服務(wù)端的任務(wù)就是響應(yīng)來自客戶端的服務(wù)請求，而客戶端的任務(wù)就是使用響應(yīng)中提供的數(shù)據(jù)來執(zhí)行一些任務(wù)。

C/S 通信模型可以追溯到二十世紀(jì)七十年代 Unix 的引入，但這一模型由于現(xiàn)代萬維網(wǎng)(WWW)中的使用而變得具有影響力。一個C/S 交互的例子就是在線閱讀紐約時報。當(dāng) www.nytimes.com 上的服務(wù)器與瀏覽器客戶端(比如 Firefox)通信時，它的任務(wù)就是發(fā)送回來紐約時報主頁的 HTML。這可能涉及到基于發(fā)送給服務(wù)器的用戶賬戶信息，計算個性化的內(nèi)容。這意味著需要展示圖片，安排視覺上的內(nèi)容，展示不同的顏色、字體和圖形，以及允許用戶和渲染后的頁面交互。

客戶端和服務(wù)端的概念是強(qiáng)大的函數(shù)式抽象。客戶端僅僅是一個提供服務(wù)的單位，可能同時對應(yīng)多個客戶端?？蛻舳耸窍姆?wù)的單位?？蛻舳瞬⒉恍枰婪?wù)如何提供的細(xì)節(jié)，或者所獲取的數(shù)據(jù)如何儲存和計算，服務(wù)端也不需要知道數(shù)據(jù)如何使用。

在網(wǎng)絡(luò)上，我們認(rèn)為客戶端和服務(wù)端都是不同的機(jī)器，但是，一個機(jī)器上的系統(tǒng)也可以擁有 C/S 架構(gòu)。例如，來自計算機(jī)輸入設(shè)備的信號需要讓運(yùn)行在計算機(jī)上的程序來訪問。這些程序就是客戶端，消耗鼠標(biāo)和鍵盤的輸入數(shù)據(jù)。操作系統(tǒng)的設(shè)備驅(qū)動就是服務(wù)端，接受物理的信號并將它們提供為可用的輸入。

C/S 系統(tǒng)的一個缺陷就是，服務(wù)端是故障單點(diǎn)。它是唯一能夠分發(fā)服務(wù)的組件。客戶端的數(shù)量可以是任意的，它們可以交替，并且可以按需出現(xiàn)和消失。但是如果服務(wù)器崩潰了，整個系統(tǒng)就會停止工作。所以，由 C/S 架構(gòu)創(chuàng)建的函數(shù)式抽象也使它具有崩潰的風(fēng)險。

C/S 系統(tǒng)的另一個缺陷是，當(dāng)客戶端非常多的時候，資源就變得稀缺?？蛻舳嗽黾酉到y(tǒng)上的命令而不貢獻(xiàn)任何計算資源。C/S 系統(tǒng)不能隨著不斷變化的需求縮小或擴(kuò)大。

2.2 P2P 系統(tǒng)

C/S 模型適合于服務(wù)導(dǎo)向的情形。但是，還有其它計算目標(biāo)，適合使用更加平等的分工。P2P 的術(shù)語用于描述一種分布式系統(tǒng)，其中勞動力分布在系統(tǒng)的所有組件中。所有計算機(jī)發(fā)送并接受數(shù)據(jù)，它們都貢獻(xiàn)一些處理能力和內(nèi)存。隨著分布式系統(tǒng)的規(guī)模增長，它的資源計算能力也會增長。在 P2P 系統(tǒng)中，系統(tǒng)的所有組件都對分布式計算貢獻(xiàn)了一些處理能力和內(nèi)存。

所有參與者的勞動力的分工是 P2P 系統(tǒng)的識別特征。也就是說，對等者需要能夠和其它人可靠地通信。為了確保消息到達(dá)預(yù)定的目的地，P2P 系統(tǒng)需要具有組織良好的網(wǎng)絡(luò)結(jié)構(gòu)。這些系統(tǒng)中的組件協(xié)作來維護(hù)足夠的其它組件的位置信息并將消息發(fā)送到預(yù)定的目的地。

在一些 P2P 系統(tǒng)中，維護(hù)網(wǎng)絡(luò)健康的任務(wù)由一系列特殊的組件執(zhí)行。這種系統(tǒng)并不是純粹的 P2P 系統(tǒng)，因為它們具有不同類型的組件類型，提供不同的功能。支持 P2P 網(wǎng)絡(luò)的組件就像腳手架那樣：它們有助于網(wǎng)絡(luò)保持連接，它們維護(hù)不同計算機(jī)的位置信息，并且它們新來者來鄰居中找到位置。

P2P 系統(tǒng)的最常見應(yīng)用就是數(shù)據(jù)傳送和存儲。對于數(shù)據(jù)傳送，系統(tǒng)中的每臺計算機(jī)都致力于網(wǎng)絡(luò)上的數(shù)據(jù)傳送。如果目標(biāo)計算機(jī)是特定計算機(jī)的鄰居，那臺計算機(jī)就一起幫助傳送數(shù)據(jù)。對于數(shù)據(jù)存儲，數(shù)據(jù)集可以過于龐大，不能在任何單臺計算機(jī)內(nèi)裝下，或者儲存在單臺計算機(jī)內(nèi)具有風(fēng)險。每臺計算機(jī)都儲存數(shù)據(jù)的一小部分，不同的計算機(jī)上可能會儲存相同數(shù)據(jù)的多個副本。當(dāng)一臺計算機(jī)崩潰時，上面的數(shù)據(jù)可以由其它副本恢復(fù)，或者在更換替代品之后放回。

Skype，一個音頻和視頻聊天服務(wù)，是采用 P2P 架構(gòu)的數(shù)據(jù)傳送應(yīng)用的示例。當(dāng)不同計算機(jī)上的兩個人都使用 Skype 交談時，它們的通信會拆成由 1 和 0 構(gòu)成的數(shù)據(jù)包，并且通過 P2P 網(wǎng)絡(luò)傳播。這個網(wǎng)絡(luò)由電腦上注冊了 Skype 的其它人組成。每臺計算機(jī)都知道附近其它人的位置。一臺計算機(jī)通過將數(shù)據(jù)包傳給它的鄰居，來幫助將它傳到目的地，它的鄰居又將它傳給其它鄰居，以此類推，直到數(shù)據(jù)包到達(dá)了它預(yù)定的目的地。Skype 并不是純粹的 P2P 系統(tǒng)。一個超級節(jié)點(diǎn)組成的腳手架網(wǎng)絡(luò)用于用戶登錄和退出，維護(hù)它們的計算機(jī)的位置信息，并且修改網(wǎng)絡(luò)結(jié)構(gòu)來處理用戶進(jìn)入和離開。

2.3 模塊化

我們剛才考慮的兩個架構(gòu) -- P2P 和 C/S -- 都為強(qiáng)制模塊化而設(shè)計。模塊化是一個概念，系統(tǒng)的組件對其它組件來說應(yīng)該是個黑盒。組件如何實現(xiàn)行為應(yīng)該并不重要，只要它提供了一個接口：規(guī)定了輸入應(yīng)該產(chǎn)生什么輸出。

在第二章中，我們在調(diào)度函數(shù)和面向?qū)ο缶幊痰纳舷挛闹杏龅搅私涌凇＿@里，接口的形式為指定對象應(yīng)接收的信息，以及對象應(yīng)如何響應(yīng)它們。例如，為了提供“表示為字符串”的接口，對象必須回復(fù) __repr__ 和 __str__ 信息，并且在響應(yīng)中輸出合適的字符串。那些字符串的生成如何實現(xiàn)并不是接口的一部分。

在分布式系統(tǒng)中，我們必須考慮涉及到多臺計算機(jī)的程序設(shè)計，所以我們將接口的概念從對象和消息擴(kuò)展為整個程序。接口指定了應(yīng)該接受的輸入，以及應(yīng)該在響應(yīng)中返回給輸入的輸出。

接口在真實世界的任何地方都存在，我們經(jīng)常習(xí)以為常。一個熟悉的例子就是 TV 遙控器。你可以買到許多牌子的遙控器或者 TV，它們都能工作。它們的唯一共同點(diǎn)就是“TV 遙控器”的接口。只要當(dāng)你按下電院、音量、頻道或者其它任何按鈕(輸入)時，一塊電路向你的 TV 發(fā)送正確的信號(輸出)，它就遵循“TV 遙控器”接口。

模塊化給予系統(tǒng)許多好處，并且是一種沉思熟慮的系統(tǒng)設(shè)計。首先，模塊化的系統(tǒng)易于理解。這使它易于修改和擴(kuò)展。其次，如果系統(tǒng)中什么地方發(fā)生錯誤，只需要更換有錯誤的組件。再者，bug 或故障可以輕易定位。如果組件的輸出不符合接口的規(guī)定，而且輸入是正確的，那么這個組件就是故障來源。

2.4 消息傳遞

在分布式系統(tǒng)中，組件使用消息傳遞來互相溝通。消息有三個必要部分：發(fā)送者、接收者和內(nèi)容。發(fā)送者需要被指定，便于接受者得知哪個組件發(fā)送了信息，以及將回復(fù)發(fā)送到哪里。接收者需要被指定，便于任何協(xié)助發(fā)送消息的計算機(jī)知道發(fā)送到哪里。消息的內(nèi)容是最寶貴的。取決于整個系統(tǒng)的函數(shù)，內(nèi)容可以是一段數(shù)據(jù)、一個信號，或者一條指令，讓遠(yuǎn)程計算機(jī)來以一些參數(shù)求出某個函數(shù)。

消息傳遞的概念和第二章的消息傳遞機(jī)制有很大關(guān)系，其中，調(diào)度函數(shù)或字典會響應(yīng)值為字符串的信息。在程序中，發(fā)送者和接受者都由求值規(guī)則標(biāo)識。但是在分布式系統(tǒng)中，接受者和發(fā)送者都必須顯式編碼進(jìn)消息中。在程序中，使用字符串來控制調(diào)度函數(shù)的行為十分方便。在分布式系統(tǒng)中，消息需要經(jīng)過網(wǎng)絡(luò)發(fā)送，并且可能需要存放許多不同種類的信號作為“數(shù)據(jù)”，所以它們并不始終編碼為字符串。但是在兩種情況中，消息都服務(wù)于相同的函數(shù)。不同的組件(調(diào)度函數(shù)或計算機(jī))交換消息來完成一個目標(biāo)，它需要多個組件模塊的協(xié)作。

在較高層面上，消息內(nèi)容可以是復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，但是在較低層面上，消息只是簡單的 1 和 0 的流，在網(wǎng)絡(luò)上傳輸。為了變得易用，所有網(wǎng)絡(luò)上發(fā)送的消息都需要根據(jù)一致的消息協(xié)議格式化。

消息協(xié)議是一系列規(guī)則，用于編碼和解碼消息。許多消息協(xié)議規(guī)定，消息必須符合特定的格式，其中特定的比特具有固定的含義。固定的格式實現(xiàn)了固定的編碼和解碼規(guī)則來生成和讀取這種格式。分布式系統(tǒng)中的所有組件都必須理解協(xié)議來互相通信。這樣，它們就知道消息的哪個部分對應(yīng)哪個信息。

消息協(xié)議并不是特定的程序或軟件庫。反之，它們是可以由大量程序使用的規(guī)則，甚至以不同的編程語言編寫。所以，帶有大量不同軟件系統(tǒng)的計算機(jī)可以加入相同的分布式系統(tǒng)，只需要遵守控制這個系統(tǒng)的消息協(xié)議。

2.5 萬維網(wǎng)上的消息

HTTP(超文本傳輸協(xié)議的縮寫)是萬維網(wǎng)所支持的消息協(xié)議。它指定了在 Web 瀏覽器和服務(wù)器之間交換的消息格式。所有 Web 瀏覽器都使用 HTTP 協(xié)議來請求服務(wù)器上的頁面，而且所有 Web 服務(wù)器都使用 HTTP 格式來發(fā)回它們的響應(yīng)。

當(dāng)你在 Web 瀏覽器上鍵入 URL 時，比如 http://en.wikipedia.org/wiki/UC_Berkeley ，你實際上就告訴了你的計算機(jī)，使用 "HTTP" 協(xié)議，從 " http://en.wikipedia.org/wiki/UC_Berkeley " 的服務(wù)器上請求 "wiki/UC_Berkeley" 頁面。消息的發(fā)送者是你的計算機(jī)，接受者是 en.wikipedia.org，以及消息內(nèi)容的格式是：

GET /wiki/UC_Berkeley HTTP/1.1 

第一個單詞是請求類型，下一個單詞是所請求的資源，之后是協(xié)議名稱(HTTP)和版本(1.1)。(請求還有其它類型，例如 PUT、POST 和 HEAD，Web 瀏覽器也會使用它們。)

服務(wù)器發(fā)回了回復(fù)。這時，發(fā)送者是 en.wikipedia.org，接受者是你的計算機(jī)，消息內(nèi)容的格式是由數(shù)據(jù)跟隨的協(xié)議頭：

HTTP/1.1 200 OK  
Date: Mon, 23 May 2011 22:38:34 GMT  
Server: Apache/1.3.3.7 (Unix) (Red-Hat/Linux)  
Last-Modified: Wed, 08 Jan 2011 23:11:55 GMT  
Content-Type: text/html; charset=UTF-8  
... web page content ... 

第一行，單詞 "200 OK" 表示沒有發(fā)生錯誤。協(xié)議頭下面的行提供了有關(guān)服務(wù)器的信息，日期和發(fā)回的內(nèi)容類型。協(xié)議頭和頁面的實際內(nèi)容通過一個空行來分隔。

如果你鍵入了錯誤的 Web 地址，或者點(diǎn)擊了死鏈，你可能會看到類似于這個錯誤的消息：

404 Error File Not Found 

它的意思是服務(wù)器發(fā)送回了一個 HTTP 協(xié)議頭，以這樣起始：

HTTP/1.1 404 Not Found 

一系列固定的響應(yīng)代碼是消息協(xié)議的普遍特性。協(xié)議的設(shè)計者試圖預(yù)料通過協(xié)議發(fā)送的常用消息，并且賦為固定的代碼來減少傳送大小，以及建立通用的消息語義。在 HTTP 協(xié)議中，200 響應(yīng)代碼表示成功，而 404 表示資源沒有找到的錯誤。其它大量 響應(yīng)代碼 也存在于 HTTP 1.1 標(biāo)準(zhǔn)中。

HTTP 是用于通信的固定格式，但是它允許傳輸任意的 Web 頁面。其它互聯(lián)網(wǎng)上的類似協(xié)議是 XMPP，即時消息的常用協(xié)議，以及 FTP，用于在客戶端和服務(wù)器之間下載和上傳文件的協(xié)議。

3 并行計算

計算機(jī)每一年都會變得越來越快。在 1965 年，英特爾聯(lián)合創(chuàng)始人戈登·摩爾預(yù)測了計算機(jī)將如何隨時間而變得越來越快。僅僅基于五個數(shù)據(jù)點(diǎn)，他推測，一個芯片中的晶體管數(shù)量每兩年將翻一倍。近50年后，他的預(yù)測仍驚人地準(zhǔn)確，現(xiàn)在稱為摩爾定律。

盡管速度在爆炸式增長，計算機(jī)還是無法跟上可用數(shù)據(jù)的規(guī)模。根據(jù)一些估計，基因測序技術(shù)的進(jìn)步將使可用的基因序列數(shù)據(jù)比處理器變得更快的速度還要快。換句話說，對于遺傳數(shù)據(jù)，計算機(jī)變得越來越不能處理每年需要處理的問題規(guī)模，即使計算機(jī)本身變得越來越快。

為了規(guī)避對單個處理器速度的物理和機(jī)械約束，制造商正在轉(zhuǎn)向另一種解決方案：多處理器。如果兩個，或三個，或更多的處理器是可用的，那么許多程序可以更快地執(zhí)行。當(dāng)一個處理器在做一些計算的一個切面時，其他的可以在另一個切面工作。所有處理器都可以共享相同的數(shù)據(jù)，但工作并行執(zhí)行。

為了能夠合作，多個處理器需要能夠彼此共享信息。這通過使用共享內(nèi)存環(huán)境來完成。該環(huán)境中的變量、對象和數(shù)據(jù)結(jié)構(gòu)對所有的進(jìn)程可見。處理器在計算中的作用是執(zhí)行編程語言的求值和執(zhí)行規(guī)則。在一個共享內(nèi)存模型中，不同的進(jìn)程可能執(zhí)行不同的語句，但任何語句都會影響共享環(huán)境。

3.1 共享狀態(tài)的問題

多個進(jìn)程之間的共享狀態(tài)具有單一進(jìn)程環(huán)境沒有的問題。要理解其原因，讓我們看看下面的簡單計算：

x = 5  
x = square(x)  
x = x + 1 

x 的值是隨時間變化的。起初它是 5，一段時間后它是 25，最后它是 26。在單一處理器的環(huán)境中，沒有時間依賴性的問題。 x 的值在結(jié)束時總是 26。但是如果存在多個進(jìn)程，就不能這樣說了。假設(shè)我們并行執(zhí)行了上面代碼的最后兩行：一個處理器執(zhí)行 x = square(x) 而另一個執(zhí)行 x = x + 1 。每一個這些賦值語句都包含查找當(dāng)前綁定到 x 的值，然后使用新值更新綁定。讓我們假設(shè) x 是共享的，同一時間只有一個進(jìn)程讀取或?qū)懭?。即使如此，讀和寫的順序可能會有所不同。例如，下面的例子顯示了兩個進(jìn)程的每個進(jìn)程的一系列步驟， P1 和 P2 。每一步都是簡要描述的求值過程的一部分，隨時間從上到下執(zhí)行：

在這個順序中， x 的最終值為 6。如果我們不協(xié)調(diào)這兩個過程，我們可以得到另一個順序的不同結(jié)果：

在這個順序中， x 將是 25。事實上存在多種可能性，這取決于進(jìn)程執(zhí)行代碼行的順序。 x 的最終值可能最終為 5，25，或預(yù)期值 26。

前面的例子是無價值的。 square(x) 和 x = x + 1 是簡單快速的計算。我們強(qiáng)迫一條語句跑在另一條的后面，并不會失去太多的時間。但是什么樣的情況下，并行化是必不可少的?這種情況的一個例子是銀行業(yè)。在任何給定的時間，可能有成千上萬的人想用他們的銀行賬戶進(jìn)行交易：他們可能想在商店刷卡，存入支票，轉(zhuǎn)帳，或支付賬單。即使一個帳戶在同一時間也可能有活躍的多個交易。

讓我們看看第二章的 make_withdraw 函數(shù)，下面是修改過的版本，在更新余額之后打印而不是返回它。我們感興趣的是這個函數(shù)將如何并發(fā)執(zhí)行。

>>> def make_withdraw(balance):  
def withdraw(amount):  
nonlocal balance  
if amount > balance:  
print('Insufficient funds')  
else:  
balance = balance - amount  
print(balance)  
return withdraw 

現(xiàn)在想象一下，我們以 10 美元創(chuàng)建一個帳戶，讓我們想想，如果我們從帳戶中提取太多的錢會發(fā)生什么。如果我們順序執(zhí)行這些交易，我們會收到資金不足的消息。

>>> w = make_withdraw(10)  
>>> w(8)  
2  
>>> w(7)  
'Insufficient funds' 

但是，在并行中可以有許多不同的結(jié)果。下面展示了一種可能性：

這個特殊的例子給出了一個不正確結(jié)果 3。就好像 w(8) 交易從來沒有發(fā)生過。其他可能的結(jié)果是 2，和 'Insufficient funds' 。這個問題的根源是：如果 P2 在 P1 寫入值前讀取余額， P2 的狀態(tài)是不一致的(反之亦然)。 P2 所讀取的余額值是過時的，因為 P1 打算改變它。 P2 不知道，并且會用不一致的值覆蓋它。

這個例子表明，并行化的代碼不像把代碼行分給多個處理器來執(zhí)行那樣容易。變量讀寫的順序相當(dāng)重要。

一個保證執(zhí)行正確性的有吸引力的方式是，兩個修改共享數(shù)據(jù)的程序不能同時執(zhí)行。不幸的是，對于銀行業(yè)這將意味著，一次只可以進(jìn)行一個交易，因為所有的交易都修改共享數(shù)據(jù)。直觀地說，我們明白，讓 2 個不同的人同時進(jìn)行完全獨(dú)立的帳戶交易應(yīng)該沒有問題。不知何故，這兩個操作不互相干擾，但在同一帳戶上的相同方式的同時操作就相互干擾。此外，當(dāng)進(jìn)程不讀取或?qū)懭霑r，讓它們同時運(yùn)行就沒有問題。

3.2 并行計算的正確性

并行計算環(huán)境中的正確性有兩個標(biāo)準(zhǔn)。第一個是，結(jié)果應(yīng)該總是相同。第二個是，結(jié)果應(yīng)該和串行執(zhí)行的結(jié)果一致。

第一個條件表明，我們必須避免在前面的章節(jié)中所示的變化，其中在不同的方式下的交叉讀寫會產(chǎn)生不同的結(jié)果。例子中，我們從 10 美元的帳戶取出了 w(8) 和 w(7) 。這個條件表明，我們必須始終返回相同的答案，獨(dú)立于 P1 和 P2 的指令執(zhí)行順序。無論如何，我們必須以這樣一種方式來編寫我們的程序，無論他們?nèi)绾蜗嗷ソ徊?，他們?yīng)該總是產(chǎn)生同樣的結(jié)果。

第二個條件揭示了許多可能的結(jié)果中哪個是正確的。例子中，我們從 10 美元的帳戶取出了 w(8) 和 w(7) ，這個條件表明結(jié)果必須總是余額不足，而不是 2 或者 3。

當(dāng)一個進(jìn)程在程序的臨界區(qū)影響另一個進(jìn)程時，并行計算中就會出現(xiàn)問題。這些都是需要執(zhí)行的代碼部分，它們看似是單一的指令，但實際上由較小的語句組成。一個程序會以一系列原子硬件指令執(zhí)行，由于處理器的設(shè)計，這些是不能被打斷或分割為更小單元的指令。為了在并行的情況下表現(xiàn)正確，程序代碼的臨界區(qū)需要具有原子性，保證他們不會被任何其他代碼中斷。

為了強(qiáng)制程序臨界區(qū)在并發(fā)下的原子性，需要能夠在重要的時刻將進(jìn)程序列化或彼此同步。序列化意味著同一時間只運(yùn)行一個進(jìn)程 -- 這一瞬間就好像串行執(zhí)行一樣。同步有兩種形式。首先是互斥，進(jìn)程輪流訪問一個變量。其次是條件同步，在滿足條件(例如其他進(jìn)程完成了它們的任務(wù))之前進(jìn)程一直等待，之后繼續(xù)執(zhí)行。這樣，當(dāng)一個程序即將進(jìn)入臨界區(qū)時，其他進(jìn)程可以一直等待到它完成，然后安全地執(zhí)行。

3.3 保護(hù)共享狀態(tài)：鎖和信號量

在本節(jié)中討論的所有同步和序列化方法都使用相同的基本思想。它們在共享狀態(tài)中將變量用作信號，所有過程都會理解并遵守它。這是一個相同的理念，允許分布式系統(tǒng)中的計算機(jī)協(xié)同工作 -- 它們通過傳遞消息相互協(xié)調(diào)，根據(jù)每一個參與者都理解和遵守的一個協(xié)議。

這些機(jī)制不是為了保護(hù)共享狀態(tài)而出現(xiàn)的物理障礙。相反，他們是建立相互理解的基礎(chǔ)上。和出現(xiàn)在十字路口的各種方向的車輛能夠安全通行一樣，是同一種相互理解。這里沒有物理的墻壁阻止汽車相撞，只有遵守規(guī)則，紅色意味著“停止”，綠色意味著“通行”。同樣，沒有什么可以保護(hù)這些共享變量，除非當(dāng)一個特定的信號表明輪到某個進(jìn)程了，進(jìn)程才會訪問它們。

鎖。鎖，也被稱為互斥體( mutex )，是共享對象，常用于發(fā)射共享狀態(tài)被讀取或修改的信號。不同的編程語言實現(xiàn)鎖的方式不同，但是在 Python 中，一個進(jìn)程可以調(diào)用 acquire() 方法來嘗試獲得鎖的“所有權(quán)”，然后在使用完共享變量的時候調(diào)用 release() 釋放它。當(dāng)進(jìn)程獲得了一把鎖，任何試圖執(zhí)行 acquire() 操作的其他進(jìn)程都會自動等待到鎖被釋放。這樣，同一時間只有一個進(jìn)程可以獲得一把鎖。

對于一把保護(hù)一組特定的變量的鎖，所有的進(jìn)程都需要編程來遵循一個規(guī)則：一個進(jìn)程不擁有特定的鎖就不能訪問相應(yīng)的變量。實際上，所有進(jìn)程都需要在鎖的 acquire() 和 release() 語句之間“包裝”自己對共享變量的操作。

我們可以把這個概念用于銀行余額的例子中。該示例的臨界區(qū)是從余額讀取到寫入的一組操作。我們看到，如果一個以上的進(jìn)程同時執(zhí)行這個區(qū)域，問題就會發(fā)生。為了保護(hù)臨界區(qū)，我們需要使用一把鎖。我們把這把鎖稱為 balance_lock (雖然我們可以命名為任何我們喜歡的名字)。為了鎖定實際保護(hù)的部分，我們必須確保試圖進(jìn)入這部分時調(diào)用 acquire() 獲取鎖，以及之后調(diào)用 release() 釋放鎖，這樣可以輪到別人。

>>> from threading import Lock  
>>> def make_withdraw(balance):  
balance_lock = Lock()  
def withdraw(amount):  
nonlocal balance  
# try to acquire the lock  
balance_lock.acquire()  
# once successful, enter the critical section  
if amount > balance:  
print("Insufficient funds")  
else:  
balance = balance - amount  
print(balance)  
# upon exiting the critical section, release the lock  
balance_lock.release()   

如果我們建立和之前一樣的情形：

w = make_withdraw(10) 

現(xiàn)在就可以并行執(zhí)行 w(8) 和 w(7) 了：

我們看到了，兩個進(jìn)程同時進(jìn)入臨界區(qū)是可能的。某個進(jìn)程實例獲取到了 balance_lock ，另一個就得等待，直到那個進(jìn)程退出了臨界區(qū)，它才能開始執(zhí)行。

要注意程序不會自己終止，除非 P1 釋放了 balance_lock 。如果它沒有釋放 balance_lock ， P2 永遠(yuǎn)不可能獲取它，而是一直會等待。忘記釋放獲得的鎖是并行編程中的一個常見錯誤。

信號量。信號量是用于維持有限資源訪問的信號。它們和鎖類似，除了它們可以允許某個限制下的多個訪問。它就像電梯一樣只能夠容納幾個人。一旦達(dá)到了限制，想要使用資源的進(jìn)程就必須等待。其它進(jìn)程釋放了信號量之后，它才可以獲得。

例如，假設(shè)有許多進(jìn)程需要讀取中心數(shù)據(jù)庫服務(wù)器的數(shù)據(jù)。如果過多的進(jìn)程同時訪問它，它就會崩潰，所以限制連接數(shù)量就是個好主意。如果數(shù)據(jù)庫只能同時支持 N=2 的連接，我們就可以以初始值 N=2 來創(chuàng)建信號量。

>>> from threading import Semaphore  
>>> db_semaphore = Semaphore(2) # set up the semaphore  
>>> database = []  
>>> def insert(data):  
db_semaphore.acquire() # try to acquire the semaphore  
database.append(data) # if successful, proceed  
db_semaphore.release() # release the semaphore  
>>> insert(7)  
>>> insert(8)  
>>> insert(9) 

信號量的工作機(jī)制是，所有進(jìn)程只在獲取了信號量之后才可以訪問數(shù)據(jù)庫。只有 N=2 個進(jìn)程可以獲取信號量，其它的進(jìn)程都需要等到其中一個進(jìn)程釋放了信號量，之后在訪問數(shù)據(jù)庫之前嘗試獲取它。

值為 1 的信號量的行為和鎖一樣。

3.4 保持同步：條件變量

條件變量在并行計算由一系列步驟組成時非常有用。進(jìn)程可以使用條件變量，來用信號告知它完成了特定的步驟。之后，等待信號的其它進(jìn)程就會開始它們的任務(wù)。一個需要逐步計算的例子就是大規(guī)模向量序列的計算。在計算生物學(xué)，Web 范圍的計算，和圖像處理及圖形學(xué)中，常常需要處理非常大型(百萬級元素)的向量和矩陣。想象下面的計算：

我們可以通過將矩陣和向量按行拆分，并把每一行分配到單獨(dú)的線程上，來并行處理每一步。作為上面的計算的一個實例，想象下面的簡單值：

我們將前一半(這里是第一行)分配給一個線程，后一半(第二行)分配給另一個線程：

在偽代碼中，計算是這樣的：

def do_step_1(index):  
A[index] = B[index] + C[index]  
def do_step_2(index):  
V[index] = M[index] . A 

進(jìn)程 1 執(zhí)行了：

do_step_1(1)  
do_step_2(1) 

進(jìn)程 2 執(zhí)行了：

do_step_1(2)  
do_step_2(2) 

如果允許不帶同步處理，就造成下面的不一致性：

問題就是 V 直到所有元素計算出來時才會計算出來。但是， P1 在 A 的所有元素計算出來之前，完成 A = B+C 并且移到 V = MA 。所以它與 M 相乘時使用了 A 的不一致的值。

我們可以使用條件變量來解決這個問題。

條件變量是表現(xiàn)為信號的對象，信號表示某個條件被滿足。它們通常被用于協(xié)調(diào)進(jìn)程，這些進(jìn)程需要在繼續(xù)執(zhí)行之前等待一些事情的發(fā)生。需要滿足一定條件的進(jìn)程可以等待一個條件變量，直到其它進(jìn)程修改了條件變量來告訴它們繼續(xù)執(zhí)行。

Python 中，任何數(shù)量的進(jìn)程都可以使用 condition.wait() 方法，用信號告知它們正在等待某個條件。在調(diào)用該方法之后，它們會自動等待到其它進(jìn)程調(diào)用了 condition.notify() 或 condition.notifyAll() 函數(shù)。 notify() 方法值喚醒一個進(jìn)程，其它進(jìn)程仍舊等待。 notifyAll() 方法喚醒所有等待中的進(jìn)程。每個方法在不同情形中都很實用。

由于條件變量通常和決定條件是否為真的共享變量相聯(lián)系，它們也提供了 acquire() 和 release() 方法。這些方法應(yīng)該在修改可能改變條件狀態(tài)的變量時使用。任何想要用信號告知條件已經(jīng)改變的進(jìn)程，必須首先使用 acquire() 來訪問它。

在我們的例子中，在執(zhí)行第二步之前必須滿足的條件是，兩個進(jìn)程都必須完成了第一步。我們可以跟蹤已經(jīng)完成第一步的進(jìn)程數(shù)量，以及條件是否被滿足，通過引入下面兩個變量：

step1_finished = 0  
start_step2 = Condition() 

我們在 do_step_2 的開頭插入 start_step_2().wait() 。每個進(jìn)程都會在完成步驟 1 之后自增 step1_finished ，但是我們只會在 step_1_finished = 2 時發(fā)送信號。下面的偽代碼展示了它：

step1_finished = 0  
start_step2 = Condition()  
def do_step_1(index):  
A[index] = B[index] + C[index]  
# access the shared state that determines the condition status  
start_step2.acquire()  
step1_finished += 1  
if(step1_finished == 2): # if the condition is met  
start_step2.notifyAll() # send the signal  
#release access to shared state  
start_step2.release()  
def do_step_2(index):  
# wait for the condition  
start_step2.wait()  
V[index] = M[index] . A 

在引入條件變量之后，兩個進(jìn)程會一起進(jìn)入步驟 2，像下面這樣：

在進(jìn)入 do_step_2 的時候， P1 需要在 start_step_2 之前等待，直到 P2 自增了 step1_finished ，發(fā)現(xiàn)了它等于 2，之后向條件發(fā)送信號。

3.5 死鎖

雖然同步方法對保護(hù)共享狀態(tài)十分有效，但它們也帶來了麻煩。因為它們會導(dǎo)致一個進(jìn)程等待另一個進(jìn)程，這些進(jìn)程就有 死鎖 的風(fēng)險。死鎖是一種情形，其中兩個或多個進(jìn)程被卡住，互相等待對方完成。我們已經(jīng)提到了忘記釋放某個鎖如何導(dǎo)致進(jìn)程無限卡住。但是即使 acquire() 和 release() 調(diào)用的數(shù)量正確，程序仍然會構(gòu)成死鎖。

死鎖的來源是 循環(huán)等待 ，像下面展示的這樣。沒有進(jìn)程能夠繼續(xù)執(zhí)行，因為它們正在等待其它進(jìn)程，而其它進(jìn)程也在等待它完成。

作為一個例子，我們會建立兩個進(jìn)程的死鎖。假設(shè)有兩把鎖， x_lock 和 y_lock ，并且它們像這樣使用：

>>> x_lock = Lock()  
>>> y_lock = Lock()  
>>> x = 1  
>>> y = 0  
>>> def compute():  
x_lock.acquire()  
y_lock.acquire()  
y = x + y  
x = x * x  
y_lock.release()  
x_lock.release()  
>>> def anti_compute():  
y_lock.acquire()  
x_lock.acquire()  
y = y - x  
x = sqrt(x)  
x_lock.release()  
y_lock.release() 

如果 compute() 和 anti_compute() 并行執(zhí)行，并且恰好像下面這樣互相交錯：

所產(chǎn)生的情形就是死鎖。 P1 和 P2 每個都持有一把鎖，但是它們需要兩把鎖來執(zhí)行。 P1 正在等待 P2 釋放 y_lock ，而 P2 正在等待 P1 釋放 x_lock 。所以，沒有進(jìn)程能夠繼續(xù)執(zhí)行。