Messages in this thread Patch in this message | | | Date | Sat, 21 Aug 1999 17:03:33 +0200 (CEST) | From | Andrea Arcangeli <> | 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/
| |