Безопасный параллельный доступ только для чтения к контейнеру STL

Question

Я хочу получить доступ к контейнеру на основе STL только для чтения от parallel идущие потоки. Без использования каких-либо пользовательских блокировок. Основой следующего кода является 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/ (current draft или 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 и, за исключением ассоциативных или неупорядоченных ассоциативных контейнеров, operator [].

Несмотря (17.6.5.9), реализации требуются , чтобы избежать гонок данных, когда содержимые Вошедший объекта в различных элементах в одной и ту же последовательности, исключая Вектор <BOOL>, являются модифицированными одновременно.

[Примечание: Для вектора <INT> х с размером больше, чем один , х = 5 и * x.begin() = 10 могут быть выполнены одновременно без гонки данных, но х [ 0] = 5 и * x.begin() = 10, выполненный , одновременно может привести к гонке данных. В качестве исключения из общего правила для вектора <bool> y, y [0] = true может участвовать в гонке с y = true. - конец примечание]

и

17.6.5.9 предотвращение гонки данных [res.on.data.races] 1 Этот раздел определяет требования, которые реализации должны отвечать, чтобы защитить данные гонки (1.10). Каждая стандартная библиотечная функция должна соответствовать каждому требованию , если не указано иное. Реализации могут предотвратить ракеты в случаях, отличных от указанных ниже.

2 C++ стандарт функции библиотеки не должны прямо или косвенно доступ к объектам (1,10) доступны, кроме текущего потока, если объекты не получают доступ прямо или косвенно через рас- смотрения работы функции, в том числе это нитками.

3 C++ стандартная библиотечная функция должна прямо или косвенно не изменять объекты (1.10), доступные нитками , кроме текущего потока, если объекты не будут доступны непосредственно или косвенно через неконстантных аргументов функции, в том числе этой ,

4 [Примечание: Это означает, что, например, реализация не может использовать статический объект для внутренних целей без синхронизации , поскольку это может вызвать гонку данных даже в программах, которые не явно разделяют объектов между потоками. - конец примечание]

5 A ++ функции стандартной библиотеки C не должны получать доступ к объектам косвенно доступными через свои аргументы или через элементы контейнера аргументов кроме вызова функций, требуемых его спецификации на этих элементов контейнера.

6 Операции по итераторам получает вызов стандартной библиотеки контейнера или член строки функции может
доступа основного контейнера, но не изменяет его. [Примечание. В разделе конкретные операции с контейнерами, которые недействительны итераторам, конфликтуют с с операциями с итераторами, связанными с этим контейнером. - конец примечание]

7 Реализации могут делиться своими внутренними объектами между нитями, если объекты не видны пользователям и защищены от гонок данных.

Если не указано иное, стандартная библиотека С ++ функции должны выполнять все операции только в пределах текущей нити, если эти операции имеют эффекты, которые видны (1,10) для пользователей.

9 [Примечание. Это позволяет реализациям распараллеливать операции , если нет видимых побочных эффектов. - Конец примечания]

Заключение
Контейнеры не являются поточно! Но безопасно называть функции const на контейнерах из нескольких параллельных потоков. Так что можно сделать только для чтения операции с параллельными потоками без блокировка. Я прав?

Я притворяюсь, что их не существует какая-либо неисправная реализация, и всякая реализация стандарта C++ 11 верна.

Пример:

// 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; 
} 

Этот код может быть скомпилирован с GCC 4.7 и прекрасно работает на моей машине.

$ echo $?

Answer 1

Представление данных из спецификации C++ 11 в разделах 1.10/4 и 1.10/21 требует, по меньшей мере, двух потоков с неатомным доступом к одному и тому же набору мест памяти, два потоки не синхронизированы с доступом к набору мест памяти, а по меньшей мере один поток записывает в или изменяет элемент в наборе мест памяти. Так что в вашем случае, если потоки только читают, вы в порядке ...по определению, поскольку ни один из потоков не записывается в один и тот же набор мест памяти, нет расчётов данных, даже несмотря на отсутствие явного механизма синхронизации между потоками.

Answer 2

Да, вы правы. Вы в безопасности, пока поток, заполняющий вектор, заканчивается, прежде чем начнутся темы чтения. Недавно было a similar question.