第三章处理机调度与死锁

第三章 处理机调度与死锁第三章 处理机调度与死锁3.1 处理机调度的基本概念1)调度类型 高级调度 ：即作业调度，选择后备作业进入内存，为其建立进程 ,分配资源并排在就绪队列。 中级调度 ：即对换调度，将暂不运行的进程调到外存等待，从而提高内存利用率和系统吞吐量 低级调度 ：即 进程调度 ，决定哪个进程可以占用 CPU， 进入运行状态。输入程序就绪阻塞就绪运行 完成阻塞后备外存中级调度对换低级调度作业调度2)进程调度方式调度方式是指但某一个进程正在处理机上执行时如果有个更重要更紧迫的进程需要处理此时应该如何分配处理机。n 非抢占方式进程一旦被调度执行，除非进程完成或发生某事件被阻塞，否则不允许其他进程抢夺其执行权。n 抢占方式允许按某种策略（原则）剥夺正在执行的进程的执行权-优先权原则-短作业 (进程 )优先原则-时间片原则3)调度类型与 O.S类型的关系 多道批处理系统：存在作业调度、进程调度 分时 /实时系统：只有进程调度共同点：均存在进程调度（分配 CPU）4) 调度队列模型 (三种 )就 队 列绪 CPU进程调度进程完成时间片完阻 队 列塞交互用户等待事件事件出现n 仅有进程调度的调度队列模型仅有进程调度的调度队列模型n 具有高级和低级的调度队列模型后 队 列备1阻 队 列塞作业调度就 队 列绪 CPU进程调度进程完成时间片完等待事件 1事件 1出现2阻 队 列塞n阻 队 列塞等待事件 2等待事件 n事件 2出现事件 n出现n 具有三级调度的调度队列模型作业调度就 队 列绪 CPU进程调度进程完成时间片完事件出现 阻 塞 列、 起 队挂阻 队 列塞等待事件就绪、挂起队列事件出现挂起中级调度后 队 列备交互型作业批量作业挂起5) 调度性能评价 作业调度算法的评价因素 CPU利用率 ：越高越好 吞吐量 ：单位时间内 CPU完成作业的数量 周转时间 ：通常与带权周转时间一起作为评价批处理系统的性能指标，定义如下：其中：作业其中：作业 Ji的提交时间为的提交时间为 tsi，执行时间为执行时间为 tri，完成时间为，完成时间为 toin个作业的平均周转时间 T和平均周转系数 W分别为n 对于每个用户来说，总是希望作业提交后立即执行，这样周转时间等于执行时间；而对于一个计算机系统来说，不可能满足每个用户的这种要求，只能使系统的平均周转时间最短。n 对于分时系统常把响应时间的长短作为评价标准；对于实时系统常把截止时间作为评价标准。3.2 调度算法l 先来先服务调度算法l 短作业（进程）优先调度算法l 高优先权者优先调度算法l 时间片轮转调度算法l 多队列反馈轮转调度算法l 实时调度算法1）先来先服务调度算法 策略： 先进入后备队列（就绪队列）的作业（进程）先被调度 优点： 算法简单易实现 缺点： 不分轻重缓急，对短作业（进程）不利2）短作业（进程）优先调度算法 策略： 启动要求运行时间最短的作业。 优点： 有效降低作业平均等待时间 提高系统的吞吐量 缺点： 长作业（进程）可能长期得不到服务3）高优先权者优先调度算法 优先权： 反映作业（进程）重要性和调度级别的权值，又称优先数。通常分为：静态优先数 ：进程创建时确定运行过程中不会改变。一般根据进程的类型，资源需求情况，估计的运行时间等因素确定。动态优先数 ：创建进程时确定一个优先级，进程运行过程中可以根据情况的变化调整优先级，调整一般是根据进程占用的 CPU的时间长短、进程等待 CPU时间长短来进行。 高响应比优先调度算法（ HRP）： 优先调度响应比高的作业响应比 RP（等待时间 +要求服务时间） /要求服务时间 响应时间 /要求服务时间 1 + 等待时间 /要求服务时间 优点：既照顾短作业又考虑作业到达的先后次序，而且不会使长作业长期得不到服务。 缺点：每次调度前都要进行响应比计算增加系统开销 类型非抢占式优先权调度 ：处理机一旦分配给就绪队列中优先权最高的进程后，该进程就一直运行下去直到自动放弃或完成，这时才可把处理机分配给另一优先级最高的进程。抢占式优先权调度 ：进程在运行时一旦出现了另一个优先级更高的进程，调度程序就停止该进程而把处理机分配给新出现的高优先权进程。4）时间片轮转调度算法（适合于分时系统） 策略： 各作业（进程）轮流运行（执行）一个时间片 优、缺点： 简单易实现，但不分轻重缓急 关键： 时间片大小的选择5）多级队列反馈轮转调度算法 策略：将时间片 与 优先级 调度相结合。-设置多个就绪队列，分别赋予不同的优先级。优先级越低则时间片越长-新进程进入内存后，先投入第一队列的末尾，按 FCFS算法调度；若按第一队列一个时间片未能执行完，则降低投入到第二队列的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按 “ 时间片轮转 ” 算法调度直到完成-仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾就绪队列 1S1 至 CPU就绪队列 2 S2 至 CPU 就绪队列 3 S3 至 CPU就绪队列 n Sn 至 CPU 调度算法性能分析设有四个作业，其提交时刻、执行时间如下表所示，分别采用FCFS、 SJF、 FPF调度方法，计算平均周转时间 T和平均周转系数 W。 作业号 提交时刻 运行时间1 8.00 2.002 8.50 0.503 9.00 0.104 9.50 0.20 先来先服务调度算法：顺序为 1 2 3 4，平均周转时间和平均周转系数的计算结果如下表所示：作业 提交时间 执行时间 开始时间 完成时间 周转时间 周转系数1 8.00 2.002 8.50 0.503 9.00 0.104 9.50 0.208.00 10.00 2.00 1.0010.00 10.50 2.00 4.0010.50 10.60 1.60 16.0010.60 10.80 1.30 6.506.90 27.50 平均周转时间 T 1.725小时，平均周转系数 W 6.875 最短作业优先调度算法 ：由于在 8.00开始执行作业，当时仅有 1，而作业 2， 3， 4尚未到达，故作业 1是最短作业。 作业 1执行完成后是 10.00，此时作业 2， 3， 4均已经到达，故选最短作业 3，然后是4， 2。所以 顺序为 1,3,4,2。 平均周转时间和平均周转系数的计算结果如下表所示： 作业 提交时间 执行时间 开始时间 完成时间 周转时间 周转系数1 8.00 2.002 8.50 0.503 9.00 0.104 9.50 0.208.00 10.00 2.00 1.0010.00 10.10 1.10 11.0010.10 10.30 0.80 4.0010.30 10.80 2.30 4.606.20 20.60 平均周转时间 T 1.55小时，平均周转系数 W 5.15 响应比高者优先算法：在作业 1执行完成，计算作业 2， 3， 4的响应比分别为： 4，11， 3.5，因此作业 1执行完成后选中作业 3完成。执行顺序为 1， 3， 2， 4。按此算法求得的平均周转时间和平均周转系数如下表所示：作业 提交时间 执行时间 开始时间 完成时间 周转时间 周转系数1 8.00 2.002 8.50 0.503 9.00 0.104 9.50 0.208.00 10.00 2.00 1.0010.00 10.10 1.10 11.0010.10 10.60 2.10 4.2010.60 10.80 1.30 6.506.50 22.70 平均周转时间 T 1.625小时，平均周转系数 W 5.675总结：就其平均周转时间和平均周转系数来说，最短作业优先算法最小，先来先服务算法最大，响应比高者优先算法居中。6）两种常见的实时调度算法n 最早截止时间优先算法 (EDF)选择就绪队列中开始截止时间最早的实时任务对应的进程先执行（一般非抢占方式）n 最低松弛度优先算法 (LLF)松弛度 =规定完成时间 -所需执行时间 -当前时间选择松弛度最小的实时任务对应的就绪进程先执行，一般采用抢占方式，当某进程松弛度为零时，必须立即抢占执行。EDF例 ： 进程到达时刻执行所需时间 开始截止时间P1 0 4 2P2 2 3 10P3 3 2 4P4 5 3 7t=0 只有 P1进程， P1执行 4个单位时间t=4 P2、 P3均到达， P3截止时间早于 P2截止时间P3执行两个单位时间t=6 P2和 P4就绪， P4截止时间早于 P2， P4执行t=9 只剩 P2， P2执行LLF例 ：两个周期性实时任务 A和 B，A：每 20ms执行一次，每次执行时间为 10msB：每 50ms执行一次，每次执行时间为 25mst (ms)0 10 20 30 40 50 60 70 80 90 100 110 120A1 A2 A3 A4 A5 A6B1 B2调度（执行） 抢占 抢占松弛度t (ms)0 10 20 30 40 50 60 70 80 90 100 110 120A1(10) A2(10) A3(10) A4(10) A5(10)B1(20) B2(10)B1(5) B2(15)A1=10 未进入 A2 A2=0 A3=10 A3=5 未进入 A4 A4=0 A5=10B1=25 B1=15 B1=15 B1=5 未进入 B2 B2=20 B2=20 B2=10A1 B1 A2 B1 A3 B2 A4 B23.3 死锁 死锁：多个进程 竞争 系统 资源 ，造成一种 僵局，使得这些进程在无外力的作用下，均 无法 继续向前 推进 。 讨论问题n 死锁的产生原因n 产生死锁的必要条件n 死锁的预防n 死锁的避免n 死锁的检测和解除1） 产生死锁的原因 死锁主要是由两个或多个进程对资源需求的冲突引起的进程 A请求资源 R2进程 B请求资源 R1请求资源 R1请求资源 R2R1分配 R2分配（阻塞） （阻塞）死锁产生的原因：p 资源竞争p 进程推进顺序不当n资源竞争引起死锁情况独占资源分为可剥夺式和不可剥夺式，死锁与不可剥夺式有关。 P1P2R1 Rn 进程的推进顺序不当导致死锁请求打印机请求读卡机释放打印机释放读卡机进程 P1请求读卡机请求打印机释放读卡机释放打印机进程 P2打印机读卡机Req(R1)Req(R2)Rel(R1)Rel(R2)Req