操作系统实验题：设计一若干并发进程的进程调度程序

一、  实验目的

无论是批处理系统、分时系统还是实时系统，用户进程数一般都大于处理机数，这将导致用户进程互相争夺处理机。这就要求进程调度程序按一定的策略，动态地把处理及分配给处于就绪队列中的某一进程，以使之执行。进程调度是处理机管理的核心内容。本实验要求采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）和先来先服务算法编写和调试一个简单的进程调度程序。通过本实验可以加深理解有关进程控制块、进程队列的概念。并体会了优先数和先来先服务调度算法的具体实施办法。

二、  实验要求

用高级语言编写和调试一个进程调度程序，以加深对进程的概念及进程调度算法的理解．

三、  实验内容

 进程调度算法：采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）和先来先服务算法（将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理）。

每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。

进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。

进程的运行时间以时间片为单位进行计算。

每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。

就绪进程获得 CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。

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

每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。 重复以上过程，直到所要进程都完成为止。

四、  实验算法流程

调度算法的流程图如下 :

　　

五、  实验程序清单

#include "stdio.h"

#include <stdlib.h>

#include <conio.h>

#define getpch(type) (type*)malloc(sizeof(type))

#define NULL 0

struct pcb { /* 定义进程控制块PCB */

char name[10];

char state;

int super;

int ntime;

int rtime;

struct pcb* link;

}*ready=NULL,*p;

typedef struct pcb PCB;

char sort() /* 建立对进程进行优先级排列函数*/

{

PCB *first, *second;

int insert=0;

if((ready==NULL)||((p->super)>(ready->super))) /*优先级最大者,插入队首*/

{

p->link=ready;

ready=p;

}

else /* 进程比较优先级,插入适当的位置中*/

{

first=ready;

second=first->link;

while(second!=NULL)

{

if((p->super)>(second->super)) /*若插入进程比当前进程优先数大,*/

{ /*插入到当前进程前面*/

p->link=second;

first->link=p;

second=NULL;

insert=1;

}

else /* 插入进程优先数最低,则插入到队尾*/

{

first=first->link;

second=second->link;

}

}

if(insert==0) first->link=p;

}

}

char input() /* 建立进程控制块函数*/

{

int i,num;

//clrscr(); /*清屏*/

printf("\n 请输入被调度的进程数目：");

scanf("%d",&num);

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

{

printf("\n 进程号No.%d:\n",i);

p=getpch(PCB);

printf("\n 输入进程名:");

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

printf("\n 输入进程优先数:");

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

printf("\n 输入进程运行时间:");

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

printf("\n");

p->rtime=0;p->state='w';

p->link=NULL;

sort(); /* 调用sort函数*/

}

}

int space()

{

int l=0; PCB* pr=ready;

while(pr!=NULL)

{

l++;

pr=pr->link;

}

return(l);

}

char disp(PCB * pr) /*建立进程显示函数,用于显示当前进程*/

{

printf("\n qname \t state \t super \t ndtime \t runtime \n");

printf("|%s\t",pr->name);

printf("|%c\t",pr->state);

printf("|%d\t",pr->super);

printf("|%d\t",pr->ntime);

printf("|%d\t",pr->rtime);

printf("\n");

}

char check() /* 建立进程查看函数 */

{

PCB* pr;

printf("\n **** 当前正在运行的进程是:%s",p->name); /*显示当前运行进程*/

disp(p);

pr=ready;

printf("\n ****当前就绪队列状态为:\n"); /*显示就绪队列状态*/

while(pr!=NULL)

{

disp(pr);

pr=pr->link;

}

}

char destroy() /*建立进程撤消函数(进程运行结束,撤消进程)*/

{

printf("\n 进程 [%s] 已完成.\n",p->name);

free(p);

}

char running() /* 建立进程就绪函数(进程运行时间到,置就绪状态*/

