(学习笔记-调度算法)进程调度算法

这篇具有很好参考价值的文章主要介绍了(学习笔记-调度算法)进程调度算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

进程调度算法也称 CPU 调度算法,毕竟进程是由 CPU 调度的。

当 CPU 空闲时,操作系统就选择内存中标的某个 [就绪状态] 的进程,将其分配给 CPU。

什么时候会发生CPU调度呢?通常有以下情况:

  1. 当进程从运行状态转换到等待状态
  2. 当进程从运行状态转换到就绪状态
  3. 当进程从等待状态转换到就绪状态
  4. 当进程从运行状态转换到终止状态

其中发生在 1 和 4 两种情况下的调度称为 [非抢占式调度] , 2 和 3 两种情况下发生的调度称为 [抢占式调度]。

非抢占式的意思是,当进程正在运行时,它就会一直运行,直到该进程完成或发生某个事件而被阻塞时,才会把 CPU 让给其他进程。

抢占式调度,顾名思义就是进程正在运行的时候,可以被打断,使其把 CPU 让给其他进程。那抢占的原则一般有三种,分别是时间片原则,优先权原则,短作业优先原则。

调度算法影响的是等待时间(进程在就绪队列中等待调度的时间总和),而不能影响进程真在使用的 CPU 时间和 I/O 时间。

常见的调度算法:

  • 先来先服务算法
  • 最短作业优先调度
  • 高响应比优先调度
  • 时间片轮转调度
  • 最高优先级调度
  • 多级反馈队列调度

先来先服务调度算法

最简单的一个调度算法,就是非抢占式的先来先服务(FCFS)算法。

(学习笔记-调度算法)进程调度算法,操作系统,学习,笔记,服务器

 先来先服务:每次从就绪队列选择最先进入队列的进程,然后一直运行,直到进程退出或被阻塞,才会继续从队列中选择第一个进程接着运行。

这似乎很公平,但是当一个长作业先运行了,那么后面的短作业等待的时间就会很长,不利于短作业。

FCFS对长作业有利,适用于CPU繁忙型作业的系统,而不适用于 I/O 繁忙型作业的系统。


最短作业优先调度算法

最短作业优先(SJF)调度算法同样也是顾名思义,它会优先选择运行时间最短的进程来运行,这有助于提高系统的吞吐量。

(学习笔记-调度算法)进程调度算法,操作系统,学习,笔记,服务器

这显然对长作业不利,很容易造成一种极端现象。

比如,一个长作业在就绪队列等待运行,而这个就绪队列有非常多的短作业,那么就会使得长作业不断地往后推,周转时间变长,致使长作业长期不会被运行。


高响应比优先调度算法

前面的 [先来先服务调度算法] 和 [最短作业优先调度算法] 都没有很好的权衡短作业和长作业。

那么。高响应比优先(HRRN)调度算法主要是权衡了短作业和长作业。

每次进行进程调度时,先计算 [响应比优先级],然后把 [响应比优先级] 最高的进程投入运行,[响应比优先级] 的计算公式:

(学习笔记-调度算法)进程调度算法,操作系统,学习,笔记,服务器

从上面的公式可以发现:

  • 如果两个进程的 [等待时间] 相同时, [要求服务时间] 越短,[响应比] 就越高,这样短作业的进程容易被选中运行
  • 如果两个进程 [要求服务时间] 相同时,[等待时间] 越长,[响应比] 就越高,这就兼顾到了长作业进程,因为进程的响应比可以随时间等待的增加而提高,当其等待时间足够长时,其响应比便可以升到很高,从而获得运行的机会

时间片轮转调度算法

最古老、最简单、最公平且使用最广泛的算法就是时间片轮转(RR)调度算法

(学习笔记-调度算法)进程调度算法,操作系统,学习,笔记,服务器

每个进程被分配一个时间段,称为时间片,即允许该进程在该时间段中运行

  • 如果时间片用完,进程还在运行,那么将会把此进程从CPU释放出来,并把 CPU分配另外一个进程
  • 如果该进程在时间片结束前阻塞或结束,则 CPU 立即进行切换

另外。时间片的长度就是一个很关键的点:

  • 如果时间片设的太短会导致过多的进程上下文切换,降低了 CPU 效率
  • 如果设的太长又可能引起对短作业进程的响应时间变长,通常将时间片设置为 20ms-50ms 是一个比较合理的折中值。

最高优先级调度算法

前面的 [时间片轮转算法] 做了一个假设,即让所有的进程同等重要,也不偏袒谁,大家的运行时间都一样。

但是对于多用户计算机系统就有不同的看法了,它们希望调度是有优先级的,即希望调度程序能从就绪队列中选择最高优先级的进程进行运行,这称为最高优先级(HPF)调度算法

进程的优先级可以分为,静态优先级或动态优先级:

  • 静态优先级:创建进程时候,就已经确定优先级了,然后整个运行时间优先级都不会变化;
  • 动态优先级:根据进程的动态变化调整优先级,比如如果进程运行时间增加,则降低其优先级,如果进程等待时间(就绪队列的等待时间)增加,则升高其优先级,也就是随着时间的推移增加等待进程的优先级

该算法也有两种处理优先级高的方法,非抢占式和抢占式:

  • 非抢占式:当就绪队列中出现优先级高的进程,运行完当前进程,再选择优先级高的进程。
  • 抢占式:当就绪队列中出现优先级高的进程,当前进程挂起,调度优先级高的进程运行。

但是依然有缺点,可能会导致低优先级的进程永远不会运行。


多级反馈队列调度算法

多级反馈队列(MFQ)调度算法是 [时间片轮转算法] 和 [最高优先级算法] 的综合和发展。

