课 程 设 计
题 目
学 院
专 业
班 级
姓 名
指导教师
进程调度模拟设计——优先级法、最高响应比优先调度算法 计算机科学与技术
吴利军
2013 年 1 月 15 日
课程设计任务书
学生姓名：
指导教师：吴利军 工作单位： 计算机科学与技术学院 题 目: 进程调度模拟设计——优先级法、最高响应比优先调度算法 初始条件：
1．预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。
2．实践准备：掌握一种计算机高级语言的使用。
要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
1．模拟进程调度，能够处理以下的情形：
⑴ 能够选择不同的调度算法（要求中给出的调度算法）；
⑵ 能够输入进程的基本信息，如进程名、优先级、到达时间和运行时间等； ⑶ 根据选择的调度算法显示进程调度队列；
⑷ 根据选择的调度算法计算平均周转时间和平均带权周转时间。
2．设计报告内容应说明：
⑴ 需求分析；
⑵ 功能设计（数据结构及模块说明）；
⑶ 开发平台及源程序的主要部分；
⑷ 测试用例，运行结果与运行情况分析；
⑸ 自我评价与总结：
i）你认为你完成的设计哪些地方做得比较好或比较出色；
ii）什么地方做得不太好，以后如何改正；
iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）； iv）完成本题是否有其他方法（如果有，简要说明该方法）；
时间安排：
设计安排一周：周1、周2：完成程序分析及设计。
周2、周3：完成程序调试及测试。
周4、周5：验收、撰写课程设计报告。
（注意事项：严禁抄袭，一旦发现，一律按0分记）
指导教师签名： 年 月 日 系主任（或责任教师）签名： 年 月 日
进程调度模拟设计
优先级法、最高响应比优先调度算法
1．设计目的与实现功能
模拟进程调度，使程序能够完成：能够输入若干进程，包括进程的一些基本信息，如进程名、优先级、到达时间和运行时间等，选择不同的调度算法（优先级法或者最高响应比法），选择算法后，根据选择的调度算法显示进程调度队列；根据选择的调度算法计算平均周转时间和平均带权周转时间。
2．需求分析
2.1实验原理
最高响应比优先算法（HRN）：最高响应比是对先来先服务和最短进程优先法德一种综合平衡。HRN调度策略同时考虑每个进程的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的进程投入执行。 响应比R定义如下：
R=(W+T)/T=1+W/T
其中T为该进程的估计需要的执行时间，W为进程在后备状态队列的等待时间。每当要进行进程调度是，系统计算每个进程的响应比，选择其中R最大者投入执行。
优先级法：系统和用户按某种原则为进程制定一个优先级来表示该进程所享有的调度优先权。根据优先级的高低来对进程加以调度。
3. 数据结构
3.1主要结构及函数
struct timer //时间类型
{
byte hour;
byte minute;
}
typedef struct process//进程结构
{
char name[20]; //进程名
byte rank; //进程等级
timer time_in; //进程到达的时间
byte use_time; //运行需要消耗时间
timer time_start;//开始运行时刻
byte used_time; //已经运行的时间
timer time_end; //进程结束时刻
bool flag; //进程运行完成标志，完成true
}process,*process_ptr;
bool search(process process_n[])//查看是否所有进程都执行完
bool compare(timer time1,timer time2) //比较两个时间类型的大小
void paixv(process process_n[])//进程按优先级有大到小排序，规定rank越小优先级越高 void printf_last(process process_n[])//打印结果
void grade_first(process process_n[])//抢占式优先级调度算法
void HRN(process process_n[])//最高响应比优先算法
优先级调度的思路：
这里设计的是一个抢占式优先级调度设一个标志位作为时钟，时间一分分地走，通过每次扫描各个进程的状态，确定这一分钟该哪个进程执行，在这之间要记录某个进程的开始时间、已运行时间和结束最后，到每个进程都执行过，完成优先级调度。
最高响应比优先调度的思路：
每次调度前都计算每个作业的响应比，从而选择其中最大者投入运行。
3.2流程图
4. 源程序的主要部分
4．1查看是否所有进程都执行完
bool search(process process_n[])
{
for(int i=0;i
{
if(process_n[i].flag==false)
{
return false;
}
}
return true;
}
//比较两个时间类型的大小
bool compare(timer time1,timer time2)
{
if(time1.hour>time2.hour)
{
return true;
}
else if(time1.hour==time2.hour&&time1.minute>=time2.minute)
{
return true;
}
else
{
return false;
}
}
4．2进程按优先级有大到小排序，规定rank越小优先级越高
void paixv(process process_n[])
{
int i,j;
process temp;
for(i=0;i
{
for(j=0;j
{
if(process_n[j].rank>process_n[j+1].rank)
{
temp=process_n[j];
process_n[j]=process_n[j+1];
process_n[j+1]=temp;
}
}
}
}
4.3打印结果
void printf_last(process process_n[])
{
float a[MAX];//记录每个进程的周转时间
float b[MAX];//记录每个进程的带权周转时间
float out_a=0;
float out_b=0;
printf("进程名 进程级别 提交时间 运行时间 开始时间 完成时间 周转时间 带权周转时间\n");
for(int i=0;i
{
a[i]=(float)((process_n[i].time_end.hour-process_n[i].time_in.hour)*60+process_n[i].time_end.minute-process_n[i].time_in.minute);
b[i]=a[i]/process_n[i].use_time;
out_a+=a[i];
out_b+=b[i];
printf("%4s\t%4d\t",process_n[i].name,process_n[i].rank);
printf("");
if(process_n[i].time_in.hour
{
printf("0%d",process_n[i].time_in.hour);
}
else
{
printf("%d",process_n[i].time_in.hour);
}
printf(":");
if(process_n[i].time_in.minute
{
printf("0%d\t",process_n[i].time_in.minute);
}
else
{
printf("%d\t",process_n[i].time_in.minute);
}
/////////////////////////////////////////////////
/////////////////////////////////////////////////
printf("%4d\t",process_n[i].use_time);
/////////////////////////////////////////////////
/////////////////////////////////////////////////
if(process_n[i].time_start.hour
{
printf("0%d",process_n[i].time_start.hour);
}
else
{
printf("%4d",process_n[i].time_start.hour);
}
printf(":");
if(process_n[i].time_start.minute
{
printf("0%d\t",process_n[i].time_start.minute);
}
else
{
printf("%d\t",process_n[i].time_start.minute);
}
/////////////////////////////////////////////////
printf("");
/////////////////////////////////////////////////
if(process_n[i].time_end.hour
{
printf("0%d",process_n[i].time_end.hour);
}
else
{
printf("%d",process_n[i].time_end.hour);
}
printf(":");
if(process_n[i].time_end.minute
{
printf("0%d\t",process_n[i].time_end.minute);
}
else
{
printf("%d\t",process_n[i].time_end.minute);
}
///////////////////////////////////////////////
///////////////////////////////////////////////
printf("%.2f\t",a[i]);
printf("%.2f\n",b[i]);
}
out_a=out_a/n;
out_b=out_b/n;
printf("平均周转时间为：%f\n",out_a);
} printf("平均带权周转时间为：%f\n",out_b);
4.4抢占式优先级调度算法
/********************************************
* 抢占式优先级调度算法 *
********************************************/
void grade_first(process process_n[])
{
int i;
bool flag;//标志位，用于控制当前时间
while(1)
{
flag=true;
for(i=0;i
{
if(compare(current,process_n[i].time_in)&&!(process_n[i].flag))
{
flag=false;
//获取开始运行时间
if(process_n[i].time_start.hour==0&&process_n[i].time_start.minute==0) {
process_n[i].time_start=current;
}
//记录进程已经运行的时间
process_n[i].used_time++;
//时钟继续一分一分走
current.minute++;
if(current.minute==60)
{
current.hour+=1;
current.minute=0;
}
//运行完成后，记录完成时间 if(process_n[i].used_time==process_n[i].use_time) { process_n[i].flag=true; process_n[i].time_end=current; } break; } } if(flag) { current.minute++;
if(current.minute==60)
{
current.hour+=1;
current.minute=0;
}
}
if(search(process_n))
{
break;
}
else
{
continue;
}
}
}
4.5最高响应比优先算法
/*****************************************************
* 最高响应比优先算法 *
*****************************************************/
void HRN(process process_n[])
{
float flag_xiangxi[MAX];//记录进程的响应比
//找到最小的时间作为当前基准时间
current=process_n[0].time_in;
for(int i=1;i
{
if(compare(current,process_n[i].time_in))
{
current=process_n[i].time_in;
}
}
///////////////////////////////////////
while(!search(process_n))
{
float temp=0;
for(int i=0;i
{
if(compare(current,process_n[i].time_start)&&process_n[i].flag==false) {
flag_xiangxi[i]=((float)(current.hour-process_n[i].time_in.hour)*60+current.minute-process_n[i].time_in.minute)/process_n[i].use_time;
if(flag_xiangxi[i]>temp)
{
temp=flag_xiangxi[i];
}
}
}
for(int j=0;j
{
if(compare(current,process_n[j].time_start)&&process_n[j].flag==false&&temp==flag_xiangxi[j]) {
process_n[j].time_start=current;
current.hour=(current.hour*60+current.minute+process_n[j].use_time)/60;
current.minute=(current.hour*60+current.minute+process_n[j].use_time)%60; process_n[j].time_end=current;
process_n[j].flag=true;
break;
}
}
}
}
4.6主函数
int main()
{
int one_two;
process process_n[MAX];
process process_n_other[MAX];
char time_string[10];
char FLAG_exit;
while(1)
{
printf("请输入进程个数：");
scanf("%d",&n);
fflush(stdin);
for(int i=0;i
{
printf("请输入第%d个进程的参数：\n",(i+1));
printf("进程名:");
scanf("%s",process_n[i].name);
fflush(stdin);
printf("进程等级:");
scanf("%d",&(process_n[i].rank));
fflush(stdin);
printf("提交时间:");
scanf("%s",&time_string);
fflush(stdin);
while(strlen(time_string)!=5)
{
printf("输入格式不符合要求！请重新输入...\n");
printf("提交时间:");
scanf("%s",&time_string);
fflush(stdin);
}
int a=(time_string[0]-48)*10+time_string[1]-48;
while(a>24)
{
printf("输入格式不符合在24小时内的要求！请重新输入...\n");
printf("提交时间:");
scanf("%s",&time_string);
fflush(stdin);
a=(time_string[0]-48)*10+time_string[1]-48;
}
process_n[i].time_in.hour=a;
a=(time_string[3]-48)*10+time_string[4]-48;
while(a>=60)
{
printf("输入格式不符合在60分钟内的要求！请重新输入...\n");
printf("提交时间:");
scanf("%s",&time_string);
fflush(stdin);
a=(time_string[3]-48)*10+time_string[4]-48;
}
process_n[i].time_in.minute=a;
printf("执行时间:");
scanf("%d",&(process_n[i].use_time));
fflush(stdin);
process_n[i].flag=false;
}
L1: printf("请你选择你将采用的调度算法:\n");
printf("1--优先级调度\n2--最高响应比优先算法\n");
printf("如果想退出程序请输入其他\n");
scanf("%d",&one_two);
fflush(stdin);
if(one_two==1)
{
current.hour=0;
current.minute=0;
for(i=0;i
{
process_n_other[i]=process_n[i];
}
paixv(process_n_other);
grade_first(process_n_other);
printf_last(process_n_other);
printf("是否退出程序？退出请输入y\n");
scanf("%c",&FLAG_exit);
fflush(stdin);
if(FLAG_exit=='y'||FLAG_exit=='Y')
return 0;
else
goto L1;
}
else if(one_two==2)
{
current.hour=0;
current.minute=0;
for(i=0;i
{
process_n_other[i]=process_n[i];
}
HRN(process_n_other);
printf_last(process_n_other);
printf("是否退出程序？退出请输入y\n");
scanf("%c",&FLAG_exit);
fflush(stdin);
if(FLAG_exit=='y'||FLAG_exit=='Y')
return 0;
else
goto L1;
}
else
{
return 0;
}
}
return 0;
}
5．测试
输入测试用例：
名称 优先级 到达时间 运行时间（分）
A 2 12:35 30
B 3 12:20 25
C 4 12:39 20
D 1 12:40 22
1. 优先级算法
分析如下：
第3级别B进程开始运行，但由于是抢占式的，在12:35时，也就是B运行15分钟后，有第2级别的A进程到来，A只运行5分钟后，D到来，由于D是最高级别，D可以运行完，此时是13:02，A继续进行25分钟，完成A，之后B再运行10分钟，完成B，最后运行C。
2. 优先级算法
分析如下：
B进程先到，所以先把B进程完成，也就到时间12:45，此时A、C、D进程都到了， 如果运行A:
R=(W+T)/T=1+W/T=（12:45+30-12:35）/30=4/3=1.333
如果运行C:
R=(W+T)/T=1+W/T=（12:45+20-12:39）/20=13/10=1.3
如果运行D:
R =(W+T)/T=1+W/T=（12:45+22-12:40）/22=27/22=1.22
由于A的响应比最大，所以先运行A,
同理，A运行之后
如果运行C：
R=(W+T)/T=1+W/T=（13:15+20-12:39）/20=14/5=2.8
如果运行D:
R=(W+T)/T=1+W/T=（13:15+22-12:40）/22=57/22=2.59
故运行C，最后运行D
6.自我评价与总结
6.1自我认为出色的地方
在这次的操作系统课程设计中，我设计的进程的结构是合理的，其中进程结束与否这个标志位对程序的运行起到了很大的作用，结构如下：
typedef struct process//进程结构
{
char name[20]; //进程名
byte rank; //进程等级
timer time_in; //进程到达的时间
byte use_time; //运行需要消耗时间
timer time_start;//开始运行时刻
byte used_time; //已经运行的时间
timer time_end; //进程结束时刻
bool flag; //进程运行完成标志，完成true
}process,*process_ptr;
优先级调度的算法实现过程中，取一个参考时钟对实现抢占式的优先级起到了很大的作用，原本想实现非抢占式的优先级调度，后来想挑战一下自己，就选择抢占式的算法，在实现过程中遇到一些问题，但很好的锻炼了自己。
在最高响应比优先采用另外一个数组flag_xainxi[MAX]来记录每个进程响应比，通过比较每个响应比的大小确定下一个执行的进程，没有在进程中的结构体中添加字段来反映响应比，简化了结构。
6.2不足之处
采用数组形式实现的，输入的进程的个数是有限的，不能动态的增加，可以采用链表的形式，结合malloc，realloc函数来实现动态增加进程。本程序也使用大量的for循环，不宜大数据量的计算，影响了程序的运行速度，以后要仔细观察，进行代码优化。
6.3总结
通过这次课程设计，巩固了知识，对进程调度的理解更加深刻，同时也对C语言的基本语言有了重新的认识，开阔了自己的思维。这些经典的进程调度算法很值得我自己动手去模拟、去实现，所以在做了这两个进程调度算法后，我又去模拟实现了磁盘的电梯调度和最短时间优先调度算法以及页式调度中的最近最久未使用（LRU）算法，感觉模拟这些并不困难，但在操作系统中实现这些算法就涉及的是真正的进程和硬件设备了，去实现一个操作系统还
是比较难的。但这些模拟让我明白操作系统怎么管理进程运行，管理内存空间的，也让我明白了自己的不足，为以后的深入学习奠定了基础。
7、源码
//优先级法、最高响应比优先调度算法
#include
#include
#include
typedef unsigned char byte;
#define MAX 20
//时间类型
struct timer
{
};
timer current; //标志当前时间
int n;
//输入的进程数 //标志当前选择的是抢占式优先--1， //还是最高响应比--2 byte hour; byte minute; byte FLAG;
//进程结构
typedef struct process
{
char name[20]; //进程名 byte rank; //进程等级
timer time_in; //进程到达的时间
byte use_time; //运行需要消耗时间 timer time_start;//开始运行时刻 byte used_time; //已经运行的时间 timer time_end; //进程结束时刻 bool flag; //进程运行完成标志，完成true
}process,*process_ptr;
//查看是否所有进程都执行完
bool search(process process_n[])
{
for(int i=0;i
}
return true;
//比较两个时间类型的大小
bool compare(timer time1,timer time2)
{
}
//进程按优先级有大到小排序
//规定rank越小优先级越高
void paixv(process process_n[])
{
int i,j; process temp; for(i=0;itime2.hour) { } else if(time1.hour==time2.hour&&time1.minute>=time2.minute) { } else { } return false; return true; return true;
if(process_n[j].rank>process_n[j+1].rank)
{
temp=process_n[j];
process_n[j]=process_n[j+1];
process_n[j+1]=temp;
}
//打印结果
void printf_last(process process_n[])
{ } } }
float a[MAX];//记录每个进程的周转时间
float b[MAX];//记录每个进程的带权周转时间
float out_a=0;
float out_b=0;
printf("进程名 进程级别 提交时间 运行时间 开始时间 完成时间 周转时间 带权周转时间\n"); for(int i=0;i
a[i]=(float)((process_n[i].time_end.hour-process_n[i].time_in.hour)*60+process_n[i].time_end.minute-process_n[i].time_in.minute);
b[i]=a[i]/process_n[i].use_time; out_a+=a[i]; out_b+=b[i]; printf("%4s\t%4d\t",process_n[i].name,process_n[i].rank); printf(""); if(process_n[i].time_in.hour
/////////////////////////////////////////////////
///////////////////////////////////////////////// if(process_n[i].time_start.hour
} printf("%4d",process_n[i].time_start.hour); printf(":"); if(process_n[i].time_start.minute
///////////////////////////////////////////////
}
/******************************************** out_a=out_a/n; out_b=out_b/n; printf("平均周转时间为：%f\n",out_a); printf("平均带权周转时间为：%f\n",out_b); /////////////////////////////////////////////// printf("%.2f\t",a[i]); printf("%.2f\n",b[i]); }
* 抢占式优先级调度算法 *
********************************************/
void grade_first(process process_n[])
{
int i;
bool flag;//标志位，用于控制当前时间
while(1)
{
flag=true; for(i=0;i
current.hour+=1;
} if(flag) { current.minute++; if(current.minute==60) { current.hour+=1; current.minute=0; } current.minute=0; } //运行完成后，记录完成时间 if(process_n[i].used_time==process_n[i].use_time) { } break; process_n[i].flag=true; process_n[i].time_end=current;
} } if(search(process_n)) { break; } else {
continue;
}
}
/*****************************************************
* 最高响应比优先算法 *
*****************************************************/
void HRN(process process_n[])
{
float flag_xiangxi[MAX];//记录进程的响应比 //找到最小的时间作为当前基准时间 current=process_n[0].time_in; for(int i=1;i
///////////////////////////////////////
while(!search(process_n)) { float temp=0; for(int i=0;i
[i].use_time;
if(flag_xiangxi[i]>temp) } { } temp=flag_xiangxi[i];
}
for(int j=0;j
if(compare(current,process_n[j].time_start)&&process_n[j].flag==false&&temp==flag_xiangxi[j]) }
{ }
process_n[j].time_start=current;
current.hour=(current.hour*60+current.minute+process_n[j].use_time)/60; current.minute=(current.hour*60+current.minute+process_n[j].use_time)%60; process_n[j].time_end=current; process_n[j].flag=true; break;
}
//主函数 int main() {
int one_two;
process process_n[MAX]; process process_n_other[MAX]; char time_string[10]; char FLAG_exit; while(1) {
printf("请输入进程个数："); scanf("%d",&n); fflush(stdin); for(int i=0;i
printf("请输入第%d个进程的参数：\n",(i+1)); printf("进程名:");
scanf("%s",process_n[i].name); fflush(stdin); printf("进程等级:");
scanf("%d",&(process_n[i].rank)); fflush(stdin); printf("提交时间:"); scanf("%s",&time_string); fflush(stdin);
while(strlen(time_string)!=5) {
printf("输入格式不符合要求！请重新输入...\n");
scanf("%s",&time_string); fflush(stdin); }
int a=(time_string[0]-48)*10+time_string[1]-48; while(a>24) {
printf("输入格式不符合在24小时内的要求！请重新输入...\n");
printf("提交时间:");
scanf("%s",&time_string); fflush(stdin);
a=(time_string[0]-48)*10+time_string[1]-48; }
process_n[i].time_in.hour=a;
a=(time_string[3]-48)*10+time_string[4]-48; while(a>=60) { }
process_n[i].time_in.minute=a;
printf("输入格式不符合在60分钟内的要求！请重新输入...\n"); printf("提交时间:"); scanf("%s",&time_string); fflush(stdin);
a=(time_string[3]-48)*10+time_string[4]-48;
printf("执行时间:");
}
printf("请你选择你将采用的调度算法:\n"); scanf("%d",&(process_n[i].use_time)); fflush(stdin);
process_n[i].flag=false;
L1:
printf("1--优先级调度\n2--最高响应比优先算法\n"); printf("如果想退出程序请输入其他\n"); scanf("%d",&one_two); fflush(stdin);
if(one_two==1)
{
current.hour=0; current.minute=0; for(i=0;i
process_n_other[i]=process_n[i];
paixv(process_n_other);
grade_first(process_n_other);
printf_last(process_n_other);
printf("是否退出程序？退出请输入y\n"); scanf("%c",&FLAG_exit); fflush(stdin);
if(FLAG_exit=='y'||FLAG_exit=='Y') else }
else if(one_two==2) {
current.hour=0; goto L1; return 0;
current.minute=0;
for(i=0;i
process_n_other[i]=process_n[i];
HRN(process_n_other); }
printf_last(process_n_other);
printf("是否退出程序？退出请输入y\n"); scanf("%c",&FLAG_exit); fflush(stdin);
if(FLAG_exit=='y'||FLAG_exit=='Y')
return 0;
else } else { } }
return 0;
return 0; goto L1;
//磁盘调度 #include #include #define MAX 20
int run_number; //记录实际柱面数 int run[MAX]; //记录每道的磁道序列 int run_jilu[MAX]; int daoshu;
bool FLAG_USED[MAX];
int abs_LONGTH[MAX];
int abs_number(int a,int b) { }
int cmp(const void *a,const void *b) { }
//电梯算法，当flag=false向下走
void SCAN(int run[],int run_jilu[],int run_begin,bool flag) {
int jilu,j; bool flag_t=false;
//如果开始位置在序列中就继续执行，否则加入其中 for(int i=0;i
if(i==run_number) {
run_number+=1; } //快排序
qsort(run,run_number,sizeof(int),cmp); for(i=0;i
if(run_begin==run[i]) { }
jilu=i; break;
run[run_number-1]=run_begin; if(run_begin==run[i]) { }
break; int x=*(int *)a; int y=*(int *)b; return (xy?1:0); if(a>b) else
return b-a; return a-b;
if(flag==false) {
j=0;
for(i=jilu;i>=0;i--) {
run_jilu[j]=run[i]; }
if(i
for(i=jilu+1;i
j++;
run_jilu[j]=run[i]; }
if(flag==true) {
j=0;
for(i=jilu;i
if(i
for(i=jilu-1;i>=0;i--) { } }
run_jilu[j]=run[i]; j++;
run_jilu[j]=run[i]; j++;
}
daoshu=run_begin-run[0]+run[run_number-1]-run[0];
j++; }
daoshu=run[run_number-1]-run_begin+run[run_number-1]-run[0]; } } //
bool end_not(bool a[]) {
for(int i=0;i
}
{ }
return true;
if(a[i]==false)
return false;
//最短寻道时间算法
void SSTF(int run[],int run_jilu[],int run_begin) {
int jilu,temp,flag; flag=0;
run_jilu[flag]=run_begin; daoshu=0;
//如果开始位置在序列中就继续执行，否则加入其中
for(int i=0;i
if(i==run_number) { }
for(i=0;i
for(i=0;i
FLAG_USED[jilu]=true; //当没走完时
while(!end_not(FLAG_USED)) {
for(int j=0;j
if(run_begin==run[i]) { }
jilu=i; break; FLAG_USED[i]=false; run_number+=1;
run[run_number-1]=run_begin; if(run_begin==run[i]) { }
break;
abs_LONGTH[j]=abs_number(run_begin,run[j]);
for(j=0;j
if(FLAG_USED[j]==false) { }
temp=abs_LONGTH[j]; break;
}
for(i=0;i
for(i=0;i
if(temp==abs_LONGTH[i]&&FLAG_USED[i]==false) {
run_begin=run[i];
flag++;
{ }
if(temp>abs_LONGTH[i]&&FLAG_USED[i]==false)
temp=abs_LONGTH[i];
run_jilu[flag]=run_begin; }
int main() {
int run_begin,as,at; bool flag;
printf("请输入柱面数:"); scanf("%d",&run_number); printf("请输入各道磁道数\n"); }
for(flag=0;flag
daoshu+=abs_number(run_jilu[flag+1],run_jilu[flag]); }
}
FLAG_USED[i]=true; break;
for(int i=0;i
{ }
printf("请输入开始磁道数:"); scanf("%d",&run_begin);
printf("请选择寻道方式(1--电梯算法，2--最短寻道)"); scanf("%d",&at); while(at!=1&&at!=2) {
printf("请选择寻道方式(1--电梯算法，2--最短寻道)"); } if(at==1) {
printf("请输入走向（1--上，2——下）:"); scanf("%d",&as);
scanf("%d",&at); scanf("%d",&run[i]);
while(as!=1&&as!=2)
{
printf("请输入走向（1--上，2——下）:"); scanf("%d",&as); }
if(as==1) {
flag=true;
} if(as==2) {
flag=false;
}
SCAN(run,run_jilu,run_begin,flag);
} if(at==2) { }
SSTF(run,run_jilu,run_begin);
printf("走道次序:"); for(i=0;i
printf("\n走过总道数:%d\n",daoshu); }
return 0;
printf("%d\t",run_jilu[i]);
本科生课程设计成绩评定表
分）、
及格（60-69分）、60分以下为不及格
指导教师签名：
2013 年 月 日
课 程 设 计
题 目
学 院
专 业
班 级
姓 名
指导教师
进程调度模拟设计——优先级法、最高响应比优先调度算法 计算机科学与技术
吴利军
2013 年 1 月 15 日
课程设计任务书
学生姓名：
指导教师：吴利军 工作单位： 计算机科学与技术学院 题 目: 进程调度模拟设计——优先级法、最高响应比优先调度算法 初始条件：
1．预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。
2．实践准备：掌握一种计算机高级语言的使用。
要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
1．模拟进程调度，能够处理以下的情形：
⑴ 能够选择不同的调度算法（要求中给出的调度算法）；
⑵ 能够输入进程的基本信息，如进程名、优先级、到达时间和运行时间等； ⑶ 根据选择的调度算法显示进程调度队列；
⑷ 根据选择的调度算法计算平均周转时间和平均带权周转时间。
2．设计报告内容应说明：
⑴ 需求分析；
⑵ 功能设计（数据结构及模块说明）；
⑶ 开发平台及源程序的主要部分；
⑷ 测试用例，运行结果与运行情况分析；
⑸ 自我评价与总结：
i）你认为你完成的设计哪些地方做得比较好或比较出色；
ii）什么地方做得不太好，以后如何改正；
iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）； iv）完成本题是否有其他方法（如果有，简要说明该方法）；
时间安排：
设计安排一周：周1、周2：完成程序分析及设计。
周2、周3：完成程序调试及测试。
周4、周5：验收、撰写课程设计报告。
（注意事项：严禁抄袭，一旦发现，一律按0分记）
指导教师签名： 年 月 日 系主任（或责任教师）签名： 年 月 日
进程调度模拟设计
优先级法、最高响应比优先调度算法
1．设计目的与实现功能
模拟进程调度，使程序能够完成：能够输入若干进程，包括进程的一些基本信息，如进程名、优先级、到达时间和运行时间等，选择不同的调度算法（优先级法或者最高响应比法），选择算法后，根据选择的调度算法显示进程调度队列；根据选择的调度算法计算平均周转时间和平均带权周转时间。
2．需求分析
2.1实验原理
最高响应比优先算法（HRN）：最高响应比是对先来先服务和最短进程优先法德一种综合平衡。HRN调度策略同时考虑每个进程的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的进程投入执行。 响应比R定义如下：
R=(W+T)/T=1+W/T
其中T为该进程的估计需要的执行时间，W为进程在后备状态队列的等待时间。每当要进行进程调度是，系统计算每个进程的响应比，选择其中R最大者投入执行。
优先级法：系统和用户按某种原则为进程制定一个优先级来表示该进程所享有的调度优先权。根据优先级的高低来对进程加以调度。
3. 数据结构
3.1主要结构及函数
struct timer //时间类型
{
byte hour;
byte minute;
}
typedef struct process//进程结构
{
char name[20]; //进程名
byte rank; //进程等级
timer time_in; //进程到达的时间
byte use_time; //运行需要消耗时间
timer time_start;//开始运行时刻
byte used_time; //已经运行的时间
timer time_end; //进程结束时刻
bool flag; //进程运行完成标志，完成true
}process,*process_ptr;
bool search(process process_n[])//查看是否所有进程都执行完
bool compare(timer time1,timer time2) //比较两个时间类型的大小
void paixv(process process_n[])//进程按优先级有大到小排序，规定rank越小优先级越高 void printf_last(process process_n[])//打印结果
void grade_first(process process_n[])//抢占式优先级调度算法
void HRN(process process_n[])//最高响应比优先算法
优先级调度的思路：
这里设计的是一个抢占式优先级调度设一个标志位作为时钟，时间一分分地走，通过每次扫描各个进程的状态，确定这一分钟该哪个进程执行，在这之间要记录某个进程的开始时间、已运行时间和结束最后，到每个进程都执行过，完成优先级调度。
最高响应比优先调度的思路：
每次调度前都计算每个作业的响应比，从而选择其中最大者投入运行。
3.2流程图
4. 源程序的主要部分
4．1查看是否所有进程都执行完
bool search(process process_n[])
{
for(int i=0;i
{
if(process_n[i].flag==false)
{
return false;
}
}
return true;
}
//比较两个时间类型的大小
bool compare(timer time1,timer time2)
{
if(time1.hour>time2.hour)
{
return true;
}
else if(time1.hour==time2.hour&&time1.minute>=time2.minute)
{
return true;
}
else
{
return false;
}
}
4．2进程按优先级有大到小排序，规定rank越小优先级越高
void paixv(process process_n[])
{
int i,j;
process temp;
for(i=0;i
{
for(j=0;j
{
if(process_n[j].rank>process_n[j+1].rank)
{
temp=process_n[j];
process_n[j]=process_n[j+1];
process_n[j+1]=temp;
}
}
}
}
4.3打印结果
void printf_last(process process_n[])
{
float a[MAX];//记录每个进程的周转时间
float b[MAX];//记录每个进程的带权周转时间
float out_a=0;
float out_b=0;
printf("进程名 进程级别 提交时间 运行时间 开始时间 完成时间 周转时间 带权周转时间\n");
for(int i=0;i
{
a[i]=(float)((process_n[i].time_end.hour-process_n[i].time_in.hour)*60+process_n[i].time_end.minute-process_n[i].time_in.minute);
b[i]=a[i]/process_n[i].use_time;
out_a+=a[i];
out_b+=b[i];
printf("%4s\t%4d\t",process_n[i].name,process_n[i].rank);
printf("");
if(process_n[i].time_in.hour
{
printf("0%d",process_n[i].time_in.hour);
}
else
{
printf("%d",process_n[i].time_in.hour);
}
printf(":");
if(process_n[i].time_in.minute
{
printf("0%d\t",process_n[i].time_in.minute);
}
else
{
printf("%d\t",process_n[i].time_in.minute);
}
/////////////////////////////////////////////////
/////////////////////////////////////////////////
printf("%4d\t",process_n[i].use_time);
/////////////////////////////////////////////////
/////////////////////////////////////////////////
if(process_n[i].time_start.hour
{
printf("0%d",process_n[i].time_start.hour);
}
else
{
printf("%4d",process_n[i].time_start.hour);
}
printf(":");
if(process_n[i].time_start.minute
{
printf("0%d\t",process_n[i].time_start.minute);
}
else
{
printf("%d\t",process_n[i].time_start.minute);
}
/////////////////////////////////////////////////
printf("");
/////////////////////////////////////////////////
if(process_n[i].time_end.hour
{
printf("0%d",process_n[i].time_end.hour);
}
else
{
printf("%d",process_n[i].time_end.hour);
}
printf(":");
if(process_n[i].time_end.minute
{
printf("0%d\t",process_n[i].time_end.minute);
}
else
{
printf("%d\t",process_n[i].time_end.minute);
}
///////////////////////////////////////////////
///////////////////////////////////////////////
printf("%.2f\t",a[i]);
printf("%.2f\n",b[i]);
}
out_a=out_a/n;
out_b=out_b/n;
printf("平均周转时间为：%f\n",out_a);
} printf("平均带权周转时间为：%f\n",out_b);
4.4抢占式优先级调度算法
/********************************************
* 抢占式优先级调度算法 *
********************************************/
void grade_first(process process_n[])
{
int i;
bool flag;//标志位，用于控制当前时间
while(1)
{
flag=true;
for(i=0;i
{
if(compare(current,process_n[i].time_in)&&!(process_n[i].flag))
{
flag=false;
//获取开始运行时间
if(process_n[i].time_start.hour==0&&process_n[i].time_start.minute==0) {
process_n[i].time_start=current;
}
//记录进程已经运行的时间
process_n[i].used_time++;
//时钟继续一分一分走
current.minute++;
if(current.minute==60)
{
current.hour+=1;
current.minute=0;
}
//运行完成后，记录完成时间 if(process_n[i].used_time==process_n[i].use_time) { process_n[i].flag=true; process_n[i].time_end=current; } break; } } if(flag) { current.minute++;
if(current.minute==60)
{
current.hour+=1;
current.minute=0;
}
}
if(search(process_n))
{
break;
}
else
{
continue;
}
}
}
4.5最高响应比优先算法
/*****************************************************
* 最高响应比优先算法 *
*****************************************************/
void HRN(process process_n[])
{
float flag_xiangxi[MAX];//记录进程的响应比
//找到最小的时间作为当前基准时间
current=process_n[0].time_in;
for(int i=1;i
{
if(compare(current,process_n[i].time_in))
{
current=process_n[i].time_in;
}
}
///////////////////////////////////////
while(!search(process_n))
{
float temp=0;
for(int i=0;i
{
if(compare(current,process_n[i].time_start)&&process_n[i].flag==false) {
flag_xiangxi[i]=((float)(current.hour-process_n[i].time_in.hour)*60+current.minute-process_n[i].time_in.minute)/process_n[i].use_time;
if(flag_xiangxi[i]>temp)
{
temp=flag_xiangxi[i];
}
}
}
for(int j=0;j
{
if(compare(current,process_n[j].time_start)&&process_n[j].flag==false&&temp==flag_xiangxi[j]) {
process_n[j].time_start=current;
current.hour=(current.hour*60+current.minute+process_n[j].use_time)/60;
current.minute=(current.hour*60+current.minute+process_n[j].use_time)%60; process_n[j].time_end=current;
process_n[j].flag=true;
break;
}
}
}
}
4.6主函数
int main()
{
int one_two;
process process_n[MAX];
process process_n_other[MAX];
char time_string[10];
char FLAG_exit;
while(1)
{
printf("请输入进程个数：");
scanf("%d",&n);
fflush(stdin);
for(int i=0;i
{
printf("请输入第%d个进程的参数：\n",(i+1));
printf("进程名:");
scanf("%s",process_n[i].name);
fflush(stdin);
printf("进程等级:");
scanf("%d",&(process_n[i].rank));
fflush(stdin);
printf("提交时间:");
scanf("%s",&time_string);
fflush(stdin);
while(strlen(time_string)!=5)
{
printf("输入格式不符合要求！请重新输入...\n");
printf("提交时间:");
scanf("%s",&time_string);
fflush(stdin);
}
int a=(time_string[0]-48)*10+time_string[1]-48;
while(a>24)
{
printf("输入格式不符合在24小时内的要求！请重新输入...\n");
printf("提交时间:");
scanf("%s",&time_string);
fflush(stdin);
a=(time_string[0]-48)*10+time_string[1]-48;
}
process_n[i].time_in.hour=a;
a=(time_string[3]-48)*10+time_string[4]-48;
while(a>=60)
{
printf("输入格式不符合在60分钟内的要求！请重新输入...\n");
printf("提交时间:");
scanf("%s",&time_string);
fflush(stdin);
a=(time_string[3]-48)*10+time_string[4]-48;
}
process_n[i].time_in.minute=a;
printf("执行时间:");
scanf("%d",&(process_n[i].use_time));
fflush(stdin);
process_n[i].flag=false;
}
L1: printf("请你选择你将采用的调度算法:\n");
printf("1--优先级调度\n2--最高响应比优先算法\n");
printf("如果想退出程序请输入其他\n");
scanf("%d",&one_two);
fflush(stdin);
if(one_two==1)
{
current.hour=0;
current.minute=0;
for(i=0;i
{
process_n_other[i]=process_n[i];
}
paixv(process_n_other);
grade_first(process_n_other);
printf_last(process_n_other);
printf("是否退出程序？退出请输入y\n");
scanf("%c",&FLAG_exit);
fflush(stdin);
if(FLAG_exit=='y'||FLAG_exit=='Y')
return 0;
else
goto L1;
}
else if(one_two==2)
{
current.hour=0;
current.minute=0;
for(i=0;i
{
process_n_other[i]=process_n[i];
}
HRN(process_n_other);
printf_last(process_n_other);
printf("是否退出程序？退出请输入y\n");
scanf("%c",&FLAG_exit);
fflush(stdin);
if(FLAG_exit=='y'||FLAG_exit=='Y')
return 0;
else
goto L1;
}
else
{
return 0;
}
}
return 0;
}
5．测试
输入测试用例：
名称 优先级 到达时间 运行时间（分）
A 2 12:35 30
B 3 12:20 25
C 4 12:39 20
D 1 12:40 22
1. 优先级算法
分析如下：
第3级别B进程开始运行，但由于是抢占式的，在12:35时，也就是B运行15分钟后，有第2级别的A进程到来，A只运行5分钟后，D到来，由于D是最高级别，D可以运行完，此时是13:02，A继续进行25分钟，完成A，之后B再运行10分钟，完成B，最后运行C。
2. 优先级算法
分析如下：
B进程先到，所以先把B进程完成，也就到时间12:45，此时A、C、D进程都到了， 如果运行A:
R=(W+T)/T=1+W/T=（12:45+30-12:35）/30=4/3=1.333
如果运行C:
R=(W+T)/T=1+W/T=（12:45+20-12:39）/20=13/10=1.3
如果运行D:
R =(W+T)/T=1+W/T=（12:45+22-12:40）/22=27/22=1.22
由于A的响应比最大，所以先运行A,
同理，A运行之后
如果运行C：
R=(W+T)/T=1+W/T=（13:15+20-12:39）/20=14/5=2.8
如果运行D:
R=(W+T)/T=1+W/T=（13:15+22-12:40）/22=57/22=2.59
故运行C，最后运行D
6.自我评价与总结
6.1自我认为出色的地方
在这次的操作系统课程设计中，我设计的进程的结构是合理的，其中进程结束与否这个标志位对程序的运行起到了很大的作用，结构如下：
typedef struct process//进程结构
{
char name[20]; //进程名
byte rank; //进程等级
timer time_in; //进程到达的时间
byte use_time; //运行需要消耗时间
timer time_start;//开始运行时刻
byte used_time; //已经运行的时间
timer time_end; //进程结束时刻
bool flag; //进程运行完成标志，完成true
}process,*process_ptr;
优先级调度的算法实现过程中，取一个参考时钟对实现抢占式的优先级起到了很大的作用，原本想实现非抢占式的优先级调度，后来想挑战一下自己，就选择抢占式的算法，在实现过程中遇到一些问题，但很好的锻炼了自己。
在最高响应比优先采用另外一个数组flag_xainxi[MAX]来记录每个进程响应比，通过比较每个响应比的大小确定下一个执行的进程，没有在进程中的结构体中添加字段来反映响应比，简化了结构。
6.2不足之处
采用数组形式实现的，输入的进程的个数是有限的，不能动态的增加，可以采用链表的形式，结合malloc，realloc函数来实现动态增加进程。本程序也使用大量的for循环，不宜大数据量的计算，影响了程序的运行速度，以后要仔细观察，进行代码优化。
6.3总结
通过这次课程设计，巩固了知识，对进程调度的理解更加深刻，同时也对C语言的基本语言有了重新的认识，开阔了自己的思维。这些经典的进程调度算法很值得我自己动手去模拟、去实现，所以在做了这两个进程调度算法后，我又去模拟实现了磁盘的电梯调度和最短时间优先调度算法以及页式调度中的最近最久未使用（LRU）算法，感觉模拟这些并不困难，但在操作系统中实现这些算法就涉及的是真正的进程和硬件设备了，去实现一个操作系统还
是比较难的。但这些模拟让我明白操作系统怎么管理进程运行，管理内存空间的，也让我明白了自己的不足，为以后的深入学习奠定了基础。
7、源码
//优先级法、最高响应比优先调度算法
#include
#include
#include
typedef unsigned char byte;
#define MAX 20
//时间类型
struct timer
{
};
timer current; //标志当前时间
int n;
//输入的进程数 //标志当前选择的是抢占式优先--1， //还是最高响应比--2 byte hour; byte minute; byte FLAG;
//进程结构
typedef struct process
{
char name[20]; //进程名 byte rank; //进程等级
timer time_in; //进程到达的时间
byte use_time; //运行需要消耗时间 timer time_start;//开始运行时刻 byte used_time; //已经运行的时间 timer time_end; //进程结束时刻 bool flag; //进程运行完成标志，完成true
}process,*process_ptr;
//查看是否所有进程都执行完
bool search(process process_n[])
{
for(int i=0;i
}
return true;
//比较两个时间类型的大小
bool compare(timer time1,timer time2)
{
}
//进程按优先级有大到小排序
//规定rank越小优先级越高
void paixv(process process_n[])
{
int i,j; process temp; for(i=0;itime2.hour) { } else if(time1.hour==time2.hour&&time1.minute>=time2.minute) { } else { } return false; return true; return true;
if(process_n[j].rank>process_n[j+1].rank)
{
temp=process_n[j];
process_n[j]=process_n[j+1];
process_n[j+1]=temp;
}
//打印结果
void printf_last(process process_n[])
{ } } }
float a[MAX];//记录每个进程的周转时间
float b[MAX];//记录每个进程的带权周转时间
float out_a=0;
float out_b=0;
printf("进程名 进程级别 提交时间 运行时间 开始时间 完成时间 周转时间 带权周转时间\n"); for(int i=0;i
a[i]=(float)((process_n[i].time_end.hour-process_n[i].time_in.hour)*60+process_n[i].time_end.minute-process_n[i].time_in.minute);
b[i]=a[i]/process_n[i].use_time; out_a+=a[i]; out_b+=b[i]; printf("%4s\t%4d\t",process_n[i].name,process_n[i].rank); printf(""); if(process_n[i].time_in.hour
/////////////////////////////////////////////////
///////////////////////////////////////////////// if(process_n[i].time_start.hour
} printf("%4d",process_n[i].time_start.hour); printf(":"); if(process_n[i].time_start.minute
///////////////////////////////////////////////
}
/******************************************** out_a=out_a/n; out_b=out_b/n; printf("平均周转时间为：%f\n",out_a); printf("平均带权周转时间为：%f\n",out_b); /////////////////////////////////////////////// printf("%.2f\t",a[i]); printf("%.2f\n",b[i]); }
* 抢占式优先级调度算法 *
********************************************/
void grade_first(process process_n[])
{
int i;
bool flag;//标志位，用于控制当前时间
while(1)
{
flag=true; for(i=0;i
current.hour+=1;
} if(flag) { current.minute++; if(current.minute==60) { current.hour+=1; current.minute=0; } current.minute=0; } //运行完成后，记录完成时间 if(process_n[i].used_time==process_n[i].use_time) { } break; process_n[i].flag=true; process_n[i].time_end=current;
} } if(search(process_n)) { break; } else {
continue;
}
}
/*****************************************************
* 最高响应比优先算法 *
*****************************************************/
void HRN(process process_n[])
{
float flag_xiangxi[MAX];//记录进程的响应比 //找到最小的时间作为当前基准时间 current=process_n[0].time_in; for(int i=1;i
///////////////////////////////////////
while(!search(process_n)) { float temp=0; for(int i=0;i
[i].use_time;
if(flag_xiangxi[i]>temp) } { } temp=flag_xiangxi[i];
}
for(int j=0;j
if(compare(current,process_n[j].time_start)&&process_n[j].flag==false&&temp==flag_xiangxi[j]) }
{ }
process_n[j].time_start=current;
current.hour=(current.hour*60+current.minute+process_n[j].use_time)/60; current.minute=(current.hour*60+current.minute+process_n[j].use_time)%60; process_n[j].time_end=current; process_n[j].flag=true; break;
}
//主函数 int main() {
int one_two;
process process_n[MAX]; process process_n_other[MAX]; char time_string[10]; char FLAG_exit; while(1) {
printf("请输入进程个数："); scanf("%d",&n); fflush(stdin); for(int i=0;i
printf("请输入第%d个进程的参数：\n",(i+1)); printf("进程名:");
scanf("%s",process_n[i].name); fflush(stdin); printf("进程等级:");
scanf("%d",&(process_n[i].rank)); fflush(stdin); printf("提交时间:"); scanf("%s",&time_string); fflush(stdin);
while(strlen(time_string)!=5) {
printf("输入格式不符合要求！请重新输入...\n");
scanf("%s",&time_string); fflush(stdin); }
int a=(time_string[0]-48)*10+time_string[1]-48; while(a>24) {
printf("输入格式不符合在24小时内的要求！请重新输入...\n");
printf("提交时间:");
scanf("%s",&time_string); fflush(stdin);
a=(time_string[0]-48)*10+time_string[1]-48; }
process_n[i].time_in.hour=a;
a=(time_string[3]-48)*10+time_string[4]-48; while(a>=60) { }
process_n[i].time_in.minute=a;
printf("输入格式不符合在60分钟内的要求！请重新输入...\n"); printf("提交时间:"); scanf("%s",&time_string); fflush(stdin);
a=(time_string[3]-48)*10+time_string[4]-48;
printf("执行时间:");
}
printf("请你选择你将采用的调度算法:\n"); scanf("%d",&(process_n[i].use_time)); fflush(stdin);
process_n[i].flag=false;
L1:
printf("1--优先级调度\n2--最高响应比优先算法\n"); printf("如果想退出程序请输入其他\n"); scanf("%d",&one_two); fflush(stdin);
if(one_two==1)
{
current.hour=0; current.minute=0; for(i=0;i
process_n_other[i]=process_n[i];
paixv(process_n_other);
grade_first(process_n_other);
printf_last(process_n_other);
printf("是否退出程序？退出请输入y\n"); scanf("%c",&FLAG_exit); fflush(stdin);
if(FLAG_exit=='y'||FLAG_exit=='Y') else }
else if(one_two==2) {
current.hour=0; goto L1; return 0;
current.minute=0;
for(i=0;i
process_n_other[i]=process_n[i];
HRN(process_n_other); }
printf_last(process_n_other);
printf("是否退出程序？退出请输入y\n"); scanf("%c",&FLAG_exit); fflush(stdin);
if(FLAG_exit=='y'||FLAG_exit=='Y')
return 0;
else } else { } }
return 0;
return 0; goto L1;
//磁盘调度 #include #include #define MAX 20
int run_number; //记录实际柱面数 int run[MAX]; //记录每道的磁道序列 int run_jilu[MAX]; int daoshu;
bool FLAG_USED[MAX];
int abs_LONGTH[MAX];
int abs_number(int a,int b) { }
int cmp(const void *a,const void *b) { }
//电梯算法，当flag=false向下走
void SCAN(int run[],int run_jilu[],int run_begin,bool flag) {
int jilu,j; bool flag_t=false;
//如果开始位置在序列中就继续执行，否则加入其中 for(int i=0;i
if(i==run_number) {
run_number+=1; } //快排序
qsort(run,run_number,sizeof(int),cmp); for(i=0;i
if(run_begin==run[i]) { }
jilu=i; break;
run[run_number-1]=run_begin; if(run_begin==run[i]) { }
break; int x=*(int *)a; int y=*(int *)b; return (xy?1:0); if(a>b) else
return b-a; return a-b;
if(flag==false) {
j=0;
for(i=jilu;i>=0;i--) {
run_jilu[j]=run[i]; }
if(i
for(i=jilu+1;i
j++;
run_jilu[j]=run[i]; }
if(flag==true) {
j=0;
for(i=jilu;i
if(i
for(i=jilu-1;i>=0;i--) { } }
run_jilu[j]=run[i]; j++;
run_jilu[j]=run[i]; j++;
}
daoshu=run_begin-run[0]+run[run_number-1]-run[0];
j++; }
daoshu=run[run_number-1]-run_begin+run[run_number-1]-run[0]; } } //
bool end_not(bool a[]) {
for(int i=0;i
}
{ }
return true;
if(a[i]==false)
return false;
//最短寻道时间算法
void SSTF(int run[],int run_jilu[],int run_begin) {
int jilu,temp,flag; flag=0;
run_jilu[flag]=run_begin; daoshu=0;
//如果开始位置在序列中就继续执行，否则加入其中
for(int i=0;i
if(i==run_number) { }
for(i=0;i
for(i=0;i
FLAG_USED[jilu]=true; //当没走完时
while(!end_not(FLAG_USED)) {
for(int j=0;j
if(run_begin==run[i]) { }
jilu=i; break; FLAG_USED[i]=false; run_number+=1;
run[run_number-1]=run_begin; if(run_begin==run[i]) { }
break;
abs_LONGTH[j]=abs_number(run_begin,run[j]);
for(j=0;j
if(FLAG_USED[j]==false) { }
temp=abs_LONGTH[j]; break;
}
for(i=0;i
for(i=0;i
if(temp==abs_LONGTH[i]&&FLAG_USED[i]==false) {
run_begin=run[i];
flag++;
{ }
if(temp>abs_LONGTH[i]&&FLAG_USED[i]==false)
temp=abs_LONGTH[i];
run_jilu[flag]=run_begin; }
int main() {
int run_begin,as,at; bool flag;
printf("请输入柱面数:"); scanf("%d",&run_number); printf("请输入各道磁道数\n"); }
for(flag=0;flag
daoshu+=abs_number(run_jilu[flag+1],run_jilu[flag]); }
}
FLAG_USED[i]=true; break;
for(int i=0;i
{ }
printf("请输入开始磁道数:"); scanf("%d",&run_begin);
printf("请选择寻道方式(1--电梯算法，2--最短寻道)"); scanf("%d",&at); while(at!=1&&at!=2) {
printf("请选择寻道方式(1--电梯算法，2--最短寻道)"); } if(at==1) {
printf("请输入走向（1--上，2——下）:"); scanf("%d",&as);
scanf("%d",&at); scanf("%d",&run[i]);
while(as!=1&&as!=2)
{
printf("请输入走向（1--上，2——下）:"); scanf("%d",&as); }
if(as==1) {
flag=true;
} if(as==2) {
flag=false;
}
SCAN(run,run_jilu,run_begin,flag);
} if(at==2) { }
SSTF(run,run_jilu,run_begin);
printf("走道次序:"); for(i=0;i
printf("\n走过总道数:%d\n",daoshu); }
return 0;
printf("%d\t",run_jilu[i]);
本科生课程设计成绩评定表
分）、
及格（60-69分）、60分以下为不及格
指导教师签名：
2013 年 月 日