短作业算法

采用短作业优先调度算法调度程序

学 号： 姓 名： 专 业： 指导老师： 日 期：

目 录

一、实验题目 ............................................................................... 3

二、课程设计的目的 .................................................................... 3

三、设计内容 ............................................................................... 3

四、设计要求 .....................................................................

1

操作系统实验

题目：

实现非抢占式短作业优先调度算法 要求：

1. 系统共有100个随机到达的作业。要求为每个作业设定到达时间和需要运行的时间。 2. 按照短作业优先进行调度，直到所有作业完成。 3. 计算每个作业的周转时间，计算平均周转时间。 提交报告

1. 实验报告打印稿（参照学校有关报告格式）。

2. 刻录一张光盘。光盘内容：用学号+姓名为每个同学建立目录，文件包括报告的电子版，

程序源代码。

一、主要数据结构及其说明

算法的基本概念和原理：本次课程设计主要是采用短作业优先算法进程的进程调度过程。短作业优先调度算法，是指对短作业或短进程优先调度的算法。他们可以分别用于作业调度和进程调度，短作业优先的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将他们调入内存运行。而短进程优先调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给他，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再度重新调度。本程序采用了非抢占式短作业优先调度。而非抢占式这种方式，一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才再把处理机分配给其它进程，决不允许某进程抢占已经分配出

学号 实验日期 P71514032 2017.10.27 专业 计算机科学与技术 教师签字 成绩 姓名

实验报告

【实验名称】 【实验目的】

在多道程序或多任务系统中，系统同时处于就绪态的进程有若干个。也就是说能运行的进程数远远大于处理机个数，为了使系统中的各进程能有条不紊的运行，必须选择某种调度策略，以选择一进程占用处理机，所以，要求使用某一种编程语言设计实现模拟单处理机调度的算法，以巩固和加深处理机调度的概念。

本实验要求采用先来先服务的调度算法和短作业优先的调度算法编写和调试一个简单的进程调度程序。通过本实验可以加深理解进程调度、进程队列的概念。

进程调度算法FCFS、FJF

【实验原理】

FCFS调度算法

先来先服务(FCFS)调度算法是一种最简单的调度算法。在进程调度中采

用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。

SJF调度算法

短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度

的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计

操作系统实验一 FCFS和SJF 实验报告含代码

实验一 先来先服务FCFS和短作业优先SJF进程调度算法

一：需求分析

程序设计的任务：设计程序模拟进程的先来先服务FCFS和短作业优先SJF调度过程。假设有n个x进程分别在T1, … ,Tn时刻到达系统，它们需要的服务时间分别为S1, … ,Sn。分别采用先来先服务FCFS和短作业优先SJF进程调度算法进行调度，计算每个进程的完成时间、周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。

通过这次实验，加深对进程概念的理解，进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。

（1）输入的形式和输入值的范围

为免去测试时候需要逐步输入数据的麻烦，输入时采用输入文件流方式将数据放在.txt文件中，第一行为进程个数，第二行为进程到达时间（各个进程的到达时间之间用空格隔开），第三行为进程的服务时间（每个服务时间之间用空格隔开）。

（2）输出的形式 模拟整个调度过程，输出每个时刻的进程运行状态，同时输出了每个进程的完成时间，并且按要求输出了计算出来的每个进程的周转时间、带权周转时间、所有进程的平均周转时间以及带权平均周转时间。

（3）程序所能达到的功能

能够模拟出进程的先

实验一 先来先服务FCFS和短作业优先SJF进程调度算法

一：需求分析

程序设计的任务：设计程序模拟进程的先来先服务FCFS和短作业优先SJF调度过程。假设有n个x进程分别在T1, … ,Tn时刻到达系统，它们需要的服务时间分别为S1, … ,Sn。分别采用先来先服务FCFS和短作业优先SJF进程调度算法进行调度，计算每个进程的完成时间、周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。

通过这次实验，加深对进程概念的理解，进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。

（1）输入的形式和输入值的范围

为免去测试时候需要逐步输入数据的麻烦，输入时采用输入文件流方式将数据放在.txt文件中，第一行为进程个数，第二行为进程到达时间（各个进程的到达时间之间用空格隔开），第三行为进程的服务时间（每个服务时间之间用空格隔开）。

（2）输出的形式 模拟整个调度过程，输出每个时刻的进程运行状态，同时输出了每个进程的完成时间，并且按要求输出了计算出来的每个进程的周转时间、带权周转时间、所有进程的平均周转时间以及带权平均周转时间。

（3）程序所能达到的功能

能够模拟出进程的先来先服务FC

VC6.0实现四种进程调度算法 测试成功

#include"stdio.h" #define N 50

int n;

int sj; struct Gzuo{

int id; //进程名字 int dt; //到达时刻

int st; //服务时间

int wct; //完成时刻

int yxj; //优先级

int st2; //标志是否完成

float zt; //周转时间

float dczt; //带权周转时间

};

