Quantcast

Lock-free message queue

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Lock-free message queue

Max Lapshin-2
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?

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:[hidden email]

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Lock-free message queue

Björn-Egil Dahlberg
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.

// Björn-Egil

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:[hidden email]

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Lock-free message queue

Michael Truog
In reply to this post by Max Lapshin-2
It probably has already been implemented here:
http://tim.klingt.org/git?p=boost_lockfree.git;a=summary

On 09/22/2010 05:48 AM, 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?
>
> ________________________________________________________________
> erlang-questions (at) erlang.org mailing list.
> See http://www.erlang.org/faq.html
> To unsubscribe; mailto:[hidden email]
>
>
>  


________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:[hidden email]

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Lock-free message queue

Mikael Pettersson-3
In reply to this post by Björn-Egil Dahlberg
=?UTF-8?B?QmrDtnJuLUVnaWwgRGFobGJlcmc=?= writes:
 > 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?

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:[hidden email]

Loading...