并发访问和自由的数据结构的 [英] concurrent access and free of a data structure

问题描述

问题是这样的：

我有500它的指针指向500元素双向链表的数组。有10个线程其中并行运行。每个线程运行50圈，并试图释放在列表中的某些元素。

的列表进行排序（包含简单的整数），并有10并行运行的其他线程，搜索包含特定整数，在该节点访问其它卫星数据的节点。所以，节点是这样的：

 结构节点
{
   INT关键; //使用的密钥来搜索这个节点
   INT X，Y，Z; //卫星数据
   结构节点* preV;
   结构节点*权利;
};
 

问题是容易解决的，如果我只是锁定搜索前列表/删除。但是，过于粗粒度。如何同步这些线程，这样我能取得更好的并发？

编辑：

1. 这是不是一门功课的问题。我不属于学术界。


2. 数组持有500指针似乎不可思议。我已像想象我的问题最少的复杂性。

解决方案

我能想到几个大的方向不涉及全局锁，而应该允许一定程度的转发进度：

1。标记，但不删除

当一个线程删除标识其受害者，将其标记为删除，但它留在地方。
当搜索线程遇到这种删除标记的节点，它只是忽略它。

您需要标志着节点删除之后发出的写/释放屏障，检查前值的获取障碍：你需要特定平台，特定的编译器的扩展，否则你书面这些障碍汇编语言。

2。真正拆除了lockfree列表

根据在Peeyush的答案纸;类似的与平台或特定CAS编译器​​的要求，并显著护理是必需的。如引用计数或危险的指针选项可以允许节点一旦没有人在看着它被真正删除。你可能会发现你需要更换你的preV / next指针短指数可以包成一个字CAS的工作：这意味着边界节点的数量和在一个数组分配它们。

还要注意的是，虽然每个线程应该能够以与这种方案的进展，各个操作（例如，遍历到下一个节点）可能会变得更加昂贵，由于同步要求。

The problem is like this:

I have an array of 500 pointers which point to 500 elements in a doubly linked list. There are 10 threads which run in parallel. Each thread runs 50 loops, and tries to free some element in the list.

The list is sorted (contain simple integers), and there are 10 other threads running in parallel, searching for the node that contains a particular integer and access the other satellite data in this node. So the node is like:

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

The problem is easily solvable if I just lock the list before search / delete. But that is too coarse grained. How do I synchronize these threads so that I can achieve better concurrency?

Edits:

1. This is not a homework question. I do not belong to academia.
2. The array holding 500 pointers seems weird. I have made it like that to visualize my problems with least possible complexity.

解决方案

I can think of a couple of broad approaches which don't involve a global lock, and should allow some degree of forward progress:

1. mark but don't remove

When a deletion thread identifies its victim, mark it as deleted but leave it in place. When a search thread encounters a node with this deleted mark, it just ignores it.

You'll need to issue a write/release barrier after marking the node deleted, and an acquire barrier before inspecting the value: you'll need platform-specific, compiler-specific extensions, otherwise you're writing those barriers in assembler.

2. genuine removal with a lockfree list

As per the paper in Peeyush's answer; similar platform- or compiler-specific requirements for CAS, and significant care is required. Options such as refcounts or hazard pointers can allow the node to be genuinely deleted once no-one is looking at it. You may find you need to replace your prev/next pointers by short indices you can pack into a single word for CAS to work: this means bounding the number of nodes and allocating them in an array.

Also note that although every thread should be able to make progress with this sort of scheme, individual operations (eg. traversing to the next node) may become much more expensive due to the synchronisation requirements.

这篇关于并发访问和自由的数据结构的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！