lkml.org 
[lkml]   [1999]   [Aug]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
Subject[patch] wake-one FIFO semaphores
This patch will make the semaphore wakeup a FIFO wake-one wakeup.

Please note the comment at the top of the patch (the only delicate issue
wrt this wake-one change). The i386 arch is just fine in such respect.

I believe this is the right thing do to also considering that the current
wakeup is basically a LIFO wakeup in SMP (in UP instead it will take care
of the priority inversion issue: it will be the scheduler that will choose
the task to run). But as I anticipated above in SMP once we started the
first blocked process sleeping in the waitqueue (in the middle of
__wake_up), then such blocked process will _just_ run on the other CPU
while we continue to wakeup other tasks (plain LIFO).

So this is not only a performance improvement, but IMHO it's also an
enforcement to better avoid semaphore starvation in SMP systems.

Patch against 2.3.15-pre1:

diff -urN 2.3.15-pre1/kernel/sched.c 2.3.15-pre1-wakeonesem1/kernel/sched.c
--- 2.3.15-pre1/kernel/sched.c Fri Aug 20 17:43:24 1999
+++ 2.3.15-pre1-wakeonesem1/kernel/sched.c Sat Aug 21 16:42:30 1999
@@ -863,6 +863,14 @@
*
* Either form may be used in conjunction with "up()".
*
+ * NOTE NOTE: The tasks that are sleeping on a semaphore will be
+ * wakenup in a FIFO wake-one behaviour. For this reason
+ * waking_non_zero_interruptible() _must_ first check if it
+ * can grab the semaphore, and if so it must return successfully.
+ * _Only_ if the seamphore is still busy it can then check if
+ * there is a signal pending and fail _only_ in such case.
+ * All architectures must enforce this rule to avoid deadlocking
+ * with the wake-one wakeup.
*/

#define DOWN_VAR \
@@ -871,10 +879,7 @@
init_waitqueue_entry(&wait, tsk);

#define DOWN_HEAD(task_state) \
- \
- \
- tsk->state = (task_state); \
- add_wait_queue(&sem->wait, &wait); \
+ add_wait_queue_exclusive(&sem->wait, &wait); \
\
/* \
* Ok, we're set up. sem->count is known to be less than zero \
@@ -891,10 +896,11 @@
* Multiple waiters contend for the semaphore lock to see \
* who gets to gate through and who has to wait some more. \
*/ \
- for (;;) {
+ for (;;) { \
+ tsk->state = (task_state);

-#define DOWN_TAIL(task_state) \
- tsk->state = (task_state); \
+#define DOWN_TAIL() \
+ schedule(); \
} \
tsk->state = TASK_RUNNING; \
remove_wait_queue(&sem->wait, &wait);
@@ -902,18 +908,19 @@
void __down(struct semaphore * sem)
{
DOWN_VAR
- DOWN_HEAD(TASK_UNINTERRUPTIBLE)
+ DOWN_HEAD(TASK_UNINTERRUPTIBLE|TASK_EXCLUSIVE)
+
if (waking_non_zero(sem))
break;
- schedule();
- DOWN_TAIL(TASK_UNINTERRUPTIBLE)
+
+ DOWN_TAIL()
}

int __down_interruptible(struct semaphore * sem)
{
int ret = 0;
DOWN_VAR
- DOWN_HEAD(TASK_INTERRUPTIBLE)
+ DOWN_HEAD(TASK_INTERRUPTIBLE|TASK_EXCLUSIVE)

ret = waking_non_zero_interruptible(sem, tsk);
if (ret)
@@ -923,8 +930,8 @@
ret = 0;
break;
}
- schedule();
- DOWN_TAIL(TASK_INTERRUPTIBLE)
+
+ DOWN_TAIL()
return ret;
}

Continuing on the wake-one thing, IMHO in accept() we want a LIFO
behaviour (we don't care at all if some of the apache clients will sleep
forever... or better we _care_ that most of them will sleep all the time
;), so IMHO it doesn't make too much sense to wait for doing some real
workload to choose between LIFO and FIFO in such place. But the problem is
that it's not possible right now to implement a LIFO wakeup in accept(2)
due the current TASK_EXCLUSIVE implementation.

I agree that it's nice to stop browsing the waitqueue at the first
TASK_EXCLUSIVE task (so doing really a wakeup in O(1)), but doing so we
can't really do a LIFO wakeup without breaking in two parts the sk->sleep
waitqueue: one waitqueue for accept() with only EXCLUSIVE tasks inserted
in not exlusive order, and one separate for select().

Comments?

Andrea


-
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/

\
 
 \ /
  Last update: 2005-03-22 13:53    [W:0.382 / U:0.008 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site