【操作系统原理】—— 进程调度

实验相关知识

1、进程调度算法：采用动态最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）

      动态最高优先数优先调度算法是一种进程调度算法，它根据进程的动态优先级来分配处理机。每个进程都被分配一个优先级数，该数值随时间的推移而变化。当一个进程等待时间较长时，其优先级就会提高，以增加它被选中执行的机会。以下是该算法的一般工作原理：

      初始化优先级： 每个进程在进入就绪队列时被分配一个初始优先级。这通常可以基于进程的属性，如等待时间、资源需求等。

      动态调整优先级： 随着时间的推移，等待时间增加的进程的优先级逐渐提高。这是为了避免长时间等待的进程饥饿，因为等待时间越长，该进程的优先级就越高，增加了它被选中执行的机会。

      选择最高优先级进程： 在每次调度时，选择具有最高优先级的进程来执行。这确保了被认为是最紧急的进程首先获得处理机。

      降低优先级： 一旦进程被选中执行，其优先级通常会降低，以确保其他等待时间较长的进程有机会被选中。

      这种调度算法的优势在于它可以适应系统的动态变化，更好地处理等待时间较长的进程。然而，可能存在的问题包括可能导致优先级逆转的情况，即优先级较低的进程长时间无法执行的问题。

2、每个进程有一个进程控制块（PCB）表示

进程控制块可以包含如下信息：

• 进程名----进程标示数ID；
• 优先数----Priority，优先数越大优先权越高；
• 到达时间----进程的到达时间为进程输入的时间；
• 进程还需要运行时间----AllTime，进程运行完毕AllTime =0；
• 已用CPU时间----CPUTime；
• 进程的阻塞时间StartBlock----表示当进程在运行StartBlock个时间片后，进程将进入阻塞状态；
• 进程的阻塞时间StartTime----表示当进程阻塞StartTime个时间片后，进程将进入就绪状态；
• 进程状态----State；
• 队列指针----Next，用来将PCB排成队列。

3、调度原则

• 进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间；
• 进程的运行时间以时间片为单位进行计算；
• 进程在就绪队列中带一个时间片，优先数加1；
• 每个进程的状态可以是就绪R（Ready）、运行R（Run）、阻塞B(Block)、或完成F（Finish）四种状态之一；
• 就绪进程获得CPU后都只能运行一个时间片，用已占用CPU时间加1来表示；
• 如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减3，然后把它插入就绪队列等待CPU；
• 每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的PCB，以便进行检查；
  重复以上过程，直到所要进程都完成为止。

实验设备与软件环境

安装环境:分为软件环境和硬件环境

硬件环境：内存ddr3 4G及以上的x86架构主机一部

系统环境：windows 、linux或者mac os x

软件环境：运行vmware或者virtualbox

软件环境：Ubuntu操作系统

实验内容

一、一个简单的进程调度模拟程序的实现

1.程序需要运用进程调度算法：采用动态最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）

对进程的优先调度不清楚，代码执行会混乱。

解决方法：通过Sort()函数对进程进行优先级排列（这里体现的是优先数最高的进程排到最前面）

      通过Sort()函数对进程进行优先级排列（这里体现的是优先数最高的进程排到最前面）。

Sort()函数

2.每个进程有一个进程控制块（PCB）表示

本程序里面进程控制块包含如下信息：

      进程名——进程标示数ID；

      优先数——Priority，优先数越大优先权越高；

      到达时间——Time,进程的到达时间为进程输入的时间；

      进程还需要运行时间——AllTime，进程运行完毕AllTime =0；

      进程的总时间——totletime，计算该进程的总时间，最开始就是该进程需要的完成时间。每经过了一次时间片，所需要完成的时间就相继-1。

      已用CPU时间——CPUTime；

      进程的阻塞时间StartBlock——表示当进程在运行StartBlock个时间片后，进程将进入阻塞状态；

      进程的阻塞时间StartTime——表示当进程阻塞StartTime个时间片后，进程将进入就绪状态；

      进程状态——State；每个进程都会有对应着四种状态：Ready（就绪）：W、Run（运行）：R、Block（阻塞）：B、Finish（结束）：F。

      队列指针——Next，用来将PCB排成队列。

