[轉自程序員]

深遠影響

　　在過去30年里，并發雖然一直被鼓吹為“下一件大事”或“未來之路”，但軟件界不為所動。現在，并行終于出現在我們面前了：新一代計算機全面支持并發，這將引發軟件開發方式的巨變。

　　本文主要討論并發對軟件——包括編程語言和程序員——的深遠影響。

　　Olukotun和Hammond所描述的硬件發展，代表著計算機計算方式的重大變化。過去30年里，半導體工業的發展及其在處理器上的應用，推動了已有順序式軟件運行速度的穩步提升。但體系結構上的多核處理器變化僅對并發應用有益，因此幾乎對絕大多數現存軟件沒有價值。在不久的將來，已有的桌面應用不可能比現在跑得更快。實際上，它們的運行速度會稍慢，因為為了降低高密度多核處理器的電能消耗，新的芯片內核被簡化并運行在更低的時鐘速度。

　　這將對軟件至少是主流軟件的開發帶來深遠影響。計算機的能力無疑越來越強，但程序不再可能從硬件性能提升大餐中免費獲益，除非它們實現了并發。

　　即便拋開多核變化的強制要求不談，我們也有理由實現并發，尤其是將工作從同步轉到異步，可以提高響應速度，就像目前的應用里必須讓工作遠離GUI線程，以便計算在后臺進行時，屏幕能得到重繪。

　　但實現并發是有難度的。不僅目前的語言和工具仍未為將應用轉化為并行程序做好充分準備，而且在主流應用中也很難找到并行，尤其糟糕的是——并發要求程序員以人類難以適應的方式思維。

　　不過，多核在未來不可回避，我們必須找到與之相適應的軟件開發方式。接下來，我們將深入探討并發的難度所在，以及一些未來可能的應對方向。

軟件新紀元

　　今天的并發編程語言和工具幾乎與結構化編程時代初期的順序化編程同時起步。信號量和協程是實現并發的基本手段，鎖與線程建立在更高層次，可以結構化構造并發程序。而我們需要的是以面向對象為基礎的并發——建立在更高層次的抽象有助于構建并發程序，就像面向對象抽象有益于構建大型組件化程序一樣。

　　幾個因素決定了并發變革對我們沖擊可能比面向對象大。首先，并發是獲得更高性能的必需手段。像C之類的語言，無視面向對象，但仍能在很多開發領域發揮作用。如果并發變成了應用性能提升的華山一條路，那么商業和系統語言的存在價值就只能建立在支持并發編程的基礎上。因此現存的如C之類的語言，就必須支持超越pthreads之流簡單模式以外的并發特性，不能支持并發編程的語言將逐步走向消亡，而僅僅能在現代硬件不重要的場合占得一席之地。

　　并發比面向對象沖擊更大的第二個原因是，盡管順序化編程已經很難，但并發編程更難。例如，在分析順序化程序時，環境相關性分析是考量環境影響行為的基礎技術。并發程序則還需要進行同步分析，而同時做環境相關性和同步分析已經被證明不可企及

　　最后，人類在遭受并發的突然襲擊后，發現并發程序比順序化代碼難以把握得多。即使最細心的程序員，也很可能考慮不到簡單半有序作業集里的交叉問題。

客戶端和服務端應用的差別

　　對客戶端應用來說，并發是一個挑戰。但是在很多服務端程序里，并發則是一個“已經解決的問題”，我們可以例行公事般地構造并發應用，結果它就能很好工作，盡管進一步改進程序以確保其更具擴展性，仍需艱巨努力。這些程序通常都包含大量并行，因為它們同時處理的是大量的彼此無關的請求。比如Web服務器和網站，運行的是同樣代碼的副本，處理絕大多數時候彼此無關的數據。

　　而且，它們的執行環境被隔離，通過高度支持并發存取結構化數據的數據庫之類的抽象數據訪問方式實現狀態共享。因此，代碼通過數據庫實現數據共享，就能得到“安寧從容的感覺”——就好像運行在一個整潔、單線程的世界一樣。

