2

我正在尝试了解 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）
Each priority array contains one queue of runnable processors per priority level.

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

然后它说

The priority arrays also contain a priority bitmap used to

高效地发现系统中优先级最高的可运行任务。

然后它说“有 140 个优先级和 32 位字，这是五个。”

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

以上是本书第 4 章的摘录，在第二个链接中发布，两者都包含相同的文本。为清楚起见，仅在此处发布。

* UPDATE1 * 基于评论我只是想澄清我在问作者说什么

BITMAP_SIZE 是无符号长类型变量数组必须为每个有效优先级提供一个位的大小。有 140 个优先级和 32 位字，这是五个。

问题 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) 时间内执行的进程。

4

1 回答 1

3

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

像这样的东西：

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
于 2013-01-07T18:25:25.537 回答