处理机调度算法的比较
计算机科学学院计算机科学与技术2009
摘要:处理机调度基本概念、调度算法优劣的评价准则、多种处理机调度算法的介绍
引言
操作系统是处理计算机硬件的一层软件和作为计算机用户与计算机硬件的中间的协调者。操作系统的CPU调度器负责给各个任务分发CPU带宽资源。调度算法负责管理当前执行任务等额顺序和性能
3 内容:
3.1 处理机调度的基本概念
高/中/低级调度
1. 高级调度(作业调度)
决定把外存上处于后备队列中的哪些作业调入内存,并为它们创建进程、分配必要的资源,准备执行。2. 低级调度(进程调度)
决定就绪队列中的哪个进程应获得处理机,然后再由分派程序执行把处理机分配给该进程的具体操作。
非抢占方式和抢占方式
3. 中级调度
决定把又具备运行条件的挂起进程重新调入内存,挂到就绪队列上,准备执行。
3.2 调度算法优劣的评价准则
衡量和比较调度算法性能优劣主要有一下几个因素:
(1)CPU利用率。CPU是计算机系统中最重要的资源,所以应尽可能使CPU保持忙,使这一资源利用率最高。
(2)吞吐量。CPU运行时表示系统正处于工作状态,工作量的大小是以每单位时间所完成的作业数目来描述的,这就叫吞吐量。
(3)周转时间。指从作业提交到作业完成所经过的时间,包括作业等待,在就绪队列中排队,在处理机上运行以及进行输入/输出操作所花时间的总和。
(4)等待时间。处理机调度算法实际上并不影响作业执行或输入/输出操作的时间,只影响作业在就绪队列中等待所花的时间。因此,衡量一个调度算法优劣常常简单的考察等待时间。
(5)响应时间。指从作业提交到系统作出相应所经过的时间。在交互式系统中,作业的周转时间并不一定是最好的衡量准则,因此,常常使用另一种度量准则,即相应时间。从用户观点看,响应时间应该快一点好,但这常常要牺牲系统资源利用率为代价。
(6)公平性——确保每个用户每个进程获得合理的 CPU 份额或其他资源份额,不会出现饿死情况。
当然,这些目标本身就存在着矛盾之处,操作系统在设计时必须根据其类型的不
同进行权衡,以达到较好的效果。下面着重看一下批处理系统的调度性能指标。
批处理系统的调度性能主要用作业周转时间和作业带权周转时间来衡量,此时间
越短,则系统效率越高,作业吞吐能率越强。如果作业i 提交给系统的时刻是ts,完成
时刻是tf,那么,作业的周转时间ti 为:
ti =tf - ts
实际上,它是作业在系统里的等待时间与运行时间之和。从操作系统来说,为了
提高系统的性能,要让若干个用户的平均作业周转时间和平均带权作业周转时间最小。
平均作业周转时间 T = (Σti) / n
如果作业i 的周转时间为ti,所需运行时间为tk,则称wi=ti /tk 为该作业的带权周
转时间。因为,ti 是等待时间与运行时间之和,故带权周转时间总大于1。
平均作业带权周转时间W = (Σwi) / n
通常,用平均作业周转时间来衡量对同一作业流施行不同作业调度算法时,它们
呈现的调度性能;用平均作业带权周转时间来衡量对不同作业流施行同一作业调度算
法时,它们呈现的调度性能。这两个数值均越小越好。
3.3几种处理机调度算法详细介绍
3.3.1作业调度
1、先来先服务算法
先来先服务FCFS(First Come,First Served)算法是按照作业进入系统的作业
后备队列的先后次序来挑选作业,先进入系统的作业优先被挑选。这是一种非剥夺式
算法,容易实现,但效率不高,只顾及到作业等候时间,而没考虑作业要求服务时间
的长短。显然这不利于短作业而优待了长作业,或者说有利于CPU 繁忙型作业而不利于I/O 繁忙型作业。有时为了等待长作业的执行,而使短作业的周转时间变得很大。
从而,平均周转时间也变大。
2、最短作业优先算法
最短作业优先SJF(Shortest Job First )算法是以进入系统的作业所要求的CPU
时间长短为标准,总是选取估计计算时间最短的作业投入运行。这是一种非剥夺式调
度算法,它克服了FCFS 偏爱长作业的缺点,易于实现,但效率也不高。它的主要弱点:一是需要预先知道作业所需的CPU 时间,这个估计值很难精确,如果程序员估计过低,系统就可能提前终止该作业;二是忽视了作业等待时间,由于系统不断地接受
新作业,而作业调度又总是选择计算时间短的作业投入运行,因此,使进入系统时间
早但计算时间长的作业等待时间过长,会出现饥饿现象;三是尽管减少了对长作业的
偏爱,但由于缺少剥夺机制,对分时、实时处理仍然很不理想。
3、响应比最高者优先(HRRF)算法
先来先服务算法与最短作业优先算法都是比较片面的调度算法。先来先服务算法
只考虑作业的等候时间而忽视了作业的计算时间,而最短作业优先算法恰好与之相反,它只考虑用户估计的作业计算时间而忽视了作业的等待时间。响应比最高者优先算法(Highest Response Ratio First)是介乎这两种算法之间的一种折衷的策略,既考虑作
业等待时间,又考虑作业的运行时间,这样既照顾了短作业又不使长作业的等待时间
过长,改进了调度性能。缺点是每次计算各道作业的响应比会有一定的时间开销,需
要估计期待的服务时间,性能要比SJF 略差。这里把作业进入系统后的等待时间与估
计计算时间之和称为作业的响应时间,作业的响应时间除以作业估计计算时间称作响
应比,现定义:
响应比=作业响应时间/作业估计计算时间=1+作业等待时间/作业估计计算时间
每当调度一个作业运行时,都要计算后备作业队列中每个作业的响应比,选择响
应比最高者投入运行。显然,计算时间短的作业容易得到较高的响应比,因为,这时
分母较小,使得HRRF 较高,因此,本算法是优待短作业的。但是,如果一个长作业在系统中等待的时间足够长后,由于,它的年龄较大使得分子足够大,则HRRF 较大,那么,它也将获得足够高的响应比,从而,可以被选中执行,不至于长时间地等待下去,饥饿的现象不会发生。
4、优先数法
这种算法是根据确定的优先数来选取作业,每次总是选择优先数高的作业。规定
用户作业优先数的方法是多种多样的。一种是由用户自己提出作业的优先数,称作外
部优先数法。有的用户为了自己的作业尽快的被系统选中就设法提高自己作业的优先数,这时系统可以规定优先数越高则需付出的计算机使用费就越多,以作限制。另一种是由系统综合考虑有关因素来确定用户作业的优先数,称作内部优先数法。
5、分类调度算法
分类调度算法预先按一定的原则把作业划分成若干类,以达到均衡使用操作系统
资源和兼顾大小作业的目的。分类原则包括:作业计算时间、对内存的需求、对外围设备的需求等。作业调度时还可以为每类作业设置优先级,从而,照顾到同类作业中的轻重缓急。
6、用磁带与不用磁带的作业搭配
这种算法将需要使用磁带机的作业分开来。在作业调度时,把使用磁带机的作业
和不使用磁带机的作业搭配挑选。在不使用磁带机的作业执行时,可预先通知操作员将下一批作业要用的磁带预先装上,这样可使要用磁带机的作业在执行时省去等待装磁带的时间。显然,这对缩短系统的平均周转时间是有益的。
3.3.2 低级调度
1、先来先服务算法
先来先服务算法是按照进程进入就绪队列的先后次序来分配处理器。先进入就绪
队列的进程优先被挑选,运行进程一旦占有处理器将一直运行下去直到运行结束或被阻塞,这是一种非剥夺式调度。这种算法容易实现,但效率不高,显然,不利于I/O 频繁的进程。
2、时间片轮转调度
轮转法调度也称之为时间片调度,具体做法是调度程序每次把CPU 分配给就绪队
列首进程使用一个时间片,例如100ms,就绪队列中的每个进程轮流地运行一个这样的时间片。当这个时间片结束时,就强迫一个进程让出处理器,让它排列到就绪队列的尾部,等候下一轮调度。实现这种调度要使用一个间隔时钟。当一个进程开始运行时,就将时间片的值置入间隔时钟内,当发生间隔时钟中断时,就表明该进程连续运行的时间已超过一个规定的时间片。此时,中断处理程序就通知处理器调度进行处理器的切换工作。这种调度策略可以防止那些很少使用外围设备的进程过长的占用处理器,导致要使用外围设备的那些进程没有机会去启动外围设备。
最常用的轮转法是基本轮转法。它要求每个进程轮流地运行相同的一个时间片。
在分时系统中,这是一种较简单又有效的调度策略。—个分时系统有许多终端设备,终端用户在各自的终端设备上同时使用计算机,如果某个终端用户的程序长时间的占用处理器,势必使其他终端用户的要求不能得到及时响应。一般说分时系统的终端用户提出要求后到计算机响应给出回答的时间只能是几秒钟,这样才能使终端用户感到满意。采用基本轮转的调度策略可以使系统及时响应。例如,一个分时系统有10 个终端,如果每个终端用户进程的时间片为100ms,那么,粗略地说,每个终端用户在每秒钟内可以得到大约100ms 的处理器时间,如果对于终端用户的每个要求,处理器花费300ms 的时间就可以给出回答时,那么,终端响应的时间大致就在3 秒左右,这样可算得上及时响应了。
基本轮转法的策略可以略加修改。例如,对于不同的进程给以不同的时间片;时
间片的长短可以动态地修改等等,这些做法主要是为了进一步提高效率。
轮转法调度是一种剥夺式调度,系统耗费在进程切换上的开销比较大,这个开销
与时间片的大小很有关系。如果时间片取值太小,以致于大多数进程都不可能在一个时间片内运行完毕,切换就会频繁,系统开销显著增大,所以,从系统效率来看,时间片取大一点好。另一方面,时间片长度较大,那么,随着就绪队列里进程数目的增
加,轮转一次的总时间增大,亦即对每个进程的响应速度放慢了,甚至时间片大到让每个进程足以完成其所有任务,这一算法便退化成先来先服务算法。为了满足用户对响应时间的要求,要么限制就绪队列中的进程数量,要么采用动态时间片法,根据当前负载状况,及时调整时间片的大小。所以,时间片大小的确定要从进程个数、切换开销、系统效率和响应时间等多方面考虑。
3、优先数调度
给每一个进程确定一个优先数,处理器调度每次选择就绪进程中优先数最大者,
让它占用处理器运行称优先数调度。怎样确定优先数呢?可以有以下几种考虑,使用外围设备频繁者优先数大,这样有利于提高效率;重要算题进程的优先数大,这样有利于用户更早得到计算结果;进入计算机时间长的进程优先数大,这样有利于缩短作业的周转时间;交互式用户的进程优先数大,这样有利于终端用户的响应时间等等,以上采用了静态优先数法。效率高性能好的低级调度可采用动态优先数法,在创建一个进程时,根括进程类型和资源使用情况确定一个优先数,而当进程耗尽时间片或重新被调度时,再次计算并调整所有进程的优先数。基本原则是:①根据进程占有CPU 时间多少来决定,当一个进程占有CPU 时间愈长,那么,在它被阻塞之后再次获得调度的优先数就越低,反之,进程获得调度的可能性越大;②根据进程等待CPU 时间多少来决定,一个进程在队列中等待CPU 的时间愈长,那么,在它再次获得调度时的优先数就越高,反之,进程获得调度的可能性越小。基于优先数的低级调度算法可以按调度方式不同分为剥夺式和非剥夺式优先数调度算法。
4、多级反馈队列调度
多级反馈队列调度这种方法又称反馈循环队列或多队列策略。其主要思想是将就
绪进程或线程分为两级或多级,系统相应建立两个或多个就绪队列,较高优先级的队列一般分配给较短的时间片。处理器调度每次先从高一级的就绪进程队列中选取可占有处理器的进程,同一队列中按先来先服务原则排队,只有在选不到时,才从较低一级的就绪进程队列中选取。
5、保证调度算法
一种完全不同的调度算法是向用户做出明确的性能保证,然后去实现它,称保证
调度算法。一种很实际并很容易实现的保证是:当你工作时己有n 个用户登录在系统,则你将获得CPU 处理能力的1/n。类似地,如果在一个有n 个进程运行的用户系统中,每个进程将获得CPU 处理能力的1/n。
为了实现所作的保证,系统必须跟踪各个进程自创建以来已经使用了多少CPU 时
间。然后,计算各个进程应获得的CPU 时间,即自创建以来的时间除以n。由于各个进程实际获得的CPU 时间已知,所以,很容易计算出实际获得的CPU 时间和应获得的CPU 时间之比,于是调度将转向比率最低的进程。
6、彩票调度算法
尽管向用户做出承诺并履行它是一个好主意,但实现却很困难。不过有另一种可
以给出类似的可预见结果,而且实现起来简单许多,这种算法称为彩票调度算法。
3.3.3实时调度
1)单比率调度算法
单比率调度事先为每个进程分配一个与事件发生频率成正比的优先数,运行频率
越高的进程其优先就数越高。例如,周期为20ms 的进程优先数为50,周期为100ms
的进程优先数为10,运行时调度程序总是调度优先数最高的就绪进程,并采取抢占式
分配策略。可以证明该算法是最优的。
2)限期调度算法
限期调度的基本思想是:当一个事件发生时,对应的进程就被加入就绪进程队列。
该就绪队列按照截止期限排序,对于一个周期性事件,其截止期限即为事件下一次发
生的时间。该调度算法首先运行队首进程,即截止时间最近的那个进程。
3)最少裕度法
最少裕度法的基本思想是:首先计算各个进程的富裕时间,即裕度(laxity),然
后选择裕度最少的进程执行。计算公式为:裕度=截止时间-(就绪时间+计算时间) ,裕度
小说明很紧迫了,就绪后让它尽快运行。
3.3.4 多处理系统调度
1)负载共享调度算法
2)群调度算法
3)处理器专派调度算法
4)动态调度算法
结语:综上所述,本文简单的介绍了处理机调度基本概念、调度算法优劣的评价准则、多种处理机调度算法的介绍。本文重点讲述了作业调度和低级调度并作出分析。
参考文献:
【1】孙钟秀主编费翔林骆斌谢立参编操作系统教程.北京:高等教育出版社,2003
课程设计报告 设计名称:模拟实现一种处理机调度算法 学生姓名: xxx 专业:计算机科学与技术 班别: xxxxxxxx 学号: xxxxxx 指导老师: xxxxx 日期: 2014 年 6 月 20 日
初始条件: 1.预备内容:阅读操作系统的处理机管理章节内容,对进程调度的功能以及进程调度算法有深入的理解。 2.实践准备:掌握一种计算机高级语言的使用。 要求完成的主要任务:(包括课程设计工作量及其技术要求,以及说明书撰写等具体要求) 1.模拟进程调度,能够处理以下的情形: ⑴能够选择不同的调度算法(要求中给出的调度算法); ⑵能够输入进程的基本信息,如进程名、优先级、到达 时间和运行时间等; ⑶根据选择的调度算法显示进程调度队列; ⑷根据选择的调度算法计算平均周转时间和平均带权周 转时间。 2.设计报告内容应说明: ⑴需求分析; ⑵功能设计(数据结构及模块说明); ⑶开发平台及源程序的主要部分; ⑷测试用例,运行结果与运行情况分析; ⑸自我评价与总结: i)你认为你完成的设计哪些地方做得比较好或比较出 色; ii)什么地方做得不太好,以后如何改正;
iii)从本设计得到的收获(在编写,调试,执行过程中 的经验和教训); iv)完成本题是否有其他方法(如果有,简要说明该方 法); 进程调度模拟设计——先来先服务、优先级法1、背景: 当计算机系统是多道程序设计系统时,通常会有多个进程或线程同时竞争CPU。只要有两个或更多的进程处于就绪状态,这种情形就会发生。如果只有一个CPU可用,那么就必须选择下一个要运行的进程。在操作系统中,完成选择工作的这一部分称为调度程序,该程序使用的算法成为调度算法。 进程调度的核心问题是采用什么样的算法把处理机分配给进程,好的算法将提高资源利用率,减少处理机的空闲时间,避免有些作业长期得不到相应的情况发生等,从而设计出受欢迎的操作系统。较常见的几种进程调度算法有:先来先服务调度算法;短作业优先调度算法;时间片轮转调度算法;优先级调度算法;高响应比优先算法和多级反馈队列调度算法等。 2.1设计目的 无论是在批处理系统还是分时系统中,用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外,系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略,动态地把处理机
处理器调度 选择题 当CPU执行操作系统代码时,则处理机处于( )。 A.执行态 B.目态 C.管态 D.就绪态 ( )是机器指令的扩充,是硬件的首次延伸,是加在硬件上的第一层软件。 A.系统调用 B.操作系统 C.内核 D.特权指令 操作系统提供给程序员的接口是( )。 A.进程 B.系统调用 C.库函数 D.B和C 用户程序向系统提出使用外设的请求方式是( )。 A.作业申请 B.原语 C.系统调用 D.I/O指令 当作业正常完成进入完成状态时,操作系统( )。 A.将输出该作业的结果并删除内存中的作业 B.将收回该作业的所占资源并输出结果 C.将收回该作业的所占资源及输出结果,并删除该作业 D.将收回该作业的所占资源及输出结果,并将它的控制块从当前的队列中删除 下列选项是关于作业和进程关系的描述,其中哪一个是不正确的( )。 A.作业的概念主要用在批处理系统中,而进程的概念则用在几乎所有的OS中。 B.作业是比进程低一级的概念。 C.一个作业至少由一个进程组成。 D.作业是用户向计算机提交任务的实体,而进程是完成用户任务的执行实体以及向系统申请分配资源的基本单位。 作业从后备作业到被调度程序选中的时间称为( )。 周转时间B.响应时间C.等待调度时间D.运行时间 设有三个作业J1,J2,J3,它们同时到达,运行时间分别为T1,T2,T3,且T1≤T2≤T3,若它们在一台处理机上按单道运行,采用短作业优先算法,则平均周转时间为( )。 A.T1+T2+T3 B.1/3(T1+T2+T3) C.T1+2/3T2+1/3T3 D.T1+1/3T2+2/3T3 从作业提交给系统到作业完成的时间间隔称为作业的( )。 A.中断时间 B.等待时间 C.周转时间 D.响应时间 设有四个作业同时到达,每个作业执行时间均为2 h,它们在一台处理机上按单道方式运行,则平均周转时间为( )。 A.1 h B.5 h C.2.5 h D.8 h FCFS调度算法有利于( )。 A.长作业和CPU繁忙型作业 B.长作业和I/O繁忙型作业 C.短作业和CPU繁忙型作业 D.短作业和I/O繁忙型作业 下列哪种说法不是SJ(P)F调度算法的缺点( )。 A.对于长作业(进程)不利 B.未考虑作业(进程)的紧迫程度 C.不能有效降低作业(进程)的平均等待时间 D.由于根据的是用户提供的估计执行时间,因此不一定真正做到短而优先。 选择排队进程中等待时间最长的进程被优先调度,该调度算法是( )。 A.先来先服务调度算法B.短进程优先调度算法 C.优先权调度算法D.高响应比优先调度算法 在采用动态优先权的优先权调度算法中,如果所有进程都具有相同优先权初值,则此时的优先权调度算法实际上和( )相同。
实验报告 学院(系)名称:计算机与通信工程学院 姓名学号专业计算机科学与技术班级2009级3班实验项目实验一:处理机调度算法的实现 课程名称操作系统课程代码0668036 实验时间2011 年11月17日第3、4节 2011 年11月21日第7、8节 2011 年11月24日第3、4节 实验地点软件实验室7-216 批改意见成绩 教师签字: 实验内容: 1.设定系统中有五个进程,每一个进程用一个进程控制块表示。 2.输入每个进程的“优先数”和“要求运行时间”。 3.为了调度方便,将五个进程按给定的优先数从大到小连成就绪队列。用一单元指出队列首进程,用指针指出队列的连接情况。 4.处理机调度总是选队首进程运行。采用动态优先数算法,进程每运行一次优先数就减“1”,同时将运行时间减“1”。 5.若某进程运行时间为零,则将其状态置为“结束”,且退出队列。 6.运行所设计程序,显示或打印逐次被选中进程的进程名,以及进程控制块的动态变化过程。 实验要求: 1.详细描述实验设计思想、程序结构及各模块设计思路; 2.详细描述程序所用数据结构及算法; 3.明确给出测试用例和实验结果; 4.为增加程序可读性,在程序中进行适当注释说明; 5.认真进行实验总结,包括:设计中遇到的问题、解决方法与收获等; 6.实验报告撰写要求结构清晰、描述准确逻辑性强; 7.实验过程中,同学之间可以进行讨论互相提高,但绝对禁止抄袭。
【实验过程记录(源程序、测试用例、测试结果及心得体会等)】 程序运行代码如下: #include
一、先来先服务算法 1.程序简介 先来先服务算法按照作业进入系统后备作业队列的先后次序挑选作业,先进入系统的作业将优先被挑选进入主存,创建用户进程,分配所需资源,然后,移入就绪队列.这是一种非剥夺式调度算法,易于实现,但效率不高.只顾及作业的等候时间,未考虑作业要求服务时间的长短,不利于短作业而优待长作业,不利于I/O繁忙型作业而有利于CPU繁忙型作业.有时为了等待场作业执行结束,短作业的周转时间和带全周转时间将变得很大,从而若干作业的平均周转时间和平均带权周转时间也变得很大。 2.分析 1.先定义一个数组代表各作业运行的时间,再定义一个数组代表各作业到达系统的时间,注意到达系统的时间以第一个作业为0基础(注意:若各程序都同时到达系统,则到达系统时间都为0)。 2.输入作业数。 3.然后运用循环结构累积作业周转时间和带权周转时间。 4.最后,作业周转时间和带权周转时间分别除以作业数即可得到平均作业周转时间和平均带权周转时间。 3.详细设计 源程序如下: #include
第四章处理机调度 4.3 习题 4.3.1 选择最合适的答案 1.某系统采用了银行家算法,则下列叙述正确的是()。 A.系统处于不安全状态时一定会发生死锁 B.系统处于不安全状态时可能会发生死锁 C.系统处于安全状态时可能会发生死锁 D.系统处于安全状态时一定会发生死锁 2.银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need,下列选项正确的是()。 A.Max[i,j]=Allocation[i,j]+Need[i,j] B.Need[i,j]= Allocation[i,j]+ Max[i,j] C.Max[i,j]= Available[i,j]+Need[i,j] D.Need[i,j]= Available[i,j]+ Max[i,j] 3.下列进程调度算法中,()可能会出现进程长期得不到调度的情况。 A.非抢占式静态优先权法 B.抢占式静态优先权法 C.时间片轮转调度算法 D.非抢占式动态优先权法 4.在下列选项中,属于预防死锁的方法是()。 A.剥夺资源法 B.资源分配图简化法 C.资源随意分配 D.银行家算法 5.在下列选项中,属于检测死锁的方法是()。 A.银行家算法 B.消进程法 C.资源静态分配法 D.资源分配图简化法 6.在下列选项中,属于解除死锁的方法是()。 A.剥夺资源法 B.资源分配图简化法 C.银行家算法 D.资源静态分配法 7.为了照顾紧迫型作业,应采用()。 A.先来服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.优先权调度算法 8.在采用动态优先权的优先权调度算法中,如果所有进程都具有相同优先权初值,则
处理机调度算法的实现 处理机调度算法的实现 1.设定系统中有五个进程,每一个进程用一个进程控制块表示。 2.输入每个进程的“优先数”和“要求运行时间”, 3.为了调度方便,将五个进程按给定的优先数从大到小连成就绪队列。用一单元指出队列首进程,用指针指出队列的连接情况。 4.处理机调度总是选队首进程运行。采用动态优先数算法,进程每运行一次优先数就减“1”,同时将运行时间减“1”。 5.若要求运行时间为零,则将其状态置为“结束”,且退出队列。 6.运行所设计程序,显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。 #include
PCB * temp2; if(Q.rear==Q.front) { Q.front->next=p; Q.rear=p; } else { temp1=Q.front; temp2=temp1->next; while(temp2->priority>=p->priority && temp2->next!=NULL) { temp1=temp2; temp2=temp1->next; } if(temp2->next==NULL && temp2->priority>=p->priority) { temp2->next=p; Q.rear=p; } else { p->next=temp1->next; temp1->next=p; } } return Q; } LinkQueue input(LinkQueue Q) /* 建立进程控制块函数*/ { int i; for(i=1;i<=5;i++) { printf("\n 进程号No.%d:\n",i); k=(PCB *)malloc(sizeof(PCB)); printf("\n 输入进程名:"); scanf("%s",k->name); printf("\n 输入进程优先数:"); scanf("%d",&k->priority); printf("\n 输入进程运行时间:"); scanf("%d",&k->time); printf("\n"); k->next=NULL; Q=sort(Q,k); /* 调用sort函数*/ } return Q; } LinkQueue running(LinkQueue Q) /* 建立进程就绪函数(进程运行时间到,置就绪状态*/ { if(k->time==0) {
处理器调度习题
处理器调度 选择题 ?当CPU执行操作系统代码时,则处理机处于( )。 ?A.执行态 B.目态 C.管态 D.就绪态 ?( )是机器指令的扩充,是硬件的首次延伸,是加在硬件上的第一层软件。 ?A.系统调用 B.操作系统 C.内核 D.特权指令 ?操作系统提供给程序员的接口是( )。 ?A.进程 B.系统调用 C.库函数 D.B和C ?用户程序向系统提出使用外设的请求方式是( )。 ?A.作业申请 B.原语 C.系统调用 D.I/O指令 ?当作业正常完成进入完成状态时,操作系统( )。 ?A.将输出该作业的结果并删除内存中的作业 ?B.将收回该作业的所占资源并输出结果 ?C.将收回该作业的所占资源及输出结果,并删除该作业 ?D.将收回该作业的所占资源及输出结果,并将它的控制块从当前的队列中删除 ?下列选项是关于作业和进程关系的描述,其中哪一个是不正确的( )。 ?A.作业的概念主要用在批处理系统中,而进程的概念则用在几乎所有的OS中。 ?B.作业是比进程低一级的概念。 ?C.一个作业至少由一个进程组成。 ?D.作业是用户向计算机提交任务的实体,而进程是完成用户任务的执行实体以及向系统申请分配资源的基本单位。 ?作业从后备作业到被调度程序选中的时间称为( )。 ?周转时间B.响应时间C.等待调度时间D.运行时间 ?设有三个作业J1,J2,J3,它们同时到达,运行时间分别为T1,T2,T3,且T1≤T2≤T3,若它们在一台处理机上按单道运行,采用短作业优先算法,则平均周转时间为( )。 ?A.T1+T2+T3 B.1/3(T1+T2+T3) ?C.T1+2/3T2+1/3T3 D.T1+1/3T2+2/3T3 ?从作业提交给系统到作业完成的时间间隔称为作业的( )。 ?A.中断时间 B.等待时间 C.周转时间 D.响应时间 ?设有四个作业同时到达,每个作业执行时间均为2 h,它们在一台处理机上按单道方式运行,则平均周转时间为( )。 ?A.1 h B.5 h C.2.5 h D.8 h ?FCFS调度算法有利于( )。 ?A.长作业和CPU繁忙型作业 B.长作业和I/O繁忙型作业 ?C.短作业和CPU繁忙型作业 D.短作业和I/O繁忙型作业 ?下列哪种说法不是SJ(P)F调度算法的缺点( )。 ?A.对于长作业(进程)不利 ?B.未考虑作业(进程)的紧迫程度 ?C.不能有效降低作业(进程)的平均等待时间 ?D.由于根据的是用户提供的估计执行时间,因此不一定真正做到短而优先。 ?选择排队进程中等待时间最长的进程被优先调度,该调度算法是( )。 ?A.先来先服务调度算法B.短进程优先调度算法 ?C.优先权调度算法D.高响应比优先调度算法 ?在采用动态优先权的优先权调度算法中,如果所有进程都具有相同优先权初值,则此时的优先权调度算法实际上和( )相同。 ?A.先来先服务调度算法B.短进程优先调度算法
: 操作系统 课程设计报告 @ 学校:广州大学 学院:计算机科学与教育软件学院 班级:计算机127班 课题:处理机调度程序 任课老师:陶文正、陈文彬 姓名:黄俊鹏 { 学号:11
班内序号:27 成绩: 日期:2015年1月6日 一、设计目的 在多道程序和多任务系统中,系统内同时处于就绪状态的进程可能有若干个。也就是说能运行的进程数大于处理机个数。为了使系统中的进程能有条不紊地工作,必须选用某种调度策略,选择一进程占用处理机。要求学生设计一个模拟处理机调度算法,以巩固和加深处理机调度的概念。 二、设计要求 1)进程调度算法包括:时间片轮转法,短作业优先算法,动态优先级算法。2)可选择进程数量 3)本程序包括三种算法,用C语言实现,执行时在主界面选择算法(可用函数实现)(进程数,运行时间,优先数由随机函数产生)执行,显示结果。 三、设计思路及算法思想 1.· 2.界面菜单选项 一级菜单提供2个选项: ①自动生成进程数量 ②手动输入所需进程数量 一级菜单选择完毕后进入二级菜单: ①重新生成进程 ②时间片轮转法 《 ③短作业优先算法 ④动态优先级算法 ⑤退出程序 3.调度算法
程序所用PCB结构体 ! 需要用到的进程结构体如上图所示 1)时间片轮转法 主要是设置一个当前时间变量,curTime和时间片roundTime。 遍历进程组的时候,每运行一个进程,就把curTime += roundTime。进程已运行时间加roundTime 2)短作业优先算法 遍历进程组,找到未运行完成并且运行时间最短的进程,让它一次运行完成,如此往复,直到所有进程都运行完成为止。 3)— 4)动态优先级算法 做法跟短作业优先算法类似,此处主要是比较进程的优先数,优先级高者,先执行。直到全部执行完毕。当一个进程运行完毕后,适当增减其余进程的优先数,以达到动态调成优先级的效果。 4.程序流程图
#include
PCB *cur,*p; p=head; cur=p->next; p->next =cur->next; cur->Level--; cur->Time--; cout<<"此次执行的进程信息(执行后):进程名"; cout< 实验二处理机调度算法 (1)处理机调度的目的是什么? 为提高内存利用率和系统吞吐量。 将那些暂时不能运行的进程调至外存,当内存不紧张时,将那些具备运行条件的就绪进程重新调入内存。 合理快速的处理计算机软件硬件资源,分配处理机,用以提高处理机的利用率及改善系统性能(吞吐量,响应时间)。 (2)处理机调度的算法有哪些,各自的优缺点是什么? ①先来先服务算法:有利于长作业(进程),不利于短作业(进程); ②短作业优先调度算法:有利于短作业(短进程),不利于长作业(长进程); ③高优先权调度算法:静态缺点:可能导致低优先权进程长期得不到调度甚至饿死; 动态:优先权随进程等待时间增加或执行而变 ④高响应比优先调度算法 ⑤基于时间片轮转调度算法:时间片太小,会频繁发生中断,系统开销增大 时间片太大,响应进程慢。 ⑥多级反馈队列调度算法:具有较好的性能,能很好满足各类型用户的需求。 1.内存中作业运行的序列:A、B、D、C 2.A进入内存的时刻1,结束的时刻5 B进入内存的时刻5,结束的时刻8 D进入内存的时刻8,结束的时刻10 C进入内存的时刻10,结束的时刻15 3.平均周转时间:6 1.内存中作业运行的序列:B、C、A、D 2.B进入内存的时刻3,结束的时刻6 C进入内存的时刻6,结束的时刻11 A进入内存的时刻11,结束的时刻15 D进入内存的时刻15,结束的时刻17 3.平均周转时间:8.75 (4)画出处理机调度算法的程序流程图; (5)补全参考程序; void process(int currentTmp, int nextTmp) { int j; int s=nextTmp-currentTmp; while(memoryNum>0 && s>=memory[0].needtime){ totalTime=totalTime+memory[0].needtime; s=s-memory[0].needtime; printf("线程%c的开始时间是:%d,结束时间 是:%f\n",memory[0].id,memory[0].cputime,totalTime+1); allTime+=totalTime+1; memoryNum--; for(j = 1; j<=memoryNum; j++) memory[j-1] = memory[j]; if(waitNum>0 && s>0){ memory[memoryNum] = wait[0]; memoryNum++; waitNum--; for(j = 1; j<=waitNum; j++) wait[j-1] = wait[j]; sort(memory,memoryNum, 'P'); } } if(memoryNum>0 && s 第四章处理机调度 一. 选择最合适的答案 1.某系统采用了银行家算法,则下列叙述正确的是()。 A.系统处于不安全状态时一定会发生死锁 B.系统处于不安全状态时可能会发生死锁 C.系统处于安全状态时可能会发生死锁 D.系统处于安全状态时一定会发生死锁 2.银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need,下列选项正确的是()。 **[i,j]=Allocation[i,j]+Need[i,j] **[i,j]= Allocation[i,j]+ Max[i,j] **[i,j]= Available[i,j]+Need[i,j] **[i,j]= Available[i,j]+ Max[i,j] 3.下列进程调度算法中,()可能会出现进程长期得不到调度的情况。 A.非抢占式静态优先权法 B.抢占式静态优先权法 C.时间片轮转调度算法 D.非抢占式动态优先权法 4.在下列选项中,属于预防死锁的方法是()。 A.剥夺资源法 B.资源分配图简化法 C.资源随意分配 D.银行家算法 5.在下列选项中,属于检测死锁的方法是()。 A.银行家算法 B.消进程法 C.资源静态分配法 D.资源分配图简化法 6.在下列选项中,属于解除死锁的方法是()。 A.剥夺资源法 B.资源分配图简化法 C.银行家算法 D.资源静态分配法 7.为了照顾紧迫型作业,应采用()。 A.先来服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.优先权调度算法 8.在采用动态优先权的优先权调度算法中,如果所有进程都具有相同优先权初值,则此时的优先权调度算法实际上和()相同。 A.先来先服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.长作业优先调度算法 中南大学 实验名称:处理机调度 课程名称:计算机操作系统 学生姓名盛希玲 学号 05 学院信息科学与工程学院 专业班级电子信息工程0602 完成时间 2008年10月12日 目录 一实验内容........................... 错误!未定义书签。二实验目的........................... 错误!未定义书签。三实验题目........................... 错误!未定义书签。四基本思想........................... 错误!未定义书签。五算法分析........................... 错误!未定义书签。六流程图............................. 错误!未定义书签。七算法描述........................... 错误!未定义书签。八运行输出结果....................... 错误!未定义书签。 一实验内容 选择一个调度算法,实现处理机调度。 二实验目的 多道系统中,当就绪进程数大于处理机数时,须按照某种策略决定哪些进程优先占用处理机。本实验模拟实现处理机调度,以加深了解处理机调度的工作。 三实验题目 设计一个按优先权调度和时间片轮转算法实现处理机调度的程序。 四基本思想 先选择时间片的个数和每个时间片需要的时间,正在运行的进程每运行一秒其优先权数目加一,即其优先权减小。每个时间片运行结束后,选择进入时间片进程优先权数目最小的进程,开始下一个时间片的运行。如果有进程运行结束,则离开,再在就绪队列中选择优先权数目最小的进程进入。在运行期间,如果有新的进程来到,按优先权大小放入就绪队列中。 五算法分析 定义一个结构体,此包含了PCB的信息: struct PCB { char PID[5]; /*进程名*/ int needtime; /*要求运行的时间*/ int cputime; /*已运行时间*/ int priority; /*优先权(越小越高)*/ int starttime; /*进入就绪队列的时间*/ int overtime; /*运行完成的时间*/ int state; /*状态:1就绪2运行3完成*/ struct PCB *next; }; 子函数struct PCB *create(int num,int n)用来建立一个按优先级大小排列的就绪进程链表和一个按时间先后循序排列的将进入就绪进程的链表。 关于处理机调度算法 《操作系统》教材中,介绍了常用的作业调度算法和进程调度算法。其中先来先服务法(FCFS)和优先级法对作业调度和进程调度都适用,时间片轮转法(RR)适用于进程调度。此外,还介绍了其他调度算法,如短作业优先法、最短剩余时间优先法、多级队列法和多级反馈队列法,这4个算法不是课程的重点内容,不作为考核要求。 需要指出的是:(1)在作业调度和进程调度中同时出现的算法,如FCFS、优先级法,其使用原理是基本相同的;(2)作业调度算法和进程调度算法应严格与存储管理中的“请求淘汰换页算法”相区别,注意不要混淆。 下面,结合具体的例题,详解调度算法: 1. 先来先服务法(FCFS) 算法描述:每次调度时,从后备作业队列或就绪队列中选择一个最先进入该队列的作业或进程。 【例1】下表给出作业l,2,3的到达时间和运行时间。采用先来先服务调度算法,试问作业调度的次序和平均周转时间各为多少?(时间单位:小时,以十进制进行计算。) 分析解题关键是要根据系统采用的调度算法,弄清系统中各道作业随时间的推进情况。我们可以用一个作业执行时间图来形象地表示作业的执行情况,帮助我们理解此题。 先来先服务调度算法是按照作业到达的先后次序挑选作业,先进入的作业优先被挑选。即按照“排队买票”的办法,依次选择作业。其作业执行时间图如下: 或者简化为下图: 作业1 作业2 作业3 | | | | 时间 0 8 12 13 由于作业1,2,3是依次到来的,所以刚开始时系统中只有作业1,于是作业1被选中。在8.0时刻,作业1运行完成,这时作业2和作业3已经到达,都在系统中等待调度,按照先来先服务法的规定,每次调度最先进入就绪队列中的作业,由于作业2比作业3先到达,于是作业2被优先选中运行。待作业2运行完毕,最后运行作业3。因此,作业调度的次序 《处理机调度算法的实现》源代码 #include "stdio.h" #include printf("到达时间:%d\n",p[i].reach); p[i].service=rand()%10+1; printf("服务时间:%f\n",p[i].service); if(c=='c'){ p[i].prior=rand()%10+1; printf("优先权:%d\n",p[i].prior); }else p[i].prior=0; p[i].finish=0; p[i].turnover=p[i].service; p[i].cum_turnover=p[i].prior; sort[i]=i; alltime=alltime+p[i].service; } for(i=1;i 第三章处理机调度与死锁 一.选择题 1.下列算法中,操作系统用于作业调度的算法是。 A.先来先服务算法B.先进先出算法 C.最先适应算法D.时间片轮转算法 2.在批处理系统中,周转时间是指。 A.作业运行时间B.作业等待时间和运行时间之和 C.作业的相对等待时间D.作业被调度进入内存到运行完毕的时间3.在作业调度中,排队等待时间最长的作业被优先调度,这是指调度算法。 A.先来先服务B.短作业优先 C.响应比高优先D.优先级 4.下列算法中,用于进程调度的算法是。 A.最先适应B.最高响应比优先 C.均衡资源调度D.优先数调度 5.两个进程争夺同一个资源。 A.一定死锁B.不一定死锁 C.只要互斥就不会死锁D.以上说法都不对 6.下列各项中,不是进程调度时机的是。 A.现运行的进程正常结束或异常结束B.现运行的进程从运行态进入就绪态C.现运行的进程从运行态进入等待态D.有一进程从等待态进入就绪态 7.进程调度算法有多种,不是进程调度算法。 A.先来先服务调度算法B.最短查找时间优先调度算法 C.静态优先数调度算法D.时间片轮转调度算法 8.作业调度程序从状态的队列中选取适当的作业投入运行。 A.就绪B.提交C.等待D.后备 9.在实时操作系统中,经常采用调度算法来分配处理器。 A.先来先服务 B.时间片轮转 C.最高优先级 D.可抢占的优先级10.采用时间片轮转调度算法主要是为了。 A.多个终端都能得到系统的及时响应 B.先来先服务 C.优先权高的进程及时得到调度 D.需要CPU时间最短的进程先做 11.下面关于优先权大小的论述中,不正确的论述是。 A.计算型作业的优先权,应低于I/O型作业的优先权 B.系统进程的优先权应高于用户进程的优先权 C.资源要求多的作业,其优先权应高于资源要求少的作业 D.在动态优先权时,随着进程运行时间的增加,其优先权降低 12.产生死锁的原因是有关。 A.与多个进程竞争CPU B.与多个进程释放资源 C.仅由于并发进程的执行速度不当 D.除资源分配策略不当外,也与并发进程执行速度不当 13.有关产生死锁的叙述中,正确的是。 A.V操作可能引起死锁B.P操作不会引起死锁 C.PV操作使用得当不会引起死锁D.以上说法均不正确 14.有关死锁的论述中,是正确的。 A.“系统中仅有一个进程进入了死锁状态” 处理机调度算法的实现 程序设计思路: 自定义结构体PCB表(进程名name,进程优先数priority,进程执行时间time)以及进程就绪队列Queue_Process(data[MAXSIZE]数组存放PCB,front,rear队首队尾指针),通过每次对进程就绪队列进行进程优先数从大到小排序来确定进程执行的选择,并且是采用动态优先数调度算法(每次优先数减1,执行时间减1),每次输出进程执行情况时只需要将队首PCB调出执行,其他进程都处于动态就绪状态,等进程执行结束后重新对进程就绪队列排序。 程序中,采用结构体、队列等数据结构,其中对队列每次排序是采用冒泡排序算法实现。 源代码: #include { Q->front = Q->rear = 0; } bool IsQueueEmpty(Queue_Process Q) //队空判断函数 { return (Q.front == Q.rear) ? true:false; } bool IsQueueFull(Queue_Process Q) //队满判断函数 { return (Q.front == (Q.rear+1)%MAXSIZE) ? true:false; } void EnQueue(Queue_Process *Q,PCB x) //入队函数 { if(IsQueueFull(*Q)) // 判断队列是否为满 { cout<<"队满,入队操作失败!"< 第三章处理机调度与死锁 ?选择题 1下列算法中,操作系统用于作业调度的算法是 ________________ 。 A .先来先服务算法 B .先进先出算法 C .最先适应算法 D .时间片轮转算法 2.在批处理系统中,周转时间是指 ______________ 。 A .作业运行时间 B .作业等待时间和运行时间之和 C .作业的相对等待时间 D .作业被调度进入内存到运行完毕的时间 3?在作业调度中,排队等待时间最长的作业被优先调度,这是指 __________ 调度算法。 A .先来先服务 B .短作业优先 C .响应比高优先 D .优先级 4.下列算法中,用于进程调度的算法是 ______________ 。 A .最先适应 B .最高响应比优先 C .均衡资源调度 D .优先数调度 5?两个进程争夺同一个资源 ____________ ■ A .一定死锁 C .只要互斥就不会死锁 6?下列各项中,不是进程调度时机的是 ______________ 。 A .现运行的进程正常结束或异常结束 B .现运行的进程从运行态进入就绪态 C .现运行的进程从运行态进入等待态 D .有一进程从等待态进入就绪态 7. ____________________________ 进程调度算法有多种, 不是进程调度算法。 A .先来先服务调度算法 B .最短查找时间优先调度算法 C .静态优先数调度算法 D .时间片轮转调度算法 8. _____________________ 作业调度程序从 状态的队列中选取适当的作业投入运行。 A .就绪 B .提交 C .等待 D .后备 9?在实时操作系统中,经常采用 ___________ 调度算法来分配处理器。 A. 先来先服务 B.时间片轮转 C.最高优先级 D.可抢占的优先级 10. _________________________________________ 采用时间片轮转调度算法主要是为了 。 A .多个终端都能得到系统的及时响应 B .先来先服务 C .优先权高的进程及时得到调度 D .需要CPU 时间最短的进程先做 11. __________________________________________________ 下面关于优先权大小的论述中,不正确的论述是 ___________________________________________________________ 。 A .计算型作业的优先权,应低于 I/O 型作业的优先权 B .系统进程的优先权应高于用户进程的优先权 C .资源要求多的作业,其优先权应高于资源要求少的作业 D .在动态优先权时,随着进程运行时间的增加,其优先权降低 12. 产生死锁的原因是 有关。 A .与多个进程竞争CPU B .与多个进程释放资源 C .仅由于并发进程的执行速度不当 D .除资源分配策略不当外,也与并发进程执行速度不当 13. ______________________________________ 有关产生死锁的叙述中,正确的是 。 A . V 操作可能引起死锁 B . P 操作不会引起死锁 C . PV 操作使用得当不会引起死锁 14. ___________________________ 有关死锁的论述中, 是正确的。 B .不一定死锁 D .以上说法都不对 D .以上说法均不正确处理机调度算法实验报告
操作系统原理-第四章处理机调度习题
计算机操作系统-处理机调度实验报告
处理机调度算法详解
计算机操作系统课程设计源代码《处理机调度算法的实现源代码》
第三章 处理机调度与死锁习题及答案 新
处理机调度算法的实现
第三章处理机调度与死锁习题及答案新