当前位置: 首页 > news >正文

进程调度算法之先来先服务(FCFS),短作业优先(SJF)以及高响应比优先(HRRN)

1.先来先服务(FCFS)

first come first service

1.算法思想

主要从“公平”的角度考虑(类似于我们生活中排队买东西的例子)

2.算法规则

按照作业/进程到达的先后顺序进行服务。

3.用于作业/进程调度

用于作业调度时,考虑的是哪个作业先到达后备队列;用于进程调度时,考虑的是哪个进程先到达就绪队列。

4.是否可抢占

非抢占式的算法。

5.优缺点

  • 优点:公平、算法实现简单
  • 缺点:排在长作业(进程)后面的短作业需要等待很长时间,带权周转时间很大,对短作业来说用户体验不好。即,FCFS算法对长作业有利,对短作业不利

6.是否导致饥饿:

不会。
饥饿:某进程/作业长期得不到服务

7.例题:

各进程到达就绪队列的时间、需要的运行时间如下表所示。使用先来先服务调度算法,计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

在这里插入图片描述
先来先服务调度算法:
按照到达的先后顺序调度,事实上就是等待时间越久的越优先得到服务。
因此,调度顺序为:P1 ⟶ \longrightarrow P2 ⟶ \longrightarrow P3 ⟶ \longrightarrow P4

在这里插入图片描述

注意:本例中的进程都是纯计算型的进程,一个进程到达后要么在等待,要么在运行。
如果是又有计算、又有I/O操作的进程,其等待时间就是周转时间 − - 运行时间 − - I/O操作的时间

2.短作业优先(SJF)

shortest job first

1.算法思想

追求最少的平均等待时间,最少的平均周转时间、最少的平均平均带权周转时间。

2.算法规则

最短的作业/进程优先得到服务(所谓“最短”,是指要求服务时间最短)

3.用于作业/进程调度

即可用于作业调度,也可用于进程调度。
用于进程调度时称为“短进程优先(SPF, Shortest Process First)算法”

4.是否可抢占

SJF和SPF是非抢占式的算法。
但是也有抢占式的版本――最短剩余时间优先算法(SRTN, Shortest Remaining Time Next)

5.优缺点

  • 优点:“最短的”平均等待时间、平均周转时间
  • 缺点:不公平。对短作业有利,对长作业不利。可能产生饥饿现象。另外,作业/进程的运行时间是由用户提供的,并不一定真实,不一定能做到真正的短作业优先。

6.是否导致饥饿:

会。如果源源不断地有短作业/进程到来,可能使长作业/进程长时间得不到服务,产生“饥饿”现象。如果一直得不到服务,则称为“饿死”

7.例题

1.例题1:各进程到达就绪队列的时间、需要的运行时间如下表所示。使用非抢占式的短作业优先调度算法,计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

在这里插入图片描述
短作业/进程优先调度算法:
每次调度时选择当前已到达且运行时间最短的作业/进程。
因此,调度顺序为:P1 ⟶ \longrightarrow P3 ⟶ \longrightarrow P2 ⟶ \longrightarrow P4

在这里插入图片描述

2.例题2:各进程到达就绪队列的时间、需要的运行时间如下表所示。使用抢占式的短作业优先调度算法,计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。
在这里插入图片描述
最短剩余时间优先算法:
每当有进程加入就绪队列改变时就需要调度,如果新到达的进程剩余时间比当前运行的进程剩余时间更短,则由新进程抢占处理机,当前运行进程重新回到就绪队列。
另外,当一个进程完成时也需要调度。

需要注意的是,当有新进程到达时就绪队列就会改变,就要按照上述规则进行检查。
以下Pn(m)表示当前Pn进程剩余时间为m。各个时刻的情况如下:

在这里插入图片描述
根据上图分析计算:
在这里插入图片描述

8.做题细节

  1. 如果题目中未特别说明,所提到的“短作业/进程优先算法”默认是非抢占式的
  2. 在所有进程同时可运行时,采用SJF调度算法的平均等待时间、平均周转时间最少
  3. 在所有进程都几乎同时到达时,采用SJF调度算法的平均等待时间、平均周转时间最少
  4. 抢占式的短作业/进程优先调度算法(最短剩余时间优先, SRNT算法)的平均等待时间、平均周转时间最少
  5. 虽然严格来说,SJF的平均等待时间、平均周转时间并不一定最少,但相比于其他算法(如FCFS),SJF依然可以获得较少的平均等待时间、平均周转时间
  6. 如果选择题中遇到“SJF算法的平均等待时间、平均周转时间最少”的选项,那最好判断其他选项是不是有很明显的错误,如果没有更合适的选项,那也应该选择该选项

