一、前言

在Linux操作系统中，进程调度是内核最核心的功能之一。CPU资源有限，而系统中同时存在大量进程，操作系统必须合理分配CPU时间片，决定哪个进程优先执行、何时切换进程。

在Linux2.6版本内核中，官方推出了O(1)调度算法，也是早期Linux经典的调度算法。该算法最大的亮点是：进程调度耗时为常数，不会随着系统进程数量增多而变慢。本文结合内核源码，通俗易懂拆解Linux2.6内核进程调度队列底层逻辑，吃透O(1)调度原理。

二、前置基础：进程切换与时间片

2.1 CPU上下文切换

CPU上下文切换也叫任务切换，是进程调度的底层基础。当内核需要切换进程时，会保存当前运行进程的CPU寄存器数据（上下文数据），存入进程自身堆栈；再将下一个进程的上下文数据从堆栈加载到CPU寄存器，完成进程切换。

简单来说：保存旧进程状态、加载新进程状态，就是上下文切换。

2.2 时间片机制

Linux是分时操作系统，系统会给每一个进程分配固定的时间片（计数器）。当进程时间片耗尽，操作系统会强制将该进程从CPU剥离，调度新进程执行，保证多进程并发运行。

三、调度核心：运行队列runqueue

3.1 runqueue核心规则

在Linux2.6内核中，每一个CPU核心，都拥有独立的runqueue（运行队列）。所有待运行的进程，都会被挂载到对应CPU的运行队列中。

如果是多CPU服务器，内核还会额外做负载均衡，避免某一个CPU队列进程过多，导致调度压力失衡。

3.2 runqueue内核源码结构

runqueue在内核中用struct rq结构体描述，也是O(1)调度算法的核心载体，课件中原版源码如下：

struct rq {
    spinlock_t lock;
    /*
    * nr_running and cpu_load should be in the same cacheline because
    * remote CPUs use both these fields when doing load calculation.
    */
    unsigned long nr_running;
    unsigned long raw_weighted_load;
#ifdef CONFIG_SMP
    unsigned long cpu_load[3];
#endif
    unsigned long long nr_switches;
    /*
    * This is part of a global counter where only the total sum
    * over all CPUs matters. A task can increase this counter on
    * one CPU and if it got migrated afterwards it may decrease
    * it on another CPU. Always updated under the runqueue lock:
    */
    unsigned long nr_uninterruptible;
    unsigned long expired_timestamp;
    unsigned long long timestamp_last_tick;
    struct task_struct *curr, *idle;
    struct mm_struct *prev_mm;
    struct prio_array *active, *expired, arrays[2];
    int best_expired_prio;
    atomic_t nr_iowait;
#ifdef CONFIG_SMP
    struct sched_domain *sd;
/* For active balancing */
    int active_balance;
    int push_cpu;
    struct task_struct *migration_thread;
    struct list_head migration_queue;
#endif
#ifdef CONFIG_SCHEDSTATS
    /* latency stats */
    struct sched_info rq_sched_info;
/* sys_sched_yield() stats */
    unsigned long yld_exp_empty;
    unsigned long yld_act_empty;
    unsigned long yld_both_empty;
    unsigned long yld_cnt;
/* schedule() stats */
    unsigned long sched_switch;
    unsigned long sched_cnt;
    unsigned long sched_goidle;
/* try_to_wake_up() stats */
    unsigned long ttwu_cnt;
    unsigned long ttwu_local;
#endif
    struct lock_class_key rq_lock_key;
};

/*
 * These are the runqueue data structures:
 */
struct prio_array {
    unsigned int nr_active;
    DECLARE_BITMAP(bitmap, MAX_PRIO+1); /* include 1 bit for delimiter */
    struct list_head queue[MAX_PRIO];
};

其中最关键的两个成员：active（活动队列指针）、expired（过期队列指针），也是O(1)算法的精髓所在。

四、进程优先级分级规则

Linux2.6内核将进程优先级划分为两大类别，总共140个优先级，优先级数值越小，进程执行权限越高：

1. 实时优先级：0 ~ 99，用于实时任务，优先级极高，普通用户无法修改；

2. 普通优先级：100 ~ 139，我们日常运行的程序、手动创建的进程都属于该级别，可通过nice值调整优先级。

