计算机操作系统 第四版 汤小丹 课件 第3章

1、第3章处理器调度和死锁，3.1处理器调度层次和调度算法目标3.2作业和作业调度3.3进程调度3.4实时调度3.5死锁概述3.6死锁预防3.7死锁避免3.8死锁检测和解决练习3.1处理器调度层次和调度算法目标在多通道程序系统中，调度的本质是一种资源分配，而处理器调度是分配处理器资源。处理器调度算法是指根据处理器分配策略的处理器分配算法。在多通道批处理系统中，作业可能需要经历从提交到处理器执行的多级处理器调度，直到作业运行。让我们首先了解处理器调度的水平。3.1.1处理器调度的层次结构1。高级调度)2。低级调度)3。中间调度)，3.1.2处理器调度算法1的目标。处理器调度算法的共同目标(1)资源利

2、用。为了提高系统的资源利用率，系统中的处理器和所有其他资源应该尽可能保持忙碌，最重要的处理器利用率可以通过以下方法计算：(2)公平性。公平意味着所有进程都应该获得合理的CPU时间，并且进程饥饿不会发生。公平是相对的，应该为相同类型的过程获得相同的服务；然而，对于不同类型的流程，由于其不同的紧迫性或重要性，应该提供不同的服务。(3)平衡。系统中可能有许多类型的进程，其中一些属于计算类型，一些属于输入/输出类型。为了保持系统中的CPU和各种外部设备始终忙碌，调度算法应该尽可能保持系统资源使用的平衡。(4)政策执行。所制定的策略，包括安全策略，必须在必要的时间内准确执行，即使这会导致一些工作延迟。批

3、处理系统的目标(1)平均周转时间短。每个用户都希望自己的工作有最短的周转时间。但是作为计算机系统的管理者，他总是希望使平均周转时间最短，这不仅会有效地提高系统资源的利用率，而且会使大多数用户满意。操作周转时间和平均操作周转时间应尽可能短。否则，许多用户将等待太长时间，这将引起用户的不满，特别是那些短期工作。平均周转时间可描述为：为了进一步反映调度性能，并更清楚地描述每个进程的等待和执行时间在其周转时间中的具体分布，通常使用加权周转时间，即作业的周转时间T与系统为其提供服务的时间Ts之比，即W=T/Ts。平均加权周转时间可表示为：(2)系统吞吐量高。由于吞吐量是指系统在单位时间内完成的作业数量，

4、因此它与批处理作业的平均长度相关。事实上，如果只是为了高系统吞吐量，应该尽可能多地选择短作业。(3)处理器利用率高。对于大中型计算机来说，CPU非常昂贵，这使得处理器的利用率成为衡量系统性能的一个非常重要的指标；调度方法和算法在处理器的使用中起着非常重要的作用。如果只是为了提高处理器的利用率，我们应该选择尽可能多的任务来运行大量的计算。从上面可以看出，这些要求之间存在一定的矛盾。分时系统的目标(1)快速响应时间。(2)均衡。4。实时系统的目标(1)期限的保证。(2)可预见性。3.2作业和作业调度在多遍批处理系统中，作业是用户提交给系统的相对独立的作业。操作员通过相应的输入设备将用户提交的作业输

5、入到磁盘存储器中，并将其存储在备份作业队列中。然后由作业调度器将它从外部存储器传输到存储器。3.2.1批处理系统1中的作业。作业和作业步骤(1)作业。(2)作业步骤。作业控制块(JCB)为了管理和调度作业，在多遍批处理系统中为每个作业设置一个作业控制块JCB，这是作业在系统中存在的标志，并存储系统管理和调度作业所需的所有信息。通常，JCB包括作业标识、用户名、用户帐号、作业类型(中央处理器忙、输入/输出忙、批处理类型、终端类型)、作业状态、调度信息(优先级、作业运行时间)、资源需求(估计运行时间、所需内存大小等)。)、资源使用等。作业操作的三个阶段和三种状态从进入系统到操作结束，作业通常需要经

