操作系统自学 系统调度算法(了解)

2024-06-15 12:48

本文主要是介绍操作系统自学 系统调度算法(了解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

各系统中的调度算法

一、批处理系统中的调度

1、先来先服务调度

在所有算法中,最简单的是非抢占式的“先来先服务”算法,进程按照他们请求CPU的顺序使用CPU

这个算法的主要有点是易于理解并且便于使用,对于排队的进程而言也是公平的,在这个算法中,一个单链表记录了所有的就绪进程,十分易于实现

但是这个算法有一个明显的缺点,很有可能让CPU密集型进程或者IO密集型进程集中执行,这样,资源利用率会大幅下降,且短进程常常需要消耗大量的时间等待长进程的完成


2、最短作业优先

这个算法适用于运行时间可以预知的进程调度,例如,保险公司因为每天都做类似的工作,所以人们可以相当精确的预测处理1000个索赔的一批作业需要多少时间,由于最短作业优先运行,后续进程的等待时间就会是最短的,平均周转时间就会是最低的

但是,对于并非所有作业都是同时运行的情况,这个调度算法是不适用的,因为最短的作业可能还没有到达


3、最短剩余时间优先

对于并非所有作业都同时运行的情况,如果新到达的作业的运行时间低于当前运行程序的剩余时间,那么就先挂起当前进程,而运行该新进程

这个算法可以使得新的短进程得到良好的服务

与最短作业优先算法一样,只适用于运行时间可以提前掌握的情况


二、交互式系统中的调度

1、轮转调度

最古老、最简单、最公平并且使用最广泛的算法就是“轮转调度”算法

每个进程被分配一个时间段,称为“时间片”,即允许该进程在该时间段内运行,如果在时间片结束时,该进程仍在运行,将剥夺CPU分配给另一个就绪的进程,如果进程提前结束,那么调度程序会立即调度新的就绪进程

时间片轮转很容易实现,只要维护一张可运行进程列表,当一个进程用完他的时间片后,将其移到队列末尾即可,如图所示:

从一个进程切换到另一个进程需要处理很多事务:保存和装入寄存器值以及内存映像、更新各种表哥和列表、清除和重新调入内存高速缓存等,一般称为“进程切换”,有时也称为“上下文切换”,切换往往会耗费大量的CPU时间

因此,如果设置的时间片太短,会导致过多的进程切换降低CPU效率,而设置过长的时间片有会引起端的交互请求响应时间变长(极端的例子就是从抢占式调度算法变成了非抢占式调度算法),一般来说将时间片设置为20 - 50ms是比较合理的


2、优先级调度

轮转调度的隐含假设是:所有的进程同等重要

而事实上,进程常常是由优先级的,这就导致了优先级调度:每个进程都被赋予一个优先级,允许优先级最高的可运行进程先运行,例如在PC机上,交互式进程常常比后台进程要重要,因此被赋予更高的优先级

为了防止高优先级的进程无休止的执行下去,调度进程可以在每个时钟滴答降低当前进程的优先级,如果这个动作导致当前进程优先级低于某个进程,那么就进行进程切换

在UNIX中,有一条命令nice,可以允许用户自愿降低自己进程的优先级,但从未有人用过它

为达到某种目的,优先级可以由系统动态确定也是允许的

如果不偶尔对优先级进行调整,则的优先级进程很可能会产生饥饿现象


3、多级队列

由于设置常时间片比频繁进行进程切换要高效的多,但是长时间片又会影响到系统的响应时间,所以,分级赋予不同长度的时间片就是一个好的方法,如对于最高优先级的进程运行1个时间片,对于次高优先级的进程运行2个时间片,以此类推,每当一个进程用完分配的时间片后,他就被移到下一类

这样,随着进程优先级的不断降低,他的获得时间片数量增长的同时运行频度则会逐渐放慢,从而为短的交互进程让出CPU

对于那些刚开始运行很长一段时间后才开始进行交互的进程,如终端,为了防止其永远处于被惩罚状态,可以才去下面的策略:

只要终端上有回车键按下,则这个终端的所有进程就都被移动到最高优先级,这样做的原因是假设此时进程即将需要交互。但是盲目的使用这种方案可能会使得某些用户为了提高优先级而刻意使用回车,这当然是不希望看到的,而同时,后台进程也有可能永远都得不到运行

这样做常常可以讨好交互用户和进程,但却牺牲了后台进程


4、最短进程有限

交互式进程通常遵循下列模式:等待命令、执行命令、等待命令、执行命令 。。。不断反复

我们也可以把每个命令的执行看作是一个作业,通过优先运行最短作业来使得响应时间最短,这里的关键问题就是系统如何预测一个进程的期望运行时间

一个很有效的方法是根据进程过去的行为推测,有一种老化算法:

如最早的一次程序执行时间为T0,之后的一次执行时间为T1,再之后的一次为T2。。。,那么,就可以得到如下队列:

          T0,T0/2+T1/2,T0/4+T1/4+T2/2,T0/8+T1/8+T2/4+T3/2,。。。

这样,先前的估计量的权值会越来越小,这种技术就被称为“老化”


5、保证调度

一种完全不同的调度算法是向用户作出明确的性能保证,然后去实现它

一种很实际并很容易实现的保证是:若用户工作时有n个用户登录,则用户将获得CPU处理能力的1/n,类似的,在一个有n个进程运行的单用户系统中,每个进程都获得1/n的CPU时间

这样看起来足够公平


6、彩票调度

保证调度很难实现,有另一个类似但是十分容易实现的调度算法就是“彩票调度”

彩票调度的基本思想是向进程提供各种系统资源(如CPU时间)的彩票,一旦需要作出一项调度决策时,就随机抽出一张彩票,拥有该彩票的进程获得该资源,比如系统可以掌握每秒50次的一种彩票,作为奖励,每个获奖者可以获得20ms的CPU时间

彩票调度是比较公平的,并且是反应迅速的,因为拥有较大份额彩票的进程会有更大的机会获得资源

对于阻塞程序,它可以把彩票还给系统,之后在阻塞结束后,系统再把彩票还给他,他就可以继续运行了

彩票调度可以用来解决其他方法很难解决的问题,比如一个视频服务器,在该服务器上若干进程正在向其用户提供视频流,每个视频流帧率都不同,假设他们分别是10、20和25帧/秒,如果给这些进程分别分配10、20和25张彩票,他们会自动地按照大致正确的比例划分CPU使用


7、公平分享制度

到目前为止的所有调度方法都有一个共同的缺陷,那就是并不关注进程的所有者,比如用户1启动了9个进程,用户2只启动了1个进程,那么用户1将获得90%的CPU

为了避免这个情况,某些系统在调度处理之前考虑谁拥有进程这一因素,每个用户分配到CPU时间的一部分,而调度程序以一种强制的方式选择进程


三、实时系统中的调度

实时系统是一种时间起着主导作用的系统

典型的,外部的一种或多种物理设备给了计算机一个刺激,而计算机必须在一个确定的时间范围内恰当的反应

比如CD播放器必须在非常短的时间内将驱动器中的位流转换为音乐,否则音乐听起来就会有异常


实时系统通常可以分为“硬实时”和“软实时”

硬实时指必须满足绝对的截止时间,而后者可以允许偶尔的错失截止时间

在这两种情形中,实时系统都是通过将程序划分为一组进程而实现的,其中每个进程的行为是可预测和提前预知的,这些进程一般寿命很短,并且极快的完成

实时系统的事件按照响应方式进一步分类为周期性事件和非周期性时间,一个系统可能要响应多个周期性事件流

实时系统的调度算法可以是静态的或者动态的,前者在系统开始运行前作出调度决策,后者在运行过程中进行调度决策,只有 在可以提前掌握所完成的工作以及必须满足截止时间等全部信息时,静态调度算法才能工作




下面代码转载自新浪微博。

操作系统系统调度算

这篇关于操作系统自学 系统调度算法(了解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1063495

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

关于数据埋点,你需要了解这些基本知识

产品汪每天都在和数据打交道,你知道数据来自哪里吗? 移动app端内的用户行为数据大多来自埋点,了解一些埋点知识,能和数据分析师、技术侃大山,参与到前期的数据采集,更重要是让最终的埋点数据能为我所用,否则可怜巴巴等上几个月是常有的事。   埋点类型 根据埋点方式,可以区分为: 手动埋点半自动埋点全自动埋点 秉承“任何事物都有两面性”的道理:自动程度高的,能解决通用统计,便于统一化管理,但个性化定

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯: