操作系统中的调度算法

操作系统中的调度算法

先来先服务FCFS

  先来先服务是最简单的策略,也成为先进先出FIFO。首先它是一个非抢占的。如字面的意思,它根据进程到达时间决定先运行哪一个进程。

  这里给出一个实际的例子。以表格的形式表现出在FIFO策略下各进程的情况。

操作系统中的调度算法

简单说就是依次执行完成,从时间轴上来看

操作系统中的调度算法

以表格的形式展现:

操作系统中的调度算法

其中开始时间是上一个进程的结束时间

      结束时间=开始时间+(服务or执行)时间

      周转周期=结束时间-到达时间

      带权周转时间=周转时间/服务时间

最短进程优先SPN

也称最短作业优先(Short Job First,SJF)。它也是一个非抢占的。是根据服务的时间经行选择。在这里要注意下到达时间的顺序。比如实例中单纯以大小来排序的话是E-A-C-D-B,但正确的排序一定是A-B为开头。以时间为顺序:

 操作系统中的调度算法

例子中A运行结束时间为3,这时只有B进程等待。所以A运行结束后直接运行B。B结束后时间点到9,CDE都在等待。这个时候就选择服务时间最少的E,然后是较少的C,最后是D。以表格的形式展示:

操作系统中的调度算法

最短剩余时间优先SRT

SRT是针对SPN增加了抢占机制的版本,就好比例子中B运行时间非常长,在这期间其他所有的进程都在等待,如果将其中断,先处理所需时间少的,运行效率会有显著提升。一定要先明确SRT是抢占的。先给出时间为顺序的图:

 操作系统中的调度算法

1. A先运行至2,B到达等待。

2. A运行到3结束,B开始运行。

3. B开始运行,运行到4时,C进程到达,且C只需要4,此时B还需要5。所以先运行C,B继续等待。

4. C运行时间点到达6时,D到达,D需要5,进入等待,排在B后。

5. C运行结束,此时时间点是8,E到达,运行时间只要2,小于等待的BD,直接运行。

6. C运行结束,B开始运行。

7. B运行结束,D开始运行。

以表格的形式展现:

操作系统中的调度算法

 

轮转RR

轮转也称时间片技术(time slicing,SL),对于轮转法,最重要的是时间片的长度。轮转算法以一个周期(q)产生中断,当中断发生时,当前运行的程序置于就绪队列(队尾)中,然后基于FCFS选择下一个就绪作业运行。在这里我们以时间片q=1举例。

q=1,所以一次只能运行一个时间片。

0:A1运转(右标表示运行了几个)

1:A2运转

2:B1运转,A3等待(B开始)

3:A3运转,B2等待

4:B2运转,C1等待,(A结束)

5:C1运转,B3等待(C开始)

6:B3运转,D1等待,C2等待

7:D1运转,C2等待,B4等待(D开始)

8:C2运行,B4等待,E1等待,D2等待

9:B4运行,E1等待,D2等待,C3等待

10:E1运行,D2等待,C3等待,B5等待(E开始)

11:D2运行,C3等待,B5等待,E2等待

12:C3运行,B5等待,E2等待,D3等待

13:B5运行,E2等待,D3等待,C4等待

14:E2运行,D3等待,C4等待,B6等待

15:D3运行,C4等待,B6等待(E结束)

16:C4运行,B6等待,D4等待

17:B6运行,D4等待(C结束)

18:D5运行,D6等待(B结束)

19:D6运行

20:D结束

表格展示:

 操作系统中的调度算法

 

高响应比优先HRRN

高响应比优先调度算法

高响应比优先调度算法主要用于作业调度,该算法是对FCFS调度算法和SJF调度算法的一种综合平衡,同时考虑每个作业的等待时间和估计的运行时间。在每次进行作业调度时,先计算后备作业队列中每个作业的响应比,从中选出响应比最高的作业投入运行。 

该算法实际上是一种动态优先调度算法,它以响应比作为作业或进程的动态优先权,其目的是既照顾短作业,又考虑到作业的等待时间,使长作业不会长期等待;但每次调度前,都要进行响应比计算,会增加系统开销。

1、响应比 = 响应时间 / 要求服务时间 = (等待时间 + 要求服务时间) / 要求服务时间
2、作业周转时间=完成时间-提交时间
3、作业带权周转时间=周转时间 / 运行时间

 

根据公式可知:

当作业的等待时间相同时,则要求服务时间越短,其响应比越高,有利于短作业。

当要求服务时间相同时,作业的响应比由其等待时间决定,等待时间越长,其响应比越高,因而它实现的是先来先服务。

对于长作业,作业的响应比可以随等待时间的增加而提高,当其等待时间足够长时,其响应比便可升到很高,从而也可获得处理机。克服了饥饿状态,兼顾了长作业。

下图为手写实例,字不太好,多多包涵,勿喷。操作系统中的调度算法

操作系统中的调度算法

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114770.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • python基础(7)内置函数divmod用法

    python基础(7)内置函数divmod用法前言我们都知道,python中//代表整数运算中的取整,%代表整数运算中的取余,那么有什么函数可以同时取到整数和余数吗?答案是有的,使用python内置函数divmoddivmod首先看一下源

  • 英语学习口诀大全be 的用法口诀

    英语学习口诀大全be 的用法口诀

  • python 下载百度文库_百度文库随便下载,解除限制「建议收藏」

    阅读须知:文章介绍的软件下载地址载文末,需要复制链接到浏览器打开今天有小伙伴在群里问有没有百度文库的下载工具,其实之前推荐过,但目前有新的工具出现了,而且更加好用,所以给大家更新一下百度文档0.95吾爱大神力作,软件是用python写的,跟其他下载器相比,优点就是能下载源文档,以前的冰点也很好用,但缺点是下载的是pdf文件,还需要转换,而这款软件相对来说方便多了纯文字文档下载之后是doc文件,图文…

  • Ubuntu保存退出vim编辑器「建议收藏」

    Ubuntu保存退出vim编辑器「建议收藏」命令模式,从键盘上输入的任何字符都被作为编辑命令来解释,vi下很多操作如配置编辑器、文本查找和替换、选择文本等都是在命令模式下进行的。输入模式,从键盘上输入的所有字符都被插入到正在编辑的缓冲区中,被当作正文。1.编辑进入vi/vim后按字母“i”或“I”即可进入编辑状态(此时左下角会出现“插入”),另外还可以用a…

  • 基于CodeMirror 10分钟打造一个记事本应用(真的能使用,非demo)[通俗易懂]

    基于CodeMirror 10分钟打造一个记事本应用(真的能使用,非demo)[通俗易懂]直接看最终效果在浏览器里面可以随时调出记事本,而且内容自动保存不怕丢失再来看怎么做的原理其实很简单主要使用了codeMirror来做编辑器数据保存在本地存储,编辑器内容变化时会自动存储,再次打开时会从本地存储里面读取并恢复在标签页直接打开、从工具栏打开记事本,需要安装chrome插件https://plugin.csdn.net/最后来看看代码怎么写1.创建扩展应用1.从桌面的`插件扩展`图标进入扩展后台2.点击`添加插件`,填写名称后,选择`本地代码`后确定即可3.在

  • 前端工程配置Nginx反向代理[通俗易懂]

    前端工程配置Nginx反向代理HTTP配置HTTPS配置配置两个反向代理,一个代理http页面,一个代理https页面,前者监听80端口,后者监听443端口。配置后整个文件如下,其中有不少冗余,挑有用的看即可。#user nobody;worker_processes 1;#error_log logs/error.log;#error_log logs/error.log notice;#error_log logs/error.log info;#pid

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号