下载文档原格式
操作系统短作业优先调度算法1操作系统实验题⽬：实现⾮抢占式短作业优先调度算法要求：1.系统共有100个随机到达的作业。
要求为每个作业设定到达时间和需要运⾏的时间。
2.按照短作业优先进⾏调度，直到所有作业完成。
3.计算每个作业的周转时间，计算平均周转时间。
提交报告1.实验报告打印稿（参照学校有关报告格式）。
2.刻录⼀张光盘。
光盘内容：⽤学号+姓名为每个同学建⽴⽬录，⽂件包括报告的电⼦版，程序源代码。
⼀、主要数据结构及其说明算法的基本概念和原理：本次课程设计主要是采⽤短作业优先算法进程的进程调度过程。
短作业优先调度算法，是指对短作业或短进程优先调度的算法。
他们可以分别⽤于作业调度和进程调度，短作业优先的调度算法是从后备队列中选择⼀个或若⼲个估计运⾏时间最短的作业，将他们调⼊内存运⾏。
⽽短进程优先调度算法则是从就绪队列中选出⼀个估计运⾏时间最短的进程，将处理机分配给他，使它⽴即执⾏并⼀直执⾏到完成，或发⽣某事件⽽被阻塞放弃处理机时再度重新调度。
本程序采⽤了⾮抢占式短作业优先调度。
⽽⾮抢占式这种⽅式，⼀旦把处理机分配给某进程后，便让该进程⼀直执⾏，直⾄该进程完成或发⽣某事件⽽被阻塞时，才再把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机。
这种调度⽅式的优点是实现简单，系统开销⼩，适⽤于⼤多数的批处理系统环境。
但它难以满⾜紧急任务的要求——⽴即执⾏，因⽽可能造成难以预料的后果。
因此，在要求⽐较严格的实时系统中，不宜采⽤这种调度⽅式。
本课程设计主要是在满⾜要求多道单处理机的情况下进⾏短作业的优先调度。
算法的简要说明：短作业（进程）优先调度算法SJ（P）F，是指对短作业或短进程优先调度的算法。
它们可以分别⽤于作业调度和进程调度。
短作业优先（SJF）的调度算法是从后备队列中选择⼀个或若⼲个估计运⾏时间最短的作业，将它们调⼊内存运⾏。
⽽短进程（SPF）调度算法则是从就绪队列中选出⼀个估计运⾏时间最短的进程，将处理机分配给它，使它⽴即执⾏并⼀直执⾏到完成，或发⽣某事件⽽被阻塞放弃处理机再重新调度。
一、根据调度算法设计流程图：实验
步骤
}
}
}
三、整合完成所有程序并实现作业调度（见源代码）。
四、进行调试阶段，对程序修改优化，进行数据测试。
五、实验结果分析
六、总结
实验
WindowsXP和CV++6.0集成开发环境
环境
实验运行的初始界面：
实验结
果与分
析
测试数据：
a1 1 2 a1
a2 2 3 a2
运行结果：
进行多次循环录入：返回算法选择界面：
测试数据：
b1 2 4 b1
b2 1 3 b2
运行结果：
实验分析和总结：
1）测试的数据必须是符合JCB模块中相同类型的，如在源码中式int类型的，而在测试的时候输入float类型就出错。
2）各个库函数的运用需要掌握相应的功能，否则会照成代码冗余、繁杂、不优化等各种问题。
3）通常在dos下运用的都是英文，而想要用汉字提示就必须考虑一些问题。
在源码中我们用制表符（\t）来控制提示，输出的数字是不能与之对齐的，所以我们要将“\t”改成空格。
4）这编写和调试程序时，为了尽快调通程序应该按照流程图的结构（保证流程图思路是对的情况下）来建立编程思路。
5）此程序也借用了现有的一些代码，并且它还不是最优化的，它还可以进行改进和优化，比如：在回调函数的引用时跳到了另一个页面，见下图：
继续Enter的时候就到下一页：
而不是在同一页面。
6）总之，在编程旅途中是一个很艰辛的过程，要在这里开拓一片蓝天就必须有孜孜不倦的精神。
让知识带有温度。
操作系统名词解释和简答题(1)多道批处理系统:在该系统中，用户所提交的作业都先存放在外存上并排成一个队列，称为“后备队列”；然后，由作业调度程序按一定的算法从后备队列中挑选若干个作业调入内存，使它们分享C P U和系统中的各种资源。
(2)分时系统:分时系统用于满足用户需求，使用户能与自己的作业举行交互，还有分享主机与便于用户上机。
(3)实时系统:指系统能准时(或即时)响应外部大事的哀求，在规定的时光内完成对该大事的处理，并控制全部实时任务协调全都地运行。
(4)实时调度:为了满足实时系统对实时进程或任务的调度。
(5)设备自立性:应用程序自立于详细使用的物理设备。
(6)系统调用:P261(7)分享存储器系统:互相通信的进程分享某些数据结构和分享存储区，进程之间能够通过这些空间举行通信。
(8)进程:进程是程序在一个数据集合上运行的过程，它是系统举行资源分配和调度的一个自立单位。
(9)线程:将进程的两个属性分开，由操作系统分开处理。
(10)调度算法:按照系统的资源分配策略所规定的资源分配算法。
(11)局部性原理:程序在执行时将展现出局部性逻辑，即在一较短时光内，程序的执行仅局限与某个部分；相应地，他所拜访的存储空间也局限于某个区域。
(12)SPOOLING技术:在主机的直接控制下，实现脱机输入、输出功能。
此时的外围操作与CPU对数据的处理同时举行，我们把这种在联机状况下实现的同时外围操作称为SPOOLing。
(13)图形用户界面:P273第1页/共3页千里之行，始于足下(14)程序并发执行:程序彼此互不依靠，则程序间可以并发执行。
(15)进程同步:是对多个相关进程在执行次序上举行协调，以使并发执行的诸进程之间能有效的分享资源和互相合作，从而使程序的执行具有可再现性。
(16)信号量机制：是一种卓有成效的进程同步机制。
(17)死锁：是指多个进程在运行过程中由于争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，他们都将无法再向前推动。
多道程序设计技术和多道批处理是计算机科学领域中的重要概念，它们对于提高计算机系统的效率和性能有着重要的意义。
本文将对多道程序设计技术和多道批处理进行深入探讨，包括其定义、原理、优缺点以及在计算机系统中的应用等方面。
一、多道程序设计技术的定义及原理多道程序设计技术是指在计算机系统中，允许多个程序同时进入内存并并行执行的技术。
其原理是通过将内存分成多个区域，每个程序都在自己的内存区域中运行，使得多个程序可以同时在计算机系统中执行。
这种技术能够提高计算机系统的利用率，减少资源的浪费，从而提高整体的性能。
二、多道程序设计技术的优缺点1. 优点：（1）提高系统资源利用率：多道程序设计技术允许多个程序同时在计算机系统中执行，可以更充分地利用系统资源，提高系统的资源利用率。
（2）提高系统的吞吐量：由于多个程序可以同时在计算机系统中执行，可以提高系统的吞吐量，从而提高系统的性能。
（3）提高用户的响应速度：多道程序设计技术能够减少用户等待程序执行的时间，提高用户的响应速度，提升用户体验。
2. 缺点：（1）资源竞争：由于多个程序共享系统资源，可能会产生资源竞争的问题，影响系统的稳定性和性能。
（2）调度复杂：多道程序设计技术需要进行复杂的调度和管理，需要一定的算法和机制来保证多个程序能够正常执行。
三、多道批处理的定义及原理多道批处理是指计算机系统能够自动地将多个作业按顺序提交给计算机系统执行的技术。
其原理是通过作业调度程序将多个作业按顺序加载到内存中并执行，当一个作业执行完成后，系统自动加载下一个作业，实现作业的连续执行。
这种技术能够提高计算机系统的利用率，提高作业的执行效率。
四、多道批处理的优缺点1. 优点：（1）提高系统利用率：多道批处理能够连续地执行多个作业，提高系统的利用率，减少资源的浪费。
（2）减少用户等待时间：多道批处理能够自动地加载和执行作业，减少用户等待的时间，提高用户体验。
2. 缺点：（1）作业之间的竞争：多道批处理可能会导致作业之间的资源竞争，影响系统的稳定性和性能。
操作系统——作业调度实验⼆作业调度模拟程序⼀、⽬的和要求 1. 实验⽬的 （1）加深对作业调度算法的理解； （2）进⾏程序设计的训练。
2．实验要求 ⽤⾼级语⾔编写⼀个或多个作业调度的模拟程序。
单道批处理系统的作业调度程序。
作业⼀投⼊运⾏，它就占有计算机的⼀切资源直到作业完成为⽌，因此调度作业时不必考虑它所需要的资源是否得到满⾜，它所运⾏的时间等因素。
作业调度算法： 1) 采⽤先来先服务（FCFS）调度算法，即按作业到达的先后次序进⾏调度。
总是⾸先调度在系统中等待时间最长的作业。
2) 短作业优先 (SJF) 调度算法，优先调度要求运⾏时间最短的作业。
3) 响应⽐⾼者优先(HRRN)调度算法，为每个作业设置⼀个优先权(响应⽐)，调度之前先计算各作业的优先权，优先数⾼者优先调度。
RP (响应⽐)＝作业周转时间 / 作业运⾏时间=1+作业等待时间/作业运⾏时间每个作业由⼀个作业控制块JCB表⽰，JCB可以包含以下信息：作业名、提交（到达）时间、所需的运⾏时间、所需的资源、作业状态、链指针等等。
作业的状态可以是等待W（Wait）、运⾏R（Run）和完成F（Finish）三种之⼀。
每个作业的最初状态都是等待W。
⼀、模拟数据的⽣成 1．允许⽤户指定作业的个数（2-24），默认值为5。
2. 允许⽤户选择输⼊每个作业的到达时间和所需运⾏时间。
3.（**）从⽂件中读⼊以上数据。
4.（**）也允许⽤户选择通过伪随机数指定每个作业的到达时间（0-30）和所需运⾏时间（1-8）。
⼆、模拟程序的功能 1．按照模拟数据的到达时间和所需运⾏时间，执⾏FCFS, SJF和HRRN调度算法，程序计算各作业的开始执⾏时间，各作业的完成时间，周转时间和带权周转时间（周转系数）。
2. 动态演⽰每调度⼀次，更新现在系统时刻，处于运⾏状态和等待各作业的相应信息（作业名、到达时间、所需的运⾏时间等）对于HRRN算法，能在每次调度时显⽰各作业的响应⽐R情况。
西安交通大学软件学院操作系统原理Operating System PrincipleOperating System Principle田丽华1-3 多道批处理系统多道程序设计 60年代中 ~ 70年代中（集成电路）目的 利用多道批处理提高资源的利用率内存中同时存放几个作业，使之都处于执行的开始点和结束点之间多个作业共享CPU 、内存、外设等资源 多道60年代通道和中断技术的出现解决了输入输出等待计算的问题通道是一种专用部件，负责外部设备与内存之间信息的传输。
中断指主机接到外界的信号（来自CPU外部或内部）时，立即中止原来的工作，转去处理这一外来事件，处理完后，主机又回到原来工作点继续工作。
Several jobs are kept in main memory at the same time, and the CPU is multiplexed among them.在内存中同时有多个作业，CPU在其中切换As long as there is always at least one job to execute, the CPU is never idle.只要系统中总是存在可执行的作业，CPU就永远不会因无事可干而闲着。
MultiprogrammingMultiprogramming increases CPU utilization by organizing jobs such that the CPU always has one to execute.多道通过组织作业使得CPU总在执行其中一个作业，从而提高了CPU的利用率运行特征内存中同时驻留多道程序并发执行，从而有效地提高了资源利用率和系统吞吐量 多道性 作业的完成顺序与它进入内存的顺序之间无严格的对应关系 无序性 作业调度、进程调度调度性优点资源利用率高:CPU,内存,I/O设备 系统吞吐量大缺点无交互能力，用户响应时间长作业平均周转时间长OS Features Needed for Multiprogramming多道程序对OS特点的要求Memory management存储管理–the system must allocate the memory to several jobs.系统必须为若干作业分派空间CPU scheduling CPU调度–the system must choose among系统必须在就绪作业中挑选挑选several jobs ready to run.系统必须在就绪作业中Resource competition and sharing资源竞争和共享Allocation of devices.设备分配提供I/O程序系统提供I/O routine supplied by the systemI/O routine supplied by the system..系统File management 文件管理。
作业调度实验报告作业调度算法实验。
二、实验目标已知n个作业的进入时间和估计运行时间（以分钟计）（1）单道环境下，分别用先来先服务调度算法、短作业优先调度算法、响应比高者优先调度算法，求出批作业的平均周转时间和带权平均周转时间；在多道环境（如2道）下，求出这些作业的平均周转时间和带权平均周转时间（2）就同一批次作业，分别讨论这些算法的优劣；（3）衡量同一调度算法对不同作业流的性能。
三、实验环境要求1.PC机。
2.Windows环境。
3.CodeBlocks四、实验基本原理（1）先来先服务算法：按照作业提交给系统的先后顺序来挑选作业，先提交的先被挑选。
（2）最短作业优先算法：是以进入系统的作业所提出的“执行时间”为标准，总是优先选取执行时间最短的作业。
（ 3）响应比高者优先算法：是在每次调度前都要计算所有被选作业（在后备队列中）的响应比，然后选择响应比最高的作业执行。
（4）两道批处理系统中最短作业优先调度算法：内存中可以进入两个作业，这两个作业按照最短作业优先调度算法调整作业执行的次序。
五、数据结构设计使用一维数组来保存多个作业Job job[20];，采用的是顺序存储。
使用queue<Jcb *> q保存调度队列里的作业指针。
struct Date//时间结构体{int hour;//时间的小时int minute;//时间的分钟};struct Jcb//作业结构体，用来描述作业{int no;//作业编号Date enter;//进入时间int operation;//估计运行时间Date start;//开始时间Date over;//结束时间int turnover;//周转时间double weighted;//带权周转时间int state=0;//标记改作业是否进入运行状态};六、流程图单道环境下算法流程图多道环境下的两道批处理系统中最短作业优先作业调度算法的流程图。
七、源代码#include<iostream> #include<stdio.h>#include<cstring>#include<algorithm> #include<queue> using namespace std;struct Date//时间结构体{int hour;//时间的小时int minute;//时间的分钟};struct Jcb//作业结构体，用来描述作业{int no;//作业编号Date enter;//进入时间int operation;//估计运行时间Date start;//开始时间Date over;//结束时间int turnover;//周转时间double weighted;//带权周转时间int state=0;//标记改作业是否进入运行状态};//函数声明void display(Jcb J[],int n);//输出void runing( queue<Jcb *> q,int n);//根据算法将就绪队列排好队后的单道作业的运行主体void fcfs( Jcb J[],int n);//先来先服务作业调度void sfc(Jcb J[],int n);//最短作业优先作业调度void hrfc(Jcb J[],int n);//最高响应比作业调度void text(void (*dispatch)(Jcb J[], int n),Jcb J[],int n,Jcb J1[],int n1, Jcb J2[],int n2);//测试单道环境，不同批次作业，相同算法void mulfc(Jcb J[],int n);//两道环境，内存中可以用两个作业，内存中的这两个作业按照作业长短调整作业执行的次序。
多道批处理系统的工作原理
多道批处理系统是一种计算机操作系统，其工作原理是将多个作业按照一定的顺序批量提交到计算机系统中进行处理。
在多道批处理系统中，计算机会根据一定的调度算法，将不同的作业放在不同的队列中，然后依次执行这些队列中的作业。
在这个过程中，计算机会根据作业的优先级、资源的可用情况以及其他一些因素，选择适合的作业进行处理。
同时，计算机还会为每个作业分配一定的CPU时间片，以确保每个作业都能得到充分的处理时间。
此外，多道批处理系统还会采用一些优化技术，如作业合并、作业分割等，来提高系统的效率和资源利用率。
通过这些优化技术，可以使多个作业同时在计算机上运行，从而提高整个系统的吞吐量和处理能力。
总的来说，多道批处理系统是一种有效的计算机操作系统，其通过合理的作业调度算法和优化技术，可以大大提高计算机的处理效率和资源利用率。
- 1 -。
计算机学院计算机科学与技术专业07 班姓名学号教师评定_________________实验题目作业调度一、实验目的本实验要求学生模拟作业调度的实现，用高级语言编写和调试一个或多个作业调度的模拟程序，了解作业调度在操作系统中的作用，以加深对作业调度算法的理解。
二、实验内容和要求1、为单道批处理系统设计一个作业调度程序(1)、编写并调试一个单道处理系统的作业调度模拟程序。
(2)、作业调度算法：分别采用先来先服务（FCFS），最短作业优先（SJF）的调度算法。
(3)、由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的CPU时限等因素。
(4)、每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。
作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。
每个作业的最初状态总是等待W。
(5)、对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，并比较各种算法的优缺点。
2、模拟批处理多道操作系统的作业调度（1）写并调试一个作业调度模拟程序。
（2）作业调度算法：分别采用先来服务（FCFS）调度算法。
（3）在批处理系统中，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求，所需要的资源是否得到满足。
作业调度程序负责从输入井选择若干个作业进入主存，为它们分配必要的资源，当它们能够被进程调度选中时，就可占用处理机运行。
作业调度选择一个作业的必要条件是系统中现有的尚未分配的资源可满足该作业的资源要求。
但有时系统中现有的尚未分配的资源既可满足某个作业的要求也可满足其它一些作业要求，那么，作业调度必须按一定的算法在这些作业中作出选择。
当作业正常运行完毕或因发生错误非正常终止时，作业进入完成状态，此时，系统将收回该作业所占用的全部资源，并清除有关的JCB。
并输出显示作业运行情况及作业输出结果。
三、实验设计方案及原理假设在单道批处理环境下有四个作业JOB1、JOB2、JOB3、JOB4，已知它们进入系统的时间、估计运行时间。
分别采用先来先服务（FCFS），最短作业优先（SJF）调度算法，计算出作业的平均周转时间和带权的平均周转时间。
作业p的周转时间：p->ttime=p->ftime-p->atime作业的平均周转时间：total=全部进程的周转时间/进程个数作业p的带权周转时间：p->wtime =p->ttime/p->ntime作业的平均带权周转时间：W=全部进程的带权周转时间/进程个数1、先来先服务调度算法（FCFS）：每次调度都是从后备作业队列中，选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。
在进程调度中采用FCFS算法时，这每次调度是从就绪队列中，选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。
该进程一直运行到完成或发生某事件阻赛后，才放弃处理机。
2、最短作业优先（SJF）：每次从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。
对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，并比较各种算法的优缺点。
3、多道作业调度算法：将作业按FCFS原则排好队，在输入井中按作业到达的先后次序来挑选作业，先进入输入井的作业优先被挑选，当系统中现有的尚未分配的资源不能满足先进入输入井的作业时，那么顺序挑选后面的作业，把不能满足要求的放回输入井尾部等待，当作业执行结束进入完成状态时，做好释放资源等善后工作。
四、流程图1、FCFS算法和SJF算法:2.多道作业调度算法五、给出程序中源程序名和执行程序名：源程序名：FCFS and SJF,执行程序名：fcfs and sjf.cpp 源程序名：DUODAO 执行程序名：duodao.cpp六、程序清单1.FCFS和SJF算法#include "stdio.h"#include <stdlib.h>#include <conio.h>#define getpch(type) (type*)malloc(sizeof(type))struct jcb{char name[10];char state;int atime;//作业到达时间int btime;//作业开始运行时间int ftime;//作业完成时间int ntime;//作业估计运行时间int rtime;//作业执行时间int ttime;//周转时间float wtime;//带权周转时间(周转时间/估计运行时间）struct jcb* link;}*ready=NULL, *p;//ready指向队头，p指向正被调度的作业typedef struct jcb JCB;int T=0; //初始化时间量float total;//记录所有作业的总时间double weight;//记录所有作业的带权周转时间void sort() /* 建立对作业进行到达时间排列函数*/{JCB *first, *second;int insert=0;if((ready==NULL)||((p->atime)<(ready->atime))) /*作业到达时间最短的,插入队首*/ {p->link=ready;ready=p;T=p->atime; //更改时间量}else /* 作业比较到达时间,插入适当的位置中*/{first=ready;second=first->link;while(second!=NULL){if((p->atime)<(second->atime)) /*若插入作业比当前队尾作业到达时间短,*/{ /*插入到当前队尾作业前面*/p->link=second;first->link=p;second=NULL;insert=1;}else /* 插入作业到达时间最长,则插入到队尾*/{first=first->link;second=second->link;}}if (insert==0) first->link=p;}}void shortjob() // 获取队列中的最短作业{JCB *pr,*min,*qr;min=ready;//min指向作业对头qr=ready;pr=ready->link;while(pr!=NULL){if((pr!=NULL)&&(T>=pr->atime)&&(pr->ntime)<(min->ntime)){//当插入作业到达时间要比时间量T小min=pr; //min指向prqr->link=pr->link;//qr的下一个指向pr的下一个pr->link=ready;pr=pr->link;}else //当pr的需要时间不小于min的需要时间{ qr=pr;pr=pr->link;}ready=min;//把最终获取的min的需要时间赋给ready，开始执行}}void input() /*建立作业控制块函数*/{int i;printf("\n 请输入4个作业：");for(i = 0; i < 4; i++){printf("\n 请输入作业号NO.%d：\n",i);p = getpch(JCB);printf("输入作业名：");scanf("%s",p->name);printf("\n输入作业到达时间：");scanf("%d",&p->atime);printf("\n 输入作业运行时间：");scanf("%d",&p->ntime);printf("\n");p->rtime = 0;p->btime=0;p->ftime=0;p->ttime=0;p->wtime=0;p->state = 'W';p->link = NULL;sort();}}int space() /*查看作业个数*/{int l = 0;JCB *pr = ready;while(pr != NULL){l++;pr = pr->link;}return(l);}void disp(JCB *pr) /*建立作业显示函数，用于显示当前作业*/{printf("\n qname \t state \t atime \t ntime \t btime \t rtime \t ftime \t ttime \t wtime \n"); printf(" |%s \t",pr->name);printf(" |%c \t",pr->state);printf(" |%d \t",pr->atime);printf(" |%d \t",pr->ntime);printf(" |%d \t",pr->btime);printf(" |%d \t",pr->rtime);printf(" |%d \t",pr->ftime);printf(" |%d \t",pr->ttime);printf(" |%.2f \t",pr->wtime);printf("\n");}void check() /* 建立作业查看函数*/{JCB* pr;printf("\n **** 当前正在运行的作业是:%s",p->name); /*显示当前运行作业*/disp(p);pr=ready;printf("\n ****当前就绪队列状态为:\n"); /*显示就绪队列状态*/while(pr!=NULL){disp(pr);pr=pr->link;}}void destroy(){printf("\n 作业[%s] 已完成。
