短作业优先调度算法例题详解
【最新版】
目录
1.短作业优先调度算法的概念和原理
2.短作业优先调度算法的例题
3.短作业优先调度算法的例题详解
正文
一、短作业优先调度算法的概念和原理
短作业优先调度算法（Shortest Job First, SJF）是一种常见的作业调度算法，其基本原理是优先执行估计运行时间最短的作业，直至完成。当有两个或两个以上的作业都等待执行时，选择估计运行时间最短的作业执行。这种算法能够使得平均等待时间最短，从而提高系统的效率。
二、短作业优先调度算法的例题
假设有一个计算机系统，其中有如下三个作业：
作业 1：运行时间为 20 分钟
作业 2：运行时间为 30 分钟
作业 3：运行时间为 10 分钟
系统按照短作业优先调度算法进行调度。
三、短作业优先调度算法的例题详解
1.作业 1、作业 2 和作业 3 都到达，系统按照短作业优先调度算法选择运行时间最短的作业 1 执行。
2.作业 1 执行完毕，作业 2 和作业 3 等待执行。
3.系统选择运行时间最短的作业 3 执行。
4.作业 3 执行完毕，作业 2 等待执行。
5.系统选择运行时间最短的作业 2 执行。
最终，三个作业的完成顺序为作业 1、作业 3、作业 2，平均等待时间为（20+10）/3=10 分钟。
通过这个例题，我们可以看到短作业优先调度算法能够使得平均等待时间最短，从而提高系统的效率。然而，这种算法也有其不足之处，即长作业可能会被频繁地中断，从而影响系统的稳定性。
短作业优先调度算法例题详解 短作业优先调度算法例题详解 什么是短作业优先调度算法？ 短作业优先调度算法是一种常见的进程调度算法，它的主要思想是优先调度执行当前剩余运行时间最短的作业。在这种算法下，长时间作业的响应时间会相对较长，但是短时间作业的响应时间会更短。算法原理 短作业优先调度算法的原理是按照作业的执行时间来进行调度，优先选择执行时间较短的作业。当一个作业到达时，操作系统会检查作业的执行时间，并将其与已有作业的执行时间进行比较，选择执行时间最短的作业进行调度。 算法实现 以下是一个简单的短作业优先调度算法的例子： 1.输入作业的数量和每个作业的执行时间。 2.按照作业的执行时间对作业进行排序，从执行时间最短的作业开 始执行。 3.执行作业直到所有作业执行完毕。
例题解析 假设有三个作业需要执行，它们的执行时间分别为5、2和8。使 用短作业优先调度算法对这些作业进行调度。 1.首先，按照作业的执行时间对作业进行排序，排序后的顺序为2、 5和8。 2.执行时间最短的作业是2，因此首先执行该作业，剩下的两个作 业的执行时间分别为5和8。 3.接下来，执行时间较短的作业是5，执行该作业后，剩下的作业 的执行时间为8。 4.最后，执行剩下的唯一一个作业，执行时间为8。 根据以上步骤，最终的作业执行顺序为2、5和8。 优缺点分析 短作业优先调度算法的优点是能够最大程度地缩短短时间作业的 响应时间，提高系统的吞吐量。然而，这种算法容易造成长时间作业 的等待时间过长，可能会导致长时间作业的执行效率较低。 总结 短作业优先调度算法是一种常见的进程调度算法，其核心原理是 选择执行时间最短的作业进行调度。通过对作业的排序和执行，可以 最大程度地减少短时间作业的响应时间。然而，这种算法也存在一些
处理机调度习题 1、现有如下作业序列： 作业提交时间运行时间 1 8.00 1.00 2 8.30 3.00 3 9.00 0.10 4 9.30 0.50 单位：小时，以十进制计 使用先来先服务和短作业优先调度算法处理该作业序列，问哪种作业调度算法性能更好？ 2、在一个4道作业的操作系统中，设在一段时间内先后到达6个作业，如下所示： 作业提交时间(时) 运行时间(分钟) JOB1 8:00 60 JOB2 8:20 35 JOB3 8:25 20 JOB4 8:30 25 JOB5 8:35 5 JOB6 8:40 10 系统采用短作业优先调度算法，作业被调入运行后不再退出，但每当一作业进入运行时，可以调整运行的优先次序。 (1)按照所选择的调度算法，请分别给出上述6个作业的执行时间序列。 (2)计算在上述调度算法下作业的平均周转时间。 3、某多道程序设计系统配有一台处理机和两台外设IO1、IO2，现有三个优先级由高到低的作业J1、J2、J3都已经进入内存，他们使用资源的先后顺序和占用时间分别是： J1: IO2/30ms, CPU/10ms, IO1/30ms, CPU/10ms J2: IO1/20ms, CPU/20ms, IO2/40ms J3: CPU/30ms, IO1/20ms 处理机调度采用可抢占的优先数算法，忽略其它辅助操作时间，回答： (1)分别计算作业J1、J2和J3从开始到完成所用的时间。 (2)3个作业全部完成时CPU的利用率。 (3)3个作业全部完成时外设IO1的利用率。 4、有5个批处理作业(A、B、C、D和E)几乎同时到达计算中心，估计运行时间分别为2、4、6、8、10分钟，优先数分别为1、2、3、4、5(1为最低优先级)。对下面每种调度算法，分别计算作业的平均周转时间。 (1)最高优先级优先 (2)时间片轮转(时间片大小2分钟) (3)FIFO(假定到达顺序为C,D,B,E,A) (4)短作业优先 5、试证明，短作业优先的作业调度算法可以得到最短的平均响应时间。 6、有5个待运行作业A,B,C,D,E，它们几乎同时到达，各自的估计运行时间分别为9,6,3,5,x。试问采用哪种运行次序使得平均周转时间最短？
课程设计 采用短作业优先调度算法调度程序 学号： 姓名： 专业： 指导老师： 日期：
目录 一、实验题目 (3) 二、课程设计的目的 (3) 三、设计内容 (3) 四、设计要求 (3) 五、主要数据结构及其说明 (4) 六、程序运行结果 (5) 七、流程图 (7) 八、源程序文件 (9) 九、实验体会 (13) 十、参考文献 (13)
摘要 在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对于批量型作业而言，通常需要经历作业调度和进程调度两个过程后方能获得处理机。作业调度是对成批进入系统的用户作业，根据作业控制块的信息，按一定的策略选取若干个作业使它们可以去获得处理器运行的一项工作。而对每个用户来说总希望自己的作业的周转时间是最小的，短作业优先（SJF）便是其中一种调度方法。本次课程设计主要是模拟短作业优先(SJF)调度算法。
一、实验题目 采用短作业优先算法的的进程调度程序 二、课程设计的目的 ●操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动 手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。 ●进一步巩固和复习操作系统的基础知识。 ●培养学生结构化程序、模块化程序设计的方法和能力。 ●提高学生调试程序的技巧和软件设计的能力。 ●提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 三、设计内容 设计并实现一个采用短作业优先算的进程调度算法演示程序 四、设计要求 1. 每一个进程有一个PCB，其内容可以根据具体情况设定。 2. 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定 3. 可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片长度、进程优先级的初始化 4. 可以在运行中显示各进程的状态：就绪、执行（由于不要求设置互斥资源与进程间同步关系，故只有两种状态） 5. 采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列
最短作业优先算法例题 最短作业优先算法（Shortest Job First，简称SJF）是一种用于调度作业的算法，根据作业的执行时间来确定优先级。具体例题如下： 假设有5个作业，它们的执行时间分别为： 作业1：5个单位时间 作业2：2个单位时间 作业3：9个单位时间 作业4：7个单位时间 作业5：3个单位时间 按照最短作业优先算法进行调度，首先选择执行时间最短的作业来执行。 1. 初始状态下，作业队列为空。 2. 比较所有作业的执行时间，找到执行时间最短的作业作为第一个执行的作业。 最短执行时间为2，因此选择执行时间为2个单位时间的作业2，并将其加入作业队列。 作业队列：作业2 3. 接下来，比较作业队列中的作业和剩下的作业的执行时间，选择执行时间最短的作业。 作业队列中只有一个作业，无需比较，因此选择剩下的作业中执行时间最短的作业。 最短执行时间为3，因此选择执行时间为3个单位时间的作业5，并将其加入作业队列。
作业队列：作业2 -> 作业5 4. 继续比较作业队列中的作业和剩下的作业的执行时间，选择执行时间最短的作业。 最短执行时间为5，因此选择执行时间为5个单位时间的作业1，并将其加入作业队列。 作业队列：作业2 -> 作业5 -> 作业1 5. 继续比较作业队列中的作业和剩下的作业的执行时间，选择执行时间最短的作业。 最短执行时间为7，因此选择执行时间为7个单位时间的作业4，并将其加入作业队列。 作业队列：作业2 -> 作业5 -> 作业1 -> 作业4 6. 最后一个作业3的执行时间为9，因此将其加入作业队列。作业队列：作业2 -> 作业5 -> 作业1 -> 作业4 -> 作业3 最终的作业队列为：作业2 -> 作业5 -> 作业1 -> 作业4 -> 作业3 按照最短作业优先算法的调度顺序，作业将按照执行时间从短到长的顺序被执行。
短作业优先调度算法例题详解(一) 短作业优先调度算法例题 简介 短作业优先调度算法（SJF）是一种常用的进程调度算法，也被称为最短作业优先调度算法。它通过选择剩余执行时间最短的作业来调 度进程，以提高系统的吞吐量和响应时间。本文将在此背景下给出一 个例题，并详细解释短作业优先调度算法的实现过程。 短作业优先调度算法的例题 假设有以下四个进程需要执行： 1.进程A，需要执行时间为5个单位时间 2.进程B，需要执行时间为3个单位时间 3.进程C，需要执行时间为8个单位时间 4.进程D，需要执行时间为1个单位时间 解题步骤 使用短作业优先调度算法调度上述四个进程，按照以下步骤进行：1.计算每个进程的执行时间，得到以下结果： –进程A，需要执行时间为5个单位时间
–进程B，需要执行时间为3个单位时间 –进程C，需要执行时间为8个单位时间 –进程D，需要执行时间为1个单位时间 2.按照执行时间的大小对进程进行排序，得到以下顺序： –进程D（执行时间为1个单位时间） –进程B（执行时间为3个单位时间） –进程A（执行时间为5个单位时间） –进程C（执行时间为8个单位时间） 3.按照排序后的顺序依次执行进程，得到以下调度结果： –进程D（执行时间为1个单位时间） –进程B（执行时间为3个单位时间） –进程A（执行时间为5个单位时间） –进程C（执行时间为8个单位时间） 结论 通过短作业优先调度算法，进程的执行顺序被合理调度，系统的响应时间得到了改善。短作业优先调度算法可有效减少作业的平均等待时间，提高系统的吞吐量。
总之，短作业优先调度算法是一种简单且高效的进程调度算法，适用于在大多数情况下需要快速响应任务的系统。它通过选择剩余执行时间最短的作业来调度进程，以提高系统性能。在实际应用中，短作业优先调度算法需要根据系统实际情况进行调优，以获得更好的性能表现。 以上就是关于短作业优先调度算法例题的详细解释。希望通过本文的介绍，读者能够对短作业优先调度算法有更加深入的了解。
短作业优先调度算法 SJF算法的核心思想是最短作业先执行，这样可以最大化利用CPU资源，减少平均等待时间和作业的响应时间。它适用于批处理系统和交互式系统。 SJF算法的实现包括两种方式：非抢占式和抢占式。 非抢占式SJF算法： 在非抢占式SJF算法中，一旦CPU开始执行一个作业，它会一直执行完毕，直到作业完成或者发生I/O请求。当一个新的作业到达时，系统会比较该作业的执行时间和当前正在执行的作业的剩余执行时间，如果新作业的执行时间较短，则优先执行新作业。 抢占式SJF算法： 在抢占式SJF算法中，一旦有一个新的作业到达，并且它的执行时间比当前正在执行的作业短，操作系统会暂停当前作业的执行，将CPU分配给新作业，等新作业执行完毕后再继续执行之前的作业。抢占式SJF算法需要操作系统具备抢占能力，即能够中断并恢复作业的执行。 SJF算法的优点是可以最大化利用CPU资源，减少平均等待时间和作业的响应时间，适用于CPU密集型的作业。然而，SJF算法也存在一些问题和局限性： 1.预测执行时间的困难：在实际系统中，很难准确预测一个作业的执行时间，因此SJF算法可能会出现误判，导致等待时间增加。
2.饥饿问题：如果有大量的短作业不断到达，长作业可能会一直等待。这种情况称为饥饿问题，长作业可能无法获取足够的CPU时间，导致低响 应性。 3.处理I/O请求的处理：SJF算法无法解决I/O请求的调度问题，因 此需要结合其他算法来处理。 为了解决SJF算法存在的问题，还发展了一些改进的版本，如最短剩 余时间优先算法（Shortest Remaining Time First, SRTF），该算法在 抢占式的基础上，可以在作业执行过程中切换到更短的作业，以进一步减 少等待时间。 总结起来，SJF算法是一种重要的进程调度算法，它按照作业的执行 时间来确定优先级。它的优点是可以最大化利用CPU资源，减少等待时间 和作业响应时间。然而，它也存在预测执行时间困难、饥饿问题和无法解 决I/O请求的问题。为了解决这些问题，可以使用改进的版本或结合其他 算法来处理。
sjf算法例题详解 SJF算法例题解析 什么是SJF算法 •SJF（Shortest Job First）算法是一种非抢占式的调度算法，也被称为最短作业优先算法。 •SJF调度算法根据进程的执行时间来进行调度，先执行执行时间短的任务，以减少平均等待时间。 SJF算法的执行过程 1.将进程按照执行时间从小到大进行排序，得到一个等待队列。 2.从等待队列中选择执行时间最短的进程进行执行。 3.若有多个进程的执行时间相同，则根据其到达时间进行选择，选 择最先到达的进程执行。 4.执行完当前进程后，更新等待队列，继续选择执行时间最短的进 程进行执行，直到所有进程执行完毕。 SJF算法的例题解析 •假设有以下五个进程需要执行，进程的执行时间和到达时间如下：进程 | 到达时间 | 执行时间 | —- | | |
P1 | 0 | 5 | P2 | 1 | 3 | P3 | 2 | 8 | P4 | 3 | 6 | P5 | 4 | 4 | 1.首先，将进程按照到达时间进行排序： 进程 | 到达时间 | 执行时间 | —- | | | P1 | 0 | 5 | P2 | 1 | 3 | P3 | 2 | 8 | P4 | 3 | 6 | P5 | 4 | 4 | 2.然后，根据执行时间进行排序，若执行时间相同，则根据到达时 间进行选择： 进程 | 到达时间 | 执行时间 | —- | | | P2 | 1 | 3 | P5 | 4 | 4 | P1 | 0 | 5 | P4 | 3 | 6 | P3 | 2 | 8 |
3.根据执行时间选择要执行的进程： 进程 | 到达时间 | 执行时间 | —- | | | P2 | 1 | 3 | 4.执行完P2进程后，更新等待队列： 进程 | 到达时间 | 执行时间 | —- | | | P5 | 4 | 4 | P1 | 0 | 5 | P4 | 3 | 6 | P3 | 2 | 8 | 5.继续选择执行时间最短的进程执行，执行完毕后更新等待队列， 直到所有进程执行完毕。 SJF算法的优缺点 优点： - SJF算法能够最大程度地减少平均等待时间。 - 对于执行时间较短的进程，能够快速得到响应和执行。 缺点： - SJF算法无法预测进程的执行时间，若某个进程的执行时间较长，则可能导致其他进程长时间等待。 - 对于长作业来说，可能会出现”饥饿”现象，即长作业一直得不到执行。
sjf算法例题详解(一) SJF算法例题 1. 什么是SJF算法？ •SJF算法（Shortest Job First，短作业优先算法）是一种操作系统调度算法。 •它的原则是按照作业的执行时间来进行调度，执行时间短的作业会被优先调度执行。 •SJF算法适用于一些具有明确执行时间的作业，能够提高作业的响应速度和系统的整体利用率。 2. SJF算法的例题 考虑以下作业列表及其执行时间： 作业列表：[A, B, C, D] 执行时间：[5, 3, 8, 2] 3. 算法过程 按照SJF算法的原则，我们需要对作业列表进行排序，排序的依据是作业的执行时间。 排序后的作业列表如下：
作业列表：[D, B, A, C] 执行时间：[2, 3, 5, 8] 4. 执行顺序 根据排序后的作业列表，我们按照顺序执行作业。 执行顺序为：D -> B -> A -> C 5. 算法优势 SJF算法的优势在于能够减少作业的等待时间和响应时间，提高系统的整体效率。 6. 算法局限性 SJF算法的局限性在于对作业的执行时间需求较高，如果无法准确估计作业的执行时间，可能会导致调度不准确。 7. 结论 SJF算法是一种高效的操作系统调度算法，适用于有明确执行时间的作业。它能够提高作业的响应速度和系统的整体利用率，但对作业的执行时间估计要求较高。在实际应用中，可以根据任务的执行时间情况选择合适的调度算法以提高系统性能。 以上是对SJF算法例题的详细解释，希望能够对读者有所帮助。
SJF算法例题 1. 什么是SJF算法？ •SJF算法（Shortest Job First，短作业优先算法）是一种操作系统调度算法。 •它的原则是按照作业的执行时间来进行调度，执行时间短的作业会被优先调度执行。 •SJF算法适用于一些具有明确执行时间的作业，能够提高作业的响应速度和系统的整体利用率。 2. SJF算法的例题 考虑以下作业列表及其执行时间： •作业列表：[A, B, C, D] •执行时间：[5, 3, 8, 2] 3. 算法过程 按照SJF算法的原则，我们需要对作业列表进行排序，排序的依据是作业的执行时间。 排序后的作业列表如下： •作业列表：[D, B, A, C] •执行时间：[2, 3, 5, 8]
《Visual FoxPro实用教程》电子实验报告 题目：求三角形的面积日期2012.9.24姓名陈庆庆 实验环境： PC机，Windows XP，Visual FoxPr6.0 实验目的： 1．熟悉VFP的集成开发环境。 2．掌握主窗口，菜单，工具栏和命令窗口的使用方法。 3．掌握查找帮助主题的方法。 实验内容： 1．理论描述： 短作业优先算法即若干个进程运行，也可能是同一时间到达，也可能是不同的时间到达，同样不同的进程所需要的时间也不一样，短作业优先即比较每个进程所需要的服务时间，如果进程是同一时间到达，那么所需服务时间最短的进程最先被执行，即服务时间由小到大排序，得出的顺序即为进程先后被执行的顺序。若进程不是同一时间到达，则需比较到达时间的先后以及所需时间的大小，通过这两者的时间来进行排序，从而找出进程先后被执行的顺序。 2．设计思想： 此算法简单来说即是对每个进程的到达时间以及所需的服务时间从而找出进程先后被执行的顺序，因此简单来说有两种情况： （1）每个进程的到达时间相同，此种情况只需对每个进程所需要的服务时间进行比较，之后输出进程被执行的先后顺序。 （2）每个进程的到达时间不同，所需要的服务时间也不同，此种情况需要对进程的到达时间和所需的服务时间同时进行比较，从而得出进程被执行的先后顺序。
3．画出流程图。 4．写出源程序调试并运行通过。 #include
作业调度之最短作业优先算法5例题解析 例题一、某系统采用不能移动已在主存储器中作业的可变分区方式管理主存储 器，现有供用户使用的主存空间100K,系统配有4台磁带机，有一批作业见 下表： 作业序号进输入井时间要求计算时间需要主存容量申请磁带机数 1 10： 00 25 分钟 15K 2 台 2 10： 20 30 分钟 60K 1 台 3 10： 30 10 分钟 50K 3 台 4 10： 3 5 20 分钟 10K 2 台 5 10： 40 15 分钟 30K 2 台 按计算时间最短者优先算法如下表： 我的解释：系统首先装入1、2、4,但1结束时4沿未到达，因此先执行2； 2 执行完毕后，资源可以分配给3或5,考虑5的时间短优先分配5并执行，执 行完5后，主存中只有4已就绪并等待执行，因此开始执行4,执行4的同时 系统会将作业3装入主存，最后自然执行作业3；因此最后的顺序是： 1\2\5\4\3 作业序号进输入井时间进入主存时间开始计算时间结束计算时间周 转时间解释 1 10： 00 10： 10 10： 00 10： 25 25 此时输入井中只有一个作业且满足资源要求,因此被选中运行。 2 10： 20 10： 20 10： 25 10： 55 35 作业2到达输入井，满足资源要求，装入主存"等到作业1运行完翅入运行。 由于作业3要求主存空间无法满足,因此作业4先旷步装入主存,当作业2 让岀处理器的同时，作业5满足资源要求进入主存就绪。根据算法作业5先迸 入处理器运行。 5 55 10： 40 11： 10 10： 55 30 10：
4 10： 35 10 11： 3055 10 ： 3511: 3 10： 30 30 11： 4070 11:3011:最后作业3装入主存并运行 平均周转时间：(25+35+30+55+70)/5 = 43分钟 ［分析］解答本题时应注意如下儿个问题•• 第一，系统采用的是多道程序设计技术，但没有限定并行工作的道数，因此，只要出前尚未分配的资源可以满足在输入井中等待的某些作业的要求时，作业调度可以按照给定的算法从中选择一个或多个作业装人主存储器；第二，釆用可变分区方式管理主存储器，但没给出主存空间的分配算法，因而, 只要有合适的空间就可分配，题中还规定可用移动技术来合并分散的空闲区； 笫三，对磁带机釆用静态分配： 笫四，进程调度采用可抢占的最高优先级调度算法，即对已被装人主存储器的作业而言优先级高的作业可抢占处理器执行； 第五，虽然作业需要使用磁带机，但题意中已提示忽略磁带机和调度所花的时间，所以，解题时不必考虑外圉设备的启动二八D中断等复杂情况，只需把它们当作纯计算型的作业； 笫六，由于没有规定什么时候开始进行作业调度，故在一般情况下只要输入井中有等待处理的作业就可按选定的算法去选择满足必要条件的作业。 根据本题的要求列表分析如下：
青岛理工大学 操作系统课程设计报告 院（系）：计算机工程学院 专业：计算机科学与技术专业 学生姓名: 班级：＿＿学号: 题目：短作业优先调度算法的进程调度程序＿ 起迄日期:＿＿＿＿＿＿＿＿ 设计地点: 指导教师: 2011—2012年度第 1 学期 完成日期: 2012 年 1 月日
一、课程设计目的 进行操作系统课程设计主要是在学习操作系统课程的基础上，在完成操作系统各部分实验的基础上，对操作系统的整体进行一个模拟，通过实践加深对各个部分的管理功能的认识，还能进一步分析各个部分之间的联系，最后达到对完整系统的理解。同时，可以提高运用操作系统知识解决实际问题的能力；锻炼实际的编程能力、开发软件的能力；还能提高调查研究、查阅技术文献、资料以及编写软件设计文档的能力。 二、课程设计内容与要求 设计目的：在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个，且进程之间也存在着同步与互斥的关系，要求采用指定的调度策略，使系统中的进程有条不紊地工作，通过观察诸进程的运行过程，以巩固和加深处理机调度的概念。 2、设计要求（多道、单处理机）： 1)每一个进程有一个PCB，其内容可以根据具体情况设定。 2)可以在界面设定的互斥资源（包括两种：输入设备与输出设备）的数目 3)进程数、进入内存时间、要求服务时间可以在界面上进行设定 4)进程之间存在一定的同步与互斥关系，可以通过界面进行设定，其表示方法如下： 进程的服务时间由三段组成：I2C10O5（表示进程的服务时间由2个时间片的输入，10个时间片的计算，5个时间片的输出） 进程间的同步关系用一个段表示：W2，表示该进程先要等待P2进程执行结束后才可以运行 因此，进程间的同步与互斥关系、服务时间可以统一用四段表示为：I2C10O5W2 5)可以在运行中显示各进程的状态：就绪、阻塞、执行 6)采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相 应的阻塞队列 7)具有一定的数据容错性 三、系统分析与设计 1、系统分析 本系统主要是采用短作业优先算法进程的进程调度过程。短作业优先调度算法，是指对短作业或短进程优先调度的算法。他们可以分别用于作业调度和进程调度，短作业优先的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将他们调入内存运行。而短进程优先调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给他，，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再度重新调度。本程序采用了非抢占式短作业优先调度。而非抢占式这种方式，一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才再把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机。这种调度方式的优点是实现简单，系统开销小，适用于大多数的批处理系统环境。但它难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果。因此，在要求比较严格的实时系统中，不宜采用这种调度方式本系统的主要是在满足要求多道单处理机的情况下进行短作业的优先调度。 本系统在测试时输入了五个进程，按实验要求如I2C10O5（表示进程的服务时间由2个时间片的输入，10个时间片的计算，5个时间片的输出，5个时间片的计算组成）的方式输入，各进程的信息如下：（0 0 1 1 1 ）（1 2 1 2 2 ）（2 4 1 1 1 ）
第二章应用题参考答案 布置作业第二章5, 8, 10, 12, 17, 20, 27, 28, 30 5 若后备作业队列中等待运行的同时有三个作业J1、J2、J3，已知它们各自的运行时间为a、b、c，且满足a
作业名进入后备 队列时间执行 时间 开始执 行时间 结束执 行时间 周转 时间 带权周 转时间 JOB18:00 60 分8:00 9:00 60 60/60 JOB38:40 30 分9:00 9:30 50 50/30 JOB48:50 10 分9:30 9:40 50 50/10 JOB28:30 50 分9:40 10:30 120 120/50 平均周转时间T= (60+50+50+120)/4=70 带权平均周转时间W= (1+5/3+5+12/5)/4=2.52 【按照抢占式优先级调度】 8:00~8:30 执行JOB1, 余30 分钟 8:30~8:40 执行JOB2, 余40 分钟 8:40~9:10 执行JOB3, 余0 分钟 9:10~9:20 执行JOB4, 余0 分钟 9:20~10:00 执行JOB2, 余0 分钟 作业名进入后备 队列时间执行 时间 开始执 行时间 结束执 行时间 周转 时间 带权周 转时间 JOB1 8:0060 分8:00 10:30 150 150 /60 JOB2 8:3050 分8:30 10:00 90 90 /50 JOB3 8:4030 分8:40 9:10 30 30/30 JOB4 8:5010 分9:10 9:20 30 30/10 平均周转时间T= (150+90+30+30)/4=75 带权平均周转时间W= (150 /60+ 90 /50+ 30/30+30/10)/4=2.075 10 有5 个待运行的作业，预计其运行时间分别是：9、6、3、5 和x，采用哪种运行次序可以使得平均响应时间最短？ 答：按照最短作业优先的算法可以使平均响应时间最短。X 取值不定，按照以下情况讨论： 1）x≤3 次序为：x，3，5，6，9 2）3 1．若程序A和B单独执行时分别需要1小时和1.5小时，其中CPU工作时间分别为18分钟和27分钟。若采用多道程序设计方法，让A和B并行工作，假定CPU利用率达到50％，另加15分钟系统开销，请问系统效率能提高多少? 解：在多道系统中，程序A和B共用的CPU时间为：(18十27)／50％＝90分钟 系统效率提高＝(A和B单独执行的时间总和－多道方式下总时间)／A和B单独执行的时间总和，即((60十90)－(90十15))／(60十90)＝45／150＝30％ 1.假定在单CPU条件下有下列要执行的作业： 作业运行时间优先级 1 10 2 2 4 3 3 3 0 作业到来的时间是按作业编号顺序进行的(即后面作业依次比前一个作业迟到一个时间单位)。 (1)用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。 (2)对于上述算法，各个作业的周转时间是多少?平均周转时间是多少? (3)对于上述算法，各个作业的带权周转时间是多少?平均带权周转时间是多少? 解： (1)非抢占式优先级算法作业的执行情况如下： 作业到达时间运行时间完成时间周转时间带权周转时间 1 0 10 10 10 1.0 2 1 4 17 16 4.0 3 2 3 13 11 3.7 平均周转时间12.3 平均带权周转时间 2.9 2．若在后备作业队列中等待运行的同时有三个作业1、2、3，已知它们各自的运行时间为a、b、c，且满足关系a＜b＜c，试证明采用短作业优先调度算法能获得最小平均周转时间。 证明：由于短作业优先调度算法总是在后备作业队列中选择运行时间最短的作业作为调度对象，因此对短作业优先调度算法而言，这三个作业的总周转时间为 T1=a+(a+b)+(a+b+c)=3a+2b+c (1) 若不按短作业优先调度算法来调度这三个作业，不失一般性，假定调度顺序为2、l、3，则其周转时间为 T2=b+(b+a)+(b+a+c)=3b+2a+c (2) 由(1)、(2)两式可得：T2-T1=b-a>0 由此可见，短作业优先调度算法能获得最小平均周转时间。 3．设有4道作业，它们的提交时间及执行时间如下： 试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。(时间单位：小时，以十进制进行计算。) 解：若采用先来先服务调度算法，则其调度顺序为1、2、3、4。 最短作业优先（抢占和非抢占） 一、流程图 解析： 在最开始，我们先创建若干进程，选择自动运行，则在运行完后，按顺序显示运行的结果。 同理，选择手动运行，那么就是最先选择最短的作业开始运行，其实当前进程并非一定在实际运行（改变自己的状态），只是一个虚拟的运行（虚拟最短作业优先运行算法），这时我们可以做其他的事情，在做事之前，先运行虚拟算法，依照最短作业优先去改变相关进程的状态（进程可能就没有实际运行过，被虚拟算法改变了状态（就绪、等待、终止）），在做完相关事情之后，再运行虚拟算法，确定是否要发生最短作业的优先抢占。 根据以上的运行结构，我们可以在这结构的基础上，人为地设置进程状态就是改变进程状态，这时就可以发生最短作业调度的抢占和非抢占式。我们可以进入查看进程状态，看看运行的状况，也可以进入修改进程状态，修改相关进程状态让其发生最短作业的抢占，或者进入创建进程，创建一个新的进程，这是也有可能实现最短作业优先的抢占。 二、虚拟运行算法： 从进程的结构分析，进程里面有状态，到达时间（取系统时间），结束时间（取系统时间），需要运行时间，已运行时间等，我们知道第一个最短作业运行的到达时间（开始运行的时间）就是创建的时间。在一个进程运行终止时，要设好终止的时间、改变状态等属性，这时进行进程间信息交换，终止进程的时间交给下一个要运行的进程的到达时间，这样不断下去就可以运行到最后一个进程， 当发生抢占调度时，也是以上的情况运行。先在抢占之前，就运行虚拟算法，改变相关的进程状态，发生引起抢占的事的时候就可以利用抢占来进行进程的切换。这样就能让CPU在有工作做时就不能空闲。直到把所有在就绪队列的进程运行完，这是CPU可以休息了，如果在CPU休息时有进程从等待进入就绪，那么CPU就要继续开工。 当我们运行完第一批输入的进程，现在CPU在空转，我们又创建了新进程，这时新进程就在创建那一刻起开始运行了，因为新进程创建好就进入了就绪的状态。 下面为具体的算法： 虚拟运行算法： PCB *run(PCB *first,PCB *cur) /*运行函数,参数为头指针和当前运行的进程*/ {PCB *pro; PCB *currentpro; int i; currentpro=cur; if(currentpro==NULL) return NULL; i=settime(currentpro); if(i) /*时间超出了*/{ pro=currentpro; while(1){ pro->state=4; pro->endtime=pro->arrivetime+(double)pro->needtime ;/*设置结束时间*/ printf(" %s >> have finished!\n ",pro->name); currentpro=seize(first);/*查找就绪队列的最短作业*/ if(currentpro==NULL) { pro->cputime=pro->needtime; break;}操作系统复习应用题
最短作业优先(抢占和非抢占)
相关主题
文本预览