{

(p->rtime)++;

if(p->rtime==p->ntime)

destroy(); /* 调用destroy函数*/

else

{

(p->super)--;

p->state='w';

sort(); /*调用sort函数*/

}

}

main() /*主函数*/

{

int len,h=0;

char ch;

input();

len=space();

while((len!=0)&&(ready!=NULL))

{

ch=getchar();

h++;

printf("\n The execute number:%d \n",h);

p=ready;

ready=p->link;

p->link=NULL;

p->state='R';

check();

running();

printf("\n 按任一键继续......");

ch=getchar();

}

printf("\n\n 进程已经完成.\n");

ch=getchar();

}

六、  运行结果分析

结果分析：根据上述输入的三个进程的信息可以得到：优先级最高的是进程ping,所以最先调度进程ping,它的状态为运行态，需要执行的时间为5。而当前就绪队列状态为：进程xu的优先级比较高，处于就绪队列前面，而进程gui的优先级是三者中最低的，所以处于就绪队列的最后。而此时这两个进程的状态都为就绪态。

结果分析：当进程ping执行了一个时间片之后而它已占用 CPU时间已达到所需要的运行时间，则将它的优先级减1之后，再将三个进程按优先级的大小排列，从中选择优先级大的进程进入运行状态，则该次进入运行态的是进程xu。

按照这种方式一直运行下去 ，直到：

结果分析：当进程ping的CPU占用时间等于它需要的执行时间时，进程ping调度完成。则这时进程调度中还有两个进程：进程gui和进程xu。

结果分析：当调度进程中只剩下进程gui和进程xu时，这时根据进程优先级的大小，进程gui将进入运行态。

结果分析：当进程xu完成调度时，进程调度程序中直剩下进程gui了，这时进程gui将进入运行态，而当前就绪队列将为空。

结果分析：当进程gui的CPU占用时间等于所需要的执行时间时，进程gui调度完成，则这时进程调度中已经没有需要调度的进程了，则整个进程调度完成。

七、  总结与体会

该实验利用进程调度中的优先级算法调度进程，开始给每一个进程设定一个优先级数，对于优先级高的进程先调度，优先级低的进程后调度，在调度一个进程时，其他进程将处于就绪态，而正在被调度的进程应处于运行态。

一开始在做这个实验的时候，我感觉大脑一片空白，不知道该从哪里动笔。后来根据书上的内容和从网上下载的资料，我慢慢地了解了大致的流程。通过这次实验，首先加深了我对进程调度方法和功能的认识，其次让我更加深刻地理解了操作系统中进程调度中优先级调度的基本原理。优先级调度算法只是进程调度算法的一种，我们还应依照书本去学习进程调度的其它算法，以便更好地了解进程调度

 

第二篇：11级操作系统_进程模拟调度实验报告

《操作系统》实验报告单

说明：仅作参考，请勿雷同

一、实验目的

在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态。当就绪进程个数大于处理器数时，就必须依照某种策略来决定哪些进程优先占用处理器。

本实验模拟在单处理器情况下的处理器调度，加深了解处理器调度的工作

二、实验要求

设计一个按优先数调度算法或时间片轮转法实现处理器调度。

1．给出进程调度的算法描述（基于动态优先级和时间片轮转调度算法的描述）。

2．用C语言设计一个对n个并发进程进行调度的程序，每个进程由一个进程控制块（PCB）结构表示，该进程控制块应包括下述信息：进程标识ID、进程优先数PRIORITY（并规定优先数与优先权成正比）、时间片数CHIP、进程已经占用CPU的时间CPUTIME，进程还需要运行的时间ALLTIME（当进程运行完毕时，其值为0）、进程的状态STATE等（为简化起见。设每个进程处于运行R（run）、就绪W（ready）和完成F（finish）三种状态之一，并假设起始状态都是就绪状态W。），以及进程队列指针NEXT（用来将PCB排成队列）等，可按照调度算法的不同而增删。

3．调度程序应当包含2种不同的调度算法，运行时可以任选一种，以利于各种方法的分析和比较。

