一、SPF算法简介

SJF算法

• SJF(shortest job first)是以进程的运行时间长度作为优先级，进程运行时间越短，优先级越高。

SJF算法的缺点

• 必须预知进程的运行时间。即使是程序员也很难准确估计进程运行时间。如果估计过低，系统就可能按估计的时间终止进程的运行，但此时进程并未完成，故一般都会偏长估计
• 对长进程不利。长进程的周转时间会明显地增长。可怕的是，SJF算法完全忽视进程等待时间，可能使进程等待时间过长，出现饥饿现象。
• 人机无法实现交互。
• 完全未考虑进程的紧迫程度。不能保证紧迫性进程得到及时处理。

二、算法流程图

 我做的流程图：http://www.processon.com/diagraming/5835692de4b086d1e79f81af

三、源代码

1. 变量声明与结构体定义

1 #include
2 #include
3 #include
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 for(i=0;iname,test->arrival_time,test->need_time);
8 if(NULL != test->link){
9 test = test->link; 10 } 11 else{ 12 printf("\ntest_link end\n"); 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 for(i=0; iname); 31 printf("\n请输入进程到达时间:"); 32 scanf("%d", &p->arrival_time); 33 printf("\n请输入进程运行时间:"); 34 scanf("%d", &p->need_time); 35
36 p->link = NULL; 37 //建立链表
38 if(NULL == 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 output(struct pcb * p, int now_time){ 3 if(NULL == p){ 4 printf("当前时刻:%d, 暂无进程在运行!\n", now_time); 5 } 6 else{ 7 printf("进程名:%s,到达时间:%d,运行需要时间:%d\n",p->name,p->arrival_time,p->need_time); 8 } 9 }

4.  找出运行时间最短的进程

1 //sjf shortest job first最短作业优先
2 struct pcb * SJF(int now_time, int * after){ 3 int min_time = 0; //最短时间，即优先运行的进程的时间
4 struct pcb * now_progress = NULL, *p = ready; 5 //遍历链表，查找出运行时间最短的进程
6 if (NULL != ready){ 7 while(NULL != p){ 8 if(now_time >= p->arrival_time){ //若进程已经到达，注意：时间单位为1
9 /*
10 min_time = p->need_time; //是错误的 11 now_progress = p; 12 if(p->need_time < min_time){ 13 min_time = p->need_time; 14 now_progress = p; 15 } */
16 if(0 == min_time){ //给最短时间赋初值
17 now_progress = p; 18 min_time = p->need_time; 19 } 20 else{ 21 if(p->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("\nSJF:a shortest progress running!\n"); 32 return now_progress; //返回指向正在运行进程的指针
33 }

4. 进程执行完毕

1 //将已经运行完成的进程添加到finish队列，并且进程数减一
2 void destory(struct pcb * p, int now_time){ 3 printf("destory start!\n");
4 struct pcb * q = ready; 5 struct pcb * f = NULL; //用于finish链表的添加
6
7
8 if(strcmp(p->name, ready->name) == 0){ //若第一个进程完成
9 ready = ready->link; 10 } 11 //若中间或最后一个进程完成
12 else{ 13 q = ready; 14 while((strcmp(q->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 if(NULL == finish){ 25 finish = p; //finish指向完成链表的表头
26 p->link = NULL; 27 } 28 else{ 29 f = finish; 30 while(NULL != f->link){ 31 f = f->link; 32 } 33 f->link = p; 34 p->link = NULL; 35 } 36
37 num--; //进程数减一
38 printf("\ndestory success!\n"); 39 }

5. 主函数

1 int main(int 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 while(num > 0){ //进程数大于0,每次循环num会减一
12 printf("start SJF"); 13 now_progress = SJF(now_time, &after); //调用SJF函数，遍历链表
14
15
16 if(NULL != now_progress){ 17 /*进程执行，每循环一次，当前时间加一 18 同时要判断当前时间是否有进程刚好到达正在在等待 */
19 for(;now_time < after; now_time++){ 20 printf("\n当前时刻:%d", now_time); 21 printf("\n-----------当前执行进程------------\n"); 22 output(now_progress, now_time); //调用output函数 23 printf("\n-----------等待执行进程------------\n"); 24 25 m = ready; 26 while(NULL != m){ //循环，若当前时间有进程到达，打印相关信息 27 if(m != now_progress){ 28 if(m->arrival_time <= now_time){ 29 output(m, now_time); 30 printf("\na new progress arrival\n"); 31 } 32 } 33 m = m->link; 34 } 35 } 36 //进程执行完后调用destory函数
37 destory(now_progress, now_time); 38
39 } 40 else{ //没有进程在运行
41 output(now_progress, now_time); 42 now_time++; 43 } 44
45 } 46 output_all(); 47 return 0; 48
49 }

 我写得这么清楚，加上我画的流程图，相信你可以懂的~~

四、测试

 

五、坑

原本这个函数我是这样写的，但发现运行结果不对~

按上面代码的运行结果：

 

按理说，a进程执行后不应该是e进程执行，应该是运行时间最短的d进程执行。同理之后是b, e, c;

我又回去看前面的代码，改正如下：

运行结果：

六、总结知识点

1. p = (struct pcb*)malloc(sizeof(struct pcb))与p = (struct pcb*)malloc(sizeof(PCB))相同, PCB是结构体struct pcb的一个结构体变量。

2. 在使用字符串处理函数(puts,gets,strcat,strcpy,strcmp,strlen,strlwr)时，应当在程序文件的开头用#include，把"string.h"文件包含到本文件中。

3. malloc函数。比如：malloc(100) 开辟100字节的临时分配域，函数值为其第1个字节的地址。只提供一个地址。若函数不能成功执行(比如内存不足)，则返回空指针。(int*)malloc(sizeof(int)) 将申请得到的空间地址转换成了int类型空间地址最后就可以赋值给指向int型空间的p指针了。