操作系统概念 第五章 进程调度

发布于:2022-12-29 ⋅ 阅读:(665) ⋅ 点赞:(0)

第五章 进程调度

5.1 基本概念

当一个进程一直执行到它应等待为止,当它等待时,操作系统就从该进程接管CPU控制,并将CPU交给另一进程。这个过程不断重复,当一个进程必须等待时,另一进程接管CPU使用权,以此达到CPU最大利用率。

5.1.1 CPU-I/O执行周期

CPU的调度成功取决于如下观察到的进程属性:进程执行包括周期(cycle)进行CPU执行和I/O等待。进程在这两个状态之间不断交替。CPU执行时间分布如下:具有大量短CPU执行和少量长CPU执行。I/O密集型程序具有大量短CPU执行;CPU密集型程序可能只有少量长CPU执行。CPU调度算法需根据这一分布合理选择。

5.1.2 CPU调度程序

每当CPU空闲时,操作系统会利用短期调度程序(short-term scheduler)或CPU调度程序,从内存中选择能够执行的进程,并为其分配CPU。

5.1.3 抢占调度

需进行CPU调度的情况可分为以下四种:

  • 当一个进程从运行状态切换到等待状态(例如,I/O请求,wait()调用等)。
  • 从运行状态切换到就绪状态(例如,出现中断时)。
  • 从等待状态切换到就绪状态(例如,I/O完成)。
  • 进程终止。

对于第1和第4种情况除了调度没有选择。如果调度只能发生在第1种和第4种情况下,则调度方案称为非抢占(nonpreemptive)或协作的(cooperative);否则称为抢占的(preemptive)。非抢占调度下一旦某个进程分配到CPU,它就会一直使用CPU,直到它终止或切换到等待状态。

多个进程共享数据时,抢占调度可能导致竞争情况。假设两个进程共享数据,当一个进程正在更新数据时,它被抢占以便第二个进程能够运行,但是第二个进程试图读取数据,这时该数据处于不一致的状态。抢占也影响操作系统的内核设计。

5.1.4 调度程序

调度程序是一个模块,其将CPU控制交给由短期调度程序选择的进程。这个功能包括:

  • 切换上下文。
  • 切换到用户模式。
  • 跳转到用户程序的合适位置,以便重新启动程序。

调度程序在每次进程切换的时候都会使用,应尽可能快。调度程序停止一个进程而启动另一个所需的时间称为调度延迟(dispatch latency)。

5.2 调度准则

比较CPU调度算法可以采用的比较准则:

  • CPU使用率
  • 吞吐量:一个时间单元内进程完成的数量
  • 周转时间:从进程提交到进程完成的时间
  • 响应时间:从提交请求到产生第一响应的时间

最大化CPU使用率和吞吐量,最小化周转时间、等待时间和响应时间,这是可取的。

5.3 调度算法

5.3.1 先到先服务(First-Come First-Served,FCFS)调度

先请求CPU的进程首先分配到CPU。实现非常简答,通过FIFO队列实现。当一个进程进入就绪队列时,它的PCB被链接到队列尾部;当CPU空闲时它会分配给位于队列头部的进程,并且这个运行进程从队列中移去。FCFS策略的缺点是平均等待时间往往很长(但通过调整进程到达就绪队列的时间的调整也可以有很大的改观)。

考虑假设有一个CPU密集型进程和多个I/O密集型进程。执行时会有护航效果(convoy effect)(这种情况下I/O密集型进程总在等待CPU密集型进程释放资源),会导致CPU和设备的使用率很低。

FCFS调度算法是非抢占的。

5.3.2 最短作业优先调度

最短作业优先(Shortest-Job-First,SJF)调度算法:当CPU空闲时,它会被赋给具有最短CPU执行的进程。一个更为恰当的表示是最短下次CPU执行(shortest-next-CPU-burst)算法。对于一组给定的进程,SJF算法的平均等待时间最小。

