1

是否有一个已知的工作代码可以同时在多个线程中将元素添加到共享的、初始化的 c 样式数组(对象),而不必对该资源使用锁定?我的意思是,到一个连续的内存块,其中元素不通过指针链接。

我的意思是,算法,而不是库等。我只想用 20 个没有锁的线程中的元素填充数组,或者必须为要填充的线程指定数组范围(很像无锁链表)。

我正在使用 slackware 13.37 64 位、pthreads、intel c++ 编译器、tcmalloc 分配器。

更新:感谢大家的回答,你们都对你的想法有所帮助;如果可以的话,我会将您的所有想法标记为答案。但是,我仍在为我的代码而苦苦挣扎。所以我稍后把代码放在另一个线程中,看看我的代码到底发生了什么,这样人们才能真正集中注意力。

4

3 回答 3

2

也许我没有正确理解这个想法,但显而易见的解决方案就是std::atomic对当前数组索引使用增量。整数类型的原子通常实现为无锁。

但是,如果这不是真的或者您的编译器不支持 C++11,您可以将其替换为您的编译器特定的无锁函数,例如InterlockedIncrementVS 或__sync_fetch_and_addGCC。

支持英特尔 C++ 编译器C++ 11 atomics。您也可以_InterlockedIncrement64从头ia64intrin.h文件中使用,请参阅第 147 页的Intel(R) C++ Intrinsics Reference.

示例代码(证明它在这里工作)

#include <atomic>
#include <thread>
#include <iostream>

const uint max_count = 100;

std::atomic_uint count;
std::string data[max_count];

void thread_func(const char* str)
{
   while(true)
   {
      const uint index = count++;
      if(index >= max_count) break;
      // Use += to see defect if data was already initialized by other thread
      data[index] += str;
      std::this_thread::sleep_for(std::chrono::milliseconds(1));
    }
 }

 int main()
 {
    std::cout << "Atomic counter is lock-free: " << 
       (count.is_lock_free() ? "Yes!" : "No!") << std::endl;

    std::thread t1(thread_func, "Thread 1");
    std::thread t2(thread_func, "Thread 2");
    std::thread t3(thread_func, "Thread 3");

    t1.join();
    t2.join();
    t3.join();

    for(uint i = 0; i < max_count; ++i)
    {
       std::cout<< i << ": " << data[i] << std::endl;
    }

    return 0;
 }
于 2012-10-23T10:40:44.303 回答
0

您可以对数组进行分区,以便每个线程都有一个卡盘。例如,如果您有:

static int array[100];

然后每个线程都可以处理它的一部分:

int size = 100 / amount_of_threads;
int* partition = array + thread_id * size;

thread_id假设是连续的并且从 0 开始。

于 2012-10-23T09:37:17.680 回答
0

如果您只是想读取和写入数组中的对象,那么您可以只使用互锁样式指令来读取和写入数据。例如:

Foo* data[10];
// some more code
Foo *value=interlocked_read(&data[2]);

interlocked_write(&data[3], new Foo);

联锁将确保您以原子方式读取有效指针,并确保您在访问数组时具有一致的内存视图。如果您使用的是 Windows,请查看同步文档中的各种 InterlockedXXX 功能。

如果要从数组中读取对象,对其进行更改然后将其写回,如果要避免锁定并避免另一个线程更改的可能性,则需要使用比较和交换方法(也称为 CAS)与您同时更新的对象。

于 2012-10-23T09:41:32.687 回答