操作系统进程调度算法实现
FCFS和SDJ都使用有七个时间(到达时间、服务时间、开始时间、完成时间、等待时间、周转时间、带权周转时间)的进程结构体,然后给进程的到达时间和服务时间赋予随机数,再经过优先最短作业和优先到达作业两种方式去计算其他四种时间,最终得出各进程的执行顺序。
短进程优先调度算法 + 动态优先权机制,既考虑进程的执行时间也考虑进程的等待时间,综合了FCFS和SPF两种算法的特点,先将到达时间最短的进程执行,再根据最先到达的进程执行的完成时间计算出其他进程的RP优先权(等待时间+服务时间/服务时间)然后挑选出RP最大的进程执行,以此类推再算出其他进程的执行。最终完成整个高响应比进出的调度。
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
struct pcb
{
int id;
int arriveTime;
int serveTime;
int startTime;
int finishTime;
int functionTime;
double valueFuntionTime;
int statue;
};
pcb work[5];
void fcfs()
{
int i;
double sum1=0,sum2=0;
int min=999,flag,j,start=0;
printf("\n运行结果:\n");
printf("进程 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转时间\n");
for(j=0;j<5;j++)
{
min=999;
for(i=0;i<5;i++)
{
if(work[i].arriveTime<min&&work[i].statue==0)
{
min=work[i].arriveTime;
flag=i;
}
}
work[flag].statue=1;
if(work[flag].arriveTime>start)
work[flag].startTime=work[flag].arriveTime;
else
work[flag].startTime=start;
work[flag].finishTime=work[flag].startTime+work[flag].serveTime;
work[flag].functionTime=work[flag].finishTime-work[flag].arriveTime;
work[flag].valueFuntionTime=work[flag].functionTime/(work[flag].serveTime*1.0);
start=work[flag].finishTime;
sum1=sum1+work[flag].functionTime;
sum2=sum2+work[flag].valueFuntionTime;
printf("进程%d: %4d %7d %7d %8d %10d %12lf \n",work[flag].id,work[flag].arriveTime,work[flag].serveTime,work[flag].startTime,work[flag].finishTime,work[flag].functionTime,work[flag].valueFuntionTime);
}
printf("平均周转时间%lf 平均带权周转时间%lf\n",sum1/5,sum2/5);
}
void sjf()
{
int i;
double sum1=0,sum2=0;
int min=999,flag,j,start=0;
printf("\n运行结果:\n");
printf("进程 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转时间\n");
for(j=0;j<5;j++)
{
min=999;
if(j==0)
for(i=0;i<5;i++)
{
if(work[i].arriveTime<min&&work[i].statue==0)
{
min=work[i].arriveTime;
flag=i;
}
}
else
{
int weight=999;
for(i=0;i<5;i++)
{
if(work[i].arriveTime<start&&work[i].serveTime<weight&&work[i].statue==0)
{
weight=work[i].serveTime;
flag=i;
}
}
}
work[flag].statue=1;
if(work[flag].arriveTime>start)
work[flag].startTime=work[flag].arriveTime;
else
work[flag].startTime=start;
work[flag].finishTime=work[flag].startTime+work[flag].serveTime;
work[flag].functionTime=work[flag].finishTime-work[flag].arriveTime;
work[flag].valueFuntionTime=work[flag].functionTime/(work[flag].serveTime*1.0);
start=work[flag].finishTime;
sum1=sum1+work[flag].functionTime;
sum2=sum2+work[flag].valueFuntionTime;
printf("进程%d: %4d %7d %7d %8d %10d %12lf \n",work[flag].id,work[flag].arriveTime,work[flag].serveTime,work[flag].startTime,work[flag].finishTime,work[flag].functionTime,work[flag].valueFuntionTime);
}
printf("平均周转时间%lf 平均带权周转时间%lf\n",sum1/5,sum2/5);
}
int main()
{
int i;
for(i=0;i<5;i++)
{
work[i].arriveTime=rand()%10;
work[i].serveTime=rand()%10+1;
work[i].id=i+1;
work[i].statue=0;
printf("进程 %d 到达时间:%d 服务时间:%d \n",work[i].id,work[i].arriveTime,work[i].serveTime);
}
fcfs();
for(i=0;i<5;i++)
{
work[i].statue=0;
}
sjf();
}
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
struct pcb
{
int id;
int ta;
int ts;
int tw;
double rp;
int tb;
int tc;
double ti;
double wi;
int statue;
};
int main()
{
pcb work[5];
int i;
printf("自动生成的到达时间和服务时间\n\n") ;
for(i=0;i<5;i++)
{
work[i].ta=rand()%10;
work[i].ts=rand()%10+1;
work[i].id=i+1;
work[i].statue=0;
printf("进程 %d 到达时间:%d 服务时间:%d \n",work[i].id,work[i].ta,work[i].ts);
}
printf("\n\n运行结果\n\n") ;
printf("进程ID 到达时间 开始时间 服务时间 等待时间 完成时间 TI wi \n");
int min=999,flag,time,j,k;
for(j=0;j<5;j++)
{
if(j==0)
{
for(k=0;k<5;k++)
if(work[k].ta<min)
{
min=work[k].ta;
flag=k;
}
work[flag].tw=0;
work[flag].rp=1+work[flag].tw/work[flag].ts;
work[flag].tb=work[flag].ta;
work[flag].tc=work[flag].tb+work[flag].ts;
work[flag].ti=work[flag].tc-work[flag].ta;
work[flag].statue=1;
work[flag].wi=work[flag].rp;
time=work[flag].tc;
printf("%5d %7d %7d %9d %7d %7d %13lf %10lf\n",work[flag].id,work[flag].ta,work[flag].tb,work[flag].ts,work[flag].tw,work[flag].tc,work[flag].ti,work[flag].wi);
}
else
{
int minRp=999,flag2;
for(k=0;k<5;k++)
{
if(work[k].statue==0&&work[k].ta<time)
{
work[k].tw=time-work[k].ta;
work[k].rp=1+work[k].tw/work[k].ts;
if(work[k].rp<minRp)
{
minRp=work[k].rp;
flag2=k;
}
}
}
work[flag2].tw=time-work[flag2].ta;
work[flag2].tb=work[flag2].ta+work[flag2].tw;
work[flag2].tc=work[flag2].tb+work[flag2].ts;
work[flag2].ti=work[flag2].tc-work[flag2].ta;
work[flag2].statue=1;
work[flag2].wi=work[flag2].rp;
time=time+work[flag2].ts;
//printf("到达时间 开始时间 服务时间 等待时间 完成时间 ");
printf("%5d %7d %7d %9d %7d %7d %13lf %10lf\n",work[flag2].id,work[flag2].ta,work[flag2].tb,work[flag2].ts,work[flag2].tw,work[flag2].tc,work[flag2].ti,work[flag2].wi);
}
}
}
图2 先来先服务和短作业优先结果比较
图3 高响应比调度结果
根据结果得出,生成相同到达时间和服务时间的进程经过短作业优先算法运行后的平均周转时间和平均带权周转时间都低于先来先服务算法的时间。
四、实验体会
(1) 通过本实验,我更加理解了什么是进程,也对高优先级(FCFS,SDJ,高响应比)调度方法有了更深层次的了解,认识到各种调度算法的优劣势,从平均结果上看,短作业优先调度略优于先来先服务算法,高响应比算法则综合考虑了两种算法的长处。借助本实验,我也加深了对其他调度算法理解。
(2) 本次试验,我通过实践,加深了理论知识。通过理论与实践的结合,
更好地掌握了知识。这也是以后要继续实行的学习方法。
(3) C语言编程技能与操作系统知识的相结合,让我在提高编程能力的同
时,加强了与实际问题的结合,提高了对实际问题的解决能力,先将实际问 题抽象为算法实现,再通过计算机仿真模拟出结果进行分析。