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