冯・诺依曼体系结构

• 冯・诺依曼体系结构，1946 年由冯・诺依曼提出，是现代所有通用电子计算机的统一硬件设计标准。
• 从个人电脑、笔记本、服务器，到手机、嵌入式 Linux 设备，全部遵循该架构设计。
• 它统一规定了：计算机硬件组成、数据存储形式、程序运行规则、硬件交互逻辑，是操作系统、进程、内存管理一切软件运行的硬件前提。

冯・诺依曼五大核心硬件组件

1. 运算器
   核心作用：完成算术运算（加减乘除）、逻辑运算（与或非、比较、判断）。

2. 控制器
   核心作用：计算机的「总指挥」。
   解析内存中的程序指令、控制硬件时序、调度五大部件协同工作、决定 CPU 下一步执行什么操作。

3. 存储器（重点：特指内存 / 主存）
   核心特性：
   1.临时存储：存放运行中的程序指令 + 待处理 / 运算完成的数据；
   2.高速中转：CPU 唯一直接交互的存储设备；
   3.断电丢失：内存是易失性存储。

4. 输入设备
   功能：将外部信息转换为计算机可识别的二进制数据，写入内存。
   举例：键盘、鼠标、网卡、扫描仪、磁盘（读数据时）。

5. 输出设备
   功能：将内存中的运算结果，转换为人 / 外部设备可识别的形式。
   举例：显示器、音响、网卡、打印机、磁盘（写数据时）。

存储程序原理

1. 程序和数据统一存放在内存中；
2. 程序运行前，必须从外存（磁盘）加载到内存；
3. CPU 从内存读取指令、执行程序。

• 中央处理器（CPU）由运算器和控制器共同组成。
• CPU在数据层面，只和内存打交道，外存只和内存打交道。
• 现代计算机没有推翻该体系，只是在原有基础上改良：引入了多级缓存（L1/L2/L3 Cache），缩小 CPU 与内存的速度差距。

硬件交互核心逻辑

速度层级差异

速度从快到慢：CPU 寄存器 > 内存 > 磁盘 / 外设
CPU 速度远超外设（键盘、磁盘、网卡），相差上万倍。

核心交互规则

CPU 永远只和内存直接交互，绝不直接访问外设（磁盘、网卡、键盘）
完整数据流转全流程：

1. 输入设备 → 数据写入内存；
2. CPU 从内存读取数据 / 指令，进行运算；
3. 运算结果写回内存；
4. 内存 将数据刷新到输出设备 / 外存。

操作系统

概念

操作系统（Operating System，简称 OS）是一款管控计算机软硬件全部资源、提供程序运行环境、为用户 / 应用提供操作接口的大型系统软件。

广义操作系统 & 狭义操作系统

操作系统严格分为狭义操作系统、广义操作系统。

• 狭义操作系统 特指：操作系统内核（Kernel）
  核心组成与功能：进程管理、内存管理、文件管理、设备管理、权限 & 安全管理

• 广义操作系统 = 狭义操作系统（内核） + 系统外壳（Shell) + 硬件驱动 + 系统工具（ls、cd等命令行工具、系统管理软件） + 基础库 + 实用程序

设计OS的目的

• 对下，统一管理软硬件资源，提高资源利用率。
• 为上层应用程序提供独立、稳定的运行环境。
• 屏蔽底层硬件差异，简化用户与开发的使用门槛。

计算机软硬件层状体系结构

计算机软件 + 硬件并不是杂乱拼接，而是严格遵循自上而下的分层架构。每层只负责自己的专属功能，仅与相邻上下层交互，下层为上层提供服务，上层依赖下层，禁止跨层直接访问。

层级顺序：
用户层 → 应用程序层 → 库函数层 → 系统调用层 → 操作系统内核层 → 设备驱动层 → 裸机硬件层

操作系统的核心功能

在整个计算机软硬件架构中，操作系统的定位是：一款纯正的“搞管理”的软件。