Gzuo a[N]; void input(Gzuo a[])

{

printf("请输入进程个数：");

scanf("%d",&n);

for(int i=0;i<n;i++) {

a[i].id=i+1;

printf("\t到达时间： ");

scanf("%d",&a[i].dt);

printf("\t服务时间： ");

scanf("%d",&a[i].st); a[i].st2 = a[i].st;

printf("\n");

} pri

实验4 作业调度算法

学院：信息工程学院 班级：计算机10-2班 学号：1005120201 姓名：常大财 实验目的:

1) 加深对作业概念的理解。

2) 理解操作系统中调度的概念和调度算法。

3) 深入理解操作系统中如何组织、管理和调度作业，如何协调和控制各作业对CPU的使用。

实验准备: 以自己的用户名进入LINUX 操作系统。 会用vi编辑文本文件。 在PC机上安装C语言集成开发环境。 熟悉C语言编程。 理解作业调度算法的基本思想。

实验内容:

编写程序完成批处理系统中的作业调度，要求分别采用先来先服务算法（FCFS）、短作业优先算法（SJF）和高响应比优先算法（HRN）。实验具体包括：首先确定作业控制块的内容，作业控制块的组织方式；然后完成作业调度；最后编写主函数对所做工作进行测试，并对程序的运行结果进行分析。

源代码：

#include

#define getjcb(type) (type*)malloc(sizeof(type)) #define NULL 0 #include #include

int n=0,time=0;float eti,ewi;

struct jcb{ char

一、银行家算法 P137-139 第三章

1．假设有PA、PB、PC、PD、PE 共5个进程，共享A、B、C 3种资源，且系统资源总数分别为A=7、B=5、C=10。在T0时刻有以下分配情况： 资源 进程 PA PB PC PD PE 试求

（1） T0时刻系统可利用资源向量Available的值。 答：Available 的值是(2,0,3)

（2）以下2个小题没有因果关系，每小题都是以T0时刻分配情况为前提条件判断能否分配及理由。若能分配，请将分配过程填入表格，并写出存在的安全序列。

①PB进程申请资源A、B、C分别为 0、1、0，能否分配？为什么？ 答：不能分配，对于B的分配，资源不够。

②PC进程申请资源A、B、C分别为 0、0、2，能否分配？为什么？ 答： 可以分配。（2,0,3）的值足够分给（0,0,2）

安全序列：(PA,PC,PB,PE,PD) 资源 进程 PA PB PC PD PE

已分配（Allocation） A B C 0 1 2 0 3 0 2

实验4 作业调度算法

学院：信息工程学院 班级：计算机10-2班 学号：1005120201 姓名：常大财 实验目的:

1) 加深对作业概念的理解。

2) 理解操作系统中调度的概念和调度算法。

3) 深入理解操作系统中如何组织、管理和调度作业，如何协调和控制各作业对CPU的使用。

实验准备: 以自己的用户名进入LINUX 操作系统。 会用vi编辑文本文件。 在PC机上安装C语言集成开发环境。 熟悉C语言编程。 理解作业调度算法的基本思想。

实验内容:

编写程序完成批处理系统中的作业调度，要求分别采用先来先服务算法（FCFS）、短作业优先算法（SJF）和高响应比优先算法（HRN）。实验具体包括：首先确定作业控制块的内容，作业控制块的组织方式；然后完成作业调度；最后编写主函数对所做工作进行测试，并对程序的运行结果进行分析。

源代码：

#include

#define getjcb(type) (type*)malloc(sizeof(type)) #define NULL 0 #include #include

int n=0,time=0;float eti,ewi;

struct jcb{ char

算法大作业——寻找多数元素

班级：0213051

学号：

(1)问题提出：

令A[1,2,…n]是一个整数序列，A中的整数a如果在A中出现的次数多于

，那么a称为多数元素。例如在序列1,3,2,3,3,4,3中，

3是多数元素，因为在7个元素中它出现了四次。有几个方法可以解决这个问题。蛮力方法是把每个元素和其他各个元素比较，并且对每个元素计数，如果某个元素的计数大于

，就可以断定它是多数元

素，否则在序列中就没有多数元素。但这样比较的次数是n(n-1)/2=Θ(

),这种方法的代价太昂贵了。比较有效的算法是对这些元素进

行排序，并且计算每个元素在序列中出现了多少次。这在最坏情况下的代价是Θ(n

).因为在最坏情况下，排序这一步需要Ω(n

元素，因为多数

) 。另外一种方法是寻找中间元素，就是第

元素在排序的序列中一定是中间元素。可以扫描这个序列来测试中间元素是否是多数元素。由于中间元素可以在Θ（n）时间内找到，这个方法要花费Θ（n）时间。

有一个漂亮的求解方法，它比较的次数要少得多，我们用归纳法导出这个算法，这个算法的实质是基于下面的观察结论。 观察结论：在原序列中去除两个不同的元素后，原序列的多数元素在新序列中还是多数元素。

这个结论支持下述寻找多数