操作系统——处理机调度(学习笔记)

简介: 调度:当有多个任务需要处理,由于资源有限,这些任务无法同时处理,这时需要某种规则来决定处理这些任务的顺序。处理机调度:从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行,以实现进程的并发执行。

一、处理机调度

1.处理机调度的概念

调度:当有多个任务需要处理,由于资源有限,这些任务无法同时处理,这时需要某种规则来决定处理这些任务的顺序

处理机调度:从就绪队列中按照一定的算法选择一个进程将处理机分配给它运行,以实现进程的并发执行。

2.处理机调度的三个层次

高级调度

高级调度又称长程调度作业调度,调度对象是作业。根据某种算法决定将外存上处于后备队列中的哪几个作业调入内存,为它们创建进程、分配必要的资源,并将它们放入就绪队列。高级调度主要用于多道批处理系统中,而在分时和实时系统中不设置高级调度。

中级调度

中级调度又称为内存调度。操作系统会把暂时不能运行的进程,调至外存等待,此时进程的状态称为挂起状态。PCB不会被调入外存,PCB常驻内存。中级调度就是决定哪个挂起态的进程被重新调入内存。引入内存调度的主要目的是,提高内存利用率和系统吞吐量。

低级调度

低级调度又称为进程调度短程调度,其所调度的对象是进程(或内核级线程)。其主要功能是,根据某种算法,决定就绪队列中的哪个进程应获得处理机,并由分派程序将处理机分配给被选中的进程。进程调度是最基本的一种调度,在多道批处理、分时和实时三种类型的操作系统中都必须配置这级调度。

三种调度的比较

image.gif

3.进程调度

时机、切换与过程

