Linux 学习笔记(八):时间片轮转调度

news/2024/10/30 15:27:57/

看这篇文章前可以先了解一下时间片:Linux 学习笔记(七):时间片_Amentos的博客-CSDN博客

一、基本概念

       时间片轮转调度算法(Round-Robin,RR)主要用于分时操作系统中的进程调度。是一种最古老、最简单、最公平、使用最广的调度算法。

       系统为每个进程分配一个时间段,称作它的时间片,即该进程允许运行的时间。若进程在时间片结束时还在运行(进程未完成),则 CPU 将被强制剥夺并分配给另一个进程;若进程在时间片结束前就阻塞或结束了,则 CPU 在阻塞或结束时当即进行切换并分配给另一个进程。

二、实现原理

       为了实现轮转调度,系统会把所有处于就绪态的进程先入先出的原则排成一个队列 —— 就绪队列,新来的进程加到就绪队列末尾。

       每当执行进程调度时,调度程序总是选出就绪队列队首进程,然后让它在 CPU 上运行一个时间片的时间(时间片是一个很小的时间单位,通常为 10~100ms 数量级)。当进程用完分配给它的时间片后,系统的计时器发会出时钟中断,调度程序就停止该进程的运行,并把该进程放入就绪队列末尾。然后,又把 CPU 转移给就绪队列新的队首进程,同样也让它运行一个时间片,如此往复。

       这样的调度算法可以保证就绪队列中的所有进程,在一给定的时间内,都能获得一时间片的处理机执行时间。调度程序要做的就是维护这张就绪进程列表,当进程用完它的时间片后,会被移到列表的末尾。

三、进程调度

       采用时间片轮转调度算法的系统,其程序就绪队列往往按照进程到达的时间来排序。进程调度程序总是选择就绪队列中的第一个进程运行,也就是按照先来先服务原则进行调度。

       但一个进程占用处理机时,一次只能使用一个时间片的时间。在使用完一个时间片后,如果该进程还没有完成运行,它必须释放出处理机给下一个就绪的进程,而被抢占的进程则返回到就绪队列末尾重新排队并等待再次运行。

       一个处理器同一个时间只能处理一个任务,当有多个任务需要处理的时候,就要看这些任务请求的时间顺序。如果时间一致,就要进行预测。挑到一个任务后,需要若干步骤才能做完,这些步骤中有些需要处理器参与,有些不需要(如磁盘控制器的存储过程)。不需要处理器参与的时候,这部分时间就要分配给其他的进程,原来的进程就要处于等待的时间段上。经过系统周密的时间分配,宏观上就像是多个任务同时进行,但微观上是有先后顺序的,也就是时间片轮换

四、时间片的长度

       时间片轮转调度中有趣的一点是时间片的长度。从一个进程切换到另一个进程是需要一定时间的 —— 保存和装入寄存器值及内存映像、更新各种表格和队列等都是需要时间的。

       假如进程切换(process switch)【有时也称为上下文切换(context switch)】,需要 5 毫秒,再假设时间片设置为 20 毫秒。则 CPU 在做完 20 毫秒有用的工作之后,还将花费 5 毫秒来进行进程的切换。也就是说 CPU 时间的 20%( 5/(20+5) )都浪费在管理开销上。

       为了提高 CPU 使用的效率,我们将时间片设置为 500 毫秒,这样 CPU 浪费的时间只有 1% 不到。但是时间片设置得越长越好吗?如果在一个分时系统中,有十个交互用户几乎同时按下了回车键,会发生什么情况?假设前九个进程都用足了它们的时间片,那么最后一个不幸的进程必须等待将近 5 秒才能获得运行的机会。如果恰好最后一个运行的进程只是一条简短的命令,却要 5 秒才能做出响应,这样对用户的使用体验非常不好。同样的问题在一台支持多道程序的个人计算机上也会发生。

       所以结论总结如下:时间片太短会导致过多的进程切换,降低了 CPU 利用效率;而时间片太长又可能导致对较短交互请求的响应变差。所以需要寻找一个合适的时间片长度,平衡 CPU 效率和交互响应效果(100毫秒通常是一个比较合理的折中值)。

