Re: sched_find_first_bit()

[Shinpei Kato <shinny@j02.itscom.net>]

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/