进程与线程：07 CPU调度策略
一、课程内容概述
本节课程主要讲解操作系统的CPU调度策略，聚焦于基本操作系统上的调度算法，探讨其大致实现方式、需折中考虑的问题。CPU调度在不同场景下复杂程度不同，如卫星、导弹等实时性要求高的系统，需采用实时调度，而本次课程主要围绕常见的基本调度策略展开，不求穷尽所有算法，旨在以点带面，帮助学习者触类旁通。
二、CPU调度的基本概念
-
调度与切换的关系：在多进程图像下，CPU调度和进程切换紧密相连。调度的目的是从就绪队列中选取下一个要执行的进程（获得next），并切换到该进程（switch to next），从而使操作系统能够实际运转。例如，当一个进程（如p1）在执行过程中因阻塞、时间片到期等原因无法继续执行时，操作系统需从就绪队列中选择另一个进程（如p2或p3）来执行，此时就涉及到调度策略的选择。
-
调度的直观想法：其直观思路是从就绪队列的众多进程中选择执行对象。生活中的银行、食堂等场景也存在类似调度，最常见的方法是先来先服务（先入先出），这种方法简单公平，但存在局限性。比如在银行，对于简单询问业务的客户，若采用先来先服务，可能导致其等待时间过长，不太合理，因此可考虑短作业适当优先。然而，若短作业的处理时间不断延长，又需适当降低其优先级，这就引出了优先级调度的概念，且优先级在实际中会不断变化 。
三、设计调度算法的指标
- 进程满意的关键因素：设计调度算法需要明确指标，而让进程满意的关键在于时间相关因素。对于进程而言，用户希望程序执行速度快，这涉及到多种时间指标，如周转时间和响应时间。
- 周转时间：周转时间是指从任务进入系统到任务结束的时间，用户希望该时间越短越好。例如，在编译任务中，用户期望编译过程尽快完成。
- 响应时间：响应时间是从操作发生到系统产生反应的时间，对于一些前台任务（如word操作），用户更关注响应时间。比如按下键盘后，希望字符能尽快显示在屏幕上。
- 其他指标：除了周转时间和响应时间，系统内耗时间也应尽量少，否则会减少实际用于处理任务的时间，导致用户不满。同时，系统完成任务的数量（吞吐量）应尽量大 。
四、CPU调度的关键——折中和综合
- 系统任务的多样性与矛盾：操作系统中存在多种任务，如前台任务（如ppt操作）和后台任务（如图像压缩），它们关注点不同，前台任务更关注响应时间，后台任务更关注周转时间。而且这些任务之间相互影响，例如，若要满足前台任务响应时间短的要求，就需要增加进程切换次数，但这会导致系统内耗增大，进而使后台任务的周转时间变长，因此CPU调度需要在这些相互矛盾的需求之间进行折中、平衡与综合 。
- I/O约束性任务和CPU约束性任务：I/O约束性任务的特点是I/O操作较多，CPU执行区间短且频率高，如银行出纳工作、word操作等；与之相对的是CPU约束性任务，这类任务长时间进行计算，几乎没有I/O操作，例如gcc编译、matlab矩阵计算等。由于两者特点不同，调度优先级也应有所区别，I/O约束性任务通常优先级更高，因为它优先执行可以使I/O和CPU并行工作，提高系统效率，且I/O约束性任务往往是前台任务，为了给用户及时反馈，也应赋予较高优先级 。
五、常见调度算法
-
先来先服务（FCFS）：这是最简单的调度算法，按照进程到达就绪队列的先后顺序进行调度。例如，进程p1先到达，p5后到达，调度顺序就是p1执行完后p2，依次类推直到p5。但这种算法可能导致周转时间较长，通过调整进程执行顺序，将短作业提前执行，可降低周转时间，提高系统整体满意度，由此引出短作业优先（SJF）算法 。
-
短作业优先（SJF）：该算法将短作业优先执行，可证明这种方法能使周转时间最小。因为在计算周转时间的公式中，先执行的作业被重复计算的次数更多，所以将短作业放在前面执行，最终得到的周转时间总和更小。这种算法在实际中有重要价值，但也有局限性 。
-
时间片轮转调度（RR）：为保证响应时间，引入时间片轮转调度算法。它将CPU时间划分为固定大小的时间片，每个进程轮流执行一个时间片。例如，给进程p1、p2、p3各分配10个时间片，执行完后再为后续进程分配。通过这种方式，可保证最长响应时间在一定范围内（为进程数量乘以时间片大小），从而确保响应时间。为提高响应速度，时间片应尽量小，但同时要限制系统中进程的数量 。
-
优先级调度：由于不同任务对响应时间和周转时间的需求不同，可采用优先级调度。直观做法是设置前台任务队列和后台任务队列，前台任务采用轮转调度以保证响应时间，后台任务采用短作业优先以减少周转时间，然后通过优先级来决定执行顺序，前台任务优先级高于后台任务。
但如果采用绝对优先级调度，可能导致后台任务饥饿，如1967年提交的一个进程，因前台任务不断出现，直到1973年都未执行。因此，任务优先级应动态调整，但这又会引发新的矛盾，如后台长CPU任务执行时会影响前台任务响应时间。所以，调度算法需要综合考虑轮转调度、优先级和短作业优先等因素，且应具备学习机制，能根据任务特点和变化自适应调整，以实现对各种任务的折中与综合 。
六、课程总结与展望
本次课程介绍了CPU调度的含义，即从就绪队列选取进程执行，强调调度算法需考虑周转时间、响应时间、任务特点和优先级等因素，还讲解了先来先服务、短作业优先、时间片轮转调度三种基本算法。未来课程将在此基础上，展示如何综合这些基本算法，设计出简单且能有效折中多种任务需求的实际调度程序，以应对操作系统中多任务的复杂情况 。