目标：
• 1. 复习CPU调度的四种基本调度算法
• 2.复习平均等待时间以及平均周转时间
• 3. 通过编程模拟CPU调度的过程，深化对CPU的四种基本调度算法的理解
基本调度算法
• FCFS(先进先出算法)
• SJF(短作业优先算法)
• 优先级调度算法
• RR(时间片轮转调度算法)
等待时间和周转时间
• 等待时间
– 进程在等待队列中的时间总和
• 周转时间
– 进程从提交到进程完成的时间总和
实验内容
• 分别使用FCFS、 SJF（非抢占）、优先级调度（非抢占）、 RR四种调度算法来模拟CPU调度的过程。（Linux、 Windows下皆可,语言不限）
• 输入：存储需要调度的作业信息的job.txt文档
• 输出：每个作业的编号、作业开始执行时间、作业结束时间以及该调度算法的平均等待时间、平均周转时间
• 选作： SJF（抢占）、优先级调度（抢占）
说明：
• 1. job.txt说明：
第一行：作业数 轮转片大小
第二行以后：作业编号 到达时间 执行时间 优先级
• 2. 输出说明：
FCFS: 作业编号 开始执行时间 结束时间
…… …… ……
Average waiting time: 平均等待时间
Time for Average Turnaround : 平均周转时间
SJF(非抢占): 作业编号 开始执行时间 结束时间
…… …… ……
Average waiting time: 平均等待时间
Time for Average Turnaround : 平均周转时间
……
代码：
#include<stdio.h>
#include<queue>
#include<iostream>
using namespace std;
int pnum;
int ptime;
int index[255];
int time1[255];
int use_time[255];
int level[255];
void FCFS()
{
int wait_time[255];
int turn_time[255];
int nowtime=0;
printf("FCFS: \n作业编号 开始执行时间 结束时间 \n");
for(int i=0;i<pnum;i++)
{
printf("%d ",index[i]);
/*开始运行*/
if(time1[i]>=nowtime) //到达时间大于现在时间 ，作业晚到wait
{
printf("%d ",time1[i]);
nowtime=time1[i];
wait_time[i]=0; //作业没有等待
}
else//到达时间小于现在时间 ，作业早到
{
printf("%d ",nowtime);
wait_time[i]=nowtime-time1[i];
}
/*结束时间*/
printf("%d ",nowtime+use_time[i]);
nowtime+=use_time[i];
turn_time[i]=nowtime-time1[i]; //结束时间-到达时间
printf("\n");
}
float all_wait_time=0;
float all_turn_time=0;
for(int i=0;i<pnum;i++)
{
all_wait_time+=wait_time[i];
all_turn_time+=turn_time[i];
}
printf("Average waiting time:%f\n",all_wait_time/pnum);
printf("Time for Average Turnaround : %f\n",all_turn_time/pnum);
}
int flag[255]; //find_min 表示以读取
int check()//检查是否完成 完成返回0
{
int end=0;
for(int i=0;i<pnum;i++)
if(flag[i]==0)
end=1;
return end;
}
int find_min(int have_in)
{
int next=999;
int min=999;
for(int i=0;i<have_in;i++)
{
if(flag[i]==0 && use_time[i]<min)
{
min=use_time[i];
next=i;
}
}
return next;
}
void SJF()
{
int have_in=1;
int wait_time[255];
int turn_time[255];
int nowtime=0;
float all_wait_time=0;
float all_turn_time=0;
for(int i=0;i<255;i++)
flag[i]=0;
printf("SJF(非抢占):\n 作业编号 开始执行时间 结束时间\n");
int i=0;
while(1)
{
if(have_in==0) //第一个
{
printf("%d %d %d\n",index[0],time1[0],use_time[0]);
nowtime=time1[i]+use_time[0];
wait_time[0]=0;
turn_time[0]=use_time[0];
flag[0]=1; //已经运行
}
for(int j=have_in;j<pnum;j++) //查找运行一个作业期间进入队列的其他队列
{
if(nowtime>=time1[j]&&flag[j]==0) //目前时间>=到达时间 作业到达
have_in++;
}
int next=find_min(have_in);
if(check()==0) //结束判断
break;
if(next==999)//目前没有新的作业进入
{
next=have_in; //直接取下一个
have_in++;
nowtime=time1[next]; //现在时间跳到下一个进程进入时间
}
printf("%d ",index[next]);
printf("%d ",nowtime);
printf("%d \n",nowtime+use_time[next]);
wait_time[next]=nowtime-time1[next];
nowtime+=use_time[next];
turn_time[next]=nowtime-time1[next];
flag[next]=1;
}
for(int i=0;i<pnum;i++)
{
all_wait_time+=wait_time[i];
all_turn_time+=turn_time[i];
}
printf("Average waiting time:%f\n",all_wait_time/pnum);
printf("Time for Average Turnaround : %f\n",all_turn_time/pnum);
}
int find_max(int have_in)
{
int next=999;
int min=999;
for(int i=0;i<have_in;i++)
{
if(flag[i]==0 && level[i]<min)
{
min=level[i];
next=i;
}
}
return next;
}
void Power()
{
int have_in=1;
int wait_time[255];
int turn_time[255];
int nowtime=0;
float all_wait_time=0;
float all_turn_time=0;
for(int i=0;i<255;i++)
flag[i]=0;
printf("优先级调度(非抢占):\n 作业编号 开始执行时间 结束时间\n");
while(1)
{
if(have_in==0) //第一个
{
printf("%d ",index[0]);
printf("%d ",time1[0]);
printf("%d \n",use_time[0]);
nowtime=time1[0]+use_time[0];
wait_time[0]=0;
turn_time[0]=use_time[0];
flag[0]=1; //已经运行
}
for(int j=have_in;j<pnum;j++) //查找运行一个作业期间进入队列的其他队列
{
if(nowtime>=time1[j]&&flag[j]==0) //目前时间>=到达时间 作业到达
have_in++;
}
int next=find_max(have_in);
if(check()==0) //结束判断
break;
if(next==999)//目前没有新的作业进入
{
next=have_in; //直接取下一个
have_in++;
nowtime=time1[next]; //现在时间跳到下一个进程进入时间
}
printf("%d ",index[next]);
printf("%d ",nowtime);
printf("%d \n",nowtime+use_time[next]);
wait_time[next]=nowtime-time1[next];
nowtime+=use_time[next];
turn_time[next]=nowtime-time1[next];
flag[next]=1;
}
for(int i=0;i<pnum;i++)
{
all_wait_time+=wait_time[i];
all_turn_time+=turn_time[i];
}
printf("Average waiting time:%f\n",all_wait_time/pnum);
printf("Time for Average Turnaround : %f\n",all_turn_time/pnum);
}
void RR()
{
queue<int> p; //创建队列
p.push(0);
int nowtime=time1[0];//调整现在时间
int have_use_time[255];//已经工作时间
int start_time[255];//开始工作时间
int end_time[255];//结束工作时间
float wait_time[255];
float turn_time[255];
int have_in=1; //已经进入
for(int i=0;i<255;i++)
{
flag[i]=0;
have_use_time[i]=0;
start_time[i]=0;
end_time[i]=0;
wait_time[i]=0;
turn_time[i]=0;
}
while(check()==1)
{
/*从队列中取出一个作业*/
int i=p.front();
p.pop();
if(have_use_time[i]==0)//运行时间为零，第一次进入
start_time[i]=nowtime;
if(have_use_time[i]+ptime>=use_time[i])
{
nowtime+=use_time[i]-have_use_time[i];
flag[i]=1;
have_use_time[i]=use_time[i];
end_time[i]=nowtime;
}
else
{
nowtime+=ptime;
have_use_time[i]+=ptime;
}
for(int j=have_in;j<pnum;j++)
{
if(nowtime>=time1[j]&&flag[j]==0)//已经进入
{
have_in++;
p.push(j);
}
}
if(have_use_time[i]!=use_time[i])
p.push(i);
if(p.empty() && check())//队列空 但未完成
{
nowtime=time1[have_in];
p.push(have_in);
have_in++;
}
}
float all_wait_time=0;
float all_turn_time=0;
for(int i=0;i<pnum;i++)
{
wait_time[i]=end_time[i]-time1[i]-use_time[i];//等待时间=结束时间-到达时间-工作时间
turn_time[i]=end_time[i]-time1[i];
printf("%d %d %d\n",index[i],start_time[i],end_time[i]);
all_wait_time+=wait_time[i];
all_turn_time+=turn_time[i];
}
printf("Average waiting time:%f\n",all_wait_time/pnum);
printf("Time for Average Turnaround : %f\n",all_turn_time/pnum);
}
int main()
{
FILE *fp=NULL;
fp=fopen("job.txt","r");
fscanf(fp,"%d",&pnum);//作业量
fscanf(fp,"%d",&ptime);//时间片
for(int i=0;i<pnum;i++)
{
fscanf(fp,"%d",&index[i]);//标号
fscanf(fp,"%d",&time1[i]);//到达时间
fscanf(fp,"%d",&use_time[i]);//所需时间
fscanf(fp,"%d",&level[i]);//优先级
}
fclose(fp);
printf("%d %d\n",pnum,ptime);
for(int i=0;i<pnum;i++)
{
printf("%d %d %d %d\n",index[i],time1[i],use_time[i],level[i]);
}
FCFS();
SJF();
Power();
RR();
}