4．程序应能显示或打印各种进程状态和参数变化情况，便于观察。即要显示每个时间片内各进程的情况，并且指出运行进程及就绪和阻塞队列中的内容

三、实验内容及主要步骤

1. 按优先数调度算法

(1) 假定系统有五个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的格式为：

其中，进程名——作为进程的标识，假设五个进程的进程名分别为P₁，P₂，P₃，P₄，P₅。

指针——按优先数的大小把五个进程连成队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程中的指针为“0”。

要求运行时间——假设进程需要运行的单位时间数。

优先数——赋予进程的优先数，调度时总是选取优先数大的进程先执行。

状态——可假设有两种状态，“就绪”状态和“结束”状态。五个进程的初始状态都为“就绪”，用“W”表示，当一个进程运行结束后，它的状态为“结束”，用“F”表示。

获得cpu时间 ——模拟cpu分配给进程的时间片

已消耗cpu时间——进程运行已消耗的时间

计数器——计算进程已运行的时间

(2) 在每次运行你所设计的处理器调度程序之前，为每个进程任意确定它的“优先数”和“要求运行时间”。

(3) 为了调度方便，把五个进程按给定的优先数从大到小连成队列。用一单元指出队首进程，用指针指出队列的连接情况。

(4) 处理器调度总是选队首进程运行。采用动态改变优先数的办法，进程每运行一次优先数就减“3”。由于本实验是模拟处理器调度，所以，对被选中的进程并不实际的启动运行，而是执行：

优先数-3

要求运行时间-1

来模拟进程的一次运行。

(5) 进程运行一次后，若要求运行时间¹0，则再将它加入队列（按优先数大小插入，且置队首标志）；若要求运行时间=0，则把它的状态修改成“结束”（F），且退出队列。

(6) 若“就绪”状态的进程队列不为空，则重复上面（4）和（5）的步骤，直到所有进程都成为“结束”状态。

(7) 在所设计的程序中应有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化。

(8) 为五个进程任意确定一组“优先数”和“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。

2. 时间片轮转法

(1) 假定系统有五个进程，每一个进程用一个进程控制块PCB来代表。进程控制块的格式为：

其中，进程名——作为进程的标识，假设五个进程的进程名分别为S₁，S₂，S₃。

指针——按优先数的大小把五个进程连成队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程中的指针为“0”。

要求运行时间——假设进程需要运行的单位时间数。

优先数——赋予进程的优先数，调度时总是选取优先数大的进程先执行。

状态——可假设有两种状态，“就绪”状态和“结束”状态。五个进程的初始状态都为“就绪”，用“W”表示，当一个进程运行结束后，它的状态为“结束”，用“F”表示。

获得cpu时间 ——模拟cpu分配给进程的时间片

已消耗cpu时间——进程运行已消耗的时间

计数器——计算进程已运行的时间

 (2) 每次运行所设计的处理器调度程序前，为每个进程任意确定它的“要求运行时间”。

(3) 把五个进程按顺序排成循环队列，用指针指出队列连接情况。另用一标志单元记录轮到运行的进程。

(4) 处理器调度总是选择标志单元指示的进程运行。由于本实验是模拟处理器调度的功能，所以，对被选中的进程并不实际的启动运行，而是执行：

已运行时间+1

来模拟进程的一次运行，表示进程已经运行过一个单位的时间。

(5) 进程运行一次后，应把该进程的进程控制块中的指针值送到标志单元，以指示下一个轮到运行的进程。同时，应判断该进程的要求运行时间与已运行时间，若该进程的要求运行时间¹已运行时间，则表示它尚未执行结束，应待到下一轮时再运行。若该进程的要求运行时间=已运行时间，则表示它已经执行结束，应指导它的状态修改成“结束”（F）且退出队列。此时，应把该进程的进程控制块中的指针值送到前面一个进程的指针位置。

(6) 若“就绪”状态的进程队列不为空，则重复上面的（4）和（5）的步骤，直到所有的进程都成为“结束”状态。