1. 进程管理：负责对系统中所有进程进行创建、销毁、调度、状态维护、资源分配，实现多任务并发执行。
2. 内存管理：管理物理内存与虚拟内存，完成内存分配回收、地址映射、进程内存隔离与内存保护。
3. 文件管理：统一管理计算机外存（磁盘）上的所有文件、目录、存储空间，提供文件存储、访问、权限、持久化能力。
4. 设备管理：统一管理计算机所有外部设备（键盘、显示器、磁盘、网卡、打印机），协调 CPU 与外设工作，解决高速 CPU 与慢速外设的矛盾。
5. 安全与权限管理：通过权限划分、运行态隔离、用户管控，保障操作系统内核安全、数据安全、系统稳定。

如何理解操作系统的 “管理”

核心结论
操作系统管理的本质：先描述，再组织。

• 先描述：通过结构体，将每一个进程、内存、文件、硬件设备等管理对象的状态、属性、资源信息进行抽象描述，形成独立的数据块；
• 再组织：利用链表、队列、红黑树等数据结构，将所有描述信息统一串联、分类、调度；
• 操作系统不直接操作硬件与进程实体，通过管理抽象后的数据结构，实现资源分配、任务调度、设备控制，从而完成整体管理。

类比：学校管理学生

1. 学生 = 进程 / 硬件（真实实体）
2. 学生档案表（学号、姓名、状态、违纪、宿舍）= 结构体「描述」
3. 班级花名册、年级总表（把档案串起来）= 链表 / 数据结构「组织」

校长（操作系统）不需要直接盯着每一个学生，只需要管理档案和表格，就能完成：分班、调座位、放假、处分、毕业、调度管理。
完全对应：先描述（档案）→ 再组织（花名册）→ 完成管理

系统调用和库函数概念

操作系统内核不允许普通用户直接访问，为了保证内核安全，操作系统提供了系统调用接口，用户程序只能通过固定接口访问内核资源。

• 系统调用（System Call）：是操作系统内核向外提供的一组底层服务接口，运行在内核态，权限最高，可直接操作系统资源。例如：fork()、open()、read()、write()。特点：功能基础、通用性强，但调用繁琐、编码成本高。
• 库函数：第三方库（如C标准库）对系统调用进行封装，运行在用户态，简化调用逻辑。例如：printf、malloc、fopen 全部都是库函数。

类比：系统调用 = 银行大厅窗口

二者关系：

• 库函数 = 系统调用 + 封装优化。库函数本质上底层一定会调用系统调用，相当于系统调用的“外壳”，降低开发者的使用门槛。部分库函数（如字符串函数strcpy）无需系统调用，完全在用户层实现。
• 系统调用和库函数是上下层封装依赖关系

进程

操作系统是怎么管理进行进程管理的呢？很简单，先把进程描述起来，再把进程组织起来！

前置铺垫

• 程序：存放在磁盘上的静态可执行文件，占用磁盘空间，不运行、不占用系统资源
• 进程：程序加载到内存后的一次执行实例，是动态的，占用CPU、内存资源，拥有独立的运行状态和资源
• 操作系统通过 PCB（进程控制块），遵循「先描述，再组织」完成对所有进程的管理
• 进程是操作系统资源分配和调度的基本单位

进程的基本概念与基本操作

• 课本概念：程序的一个执行示例，正在执行的程序等
• 内核观点：担当分配系统资源（CPU时间，内存）的实体
• 实际：进程 = 内核数据结构（task_struct） + 进程自身的程序代码和数据

描述进程 - PCB（进程控制块）

PCB 全称：进程控制块（Process Control Block）

• 操作系统为了管理每一个进程，在内核空间中专门创建的一个核心数据结构。
• 作用：描述一个进程的所有信息，是内核管理进程的唯一依据。
• 操作系统不认识进程代码，只认识 PCB
• Linux 内核中，PCB 的具体实现就是 task_struct 结构体。

PCB /task_struct 内部核心存储内容

1. 进程标识：用来唯一标识一个进程，区分系统内所有进程：

• PID：进程唯一编号
• PPID：父进程编号
• 进程名、进程组 ID、会话 ID

2. 进程状态：记录进程当前运行状态，是内核调度的核心依据：五大状态：R、S、D、T、Z，进程唤醒 / 阻塞标记
3. 优先级：相对于其他进程的优先级。
4. 程序计数器：程序中即将被执行的下一条指令的地址。
5. 内存指针：包括程序代码和进程相关数据的指针，还有和其他进程共享的内存块的指针
6. 上下文数据：进程执行时处理器的寄存器中的数据
   等等

