一、SPF算法简介
SJF算法
SJFshortest job first)是以进程的运行时间长度作为优先级，进程运行时间越短，优先级越高。
SJF算法的缺点
必须预知进程的运行时间。即使是程序员也很难准确估计进程运行时间。如果估计过低，系统就可能按估计的时间终止进程的运行，但此时进程并未完成，故一般都会偏长估计
对长进程不利。长进程的周转时间会明显地增长。可怕的是，SJF算法完全忽视进程等待时间，可能使进程等待时间过长，出现饥饿现象。
人机无法实现交互。
完全未考虑进程的紧迫程度。不能保证紧迫性进程得到及时处理。
二、算法流程图
我做的流程图：http://www.processon.com/diagraming/5835692de4b086d1e79f81af
三、源代码
1. 变量声明与结构体定义
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 5 /* run this program using the console pauser or add your own getch, system"pause") or input loop */ 6 7 8 struct pcb{ 9 char name[10]; //进程名 10 int arrival_time; //进程到达时间) 11 int start_time; //进程开始时间 12 int need_time; //进程运行所需时间 13 int finish_time; //运行结束时间 14 struct pcb * link; //链接下一个pcb的指针 15 }; 16 17 18 int num = 0; //输入的进程数 19 typedef struct pcb PCB; //定义结构体变量 20 /* 21 结构体指针p指向 每新建的一个进程 22 ready指针指向链表的第一个pcb 23 finish指针指向完成队列的第一个pcb结构体 24 */ 25 struct pcb *p = NULL, *ready = NULL, *finish = NULL;
2. 输入函数
1 //用来测试链表建立，输入链表结构体数据 2 void print_test){ 3 int i; 4 struct pcb * test = ready; 5 fori=0;i<num;i++){ 6 printf" 进程号:%d,进程名:%s,进程到达时间:%d,进程完成时间:%d", 7 i,test->name,test->arrival_time,test->need_time); 8 ifNULL != test->link){ 9 test = test->link; 10 } 11 else{ 12 printf" test_link end "); 13 } 14 15 } 16 } 17 18 19 20 //输入函数，建立链表 21 void input){ 22 int i; 23 struct pcb * q; //定义结构体变量 24 printf"请输入进程数:"); 25 scanf"%d", &num); 26 fori=0; i<num; i++){ 27 printf" 进程号 NO.%d:", i); 28 p = struct pcb*)mallocsizeofstruct pcb)); 29 printf" 输入进程名:"); 30 scanf"%s", p->name); 31 printf" 请输入进程到达时间:"); 32 scanf"%d", &p->arrival_time); 33 printf" 请输入进程运行时间:"); 34 scanf"%d", &p->need_time); 35 36 p->link = NULL; 37 //建立链表 38 ifNULL == ready){ //建立第一个结构体，使指针p,q指向它 39 ready = p; 40 q = ready; 41 } 42 else{ //链表建立 43 q->link = p; 44 q = p; 45 } 46 printf"input success"); 47 } 48 print_test); //测试链表是否建立 49 }
3. 所有进程结束后，输出所有进程信息
1 //输出当前运行进程相关数据或者打印暂无进程运行 2 void outputstruct pcb * p, int now_time){ 3 ifNULL == p){ 4 printf"当前时刻:%d, 暂无进程在运行! ", now_time); 5 } 6 else{ 7 printf"进程名:%s,到达时间:%d,运行需要时间:%d ",p->name,p->arrival_time,p->need_time); 8 } 9 }
4. 找出运行时间最短的进程
1 //sjf shortest job first最短作业优先 2 struct pcb * SJFint now_time, int * after){ 3 int min_time = 0; //最短时间，即优先运行的进程的时间 4 struct pcb * now_progress = NULL, *p = ready; 5 //遍历链表，查找出运行时间最短的进程 6 if NULL != ready){ 7 whileNULL != p){ 8 ifnow_time >= p->arrival_time){ //若进程已经到达，注意：时间单位为1 9 /* 10 min_time = p->need_time; //是错误的 11 now_progress = p; 12 ifp->need_time < min_time){ 13 min_time = p->need_time; 14 now_progress = p; 15 } */ 16 if0 == min_time){ //给最短时间赋初值 17 now_progress = p; 18 min_time = p->need_time; 19 } 20 else{ 21 ifp->need_time < min_time){ 22 now_progress = p; 23 min_time = p->need_time; 24 } 25 } 26 } 27 p = p->link; 28 } 29 } 30 *after = min_time + now_time; 31 printf" SJF:a shortest progress running! "); 32 return now_progress; //返回指向正在运行进程的指针 33 }
4. 进程执行完毕
1 //将已经运行完成的进程添加到finish队列，并且进程数减一 2 void destorystruct pcb * p, int now_time){ 3 printf"destory start! "); 4 struct pcb * q = ready; 5 struct pcb * f = NULL; //用于finish链表的添加 6 7 8 ifstrcmpp->name, ready->name) == 0){ //若第一个进程完成 9 ready = ready->link; 10 } 11 //若中间或最后一个进程完成 12 else{ 13 q = ready; 14 whilestrcmpq->link->name,p->name) != 0) && NULL != q->link){ 15 q = q->link; 16 } 17 q->link = p->link; 18 } 19 20 p->finish_time = now_time; //结束时间 21 p->start_time = now_time - p->need_time; //开始时间 22 23 //将已经运行的进程添加到finish队列 24 ifNULL == finish){ 25 finish = p; //finish指向完成链表的表头 26 p->link = NULL; 27 } 28 else{ 29 f = finish; 30 whileNULL != f->link){ 31 f = f->link; 32 } 33 f->link = p; 34 p->link = NULL; 35 } 36 37 num--; //进程数减一 38 printf" destory success! "); 39 }
5. 主函数
1 int mainint argc, char *argv[]) { 2 3 4 input); //调用输入函数 5 6 int now_time = 0; //初始时间为0 7 int after = 0; //执行完一个进程后的时间:优先运行进程的运行时间+当前时间 8 struct pcb * now_progress = NULL; //now_progress指向正在运行的进程结构体) 9 struct pcb *m = NULL; 10 11 whilenum > 0){ //进程数大于0,每次循环num会减一 12 printf"start SJF"); 13 now_progress = SJFnow_time, &after); //调用SJF函数，遍历链表 14 15 16 ifNULL != now_progress){ 17 /*进程执行，每循环一次，当前时间加一 18 同时要判断当前时间是否有进程刚好到达正在在等待 */ 19 for;now_time < after; now_time++){ 20 printf" 当前时刻:%d", now_time); 21 printf" -----------当前执行进程------------ "); 22 outputnow_progress, now_time); //调用output函数 23 printf" -----------等待执行进程------------ "); 24 25 m = ready; 26 whileNULL != m){ //循环，若当前时间有进程到达，打印相关信息 27 ifm != now_progress){ 28 ifm->arrival_time <= now_time){ 29 outputm, now_time); 30 printf" a new progress arrival "); 31 } 32 } 33 m = m->link; 34 } 35 } 36 //进程执行完后调用destory函数 37 destorynow_progress, now_time); 38 39 } 40 else{ //没有进程在运行 41 outputnow_progress, now_time); 42 now_time++; 43 } 44 45 } 46 output_all); 47 return 0; 48 49 }
我写得这么清楚，加上我画的流程图，相信你可以懂的~~
四、测试
五、坑
原本这个函数我是这样写的，但发现运行结果不对~
按上面代码的运行结果：
按理说，a进程执行后不应该是e进程执行，应该是运行时间最短的d进程执行。同理之后是b, e, c;
我又回去看前面的代码，改正如下：
运行结果：
六、总结知识点
p = struct pcb*)mallocsizeofstruct pcb))与p = struct pcb*)mallocsizeofPCB))相同, PCB是结构体struct pcb的一个结构体变量。
在使用字符串处理函数puts,gets,strcat,strcpy,strcmp,strlen,strlwr)时，应当在程序文件的开头用#include<string.h>，把”string.h”文件包含到本文件中。
malloc函数。比如：malloc100) 开辟100字节的临时分配域，函数值为其第1个字节的地址。只提供一个地址。若函数不能成功执行比如内存不足)，则返回空指针。int*)mallocsizeofint)) 将申请得到的空间地址转换成了int类型空间地址最后就可以赋值给指向int型空间的p指针了。
总代码
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 5 /* run this program using the console pauser or add your own getch, system"pause") or input loop */ 6 7 8 struct pcb{ 9 char name[10]; //进程名 10 int arrival_time; //进程到达时间) 11 int start_time; //进程开始时间 12 int need_time; //进程运行所需时间 13 int finish_time; //运行结束时间 14 struct pcb * link; //链接下一个pcb的指针 15 }; 16 17 18 int num = 0; //输入的进程数 19 typedef struct pcb PCB; //定义结构体变量 20 /* 21 结构体指针p指向 每新建的一个进程 22 ready指针指向链表的第一个pcb 23 finish指针指向完成队列的第一个pcb结构体 24 */ 25 struct pcb *p = NULL, *ready = NULL, *finish = NULL; 26 27 28 //用来测试链表建立，输入链表结构体数据 29 void print_test){ 30 int i; 31 struct pcb * test = ready; 32 fori=0;i<num;i++){ 33 printf" 进程号:%d,进程名:%s,进程到达时间:%d,进程完成时间:%d", 34 i,test->name,test->arrival_time,test->need_time); 35 ifNULL != test->link){ 36 test = test->link; 37 } 38 else{ 39 printf" test_link end "); 40 } 41 42 } 43 } 44 45 46 47 //输入函数，建立链表 48 void input){ 49 int i; 50 struct pcb * q; //定义结构体变量 51 printf"请输入进程数:"); 52 scanf"%d", &num); 53 fori=0; i<num; i++){ 54 printf" 进程号 NO.%d:", i); 55 p = struct pcb*)mallocsizeofstruct pcb)); 56 printf" 输入进程名:"); 57 scanf"%s", p->name); 58 printf" 请输入进程到达时间:"); 59 scanf"%d", &p->arrival_time); 60 printf" 请输入进程运行时间:"); 61 scanf"%d", &p->need_time); 62 63 p->link = NULL; 64 //建立链表 65 ifNULL == ready){ //建立第一个结构体，使指针p,q指向它 66 ready = p; 67 q = ready; 68 } 69 else{ //链表建立 70 q->link = p; 71 q = p; 72 } 73 printf"input success"); 74 } 75 print_test); //测试链表是否建立 76 } 77 78 79 80 //sjf shortest job first最短作业优先 81 struct pcb * SJFint now_time, int * after){ 82 int min_time = 0; //最短时间，即优先运行的进程的时间 83 struct pcb * now_progress = NULL, *p = ready; 84 //遍历链表，查找出运行时间最短的进程 85 if NULL != ready){ 86 whileNULL != p){ 87 ifnow_time >= p->arrival_time){ //若进程已经到达，注意：时间单位为1 88 /* 89 min_time = p->need_time; //是错误的 90 now_progress = p; 91 ifp->need_time < min_time){ 92 min_time = p->need_time; 93 now_progress = p; 94 } */ 95 if0 == min_time){ //给最短时间赋初值 96 now_progress = p; 97 min_time = p->need_time; 98 } 99 else{ 100 ifp->need_time < min_time){ 101 now_progress = p; 102 min_time = p->need_time; 103 } 104 } 105 } 106 p = p->link; 107 } 108 } 109 *after = min_time + now_time; 110 printf" SJF:a shortest progress running! "); 111 return now_progress; //返回指向正在运行进程的指针 112 } 113 114 115 //输出当前运行进程相关数据或者打印暂无进程运行 116 void outputstruct pcb * p, int now_time){ 117 ifNULL == p){ 118 printf"当前时刻:%d, 暂无进程在运行! ", now_time); 119 } 120 else{ 121 printf"进程名:%s,到达时间:%d,运行需要时间:%d ",p->name,p->arrival_time,p->need_time); 122 } 123 } 124 125 126 //将已经运行完成的进程添加到finish队列，并且进程数减一 127 void destorystruct pcb * p, int now_time){ 128 printf"destory start! "); 129 struct pcb * q = ready; 130 struct pcb * f = NULL; //用于finish链表的添加 131 132 133 ifstrcmpp->name, ready->name) == 0){ //若第一个进程完成 134 ready = ready->link; 135 } 136 //若中间或最后一个进程完成 137 else{ 138 q = ready; 139 whilestrcmpq->link->name,p->name) != 0) && NULL != q->link){ 140 q = q->link; 141 } 142 q->link = p->link; 143 } 144 145 p->finish_time = now_time; //结束时间 146 p->start_time = now_time - p->need_time; //开始时间 147 148 //将已经运行的进程添加到finish队列 149 ifNULL == finish){ 150 finish = p; //finish指向完成链表的表头 151 p->link = NULL; 152 } 153 else{ 154 f = finish; 155 whileNULL != f->link){ 156 f = f->link; 157 } 158 f->link = p; 159 p->link = NULL; 160 } 161 162 num--; //进程数减一 163 printf" destory success! "); 164 } 165 166 167 168 void output_all){ 169 struct pcb * p = finish; 170 printf" ---------------统计结果---------------- "); 171 whileNULL != p){ 172 printf" 进程名:%s,开始时间:%d,结束时间:%d,运行时间:%d,到达时间:%d", 173 p->name,p->start_time,p->finish_time,p->need_time,p->arrival_time); 174 p = p->link; 175 } 176 } 177 178 179 180 int mainint argc, char *argv[]) { 181 182 183 input); //调用输入函数 184 185 int now_time = 0; //初始时间为0 186 int after = 0; //执行完一个进程后的时间:优先运行进程的运行时间+当前时间 187 struct pcb * now_progress = NULL; //now_progress指向正在运行的进程结构体) 188 struct pcb *m = NULL; 189 190 whilenum > 0){ //进程数大于0,每次循环num会减一 191 printf"start SJF"); 192 now_progress = SJFnow_time, &after); //调用SJF函数，遍历链表 193 194 195 ifNULL != now_progress){ 196 /*进程执行，每循环一次，当前时间加一 197 同时要判断当前时间是否有进程刚好到达正在在等待 */ 198 for;now_time < after; now_time++){ 199 printf" 当前时刻:%d", now_time); 200 printf" -----------当前执行进程------------ "); 201 outputnow_progress, now_time); //调用output函数 202 printf" -----------等待执行进程------------ "); 203 204 m = ready; 205 whileNULL != m){ //循环，若当前时间有进程到达，打印相关信息 206 ifm != now_progress){ 207 ifm->arrival_time <= now_time){ 208 outputm, now_time); 209 printf" a new progress arrival "); 210 } 211 } 212 m = m->link; 213 } 214 } 215 //进程执行完后调用destory函数 216 destorynow_progress, now_time); 217 218 } 219 else{ //没有进程在运行 220 outputnow_progress, now_time); 221 now_time++; 222 } 223 224 } 225 output_all); 226 return 0; 227 228 }
View Code