(7) 在所设计的程序中应有显示或打印语句，能显示或打印每次选中进程的进程名以及运行一次后进程队列的变化。

(8) 为五个进程任意确定一组“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中的进程名以及进程控制块的动态变化过程。

3．数据结构

程序中进程可用PCB表示，其类型描述如下：

typedef struct node

{

 char name[10];/*name of the process*/

      int prio;     /*priority of the process*/

 int round;    /*time given */

 int cputime;  /*time used*/

 int needtime; /*timed needed*/

      int count;    /*counter*/

 char state;   /*state of the process  'R':running,  'W'：waiting,  'F':finish*/

      struct node *next;/*pointer to next process*/    

}PCB;

struct  PCB  *ready=NULL,       //ready队列队首指针

*tail=NULL ,       //ready队列队尾指针

*finish=NULL,    //finish队列队首指针

*run=NULL;     //run队列队首指针

四、程序运行部分结果截图

Ubuntu 6.10 vi编译器编译

 

采用优先级优先算法调度进程结果

采用时间片轮转算法调度结果

五、实验程序清单

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

/*process struct*/

typedef struct node

{

 char name[10];/*name of the process*/

 int prio;     /*priority of the process*/

 int round;    /*time given */

 int cputime;  /*time used*/

 int needtime; /*timed needed*/

 int count;    /*counter*/

 char state;   /*state of the process'R':running,'W'：waiting,'F':finish*/

 struct node *next;/*pointer to next process*/    

}PCB;

PCB *finish,*ready,*tail,*run;/*pointer to three processSqueue，tail point to the end of readySqueue*/

int N;/*the number of process*/

/*

function:put the first process in readySqueue into running

void firstin(void)

*/

void firstin(void)

{

    if(ready!=NULL)

    {

     run=ready;

     ready=ready->next;

     run->state='R';

     run->next=NULL;

    }

    else

    {

     run=NULL;

    } 

}

/*

function:output the type of the processCalling

void prt1(char a)

a=='p': priority ，=='r':time round

*/

void prt1(char a)

{

  if((a=='P')||(a=='p'))

  {

   printf(" name  cputime  needtime  priority  state \n");

  }

  else

  {

   printf(" name  cputime  needtime  count  round  state \n");

  }   

}

/*

function:output information of one process

void prt2(char a,PCB *p)

char a :a=='p':priority =='r':time round

PCB *p : p point to the processSqueue to be outputed

*/

void prt2(char a,PCB *p)

{

  if(a=='P' || a=='p')

  {

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

  }

  else

  {

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

  }

}

/*

function: output information of all the processSqueue

void prt(char algo)

char algo :algo=='p': priority ，=='r':time round

*/

void prt(char algo)

{

  PCB *p;

  prt1(algo); //output the type

  if(run!=NULL) //if the running pointer not equal NULL ,output the process's information

  {

    prt2(algo,run);

  }

  p=ready;

  while(p!=NULL)

  {

   prt2(algo,p);//output the information of the readySqueue

   p=p->next;

  }

  p=finish;

  while(p!=NULL)

  {

    prt2(algo,p);//output the information of the finishSqueue

    p=p->next;

  }

}

/*

function:Priority method insert a process into a suqeue

void insert1(PCB *q)

*/

void insert1(PCB *q)

{

  PCB *p,*s,*r;

  int b;

  s=q;

  p=ready;

  r=p;

  b=1;

  if(s->prio>=ready->prio)

  {

    s->next=ready;

    ready=s;         

  }

  else

  {

    while((p!=NULL)&&b)

    {

      if(p->prio>=s->prio)

      {

        r=p;

        p=p->next;

      }

      else

      {

       b=0;

      }

    }

   s->next=p;

   r->next=s;

  }

}

/*

function: time round insert o process into a squeue

void insert2(PCB *q)

*/

 void insert2(PCB *q)

 {

  tail->next=q;

  tail=q;

  q->next=NULL;

 }

