大工20秋《操作系统》辅导资料六

易百网

操作系统辅导资料六主    题：第五章的辅导资料
学习时间：2020年11月2日--11月8日
“不忘初心、牢记使命”主题理论学习：我们党要始终成为时代先锋、民族脊梁，始终成为马克思主义执政党，自身必须始终过硬。全党要更加自觉地坚定党性原则，勇于直面问题，敢于刮骨疗毒，消除一切损害党的先进性和纯洁性的因素，清除一切侵蚀党的健康肌体的病毒，不断增强党的政治领导力、思想引领力、群众组织力、社会号召力，确保我们党永葆旺盛生命力和强大战斗力。
摘选自《决胜全面建成小康社会，夺取新时代中国特色社会主义伟大胜利》内    容：第五章
这周我们将继续学习课件第五章  处理器调度（处理器调度，处理器调度算法，实时调度与进程切换）。本章的学习要求及需要掌握的重点内容如下：
基本要求：
1．了解处理器调度的基本概念
2. 掌握处理器调度的基本算法
重点掌握内容：
1．重点：处理器调度的基本概念，调度算法。
2．难点：调度算法。处理器调度
课前问题：
1.什么是处理器调度？
2.处理器调度分为哪几类？
3.如何选择调度算法？1. 处理器调度就是按照一定的规则分配处理器。在多道程序环境中，一个作业提交后，必须经过处理器调度，方能获得处理器而运行。不同类型的作业，需要经历的调度各不相同。
对批处理作业而言，一般需要先后经历高级调度（作业调度）和低级调度（进程调度）方能获得处理器；
而对于交互型的终端作业，通常只需经过低级调度（进程调度）就可以获得处理器。
除了高级调度和低级调度以外，在一些比较完善的操作系统中，还设置了中级调度。每一种调度可以采用不同的调度方式和调度算法来实现。
各种调度类型与进程状态之间的关系图如下
/2.调度分类
低级调度又称为短程调度，在没有引入线程的操作系统中被称为进程调度，而在多线程操作系统中被称为线程调度。低级调度的功能是根据某种原则，将处理机分配就绪队列中的某个进程或线程，然后进行进程（线程）切换，使选中的进程（线程）执行。
低级调度是操作系统中最基本的一种调度，是操作系统中最核心的部分，各种操作系统中都必须配置这级调度。由于低级调度十分频繁，其调度策略的优劣直接影响整个系统的性能，因此，用于低级调度的这部分代码必须精心设计，且常驻内存。
存在两种低级调度方式：1） 非抢占调度方式2）抢占调度方式
（1） 非抢占调度方式
在采用非抢占调度方式时，可能引起进程调度的因素可归结为这样几个：
① 正在执行的进程执行完毕， 或因发生某事件而不能再继续执行；
② 执行中的进程因提出I/O请求而暂停执行；
③ 在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语、Wakeup原语等。
优点：实现简单、系统开销小，适用于大多数的批处理系统环境。
缺点：但它难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果。显然，在要求比较严格的实时系统中，不宜采用这种调度方式。
（2）抢占调度方式
又称为剥夺方式。若采用这种调度方式，则允许调度程序根据某种原则，暂停当前正在执行的进程（线程），将处理机重新分配给另一个就绪进程（线程）。
抢占的原则有：
1）优先权原则
2）短作业(进程)优先原则
3）时间片原则  
低级调度是各类操作系统必须具备的一种调度。在最简单的分时操作系统和实时操作系统中，可以只设置低级调度。与低级调度相关联的进程（线程）队列称为就绪队列。就绪队列可以按照多种方式进行组织（FIFO原则、优先权原则、短进程优先原则），若按先进先出原则组织，并采用时间片原则进行调度，则只有低级调度的处理机调度模型如下所示。
/
高级调度又称为长程调度、接纳调度、作业调度。该调度与作业有关。
作业：用户交给计算机所做的工作，由程序、数据和作业说明书三部分组成。
作业类型：
（1）交互式作业（终端作业或联机作业）
这类作业主要出现在分时系统和个人计算机中，作业常通过命令方式提供，作业直接提交到内存。
（2）批处理作业（脱机作业）
这类作业要求用户预先将作业的三部分准备好，然后在系统的控制下通过某种作业输入方式（脱机输入方式、SPOOLing方式等）将它们提交到外部辅助存储器上，同时为该作业申请一个作业控制块JCB，于是，一个作业被建立起来。批处理作业建立起来后，以后的启动运行就不再需要用户干预，系统会根据作业说明书来控制作业的执行过程。
把外存中的作业按一定的方式组织成队列形式，称为后备队列。
高级调度就是根据一定的调度算法，从后备队列中选择若干作业，将它们调入内存，为它们创建进程，并分配除CPU之外的其他资源，然后将新创建的进程插入就绪队列，等待低级调度。高级调度是批处理操作系统特有的调度。
作业经由高级调度调入内存，为它们分配资源，建立进程，插入就绪队列之后，还需要经过低级调度才能获得处理机而执行。具有高级和低级两级调度的处理机调度模型如图所示。/
在具有两级调度的模型中，低级调度常采用最高优先权优先调度算法，就绪队列可能有两种组织方式：
（1）优先权队列  （2）无序链表
中级调度又称为中程调度、交换调度、平衡调度等。引入这种调度的目的是提高内存的利用率和提高系统吞吐量。中级调度实际上就是交换（对换）功能。
中级调度可以使内存得到更加合理的利用，起到短期均衡系统负载的作用。
/3. 选择调度算法的原则
（1）面向系统准则
/
系统吞吐量指单位时间内系统完成的作业数量
（2）面向用户准则
/
处理器调度算法
课前问题：
1. 常用的调度算法都有哪些？
2. 如何计算平均周转时间等参数？1．调度算法
先来先服务调度算法（FCFS）
是最简单的一种调度算法，它既可以用于高级调度，也可以用于低级调度。这种调度算法是根据作业/进程（线程）进入调度队列的顺序来决定调度次序。
先来先服务调度算法属于非剥夺调度算法。进程（线程）一旦获得CPU就一直运行下去，直到执行结束或因等待某事件，才主动放弃CPU。进程（线程）运行过程中不允许抢占发生。
例题：三个作业进入系统，用FCFS算法求：平均周转时间，带权平均周转时间。
/
解答：
/
平均周转时间=（120+120+120）/3=120min
平均带权周转时间=（1+2.4+12）/3=5.13min短作业（进程）优先调度算法
短作业优先(SJF)：从后备队列中选择估计运行时间最短的作业，调入内存运行。
短进程优先(SPF)：从就绪队列中选出估计运行时间最短的进程，将处理机分配给它
短作业（进程）优先调度算法缺点
（1）该算法对长作业不利
（2）该算法完全未考虑作业的紧迫程度
（3）由于作业(进程)的长短只是根据用户所提供的估计执行时间而定
例题：三个作业进入系统，用FCFS算法求：平均周转时间，带权平均周转时间。
/
解答：
/
第一个作业完成后 2号3号 都到达，此时比较哪个比较短，三号短  作业执行顺序1 3 2
/
平均周转时间=（120+70+130）/3=106.7min
平均带权周转时间=（1+1.4+13）/3=5.13min最高响应比优先调度算法
（1）如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。
（2）当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。
（3）对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高， 从而也可获得处理机。  
  缺点：每次进行调度之前，要重新计算各个作业的响应比，增加了系统开销。实时调度与进程切换
