摘要：第四章分布式和并行計(jì)算來源譯者飛龍協(xié)議引言目前為止，我們專注于如何創(chuàng)建解釋和執(zhí)行程序。一個(gè)交互的例子就是在線閱讀紐約時(shí)報(bào)。當(dāng)上的服務(wù)器與瀏覽器客戶端比如通信時(shí)，它的任務(wù)就是發(fā)送回來紐約時(shí)報(bào)主頁(yè)的。消息有三個(gè)必要部分發(fā)送者接收者和內(nèi)容。

來源：Chapter 4: Distributed and Parallel Computing
譯者：飛龍
協(xié)議：CC BY-NC-SA 4.0

目前為止，我們專注于如何創(chuàng)建、解釋和執(zhí)行程序。在第一章中，我們學(xué)會(huì)使用函數(shù)作為組合和抽象的手段。第二章展示了如何使用數(shù)據(jù)結(jié)構(gòu)和對(duì)象來表示和操作數(shù)據(jù)，以及向我們介紹了數(shù)據(jù)抽象的概念。在第三章中，我們學(xué)到了計(jì)算機(jī)程序如何解釋和執(zhí)行。結(jié)果是，我們理解了如何設(shè)計(jì)程序，它們?cè)趩我惶幚砥魃线\(yùn)行。

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

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

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

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

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

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

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

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

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

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

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

所有參與者的勞動(dòng)力的分工是 P2P 系統(tǒng)的識(shí)別特征。也就是說，對(duì)等者需要能夠和其它人可靠地通信。為了確保消息到達(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)，因?yàn)樗鼈兙哂胁煌愋偷慕M件類型，提供不同的功能。支持 P2P 網(wǎng)絡(luò)的組件就像腳手架那樣：它們有助于網(wǎng)絡(luò)保持連接，它們維護(hù)不同計(jì)算機(jī)的位置信息，并且它們新來者來鄰居中找到位置。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

GET /wiki/UC_Berkeley HTTP/1.1

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

服務(wù)器發(fā)回了回復(fù)。這時(shí)，發(fā)送者是 en.wikipedia.org，接受者是你的計(jì)算機(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ā)生錯(cuò)誤。協(xié)議頭下面的行提供了有關(guān)服務(wù)器的信息，日期和發(fā)回的內(nèi)容類型。協(xié)議頭和頁(yè)面的實(shí)際內(nèi)容通過一個(gè)空行來分隔。

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

404 Error File Not Found

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

HTTP/1.1 404 Not Found

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

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

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

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

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

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

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

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

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

P1                    P2
read x: 5
                      read x: 5
calculate 5*5: 25     calculate 5+1: 6
write 25 -> x
                      write x-> 6

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

P1                    P2
                      read x: 5
read x: 5             calculate 5+1: 6
calculate 5*5: 25     write x->6
write 25 -> x

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

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

讓我們看看第二章的make_withdraw函數(shù)，下面是修改過的版本，在更新余額之后打印而不是返回它。我們感興趣的是這個(gè)函數(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 美元?jiǎng)?chuàng)建一個(gè)帳戶，讓我們想想，如果我們從帳戶中提取太多的錢會(huì)發(fā)生什么。如果我們順序執(zhí)行這些交易，我們會(huì)收到資金不足的消息。

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

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

P1: w(8)                        P2: w(7)
read balance: 10
read amount: 8                  read balance: 10
8 > 10: False                   read amount: 7
if False                        7 > 10: False
10 - 8: 2                       if False
write balance -> 2              10 - 7: 3
read balance: 2                 write balance -> 3
print 2                         read balance: 3
                                print 3

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

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

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

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

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

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

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

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

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

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

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

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

我們可以把這個(gè)概念用于銀行余額的例子中。該示例的臨界區(qū)是從余額讀取到寫入的一組操作。我們看到，如果一個(gè)以上的進(jìn)程同時(shí)執(zhí)行這個(gè)區(qū)域，問題就會(huì)發(fā)生。為了保護(hù)臨界區(qū)，我們需要使用一把鎖。我們把這把鎖稱為balance_lock（雖然我們可以命名為任何我們喜歡的名字）。為了鎖定實(shí)際保護(hù)的部分，我們必須確保試圖進(jìn)入這部分時(shí)調(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)了：

P1                                  P2
acquire balance_lock: ok
read balance: 10                    acquire balance_lock: wait
read amount: 8                      wait
8 > 10: False                       wait
if False                            wait
10 - 8: 2                           wait
write balance -> 2                  wait
read balance: 2                     wait
print 2                             wait
release balance_lock                wait
                                    acquire balance_lock:ok
                                    read balance: 2
                                    read amount: 7
                                    7 > 2: True
                                    if True
                                    print "Insufficient funds"
                                    release balance_lock

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

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

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

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

>>> 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)

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

P1                          P2                           P3
acquire db_semaphore: ok    acquire db_semaphore: wait   acquire db_semaphore: ok
read data: 7                wait                         read data: 9
append 7 to database        wait                         append 9 to database
release db_semaphore: ok    acquire db_semaphore: ok     release db_semaphore: ok
                            read data: 8
                            append 8 to database
                            release db_semaphore: ok

值為 1 的信號(hào)量的行為和鎖一樣。

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

我們可以通過將矩陣和向量按行拆分，并把每一行分配到多帶帶的線程上，來并行處理每一步。作為上面的計(jì)算的一個(gè)實(shí)例，想象下面的簡(jiǎn)單值：

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

在偽代碼中，計(jì)算是這樣的：

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)

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

P1                          P2
read B1: 2
read C1: 0
calculate 2+0: 2
write 2 -> A1               read B2: 0
read M1: (1 2)              read C2: 5
read A: (2 0)               calculate 5+0: 5
calculate (1 2).(2 0): 2    write 5 -> A2
write 2 -> V1               read M2: (1 2)
                            read A: (2 5)
                            calculate (1 2).(2 5):12
                            write 12 -> V2

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

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

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

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

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

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

step1_finished = 0
start_step2 = Condition()

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

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

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

P1                            P2
read B1: 2
read C1: 0
calculate 2+0: 2
write 2 -> A1                 read B2: 0
acquire start_step2: ok       read C2: 5
write 1 -> step1_finished     calculate 5+0: 5
step1_finished == 2: false    write 5-> A2
release start_step2: ok       acquire start_step2: ok
start_step2: wait             write 2-> step1_finished
wait                          step1_finished == 2: true
wait                          notifyAll start_step_2: ok
start_step2: ok               start_step2:ok
read M1: (1 2)                read M2: (1 2)
read A:(2 5)
calculate (1 2). (2 5): 12    read A:(2 5)
write 12->V1                  calculate (1 2). (2 5): 12
                              write 12->V2

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

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

死鎖的來源是循環(huán)等待，像下面展示的這樣。沒有進(jìn)程能夠繼續(xù)執(zhí)行，因?yàn)樗鼈冋诘却渌M(jìn)程，而其它進(jìn)程也在等待它完成。

作為一個(gè)例子，我們會(huì)建立兩個(gè)進(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í)行，并且恰好像下面這樣互相交錯(cuò)：

P1                          P2
acquire x_lock: ok          acquire y_lock: ok
acquire y_lock: wait        acquire x_lock: wait
wait                        wait
wait                        wait
wait                        wait
...                         ...

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