6、历三个阶段：接收、运行和完成。相应的作业也有“待机状态”、“运行状态”和“完成状态”。(1)接待阶段。(2)运行阶段。(3)完成阶段。作业调度的主要任务作业调度的主要任务是根据JCB中的信息检查系统中的资源是否能满足作业对资源的需求，从外部备份队列中选择一些作业，并按照一定的调度算法将它们转移到内存中，并为它们创建进程和分配必要的资源。然后，新创建的进程被放在就绪队列中进行调度。因此，作业调度也称为准入调度。每次执行作业调度时，需要做出以下两个决定。1.承认多少工作2。3.2.3先来先服务(FCFS)和短作业先服务(SJF) 1的调度算法。先到先服务(FCFS)调度算法FCFS是最简单的调度算

7、法，可用于作业调度和进程调度。在作业调度中使用该算法时，系统将根据作业到达的顺序进行调度，或者优先考虑系统中等待时间最长的作业，而不考虑作业所需的执行时间长度。从备份作业队列中选择几个首先进入队列的作业，将它们转移到内存中，为它们分配资源并创建进程。然后把它放到准备好的队列中。短作业优先(SJF)调度算法由于短作业(流程)在实际情况中占很大比例，为了使它们先于长作业执行，产生了短作业优先调度算法。1)短作业优先级算法SJF算法根据作业的长度计算优先级，作业越短，优先级越高。作业的长度由作业所需的运行时间来衡量。SJF算法可以分别用于作业调度和过程调度。当短作业优先调度算法用于作业调度时，它将从

8、外部作业备份队列中选择几个估计运行时间最短的作业，并首先将它们转移到内存中。短作业优先算法的缺点SJF调度算法与FCFS算法相比有明显的改进，但仍存在一些不可忽视的缺点：(1)需要预测作业的运行时间。当采用这种算法时，我们首先应该知道每个作业的运行时间。程序员很难准确估计工作的运行时间。如果估计值太低，系统可能会根据估计的时间终止作业的运行，但此时作业没有完成，因此通常估计的时间太长。(2)长时间运行非常不利，长时间运行的周转时间会明显增加。此外，该算法完全忽略了作业的等待时间，这可能会使作业的等待时间过长，导致饥饿。(3)采用FCFS算法时，无法实现人机交互。(4)调度算法根本没有考虑作业的

9、紧急性，因此不能保证紧急作业能够及时处理。优先级调度算法和高响应率优先级调度算法。优先级调度算法我们可以用这种方法来看作业的优先级。对于先到先服务的调度算法，作业的等待时间是作业的优先级，等待时间越长，优先级越高。对于短作业优先级调度算法，作业的长度是作业的优先级，作业运行时间越短，优先级越高。然而，上述两个优先事项都不能反映工作的紧迫性。最高响应率下一个(HRRN)在批处理系统中，FCFS算法只考虑作业的等待时间，而忽略作业的运行时间。相反，SJF算法只考虑作业的运行时间，而忽略了作业的等待时间。高响应率的优先级调度算法是一种兼顾任务等待时间和运行时间的调度算法，不仅可以处理短任务，而且不会

10、使长任务的等待时间过长，从而提高处理器调度的性能。高响应率优先级算法是如何实现的？如果我们能为每个作业引入一个动态优先级，即优先级可以改变，并且它会随着等待时间的延长而增加，这将使得长作业的优先级在等待期间不断增加，并且在足够的时间之后，将有机会得到处理器。优先级的变化规律可以描述为：因为等待时间和服务时间之和是系统对作业的响应时间，所以优先级相当于响应率RP。据此，优先级可以表示为：3.3。进程调制过程的调度是操作系统中不可缺少的调度。因此，在所有三种类型的操作系统中，进程调度都是无一例外地进行配置的。此外，它也是一种对系统性能影响最大的处理器调度，因此有很多关于进程调度的算法。3.3.1过

11、程调度的任务、机制和模式1。进程调度的任务进程调度有三个主要任务：(1)保存处理器的字段信息。(2)根据某种算法选择流程。(3)为进程分配处理器。过程调度机制为了实现过程调度，过程调度机制应该有以下三个基本部分，如图3-1所示。(1)排队。(2)调度员。(3)上下文切换器。图3-1流程调度机制3。进程调度模式1)非抢占模式在这种调度模式中，一旦处理器被分配给一个进程，它将始终运行，并且它将不会由于时钟中断或任何其他原因抢占当前运行的进程的处理器，并且它将不会被分配给其他进程，直到进程完成或由于事件而被阻塞。抢占模式这种调度模式允许调度程序根据某种原则暂停正在执行的进程，并将分配给该进程的处理器

12、重新分配给另一个进程。抢占在现代操作系统中被广泛使用，因为对于批处理机系统，可以防止长进程长时间占用处理器，从而保证处理器能够为所有进程提供更公平的服务。在分时系统中，只有通过抢占才能实现人机交互。在实时系统中，抢占可以满足实时任务的需要。然而，抢占方法很复杂，系统开销也很大。3.3.2循环调度算法1。循环方法的基本原理在循环方法中，系统根据FCFS策略将所有就绪进程排列成就绪队列。系统可以每隔一定时间(例如30毫秒)设置一个中断，停用进程调度器进行调度，将中央处理器分配给组长进程，并使其执行一个时间片。当它运行时，它将处理器分配给就绪队列中的新队列头进程，并让它执行一个时间片。通过这种方式，

13、可以确保就绪队列中的所有进程可以在特定时间段内获得一个时间片的处理器时间。进程切换定时在RR调度算法中，何时切换进程可以分为两种情况：如果一个时间片没有用完，并且正在运行的进程已经完成，则立即激活调度器，将其从就绪队列中删除，然后在就绪队列的头部调度进程运行并开始新的时间片。当时间片用完时，定时器中断处理程序被激活。如果进程没有完成运行，调度程序将把它发送到就绪队列的末尾。时间片大小的确定在旋转算法中，时间片大小对系统性能有很大影响。图3-2显示了时间片大小对响应时间的影响，其中图(a)显示时间片略大于典型交互时间，而图(b)显示时间片短于典型交互时间。图3-3显示了当时间片分别为q=1和q=

14、4时对平均周转时间的影响。图3-2时间片大小对响应时间的影响图3-3当Q=1和q=4时进程的周转时间3.3.3优先级调度算法类型优先级调度算法优先级进程调度算法将处理器分配给就绪队列中最高优先级的进程。此时，算法可以进一步分为以下两种类型。(1)非优先调度算法。(2)抢占式优先级调度算法。优先级类型1)静态优先级静态优先级在创建进程时确定，并在进程的整个运行期间保持不变。优先级由一定范围内的整数表示，如0255中的整数，也称为优先级数。确定流程优先级有三个原因：(1)流程类型。(2)过程对资源的需求。(3)用户要求。动态优先级动态优先级是指在进程创建之初赋予其优先级，然后随着进程的进展或等待时

15、间的增加，其值会发生变化，以获得更好的调度性能。多队列调度算法，如上面提到的各种调度算法，特别是应用于进程调度时，因为系统中只设置了一个进程就绪队列，即底层调度算法是固定的、单一的，不能满足不同用户对进程调度策略的不同要求。在多处理器系统中，这种单一调度策略实现机制的缺点更加突出，因此多级队列调度算法可以在一定程度上弥补这一缺点。调度机制多级反馈队列调度算法的调度机制可以描述如下：(1)建立多个就绪队列。图3-4是多级反馈排队算法的示意图。图3-4多级反馈队列调度算法，(2)每个队列采用FCFS算法。当新进程进入内存时，它首先被放在第一个队列的末尾，并根据FCFS原则等待调度。当轮到进程执行时

16、，如果它能在这个时间片内完成，系统可以被抽空。否则，它不会在时间片结束时完成，调度程序会将其转移到第二个队列的末尾，等待调度；如果在第二个队列中运行一个时间片后仍未完成，则依次将其放入第三个队列，依此类推。当进程最终被放到第n个队列时，它在第n个队列中以RR模式运行。(3)根据队列优先级调度。调度器首先调度最高优先级队列中的进程，并且仅在第一队列空闲时调度第二队列中的进程。换句话说，只有当第一个队列(I-1)中的所有队列都为空时，第一个队列中的进程才会计划运行。如果在处理器为第一队列中的一个进程服务时，一个新进程进入了任何具有较高优先级的队列，则必须立即将正在运行的进程放回到第一队列的末尾，并将处理器分配给新到达的高优先级进程。调度算法的性能在多级反馈队列调度算法中，如果第一个队列的时间片比大多数人机交互所需的处理时间稍长，就能更好地满足各类用户的需求。(1)终端用户。(2)短批处理作业用户。(3)长批作业用户。基于公平1的调度算法。保证调度算法保证调度算法是另一种调度算法，它对用户的保证不是优先级操作，而是明确的性能保证，可以实现调度的公平性。一个简单的性能保证是处理器分配的公平性。如果系统中有n个相同类型的