Thank you for your rapid reply.
> I do not really understand the question.
I'm sorry for my poor english.
> Five basic things here:
>
> - array->bitmap is an n-bit bitmap where n is the number of
> priority levels on the system
>
> - set_bit() sets a bit in the bitmap
>
> - clear_bit() clears a bit in the bitmap
>
> - sched_find_first_bit() returns the bit number of the first
> set bit
>
> - if the k-th bit is set, then there is a runnable task at
> priority k
>
> So when a task becomes runnable, set_bit() is used to set the
> corresponding bit. This is called from enqueue_task(). When there are
> no longer any runnable tasks at a given priority, clear_bit() is called
> to clear the bit. This is called from dequeue_task().
Your description is easy to understand. But what I can't understand is
sched_find_first_bit(). It is as follows.
static inline int sched_find_first_bit(const unsigned long *b)
{
if (unlikely(b[0]))
return __ffs(b[0]);
if (unlikely(b[1]))
return __ffs(b[1]) + 32;
if (unlikely(b[2]))
return __ffs(b[2]) + 64;
if (b[3])
return __ffs(b[3]) + 96;
return __ffs(b[4]) + 128;
}
You said sched_find_first_bit() returns the bit number of the first set
bit. But I can't understand how this function works. __ffs() returns the
first set bit, doesn't it?
> The goal of the scheduler is to run the highest priority runnable task
> with timeslice remaining. So sched_find_first_bit() on the active array
> returns that priority number.
>
> That number is then used to index into the priority array, to find the
> link list of runnable tasks of that priority. The task at the head of
> the list is the guy to run.
Although my understanding had been vague, it got clear. Thanks.
> > Additionally, the kernel 2.6 scheduler, so-called O(1) scheduler, is
> > said to have two priority-ordered queues, active & expired.
> > But I see they're not priority-ordered queues because we use Bitmap to
> > find the highest priority task. What do you think about it?
>
> They are "priority arrays" not "priority-ordered queues". In reality,
> they are actually queues of queues. Look at struct prio_array ::
> kernel/sched.c.
I see. I've read in http://www.ussg.iu.edu/hypermail/linux/kernel/0201.0/0810.html
that these queues are priority-ordered. But it might have been changed.
Now I could correct my missunderstanding.
> They are an array of n linked list heads, for n total priorities on the
> system.
>
> Everything is O(1).
>
> Rob Love
>
>
Regards,
Shinpei Kato
--
Kernelnewbies: Help each other learn about the Linux kernel.
Archive: http://mail.nl.linux.org/kernelnewbies/
FAQ: http://kernelnewbies.org/faq/