进程控制块PCB

      程序通过OutPut(struct PCB * pr)函数在每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。

会显示当前进程的进程ID，状态（state）、优先数（Priority）、进程还需要运行时间（ALLTime）、已用 CPU 时间（CPUTime）。

      值得注意的是，当totletime（进程的总时间）等于0的时候，代表该进程完成了，此时进程的状态为结束，即F(Finish )。

      否则此时进程的状态根据运行的情况来得知是就绪W（Ready））、运行R(Run)还是堵塞B(Block)。

显示当前进程

3. 调度原则

3.1 进程的优先数及需要的运行时间可以事先人为地指定

      通过Input()函数输入进程控制块信息。输入进程的信息包括进程优先数和进程需要运行时间。接着对于CPUTime、StartBlock、StartTime进行初始化为0。

      初始化进程状态（State）–> Ready（就绪），以及将 进程需要运行时间赋值给totletime。

Input()函数输入进程控制块信息

3.2 进程的运行时间以时间片为单位进行计算；进程在就绪队列中带一个时间片，优先数加1

      Check()函数查看进程情况，如果进程在就绪队列中带一个时间片，优先数加1；

Check()函数建立进程查看

3.3 每个进程的状态可以是就绪 R（Ready）、运行 R（Run）、阻塞 B(Block)、或完成 F（Finish）四种状态之一

      因为就绪和运行的首字母都是R，为了方便区分，我设置就绪为W、运行为R。阻塞还是B，结束还是F。

进程状态

3.4 如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减3，然后把它插入就绪队列等待CPU

Destroy()和Running()函数

3.5 每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查

      通过OutPut(struct PCB * pr)函数能显示当前进程的进程ID，状态（state）、优先数（Priority）、进程还需要运行时间（ALLTime）、已用 CPU 时间（CPUTime）。

      值得注意的是，当totletime（进程的总时间）等于0的时候，代表该进程完成了，此时进程的状态为结束，即F(Finish )。

否则此时进程的状态根据运行的情况来得知是就绪W（Ready））、运行R(Run)还是堵塞B(Block)。

OutPut(struct PCB * pr)函数

二、进程调度模拟程序的程序代码

优化过后的程序代码：

