閱讀802 返回首頁    go 阿裏雲 go 技術社區[雲棲]

深入理解並行編程-分割和同步設計（四）

設計模式與鎖粒度

圖1.1：設計模式與鎖粒度

圖1.1是不同程度同步粒度的圖形表示。每一種同步粒度都用一節內容來描述。下麵幾節主要關注鎖，不過其他幾種同步方式也有類似的粒度問題。

1.1. 串行程序

Intel處理器的MIPS時鍾頻率變化趨勢

圖1.2：Intel處理器的MIPS/時鍾頻率變化趨勢

如果程序在單處理器上運行的足夠快，並且不與其他進程、線程或者中斷處理程序發生交互，那麼您可以將代碼中所有的同步原語刪掉，遠離它們所帶來的開銷和複雜性。好多年前曾有人爭論摩爾定律最終會讓所有程序都變得如此。但是，隨著2003年以來Intel CPU的CPU MIPS和時鍾頻率增長速度的停止，見圖1.2，此後要增加性能，就必須提高程序的並行化程度。關於是否這種趨勢會導致一塊芯片上集成幾千個CPU的爭論不會很快停息，但是考慮到Paul是在一台雙核筆記本上敲下這句話的，SMP的壽命極有可能比你我都長。另一個需要注意的地方是以太網的帶寬持續增長，如圖1.3所示。這種增長會導致多線程服務器的產生，這樣才能有效處理通信載荷。

以太網帶寬 v.s. Intel x86處理器的性能

圖1.3：以太網帶寬 v.s. Intel x86處理器的性能

請注意，這並不意味這您應該在每個程序中使用多線程方式編程。我再一次說明，如果一個程序在單處理器上運行的很好，那麼您就從SMP同步原語的開銷和複雜性中解脫出來吧。圖1.4中哈希表查找代碼的簡單之美強調了這一點。

01 struct hash_table
02  
03 {
04  
05 long nbuckets;
06  
07 struct node **buckets;
08  
09 };
10  
11 typedef struct node {
12  
13 unsigned long key;
14  
15 struct node *next;
16  
17 } node_t;
18  
19 int hash_search(struct hash_table *h, long key)
20  
21 {
22  
23 struct node *cur;
24  
25 cur = h->buckets[key % h->nbuckets];
26  
27 while (cur != NULL) {
28  
29 if (cur->key >= key) {
30  
31 return (cur->key == key);
32  
33 }
34  
35 cur = cur->next;
36  
37 }
38  
39 return 0;
40  
41 }

圖1.4：串行版的哈希表搜索算法

1.2. 代碼鎖

代碼鎖是最簡單的設計，隻使用全局鎖。在已有的程序上使用代碼鎖，可以很容易的讓程序可以在多處理器上運行。如果程序隻有一個共享資源，那麼代碼鎖的性能是最優的。但是，許多較大且複雜的程序會在臨界區上執行許多次，這就讓代碼鎖的擴展性大大受限。

01 spinlock_t hash_lock;
02  
03 struct hash_table
04  
05 {
06  
07 long nbuckets;
08  
09 struct node **buckets;
10  
11 };
12  
13 typedef struct node {
14  
15 unsigned long key;
16  
17 struct node *next;
18  
19 } node_t;
20  
21 int hash_search(struct hash_table *h, long key)
22  
23 {
24  
25 struct node *cur;
26  
27 int retval;
28  
29 spin_lock(&hash_lock);
30  
31 cur = h->buckets[key % h->nbuckets];
32  
33 while (cur != NULL) {
34  
35 if (cur->key >= key) {
36  
37 retval = (cur->key == key);
38  
39 spin_unlock(&hash_lock);
40  
41 return retval;
42  
43 }
44  
45 cur = cur->next;
46  
47 }
48  
49 spin_unlock(&hash_lock);
50  
51 return 0;
52  
53 }

圖1.5：基於代碼鎖的哈希表搜索算法

因此，您最好在隻有一小段執行時間在臨界區程序，或者對擴展性要求不高的程序上使用代碼鎖。這種情況下，代碼鎖可以讓程序相對簡單，和單線程版本類似，如圖1.5所示。但是，和圖1.4相比，hash_search()從簡單的一行return變成了3行語句，因為在返回前需要釋放鎖。

圖1.6：鎖競爭

並且，代碼鎖尤其容易引起“鎖競爭”，一種多個CPU並發訪問同一把鎖的情況。照顧一群小孩子（或者像小孩子一樣的老人）的SMP程序員肯定能馬上意識到某樣東西隻有一個的危險，如圖1.6所示。

該問題的一種解決辦法是下節描述的“數據鎖”。

1.3. 數據鎖

01 struct hash_table
02 {
03 long nbuckets;
04 struct bucket **buckets;
05 };
06  
07 struct bucket {
08 spinlock_t bucket_lock;
09 node_t *list_head;
10 };
11  
12 typedef struct node {
13 unsigned long key;
14 struct node *next;
15 } node_t;
16  
17 int hash_search(struct hash_table *h, long key)
18 {
19 struct bucket *bp;
20 struct node *cur;
21 int retval;
22  
23 bp = h->buckets[key % h->nbuckets];
24 spin_lock(&bp->bucket_lock);
25 cur = bp->list_head;
26 while (cur != NULL) {
27 if (cur->key >= key) {
28 retval = (cur->key == key);
29 spin_unlock(&bp->hash_lock);
30 return retval;
31 }
32 cur = cur->next;
33 }
34 spin_unlock(&bp->hash_lock);
35 return 0;
36 }

