关于常见的一些进程调度,FCFS,SPF,HPF

admin 管理员组

文章数量: 1184232

关于常见的一些进程调度,FCFS,SPF,HPF

关于常见的一些进程调度

仅供自己复习，有些代码不是很完善，要求未能全部满足

• 先来先服务（FCFS）调度算法，按照顺序依次分配处理机。最简单的调度算法，既可以用于作业调度 ，也可以用于程序调度，当作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，优先从后备队列中，选择一个或多个位于队列头部的作业，把他们调入内存，分配所需资源、创建进程，然后放入“就绪队列”,直到该进程运行到完成或发生某事件堵塞后，进程调度程序才将处理机分配给其他进程。
• 短进程优先(SPF)调度算法，是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。
• 优先级调度算法（HPF）, 基于作业的紧迫程度，由外部赋予作业相应的优先级。调度算法则根据优先级进行调度，本实验报告中实验的是非抢占式优先级调度算法。
• 完成时间=开始时间+服务/运行时间
• 等待时间=开始时间-到达时间
• 周转时间=完成时间-到达时间
• 平均周转时间=周转时间/服务（运行）时间
  所有例题请自行想象

下面展示一些 内联代码片。

#include<stdio.h>
#include <stdlib.h>
#define Max 100   //进程最大数量
#define INF 1000000.0/*****************
数据结构
****************/typedef struct JCB
{float arr_time;//到达时间float ser_time;//服务时间float sta_time;//开始时间float fin_time;//完成时间float cpu_time;//还需占用cpu时间float tur_time;//周转时间float wtur_time;//带权周转时间float need_time;//还需运行时间int priority;//优先级数int round;//进程轮转时间片char state;//进程状态char name[Max];//进程名字
} list;int count;//计数器void FCFS(list *p,int count);   //先来先服务算法
void SJF1(list *p,int count);   //短进程优先算法中状态显示
void SJF2(list *p,int count);   //短进程优先算法中结果显示
void HPF(list *p,int count);    //高优先级算法
void Output1(list *p,int count);    //各个状态输出
void Output2(list *p,int count);    //结果输出
void avg(list *p,int count);        //平均周转时间和平均带权周转时间
int findNext(list *p, int count, float lastTime );  //短进程优先算法中寻找下一进程/* 两种情况：1.在lastTime时刻，选择已经到达且拥有最短运行时间的进程2.在lastTime时刻，没有进程到达，此时选择拥有最早到达时间的进程
*/
int findNext(list *p, int count, float lastTime )
{// k是已经到达且拥有最短运行时间的进程的下标// q是没有到达的进程中拥有最早到达时间的进程的下标int i, k, q;double minNeedTime, minReachTime;k= q = -1;minNeedTime = minReachTime = INF;for( i = 0; i < count; i++ ){if( p[i].state=='W' )   // 进程处就绪状态{if( p[i].arr_time<=lastTime && p[i].ser_time<minNeedTime ){k = i;minNeedTime = p[i].ser_time;}if( p[i].arr_time>lastTime && p[i].arr_time<minReachTime ){q = i;minReachTime = p[i].arr_time;}}}// p为-1时,代表在lastTime时刻还没进程到达,此时选择下一个最早到达的进程qif( k != -1 )return k;elsereturn q;
}void Output1(list *p,int count)
{int i;printf("\n*******************************************\n\n");printf("进程名\t服务\t已运行\t还需运行时间\t状态\t\n");for(i=0; i<count; i++){printf("%s\t%.2f\t%.2f\t%.2f\t%c\t\n",p[i].name,p[i].ser_time,p[i].cpu_time,p[i].need_time,p[i].state);}
}void Output2(list *p,int count)
{int i;printf("\n*******************************************\n\n");printf("进程名\t到达\t服务\t开始\t完成\t周转\t带权周转时间\n");for(i=0; i<count; i++){printf("%s\t%.2f\t%.2f\t%.2f\t%.2f\t%.2f\t%.2f\n",p[i].name,p[i].arr_time,p[i].ser_time,p[i].sta_time,p[i].fin_time,p[i].tur_time,p[i].wtur_time);}}void avg(list *p,int count)
{float AvgTur1;        //平均周转float AvgTur2;        //平均带权周转float t1 = 0;float t2 = 0;int i;for(i = 0; i < count; i++){t1 += p[i].tur_time;                //周转时间和t2 += p[i].wtur_time;               //带权周转和}AvgTur1 = t1/count;AvgTur2 = t2/count;printf("\n平均周转时间为：%.2f\t平均带权周转时间为：%.2f\n",AvgTur1,AvgTur2);printf("\n*****************************************************************\n");return;
}void FCFS(list *p,int count)
{int i,j;list temp;//对时间进行排序，按照升序排序for(i=1; i<count; i++){temp=p[i];j=i-1;while(temp.arr_time<p[j].arr_time&&j>=0){p[j+1]=p[j];--j;}p[j+1]=temp;}//循环显示各个进程的变化状态for(i=0; i<count; i++){for(j=0; j<p[i].ser_time; j++){p[i].state='R';p[i].need_time--;p[i].cpu_time=p[i].ser_time-p[i].need_time;if(p[i].cpu_time==p[i].ser_time)p[i].state='F';Output1(p,count);}}//循环计算进程时间值for(i=0; i<count; i++){if(i==0)p[i].sta_time=p[i].arr_time;elsep[i].sta_time = p[i-1].fin_time;    //开始时刻==前一个作业的完成时刻p[i].fin_time=p[i].sta_time+p[i].ser_time;p[i].tur_time=p[i].fin_time-p[i].arr_time;p[i].wtur_time=p[i].tur_time/p[i].ser_time;}Output2(p,count);return;}
void SJF1(list *p,int count)                   //最短作业优先算法各个状态变化（SJF1）
{int i,j=0;int g[Max];double lastTime;  // 为上一个进程的完成时间,用来确定当前进程的开始时间lastTime = INF;  // 最开始lastTime的为第一个作业的reachTime(到达时间)for(i=0; i<count; i++){if( lastTime>p[i].arr_time )lastTime=p[i].arr_time;}for(i=0; i<count; i++){int temp = findNext( p, count, lastTime ); // 找到下一个将要执行的进程// 两种情况：将要执行的进程可能已经到达，或者还没到达if( p[temp].arr_time<=lastTime )p[temp].sta_time = lastTime;elsep[temp].sta_time = p[temp].arr_time;for(j=0; j<p[temp].ser_time; j++){p[temp].state='R';p[temp].need_time--;p[temp].cpu_time=p[i].ser_time-p[i].need_time;if(p[temp].cpu_time==p[i].ser_time)p[temp].state='F';Output1(p,count);}lastTime = p[temp].fin_time; // 更新lastTime}}
void SJF2(list *p,int count)                   //最短作业优先算法结果时间（SJF2）
{int i,j=0;double lastTime;  // 为上一个进程的完成时间,用来确定当前进程的开始时间lastTime = INF;  // 最开始lastTime的为第一个作业的reachTime(到达时间)for(i=0; i<count; i++){if( lastTime>p[i].arr_time )lastTime=p[i].arr_time;}for( i = 0; i < count; i++ ){int temp = findNext( p, count, lastTime ); // 找到下一个将要执行的进程// 两种情况：将要执行的进程可能已经到达，或者还没到达if( p[temp].arr_time<=lastTime ) p[temp].sta_time = lastTime;else p[temp].sta_time = p[temp].arr_time;// 确定进程的完成时间，周转时间，带权周转时间p[temp].fin_time = p[temp].sta_time + p[temp].ser_time;p[temp].tur_time = p[temp].fin_time - p[temp].arr_time;p[temp].wtur_time = p[temp].tur_time/p[temp].ser_time;p[temp].state = 'F';lastTime = p[temp].fin_time; // 更新lastTime}Output2(p,count);
}//非抢占式最高优先级优先算法
void HPF(list *sum,int count)
{list tim;			//临时结构体int k=100;		//记录最高优先级的进程的下标int min=100;int time=100;   //记录进程完成时间int i,j=0;//将进程按照时间升序排列for(i=1; i<count; i++){tim=sum[i];j=i-1;if(tim.arr_time<sum[j].arr_time&&j>=0){sum[j+1]=sum[j];j--;}tim=sum[j+1];}for(i=0; i<count; i++){//第一个到达的进程，不用考虑优先级if(i==0){sum[i].sta_time=sum[i].arr_time;sum[i].fin_time=sum[i].arr_time+sum[i].ser_time;sum[i].tur_time=sum[i].fin_time-sum[i].arr_time;sum[i].wtur_time=sum[i].tur_time/sum[i].ser_time;sum[i].state='F';time=sum[i].fin_time;           //更新time}else{//找寻在所有满足到达时间内最高优先级的程序for(j=1; j<count; j++){if(sum[j].state=='W')   //满足条件的进程{if(sum[j].arr_time<=time)  //如果上一个进程结束，已经有进程达到到达时间{//找最高优先级if(min>sum[j].priority)min=sum[j].priority;k=j;}elsetime++;}}sum[k].sta_time=time;sum[k].fin_time=sum[k].sta_time+sum[k].ser_time;sum[k].tur_time=sum[k].fin_time-sum[k].arr_time;sum[k].wtur_time=sum[k].tur_time/sum[k].ser_time;sum[k].state='F';time=sum[k].fin_time;}}Output2(sum,count);
}int main()
{list p[Max];                  //最多可以一百个作业int job_count = 0;             //作业数量int flag = 1;                  //算法标记int i = 0;printf("请输入作业数量：");scanf("%d",&job_count);printf("请输入作业ID，到达时刻，估计运行时间(用空格隔开)：\n");for(i=0; i<job_count; i++){printf("请输入进程%d的名称ID，到达时刻，服务时间，优先级(用空格隔开)：",i+1);scanf("%s %f %f %d",&p[i].name,&p[i].arr_time,&p[i].ser_time,&p[i].priority);p[i].sta_time=0;p[i].cpu_time=0;p[i].need_time=p[i].ser_time;p[i].tur_time=0;p[i].wtur_time=0;p[i].state='W';}printf("请选择算法：\n1,   先来先服务算法！\n2,   最短作业优先算法！\n3,  非抢占式优先级优先算法！\n");scanf("%d",&flag);switch(flag){case 1 :{printf("\n*******************************************\n\n");printf("先来先服务算法\n");FCFS(p,job_count);avg(p,job_count);}break;case 2 :{printf("\n*******************************************\n\n");printf("最短作业优先算法\n");SJF2(p,job_count);avg(p,job_count);for(i=0; i<job_count; i++)p[i].state='W';SJF1(p,job_count);}break;case 3:{printf("\n*******************************************\n\n");printf("非抢占式优先级优先算法\n");HPF(p,job_count);avg(p,job_count);}break;}return 0;
}

还有很多不足，欢迎大家指正

本文标签： 关于常见的一些进程调度 FCFS SPF HPF