操作系统常见的几种算法举例分析.pdf
收稿日期:2010-11-15作者简介:孙杨模(1976-),男,湖北嘉鱼人,湖北黄冈艺术学校教师、工程师,主要研究单片机、嵌入式系统。2010年 12月第 7卷?第 2期湖 北 三 峡 职 业 技 术 学 院 学 报Journal ofHuBeiThree GrogesVocational and TechnicalCollegeDec.2010Vol?7?No.2操作系统常见的几种算法举例分析孙杨模(湖北黄冈艺术学校 计算机中心,湖北 黄冈?438000)摘?要:本文通过举例分析操作系统应用中常见的几种算法,比较不同算法各自的特点,分别适合哪种场合,以期对操作系统的教学和学习起到借鉴作用。关键词:操作系统;?算法;?调度中图分类号:TP316?文献识别码:A?文章编号:2027/YC-(2010)02-0087-004?操作系统(英语:Operating System,简称 OS)是控制其他程序运行,管理系统资源并为用户提供操作界面的系统软件的集合。大致包括 5个方面的管理功能:进程与处理机管理、作业管理、存储管理、设备管理、文件管理。操作系统是高校计算机专业的主干课程,理论性强,很多学生在学习这门课程时,没有实践经验,对于其中很多概念难以理解,本文结合典型例题,分析不同算法的优缺点以及它们的不同应用,具体如下:一、作业调度算法作业调度算法常见的有 3种:1、先来先服务算法。2、计算时间短的作业优先算法。3、响应比高者优先算法。1、先来先服务(FCFS,First Come F irst Serve)是最简单的调度算法,按先后顺序进行调度。优点:算法简单,比较有利于长作业,而不利于短作业。有利于 CPU繁忙的作业,而不利于 I/O 繁忙的作业。缺点:如果先来的进程需要很长的处理时间,而后来的进程要等很长时间。2、计算时间短的作业优先算法又称为短作业优先(SJF,Shortest Job First):对预计执行时间短的作业(进程)优先分派处理机。优点:比 FCFS改善平均周转时间和平均带权周转时间,缩短作业的等待时间;提高系统的吞吐量。缺点:对长作业非常不利,可能长时间得不到执行;未能依据作业的紧迫程度来划分执行的优先级;难以准确估计作业(进程)的执行时间,从而影响调度性能。3、响应比高者优先算法(HRN,H ighest Response_ratio Next):对 FCFS方式和 SJF 方式的一种综合平衡,HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短,从中选出响应比最高的作业投入执行。缺点:由于每次调度前要计算响应比,系统开销也要相应增加。例题分析:例 1:某一多道程序设计系统,采用可移动已在主存储器中作业的可变分区方式管理主存,已知供用户使用的主存空间为 100K,系统配有 4台打印机,对打印机采用静态分配。现有一作业序列如下表所示,假设作业调度从 11时开始,请回答:(1)若作业调度采用?先来先服务调度算法 ,求每一作业的周转时间和平均周转时间。(2)若作业调度采用?计算时间最短优先调度算法 ,求选中作业执行时的先后次序和作业完成的先后次序。(注:忽略系统开销。)作业编号进输入井时间要求执行时间需打印机数要求主存量110.0时0.4时2台15K210.2时0.5时1台60K310.5时0.1时3台40K410.6时0.3时2台40K510.8时0.2时1台65K?解:(1)从题中可知作业调度从 11时开始,也就87是 5个作业都到达输入井,采用先来先服务调度算法并且是多道系统,受资源限制,开始只能作业 1、2进入,1运行结束,释放占用的资料,因为是先来先服务调度算法,3进入,当 2运行结束,4、5都必须等,因为没有资源没有满足,具体运行情况如下:作业编号进输入井时间要求执行时间结束时间周转时间110.0时0.4时11.4时1.4时210.2时0.5时11.9时1.7时310.5时0.1时12时1.5时410.6时0.3时12.3时1.7时510.8时0.2时12.5时1.7时?特别强调:周转时间=结束时间-进入输入井时间平均时间=(1.4时+1.7时+1.5时+1.7时+1.7时)/5=1.6时(2)从 11时开始,也就是 5个作业都到达输入井,采用计算时间最短优先调度算法并且是多道系统,受资源限制,开始只能作业 3进入,3运行结束,释放占用的资料,因为是计算时间最短优先调度算法,5、1进入,当 5运行结束,4进入,最后 2进入,具体运行情况如下:作业编号进输入井时间要求执行时间结束时间周转时间110.0时0.4时11.7时1.7时210.2时0.5时12.5时2.3时310.5时0.1时11.1时0.6时410.6时0.3时12时1.4时510.8时0.2时11.3时0.5时?平均时间=(1.7时+2.3时+0.6时+1.4时+0.5时)/5=1.18时例 2:有 4个作业 J1、J2、J3、J4,它们的到达时间和计算时间如下表所示。若这 4个作业在一台处理机上按单道方式运行,采用响应比高者优先调度算法,试写出各作业的执行顺序、各作业的周转时间及平均周转时间。(从作业J1到 8!00开始调度运行)作业的到达时间和计算时间作业到达时间计算时间J18!002小时J28!3040分钟J39!0025分钟J49!3030分钟?解:从题中可知作业调度从 8时开始,也就是只有作业 J1到达输入井,采用响应比高者优先调度算法并且是单道系统,开始只能作业 J1进入,J1运行结束,已经 10时,故 J2、J3、J4都已到达输入井,因为是响应比高者优先调度算法,故要计算 J2、J3、J4的响应比,响应比=等待时间/计算时间,具体运行情况如下:J2、J3、J4到 10时等待时间分别为 90分钟、60分钟、30分钟,J2=90/40=2.25J3=60/25=2.4J4=30/30=1故 J1结束,J3响应比最高,故 J3进入。当 J3结束,J2、J4等待时间分别为 115分钟、55分钟,响应比分别为:J2=115/40=2.875J4=55/30=1.833故 J3结束,J2响应比最高,故 J2进入。最后 J4进入。综上所述 J1周转时间为 10时-8时=120分钟;J3周转时间为 10:25时-9时=85分钟;J2周转时间为 11.05时-8:30时=155分钟;J4周转时间为 11.35时-9:30时=125分钟;平均周转时间=(120分钟+85分钟+155分钟+125分钟)/4=121.25分钟二、页面调度算法页面调度算法常见的主要有两种:1、先进先出调度算法(FIFO)。2、最近久未使用调度算法(LRU)。例题分析:例 3:对访问串 1、2、3、4、1、2、5、1、2、3、4、5,指出在驻留集大小为 3时,使用 FIFO和 LRU替换算法的页故障数,写出驻留集内页号的变化过程。解:(1)使用 FIFO算法FIFO算法原理:先进先出调度算法。该算法总是淘汰最先进入内存的页面,既选择在内存中驻留时间最久的页面予以淘汰。页号的变化过程如下:故共产生 6次缺页中断。(2)使用 LRU算法LRU算法原理:LRU是 Least Recently Used的缩88写,即最近最少使用页面置换算法,是为虚拟页式存储管理服务的,该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间 T,当须淘汰一个页面时,选择现有页面中其 T值最大的给予淘汰。在实际应用中,用页号队列的方法,这种方法能方便地正确选出最近最久未使用的页,队列中存放当前主存中的页,但不需要使用指针。规定队首总是最久未使用的页,而队尾是最近才被访问的页。页号的变化过程如下:故共产生 7次缺页中断三、磁盘驱动调度算法磁盘驱动调度算法包括?移臂调度 和?旋转调度 ,移臂调度是根据等待访问者欲访问的柱面位置来进行调度的。移臂调度包括:1、先来先服务算法。2、最短寻找时间优先算法。3、电梯调度算法。例题分析:例 4:假定在某动臂磁盘上,刚处理了访问 75号柱面的请求,目前正在 74号柱面上读信息,且有如下请求序列在等待访问磁盘:请求序列12345678欲访问柱面号22481931889278156101?试回答:(1)写出电梯调度算法处理时的序列次序;(2)写出最短寻找时间优先算法时处理的序列次序;(3)采用最短寻找时间优先算法处理时臂的移动方向改变了几次?解:(1)电梯调度算法原理:总是沿着臂的移动方向去选择,仅当沿臂移动方向无等待访问者时才改变臂的移动方向。有效减少移动臂来回改变方向的次数,减少移动臂移动时所花的时间。我们知道磁盘柱面号由外向内增大,最外柱面号为 0,由题知刚处理了访问 75号柱面的请求,目前正在 74号柱面上读信息,说明磁头由内向外运行,根据电梯调度算法原理,下一步应访问 48号柱面,接着访问 22号柱面,然后磁头改变方向,由外向内运行,依次访问 78、92、101、156、188、193号柱面。对应的序列次序为:2 1 6 5 8 7 4 3(2)最短寻找时间优先算法原理:不考虑臂的移动方向,总是优先选择离当前位置最近的那个柱面的访问者,这种选择可能导致移动臂来回改变移动方向。由题知磁头目前正在 74号柱面上读信息,根据最短寻找时间优先算法原理,离 74最近的柱面为 78,故下一步应访问 78号柱面,依此类推,离 78最近的柱面为 92,离 92最近的柱面为 101,离 101最近的柱面为 48,离 48最近的柱面为 22,离 22最近的柱面为156,离 156最近的柱面为 188,离 188最近的柱面为193。对应的序列次序为:6 5 8 2 1 7 4 3(3)根据题意以及(2)的分析可知,采用最短寻找时间优先算法处理时臂的移动方向改变了 3次。分别为访问 78号柱面,访问 48号柱面,访问 156号柱面。四、银行家算法银行家算法是一个非常古典的避免死锁的算法,其原理为:采用银行家算法分配资源时,测试进程对资源的最大需求量,如果系统现存的资源可能满足它的最大需求量时,就满足进程当前申请,否则就推迟分配。这样做,能保证至少有一个进程可得到需要的全部资源而执行到结束,然后归还资源供别的进程使用。例题分析:例 5:假设某系统有同类资源 10个,供 P、Q、R三进程共享。P、Q、R所需资源总数分别为 8、4、9,它们申请资源次序和数量如下:次序进程申请量1R22P43Q24P25R16Q27R58P4#?请回答以下问题:(1)若 1、2、3、4的申请均成功,则执行完次序号为 4的申请时,请填写下表,并判断此时系统是否安全。进程已占资源数最大需求数P8Q4R9剩余资源数89?(2)若系统按银行家算法分配资源时,申请不成功的序号有哪些?简述理由。解:(1)当执行完次序号为 4的申请时,已占资源数 P、Q、R分别为 6、2、2,因共有资源 10个,故剩余资源数为 0个,显然不安全,因为没有一个进程最大需求数能得到满足,造成死锁。(2)银行家算法保证剩余资源数至少满足一个进程最大需求量,显然根据题目给出的已知条件,次序4、5、7申请不成功。理由如下:若次序 4分配,则剩余资源数为 0个,没有一个进程最大需求数能得到满足;若次序 5分配,则剩余资源数为 1个,没有一个进程最大需求数能得到满足;若次序 7分配,则剩余资源数在 Q释放后只有 4个,不可能分配 5个资源。综上所述,操作系统的学习只有结合具体的应用实例,才能深刻理解,真正融会贯通,提高学习效率。参考文献:1?梁红兵.计算机操作系统%学习指导与题解 M.西安:西安电子科技大学出版社,2008.2?曾平,郑鹏,金晶.操作系统教程(第 2版)M.北京:清华大学出版社,2008.3?谭耀铬.操作系统(2007版)M.北京:中国人民大学出版社,2007.4?谭耀铭.操作系统概论 2005年版 M.北京:经济科学出版社,2005.5?谭耀铭.操作系统概论同步配套题解 M.北京:光明日报出版社,2009.6?杜和庆.操作系统概论-历年试题/冲刺模拟试卷(附串讲)M.北京:光明日报出版社,2009.责任编辑:朱玉萍 Example Analysis of SeveralCommon Algorithms in the Operating Syste mS UN Yangmo(Computer Center of Huanggang Art School,Huanggang 438000,Hubei)Abstract:The article analyzes several common algorithms in the application of operating system through some ex?amples,compares different algorithms&characteristics and their respective application on different occasions,hoping tohave a good reference for operating system teaching and learning.KeyW ords:operating system;?algorithm;?scheduling(上接第 62页)D iscussion on theW ord?Bi in The Analects of ConfuciusHUANG Ye?JI ANG X iangqiong(BasicCoursesDepart m ent,Hubei Three GorgesPolytechnic,Yichang 443002,Hubei)Abstract:In the bookTheAnalects of Confucius,theword?Bi is appeared 76 ti mes.Som eti mes it serves as anaffirmative expression adverb,the samemeaning as?certainly,and?surely;someti mes it doesn&tmean tha,t butit is a conjunction meaning?if and show s supposition relation usedw ith the adverb?jiu.If you m isunderstand theword you w ill not get the originalmeaning of the article.KeyW ords:b;i?certainly;?if90
