There is both a qualitative difference and quantitative difference in a
lockless algorithm as described versus one that uses locking. Most
importantly for Linux, these algorithms in practice have better performance
characteristics. There is a whole body of literature on lock free
algorithms (see Maurice Herlihy's 1988 PODC Wait-Free Synchronization
paper). When a process holds a lock nobody else can make progress. If
that process is interrupted everybody waits. Furthermore, when designing
for scalability, queue locks are used, which considerably exacerbates the
problem (see Kontothanassis TOCS Feb 1997). Locking reduces concurrency,
lockfree and lockless algorithms allow increased concurrency (both
processes can simultaneously log their events once they've reserved space).
The lockless tag is indeed correct, accurate, and helpful in identifying
the characteristics of the algorithm. More of these algorithms, such as
the recent RCU work, will need to be placed into Linux for it to perform
well on multiprocessors.
Robert Wisniewski
The K42 MP OS Project
Advanced Operating Systems
Scalable Parallel Systems
IBM T.J. Watson Research Center
914-945-3181
http://www.research.ibm.com/K42/
bob@watson.ibm.com
Perez-Gonzalez, Inaky writes:
>
> > From: Karim Yaghmour [mailto:karim@opersys.com]
> >
> > relayfs actually uses 2 mutually-exclusive schemes internally -
> > 'lockless' and 'locking', depending on the availability of a cmpxchg
> > instruction (lockless needs cmpxchg). If the lockless scheme is being
> > used, relay_lock_channel() does no locking or irq disabling of any
> > kind i.e. it's basically a no-op in that case.
>
> So that means you are using cmpxchg to do the locking. I mean, not the
> "locking" itself, but a similar process to that of locking. I see.
>
> However, isn't it the almost the same as spinlocking? You are basically
> trying to "allocate" a channel idx with atomic cmpxchg; if it fails, you
> are retrying, spinning on the retry code until successful.
>
> Not meaning to be an smartass here, but I don't buy the "lockless" tag,
> I would agree it is an optimized-lock scheme [assuming it works better
> than the spinlock case, that I am sure it does because if not you guys
> would have not gone through the process of implementing it], but it is
> not lockless.
>
>> Don't get me wrong - I don't mean the actual difference is not important;
>> what I mean is not important is me buying the "lockless" tag or not. I
>> actually think that the method you guys use is really sharp.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Wed Apr 30 2003 - 22:00:17 EST