@[TOC](Linux O(1)调度算法详解)

1. 双链表结构重新设计

在Linux内核中，进程控制块task_struct的组织方式采用了独特的双链表设计：

struct link
{
    struct link* next;
    struct link* prev;
};

struct task_struct
{
    // 进程的各种属性
    struct link node;
    // ...
};

这种设计的核心思想是：数据不再存储在link结构体中，而是存储在task_struct中，link仅负责指向下一个task_struct中的node成员地址。

技术要点：

1. 通过偏移量访问成员：已知link的地址后，可以通过偏移量计算出task_struct的地址。具体方法为：&((struct task_struct*)0->node)计算出偏移量，然后结合&node，即可求出struct task_struct的地址，从而直接访问其成员。

2. 设计优势：

   • 统一管理：Linux内核将所有进程的task_struct统一组织在双链表中。
   • 灵活性：task_struct不仅可以放在双链表中，还可以同时存在于运行队列、阻塞队列等多种数据结构中。
   • 通用性：这种双链表设计可以重用于红黑树、哈希表、二叉树等其他数据结构。

2. 调度队列设计

每个CPU都有一个调度队列：struct runqueue。

在runqueue中，有一个queue数组，可以理解为struct task_struct queue[140]。这个队列的设计如下：

• 索引0-99：用于实时进程（必须执行完毕才能切换到下一个进程），通常不关注
• 索引100-139：用于分时进程，与nice值（-20到19）的范围一一对应，映射关系为：PRI(实时)+40放到queue队列的对应位置

优先级处理机制：

• 如果优先级相同，可以在queue对应位置设计成链表结构
• 核心结论：优先级数字本质上是数组下标
• 根据优先级选择进程的过程，本质上是一个哈希查找过程
• 一旦确定目标队列，剩余的就是FIFO（先进先出）调度

查找最高优先级进程的方法：

1. 遍历法：从100到139遍历，判断哪个位置不为空，第一个非空位置即为最高优先级
2. 位图法：使用比特位表示队列状态（0表示空，1表示有进程），通过位运算快速查找
   • 可以8位一组进行检查，提高查找速度
   • Linux使用bitmap实现位图：long bitmap[5]（long为4字节，4×8×5=160>140，足以表示所有队列状态）

队列状态记录：

• nr_active：记录队列中的进程数量
• 上述三个组件共同构成struct prio_array_t优先级结构体：

struct prio_array_t
{
    queue[140];
    bitmap[5];
    nr_active;
};

这种设计实现了O(1)时间复杂度的进程查找。

问题1：进程饥饿问题

场景：如果有一个优先级为61的进程，后续到达的进程优先级都是60，那么61进程是否永远无法被调度？（即进程饥饿问题：高优先级进程优先调度，但低优先级进程也需要获得调度机会）

解决方案：双队列设计

在runqueue中，有两个完全相同的优先级结构体：

struct prio_array_t[2]
{
    queue[140];
    bitmap[5];
    nr_active;
};

• array[0]：活跃队列（active queue）
• array[1]：过期队列（expired queue）
• 两个指针：
  • *active：指向array[0]
  • *expired：指向array[1]

工作流程：

1. CPU调度时只查看active指针指向的队列
2. CPU调度完一个进程后，将该进程根据其优先级插入到过期队列中
3. 活跃队列中的进程越调度越少，直到为空
4. 执行swap(&active, &expired)交换指针
5. 新到达的进程都先放入过期队列，等到下一次swap时才体现其优先级

这种设计有效避免了明显的进程饥饿问题。

问题2：优先级动态更改问题

问题：当进程优先级从80改为81时，不仅需要修改nice值，还需要在调度队列的queue中改变该进程的位置。如何实现？

解决方案：在队列交换过程中重新定位

当进程被调度后，在两个队列进行交换的过程中，系统会检查进程的nice值，并根据新的nice值重新确定该进程在队列中的位置。

补充：抢占机制

抢占是指系统可以强制中断当前正在运行的进程，将CPU使用权收回并分配给其他更高优先级或更紧急的进程。

抢占过程：

1. 中断当前进程：强制暂停当前正在CPU上运行的进程
2. 保存上下文：将该进程的当前状态（程序计数器、寄存器值等）完整保存到其进程控制块（PCB）中，以便后续从断点恢复执行
3. 选择新进程：根据调度算法（如优先级、时间片轮转等）从就绪队列中选择一个新进程
4. 恢复上下文：将新进程之前保存的上下文状态加载到CPU寄存器中
5. 开始执行：将CPU控制权交给新进程，使其开始或继续运行

总结：上述就是Linux O(1)调度算法的核心原理和实现机制。