Understanding the linux scheduler
I am new to linux kernel and low level programming. I wanted to know how linux scheduler is supposed to be O(1) in time complexity.
I came across the following article which is very informative but I have a problem understanding the pargraph I have reproduced below http://www.ibm.com/developerworks/linux/library/l-scheduler/
The job of the scheduler is simple: choose the task on the highest priority list to execute. To make this process more efficient, a bitmap is used to define when tasks are on a given priority list. Therefore, on most architectures, a find-first-bit-set instruction is used to find the highest priority bit set in one of five 32-bit words (for the 140 priorities). The time it takes to find a task to execute depends not on the number of active tasks but instead on the number of priorities. This makes the 2.6 scheduler an O(1) process because the time to schedule is both fixed and deterministic regardless of the number of active tasks.
Why 5 words of 32 bits for 140 queues ? Who the find-first-bit-set instruction helps to select one of the 140 queues ?
A bit field uses a single value to represent a number of boolean states, for example if we were using an 8 bit integer then we might say that:
17 (decimal) = 00010001 (binary)
Which would indicates that the 4th and 8th boolean values are true, where all other boolean values are false. In total 8 boolean states can be tracked as there are 8 bits.
As we wish to track 140 states (1 for each queue, true indicating that queue contains a task), 140 bits are required, and so as 140 / 32 = 4.375, we need at least 5 32 bit integers to store all boolean states.
Something like this:
int bitmap_idx = priority/BITS_PER_WORD;
int bitmap_bit = priority%BITS_PER_WORD;
isSet = ( bitmap[bitmap_idx]&(1<<bitmap_bit) ); //test
bitmap[bitmap_idx] |= 1<<bitmap_bit; //set
is used to reach the particular process with priority array and this is how bitmaps are used in scheduler which in turns depends upon struct prio_array
The article you pointed out is outdated check this one http://www.informit.com/articles/article.aspx?p=101760&seqNum=2
链接地址: http://www.djcxy.com/p/84790.html下一篇: 了解Linux调度程序