SJF算法的真正困难是如何知道下次CPU执行的长度。对于批处理系统的长期调度,可以将用户提交作业时指定的进程时限作为长度,这种情况下用户估值的精确度会有很大的影响(低值可能意味更快的响应)。SJF算法经常用于长期调度,它不能在短期CPU调度级别上加以实现,因为没有办法知道下次CPU执行的长度。虽然不知道下次CPU执行的长度,但可以预测它,近似SJF调度。下次CPU执行通常预测为以前CPU执行的测量长度的指数平均(exponential average)。具体算法感兴趣可自行查阅资料。

SJF算法可以是抢占的或非抢占的。当一个新进程到达就绪队列而以前进程正在执行时就需要选择了。若新进程的下次CPU执行更小,抢占SJF算法会抢占当前运行的进程,而非抢占SJF会允许当前运行进程先完成CPU执行。抢占SJF调度有时称为最短剩余时间优先(shortest-remaining-time-first)调度。

5.3.3 优先级调度

SJF算法是通用优先级调度(priority-scheduling)算法的一个特例。每个进程都有一个优先级与之关联,具有最高优先级的进程会分配到CPU,具有相同优先级的进程按FCFS顺序调度。

优先级的定义可分为内部的或外部的,内部定义的优先级采用一些测量数据来计算,例如,时限、内存要求等;外部优先级采用操作系统之外的准则,如进程重要性等。

优先的调度可以是抢占的或非抢占的,当一个进程到达就绪队列,如果新到达进程优先级高于当前运行进程的优先级,那么抢占优先级调度算法会抢占CPU,非抢占只是将新的进程加到就绪队列的头部。

优先级调度算法的一个主要问题是无穷阻塞(idefinite blocking)或饥饿(starvation)。优先级调度算法可以让某个低优先级进程无穷等待CPU(当一直有优先级比它高的进程加到就绪队列)。低优先级进程的无穷等待问题的解决方案之一是老化(aging)。老化逐渐增加在系统中等待很长时间的进程的优先级。

5.3.4 轮转调度

轮转(Round-Robin,RR)调度算法是专门为分时系统设计的。将一个较小时间单元定义为时间量(time quantum)或时间片(time slice)。就绪队列作为循环队列,CPU调度程序循环整个就绪队列,为每个进程分配不超过一个时间片的CPU。RR调度算法是抢占的,如果进程的CPU执行超过一个时间片,该进程就会被抢占,并被放回到就绪队列。一般我们希望时间片远大于上下文切换的时间,否则上下文切换的时间将会占较大的比例。周转时间(进程从提交到结束的时间)也依赖于时间片大小。随时间片大小增加,平均周转时间不一定会改善,若大多数进程能在一个时间片内完成,那么平均周转时间会改善。以三个进程,都需要是个时间单元,时间片分别为1和10时,平均周转时间分别为29,20。另外考虑到上下文切换时间,平均周转时间会增大。

5.3.5 多级队列调度

多级队列(multilevel queue)调度算法将就绪队列分成多个单独队列。根据进程属性,如内存大小、进程优先级、进程类型等,一个进程永久分到一个队列,每个队列有自己的调度算法,队列之间也有调度,通常采用固定优先级抢占调度,即优先级高的队列中的进程会抢占优先级低的队列中进程的CPU(每个队列与更低层队列相比具有绝对的优先)。另一种可能时在队列之间划分时间片,每个队列都有一定的CPU时间可用于调度队列内进程。

5.3.6 多级反馈队列调度

