对STL容器的安全并行只读访问 [英] Safe parallel read-only access to a STL container
问题描述
我想从并行运行的线程访问基于STL的容器只读。不使用任何用户实现的锁定。以下代码的基础是C ++ 11，并且标准的正确实现。
http://gcc.gnu.org/onlinedocs/libstdc++/manual/using_concurrency.html
http://www.sgi.com/tech/stl/thread_safety.html
http://www.hpl.hp.com/personal/Hans_Boehm/c++mm/threadsintro.html
http://www.open-std.org/jtc1/sc22/wg21 / （当前草稿或 N3337 ，它本质上是C ++ 11，具有小错误和错误纠正）
23.2.2容器数据竞争[container.requirements.dataraces]
为了避免数据竞争（17.6.5.9），实现将
考虑以下函数为const：begin，end，rbegin，
rend，front，back，data，find，lower_bound，upper_bound ，equal_range，
at and，except in associative or unordered associative containers，
operator []。
尽管（17.6.5.9）当
中除了向量< bool>之外的同一序列中的不同元素的内容同时被
修改时，需要
以避免数据竞争。
[注意：对于向量< int> x的大小比
大，x [1] = 5和* x.begin（）= 10可以同时执行
没有数据竞争，但x [0] = 5和* x .begin（）= 10执行
并发可能导致数据竞争。作为一般的
规则的例外，对于向量< bool> y，y [0] = true可能与y [1]竞争
= true。 - end note]
和
17.6.5.9数据竞争避免[res.on.data.races] 1本节指定实现应满足以防止数据
竞争（1.10）的要求。除非另有规定，每个标准库函数都应满足每个
的要求。实现可以防止在以下指定的以外的情况下的
数据竞争。
2 C ++标准
库函数不应直接或间接访问对象
（1.10）可以通过当前线程之外的线程访问，除非
对象直接或间接通过函数的
参数访问，包括这个。
3 C ++标准库函数
不能直接或间接修改当前线程以外的线程
访问的对象（1.10），除非直接访问对象
或间接通过函数的非const参数，包括
this。
4 [注意：这意味着，例如，实现不能
使用静态对象用于内部目的而没有同步
，因为它可能导致数据竞争，甚至在不
的程序中，在线程之间显式地共享对象。 - end note]
5 C ++标准库函数不能间接访问对象
通过其参数或通过其容器的元素可访问
参数，通过调用这些容器元素上的规范
所需的函数。
6通过
获得的迭代器上的操作调用标准库容器或字符串成员函数可以
访问底层容器，但不得修改它。 [注意：在
中，使迭代器无效的容器操作会冲突
，并对与该容器相关联的迭代器执行操作。 - end
note]
7如果对象对用户不可见并受到保护，实现可以在
线程之间共享自己的内部对象$ b
8除非另有说明，否则C ++标准库
函数必须在当前
线程内执行所有操作，如果这些操作具有可见（1.10）到
用户的效果。
9 [注意：这允许实现并行操作
效果。 - end note]
结论
容器不是线程安全的！但是从多个并行线程调用 const函数是安全的。因此，可以在不锁定的情况下，从并行线程执行只读操作。
我是对的吗？
我假设他们不存在任何错误的实现，并且每个C ++ 11标准的实现都是正确的。
示例：
//并发线程访问stl容器
// g ++ -std = gnu ++ 11 -o p_read p_read.cpp -pthread -Wall -pedantic&& ./p_read
#include< iostream>
#include< iomanip>
#include< string>
#include< unistd.h>
#include< thread>
#include< mutex>
#include< map>
#include< cstdlib>
#include< ctime>
using namespace std;
// new in C ++ 11
使用str_map = map< string，string> ;;
//线程在C ++中是新的11
// to_string（）在C ++中是新的11
mutex m;
const unsigned int MAP_SIZE = 10000;
void fill_map（str_map& store）{
int key_nr;
string mapped_value;
string key;
while（store.size（）< MAP_SIZE）{
// 0 - 9999
key_nr = rand（）％MAP_SIZE;
//将数字转换为字符串
mapped_value = to_string（key_nr）;
key =key_+ mapped_value;
pair< string，string> value（key，mapped_value）;
store.insert（value）;
}
}
void print_map（const str_map& store）{
str_map :: const_iterator it = store.begin（）;
while（it！= store.end（））{
pair< string，string> value = * it;
cout<<左< setw（10）< value.first<<右< setw（5）<< value.second<< \\\
;
it ++;
}
}
void search_map（const str_map& store，int thread_nr）{
m.lock（）;
cout<< thread（<< thread_nr<<）launched\\\
;
m.unlock（）;
//使用直接搜索或随机抽取
bool straight = false;
if（（thread_nr％2）== 0）{
straight = true;
}
int key_nr;
string mapped_value;
string key;
str_map :: const_iterator it;
string first;
string second;
for（unsigned int i = 0; i
if（straight）{
key_nr = i;
} else {
// 0 - 9999，rand不是线程安全的，nrand48是一个替代的
m.lock（）;
key_nr = rand（）％MAP_SIZE;
m.unlock（）;
}
//将数字转换为字符串
mapped_value = to_string（key_nr）;
key =key_+ mapped_value;
it = store.find（key）;
//检查结果
if（it！= store.end（））{
// pair
first = it->
second = it-> second;
// m.lock（）;
// cout<< thread（<< thread_nr<<）<键<< ：
//<<右< setw（10）<第一< setw（5）<<第二< \\\
;
// m.unlock（）;
//检查不匹配
if（key！= first || mapped_value！= second）{
m.lock（）;
cerr<<键<< ：<<第一<第二< \\\
<< Mismatch in thread（<< thread_nr<<）！\\\
;
exit（1）;
//从未到达
m.unlock（）;
}
} else {
m.lock（）;
cerr<< 在线程中找不到警告：key（<<<<<<）（
<< thread_nr<
exit（1）;
//从未到达
m.unlock（）;
}
}
}
int main（）{
clock_t start，end;
start = clock（）;
str_map store;
srand（0）;
fill_map（store）;
cout<< fill_map finished\\\
;
// print_map（store）;
// cout<< print_map finished\\\
;
// copy for check
str_map copy_store = store;
//启动线程
thread t [10];
for（int i = 0; i <10; i ++）{
t [i] = thread（search_map，store，i）;
}
//等待完成
for（int i = 0; i <10; i ++）{
t [i] .join
}
cout<< search_map threads finished\\\
;
if（store == copy_store）{
cout<< equal\\\
;
} else {
cout<< not equal\\\
;
}
end = clock（）;
cout<< CLOCKS_PER_SEC< CLOCKS_PER_SEC<< \\\
;
cout<< CPU-TIME START<开始<< \\\
;
cout<< CPU-TIME END<<端<< \\\
;
cout<< CPU-TIME END-START< end-start<< \\\
;
cout<< TIME（SEC）< static_cast< double>（end-start）/ CLOCKS_PER_SEC< \\\
;
return 0;
}
此代码可以用 GCC 4.7 在我的机器上运行良好。
$ echo $？
$ 0
从C ++ 11规范的1.10 / 4和1.10 / 21节开始的数据竞争需要至少两个线程对同一组内存位置进行非原子访问，这两个线程不同步关于访问该组存储器位置，并且至少一个线程写入或修改存储器位置集合中的元素。所以在你的情况下，如果线程只读取，你很好...根据定义，因为没有线程写入同一组内存位置，没有数据竞争，即使没有明确的同步机制之间
I want access a STL based container read-only from parallel running threads. Without using any user implemented locking. The base of the following code is C++11 with a proper implementation of the standard.
http://gcc.gnu.org/onlinedocs/libstdc++/manual/using_concurrency.html
http://www.sgi.com/tech/stl/thread_safety.html
http://www.hpl.hp.com/personal/Hans_Boehm/c++mm/threadsintro.html
http://www.open-std.org/jtc1/sc22/wg21/ (current draft or N3337, which is essentially C++11 with minor errors and typos corrected)
23.2.2 Container data races [container.requirements.dataraces]
For purposes of avoiding data races (17.6.5.9), implementations shall consider the following functions to be const: begin, end, rbegin, rend, front, back, data, find, lower_bound, upper_bound, equal_range, at and, except in associative or unordered associative containers, operator[].
Notwithstanding (17.6.5.9), implementations are required to avoid data races when the contents of the con- tained object in different elements in the same sequence, excepting vector<bool>, are modified concurrently.
[ Note: For a vector<int> x with a size greater than one, x[1] = 5 and *x.begin() = 10 can be executed concurrently without a data race, but x[0] = 5 and *x.begin() = 10 executed concurrently may result in a data race. As an exception to the general rule, for a vector<bool> y, y[0] = true may race with y[1] = true. — end note ]
and
17.6.5.9 Data race avoidance [res.on.data.races] 1 This section specifies requirements that implementations shall meet to prevent data races (1.10). Every standard library function shall meet each requirement unless otherwise specified. Implementations may prevent data races in cases other than those specified below.
2 A C++ standard library function shall not directly or indirectly access objects (1.10) accessible by threads other than the current thread unless the objects are accessed directly or indirectly via the function’s argu- ments, including this.
3 A C++ standard library function shall not directly or indirectly modify objects (1.10) accessible by threads other than the current thread unless the objects are accessed directly or indirectly via the function’s non-const arguments, including this.
4 [ Note: This means, for example, that implementations can’t use a static object for internal purposes without synchronization because it could cause a data race even in programs that do not explicitly share objects between threads. — end note ]
5 A C++ standard library function shall not access objects indirectly accessible via its arguments or via elements of its container arguments except by invoking functions required by its specification on those container elements.
6 Operations on iterators obtained by calling a standard library container or string member function may
access the underlying container, but shall not modify it. [ Note: In particular, container operations that invalidate iterators conflict with operations on iterators associated with that container. — end note ]7 Implementations may share their own internal objects between threads if the objects are not visible to users and are protected against data races.
8 Unless otherwise specified, C++ standard library functions shall perform all operations solely within the current thread if those operations have effects that are visible (1.10) to users.
9 [ Note: This allows implementations to parallelize operations if there are no visible side effects. — end note ]
Conclusion
Containers are not thread safe! But it is safe to call const functions on containers from multiple parallel threads. So it is possible to do read-only operations from parallel threads without locking.
Am I right?
I pretend that their doesn't exist any faulty implementation and every implementation of the C++11 standard is correct.
Sample:
// concurrent thread access to a stl container
// g++ -std=gnu++11 -o p_read p_read.cpp -pthread -Wall -pedantic && ./p_read
#include <iostream>
#include <iomanip>
#include <string>
#include <unistd.h>
#include <thread>
#include <mutex>
#include <map>
#include <cstdlib>
#include <ctime>
using namespace std;
// new in C++11
using str_map = map<string, string>;
// thread is new in C++11
// to_string() is new in C++11
mutex m;
const unsigned int MAP_SIZE = 10000;
void fill_map(str_map& store) {
int key_nr;
string mapped_value;
string key;
while (store.size() < MAP_SIZE) {
// 0 - 9999
key_nr = rand() % MAP_SIZE;
// convert number to string
mapped_value = to_string(key_nr);
key = "key_" + mapped_value;
pair<string, string> value(key, mapped_value);
store.insert(value);
}
}
void print_map(const str_map& store) {
str_map::const_iterator it = store.begin();
while (it != store.end()) {
pair<string, string> value = *it;
cout << left << setw(10) << value.first << right << setw(5) << value.second << "\n";
it++;
}
}
void search_map(const str_map& store, int thread_nr) {
m.lock();
cout << "thread(" << thread_nr << ") launched\n";
m.unlock();
// use a straight search or poke around random
bool straight = false;
if ((thread_nr % 2) == 0) {
straight = true;
}
int key_nr;
string mapped_value;
string key;
str_map::const_iterator it;
string first;
string second;
for (unsigned int i = 0; i < MAP_SIZE; i++) {
if (straight) {
key_nr = i;
} else {
// 0 - 9999, rand is not thread-safe, nrand48 is an alternative
m.lock();
key_nr = rand() % MAP_SIZE;
m.unlock();
}
// convert number to string
mapped_value = to_string(key_nr);
key = "key_" + mapped_value;
it = store.find(key);
// check result
if (it != store.end()) {
// pair
first = it->first;
second = it->second;
// m.lock();
// cout << "thread(" << thread_nr << ") " << key << ": "
// << right << setw(10) << first << setw(5) << second << "\n";
// m.unlock();
// check mismatch
if (key != first || mapped_value != second) {
m.lock();
cerr << key << ": " << first << second << "\n"
<< "Mismatch in thread(" << thread_nr << ")!\n";
exit(1);
// never reached
m.unlock();
}
} else {
m.lock();
cerr << "Warning: key(" << key << ") not found in thread("
<< thread_nr << ")\n";
exit(1);
// never reached
m.unlock();
}
}
}
int main() {
clock_t start, end;
start = clock();
str_map store;
srand(0);
fill_map(store);
cout << "fill_map finished\n";
// print_map(store);
// cout << "print_map finished\n";
// copy for check
str_map copy_store = store;
// launch threads
thread t[10];
for (int i = 0; i < 10; i++) {
t[i] = thread(search_map, store, i);
}
// wait for finish
for (int i = 0; i < 10; i++) {
t[i].join();
}
cout << "search_map threads finished\n";
if (store == copy_store) {
cout << "equal\n";
} else {
cout << "not equal\n";
}
end = clock();
cout << "CLOCKS_PER_SEC " << CLOCKS_PER_SEC << "\n";
cout << "CPU-TIME START " << start << "\n";
cout << "CPU-TIME END " << end << "\n";
cout << "CPU-TIME END - START " << end - start << "\n";
cout << "TIME(SEC) " << static_cast<double>(end - start) / CLOCKS_PER_SEC << "\n";
return 0;
}
This code can be compiled with GCC 4.7 and runs fine on my machine.
$ echo $?
$ 0
A data-race, from the C++11 specification in sections 1.10/4 and 1.10/21, requires at least two threads with non-atomic access to the same set of memory locations, the two threads are not synchronized with regards to accessing the set of memory locations, and at least one thread writes to or modifies an element in the set of memory locations. So in your case, if the threads are only reading, you are fine ... by definition since none of the threads write to the same set of memory locations, there are no data-races even though there is no explicit synchronization mechanism between the threads.
这篇关于对STL容器的安全并行只读访问的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
