【操作系统】进程调度

简介: 进程调度知识总结

 目录

调度的概念

调度目标

   所有系统

   批处理系统

   交互式系统

   实时系统

调度算法

   非抢占式调度算法

       先来先服务

       最短作业优先

       非抢占式优先级调度

   抢占式调度算法

       最短剩余时间优先

       轮转调度

       抢占式优先级调度

       多级反馈队列

       彩票调度

       公平分享调度


调度的概念

    • 进程是资源分配的基本单位;
    • 线程是CPU调度的基本单位。

    一个单核CPU在某一时刻只能允许一个线程执行,但是现在的计算机总是有一大堆进/线程等待执行。这就需要某种规则来决定处理这些进/线程的顺序,这就是调度要研究的问题。

    进程状态:

    image.gif编辑

    运行态:当前正在占有CPU的进/线程;

    就绪态:具备运行条件,等待系统分配CPU的进/线程;

    阻塞态:不具备运行条件,正在等待某外部事件发生的进/线程。

    所谓进程调度,就是指在处于就绪态的一堆进/线程里,按照一定的调度算法,选出一个进/线程并给它分配CPU时间让它运行,从而实现多进程/多线程的并发执行。

    进程切换的基本流程:

      1. 首先用户态必须切换到内核态;
      2. 保存当前进程的状态,包括在其PCB中保存CPU各寄存器值,以便日后重新执行;
      3. 调度算法选定一个新进程;
      4. 新进程的内存地址空间重新装入MMU(内存管理单元);
      5. 新进程开始执行。

      调度目标

         所有系统

      对于所有系统,都应该有以下调度目标:

        • 公平——给每个进程公平的CPU份额;
        • 策略强制执行——保证规定的调度策略被执行;
        • 平衡——保证系统的所有部分都在忙碌。

           批处理系统

        批处理系统更适合非抢占式调度算法,应有以下调度目标:

          • 吞吐量——每小时最大作业数;
          • 周转时间——从提交到终止的最短时间;
          • CPU利用率——保持CPU始终忙碌。

             交互式系统

          交互式系统更适合抢占式调度算法,应有以下调度目标:

            • 响应时间——快速响应请求;
            • 均衡性——满足用户的期望。

               实时系统

            对于实时系统,应有以下调度目标:

              • 满足截止时间——避免丢失数据;
              • 可预测性——如多媒体系统中避免品质降低。

              调度算法

              进程调度的核心自然是调度规则,即各种调度算法。

              计算机都有一个硬件时钟,也叫RTC或CMOS,它独立于操作系统,由主板上一块电池供电的芯片,所以即使计算机断电,RTC也可以维持时间。这个硬件时钟会周期性的发出时钟中断。

              根据如何处理时钟中断,可以把调度算法分为两类:

                • 非抢占式调度算法:发生时钟中断时不调度;
                • 抢占式调度算法:通过时钟中断使CPU控制权返回给调度程序,进而调度其它进程。

                非抢占式调度算法:正在运行的进程只有在该进程执行完成或发生阻塞(如I/O请求)的情况下才会释放CPU;

                抢占式调度算法:分给进程的时间片耗尽之后,无论当前进程有没有执行完成,调度程序均选择其他进程执行。

                   非抢占式调度算法

                       先来先服务

                先来先服务算法(FCFS):按照进程请求CPU的顺序调度它们。

                意思就是,所有的就绪状态的进程在一个队列中,申请使用CPU的进程按照先来后到的顺序排在队列尾部,每执行完一个进程,系统就从该队列的头部取出第一个进程来执行。

                优点:

                  • 易于理解且算法实现简单;

                  缺点:

                    • 对短进程不利。排在长进程后面的短进程需要等待很长时间,短进程的响应时间可能会很长。

                           最短作业优先

                    最短作业优先算法(SJF):每次调度时选择当前已到达的、且运行时间最短的作业。

                    优点:

                      • 对比FCFS,平均等待时间、平均周转时间、平均带权周转时间均有提高;

                      缺点:

                        • 需提前掌握各作业的运行时间;
                        • 对长作业不利。因为如果一直有短作业到来,那么长作业永远得不到调度,长作业有可能会饿死,处于一直等待短作业执行完毕的状态。

                        周转时间:从进程请求CPU到进程执行完毕为止的统计平均时间。

                               非抢占式优先级调度

                        优先级调度:每个进程被赋予一个优先级,允许优先级最高的可运行进程先运行。

                        对于非抢占式优先级调度,当一个进程到达就绪队列时,比较它的优先级与当前运行进程的优先级。如果新到达进程的优先级高于当前运行进程的优先级,非抢占优先级调度算法只是将新的进程加到就绪队列的头部,而不会进行进程切换。

                        缺点:

                          • 若有源源不断的高优先级进程到来,低优先级进程会导致饥饿。

                             抢占式调度算法

                                 最短剩余时间优先

                          最短剩余时间优先(SRTN):当一个新的进程到达时,把它所需要的整个运行时间与当前进程的剩余运行时间作比较。如果新的进程需要的时间更少,则挂起当前进程,运行新的进程,否则新的进程等待。

                          优点:

                            • 可以使新的短进程得到良好的服务。

                            缺点:

                              • 需提前掌握各进程的运行时间;
                              • 对长进程不利。

                              最短剩余时间优先(SRTN)是最短作业优先的抢占式版本。

                                     轮转调度

                              轮转调度(RR):每个进程被分配一个时间段,称为时间片,即允许该进程在该时间段内运行。如果在时间片结束时该进程还在运行,则剥夺其CPU并分配给另一个进程;如果该进程在时间片结束前阻塞或结束,则立即进行进程切换。

                              轮转调度算法对每个进程都一视同仁,就好比大家都排好队,一个一个来,每个人都运行一会儿再接着重新排队等待运行。

                              image.gif编辑

                              优点:

                                • 易理解且算法易实现;
                                • 可以兼顾长进程和短进程。

                                缺点:

                                  • 平均等待时间较长,频繁上下文切换比较费时;
                                  • 时间片的长度选取困难。

                                  时间片设置的太短会导致过多的进程切换,降低CPU效率;

                                  时间片设置的太长又可能会引起对短的交互请求的响应时间变长。

                                  通常时间片设为20-50ms是一个较合理的折中。

                                         抢占式优先级调度

                                  优先级调度:每个进程被赋予一个优先级,允许优先级最高的可运行进程先运行。

                                  优先级调度的问题在于高优先级进程可能无休止地运行下去,对此有两种解决方案:

                                    • 调度程序可能在每个时钟中断降低当前进程的优先级。如果调整后该进程的优先级低于次高优先级的进程,则进行进程切换。
                                    • 给每个进程赋予一个允许运行的最大时间片,时间片耗尽,次高优先级的进程就获得运行机会。

                                    优先级有静态赋予和动态赋予两种方式。

                                    静态赋予即在创建进程时人为确定进程的优先级,并且规定它在进程的整个运行期间保持不变;

                                    动态赋予即在创建进程时赋予该进程一个初始优先级,然后系统根据进程的执行情况的变化而不断改变其优先级,以便获得更好的调度性能。

                                    对于抢占式优先级调度,当一个进程到达就绪队列时,比较它的优先级与当前运行进程的优先级。如果新到达进程的优先级高于当前运行进程的优先级,那么抢占式优先级调度算法就会进行进程切换,让新到的高优先级进程运行。

                                           多级反馈队列

                                    多级反馈队列:在系统中设置多个就绪队列,并为每个队列赋予不同的优先级,从第一个开始逐个降低。不同队列中的进程所赋予的执行时间也不同,优先级越高,时间片越小。

                                      • 首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程,则调度次优先级队列中的进程;
                                      • 对于同一个队列中的各个进程,按照时间片轮转调度;
                                      • 当一个进程用完分配的时间片后,它被移到低一级优先级队列。

                                             彩票调度

                                      彩票调度:为进程提供各种系统资源(如CPU时间)的彩票。一旦要做出调度决策时,就随机抽取一张彩票,拥有该彩票的进程则获得该资源。

                                      为了增加重要进程“中彩票”的机率,可以给它们额外的彩票。

                                             公平分享调度

                                      公平分享调度:考虑进程的拥有者是谁,保证每个用户公平的分享CPU。

                                      之前的调度算法都不关注进程所有者是谁。这样做的结果是,如果用户1启动9个进程而用户2启动1个进程,使用轮转或相同优先级调度算法,那么用户1将得到90%的CPU时间,而用户2只得到10%的CPU时间。

                                      相关实践学习
                                      CentOS 7迁移Anolis OS 7
                                      龙蜥操作系统Anolis OS的体验。Anolis OS 7生态上和依赖管理上保持跟CentOS 7.x兼容,一键式迁移脚本centos2anolis.py。本文为您介绍如何通过AOMS迁移工具实现CentOS 7.x到Anolis OS 7的迁移。
                                      相关文章
                                      |
                                      3天前
                                      |
                                      算法 调度 UED
                                      深入理解操作系统:进程调度与优先级队列
                                      【10月更文挑战第31天】在计算机科学的广阔天地中,操作系统扮演着枢纽的角色,它不仅管理着硬件资源,还为应用程序提供了运行的环境。本文将深入浅出地探讨操作系统的核心概念之一——进程调度,以及如何通过优先级队列来优化资源分配。我们将从基础理论出发,逐步过渡到实际应用,最终以代码示例巩固知识点,旨在为读者揭开操作系统高效管理的神秘面纱。
                                      |
                                      2天前
                                      |
                                      Linux 调度 C语言
                                      深入理解操作系统:进程和线程的管理
                                      【10月更文挑战第32天】本文旨在通过浅显易懂的语言和实际代码示例,带领读者探索操作系统中进程与线程的奥秘。我们将从基础知识出发,逐步深入到它们在操作系统中的实现和管理机制,最终通过实践加深对这一核心概念的理解。无论你是编程新手还是希望复习相关知识的资深开发者,这篇文章都将为你提供有价值的见解。
                                      |
                                      4天前
                                      |
                                      算法 调度 UED
                                      深入理解操作系统的进程调度机制
                                      本文旨在探讨操作系统中至关重要的组成部分之一——进程调度机制。通过详细解析进程调度的概念、目的、类型以及实现方式,本文为读者提供了一个全面了解操作系统如何高效管理进程资源的视角。此外,文章还简要介绍了几种常见的进程调度算法,并分析了它们的优缺点,旨在帮助读者更好地理解操作系统内部的复杂性及其对系统性能的影响。
                                      |
                                      5天前
                                      |
                                      算法 Linux 定位技术
                                      Linux内核中的进程调度算法解析####
                                      【10月更文挑战第29天】 本文深入剖析了Linux操作系统的心脏——内核中至关重要的组成部分之一,即进程调度机制。不同于传统的摘要概述,我们将通过一段引人入胜的故事线来揭开进程调度算法的神秘面纱,展现其背后的精妙设计与复杂逻辑,让读者仿佛跟随一位虚拟的“进程侦探”,一步步探索Linux如何高效、公平地管理众多进程,确保系统资源的最优分配与利用。 ####
                                      28 4
                                      |
                                      5天前
                                      深入理解操作系统:进程与线程的管理
                                      【10月更文挑战第30天】操作系统是计算机系统的核心,它负责管理计算机硬件资源,为应用程序提供基础服务。本文将深入探讨操作系统中进程和线程的概念、区别以及它们在资源管理中的作用。通过本文的学习,读者将能够更好地理解操作系统的工作原理,并掌握进程和线程的管理技巧。
                                      15 2
                                      |
                                      4天前
                                      |
                                      消息中间件 算法 Linux
                                      深入理解操作系统之进程管理
                                      【10月更文挑战第30天】在数字时代的浪潮中,操作系统作为计算机系统的核心,扮演着至关重要的角色。本文将深入浅出地探讨操作系统中的进程管理机制,从进程的概念入手,逐步解析进程的创建、调度、同步与通信等关键过程,并通过实际代码示例,揭示这些理论在Linux系统中的应用。文章旨在为读者提供一扇窥探操作系统深层工作机制的窗口,同时激发对计算科学深层次理解的兴趣和思考。
                                      |
                                      6天前
                                      |
                                      缓存 负载均衡 算法
                                      Linux内核中的进程调度算法解析####
                                      本文深入探讨了Linux操作系统核心组件之一——进程调度器,着重分析了其采用的CFS(完全公平调度器)算法。不同于传统摘要对研究背景、方法、结果和结论的概述,本文摘要将直接揭示CFS算法的核心优势及其在现代多核处理器环境下如何实现高效、公平的资源分配,同时简要提及该算法如何优化系统响应时间和吞吐量,为读者快速构建对Linux进程调度机制的认知框架。 ####
                                      |
                                      6天前
                                      |
                                      消息中间件 算法 调度
                                      深入理解操作系统:进程管理与调度策略
                                      【10月更文挑战第29天】本文将带领读者深入探讨操作系统中的核心组件之一——进程,并分析进程管理的重要性。我们将从进程的生命周期入手,逐步揭示进程状态转换、进程调度算法以及优先级调度等关键概念。通过理论讲解与代码演示相结合的方式,本文旨在为读者提供对进程调度机制的全面理解,从而帮助读者更好地掌握操作系统的精髓。
                                      18 1
                                      |
                                      6天前
                                      |
                                      算法 调度 UED
                                      深入理解操作系统中的进程调度
                                      【10月更文挑战第29天】探索进程调度的奥秘,本文将带你深入了解在操作系统中如何管理和控制多个并发执行的程序。从简单的调度算法到复杂的多级反馈队列,我们将逐步揭示如何优化系统性能和提高资源利用率。准备好一起揭开进程调度的神秘面纱吧!
                                      |
                                      2天前
                                      |
                                      算法 调度 UED
                                      深入浅出操作系统调度策略
                                      【10月更文挑战第33天】在数字时代的心脏,操作系统扮演着至关重要的角色。本文将探讨操作系统的核心功能之一——进程调度策略的设计与影响。我们将从理论到实践,通过浅显易懂的语言和具体代码示例,揭示如何通过不同的调度算法来优化系统性能和用户体验。无论你是技术新手还是资深开发者,这篇文章都将为你提供新的视角和深入的理解。