与多级队列调度相比,多级反馈队列(multilevel feedback queue)调度算法允许进程在队列之间迁移。考虑下面一种多级反馈队列的调度程序:
它有三个队列,从0到2,编号小的队列有绝对的优先级,即只有在队列0为空时队列1中的进程才能执行。每个进程进入就绪队列后就被添加到队列0,队列0内的每个进程都有8ms的时间片,如果一个进程不能在这一个时间片内完成,那么它被移到队列1的尾部,队列0为空时,队列1头部的进程会得到一个16ms的时间片,如果它不能完成,那么将会被抢占,并添加到队列2,只有队列0和1为空时,队列2内的进程才可根据FCFS来执行。这样的调度算法给CPU执行不超过8ms的进程最高优先级。这类进程可以很快得到CPU,完成执行,并且处理下个I/O执行。

通常,多级反馈队列调度程序可由下列参数来定义:

  • 队列数量。
  • 每个队列的调度算法。
  • 用以确定何时升级到更高优先级队列的方法。
  • 用以确定何时降低到更低优先级对立的方法。
  • 用以确定进程在需要服务时将会进入哪个队列的方法。

5.4 线程调度

5.4.1 竞争范围

对于实现多对一和多对多模型的系统线程库会调度用户级线程,以便在可用LWP上运行。这种方案称为进程竞争范围(Process-Contention Scope,PCS)。
为了决定哪个内核级线程调度到一个处理器上,内核采用系统竞争范围(System-Contention Scope,SCS)。
通常情况PCS采用优先级调度。

5.4.2 Pthreads 调度

感兴趣可自行查阅资料。

5.5 多处理器调度

5.5.1 多处理器调度的方法

非对称多处理(asymmetric multiprocessing):让一个处理器(主服务器)处理所有调度决定、I/O处理及其他系统活动,其他的处理器只执行用户代码。
对称多处理(Symmetric MultiProcessing,SMP):每个处理器自我调度。所有进程可能处于一个共同的就绪队列,或每个处理器都有它自己私有的就绪进程队列。无论如何,调度这样进行:每个处理器的调度程序都就检查共同的就绪队列,以便选择执行一个进程。

5.5.2 处理器亲和性

处理器亲和性(processor affinity):一个进程对它运行的处理器具有亲和性。进程最近访问的数据会更新处理器的缓存,可使进程的后续内存访问通常通过缓存来满足。如果将进程一道其他处理器上,应设置第一个处理器缓存的内容为无效,第二个处理器缓存应重新填充,缓存的无效或重新填充的代价很高。系统的内存架构可以影响处理器的亲和性。

5.5.3 负载平衡

负载平衡(load balance)设法将负载平均分配到SMP系统的所有处理器。对于处理器具有私有的可执行进程队列的系统,负载平衡是必须的,而对于有公共队列的系统,负载平衡通常没有必要。

负载平衡通常有两种方法:推迁移(push migration)和拉迁移(pull migration)。一个特定的任务周期性检查每个处理器的负载,如果发现不平衡,那么通过将进程从超载处理器push到空闲或不太忙的处理器,这是推迁移。当一个空闲处理器从一个忙的处理器pull一个等待任务时,发生拉迁移。两种方式并不相互排斥。

有趣的是,负载平衡往往会抵消处理器亲和性的好处。

5.5.4 多核处理器

传统上,SMP系统具有多个物理处理器,然而计算机硬件的最近做法是,将多个处理器放置在同一个物理芯片上,从而产生多核处理器(multicore processor)。
一般来说处理器核的多线程有两种方法:粗粒度(coarse-grained)和细粒度(fine-grainded)的多线程。粗粒度的多线程,线程一直在处理器上执行,直到一个长延迟事件发生,细粒度的多线程在更细的力度级别上切换线程。

5.6 实时CPU调度

软实时系统(soft real-time system):不保证会调度关键实时进程;只保证这类进程会优先于非关键进程。
硬实时系统(hard real-time system):一个任务应在它的截止期限之前完成,否则与没有完成是完全一样的。

5.6.1 最小化延迟

