0923 进程调度

本次会议聚焦操作系统的进程调度和内存管理两大核心内容。宫晓利老师详细回顾了上节课进程调度相关知识，深入讲解多种经典调度算法，分析其优缺点及应用场景；接着介绍内存的物理结构、工作原理和内存管理的发展阶段，探讨重定位技术等内容。内容如下：

进程调度算法回顾与讲解

上节课内容复习

• 上下文与进程概念：宫晓利指出上节课用汇编代码展示了为应用程序创建和恢复存盘点的功能，引入了 “context”（上下文）数据结构来存储寄存器信息，每个进程都有对应的上下文。同时引出进程概念，它用于描述正在运行状态的程序。

• 汇编代码作用：强调使用汇编代码的原因，一是操作寄存器，C 语言编程中寄存器对程序员透明，无法控制变量存放的寄存器；二是打破函数的调用和返回序列，如在 “switch two” 函数中，可任意操纵 PC 值，改变程序执行轨迹。

• 进程状态机：介绍了进程状态机的概念，其状态数目有限，状态迁移条件确定。最简单的进程状态机包括运行、等待和就绪三种状态，每个状态对应一个链表，进程状态迁移就是将进程对象从一个链表转移到另一个链表。
  

• 调度算法引出：上周临下课提到调度算法是进程调度的最后一环，即从就绪队列中选择进程运行的原则和时机。

经典调度算法分析

先来先服务（FCFS）

• 算法原理：宫晓利表示这是批处理任务时代最简单、最易理解的调度算法，如同排队打饭，先来的任务先被处理。

• 周转时间问题：以任务进入调度队列到完成指令执行的时间为周转时间，平均周转时间是所有任务周转时间的平均值。不同任务到来顺序和运行时间顺序会导致平均周转时间不同，若先执行长任务，会使后续任务等待时间增加，平均周转时间变长。

短任务优先（SJF）

• 优化目标：以平均周转时间最小为优化目标，将任务按运行时间排序，运行时间短的任务优先执行。

• 算法缺陷：该算法需要预知任务运行时间，但在现代计算机程序中，准确估算程序运行时间具有挑战性。此外，短任务优先会导致长任务长时间得不到执行。

高响应比优先（HRRN）

• 算法改进：为解决短任务优先算法中长任务等待时间过长的问题，引入等待时间作为参数。响应比 =（等待时间 + 执行时间）/ 执行时间，等待时间越长，响应比越高，长任务获得运行机会增加。

• 创新思路：宫晓利认为在已有算法基础上，通过引入新的考量因素可提出新的调度算法，如高响应比优先算法，这也是撰写学术论文的一种思路。

时间片轮转（RR）

• 算法机制：将 CPU 时间划分为一个个小的时间片，进程在时间片内运行，时间片结束后，触发调度，将进程从运行态变为就绪态，选择下一个进程运行。为保障时间片轮转，系统设置时钟中断，每隔一段时间触发一次，打断当前进程，保存其上下文并调用 “switch to” 函数。

• 时间片大小选择：时间片大小对系统性能和用户体验有重要影响。时间片过大，算法接近先来先服务；时间片过小，会增加上下文切换开销，降低系统性能。操作系统最初将时间片设为 5 毫秒，沿用 20 多年，如今设备时间片已提升到 5 微秒，但频繁中断会降低系统性能，Linux 内核引入 “no 赫兹” 补丁进行优化。

多级反馈调度队列

• 任务分类：根据任务对延迟的敏感程度，将任务分为延迟敏感型（latency critical）和延迟不敏感型（latency insensitive），分别放入不同的就绪队列。

• 调度原则：操作系统先处理高优先级队列中的任务，高优先级任务时间片较短，低优先级任务时间片较长。高优先级任务通常是承载用户交互使命、IO 较多的任务，低优先级任务通常是承担运算使命、需要连续长时间运算的任务。

优先级调度

• 优先级设置：操作系统为每个进程增加 “priority” 属性，用户可设置进程优先级，操作系统从就绪队列中选择 “priority” 最小的进程优先执行。为保证系统安全性，部分操作系统只允许用户降低进程优先级。

• 排序问题：当就绪进程较多时，按优先级排序会面临时间复杂度问题，如最优排序时间复杂度为 $n\times logn$。因此需要选择合适的排序算法，如堆排序等，以维护优先级队列。

调度算法的思考与创新

• 机制与策略分离：强调操作系统设计中，“如何做”（机制）和“做什么”（策略）是分开的。如 “switch to” 函数的实现是机制，而选择哪个进程运行是策略。机制确定后，策略可灵活调整，如通过设置进程优先级来优化系统运行效率。

