棧和隊(duì)列都很簡(jiǎn)單：接口相對(duì)固定，并且它們應(yīng)用于比較特殊的情況。并不是所有數(shù)據(jù)結(jié)構(gòu)都像它們一樣簡(jiǎn)單；大多數(shù)數(shù)據(jù)結(jié)構(gòu)支持更加多樣化的操作。原則上，這將增大并行的可能性，但是也讓對(duì)數(shù)據(jù)保護(hù)變得更加困難，因?yàn)橐紤]對(duì)所有能訪問(wèn)到的部分。當(dāng)為了并發(fā)訪問(wèn)對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行設(shè)計(jì)時(shí)，這一系列原有的操作，就變得越發(fā)重要，需要重點(diǎn)處理。
先來(lái)看看，在查詢表的設(shè)計(jì)中，所遇到的一些問(wèn)題。
查詢表或字典是一種類型的值(鍵值)和另一種類型的值進(jìn)行關(guān)聯(lián)(映射的方式)。一般情況下，這樣的結(jié)構(gòu)允許代碼通過(guò)鍵值對(duì)相關(guān)的數(shù)據(jù)值進(jìn)行查詢。在C++標(biāo)準(zhǔn)庫(kù)中，這種相關(guān)工具有：std::map<>, std::multimap<>, std::unordered_map<>以及std::unordered_multimap<>。
查詢表的使用與棧和隊(duì)列不同。棧和隊(duì)列上，幾乎每個(gè)操作都會(huì)對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行修改，不是添加一個(gè)元素，就是刪除一個(gè)，而對(duì)于查詢表來(lái)說(shuō)，幾乎不需要什么修改。清單3.13中有個(gè)例子，是一個(gè)簡(jiǎn)單的域名系統(tǒng)(DNS)緩存，其特點(diǎn)是，相較于std::map<>削減了很多的接口。和隊(duì)列和棧一樣，標(biāo)準(zhǔn)容器的接口不適合多線程進(jìn)行并發(fā)訪問(wèn)，因?yàn)檫@些接口在設(shè)計(jì)的時(shí)候都存在固有的條件競(jìng)爭(zhēng)，所以這些接口需要砍掉，以及重新修訂。
并發(fā)訪問(wèn)時(shí)，std::map<>接口最大的問(wèn)題在于——迭代器。雖然，在多線程訪問(wèn)(或修改)容器時(shí)，可能會(huì)有提供安全訪問(wèn)的迭代器，但這就問(wèn)題棘手之處。要想正確的處理迭代器，你可能會(huì)碰到下面這個(gè)問(wèn)題：當(dāng)?shù)饕玫脑乇黄渌€程刪除時(shí)，迭代器在這里就是個(gè)問(wèn)題了。線程安全的查詢表，第一次接口削減，需要繞過(guò)迭代器。std::map<>(以及標(biāo)準(zhǔn)庫(kù)中其他相關(guān)容器)給定的接口對(duì)于迭代器的依賴是很嚴(yán)重的，其中有些接口需要先放在一邊，先對(duì)一些簡(jiǎn)單接口進(jìn)行設(shè)計(jì)。
查詢表的基本操作有：
添加一對(duì)“鍵值-數(shù)據(jù)”
修改指定鍵值所對(duì)應(yīng)的數(shù)據(jù)
刪除一組值
容器也有一些操作是非常有用的，比如：查詢?nèi)萜魇欠駷榭?，鍵值列表的完整快照和“鍵值-數(shù)據(jù)”的完整快照。
如果你堅(jiān)持之前的線程安全指導(dǎo)意見(jiàn)，例如：不要返回一個(gè)引用，并且用一個(gè)簡(jiǎn)單的互斥鎖對(duì)每一個(gè)成員函數(shù)進(jìn)行上鎖，以確保每一個(gè)函數(shù)線程安全。最有可能的條件競(jìng)爭(zhēng)在于，當(dāng)一對(duì)“鍵值-數(shù)據(jù)”加入時(shí)；當(dāng)兩個(gè)線程都添加一個(gè)數(shù)據(jù)，那么肯定一個(gè)先一個(gè)后。一種方式是合并“添加”和“修改”操作，為一個(gè)成員函數(shù)，就像清單3.13對(duì)域名系統(tǒng)緩存所做的那樣。
從接口角度看，有一個(gè)問(wèn)題很是有趣，那就是任意(if any)部分獲取相關(guān)數(shù)據(jù)。一種選擇是允許用戶提供一個(gè)“默認(rèn)”值，在鍵值沒(méi)有對(duì)應(yīng)值的時(shí)候進(jìn)行返回：
mapped_type get_value(key_type const& key, mapped_type default_value);在種情況下，當(dāng)default_value沒(méi)有明確的給出時(shí)，默認(rèn)構(gòu)造出的mapped_type實(shí)例將被使用。也可以擴(kuò)展成返回一個(gè)std::pair<mapped_type, bool>來(lái)代替mapped_type實(shí)例，其中bool代表返回值是否是當(dāng)前鍵對(duì)應(yīng)的值。另一個(gè)選擇是，返回一個(gè)有指向數(shù)據(jù)的智能指針；當(dāng)指針的值是NULL時(shí)，那么這個(gè)鍵值就沒(méi)有對(duì)應(yīng)的數(shù)據(jù)。
如我們之前所提到的，當(dāng)接口確定時(shí)，那么(假設(shè)沒(méi)有接口間的條件競(jìng)爭(zhēng))就需要保證線程安全了，可以通過(guò)對(duì)每一個(gè)成員函數(shù)使用一個(gè)互斥量和一個(gè)簡(jiǎn)單的鎖，來(lái)保護(hù)底層數(shù)據(jù)。不過(guò)，當(dāng)獨(dú)立的函數(shù)對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行讀取和修改時(shí)，就會(huì)降低并發(fā)的可能性。一個(gè)選擇是使用一個(gè)互斥量去面對(duì)多個(gè)讀者線程，或一個(gè)作者線程，如同在清單3.13中對(duì)boost::shared_mutex的使用一樣。雖然，這將提高并發(fā)訪問(wèn)的可能性，但是在同一時(shí)間內(nèi)，也只有一個(gè)線程能對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行修改。理想很美好，現(xiàn)實(shí)很骨感？我們應(yīng)該能做的更好！
為細(xì)粒度鎖設(shè)計(jì)一個(gè)映射結(jié)構(gòu)
在對(duì)隊(duì)列的討論中(在6.2.3節(jié))，為了允許細(xì)粒度鎖能正常工作，需要對(duì)于數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)進(jìn)行仔細(xì)的考慮，而非直接使用已存在的容器，例如std::map<>。這里列出三個(gè)常見(jiàn)關(guān)聯(lián)容器的方式：
二叉樹(shù)，比如：紅黑樹(shù)
有序數(shù)組
二叉樹(shù)的方式，不會(huì)對(duì)提高并發(fā)訪問(wèn)的概率；每一個(gè)查找或者修改操作都需要訪問(wèn)根節(jié)點(diǎn)，因此，根節(jié)點(diǎn)需要上鎖。雖然，訪問(wèn)線程在向下移動(dòng)時(shí)，這個(gè)鎖可以進(jìn)行釋放，但相比橫跨整個(gè)數(shù)據(jù)結(jié)構(gòu)的單鎖，并沒(méi)有什么優(yōu)勢(shì)。
有序數(shù)組是最壞的選擇，因?yàn)槟銦o(wú)法提前言明數(shù)組中哪段是有序的，所以你需要用一個(gè)鎖將整個(gè)數(shù)組鎖起來(lái)。
那么就剩哈希表了。假設(shè)有固定數(shù)量的桶，每個(gè)桶都有一個(gè)鍵值(關(guān)鍵特性)，以及散列函數(shù)。這就意味著你可以安全的對(duì)每個(gè)桶上鎖。當(dāng)你再次使用互斥量(支持多讀者單作者)時(shí)，你就能將并發(fā)訪問(wèn)的可能性增加N倍，這里N是桶的數(shù)量。當(dāng)然，缺點(diǎn)也是有的：對(duì)于鍵值的操作，需要有合適的函數(shù)。C++標(biāo)準(zhǔn)庫(kù)提供std::hash<>模板，可以直接使用。對(duì)于特化的類型，比如int，以及通用庫(kù)類型std::string，并且用戶可以簡(jiǎn)單的對(duì)鍵值類型進(jìn)行特化。如果你去效仿標(biāo)準(zhǔn)無(wú)序容器，并且獲取函數(shù)對(duì)象的類型作為哈希表的模板參數(shù)，用戶可以選擇是否特化std::hash<>的鍵值類型，或者提供一個(gè)獨(dú)立的哈希函數(shù)。
那么，讓我們來(lái)看一些代碼吧。怎樣的實(shí)現(xiàn)才能完成一個(gè)線程安全的查詢表？下面就是一種方式。
清單6.11 線程安全的查詢表
template<typename Key,typename Value,typename Hash=std::hash<Key> >
class threadsafe_lookup_table
{
private:
class bucket_type
{
private:
typedef std::pair<Key,Value> bucket_value;
typedef std::list<bucket_value> bucket_data;
typedef typename bucket_data::iterator bucket_iterator;
bucket_data data;
mutable boost::shared_mutex mutex; // 1
bucket_iterator find_entry_for(Key const& key) const // 2
{
return std::find_if(data.begin(),data.end(),
[&](bucket_value const& item)
{return item.first==key;});
}
public:
Value value_for(Key const& key,Value const& default_value) const
{
boost::shared_lock<boost::shared_mutex> lock(mutex); // 3
bucket_iterator const found_entry=find_entry_for(key);
return (found_entry==data.end())?
default_value:found_entry->second;
}
void add_or_update_mapping(Key const& key,Value const& value)
{
std::unique_lock<boost::shared_mutex> lock(mutex); // 4
bucket_iterator const found_entry=find_entry_for(key);
if(found_entry==data.end())
{
data.push_back(bucket_value(key,value));
}
else
{
found_entry->second=value;
}
}
void remove_mapping(Key const& key)
{
std::unique_lock<boost::shared_mutex> lock(mutex); // 5
bucket_iterator const found_entry=find_entry_for(key);
if(found_entry!=data.end())
{
data.erase(found_entry);
}
}
};
std::vector<std::unique_ptr<bucket_type> > buckets; // 6
Hash hasher;
bucket_type& get_bucket(Key const& key) const // 7
{
std::size_t const bucket_index=hasher(key)%buckets.size();
return *buckets[bucket_index];
}
public:
typedef Key key_type;
typedef Value mapped_type;
typedef Hash hash_type;
threadsafe_lookup_table(
unsigned num_buckets=19,Hash const& hasher_=Hash()):
buckets(num_buckets),hasher(hasher_)
{
for(unsigned i=0;i<num_buckets;++i)
{
buckets[i].reset(new bucket_type);
}
}
threadsafe_lookup_table(threadsafe_lookup_table const& other)=delete;
threadsafe_lookup_table& operator=(
threadsafe_lookup_table const& other)=delete;
Value value_for(Key const& key,
Value const& default_value=Value()) const
{
return get_bucket(key).value_for(key,default_value); // 8
}
void add_or_update_mapping(Key const& key,Value const& value)
{
get_bucket(key).add_or_update_mapping(key,value); // 9
}
void remove_mapping(Key const& key)
{
get_bucket(key).remove_mapping(key); // 10
}
};這個(gè)實(shí)現(xiàn)中使用了std::vector<std::unique_ptr<bucket_type>>⑥來(lái)保存桶，其允許在構(gòu)造函數(shù)中指定構(gòu)造桶的數(shù)量。默認(rèn)為19個(gè)，其是一個(gè)任意的質(zhì)數(shù);哈希表在有質(zhì)數(shù)個(gè)桶時(shí)，工作效率最高。每一個(gè)桶都會(huì)被一個(gè)boost::shared_mutex①實(shí)例鎖保護(hù)，來(lái)允許并發(fā)讀取，或?qū)γ恳粋€(gè)桶，只有一個(gè)線程對(duì)其進(jìn)行修改。
因?yàn)橥暗臄?shù)量是固定的，所以get_bucket()⑦可以無(wú)鎖調(diào)用，⑧⑨⑩也都一樣。并且對(duì)桶的互斥量上鎖，要不就是共享(只讀)所有權(quán)的時(shí)候③，要不就是在獲取唯一(讀/寫)權(quán)的時(shí)候④⑤。這里的互斥量，可適用于每個(gè)成員函數(shù)。
這三個(gè)函數(shù)都使用到了find_entry_for()成員函數(shù)②，在桶上用來(lái)確定數(shù)據(jù)是否在桶中。每一個(gè)桶都包含一個(gè)“鍵值-數(shù)據(jù)”的std::list<>列表，所以添加和刪除數(shù)據(jù)，就會(huì)很簡(jiǎn)單。
已經(jīng)從并發(fā)的角度考慮了，并且所有成員都會(huì)被互斥鎖保護(hù)，所以這樣的實(shí)現(xiàn)就是“異常安全”的嗎？value_for是不能修改任何值的，所以其不會(huì)有問(wèn)題；如果value_for拋出異常，也不會(huì)對(duì)數(shù)據(jù)結(jié)構(gòu)有任何影響。remove_mapping修改鏈表時(shí)，將會(huì)調(diào)用erase，不過(guò)這就能保證沒(méi)有異常拋出，那么這里也是安全的。那么就剩add_or_update_mapping了，其可能會(huì)在其兩個(gè)if分支上拋出異常。push_back是異常安全的，如果有異常拋出，其也會(huì)將鏈表恢復(fù)成原來(lái)的狀態(tài)，所以這個(gè)分支是沒(méi)有問(wèn)題的。唯一的問(wèn)題就是在賦值階段，這將替換已有的數(shù)據(jù)；當(dāng)復(fù)制階段拋出異常，用于原依賴的始狀態(tài)沒(méi)有改變。不過(guò)，這不會(huì)影響數(shù)據(jù)結(jié)構(gòu)的整體，以及用戶提供類型的屬性，所以你可以放心的將問(wèn)題交給用戶處理。
在本節(jié)開(kāi)始時(shí)，我提到查詢表的一個(gè)可有可無(wú)(nice-to-have)的特性，會(huì)將選擇當(dāng)前狀態(tài)的快照，例如，一個(gè)std::map<>。這將要求鎖住整個(gè)容器，用來(lái)保證拷貝副本的狀態(tài)是可以索引的，這將要求鎖住所有的桶。因?yàn)閷?duì)于查詢表的“普通”的操作，需要在同一時(shí)間獲取一個(gè)桶上的一個(gè)鎖，而這個(gè)操作將要求查詢表將所有桶都鎖住。因此，只要每次以相同的順序進(jìn)行上鎖(例如，遞增桶的索引值)，就不會(huì)產(chǎn)生死鎖。實(shí)現(xiàn)如下所示：
清單6.12 獲取整個(gè)threadsafe_lookup_table作為一個(gè)std::map<>
std::map<Key,Value> threadsafe_lookup_table::get_map() const
{
std::vector<std::unique_lock<boost::shared_mutex> > locks;
for(unsigned i=0;i<buckets.size();++i)
{
locks.push_back(
std::unique_lock<boost::shared_mutex>(buckets[i].mutex));
}
std::map<Key,Value> res;
for(unsigned i=0;i<buckets.size();++i)
{
for(bucket_iterator it=buckets[i].data.begin();
it!=buckets[i].data.end();
++it)
{
res.insert(*it);
}
}
return res;
}清單6.11中的查詢表實(shí)現(xiàn)，就增大的并發(fā)訪問(wèn)的可能性，這個(gè)查詢表作為一個(gè)整體，通過(guò)單獨(dú)的操作，對(duì)每一個(gè)桶進(jìn)行鎖定，并且通過(guò)使用boost::shared_mutex允許讀者線程對(duì)每一個(gè)桶進(jìn)行并發(fā)訪問(wèn)。如果細(xì)粒度鎖和哈希表結(jié)合起來(lái)，會(huì)更有效的增加并發(fā)的可能性嗎？
在下一節(jié)中，你將使用到一個(gè)線程安全列表(支持迭代器)。
鏈表類型是數(shù)據(jù)結(jié)構(gòu)中的一個(gè)基本類型，所以應(yīng)該是比較好修改成線程安全的，對(duì)么？其實(shí)這取決于你要添加什么樣的功能，這其中需要你提供迭代器的支持。為了讓基本數(shù)據(jù)類型的代碼不會(huì)太復(fù)雜，我去掉了一些功能。迭代器的問(wèn)題在于，STL類的迭代器需要持有容器內(nèi)部屬于的引用。當(dāng)容器可被其他線程修改時(shí)，有時(shí)這個(gè)引用還是有效的；實(shí)際上，這里就需要迭代器持有鎖，對(duì)指定的結(jié)構(gòu)中的部分進(jìn)行上鎖。在給定STL類迭代器的生命周期中，讓其完全脫離容器的控制是很糟糕的。
替代方案就是提供迭代函數(shù)，例如，將for_each作為容器本身的一部分。這就能讓容器來(lái)對(duì)迭代的部分進(jìn)行負(fù)責(zé)和鎖定，不過(guò)這將違反第3章指導(dǎo)意見(jiàn)對(duì)避免死鎖建議。為了讓for_each在任何情況下都有用，在其持有內(nèi)部鎖的時(shí)候，必須調(diào)用用戶提供的代碼。不僅如此，而且需要傳遞一個(gè)對(duì)容器中元素的引用到用戶代碼中，為的就是讓用戶代碼對(duì)容器中的元素進(jìn)行操作。你可以為了避免傳遞引用，而傳出一個(gè)拷貝到用戶代碼中；不過(guò)當(dāng)數(shù)據(jù)很大時(shí)，拷貝所要付出的代價(jià)也很大。
所以，可以將避免死鎖的工作(因?yàn)橛脩籼峁┑牟僮餍枰@取內(nèi)部鎖)，還有避免對(duì)引用(不被鎖保護(hù))進(jìn)行存儲(chǔ)時(shí)的條件競(jìng)爭(zhēng)，交給用戶去做。這樣的鏈表就可以被查詢表所使用了，這樣很安全，因?yàn)槟阒肋@里的實(shí)現(xiàn)不會(huì)有任何問(wèn)題。
那么剩下的問(wèn)題就是哪些操作需要列表所提供。如果你愿在花點(diǎn)時(shí)間看一下清單6.11和6.12中的代碼，你會(huì)看到下面這些操作是需要的：
向列表添加一個(gè)元素
當(dāng)某個(gè)條件滿足時(shí)，就從鏈表中刪除某個(gè)元素
當(dāng)某個(gè)條件滿足時(shí)，從鏈表中查找某個(gè)元素
當(dāng)某個(gè)條件滿足時(shí)，更新鏈表中的某個(gè)元素
提供了這些操作，我們的鏈表才能是一個(gè)比較好的通用容器，這將幫助我們添加更多功能，比如，在指定位置上插入元素，不過(guò)這對(duì)于我們查詢表來(lái)說(shuō)就沒(méi)有必要了，所以這里就算是給讀者們留的一個(gè)作業(yè)吧。
使用細(xì)粒度鎖最初的想法，是為了讓鏈表每個(gè)節(jié)點(diǎn)都擁有一個(gè)互斥量。當(dāng)鏈表很長(zhǎng)時(shí)，那么就會(huì)有很多的互斥量!這樣的好處是對(duì)于鏈表中每一個(gè)獨(dú)立的部分，都能實(shí)現(xiàn)真實(shí)的并發(fā)：其真正感興趣的是對(duì)持有的節(jié)點(diǎn)群進(jìn)行上鎖，并且在移動(dòng)到下一個(gè)節(jié)點(diǎn)的時(shí)，對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行釋放。下面的清單中將展示這樣的一個(gè)鏈表實(shí)現(xiàn)。
清單6.13 線程安全鏈表——支持迭代器
template<typename T>
class threadsafe_list
{
struct node // 1
{
std::mutex m;
std::shared_ptr<T> data;
std::unique_ptr<node> next;
node(): // 2
next()
{}
node(T const& value): // 3
data(std::make_shared<T>(value))
{}
};
node head;
public:
threadsafe_list()
{}
~threadsafe_list()
{
remove_if([](node const&){return true;});
}
threadsafe_list(threadsafe_list const& other)=delete;
threadsafe_list& operator=(threadsafe_list const& other)=delete;
void push_front(T const& value)
{
std::unique_ptr<node> new_node(new node(value)); // 4
std::lock_guard<std::mutex> lk(head.m);
new_node->next=std::move(head.next); // 5
head.next=std::move(new_node); // 6
}
template<typename Function>
void for_each(Function f) // 7
{
node* current=&head;
std::unique_lock<std::mutex> lk(head.m); // 8
while(node* const next=current->next.get()) // 9
{
std::unique_lock<std::mutex> next_lk(next->m); // 10
lk.unlock(); // 11
f(*next->data); // 12
current=next;
lk=std::move(next_lk); // 13
}
}
template<typename Predicate>
std::shared_ptr<T> find_first_if(Predicate p) // 14
{
node* current=&head;
std::unique_lock<std::mutex> lk(head.m);
while(node* const next=current->next.get())
{
std::unique_lock<std::mutex> next_lk(next->m);
lk.unlock();
if(p(*next->data)) // 15
{
return next->data; // 16
}
current=next;
lk=std::move(next_lk);
}
return std::shared_ptr<T>();
}
template<typename Predicate>
void remove_if(Predicate p) // 17
{
node* current=&head;
std::unique_lock<std::mutex> lk(head.m);
while(node* const next=current->next.get())
{
std::unique_lock<std::mutex> next_lk(next->m);
if(p(*next->data)) // 18
{
std::unique_ptr<node> old_next=std::move(current->next);
current->next=std::move(next->next);
next_lk.unlock();
} // 20
else
{
lk.unlock(); // 21
current=next;
lk=std::move(next_lk);
}
}
}
};清單6.13中的threadsafe_list<>是一個(gè)單鏈表，可從node的結(jié)構(gòu)①中看出。一個(gè)默認(rèn)構(gòu)造的node，作為鏈表的head，其next指針②指向的是NULL。新節(jié)點(diǎn)都是被push_front()函數(shù)添加進(jìn)去的；構(gòu)造第一個(gè)新節(jié)點(diǎn)④，其將會(huì)在堆上分配內(nèi)存③來(lái)對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)，同時(shí)將next指針置為NULL。然后，你需要獲取head節(jié)點(diǎn)的互斥鎖，為了讓設(shè)置next的值⑤，也就是插入節(jié)點(diǎn)到列表的頭部，讓頭節(jié)點(diǎn)的head.next指向這個(gè)新節(jié)點(diǎn)⑥。目前，還沒(méi)有什么問(wèn)題：你只需要鎖住一個(gè)互斥量，就能將一個(gè)新的數(shù)據(jù)添加進(jìn)入鏈表，所以這里不存在死鎖的問(wèn)題。同樣，(緩慢的)內(nèi)存分配操作在鎖的范圍外，所以鎖能保護(hù)需要更新的一對(duì)指針。那么，現(xiàn)在來(lái)看一下迭代功能。
首先，來(lái)看一下for_each()⑦。這個(gè)操作需要對(duì)隊(duì)列中的每個(gè)元素執(zhí)行Function(函數(shù)指針)；在大多數(shù)標(biāo)準(zhǔn)算法庫(kù)中，都會(huì)通過(guò)傳值方式來(lái)執(zhí)行這個(gè)函數(shù)，這里要不就傳入一個(gè)通用的函數(shù)，要不就傳入一個(gè)有函數(shù)操作的類型對(duì)象。在這種情況下，這個(gè)函數(shù)必須接受類型為T的值作為參數(shù)。在鏈表中，會(huì)有一個(gè)“手遞手”的上鎖過(guò)程。在這個(gè)過(guò)程開(kāi)始時(shí)，你需要鎖住head及節(jié)點(diǎn)⑧的互斥量。然后，安全的獲取指向下一個(gè)節(jié)點(diǎn)的指針(使用get()獲取，這是因?yàn)槟銓?duì)這個(gè)指針沒(méi)有所有權(quán))。當(dāng)指針不為NULL⑨，為了繼續(xù)對(duì)數(shù)據(jù)進(jìn)行處理，就需要對(duì)指向的節(jié)點(diǎn)進(jìn)行上鎖⑩。當(dāng)你已經(jīng)鎖住了那個(gè)節(jié)點(diǎn)，就可以對(duì)上一個(gè)節(jié)點(diǎn)進(jìn)行釋放了?，并且調(diào)用指定函數(shù)?。當(dāng)函數(shù)執(zhí)行完成時(shí)，你就可以更新當(dāng)前指針?biāo)赶虻墓?jié)點(diǎn)(剛剛處理過(guò)的節(jié)點(diǎn))，并且將所有權(quán)從next_lk移動(dòng)移動(dòng)到lk?。因?yàn)閒or_each傳遞的每個(gè)數(shù)據(jù)都是能被Function接受的，所以當(dāng)需要的時(shí)，需要拷貝到另一個(gè)容器的時(shí)，或其他情況時(shí)，你都可以考慮使用這種方式更新每個(gè)元素。如果函數(shù)的行為沒(méi)什么問(wèn)題，這種方式是完全安全的，因?yàn)樵讷@取節(jié)點(diǎn)互斥鎖時(shí)，已經(jīng)獲取鎖的節(jié)點(diǎn)正在被函數(shù)所處理。
find_first_if()?和for_each()很相似；最大的區(qū)別在于find_first_if支持函數(shù)(謂詞)在匹配的時(shí)候返回true，在不匹配的時(shí)候返回false?。當(dāng)條件匹配，只需要返回找到的數(shù)據(jù)?，而非繼續(xù)查找。你可以使用for_each()來(lái)做這件事，不過(guò)在找到之后，繼續(xù)做查找就是沒(méi)有意義的了。
remove_if()?就有些不同了，因?yàn)檫@個(gè)函數(shù)會(huì)改變鏈表；所以，你就不能使用for_each()來(lái)實(shí)現(xiàn)這個(gè)功能。當(dāng)函數(shù)(謂詞)返回true?，對(duì)應(yīng)元素將會(huì)移除，并且更新current->next?。當(dāng)這些都做完，你就可以釋放next指向節(jié)點(diǎn)的鎖。當(dāng)std::unique_ptr<node>的移動(dòng)超出鏈表范圍?，這個(gè)節(jié)點(diǎn)將被刪除。這種情況下，你就不需要更新當(dāng)前節(jié)點(diǎn)了，因?yàn)槟阒恍枰薷膎ext所指向的下一個(gè)節(jié)點(diǎn)就可以。當(dāng)函數(shù)(謂詞)返回false，那么移動(dòng)的操作就和之前一樣了(21)。
那么，所有的互斥量中會(huì)有死鎖或條件競(jìng)爭(zhēng)嗎？答案無(wú)疑是“否”，這里要看提供的函數(shù)(謂詞)是否有良好的行為。迭代通常都是使用一種方式，都是從head節(jié)點(diǎn)開(kāi)始，并且在釋放當(dāng)前節(jié)點(diǎn)鎖之前，將下一個(gè)節(jié)點(diǎn)的互斥量鎖住，所以這里就不可能會(huì)有不同線程有不同的上鎖順序。唯一可能出現(xiàn)條件競(jìng)爭(zhēng)的地方就是在remove_if()?中刪除已有節(jié)點(diǎn)的時(shí)候。因?yàn)?，這個(gè)操作在解鎖互斥量后進(jìn)行(其導(dǎo)致的未定義行為，可對(duì)已上鎖的互斥量進(jìn)行破壞)。不過(guò)，在考慮一陣后，可以確定這的確是安全的，因?yàn)槟氵€持有前一個(gè)節(jié)點(diǎn)(當(dāng)前節(jié)點(diǎn))的互斥鎖，所以不會(huì)有新的線程嘗試去獲取你正在刪除的那個(gè)節(jié)點(diǎn)的互斥鎖。
這里并發(fā)概率有多大呢？細(xì)粒度鎖要比單鎖的并發(fā)概率大很多，那我們已經(jīng)獲得了嗎？是的，你已經(jīng)獲取了：同一時(shí)間內(nèi)，不同線程可以在不同節(jié)點(diǎn)上工作，無(wú)論是其使用for_each()對(duì)每一個(gè)節(jié)點(diǎn)進(jìn)行處理，使用find_first_if()對(duì)數(shù)據(jù)進(jìn)行查找，還是使用remove_if()刪除一些元素。不過(guò)，因?yàn)榛コ饬勘仨毎错樞蛏湘i，那么線程就不能交叉進(jìn)行工作。當(dāng)一個(gè)線程耗費(fèi)大量的時(shí)間對(duì)一個(gè)特殊節(jié)點(diǎn)進(jìn)行處理，那么其他線程就必須等待這個(gè)處理完成。在完成后，其他線程才能到達(dá)這個(gè)節(jié)點(diǎn)。
掃碼關(guān)注鍍金池微信號(hào)
手機(jī)訂課，優(yōu)惠多多