《IT软件的项目管理》由会员分享，可在线阅读，更多相关《IT软件的项目管理（30页珍藏版）》请在金锄头文库上搜索。
1、第4章处理机调度n4.1分级调度 n4.2作业调度n4.3进程调度n4.4调度算法n4.5算法评价n4.6实时系统调度方法1.处理机调度概述n早期的计算机系统：n不存在处理机分配和调度n因为是一个作业独占n不同的现代操作系统提供的性能对CPU管理的要求n多道批处理系统：n增加作业的吞吐率n就要提高处理机的效率n作业搭配合理，充分利用系统资源n分时系统n交互式工作，必须提供较快的响应时间n必须考虑的时每个用户得到处理机的均等性n实时系统n处理机的响应时间n可见，操作系统的要求不同，处理机的管理策略也不同2.处理机调度概述n衡量调度策略的指标n周转时间：将一个作业提交给计算机系统后到该作业的结果返
2、回给用户所需要的时间n吞吐率：是指再给定时间内，一个计算机系统所完成的总工作量n响应时间：交互式进程从提交一个请求(命令)到接收到响应之间的时间间隔称响应时间n设备利用率：主要是指输入输出设备的使用情况3.4.1分级调度 n作业的概念 n作业:一个作业是指在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该次业务处理的全部工作n作业的过程有：提交、执行和输出等过程n作业执行过程要经过多级调度：n作业调度n交换调度n进程调度n线程调度4.作业的状态及其转换n提交状态：n一个作业在其处于从输入设备进入外部存储器的过程，称为提交状态n处于提交状态的作业，其信息没有全部进入系统，
3、所以不能被调度进程选取n收容状态也叫后备状态）：n输入管理程序不断将作业输入到输入井中，此时作业的信息正在从输入设备上预输入n此时作业预输入结束但尚未被创建进程不能执行），作业的 全部信息已经输入到输入井中5.作业的状态及其转换n作业调度高级调度(High Scheduling) ）：n作业调度程序从后备作业中选取若干个作业到内存投入运行n在每次执行作业调度时，都须做出以下两个决定。n 1) 接纳多少个作业 n 2) 接纳哪些作业 n作业的执行状态：n就绪：准备就绪n等待：等待资源n由进程调度决定执行那个作业真正执行6.作业的状态及其转换n完成状态：n作业运行完毕，但是其所占用的资源并没有完全
4、被系统回收n系统还需要做善后处理7.4.1.2 调度的层次n处理机调度：就是处理机的分配问题n参与进程调度的资格：必须是除处理机之外的所有资源都已经满足，也就是处于就绪状态。这些资源包括n内存n外设n相关的数据结构8.4.1.2 调度的层次n处理机调度层次4级）：n作业调度n交换调度n进程调度n线程调度9.4.1.2 调度的层次n作业调度高级调度(High Scheduling) ）：作业调度程序从后备作业中选取若干个作业到内存投入运行n在每次执行作业调度时，都须做出以下两个决定。n 1) 接纳多少个作业 n 2) 接纳哪些作业 10.4.1.2 调度的层次n交换调度中级调度又称中程调度(Me
5、dium-Term Scheduling) ） ： n 引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量。 n为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。 11.4.1.2 调度的层次n进程调度低级调度）：n 主要功能是决定哪些进程获得CPU进行工作。n系统同时必须进行进程上下文切换n并建立相应的执行环境n有两类低级调度方式：n第一类称
6、剥夺方式：n高优先级剥夺原则被剥夺的进程加入到就绪队列的最前面）n时间片剥夺原则n短作业(进程)优先原则n第二类称非剥夺方式n某进程或线程占有CPU后不再出让，直到运行结束或发生了某事件不能继续运行12.4.1.2 调度的层次n不同的操作系统具有不同的调度n多道批处理系统存在：n作业调度n进程调度n分时系统和实时系统中存在：n进程调度n交换调度n线程调度n不存在作业调度，因为为了缩短时间，作业是直接建立在内存中13.调度队列模型调度队列模型 1. 仅有进程调度的调度队列模型仅有进程调度的调度队列模型 仅具有进程调度的调度队列模型 14.2. 具有高级和低级调度的调度队列模型具有高级和低级调度的
7、调度队列模型 具有高、低两级调度的调度队列模型 15.(1)就绪队列的形式。(2) (3)(2) 设置多个阻塞队列。 上图示出了具有高、低两级调度的调度队列模型。该模型与前一模型的主要区别在于如下两个方面。 16.3. 同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型 具有三级调度时的调度队列模型 17.4.1.3作业与进程的关系n作业(JOB)：是用户提交给OS计算的一个独立任务n例如：n一次计算n一次控制过程n作业的四个阶段：n提交、收留、执行和完成n是一个动态的概念n关系：n作业是任务实体，是用户提交给OS计算的一个独立任务；n进程是完成任务的执行实体；是系统分配资源的基本单
8、位；n没有作业任务，进程无事可干，没有进程，作业任务没法完成。n一个作业总是由一个以上的进程构成；n作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系统。18.4.2作业调度n作业调度主要完成的状态变换n完成作业从后备作业到执行状态的转变n完成从执行状态的转换19.4.2.1作业调度功能n(1) 记录系统中各作业的状况，包括执行阶段的有关情况n系统通常为每个作业建立一个作业控制块JCB）n不同的操作系统，其JCB的内容是不同的nJCB基本的信息20.4.2.1作业调度功能n作业名：是系统课识别的作业标志符n作业类型n计算机型：要求CPU时间多n管理型：要求输入输出量大n图形设
9、计型：要求高速图形显示n资源要求n作业估计执行时间n要求最迟完成时间n要求内存量和外存量n要求外设类型及数量n资源使用情况n作业进入系统时间：指作业全部进入输入井，作业的状态为后备状态的时间。n开始时间：作业被选中，状态由后备状态转变为执行状态的时间n已执行时间n内存地址n外设数量等n优先级别：可由用户产生，也可以由系统自动计算产生21.4.2.1作业调度功能n（2） 从后备队列中选取一部分作业投入运行n根据调度算法从后备作业队列中选取若干个作业投入运行n（3） 为被选中的作业做好执行前的准备工作n为选中的作业建立进程n为这些进程分配它们所学要的资源22.4.2.1作业调度功能n（4） 在作业
10、执行结束后做善后的处理n输出作业管理信息，如执行时间等n回收该作业所占用的资源n撤销与该作业有关的全部进程和该作业的作业控制块等23.作业调度中状态的转换过程 24.4.2.2作业调度目标与性能衡量n作业调度目标n对所有的作业应该是公平合理的n应使设备有高的利用率n每天执行尽可能多的作业n有快的响应时间n各个目标之间有一定的冲突，不可能同时满足n衡量调度算法的优劣的标准n周转时间n带权周转时间25.1. 周转时间n周转时间：将一个作业提交给计算机系统后到该作业的结果返回给用户所需要的时间n作业i的周转时间Ti为nTi Tei TsinTei 作业i的完成时间nTsi 作业i的提交时间nTi包括
11、量部分：作业的等待时间和作业的执行之间nTi Twi TrinTwi 作业i由后备状态到执行状态的等待时间nTri 作业i执行时间nN个作业的平均周转时间为：nT(1/n) 11nTi26.进程进程到达时间到达时间服务时间服务时间 A03B26C44D65E82假设一个系统有5个进程，他们的到达时间和服务时间如上表所示，忽略I/O以及其他的开销时间，若分别按先来先服务FCFS）、非抢占式及抢占的短进程优先SJF调度算法进行CPU调度，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。 27.进程进程ABCDE平平均均FCFS完成时间完成时间39131820周转时间
12、周转时间37912128.6带权周转带权周转时间时间11.172.252.462.56SJF（非抢占）（非抢占）完成时间完成时间39152011周转时间周转时间37111437.6带权周转带权周转时间时间11.172.752.81.51.84SJF（抢占）（抢占）完成时间完成时间31582010周转时间周转时间31341427.2带权周转带权周转时间时间12.1612.811.59进进程程到达到达时时间间服服务务时时间间 A03B26C44D65E8228.2. 带权周转时间n为了进一步反映调度性能，使用带权周转时间n带权周转时间:是作业的周转时间与作业的执行时间之比n作业i的带权周转时间Wi
13、为nWi Ti/ TrinN个作业的平均带权周转时间为：nW(1/n) 11nWi29.进程进程ABCDE平平均均FCFS完成时间完成时间39131820周转时间周转时间37912128.6带权周转带权周转时间时间11.172.252.462.56SJF（非抢占）（非抢占）完成时间完成时间39152011周转时间周转时间37111437.6带权带权周周转转时间时间11.172.752.81.51.84SJF（抢占）（抢占）完成时间完成时间31582010周转时间周转时间31341427.2带权周转带权周转时间时间12.1612.811.59进进程程到达到达时时间间服服务务时时间间 A03B26C44D65E8230.
