计算机科学与应用系
操作系统原理
课程设计报告
题目 进程调度算法
学号
班级
姓名
专业 计算机科学与技术
指导教师
完成日期
进程调度算法
一.实验目的
通过优先权法与轮转调度算法的模拟加深对进程概念和进程调度过程的理解，掌握进程状态之间的切换，同时掌握进程调度算法的实现方法和技巧。
二.实验内容
1.用C语言或C++语言来实现对N个进程采用优先算法以及轮转算法的进程调度。
2.每个用来标示进程的进程控制块PCB用结果来描述，包括以下字段
（1）进程标识ID，其中0为闲逛进程，用户进程的标识数为1、2、3、、、、、、、。
（2）进程优先级Priority，闲逛进程（idle）的优先级为0，用户有进程的优先级大于0，且随机产生，标识数越大，优先级越高。
（3）进程占用的CPU时间CPUtime，进程每运一次，累积等于4.
（4）进程总共需要运行时间Alltime，利用随机函数产生。
（5）进程状态，0—就绪态，1—运行态，2—阻塞态。
（6）队列指针next，用来将多个进程控制块PCB链接为队列。
3.优先数改变的原则
（1）进程在就绪队列中每呆一个时间片，优先数增加1.
（2）进程每运行一个时间片，优先数增加1.
4.在调度前，系统中拥有的进程数PCB_number有键盘输入，进初始化后，所有的进程控制块PCB连接成就绪队列。
5.为了清楚的观察诸进程的调度过程，程序应将每个时间片内的进程的情况显示出来。
三.设计要求
1．需写出设计说明；
2．设计实现代码及说明；
3．运行结果.
四.实验步骤
1.进程管理程序调试好后运行进程管理程序
图1 进程管理调试界面
优先权调度模拟流程图
2.优先权调度
（1）输入1选择优先权调度算法模拟。
（2）输入开始进程个数n，创建n个PCB并加入就绪队列ready_queue中。
（3）就绪队列ready_queue不为空，调度就绪队列中第一个进程运行，否则，从闲逛队列idleprocess中调度闲逛进程运行。
（4）在运行过程中，当遇到阻塞，则该进程插入到阻塞队列block_queue中，且将该进程从ready_queue中删除。
（5）如果运行时间CPUtime大于等于Alltime，该进程运行完毕，释放该进程；否则插入到就绪队列中。
（6）更新就绪队列中的优先级数。
（7）随机对阻塞队列block_queue中的进程PCB询问是否要唤醒，唤醒，即从唤醒队列中选择第一个进程，且插入就绪队列中；阻塞队列中没有阻塞进程返回。
（8）重复上述步骤，直到本次调度结束。
图2 优先调度运行结果
3.轮转调度
（1）输入2选择优先权调度算法模拟。
（2）输入开始进程个数n，创建n个PCB并加入就绪队列ready_queue中。
（3）就绪队列ready_queue不为空，调度就绪队列中第一个进程运行，否则，从闲逛队列idleprocess中调度闲逛进程运行。
（4）在运行过程中，当遇到阻塞，则该进程插入到阻塞队列block_queue中，且将该进程从ready_queue中删除。
（5）如果运行时间CPUtime大于等于Alltime，该进程运行完毕，释放该进程；否则插入到就绪队列中。
（6）随机对阻塞队列block_queue中的进程PCB询问是否要唤醒，唤醒，即从唤醒队列中选择第一个进程，且插入就绪队列中；阻塞队列中没有阻塞进程返回。
（7）如果时间到，本次调度结束，否则重复上述步骤，直到本次调度结束。
图3 轮转调度运行结果
轮转调度模拟流程图
五.实验过程中遇到的问题及解决方案
1、请仔细阅读动态优先权的进程调度算法的模拟实现代码,说明该算法与教材中介绍的算法做了哪些简单化处理.
优先权模拟时优先权是随机产生，在实际的系统中，系统进程的优先权高于一般用户进程的优先权。
2、为什么对进程的优先数可按上述原则进行修改?
最高优先权调度算法仅照顾了优先权高的进程，当不断有优先权高的进程需调度时，而优先权低的进程将很难得到处理机的调度，所以进程在就绪队列中每呆一个时间片，优先数增加1，使优先权低的进程不总是忙等。
3、请给出设计实现的轮转发进程调度算法的设计思想.
时间轮转调度算法：系统将所有的就像进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给首进程，并令其执行一个时间片。当执行的时间片用完时，发出中断请求，调度程序便据此信号来停止该进程的执行，并将其送到就绪队列的末尾，如此反复，就可以保证就绪队列中的所有进程在一个给定的时间内，均能获得一时间片处理机执行时间。
4、在实际的进程调度中，除了按调度算法选择下一个执行的进程外,还应处理哪些工作? 最高优先权调度算法，常用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可以用于实时系统中：时间轮转调度算法，一般用于分时系统中。
六.实验体会
1、当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业，装入内存，当用于进程调度算法时，该算法是把处理及分配给就绪队列中优先权最高的进程。
2、当系统空闲（就绪队列为空）时，系统运行闲逛进程，否则运行其他进程，发生变迁（就绪→运行）
3、在运行进程（包括闲逛进程）的过程中，可能发生变迁2(运行→阻塞)，即将运行进程插入到阻塞队列（闲逛进程不能不被阻塞），可能有其他的进程创建PCB，还可能唤醒阻塞队列中的某些进程PCB，发生变迁3（阻塞→就绪），即从阻塞队列中插入就绪队列中。
4、时间片运行结束后，若进程累积占用CPU时间大于等于进程需要运行时间，则进程执行结束，释放其PCB。若进程累积占用CPU时间小于进程需要运行时间，发生变迁4（运行→就绪），即将当前运行的进程插入就绪队列中。
七.参考资料
《计算机操作系统》
《计算机操作系统实验指导书》
《C程序设计》
《C语言程序设计_现代方法》
八.源代码
#include
#include
#include
#define N 5 //进程个数，可改变
int rt[N]; //到达时间
int st[N]; //服务时间
int ct[N]; //完成时间
int cyt[N]; //周转时间
float rct[N]; //带权周转时间
float av[2];
int n,m,c=1,which;
void line() //美化程序，使程序运行时更加明朗美观
{
printf("------------------------------------------------------------------\n");
}
void start() //表示FCFS算法开始
{
line();
printf(" FCFS算法开始\n");
printf(" ——Designed by Zhang Hong\n"); line();
}
void end() //表示FCFS算法结束
{
line();
printf(" FCFS算法结束,谢谢使用\n");
line();
}
void input()
{
printf("请输入%d个进程的到达时间：",N);
for (n=0;n
scanf("%d",&rt[n]);
printf("请输入%d个进程对应的服务时间：",N);
for (n=0;n
scanf("%d",&st[n]);
}
void random()
{
srand((unsigned)time(NULL));
for (n=0;n
{
rt[n]=rand()%100;
for (m=0;m
if (n!=0 && rt[n]==rt[m])
{
rt[n]=rand()%100;
m=0;
}
st[n]=rand()%98+1;
for (m=0;m
if (n!=0 && st[n]==st[m])
{
st[n]=rand()%98+1;
m=0;
}
}
}
void ordination() //重新排序，应对出现输入的到达时间为乱序的情况
{
int temp;
for (n=0;n
for (m=0;m
if (rt[m+1]
{
temp=rt[m+1];
rt[m+1]=rt[m];
rt[m]=temp;
temp=st[m+1];
st[m+1]=st[m];
st[m]=temp;
}
}
void fcfs() //执行fcfs算法
{
av[0]=0;
av[1]=0;
ct[0]=rt[0]+st[0];
for (n=1;n
{
if (ct[n-1]>=rt[n]) //考虑当前一个进程完成而后一个进程还没有到达的情况
ct[n]=ct[n-1]+st[n];
else
ct[n]=rt[n]+st[n];
}
for (n=0;n
cyt[n]=ct[n]-rt[n];
for (n=0;n
rct[n]=(float)cyt[n]/(float)st[n];
for (n=0;n
{
av[0]+=(float)cyt[n]/N;
av[1]+=rct[n]/N;
}
}
void output() //输出结果
{
line();
printf("进程名\t");
for (n=0;n
printf("\t%c",65+n);
printf("\t平均\n到达时间");
for (n=0;n
printf("\t%d",rt[n]);
printf("\n服务时间");
for (n=0;n
printf("\t%d",st[n]);
printf("\n完成时间");
for (n=0;n
printf("\t%d",ct[n]);
printf("\n周转时间");
for (n=0;n
printf("\t%d",cyt[n]);
printf("\t%0.1f",av[0]);
printf("\n带权周转时间");
for (n=0;n
printf("\t%0.1f",rct[n]);
printf("\t%0.1f",av[1]);
printf("\n");
line();
}
void main()
{
start();
for (;c==1;)
{
for (;;)
{
printf("输入数据还是由系统随机产生数据？\n1、输入数据\t2、系统随机产生数据\n请输入：");
scanf("%d",&which);
if (which==1)
{
input();
}
break; } else if (which==2) { random(); break; } printf("输入错误，请重新输入！"); } ordination(); //进程按照到达时间进行排序 fcfs(); output(); printf("继续输入，退出输入。请输入："); scanf("%d",&c); } end();
计算机科学与应用系
操作系统原理
课程设计报告
题目 进程调度算法
学号
班级
姓名
专业 计算机科学与技术
指导教师
完成日期
进程调度算法
一.实验目的
通过优先权法与轮转调度算法的模拟加深对进程概念和进程调度过程的理解，掌握进程状态之间的切换，同时掌握进程调度算法的实现方法和技巧。
二.实验内容
1.用C语言或C++语言来实现对N个进程采用优先算法以及轮转算法的进程调度。
2.每个用来标示进程的进程控制块PCB用结果来描述，包括以下字段
（1）进程标识ID，其中0为闲逛进程，用户进程的标识数为1、2、3、、、、、、、。
（2）进程优先级Priority，闲逛进程（idle）的优先级为0，用户有进程的优先级大于0，且随机产生，标识数越大，优先级越高。
（3）进程占用的CPU时间CPUtime，进程每运一次，累积等于4.
（4）进程总共需要运行时间Alltime，利用随机函数产生。
（5）进程状态，0—就绪态，1—运行态，2—阻塞态。
（6）队列指针next，用来将多个进程控制块PCB链接为队列。
3.优先数改变的原则
（1）进程在就绪队列中每呆一个时间片，优先数增加1.
（2）进程每运行一个时间片，优先数增加1.
4.在调度前，系统中拥有的进程数PCB_number有键盘输入，进初始化后，所有的进程控制块PCB连接成就绪队列。
5.为了清楚的观察诸进程的调度过程，程序应将每个时间片内的进程的情况显示出来。
三.设计要求
1．需写出设计说明；
2．设计实现代码及说明；
3．运行结果.
四.实验步骤
1.进程管理程序调试好后运行进程管理程序
图1 进程管理调试界面
优先权调度模拟流程图
2.优先权调度
（1）输入1选择优先权调度算法模拟。
（2）输入开始进程个数n，创建n个PCB并加入就绪队列ready_queue中。
（3）就绪队列ready_queue不为空，调度就绪队列中第一个进程运行，否则，从闲逛队列idleprocess中调度闲逛进程运行。
（4）在运行过程中，当遇到阻塞，则该进程插入到阻塞队列block_queue中，且将该进程从ready_queue中删除。
（5）如果运行时间CPUtime大于等于Alltime，该进程运行完毕，释放该进程；否则插入到就绪队列中。
（6）更新就绪队列中的优先级数。
（7）随机对阻塞队列block_queue中的进程PCB询问是否要唤醒，唤醒，即从唤醒队列中选择第一个进程，且插入就绪队列中；阻塞队列中没有阻塞进程返回。
（8）重复上述步骤，直到本次调度结束。
图2 优先调度运行结果
3.轮转调度
（1）输入2选择优先权调度算法模拟。
（2）输入开始进程个数n，创建n个PCB并加入就绪队列ready_queue中。
（3）就绪队列ready_queue不为空，调度就绪队列中第一个进程运行，否则，从闲逛队列idleprocess中调度闲逛进程运行。
（4）在运行过程中，当遇到阻塞，则该进程插入到阻塞队列block_queue中，且将该进程从ready_queue中删除。
（5）如果运行时间CPUtime大于等于Alltime，该进程运行完毕，释放该进程；否则插入到就绪队列中。
（6）随机对阻塞队列block_queue中的进程PCB询问是否要唤醒，唤醒，即从唤醒队列中选择第一个进程，且插入就绪队列中；阻塞队列中没有阻塞进程返回。
（7）如果时间到，本次调度结束，否则重复上述步骤，直到本次调度结束。
图3 轮转调度运行结果
轮转调度模拟流程图
五.实验过程中遇到的问题及解决方案
1、请仔细阅读动态优先权的进程调度算法的模拟实现代码,说明该算法与教材中介绍的算法做了哪些简单化处理.
优先权模拟时优先权是随机产生，在实际的系统中，系统进程的优先权高于一般用户进程的优先权。
2、为什么对进程的优先数可按上述原则进行修改?
最高优先权调度算法仅照顾了优先权高的进程，当不断有优先权高的进程需调度时，而优先权低的进程将很难得到处理机的调度，所以进程在就绪队列中每呆一个时间片，优先数增加1，使优先权低的进程不总是忙等。
3、请给出设计实现的轮转发进程调度算法的设计思想.
时间轮转调度算法：系统将所有的就像进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给首进程，并令其执行一个时间片。当执行的时间片用完时，发出中断请求，调度程序便据此信号来停止该进程的执行，并将其送到就绪队列的末尾，如此反复，就可以保证就绪队列中的所有进程在一个给定的时间内，均能获得一时间片处理机执行时间。
4、在实际的进程调度中，除了按调度算法选择下一个执行的进程外,还应处理哪些工作? 最高优先权调度算法，常用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可以用于实时系统中：时间轮转调度算法，一般用于分时系统中。
六.实验体会
1、当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业，装入内存，当用于进程调度算法时，该算法是把处理及分配给就绪队列中优先权最高的进程。
2、当系统空闲（就绪队列为空）时，系统运行闲逛进程，否则运行其他进程，发生变迁（就绪→运行）
3、在运行进程（包括闲逛进程）的过程中，可能发生变迁2(运行→阻塞)，即将运行进程插入到阻塞队列（闲逛进程不能不被阻塞），可能有其他的进程创建PCB，还可能唤醒阻塞队列中的某些进程PCB，发生变迁3（阻塞→就绪），即从阻塞队列中插入就绪队列中。
4、时间片运行结束后，若进程累积占用CPU时间大于等于进程需要运行时间，则进程执行结束，释放其PCB。若进程累积占用CPU时间小于进程需要运行时间，发生变迁4（运行→就绪），即将当前运行的进程插入就绪队列中。
七.参考资料
《计算机操作系统》
《计算机操作系统实验指导书》
《C程序设计》
《C语言程序设计_现代方法》
八.源代码
#include
#include
#include
#define N 5 //进程个数，可改变
int rt[N]; //到达时间
int st[N]; //服务时间
int ct[N]; //完成时间
int cyt[N]; //周转时间
float rct[N]; //带权周转时间
float av[2];
int n,m,c=1,which;
void line() //美化程序，使程序运行时更加明朗美观
{
printf("------------------------------------------------------------------\n");
}
void start() //表示FCFS算法开始
{
line();
printf(" FCFS算法开始\n");
printf(" ——Designed by Zhang Hong\n"); line();
}
void end() //表示FCFS算法结束
{
line();
printf(" FCFS算法结束,谢谢使用\n");
line();
}
void input()
{
printf("请输入%d个进程的到达时间：",N);
for (n=0;n
scanf("%d",&rt[n]);
printf("请输入%d个进程对应的服务时间：",N);
for (n=0;n
scanf("%d",&st[n]);
}
void random()
{
srand((unsigned)time(NULL));
for (n=0;n
{
rt[n]=rand()%100;
for (m=0;m
if (n!=0 && rt[n]==rt[m])
{
rt[n]=rand()%100;
m=0;
}
st[n]=rand()%98+1;
for (m=0;m
if (n!=0 && st[n]==st[m])
{
st[n]=rand()%98+1;
m=0;
}
}
}
void ordination() //重新排序，应对出现输入的到达时间为乱序的情况
{
int temp;
for (n=0;n
for (m=0;m
if (rt[m+1]
{
temp=rt[m+1];
rt[m+1]=rt[m];
rt[m]=temp;
temp=st[m+1];
st[m+1]=st[m];
st[m]=temp;
}
}
void fcfs() //执行fcfs算法
{
av[0]=0;
av[1]=0;
ct[0]=rt[0]+st[0];
for (n=1;n
{
if (ct[n-1]>=rt[n]) //考虑当前一个进程完成而后一个进程还没有到达的情况
ct[n]=ct[n-1]+st[n];
else
ct[n]=rt[n]+st[n];
}
for (n=0;n
cyt[n]=ct[n]-rt[n];
for (n=0;n
rct[n]=(float)cyt[n]/(float)st[n];
for (n=0;n
{
av[0]+=(float)cyt[n]/N;
av[1]+=rct[n]/N;
}
}
void output() //输出结果
{
line();
printf("进程名\t");
for (n=0;n
printf("\t%c",65+n);
printf("\t平均\n到达时间");
for (n=0;n
printf("\t%d",rt[n]);
printf("\n服务时间");
for (n=0;n
printf("\t%d",st[n]);
printf("\n完成时间");
for (n=0;n
printf("\t%d",ct[n]);
printf("\n周转时间");
for (n=0;n
printf("\t%d",cyt[n]);
printf("\t%0.1f",av[0]);
printf("\n带权周转时间");
for (n=0;n
printf("\t%0.1f",rct[n]);
printf("\t%0.1f",av[1]);
printf("\n");
line();
}
void main()
{
start();
for (;c==1;)
{
for (;;)
{
printf("输入数据还是由系统随机产生数据？\n1、输入数据\t2、系统随机产生数据\n请输入：");
scanf("%d",&which);
if (which==1)
{
input();
}
break; } else if (which==2) { random(); break; } printf("输入错误，请重新输入！"); } ordination(); //进程按照到达时间进行排序 fcfs(); output(); printf("继续输入，退出输入。请输入："); scanf("%d",&c); } end();