español - map c++

Acceso seguro de solo lectura en paralelo a un contenedor STL

Question

Quiero acceder a un contenedor basado en STL de solo lectura desde subprocesos en ejecución en paralelo . Sin utilizar ningún usuario implementado el bloqueo. La base del siguiente código es C ++ 11 con una implementación adecuada del estándar.

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/ ( borrador actual o N3337 , que es esencialmente C ++ 11 con errores menores y errores tipográficos corregidos)

23.2.2 Carreras de datos de contenedor [container.requirements.dataraces]

A los efectos de evitar las carreras de datos (17.6.5.9), las implementaciones deben considerar las siguientes funciones const: begin, end, rbegin, rend, front, back, data, find, lower_bound, upper_bound, equal_range, at y, excepto en asociativa o contenedores asociativos desordenados, operador [].

No obstante (17.6.5.9), se requieren implementaciones para evitar las carreras de datos cuando los contenidos del objeto contenido en diferentes elementos en la misma secuencia, excepto el vector <bool>, se modifican al mismo tiempo.

[Nota: para un vector <int> x con un tamaño mayor que uno, x [1] = 5 y * x.begin () = 10 se pueden ejecutar simultáneamente sin una carrera de datos, pero x [0] = 5 y * x.begin () = 10 ejecutado simultáneamente puede resultar en una carrera de datos. Como excepción a la regla general, para un vector <bool> y, y [0] = verdadero puede correr con y [1] = verdadero. - nota final]

y

17.6.5.9 Evitación de carreras de datos [res.on.data.races] 1 Esta sección especifica los requisitos que deben cumplir las implementaciones para evitar las carreras de datos (1.10). Cada función de biblioteca estándar debe cumplir con cada requisito a menos que se especifique lo contrario. Las implementaciones pueden evitar las carreras de datos en casos distintos a los especificados a continuación.

2 Una función de biblioteca estándar de C ++ no accederá directa o indirectamente a objetos (1.10) accesibles por subprocesos que no sean el subproceso actual, a menos que se acceda a los objetos directa o indirectamente a través de los argumentos de la función, incluido esto.

3 Una función de biblioteca estándar de C ++ no modificará directa o indirectamente los objetos (1.10) accesibles por subprocesos distintos del subproceso actual a menos que se acceda a los objetos directa o indirectamente a través de los argumentos no constantes de la función, incluido esto.

4 [Nota: Esto significa, por ejemplo, que las implementaciones no pueden usar un objeto estático para fines internos sin sincronización porque podría causar una carrera de datos incluso en programas que no comparten objetos de forma explícita entre hilos. - nota final]

5 Una función de biblioteca estándar de C ++ no accederá a los objetos accesibles indirectamente a través de sus argumentos o a través de elementos de sus argumentos de contenedor, excepto mediante la invocación de funciones requeridas por su especificación en esos elementos de contenedor.

6 Las operaciones en los iteradores obtenidas llamando a un contenedor de biblioteca estándar o una función de miembro de cadena pueden
acceder al contenedor subyacente, pero no lo modificaremos. [Nota: En particular, las operaciones de contenedor que invalidan los iteradores entran en conflicto con las operaciones en los iteradores asociados con ese contenedor. - nota final]

7 Las implementaciones pueden compartir sus propios objetos internos entre subprocesos si los objetos no son visibles para los usuarios y están protegidos contra las carreras de datos.

8 A menos que se especifique lo contrario, las funciones de la biblioteca estándar de C ++ realizarán todas las operaciones únicamente dentro del hilo actual si esas operaciones tienen efectos visibles (1.10) para los usuarios.

9 [Nota: Esto permite que las implementaciones paralelicen operaciones si no hay efectos secundarios visibles. - nota final]

Conclusión
¡Los contenedores no son seguros para roscas! Pero es seguro llamar a las funciones const en contenedores desde múltiples hilos paralelos. Por lo tanto, es posible realizar operaciones de solo lectura desde hilos paralelos sin bloqueo . Estoy en lo cierto

Pretendo que no existe ninguna implementación defectuosa y que todas las implementaciones del estándar C ++ 11 son correctas.

Muestra:

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

Este código se puede compilar con GCC 4.7 y funciona bien en mi máquina.

$ echo $?
$ 0

Answer 1

Sí, tiene usted razón. Usted está seguro siempre que el hilo que llena su vector termine de hacerlo antes de que se inicien los hilos del lector. Hubo una pregunta similar recientemente.

Answer 2

Una carrera de datos, de la especificación C ++ 11 en las secciones 1.10 / 4 y 1.10 / 21, requiere al menos dos subprocesos con acceso no atómico al mismo conjunto de ubicaciones de memoria, los dos subprocesos no están sincronizados con respecto al acceso el conjunto de ubicaciones de memoria, y al menos un hilo escribe o modifica un elemento en el conjunto de ubicaciones de memoria . Entonces, en su caso, si los subprocesos solo están leyendo, está bien ... por definición, ya que ninguno de los subprocesos escribe en el mismo conjunto de ubicaciones de memoria, no hay carreras de datos, aunque no haya un mecanismo de sincronización explícito entre los trapos.