组织进程

• 组织进程，本质不是组织代码，而是组织所有进程的 PCB 结构体。
• 所有运行在系统里的进程都以 task_struct 双向循环链表的形式存在内核里。

查看进程

核心进程标识

• PID：进程 ID，系统全局唯一，进程的身份证
• PPID：父进程 ID，记录当前进程的创建者

特点：PID 由操作系统动态分配，随机不重复；进程销毁后，PID 会被系统回收复用。

1. 进程的信息可以通过 /proc 系统文件夹查看

• /proc 是虚拟文件系统，全部驻留在内存中，不占用磁盘空间；所有文件 / 目录都是内核实时动态生成；内核直接把 PCB (task_struct) 中的所有信息，以文件形式对外开放
• 系统中每一个正在运行的进程，都会在 /proc 下生成一个以自己 PID 命名的文件夹。：/proc/进程PID/

2. 大多数进程信息同样可以使用top和ps这些用户级工具来获取
   示例：
   

补充：
在 Linux 终端里执行的所有指令、自己写的 C 程序、可执行文件，它们的父进程，全部都是当前终端的 -bash。

• 当你打开虚拟机 / Xshell / 终端窗口时：系统自动启动一个 bash 进程，这个 bash 一直挂在前台，等待你输入命令。
• 因此，终端下所有普通程序的 PPID 都是 bash 的 PID，bash 是它们的父进程

通过系统调用获取进程标示符

#include <stdio.h>    
#include <unistd.h>    
#include <sys/types.h>    
    
int main()    
{    
    while(1)    
    {    
        sleep(1);    
        printf("我是一个进程 !, 我的pid：%d, 我的父进程id：%d\n", getpid(), getppid());                                                   
    }    
}

创建进程 - fork初始

fork() 是内核提供的系统调用
作用：以当前进程（父进程）为模板，复制创建一个全新的子进程。

fork() 会在父子进程中分别返回，用返回值区分身份：

进程身份	fork () 返回值	含义
父进程	大于 0 的整数	返回子进程的 PID
子进程	0	标记自己是子进程
创建失败	-1	系统资源不足等错误

内核执行 fork() 的完整流程（底层原理）

1. 先描述：创建子进程 PCB

• 内核申请内存，新建一个 task_struct（PCB）；
• 复制父进程 PCB 的所有属性（优先级、文件描述符、环境变量、工作目录 cwd）；
• 给子进程分配全新的 PID，设置 PPID = 父进程 PID。

2. 管理虚拟地址空间：写时拷贝（COW）

• 代码段：父子进程完全共享（只读，无需复制）；
• 数据段 / 堆 / 栈：暂时共享，只有当一方尝试修改数据时，内核才会复制一份副本 → 实现数据独立。

3. 再组织：加入进程队列

• 把子进程 PCB 加入全局进程链表；
• 放入运行就绪队列，等待 CPU 调度。

父子进程的关系：两个独立进程，各自有 PID、PCB、虚拟地址空间，调度互不干扰。读时共享，写时拷贝。谁先被 CPU 调度执行，完全随机。

代码示例：

#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>

int main()
{
    printf("父进程开始运行,pid: %d\n", getpid());
    pid_t id = fork();
    if(id < 0)
    {
        perror("fork");
        return 1;
    }
    else if(id == 0)
    {
        // child
        while(1)
        {
            sleep(1);
            printf("我是一个子进程 !, 我的pid：%d, 我的父进程id：%d\n", getpid(), getppid());
         }
    }
    else 
    {
        // father
        while(1)
        {
            sleep(1);
            printf("我是一个父进程 !, 我的pid：%d, 我的父进程id：%d\n", getpid(), getppid());
         }
    }
    printf("进程开始运行,pid: %d\n", getpid());

	return 0;
}

• 问题一：为什么fork () 给父子进程返回不同的值？

• 答：因为这是唯一区分方式，fork 后父子进程代码完全相同，只有返回值能区分身份。父进程需要知道自己创建的子进程是谁，用于回收、管理、控制子进程。子进程知道自己是子进程就够了，子进程可自行获取父 PID。

