> > 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! Can I ask one more thing. Look at following codes.
++++
#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
struct prio_array {
int nr_active;
unsigned long bitmap[BITMAP_SIZE];
struct list_head queue[MAX_PRIO];
};
++++
The default MAX_PRIO is defined 140 and if we assume the size of long is
32 bits, BITMAP_SIZE comes to be ((((140+1+7)/8)+4-1)/4)) = 5. So a
range of b[0] to b[4] is related to MAX_PRIO, isn't it?
> > 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.
Oh really? I suppose I should buy it.
> 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.
Ok. In this point, the way of task priority management came to be very
clear for me. As for remainning parts, I'll try to understand by myself
with sources. Nontheless I'll be unable to understand, please forgive me
to ask again.
> Looking at the source helps a lot.
Certainly.
Thank you for your sharing your time to explain details.
Regards,
Shinpei Kato
--
Kernelnewbies: Help each other learn about the Linux kernel.
Archive: http://mail.nl.linux.org/kernelnewbies/
FAQ: http://kernelnewbies.org/faq/
