6.1 為并發(fā)設(shè)計的意義何在？

設(shè)計并發(fā)數(shù)據(jù)結(jié)構(gòu)，意味著多個線程可以并發(fā)的訪問這個數(shù)據(jù)結(jié)構(gòu)，線程可對這個數(shù)據(jù)結(jié)構(gòu)做相同或不同的操作，并且每一個線程都能在自己的自治域中看到該數(shù)據(jù)結(jié)構(gòu)。且在多線程環(huán)境下，無數(shù)據(jù)丟失和損毀，所有的數(shù)據(jù)需要維持原樣，且無條件競爭。這樣的數(shù)據(jù)結(jié)構(gòu)，稱之為“線程安全”的數(shù)據(jù)結(jié)構(gòu)。通常情況下，當(dāng)多個線程對數(shù)據(jù)結(jié)構(gòu)進行同一并發(fā)操作是安全的，但不同操作則需要單線程獨立訪問數(shù)據(jù)結(jié)構(gòu)?；蛳喾?，當(dāng)線程執(zhí)行不同的操作時，對同一數(shù)據(jù)結(jié)構(gòu)的并發(fā)操作是安全的，而多線程執(zhí)行同樣的操作，則會出現(xiàn)問題。

實際的設(shè)計意義并不止上面提到的那樣：這就意味著，要為線程提供并發(fā)訪問數(shù)據(jù)結(jié)構(gòu)的機會。本質(zhì)上，是使用互斥量提供互斥特性：在互斥量的保護下，同一時間內(nèi)只有一個線程可以獲取互斥鎖?；コ饬繛榱吮Ｗo數(shù)據(jù)，顯式的阻止了線程對數(shù)據(jù)結(jié)構(gòu)的并發(fā)訪問。

這被稱為序列化(serialzation)：線程輪流訪問被保護的數(shù)據(jù)。這其實是對數(shù)據(jù)進行串行的訪問，而非并發(fā)。因此，你需要對數(shù)據(jù)結(jié)構(gòu)的設(shè)計進行仔細斟酌，確保其能真正并發(fā)訪問。雖然，一些數(shù)據(jù)結(jié)構(gòu)有著比其他數(shù)據(jù)結(jié)構(gòu)多的并發(fā)訪問范圍，但是在所有情況下的思路都是一樣的：減少保護區(qū)域，減少序列化操作，就能提升并發(fā)訪問的潛力。

在我們進行數(shù)據(jù)結(jié)構(gòu)的設(shè)計之前，讓我們快速的瀏覽一下，在并發(fā)設(shè)計中的指導(dǎo)建議。

6.1.1 數(shù)據(jù)結(jié)構(gòu)并發(fā)設(shè)計的指導(dǎo)與建議(指南)

如之前提到的，當(dāng)設(shè)計并發(fā)數(shù)據(jù)結(jié)構(gòu)時，有兩方面需要考量：一是確保訪問是安全的，二是能真正的并發(fā)訪問。在第3章的時候，已經(jīng)對如何保證數(shù)據(jù)結(jié)構(gòu)是線程安全的做過簡單的描述：

• 確保無線程能夠看到，數(shù)據(jù)結(jié)構(gòu)的“不變量”破壞時的狀態(tài)。

• 小心那些會引起條件競爭的接口，提供完整操作的函數(shù)，而非操作步驟。

• 注意數(shù)據(jù)結(jié)構(gòu)的行為是否會產(chǎn)生異常，從而確?！安蛔兞俊钡臓顟B(tài)穩(wěn)定。

• 將死鎖的概率降到最低。使用數(shù)據(jù)結(jié)構(gòu)時，需要限制鎖的范圍，且避免嵌套鎖的存在。

在你思考設(shè)計細節(jié)前，你還需要考慮這個數(shù)據(jù)結(jié)構(gòu)對于使用者來說有什么限制；當(dāng)一個線程通過一個特殊的函數(shù)對數(shù)據(jù)結(jié)構(gòu)進行訪問時，那么還有哪些函數(shù)能被其他的線程安全調(diào)用呢？

這是一個很重要的問題，普通的構(gòu)造函數(shù)和析構(gòu)函數(shù)需要獨立訪問數(shù)據(jù)結(jié)構(gòu)，所以用戶在使用的時候，就不能在構(gòu)造函數(shù)完成前，或析構(gòu)函數(shù)完成后對數(shù)據(jù)結(jié)構(gòu)進行訪問。當(dāng)數(shù)據(jù)結(jié)構(gòu)支持賦值操作，swap()，或拷貝構(gòu)造時，作為數(shù)據(jù)結(jié)構(gòu)的設(shè)計者，即使數(shù)據(jù)結(jié)構(gòu)中有大量的函數(shù)被線程所操縱時，你也需要保證這些操作在并發(fā)環(huán)境下是安全的(或確保這些操作能夠獨立訪問)，以保證并發(fā)訪問時不會出現(xiàn)錯誤。

第二個方面是，確保真正的并發(fā)訪問。這里沒法提供更多的指導(dǎo)意見；不過，作為一個數(shù)據(jù)結(jié)構(gòu)的設(shè)計者，在設(shè)計數(shù)據(jù)結(jié)構(gòu)時，自行考慮以下問題：

• 鎖的范圍中的操作，是否允許在鎖外執(zhí)行？

• 數(shù)據(jù)結(jié)構(gòu)中不同的區(qū)域是否能被不同的互斥量所保護？

• 所有操作都需要同級互斥量保護嗎？

• 能否對數(shù)據(jù)結(jié)構(gòu)進行簡單的修改，以增加并發(fā)訪問的概率，且不影響操作語義？

這些問題都源于一個指導(dǎo)思想：如何讓序列化訪問最小化，讓真實并發(fā)最大化？允許線程并發(fā)讀取的數(shù)據(jù)結(jié)構(gòu)并不少見，而對數(shù)據(jù)結(jié)構(gòu)的修改，必須是單線程獨立訪問。這種結(jié)構(gòu)，類似于boost::shared_mutex。同樣的，這種數(shù)據(jù)結(jié)構(gòu)也很常見——支持在多線程執(zhí)行不同的操作時，并序列化執(zhí)行相同的操作的線程(你很快就能看到)。

最簡單的線程安全結(jié)構(gòu)，通常使用的是互斥量和鎖，對數(shù)據(jù)進行保護。雖然，這么做還是有問題（如同在第3中提到的那樣），不過這樣相對簡單，且保證只有一個線程在同一時間對數(shù)據(jù)結(jié)構(gòu)進行一次訪問。為了讓你輕松的設(shè)計線程安全的數(shù)據(jù)結(jié)構(gòu)，接下來了解一下基于鎖的數(shù)據(jù)結(jié)構(gòu)，以及第7章將提到的無鎖并發(fā)數(shù)據(jù)結(jié)構(gòu)的設(shè)計。