• 问题二：为什么一个函数会返回两次

• 答：内核执行 fork：创建子进程的 PCB，做写时拷贝，复制父进程的内存空间，生成一个全新的子进程。函数返回，父子进程各执行了一次这个 return。

进程状态

进程状态就是 task_struct 内的一个整数

前置核心前提

1. Linux 进程状态全部记录在 task_struct（PCB） 的状态成员中；
2. 状态切换本质：修改 PCB 状态标记 + 把进程 PCB 在不同内核队列间迁移；
3. 用 ps aux / ps axj 的 STAT 字段、/proc/[PID]/status 可直接查看；

阻塞与挂起概念

阻塞：进程等待某外部事件（I/O、信号、资源）而放弃 CPU，驻留内存，事件完成后转入就绪态。
触发场景：等待键盘输入、等待磁盘读写、等待网络数据、sleep()、等待子进程、读文件等。

核心特征

1. 还在内存中，数据、PCB 都保留在内存；
2. 从「运行队列」移出，进入等待队列；
3. 事件完成后 → 不能直接运行，先转为就绪态，再排队抢 CPU。

挂起：
当内存不足时，操作系统把暂时不用的进程：从 内存 → 拷贝到磁盘 swap 分区；释放内存空间，缓解内存压力，这个过程叫挂起。

核心特征

1. 不在内存里，程序数据存在硬盘上；
2. 挂起只是内存管理手段，和等待 IO 无关；
3. 挂起分为两种：

• 阻塞挂起：本来在等事件，内存不够→挪到磁盘
• 就绪挂起：本来排队等 CPU，内存不够→挪到磁盘

4. 想要重新运行：必须先换回内存 → 变就绪 / 阻塞

补充：如何理解Linux内核链表
内核单独定义一个纯指针小结构体，不带任何数据：

struct list_head {
    struct list_head *next, *prev;
};

struct list_head 是 Linux 内核通用的双向链表连接件
作用：把内核里的各种对象（进程 PCB、文件、设备）串成链表 / 队列。

示例：进程PCB（task_struct）

// 进程PCB：描述一个进程
struct task_struct {
    pid_t pid;        // 进程ID
    int state;        // 进程状态 R/S/D/Z
    // 其他所有进程属性...

    //  嵌一个内核链表连接件！
    struct list_head run_list;
};

两个指针的作用：

• next：指向 下一个对象的连接件
• prev：指向 上一个对象的连接件

示例：

CPU中的调度队列的底层实现：就是用 struct list_head 串起来的一串进程 PCB！

进程状态切换 = 改指针（内核本质）

1. 进程进入就绪队列
   把它的 run_list 挂到 CPU 调度链表上
2. 进程上 CPU 运行
   把它从链表摘下来（不在队列里了）
3. 时间片用完，重回队列
   重新挂回链表
4. 进程阻塞（S/D 状态）
   从调度链表摘下 → 挂到 阻塞等待链表

总结：进程入队、出队、状态切换，本质就是修改 next/prev 指针。

Linux的进程状态

1. R 运行状态（running）：进程正在CPU上执行，或处于运行队列，等待CPU调度
   核心特点：唯一参与 CPU 调度的状态；调度队列里的所有进程，统一都是 R 态；
   典型场景：死循环程序、代码编译、数据运算、压测等高负载进程。

2. S 可中断睡眠状态（sleeping）：进程主动放弃 CPU，等待某一事件 / 资源，属于轻度阻塞。

核心特点

• 驻留内存，从调度队列摘除，加入设备等待队列；
• 可被信号唤醒：Ctrl+C、kill、自定义信号都能唤醒；
• 事件完成后，自动转为 R 态，重新进入调度队列。

典型场景：终端 bash、后台服务、sleep()、等待键盘输入、等待网络数据、父进程 wait 等待子进程。

3. D 不可中断睡眠（disk sleep）：进程正在执行底层硬件临界 I/O 操作（磁盘、SSD、块设备）

核心特点

• 不响应任何信号：kill -9、强制终止全部无效；
• 无法手动唤醒，只能等待硬件 I/O 自动完成；
• 内核为了防止文件 / 磁盘数据损坏，强制屏蔽中断。

典型场景：大批量读写硬盘、U 盘挂载、文件系统底层操作。

