《2019年操作系统课程第3章处理机调度ppt课件.ppt》由会员分享，可在线阅读，更多相关《2019年操作系统课程第3章处理机调度ppt课件.ppt（161页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益4/25/20231为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益第三章第三章第三章第三章 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁q 处理机调度的基本概念处理机调度的基本概念 v处理机调度的目标充分有效地利用处理机（CPU）资源q 调度算法调度算法 q 实时调度实时调度 q 产生死锁的原因和必要条件产生死锁的原因和必要条件 q 预防死锁的方法预防死锁的方法 q 死锁的检测与解除死锁的检
2、测与解除4/25/20232为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.1 3.1 处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念 q操作系统操作系统调度调度级别级别q进程调度的任务进程调度的任务q确定算法的原则确定算法的原则q进程调度方式进程调度方式q调度队列模型调度队列模型q选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则4/25/20233为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.1处理
3、机调度的基本概念处理机调度的基本概念3.1.1操作系统操作系统调度调度级别级别1.高级调度高级调度2.低级调度低级调度3.中级调度中级调度4/25/20234为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.1.1 3.1.1 高级、中级和低级调度高级、中级和低级调度高级、中级和低级调度高级、中级和低级调度q1.1.高级调度高级调度 又称又称作业调度作业调度v主要任务是按一定的原则对外存上处于后备主要任务是按一定的原则对外存上处于后备状态的作业进行选择，给选中的作业状态的作业进行选择，给选中的作业分配分配内内存、输入存、输入
4、/输出设备等输出设备等必要的资源必要的资源，并，并建立建立相相应的应的进程进程，插插入入就绪就绪队列队列，以使该作业的进，以使该作业的进程获得竞争处理机的权利程获得竞争处理机的权利4/25/20235作作 业业 调调 度度 q作业作业是用户在一次解题或一个事务处理过程是用户在一次解题或一个事务处理过程中中要求计算机系统所做工作的集合要求计算机系统所做工作的集合，包括用，包括用户程序、所需的数据及命令等户程序、所需的数据及命令等q作作业业状状态态:作作业业从从提提交交给给系系统统，直直到到完完成成任任务务后后退退出出系系统统前前，在在整整个个活活动动过过程程中中它它会会处处于于不不同同的的状状态
5、态。通通常常，作作业业状状态态分分为为四四种种：提交、提交、后备、后备、执行和完成执行和完成，如图如图3-1所示。所示。4/25/20236为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益运行状态运行状态作作 业业 调调 度度 后备状态后备状态完成状态完成状态就绪就绪阻塞阻塞执行执行I/O完成完成I/O请求请求时间片完时间片完作业作业提交提交作业作业调度调度进程进程调度调度终止终止作业作业q作业作业状态间转换状态间转换图图3-1作业的基本状态作业的基本状态4/25/20237为了规范事业单位聘用关系，建立和完善适应社会主义市场
6、经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益数据提交状态退出状态后备状态运行状态作业控制进程 输入设备数据源程序输出设备作业说明书输入井运行等待就绪输出井输入程序输出程序作业调度进程调度4/25/20238 （1）提交状态提交状态即用户向系统提交一个作业时，即用户向系统提交一个作业时，该作业所处的状态。该作业所处的状态。（2）后备状态后备状态即用户作业经输入设备（如读卡机）即用户作业经输入设备（如读卡机）送入输入井（磁盘）中存放，送入输入井（磁盘）中存放，等待进入内存时所处的等待进入内存时所处的状况。状况。（3）执行状态执行状态即作业分配到所需的资源，即作业分配到所需的资源
7、，被调被调入内存，入内存，并且在处理机（并且在处理机（CPU）上执行相应的程序时所）上执行相应的程序时所处的状况。处的状况。（4）完完成成状状态态即即作作业业完完成成了了计计算算任任务务，结结果果由由打打印印机机输输出出，最最后后由由系系统统回回收收分分配配给给它它的的全全部部资资源源，准备退出系统时的作业状况。准备退出系统时的作业状况。作业状态作业状态4/25/20239q 作业控制块作业控制块（JCB）q 在多道批处理系统中通常有上百个作业被收在多道批处理系统中通常有上百个作业被收容在容在输入井输入井（磁盘）中。（磁盘）中。为了管理和调度作为了管理和调度作业，业，系统为每个作业设置了一个作
8、业控制块系统为每个作业设置了一个作业控制块（JCB），），它记录该作业的有关信息。它记录该作业的有关信息。JCB的的主要内容如图主要内容如图3-2所示。所示。作作 业业 调调 度度 4/25/202310图3-2 作业控制块 4/25/202311 作业调度的功能作业调度的功能作业调度的功能作业调度的功能 作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转换。(1)记录系统中各个作业的情况。(2)按照某种调度算法从后备作业队列中挑选作业。(3)为选中的作业分配内存和外设等资源。(4)为选中的作业建立相应的进程。(5)作业结束后进行善后处理工作，如输出必要的信息，收回该作
9、业所占用的全部资源，撤消与该作业相关的全部进程和该作业的JCB。4/25/202312为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益高级、中级和低级调度高级、中级和低级调度高级、中级和低级调度高级、中级和低级调度在每次作业调度时，须决定：在每次作业调度时，须决定：v接纳多少个作业接纳多少个作业 即允许多少个作业同时在内存中运行即允许多少个作业同时在内存中运行作业太多作业太多 服务质量下降服务质量下降作业太少作业太少 资源利用率低资源利用率低v接纳哪些作业接纳哪些作业 取决于作业调度算法取决于作业调度算法先来先服务先来先服务短
10、作业优先短作业优先作业优先权调度作业优先权调度响应比调度响应比调度周转时间太长系统吞吐量太低 适当的折衷周周周周转转转转时时时时间间间间：从从作作业业被被提提交交给给系系统统开开始始，到到作作业业完完成成为为止的这段时间间隔。止的这段时间间隔。吞吐量吞吐量吞吐量吞吐量：是指在单位时间内系统所完成的作业数。：是指在单位时间内系统所完成的作业数。4/25/202313为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.1.1 3.1.1 高级、中级和低级调度高级、中级和低级调度高级、中级和低级调度高级、中级和低级调度2.2.中级调
11、度中级调度v目的：是目的：是为了提高内存利用率和系统吞吐量为了提高内存利用率和系统吞吐量。q功能功能：暂时不能运行的暂时不能运行的进程挂起进程挂起，释放宝贵的内存资源。，释放宝贵的内存资源。具备条件时：把外存上的就绪进程，重新调入内存，挂在就绪队具备条件时：把外存上的就绪进程，重新调入内存，挂在就绪队列上等待进程调度。列上等待进程调度。外存外存外存外存 阻塞队列阻塞队列阻塞队列阻塞队列 阻塞进程队列阻塞进程队列阻塞进程队列阻塞进程队列 作业作业作业作业4 4 作业作业作业作业3 3 作业作业作业作业2 2 作业作业作业作业1 1 进程进程进程进程3 3 进程进程进程进程2 2 进程进程进程进程
12、1 1 内存内存内存内存 4/25/202314为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.1.1 3.1.1 高级、中级和低级调度高级、中级和低级调度高级、中级和低级调度高级、中级和低级调度3.3.低级调度低级调度 进程调度进程调度v主要任务是按照某种主要任务是按照某种策略和方法策略和方法选取选取一一个处于个处于就绪就绪状态的进程，将处理机状态的进程，将处理机分分配配给它给它v常见的低级调度有常见的低级调度有非抢占式非抢占式和和抢占式抢占式两两种种4/25/202315为了规范事业单位聘用关系，建立和完善适应社会主义
13、市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益处理机调度的层次处理机调度的层次4/25/202316为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益 q作业调度又称为1，它决定将那些在外存储器上的处于2状态的作业调入主机内存，系统经作业调度程序选中一个或多个作业后，就为它们分配必要的内存、设备及软资源。然后控制权就交给了3，由3将它们变为一个或一组4。1()：A、高级调度 B、低级调度 C、中级调度 D、进城调度 2（）：A、就绪 B、阻塞 C、提交 D、后备 3（）：A、存储管理模块 B、处理机管理模块
14、 C、文件管理模块 D、设备管理模块 4（）：A、指令 B、子程序 C、进程 D、程序段 4/25/202317为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益q处于后备状态的作业存放在（）中。A、外存 B、内存 C、A和B D、扩展内存q在操作系统中，作业处于（）状态时，已处于进程的管理之下。A、后备 B、阻塞 C、执行 D、完成4/25/202318为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.13.1处理机调度的基本概念处理机调度的基本概念处理机调
15、度的基本概念处理机调度的基本概念 q 高级、中级和低级调度高级、中级和低级调度q 进程调度的任务进程调度的任务q 确定算法的原则确定算法的原则q 进程调度方式进程调度方式q 调度队列模型调度队列模型q 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则4/25/202319为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.1.2 3.1.2 进程调度的任务进程调度的任务进程调度的任务进程调度的任务q 进程调度的任务进程调度的任务 是是控制、协调进程控制、协调进程对对CPUCPU的竞争的竞争,即按一定的即按一定的
16、调度算法从就绪队列中选中一个进程，把调度算法从就绪队列中选中一个进程，把CPUCPU的的使用权交给被选中的进程使用权交给被选中的进程4/25/202320为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念 q 高级、中级和低级调度高级、中级和低级调度q 进程调度的任务进程调度的任务q 确定算法的原则确定算法的原则q 进程调度方式进程调度方式q 调度队列模型调度队列模型q 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则4/25/202
17、321为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.1.3 3.1.3 确定算法的原则确定算法的原则确定算法的原则确定算法的原则q 具有具有公平性公平性q 资源资源利用率高利用率高（特别是（特别是CPUCPU利用率）利用率）q 在交互式系统情况下要追求在交互式系统情况下要追求响应时间响应时间（越短越好）（越短越好）q 在批处理系统情况下要追求系统在批处理系统情况下要追求系统吞吐量吞吐量4/25/202322为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益
18、处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念 q 高级、中级和低级调度高级、中级和低级调度q 进程调度的任务进程调度的任务q 确定算法的原则确定算法的原则q 进程调度方式进程调度方式q 调度队列模型调度队列模型q 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则4/25/202323为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.1.43.1.4进程调度方式进程调度方式进程调度方式进程调度方式q非抢占方式非抢占方式q抢占方式抢占方式4/25/202324为了规范事业单位聘
19、用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益进程调度方式进程调度方式进程调度方式进程调度方式q非抢占方式非抢占方式(Non-preemptive Mode)(Non-preemptive Mode)引起进程调度的因素引起进程调度的因素正在执行的进程执行完毕，正在执行的进程执行完毕，或因发生某事或因发生某事件而不能再继续执行件而不能再继续执行执行中的进程因提出执行中的进程因提出I/OI/O请求而暂停执行；请求而暂停执行；在进程通信或同步过程中执行了某种原语在进程通信或同步过程中执行了某种原语操作，如操作，如waitwait、BlockBloc
20、k、WakeupWakeup原语原语优点优点：算法简单，：算法简单，系统开销小系统开销小缺点缺点：紧急任务不：紧急任务不能及时响应；短进能及时响应；短进程到达要等待长进程到达要等待长进程运行结束程运行结束4/25/202325为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益进程调度方式进程调度方式进程调度方式进程调度方式q抢占方式抢占方式q 抢占式调度主要有以下原则抢占式调度主要有以下原则优先权原则优先权原则 允许高优先权的新到进程抢允许高优先权的新到进程抢占当前进程的处理机占当前进程的处理机短作业短作业(进程进程)优先原则优
21、先原则允许执行时间短允许执行时间短的新到进程抢占当前进程的处理机的新到进程抢占当前进程的处理机 时间片原则时间片原则 时间片用完后停止执行，时间片用完后停止执行，重新进行调度，适用于分时系统重新进行调度，适用于分时系统 优点优点：适于时间要：适于时间要求严格的实时系统求严格的实时系统缺点缺点：调度算法复：调度算法复杂，系统开销大杂，系统开销大4/25/202326为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.13.1处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念 q 高级、中级和低级调度
22、高级、中级和低级调度q 进程调度的任务进程调度的任务q 确定算法的原则确定算法的原则q 进程调度方式进程调度方式q 调度队列模型调度队列模型q 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则4/25/202327为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.1.5 3.1.5 调度队列模型调度队列模型调度队列模型调度队列模型q仅有进程调度的调度队列模型仅有进程调度的调度队列模型q具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型q同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型
23、4/25/202328为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.1.5 3.1.5 调度队列模型调度队列模型调度队列模型调度队列模型q仅有进程调度的调度队列模型仅有进程调度的调度队列模型v在分时系统中，通常仅设有进程调度在分时系统中，通常仅设有进程调度v系统把这些进程组织成一个系统把这些进程组织成一个就绪队列就绪队列v每个进程在执行时，可能有以下几种情况每个进程在执行时，可能有以下几种情况进程获得进程获得CPUCPU正在执行正在执行任务在给定时间片内任务在给定时间片内已完成已完成，释放处理，释放处理机后为完成状态机后
24、为完成状态任务在时间片内任务在时间片内未完成未完成，进入就绪队列，进入就绪队列末尾末尾在执行期间因某事件而阻塞在执行期间因某事件而阻塞4/25/202329为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.1.5 3.1.5 调度队列模型调度队列模型调度队列模型调度队列模型q仅有进程调度的调度队列模型仅有进程调度的调度队列模型就就 绪绪队队 列列阻阻 塞塞队队列列进程调度进程调度CPU进程完成进程完成等待事件等待事件交互用户交互用户事事件件出出现现时间片完时间片完4/25/202330为了规范事业单位聘用关系，建立和完善适应
25、社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.1.5 3.1.5 调度队列模型调度队列模型调度队列模型调度队列模型q具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型v在批处理系统中，不仅需要在批处理系统中，不仅需要进程调度进程调度，而，而且还要有且还要有作业调度作业调度v就绪队列的形式就绪队列的形式在批处理系统中，常用高优先权队列。在批处理系统中，常用高优先权队列。进程进入就绪队列时，按优先权高低插进程进入就绪队列时，按优先权高低插入相应位置，调度程序总是把处理机分入相应位置，调度程序总是把处理机分配给就绪队首进程配给就绪队首进程v设置多个阻塞
26、队列设置多个阻塞队列根据事件的不同设置多个队列提高效率根据事件的不同设置多个队列提高效率4/25/202331为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.1.5 3.1.5 调度队列模型调度队列模型调度队列模型调度队列模型进程调度进程调度CPU进程完成进程完成时间片完时间片完就就 绪绪队队列列12等待事件等待事件等待事件等待事件等待事件等待事件n12n事件事件 出现出现事件事件 出现出现事件事件 出现出现后后备备 队队列列作业作业调度调度与上一模型的主要区别：就绪队列的形式；与上一模型的主要区别：就绪队列的形式；设置多
27、个阻塞队列设置多个阻塞队列阻阻队队列列塞塞2 2阻阻队队列列塞塞n n阻阻队队列列塞塞1 14/25/202332为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.1.5 3.1.5 调度队列模型调度队列模型调度队列模型调度队列模型q同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型就绪队列就绪队列进程调度进程调度就绪，挂起队列就绪，挂起队列中级调度中级调度阻塞，挂起队列阻塞，挂起队列阻塞队列阻塞队列等待事件等待事件进程完成进程完成时间片完时间片完作业调度作业调度交互型作业交互型作业后备队列后备队列批量作业批量作业
28、挂起挂起事件出现事件出现事事件件出出现现事件出现事件出现CPU4/25/202333为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.1 3.1 处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念 q 高级、中级和低级调度高级、中级和低级调度q 进程调度的任务进程调度的任务q 确定算法的原则确定算法的原则q 进程调度方式进程调度方式q 调度队列模型调度队列模型q选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则如果你是用户，你希望系统如何为你服务，如何考虑？如果你是用户，你希望系统
29、如何为你服务，如何考虑？如果你是调度者，从系统整体角度出发，应如何考虑？如果你是调度者，从系统整体角度出发，应如何考虑？4/25/202334为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.1.6选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则1.面向用户的准则面向用户的准则2.面向系统的准则面向系统的准则4/25/202335为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.1.6选择调度方式和调度算法的若干准则选择调度方式和调度算法的
30、若干准则1.面向用户的准则面向用户的准则(1)周转时间短。周转时间短。(2)响应时间快。响应时间快。(3)截止时间的保证。截止时间的保证。(4)优先权准则。优先权准则。4/25/202336为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则q面向用户的准则面向用户的准则v周转时间短周转时间短平均周转时间平均周转时间带权周转时间：带权周转时间：进程（或作业）的进程（或作业）的周转时周转时间间T T与系统为
31、它与系统为它提供服务的时间提供服务的时间T TS S之比，即之比，即W=T/TW=T/TS S。而。而平均带权周转时间平均带权周转时间则可表示为则可表示为:4/25/202337为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益 通常把通常把周转时间周转时间作为评价批处理系统的性能、选择作业作为评价批处理系统的性能、选择作业调度方式与算法的准则。调度方式与算法的准则。所所谓谓周周转转时时间间，是是指指从从作作业业提提交交给给系系统统开开始始，到到作作业业完完成为止的这段时间间隔成为止的这段时间间隔(称为作业周转时间称为作业周转时
32、间)。它包括：它包括：(1)(1)作业在外存后备队列上等待作业在外存后备队列上等待(作业作业)调度的时间；调度的时间；(2)(2)进程在就绪队列上等待进程调度的时间；进程在就绪队列上等待进程调度的时间；(3)(3)进程在进程在CPUCPU上执行的时间；上执行的时间；(4)(4)等待等待I IO O操作完成的时间。操作完成的时间。其其中中，第第(2)(2)、(3)(3)、(4)(4)项项在在一一个个作作业业的的处处理理过过程程中中，可可能能发发生多次。生多次。4/25/202338为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益
33、可把平均周转时间描述为可把平均周转时间描述为：作作业业的的周周转转时时间间T与与系系统统为为它它提提供供服服务务的的时时间间TS之之比比，即即W=T/TS，称称为为带带权权周周转转时时间间，而而平平均均带带权权周周转转时时间间则则可可表示为表示为:系统以多个用户都满意为目标系统以多个用户都满意为目标周转时间服务时间周转时间服务时间周转时间完成时间到达时间周转时间完成时间到达时间4/25/202339为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则选择调度方式和调度
34、算法的若干准则选择调度方式和调度算法的若干准则q面向用户的准则面向用户的准则v响应时间快响应时间快响应时间响应时间是指从用户通过键盘提交一个请求是指从用户通过键盘提交一个请求开始，直至系统中开始，直至系统中首次首次产生产生响应响应为止的时间为止的时间v截止时间保证截止时间保证截止时间截止时间是指某任务必须开始执行的最迟时是指某任务必须开始执行的最迟时间或必须完成的最迟时间间或必须完成的最迟时间截止时间是截止时间是实时系统实时系统中的重要指标中的重要指标4/25/202340为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益选择调
35、度方式和调度算法的若干准则选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则q面向用户的准则面向用户的准则v等待时间短等待时间短等待时间等待时间是在就绪队列中等待所花的时间是在就绪队列中等待所花的时间调度算法并不影响进程运行和执行调度算法并不影响进程运行和执行I/O的时的时间量；只影响进程在就绪队列中等待所花费间量；只影响进程在就绪队列中等待所花费的时间的时间v优先权准则优先权准则在在批处理批处理、实时实时和和分时系统分时系统中都可以选择优中都可以选择优先权准则，以便让紧急任务先处理先权准则，以便让紧急任务先处理有时还选择抢占式调度方式有时还选择抢
36、占式调度方式4/25/202341为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则q面向系统的准则面向系统的准则v系统吞吐量高系统吞吐量高吞吐量吞吐量指单位时间内系统所完成的作业数指单位时间内系统所完成的作业数作业调度的方式和算法对吞吐量的大小有较作业调度的方式和算法对吞吐量的大小有较大影响大影响v处理机利用率高处理机利用率高v各类资源的平衡利用各类资源的平衡利用使内存、外存和使内存、外存和I/OI/
37、O设备的利用率高设备的利用率高基于这样的准则，你设计操作系统的调度策略应如何？基于这样的准则，你设计操作系统的调度策略应如何？4/25/202342为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益q（）是指从作业提交给系统到作业完成的时间间隔。A周转时间 B、响应时间 C、等待时间 D、运行时间q 作业从进入后备队列到被调度程序选中的时间间隔成为（）。A周转时间 B、响应时间 C、等待时间 D、触发时间q在批处理系统中，周转时间是（）。A、作业运行时间 B、作业等待时间和运行时间之和 C、作业的相对等待时间 D、作业被调度进入
38、内存到运行完毕的时间4/25/202343为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益第三章第三章第三章第三章 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁q处理机调度的基本概念处理机调度的基本概念 q调度算法调度算法 q实时调度实时调度 q产生死锁的原因和必要条件产生死锁的原因和必要条件 q预防死锁的方法预防死锁的方法 q死锁的检测与解除死锁的检测与解除4/25/202344为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.2 3.
39、2 调度算法调度算法调度算法调度算法q在在OS中中调度的实质是一种资源分配调度的实质是一种资源分配，因而，因而调度算法是指：根据系统的资源分配策略调度算法是指：根据系统的资源分配策略所规定的资源分配算法所规定的资源分配算法q问题提出问题提出q如何制定分配策略：对不同的系统和系统如何制定分配策略：对不同的系统和系统目标，通常采用不同的算法，如短作业优目标，通常采用不同的算法，如短作业优先，时间片轮转等先，时间片轮转等q有些算法适用于作业调度，有些适用于进有些算法适用于作业调度，有些适用于进程调度，有些两者皆可程调度，有些两者皆可4/25/202345为了规范事业单位聘用关系，建立和完善适应社会主
40、义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益调度算法调度算法调度算法调度算法q 先来先服务和短作业优先算法先来先服务和短作业优先算法q 高优先权优先调度算法高优先权优先调度算法q 基于时间片的轮转调度算法基于时间片的轮转调度算法4/25/202346为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.2.13.2.1先来先服务和短作业优先算法先来先服务和短作业优先算法先来先服务和短作业优先算法先来先服务和短作业优先算法q先来先服务先来先服务(FCFS)/先进先出先进先出(FIFO)调度算法调度算法v按
41、照作业按照作业/进程进入系统的进程进入系统的先后次序先后次序进行调度，进行调度，先进入系统者先调度；即启动等待时间最长的先进入系统者先调度；即启动等待时间最长的作业作业/进程进程v是一种最简单的调度算法，即可用于是一种最简单的调度算法，即可用于作业调度作业调度，也可用于也可用于进程调度进程调度q几个术语几个术语v到达时间、服务时间、开始时间到达时间、服务时间、开始时间v完成时间、等待时间完成时间、等待时间v周转时间：完成时间周转时间：完成时间-到达时间到达时间v带权周转时间：周转时间带权周转时间：周转时间/服务时间服务时间4/25/202347为了规范事业单位聘用关系，建立和完善适应社会主义市
42、场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益先来先服务和短作业优先算法先来先服务和短作业优先算法先来先服务和短作业优先算法先来先服务和短作业优先算法04A13B25C32D44E044476先来先服务（先进先出）：先来先服务（先进先出）：712101214111418141225.53.592.8A A A A B B B C C C C C D D E E E E05101518t4/25/202348为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益先来先服务和短作业优先算法先来先服务和短作业优先算法先
43、来先服务和短作业优先算法先来先服务和短作业优先算法q先来先服务先来先服务（先进先出）（先进先出）优缺点优缺点v比较有利于比较有利于长作业（进程）长作业（进程），而不利于，而不利于短作短作业（进程）业（进程）v有利于有利于CPU繁忙型作业（进程）繁忙型作业（进程），而不利于，而不利于I/O繁忙型作业（进程）繁忙型作业（进程）v用于批处理系统，不适于分时系统用于批处理系统，不适于分时系统4/25/202349为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益先来先服务和短作业优先算法先来先服务和短作业优先算法先来先服务和短作业优先算
44、法先来先服务和短作业优先算法q短作业短作业(进程进程)优先调度算法优先调度算法SJ(P)FSJ(P)Fv短作业短作业(进程进程)优先调度算法优先调度算法SJ(P)FSJ(P)F，以要求，以要求运运行时间长短行时间长短进行调度，即启动要求运行时间最进行调度，即启动要求运行时间最短的作业短的作业v可以分别用于可以分别用于作业调度作业调度和和进程调度进程调度v短作业优先短作业优先(SJF)(SJF)的调度算法，是从后备队列的调度算法，是从后备队列中选择一个或若干个中选择一个或若干个估计运行时间估计运行时间最短的作业，最短的作业，将它们调入内存运行；而短进程优先将它们调入内存运行；而短进程优先(SPF
45、)(SPF)调调度算法，则是从就绪队列中选出一度算法，则是从就绪队列中选出一估计运行时估计运行时间间最短的进程，将处理机分配给它，使它立即最短的进程，将处理机分配给它，使它立即执行并一直执行到完成执行并一直执行到完成，或，或发生某事件发生某事件而被阻而被阻塞放弃处理机时，再重新调度塞放弃处理机时，再重新调度4/25/202350为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益先来先服务和短作业优先算法先来先服务和短作业优先算法先来先服务和短作业优先算法先来先服务和短作业优先算法04A13B25C32D44E0441短作业短作业
46、/短进程优先（短进程优先（SJF/SPF）：）：4633/26988/391399/413181616/540/52.1A A A AB B BC C C C CD DE E E E05101518t4/25/202351为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益qFCFS/SJF调度算法的性能调度算法的性能先来先服务和短作业优先算法先来先服务和短作业优先算法先来先服务和短作业优先算法先来先服务和短作业优先算法SJFSJF平均周转平均周转时间和平均带时间和平均带权周转时间明权周转时间明显改善显改善4/25/202352为
47、了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益SJFSJF的特点的特点的特点的特点q优点优点：v比比FCFS改善改善平均周转时间平均周转时间和和平均带权周转时间平均带权周转时间，缩短，缩短作业的等待时间；作业的等待时间；v提高系统的提高系统的吞吐量吞吐量。q缺点缺点：v对长作业非常不利对长作业非常不利，可能长时间得不到执行；，可能长时间得不到执行；v未能依据作业的未能依据作业的紧迫程度紧迫程度来划分执行的优先级；来划分执行的优先级；v难以准确估计作业（进程）的执行时间难以准确估计作业（进程）的执行时间，从而影响调，从而影响调度
48、性能。度性能。4/25/202353为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益调度算法调度算法调度算法调度算法q先来先服务和短作业优先算法先来先服务和短作业优先算法q高优先权优先调度算法高优先权优先调度算法q基于时间片的轮转调度算法基于时间片的轮转调度算法4/25/202354为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.2.23.2.2高优先权优先高优先权优先高优先权优先高优先权优先（HPFHPF，HighestPriorityFirstHigh
49、estPriorityFirst）调度调度调度调度算法算法算法算法q优先权调度算法的类型优先权调度算法的类型v非抢占式非抢占式优先权调度算法优先权调度算法v抢占式抢占式优先权调度算法优先权调度算法4/25/202355为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益高优先权优先高优先权优先高优先权优先高优先权优先（HPFHPF，HighestPriorityFirstHighestPriorityFirst）调度算法调度算法调度算法调度算法q优先权调度算法的类型优先权调度算法的类型v非抢占式非抢占式优先权调度算法优先权调度算法
50、特点：系统一旦把处理机分配给就绪队特点：系统一旦把处理机分配给就绪队列中列中优先权最高优先权最高的进程后，该进程便的进程后，该进程便一一直执行直执行下去，直至完成，或因发生某事下去，直至完成，或因发生某事件使该进程放弃处理机时，系统才将处件使该进程放弃处理机时，系统才将处理机重新分配给另一优先权最高的进程理机重新分配给另一优先权最高的进程主要主要用于批处理系统用于批处理系统中，也可用于某些中，也可用于某些对实时性对实时性要求不严的实时系统要求不严的实时系统中中4/25/202356为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权