Re: [PATCH] semaphore fairness patch against test11-pre6

[Andrew Morton]

Christoph Rohland wrote:
> 
> Hi David,
> 
> David Mansfield <[e-mail]> writes:
> > If you can find the time to check this out more completely, I recommend
> > it, because it seems like a great improvement to be able to accurately
> > see vmstat numbers in times of system load.  I hope the other side
> > effects are beneficial as well :-)
> 
> I wanted to point out that there may be some performance impacts by
> this: We had exactly the new behaviour on SYSV semaphores. It led to
> very bad behaviour in high load situations since for high frequency,
> short critical paths this led to very high context switch rates
> instead of using the available time slice for the program.
> 
> We changed the behaviour of SYSV semaphores to the current kernel sem
> behaviour and never had problems with that change.
> 
> I still think that your change is right since this is kernel space and
> you do not have the notion of a time slice.

Has anyone tried it on SMP?  I get fairly repeatable instances of immortal
`D'-state processes with this patch.

The patch isn't right - it allows `sleepers' to increase without bound.
But it's a boolean!

If you cut out the unnecessary code and the incorrect comments from
__down() it looks like this:

void __down(struct semaphore * sem)
{
        struct task_struct *tsk = current;
        DECLARE_WAITQUEUE(wait, tsk);
        tsk->state = TASK_UNINTERRUPTIBLE;
        add_wait_queue_exclusive(&sem->wait, &wait);

        spin_lock_irq(&semaphore_lock);
        for (;;) {
                /*
                 * Effectively:
                 *
                 *      if (sem->sleepers)
                 *              sem->count++
                 *      if (sem->count >= 0)
                 *              sem->sleepers = 0;
                 *              break;
                 */
                if (!atomic_add_negative(sem->sleepers, &sem->count)) {
                        sem->sleepers = 0;
                        break;
                }
                sem->sleepers = 1;
                spin_unlock_irq(&semaphore_lock);

                schedule();
                tsk->state = TASK_UNINTERRUPTIBLE;
                spin_lock_irq(&semaphore_lock);
        }
        spin_unlock_irq(&semaphore_lock);
        remove_wait_queue(&sem->wait, &wait);
        tsk->state = TASK_RUNNING;
        wake_up(&sem->wait);
}

I spent a couple of hours trying to get "fairness" working right
and have not been able to come up with a non-racy solution.  That
semaphore algorithm is amazing.  I'm really impressed.