3.高响应比优先(HRRN)

highest response ratio next

1.算法思想

要综合考虑作业/进程的等待时间和要求服务的时间

2.算法规则

在每次调度时先计算各个作业/进程的响应比,选择响应比最高的作业/进程为其服务。
响应比 = 等待时间 + 要求服务时间 要求服务时间 响应比=\frac{等待时间+要求服务时间}{要求服务时间} 响应比=要求服务时间等待时间+要求服务时间
响应比大于等于1。

3.用于作业/进程调度

即可用于作业调度,也可用于进程调度。

4.是否可抢占

非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时,才需要调度,才需要计算响应比。

5.优缺点

  • 综合考虑了等待时间和运行时间(要求服务时间)
  • 等待时间相同时,要求服务时间短的优先( SJF的优点)
  • 要求服务时间相同时,等待时间长的优先(FCFS的优点)
  • 对于长作业来说,随着等待时间越来越久,其响应比也会越来越大,从而避免了长作业饥饿的问题

6.是否导致饥饿:

不会。

7.例题

各进程到达就绪队列的时间、需要的运行时间如下表所示。使用高响应比优先调度算法,计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

在这里插入图片描述
高响应比优先算法:
非抢占式的调度算法,只有当前运行的进程主动放弃CPU时(正常/异常完成,或主动阻塞),才需要进行调度,调度时计算所有就绪进程的响应比,选响应比最高的进程上处理机。

在这里插入图片描述

注:
这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标,但是不关心“响应时间”,也并不区分任务的紧急程度,因此对于用户来说,交互性很糟糕。
因此这三种算法一般适合用于早期的批处理系统,当然,FCFS算法也常结合其他的算法使用,在现在也扮演着很重要的角色。

相关文章:

进程调度算法之先来先服务(FCFS),短作业优先(SJF)以及高响应比优先(HRRN)

1.先来先服务(FCFS) first come first service 1.算法思想 主要从“公平”的角度考虑(类似于我们生活中排队买东西的例子) 2.算法规则 按照作业/进程到达的先后顺序进行服务。 3.用于作业/进程调度 用于作业调度时,考虑的是哪个作业先…...

MyBatisPlus(九)模糊查询

说明 模糊查询&#xff0c;对应SQL语句中的 like 语句&#xff0c;模糊匹配“要查询的内容”。 like /*** 查询用户列表&#xff0c; 查询条件&#xff1a;姓名包含 "J"*/Testvoid like() {String name "J";LambdaQueryWrapper<User> wrapper ne…...

Spring 原理

它是一个全面的、企业应用开发一站式的解决方案&#xff0c;贯穿表现层、业务层、持久层。但是 Spring仍然可以和其他的框架无缝整合。 1 Spring 特点 轻量级控制反转面向切面容器框架集合 2 Spring 核心组件 3 Spring 常用模块 4 Spring 主要包 5 Spring 常用注解 bean…...

基于微信小程序的明星应援小程序设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言系统主要功能&#xff1a;具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09;有保障的售后福利 代码参考源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计…...

try catch 中的finally什么时候运行

try catch 中的finally什么时候运行 在Java、C#等编程语言中&#xff0c;try-catch-finally语句块用于处理异常。finally块的执行时机通常是在try块中的代码执行完毕之后&#xff0c;无论try块中的代码是否引发了异常。 具体执行顺序如下&#xff1a; 1、try块中的代码首先被…...

力扣 -- 322. 零钱兑换(完全背包问题)

参考代码&#xff1a; 未优化代码&#xff1a; class Solution { public:int coinChange(vector<int>& coins, int amount) {int n coins.size();const int INF 0x3f3f3f3f;//多开一行&#xff0c;多开一列vector<vector<int>> dp(n 1, vector<i…...

[python]pip安装requiements.txt跳过错误包继续安装

