短进程（作业）优先调度算法对五个进程进行调度。（C/C++）
程序员文章站
2024-03-24 19:32:58
...
实验描述： 用高级语言编写和调试一个进程调度程序，以加深对进程的概念及进程调度算法的理解。
- 设计简单的进程PCB 结构，完成进程信息记录；
- 设计一个有 N个进程并发执行的进程调度程序（以下三选一）
（1）编写并调试一个模拟的进程调度程序，采用“最高优先数优先”调度算法对五个进程进行调度。
（2）编写并调试一个模拟的进程调度程序，采用“轮转法”调度算法对五个进程进行调度。 轮转法可以是简单轮转法、可变时间片轮转法，或多队列轮转法。
（3）编写并调试一个模拟的进程调度程序，采用“短进程优先”调度算法对五个进程进行调度。 - 完成设计的调度算法的测试
使用下表进程（几乎同时到达）作为测试数据完成设计的调度算法的测试，输出各个进程的周转时间和带权周转时间，计算并输出平均周转时间和平均带权周转时间。
| 进程名 | 处理时间 | 优先级 |
|---|---|---|
| A | 3 | 2 |
| B | 6 | 1 |
| C | 4 | 3 |
| D | 5 | 4 |
| E | 2 | 5 |
一、设计简单的进程PCB 结构，完成进程信息记录；
//定义一个结构体：PCB
typedef struct PCB{
char processName[10]; //进程名
float arriveTime; //到达时间
float serviceTime; //服务时间
float startTime; //开始执行时间
float finishTime; //结束时间
float turnroundTime; //周转时间
float weightedTurnaroundTime; //带权周转时间
}pcb;
二、进程调度算法描述
进程调度算法：采用短进程（短作业）优先调度算法。即从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行，短作业优先调度算法从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，使之立即执行，直到完成或发生某事件而阻塞时，才释放处理机。
三、参考代码及测试
完整代码如下：
#include <stdlib.h>
#include <stdio.h>
//定义一个结构体：PCB
typedef struct PCB{
char processName[10]; //进程名
float arriveTime; //到达时间
float serviceTime; //服务时间
float startTime; //开始执行时间
float finishTime; //结束时间
float turnroundTime; //周转时间
float weightedTurnaroundTime; //带权周转时间
}pcb;
//输入进程信息，将N个进程的信息写入PCB型数组
void input(pcb *p,int N)
{
int i;
printf("\n");
printf("请输入进程的名字 到达时间 服务时间: (例如: A 0 100)\n");
for(i=0; i <= N-1; i++)
{
printf("请输入进程%d的信息：", i+1);
scanf("%s", &p[i].processName);
scanf("%f", &p[i].arriveTime);
scanf("%f", &p[i].serviceTime);
}
}
//对服务先后优先级排序
void sort(pcb *p, int N)
{
/*
1、对pcb型数组中的元素进行一个简单的排序
找到优先级最高的进程
并把其他进程也进行简单排序，方便后续工作
*/
//排序: N次循环,每次找到从i到N-1中优先级最高的进程，放到p[i]
for(int i=0;i<=N-1;i++)
{
//循环比较剩余的变量 //排序后：从0~N-1 arriveTime增加 ， arriveTime相同时， serviceTime短的优先
for(int j=i+1;j<N;j++)
{
if(p[i].arriveTime>p[j].arriveTime || (p[i].arriveTime==p[j].arriveTime && p[i].serviceTime>p[j].serviceTime) )
{
//p[j]的优先级高于p[i],因此把p[j]放到p[i]
pcb temp;
temp = p[i];
p[i] = p[j];
p[j] = temp;
}
}
}
//2、每个进程运行完成之后，找到当前时刻已经到达的最短进程P[0]优先级最高，
for(int m=0; m<N-1; m++)
{
if(m == 0)
p[m].finishTime = p[m].arriveTime + p[m].serviceTime;
else
p[m].finishTime = ((p[m-1].finishTime >= p[m].arriveTime)? p[m-1].finishTime: p[m].arriveTime) + p[m].serviceTime;
//(1)找到p[m].finishTime时刻哪些进程已经到达
int i=0; //i统计 p[m].finishTime时刻有几个进程已经到达
//从下一个进程p[m+1]开始寻找
for(int n = m+1; n <= N-1; n++)
{
if(p[n].arriveTime <= p[m].finishTime)
i++;
else
break;
/*由于在第1步已经对进程按照到达时间进行了排序
故：当p[n].arriveTime > p[m].finishTime时，
说明p[n]进程和其后面的其他进程都未到达。
i的值为p[m].finishtime时刻已经到达的进程数目。
*/
}
//(2)找到p[m].finishTime时刻已经到达的最短进程
float min = p[m+1].serviceTime; //next进程服务时间为p[m+1].serviceTime （初值）
int next = m+1; //next进程为m+1 （初值）
//p[m+1]至p[m+i]这i个已到达进程中找到最短进程
for(int k = m+1; k < m+i; k++) //k为m+1 ~ m+i-1
{
//min的初值是p[m+1].serviceTime, k+1为m+2 ~m+i
if(p[k+1].serviceTime < min)
{
min = p[k+1].serviceTime;
next = k+1;
}
}
//(3)把最短进程放在p[m+1]进程处
pcb temp;
temp=p[m+1];
p[m+1]=p[next];
p[next]=temp;
}
}
//运行
void run(pcb *p, int N)
{
int k;
//计算各进程的开始时间和结束时间
for(k=0; k <= N-1; k++)
{
if(k==0) //第1个进程
{
p[k].startTime = p[k].arriveTime; //第1个进程到达之后即可执行
p[k].finishTime = p[k].startTime + p[k].serviceTime;
}
else
{
p[k].startTime = (p[k-1].finishTime >= p[k].arriveTime)? p[k-1].finishTime: p[k].arriveTime;
p[k].finishTime = p[k].startTime + p[k].serviceTime;
}
}
//计算各进程的周转时间和带权周转时间
for(k=0; k<=N-1; k++)
{
p[k].turnroundTime = p[k].finishTime - p[k].arriveTime;
p[k].weightedTurnaroundTime = p[k].turnroundTime / p[k].serviceTime;
}
}
//打印结果
void Print(pcb *p, int N)
{
int k;
printf("\n调用最短进程优先算法以后进程运行的顺序是: ");
printf("%s",p[0].processName);
for(k=1;k<N;k++)
{
printf("-->");
printf("%s", p[k].processName);
}
printf("\n");
printf("具体进程调度信息:\n");
printf("进程名 到达时间 服务时间 开始时间 结束时间 周转时间 带权周转时间\n");
for(k=0; k<=N-1; k++)
{
printf("%4s", p[k].processName);
printf("%10.3f", p[k].arriveTime);
printf("%10.3f", p[k].serviceTime);
printf("%10.3f", p[k].startTime);
printf("%10.3f", p[k].finishTime);
printf("%10.3f", p[k].turnroundTime);
printf("%10.3f\n", p[k].weightedTurnaroundTime);
}
}
//短进程优先
void sjff(pcb *p,int N)
{
sort(p, N);
run(p, N);
Print(p, N);
int k;
float atTime = 0; // 平均周转时间
float AQTTime = 0; //平均带权周转时间
for(k=0; k<=N-1; k++)
{
atTime += p[k].turnroundTime;
AQTTime += p[k].weightedTurnaroundTime;
}
atTime = atTime/N;
AQTTime = AQTTime/N;
printf("\n调用短进程优先算法的平均周转时间为:");
printf("%.3f\n", atTime);
printf("调用短进程优先算法的平均带权周转时间为:");
printf("%.3f\n", AQTTime);
}
int main()
{
pcb a[50];
int N; //进程数目
printf("\n");
printf("\n");
printf("输入进程数目:");
scanf("%d", &N);
input(a, N);
sjff(a, N);
return 0;
}
测试结果：
由于数据给出的到达时间几乎相同，不能较好的测试短进程优先，以及在不同到达时间的作业调度情况，那么请看下面的一组测试数据：
再次调试程序，发现我们程序运行结果还是不错的。