二：处理机调度

处理机调度

调度的概念、层次

调度的基本概念

1. 在多道程序系统中，进程的数量往往多于处理机的个数，因此进程争用处理机的情况在所难免。处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法（公平、高效的原则）选择一个进程并将处理机分配给它运行，以实现进程并发地执行。
2. 处理机调度是多道程序操作系统的基础，是操作系统设计的核心问题。

调度的层次

1. 一个作业从提交开始直到完成，往往要经历以下三级调度：
   1. 高级调度(作业调度)
   • 按照一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。
   • 作业：一个具体的任务。
   • 用户向系统提交一个作业 ≈ 用户让操作系统启动一个程序(来处理一个具体任务)
   • 简而言之，作业调度就是内存与辅存之间的调度。每个作业只调入一次、调出一次。
   2. 中级调度(内存调度)
   • 引入中级调度的目的是提高内存利用率和系统吞吐量
   • 将那些暂时不能运行的进程调度至外存等待，此时进程的状态称为挂起态。当它们已具备运行条件且内存又稍有空闲时，由中间调度决定把外存上的那些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪态，挂在就绪队列上等待。
   • 中级调度实际上是存储器管理中的对换功能。
   3. 低级调度(进程调度/处理机调度)
   • 按照某种策略从就绪队列中选取一个进程，将处理机分配给它。
   • 进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度

三级调度的联系

作业调度从外存的后备队列中选择一批作业进入内存，为它们建立进程，这些进程被送入就绪队列，进程调度从就绪队列中选出一个进程，并把其状态改为运行态，把CPU分配给它。中级调度是为了提高内存的利用率，系统将那些暂时不能运行的进程挂起来。

• 作业调度为进程活动做准备，进程调度使进程正常活动起来。
• 中级调度将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之间。
• 作业调度次数少，中级调度次数略多，进程调度频率最高。
• 进程调度是最基本的，不可或缺。

进程的挂起态与七状态模型

三层调度的联系、对比

总结

进程调度的时机切换与过程调度的方式

进程调度的时机

1. 现代操作系统中，不能进行进程的调度与切换的情况有以下几种：
   1. 在处理中断的过程中。中断处理过程复杂，在实现上很难做到进程切换，而且中断处理是系统工作的一部分，逻辑上不属于某一进程，不应被剥夺处理机资源。
   2. 进程在操作系统内核临界区中。进入临界区后，需要独占式地访问，理论上必须加锁， 以防止其他并行进程进入，在解锁前不应切换到其他进程，以加快临界区的释放。
   3. 其他需要完全屏蔽中断的原子操作过程中。如加锁、解锁、中断现场保护、恢复等原子操作。在原子过程中，连中断都要屏蔽，更不应该进行进程调度与切换。
2. 进程切换往往在调度完成后立刻发生，它要求保存原进程当前断点的现场信息，恢复被调度进程的现场信息。现场切换时，操作系统内核将原进程的现场信息推入当前进程的内核堆栈来保存它们，并更新堆栈指针。内核完成从新进程的内核栈中装入新进程的现场信息、更新当前运行进程空间指针、重设PC寄存器等相关工作之后，开始运行新的进程。

进程调度方式

进程的切换与过程

调度器、闲逛进程

1. 调度程序(调度器)
   
   
2. 用于调度和分派CPU的组件称为调度程序，它通常由三部分组成:
   ① 排队器。将系统中的所有就绪进程按照一定的策略排成一个或多个队列，以便于调度程序选择。每当有一个进程转变为就绪态时，排队器便将它插入到相应的就绪队列中。
   ②分派器。依据调度程序所选的进程，将其从就绪队列中取出，将CPU分配给新进程
   ③上下文切换器。在对处理机进行切换时，会发生两对上下文的切换操作：第一对，将当前进程的上下文保存到其PCB中，再装入分派程序的上下文，以便分派程序运行；第二对，移出分派程序的上下文，将新选进程的CPU现场信息装入处理机的各个相应寄存器。
   
3. 闲逛进程
   1. 调度程序永远的备胎，没有其他就绪进程时，运行闲逛进程
   2. 闲逛进程的特性：
   • 优先级最低
   • 可以是0地址指令，占一个完整的指令周期(指令周期末尾例行检查中断)
   • 能耗低

调度算法的评价指标

处理机调度算法的性能评价标准：

1. CUP利用率：CPU是计算机系统中最重要和昂贵的资源之一，所以应尽可能使CPU保持“忙”状态，使这一资源利用率最高。CPU利用率的计算方式如下：
   
   
2. 系统吞吐量。表示单位时间内CPU完成作业的数量。长作业需要消耗较长的处理机时间,因此会降低系统的吞吐量。而对于短作业，需要消耗的处理机时间较短，因此能提高系统的吞吐量。调度算法和方式的不同，也会对系统的吞吐量产生较大的影响。
   
   
3. 周转时间。指从作业提交到作业完成所经历的时间，是作业等待、在就绪队列中排队、 在处理机上运行及输入/输出操作所花费时间的总和。周转时间的计算方法如下：

周转时间=作业完成时间-作业提交时间

平均周转时间是指多个作业周转时间的平均值：

平均周转时间=（作业1的周转时间+...+作业n的周转时间）/ n

带权周转时间是指作业周转时间与作业实际运行时间的比值:

带权周转时间与周转时间都是越小越好

平均带权周转时间是指多个作业带权周转时间的平均值：

