4

Suppose I have a sorted, singly-linked list of N integers containing no duplicates, and k threads (where k << N), each trying to insert some integer (larger than the head node) into the list.

Is it possible to synchronize insertions into such a list such that:

  • A thread may only block access to its (immediately) previous node
    (No locking the "whole list")
  • At most O(k) mutexes and condition variables may be used
  • No preemption/interrupts may occur

?

2
  • 1
    Homework? Interview question? What have you done to attempt to answer this yourself? And what does this have to do with C?
    – Jim Balter
    Feb 28, 2011 at 11:34
  • I'm working on a personal project and the problem I'm currently facing (which is more complex) reduces to what I ask above. I'm trying to implement the solution using pthreads in C, that's why I added the c-tag. Should I provide some more implementation detail?
    – ManRow
    Feb 28, 2011 at 11:43

1 Answer 1

4

First, if insertion into the collection is anything but a very infrequent task, then linked lists aren't a great solution for this - because finding the insertion point is an O(N) operation, even for a sorted list, and hence going to end up scaling badly.

If you still need to do it, it's possible to perform insertion (unlike deletion) into a sorted list as lockless operation, with some care:

  1. Find insertion point, cur
  2. Create new node (assign prev/next linkage to cur/cur->next)
  3. Atomic op: compare_and_swap(cur->next, new, new->next);
    If fail: if (new->value == next->value) return; // someone beat us to it
    Else: cur = cur->next and repeat the dance (list is sorted, someone inserted before us)

I.e. the outcome of the attempt to link a new node in is either that we succeed, or that someone beat us to inserting the same node (in which case we're ok - it's already there), or someone inserted into a gap (i.e. existing was N, N+3, we tried N+1, someone else succeeded N+2) in which case we retry till we succeed or find 'our' node done by someone else.

It's far more difficult to synchronize deletion; lookup RCU (Read-Copy-Update) for that.

3
  • Wouldn't locating the insertion point as such inherently lead to a readers-writers problem? I.e., we cannot be searching for or finding the insertion point curr if the list ahead is being modified.
    – ManRow
    Mar 1, 2011 at 1:02
  • You're testing for "earlier than", and that point will not be changed by insertion (notice: I'm not saying modification because that'd include deletion). Within the "atomic dance" you might have to advance the insertion point if another inserter raced you, but you'll never need to step back.
    – FrankH.
    Mar 2, 2011 at 8:52
  • @FrankH. I didn't get why there are three arguments for compareAndSwap. In Java it will be (oldObject, newObject), what is the third argument here? Dec 9, 2015 at 6:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.