Re: Why Semaphore Hardware-Dependent?

Andi Kleen <ak@xxxxxxx> wrote:

BTW maybe it would be a good idea to switch the wait list to a hlist,
then the last user in the queue wouldn't need to
touch the cache line of the head. Or maybe even a single linked
list then some more cache bounces might be avoidable.

You need a list_head to get O(1) push at one end and O(1) pop at the other.

The poper should know its node address already because it's on its own stack.

No. The popper (__rwsem_do_wake) runs in the context of up_xxxx(), not
down_xxxx(). Remember: up() may need to wake up several processes if there's
a batch of readers at the front of the queue.

Remember also: rwsems, unlike mutexes, are completely fair.

In addition a singly-linked list makes interruptible ops non-O(1) also.

When they are interrupted I guess? Hardly a problem to make that slower.

Currently interruptible rwsems are not available, but that may change, and
whilst I agree making it slower probably isn't a problem, it's still a point
that has to be considered.

David
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Relevant Pages

  • Re[2]: How does disk caching work?
    ... >> While you are correct that when cache is emtry kenrel will dip into the inactive queue. ... Pages on the cache queue still have the association. ... > You may want to study the kernel sources some more, ...
    (freebsd-performance)
  • Re: What happened to computer architecture (and comp.arch?)
    ... the memory order and cache coherent models these primitaves have to ... I have been working, of late, with device drivers that have multiple threads ... I got negative scaling going from 2 to 4 CPUs. ... circular queue that had no spin locks. ...
    (comp.arch)
  • Re: Best database for implementing a cache
    ... However i need to limit the size of the cache so that it may not grow ... metric for evicting existing stored images. ... simply rebuilding meta data at startup (list all files on disk ... with a file and the priority queue will implement file aviction ...
    (comp.lang.java.programmer)
  • Re: [RFC] [PATCH 0/3] ioat: DMA engine support
    ... > the queue of copies long (to amortize the cost of ... Don't forget that there are benefits of not polluting the cache with the ... userland data on the return-to-userspace code path. ... send the line "unsubscribe linux-kernel" in ...
    (Linux-Kernel)
  • Re: memory reading and writing
    ... task manager and iexplore with which I am ... The responsiveness of the whole system seems to be slower by around ... on the whole it seems on my system atleast the L1 cache is critical ...
    (alt.lang.asm)