补充知识点：nice值取值范围为-20 ~ 19，nice值越小，进程优先级越高；优先级计算公式：PRI(new)=PRI(old)+nice。

五、结合结构图：双队列底层架构

前文提到runqueue运行队列中存在活动、过期双队列，结合插入的内核结构图，我们可以直观看透底层存储关系：内核并不是单独定义两个队列，而是依靠 arrays[2] 数组维护双队列，这也是图片中最核心的结构。

在struct rq结构体中存在关键成员：struct prio_array_t *active, *expired, arrays[2];，所有调度队列全部依托该数组实现。

5.1 arrays[2]数组：活动队列与过期队列载体

arrays[0] = 活动队列（active）：图片中标识为active，专门存放时间片未消耗完的就绪进程。active指针永远指向arrays[0]，作为当前正在调度的工作队列。

arrays[1] = 过期队列（expired）：图片中标识为expired，专门存放时间片耗尽的进程。expired指针永远指向arrays[1]，等待后续重新分配时间片。

简单总结：arrays数组是容器，下标0存活跃进程，下标1存过期进程，active、expired指针负责标记区分。

5.2 prio_array：队列内部三大核心成员

不管是arrays[0]活动队列，还是arrays[1]过期队列，本质都是prio_array_t优先级数组，图片清晰展示了它的三大核心成员，缺一不可。

5.3 优先级数组prio_array

5.2.1 nr_active：进程计数器

图片中每个队列上方都标注了nr_active，它的作用非常简单直白：记录当前队列内，一共有多少个就绪进程。只要有进程入队，nr_active自增；进程调度结束出队，nr_active自减，内核可快速判断队列是否为空。

5.2.2 bitmap[5]：快速检索位图

图片中明确画出bitmap[5]位图数组，这是O(1)算法提速关键。bitmap是一个长度为5的位图数组（5×32bit=160位），专门映射下方140条优先级队列。每一个比特位，对应一条优先级队列：比特位为1，代表该队列存在进程；为0则队列为空。内核通过硬件位运算，快速跳过空队列，精准定位有进程的优先级队列。

5.2.3 queue[140]：进程链表数组

queue是长度为140的链表数组，完全对应Linux的140个进程优先级。数组下标 = 进程优先级，下标越小优先级越高。相同优先级的进程，以双向链表形式挂载在同一个queue位置，遵循FIFO先进先出规则排队。

struct prio_array {
unsigned int nr_active;        // 当前队列就绪进程总数
DECLARE_BITMAP(bitmap, MAX_PRIO+1); // 位图，快速检索非空队列
struct list_head queue[MAX_PRIO];   // 140条优先级进程链表
};

结合图片做层级总结（由外到内）：runqueue → arrays[2]双队列 → prio_array → nr_active计数/bitmap位图/queue进程链表。

• queue[MAX_PRIO]：长度为140的进程链表数组，数组下标对应进程优先级；

• bitmap：位图标记，用于快速判断队列是否为空，是实现O(1)调度的关键。

六、进程查找+完整轮换流转机制

基于图片结构，我们拆分两大核心流程：一是内核如何快速查找要执行的进程，二是进程如何在双队列中轮换，彻底吃透调度逻辑。

6.1 进程查找流程（bitmap → queue）

1. 第一步：判断队列状态：读取活动队列arrays[0]的nr_active，若为0说明无就绪进程，直接切换队列；

2. 第二步：bitmap位图筛选：遍历bitmap[5]位图，从低位向高位检索，找到第一个置1的比特位，锁定最高优先级的非空队列；

3. 第三步：queue链表取进程：根据位图定位的下标，进入queue[140]对应链表，取出队首进程；

4. 第四步：CPU执行：将该进程加载至CPU运行，完成一次调度。

6.2 位图规则

位图中每一个比特位，对应一个优先级队列：比特位为1，代表该优先级队列存在进程；比特位为0，队列为空。

6.3 查找流程

1. 从bitmap低位开始遍历，找到第一个置1的比特位；

2. 该比特位下标，对应最高优先级的非空队列；

3. 取出队列队首进程，直接调度执行。

位图查找是硬件级位运算，执行速度极快，固定耗时，这也是算法能做到O(1)的核心原因。

6.4 进程完整轮换流程

这是图片最核心的流转逻辑，所有进程严格遵循 活动队列运行 → 时间片耗尽 → 移入过期队列 → 指针互换 → 重新运行 的轮换闭环：