#include<stdio.h>
#include<stdlib.h>
//ZShiJ
//每个进程都会有对应着四种状态：就绪：W、运行：R、阻塞：B、结束：F，在每个时间片时，都会有对应的状态显示。
enum STATE {//就绪：W、运行：R、阻塞：B、结束：F
    Ready='W',Run='R',Block='B',Finish='F'
};
struct PCB {
  int ID;       //进程名
  int Priority;     //优先数
  int Time;       //到达时间
  int AllTime;    //进程还需要运行时间
  int totletime;    //进程的总时间
  int CPUTime;    //已用 CPU 时间
  int StartBlock;   //进程的进入阻塞时间
  int StartTime;    //进程的等待阻塞时间
  enum STATE State;   //进程状态
  struct PCB* Next;   //队列指针
}*ready=NULL,*p;
void Sort() { // 该程序采用最高优先级数优先的调度算法。
  // 建立对进程进行优先级排列函数
  PCB *first, *second;
  int insert=0;
  if(ready==NULL||(p->Priority>ready->Priority)) { //优先级最大者,插入队首
    p->Next=ready;
    ready=p;
  } else { // 进程比较优先级,插入适当的位置中
    first=ready;
    second=first->Next;
    while(second!=NULL) {
      if(p->Priority>second->Priority) { //若插入进程比当前进程优先数大
        //插入到当前进程前面
        p->Next=second;
        first->Next=p;
        second=NULL;
        insert=1;
      } else { // 插入进程优先数最低,则插入到队尾
        first=first->Next;
        second=second->Next;
      }
    }
    if(insert==0) first->Next=p;
  }
}
void Input() {
  // 输入进程控制块信息
  int i,num;
  //clrscr(); /*清屏*/
  //采用动态最高优先数优先的调度算法的进程调度模拟程序
  printf(" ________________________________________________________________\n");
  printf("|                                                                |\n");
  printf("|   欢迎使用采用动态最高优先数优先的调度算法的进程调度模拟程序   |\n");
  printf("|                          作者：ZShiJ                           |\n");
  printf("|________________________________________________________________|\n");
  printf("\n注意：进程(state)有四种状态：就绪：W、运行：R、阻塞：B、结束：F。\n");
  printf("__________________________________________________________________\n");
  printf("\n 请输入进程数量:");
  scanf("%d",&num);
  for(i=0; i<num; i++) {
    p=(struct PCB*)malloc(sizeof(struct PCB)); //动态生成
    p->ID=i+1;
    printf("\n 输入进程 %d 的信息:\n",p->ID);
    printf("\n     进程优先数:");
    scanf("%d",&p->Priority);
    printf("\n     进程需要运行时间:");
    scanf("%d",&p->AllTime);
    p->Time=3*i;
    p->CPUTime=0; //初始化 已用CPU时间=0
    p->StartBlock=0;//初始化 进程的阻塞时间=0
    p->StartTime=0; //初始化 进程的阻塞时间=0
    
    p->State=Ready;//初始化 进程状态 --> Ready（就绪）
    p->Next=NULL;
    p->totletime=p->AllTime;/*计算该进程的总时间，最开始就是该进程需要的完成时间*/
    p->Next=NULL;     /*让队列持续进行*/
    printf("\n");
    Sort(); /* 调用 sort 函数*/
  }
}
int Length() {
  int l=0;
  struct PCB* pr=ready;
  while(pr!=NULL) {
    l++;
    pr=pr->Next;
  }
  return(l);
}
void OutPut(struct PCB * pr) { //显示当前进程
  //四种状态：就绪：W、运行：R、阻塞：B、结束：F
  printf("\n进程ID 状态    优先数    进程还需要运行时间         已用 CPU 时间");
  printf("\n ID    state  Priority  ALLTime(还需要运行的时间)    CPUTime \n");
  printf(" %d\t",pr->ID);
  if(pr->totletime==0)
    printf("F\t");
  else
    printf("%c\t",pr->State);
  printf(" %d\t",pr->Priority);
  printf(" %d\t\t\t\t",pr->totletime);
  printf(" %d\t",pr->CPUTime);
  printf("\n\n");
}
void Check() { // 建立进程查看函数
  struct PCB* pr;
  printf("\n ·········当前正在运行的进程如下显示·········\n\n"); //显示当前运行进程
  OutPut(p);
  pr=ready;
  printf("\n ·········当前就绪队列状态如下显示·········\n"); //显示就绪队列状态
  if(pr==NULL) {
    printf("\n -------------------当前就绪队列没有进程啦！------------------- \n");
  } else {
    while(pr!=NULL) {
      OutPut(pr);
      (pr->Priority)++;//进程在就绪队列中带一个时间片，优先数加 1*/
      pr=pr->Next;
    }
  }
}
void Destroy() { //建立进程撤消函数(进程运行结束,撤消进程)
  printf("\n\n 该时间片后进程 [%d] 已完成,信息如下：\n",p->ID);
  OutPut(p);
  // printf("\n");
  free(p);
}
void Running() { // 建立进程就绪函数(进程运行时间到,置就绪状态
  p->CPUTime++;
  p->totletime--;/*每经过了一次时间片，所需要完成的时间就相继-1*/
  p->State=Run;
  if(p->CPUTime==p->AllTime)
    Destroy(); //调用 Destroy() 函数
  else {
//    (p->Priority)--;
    (p->Priority)-=3;/*当进程还需要继续运行，此时应将进程的优先数减 3*/
    p->State=Ready;
    Sort(); //调用 sort 函数
  }
}
int main() { //主函数
  int len,h=0;
  char ch;
  Input();
  len=Length();
  while((len!=0)&&(ready!=NULL)) {
    ch=getchar();
    h++;
    printf("\n             ! ! !目前执行的是第【%d】个时间片! ! ! \n",h);
    p=ready;
    ready=p->Next;
    p->Next=NULL;
    // p->State=Ready；
    p->State=Run;/*开始运行程序*/
    Check();
    Running();
    printf(" ________________________________________________________________ \n");
    printf(" ---------------------------------------------------------------- \n");
    printf("\n 按任意键继续......");
    
    //ch=getchar();
  }
  printf("\n\n 所有进程已经完成.\n");
  ch=getchar();
}

