为什么不直接适用粗粒度的锁？只是锁定整个队列。

一个更复杂（但不一定更有效，取决于你的使用模式）的解决方案是使用读写锁，读，写，分别为。

---

使用无锁的操作似乎对我没有对你的情况很不错的主意。想象一些线程遍历队列，并在同一时刻的当前项被删除。不要紧，你遍历算法多少额外的链接认为，所有的项目可能会被删除，所以你的code就没有机会完成穿越。

---

使用比较和交换的另一个问题是，使用指针你永远不知道是否真的指向相同的旧结构，或者旧的结构已被释放，并在同一地址的一些新的结构分配。这可以或者为您的算法可能不会成为一个问题。

---

有关的本地锁定（即可能性分别锁定每个列表项）的情况下，一个想法是，以有序的锁。订购锁保证了僵局是不可能的。所以，你的操作是这样的：

由指针p到 previous 的项目删除

1. 锁P，检查（在项目使用特殊也许标志），该项目仍处于列表


2. 锁定下一个P->，确认这不是零和列表;这样可以确保在p>下一步 - >下一步会不会在此期间被删除


3. 锁P->下一步 - >下一步


4. 设置在p->标志旁边表明它是不在列表中


5. （P->下一步 - >下一个 - > preV，P->下一个 - > preV）=（P，NULL）; （P->接下来，P->下一步 - >下一步）=（P->下一步 - >接下来，空）


6. 释放锁

插入开头：

1. 锁头


2. 将标志新项目，表明它在列表


3. 锁定新项目


4. 锁流浆>接下来


5. （流浆>下一个 - > $ P $光伏，新 - > preV）=（新，头）; （新建 - >接下来，头）=（头，新）


6. 释放锁

这似乎是正确的，我没有尝试但这个想法。

从本质上讲，这使得双链表工作就好像它是一个单链接列表。

---

如果你没有指针previous列表元素（当然这是通常的情况下，因为它几乎不可能保持一致的状态，这样的指针），你可以做到以下几点：

由指针c删除到要删除的选项：

1. 锁定C，检查它是否仍是列表的一部分（这是在列表项标志），如果没有，操作失败


2. 获得指针p = C - > $ P $光伏


3. 解锁C（现在，C可以移动或通过其他线程删除，P可以从列表中移动或删除以及）为了避免C的释放，你需要有类似的共享指针，或在至少一种引用计数列表项这里]的


4. 锁定P


5. 检查如果p是列表的一部分（它可以被第3步后删除）;如果没有，解锁p和从头开始重新


6. ，检查是否P->下一等于C如果没有，解锁p和从头开始重新[这里我们也许可以优化了重启，不知道ATM]


7. 锁P->旁边;在这里，你可以肯定的是P->下一== c和不被删除，因为C删除将需要的P锁定


8. 锁P->下一步 - 下一步>;现在所有的锁已被占用，所以我们可以继续


9. 设置c是不在列表中的一部分标记


10. 执行习惯（P->接下来，C->接下来，C - > preV，C->下一个 - > preV）=（C->接下来，NULL，NULL，P）


11. 释放所有的锁

请注意，仅仅有一个指向某个列表项不能确保该项目不释放，所以你需要有一种引用计数，使该项目不会在非常时刻摧毁你试图锁定

---

请注意，在最后算法重试次数是有界的。事实上，新的项不能显示在C的左侧（插入是在最右边的位置）。如果我们的步骤5失败，因此，我们需要一个重试，这只能由具有p-从同时列表中删除引起的。这种去除可以发生大于N-1次，其中N为c的列表中的初始位置不多。当然，这个最坏的情况下是相当不太可能发生。

I'm trying to implement a (special kind of) doubly-linked list in C, in a pthreads environment but using only C-wrapped synchronization instructions like atomic CAS, etc. rather than pthread primitives. (The elements of the list are fixed-size chunks of memory and almost surely cannot fit pthread_mutex_t etc. inside them.) I don't actually need full arbitrary doubly-linked list methods, only:

• insertion at the end of the list
• deletion from the beginning of the list
• deletion at arbitrary points in the list based on a pointer to the member to be removed, which was obtained from a source other than by traversing the list.

So perhaps a better way to describe this data structure would be a queue/fifo with the possibility of removing items mid-queue.

Is there a standard approach to synchronizing this? I'm getting stuck on possible deadlock issues, some of which are probably inherent to the algorithms involved and others of which might stem from the fact that I'm trying to work in a confined space with other constraints on what I can do.