　　而客戶端應用的世界里，則沒有那么規則和結構化。通常，客戶端程序為單用戶執行相關的小型運算，由此出發，我們發現可以通過將運算分割為多個更有效率的小片斷來實現并發。也就是說讓用戶界面和程序運算小片斷可能以多種方式交互和共享數據。但這類程序難以并發執行，因為其代碼是非均態的，結構密織、交互復雜，而且操作的是基于指針的數據結構。

并行

　　·編程模型(Programming Models)

　　現在，你能用多種方式實現并行，但每種方式僅僅適用于特定類型程序。大多數時候，沒有細致入微的設計與分析，很難事先知道哪種模型適合給定問題。如果無法清楚確定給出的問題能套用哪種模型，往往就必須將多個模型雜合起來靈活運用。

　　這些并行編程模型可以從以下兩個方面明確加以區分：并行作業的粒度，和任務間的耦合程度。這兩個方面的不同，造就了迥異的編程模型。我們接下來依次討論。

　　并行作業，小到單個指令，比如加法和乘法運算，大到需花費數小時甚至數天的程序。顯然，并行體系中小作業的累計耗費是巨大的，因此，像并行指令運算等一般要求用硬件實現。與多處理器結構相比，多核處理器減少了通訊和同步消耗，因此減少了小片代碼的累計成本。同樣，一般來說，粒度劃分越小，就越要注意拆分任務、以及為它們提供彼此間通訊和同步的成本。

　　另一方面是作業在通訊和同步時的耦合程度。不要有這樣的幻想：作業完全獨立執行，最后產生完全不同的輸出。在這種情況下，各作業有序執行，不會引發同步和通訊問題，很容易實現無數據競爭可能的編程。這樣的情況是罕見的，絕大多數程序的并發作業都要共享數據。因此作業更為變化多端，保證其正確和高效的復雜性也大為增加。最簡單的情況是每個任務執行完全一樣的代碼。這種類型的共享常常是規則的，通過對單個任務的分析就能理解。更具挑戰性的是不規則并行，這個時候，各作業的情況互不相同，共享模式更難于理解。

　　·無依賴并行(Independent parallelism)

　　可能最簡單、只具有基本行為的模型是無依賴并行(有時候也叫密集并行(EP，Embarrassingly Parallel))，一個或者多個作業獨立運行，處理分離的數據。

　　小粒度數據并行依賴于并發執行的作業的獨立性。它們應該無輸入輸出數據的共享、無交叉執行，比如：

　　double A[100][100];

　　…

　　A = A * 2;

　　求得100×100數組每個元素與2的乘積，然后保存到原元素位置。100000次的乘法運算都獨立運行，彼此沒有交叉。它可能是比大多數計算機的實際需要更理想化的并行模型，粒度很小，因此實際應用中通常會將矩陣分成n×m個塊，然后在這些塊的基礎上執行并行計算。

　　而在粒度軸的另一端，很多應用，比如搜索引擎，共享僅僅一個巨型只讀數據庫，因此要求并行查詢沒有交叉。同樣，大規模仿真系統要求很多并行程序同時訪問包含輸入參數的大型空間，這是一個讓人頗感棘手的并行應用。

　　·規則并行(Regular parallelism)

　　比無依賴并行略為復雜的是計算工作彼此依賴時，將同樣的操作應用到一個數據集上。如果在兩個操作間需要通訊或同步，則操作間存在依賴。

　　我們考慮以下用四個相鄰元素的平均值替換數組中每個元素的運算模型：

　　A[i, j] = (A[i-1, j] + A[i, j-1] + A[i+1, j] + A[i, j+1]) / 4;

　　這類運算要求細致協調，確保在用平均值替換前，已經準備好數組中相鄰數據。如果不考慮空間消耗，可以將計算得到的平均值寫入一個新數組。一般，其他更結構化的計算策略，比如用Diagonal Wavefront算法訪問數組，會得到同樣的結果，而且有更好的緩存尋址和更低的內存消耗收益。

　　規則并行程序可能需要同步控制，或者精心排練的執行策略，以確保得到正確的結果，但不像普通并行，它可以通過分析隱藏在操作后面的代碼以確定怎樣實現并行，并知道如何共享數據。

　　再次移到粒度軸的另一端，譬如Web站點上的運算工作，除了訪問相同數據庫，存在典型的獨立性。因此除了數據庫事務，所有的運算都并行進行，不需要大量協調工作。

