On Sun, 2003-12-07 at 11:53, Shinpei Kato wrote:
> I'm sorry for my poor english.
Do not apologize :)
> 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?
Ah, OK. This is a simple misunderstanding.
The reason sched_find_first_bit() is so complicated looking is that
__ffs() only does a find-first-set on a word. It is actually an x86
instruction, so it is very fast. But then we have to do it for each
word.
So the above code is quite optimized. It translates into good assembly.
Basically, the if statements check if _any_ bit in the word is set. If
a bit is set, then we call __ffs() on that word. Otherwise, we move on.
> 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.
Well, the queues INSIDE the array are kept by priority. It is hard to
explain the relationship in text. I wrote a book that goes over the
O(1) scheduler in considerable depth and includes diagrams, "Linux
Kernel Development", SAMS, September 2003.
Basically, you have the two priority arrays, active and expired, per
processor.
Inside of those priority arrays is an array of N list_head (heads of
linked lists), for the N total priorities on the system. Each of those
list heads corresponds to one priority level. It is kept sorted FIFO,
so that the item at the head of the list is the first to run at that
priority.
Looking at the source helps a lot.
Hope this helps.
My best,
Rob Love
--
Kernelnewbies: Help each other learn about the Linux kernel.
Archive: http://mail.nl.linux.org/kernelnewbies/
FAQ: http://kernelnewbies.org/faq/