Edit: In particular, I'm stuck on what to do if adjacent objects are to be removed simultaneously. Presumably when removing an object, you need to obtain locks on both the previous and next objects in the list and update their next/prev pointers to point to one another. But if either neighbor is already locked, this would result in a deadlock. I've tried to work out a way that any/all of the removals taking place could walk the locked part of the list and determine the maximal sublist that's currently in the process of removal, then lock the nodes adjacent to that sublist so that the whole sublist gets removed as a whole, but my head is starting to hurt.. :-P

Conclusion(?): To follow up, I do have some code I want to get working, but I'm also interested in the theoretical problem. Everyone's answers have been quite helpful, and combined with details of the constraints outside what I expressed here (you really don't want to know where the pointer-to-element-to-be-removed came from and the synchronization involved there!) I've decided to abandon the local-lock code for now and focus on:

• using a larger number of smaller lists which each have individual locks.
• minimizing the number of instructions over which locks are held and poking at memory (in a safe way) prior to acquiring a lock to reduce the possibility of page faults and cache misses while a lock is held.
• measuring the contention under artificially-high load and evaluating whether this approach is satisfactory.

Thanks again to everybody who gave answers. If my experiment doesn't go well I might come back to the approaches outlined (especially Vlad's) and try again.

Why not just apply a coarse-grained lock? Just lock the whole queue.

A more elaborate (however not necessarily more efficient, depends on your usage pattern) solution would be using a read-wrote lock, for reading and writing, respectively.

---

Using lock-free operations seem to me not a very good idea for your case. Imagine that some thread is traversing your queue, and at the same moment the "current" item is deleted. Doesn't matter how many additional links your traverse algorithm holds, all that items may be deleted, so your code would have no chance to finish the traversal.

---

Another issue with compare-and-swap is that with pointers you never know whether it really points to the same old structure, or the old structure has been freed and some new structure is allocated at the same address. This may or may not be an issue for your algorithms.

---

For the case of "local" locking (i.e., the possibility to lock each list item separately), An idea would be to make the locks ordered. Ordering the locks ensures the impossibility of a deadlock. So your operations are like that:

Delete by the pointer p to the previous item:

1. lock p, check (using perhaps special flag in the item) that the item is still in the list
2. lock p->next, check that it's not zero and in the list; this way you ensure that the p->next->next won't be removed in the meantime
3. lock p->next->next
4. set a flag in p->next indicating that it's not in the list
5. (p->next->next->prev, p->next->prev) = (p, null); (p->next, p->next->next) = (p->next->next, null)
6. release the locks

Insert into the beginning:

1. lock head
2. set the flag in the new item indicating that it's in the list
3. lock the new item
4. lock head->next
5. (head->next->prev, new->prev) = (new, head); (new->next, head) = (head, new)
6. release the locks

This seems to be correct, I didn't however try this idea.

Essentially, this makes the double-linked list work as if it were a single-linked list.

---

If you don't have the pointer to the previous list element (which is of course usually the case, as it's virtually impossible to keep such a pointer in consistent state), you can do the following:

Delete by the pointer c to the item to be deleted:

1. lock c, check if it is still a part of the list (this has to be a flag in the list item), if not, operation fails
2. obtain pointer p = c->prev
3. unlock c (now, c may be moved or deleted by other thread, p may be moved or deleted from the list as well) [in order to avoid the deallocation of c, you need to have something like shared pointer or at least a kind of refcounting for list items here]
4. lock p
5. check if p is a part of the list (it could be deleted after step 3); if not, unlock p and restart from the beginning
6. check if p->next equals c, if not, unlock p and restart from the beginning [here we can maybe optimize out the restart, not sure ATM]
7. lock p->next; here you can be sure that p->next==c and is not deleted, because the deletion of c would have required locking of p
8. lock p->next->next; now all the locks are taken, so we can proceed
9. set the flag that c is not a part of the list
10. perform the customary (p->next, c->next, c->prev, c->next->prev) = (c->next, null, null, p)
11. release all the locks

Note that just having a pointer to some list item cannot ensure that the item is not deallocated, so you'll need to have a kind of refcounting, so that the item is not destroyed at the very moment you try to lock it.

---

Note that in the last algorithm the number of retries is bounded. Indeed, new items cannot appear on the left of c (insertion is at the rightmost position). If our step 5 fails and thus we need a retry, this can be caused only by having p removed from the list in the meanwhile. Such a removal can occur not more than N-1 times, where N is the initial position of c in the list. Of course, this worst case is rather unlikely to happen.