4. T 普通停止态（stopped）：由 Ctrl+Z 或停止信号触发，是用户手动暂停进程，可通过 fg/bg 恢复执行

核心特点

• 进程直接脱离 CPU 调度队列（runqueue）
• 代码完全暂停，不再执行任何指令
• 不属于阻塞、不属于睡眠

如何恢复运行：发送继续信号 SIGCONT
典型场景：你在终端运行程序、脚本、服务，按 Ctrl+Z 挂起暂停，

5. t 调试追踪停止态（tracing stop）：由 GDB 等调试器、断点、陷阱信号触发，用于程序调试，仅能通过调试器恢复

核心特点

• 进程被调试进程（gdb）接管管控
• 暂停原因是「代码断点 / 指令追踪」，不是人为手动暂停

典型场景

gdb ./a.out
(gdb) b main    # 打断点
(gdb) run       # 运行到断点暂停

6. X 死亡状态（dead）：进程彻底结束，PCB 被内核完全回收，无任何残留。生命周期极短，用户使用 ps 几乎看不到。
7. Z 僵尸进程（zombie）：子进程已经完全退出、绝大部分资源全部释放，但 PCB 进程控制块仍然保留，等待父进程读取退出信息、进行回收，此时该进程就是僵尸进程。(内核会把「子进程退出码、终止原因、运行统计信息」保存在 PCB 中)

核心特征

• 进程已经停止运行，无任何代码执行
• 不占用 CPU、不占用内存；
• 长期占用系统 PID 资源，大量僵尸会导致无法创建新进程；
• 解决：父进程回收 或 杀死父进程（子进程被 systemd 收养自动清理）。

补充：僵尸进程属于一种轻量级内核内存泄漏

示例：

#include <stdio.h>    
#include <sys/types.h>    
#include <unistd.h>    
    
int main()    
{    
    pid_t id = fork();    
    if(id == 0)    
    {    
        //child    
        int count = 5;    
        while(count)    
        {    
            printf("我是子进程，我正在运行：%d\n", count);                     
            sleep(1);    
            count--;    
        }    
    }    
    else    
    {    
        while(1)    
        {    
            printf("我是父进程，我正在运行...\n");    
            sleep(1);    
        }    
    }    
    return 0;    
}

进程状态查看

ps 命令：ps aux / ps axj 命令

• a：显示一个终端所有的进程，包括其他用户的进程。
• x：显示没有控制终端的进程，例如后台运行的守护进程。
• j：显示进程归属的进程组ID、会话ID、父进程ID，以及与作业控制相关的信息
• u：以用户为中心的格式显示进程信息，提供进程的详细信息，如用户、CPU和内存使用情况等

孤儿进程

父进程先终止，子进程仍然正常运行，该子进程称为孤儿进程
Linux 内核自动机制：所有孤儿进程，统一被 PID = 1 的进程（systemd/init）收养。

核心特点

• 可以正常使用 CPU、内存、IO、网络，完全稳定运行
• 无资源泄漏
• 脱离原终端；不受原终端关闭、Ctrl+C 影响，可后台长期运行。

核心内核机制

1. 凡是父进程消亡，存活的子进程全部过继给 1 号进程
2. 1 号进程是什么？

• 系统第一个启动的进程，终身运行、不会退出；
• 是系统所有孤儿的养父；
• 自带自动回收机制：
  只要它的养子（孤儿进程）退出，
  1 号进程会立刻自动调用 wait 回收 PCB，绝对不会产生僵尸。

示例：

#include <stdio.h>    
#include <sys/types.h>    
#include <unistd.h>    
    
int main()    
{    
    pid_t id = fork();    
    if(id == 0)    
    {    
        //child    
        while(1)    
        {    
            printf("我是一个子进程，pid: %d, ppid: %d\n", getpid(), getppid());            sleep(1);
        }                
    }        
    else 
    {       
        //father
        int cnt = 5;
        while(cnt)      
        {             
            printf("我是一个父进程，pid: %d, ppid: %d\n", getpid(), getppid());
            cnt--;          
            sleep(1);                                                             
        }             
    }
    return 0;
}

进程优先级

基本概念