平均带权周转时间=（作业1的带权周转时间+•••+作业n的带权周转时间）/ n

1. 等待时间。
   1. 指进程处于等处理机的时间之和，等待时间越长，用户满意度越低。
   2. 处理机调度算法实际上并不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法的优劣，常常只需简单地考察等待时间。
   3. 对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。
   4. 对于作业来说，不仅考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。
   5. 一个作业总共需要被CPU服务多久，被I/O设备服务多久一般是不确定的，因此调度算法其实只会影响作业/进程的等待时间。
2. 响应时间。指从用户提交请求到系统首次产生响应所用的时间。在交互式系统中，周转时间不是最好的评价准则，一般采用响应时间作为衡量调度算法的重要准则之一。从用户角度来看，调度策略应尽量降低响应时间，使响应时间处在用户能接受的范围之内。
3. 设计调度程序，一方面要满足特定系统用户的要求（如某些实时和交互进程的快速响应要求），另一方面要考虑系统整体效率（如减少整个系统的进程平均周转时间），同时还要考虑调度算法的开销。
   

调度算法

Tips：各种调度算法的学习思路

1. 算法思想
2. 算法规则
3. 这种调度算法是用于 作业调度 还是 进程调度？
4. 抢占式？非抢占式？
5. 优点和缺点
6. 是否会导致饥饿

先来先服务(FCFS)

短作业优先(SJF)

1. 非抢占式的短作业优先调度算法—> 又称为“最短剩余时间优先算法(SRTN)”
   
2. 抢占式的短作业优先算法
   
   
   
   

高响应比优先(HRRN)

1. 算法规则–>在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务.
   $$ 响应比=\frac{等待时间+要求服务时间}{要求服务时间}$$
   
   
   

时间片轮转法

1. 算法规则 –> 按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如 100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
2. 时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片已到。
3. 时间片大小为2时
   
   
   
4. 时间片大小为5时
   
5. 如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。
6. 进程调度、切换是有时间代价的(保存、恢复运行环境)，因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。
   

优先级调度算法

1. 算法规则 —> 每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程。
2. 非抢占式
   
3. 抢占式
   
4. 补充
   
   

多级反馈队列调度算法

1. 算法思想
   1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
   2. 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
   3. 只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片用于进程调度
      
      
      

多级队列调度算法

各种算法总结

题目总结

1. 时间片轮转调度算法是为了多个用户能及时干预系统
2. CPU繁忙型作业是指该类作业需要占用很长的CPU时间，而很少请求I/O操作，因此CPU繁忙型作业类似于长作业。
3. I/O繁忙型作业是指作业执行时需频繁请求I/O操作，即可能频繁放弃CPU，所以占用CPU的时间不会太长，一旦放弃CPU，则必须重新排队等待调度，故采用短作业优先合适。
4. 进程(线程)调度的时机有：
   1. 运行的进程(线程)运行完毕
   2. 运行的进程(线程)所需资源未准备好
   3. 运行的进程(线程)时间片用完
   4. 运行的进程(线程)自我阻塞
   5. 运行的进程(线程)出现错误
5. 时间片轮转算法是按固定的时间配额来运行的，时间一到，不管是否完成，当前进程必须撤下，调度新的进程，因此它是由时间配额决定的、是绝对可抢占的。而优先级算法和短进程优先算法都可分为抢占式和非抢占式。
6. 作业是用户提交的，进程是系统自动生成的，除此之外，两者的区别是
   1. 处理：作业通常指一组相互独立的任务或者程序，系统需要根据用户的要求分配资源，将其作为一个整体进行处理；而进程是系统进行资源调度和管理的基本单位，它是程序执行的实例，包括程序、数据和执行状态等元素。
   2. 生命周期：作业在系统中的生命周期包括提交、接受、调度、执行和完成等阶段；而进程的生命周期包括创建、就绪、运行、阻塞和完成等阶段，它有自己的程序计数器、内存空间和执行状态，可以被处理器调度执行。
   3. 独立性：一般情况下，作业是相互独立的，它们可以在不同的时间、不同的系统中进行处理；而进程之间相互依赖，它们需要共享资源、通信等协作操作，形成协同的执行方式。
   4. 资源占用：一个作业需要在执行前获得足够的系统资源，包括内存、CPU、IO等，通常比较耗费系统的资源；而一个进程可以比一个作业更轻量级，它只需获得少量的系统资源即可执行，因为它可以共享许多系统资源（如内存、存储器等）。
   5. 调度：作业调度主要是以作业为单位，对用户提交的作业进行优先级调度和资源分配等处理；而进程调度是以进程为单位，进行时间片轮转、优先级调度等操作，使所有进程能够得到公平的处理。
   6. 作业是以用户任务为单位，进程是以操作系统控制为单位
      
7. 假设系统中所有进程同时到达，则使进程平均周转时间最短的算法是短进程优先调度算法。
8. 高响应比优先算法在等待时间相同的情况下，作业执行时间越短，响应比越高，满足短任务优先。
9. 一种既有利于短小作业又兼顾到长作业的作业调度算法是最高响应比优先算法。这种算法在等待时间相同时，作业执行的时间越短，响应比越高，满足短任务优先。同时，响应比会随着等待时间增加而变大，优先级会提高，能够避免饥饿现象。
10. 从系统的角度来考虑，希望进入“输入井”的批处理作业的等待时间尽可能小。这样可以提高系统的吞吐量和资源利用率。