并发访问且不受数据结构的影响

Question

问题是这样的:

我有一个包含 500 个指针的数组，它们指向双向链表中的 500 个元素。有 10 个并行运行的线程。每个线程运行 50 个循环，并尝试释放列表中的某些元素。

列表已排序(包含简单整数)，并且有 10 个其他线程并行运行，搜索包含特定整数的节点并访问该节点中的其他卫星数据。所以节点就像:

struct node
{
   int key;         // Key used to search this nodes
   int x,y,z;       // Satellite data
   struct node *prev;
   struct node *right;
};

如果我在搜索/删除之前锁定列表，这个问题很容易解决。但这太粗粒度了。如何同步这些线程以便获得更好的并发性？

编辑:

1. 这不是一个家庭作业问题。我不属于学术界。
2. 保存 500 个指针的数组看起来很奇怪。我这样做是为了以尽可能最小的复杂性可视化我的问题。

Answer 1

我可以想到几种不涉及全局锁定的广泛方法，并且应该允许一定程度的前进:

1。标记但不删除

当删除线程识别出其受害者时，将其标记为已删除，但将其保留在原处。 当搜索线程遇到带有此删除标记的节点时，它会忽略它。

在标记节点已删除后，您需要发出写入/释放屏障，并在检查值之前发出获取屏障:您将需要特定于平台、特定于编译器的扩展，否则您将在中写入这些屏障汇编程序。

2。使用无锁列表进行真正的删除

根据 Peeyush 回答中的论文； CAS 的类似平台或编译器特定要求，并且需要特别小心。诸如引用计数或危险指针之类的选项可以允许节点在无人查看时被真正删除。您可能会发现需要将上一个/下一个指针替换为可以打包到单个单词中的短索引，以便 CAS 正常工作:这意味着限制节点数量并将它们分配在数组中。 p>

另请注意，虽然每个线程都应该能够通过这种方案取得进展，但由于同步要求，单个操作(例如遍历到下一个节点)可能会变得更加昂贵。