• 学术研究方向：鼓励学生关注学术研究，如用 AI 辅助操作系统为进程设置优先级。同时指出可从现有调度算法的不足中寻找创新点，撰写论文，如发现现有调度算法在特定场景下的缺陷，提出新的指标或方法进行改进。

多核处理器下的调度问题

多核与多处理器概念区分

• 多处理器架构：宫晓利介绍多处理器指处理器之间相对独立，通过系统总线或内存进行数据交互，如组成原理课上的多个独立芯片。

• 多核处理器架构：多核处理器将多个运算器集成在一个芯片中，在 CACHE 或高速通信层面有更多交流机会，可细粒度、低成本地交换数据，如笔记本电脑和手机的处理器。

调度队列设计

• 排队论应用：提出在多核处理器系统中，关于就绪队列的设计问题，即所有就绪队列排成一队还是为每个 CPU 各排一队。根据排队论，排成一队平均等待时间最小，但在 CPU 世界中，多个 CPU 同时访问同一队列会产生内存争抢问题，即临界区问题。

• 实际解决方案：为避免临界区问题，现代操作系统为每个 CPU 维护一个就绪队列，但这种方式在理论上不是最优的，可能出现部分 CPU 空闲，部分 CPU 任务堆积的情况。

进程对核心的亲和性

• CACHE 影响：进程在一个 CPU 上运行时，其数据会存储在该 CPU 的 CACHE 中。若进程迁移到其他 CPU 运行，CACHE 中的数据将失效，需要重新从内存中读取数据，降低了 CACHE 的利用率，这就是进程对核心的亲和性。

• 调度策略考量：在设计多核处理器的调度队列时，除避免队列争抢和保证任务公平分配外，还需考虑进程对核心的亲和性，使进程尽可能在原处理器上运行。这一领域存在诸多研究点，可产生大量学术论文。

智能手机调度问题

• 任务区分：指出智能手机上的任务可分为后台收数据任务和前台交互任务，两者重要性不同，如玩游戏不能卡，外卖信息晚到影响较小。

• 进程迁移：处理器厂商使不同 CPU 的寄存器组相同，降低了进程在不同核心之间迁移的代价。但迁移进程需要考虑进程的重要性和负载情况，鸿蒙系统通过传递更多用户信息，实现更准确的进程分配。

• 调度器学习：介绍现代操作系统中的三个著名调度器，CFS（completely fair scheduler）用于服务器，PLT 用于异构多核设备，EAS（energy aware scheduling）用于手机，建议学生课余自学。

内存管理的介绍与分析

内存的物理结构与工作原理

• 内存基本概念：表示内存是计算机中重要的数据存储单元，期待其与 CPU 运行速度接近，能可靠地存储和读取数据。现代内存主要采用 DRAM 控制器，其核心是电容。

• 电容工作原理：电容通过开关控制充电和放电，实现数据的存储和读取。但电容在空气中会缓慢放电，导致数据丢失，因此需要自刷新周期来保证数据的正确性。

• 数据安全问题：电容内存存在不可靠性，数据易受物理攻击，如通过给电容充电可任意修改数据。同时，内存数据断电易丢失，但在极低温度下，数据放电曲线会拉长，可用于数据破解。

• SPD 作用：SPD 是内存条上的掉电不丢失存储设备，记录内存容量、自刷新周期等信息。CPU 通过读取 SPD 值确定物理内存情况，早期无 SPD 时，CPU 通过写入特定值（如 0X55 和 0XAA）来扫描内存地址。

内存管理的发展阶段

• 裸地址编程时代：早期程序员使用裸地址编程，将每八个电容为一组称为一个字节，为字节编号形成地址概念。随着内存容量增加，处理器内存管理设备的位宽也增大。

• 操作系统划分内存：为实现应用程序的加载和执行，操作系统将物理内存划分区域，如 DOS 系统从 0 开始的 64K 被操作系统占用，应用程序从 64K 之后开始使用。但这种方式存在安全隐患，恶意程序可能破坏操作系统数据。

• 重定位技术：为解决多个应用程序同时加载的问题，操作系统引入重定位技术，即在程序加载时，将指令中与地址相关的数据进行修改。为提高效率，可制作地址表记录地址位置，还可通过硬件器件完成地址偏移过程。

课程总结与展望

• 课程内容总结：总结本次课程涵盖了进程调度和内存管理两大部分内容，强调操作系统设计要兼顾历史发展和新技术路线。

• 学术研究鼓励：鼓励学生关注学术研究，如用 AI 辅助操作系统为进程设置优先级，同时指出可从现有算法的不足中寻找创新点，撰写论文。

• 后续课程安排：留下 CFS、PLT、EAS 三个调度器让学生课余自学，后续课程将继续深入讲解内存管理相关内容，如处理器设计者为解决重定位问题所做的硬件优化。