c ++链表在多线程分配后丢失节点，对x64 linux;为什么？ [英] c++ linked list missing nodes after allocation in multiple threads, on x64 linux; why?

问题描述

我包含了一个源代码，你可以自己编译并查看问题。编译g ++ -lpthread list-memchk.cpp -o list-memchk

运行此示例，./list-memchk 43000000 30000000 10

包含三个文件，第一个

list-memchk.cpp

  #include< cstdlib> 
 #include< iostream> 
 #include< pthread.h> 
 
 
使用namespace std; 
 
 
结构节点
 {
 public：
 unsigned int part1; // 4 bytes 
 unsigned int part2; // 4 bytes 
 node * next; //指针，64位系统上的8个字节
 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 
 {
 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 allocationations = 300000000; 
 unsigned int index_size = 430000000; //索引列表，430m，。 
 pthread_mutex_t mutex; 
 //将在堆上创建
 LinkedList * list = NULL; 
 
 
 
 unsigned long node_count（）{
 
 unsigned long numNodes = 0; 
 
 
 for（int i = 0; i< index_size; i ++）
 {
 
 
 node * current = list [i] 。头; 
 
 //如果root为null，则节点数为0 
 if（current！= NULL）{
 
 //如果root不为null，我们至少有一个节点
 numNodes ++; 
 
 //计数所有节点
 while（current-> next！= NULL）{
 numNodes ++; 
 current = current-> next; 
} 
 
} 
 
} 
 
 return numNodes; 
 
} 
 
 
 #includealloc_threads.cpp
 
 
 
 
 
 
 
 
 
 
 void start_threads（int thread_count）{
 
 alloc_threads alloc_thr [thread_count]; //线程对象
 pthread_t threads [thread_count]; 
 
 pthread_mutex_init（& mutex，NULL）; 
 
 for（int i = 0; i  {
 
 alloc_threads * rr; 
 
 rr = new alloc_threads（list，mutex，allocation）; 
 alloc_thr [i] = * rr; 
 
 pthread_create（& threads [i]，NULL，& alloc_threads :: allocation_helper，& alloc_thr [i]）; 
 
 delete rr; 
} 
 
 for（int i = 0; i  pthread_join（threads [i]，NULL）; 
 
 
} 
 
 
 
 
 
 
 
 
 int main（int argc，char * argv []）
 
 {
 if（argc <4）
 {
 std :: cout< Missing paramaters。< endl; 
 std :: cout<< 请像这样运行：< 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 take [<< sizeof（list_instance）<< ] bytes in memory！< endl; 
 
 node node_instance; 
 
 cout<< 1个节点实例采用[< sizeof（node_instance）<<] in memory！< endl; 
 
 
 list = new（nothrow）LinkedList [index_size]; 
 if（！list）
 {
 cout<< 分配存储器错误< 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<< 这个过程*应该*周围消耗< sk  
 cout<< Allocating done，* check the process size * ...< endl; 
 
 
 cout<< 让计数`节点看看我们有多少;计数，请等待...< endl; 
 
 cout<< 我们已经达到了[< node_count（）<< ] nodes，expected [< allocations * thr_cnt<< ] nodes。您可以按任意数字键退出。 << endl; 
 
 string s; 
 getline（std :: cin，s）; 
 
 
 
 return 0; 
} 
  

那么，
alloc_threads.cpp

  #includealloc_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  {
 
 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（）
 {
} 
  

和最后
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; 
 
}; 
  

代码本身没有注释，但希望它不是很难理解。什么是做的，是在多个并发线程中使用标准分配器分配内存，例如，10。在所有线程中完成分配之后，im访问每个节点并在成功访问后增加 numNodes 。我通常得到的是 numNodes 值比预期小几个/几百或几千。哪里不对 ？

解决方案

看来，im使用互斥体错误的方式 - 它不会停止并发线程写入相同的内存。

我发现的解决方案是： mutex变量在list-memchk.cpp中，并避免将其传递给线程，但使用作为。

< memchk.cpp：
用这个替换mutex定义，

  pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; 
  

remove

  pthread_mutex_init（& mutex，NULL）; 
  

alloc_threads.h：
从此文件中删除mutex;

alloc_threads.cpp：
remove mutex = x_mutex;

它。没有更多的缺失节点。然而，分配速度是悲惨的。看起来线程正在等待对方解开互斥; cpu内核空闲，分配需要大量的时间。

I've included a source code you can compile and see the problem for yourself. compile with g++ -lpthread list-memchk.cpp -o list-memchk

RUN THIS, FOR EXAMPLE, ./list-memchk 43000000 30000000 10

ive included three files, first one,

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

then, 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()
{
}

and, finally, 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;

};

Code itself is not commented at all, but hopefully its not that hard to understand. what ive done, is im allocating memory with standard allocator in multiple concurrent threads, lets say, 10, for example. after allocation is done in all threads, im accessing each node and incrementing numNodes upon successful access. what i typically get, is numNodes value to be smaller by few/few hundred or few thousand than expected. what is wrong ? and, ive done this with two different allocators, both of them have the same behavior.

解决方案

It seems, im using mutex the wrong way - it doesnt stop concurrent threads from writing to same memory.

The solution i found, is : defining mutex variable in list-memchk.cpp and avoid passing it to threads but using it as is.

list-memchk.cpp : replace mutex definition with this,

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER ;

remove

pthread_mutex_init(&mutex, NULL);

alloc_threads.h : remove mutex from this file;

alloc_threads.cpp : remove mutex = x_mutex;

Thats it. No more missing nodes. However, allocation speed is miserable. Looks like threads are waiting on each other to unlock mutex; cpu cores are idling and allocation takes huge amounts of time.

这篇关于c ++链表在多线程分配后丢失节点，对x64 linux;为什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！