课前问题：
1. 实时调度的条件都有哪些？
2. 实时调度算法的分类有哪些？
3. 什么是进程切换？1.实现实时调度的基本条件
/
2. 实时调度算法的分类
根据实时任务性质：
                               硬实时调度算法
                               软实时调度算法
根据调度方式：
                              抢占式实时调度算法
                              不可抢占式实时调度算法
根据调度的时间：
                              静态调度算法
                              动态调度算法
静态调度无论是单处理器调度还是分布式调度，一般以比率单调调度算法（RMS）为基础，而动态调度则以最早截止时间优先调度算法(EDF)和最短空闲时间优先调度算法（LLF）为基础。3. 进程切换
进程调度和切换程序是操作系统内核程序。获得内核服务的唯一方法是通过中断或异常。处理机在执行每一条指令时，系统都会检查是否有中断或异常发生；如果没有中断和异常，处理机继续执行原来的流程；如果有中断或异常发生，系统将暂停正在执行的进程，将处理机的状态由用户态切换到核心态，执行操作系统内核程序。这个过程称为处理机模式切换。进行处理机模式切换后，被中断进程仍处于自己的执行环境中，内核在被中断进程的环境中进行处理。
处理机模式切换的步骤如下：
/若中断或异常本身由请求调度的事件引起，或者在处理其他中断或异常时，引发了请求调度事件则会发生进程调度和切换。
进行进程调度和切换涉及以下过程：
（1）保存CPU的现场
（2）修改被中断进程的PCB
（3）将被中断进程的PCB链接到新状态队列中。
（4）挑选准备占用CPU运行的新就绪进程。
（5）修改被选中进程的PCB态。
（6）设置地址空间，恢复存储管理信息。
（7）恢复CPU现场
进程切换与处理机模式切换区别：
处理机模式切换,并没有进行进程切换，不需要恢复进程空间等环境信息
进程切换指处理机从执行一个进程转到执行另一个进程，进程切换过程中，由于当前运行的进程改变了，因而当前进程空间等环境信息也需要改变。重要考点
一、名词解释汇总
1.交互式作业：参见教材3.1.1 “处理器调度的基本概念”。主要出现在分时系统和个人计算机中，作业常通过命令方式提供，作业直接提交到内存。
2.批处理作业：参见教材3.1.1 “处理器调度的基本概念”。这类作业要求用户预先将作业的三部分准备好，然后在系统的控制下通过某种作业输入方式将它们提交到外部辅助存储器上，同时为该作业申请JCB。
3.后备队列：参见教材3.1.1 “处理器调度的基本概念”。把外存中的作业按一定的方式组织成队列形式，称为后备队列。
4.系统吞吐量：参见教材3.1.2 “选择调度算法的原则”。指单位时间内系统完成的作业数量。二、计算题
在一个单道的程序设计系统中，有3个作业A、B、C，他们分别在7:50、8:00和8:30到达输入井，他们需要执行的时间是1.5小时、0.4小时和1小时。系统在9:00开始按最高响应比优先调度算法对他们进行调度，请回答下列问题：
（1）当9:00系统开始调度时，此刻各作业的响应比是多少？(计算结果保留小数点后1位)
（2）哪一个作业被第一个选中执行？
解：到达时间7:50、8:00和8:30   运行时间1.5小时、0.4小时和1小时。
/
响应比是：
A:1+70/90=1.8；B:1+60/24=3.5；C:1+30/60=1.5
最终B被选中
本内容由易百教育整理发布
网址www.openhelp100.com
QQ 515224986