短进程优先算法C语言实现
目录：
1、实验说明：
2、程序定义：
3、源代码示例：
4、运行结果：
5、算法流程图：
6、C语言知识点：
1、实验说明：
答：本实验实现了短进程优先的进程调度操作，但因为是非抢占式，所以实现起来比较简单。
短进程优先算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行。
2、程序定义：
（1）PCB：
①作业号 ②到达时间 ③需要运行时间 ④开始时间 ⑤完成时间 ⑥周转时间 ⑦带权周转时间
（2）公式：
完成时间
周转时间
带权周转时间
（3）附：当全部进程执行完毕，
①打印出平均带权周转时间
②打印出调度顺序
③打印出平均周转时间
最先到的进程从0时刻到达，首先开始执行它。
比较处于等待队列中的进程的需要运行时间， 谁的需要运行时间短就先执行谁，如果需要运行时间相同则看它们的到达时间，到达时间早的先执行。
3、源代码示例：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TAKEIN "Takein"//吸纳状态
#define WAIT "Wait"//就绪状态
#define RUN "Run"//运行状态
#define FINISH "Finish"//完成状态
#define JOBNUMBER 5 //设置进程测试数为5
#define MIN 100
typedef struct PCB{
char jobName[10];//作业号
int arriveTime;//到达时间
int runTime;//需要运行时间
int startTime;//开始时间
int endTime;//完成时间
int turnoverTime;//周转时间
float useWeightTurnoverTime;//带权周转时间
char processStatus[10];//进程状态
};
static int currentTime = 0;
static int finishNumber = 0;
char JobArray[JOBNUMBER][10];
static int indexJob = 1;
//创建PCB
void createPCB(struct PCB* pcb){
freopen("input.txt","r",stdin);
printf("从文件中读入三个参数的数据：\n");
printf("作业号 到达时间 需要运行时间\n");
for(int i = 0; i < 5; i++){
scanf("%s", &pcb[i].jobName);//作业号
scanf("%d", &pcb[i].arriveTime);//到达时间
scanf("%d", &pcb[i].runTime);//需要运行时间
pcb[i].startTime = 0;
pcb[i].endTime = 0;
pcb[i].turnoverTime = 0;
pcb[i].useWeightTurnoverTime = 0.0;
strcpy(pcb[i].processStatus, TAKEIN);
printf("%s\t%d\t%d\n",pcb[i].jobName, pcb[i].arriveTime,pcb[i].runTime);
}
printf("---------------------------------------------\n");
}
//打印用途
void printJob(struct PCB* pcb){
printf("当前时间为%d\n", currentTime);
printf("作业号 到达时间 需要运行时间 开始时间 完成时间 周转时间 带权周转时间 进程状态\n");
for(int i = 0; i < JOBNUMBER; i++){
if(strcmp(pcb[i].processStatus, FINISH) == 0)//如果进程为finish状态，这样输出
printf("%s\t%d\t%4d\t\t%d\t%d\t %d\t%.2f\t%s\n", pcb[i].jobName, pcb[i].arriveTime, pcb[i].runTime, pcb[i].startTime, pcb[i].endTime, pcb[i].turnoverTime, pcb[i].useWeightTurnoverTime, pcb[i].processStatus);
else if(strcmp(pcb[i].processStatus, RUN) == 0)//如果进程为run状态，这样输出
printf("%s\t%d\t%4d\t\t%d\t运行中\t none\tnone \t%s\n", pcb[i].jobName, pcb[i].arriveTime, pcb[i].runTime, pcb[i].startTime, pcb[i].processStatus);
else //如果进程为take in或wait状态，这样输出
printf("%s\t%d\t%4d\t\t未运行\tnone\t none\tnone \t%s\n", pcb[i].jobName, pcb[i].arriveTime, pcb[i].runTime, pcb[i].processStatus);
}
printf("---------------------------------------------\n");
}
//根据当前时间修改status状态
void statusConfirm(struct PCB* pcb){
for(int i = 0; i < JOBNUMBER; i++){
//将当前时间为进程的到达时间，修改take in状态改为Wait状态
if(currentTime >= pcb[i].arriveTime && strcmp(pcb[i].processStatus, TAKEIN) == 0){
strcpy(pcb[i].processStatus, WAIT);
}
}
}
//确定当前时间wait进程中最短进程的数组下标,没有wait进程则返回-1
int shortIndex(struct PCB* pcb){
int min = MIN, temp = -1;
statusConfirm(pcb);
for(int i = 0; i < JOBNUMBER; i++){
if(strcmp(pcb[i].processStatus, WAIT) == 0){
if(pcb[i].runTime <= min){
min = pcb[i].runTime;
temp = i;
}
}
}
return temp;
}
//运行第一个到达的进程
void runFirstJob(struct PCB* pcb){
pcb[0].startTime = currentTime;
int endTime = pcb[0].startTime + pcb[0].runTime;
strcpy(pcb[0].processStatus, RUN);
while(true){
if(currentTime == endTime){
pcb[0].endTime = endTime;
pcb[0].turnoverTime = pcb[0].endTime - pcb[0].arriveTime;
pcb[0].useWeightTurnoverTime = pcb[0].turnoverTime * 1.0 / pcb[0].runTime;
strcpy(pcb[0].processStatus, FINISH);
finishNumber++;
break;
}
else{
statusConfirm(pcb);
printJob(pcb);
currentTime++;
}
}
}
//运行其他进程
void runOtherJob(struct PCB* pcb)
{
int index = shortIndex(pcb);
strcpy(JobArray[indexJob++], pcb[index].jobName);
if(index == -1) //没有进程处于wait状态
printJob(pcb);
else{
pcb[index].startTime = currentTime;
pcb[index].endTime = pcb[index].startTime + pcb[index].runTime;
pcb[index].turnoverTime = pcb[index].endTime - pcb[index].arriveTime;
pcb[index].useWeightTurnoverTime = pcb[index].turnoverTime * 1.0 / pcb[index].runTime;
strcpy(pcb[index].processStatus, RUN);
while(true){
statusConfirm(pcb);
if(currentTime == pcb[index].endTime){
strcpy(pcb[index].processStatus, FINISH);
finishNumber++;
if(finishNumber == JOBNUMBER){
printJob(pcb);
}
break;
}
else{
printJob(pcb);
currentTime++;
}
}
}
}
//比较各个进程之间的到达时间,按升序排列
void compare(struct PCB* pcb){
for(int i = 0; i < JOBNUMBER; i++){
int min = pcb[i].arriveTime;
int minIndex = i;
for(int j = i + 1; j < JOBNUMBER; j++){
if(pcb[j].arriveTime < min){
min = pcb[j].arriveTime;
minIndex = j;
}
}
struct PCB temp = pcb[i];
pcb[i] = pcb[minIndex];
pcb[minIndex] = temp;
}
}
//计算平均带权周转时间
float weightTurnoverTimeCount(struct PCB* pcb){
float sum = 0.0;
for(int i = 0; i < JOBNUMBER; i++){
sum += pcb[i].useWeightTurnoverTime;
}
return sum / JOBNUMBER;
}
//计算平均周转时间
float turnOverTimeCount(struct PCB* pcb){
float sum = 0.0;
for(int i = 0; i < JOBNUMBER; i++){
sum += pcb[i].turnoverTime;
}
return sum / JOBNUMBER;
}
//开始进程调度
void start(struct PCB* pcb){
compare(pcb);
int firstArriveTime = pcb[0].arriveTime;
//进程调度位currentTime每次加1，直到进程全部被调度完成为止
for(; finishNumber != 5; currentTime++){
if(currentTime < firstArriveTime)//当前时间小于第一个节点到来时间时，直接打印
printJob(pcb);
else if(currentTime == firstArriveTime)//当时间来到第一个进程的到达时间，调度该进程
runFirstJob(pcb);
else{ //根据短进程优先开始调度
currentTime--;
runOtherJob(pcb);
}
}
printf("1、进程调度顺序为：%s, %s, %s, %s, %s\n", pcb[0].jobName, JobArray[1], JobArray[2], JobArray[3], JobArray[4]);
printf("2、平均周转时间为：%.2f\n",turnOverTimeCount(pcb));
printf("3、平均带权周转时间为：%.2f\n", weightTurnoverTimeCount(pcb));
printf("------------------测试完毕 版权归邓钦艺所有---------\n");
}
//主函数
int main(){
struct PCB pcb[JOBNUMBER];
createPCB(pcb);
start(pcb);
return 0;
}4、运行结果：
（1）外部input.txt文件
图4.1 外部文件
（2）结果截图：
①当前时间为0时，五个进程全部进入到后备队列中，为take in状态；
当前时间为1时，job5开始执行，进程状态由take in转换为run；
当前时间为2时，job3到达，进程状态由take in转换为run；
当前时间为3时，job1到达，进程状态由take in转换为run，job5运行结束，进程状态由run转换为finish，job3开始执行，进程状态由wait转换为run
图4.2 结果截图1
②当前时间为5时，job3运行结束，进程状态由run转换为finish，job1到达时间为5，因此无需等待，直接运行，进程状态由take in直接转换为run；
当前时间为6时，job4到达，进程状态由take in转换为wait；
当前时间为8时，job2运行结束，进程状态由run转换为finish，job1开始执行，进程状态由wait转换为run；
图4.3 结果截图2
③当前时间为12时，job1运行结束，进程状态由run转换为finish，job4开始执行，进程状态由wait转换为run；
图4.4 结果截图3
④当前时间为17时，job4运行结束，进程状态由run转换为finish，五个进程状态均为finish，进程调度完毕，退出调度算法，打印出进程调度顺序，平均周转时间，以及平均带权周转时间。
图4.5 结果截图4
5、算法流程图：
图5.1 算法流程图
6、C语言知识点：
答：把大一的课件找到，将要用到的C语言基本知识复习了一下，做了些笔记。
①二级指针：指向指针的指针，指针变量中存放一级指针变量的地址。
②int **ptr：表示指向“一群”指向整数的指针的指针。
int *p[5]：表示指向5个指向整数的指针的指针。
int **ptr因为是指针的指针，需要两次内存分配才能使用其最终内容。
指针数组名p是二级指针常量，指针数组作形参，int **ptr与int *p[5]完全等价。
③内存动态分配：
A)非静态的局部变量是分配在内存中的动态存储区中的，这个存储区是称为栈的区域。
B)内存动态分配区域，用来存放一些临时用的数据，这些数据需要时随时开辟，不需要时随时释放，存放在堆区。
C)对内存的动态分配是通过系统提供的库函数来实现的，主要有malloc，calloc，free和realloc这四个函数。
④A)malloc函数（memory allocate）：
void *malloc(unsigned int size):在内存的动态存储区中分配一个长度为size的连续空间，返回的指针指向该分配域的开头位置。
B)calloc函数：
void *calloc(unsigned n, unsigned size)：在内存的动态存储区中分配n个长度为size的连续空间，函数返回指向所分配域的起始位置的指针；如果分配不成功，返回null。
C)free函数：
void *free(void * p)：释放指针变量p所指向的动态空间，使这部分空间能重新被其他变量使用。p应是最近一次调用calloc或malloc函数时得到的函数返回值。
D)realloc函数：
void *realloc(void * p, unsigned int size)：如果已经通过malloc函数或calloc函数获得了动态空间，想改变其大小，可以用recalloc函数重新分配。用realloc函数将p所指向的动态空间的大小改变为size。p的值不变。如果重分配不成功，返回NULL。
⑤结构体变量不能整体引用，只能引用变量成员。
引用方式：
a)结构体变量名.成员名
b)指针变量->成员名
ptr->num在计算机内部会被转化为(*ptr).num
虽然最后为了代码好写由指针全部推掉转换为了结构体数组，但复习过后，下次人工智能以及操作系统的实验都会用到。