文档介绍：Linux操作系统是一种能运行于多种平台、源代码免费公开、功能稳定强大、符合POSIX规范与Unix兼容的操作系统。它已经成功应用于巨型机、小型机、PC机直到嵌入式系统的广泛领域,成为windows操作系统强有力的竞争对手。
Linux操作系统支持多任务、多用户、多处理器。进程调度是所有支持多任务操作系统的关键部分, Linux操作系统具有一个高效优雅的基于优先级的进程调度器。,相对2. 4系列内核有很大的改进,特别在进程管理方面,,改进了进程调度算法,支持O(1)级调度算法[1]。本文就Linux 。
1  就绪进程队列
在linux中,每个CPU的就绪进程队列由一个struct  runqueue结构描述,其中最关键的子结构是优先级就绪数组。每个runqueue包含两个优先级就绪数组:active和expired数组。active 指向时间片没用完、当前可被调度的就绪进程,expired 指向时间片已用完的就绪进程。描述优先级就绪数组的数据结构是prio_array_t,定义为:
struct prio_array {
        int               nr_active;         /* number of tasks in the queues */
        unsigned long     bitmap[BITMAP_SIZE];  /* priority bitmap */
        struct list_head  queue[MAX_PRIO];      /* priority queues */
};
优先级就绪数组包含MAX_PRIO个队列queue,每个queue维护了一个就绪进程列表,这些进程具有相同的优先级。此外,prio_array还包含一个优先级位图(bitmap),用于快速定位优先级最高的进程。bitmap所有位的初始状态都是0,当一个优先级为N的进程变为TASK_RUNNING时,bitmap中对应的位N置1。此后内核可以通过调用sched_find_first_bit() 函数寻找第一个非空的就绪进程链表。 prio_array还包含一个nr_active变量用于记录该优先级就绪数组中进程的数目。
Runqueue结构中另两个重要的成员变量是best_expired_prio和expired_timestamp。前者记录expired 就绪进程组中的最高优先级,后者用来表征 expired 中就绪进程的最长等待时间。
2  task_struct结构
Linux用task_struct结构表示进程,。该结构记录了进程的重要信息,与进程调度有关的信息包括:
(1)state
进程状态由state成员变量表示。一个进程共有7种可能状态,分别是:TASK_RUNNING、TASK_INTERRUPTIBLE、TASK_UNINTERRUPTIBLE、TASK_STOPPED、TASK_TRACED、EXIT_ZOMBIE和EXIT_DEAD
(2)timestamp
进程发生调度事