操作系统调度算法-短进程优先的调度算法(SPF)c语言实现
·
目录
一、算法原理
短进程优先调度算法的核心思想是：执行时间较短的进程会被优先调度执行，以减少平均等待时间和提高系统的响应速度。每个进程被分配一个执行时间，通常用一个整数来表示，执行时间越短表示优先级越高。当系统中有多个就绪进程时，调度程序会选择执行时间最短的进程进行执行。
二、算法步骤(两种步骤)
第一种（排序版）
首先对进程按照运行时间进行排序。
从排好序开始位置开始往后找，找已经到了的进程，如果找到了就交换位置并执行。如果没有找到，就表示所以进程没有到达，那就从开始位置找一个最早提交时间的进程并执行。
第二种（不排序版）
同时找在当前时间已经到了又是最小运行时间的进程，如果找到了，交换位置并执行，如果没有找到，就表示所以进程没有到达，那就从开始位置找一个最早提交时间的进程并执行。
三、算法时间计算
开始时间 =如果提交时间早于等于上一个完成时间，则开始时间为上一个完成时间;（第一个作业的开始时间=提交时间，也就是下标为0）
完成时间 =开始时间+运行时间 ；
周转时间 = 完成时间- 提交时间 ；
带权周转时间 = 周转时间 / 运行时间 ；
平均周转时间 = 周转时间总和 / 作业个数
平均带权周转时间 = 带权周转时间总和/ 作业个数
四、算法代码实现
1.结构体及结构体数组
#define MAX 4
struct PCB
{
int id; //进程号
double submittime; //提交时间
double runtime; //运行时间
double starttime; //开始时间
double finishtime; //完成时间
double cycletime; //周转时间
double qtt; //带权周转时间
};
//struct JCB jcb[10];
struct PCB pcb[MAX] = {
{1, 1.0, 2.0},
{2, 2.0, 1.0},
{3, 0.0, 2.0},
{4, 6.0, 1.0}
};2.进程位置交换函数
/// <summary>
/// 进程位置交换
/// </summary>
/// <param name="i"></位置i>
/// <param name="tmpNum"></位置tmpNum>
void swap_p(int i, int tmpNum)
{
struct PCB tmp = pcb[tmpNum];
pcb[tmpNum] = pcb[i];
pcb[i] = tmp;
}3.找早最提交的进程函数
/// <summary>
/// 在n个进程中，从j开始找到一个最早提交时间的进程
/// </summary>
/// <param name="n"></进程个数>
/// <param name="j"></开始位置>
void getMinSubmittime(int n, int j)
{
int tmpNum = j;
for (int i = j + 1; i < n - 1; i++)
{
struct PCB tmp = pcb[tmpNum];
if (pcb[i].submittime < tmp.submittime)
{
tmpNum = i;
}
}
swap_p(j,tmpNum);
}4.排序算法函数
/// <summary>
/// 在n个进程中，从=i开始直接插入排序按作业运行时间升序排序
/// </summary>
/// <param name="n"></进程个数>
/// <param name="i"></开始位置>
void InsertSort(int n, int i)
{
int start = i;
for (; i < n - 1; i++)
{
int end = i;
struct PCB tmp = pcb[end + 1];
while (end >= start && pcb[end].runtime > tmp.runtime)
{
pcb[end + 1] = pcb[end];
end--;
}
pcb[end + 1] = tmp;
}
}5.SPF算法函数
第一种（排序版）：
void SPF(int num)
{
getMinSubmittime(num, 0);//从0开始找到一个最早提交时间的进程,也就是第一个到了执行的进程
int i = 0;
pcb[i].starttime = pcb[i].submittime;
pcb[i].finishtime = pcb[i].starttime + pcb[i].runtime;
pcb[i].cycletime = pcb[i].finishtime - pcb[i].submittime;
pcb[i].qtt = pcb[i].cycletime / pcb[i].runtime;
for (i = 1; i < num; i++)
{
InsertSort(num, i);//从=i开始直接插入排序按作业运行时间升序排序
int flagnum = -1;
//从排好序i位置开始往后找，找已经到了的进程
for (int j = i; j < num; j++) {
if (pcb[j].submittime <= pcb[i - 1].finishtime)
{
flagnum = j;
break;
}
}
if (flagnum != -1)//如果找到了就叫互换
{
swap_p(i, flagnum);
}
else//如果没有找到，就表示所以进程没有到达，那就从j开始找一个最早提交时间的进程
{
getMinSubmittime(num, i);
}
//计算
if (pcb[i].submittime <= pcb[i - 1].finishtime)
{
pcb[i].starttime = pcb[i - 1].finishtime;
}
else
{
pcb[i].starttime = pcb[i].submittime;
}
pcb[i].finishtime = pcb[i].starttime + pcb[i].runtime;
pcb[i].cycletime = pcb[i].finishtime - pcb[i].submittime;
pcb[i].qtt = pcb[i].cycletime / pcb[i].runtime;
}
}第二种（不排序版）：
/// <summary>
/// 同时找在当前时间已经到了又是最小运行时间的进程
/// </summary>
/// <param name="n"></进程个数>
/// <param name="j"></开始位置>
/// <param name="nowtime"></当前时间>
void getMinSubtime_runtime(int n, int j, int nowtime)
{
int tmpNum = j;
double tmprun = INT_MAX;
int flag = -1;
for (int i = j; i < n; i++)
{
struct PCB tmp = pcb[tmpNum];
//找已经到了又是最小运行时间
if (pcb[i].submittime <= nowtime && pcb[i].runtime <= tmprun)
{
tmpNum = i;
flag = 1;
tmprun = pcb[i].runtime;//更新最小运行时间
}
}
//判断有没有找到,不能用if (tmpNum !=j),因为可能符合条件的就是j
if (flag == 1)
{
swap_p(j, tmpNum);
}
else {
getMinSubmittime(n, j);
}
}
void SPF2(int num)
{
getMinSubmittime(num, 0);//从0开始找到一个最早提交时间的进程,也就是第一个到了执行的进程
int i = 0;
pcb[i].starttime = pcb[i].submittime;
pcb[i].finishtime = pcb[i].starttime + pcb[i].runtime;
pcb[i].cycletime = pcb[i].finishtime - pcb[i].submittime;
pcb[i].qtt = pcb[i].cycletime / pcb[i].runtime;
for (i = 1; i < num; i++)
{
int newtime = pcb[i - 1].finishtime;//当前时间就是上一个的完成时间
getMinSubtime_runtime(num, i, newtime);
//计算
if (pcb[i].submittime <= pcb[i - 1].finishtime)
{
pcb[i].starttime = pcb[i - 1].finishtime;
}
else
{
pcb[i].starttime = pcb[i].submittime;
}
pcb[i].finishtime = pcb[i].starttime + pcb[i].runtime;
pcb[i].cycletime = pcb[i].finishtime - pcb[i].submittime;
pcb[i].qtt = pcb[i].cycletime / pcb[i].runtime;
}
}6.信息展示函数
void showInfo(int num)
{
double acycletime = 0.0;
double aqtt = 0.0;
printf("进程号 \t提交时间\t运行时间\t开始时间\t完成时间\t周转时间\t带权周转时间\n");
for (int i = 0; i < num; i++)
{
printf("%d\t %0.1lf\t\t %0.1lf\t\t %0.1lf\t\t %0.1lf\t\t %0.1lf\t\t %0.1lf\n", pcb[i].id, pcb[i].submittime, pcb[i].runtime, pcb[i].starttime, pcb[i].finishtime, pcb[i].cycletime, pcb[i].qtt);
acycletime += pcb[i].cycletime;
aqtt += pcb[i].qtt;
}
printf("平均周转时间=%0.1lf\n", acycletime / num);
printf("平均带权周转时间=%0.1lf\n", aqtt / num);
}7.main函数
int main()
{
int num = MAX;
//SPF1(num);
SPF2(num);
showInfo(num);
return 0;
}五、实现效果
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
6
0- 0
已为社区贡献1条内容
所有评论(0)