三、进程调度模拟程序执行结果与分析

1.运行结果

（1）单进程运行情况

进程信息：

      进程ID：1

      优先级：6

      所需要的运行时间：3

运行截图：

输入单进程控制块信息

第1个时间片

第2个时间片

单进程运行结束

（2）双进程运行情况

进程信息：

      进程 ID：1

      优先级：6

      所需要的运行时间：2

      进程 ID：2

      优先级：3

      所需要的运行时间：2

运行截图：

输入双进程控制块信息

第1个时间片

第2个时间片

第3个时间片

双进程运行结束

（3）多进程运行情况

进程信息：

      进程 ID：1

      优先级：6

      所需要的运行时间：2

      进程 ID：2

      优先级：3

      所需要的运行时间：2

      进程 ID：3

      优先级：9

      所需要的运行时间：2

输入多进程控制块信息

第1个时间片

第2个时间片

第3个时间片

第4个时间片

第5个时间片

多进程运行结束

2.运行结果分析（以双进程为例）

输入双进程控制块信息：

输入双进程控制块信息

分析：

      通过Input()函数输入进程控制块信息。输入进程的信息包括进程优先数和进程需要运行时间。

      值得注意的是：每个进程都会有对应着四种状态：就绪W（Ready）、运行R(Run)、堵塞B(Block)、结束F(Finish )，在每个时间片时，都会有对应的状态显示。

      程序采用动态最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）。即通过Sort()函数对进程进行优先级排列（这里体现的是优先数最高的进程排到最前面）。

时间片1：

第1个时间片

分析：

      如图可以发现，进程1的优先级数为6明显大于进程2的优先级数3，所以会先运行进程1，让进程2进入就绪队列，并且显示就绪状态W（Ready）。

正在运行的进程1在经过时间片1后，进程1的CPUTime会加 1。

时间片2：

第2个时间片

分析：

      通过实验要求，我们设计的程序对于要进行的进程有如下要求：

• 进程的运行时间以时间片为单位进行计算；
• 进程在就绪队列中带一个时间片，优先数加1；
• 就绪进程获得CPU后都只能运行一个时间片，用已占用CPU时间加1来表示；
• 如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减3，然后把它插入就绪队列等待CPU；

      在经历时间片1之后，进程1未达到所需要的运行时间，所以还需要持续运行，此时应该将进程1的优先数减3，接着插入就绪队列等待CPU，此时进程1的优先级数变为3；而经过第一个时间片后，CPU 时间就相对应加1，还需要的时间相应减 1。

      同时进程2在时间片1的时候是在就绪队列当中，带了一个时间片，所以优先数加1，此时进程2的优先级数为4；

      因此，在时间片2时，进程2的优先级数4大于进程1的优先级数3，因此进程2会显示运行状态，进程1显示就绪W（Ready）状态，插入就绪队列。后面依次类推。

      运行的进程 2 在经过时间片后，CPUTime 会加 1。

时间片3：

第3个时间片

分析：

      如同时间片2分析的一样，进程2经过第二个时间片后，仍未达到所需要的运行时间，还需要持续运行，因此进程2的优先数减3，插入就绪队列。

      同时，进程1在就绪队列带有了一个时间片，所以优先级数加1。

      在时间片3时。进程1的优先级数4大于进程2的优先级数1，因此进程1进行运行，进程2插入就绪队列。运行的进程1在经过时间片后，CPUTime会加1。

      执行完第3个时间片后，会发现进程1的CPU时间等于2，已经达到了所需要的运行时间，因此，进程1已经完成，显示状态为结束F(Finish )，CPUTime 为2。

时间片4：

双进程运行结束

分析：

      在第三个时间片后，目前就只剩下进程2仍未结束，因此直接进行运行进程2。运行的进程2在经过第四个时间片后，CPUTime 会加1，此时会发现也达到了需要的运行时间，至此，进程2的状态为结束F(Finish )。

      最后，所有进程均已完成。