你的位置:首页 > 操作系统

[操作系统]操作系统——进程调度之短进程优先


 1、什么是进程调度

  无论是在批处理系统还是分时系统中,用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外,系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略,动态地把处理机分配给处于就绪队列中的某一个进程,以使之执行。   

 

2、处理机调度分类

高级、中级和低级调度作业从提交开始直到完成,往往要经历下述三级调度:
  • 高级调度:(High-Level Scheduling)又称为作业调度,它决定把后备进程调入内存运行; 
  • 低级调度:(Low-Level Scheduling)又称为进程调度,它决定把就绪队列的某进程获得CPU; 
  • 中级调度:(Intermediate-Level Scheduling)又称为在虚拟存储器中引入,在内、外存对换区进行进程对换

3、短进程优先

最短CPU运行期优先调度算法(SCBF--Shortest CPU Burst First)
该算法从就绪队列中选出下一个“CPU执行期最短”的进程,为之分配处理机
例如,在就绪队列中有四个进程P1、P2、P3和P4,它们的下一个执行
期分别是16、12、4和3个单位时间,执行情况如下图:
P1、P2、P3和P4的周转时间分别为35、19、7、3,平均周转时间为16。
该算法虽可获得较好的调度性能,但难以准确地知道下一个CPU执行期,而只能根据每一个进程的执行历史来预测。
 
4、C语言模式实现
  1》、常量声明和数据结构定义
#include "stdio.h"#include <stdlib.h>#include "string.h"#define NULL 0typedef struct pcb{  char name[10]; //进程名称  int ArrivalTime; //到达时间   int StartTime;  //开始运行时间  int FinishTime; //结束运行时间  int WholeTime;  //运行所需时间  struct pcb *link; //下一个指针 }pcb; int N; //运行的进程数量 void input();pcb *ready=NULL,*p=NULL,*finish = NULL; //ready 是初始时的状态,finish 是结束时状态 int M; 

 


  2》、输入进程信息函数
