[erlang-questions] Lock-free message queue
Wed Sep 22 23:36:24 CEST 2010
> On 2010-09-22 14:48, Max Lapshin wrote:
> > Just a curiosity: currently there is some kind of locks in sending message.
> > Have anybody tried to implement a lock-free linked list:
> > http://www.amd64.org/fileadmin/user_upload/pub/epham08-asf-eval.pdf
> > Or I'm just looking at wrong place and erts_smp_proc_lock is already
> > using something like this?
> The message queue already has this, sort of. The process that owns the
> message box has an "inner box" that he has a lock on and an "outer box"
> that all senders compete for. So the lock contention is on the tail of
> the queue on the "outer box" when lots of processes sends to that
> process. The mail box owner is not concerned with it though.
A problem here is that people seem to equate "lock-free" with
"better than locks". Both approaches ultimately have similar
hardware costs, namely cache lines ping-ponging over a bus
between caches belonging to whichever package/core/thread wants
ownership at the moment. If you call it a lock or just do the
appropriate memory barrier + CAS or LL/SC doesn't matter IMO.
In addition, lock-free algorithms generally only work as far
as modifying the shared data structure goes; then there's a
very tricky memory management problem(*), which brings in a
whole new set of problems and possible solutions.
Having said that, I do think that the process in-mbox (the outer
one) is simple and restricted enough that a lock-free solution
should be possible.
(*) When you delete a node from a shared data structure,
_who_ exactly gets to free() that node and when?
More information about the erlang-questions