/*

function:priority method initialization

void pcreate_task(char algo)

*/

void pcreate_task(char algo, int n)

{

  PCB *p;

  int i,time;

  char na[10];

  ready=NULL;

  finish=NULL;

  run=NULL;

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

  {

   p=(PCB*)malloc(sizeof(PCB));

   printf("Enter the name of process %d: ",i);

   scanf("%s",&na);

   getchar();

   printf("Enter the time of process %d: ",i);

   scanf("%d",&time);

   getchar();

   strcpy(p->name,na);

   p->cputime=0;

   p->needtime=time;

   p->state='W';

   p->prio=time;

   if(ready==NULL)

   {

    ready=p;

    ready->next=NULL;

   }

   else

   {

     insert1(p);

   }

  }

  printf("Output the waiting processes information\n");

  prt(algo);

  firstin();

}

/*

function:time round initialization

void rcreate_task(char algo)

*/

void rcreate_task(char algo,int n)

{

  PCB *p;

  int i,time;

  char na[10];

  ready=NULL;

  finish=NULL;

  run=NULL;

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

  {

    p=(PCB*)malloc(sizeof(PCB));

    printf("Enter the name of process i: ",i);

    scanf("%s",&na);

    getchar();

    printf("Enter the time of process i: ",i);

    scanf("%d",&time);

    getchar();

    strcpy(p->name,na);

    p->cputime=0;

    p->needtime=time;

    p->count=0;

    p->state='W';

    p->round=2;

    if(ready!=NULL)

    {

      insert2(p);

    }

    else

    {

      p->next=ready;

      ready=p;

      tail=p;

    }

  }

  printf("Output the waiting processes information\n");

  prt(algo);

  run=ready;

  ready=ready->next;

  run->state='R';   

}

/*

function:priority method calling

void priority(char algo)

char algo:type sign :'P':priority 'R': time round

*/

void priority(char algo)

{

  while(run!=NULL)

  {

    run->cputime+=1;

    run->needtime-=1;

    run->prio-=3;

    if(run->needtime==0)

    {

      run->next=finish;

      finish=run;

      run->state='F';

      run=NULL;

      firstin();       

    }

    else

    {

      if((ready!=NULL)&&(run->prio<ready->prio))

      {

       run->state='W';

       insert1(run);

       run=NULL;

       firstin();

      }

    }

   // prt(algo);

  }

  prt(algo);

}

/*

function:time round calling

void roundrun(char algo)

*/

void roundrun(char algo)

{

  while(run!=NULL)

  {

    run->cputime=run->cputime+1;

    run->needtime=run->needtime-1;

    run->count=run->count+1;

    if(run->needtime==0)

    {

      run->next=finish;

      finish=run;

      run->state='F';

      run=NULL;

      if(ready!=NULL)

      {

        firstin();

      }        

    }

    else

    {

      if(run->count==run->round)

      {

       run->count=0;

       if(ready!=NULL)

       {        

         run->state='W';

         insert2(run);

         firstin();

       }

      }

    }

   prt(algo);

  } 

}

/*main */

int main()

{

  char algo;

  printf("Choose the type of attemper P:priority R:timeround : ");

  scanf("%c",&algo);

  getchar();

  printf("Please enter the number of processes N: ");

  scanf("%d",&N);

  getchar();

  if((algo=='P')||(algo=='p'))

  {

    pcreate_task(algo,N);

    priority(algo); 

  } 

  else if((algo=='r')||(algo=='R'))

  {

   rcreate_task(algo,N);

   roundrun(algo); 

  }

  return 1;

}

六、实践经验及问题分析

通过这次试验，自己对linux进程调度，以及一些调度算法有了更深的了解，不过也有些缺陷，进程的信息是由手工输入，未达到随机分配的效果，另外，在做这个实验的时候，也借鉴了别人的一些算法，以及查阅了相关资料，充实了自己。