电子科技大学
实验报告
学生姓名：满博学号：2823103017 指导教师：罗惠琼
一、实验室名称：软件实验室A2412
二、实验项目名称：进程调度算法的设计（短进程优先调度SPF）
三、实验原理：
在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。

对调度的处理又都可采用不同的调度方式和调度算法。

调度算法是指：根据系统的资源分配策略所规定的资源分配算法。

短进程优先调度算法是指对短进程优先调度的算法，它是从后备队列中选择一个或者若干个进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。

四、实验目的：
通过实现SPF算法深入了解进程调度机制，加深理解。

五、实验内容：
1. 编写SPF算法：
●进程通过定义一个进程控制块的数据结构（PCB）来表示；
●每个进程需要赋予进程ID、进程到达时间、进程需要运行的总时间的属性；
2. 调试无误后运行；
3. 输入需要请求调入的页号；
4. 查看执行结果，根据执行结果判断实验是否成功；
六、实验器材（设备、元器件）：
1．基本环境要求
①宽敞整洁专用实验室
②必备的基本实验工具
2．最低设备要求
①计算机CPU不小于800MHZ；
②计算机内存不小于128M；
3．软硬件要求
①实验平台Visual c++ 6.0
七、实验步骤：
代码如下：
#include<stdio.h>
#define n 5
#define num 5
#define max 65535
typedef struct pro
{
int PRO_ID;
int arrive_time;
int sum_time;
int flag;
}Pro;
//整数排序
int bubble(int temp[])
{
int i,j,tem=0;
for(i=1;i<num;i++)
{
int lastX=1;
for(j=0;j<num-i;j++)
{
if(temp[j]>temp[j+1])
{
tem=temp[j];
temp[j]=temp[j+1];
temp[j+1]=tem;
lastX=0;
}
}
if(lastX==1) break;
}
return temp[0];
}
//进程排序
Pro bubble(Pro p[])
{
int i,j;
Pro temp={0};
Pro s[num];
for(i=0;i<num;i++){
s[i]=p[i];
}
for(i=1;i<num;i++)
{
int lastX=1;
for(j=0;j<num-i;j++)
{
if(s[j].sum_time>s[j+1].sum_time)
{
temp=s[j];
s[j]=s[j+1];
s[j+1]=temp;
lastX=0;
}
}
if(lastX==1) break;
}
return s[0];
}
void SPF(int p)
{
if(n>0)
{
int i,j,k,l,tc=0;
Pro seq[n];
Pro temp_seq[n];
printf("短进程优先调度算法SPF\n");
printf("请依次输入5个进程的进程号、到达时间和执行时间\n");
printf("成员变量用逗号隔开；进程间用回车隔开\n");
for(i=0;i<n;i++){
scanf("%d,%d,%d",&seq[i].PRO_ID,&seq[i].arrive_time,&seq[i].sum_time);
}
printf("调度顺序是：\n");
//初始化tc
int temp[num];
for(i=0;i<num;i++)
{
temp[i]=seq[i].arrive_time;
}
tc=bubble(temp);//tc是断点啊
//flag 表示对应i的pro的队列情况
//-1表示未进入过队列，0表示在队列中，1表示被清除了for(i=0;i<n;i++){
seq[i].flag=-1;
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(seq[j].flag!=1&&seq[j].arrive_time<=tc){
seq[j].flag=0;
}
}
for(j=0;j<n;j++){
temp_seq[j]=seq[j];
if(seq[j].flag!=0){
temp_seq[j].sum_time=max;
}
}
l=bubble(temp_seq).PRO_ID;
for(j=0;j<n;j++){
if(l==seq[j].PRO_ID){
k=j;
}
}
tc=tc+bubble(temp_seq).sum_time;
seq[k].flag=1;
printf("%d",l);
}
printf("\n");
}
}
void main()
{
SPF(n);
}
结果截图：
实例1
实例2
八、实验数据及结果分析：
/*
算法详细设计：
进程（PRO_ID，arrive_time，sum_time，flag）
1．比较停顿时间点，小于等于当前停顿时间点tc的到达时间点seq[i].arrive_time的进程seq[i]的PRO_ID加入到队列中；
2．在现有更新后的队列temp_seq中，用bubble选出最短执行时间的进程的PRO_ID；
3．选进程（算法核心L=bubble（int temp[]）），更新下一个停顿时间点tc 就是当前停顿时间点tc+L的执行时间sum_time；
4．将X踢出队列。

seq[i].flag，-1表示未进入过队列，0表示在队列中，1表示被踢了；
设当前时间点为tc，对pro.arr<=tc且seq[i].flag！=1的seq[i]，将seq[i].flag 标记为0；
创建临时变量temp_seq[]=seq[];
对所有flag[i]==0的temp_seq[i]，bubble(temp_seq)，返回的是Pro进程类型。

将tc更新，tc==tc+ bubble(temp_seq).sum_time;
找出该bubble(temp_seq)对应的原来seq[i]，标记为1。

这步最容易错，注意下标和PRO_ID并不是一回事。

怎么选第一个tc：设tc=0；如果出现最小的pro.arr不是0的话，那么
初始化：bubble seq[i].arrive_time tc=min{ seq[i].arrive_time }
Bubble么，就不用我说了。

*/
使用了教材上的例子和自己的实例，结果与笔算相同。

九、实验结论：
成功的实现了短进程优先调度算法（SPF），实验结果验证无误。

十、总结及心得体会：
通过本次试验，我熟悉了短进程优先调度算法的原理，代码实现了其功能，收获很大。

十一、对本实验过程及方法、手段的改进建议：
若C++编程可用函数重载，避免bubble因参数不同造成的代码无法重用。

报告评分：
指导教师签字：。