　　·無結構并行(Unstructured parallelism)

　　大多數情況下，最沒有規律的并行形式是并行運算彼此不同，因此它們的數據訪問無可預測，需要通過顯式同步加以協調。這是使用多線程和顯式同步編寫的程序里最常見的并行形式，其中的線程在程序里扮演著互不相同的角色。一般，對于這種并行形式，除了知道兩個線程訪問數據發生沖突時需要顯式同步，我們在其他方面很難說出個頭頭道道;另外，這類程序具有不確定性。

鎖

　　·狀態共享存在的問題;鎖的局限性

　　無結構并行面臨的又一個挑戰來源于無結構狀態共享。客戶端應用通常通過共享內存的辦法來解決對象圖(Graphs of Objects)中交互行為無可預測的問題。

　　假設兩個任務希望訪問同一個對象，其中一個可以修改對象的狀態，如果我們不加控制，那么就會產生數據競爭。競爭的后果很糟糕，并發任務可能讀寫到不一致或已損毀的數據。

　　有大量同步策略可以解決數據競爭問題，其中最簡單的就是鎖。每一個需要訪問共享數據片的任務在訪問數據前必須申請得到鎖，然后執行計算;最后要釋放鎖，以便其他任務可以對這些數據執行別的操作。不幸的是，盡管鎖在一定程度上能避免數據競爭，但它也給現代軟件開發帶來了嚴重問題。

　　最主要的問題是，鎖不具有可組合性。你不能保證由兩部分以鎖為基礎、能正確運行的代碼合并得到的程序依然正確。而現代軟件開發的基礎恰恰是將小程序庫合并為更大程序的組裝能力;因此，我們無法做到不考察組件的具體實現，就能在它們基礎上組裝大軟件，這是個大問題。

　　造成組裝失敗的禍首是死鎖。考慮最簡單的情況，當兩個任務以相反順序申請兩個鎖時，死鎖就出現了：任務T1獲得了鎖L1，任務T2獲得了鎖L2，然后，T1申請獲得鎖L2，同時T2申請獲得L1。此時，兩個任務將永久阻塞。而被以相反順序請求兩個鎖的情況在任何時候都可能發生，所以獲得一個鎖后，只有讓調用進入你無法控制代碼的內部，才可能找到解決死鎖問題的辦法。

　　但是，那些可擴展的框架卻沒有考慮這個問題。即使目前最根正苗紅的商業應用框架也是這么干的，包括.NET框架、Java標準庫等。之所以沒出什么大問題，是因為開發人員仍然沒有編寫要求頻繁鎖定的大量并發的程序。很多復雜模型希望解決死鎖問題——比如實現退避/重送(backoff-and-retry)協議——但這些模型都需要程序員經受嚴格訓練，并且一些解決辦法還可能引入其他問題(比如活鎖(或空轉，livelock))。

　　通過確保所有鎖申請都只能在安全順序基礎上得到滿足的死鎖預防技術，也無能為力。例如鎖調整與鎖分級策略，要求所有同級鎖按照預定順序一次滿足，此后只能申請獲得更高級別的單一鎖，以此的確可以避免鎖沖突。這類技術雖然在實踐中還未普及，不過在單一團隊維護的模塊和框架內已經發揮了作用。但是，它們要求對全部代碼的完全控制。這就嚴重限制了這些技術在可擴展框架、插件系統和其他需要將多方編寫的代碼整合環境里的應用。

　　一個更基本問題是，鎖的實現依賴于程序員對協定的嚴格遵循。鎖與它所保護的數據間關系相當隱諱，只能通過程序員的紀律性得到維系。程序員必須總能清楚記得訪問共享數據前，要在正確地點放置恰當的鎖。有時，程序里的鎖管理協定的確存在，但它們幾乎從來沒有精確到可供工具實現檢驗。

　　鎖還有其他一些更加微妙的問題。鎖定是一個全局屬性，很難被本地化到單個過程、類或者框架。所有訪問共享數據片的代碼都必須知道且服從鎖約定，無論是誰編寫這些代碼，代碼用在什么地方。

