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

# Re: New schedule() and semaphore implementation ...

Andrea Arcangeli (andrea@suse.de)
Sat, 12 Jun 1999 15:29:55 +0200 (CEST)

- Messages sorted by: [ date ][ thread ][ subject ][ author ]
- Next message: Steven N. Hirsch: "2.2.9-ac5 fix for smbfs"
- Previous message: Andrea Arcangeli: "Re: [PATCH] some 2.3.6 fixes"
- In reply to: Davide Libenzi: "Re: New schedule() and semaphore implementation ..."

On Sat, 12 Jun 1999, Davide Libenzi wrote:

>I'm not so sure about the semaphore one, in which my patch does exactly
>the same thing with a much lower overhead ( on a semaphore queue can sleep

It does _not_ the same thing. You don't know at wakeup time which will be
the CPU that will get the task. You don't know which will be its prev->mm.

>1) As I've sad before it does the same thing in _1_ wakeup and not
> in N wakeups and N-1 schedule()

This is true also using FIFO.

>2) It applies the same scheduling decisions of schedule(), without
> wake_one(), wake_first(), wake_last_before(), TASK_EXCLUSIVE ...
> and other things like this. It simply wake up the best in the
> schedule() sense.

(2) is not true. It may be close to the real best task though.

>3) It gives a chance to _every_ task waiting to exit from the queue,
> accumulating task's counter during the schedule() recharge loop.
> And Alan, even if sys5 gives no starvation guarantees for semaphores,
> why we can't do better ?

You can avoid starvation even with FIFO behaviour. BTW I noticed now that
currently (in 2.3.6) we are doing a _FIFO_ wakeup even in accept(2) (my
2.2.x patch was doing LIFO in accpet(2) instead). the EXCLUSIVE tasks
sleeping in accept(2) instead _must_ be wakenup in a LIFO behaviour.
There's no starvation issue with accept and with LIFO we'll get a sure
better caching behaviour. Is somebody going to fix this problem? (I can do
that myself otherwise). I think we have two options:

1) add two waitqueues in the network layer, one for select() and one for
accept(), then replace the add_wait_queue_exclusive with add_wait_queue
in the wait_for_connect().
2) the other option is to add a secondary lists in the waitqueue, so
then we'll be able to choose between putting task at the top or at the
bottom of the list, even when we must support a wake-all in the same
waitqueue (as in accept(2)).

>This is for Andrea:
>>Also consider that you don't know which will be the CPU
>>(and its prev task) that will reschedule the task blocked in the semaphore
>>so the goodness may be not completly relialable (the wakenup task may be
>>rescheduled from the other CPU before you'll exit from your sem_wake_up).
>
>I forgot to add a runqueue_lock in __sem_wake_up().

You still don't know which will be the CPU that will reschedule the task.
When you do spin_unlock then the other CPU will enter in schedule before
you, even if you'll schedule someway a bit after the wake_up (and it's
not obvious that you'll schedule after the wake_up).

Andrea Arcangeli

PS. Now I am running with the FIFO wakeup in the seamphores (previous
patch with add_wait_queue_exclusive() instead of add_wait_queue()) and
it's running fine.

-
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: Steven N. Hirsch: "2.2.9-ac5 fix for smbfs"
- Previous message: Andrea Arcangeli: "Re: [PATCH] some 2.3.6 fixes"
- In reply to: Davide Libenzi: "Re: New schedule() and semaphore implementation ..."