Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

From: Victor Yodaiken (
Date: Wed Oct 10 2001 - 17:24:19 EST

On Thu, Oct 11, 2001 at 07:56:43AM +1000, Keith Owens wrote:
> On Wed, 10 Oct 2001 09:54:36 -0600,
> Victor Yodaiken <> wrote:
> >Although I kind of like the idea of
> > normal operation create mess by avoiding synchronization
> > when system seems idle, get BKL, and clean up.
> That does not work. A process can read an entry from a list then
> perform an operation that puts the process to sleep. When it wakes up
> again, how can it tell if the list has been changed? How can the

In general you're right, and always its better to
reduce contention than to come up with silly algorithms for
reducing the cost of contention, but if you want to live

        atomic increment read_count
        do stuff; skip queue elements marked
                as zombie
        atomic decrement read_count

        spin lock queue
        to delete element
        mark element as zombie

        spin lock queue
        if(read_count == 0){
                get big kernel lock
                if(read_count is still 0)
                        // now nobody will be able to get to queue
                        clean up queue
                unlock kernel
        unlock spin

So you accomplished making the code harder to read and maintain, slowing
down worst case, and maybe reducing average case read spinlock delay.
For some very carefully selected cases this may be a win, but ...

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

This archive was generated by hypermail 2b29 : Mon Oct 15 2001 - 21:00:35 EST