[adekok]

Locking isn't the problem. Contention is the problem.

Even "lock free" algorithms can still not scale due to contention. Read this paper for a good summary:

http://queue.acm.org/detail.cfm?id=2991130

In short, a queue is made up of a linked list, where each entry is itself a circular buffer. Insertions go into a circular buffer... unless there's contention, in which case the next circular buffer is used.

The result is that insertions are mostly not contented. Removals are mostly not contented. And it scales very well.