1. 进程入驻：新建进程依据优先级，挂载到arrays[0]活动队列的对应queue链表中，nr_active计数+1；

2. CPU运行：内核通过bitmap+queue找到进程，分配CPU时间片执行；

3. 队列迁移：进程时间片耗尽从CPU取出，内核将该进程从arrays[0]剥离，移入arrays[1]过期队列，等待重置时间片；

4. 指针切换：当arrays[0]活动队列所有进程全部耗尽时间片、nr_active变为0时，内核不做数据拷贝，仅交换指针：active指向arrays[1]，expired指向arrays[0]；

5. 循环轮换：原过期队列arrays[1]变为新活动队列，进程重新获得时间片、参与调度；原空队列arrays[0]变为过期队列，承接下一轮耗尽时间片的进程。

随着进程不断执行，活动队列的进程会慢慢耗尽时间片，全部移入过期队列，此时活动队列为空。常规思路需要遍历过期队列重新排序，开销极大，而Linux2.6采用极简优化：直接交换active和expired指针。

6.5 交换逻辑

1. 活动队列所有进程时间片耗尽，队列清空；

2. 内核交换active指针与expired指针；

3. 原过期队列变为新的活动队列，重新参与调度；

4. 原活动队列清空，作为新的过期队列，等待存放耗尽时间片的进程。

6.6 指针交换核心优势

图片中两个队列结构完全一致，指针交换仅修改active、expired的内存指向，无需拷贝进程、无需遍历排序。哪怕系统存在上百个进程，切换开销也恒定不变，这就是O(1)算法的精髓。

七、O(1)调度算法完整调度流程

1. 进程挂载：新建进程根据自身优先级，挂载到CPU运行队列的活动队列对应链表中；

2. 进程选取：通过bitmap位图快速找到最高优先级非空队列，取出队首进程占用CPU；

3. 时间片消耗：进程运行消耗时间片，时间片未耗尽则留在活动队列；

4. 队列迁移：进程时间片耗尽，被移入过期队列；

5. 指针切换：活动队列为空时，交换active、expired指针，重复调度流程。

八、两个问题

1. 如何修改优先级？

在Linux2.6 O(1)调度算法中，正在活动队列中运行的进程，禁止直接实时修改优先级。如果一个进程当前处于活动队列、优先级为80，需要修改为81，内核采用延后修改、过期生效的机制，不会打断本次进程执行。

具体修改流程：

1. 本次执行不改动：该进程依旧以优先级80留在活动队列，正常占用CPU执行当前时间片，内核不会中途修改它的优先级、不会打断进程运行；

2. 预先写入修正标记：用户通过命令或 setpriority() 函数，给该进程的PCB中添加一个nice修正值，仅做标记，此刻优先级不会发生任何变化；

3. 时间片耗尽迁移：待该进程时间片消耗完毕，会遵循调度规则，从活动队列移入arrays[1]过期队列；

4. 过期队列刷新优先级：内核在过期队列中统一重置进程时间片，根据公式PRI(new) = PRI(old) + nice，结合提前写入的nice值，将该进程优先级从80刷新修改为81；

5. 下次调度生效：等到双队列指针互换，该进程重回活动队列时，以新优先级81参与调度。

• nice取值范围：-20 ~ 19；

• nice值越小，新PRI越小，进程优先级越高；

核心总结：O(1)调度不允许活动队列动态改优先级，执行期间打nice标记、过期队列更新优先级、下一轮调度生效。

2. O(1)调度算法如何解决进程饥饿问题？

进程饥饿：低优先级进程一直得不到CPU执行权限，长期被高优先级进程抢占资源，永久无法执行。

Linux2.6 O(1)算法依靠双队列轮换机制完美解决饥饿，核心原理：

1. 所有进程都会分配固定时间片，时间片耗尽后，无论优先级高低，一律被移入expired过期队列；

2. 当活动队列为空时，内核直接指针互换，过期队列转正为活动队列；

3. 内核会统一给过期队列中所有进程重新分配时间片，低优先级进程也能获得执行机会；

4. 不存在高优先级进程永久霸占CPU的情况，所有进程公平轮换，彻底杜绝饥饿。

一句话总结：时间片强制回收 + 双队列平等轮换，是O(1)算法防饥饿的核心。