C++ 无锁 C 风格共享数组(用于添加元素)

Question

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

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

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

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

Answer 1

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

但如果这不是真的或者你的编译器不支持 C++11，你可以用你的编译器特定的无锁函数替换它，例如InterlockedIncrement对于 VS 或 __sync_fetch_and_add用于海湾合作委员会。

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

示例代码(证明它有效 here )

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