CODEWITHSUNDEEP
multithreadingalgorithmdata-structureslanguage-agnosticnonblocking
user541686
user541686

Reputation: 210705

How are "nonblocking" data structures possible?

I'm having trouble understanding how any data structure can be "nonblocking".

Say you're making a "nonblocking" hashtable. At some point or another, your hashtable gets too full, so you have to re-hash into a larger table.

This implies you need to allocate memory, which is a global resource. So it seems that you must obtain some sort of lock to prevent global corruption of the heap... irrespective of possible problems with your data structure itself!
But then that means every other thread must block while you allocate your memory...

What am I missing here?
(How) can you allocate memory without blocking another thread which is doing the same?

Upvotes: 8

Views: 2581

Answers (4)

Brian Gideon
Brian Gideon

Reputation: 48959

Most strategies have one fundamental pattern in common. They use a compare and swap (CAS) operation in a loop until it succeeds.

For example, lets consider a stack implemented with a linked list. I chose a linked list implementation because it is easy to make concurrent with a CAS, but there are other ways to do it. I will use C-like pseudocode.

Push(T item)
{
  Node node = new Node(); // allocate node memory
  Node initial;
  do
  {
    initial = head;
    node.Value = item;
    node.Next = initial;
  }
  while (CompareAndSwap(head, node, initial) != initial);
}

Pop()
{
  Node node;
  Node initial;
  do
  {
    initial = head;
    node = initial.Next;
  }
  while (CompareAndSwap(head, node, initial) != initial);
  T value = initial.Value;
  delete initial; // deallocate node memory
  return value;
}

In the above code CompareAndSwap is a non-blocking atomic operation that replaces the value in a memory address with a new value and returns the old value. If the old value does not match the expected value then you spin through the loop and try it all again.

Upvotes: 2

MicSim
MicSim

Reputation: 26816

Just for some definitions, additional information and to distinguish between non-blocking, lock-free and wait-free terms, I recommend reading the following article (I won't copy the relevant passages here as it's too long):

Definitions of Non-blocking, Lock-free and Wait-free

Upvotes: 3

Martin Hock
Martin Hock

Reputation: 964

All that non-blocking means is that you never wait indefinitely, not that you never wait at all. As long as your heap is also implemented using a non-blocking algorithm, you can implement other non-blocking algorithms on top of it.

Upvotes: 0

amit
amit

Reputation: 178491

Two examples for non blocking designs are optimistic design and Transactional Memory.

The idea of this is - in most of the cases, the blocking is redundant - since two OPs can concurrently occur without interrupting each other. However, sometimes when 2 OPs occur concurrently and the data becomes corrupted because of it - you can roll back to your previous state, and retry.

There might still be locks in these designs, but the time the data is locked is significantly shorter, and is limited only to the critical time where the affect of the OP is taking place.

Upvotes: 5

Related Questions