摘要：第四章分布式和并行計算來源譯者飛龍協議引言目前為止，我們專注于如何創建解釋和執行程序。一個交互的例子就是在線閱讀紐約時報。當上的服務器與瀏覽器客戶端比如通信時，它的任務就是發送回來紐約時報主頁的。消息有三個必要部分發送者接收者和內容。

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

目前為止，我們專注于如何創建、解釋和執行程序。在第一章中，我們學會使用函數作為組合和抽象的手段。第二章展示了如何使用數據結構和對象來表示和操作數據，以及向我們介紹了數據抽象的概念。在第三章中，我們學到了計算機程序如何解釋和執行。結果是，我們理解了如何設計程序，它們在單一處理器上運行。

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

接下來，我們會考慮并行計算。并行計算是這樣，當一個小程序由多個處理器使用共享內存執行時，所有處理器都并行工作來使任務完成得更快。并發（或并行）引入了新的挑戰，并且我們會開發新的機制來管理并發程序的復雜性。

分布式系統是自主的計算機網絡，計算機互相通信來完成一個目標。分布式系統中的計算機都是獨立的，并且沒有物理上共享的內存或處理器。它們使用消息來和其它計算機通信，消息是網絡上從一臺計算機到另一臺計算機傳輸的一段信息。消息可以用于溝通許多事情：計算機可以讓其它計算機來執行一個帶有特定參數的過程，它們可以發送和接受數據包，或者發送信號讓其它計算機執行特定行為。

分布式系統中的計算機具有不同的作用。計算機的作用取決于系統的目標，以及計算機自身的硬件和軟件屬性。分布式系統中，有兩種主要方式來組織計算機，一種叫客戶端-服務端架構（C/S 架構），另一種叫做對等網絡架構（P2P 架構）。

C/S 架構是一種從中心來源分發服務的方式。只有單個服務端提供服務，多臺客戶端和服務器通信來消耗它的產出。在這個架構中，客戶端和服務端都有不同的任務。服務端的任務就是響應來自客戶端的服務請求，而客戶端的任務就是使用響應中提供的數據來執行一些任務。

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

客戶端和服務端的概念是強大的函數式抽象。客戶端僅僅是一個提供服務的單位，可能同時對應多個客戶端。客戶端是消耗服務的單位。客戶端并不需要知道服務如何提供的細節，或者所獲取的數據如何儲存和計算，服務端也不需要知道數據如何使用。

在網絡上，我們認為客戶端和服務端都是不同的機器，但是，一個機器上的系統也可以擁有 C/S 架構。例如，來自計算機輸入設備的信號需要讓運行在計算機上的程序來訪問。這些程序就是客戶端，消耗鼠標和鍵盤的輸入數據。操作系統的設備驅動就是服務端，接受物理的信號并將它們提供為可用的輸入。

C/S 系統的一個缺陷就是，服務端是故障單點。它是唯一能夠分發服務的組件。客戶端的數量可以是任意的，它們可以交替，并且可以按需出現和消失。但是如果服務器崩潰了，整個系統就會停止工作。所以，由 C/S 架構創建的函數式抽象也使它具有崩潰的風險。

C/S 系統的另一個缺陷是，當客戶端非常多的時候，資源就變得稀缺。客戶端增加系統上的命令而不貢獻任何計算資源。C/S 系統不能隨著不斷變化的需求縮小或擴大。

C/S 模型適合于服務導向的情形。但是，還有其它計算目標，適合使用更加平等的分工。P2P 的術語用于描述一種分布式系統，其中勞動力分布在系統的所有組件中。所有計算機發送并接受數據，它們都貢獻一些處理能力和內存。隨著分布式系統的規模增長，它的資源計算能力也會增長。在 P2P 系統中，系統的所有組件都對分布式計算貢獻了一些處理能力和內存。

所有參與者的勞動力的分工是 P2P 系統的識別特征。也就是說，對等者需要能夠和其它人可靠地通信。為了確保消息到達預定的目的地，P2P 系統需要具有組織良好的網絡結構。這些系統中的組件協作來維護足夠的其它組件的位置信息并將消息發送到預定的目的地。

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

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

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

我們剛才考慮的兩個架構 -- P2P 和 C/S -- 都為強制模塊化而設計。模塊化是一個概念，系統的組件對其它組件來說應該是個黑盒。組件如何實現行為應該并不重要，只要它提供了一個接口：規定了輸入應該產生什么輸出。

在第二章中，我們在調度函數和面向對象編程的上下文中遇到了接口。這里，接口的形式為指定對象應接收的信息，以及對象應如何響應它們。例如，為了提供“表示為字符串”的接口，對象必須回復__repr__和__str__信息，并且在響應中輸出合適的字符串。那些字符串的生成如何實現并不是接口的一部分。

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

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

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

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

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

在較高層面上，消息內容可以是復雜的數據結構，但是在較低層面上，消息只是簡單的 1 和 0 的流，在網絡上傳輸。為了變得易用，所有網絡上發送的消息都需要根據一致的消息協議格式化。

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

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

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

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

GET /wiki/UC_Berkeley HTTP/1.1

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

服務器發回了回復。這時，發送者是 en.wikipedia.org，接受者是你的計算機，消息內容的格式是由數據跟隨的協議頭：

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" 表示沒有發生錯誤。協議頭下面的行提供了有關服務器的信息，日期和發回的內容類型。協議頭和頁面的實際內容通過一個空行來分隔。

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

404 Error File Not Found

它的意思是服務器發送回了一個 HTTP 協議頭，以這樣起始：

HTTP/1.1 404 Not Found

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

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

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

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

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

為了能夠合作，多個處理器需要能夠彼此共享信息。這通過使用共享內存環境來完成。該環境中的變量、對象和數據結構對所有的進程可見。處理器在計算中的作用是執行編程語言的求值和執行規則。在一個共享內存模型中，不同的進程可能執行不同的語句，但任何語句都會影響共享環境。

多個進程之間的共享狀態具有單一進程環境沒有的問題。要理解其原因，讓我們看看下面的簡單計算：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

并行計算環境中的正確性有兩個標準。第一個是，結果應該總是相同。第二個是，結果應該和串行執行的結果一致。

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

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

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

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

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

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

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

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

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

現在就可以并行執行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

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

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

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

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

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

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

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 的信號量的行為和鎖一樣。

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

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

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

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

def do_step_1(index):
  A[index] = B[index] + C[index]

def do_step_2(index):
        V[index] = M[index] . A

進程 1 執行了：

do_step_1(1)
do_step_2(1)

進程 2 執行了：

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

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

條件變量是表現為信號的對象，信號表示某個條件被滿足。它們通常被用于協調進程，這些進程需要在繼續執行之前等待一些事情的發生。需要滿足一定條件的進程可以等待一個條件變量，直到其它進程修改了條件變量來告訴它們繼續執行。

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

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

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

step1_finished = 0
start_step2 = Condition()

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

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

在引入條件變量之后，兩個進程會一起進入步驟 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

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

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

死鎖的來源是循環等待，像下面展示的這樣。沒有進程能夠繼續執行，因為它們正在等待其它進程，而其它進程也在等待它完成。

作為一個例子，我們會建立兩個進程的死鎖。假設有兩把鎖，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()并行執行，并且恰好像下面這樣互相交錯：

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

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