热门标签 | HotTags
当前位置:  开发笔记 > 后端 > 正文

2.2.4调度算法(1)

调度算法一、先来先服务(FCFS,FirstComeFirstServe)​例题:各进程到达就绪队列的时间、需要的运行时间如下表所示。使用先来先服务调度算法,计算各进程的等待时间

调度算法

image-20210918225232607


一、先来先服务(FCFS,First Come First Serve)

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

image-20210918232106451

​ 先来先服务调度算法:按照到达的先后顺序调度,事实上就是等待时间越久的越优先得到服务。

​ 因此,调度顺序为:P1 →P2→P3→P4

image-20210918232131120

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

image-20210918232357132

image-20210918232546220






二、短作业优先(SJF, Shortest Job First )

​ 例题:各进程到达就绪队列的时间、需要的运行时间如下表所示。使用非抢占式(严格来说,用于进程调度应该称为短进程优先调度算法(SPF))的短作业优先调度算法,计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

image-20210918232106451

​ 短作业/进程优先调度算法:每次调度时选择当前已到达运行时间最短的作业/进程。

​ 因此,调度顺序为:P1→P3→P2→P4

image-20210918233009514

image-20210918233027793

​ 对比FCFS算法的结果,显然SPF算法的平均等待/周转/带权周转时间都要更低



​ 例题:各进程到达就绪队列的时间、需要的运行时间如下表所示。使用抢占式(抢占式的短作业优先算法又称“最短剩余时间优先算法(SRTN))的短作业优先调度算法,计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

image-20210918232106451

最短剩余时间优先算法:每当有进程加入就绪队列改变时就需要调度,如果新到达的进程剩余时间比当前运行的进程剩余时间更短,则由新进程抢占处理机,当前运行进程重新回到就绪队列。另外,当一个进程完成时也需要调度

image-20210918233704073

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

​ 0时刻(P1到达):P1(7)

​ 2时刻(P2到达)

推荐阅读
  • SPFA算法详解与应用
    当图中包含负权边时,传统的最短路径算法如Dijkstra不再适用,而Bellman-Ford算法虽然能解决问题,但其时间复杂度过高。SPFA算法作为一种改进的Bellman-Ford算法,能够在多数情况下提供更高效的解决方案。本文将详细介绍SPFA算法的原理、实现步骤及其应用场景。 ... [详细]
  • 本文详细介绍了Socket在Linux内核中的实现机制,包括基本的Socket结构、协议操作集以及不同协议下的具体实现。通过这些内容,读者可以更好地理解Socket的工作原理。 ... [详细]
  • Java高级工程师学习路径及面试准备指南
    本文基于一位朋友的PDF面试经验整理,涵盖了Java高级工程师所需掌握的核心知识点,包括数据结构与算法、计算机网络、数据库、操作系统等多个方面,并提供了详细的参考资料和学习建议。 ... [详细]
  • 本文详细介绍了二叉堆的概念及其在Java中的实现方法。二叉堆是一种特殊的完全二叉树,具有堆性质,常用于实现优先队列。 ... [详细]
  • 来自FallDream的博客,未经允许,请勿转载,谢谢。一天一套noi简直了.昨天勉强做完了noi2011今天教练又丢出来一套noi ... [详细]
  • 本文详细介绍了 Redis 中的主要数据类型,包括 String、Hash、List、Set、ZSet、Geo 和 HyperLogLog,并提供了每种类型的基本操作命令和应用场景。 ... [详细]
  • 本笔记记录了几个典型的 LeetCode 编程题目及其解决方案,包括使用两个栈实现队列、计算斐波那契数列、青蛙跳台阶问题以及寻找旋转排序数组中的最小值。 ... [详细]
  • 入门指南:使用FastRPC技术连接Qualcomm Hexagon DSP
    本文旨在为初学者提供关于如何使用FastRPC技术连接Qualcomm Hexagon DSP的基础知识。FastRPC技术允许开发者在本地客户端实现远程调用,从而简化Hexagon DSP的开发和调试过程。 ... [详细]
  • Jenkins API当前未直接提供获取任务构建队列长度的功能,因此需要通过解析HTML页面来间接实现这一需求。 ... [详细]
  • 本文探讨了有效学习专业技能的方法,包括编程语言、操作系统、软件组件及前沿技术的探索,旨在为初学者提供一套系统的自学指南。 ... [详细]
  • 流处理中的计数挑战与解决方案
    本文探讨了在流处理中进行计数的各种技术和挑战,并基于作者在2016年圣何塞举行的Hadoop World大会上的演讲进行了深入分析。文章不仅介绍了传统批处理和Lambda架构的局限性,还详细探讨了流处理架构的优势及其在现代大数据应用中的重要作用。 ... [详细]
  • 1、什么是过滤器管道使用竖线(|)将两个命令隔开,竖线左边命令的输出就会作为竖线右边命令的输入。连续使用竖线表示第一个命令的输出会作为第二个命令的输入,第二个命令的输出又会作为第三个命令的输入, ... [详细]
  • 深入探讨:Actor模型如何解决并发与分布式计算难题
    在现代软件开发中,高并发和分布式系统的设计面临着诸多挑战。本文基于Akka最新文档,详细探讨了Actor模型如何有效地解决这些挑战,并提供了对并发和分布式计算的新视角。 ... [详细]
  • JUC并发编程——线程的基本方法使用
    目录一、线程名称设置和获取二、线程的sleep()三、线程的interrupt四、join()五、yield()六、wait(),notify(),notifyAll( ... [详细]
  • 本文探讨了如何在Windows程序中实现高精度的定时控制,特别是针对需要精确控制发包频率的应用场景,如“小兵以太网测试仪”。 ... [详细]
author-avatar
小变态徒
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有