• 简单理解：进程优先级是进程得到CPU资源的先后顺序
• 标准定义：进程优先级是操作系统为为每一个进程分配的优先级别，用于控制 CPU 调度顺序与时间片分配
• 优先级数值越小 → 优先级越高

两大核心参数：NI（Nice）、PRI（进程优先级）

1. NI ：Nice 值（进程优先级的修正数据）

• 取值范围：−20∼19
• 默认值：0
• NI 越大：进程越谦让，少抢 CPU → 优先级越低
  NI 越小：进程越强势，优先抢 CPU → 优先级越高
• 权限限制
  普通用户：只能加大 NI，只能降低自己进程优先级，不能抢占系统资源
  root 超级用户：可自由修改 −20∼19，能拉高进程优先级

2. PRI ：进程优先级

• PRI 不能手动直接修改，完全由 Nice 值计算得出。
• 默认：PRI=80
• 范围：60∼99
• 进程真实的优先级 = PRI（默认） + NI

示例：NI=−20⇒PRI=60（普通进程最高优先级）

查看进程优先级的命令

静态查看：ps -al

进程优先级 修改命令

1. nice ：启动进程时指定优先级

# 降低优先级，NI=5
nice -n 5 ./test
# root 提升优先级，NI=-10
sudo nice -n -10 ./test

2. renice：修改正在运行的进程

renice 5 -p 进程PID  # NI改为5

3. 用top命令更改已存在进程的nice
   1.启动 top
   2.在 top 界面中，直接按 r（renice 缩写）
   3.输入要修改的进程 PID（如1234），按回车
   4.输入目标 NI 值，按回车确认

4. 系统函数
   示例：

#include <stdio.h>
#include <unistd.h>
#include <sys/resource.h>
#include <errno.h>

int main()
{
    // 1. 获取当前进程 nice
    int ni = getpriority(PRIO_PROCESS, 0);
    printf("原始 nice = %d\n", ni);

    // 2. 增量修改：nice()
    nice(3);  

    // 3. 直接设置：setpriority()
    setpriority(PRIO_PROCESS, 0, 5);

    // 4. 再次查看
    ni = getpriority(PRIO_PROCESS, 0);
    printf("修改后 nice = %d\n", ni);

    return 0;
}

补充概念：竞争、独立、并行、并发

• 竞争性：系统进程数目众多，而CPU资源只有少量，甚至1个，所以进程之间是具有竞争属性的。为了高效完成任务，更合理竞争相关资源，便具有了优先级
• 独立性：多进程运行，需要独享各种资源，多进程运行期间互不干扰
• 并行：多个进程在多个CPU下分别，同时进行运行，这称之为并行
• 并发：多个进程在⼀个CPU下采用进程切换的方式，在一段时间之内，让多个进程都得以推进，称之为并发

进程切换

进程切换又称上下文切换，指操作系统暂停当前运行进程，保存运行上下文，调度并加载新进程执行的过程

进程上下文：进程在 CPU 上运行时，所有运行环境与硬件寄存器信息的集合。包含 CPU 寄存器、程序计数器、内存页表、运行状态等

进程切换的触发时机：时间片耗尽、进程主动阻塞、抢占式调度（高优进程就绪）、进程正常终止 / 退出、硬件中断 / 系统调用

进程切换完整流程：

1. 保存当前进程上下文
   将 CPU 寄存器、PC、状态字、栈指针等现场，存入当前进程的 PCB；
2. 修改当前进程状态
   运行态 → 转为 就绪态 / 阻塞态，放回对应队列；
3. 内核调度器工作
   遍历就绪队列（runqueue），按照调度算法（CFS / 时间片），选出下一个就绪进程；
4. 切换内存地址空间
   进程是独立虚拟地址空间，刷新页表、MMU 内存管理单元，切换映射关系；
5. 恢复新进程上下文
   从新进程的 PCB 中，读取寄存器、PC、页表等数据，载入 CPU；
6. 新进程开始运行

补充：时间片是操作系统分配给进程单次占用 CPU 的最大时间段，是分时系统实现并发的基础

Linux 2.6 内核O(1)调度算法

每一个CPU都有一个自己的runqueue

图中的关键成员

