On Sun, 2003-12-07 at 10:44, Shinpei Kato wrote: > In 2.6, it seems to use "sched_find_first_bit()" function to find the > highest priority task. > This function calculates the index of the highest priority queue by > "array->bitmap" and it's definited in "bitops.h". > But I can't understand why it can return the index we want. > "array->bitmap" must be set by __set_bit() function. I see this function > just only set a bit. So, what relationship is between "__set_bit()" and > "sched_find_first_bit()". I mean how "array->bitmap" works to find the > highest priority task? I do not really understand the question. 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(). 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. > 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. They are an array of n linked list heads, for n total priorities on the system. Everything is O(1). Rob Love -- Kernelnewbies: Help each other learn about the Linux kernel. Archive: http://mail.nl.linux.org/kernelnewbies/ FAQ: http://kernelnewbies.org/faq/