五、其它调度算法

时间片轮转调度外,还有很多其它的进程调度算法,它们各有各的优缺点,可以自行查阅资料详细了解。

1、先来先服务调度算法

       按照进程进入就绪队列先后顺序进行调度并分配处理机执行。

       先来先服务调度算法(first come first service,FCFS)是一种非抢占式的算法,先进入就绪队列的进程,先分配处理机运行。一旦一个进程占有了处理机,它就一直运行下去,直到该进程完成工作或因为等待某事件发生而不能继续运行时(阻塞),才释放出处理机。

2、短作业(进程)优先调度算法

       对短作业短进程进行优先调度的算法,可分别用于作业调度和进程调度。

       短作业优先调度算法(shortest job first,SJF)是从后备队列中选择一个若干个估计运行时间最短的作业,将它们调入内存运行。

       短进程优先调度算法(shortest process first,SPF)是从就绪队列中选出一个估计运行时间最短的进程,将处理机分配给它,并让它立即执行一直执行,直到该进程完成或发生某事件而被阻塞放弃处理机时再重新调度。

3、多级反馈队列调度算法

       设置多个就绪队列,并分别赋予不同的优先级。队列  的优先级最高,队列  次之,其余各队列优先权逐个降低。每个队列执行时间片的长度也不同,规定优先级越低则时间片越长(如:队列  的时间片要比队列  的时间片长一倍,……,队列  i+1  的时间片要比队列  的时间片长一倍)。

       (1)当一个新进程进入内存后,首先将它放入队列  的末尾,并按照 FCFS 原则排队等待调度。当轮到该进程执行时,如果它能在一个时间片内完成,便可以准备撤离系统;如果它在一个时间片结束时尚未完成,调度程序便将该进程转入队列  2  的末尾,并同样按照 FCFS 原则排队等待调度执行。如果该进程在队列  2  中运行一个时间片后仍未完成,则依次将它放入队列  3  的末尾。……如此下去,当进程降到最后一个队列——队列  n  时,则切换为 “时间片轮转” 算法进行调度直到完成。

       (2)只有当优先级较高的队列为空时,才能调度优先级较低的队列中的进程并执行。如果进程执行过程中有新进程进入优先级更高的队列,则抢先执行这个新进程,并将被抢先的进程投入原队列的末尾

       多级反馈队列调度算法又称反馈循环队列多队列策略。主要思想是将就绪进程分为两级多级,系统相应地建立两个多个就绪进程队列,优先级较高的队列一般分配较短的时间片。处理器调度先从高级就绪进程队列中选取可占有处理器的进程,当选取不到时,再从较低级的就绪进程队列中进行选取。

4、高优先权优先调度算法

       为了照顾紧迫型作业,使之在进入系统后获得优先处理,引入了最高优先权优先调度算法(first priority first,FPF)。此算法常被用于批处理系统中,作为作业调度算法,也作为多种操作系统中的进程调度算法,还可用于实时系统中。

       该算法用于作业调度时,系统将从后备队列中选择若干个优先权最高的作业装入内存。

       该算法用于进程调度时,系统把处理机分配给就绪队列优先权最高的进程,这时又可进一步把该算法分成如下两种。

       (1)非抢占式优先权调度算法

       这种方式下,系统一旦将处理机分配给就绪队列中优先权最高的进程后,该进程便一直执行下去,直至完成;或者因发生某事件使得该进程放弃处理机时,系统方可将处理机重新分配给另一优先权最高的进程。非抢占式调度算法主要用于批处理系统中,也可用于某些对实时性要求不严的实时系统中。

       (2)抢占式优先权调度算法

       这种方式下,系统同样是把处理机分配给优先权最高的进程,使之执行。但是在该进程执行期间,如果出现了另一个优先权更高的进程,调度程序就会立即停止当前进程(原优先权最高的进程)的执行,并重新将处理机分配给最新的优先权最高的进程。

       因此,在采用抢占式调度算法时,每当系统中出现一个新的就绪进程  i  时,就将其优先权 Pi 与正在执行的进程  j  的优先权 Pj 进行比较:

       ① 如果 PiPj,原进程  j  继续执行

       ② 如果 Pi > Pj,则立即停止原进程  j  的执行,并做进程切换,使进程  i  投入执行

       显然,抢占式的调度算法能更好地满足紧迫作业的要求,所以常用于对实时性要求严格的实时系统、以及对性能要求较高的批处理和分时系统中。


