按年被提到
20142014 · 2 次2026
算法与数据结构›经典算法与数据结构·arXiv:1408.1935 · cs.DC

Non-Blocking Doubly-Linked Lists with Good Amortized Complexity

Niloufar Shafiei · 2014
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2014-08-11 · 最近 2014-12-22
2不同的人
2活跃月份
2讨论串
7被引(OpenAlex)
arXiv 摘要(候选层不写导读)

We present a new non-blocking doubly-linked list implementation for an asynchronous shared-memory system. It is the first such implementation for which an upper bound on amortized time complexity has been proved. In our implementation, operations access the list via cursors. Each cursor is associated with an item in the list and is local to a process. The implementation supports two update operations, insertBefore and delete, and two move operations, moveRight and moveLeft. An insertBefore(c, x) operation inserts an item x into the list immediately before the cursor c's location. A delete(c) operation removes the item at the cursor c's location and sets the cursor to the next item in the list. The move operations move the cursor one position to the right or left. The update operations use single-word Compare&Swap instructions. The move operations only read shared memory and never change the state of the data structure. If all update operations modify different parts of the list, they run completely concurrently. Let cp(op) be the maximum number of active cursors at any one time during the operation op. The amortized complexity of each update operation op is O(cp(op)) and each move operation is O(1). We have written a detailed correctness proof and amortized analysis of our implementation.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

没有评论直接链到它;下面是它被提交的讨论串里回复最多的评论(不计入统计)
讨论串评论s1m0n · 2014-08

“Lines 18 and 32 of the pseudo clearly show a "while(true)" which blocks... so how can this be called "non-blocking"? Isn't looping until we get lucky pretty much like a "spin lock"? And because the number of loops is not deterministic then surely starvation can occur? For example, if all the threads try to push or pull at the same time to the head or tail…”

Non-Blocking Doubly-Linked Lists with Good Amortized Complexity原评论 ↗
被提交为 story · 2 次