计算机与信息技术学院综合性实验报告

专业：计算机科学与技术  年级/班级：20##级      20##—20##学年第一学期

一、    实验目的：

通过优先级调度算法的模拟，加深进程概念和进程调度过程的理解。

二、    实验仪器或设备：

微型计算机、Linux操作系统、dev C++

三、    总体设计：

1、设计原理及方案：1)在Linux下用C语言编程模拟优先级程调度算法。为了清楚地观察每个进程的调度过程，程序将每个时间片内的进程情况显示出来。2)进程控制块是进程存在的唯一标志，因此，在模拟算法中每一个进程用一个进程控制块PCB来代表，PCB用一结构体表示。3)进程在运行过程中其状态将在就绪、执行、完成几种状态之间转换，同时进程可能处于不同的队列中，如就绪队列。在优先级调度算法中，选择单向队列，入队既是将进程控制块插入队尾，出队既是按优先级重新排列的队，删除队头元素。4）为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先级认为输入，运行所需时间随机产生。5）优先权调度算法采用动态优先权，进程每运行一个时间片，优先数减1；进程在就绪队列等待一个时间单位，优先数加1。6）对于遇到优先权一致的情况，采用FCFS策略解决。7）由于是模拟进程调度，所以，对被选中的进程并不实际启动运行，而是修改进程控制块的相关信息来模拟进程的一次运行。

2、          分别用两种调度算法对伍个进程进行调度。每个进程可有三种状态；执行状态（R）、就绪状态（W,包括等待状态）和完成状态（F，并假定初始状态为就绪状态。

（1）进程控制块结构如下：
    name——进程标示符
    prio——进程优先数
    cputime——进程累计占用CPU的时间片数
   needtime——进程到完成还需要的时间片数
   state——进程状态
   next——链指针
   （2）进程的就绪态和等待态均为链表结构，共有四个指针如下：
      run——当前运行进程指针
      ready——就绪队列头指针
      tall——就绪队列尾指针
      finish——完成队列头指针

2、程序流程图：

四、    按照流程图编写代码

view plaincopy to clipboardprint?

/*   优先级调度算法   

#include <stdio.h>    

#include <stdlib.h>    

#include <string.h>    

typedef struct node    

{    

 char name[20];    /*进程的名字*/    

 int prio;     /*进程的优先级*/    

 int cputime;    /*CPU执行时间*/    

 int needtime;    /*进程执行所需要的时间*/    

 char state;/*进程的状态，W——就绪态，R——执行态，F——完成态*/    

 int count;     /*记录执行的次数*/    

 struct node *next;   /*链表指针*/    

 }PCB;    

PCB *ready=NULL,*run=NULL,*finish=NULL; /*定义三个队列，就绪队列，执行队列和完成队列*/    

int num;    

void GetFirst();    /*从就绪队列取得第一个节点*/    

void Output();     /*输出队列信息*/    

void InsertPrio(PCB *in);//创建优先级队列规定优先数越小优先级越高void PrioCreate();    /*优先级输入函数*/    

void Priority();    /*按照优先级调度*/    

int main(void)    

{  printf("请输入要创建的进程数目:\n");    

scanf("%d",&num);    

  getchar();    

  printf("优先级调度算法： \n");    

  PrioCreate();    

Priority();        

  Output();    

  return 0;    

}    

void GetFirst()  /*取得第一个就绪队列节点*/    

{  run = ready;    

  if(ready!=NULL)    

  { run ->state = 'R';    

    ready = ready ->next;    

   run ->next = NULL;    

  }    

}    

void Output()    /*输出队列信息*/    