　　即便將同步本地化，也并非任何時候都能正常工作。拿一個常見解決方案，如Java中的synchronized方法來說。對象的每個方法都能從對象得到一個鎖，所以沒有任何兩個線程可以同時直接訪問對象的狀態。而對象狀態僅能通過對象的方法訪問，程序員又記得給方法增加了synchronized聲明，如此一來，看似達到了我們的目的。

　　而實際上，synchronized方法至少有三個主要的問題。首先，它們不適合于其方法會調用別的對象(比如Java的Vector和.NET的SyncHashTable)的虛函數的類型，因為獲得一個鎖后調用進入第三方代碼，就可能引發死鎖。其次，synchronized方法可能導致頻繁鎖定，因為它們要求在所有的對象實例上獲得和釋放鎖，即便很多對象從不存在線程交互。第三，synchronized方法的鎖粒度過小，當程序在單或多個對象上調用多個方法時，無法保證操作的原子性。我們以如下簡單的銀行事務為例：

　　account1.Credit(amount); account2.Debit(amount)

　　逐對象(Per-object)鎖定可以保護每個調用，但不能阻止其他線程看到兩個賬戶在多次調用之間的不一致信息。這種類型的操作，原子性與單個調用的邊界不吻合，因此需要額外的、顯式同步。

　　·鎖的替代者

　　考慮到內容完整性，我得提一下鎖的兩個主要備選方案。一個是無鎖編程(Lock-Free Programming)。通過對處理器內存模式的深入認識，建立可共享但無顯式鎖定的數據結構是可能的。無鎖編程難度很大且非常脆弱，因此新的無鎖數據結構實現方案，仍在不斷修改之中。

　　第二個替代物是事務內存(Transactional Memory)，它將數據庫中事務模式的核心思想移植到編程語言里來。程序員將自己的程序編寫為一個個具有確定原子性的塊，它們可以分離執行，因此只有在每個原子行為執行前和執行后，并發操作才能訪問共享數據。盡管很多人看好事務內存的前途，但它目前仍處于研究之中。

對語言的要求

　　·我們需要何種編程語言

　　我們需要更高層次的語言抽象，要讓目前的命令式語言進化式擴展，這樣，現存的應用才能快速實現并發執行。無論是初始開發階段，還是維護階段，編程模型都必須讓并發易于理解和實現。

　　·顯式、隱式和自動并行

　　顯式編程模型提供的抽象要求程序員能明確定位并發出現的位置。其主要優點是，它允許程序員充分利用各自在應用領域的知識，充分挖掘應用的并發潛能。不足在于面對共享數據時，要求程序員高度熟練，以實現新的更高層次的編程抽象模型。

　　隱式編程模型將并發隱藏在庫和API包內部，因此在庫以并行方式執行工作時，程序員得以持續保有全局視野。這種方式可以讓初級程序員安全使用并發。主要弱點是難以獲得并發的全部性能收益。另外，也很難設計出在任何場合都不暴露并發的接口——比如，當程序將操作應用在相同數據的多個實例時。

　　另一個正被廣泛研究的方法是自動并行，編譯器試圖自動找到并行部分，通常應用于Forthan之類老式語言編寫的程序里。聽起來很吸引人哦，但這種辦法在實踐中不大行得通。必須有對程序的精確分析，才能弄清程序的潛在行為。而對Forthan之類簡單語言做這類分析就頗具挑戰性了，面對像C這樣的以指針為基礎操作數據的語言，更是難上加難。再說，順序式程序通常使用的是順序式算法，能實現并發的部分非常有限。

　　·命令式和函數式語言