顾名思义:

  • [多级] 表示有多个队列,每个队列优先级从高到低,同时优先级越高时间片越短
  • [反馈] 表示如果有新的进程加入优先级高的队列时,立刻停止当前正在运行的进程,转而去运行优先级高的队列

(学习笔记-调度算法)进程调度算法,操作系统,学习,笔记,服务器

 工作方式:

  • 设置多个队列,赋予每个队列不同的优先级,每个队列优先级从高到低,同时优先级越高时间片越短
  • 新的进程会被放入到第一级队列的末尾,按先来先服务的原则排队等待被调度,如果在第一级队列规定的时间片没运行完成,则将其装入到第二级队列的末尾,以此类推,直至完成
  • 当较高优先级的队列为空,才调度较低优先级的队列中的进程运行。如果进程运行时,有新的进程进入较高优先级的队列,则停止当前运行的进程并将其移入到原队列末尾,接着让较高优先级的进程运行

可以发现,对于短作业可能可以在第一级队列很快被处理完。对于长作业,如果在第一级队列处理不完,可以移入下次队列等待被执行,虽然等待的时间变长了,但是运行时间也会变长,所以该算法很好的兼顾了长短作业,同时有较好的响应时间文章来源地址https://www.toymoban.com/news/detail-665606.html


到了这里,关于(学习笔记-调度算法)进程调度算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【操作系统】期末速成之计算题:进程调度算法

    先来先服务是非抢占式的算法 一个🌰 例题:各进程到达就绪队列的时间、需要的运行时间如下表所示。使用先来先服务调度算法,计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。 进程 到达时间 运行时间 P1 0 7 P2 2 4

    2024年02月11日
    浏览(41)
  • 用代码模拟操作系统进程调度算法(Python)

     引言 近日,在学习完操作系统的进程调度部分后,我萌生了一个有趣的想法:通过编写代码来模拟进程调度算法,以加深自己对这一知识点的理解。于是,我花了一整天的时间投入到了这个突发奇想的实践中。  背景 进程调度是操作系统中的重要概念,它决定了如何合理地

    2024年02月06日
    浏览(55)
  • 计算机操作系统实验-进程调度模拟算法

    进程调度是处理机管理的核心内容。本实验要求用高级语言编写模拟进程调度程序,以 便加深理解有关进程控制快、进程队列等概念,并体会和了解优先数算法和时间片轮转算法 的具体实施办法。 1.设计进程控制块 PCB 的结构,通常应包括如下信息: 进程名、进程优先数(

    2024年02月05日
    浏览(73)
  • 操作系统进程调度算法(c语言模拟实现)

            前言: 本文旨在分享如何使用c语言对操作系统中的部分进程调度算法进行模拟实现,以及算法描述的讲解, 完整代码放在文章末尾,欢迎大家自行拷贝调用 目录 常见的调度算法 数据结构 先来先服务调度算法 算法模拟思路: 算法模拟:  最短作业优先调度算法

    2024年02月06日
    浏览(55)
  • 操作系统进程调度算法的模拟实现(c语言版本)

            前言: 本文旨在分享如何使用c语言对操作系统中的部分进程调度算法进行模拟实现,以及算法描述的讲解, 完整代码放在文章末尾,欢迎大家自行拷贝调用 目录 常见的调度算法 数据结构 先来先服务调度算法 算法模拟思路: 算法模拟:  最短作业优先调度算法

    2024年02月06日
    浏览(55)
  • 操作系统:实验一:进程调度实验——最高优先数优先的调度算法以及先来先服务算法 源码

    一、实验目的 (1)了解进程实体PCB结构; (2)理解进程不同状态和状态之间的转换过程; (3)掌握优先数的调度算法和先来先服务算法; 二、实验内容与要求 设计一个有 N个进程共行的进程调度程序 四、实验步骤 (1)实验设计 进程调度算法: 采用最高优先数优先的调

    2024年02月06日
    浏览(45)
  • 操作系统有关进程调度算法(含先来先服务,短作业优先,优先级调度算法和时间片轮转调度算法)

    本文采用的进程调度算法有:先来先服务,短作业优先,优先级调度算法和时间片轮转调度算法。 针对这四种算法,我采用的是建立数组结构体,如: 先来先服务(FCFS)调度算法是一种最简单的调度算法,该算法既可用于作业调度,也可用于进程调度。采用FCFS算法,每次从

    2024年02月03日
    浏览(61)
  • 【操作系统】c语言--进程调度算法(FCFS和SPN)

    创作不易,本篇文章如果帮助到了你,还请点赞 关注支持一下♡𖥦)!! 主页专栏有更多知识,如有疑问欢迎大家指正讨论,共同进步! 🔥c++系列专栏:C/C++零基础到精通 🔥 给大家跳段街舞感谢支持!ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ c语言内容💖:

    2024年02月12日
    浏览(48)
  • 操作系统进程线程(一)—进程线程协程区别、多进程多线程、进程调度算法、进程线程通信

    定义上 进程: 资源分配和拥有 的基本单位,是调度的基本单位。 运行一个可执行程序会创建一个或者多个进程;进程就是运行起来的程序 线程:程序 执行 基本单位,轻量级进程。 每个进程中都有唯一的主线程 ,主线程和进程是相互依赖的关系。 协程: 用户态 的轻量级

    2024年02月01日
    浏览(57)
  • 操作系统理论:Linux进程与进程状态(进程调度的大O(1)算法数据结构模型)

    冯诺依曼体系的计算机在运行时,内存中会预加载许多程序(数据+运算指令集),然而CPU 同一时刻只能执行一个程序 (多个程序竞争CPU资源),此时就需要操作系统 对内存中的诸多程序进行管理 ,让CPU资源得到合理的分配,于是便有了进程的概念: 进程:描述程序的结构体对象( PCB结构体

    2024年02月15日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包