Understanding the linux scheduler

Question

I am new to the Linux kernel and low-level programming. I would like to know how the linux scheduler should be O (1) in time complexity.

I came across the following article, which is very informative, but I have a problem understanding the graph that I reproduced below. http://www.ibm.com/developerworks/linux/library/l-scheduler/

The task of the scheduler is simple: select the task at the highest level, a list of priorities to be completed. To make this process more efficient, bitmap is used to determine when tasks are in a given priority list. Therefore, on most architectures, a search-based instruction with the first bit is used to search for the bit with the highest priority, set in one of five 32-bit words (for 140 priorities). The time required to complete the task does not depend on the number of active tasks, but on the number of priorities. This makes scheduler 2.6 the O (1) process, since the time on the schedule is fixed and deterministic, regardless of the number of active tasks.

Why 5 words of 32 bits for 140 queues? Who does the find-first-bit-set command help select one of 140 queues?

Answer 1

The bit field uses a single value to represent several Boolean states, for example, if we used an 8-bit integer, then we can say that:

17 (decimal) = 00010001 (binary) 

Which will mean that the 4th and 8th Boolean values ​​are true, where all other logical values ​​are false. Only 8 Boolean states can be traced since there are 8 bits.

As we want to track 140 states (1 for each queue, a truth indicating that the queue contains the task), 140 bits are required, and since 140/32 = 4.375, we need at least 5 32-bit integers to store all Boolean states .

Answer 2

Something like that:

 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 

used to access a specific process using an array of priorities, and that is how bitmaps are used in the scheduler, which in turn depends on the structure of prio_array

You indicated that an outdated article is checking this http://www.informit.com/articles/article.aspx?p=101760&seqNum=2