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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 所有操作都需要同級(jí)互斥量保護(hù)嗎？

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

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

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