成员	图中位置	核心作用
lock	顶部	队列自旋锁，防止多个 CPU 同时修改队列导致数据混乱
nr_running	顶部	队列中就绪进程的总数，快速判断队列是否为空
cpu_load	标注 “负载因子”	基于队列中进程数量计算的负载值，用于 SMP 多核负载均衡
*curr	中间	指向当前正在 CPU 上运行的进程（task_struct）
*idle	中间	指向 CPU 的空闲进程，当队列为空时运行它
*active / *expired	中间偏下	指向两个核心队列：活跃队列和过期队列（图中蓝色 / 红色框的prio_array_t）
migration_thread/migration_queue	底部	进程迁移线程 / 队列，负责把忙 CPU 的进程迁移到空闲 CPU
*sd	底部	调度域（sched_domain），用于多核负载均衡的拓扑管理

其中，*active和*expired是 O (1) 调度器的灵魂指针，指向两个完全相同的prio_array_t结构（图中的array[0]和array[1]）

优先级数组（prio_array_t）的内部结构

图中active/expired指向的prio_array_t，是真正管理进程优先级的核心结构

1. nr_active：队列进程总数
   记录当前队列中就绪进程的数量，快速判断队列是否为空。
2. bitmap[5]：优先级位图
   作用：快速找到最高优先级的非空进程队列。
   原理：

• Linux 进程优先级范围是0~139（0-99 是实时进程，100-139 是普通进程，共 140 个优先级）。
• bitmap是一个uint32_t bitmap[5]数组，共5×32=160位，覆盖 0-159 位（实际只用 0-139 位）。
• 每一位对应一个优先级队列：如果bitmap的第i位为1，说明queue[i]链表中有进程。

调度时，内核用硬件指令find_first_set_bit直接找到bitmap中第一个为1的位，就能定位到最高优先级的非空队列，时间复杂度 O (1)。

3. queue[140]：优先级进程链表数组

• Linux 内核把进程优先级划分为 140 个等级（0 ~ 139）
• 0 ~ 99：实时进程优先级（共 100 个）
• 100 ~ 139：普通进程优先级（共 40 个，对应 nice -20~19）
• 每个下标i对应一个优先级，一个优先级对应一个链表，queue[i]是一个双向链表，挂着所有该优先级的task_struct（进程控制块）。
• 图中queue[140]指向的task_struct链表，就是同一优先级的所有就绪进程，按时间片轮转执行。

核心设计：active/expired 双队列机制

• active（活跃队列）：存放还有剩余时间片的就绪进程，是当前调度的 “主队列”。
• expired（过期队列）：存放时间片已用完的进程，等待重新分配时间片。

队列切换的 O (1) 魔法

• 当active队列中的所有进程都用完时间片（队列空了），内核不需要遍历任何进程，只需要交换active和expired两个指针
• 原来的expired队列变成新的active队列，原来的active队列变成新的expired队列。整个操作只是交换两个指针，时间复杂度严格为 O (1)

调度算法 核心流程

第 1 步：调度触发（开始调度的时机）
第 2 步：访问当前 CPU 的私有运行队列

• 读取 runqueue 中的 active（活跃队列指针）
• active 指向：还有时间片的就绪进程队列

第 3 步：通过位图 bitmap 快速找最高优先级
读取活跃队列的 bitmap[5]，内核用硬件指令，直接找到 bitmap 中 第一个为 1 的位

第 4 步：从 queue[i] 取出待运行进程
根据上一步找到的优先级 i，定位到 queue[i]，queue[i] 是该优先级的进程链表，直接取出链表的第一个进程

第 5 步：处理当前正在运行的旧进程
根据旧进程的状态，分两种情况：

• 情况 A：进程时间片耗尽
  重新计算该进程的新时间片，将进程移入 expired 过期队列（等待下一轮调度）
• 情况 B：进程阻塞 / 主动放弃 CPU
  直接将进程移出队列（不进入过期队列）
• 情况 C：进程被高优先级抢占
  保留剩余时间片，放回 active 队列

第 6 步：判断活跃队列是否为空（双队列切换）
当 active 队列中所有进程都用完时间片（队列为空）：执行 指针交换

第 7 步：完成进程上下文切换
第 8 步：新进程开始运行
CPU 执行新进程，直到下一次调度触发，循环以上流程