姓名李令琪原创作品转载请注明出处课程《Linux 内核分析》MOOC课程地址http://mooc.study.163.com/course/USTC-10000290001. 实验环境与步骤实验使用实验楼提供的 Linux 虚拟机内核源码版本为 Linux3.9.4。首先进入源码目录应用 mykernel 补丁并编译内核cd~/LinuxKernel/linux-3.9.4rm-rfmykernel patch-p1../mykernel_for_linux3.9.4sc.patchmakeallnoconfigmakeqemu-kernelarch/x86/boot/bzImage基础实验运行成功后进入cd~/LinuxKernel/linux-3.9.4/mykernel在时间片轮转版本中主要分析和修改以下文件mypcb.h —— PCB、任务数量、内核栈及线程上下文定义 mymain.c —— 创建任务、建立循环链表、启动第一个任务 myinterrupt.c —— 时钟处理、调度以及上下文切换 Makefile —— 将 mymain.o 和 myinterrupt.o 编入内核修改源代码后重新回到 Linux 3.9.4 根目录执行make再使用 QEMU启动新生成的bzImage。2. 基础版 mykernel主执行流与时钟中断最初应用实验补丁后my_start_kernel()中主要是一个不断递增计数器的无限循环达到指定次数时打印my_start_kernel here。与此同时补丁把my_timer_handler()接入 x86的 timer interrupt路径因此即使主执行流一直处于无限循环硬件时钟中断仍然能够周期性打断它。图 1基础版 mykernel 的 QEMU 输出从图 1 可以看到屏幕持续输出my_start_kernel here ...同时周期性出现my_timer_handler here这一现象非常重要。它说明 CPU 并不是因为主程序进入while(1)就永远无法执行其他代码。时钟中断到来后处理器可以暂时中断当前控制流进入中断处理路径执行完中断处理后再回到原来的执行位置。mykernel 补丁还做了三件关键工作把mykernel/加入 Linux 内核的构建目录在 Linux 的start_kernel()后段调用my_start_kernel()在 x86 的时钟中断路径中调用my_timer_handler()。因此mykernel 并不是一个从固件开始独立启动的完整操作系统而是借助Linux 3.9.4已有的启动、中断和硬件初始化环境把教学代码嵌入其中从而让实验重点集中在任务管理和上下文切换上。3. 时间片轮转版本的总体结构完成时间片轮转代码后我首先检查关键符号是否已经存在并重新编译内核。图 2源码检查与重新编译图 2 中可以确认mymain.c已经存在my_process()myinterrupt.c已经存在my_schedule()mypcb.h中MAX_TASK_NUM为 4修改后重新执行了make。整个精简调度模型可以概括为Linux 启动 | v start_kernel() | v my_start_kernel() | -- 初始化 PCB 0、1、2、3 | 并用 next 指针形成循环链表 | v 启动 task[0] | v my_process() 持续执行 | | 周期性时钟中断 | | | v | my_timer_handler() | | | my_need_sched 1 | | -------------- | v my_process() 检查调度标志 | v my_schedule() | -- 保存当前任务上下文 -- current current-next -- 恢复/启动下一个任务 | v 0 - 1 - 2 - 3 - 0 - ...4. PCB操作系统描述任务的核心数据结构mypcb.h中定义了这个实验使用的简化 PCB。实验一共创建 4个任务每个任务拥有自己的内核栈。PCB 中最值得关注的字段可以抽象为PCB ├── pid 任务编号 ├── state 任务状态 ├── stack[] 任务自己的内核栈 ├── thread.ip 保存的指令执行位置 ├── thread.sp 保存的栈指针 ├── task_entry 任务入口 └── next 指向下一个 PCB其中thread.ip和thread.sp是理解上下文切换的关键。对于 x86 32位环境可以把它们分别联系到 EIP 和 ESPEIP决定 CPU 下一步从哪里继续执行ESP决定 CPU 当前使用哪一个栈以及栈顶位于哪里。真实 Linux的进程描述结构远比这里复杂还需要保存和管理地址空间、文件、信号、调度实体、凭据等大量信息。本实验刻意把PCB 压缩到最小规模是为了突出执行上下文 独立栈 调度关系这三个核心概念。5. 进程任务的创建与循环链表5.1 初始化 task[0]my_start_kernel()首先初始化 0 号任务。它主要完成以下工作pid 0 state runnable task_entry / ip my_process sp task[0] 自己的栈顶 next 自己这里最关键的两个初始化是IP - my_process SP - task[0] 的独立栈也就是说在任务真正开始运行之前内核已经准备好了从哪里执行和使用哪一个栈。5.2 创建其余任务接下来程序以task[0]为模板建立其余任务并分别修改PID初始状态每个任务自己的栈顶next指针。最终 4 个 PCB 构成一个循环链表--------- --------- --------- --------- | task 0 | -- | task 1 | -- | task 2 | -- | task 3 | --------- --------- --------- --------- ^ | |________________________________________________|这也是本实验能够自然实现 Round-Robin的原因。调度器不需要复杂的选择算法只要取当前 PCB 的next就能够依次得到0 - 1 - 2 - 3 - 0 - 1 - ...6. 第一个任务是怎样启动的完成 PCB 初始化后my_current_task - task[0]但仅仅改变一个 C 指针并不会让 CPU 自动开始执行 task 0。CPU真正关心的是当前寄存器状态。因此实验代码使用内联汇编完成了两件本质性的工作把 ESP 切换到task[0]准备好的独立栈让控制流转移到 task 0 的入口my_process()。可以把这个过程抽象成my_start_kernel() | | 准备 task[0].thread.sp | 准备 task[0].thread.ip v ESP - task[0].thread.sp EIP - task[0].thread.ip | v my_process()实验实现利用栈和ret指令完成控制流转移先把目标执行地址安排到新栈中再由ret把目标地址装入 EIP。因此启动一个任务从处理器层面看并不是某种神秘操作。其核心就是为任务准备一套有效的 CPU执行上下文尤其是栈和下一条指令的位置然后让处理器开始使用这套上下文。这也解释了为什么每个任务必须拥有独立的栈。如果多个任务共享同一套栈帧那么函数调用、局部变量和返回地址会互相破坏任务就无法独立暂停和恢复。7.my_process()任务运行与调度检查点4 个任务最终都运行同一个my_process()函数但因为my_current_task指向不同 PCB所以打印出的 PID 不同。其逻辑可以概括为while (true): 做一些计算 周期性打印当前 pid 如果 my_need_sched 1: 清除调度标志 调用 my_schedule() 继续执行这说明实验中的任务并不是 4 份完全不同的程序而是 4套彼此独立的执行上下文。即使代码入口相同只要它们拥有不同的PCB、不同的栈以及不同的执行现场就可以作为不同任务被分别调度。8. 时钟中断如何产生时间片myinterrupt.c中的my_timer_handler()由系统时钟中断周期性触发。处理函数维护一个计数器当满足设定周期并且当前还没有待处理的调度请求时就设置my_need_sched 1同时这里可以注意到这个教学版本的时钟中断处理函数本身并没有立即执行my_schedule()。它只是设置需要调度的标志。真正的my_schedule()是当前任务回到my_process()后在检查到my_need_sched时调用的。因此实验的调度链条实际是时钟中断到来 | v my_timer_handler() | v 设置 my_need_sched | v 中断返回当前任务继续 | v my_process() 到达检查点 | v 发现需要调度 | v my_schedule()9.my_schedule()时间片轮转与上下文切换9.1 选择下一个任务调度器首先保存当前 PCB并沿着循环链表选择下一个 PCBprev current next current-next随后current next由于 PCB 已经构成循环链表所以这一选择天然实现0 - 1 - 2 - 3 - 09.2 为什么必须保存上下文假设 task 0 正在执行时间片结束后要切换到 task 1。如果内核只是简单跳转到 task 1而没有记录 task 0的执行位置那么以后再次调度 task 0 时就不知道应该从哪里继续。因此切换前必须保存现场。在这个精简实验中最关键的是task 0: 保存 ESP 保存 EIP 保存与栈帧有关的 EBP task 1: 恢复 ESP 恢复 EIP 恢复相应栈帧状态于是任务切换可以抽象为正在运行 task 0 | v 保存 task 0 上下文 | v 选择 task 1 | v 恢复 task 1 上下文 | v CPU 从 task 1 上次的位置继续运行这就是上下文切换的核心。9.3 已运行任务与第一次运行任务my_schedule()对已经运行过的任务和第一次被调度的任务采用不同处理。情况 A任务以前已经运行过这种任务曾经被切走所以已经保存了有效的执行现场。重新调度它时只需要恢复保存的栈和执行位置恢复旧 SP 恢复旧 IP 继续上次被切走的位置情况 B任务第一次运行新任务没有上一次暂停的位置因为它从来没有运行过。因此第一次调度时需要使用初始化阶段准备好的SP - 新任务自己的栈 IP - my_process 入口使其从入口开始第一次执行。这一区别非常重要恢复一个旧任务和第一次启动一个新任务在概念上并不是同一件事。10. 实验现象从 task 0 切换到 task 1运行时间片轮转版本后QEMU 中出现了以下关键输出图 3task 0 切换到 task 1截图中的关键顺序为this is process 0 my_timer_handler here my_schedule switch 0 to 1 this is process 1这段输出可以逐步解释为task 0 正在运行时钟中断到来my_timer_handler()提出调度请求task 0 在运行过程中检查到调度标志进入my_schedule()调度器选择 task 1保存 task 0 的执行现场task 1 第一次被调度切换到自己的栈和入口CPU 开始执行 task 1因此随后打印this is process 1。这里最重要的不是switch 0 to 1这句日志本身而是日志之后确实开始持续输出 process1。这说明控制流已经真正进入 task 1。11. 实验现象从 task 3 回到 task 0继续运行后还观察到了 task 3 向 task 0 的切换图 4task 3 切换回 task 0截图中可以看到this is process 3 my_timer_handler here my_schedule switch 3 to 0 this is process 0这张截图具有特别重要的意义。task 0 并不是第一次启动。它此前已经运行过并在切换到 task 1时保存了自己的执行现场。现在从 task 3 再次调度到 task 0调度器恢复 task0 保存的上下文task 0 因而能够继续运行。同时3 - 0也证明 PCB 链表是闭环的。结合之前的0 - 1以及 4个任务的循环链表结构可以验证本实验的 Round-Robin调度机制已经正常工作。12. 一次完整轮转的逻辑分析把整个过程连起来可以得到task 0 运行 | | 时间片到 v 保存 task 0 恢复/启动 task 1 | | 时间片到 v 保存 task 1 恢复/启动 task 2 | | 时间片到 v 保存 task 2 恢复/启动 task 3 | | 时间片到 v 保存 task 3 恢复 task 0 | -------------------- 下一轮从调度策略上看这是最简单的公平轮转没有优先级也没有复杂的动态时间片计算只按照固定的循环链表顺序选择下一个任务。从 CPU 角度看真正发生的事情则更加基础保存 A 的寄存器/栈状态 ↓ 修改当前 PCB ↓ 恢复 B 的寄存器/栈状态 ↓ CPU 开始沿 B 的控制流执行所谓进程 A 被暂停、进程 B开始运行本质上就是这组底层状态变化所形成的高级抽象。13. 对操作系统是如何工作的的理解完成这个实验之前“进程调度”“时钟中断”上下文切换等概念很容易停留在课本定义上。通过mykernel可以把它们连接成一条实际的 CPU 控制流。首先CPU 本身并不知道进程 0进程1这样的高级概念。处理器看到的是寄存器、内存、栈和指令。操作系统通过 PCB把一组执行状态组织成一个可以管理的任务并通过my_current_task等数据结构记录当前正在运行的任务。其次操作系统必须能够重新获得 CPU 控制权。如果一个程序获得 CPU后可以永远运行而不被打断操作系统就无法可靠地实施多任务调度。周期性硬件时钟中断解决了这个问题即使当前任务一直执行循环时钟中断仍能让处理器进入内核的中断处理路径。于是操作系统获得了检查时间片和提出调度请求的机会。同时调度并不只是选一个进程。选择下一个任务只是第一步。真正让另一个任务继续运行还必须完成上下文切换保存当前任务的执行现场并恢复目标任务以前保存的执行现场。对于第一次运行的新任务则需要人为构造初始上下文让其从入口函数和自己的独立栈开始执行。因此我对操作系统是如何工作的的理解可以概括为操作系统依靠中断等机制不断获得处理器控制权以数据结构记录和管理系统中的任务与资源根据策略决定下一步应该让谁运行再通过保存和恢复CPU 执行上下文把处理器从一个任务切换到另一个任务。14. 实验结论本实验完成了一个简单的时间片轮转多道程序内核模型并通过 QEMU输出验证了任务切换。实验中首先观察到基础版my_start_kernel()与my_timer_handler()的交替执行从而验证硬件时钟中断可以打断当前控制流。随后通过 4 个PCB、4 套独立内核栈和循环next指针建立任务队列利用时钟中断设置调度请求由my_schedule()选择下一个任务并通过保存与恢复执行上下文完成切换。实验截图中成功观察到my_timer_handler my_schedule switch 0 to 1以及my_timer_handler my_schedule switch 3 to 0这说明调度器不仅能够从 task 0 切换到后继任务也能够在循环链表末端从task 3 回到 task 0时间片轮转机制能够正常工作。通过源代码和运行结果可以得出进程切换的本质是执行上下文的切换时间片轮转的基础是周期性时钟中断和可恢复的任务上下文操作系统正是通过不断管理、保存、选择和恢复这些状态让多个任务有序共享同一个处理器。