　　流行商用編程語言(如Pascal、C、C++、Java和C#)都是命令式語言，在這些語言里，程序員分步指定對變量和數據結構的變化。小粒度控制構造(如循環)、低層次數據操作和共享易變對象實例等因此，使以這些語言編寫的程序難以分析并實現自動并行。

　　我們通常相信函數式語言，如Scheme、ML和Haskell等，能夠鏟除這類障礙，因為它們就為并發而生。以這些語言寫成的程序，操作沒有并發危險、不需改變的對象實例。此外，它們沒有副作用，執行順序上的限制很少。

　　但實際中，函數式語言并不一定有益于并發。函數式程序中的并行主要執行于過程調用層次，這對于傳統并行處理器來說，粒度過小。而且，大多數函數式語言允許操作可變對象時存在部分副作用，因此應用了這些特性的代碼，也難以實現自動并行。

　　這些語言為了增加表達能力和提高效率又引入了可變狀態。在純粹的函數式語言里，復合數據結構，如數組、樹等，是通過原結構副本外加待修改數據實現更新的。這種方法從語義上講頗有魅力，但性能糟糕(線性算法很容易升級為二階算法)。此外，函數式更新對嚴格的順序式運算無能為力，此時，每個操作都會等待至上一個操作完成對程序狀態的更新才能執行。

　　函數式語言對于并發的真正貢獻是這些語言中廣泛采用的高層次編程方式，在這種方式下，像Map和Map-Reduce等操作會將計算應用于復合數據結構的所有元素。這種高層次的操作方式是并發的堅實基礎。這種編程風格，幸運的是，這種編程方式沒有被固化于函數式語言，對命令式語言有重要借鑒意義。

　　例如，Google的Jeffrey Dean和Sanjay Ghemawat描述過Google如何使用Map-Reduce實現大規模分布式計算。命令式語言可以開動腦筋將這些特性納為己用，并從中獲益。這一點重要，畢竟，我們的工業不能從頭再來。為了保護全世界對現存軟件的巨大投資，特別需要盡快增加對并發的支持，同時保護軟件開發人員擁有的命令式語言專業知識和經驗。

抽象優化

　　目前的大多數語言都在線程和鎖層次實現了顯式編程。這種抽象層次過低且難以系統化。這種架構不足以成為構建抽象的堅實基礎，它縱容多線程程序隨意阻塞和重入(reentrancy)，以致帶來很多問題。

　　更高層次抽象允許程序員用自然方式表述任務，此時，運行時系統能將這些任務有計劃調度，使之適配于計算機硬件。這將使應用在新的硬件上獲得更好性能。另外，在常規開發中，程序員將得閑將精力放在任務內部的順序執行流程上來。

　　有關更高層次抽象的兩個基本例子是異步調用和future。無阻塞函數和方法產生的是異步調用。調用者可繼續執行，從概念上說，也就是消息被發送到任務或者fork進程去獨立執行操作。期貨(future)是一種從異步調用返回操作結果的機制，但目前僅是一個有價值的概念，還未具體實現。

　　更高層次抽象的又一個例子是主動對象(Active Object)，它運行在自有的線程里，因此創建1000個這樣的對象，就相當于創建了1000個執行線程。主動對象僅有一個方法在給定時間執行，它扮演監視器的角色，但不要求傳統意義上的鎖定。相反，來源于主動對象外部的方法調用是通過此對象匯集、編隊和派發異步消息實現的。從專業化的Actor語言到傳統C代碼的STA(Single-Threaded Apartment)式COM套件等，主動對象有很多種設計實現。

　　其他更高層次抽象也是需要的，比如描述和檢測異步消息交換的協議。所有這些方法應該被整合起來構建一個統一的編程模型，從而滿足各主要粒度層次的典型應用的并發要求。

對工具的要求

　　·我們需要何種工具

　　因為并行編程的固有難度和我們對它的不熟悉，必然需要更好的編程工具系統地幫助我們查漏補缺、調試程序、尋找性能瓶頸和測試程序。沒有這些工具，并發將成為提高開發和測試人員生產率的障礙，導致并發軟件成本更高，而質量更低劣。

　　并發會帶來不同于順序式代碼的新型程序錯誤。數據競爭(同步不足或死鎖造成)和活鎖(不適當同步造成)缺陷難以發現和理解，因為其行為通常具有不確定性且難以重現。傳統調試方法，比如啟動前設置斷點再重新運行程序，對于執行路徑和行為每次都可能發生變化的并發程序來說，無能為力。

　　在并發世界里，系統級的缺陷檢測工具具有重大價值。這些工具利用靜態程序分析法系統地探測程序所有可能的執行行為，因此它們能夠捕捉到不能重現的錯誤。盡管類似技術，比如模型檢測，已經在天生支持并發的硬件的缺陷探測中獲得重大成功，但在軟件中非常困難。大多數情況下，軟件的狀態空間比硬件大得多，因此這些系統探測虛擬狀態的技術還有很多工作要做。無論是硬件還是軟件，模塊化和抽象都是提高分析可行性的關鍵。在硬件模型測試中，如果你能將ALU (arithmetic logic unit)拆分為一個個寄存器做獨立分析，那么你的任務就變得很容易實現了。

　　這就引出了軟件更難以分析的第二個原因：將軟件切分為眾多片段，做獨立分析，然后合并結果去看它們如何一起工作要難得多。共享狀態、不確定接口和格式不明的交互將使軟件分析任務的挑戰性大大增加。

　　目前，并發軟件的缺陷檢測工具是個熱門研究領域。其中，微軟研究院的KISS(Keep it Strictly Sequential)是項有前途的技術，它將多線程程序轉化為包括了原始的不超過兩個切換環境的線程的所有可能行為的順序式程序。轉換后的程序可以被大量現存的順序式工具分析，因此這些工具得以完成有限模型的并發缺陷檢測工作。

　　即便我們取得了上述一些成績，程序員仍然需要優秀的調試工具幫助他們理解并行程序里的復雜和難以重現的交互行為。有兩項常規技術可以收集這方面信息。一是更好的日志跟蹤工具，可以記錄哪一個消息被送到了哪個進程或線程，進程和線程又訪問了哪個對象，因此開發者可以回溯并部分理解程序的執行行為。開發者也希望獲得追蹤跨線程因果關系(比如哪個消息傳遞到了主動對象，何時執行，導致哪一個別的消息傳遞到了其他主動對象)、回放、重排隊列里的消息、步進包含回調的異步調用模式，以及其他能力，借以檢測代碼的并發執行行為。第二個辦法是重放執行，它能讓程序員備份程序的執行歷史，然后可重新執行一些代碼。重放調試的想法由來已久，但它的高成本和復雜性導致了被拋棄的下場。最近，虛擬機監視器(VMM，Virtual Machine Monitor)已經逐漸呈現出取代這兩項技術的趨勢，未來的并發世界里，這項技術很可能成為必需品。

　　并發世界也需要性能調試和調節方面的新工具。并發引入了新的性能瓶頸，比如鎖競爭(Lock Contention)、緩存一致性(Cache Coherence)管理和鎖護送效應(Lock Convoys)等，這些問題依靠簡單工具是難以察覺的。對計算機底層和程序并發結構更為敏感的新工具，將幫助我們更好的發現這些問題。

　　測試領域，也必須發生變化。并發程序，因其不確定性行為，更難于測試。用以跟蹤語句和分支是否得到執行的簡單代碼覆蓋測試方法，需要被擴展以支持對其他并行執行代碼的評估，否則測試將提供不符實際的反應程序執行完整度的優化結果圖。另外，簡單壓力測試也需要通過更多地使用類似模塊檢測技術以探測系統狀態空間的系統級技術加以擴充。比如，Verisoft使用這些技術在尋找電話交換軟件錯誤方面已經取得相當成功。現在，很多并發應用通過加大測試時的壓力大小來建立應用不太可能遭受嚴重競爭的信心。未來，這將愈加顯得不夠，軟件開發者將必須以嚴格的確定性測試代替基于壓力測試的想當然，來證明他們產品的質量。

并行是關鍵

　　并發解決方案將是軟件史上的一次重大變革。其難點不在于多核硬件的構建，二是讓主流應用從持續爆炸式增長的CPU性能中獲益的編程方式。

　　軟件工業必須重歸現存應用在新硬件上更快運行的跑道。為此，我們必須開始學習編寫包含至少數十最好數百可分離任務(當然不是說同時處于活動狀態)的并發應用。

　　并發也開啟了新的可能，那就是讓軟件功能更多、能力更強。這就要求我們積極發揮想象力，找到挖掘并利用新處理器指數級增長的潛能的辦法。

　　為了促成軟件目標的早日實現，程序語言設計師、系統構建者和編程工具創造者需要開始努力思考并行，找到比目前成為并行程序構建基礎的低層次線程工具和顯式同步更好的技術。我們需要更高層次的并行構建實現，借此更清楚表述開發人員的意圖，以使程序的并行架構更加明晰，更容易理解，更能被工具驗證。