从事件发生到事件得到服务的这段时间称为事件延迟(event latency)。
中断延迟(interrupt latency)是从CPU收到中断到中断处理程序开始的时间。(中断发生时,操作系统先完成正在执行的指令,再确定中断的类型,保存当前进程状态,采用特定的中断服务程序(Interrupt Service Routine,ISR)来处理中断。执行这些任务的总时间为中断延迟。)
调度延迟(dispatch latency)是指调度程序从停止一个进程到启动另一个进程所需的时间量。调度延迟可分为冲突和调度两个部分。调度延迟的冲突阶段(conflict phase)有两个部分:抢占在内核中运行的任何进程;释放高优先级进程所需的、低优先级进程占有的资源。

5.6.2 优先权调度

有点没看懂,后面可能补上。

5.6.3 单调速率调度

单调速率(rate-monotonic)调度算法采用抢占的、静态优先级的策略,调度周期性任务。每个周期性任务会分配一个优先级,它与周期成反比(周期越短,优先级越高);这样,更频繁地需要CPU的任务应分配到更高的优先级。此外,单周期速率调度假定,对于每次CPU的执行,周期性进程的处理时间是一样的。一个周期开始时,进程按照优先级从高到低依次执行,一旦到达一个最短的周期,若仍有优先级低的进程在执行,那么优先级更高的进程将会抢占它的CPU,当优先级高的进程执行完后,优先级低的进程才能继续执行。在最长的一个周期内,观察所有的进程是否均能在各自截止期限之前完成。

单调速率调度可认为是最优的,如果一组进程不能由此算法调度,它不能由任何其他分配静态优先级的算法来调度。但是单调速率调度有一个限制:CPU利用率是有限的,并不总是可能完全最大化CPU资源。调度N个进程的最坏情况下CPU利用率为:
N(21/N-1)

5.6.4 最早截止期限优先调度

最早截止期限优先(Earliest-Deadline-First,EDF)调度根据截止期限动态分配优先级。截止期限越早,优先级越高。当一个进程运行时,它应向系统公布截止期限要求,优先级可能需要进行调整,以便反应新可运行进程的截止期限。运行机制与单调速率调度基本相同只是,EDF调度中进程的优先级是动态改变的。并且EDF调度不要求进程是周期的,也不要求进程的CPU执行长度是固定的,唯一要求的是进程在变成可运行时,应宣布它的截止期限。EDE调度理论上是最佳的,它可以调度进程是CPU利用率最大化,但实际中由于进程的上下文切换和中断处理,CPU利用率100%是不可能的。

5.6.5 比例分享调度

比例分享(proportional share)调度程序在所有应用之间分配T股,如果一个应用程序接收N股的时间,那么确保了它将有N/T的总的处理器时间。比例分享调度程序应采用准入控制策略,以便确保每个进程能够得到分配时间。准入控制策略是:只有客户请求的股数小于可用股数,才能允许客户进入,即进程请求的股数小于可用股数才能进入系统,否则准入控制器会拒绝进程进入系统。

5.6.6 POSIX 实时调度

略。

5.7 操作系统例子

5.7.1 Linux 调度

Linux系统的调度基于调度类(scheduling class)。
内核V2.6.23的发布中,完全公平调度程序(Completely Fair Scheduler,CFS)成为默认的Linux调度算法。

5.7.2 Windows 调度

5.7.3 Solaris 调度

略。

5.8 算法评估

首要问题是为算法选择定义准则。通常采用CPU使用率、响应时间或吞吐量等,还需定义这些参数的相对重要性。

5.8.1 确定性模型

一种主要类别的评估方法称为分析评估法(analytic evaluation),分析评估法使用给定算法和系统负荷,生成一个公式或数字,以评估在该负荷下的算法性能。
确定性模型(deterministic modeling)为一种分析评估模型。这种方法采用特定的预先确定的负荷,计算在给定负荷下每个算法的性能。

5.8.2 排队模型

5.8.3 仿真

5.8.4 实现


网站公告

今日签到

点亮在社区的每一天
去签到