void input(){  printf("请输入进程数量:");  scanf("%d",&N);  //N为全局变量  M = N;  struct pcb *q = ready;  int i = 0;  for( i=0 ;i<N;i++)  {    printf("请输入第 %d 个进程信息-----------\n",i+1);    p = (pcb *)malloc(sizeof(pcb));    printf("请输入进程名:")  ;    scanf("%s",p->name);    printf("请输入进程到达时间:");    scanf("%d",&p->ArrivalTime);    printf("请输入进程运行时间:");    scanf("%d",&p->WholeTime);    p->link = NULL;    if(NULL == ready)    {      ready = p;        q = ready;        }    else    {      q = ready;      while(NULL != q->link) //将q移动到就绪队列最后一个进程       {        q = q->link;      }      p->link = NULL;      q->link = p;        q=p;    }    printf("\n");  }  q= NULL;  free(q);  } 

 


  3》、短进程优先算法【核心代码】
//先输入的肯定是先到达的 //nowTime 是现在执行的时间 pcb* sjf(int nowTime,int *after){  int i = 0 ;  pcb *nowProgress=NULL, *p = ready;  int ProgressNum = 0; // 当前最短的是第几个线程   int minTime =0; // 最短运行时间    if(NULL != ready)  {    while(NULL != p) //遍历整个链表,查找出最短的进程,即运行时间最短     {    //  printf("\n%d %d %d \n",p->ArrivalTime,nowTime >= p->ArrivalTime,nowTime) ;      if(nowTime >= p->ArrivalTime)      {         if(0 == minTime) //首次赋值         {          nowProgress = p;          minTime = p->WholeTime;                  }        else        {          if(p->WholeTime < minTime)          {            nowProgress = p;            minTime = p->WholeTime;          }        }                *after = minTime+nowTime;      }        p = p->link;    }  }     return nowProgress;  }

 


  4》、输出每个时刻的进程信息函数
void output(pcb *p,int now_time){  if(NULL == p)  {    printf("当前时刻:%d,暂无进程在运行!\n",now_time);  }  else  {      printf("进程名:%s,运行时间:%d,到达时间:%d\n",p->name,p->WholeTime,p->ArrivalTime);      }  }

 

  5》、输出进程运行总体情况统计


void outputAll(){  pcb *p = finish;  printf("\n-----------------------统计结果:-------------------\n");  float avgRevolve = 0;  float avgSuperRevolve = 0;     while(NULL != p)  {    avgRevolve += p->StartTime+p->WholeTime-p->ArrivalTime;    avgSuperRevolve += 1.0*(p->StartTime+p->WholeTime-p->ArrivalTime)/p->WholeTime;    printf("\n进程名:%s,开始时间%d,结束时间:%d,运行时间:%d,到达时间:%d\n",p->name,p->StartTime,p->FinishTime,p->WholeTime,p->ArrivalTime);    p = p->link;    }      printf("\n----这组进程平均周转时间:%f,平均带权平均周转时间:%f\n",avgRevolve/M,avgSuperRevolve/M);} 

   

  6》、删除准备队列(ready)已经运行的进程p ,添加到完成队列(finish)队列中 


// 删除准备队列(ready)已经运行的进程p ,添加到完成队列(finish)队列中 void destory(pcb *p,int now_time){  pcb *q = ready;  pcb *f = NULL;  if(strcmp(p->name,ready->name) == 0) //第一个进程   {    ready = ready ->link;  }  else //中间进程   {    q = ready;    while( (strcmp(q->link->name,p->name) != 0) && NULL != q->link) //找到p要删除的位置     {            q= q->link;            }      q->link = p->link;            }             //将已经运行的进程添加到finish队列     p->StartTime = now_time-p->WholeTime;      p->FinishTime = now_time;      if(NULL == finish) //第一个完成的进程     {      finish = p;      p->link = NULL;    }      else //中间完成的进程     {      f = finish;      while(NULL != f->link )        {        f = f->link;      }      f->link = p;      p->link = NULL;    }        N--; //等待进程减1 }

 


  7》、主函数
int main(){  input();  struct pcb *s = ready;   int now_time = 0 ;  struct pcb *nowProgress = NULL; //当前运行的进程   int *after = 0; //执行完一个进程之后的时间   int i = 0 ;      pcb *m = ready;    while(N > 0)//一次运行一个进程   {    nowProgress = sjf(now_time,&after);        if(NULL != nowProgress) //当前有进程在运行     {      for(;now_time < after;now_time++) //输出每个时刻运行的进程情况     {      printf("#################################################\n");      printf("当前时刻:%d\n",now_time);       printf("\n-------------当前执行进程:----------\n");         output(nowProgress,now_time);         printf("\n-------------等待执行进程:----------\n");      m=ready;      while(NULL != m)      {        if(m != nowProgress)        {          if(m->ArrivalTime <= now_time)          output(m,now_time);        }        m= m->link;      }      printf("#################################################\n\n");    }                printf("\n");      destory(nowProgress,now_time);           }    else  //没有进程在运行     {      output(nowProgress,now_time);      now_time ++;     }          }        outputAll();  return 0;}

 


  8》、测试
输入数据:

 
运行结果:

 
省略中途的截图,这里只给出最后的总计情况的截图
 

 
  实际上,进程调度有很多种进程调度的方式,不同的进程调度方式,他们的优缺点各有不同,而且他们的适用场景也不尽相同,这里只给出了短进程优先的调度方式。下面我们来比较一下,一些调度方式【只是部分】的优缺点:

1.先来先服务(FCFS, First Come First Serve),按先后顺序进行调度。 
(1)、适用场景:
比较有利于长进程,而不利于短进程。因为长进程会长时间占据处理机。
有利于CPU繁忙的进程,而不利于I/O繁忙的进程。 

(2)、优点:

有利于长进程,有利于等待时间久的进程,不会有进程长期等待而得不到响应。有利于CPU频繁的进程。

(3)、缺点:

不利于短进程,忽视了进程的运行时间。不利于I/O频繁的进程。

 

 

2. 响应比高者优先(HRN):FCFS和SJF的的折中,动态生成昨夜的优先级。

(1)、优点:

既考虑了进程的等待时间,又考虑了进程的运行时间,是FCFS和SJF的的折中,会考虑让进程短的先进行,随着长进程等待时间的增加,优先级相应的增加,使得通过一定时间的等待,必然有机会获得处理机。

(2)、缺点:

在每次进行调度之前,都需要先做响应比的计算,会增加系统的开销


3. 优先级法(Priority Scheduling):按照进程的优先级,对进程进程调度。

(1)、分类:
静态优先级:
  进程调度中的静态优先级大多按以下原则确定: 
  由用户自己根据进程的紧急程度输入一个适当的优先级。 
  由系统或操作员根据进程类型指定优先级。 
  系统根据进程要求资源情况确定优先级。 
  进程的静态优先级的确定原则: 
  按进程的类型给予不同的优先级。 
  将进程的情态优先级作为它所属进程的优先级。 
动态优先级:
  进程的动态优先级一般根据以下原则确定: 
  根据进程占用有CPU时间的长短来决定。 
  根据就绪进程等待CPU的时间长短来决定。 

(2)、优点:

可以通过优先级反映进程的紧迫程序,使比较紧迫的进程优先运行

(3)、缺点:

需要计算进程的优先级,会产生一定的开销。
4.短进程优先法(SJF, Shortest Job First):短进程优先运行,其目标是减少平均周转时间。 

(1) 优点: 
  比FCFS改善平均周转时间和平均带权周转时间,缩短进程的等待时间; 
  提高系统的吞吐量; 
(2) 缺点: 
  对长进程非常不利,可能长时间得不到执行; 
  未能依据进程的紧迫程度来划分执行的优先级; 
  难以准确估计进程(进程)的执行时间,从而影响调度性能。 

采用SJF算法时,人—机交互无法实现

 完全未考虑进程的紧迫程度,故不能保证紧迫性进程得到及时处理