10
$\begingroup$

David Rodríguez - dribeas wrote in a comment on StackOverflow that "Not all collections can be implemented without locks". I'm not sure if this is true, and I can't find proof either way.

This statement isn't very precise, but let me try to rephrase it in a slightly more formal way: For every collection type C, there exists a lock-free collection type CLF that offers the same set of operations, and where each operation on CLF has the same big-O complexity as the corresponding operation on C.

I don't expect a transformation, by the way.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ As a non-expert, I wonder if “lock-free” can be rigorously defined. $\endgroup$
    – Tsuyoshi Ito
    Jan 27, 2011 at 10:31
  • 1
    $\begingroup$ @Suresh: Maybe a synonym for “data structure”? $\endgroup$
    – Tsuyoshi Ito
    Jan 27, 2011 at 10:42
  • 2
    $\begingroup$ What if you just take a lock-free implementation of STM (software transactional memory), and implement any data structures on top of that? $\endgroup$
    – Jukka Suomela
    Jan 27, 2011 at 11:12
  • 5
    $\begingroup$ @Tsuyoshi: I think there is no formal definition of lock-free. Informally, it means you don't use the LOCK instruction of the CPU, which is slow, and stick to the faster compare-and-swap. Since a LOCK can be simulated with compare-and-swap it's difficult to put a hard boundary between "you essentially use compare-and-swap here to simulate a lock (or a transaction for that matter)" and "oh, this is a really clever use of compare-and-swap, and doesn't look at all as if it simulates some higher level operation that we know of." $\endgroup$
    – Radu GRIGore
    Jan 27, 2011 at 11:32
  • 1
    $\begingroup$ As far as I understand it, lock-free is here understood to be synonymous with non-blocking. This doesn't involve the CPU's LOCK instruction but the thread scheduler, via mutexes/semaphores/etc. $\endgroup$
    – MSalters
    Jan 27, 2011 at 14:49

2 Answers 2

Reset to default
11
$\begingroup$

Since I was myself somewhat confused, I begin by clarifying a few concepts in the question.

Collection. I see no reason to spend time rigorously defining what "collection" means when we can simply ask what happens for data structures in general. A data structure occupies a piece of memory and has some operations that may access that memory and that may be invoked by users. These users may be distinct processors or just different threads, it does not concern us. All that matters is that they may execute operations in parallel.

Lock-free. Herlihy and Boss say that a data structure is lock-free when a crashing user does not prevent further uses of the data structure. For example, imagine one pours water on a processor that is in the midst of inserting a node in a sorted set. Well, if other processors try later to insert into that sorted set, they should succeed. (Edit: According to this definition, it is the case that if a data structure uses locks then it is not lock-free, but it is not the case that if a data structure does not use locks then it is lock-free.)

With these definition, I think Herlihy and Boss basically say that the answer is to turn critical regions into transactions.

But, you may ask, does this have the same complexity? I'm not sure the question makes sense. Consider push(x) { lock(); stack[size++] = x; unlock(); }. Is this a constant time operation? If you ignore the locking operation and hence other users then you can answer YES. If you do not wish to ignore other users, then there really is no way to say whether push will run in constant time. If you go one level up and see how the stack is used by some particular algorithm, then you might be able to say that push will always take constant time (measured now in terms of whatever happens to be the input of your parallel algorithm). But that really is a property of your algorithm, so it doesn't make sense to say that push is a constant time operation.

In summary, if you ignore how much a user executing an operation waits for other users, then using transactions instead of critical regions answers your question affirmatively. If you don't ignore the waiting time, then you need to look at how the data structure is used.

Improve this answer
$\endgroup$
12
  • $\begingroup$ I am not too sure on whether you can actually consider that the push operation as stated above is not a constant time operation. For a fixed number of processors, and a common implementation of lock that guarantees no starvation, the above operation (in the worst case, for any given processor takes N_proc * O(1), which can naïvely be assumed to be O(1) (number of processors being factored into the hidden constant). $\endgroup$
    – David Rodríguez - dribeas
    Jan 29, 2011 at 23:27
  • $\begingroup$ It is a surprisingly common error to fix $n$ in $f(n)$ and then claim that $f$ is constant. The other day I asked some colleagues if they can come up with a constant time algorithm for the ruler function, and some objected that the number of bits in a computer word is constant. (Hence, I presume was implied, all algorithms for computing the ruler function are constant time.) To address your comment directly, yes, that's what I meant by `ignoring other users', that we treat that variable as a constant. $\endgroup$
    – Radu GRIGore
    Jan 30, 2011 at 8:02
  • $\begingroup$ Well, memory access is a common case of that. Most algorithm analysis assumes that memory access is O(1) independent of memory used; real memory architectures (with caches etc) are better approximate by O(log N) where N is memory used. $\endgroup$
    – MSalters
    Jan 31, 2011 at 11:25
  • $\begingroup$ While the assumption that the number of processors is a constant is quite practical, I will avoid it. Then the issue is that the complexity cannot be analyzed in a unidimensional fashion, as the size of the problem is bound to grow both in the size of the input and the number of processors, both of which are orthogonal dimensions. Assuming a particular container in the C++ standard library (I'm obviously picking a hard one) one of the requirements is that all elements are held in a contiguous block of memory. $\endgroup$
    – David Rodríguez - dribeas
    Feb 1, 2011 at 22:58
  • $\begingroup$ Now, appending an element to the vector is an amortized constant time operation (if it does not fit in the previously allocated block, the call will take a linear time on the number of elements in the container, but if the reserved block of memory is acquired following an exponential sequence the amortized cost is constant). If you implement a thread safe container, you would lock and then perform the change, the cost of the operation is proportional to the cost of locking --which I don't really know... but in a first approximation you can consider mostly constant $\endgroup$
    – David Rodríguez - dribeas
    Feb 1, 2011 at 23:02
3
$\begingroup$

I think that "COLLECTIONS" stands for "queues, stacks, linked lists, trees, ..."

From http://www.cl.cam.ac.uk/research/srg/netos/lock-free/

Through careful design and implementation it's possible to build data structures that are safe for concurrent use without needing to manage locks or block threads. These non-blocking data structures can increase performance by allowing extra concurrency and can improve robustness by avoiding some of the problems caused by priority inversion in local settings, or machine and link failures in distributed systems.

The best overall introduction to our non-blocking algorithms is the paper Concurrent programming without locks, currently under submission, which covers our designs for multi-word compare-and-swap, word-based software transactional memory and object-based software transactional memory.

If "lock-free" means "do not use operarting system's semaphores, mutex, monitors, ..." then I think (but I'm not an expert) that every collection can be made lock-free using atomic read-write-modify primitives that must be supported by the hardware.

A computational overhead is needed, but I think that for simple structures like lists, trees, hash tables ... the overall computational complexity of searches/insertions/deletions $O(\cdot)$ does not change.

Exhaustive documentation on the subject can be found online:

http://www.google.it/search?q=lock+free+algorithm+filetype%3Apdf

(... and further references at the end of each document)

Improve this answer
$\endgroup$

Your Answer

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

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