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

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

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

在我們進(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í)，有兩方面需要考量：一是確保訪問(wèn)是安全的，二是能真正的并發(fā)訪問(wèn)。在第3章的時(shí)候，已經(jīng)對(duì)如何保證數(shù)據(jù)結(jié)構(gòu)是線程安全的做過(guò)簡(jiǎn)單的描述：

• 確保無(wú)線程能夠看到，數(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ì)于使用者來(lái)說(shuō)有什么限制；當(dāng)一個(gè)線程通過(guò)一個(gè)特殊的函數(shù)對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行訪問(wèn)時(shí)，那么還有哪些函數(shù)能被其他的線程安全調(diào)用呢？

這是一個(gè)很重要的問(wèn)題，普通的構(gòu)造函數(shù)和析構(gòu)函數(shù)需要獨(dú)立訪問(wèn)數(shù)據(jù)結(jié)構(gòu)，所以用戶在使用的時(shí)候，就不能在構(gòu)造函數(shù)完成前，或析構(gòu)函數(shù)完成后對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行訪問(wè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ú)立訪問(wèn))，以保證并發(fā)訪問(wèn)時(shí)不會(huì)出現(xiàn)錯(cuò)誤。

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

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

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

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

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

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

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