资源预览内容
第1页 / 共71页
第2页 / 共71页
第3页 / 共71页
第4页 / 共71页
第5页 / 共71页
第6页 / 共71页
第7页 / 共71页
第8页 / 共71页
第9页 / 共71页
第10页 / 共71页
亲,该文档总共71页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
2018/9/17,1,操作系统原理与UNIX,柳青E-mail:liuqingynu.edu.cn,云南大学软件学院,2018/9/17,2,第四章 处理机调度,4.1 分级调度 4.2 作业调度 4.3 进程调度 4.4 调度算法 4.5 算法评价 4.6 实时系统调度方法,2018/9/17,3,第四章 处理机调度,处理机调度问题实际上就是处理机的分配与管理。 处理机管理的工作是对CPU资源进行合理的分配使用,以提高处理机利用率,并使各用户公平地得到处理机资源。这里的主要问题是处理机调度算法和调度算法特征分析。,2018/9/17,4,衡量调度策略的常用指标,我们可从不同的角度来判断处理机调度算法的性能: 用户的角度; 处理机的角度; 算法实现的角度。实际的处理机调度算法选择是一个综合的判断结果。,2018/9/17,5,1.面向用户的性能指标,周转时间:从作业提交给系统到返回结果所需时间; 平均周转时间T 平均带权周转时间带权周转时间W是 T(周转)/T(CPU执行) 响应时间:用户输入一个请求(如击键)到系统给出首次响应(如屏幕显示)的时间分时系统 截止时间:开始截止时间和完成截止时间实时系统,与周转时间有些相似。 公平性:不因作业或进程本身的特性而使上述指标过分恶化。如长作业等待很长时间。 优先级:可以使关键任务达到更好的指标。,2018/9/17,6,2.面向系统的性能指标,吞吐率:在给定时间内,一个计算机系统所完成的总工作量; 响应时间:用户向计算机发出一个命令到计算机将结果返回给用户所需的时间; 设备利用率:指I/O设备的使用情况。,2018/9/17,7,3.面向算法的性能指标,实现难度:实现该算法是否容易 执行开销比:该算法是否消耗太多系统资源,2018/9/17,8,4.1 分级调度(Scheduling),作业调度-高级调度 交换调度-中级调度 进程调度-低级调度 线程调度,2018/9/17,9,4.1 分级调度-作业调度,高级(Long-term)调度作业调度作业调度用于决定把外存输入井上处于作业后备队列上的哪些作业调入内存,并为它们创建进程、分配必要的资源,然后再将新创建的进程排在就绪队列上,准备执行。在批处理系统中,作业是先驻留在外存的输入井上的,因此需要有作业调度。然而在分时系统中,通过键盘输入的命令和数据直接进入内存,无需作业调度。,2018/9/17,10,中级(Medium-term)调度交换调度引入中级调度的目的是为了提高主存利用率和系统吞吐量。由于在进程并发执行过程中,为了充分发挥内存的效能,需将那些暂时不能运行的进程从内存调到外存盘交换区去等待,而将那些在盘交换区的等待事件已经发生急需调度运行的进程从盘交换区调入内存。在UNIX系统中中级调度就是存储管理中的交换,采用虚拟存储技术的分时系统往往设立中级调度。,4.1 分级调度-交换调度,2018/9/17,11,4.1 分级调度-进程调度,低级(Short-term)调度进程调度进程调度决定就绪队列中哪个进程将获得处理机,然后由分派程序执行把处理机分配给该进程的操作。在确定了占用处理机的进程之后,系统必须进行进程上下文切换以建立与占用处理机进程相适应的执行环境。进程调度是最基本的调度,任何操作系统都有进程调度。,2018/9/17,12,线程调度在多线程系统中,按照一定的策略和方法选取一个处于就绪队列中的线程占有处理机。,4.1 分级调度-线程调度,图:处理机四级调度,作业运行状态外存,外存(盘)交换区,作业收容状态,作业提交状态,作业完成状态,终止作业,就绪态,阻塞态,线程调度,交换调度,作业调度,2018/9/17,14,4.1.3 作业与进程的关系,作业可被看作是用户向计算机提交任务的实体。如一次计算,一个控制过程等。 进程则是计算机为了完成用户任务实体而设置的执行实体,是系统分配资源的基本单位。 一个作业可以由一个或多个进程组成。而一个进程不可能对应多个作业。,2018/9/17,15,4.2 作业调度,1.作业的状态作业从进入到运行结束,一般需要经历“提交”、“后备”、“运行”和“完成”四个阶段。 2.作业调度功能 (1)记录系统中各作业的状况 (2)从后备队列中选出一部分作业投入执行。 (3)为被选中作业做好执行前的准备工作。 (4)在作业执行结束时做善后处理工作。,2018/9/17,16,4.2 作业调度,3. 作业调度目标与性能衡量 (1)作业调度目标 对所有作业应该是公平合理的; 应使设备有高的利用率; 每天执行尽可能多的作业; 有快的响应时间。 注:上述目标之间是互相冲突的。,2018/9/17,17,4.2 作业调度,(2)性能衡量 (平均)周转时间作业i的周转时间Ti为 Ti=Tei-Tsin个作业的平均周转时间为:n个作业的周转时间之和除以n。 (平均)带权周转时间是作业周转时间与作业执行时间之比:wi = Ti / Trin个作业的平均带权周转时间:n个作业的带权周转时间之和除以n。,2018/9/17,18,4.3 进程调度,进程调度的功能: 记录系统中所有进程的执行情况进程管理模块在各进程的PCB表中记录系统各进程的执行情况和状态特征,并将各PCB表根据进程状态特征和资源要求排成相应的队列,并进行动态队列转换。 选择占有处理机进程进程调度的主要功能是按照一定的策略(由它决定的调度算法),选择一个处于就绪态的进程,使其获得处理机执行。 进行进程上下文切换进程上下文实际上是进程执行活动全过程的静态描述,一个进程的执行是在进程上下文中执行。当正在执行的进程由于某种原因要让出处理机时,系统要做上下文切换,以使另一个进程得以执行。,4.3 进程调度,进程调度的功能: 记录系统中所有进程的执行情况进程管理模块在各进程的PCB表中记录系统各进程的执行情况和状态特征,并将各PCB表根据进程状态特征和资源要求排成相应的队列,并进行动态队列转换。 选择占有处理机进程进程调度的主要功能是按照一定的策略(由它决定的调度算法),选择一个处于就绪态的进程,使其获得处理机执行。 进行进程上下文切换进程上下文实际上是进程执行活动全过程的静态描述,一个进程的执行是在进程上下文中执行。当正在执行的进程由于某种原因要让出处理机时,系统要做上下文切换,以使另一个进程得以执行。,2018/9/17,20,4.3.2 进程调度的时机,引起进程调度的原因有: 1. 正在执行的进程执行完毕; 2. 执行中的进程调用阻塞原语将自己阻塞起来进入睡眠状态; 3. 执行中的进程调用了P原语操作,从而因资源不足而被阻塞;或调用了V原语激活了等待资源的进程队列; 4. 执行中的进程提出I/O请求后被阻塞; 5. 执行中的进程在分时系统中的时间片已用完; 6. 系统程序返回用户进程时,可认为系统进程执行完毕,从而可调度选择一个新的用户进程执行; 7. 在剥夺方式下,就绪队列中的进程优先级高于执行中的进程,执行进程被剥夺处理机资源。,2018/9/17,21,进程调度的方式,非剥夺(非抢占 Nonpreemptive mode )方式:采用这种调度方式时,一旦把处理机分配给某进程后,便让进程一直执行,直到该进程完成或发生某事件而被阻塞时,才把处理机分配给其它进程,决不允许某进程抢占已经分配出去的处理机。这种调度方式的优点是实现简单、系统开销小,适用于大多数批处理系统环境。缺点是难以满足紧急任务的要求,不适用于实时、分时系统要求。,进程调度的方式,剥夺(抢占)方式(Preemptive mode)这种调度方式,允许进程调度程序根据某个原则,去停止某个正在执行的进程,将已分配给进程的处理机,重新分配给另一个进程。抢占的原则有: 时间片原则。各进程按时间片运行,当一个时间片用完后,便停止该进程的执行而重新进行调度。这个原则适用于分时系统。 优先权原则。通常是对一些重要的和紧急的进程赋予较高的优先权。当这种进程进入就绪队列时,例如由阻塞态转换为就绪态,或从静止就绪态转为活动就绪态时,或新创建进入就绪态的进程进入就绪队列时,如果其优先权比正在执行的进程优先权高,便停止正在执行的进程,将处理机分配给优先权高的进程,使之执行。,2018/9/17,23,4.3.3 进程上下文切换,进程上下文由正文段、数据段、硬件寄存器的内容和有关数据结构等组成。 进程上下文切换包括4个步骤: 1. 决定是否作上下文切换以及是否允许做上下文切换。包括对进程调度原因的检查分析,以及当前执行进程的资格和CPU执行方式的检查等; 2. 保存当前执行进程的上下文。,2018/9/17,24,4.3.3 进程上下文切换(续),进程上下文切换的步骤: 3. 按照某个进程调度算法,选择一个处于就绪状态的进程。 4. 恢复或装配所选进程的上下文,将CPU控制权交给所选进程。,2018/9/17,25,4.3.4 进程调度性能评价,进程调度性能的衡量是操作系统设计的一个重要指标。 进程调度性能的定性衡量: 可靠性:如进程调度是否会破坏数据结构。 简洁性:调度程序不会太繁琐和复杂 进程调度性能的定量衡量: CPU利用率 进程等待-执行时间比 响应时间,2018/9/17,26,4.4 调度算法,先来先服务(FCFS) 时间片轮转法(Round robin) 多级反馈轮转法(round robin with multiple feedback) 优先级法(priority) 最短作业优先(shortest job first) 最高响应比优先(highest response_ratio next),2018/9/17,27,1. 先来先服务(FCFS),按照进程提交或进程变为就绪状态的先后次序,分派CPU; 当前进程占用CPU,直到执行完或阻塞,才出让CPU(非抢占方式)。 在进程唤醒后(如I/O完成),并不立即恢复执行,通常等到当前作业或进程出让CPU。 特点: 最简单的算法,表面上很公平; 比较有利于长作业,而不利于短作业。 有利于CPU繁忙的作业,而不利于I/O繁忙的作业。,2018/9/17,28,2.轮转法(Round Robin),将系统中所有的就绪进程按照FCFS原则,排成一个队列。 每次调度时将CPU分派给队首进程,让其执行一个时间片。时间片的长度从几个ms到几百ms。 在一个时间片结束时,发生时钟中断。 调度程序据此暂停当前进程的执行,将其送到就绪队列的末尾,并通过上下文切换执行当前的队首进程。 进程可以未使用完一个时间片,就出让CPU(如阻塞)。,2018/9/17,29,2.轮转法(Round Robin),轮转法调度:,完成,2018/9/17,30,2.轮转法(Round Robin) -时间片长度的确定,时间片长度变化的影响 过长退化为FCFS算法,进程在一个时间片内都执行完,响应时间长。 过短用户的一次请求需要多个时间片才能处理完,上下文切换次数增加,响应时间长。 对响应时间的要求: q(时间片) = R(响应时间)/Nmax(进程数目) 时间片长度的影响因素: 就绪进程的数目:数目越多,时间片越小(当响应时间一定时) 系统的处理能力:应当使用户输入通常在一个时间片内能处理完,否则使响应时间,平均周转时间和平均带权周转时间延长。,2018/9/17,31,3.多级反馈轮转法,把就绪队列按照进程到达就绪队列的类型和进程被阻塞时的原因分成不同的就绪队列; 每个队列按FCFS方式排列,各队列之间的进程享有不同的优先级,但同一队列内优先级相同; 当一个进程在执行完它的时间片后,或从睡眠中被唤醒以及被创建之后,将进入不同的就绪队列。,多级反馈队列:,2018/9/17,33,多级反馈轮转法的特点:,多级反馈轮转法不必事先知道各种进程所需的执行时间,仍能基本满足短进程优先和I/O频繁的进程优先的需要,因而是目前公认的较好的一种进程调度算法。在UNIX系统、WindowsNT、OS/2中都采用了类似的调度算法。,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号