在linux上可以用下面操作进行 while read requirement; do sudo pip install $requirement; done < requirement.txt 在windows上写个脚本 import sys from pip._internal import main as pip_maindef install(package):pip_main([--default-timeout1000,install,-U, pac…...

1.5 计算机网络的类别

思维导图&#xff1a; 1.5.1 计算机网络的定义 我的笔记&#xff1a; #### 精确定义&#xff1a; 计算机网络没有统一的精确定义&#xff0c;但一种较为接近的定义是&#xff1a;计算机网络主要由一些通用的、可编程的硬件互连而成&#xff0c;这些硬件并非专门用来实现某一特…...

Go 基本数据类型和 string 类型介绍

Go 基础之基本数据类型 文章目录 Go 基础之基本数据类型一、整型1.1 平台无关整型1.1.1 基本概念1.1.2 分类有符号整型&#xff08;int8~int64&#xff09;无符号整型&#xff08;uint8~uint64&#xff09; 1.2 平台相关整型1.2.1 基本概念1.2.2 注意点1.2.3 获取三个类型在目标…...

Python中print()打印如何不换行?

文章目录 Python中print()打印如何不换行python2.xpython3.x print()函数语法objects基本语法sep基本语法end基本语法 Python中print()打印如何不换行 print() 函数用于打印输出&#xff0c;是python中最常见的一个内置函数。 如何在Python中打印两个或多个变量、语句时而不进…...

python 学习随笔 4

列表list 将序列前几个进行替换&#xff08;数量可以不同&#xff09; 将序列进行间隔替换&#xff08;必须保证数量相同&#xff0c;否则报错&#xff09; 删除序列内元素 向序列后新增一个元素 向序列后新增多个元素 将序列进行数乘&#xff08;不是产生几个序列哦&#xff0…...

【网络安全-信息收集】网络安全之信息收集和信息收集工具讲解

一&#xff0c;域名信息收集 1-1 域名信息查询 可以用一些在线网站进行收集&#xff0c;比如站长之家 域名Whois查询 - 站长之家站长之家-站长工具提供whois查询工具&#xff0c;汉化版的域名whois查询工具。https://whois.chinaz.com/ 可以查看一下有没有有用的信息&#xf…...

设计模式12、代理模式 Proxy

解释说明&#xff1a;代理模式&#xff08;Proxy Pattern&#xff09;为其他对象提供了一种代理&#xff0c;以控制对这个对象的访问。在某些情况下&#xff0c;一个对象不适合或者不能直接引用另一个对象&#xff0c;而代理对象可以在客户端和目标对象之间起到中介的作用。 抽…...

ZXing - barcode scanning library for Java, Android

官网 GitHub - zxing/zxing: ZXing ("Zebra Crossing") barcode scanning library for Java, Android 使用说明 Getting Started Developing zxing/zxing Wiki GitHub 参考 Android中二维码的扫描与生成&#xff08;zxing库&#xff09;_android 二维码生成-C…...

MySQL存储引擎:选择合适的引擎优化数据库性能

什么是存储引擎&#xff1f; 在MySQL中&#xff0c;存储引擎是数据库管理系统的一部分&#xff0c;负责数据的存储、检索和管理。 常见的MySQL存储引擎 InnoDB InnoDB是MySQL的默认存储引擎&#xff0c;它支持事务和行级锁定&#xff0c;适用于大多数在线事务处理&#xff…...

用向量数据库Milvus Cloud 搭建AI聊天机器人

加入大语言模型(LLM) 接着,需要在聊天机器人中加入 LLM。这样,用户就可以和聊天机器人开展对话了。本示例中,我们将使用 OpenAI ChatGPT 背后的模型服务:GPT-3.5。 聊天记录 为了使 LLM 回答更准确,我们需要存储用户和机器人的聊天记录,并在查询时调用这些记录,可以用…...

深入理解JVM虚拟机第十一篇:详细介绍JVM中运行时数据区

文章目录 前言 一:运行时数据区详解 1:线程私有和线程公有区域 2:阿里的运行时数据区图...

mysql面试题17:MySQL引擎InnoDB与MyISAM的区别

该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:MySQL引擎InnoDB与MyISAM的区别 InnoDB和MyISAM是MySQL中两种常见的存储引擎,它们在功能和性能方面有一些区别。下面将详细介绍它们之间的差异。…...

第2篇 机器学习基础 —(1)机器学习方式及分类、回归

前言&#xff1a;Hello大家好&#xff0c;我是小哥谈。机器学习是一种人工智能的分支&#xff0c;它使用算法和数学模型来使计算机系统能够从经验数据中学习和改进&#xff0c;而无需显式地编程。机器学习的目标是通过从数据中发现模式和规律&#xff0c;从而使计算机能够自动进…...

uniapp echarts 适配H5与微信小程序

文章目录 前言一、修改 ec-canvas组件1.1 在ec-canvas组件methods中定义一个initChart方法1.2 用initChart全局替换this.ec.onInit1.3 监听数据变化1.4 ec-canvas完整代码参考 二、H5 echarts组件三、供外部调用的组件外部调用组件 uni-chart代码使用uni-chart 前言 接上文&…...

第46节——redux中使用不可变数据+封装immer中间件——了解

一、为什么redux中要使用不可变数据 Redux 要求使用不可变数据&#xff0c;是因为它遵循了函数式编程的原则。在函数式编程中&#xff0c;数据不可变是一项重要的原则&#xff0c;这有助于避免状态更改产生的不可预知的副作用。 在 Redux 中&#xff0c;每当 action 被分发&a…...

《数字图像处理-OpenCV/Python》连载(10)图像属性与数据类型

《数字图像处理-OpenCV/Python》连载&#xff08;10&#xff09;图像属性与数据类型 本书京东优惠购书链接&#xff1a;https://item.jd.com/14098452.html 本书CSDN独家连载专栏&#xff1a;https://blog.csdn.net/youcans/category_12418787.html 第2章 图像的数据格式 在P…...

sheng的学习笔记-【中文】【吴恩达课后测验】Course 2 - 改善深层神经网络 - 第三周测验

课程2_第3周_测验题 目录&#xff1a;目录 第一题 1.如果在大量的超参数中搜索最佳的参数值&#xff0c;那么应该尝试在网格中搜索而不是使用随机值&#xff0c;以便更系统的搜索&#xff0c;而不是依靠运气&#xff0c;请问这句话是正确的吗&#xff1f; A. 【  】对 B.…...

LLMs 用强化学习进行微调 RLHF: Fine-tuning with reinforcement learning

让我们把一切都整合在一起&#xff0c;看看您将如何在强化学习过程中使用奖励模型来更新LLM的权重&#xff0c;并生成与人对齐的模型。请记住&#xff0c;您希望从已经在您感兴趣的任务上表现良好的模型开始。您将努力使指导发现您的LLM对齐。首先&#xff0c;您将从提示数据集…...

iMazing 2.17.10官方中文版含2023最新激活许可证码

iMazing 2.17.10官方中文版是一款iOS设备管理软件&#xff0c;该软件支持对基于iOS系统的设备进行数据传输与备份&#xff0c;用户可以将包括&#xff1a;照片、音乐、铃声、视频、电子书及通讯录等在内的众多信息在Windows/Mac电脑中传输/备份/管理。 iMazing 2.17.10官方中文…...

如何在windows系统环境下使用tail命令查看日志

答案是&#xff1a; 使用tail for Windows工具 tail for Windows 是便携式软件不需要安装&#xff0c;它可用于显示文件的最后一行并跟踪/监视文件的更改。 下载地址&#xff1a; https://tail-for-windows.en.softonic.com/ 点击直接下载 解压使用 解压后需将tail.exe放入 c:…...

设计模式——访问者模式

访问者模式是什么&#xff1f; 表示一个作用于某对象结构中的各元素的操作&#xff0c;它使你可以再不改变各元素的类的前提下定义作用于这些元素的新操作 访问者模式解决什么问题&#xff1f; 男女在不同情境下表现的不同 abstract class Person {protected String action…...

一文读懂UTF-8的编码规则

之前写过一篇文章“一文彻底搞懂计算机中文编码”里面只是介绍了GB2312编码知识&#xff0c;关于utf8没有涉及到&#xff0c;经过查询资料发现utf8是对unicode的一种可变长度字符编码&#xff0c;所以再记录一下。 现在国家对于信息技术中文编码字符集制定的标准是《GB 18030-…...

二叉树题目:路径总和 II

文章目录 题目标题和出处难度题目描述要求示例数据范围 前言解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目 标题和出处 标题&#xff1a;路径总和 II 出处&#xff1a;113. 路径总和 II 难度 4 级 题目描述 要求 给你二叉树的根结点 root \tex…...

Qt model/view 理解01

在 Qt 中对数据处理主要有两种方式&#xff1a;1&#xff09;直接对包含数据的的数据项 item 进行操作&#xff0c;这种方法简单、易操作&#xff0c;现实方式单一的缺点&#xff0c;特别是对于大数据或在不同位置重复出现的数据必须依次对其进行操作&#xff0c;如果现实方式改…...