计算机操作系统(第四版)第三章调度算法.pptxVIP

计算机操作系统(第四版)第三章调度算法2023-2026ONEKEEPVIEWREPORTING

目录CATALOGUE调度算法概述先来先服务调度算法短作业优先调度算法优先级调度算法时间片轮转调度算法

调度算法概述PART01

0102调度算法的定义调度算法是操作系统核心组成部分之一，它负责决定哪个进程将获得处理机，以及何时获得处理机。调度算法是指根据系统的资源分配策略和用户的需求，对计算机系统中的任务进行合理调度的算法。

一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。非抢占式调度算法允许调度程序以一定的频率中断CPU上运行的进程，并抢占处理机。抢占式调度算法在进程创建时确定其优先级，且在进程的整个运行期间保持不变。静态优先级调度算法在进程创建之初，先赋予其一个优先级，然后其值随进程的推进或等待时间的增加而改变。动态优先级调度算法调度算法的分类

CPU利用率CPU是计算机系统中最重要的资源之一，CPU利用率是衡量调度算法性能的重要指标之一。单位时间内系统完成作业的数量，反映了系统的整体性能。从作业提交到作业完成的时间间隔，包括等待时间、运行时间和其他时间（如输入/输出操作时间）。进程/作业处于等待处理机状态的时间之和，等待时间越长，用户满意度越低。从用户提交请求到系统首次产生响应所用的时间。在交互式系统中，周转时间不可能是最好的评价准则，一般采用响应时间来衡量调度算法的性能。系统吞吐量等待时间响应时间周转时间调度算法的评价指标

先来先服务调度算法PART02

算法原理按照进程到达的先后顺序进行服务，即先到达的进程先被服务，后到达的进程后被服务。不考虑进程的长度和优先级等因素，只根据到达时间进行排队。

创建一个队列，用于存储到达的进程。当一个进程到达时，将其加入队列的末尾。调度器每次从队列的头部取出一个进程进行服务。服务完成后，将该进程从队列中移除现过程

优点算法简单，易于实现。对所有进程公平，不会产生饥饿现象。优缺点分析

缺点不考虑进程的优先级，可能会导致重要进程得不到及时服务。对I/O密集型进程不利，因为这类进程经常需要等待I/O操作完成，而在等待期间CPU资源被浪费。平均等待时间较长，因为长进程会占用较长时间的CPU资源，导致后续进程等待时间过长。优缺点分析

短作业优先调度算法PART03

基于作业执行时间的调度算法短作业优先（SJF,ShortestJobFirst）调度算法是一种非抢占式的算法，它根据作业的执行时间来进行调度。该算法优先选择执行时间最短的作业进行调度，以最小化平均等待时间和平均周转时间。队列中的作业排序在SJF算法中，当多个作业同时到达时，它们会根据各自的估计执行时间进行排序。执行时间最短的作业会被优先调度执行。算法原理

作业到达与排序01当有新的作业到达时，系统会将其加入到等待队列中，并根据估计的执行时间对队列中的作业进行排序。选择最短作业执行02调度器会始终选择执行时间最短的作业进行调度执行。如果多个作业具有相同的执行时间，则按照它们到达的先后顺序进行选择。等待与执行03被选中的作业将进入执行状态，而其他作业则继续在等待队列中等待。当执行完一个作业后，调度器会再次从等待队列中选择下一个执行时间最短的作业进行调度。实现过程

最小化平均等待时间和平均周转时间由于优先选择执行时间短的作业，SJF算法可以有效地降低作业的等待时间和周转时间。适用于短作业较多的场景在大量短作业存在的场景下，SJF算法能够显著提高系统的吞吐量。优缺点分析

优缺点分析对长作业的歧视由于SJF算法总是优先选择执行时间短的作业，长作业可能会经历长时间的等待，导致饥饿现象。需要预知作业的执行时间SJF算法要求提前知道每个作业的执行时间，这在某些情况下可能难以实现。不适用于实时系统实时系统通常要求在规定的时间内完成作业的执行，而SJF算法无法保证这一点。

优先级调度算法PART04

每个进程被赋予一个优先级，优先级高的进程优先获得处理机。根据是否允许优先级低的进程被优先级高的进程中断，分为抢占式优先级调度和非抢占式优先级调度。算法原理抢占式与非抢占式优先级分配

03进程选择在优先级最高的队列中，按照某种策略（如先来先服务、短作业优先等）选择一个进程执行。01进程优先级确定根据进程类型、进程对资源的需求和紧迫程度等因素，确定每个进程的优先级。02调度队列建立将不同优先级的进程分别放入不同的队列中，优先级高的队列优先获得处理机。实现过程

03适应性强，可以根据不同需求调整优先级。01优点02保证重要进程优先执行，提高系统效率。优缺点分析缺点分析缺点可能导致低优先级进程长时间得不到执行，产生饥饿现象。优先级逆转问题：高优先级进程