并发访问和没有数据结构
问题是这样的：
我有一个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; }; 如果我只是在搜索/删除之前锁定列表，则问题很容易解决。 但这太粗糙了。 我如何同步这些线程，以便我可以实现更好的并发？
编辑：
- 这不是一个家庭作业问题。 我不属于学术界。
- 持有500个指针的数组看起来很奇怪。 我已经做到了这样，以尽可能少的复杂性来形象化我的问题。
我可以想到一些不涉及全局锁定的广泛方法，并且应该允许一定程度的前进：
1.标记但不要删除
当删除线程识别其受害者时，将其标记为已删除但将其保留在原位。 当搜索线程遇到具有此删除标记的节点时，它只是忽略它。
在标记删除的节点之后，您需要发出写入/释放障碍，并在检查值之前发出获取障碍：您需要特定于平台的，特定于编译器的扩展，否则您将在汇编程序中编写这些障碍。
2.使用无锁列表进行真正删除
根据Peeyush的回答中的论文; CAS的类似平台或编译器特定要求，需要非常小心。 诸如refcounts或危险指针之类的选项可以允许在没有人看到节点时真正删除节点。 您可能会发现需要用short索引替换prev / next指针，您可以将其打包成单个单词以便CAS工作：这意味着限制节点数并将它们分配到数组中。
还要注意，虽然每个线程都应该能够在这种方案上取得进展，但是由于同步要求，各个操作（例如，遍历到下一个节点）可能变得更加昂贵。
您可以使用CompareAndSwap操作考虑无锁链表。
链接到纸张
您需要锁定任何可以更改的数据。 如果您要做很多工作，请在列表中为每个项目创建一个锁。 线程必须锁定上一个，当前和下一个项目才能删除中间项目。 确保始终以相同的顺序获取锁定以避免死锁。
其他删除线程和搜索线程必须等到删除对象并设置新链接。 然后锁被释放，他们可以继续。