http://www.ppmy.cn/news/70230.html

相关文章

Mysql锁

Mysql锁 一级目录N. DML 语句和 DDL 语句区别附录 一级目录 N. DML 语句和 DDL 语句区别 DML 语句和 DDL 语句区别: DML 是数据库操作语言(Data Manipulation Language)的缩写,是指对数据库中表记录的操作,主要包括…

Linux tail cat grep 命令详解

文章目录 tail补充说明语法选项参数实例 cat概要主要用途参数选项返回值例子注意参考链接 grep补充说明选项规则表达式 grep命令常见用法grep递归搜索文件 tail 在屏幕上显示指定文件的末尾若干行 补充说明 tail命令 用于输入文件中的尾部内容。 默认在屏幕上显示指定文件的…

three.js实现拖拽生成模型场景

THREE.js 可以实现很多web 3D的效果&#xff0c;最近想实现一个拖拽生成场景的功能&#xff0c;主要用到拖拽API,draggable 的几个事件来实现&#xff0c;拖拽模型时记录模型属性&#xff0c;释放到画布时生成当前屏幕坐标对应的焦点上&#xff0c;最后生成模型。 <!DOCTYP…

计算机组成原理---第二章 习题详解版

(一&#xff09;课内习题 1. &#xff08;二&#xff09;课后练习 1.写出下列各整数的原码、反码和补码表示&#xff08;用8位二进制表示&#xff09;。其中MSB是最高位&#xff08;符号位&#xff09;&#xff0c;LSB是最低位。 &#xff08;1&#xff09;-35 &#…

(数字图像处理MATLAB+Python)第五章图像增强-第三节:基于照度反射模型的图像增强

文章目录 一&#xff1a;基于同态滤波的增强&#xff08;1&#xff09;概述&#xff08;2&#xff09;程序 二&#xff1a;Retinex理论&#xff08;1&#xff09;Retinex理论概述&#xff08;1&#xff09;SSR&#xff08;单尺度Retinex 算法&#xff09;&#xff08;2&#xf…

C语言读取DHCP数据包(pcap文件)内容

目录 设计要求 设计过程 1&#xff09;定义pcap文件头结构体&#xff0c;时间戳结构体&#xff0c;pcap数据包头结构体 2&#xff09;数据链路层结构体定义 3&#xff09;IP数据包头结构体定义 4&#xff09;UDP数据包头结构体定义 5&#xff09;DHCP数据包结构体定义 …

[数据集][目标检测]篮球数据集VOC格式7398张

数据集格式&#xff1a;Pascal VOC格式(不包含分割路径的txt文件和yolo格式的txt文件&#xff0c;仅仅包含jpg图片和对应的xml) 图片数量(jpg文件个数)&#xff1a;7398 标注数量(xml文件个数)&#xff1a;7398 标注类别数&#xff1a;1 标注类别名称:["basketball"]…

npm依赖更新无效

项目场景&#xff1a; 项目是使用ice2.0.0搭建的react项目 项目需要替换新版本的sdk,使用npm进行对应sdk的版本升级 问题描述 卸载sdk tnpm uninstall tds/sdk安装最新版本sdk tnpm i tds/sdk^0.0.16控制台依旧输出旧版本的输出 解决过程 提示&#xff1a;这里填写问题接解决…