3.3 调度算法
即资源CPU分配策略。不同系统和不同系统目标，采用不同算法。
适于作业/进程调度。
调度实质上是一个策略问题。
3.3.1 先来先服务调度算法FCFS：First Come First Serve
1．基本思想：按作业（进程）到达时间先后顺序依次使用CPU。
2．适用于作业/进程调度
3．非抢占调度方式
4．优点：实现简单
缺点：未考虑进程的优先级或紧急性，不利于短作业（进程）的运行，
利于CPU繁忙型作业，而不利于I/O繁忙型作业。
很少单独使用，常与其他算法结合使用（辅助算法）。
3.3.2 短作业（进程）优先调度算法（SJF：Shortest Job First）
1．基本思想：选择就绪（后备）队列中估计运行时间最短的进程（作业）投入运行。2．适用于作业/进程调度
3．非抢占调度方式——>最短剩余时间优先算法
或抢占调度方式
4．优点：有效缩短作业的平均周转时间，从而提高系统吞吐量。
缺点：不利于长作业和紧迫作业的运行（无法满足公平性，估计有主观性）。
总结：这咱算法容易实现，且效率比较高，但未考虑作业的利益。
3.3.3 高优先权优先调度算法（HPF：Highest Priority First）
引入：为照顾紧迫型作业优先处理。“急事急办”，“重要事先办”
1．基本思想：选择优先级最高的进程或作业投入运行。
2．适用于作业/进程调度
3．非抢占调度方式——批处理系统“等你打完我再打”
抢占调度方式——实时系统“不等你打完电话，抢过话筒就打”
4．优先级（优先权）
即优先数，是由系统或用户按某种原则指定的，一般用整数表示。
（1）静态优先权“一定终身”
是在创建进程/作业时确定的，且在整个运行期间保持不变。
优先级的确定依据：用户要求、进程/作业类型、对资源的要求
不同系统有不同的确定原则，及表求方法。
优点：简单易行，系统开销小。
缺点：不够精确，可能出现某些低优先级的进程永不能被执行。
（2）动态优先权
是在创建进程/作业时赋予的优先级，可随着进程的推进而改变。
决定/动态改变因素：等待时间、已使用处理机的时间、其他资源的使用情况等
特点：可防止低优先级的进程/作业长时间得不到调度。
3.3.4 高响应比优先调度算法（HRN：Highest Response Ratio Next）
实际上是一种动态优先权调度算法。
响应比R = 响应时间/ 要求服务时间
=（等待时间+ 运行时间）/ 运行时间
= 1 +（等待时间/ 运行时间）
1．基本思想：同时兼顾每个作业等待时间和运行时间两方面因素，选择响应比最高的作业/进程投入运行。
2．优点：利于短作业，利于长作业。缺点：系统开销大。
3.3.5 基于时间片的轮调度算法（RR）
1．基本思想：
2．时间片大小的确定：固定时间片可变时间片
系统响应时间正比
就绪进程个数反比
CPU能力
进程切换时间q 时间片t 则q/t不大于某个值
3．时间片t大小的选择影响：
太大，则——>FCFS
太小，则系统开销增大（频繁切换）
t = R / Nmax R为响应时间，Nmax允许的最大就绪数
4．抢占式调度
3.3.6 多级反馈队列调度算法（FB）
是时间片轮转算法的发展，其出发点是为照顾各种作业/进程。
1．基本思想：
（1）系统中设置有多个不同优先级的就绪队列，且每个队列具有不同的时间片，使优先级愈高的队列时间片愈小。
（2）各个队列按照FCFS调度算法，而最后一级则时间片轮转。
（3）一个新进程就绪后进入第一级队列。
（4）进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列。
（5）当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾。
（6）当第一队列空时，就去调度第二级队列，依次类推。
（7）当时间片到后却还未完成的进程，则必须放弃Array CPU，回到下一级队列。
2．示意图：96页图3-7
3．优点：有较好的性能，能满足各类型用户需要。
终端型作业用户作业小，第一队列
短批处理作业用户
长批处理作业用户不会“饥饿”
3.3.7 作业调度算法应用例子
在两道环境下有四个作业，已知它们进入系统的
时间、估计运行时间，系统采用短作业优先作业调度算法，作业被调度运行后不再退出。
当一新作业投入运行后，可按照作业运行时间长短调整作业执行的次序。
请给出这四个作业的执行时间序列，并计算出平均周转时间及带权平均周转时间
（1）两道批处理系统中最短作业优先作业算法计算结果：
（2）四个作业的执行时间序列为：
JOB1：10：00—10：05，10：40—11：05
JOB2：10：05—10：25
JOB3：10：25—10：30
JOB4：10：30—10：40
（3）分析过程：
10：00，JOB1进入，只有一作业，JOB1被调入执行。
10：05，JOB2到达，最多允许两作业同时进入，所以JOB2也被调入。
?内存中有两作业，哪一个执行？题目规定当一新作业运行后，可按作业运行时间长短调整执行次序
?即基于优先数可抢占式调度策略。优先数是根据作业估计运行时间大小来决定
由于JOB2运行时间（20分）比JOB1少（到10：05，JOB1还需25分钟），所以JOB2运行，而JOB1等待。
10：10，JOB3到达输入井，内存已有两作业，JOB3不能马上进入内存；
10：20，JOB4也不能进入内存。
10：25，JOB2运行结束，退出，内存中剩下JOB1，输入井中有两作业JOB3和JOB4，如何调度？
?作业调度算法：最短作业优先
因此JOB3进入内存。比较JOB1和JOB3运行时间，JOB3运行时间短，故JOB3运行。
同样，JOB3退出后，下一个是JOB4。
JOB4结束后，JOB1才能继续运行。
多道程序对平均周转时间的影响
作业流在多道环境下运行，
?平均周转时间、带权平均周转时间，比单道环境下都有明显改善。
?不是任意作业组合都能改善调度性能，有时甚至可能变坏。
示例：
四个各需两小时作业同时投入运行，I/O等待时间均占25%，即占CPU时间各为1.5小时
根据计算公式，CPU的空转率为0
采用简单轮转法调度，每小时各作业分别占用25%的CPU时间，算得该作业组合的平均周转时间约为6小时，而平均带权周转时间约为3
但是，若以单道程序方式运行：
平均周转时间T=（2+4+6+8）/4=5小时
平均带权周转时间W=（1+2+3+4）/4=2.5
3.3.8 作业调度与进程调度
作业能否占用处理器？什么时间能够占用处理器？——由进程调度来决定
进程的初始状态为就绪状态，进程调度选择当前可占用CPU处理进程，当它让出处理器时，进程调度就再选另一作业的进程。
作业调度与进程调度相互配合，实现作业的并行。
1．进程调度的时机
?当一个进程运行完毕，或由于某种错误而终止运行
?当一个进程在运行中处于等待状态（等待I/O）
?分时系统中时间片到
?当有一个优先级更高的进程就绪（可抢占式）
例如：新创建一个进程，一个等待进程变成就绪
?在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞/唤醒原语）2．何时切换进程
只要OS取得对CPU的控制，进程切换就可能发生，如：
?超级用户调用来自程序的显式请求(如：打开文件)，该进程通常会被阻塞
?陷阱最末一条指令导致出错，会引起进程移至退出状态
?中断外部因素影响当前指令的执行，控制被转移至IH（中断处理程序）
3．引起进程调度的原因
?正在执行的进程执行完毕或因发生某事件而不能再继续执行；
?执行中的进程因提出I/O请求而暂停执行；
?在进程通信或同步过程中执行了某种原语操作如P操作、阻塞、挂起原语等；
?在可剥夺式调度中，有比当前进程优先权更高的进程进入就绪队列；
?在时间片轮转法中，时间片完。
?通常系统是按先来先服务或优先权形式来组织调度队列。
4．作业调度与进程调度的例子
某系统采用不能移动已在内存中作业的可变分区方案管理内存，供用户使用的内存空间为100K，系统配有4台磁带机，一批作业如下图：
调度所共花的时间，请分别给出采用“先来先服务调度算法”和“短作业优先算法”选中作业执行的次序以及它们的平均周转时间。
若允许移动已在主存储器中的作业，则作业被选中的次序又是怎样的呢？它们的平均周转时间又如何？
课程设计报告 设计名称：模拟实现一种处理机调度算法 学生姓名： 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 .以上说法均不正确处理机调度算法实验报告
操作系统原理-第四章处理机调度习题
计算机操作系统-处理机调度实验报告
处理机调度算法详解
计算机操作系统课程设计源代码《处理机调度算法的实现源代码》
第三章 处理机调度与死锁习题及答案 新
处理机调度算法的实现
第三章处理机调度与死锁习题及答案新
相关主题
文本预览