调度算法—SJF调度算法详解

  • Post author:
  • Post category:其他




吐槽

上课时操作系统没咋学,倒不是不想学,实在是老师讲的太乏味,照着PPT读,今天学习SJF时,发现不少博客写错了,居然直接将服务时间排序而不考虑到达时间,导致我一下陷入自我怀疑。



SJF概念介绍

SJF,全称Short Job First,中文名:短作业优先调度算法

优点:考虑到作业的服务时间情况,降低了周转时间等相应时间;

缺点:有可能短进程一致插队,导致长进程处于长期饥饿状态;


理解误区:不是直接将进程按服务时间的长短排序后顺序执行!!,而是先按到达时间排序,若有多个进程的到达时间小于上一进程的结束时间,则将这多个进程按服务时间长短调度



SJF代码实现

CreateProcessQueue模块的实现思路和之前我写的先来先服务算法FCFS的CreateProcessQueue模块的实现思路一样,实现创建进程和初始化进程功能。

Sort模块的实现思路:

  • 冒泡算法

SJF模块的实现思路:

  1. 先将所有进程按到达时间排序,用sort函数实现;
  2. 利用循环体依次调度进程;
  3. 判断进程状态,‘f’为未调用;
  4. 先实现第一个进程;
  5. 往后的进程判断到达时间是否小于上一进程的结束时间;
  6. 若小于上一进程的结束时间,将小于上一进程结束时间的进程按服务时间排序,这里利用冒泡算法;
  7. 若大于,直接执行;

这里使用了数组存取进程,是因为SJF算法很少涉及插入删除操作,比较链表,还是数组更合适。

SJF算法的完整实现代码:

#include<stdio.h>
#include<stdlib.h>
#define MAX 100

typedef struct PCB{
	int no;
	char name[10];
	char State;
	int ArrivalTime;            //到达时间 
	int ServeTime;              //服务时间 
	int StartTime;              //开始时间 
	int EndTime;                //结束时间 
	float TurnaroundTime;       //周转时间 
	float TakePowerTime;        //带权周转时间 
	struct PCB *next;
}PCB;

PCB Queue[MAX] = {0};
int time;                       //计时器 
int n;							//进程数量 

void CreateProcessQueue(){
	printf("创建进程数:");
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		//进程初始化 
		Queue[i].State = 'f';           
		Queue[i].StartTime = 0;
		Queue[i].EndTime = 0;
		Queue[i].TakePowerTime = 0;
		Queue[i].TurnaroundTime = 0;
		printf("进程编号 进程名 到达时间 服务时间\n");
		scanf("%d %s %d %d",&Queue[i].no,&Queue[i].name,&Queue[i].ArrivalTime,&Queue[i].ServeTime);		
	}
}

void Run(PCB pcb){
	pcb.State = 't';
	pcb.StartTime = time;
	pcb.EndTime = pcb.ServeTime+pcb.StartTime;
	time = pcb.EndTime;
	pcb.TurnaroundTime = pcb.EndTime - pcb.ArrivalTime;
	pcb.TakePowerTime = pcb.TurnaroundTime/pcb.ServeTime;
	printf("进程编号 进程名 开始时间 结束时间 周转时间 带权周转时间\n");
	printf("%d       %s     %d        %d       %.2f     %.2f\n",pcb.no,pcb.name,pcb.StartTime,pcb.EndTime,pcb.TurnaroundTime,pcb.TakePowerTime);
}

void sort(){
	//按到达时间排序 
	for(int j=0;j<n;j++){
		for(int i=0;i<n-j-1;i++){
			if(Queue[i].ArrivalTime>Queue[i+1].ArrivalTime){
				PCB temp = Queue[i];
				Queue[i] = Queue[i+1];
				Queue[i+1] = temp;
			}	
		}
	}
}

void SJF(){
	sort();
	time = Queue[0].ArrivalTime;

	for(int i=0;i<n;i++){
		if(Queue[i].State = 'f'){
			if(i ==0){
				Run(Queue[i]);	
			}else if(Queue[i].ArrivalTime<time){
				int num = i;
				while(Queue[num].ArrivalTime<time && num<n){
					num++;
				}
				for(int x=i;x<num;x++){
					for(int t=i;t<num-x;t++){
						if(Queue[t].ServeTime>Queue[t+1].ServeTime){
							PCB temp = Queue[t];
							Queue[t] = Queue[t+1];
							Queue[t+1] = temp;
						}	
					}
				}
				Run(Queue[i]);
			}else{
				Run(Queue[i]);
			}				
		}
	}
}

int  main(){
	CreateProcessQueue();
	SJF();
	return 0;
}  


一些思考

我实现SJF算法时走了很多弯路,集中在SJF模块,我之前曾想若多个进程小于计时器时间,通过排序找到最小服务时间进程并执行,但这样就漏掉了最小服务时间进程前面的进程,因为循环体不会往前走。也曾想通过一些限制返回到漏掉的进程处重新开始,但没能实现。

之所以能用冒泡算法将小于计时器的进程排序,因为之后的进程必然在这些进程中选择执行,因为之前是按到达时间排序的。



版权声明:本文为weixin_44078014原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。