操作系统进程调度算法（c语言实现）
- 格式：pdf
- 大小：286.90 KB
- 文档页数：11
操作系统进程调度算法（c语⾔实现）
进程调度算法
⼀、先来先服务（FCFS）
基本思想：先到达的进程先进⼊就绪队列，先进⾏调度的原则。⾮抢占⽅式。
⼆、短作业优先（SJF）
基本思想：根据进程中的执⾏时间，选取执⾏时间最短的作业优先调度；可有抢占或⾮抢占⽅式。
三、优先权⾼者优先（HPF）
基本思想：系统根据作业的优先权进⾏作业调度，每次选取优先权⾼的作业优先调度。作业的优先权通常⽤⼀个整数表⽰，也叫做优先数。
可有抢占或⾮抢占⽅式。
四、时间⽚轮转（RR）
基本思想：系统将所有的就绪进程按先来先服务的原则，排成⼀个队列，每次调度时，把CPU分配给队⾸进程，并令其执⾏⼀个时间⽚。时
间⽚结束之后，将该进程加到就绪队列队尾；然后再把处理机分配给就绪队列中新的⾸进程。
各程序的实现算法
（1）FCFS先来先服务
算法思想：①⾸先将输⼊的进程放⼊⼀个进程数组中，然后根据进程的到达时间进⾏排序（冒泡排序）。将最先到达的进程放⼊进程就绪队
列中。②当队列不空时，从队头取出⼀个进程来执⾏，直⾄此进程执⾏完，并将在此进程执⾏期间到达的进程依次加⼊进程就绪队列。③如
果队列为空，但进程数组中仍存在未到达的进程，这时将要到达进程加⼊进程就绪队列。
void FCFS(program pro[],int num){
printf("进程 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转时间\n");
sortWithEnterTime(pro,num); //按照到达顺序排序
programQueue* queue = (programQueue*)malloc(sizeof(programQueue));
Queueinit(queue); //初始化进程就绪队列
EnterQueue(queue,&pro[0]); //将第⼀个进程放⼊队列
int time = pro[0].enter_time;
int pronum=1; //记录当前已进⼊的进程
float sum_T_time = 0,sum_QT_time = 0 ;
while(queue->size>0){ //当队列不为空
program* curpro = poll(queue); //从进程队列中取出进程
if(timeenter_time) //如果此进程的进⼊时间⼤于此时的时间，需要将时间转换到此进程的到达时间
time = curpro->enter_time;
int done_time = time+curpro->running_time; //记录完成时间
int T_time = done_time - curpro->enter_time; //记录周转时间
sum_T_time += T_time;
float QT_time = T_time / (curpro->running_time+0.0) ; //记录带权周转
sum_QT_time += QT_time;
for(int tt = time;tt<=done_time&&pronum
if(tt>=pro[pronum].enter_time){ //程序执⾏时有程序到达则进⼊程序队列
EnterQueue(queue,&pro[pronum]);
pronum++;
}
}
printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\n",curpro->name,curpro->enter_time,curpro->running_time,time,done_time,T_time,QT_time); //输出结果
time += curpro->running_time;
if(queue->size==0&&pronum
EnterQueue(queue,&pro[pronum]);
pronum++;
}
}
printf("平均周转时间为%.2f\t平均带权周转时间为%.2f\n",sum_T_time/(num+0.0),sum_QT_time/(num+0.0));
}（2）短作业优先（SJF）
算法思想：①⾸先也是按进程的到达时间进⾏排序。让最先到达的进程⼊队。②当队列不空时，从队头取出⼀个进程来执⾏，直⾄此进程执
⾏完，设置⼀个变量记录此进程执⾏过程中所有到达的进程。③将这些到达的进程进⾏排序，按照进程服务时间的⼤⼩。然后将排序好的进
程数组中的进程依次加⼊进程队列。（只排当前进程执⾏期间到达的进程）④此时也要考虑如果队列为空，但进程数组中仍存在未到达的进
程，这时将要到达进程加⼊进程就绪队列。
void SJF(program pro[],int num) {
printf("进程 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转时间\n");
sortWithEnterTime(pro,num);
programQueue* queue = (programQueue*)malloc(sizeof(programQueue));;
Queueinit(queue);
EnterQueue(queue,&pro[0]); //第⼀个进程⼊队
int time = pro[0].enter_time;
int pronum=1; //记录当前的进程
float sum_T_time = 0,sum_QT_time = 0;
while(queue->size>0){
program* curpro = poll(queue); //从进程队列中取出进程
if(timeenter_time)
time = curpro->enter_time;
int done_time = time+curpro->running_time;
int T_time = done_time - curpro->enter_time;
float QT_time = T_time / (curpro->running_time+0.0) ;
sum_T_time += T_time;
sum_QT_time += QT_time;
int pre = pronum; //记录此进程执⾏期间第⼀个到达的进程的位置
for(int tt = time;tt<=done_time&&pronum
if(tt>=pro[pronum].enter_time){ // 统计从此任务开始到结束之间有⼏个进程到达
pronum++;
}
}
sortWithLongth(pro,pre,pronum);//将到达的进程按照服务时间排序
for(int i=pre;i
EnterQueue(queue,&pro[i]);
}
pre = pronum;
printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\n",curpro->name,curpro->enter_time,curpro->running_time,time,done_time,T_time,QT_time);
time += curpro->running_time;
if(queue->size==0&&pronum
EnterQueue(queue,&pro[pronum]);
pronum++;
}
}
printf("平均周转时间为%.2f\t平均带权周转时间为%.2f\n",sum_T_time/(num+0.0),sum_QT_time/num);
}
（3）优先权⾼者优先（HPF）
算法思想：①⾸先也是按进程的到达时间进⾏排序。让最先到达的进程⼊队。②当队列不空时，从队头取出⼀个进程来执⾏，直⾄此进程执
⾏完，设置⼀个变量记录此进程执⾏过程中所有到达的进程。③将这些到达的进程进⾏排序，按照进程优先权排序（权值⼩的先⼊）。然后
将排序好的进程数组中的进程依次加⼊进程队列。（只排当前进程执⾏期间到达的进程）④此时也要考虑如果队列为空，但进程数组中仍存
在未到达的进程，这时将要到达进程加⼊进程就绪队列。void HPF(program pro[],int num){
printf("进程 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转时间\n");
sortWithEnterTime(pro,num);
programQueue* queue = (programQueue*)malloc(sizeof(programQueue));;
Queueinit(queue);
EnterQueue(queue,&pro[0]);
int time = pro[0].enter_time;
int pronum=1; //记录当前的进程
float sum_T_time = 0,sum_QT_time = 0;
while(queue->size>0){
program* curpro = poll(queue); //从进程队列中取出进程
if(timeenter_time)
time = curpro->enter_time;
int done_time = time+curpro->running_time;
int T_time = done_time - curpro->enter_time;
float QT_time = T_time / (curpro->running_time+0.0) ;
sum_T_time += T_time;
sum_QT_time += QT_time;
int pre = pronum;
for(int tt = time;tt<=done_time&&pronum
if(tt>=pro[pronum].enter_time){ // 统计从此任务开始到结束之间有⼏个进程到达
pronum++;
}
}
sortWithPriority(pro,pre,pronum);//将到达的进程按照服务时间排序
for(int i=pre;i
EnterQueue(queue,&pro[i]);
}
pre = pronum;
printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\n",curpro->name,curpro->enter_time,curpro->running_time,time,done_time
,T_time,QT_time);
time += curpro->running_time;
if(queue->size==0&&pronum
EnterQueue(queue,&pro[pronum]);
pronum++;
}
}
printf("平均周转时间为%.2f\t平均带权周转时间为%.2f\n",sum_T_time/(num+0.0),sum_QT_time/(num+0.0));
}
（4）时间⽚轮转（RR）
算法思想：
①⾸先也是按进程的到达时间进⾏排序。让最先到达的进程⼊队。
②当队列不空时，从队头取出⼀个进程来执⾏。此时分两种情况
2.1、如果当前进程的剩余服务时间不⼤于时间⽚⼤⼩，说明此次将会将这个进程执 ⾏完毕，在此进程执⾏过程中到达的进程需要添加到进
