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

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

Davide Libenzi (davidel@maticad.it)
Fri, 11 Jun 1999 08:55:19 +0200

- Messages sorted by: [ date ][ thread ][ subject ][ author ]
- Next message: Alex Buell: "Re: 2.3.6 (mmap fails)"
- Previous message: V Ganesh: "Re: New semaphore __wake_up() implementation ..."
- Maybe in reply to: Davide Libenzi: "New semaphore __wake_up() implementation ..."
- Next in thread: Davide Libenzi: "Re: New semaphore __wake_up() implementation ..."

Hi andrea,

>>N = Number of tasks in runqueue
>>M = Number of tasks in semaphore queue
>>L = The cost of linear scan of wait queue of semaphore
>>W = The cost of a wakeup() operation
>>S = The cost of a schedule() search of next to run
>>
>>the total cost of a "up" operation is:
>>
>>TCo = L + M * W + (M - 1) * S
>
>The above is wrong. __wake_up in general only does a wake_up_process() for
>the number of tasks in the waitqueue.

The expression is correct, if You have M task in semaphore wait queue You
perform
M wakeups of which only one get the free way and other get immediately
scheduled.
Since:

TCo = L + M * W + (M - 1) * S

>
>>My new implementation release only the best suitable process to run,
>>resulting in a cost:
>
>The most suitable process to run in general is the last one inserted in
>the waitqueue even if is going to expire its timeslice because it has more
>probability to be still in cache. Anyway this is an issue only for
>TASK_EXCLUSIVE sleeps, if they are not EXCLUSIVE you _must_ wake up all
>tasks in the runqueue (in LIFO order too even if you won't be sure that
>the task that goes ahead will be the last running one). (really in some
>case like flock() probably it woud be better to do a FIFO wakeup but this
>is another issue)

My implementation do the same thing You obtain releasing all processes.
Actual code release all task and the goodness calculation in schedule() loop
get the last one in cache ( and SMP issue ):
...
if (p->processor == this_cpu)
weight += PROC_CHANGE_PENALTY;

if (p->mm == prev->mm)
weight += 1;
...

My code does the same thing without the extra cost of M wakeups and
(M - 1) schedule():

...
for (tmp = head->next; tmp != head; tmp = tmp->next) {
..
if (can_schedule(p)) {
int weight = goodness(current, p, this_cpu);
if (weight > c)
c = weight, next = p;
}
..

Anyway this is my code for __wake_up():

void __wake_up(wait_queue_head_t *q, unsigned int mode)
{
struct list_head *tmp, *head;
struct task_struct *next = NULL, *p;
int c = 0, this_cpu = current->processor;
unsigned int state;
unsigned long flags;

if (!q)
goto out;

wq_write_lock_irqsave(&q->lock, flags);

#if WAITQUEUE_DEBUG
CHECK_MAGIC_WQHEAD(q);
#endif

head = &q->task_list;
#if WAITQUEUE_DEBUG
if (!head->next || !head->prev)
WQ_BUG();
#endif
for (tmp = head->next; tmp != head; tmp = tmp->next) {
wait_queue_t *curr = list_entry(tmp, wait_queue_t,
task_list);

#if WAITQUEUE_DEBUG
CHECK_MAGIC(curr->__magic);
#endif
p = curr->task;
state = p->state;
if (state & mode) {
#if WAITQUEUE_DEBUG
curr->__waker = (long)__builtin_return_address(0);
#endif
if (state & TASK_EXCLUSIVE) {
next = p;
break;
}
/* Search the best one to run */
if (can_schedule(p)) {
int weight = goodness(current, p, this_cpu);
if (weight > c)
c = weight, next = p;
}
}
}
/* Found it ? */
if (next)
wake_up_process(next);
else {
/* Old way. Release all task !! */
for (tmp = head->next; tmp != head; tmp = tmp->next) {
wait_queue_t *curr = list_entry(tmp, wait_queue_t, task_list);

p = curr->task;
if (p->state & mode)
wake_up_process(p);
}
}
wq_write_unlock_irqrestore(&q->lock, flags);
out:
return;
}

Cheers,
Davide.

    --
    "Debian, the Freedom in Freedom."

    -
    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: Alex Buell: "Re: 2.3.6 (mmap fails)"
- Previous message: V Ganesh: "Re: New semaphore __wake_up() implementation ..."
- Maybe in reply to: Davide Libenzi: "New semaphore __wake_up() implementation ..."
- Next in thread: Davide Libenzi: "Re: New semaphore __wake_up() implementation ..."