第4章 处理机调度讲义

《第4章 处理机调度讲义》由会员分享，可在线阅读，更多相关《第4章 处理机调度讲义（46页珍藏版）》请在金锄头文库上搜索。

1、第四章 处理机调度,4.1 调度的层次与分类 4.2 调度算法的设计目标和性能指标 4.3 调度算法,4.1 调度的层次与分类,4.1.1 调度的层次,1. 高级调度(High Scheduling),高级调度是指作业调度，又称为宏观调度。 (1) 功能：审查系统是否能够满足作业的资源要求并按照某种调度算法来选取作业调度内存 (2) 时机：通常在以下3种情况下操作系统会启动“作业调度程序”选择作业进入内存 一个作业运行结束 有新作业提交 处理机利用率较低,2. 低级调度(Low Level Scheduling),低级调度是指进程调度，又称为微观调度。 (1) 功能：是操作系统中最基本的一级调

2、度，主要用来分配处理机，其调度对象是系统内存中的进程 (2) 时机：当处于执行状态的进程让出处理机或被调度程序剥夺处理机时通常发生低级调度，有以下几种情况 正在执行的进程执行完毕 正在执行的进程由于等待某事件的发生而被阻塞 分时系统中分配给该进程的时间片用完 在可剥夺方式下，当就绪队列中某进程的优先级高于当前执行进程的优先级，也将引发进程调度,(3) 分类 非抢占方式 优点：实现简单、系统开销小，适用于大多数的批处理系统环境。 缺点：难于满足紧迫任务立即执行的要求，因而可能造成难以预料的后果，在实时性要求比较严格的系统中不宜采用这种调度方式。 可抢占方式 适用于分时系统和大多数实施系统，通常遵

3、循以下3条原则：第一，时间片原则；第二，优先级原则；第三，短进程优先原则。,3. 中级调度(Intermediate-Level Scheduling),是指交换调度，是位于高级调度和低级调度之间的一级调度。 引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量。 为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。,4.1.2 调度的分类,1.

4、批处理调度,2. 分时调度,3. 实时调度,实时系统主要用于一些对响应时间要求更为严格的特殊领域。与分时系统类似，实时系统中主要涉及低级调度，其调度方式根据实时任务的不同有较大的灵活性。,4. 完整的3级调度,4.2 调度算法的设计目的和性能指标,4.2.1 设计目标,1. 公共系统设计目标 (1) 在所有的调度中，公平是很重要的。相似的进程应该得到相似的服务，对一个进程给予其他等价进程更多的处理机时间是不公平的。 (2) 另一个共同的目标是保持系统的所有部分尽可能忙碌。,2. 批处理系统设计目标 (1) 批处理系统通常用于大型计算机，主要追求的目标是大吞吐量、小周转时间以及高CPU利用率。

5、吞吐量是指系统每小时完成作业的数量，是显示计算机效率的重要指标。 周转时间是指一个批处理作业从提交到完成所花费的时间长度，该数据从用户角度反映了系统的性能。 (2) CPU利用率也是一个问题 在运行批处理系统的大型机上，CPU仍然是主要的昂贵资源，如果利用率较低，则是最大的浪费。,3. 分时系统设计目标 (1) 小的响应时间。 响应时间是指从发出命令到得到响应之间的时间，显示了系统的反应速度 (2) 好的均衡性也很重要。,4. 实时系统设计目标 在用户要求的时限内进行时间处理和控制，因此最主要的目标是满足任务的截止时间要求,1. 周转时间 从用户提交作业的全部信息进入系统开始，到作业完成时刻为

6、止的这段时间间隔称为该作业的周转时间。具体包括作业在外存后备队列上等待高级调度的时间、该作业对进程在内存就绪队列中等待低级调度的时间、进程在处理机上执行的时间、进程等待I/O操作完成的时间。 作业i的周转时间Ti为：,4.2.2 性能指标,其中Tei为作业i的完成时间，Tsi为作业的提交时间,也可将其表示为另一种形式：,其中，Twi主要是指作业i处于后备状态的等待时间，Tri是指作业的运行时间，即进入运行状态直至运行结束的时间。 作业的平均周转时间为：,作业的平均周转时间可用来衡量不同调度算法对同一作业流的调度性能。,2. 带权周转时间 作业周转时间仅反应了作业经历的绝对时间长度，为了进一步反

7、映调度性能，引入了带权周转时间的概念，带权周转时间Wi是作业周转时间与作业运行时间的比，即：,对于整个系统来说，平均带权周转时间W为：,平均带权周转时间反映了作业对单位执行时间所付出的平均等待时间，因此更能直观地体现出系统的工作效率,3. 系统吞吐量 指系统在单位时间内所完成的作业数，是批处理系统性能评价的一个重要指标。 系统吞吐量与作业的长度存在密切的关系，但调度方式和算法的选择对其也会产生很大的影响。,4. 响应时间 响应时间是分时系统和实时系统中衡量调度性能的一个重要指标。 响应时间是用户从提交一个请求开始，知道在屏幕上显示出结果为止的一段时间间隔 响应时间通常以人们所能接受的等待时间来

