Linux-kernel mailing list archive 1999-23,: Re: New semaphore __wake_up() implementation ...

# Re: New semaphore __wake_up() implementation ...

V Ganesh (ganesh@vxindia.veritas.com)
Fri, 11 Jun 1999 23:36:26 +0530 (IST)

- Messages sorted by: [ date ][ thread ][ subject ][ author ]
- Next message: Jeff Merkey: "Re: VFAT Naming Bugs"
- Previous message: Adam Spiers: "Re: 2.2.7 Oops on SMP machine in __free_page() while loading executable"
- Maybe in reply to: Davide Libenzi: "New semaphore __wake_up() implementation ..."

> From: Andrea Arcangeli <andrea@suse.de>
>
> On Fri, 11 Jun 1999, V Ganesh wrote:
>
> >in trouble. LIFO is unacceptable, FIFO might have priority inversion.
>
> What do you mean exactly with "priority inversion"?
>
> Andrea Arcangeli

the classic priority inversion situation is where a low
priority thread holds a resource, while a high priority process is
blocked waiting for it. since the low-pri thread is rarely scheduled
the high-pri thread suffers as a result, running effectively at the
priority of the holder.
in this case, if we use FIFO, then we will be fair (all processes will
eventually get the lock), but the scheduling goals may not be met (a
higher priority process could wait a long time for a lower priority
process).

this may not be such a problem if we assume that a process taking the
semaphore is obviously in kernel mode and non-preemptible. so it is quite
likely to run through its critical section without blocking and up() the
semaphore, thus minimizing any ill effects of priority inversion due to FIFO.
however, if processes do block often after acquiring a semaphore or need
more than one semaphore, then we still have a problem. I don't know the
source well enough to know which case predominates. but if it is the
former, then I really can't understand why we didn't just wake the
first process off the queue instead of the elaborate thundering herd
mechanism we have.

ganesh

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

- Next message: Jeff Merkey: "Re: VFAT Naming Bugs"
- Previous message: Adam Spiers: "Re: 2.2.7 Oops on SMP machine in __free_page() while loading executable"
- Maybe in reply to: Davide Libenzi: "New semaphore __wake_up() implementation ..."