resueltos - lista enlazada c++ nodos faltantes después de la asignación en múltiples hilos, en x64 linux; ¿por qué?

listas simples estructura de datos

Question

He incluido un código fuente que puedes compilar y ver el problema por ti mismo. compilar con g ++ -lpthread list-memchk.cpp -o list-memchk

EJECUTE ESTO, POR EJEMPLO, ./list-memchk 43000000 30000000 10

He incluido tres archivos, el primero,

list-memchk.cpp

#include <cstdlib>
#include <iostream>
#include <pthread.h>


using namespace std;


 struct node
{
    public :
          unsigned int part1; // 4 bytes
          unsigned int part2; // 4 bytes
          node *next;         //pointer, 8 bytes on 64 bit system
      unsigned int read_part1();
 };


struct LinkedList
 {
     public:
     LinkedList();
          void insert(unsigned int data[], unsigned int data1);
          bool isEmpty() const;
          node* head;
 };

unsigned int node::read_part1() {
return part1;
}
 LinkedList::LinkedList():
 head(NULL)
{
}

bool LinkedList::isEmpty() const
{
  return (head == NULL);
}

  void LinkedList::insert(unsigned int data[], unsigned int data1)
 {



    node* oldHead = head;
    node* newHead = new node();
    newHead->part1 = data[0];
    newHead->part2 = data1;
    newHead->next = oldHead;
    head = newHead;

  }

unsigned int allocations = 300000000;
unsigned int index_size = 430000000;//index of lists, 430m,.
pthread_mutex_t mutex;
                    //will be creatad on heap
    LinkedList *list = NULL;



unsigned long node_count() {

 unsigned long numNodes = 0;


for (int i=0; i<index_size; i++)
{


  node* current = list[i].head;

// if root is null, the number of nodes is 0
if(current != NULL) {

// if root is not null, we have at least one node
    numNodes++;

// count all nodes
while(current->next != NULL) {
numNodes++;
current = current->next;
}

}

}

return numNodes;

}


#include "alloc_threads.cpp"










void start_threads(int thread_count) {

alloc_threads alloc_thr[thread_count];//thread objects
pthread_t threads[thread_count];

pthread_mutex_init(&mutex, NULL);

for (int i=0; i<thread_count; i++)
{

alloc_threads *rr;

rr = new alloc_threads(list, mutex, allocations);
alloc_thr[i] = *rr;

pthread_create(&threads[i], NULL, &alloc_threads::allocation_helper,&alloc_thr[i]);

delete rr;
}

for (int i=0; i<thread_count; i++)
pthread_join( threads[i], NULL);


}








int main(int argc, char *argv[])

{
if ( argc < 4 )
{
std::cout << "Missing paramaters. " << endl;
std::cout << "Please run me like this : <list-memchk> <index_size> <allocations_per_thread> <thread_count>" << endl;
return 1;
}


index_size = strtoul(argv[1], 0, 10);
allocations = strtoul(argv[2], 0, 10);
unsigned int thr_cnt = strtoul(argv[3], 0, 10);

LinkedList list_instance;

cout << "1 LinkedList instance takes [" << sizeof(list_instance) << "] bytes in memory!"<< endl;

node node_instance;

cout << "1 node instance takes [" << sizeof(node_instance) <<"] bytes in memory !"<< endl;


list = new (nothrow) LinkedList[index_size];
    if (!list)
    {
        cout << "Error allocating memory" << endl;
        return 1;
    }


unsigned int some_data[] = {00, 01};
unsigned int index;





cout << "Allocating ..." << endl;
start_threads(thr_cnt);


unsigned long sk = ((allocations * sizeof(node_instance) + index_size*sizeof(list_instance))) / (1024*1024*1024);

cout << "This process *should* consume around " << sk <<" GBytes of memory, but does it ?"<< endl;

cout << "Allocating done, *check the process size* ..." << endl;


cout << "Lets count `nodes` to see how many do we have; counting, please wait ..." << endl;

cout << "We have reached [" << node_count() << "] nodes, expected [" << allocations * thr_cnt << "] nodes. You may press any number key to exit." << endl;

string s;
getline(std::cin, s);



return 0;
}

entonces, alloc_threads.cpp

#include "alloc_threads.h"
using namespace std;

alloc_threads::alloc_threads()
{
}

 void *alloc_threads::allocation_helper(void *context)
    {
        return ((alloc_threads *)context)->allocation();
    }

 alloc_threads::alloc_threads(LinkedList* x_list, pthread_mutex_t x_mutex, unsigned int x_allocations)


{
        list = x_list;
        mutex = x_mutex;
        allocations = x_allocations;
}

void * alloc_threads::allocation(void)
{

cout << "Thread started" << endl;
unsigned int some_data[] = {00, 01};
unsigned int index;
unsigned short inde;

LinkedList *list_instance2 = NULL;
for (int i=0; i<allocations; i++)
{

pthread_mutex_lock(&mutex);



index = rand();
inde = (unsigned short)index;
list_instance2 = &list[inde];

list_instance2->insert(some_data, some_data[1]);

pthread_mutex_unlock(&mutex);
}





cout << "Thread finished" << endl;
return 0;
}

alloc_threads::~alloc_threads()
{
}

y, finalmente, alloc_threads.h

class alloc_threads{
public:
    void *allocation(void);
    static void *allocation_helper(void *context);
    alloc_threads();
    alloc_threads(LinkedList *x_list, pthread_mutex_t x_mutex, unsigned int x_allocations);
    ~alloc_threads();
private:    
       pthread_mutex_t mutex;
       LinkedList* list;
       unsigned int allocations;

};

El código en sí no se comenta en absoluto, pero espero que no sea tan difícil de entender. lo que he hecho, es im asignar memoria con un asignador estándar en múltiples hilos concurrentes, digamos, 10, por ejemplo. después de que la asignación se realiza en todos los hilos, estoy accediendo a cada nodo e incrementando los numNodes luego de un acceso exitoso. lo que normalmente obtengo es que el valor numNodes sea ​​menor en unos pocos / pocos cientos o pocos miles de lo esperado. qué está mal ? y, he hecho esto con dos asignadores diferentes, ambos tienen el mismo comportamiento.

Answer 1

Parece, estoy usando mutex de la manera incorrecta - no detiene los hilos concurrentes desde la escritura en la misma memoria.

La solution encontré, es la siguiente: definir la variable mutex en list-memchk.cpp y evitar pasarla a hilos pero usarla tal as is .

list-memchk.cpp: reemplace la definición mutex con esto,

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER ;

retirar

pthread_mutex_init(&mutex, NULL);

alloc_threads.h: eliminar mutex de este archivo;

alloc_threads.cpp: eliminar mutex = x_mutex;

Eso es. No más nodos faltantes. Sin embargo, la velocidad de asignación es miserable. Parece que los hilos están esperando unos a otros para desbloquear mutex; los núcleos de la CPU están inactivos y la asignación requiere grandes cantidades de tiempo.