q=p;
p->name=j+1;
p->needtime=1+(int)(10.0*rand()/(RAND_MAX+1.0));
p->arrivetime=(int)(10.0*rand()/(RAND_MAX+1.0));
p->pri=1+(int)(9.0*rand()/(RAND_MAX+1.0));
p->state=0;
p->cputime=0;
p->next=(plist*)malloc(sizeof(plist));
p=p->next;
}
q->next=NULL;
returnhead;
}
流程图:
2.2模拟CPU运行进程
算法思想:
需要运行进程的PCB作为函数参数,先修改进程状态,然后修改再修改进程已运行时间和还需运行时间。
代码:
voidaction(plist*nowpro)
//模拟CUP运行进程的过程
{
nowpro->state=2;//设置进程状态为运行态
printf("nowisprocess%d",nowpro->name);
nowpro->needtime--;//修改进程还需运行时间
nowpro->cputime++;//修改进程已运行时间
nowpro->state=1;
if(nowpro->needtime==0)//进程运行结束
{
printf("\ttheprocess%disend\n",nowpro->name);
nowpro->state=4;//进程运行结束,设置进程状态为结束态
}
else
{
printf("\tprocess%dneedtimeis%d\n",nowpro->name,nowpro->needtime);
}
printf("-----------------------------\n");
}
流程图:
2.3显示
算法思想:
先判断链表借点是否为空,然后利用循环输出各PCB信息
代码:
voidshow(plist*process)
//显示
{
if(!
process)
{
printf("thereisnoprocessnow\n");
}
while(process&&process->state!
=4)
{
printf("nameofprocess%d",process->name);
printf("\tneedtime%d",process->needtime);
printf("arrivetime%d",process->arrivetime);
printf("pri%d",process->pri);
printf("state%d",process->state);
printf("cputime%d\n",process->cputime);
process=process->next;
}
}
流程图:
2.4排序
算法思想:
利用两层循环,比较相邻两个元素的大小,第一遍将最大的数排到最末,第二遍将次大的数排到最末的数的前面,经N-1遍后将满足排序的要求。
代码:
plist*sort(plist*head)
//将进程队列按到达先后顺序排序
{
plist*p,*p1,*p2,*p3,*temp;
p=head;
while(p->next!
=NULL){
p=p->next;
}
while(p!
=head){
p3=p1=head;
p2=p1->next;
while(p1!
=p&&p1->next!
=NULL){
if((p1->arrivetime)>(p2->arrivetime)){
if(p1==head){
head=p2;
}
else{
p3->next=p2;
}
temp=p2->next;
p2->next=p1;
p1->next=temp;
temp=p1;
p1=p2;
p2=temp;
}
p3=p1;
p1=p1->next;
p2=p1->next;
}
p=p3;
}
returnhead;
}
2.5建立先来先服务调度算法的就绪队列
算法思想:
先来先服务调度算法中的就绪队列是按到达时间的先后排序的,当就绪队列为空时,直接将作为将要添加的进程PCBtemp作为队头,如果就绪队列不为空,则将temp添加到队列末尾。
添加到就绪队列后再修改进程状态为就绪态。
代码:
plist*fcfs_creatready(plist*ready_queue,plist*temp)
//将进程temp添加到就绪队列ready_queue的尾部
{
plist*q;
q=ready_queue;
if(ready_queue){//当就绪队列不为空时,新进入的进程添加到就绪队列末尾
while(q->next){
q=q->next;
}//使指针P指向就绪队列中最后一个进程
q->next=temp;
temp->state=1;//修改进程状态
temp->next=NULL;
}
else{//当就绪队列为空时,新进入的进程作为就绪队列头部
ready_queue=temp;
ready_queue->state=1;//将进程状态设为就绪状态
temp->next=NULL;
}
returnready_queue;
}
流程图:
2.6建立最高优先数优先调度算法的就绪队列
算法思想:
最高优先数优先调度算法中的就绪队列是按进程优先数递减排序的,当就绪队列为空时,直接将作为将要添加的进程PCBtemp作为队头,如果就绪队列不为空,则将temp添加到队列合适位置。
然后再修改进程状态为就绪态。
代码:
plist*hrrn_creatready(plist*ready_queue,plist*temp)
//按优先数递减的顺序将进程temp添加到就绪队列ready_queue的合适位置
{
plist*q,*p;
p=q=ready_queue;
if(ready_queue&&ready_queue->pri>temp->pri){
//按优先数递减的顺序将进程temp添加到就绪队列ready_queue的合适位置
while(q&&q->pri>=temp->pri){
p=q;
q=q->next;
}//使指针P->next指向就绪队列中进程temp的插入位置
p->next=temp;
temp->next=q;
temp->state=1;//修改进程状态
}
else{//当就绪队列为空时,新进入的进程作为就绪队列头部
temp->next=ready_queue;
ready_queue=temp;
ready_queue->state=1;//将进程状态设为就绪状态
}
returnready_queue;
}
流程图:
2.7进程模拟调度
算法思想:
1.先来先服务调度算法
先来先服务调度算法是一种最简单的调度算法,该算法既可以用于作业调度,也可用于进程调度。
当在作业调度中采用该算法时,每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业,将他们调入内存,为它们分配资源、创建进程,然后放入就绪队列。
在进程调度中采用FCFS算法时,则每次调度是从就绪队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。
该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。
FCFS算法比较有利于长作业(进程),而不利于短作业(进程)。
2.最高优先数调度算法
优先数调度算法常用于批处理系统中。
在进程调度中,每次调度时,系统把处理机分配给就绪队列中优先数最高的进程。
它又分为两种:
非抢占式优先数算法和抢占式优先数算法。
在非抢占式优先数算法下,系统一旦把处理机分配给就绪队列中优先数最高的进程后,这个进程就会一直运行,直到完成或发生某事件使它放弃处理机,这时系统才能重新将处理机分配给就绪队列中的另一个优先数最高的进程。
在抢占式优先数算法下,系统先将处理机分配给就绪队列中优先数最高的进程度让它运行,但在运行的过程中,如果出现另一个优先数比它高的进程,它就要立即停止,并将处理机分配给新的高优先数进程。
本次模拟采用抢占式最高优先数调度算法。
如果调用此函数时是process_simulation(process,fcfs_creatready);则此时是先来先服务算法模拟调度。
如果调用此函数时是process_simulation(process,hrrn_creatready);则此时是最高优先数优先算法模拟调度。
代码:
voidprocess_simulation(plist*process,plist*creatready(plist*,plist*))
{
inttime;//模拟CPU时钟
plist*temp;
plist*ready_queue=NULL;//定义就绪队列,并初始化
time=0;//初始化CPU时序
while(process||ready_queue)//当进程队列不为空,或者就绪队列不为空
{
while(process&&time==process->arrivetime){//进程到达时进入就绪队列
temp=process;
process=process->next;
ready_queue=creatready(ready_queue,temp);
}
if(ready_queue==NULL){//如果没有进程运行,打印CPU空转信息
printf("Thetimesequenceis:
%d\n",time);
printf("Thereadyqueueis:
\n");
printf("thereisnoprocessnow\n");
printf("-----------------------------\n");
time++;
Sleep(500);
}
else{//如果有进程需要运行,则模拟进程运行过程
printf("Thetimesequenceis:
%d\n",time);
printf("Thereadyqueueis:
\n");
show(ready_queue->next);//打印就绪队列
action(ready_queue);//模拟进程运行
if(ready_queue->needtime==0){//进程运行结束,此时将此进程从就绪队列中删除
ready_queue=ready_queue->next;
}
time++;
Sleep(1000);
}
}
printf("Thetimesequenceis:
%d\n",time);//先来先服务模拟调度结束
printf("thereisnoprocessnow\n");
printf("-----------------------------\n");
}
流程图:
2.8主函数
算法思想:
先建立所有需要模拟调度的PCB链表,然后采用冒泡法将链表按进程到达时间递增的顺序排序,然后采用switch--case选择结构进行菜单选择需要模拟的调度模拟。
代码:
voidmain()
{
intn;/*thenumberofprocess*/
intk;
plist*process;
printf("pleaseinputthenumberofprocess:
");
scanf("%d",&n);
process=creatpro(n);
process=sort(process);/******利用冒泡法将进程按到达时间排序******/
show(process);
printf("pleasechoosethewhatyouwanttouse:
\n");
printf("\t1先来先服务\n\t2最高优先数优先\n");
scanf("%d",&k);
switch(k)
{
case1:
{
process_simulation(process,fcfs_creatready);/******先来先服务******/
break;
}
case2:
{
process_simulation(process,hrrn_creatready);/******最高优先数算法******/
break;
}
default:
{
printf("请输入正确选项!
!
!
\n");
break;
}
}
}
3程序运行平台
Windowsxp
MicrosoftVisualC++6.0
4总体设计
系统总体框架图
5程序结构体的说明
typedefstructpcb
{
intname;//进程名
intneedtime;//进程所需运行时间
intarrivetime;//进程到达时间
intpri;//进程优先数
intstate;//进程状态:
0表示未到达1表示就绪2表示运行3表示等待
4表示结束
intcputime;//已用CPU时间
structpcb*next;
}plist;
6程序运行结果
先来先服务模拟调度运行结果:
最高优先数优先调度模拟运行结果:
7结论
这次课程设计的题目是模拟进程调度,课程设计的任务书要求实现模拟作业调度的两个算法:
先来先服务调度算法,最高优先数优先算法。
这次的课程设计我采用的是C语言来编写的,首先编写一个结构体用来存放进程的相关信息,即PCB。
然后将要模拟调度的进程PCB放在队列中。
通过不断的调试与优化,程序很好的模拟了进程的调度过程,先来先服务,最高优先数优先。
在编写实现最高优先数优先算法的时候,刚开始由于没有考虑到后到达的进程的优先数,和当前运行的进程的优先数有高低之分,导致调度得不到预想的结果,经过改正之后就得到了正确的结果。
他们的调度结果都不一样,但是对于进程调度而言,这几个算法各有个的优点和缺点。
先来先服务算法有利于长进程而不利于短进程;最高优先数优先算法既照顾了长进程,又考虑了进程的优先级,不会使长进程长期得不到服务,该算法实现了比较好的折中。
通过本次课程设计加深了我对进程调度算法的理解并且还明白了调度的过程。
在上操作系统课的时候对这几个算法并不是很理解,通过实现了这几个调度算法的模拟之后我,我就明白了这几个算法的本质,并且理解了这几个算法。
在做课程设计的时候自己还是存在不足之处,在考虑算法的时候考虑的不够周全,在编写最高优先数优先的时候刚开始由于没有考虑到后到达的进程与之前的进程的优先数不一样造成调度的结果与预想的不一样,通过仔细的检查与思考之后发现了这个问题并且改正了之后就可以得到正确的结果了。
这次课程设计还让我明白了只有多实践才能发现自己的问题所在才能够很好的掌握知识。
8参考文献
1.张尧学等编著.计算机操作系统教程.北京:
清华大学出版社,2006.02
2.汤子瀛等编著.计算机操作系统.西安:
西安电子科技出版社,1996.12
3.陈向群编著.操作系统教程.北京:
北京大学出版社,2007.01
4.罗宇等编著.操作系统课程设计.北京:
机械工业出版社,2005.9
附录
程序源代码:
#include
#include
#include
#include
typedefstructpcb
{
intname;//进程名
intneedtime;//进程所需运行时间
intarrivetime;//进程到达时间
intpri;//进程优先数
intstate;//进程状态:
0表示未到达1表示就绪2表示运行3表示等待4表示结束
intcputime;//已用CPU时间
structpcb*next;
}plist;
plist*creatpro(intn)
//建立所有将要进行N个模拟调度的进程
{
intj;
plist*p,*q,*head;
p=(plist*)malloc(sizeof(plist));
head=p;
for(j=0;j{
q=p;
p->name=j+1;
p->needtime=1+(int)(10.0*rand()/(RAND_MAX+1.0));
p->arrivetime=(int)(10.0*rand()/(RAND_MAX+1.0));
p->pri=1+(int)(9.0*rand()/(RAND_MAX+1.0));
p->state=0;
p->cputime=0;
p->next=(plist*)malloc(sizeof(plist));
p=p