{ PCB *p;    

  p = ready;    

  printf("进程名\t优先级\tcpu时间\t需要时间\t进程状态\t计数器\n");    

  while(p!=NULL)    

  {printf("%s\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->cputime,p->needtime,p->state,p->count);    

    p = p->next;   

  }    

  p = finish;    

  while(p!=NULL)    

  {printf("%s\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->cputime,p->needtime,p->state,p->count);    

    p = p->next;    

  }    

  p = run;    

  while(p!=NULL)    

  {printf("%s\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->cputime,p->needtime,p->state,p->count);    

    p = p->next;    

  }    

}    

void InsertPrio(PCB *in) //创建优先级队列，规定优先数越小，优先级越低 

{  PCB *fst,*nxt;    

  fst = nxt = ready;    

  if(ready == NULL)  /*如果队列为空，则为第一个元素*/    

  {  in->next = ready;    

    ready = in;    

  }    

  else     /*查到合适的位置进行插入*/    

  {if(in ->prio >= fst ->prio)/*比第一个还要大，则插入到队头*/  

    {  in->next = ready;    

      ready = in;    

    }    

    else    

  {while(fst->next != NULL)  /*移动指针查找第一个别它小的元素的位置进行插入*/    

      {  nxt = fst;    

        fst = fst->next;    

      }    

     if(fst ->next == NULL) /*已经搜索到队尾，则其优先级数最小，将其插入到队尾即可*/    

      {  in ->next = fst ->next;    

        fst ->next = in;    

      }    

      else     /*插入到队列中*/    

      {  nxt = in;    

        in ->next = fst;    

      }    

    }    

  }    

}    

void InsertTime(PCB *in)  /*将进程插入到就绪队列尾部*/    

{  PCB *fst;    

  fst = ready;    

  if(ready == NULL)    

  {  in->next = ready;    

    ready = in;    

  }    

  else    

  {while(fst->next != NULL)    

    {  fst = fst->next; }    

    in ->next = fst ->next;    

    fst ->next = in;    

  }    

}    

void InsertFinish(PCB *in)  /*将进程插入到完成队列尾部*/    

{  PCB *fst;    

  fst = finish;    

  if(finish == NULL)    

  {  in->next = finish;    

    finish = in;    

  }    

  else    

  {while(fst->next != NULL)    

    {fst = fst->next;}    

    in ->next = fst ->next;    

    fst ->next = in;    

  }    

}    

void PrioCreate() /*优先级调度输入函数*/    

{   PCB *tmp;      

  int i;    

  printf("输入进程名字和进程所需时间：\n");    

  for(i = 0;i < num; i++)    

  {if((tmp = (PCB *)malloc(sizeof(PCB)))==NULL)    

    { perror("malloc");    

      exit(1);}    

    scanf("%s",tmp->name);    

    getchar();    /*吸收回车符号*/    

    scanf("%d",&(tmp->needtime));    

    tmp ->cputime = 0;    

    tmp ->state ='W';    

    tmp ->prio = 50 - tmp->needtime;  /*设置其优先级，需要的时间越多，优先级越低*/    

    tmp ->count = 0;    

    InsertPrio(tmp);   /*按照优先级从高到低，插入到就绪队列*/ 

  }    

}    

void Priority()   /*按照优先级调度，每次执行一个时间片*/    

{  int flag = 1;    

  GetFirst();    

  while(run != NULL)//当就绪队列不为空时，则调度进程如执行队列

   {    

    Output();  /*输出每次调度过程中各个节点的状态*/    

    while(flag)    

    {    

     run->prio -= 3; /*优先级减去三*/    

     run->cputime++; /*CPU时间片加一*/    

     run->needtime--;/*进程执行完成的剩余时间减一*/    

     if(run->needtime == 0)/*如果进程执行完毕，将进程状态置为F，将其插入到完成队列*/    

      {  run ->state = 'F';    

        run->count++; /*进程执行的次数加一*/    

        InsertFinish(run);    

        flag = 0;    

      }    

      else   /*将进程状态置为W，入就绪队列*/    

      {  run->state = 'W';    

        run->count++; /*进程执行的次数加一*/    

        InsertTime(run);    

        flag = 0;    

      }    

    }    

    flag = 1;    

    GetFirst();    /*继续取就绪队列队头进程进入执行队列*/    

  }    

}    

显示结果：

请输入进程个数：

3

优先级调度算法：

输入进程名字和进程所需时间：

a 2 b 1 c 5

进程名   优先级   cpu时间     需要时间  进程状态   计数器

a         48        0            2        W          0

c         45        0            5        W          0

b         49        0            1        R          0

进程名   优先级   cpu时间     需要时间  进程状态   计数器

c         45        0            5        W          0

b         46        1            0        F          1

a         48        0            2        R          0

………

………

进程名   优先级   cpu时间     需要时间  进程状态   计数器

b         46        1            0        F          1

a         42        2            0        F          2

c         33        4            1        R          4

进程名   优先级   cpu时间     需要时间  进程状态   计数器

b        46        1            0        F          1

a        42        2            0        F          2

c        30        5            0        F          5

五、    结果分析与总结:

 这次实验使我加深对处理机进程调度机制的理解，对进程的概念有了更深一层次的认识。通过实现优先级调度算法，掌握进程状态转换过程和处理机调度策略的实现。在编程中我不仅对课本内容有了更好的理解也提高了自己的编程能力。

教师签名：

         年    月     日

 

第二篇：操作系统实验报告-进程调度

实验二进程调度

一、实验目的

在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态。当就绪进程个数大于处理器数时，就必须依照某种策略来决定哪些进程优先占用处理器。本实验模拟在单处理器情况下的处理器调度，帮助学生加深了解处理器调度的工作。

二、程序中使用的数据结构及符号说明

按优先数调度算法实现处理器调度的程序

用C语言对其进程的数据结构进行定义如下：

struct PCB  //定义进程的数据结构

          {char name[20]; //进程的名称

           char point;  //指针

           int time;  //要求运行时间

           int math;  //优先数

           char state;  //状态

          };

使用的调度算法：

  void diaodu()   //核心算法，进程调度算法

   {int g,h;

     struct PCB Y;

     for(g=0;g<m;g++)

        for(h=g+1;h<m;h++)

           if(P[g].math<P[h].math)  //按优先级判断，如果优先级低，就进行交换

          { Y=P[g];

              P[g]=P[h];

              P[h]=Y;

          }

   }

按时间片轮转法实现处理器调度的程序

#define PCB_NUM 10 /* 该程序包含十个PCB */

#define EXAMPLES 3 /* 该程序最多可模拟三个运行着的进程 */

/* 定义进程控制块 */

typedef struct pcb

{

    struct pcb *next; /* 进程的下一个进程 */

    char name[20]; /* 进程的名字 */

    int time;   /* 进程运行的时间 */

}PCB;

/* 定义全局变量 */

PCB pcbTable[PCB_NUM]; /* 进程控制表 */

PCB *pcbCurrent = NULL; /* 当前运行的进程 */

PCB *pcbFree = NULL; /* 空闲进程 */

PCB *pcbReady = NULL; /* 就绪进程 */

PCB *pcbReadyRear = NULL;

int currentProcesses = 0; /* 当前进程数 */

/* 函数声明 */

void InitPcbTable(); /* 初始化进程表 */

void DisplayIdle();   /* 显示空闲队列 */

int CreateProcesses(); /* 创建进程 */

void DisplayReadys(); /* 显示就绪进程 */

void Run();

PCB* Schedule();

/* 主函数 */

void main()

三、源程序及注释

#include<stdio.h>

 char E;

 int m=5;   //进程的数量

 struct PCB  //定义进程的数据结构

   {char name[20]; //进程的名称

     char point;  //指针

     int time;  //要求运行时间

     int math;  //优先数

     char state;  //状态

   };

struct PCB P[5]={   //定义一个PCB结构的数组，用于存放五个进程

   {"p1",'k1',2,3,'R'},  //分别对五个“进程”赋初值

   {"p2",'k4',3,5,'R'},

   {"p3",'k5',1,3,'R'},

   {"p4",'k3',2,4,'R'},

   {"p5",'k1',4,6,'R'}};

void diaodu()   //核心算法，进程调度算法

   {int g,h;

     struct PCB Y;

     for(g=0;g<m;g++)

        for(h=g+1;h<m;h++)

           if(P[g].math<P[h].math)  //按优先级判断，如果优先级低，就进行交换

          { Y=P[g];

              P[g]=P[h];

              P[h]=Y;

          }

   }

void main()   //主函数

{

   int i,j;

   for(i=0;i<m;i++)   //打印五个进程的初始值

   printf("%d %s %c %d %c \n",P[i].math,P[i].name,P[i].point,P[i].time,P[i].state);

   do{

     diaodu();

     printf("%s\n",P[0].name);

     P[0].time-2;    //每进行一次调度之后，时间和优先级都减2

     P[0].math-2;

     if(P[0].time==0)   //对运行时间进行判0，如果为0，则将其状态设为End

       {

         P[0].state='E';

         P[0].math=0;

       }

for(i=0;i<m;i++)  //调度一次之后，再次打印当前进程状态

printf("%d %s %c %d %c \n",P[i].math,P[i].name,P[i].point,P[i].time,P[i].state);

}while(P[0].state!='E'||P[1].state!='E'||P[2].state!='E'||P[3].state!='E'||P[4].state!='E');

}

#include <stdio.h>

#include <conio.h>

#include <string.h>

/* 定义宏 */

#define PCB_NUM 10 /* 该程序包含十个PCB */

#define EXAMPLES 3 /* 该程序最多可模拟三个运行着的进程 */

/* 定义进程控制块 */

typedef struct pcb

{

    struct pcb *next; /* 进程的下一个进程 */

    char name[20]; /* 进程的名字 */

    int time;   /* 进程运行的时间 */

}PCB;

/* 定义全局变量 */

PCB pcbTable[PCB_NUM]; /* 进程控制表 */

PCB *pcbCurrent = NULL; /* 当前运行的进程 */

PCB *pcbFree = NULL; /* 空闲进程 */

PCB *pcbReady = NULL; /* 就绪进程 */

PCB *pcbReadyRear = NULL;

int currentProcesses = 0; /* 当前进程数 */

/* 函数声明 */

void InitPcbTable(); /* 初始化进程表 */

void DisplayIdle();   /* 显示空闲队列 */

int CreateProcesses(); /* 创建进程 */

void DisplayReadys(); /* 显示就绪进程 */

void Run();

PCB* Schedule();

/* 主函数 */

void main()

{

    InitPcbTable();   /* 初始化进程表 */

    DisplayIdle();   /* 显示空闲进程队列 */

    CreateProcesses(); /* 创建一个进程 */

    DisplayIdle();

    DisplayReadys(); /* 显示就绪进程 */

    while(pcbReady != NULL)

    {

         pcbCurrent = Schedule();

         printf("current process is:%s\n",pcbCurrent->name);

         Run();

         DisplayIdle();

         getch();

DisplayReadys();

         getch();

    }

}

void InitPcbTable()  //初始化进程表函数

{

     int i = 0;

     pcbFree = &pcbTable[0]; /* pcbFree是一个指向进程表表头的指针 */

     pcbTable[PCB_NUM-1].next = NULL; /* 处理进程表中表尾位置的PCB */

     pcbTable[PCB_NUM-1].time = 0;

     strcpy(pcbTable[PCB_NUM-1].name,"idle");

     for(i = 0; i < PCB_NUM-1; i++) /* 处理进程表中除表尾PCB的其余PCB*/

     {

          pcbTable[i].next = &pcbTable[i+1];

          pcbTable[i].time = 0;

          strcpy(pcbTable[i].name,"idle");

     }

}

void DisplayIdle()  //显示空闲进程队列函数

{

     PCB *p = pcbFree; /* p来搜索空闲进程队列 */

     printf("number of idles:%d\n", PCB_NUM - currentProcesses);

     while(p != NULL)

     {

         printf("%s   ", p->name);

         p = p->next;

     }

     printf("\n");

}

int CreateProcesses()   //创建进程函数

{

     PCB *p;

     int i = 0;

     for(i = 0; i < EXAMPLES; i++) /* EXAMPLE为最大可模拟的进程数目 */

     {

          if(pcbFree == NULL) /* 当前没有空闲进程，则返回错误信息 */

               return(-1);

          p = pcbFree;

          pcbFree = pcbFree->next ;

          printf("enter p %d's name:\n", i);

          scanf("%s", p->name);

          printf("enter p %d's time:(1~5)\n", i);

          scanf("%d", &p->time);

          currentProcesses++;

p->next = NULL;

          if(pcbReady == NULL) /* 判断当前状态是否有就绪进程 */

         {

              pcbReadyRear = p;

              pcbReady = pcbReadyRear;

         }

         else

         {

              pcbReadyRear->next = p;

              pcbReadyRear = p;

         }

    }

    return(currentProcesses);

}

void DisplayReadys()  //显示就绪队列函数

{

     PCB *p;

     p = pcbReady;

     printf("name    time\n");

     while(p != NULL)

     {

          printf("%s      %d\n",p->name, p->time);

          p = p->next ;      

     }

}

PCB *Schedule()   //进程调度函数

{

     PCB *p;

     if(pcbReady != NULL)

     {

          p = pcbReady;

          pcbReady = pcbReady->next ;

          return (p);

     }

     else

          return(NULL);

}

void Run()   //运行函数

{

     pcbCurrent->time--;

     if(pcbCurrent->time == 0)

     {

          pcbCurrent->next = pcbFree;

          pcbFree = pcbCurrent;

          currentProcesses--;

}

     else

     {pcbReadyRear->next = pcbCurrent;

      pcbReadyRear = pcbCurrent;

      pcbReadyRear->next = NULL;}  }

四、运行结果：