圖1.7：基於數據鎖的哈希表搜索算法

許多數據結構都可以分割，數據結構的每個部分帶有一把自己的鎖。這樣雖然每個部分一次隻能執行一個臨界區，但是數據結構的各個部分形成的臨界區就可以並行執行了。在鎖競爭必須降低時，和同步開銷不是主要局限時，可以使用數據鎖。數據鎖通過將一塊過大的臨界區分散到各個小的臨界區來減少鎖競爭，比如，維護哈希表中的per-hash-bucket臨界區，如圖1.7所示。不過這種擴展性的增強帶來的是複雜性的提高，增加了額外的數據結構struct bucket。

數據鎖

圖1.8：數據鎖

和圖1.6中所示的緊張局麵不同，數據鎖帶來了和諧，見圖1.8——在並行程序中，這總是意味著性能和可擴展性的提升。基於這種原因，Sequent在它的DYNIX和DYNIX/ptx操作係統中大量使用了數據鎖[BK85][Inm85][Gar90][Dov90][MD92][MG92][MS93]。

不過，那些照顧過小孩子的人可以證明，再細心的照料也不能保證一切風平浪靜。同樣的情況也適用於SMP程序。比如，Linux內核維護了一種文件和目錄的緩存（叫做“dcache”）。該緩存中的每個條目都有一把自己的鎖，但是對應根目錄的條目和它的直接後代相較於其他條目更容易被遍曆到。這將導致許多CPU競爭這些熱門條目的鎖，就像圖1.9中所示的情景。

數據鎖出現問題

圖1.9：數據鎖出現問題

在許多情況下，可以設計算法來減少數據衝突的次數，某些情況下甚至可以完全消滅衝突（像Linux內核中的dcache一樣[MSS04]）。數據鎖通常用於分割像哈希表一樣的數據結構，也適用於每個條目用某個數據結構的實例表示這種情況。2.6.17內核的task list就是後者的例子，每個任務結構都有一把自己的proc_lock鎖。

在動態分配結構中，數據鎖的關鍵挑戰是如何保證在已經獲取鎖的情況下結構本身是否存在。圖1.7中的代碼通過將鎖放入靜態分配並且永不釋放的哈希桶，解決了上述挑戰。但是，這種手法不適用於哈希表大小可變的情況，所以鎖也需要動態分配。在這種情況，還需要一些手段來阻止哈希桶在鎖被獲取後這段時間內釋放。

小問題1.1：當結構的鎖被獲取時，如何防止結構被釋放呢？

1.4. 數據所有權

數據所有權方法按照線程或者CPU的個數分割數據結構，這樣每個線程/CPU都可以在不需任何同步開銷的情況下訪問屬於它的子集。但是如果線程A希望訪問另一個線程B的數據，那麼線程A是無法直接做到這一點的。取而代之的是，線程A需要先與線程B通信，這樣線程B以線程A的名義執行操作，或者，另一種方法，將數據遷移到線程A上來。

數據所有權看起來很神秘，但是卻應用得十分頻繁。

1. 任何隻能被一個CPU或者一個線程訪問的變量（C或者C++中的auto變量）都屬於這個CPU或者這個進程。

2. 用戶接口的實例擁有對應的用戶上下文。這在與並行數據庫引擎交互的應用程序中十分常見，這讓並行引擎看起來就像順序程序一樣。這樣的應用程序擁有用戶接口和他當前的操作。顯式的並行化隻在數據庫引擎內部可見。

3. 參數模擬通常授予每個線程一段特定的參數區間，以此達到某種程度的並行化。

如果共享比較多，線程或者CPU間的通信會帶來較大的複雜性和通信開銷。不僅如此，如果使用的最多的數據正好被一個CPU擁有，那麼這個CPU就成為了“熱點”，有時就會導致圖1.9中的類似情況。不過，在不需要共享的情況下，數據所有權可以達到理想性能，代碼也可以像圖1.4中所示的順序程序例子一樣簡單。最壞情況通常被稱為“尷尬的並行化”，而最好情況，則像圖1.8中所示一樣。

另一個數據所有權的重要實例發生在數據是隻讀時，這種情況下，所有線程可以通過複製來“擁有”數據。

1.5鎖粒度與性能

本節以一種數學上的同步效率的視角，將視線投向鎖粒度和性能。對數學不敢興趣的讀者可以跳過本節。

本節的方法是用一種關於同步機製效率的粗略隊列模型，該機製隻操作一個共享的全局變量，基於M/M/1隊列。M/M/1隊列。

（本節未翻譯）

文章轉自 並發編程網-ifeve.com

最後更新：2017-05-22 15:03:24

  上一篇：go  深度學習論文閱讀路線圖
  下一篇：go  看人品的阿裏雲代金券--阿裏雲幸運券，適用大量阿裏雲熱門服務的代金券免費領取