c - 了解Linux内核中的优先级数组

Question

我试图了解Linux内核的调度程序是如何工作的

如该链接所示

http://books.google.co.in/books?id=NXVkcCjPblcC&lpg=PP1&pg=PA47#v=onepage&q&f=false 和以下链接 http://www.informit.com/articles/article.aspx?p=101760&seqNum=2

struct runque 是调度程序运行的基本数据结构

是

struct runqueue {
    spinlock_t     lock;        /* spin lock which protects this
                                   runqueue */
    unsigned long    nr_running;     /* number of runnable tasks */
    unsigned long    nr_switches;     /* number of contextswitches */
    unsigned long    expired_timestamp;  /* time of last array swap */
    unsigned long    nr_uninterruptible; /* number of tasks in
                                               uinterruptible sleep */
    struct task_struct *curr;        /* this processor's currently
                                      running task */
    struct task_struct *idle;        /* this processor's idle task */
    struct mm_struct  *prev_mm;      /* mm_struct of last running task
                                      */
    struct prio_array  *active;       /* pointer to the active priority
                                        array */
    struct prio_array  *expired;      /* pointer to the expired
                                         priority array */
    struct prio_array  arrays[2];      /* the actual priority arrays */
    int         prev_cpu_load[NR_CPUS];/* load on each processor */
    struct task_struct *migration_thread;  /* the migration thread on this
                                              processor */
    struct list_head  migration_queue;   /* the migration queue for this
                                             processor */
    atomic_t      nr_iowait;      /* number of tasks waiting on I/O
                                   */
}

上面有两个成员

struct prio_array  *active;       /* pointer to the active priority
                                    array */
struct prio_array  *expired;      /* pointer to the expired priority array */

struct prio_array 定义为

struct prio_array {
    int        nr_active;      /* number of tasks */ 
    unsigned long   bitmap[BITMAP_SIZE]; /* priority bitmap */
    struct list_head queue[MAX_PRIO];   /* priority queues */
};

我不太清楚下面的句子

问题 1)
每个优先级数组包含每个优先级的一个可运行处理器队列。

在上面的struct prio_array定义中可运行处理器的队列在哪里

然后它说

The priority arrays also contain a priority bitmap used to  

efficiently discover the highest priority runnable task in the system.

然后它说 “如果有 140 个优先级和 32 位字，则为 5 个。”

这个是五的结论是怎么得出的？背后有什么数学计算？

以上内容是本书第 4 章的摘录，在第二个链接中发布，两者包含相同的文本。为了清楚起见，只是将其发布到此处。

*更新1 * 根据评论我只是想澄清我的要求 作者说

BITMAP_SIZE is the size that an array of unsigned long typed variables would have to be to provide one bit for each valid priority level. With 140 priorities and 32-bit words, this is five.

问题 2)
我不清楚的是，每个优先级给出一位，并且有 140 个优先级，那么数组大小是怎么来的 5 我没有得到 BITMAP_SIZE 计算的逻辑，而不是 140/32=5

它与下面的段落有关

    When a task of a given priority becomes runnable (that is,  
 its state becomes TASK_RUNNING), the corresponding bit in the 
bitmap is set to one. For example, if a task with priority seven is 
runnable, then bit seven is set

在链接上，这是数组

 unsigned long   bitmap[BITMAP_SIZE]; /* priority bitmap */

已设置，所以基本上我不清楚的是该数组是如何设置的，如果我能够正确解释，请参阅问题 1。

更新2和下面答案的解释

对于下面的答案，我只是添加一个小解释，它可能会对将来的某些人有所帮助 如果他们基本上都来这里

调度程序维护一个运行队列和可运行进程的列表，每个可运行进程都位于一个运行队列上，我给出的链接文章考虑了具有许多运行队列的多处理器系统，回到我们使用一个处理器和一个运行队列的情况具有不同优先级的进程

有140个优先级，每个优先级在TASK_RUNNING状态下有不同的进程，例如可以有很多优先级为8的进程等等(我以8为例) struct runque 指向优先级数组，它告诉

btimap[BITMAP] /* this is the priority level 
struct list_head /* points to the start of list of processes of that run level

因此 runque 指向优先级数组，从优先级数组中您可以轻松获取进程 需要在 O(1) 时间内执行。

Answer 1

您是在问如何在数组中找到正确的位吗？

类似这样的事情:

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