我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:全民彩票 > 多级反馈 >

操作系统的进程调度方法和磁盘臂调度算法

归档日期:05-02       文本归类:多级反馈      文章编辑:爱尚语录

  先来先服务(FCFS)调度算法是一种最简单的调度算法,该算法既可用于作业调度,也可用于进程调度。当在作业调度中采用该算法时,每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业,将它们调入内存,为它们分配资源、创建进程,然后放入就绪队列。在进程调度中采用FCFS算法时,则每次调度是从就绪队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。

  短作业(进程)优先调度算法SJ(P)F,是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业,将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程,将处理机分配给它,使它立即执行并一直执行到完成,或发生某事件而被阻塞放弃处理机时再重新调度。

  为了照顾紧迫型作业,使之在进入系统后便获得优先处理,引入了最高优先权优先(FPF)调度算法。此算法常被用于批处理系统中,作为作业调度算法,也作为多种操作系统中的进程调度算法,还可用于实时系统中。当把该算法用于作业调度时,系统将从后备队列中选择若干个优先权最高的作业装入内存。当用于进程调度时,该算法是把处理机分配给就绪队列中优先权最高的进程,这时,又可进一步把该算法分成如下两种。

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

  在这种方式下,系统同样是把处理机分配给优先权最高的进程,使之执行。但在其执行期间,只要又出现了另一个其优先权更高的进程,进程调度程序就立即停止当前进程(原优先权最高的进程)的执行,重新将处理机分配给新到的优先权最高的进程。因此,在采用这种调度算法时,是每当系统中出现一个新的就绪进程i 时,就将其优先权Pi与正在执行的进程j 的优先权Pj进行比较。如果Pi≤Pj,原进程Pj便继续执行;但如果是PiPj,则立即停止Pj的执行,做进程切换,使i 进程投入执行。显然,这种抢占式的优先权调度算法能更好地满足紧迫作业的要求,故而常用于要求比较严格的实时系统中,以及对性能要求较高的批处理和分时系统中。

  在批处理系统中,短作业优先算法是一种比较好的算法,其主要的不足之处是长作业的运行得不到保证。如果我们能为每个作业引入前面所述的动态优先权,并使作业的优先级随着等待时间的增加而以速率a 提高,则长作业在等待一定的时间后,必然有机会分配到处理机。该优先权的变化规律可描述为:

  由于等待时间与服务时间之和就是系统对该作业的响应时间,故该优先权又相当于响应比RP。据此,又可表示为:

  (1) 如果作业的等待时间相同,则要求服务的时间愈短,其优先权愈高,因而该算法有利于短作业。

  (2) 当要求服务的时间相同时,作业的优先权决定于其等待时间,等待时间愈长,其优先权愈高,因而它实现的是先来先服务。

  (3) 对于长作业,作业的优先级可以随等待时间的增加而提高,当其等待时间足够长时,其优先级便可升到很高,从而也可获得处理机。简言之,该算法既照顾了短作业,又考虑了作业到达的先后次序,不会使长作业长期得不到服务。因此,该算法实现了一种较好的折衷。当然,在利用该算法时,每要进行调度之前,都须先做响应比的计算,这会增加系统开销。

  在早期的时间片轮转法中,系统将所有的就绪进程按先来先服务的原则排成一个队列,每次调度时,把CPU 分配给队首进程,并令其执行一个时间片。时间片的大小从几ms 到几百ms。当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序便据此信号来停止该进程的执行,并将它送往就绪队列的末尾;然后,再把处理机分配给就绪队列中新的队首进程,同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之,系统能在给定的时间内响应所有用户的请求。

  前面介绍的各种用作进程调度的算法都有一定的局限性。如短进程优先的调度算法,仅照顾了短进程而忽略了长进程,而且如果并未指明进程的长度,则短进程优先和基于进程长度的抢占式调度算法都将无法使用。而多级反馈队列调度算法则不必事先知道各种进程所需的执行时间,而且还可以满足各种类型进程的需要,因而它是目前被公认的一种较好的进程调度算法。在采用多级反馈队列调度算法的系统中,调度算法的实施过程如下所述。

  (1) 应设置多个就绪队列,并为各个队列赋予不同的优先级。第一个队列的优先级最高,第二个队列次之,其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同,在优先权愈高的队列中,为每个进程所规定的执行时间片就愈小。例如,第二个队列的时间片要比第一个队列的时间片长一倍,……,第i+1个队列的时间片要比第i个队列的时间片长一倍。

  (2) 当一个新进程进入内存后,首先将它放入第一队列的末尾,按FCFS原则排队等待调度。当轮到该进程执行时,如它能在该时间片内完成,便可准备撤离系统;如果它在一个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾,再同样地按FCFS原则等待调度执行;如果它在第二队列中运行一个时间片后仍未完成,再依次将它放入第三队列,……,如此下去,当一个长作业(进程)从第一队列依次降到第n队列后,在第n队列便采取按时间片轮转的方式运行。

  (3) 仅当第一队列空闲时,调度程序才调度第二队列中的进程运行;仅当第1~(i-1)队列均空时,才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时,又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列),则此时新进程将抢占正在运行进程的处理机,即由调度程序把正在运行的进程放回到第i队列的末尾,把处理机分配给新到的高优先权进程

  移臂调度算法又叫磁盘调度算法,根本目的在于有效利用磁盘,保证磁盘的快速访问。

  1) 先来先服务算法:该算法实际上不考虑访问者要求访问的物理位置,而只是考虑访问者提出访问请求的先后次序。有可能随时改变移动臂的方向。

  2) 最短寻找时间优先调度算法:从等待的访问者中挑选寻找时间最短的那个请求执行,而不管访问者的先后次序。这也有可能随时改变移动臂的方向。

  3) 电梯调度算法:从移动臂当前位置沿移动方向选择最近的那个柱面的访问者来执行,若该方向上无请求访问时,就改变臂的移动方向再选择。

  4) 单向扫描调度算法。不考虑访问者等待的先后次序,总是从0号柱面开始向里道扫描,按照各自所要访问的柱面位置的次序去选择访问者。在移动臂到达最后一个柱面后,立即快速返回到0号柱面,返回时不为任何的访问者提供服务,在返回到0号柱面后,再次进行扫描。

  例:假定某磁盘共有200个柱面,编号为0-199,如果在为访问143号柱面的请求者服务后,当前正在为访问125号柱面的请求服务,同时有若干请求者在等待服务,它们每次要访问的柱面号为

  a.分别用先来先服务算法,最短寻找时间优先算法、电梯调度算法和单各扫描算法来确定实际的服务次序。

  答:a当前柱面位置:125#,采用不同的调度算法服务满足次序如:表(1)

  先来先服务 (125)86.147.91.177.94.150.102.175.130

  最短寻找时间优先 (125)130.147.150.175.177.102.94.91.86

  电梯调度 (125),102,94,91,86,130,147,150,175,177

  想:按当前位置找出最近的那个数,当前位置指向最近数决定方向,依次排列数字,排到尽头,再按当位置和最近数的相反方面依次排列数字。

  单向扫描 (125)130.147.150.175.177.86.91.94.102

  先来先服务 39+22+34+52+31+25+23+50+5=281

  单向扫描 5+17+3+25+2+22+1+86+5+3+8=177。注意此处有个199到0的+1。

  定位到所要的磁盘位置通常需要以下三个参数:寻道时间:定位到柱面的时间旋转延迟:定位到扇区的时间传输时间:读写数据的时间其中寻道时间占据了主要地位。因此也就有了磁盘臂调度算法。磁盘IO任务是以柱面为队列...博文来自:u010900754的专栏

  背景计算机硬件性能在过去十年间的发展普遍遵循摩尔定律,通用计算机的CPU主频早已超过3GHz,内存也进入了普及DDR4的时代。然而传统硬盘虽然在存储容量上增长迅速,但是在读写性能上并无明显提升,同时S...博文来自:weixin_36145588的博客

  本次实现的是模拟在单处理器情况下的处理器调度,目的是设计一个按优先数调度算法实现处理器调度的程序。内容(1)假定系统有五个进程,每一个进程用一个进程控制块PCB来代表,进程控制块的格式为:进程名——作...博文来自:IT_xiaoye的博客

  1、先来先服务调度算法(FCFS,firstcomefirstserved) 各个进程按照先后顺序排队,然后依次被调度2、时间片轮转调度算法(RR,Round-Robin)每次没给进程的运行时间片段相...博文来自:luhaowei0066的博客

  1、进程的基本状态:(1)运行:已经获得必要的资源 占用处理机处理机正在执行该进程(2)就绪:进程等待分配CPU(3)阻塞:等待某个事件 运行——就绪:1,主要是进程占用CPU的时间过长,时间片用完...博文来自:LingLee

  进程调度属于低级调度,用来决定就绪队列中的那个进程获取处理器,然后有分派程序将执行把处理器分派给该进程的具体操作。进程调度的方式有两个非抢占式调度和抢占式调度1、非抢占方式(Non-preemptiv...博文来自:onebutterfly

  本篇收录了一些面试中经常会遇到的经典面试题以及自己面试过程中遇到的一些问题,并且都给出了我在网上收集的答案。马上就要过春节了,开年就是崭新的一年,相信很多的前端开发者会有一些跳槽的悸动,通过对本篇知识...博文来自:wdlhao的博客

  调度性能的衡量面向用户周转时间短周转时间,指作业从提交系统开始,直到作业完成为止的时间间隔。周转时间细分包括:作业在外存后备队列中的等待时间作业调入内存后创建的相应进程在就绪队列中的等待时间进程在CP...博文来自:smile4lee的博客

  进程的三种状态:1、等待态:等待某个事件的完成;2、就绪态:等待系统分配处理器以便运行3、运行态:占有处理器正在运行三种状态的转化:运行态到等待态:往往是由于等待外设,等待主存等资源分配或等待人工干预...博文来自:vqtyh的博客

  我虽是一个IT屌丝,但特别喜欢关注整个大行业的动态,干IT运维相关工作到现在也快8年了,企业对运维人员的专业能力要求确实提高了不少,现在再去面个运维工程师的职位都要求会个开发语言啥的,这在2007是不...博文来自:alex3714的专栏

  任务代码:执行情况:知识总结:冒泡排序法:也叫升序排序法,但是相比起二分法查找只能应用于有序数列,二如何将一个无序数列变的有序就可以使用冒泡排序法!!!对上面的过程进行总结:该思想体现在成续上的解法是...博文来自:Geek宝宝的努力!

  我们在编码开发的时候,就是在跟进程打交道。不过,可能由于一些高级语言的封装,我们在开发的过程可能感觉不到我们的代码对进程的创建或调用过程。当然,这也不是本文的重点。但是,操作系统却不能不理会进程。下面...博文来自:大鱼

  一、SPF算法简介SJF算法SJF(shortestjobfirst)是以进程的运行时间长度作为优先级,进程运行时间越短,优先级越高。SJF算法的缺点必须预知进程的运行时间。即使是程序员也很难准确估计...博文来自:yinjing8435的博客

  FCFS:先来先服务,也可以称为先进先出轮转:以一个周期性间隔产生时钟中断,此时当前正在运行的进程被置于就绪队列,基于FCFS选择下一个就绪进程      运行。SPN:最短进程优先,下一次选择所需处...博文来自:我的梦

  软件简介(Introduction)免费、轻量、快速的多引擎搜索工具,拥有详细的搜索分类。免费:无须注册,无任何功能限制;轻量:可执行文件的大小只有不到130KB;快速:多线程加快搜索速度,多个引擎的...博文来自:B o o M W o r k s

  Windows10操作系统于2015年7月29日正式发布,此后,win10也就成了新上市的笔记本电脑或者台式机电脑的预装操作系统!win10系统给我们带了全新的体验,当然也带来了一定的烦恼!就拿win...博文来自:happycell188的博客

  对于初学者来说,CPU是什么、什么是双核、4核、6核、8核等。下面,就以上的问题,我们做出一一解答。 故障网帮你解答:CPU是什么、做什么用、一般CPU是接在哪里的,我们先来看看CPU是什么,CPU既...博文来自:he_jian1的专栏

  高等数学积分公式大全导数公式:基本积分表:三角函数的有理式积分:曲率:更多参见:博文来自:吾尝终日而思矣,不如须臾之所学也

  先来先服务(FCFS,firstcomefirstserved)在所有调度算法中,最简单的是非抢占式的FCFS算法。算法原理:进程按照它们请求CPU的顺序使用CPU.就像你买东西去排队,谁第一个排,谁...博文来自:如风

  前言抖音短视频APP里虽然有保存视频的按钮,但这种方式保存的视频右下角有抖音的水印,并且这种方式不适用于电脑。所以,写这篇文章来分享如何下载没有水印的抖音视频到本地,此方法适用于电脑和手机,且不需要安...博文来自:Spring的博客

  使用SSM(Spring、SpringMVC和Mybatis)已经有三个多月了,项目在技术上已经没有什么难点了,基于现有的技术就可以实现想要的功能,当然肯定有很多可以改进的地方。之前没有记录SSM整合...博文来自:AndyLizh的专栏

  导演:金沙主演:迪丽热巴/邓伦/陈奕龙/王瑞子/张昊唯类型:剧情/爱情制片国家/地区:中国大陆语言:汉语普通线分钟一千零一夜yun.bai...博文来自:的博客

  前言qq坦白说的推出让许多人感到烦恼,或是被骚扰,或是被撩,完事儿被戏弄之后你还不能屏蔽。。。·...博文来自:WYJ的博客

  以下面试题为个人在面试过程中所遇到的,仅供参考!如有错误,望指出。技术交流群:365814763 1、servlet执行流程客户端发出http请求,web服务器将请求转发到servlet容器,serv...博文来自:eriz程序之路

  支持1. QQ空间短链接生成2. 支持长链接转换3. 支持提交真实QQ号(为了确保提交的数据真实,本站不得已采用QQ登录方式)4. 支持json数据解密(具体请看坦白说数据获取视频教程)工具地址:ht...博文来自:的博客

  之所以分享这篇文章,是因为它不仅适用于小米手机,几乎适合所有安卓机。原理就是,在网站下载好apk,再传到手机中安装。...博文来自:wuwao_1的地盘

  进程调度的任务和机制进程调度任务保存处理机的现场信息按某种算法选取进程把处理器分配给进程进程调度机制进程调度方式非抢占方式一旦把处理机分配给某进程,就让它一直运行下去,直至该进程完成或阻塞时,才把处理...博文来自:杨森源的博客

  最近要研究一下滤波器设计的无乘法器的实现,所以要学习一下加法器的电路,丢了一段时间,忘的差不多了,这里罗列一下常用的门电路的符号。这是一个1位全加器的数字电路组成:以下两幅图可以复习一下数字电路中的常...博文来自:邱长勇的专栏 [计算机视觉 计算机图形学 三维重建 图像理解 语音识别 音视频编解码 机器学习]

  快速排序今天看到大神写的一篇快速排序的博客,肃然起敬,觉得原来快速排序这么简单下面进行简单的试试快速排序的基本思想是1、先从数列中取出一个数作为基准数2、分区过程,将比这个数大的数全放到它的右边,小于...博文来自:code_AC的博客

  现在的搜索引擎会极大的帮助用户搜索到想要的搜索的内容,我们常用的搜索引擎包括百度、搜狗、等等,今天就为大家推荐一个超级搜索的插件。超级搜索基于浏览器的全面搜索。智能识别搜索关键字,集成收藏夹...博文来自:c1007726825的博客

  地图的绚丽是众所周知的,可是在浏览器内看到的地图却只能浏览,不能下载,那我们怎么样才能下载属于自己的能够离线浏览的地图呢,现在就给大家推荐一款超级强大的下载器,话不多说,首先来看看我们的下载成果。...博文来自:水经注地图下载标注与行业应用

  1. 线性代数知识图谱线性代数是代数学的一个分支,主要处理线性关系问题。线性关系意即数学对象之间的关系是以一次形式来表达的。例如,在解析几何里,平面上直线的方程是二元一次方程;空间平面的方程是三元一次...博文来自:MyArrow的专栏

  说到安卓手机,越来越多的功能方便了我们日常使用。如投影到高清电视的无线投屏功能、NFC功能,以及与周边设备数据交换的OTG功能。本文重点讲下OTG功能。OTG功能是onthego的简写,让手机等移动设...博文来自:关注IT、科技、数码周边

  我们的电脑硬盘分区格式一共有两种,一种是GUID(GPT),一种是MBR。怎么判断自己硬盘是哪一种:   如果你的电脑原装系统是win8或者以上的,那么他的硬盘分区表格式为GUID(GPT)格式的;如...博文来自:周士豪

  最近写了一个小程序,打算做成deb发布,折腾了两天,终于找到了一个简单的deb制作方法 1、首先要编译好程序,获得程序的可执行文件 2、新建一个文件夹,例如在用户目录下新建mydeb文件夹 3、在my...博文来自:youngyang的专栏

  最近比较有空,大四出来实习几个月了,作为实习狗的我,被叫去研究Docker了,汗汗! Docker的三大核心概念:镜像、容器、仓库 镜像:类似虚拟机的镜像、用俗话说就是安装文件。 容器:类似一个轻量...博文来自:我走小路的博客

  最大多普勒频移越大,相干时间越小,能容忍的符号时间越短,越容易产生符号间干扰,信号越容易发生快速变化,若相干时间小于符号时间,这时候的信道就属于快衰落信道(快时变);反之,则属于慢衰落信道(慢时变)...博文来自:u010237785的博客

  今日遇见一个开超市的朋友,真没想到在高校开超市一个月可以达到月净利润50K,相比起我们程序员的工资,真是不可同日而语,这个世道啊,真是做程序员不如经商开超市,我们高科技的从业者,真是造不...博文来自:尹成的技术博客

  遗传算法,核心是达尔文优胜劣汰适者生存的进化理论的思想。 我们都知道一个种群,通过长时间的繁衍,种群的基因会向着更适应环境的趋势进化,牛B个体的基因被保留,后代越来越多,适应能力低个体的基因被淘汰,...博文来自:ljp1919的专栏

  一、组合模式适用场景把部分和整体的关系用树形结构来表示,从而使客户端可以使用统一的方式对部分对象和整体对象进行管理。二、组合模式结构 抽象构件(Conponent)角色:所有类的共有接口,定义了叶子和...博文来自:小小本科生成长之路

  强连通分量: 简言之 就是找环(每条边只走一次,两两可达) 孤立的一个点也是一个连通分量   使用tarjan算法 在嵌套的多个环中优先得到最大环( 最小环就是每个孤立点)   定义: int Ti...博文来自:九野的博客

  jquery/js实现一个网页同时调用多个倒计时(最新的) 最近需要网页添加多个倒计时. 查阅网络,基本上都是千遍一律的不好用. 自己按需写了个.希望对大家有用. 有用请赞一个哦! //js ...博文来自:Websites

  前段时间看了一些关于LSTM方面的论文,一直准备记录一下学习过程的,因为其他事儿,一直拖到了现在,记忆又快模糊了。现在赶紧补上,本文的组织安排是这样的:先介绍rnn的BPTT所存在的问题,然后介绍最初...博文来自:天道酬勤,做一个务实的理想主义者

  最近用软碟通制作了一个win7原版映像,但是在装新系统的时候发现了一个问题,进入安装界面后,显示没有找到驱动器,但是明明是差了U盘的,通过“shift+f12”调出命令行窗口,输入disk list命...博文来自:g_newbie的博客

  一、场景 当需要生产一辆汽车时,我们需要为其装配发动机、轮胎、座椅等等部件,这个装配过程是比较复杂的而且也需要较高的组装技术。而建造者模式(Builder Pattern)就是为了将...博文来自:小小本科生成长之路

本文链接:http://jomsell.com/duojifankui/83.html

上一篇:搜狗搜索

下一篇:Task_struct结构体