1.进程主动放弃处理机

    • 进程正常终止
    • 运行过程中发生异常而终止
    • 进程主动请求阻塞(如 等待 I/O)

    2.进程被动放弃处理机

      • 分给进程的时间片用完
      • 处理更紧急的事(如I/O中断)
      • 有更高优先级的进程进入就绪队列

      3.不能切换进程的情况:

        • 在处理中断的过程中。中断处理过程复杂,与硬件密切相关,很难做到在中断处理过程中进行进程切换。
        • 进程在操作系统内核程序临界区中。
        • 在原子操作过程中(原语)。原子操作不可中断。

        进程切换是有代价的,因此如果过于频繁的进行进程调度、切换,必然会使整个系统的效率降低,使系统大部分时间都花在了进程切换上,而真正用于执行进程的时间减少。

         

        方式

        非抢占式:只允许进程主动放弃处理机。在运行过程中即便有更紧急的任务到达,当前进程依旧会继续使用处理机,直到该进程终止或主动要求进入阻塞。

        抢占式:当一个进程正在处理机上执行时,如果有一个更紧急或更重要的需要使用处理机,就立刻暂停正在执行的进程,把处理机分配给更重要紧急的那个进程。

        4.调度算法的目标和评价指标

        处理机调度算法的共同目标

        1.资源利用率高

        CPU的利用率 =  CPU有效工作时间 / CPU有效工作时间 + CPU空闲等待时间

        2.公平性

        使所有进程都获得合理的CPU时间,不会发生进程饥饿现象。

        3.资源的平衡利用

        由于在系统中可能具有多种类型的进程,有的属于计算型作业,有的属于I/O型。为使系统中的CPU和各种外部设备都能经常处于忙碌状态,调度算法应尽可能保持系统资源使用的平衡性。

        4.策略的强制执行

        对所制定的策略其中包括安全策略,只要需要,就必须予以准确地执行,即使会造成某些工作的延迟也要执行。

        批处理系统的目标

          • 周转时间短

          每个用户都希望自己的周转时间短,系统希望平均周转时间短。

            • CPU利用率高

            尽量选择计算量大的作业。

              • 系统吞吐量高

              吞吐量指在单位时间内系统所完成的作业数。

              系统的吞吐量 = 总共完成的作业数 / 总共花费的时间

              评价指标

              周转时间:某一作业提交系统的时间到该作业完成的这段时间间隔。(作业完成时间 - 作业提交时间)

              包括四个部分:作业在外存后备队列上等待作业调度(高级调度)的时间进程在就绪队列上等待进程调度(低级调度)的时间进程在CPU上执行的时间进程等待I/O操作完成的时间

              平均周转时间 = 各作业周转时间之和 / 作业数

              带权周转时间 = 作业周转时间 / 作业实际允许时间  = 作业完成时间 - 作业提交时间 / 作业实际允许时间 (>=1 越小用户体验越好)

              平均周转时间 =各作业带权周转时间之和 / 作业数

              等待时间:进程/作业 等待被服务的时间之和

              响应时间:从用户提交请求到首次产生响应所用的时间


              二、调度算法

              1.先来先服务(FCFS)

              按照到达的先后顺序调度,类似于队列先进先出的特点。

              image.gif

              不会导致饥饿,因为在队列中就算等待时间再长也会到达队头进行执行。

              例题:

              image.gif

              2.短作业优先(SJF)

              优先处理短作业(服务时间短)

              image.gif

              例题:

              image.gif

              3.高相应比优先(HRRN)

              image.gif

              image.gif

              0时刻,只有p1一个进程,p1被处理机调度

              7时刻(p1主动放弃CPU):就绪队列中有 p2(响应比:(5+4)/ 4 = 2.25)p3(相应比:(3+1)/1 = 4 )p4(响应比 :(2+4) / 4 = 1.5)    p3响应比最高被处理机调度

              8时刻(p3完成):p2(2.5)、 p4(1.75)   p2被调度执行

              12时刻(p2完成) : p4被调度执行

              注:这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标,但是不关心“响应时间”,也并不区分任务的紧急程度,因此对于用户来说,交互性很差。因此这三种算法一般适合用于早期的批处理系统。

               

              4.时间片轮转(RR)

              image.gif

              时间片大小为2

              image.gif

              时间片大小为5

              image.gif

              注:如果时间片太大,使得每个进程都可以在一个时间片内就完成,则时间片轮转调度算法退化为先来先服务调度算法,并且会增大进程响应时间。因此时间片不能太大。

              进程调度、切换是有时间代价的(保存、恢复运行环境),因此如果时间片太小,会导致进程切换过于频繁,系统会花大量的时间来处理进程切换,从而导致实际用于进程执行的时间比例减少,因此时间片也不能太小。

               

              时间片大小的选取一般要略大于一次典型的交互所需要的时间。

              5.优先级调度算法

              image.gif

              例题:

              非抢占式

              image.gif

                             优先数越高,优先级越大

              抢占式

              image.gif

              当然这是静态优先级:创建进程时确定,之后一直不变。还有动态优先级,创建进程时有一个初始值,之后会一直变化。 例如每次执行一个时间片优先级就 -1

              6.多级反馈队列调度算法

              image.gif

              1.设置多级就绪队列,各级队列优先级从高到低,时间片从小到大。
              2.新进程到达时先进入第1级队列,按FCFS原则排队等待被分配时间片。若用完时间片进程还未结束,则进程进入下一级队列队尾。如果此时已经在最下级的队列,则重新放回最下级队列队尾。
              3.只有第k级队列为空时,才会为k+1级队头的进程分配时间片被抢占处理机的进程重新放回原队列队尾。

              例题:image.gif

              参考《王道考研 操作系统》 《计算机 操作系统》(汤小丹 第四版)

              相关文章
              |
              2月前
              |
              算法 调度 UED
              探索操作系统的心脏:调度算法的奥秘与影响
              【10月更文挑战第9天】 本文深入探讨了操作系统中至关重要的组件——调度算法,它如同人体的心脏,维持着系统资源的有序流动和任务的高效执行。我们将揭开调度算法的神秘面纱,从基本概念到实际应用,全面剖析其在操作系统中的核心地位,以及如何通过优化调度算法来提升系统性能。
              |
              24天前
              |
              算法 调度 UED
              深入理解操作系统:进程调度与优先级队列
              【10月更文挑战第31天】在计算机科学的广阔天地中,操作系统扮演着枢纽的角色,它不仅管理着硬件资源,还为应用程序提供了运行的环境。本文将深入浅出地探讨操作系统的核心概念之一——进程调度,以及如何通过优先级队列来优化资源分配。我们将从基础理论出发,逐步过渡到实际应用,最终以代码示例巩固知识点,旨在为读者揭开操作系统高效管理的神秘面纱。
              |
              21天前
              |
              算法 调度 UED
              深入理解操作系统:进程管理与调度策略
              【10月更文挑战第34天】本文旨在探讨操作系统中至关重要的一环——进程管理及其调度策略。我们将从基础概念入手,逐步揭示进程的生命周期、状态转换以及调度算法的核心原理。文章将通过浅显易懂的语言和具体实例,引导读者理解操作系统如何高效地管理和调度进程,保证系统资源的合理分配和利用。无论你是初学者还是有一定经验的开发者,这篇文章都能为你提供新的视角和深入的理解。
              40 3
              |
              26天前
              |
              消息中间件 算法 调度
              深入理解操作系统:进程管理与调度策略
              【10月更文挑战第29天】本文将带领读者深入探讨操作系统中的核心组件之一——进程,并分析进程管理的重要性。我们将从进程的生命周期入手,逐步揭示进程状态转换、进程调度算法以及优先级调度等关键概念。通过理论讲解与代码演示相结合的方式,本文旨在为读者提供对进程调度机制的全面理解,从而帮助读者更好地掌握操作系统的精髓。
              36 1
              |
              26天前
              |
              算法 调度 UED
              深入理解操作系统中的进程调度
              【10月更文挑战第29天】探索进程调度的奥秘,本文将带你深入了解在操作系统中如何管理和控制多个并发执行的程序。从简单的调度算法到复杂的多级反馈队列,我们将逐步揭示如何优化系统性能和提高资源利用率。准备好一起揭开进程调度的神秘面纱吧!
              |
              1月前
              |
              算法 大数据 Linux
              深入理解操作系统之进程调度算法
              【10月更文挑战第24天】本文旨在通过浅显易懂的语言,带领读者深入了解操作系统中的进程调度算法。我们将从进程的基本概念出发,逐步解析进程调度的目的、重要性以及常见的几种调度算法。文章将通过比喻和实例,使复杂的技术内容变得生动有趣,帮助读者建立对操作系统进程调度机制的清晰认识。最后,我们还将探讨这些调度算法在现代操作系统中的应用和发展趋势。
              |
              2月前
              |
              算法 调度
              深入理解操作系统:进程调度与优先级反转问题
              【9月更文挑战第36天】操作系统是计算机科学中的核心概念,它管理着计算机的硬件资源和软件进程。在多任务处理环境中,进程调度是保证系统高效运行的关键机制之一。本文将探讨进程调度的基本概念、调度算法以及它们如何影响系统性能。同时,我们还将讨论优先级反转问题,这是一个在实时系统中常见的问题,它可能导致系统响应时间不可预测。通过分析优先级反转的原因和解决方案,我们可以更好地理解操作系统的设计和优化策略。
              |
              2月前
              |
              分布式计算 算法 大数据
              探索操作系统的核心:调度与内存管理机制
              【10月更文挑战第11天】 本文深入探讨了操作系统中两大核心功能——调度与内存管理机制。通过分析调度算法、进程状态转换及内存分配策略等关键方面,揭示了它们如何共同维护系统性能和稳定性。旨在为读者提供对操作系统内部运作的深刻理解,同时引起对优化策略的思考。
              65 5
              |
              2月前
              |
              算法 调度 UED
              探索操作系统的心脏:深入理解进程调度
              【10月更文挑战第7天】在数字世界的海洋中,操作系统是那艘承载着软件与硬件和谐共处的巨轮。本文将带你潜入这艘巨轮的核心区域——进程调度系统,揭示它如何精准控制任务的执行顺序,保障系统的高效运行。通过深入浅出的语言,我们将一起解码进程调度的奥秘,并借助代码示例,直观感受这一机制的魅力所在。准备好,让我们启航吧!
              |
              22天前
              |
              算法 调度 UED
              深入浅出操作系统调度策略
              【10月更文挑战第33天】在数字时代的心脏,操作系统扮演着至关重要的角色。本文将探讨操作系统的核心功能之一——进程调度策略的设计与影响。我们将从理论到实践,通过浅显易懂的语言和具体代码示例,揭示如何通过不同的调度算法来优化系统性能和用户体验。无论你是技术新手还是资深开发者,这篇文章都将为你提供新的视角和深入的理解。