8、确定。在分时系统中，无论系统内的用户有多少，只要终端用户对系统的请求能够在很短的时间内得到响应，每个用户就感觉到自己独占这台计算机，通常只要在23s内给予响应即可；对于实时系统，响应时间要求则有很大的差别，它是以控制对象所要求的开始截止时间或完成截止时间来确定的，一般为秒级、毫秒级，甚至有的为微妙级。,5. 处理机利用率 一般来说，追求较高的处理机利用率与追求较高的吞吐量是一致的，只有较高的处理机利用率才可能有较高的吞吐量。在实际系统中，考虑到处理机要运行管理程序，其利用率不可能达到100% 处理机利用率是单位时间R内处理机运行用户程序的时间总和与R的比值，即：,其中，tsi为作业i占用处理机

9、的执行时间。,4.3 调度算法,3.2.1 先来先服务调度算法,4.3.2 短作业(进程)优先调度算法,短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。,SJ(P)F调度算法也存在不容忽视的缺点： (1) 该算法对长作业不利，如作业C的周转时间由10增至16

10、，其带权周转时间由2增至3.1。更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。 (2) 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。 (3) 由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。,4.3.3 高响应比优先调度算法,高响应比优先调度算法(HRF算法)是为了克服上述两种算法的不足之处提出的一种这种算法。采用该算法进行调度时，作业进入系

11、统的先后次序和作业的运行长度都是影响调度次序的因素，选择响应比最高的作业优先调度。作业i的响应比Ri定义如下：,其中，Twi为作业在后备队列中的等待时间，Tri为作业的估计运行时间。作业的响应比是一个随时间不断变化的数，每当系统进行作业调度时，都需要重新计算当前时刻每个作业的响应比，选择最高的投入运行,4.3.4 时间片轮转调度算法,1. 调度算法 在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进

12、程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。,2. 时间片长度的选择 在轮转算法中，时间片长度的确定是一个影响响应时间和系统开销的重要因素。 时间片的长度q可根据系统对响应时间的要求R和就绪队列中所允许的最大进程数N确定，在忽略切换开销的情况下，可有q=R/N。 此外，还要考虑到系统的处理能力，通常应当使用户输入的常用命令在一个时间片内能处理完，否则将会延长系统的响应时间、平均周转时间和平均带权周转时间。,3. 算法实例 假设有一个系统，0时刻

13、有4个进程按A、B、C、D的顺序几乎同时到达，它们的执行时间分别为40ms、20ms、10ms、30ms。按时间片轮转调度算法，下图给出了时间片为10ms时各进程的运行情况,4.3.5 优先级调度算法,1.调度算法的两种方式 (1) 非抢占式优先级算法 (2) 抢占式优先级算法,2.优先级的类型 (1) 静态优先级 在创建进程时就确定下来，而且在进程的整个执行期间保持不变。 优点：易于实现，系统开销小；缺点：不太灵活 (2) 动态优先级 在进程创建时赋予该进程一个初始的优先级，随着进程的执行优先级可不断变化，以获得更好的调度性能。 优点：更加灵活、科学；缺点：花费较多的执行时间，系统开销很大,

14、3.算法实例,4.3.6 多级反馈队列调度算法,1.调度算法 应设置多个就绪队列，并为各个队列赋予不同的优先级(p表示优先级)。 第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片(q表示时间片)的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，第i+1个队列的时间片要比第i个队列的时间片长一倍。 下图是多级反馈队列模型。,当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；

15、如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。,2. 算法性能,终端型作业用户。 (2) 短批处理作业用户。 (3) 长批处理作业用户。,4.4 实时系统调度,1.提供必要的信息 就绪时间 开始截止时间和完成截止时间 处理时间 资源要求 优先级,4.4.1 实现实时调度的基本条件,2. 系统处理能力强,在实时系统中，通常都有着多个实时任务。若处理机的处理能力不够强，

16、则有可能因处理机忙不过来而使某些实时任务不能得到及时处理， 从而导致发生难以预料的后果。假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Tri，周期时间表示为Ti，则在单处理机情况下，必须满足下面的限制条件：,3. 采用抢占式调度机制,当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。但这种调度机制比较复杂。 对于一些小的实时系统，如果能预知任务的开始截止时间，则对实时任务的调度可采用非抢占调度机制，以简化调度程序和对任务调度时所花费的系统开销。但在设计这种调度机制时，应使所有的实时任务都比较小，并在执行完关键性程序和临界区后，能及时地将自己阻塞起来，以便释放出处理机， 供调度程序去调度那种开始截止时间即将到达的任务。,4. 具有快速响应外部中断的能力,在紧迫的外部事件请求中断时，为了能及时响应，要求系统具有快速硬件中断机制，并且还应使禁止中断的时间间隔尽量短，以免耽误其他紧迫任务的执行时机。,5. 具有快速切换机制,该机制应具有如下两方面的能力： (1