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

交互式调度算法学不会?————一文学懂(RR(时间片轮转调度算法),优先级调度算法,多级反馈队列调度算法)保姆式解析

一.时间片轮转调度(RR)算法

算法核心:
在这里插入图片描述
我们来看一道题目:
在这里插入图片描述
先来分析时间片为2的情况:

在这里插入图片描述
注意5时刻p1才运行了1个时间片还没用完分配的两个时间片,所以处于运行态不是就绪态。

在这里插入图片描述
这里要注意p3分配的时间片没有用完就已经运行结束会主动放弃处理机,一定要分清是主动让出处理机还是时间片用完被迫放弃处理机

在这里插入图片描述
甘特图如下
在这里插入图片描述
再来分析时间片大小为5的情况:

在这里插入图片描述
甘特图如下:
在这里插入图片描述
通过甘特图我们可以看出时间片越小,进程调度越频繁

补充:时间片过大或者过小的影响?****(考点)
在这里插入图片描述
小结:

在这里插入图片描述
注意时间片算法中一般只考虑响应时间不考率周转时间

二.非抢占式优先级调度算法

算法核心:
每次调度时选择当前已到达且优先级最高的进程(优先数越大,优先级越高),当前进程主动放弃处理机时发生调度。注意优先级相同时,则按照到达时间的先后顺序使用处理机,我们来看一个例子:
在这里插入图片描述
调度流程分析:
在这里插入图片描述
注意p3完成时p2,p4的优先级相同,但是p2到达时间更早优先使用处理机
在这里插入图片描述

三.抢占式优先级调度算法

我们还是以具体题目分析:
在这里插入图片描述
调度流程分析:
在这里插入图片描述

这里需要注意p3完成时由于p2和p4的优先级相同,所以p4不会抢占处理机而是等p2结束让出处理机,而p1的优先级最低,所以p1会最后执行完,因此我们画出的甘特图如下:
在这里插入图片描述
可以看出p1在被不断的抢占,所以到达早的不一定最早执行完,到达晚的也不一定最晚执行完,所以实现了相对的公平。

关于优先级算法的补充说明:
在这里插入图片描述

思考题1:我们应该如何合理地设置各类进程的优先级?
在这里插入图片描述
注意:

I/O设备和CPU可以并行工作。如果优先让I/O繁忙型进程优先运行的话,则越有可能让I/O设备尽早的投入工作,资源利用率和系统吞吐量都会得到提升

思考题2:如果采用的是动态优先级,什么时候应该调整?
在这里插入图片描述
总结:
在这里插入图片描述
思考题3:
在这里插入图片描述
那么有没有一种算法可以综合他们的优点呢?由此我们引入多级反馈队列调度算法

四.多级反馈队列调度算法

算法核心:
在这里插入图片描述
我们来看一道题目:
在这里插入图片描述

在这里插入图片描述
p1先上处理机运行,用完一个时间片后进入下一级队列队尾,此时正好p2到达
在这里插入图片描述
由于第一级队列还有进程没有处理暂时还不会处理下一级的进程,所以p2再使用一个时间片,然后到下一级队列队尾
在这里插入图片描述
注意算法中有一点,当第k级队列为空时,才会为k+1级队列分配时间片,此时是第2时刻,而p3进程是在第5时刻到达,所以还未到达,所以第一级队列为空开始为第二级队列分配时间片,第二级队列的时间片大小为2,p1执行两个时间片,时间片用完后还没有运行结束,于是放到第三级队列队尾,此时p2分配时间片,要注意p2使用了一个时间片时,p3到达第一级队列,会发生如下图情况:

在这里插入图片描述
p3的优先级更高此时会发生抢占的情况,这里要注意被抢占的进程放到原队列队尾,而不是下一级队尾,所以p2放到第二级队列队尾,p3上处理机,p3使用1个时间片后正好运行结束,调出内存,如下图:
在这里插入图片描述
然后p2上处理机,由于p2此前已经运行了两个时间片(第一级一个,第二级一个,第二级被p3截断),所以再分配两个时间片即可运行结束,所以不需要转入下一级队列,此时只剩p1,如下图:
在这里插入图片描述
p1上处理机运行4个时间片,我们来看一下现在各进程的时间片使用情况:
在这里插入图片描述
p1已经使用了7个时间片,但是p1需要运行8个时间片,所以时间片使用结束后,理论上应该放到下一级队尾,但是它已经在最下面一层队列,所以它只能放回队尾再一次被调度上处理机,再分配一个时间片,如下图所示是整个运行流程:
在这里插入图片描述
小结:
在这里插入图片描述
四种算法比较:
在这里插入图片描述
写在最后:多级反馈队列算法过程相对比较复杂读者要重点理解,另外本文介绍的几种算法适用于交互式系统,上一篇文章有介绍批处理系统的四种算法,读者可比较分析


http://www.kler.cn/a/585753.html

相关文章:

  • DPU的架构:模块化与可扩展性
  • MFC控件按钮的使用
  • 破局企业数据泄露风险:安当TDE透明加密重塑文件服务器安全防线
  • Flutter+Rust Android, IOS移动端适配通用流程及依赖库处理(Openssl, Curl等)
  • 百度百科更新!树莓集团宜宾项目的深远影响与意义
  • leetcode hot100贪心
  • LeetCode hot 100—滑动窗口最大值
  • win32汇编环境,对话框程序中创建托盘示例一
  • PyTorch 系列教程:探索自然语言处理应用
  • 基于RWA 与 AI-Agent 协同的企业数字化生态构建
  • Go语言环境搭建并执行第一个Go程序
  • X86 RouterOS 7.18 设置笔记十:上海电信IPTV使用msd_lite实现组播转单拨
  • C++小课堂——friend友元
  • 基础知识《DICT协议》
  • 路由器配置命令
  • 完善机器人:让 DeepSeek 生成 API 接口,并在网页上调用
  • MySQL 的 innodb_buffer_pool_size 参数配置指南
  • [AI QA] strace | 探索 a.out
  • 正则表达式 - 修饰符
  • 书籍品读:我的世界(陈州)