精品作业分享_OS-优先数调度算法源代码(实验报告)

《计算机操作系统》

一、设计理论描述

进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位。另有一种定义方法是“程序在处理器上的执行”。简单地说,进程包括三种状态:运行状态(Running)、就绪状态(Ready)、等待状态或阻塞状态(Blocked);严格地说,进程除了上面的三个状态,还有挂起就绪(Readya)和挂起等待(Blocked)等状态。进程控制块(PCB)的数据结构来记录进程的属性信息。PCB一般应包含以下信息:进程标识信息(本进程的标志ID、父进程的标志ID、用户标识);处理机状态信息(用户使用的寄存器、控制和状态寄存器、堆栈指针);进程调度和控制信息(进程的状态、进程的调度优先级、程序和数据的地址、进程同步和通信机制、进程已等待时间、已使用的处理器时间、进程在有关队列中的链接指针、分给进程的主存大小和位置、进程使用的其他资源信息、进程得到有关服务的优先级、进程调度所需的其他信息)

进程调度算法:(1)先进先出调度算法(FIFO):按照进程的到达顺序调度进程,属于不可抢占策略。(2)优先级调度算法:按照进程的优先级大小来调度,是高优先级进程得到优先的处理的调度策略,可使用非抢占或可抢占两种策略。

二、设计思想、设计分析及数据结构模型

这个设计需要考虑三个问题:如何组织进程、如何创建进程和如何实现处理机调度。

考虑如何组织进程,首先就要设置进程控制块的内容。进程控制块PCB记录各个进程执行时的情况。一般操作系统中,无论进程控制块中信息量多少,信息都可以大致分为以下四类:

1)标识信息

每个进程都要有一个唯一的标识符,用来标识进程的存在和区别于其他进程。这个标识符是必不可少的,可以用符号或编号实现,它必须是操作系统分配的。在后面给出的参考程序中,采用编号方式,也就是为每个进程依次分配一个不相同的正整数。

2)说明信息

用于记录进程的基本情况,例如,进程的状态、等待原因、进程程序存放位置、进程数据存放位置等。设计中,因为进程没有数据和程序,仅使用进程控制块模拟进程,所以这部分内容仅包括进程状态。

3)现场信息

现场信息记录各个寄存器的内容。当进程由于某种原因让出处理机时,需要将现场信息记录在进程控制块中,当进行进程调度时,从选中进程的进程控制块中读取现场信息进行现场恢复。现场信息就是处理机的相关寄存器内容,包括通用寄存器、程序计数器和程序状态字寄存器等。在设计中,可选取几个寄存器作为代表。用大写的全局变了量AXBXCXDX模拟通用寄存器,大写的全局变量PC模拟程序计数器,大写的全局变量PSW模拟程序状态字寄存器。

4)管理信息

管理信息记录进程管理和调度的信息。例如进程优先数和进程队列指针等。设计中,仅包括队列指针。

因此可将进程控制块结构定义如下:

typedef struct node

{

   char name[10];  /*进程标识符*/

   int prio;   /*进程优先数*/

   int cputime; /*进程占用CPU时间*/

   int needtime; /*进程到完成还要的时间*/

   char state; /*进程的状态*/

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

}PCB;

PCB *finish,*ready,*run; /*队列指针*/

int N; /*进程数*/

确定进程控制块内容后,要考虑的就是如何将进程控制块组织在一起。多道程序设计系统,往往同时创建多个进程。在单处理机的情况下,每次只能有一个进程处于运行态,其他的进程处于就绪状态或等待状态。为了便于管理,通常把处于相同状态的进程的进程控制块链接在一起。单处理机系统中,正在运行的进程只有一个,因此,单处理机系统中进程控制块分成一个正在运行进程的进程控制块、就绪进程的进程控制块组织成的就绪队列和等待进程的进程控制块组成的等待队列。由于设计模拟的是进程调度,没有对等待队列的操作,所以设计中只有一个指向正在运行进程的进程控制块指针和一个就绪进程的进程控制块队列指针。操作系统的实现中,系统往往在内存中划分出一个连续的专门区域存放系统的进程控制块,设计中应该用数组模拟这个专门的进程控制块区域,定义如下:

#define n  l0     //假定系统允许进程个数为10

struct pcb  pcbarea[n]    //模拟进程控制块区域的数组

这样,进程控制块的链表实际上是数据结构中使用的静态链表。进程控制块的链接方式可以采用单向和双向链表,设计中,进程控制块队列采用单向不循环静态链表。为了管理空闲进程控制块,还应该将空闲控制块链接成一个队列。

设计中指向运行进程的进程控制块指针、就绪队列指针和空闲进程控制块队列指针定义如下:

int run    //定义指向正在运行进程的进程控制块的指针

{int head;

Int tail;

}ready;      //定义指向就绪队列的头指针head和尾指针tail

Int pfree;   //定义指向空闲进程控制块队列的指针

以上是如何组织进程,下面考虑如何创建进程。

进程创建是一个原语,因此在设计中应该用一个函数实现,进程创建的过程应该包括:

(1)申请进程控制块。进程控制块的数量是有限的,如果没有空闲进程控制块,则进程不能创建,如果申请成功才可以执行第二步。

(2)申请资源。除了进程控制块外,还需要有必要的资源才能创建进程,如果申请资源不成功,则不能创建进程,并且归还已申请的进程控制块;如果申请成功,则执行第三步,设计无法申请资源,所以模拟程序忽略了申请资源这一步。

(3)填写进程控制块。将该进程信息写入进程控制块内,设计中只有进程标识符、进程状态可以填写,每个进程现场信息中的寄存器内容由于没有具体数据而使用进程(模拟进程创建时,需输入进程标识符字,进程标识符本应系统建立,并且是唯一的,输入时注意不要冲突),刚刚创建的进程应该为就绪态,然后转去执行第四步。

(4)挂入就绪队列。如果原来就绪队列不为空,则将该进程控制块挂入就绪队列尾部,并修改就绪队列尾部指针:如果原来就绪队列为空,则将就绪队列的头指针、尾指针均指向该进程控制块,进程创建完成。

多道程序设计的系统中,处于就绪态的进程往往是多个,它们都要占用处理机,但是,单处理机系统的处理机只有一个,进程调度就是解决这个处理机竞争问题的。进程调度的任务就是按照某种算法从就绪进程队列中选择一个进程,让它占有处理机。因此进程调度程序就应该包括两部分,一部分是在进程就绪队列中选择一个进程,并将其进程控制块从进程就绪队列中摘下来,另一部分工作就是分配处理机给选中的进程,也就是将指向正在运行进程的进程控制块指针指向该进程的进程控制块,并将该进程的进程控制块信息写入处理机的各个寄存器中。

在每次运行调度程序之前,为每个进程任意确定它的“优先数”和“需要运行的时间数”,五个进程按给定的优先数从大到小连成队列,调度总是选队首进程运行。

    每个进程可有三种状态:R——运行状态(RUN);W——就绪状态(READY)和F——完成状态(FINISH)。并假定初始状态为就绪状态。

PCB结构包括以下信息:进程名、进程优先数(或轮转时间片),进程所占用的CPU时间,进程的状态,当前队列指针等。根据调度算法的不同,PCB结构的内容可以作适当的增删。

PCB结构:

   NAME——进程标识符;

   PRIO——进程优先数;

   CPUTIME——进程占用CPU时间;

   NEEDTIME——进程到完成还需要的CPU时间;

   STATE——进程的状态

   NEXT——链指针。

本实验是模拟进程调度程序,被选中的进程并不实际启动运行,进程每执行一次,优先数减3,CPU时间片数加1,进程还需要的时间片数减1。在轮转法中,采用固定时间片,时间片数为2,进程每执行一次,CPU时间片数加2,进程还需要的时间片数减2,并排到就绪队列的尾上。

被选中运行的进程,进程状态置为“R”,进程运行一次后,若需要运行时间≠0,进程从运行状态变为就绪状态,状态置为“W”,并按优先数大小插入到队列中,若需要运行时间=0,则把它的状态置为完成状态(F)。

若“就绪”状态的进程队列不为空,则重复上面的(4)、(5)执行步骤,直到所有进程运行完毕(都为“完成”状态)。

设计的程序中能显示或打印进程控制块的动态变化过程。

三、程序流程图(省略)

四、源代码

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<conio.h>

typedef struct node

{

   char name[10];  /*进程标识符*/

   int prio;   /*进程优先数*/

   int cputime; /*进程占用CPU时间*/

   int needtime; /*进程到完成还要的时间*/

   char state; /*进程的状态*/

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

}PCB;

PCB *finish,*ready,*run; /*队列指针*/

int N; /*进程数*/

/*将就绪队列中的第一个进程投入运行*/

void firstin()

{

   run=ready;   /*就绪队列头指针赋值给运行头指针*/

   run->state='R';   /*进程状态变为运行态*/

   ready=ready->next;  /*就绪对列头指针后移到下一进程*/

}

void prt1()    /*标题输出函数*/

{

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

}

void prt2(PCB *q)  /*进程PCB输出*/

{

   printf("  %-10s%-10d%-10d%-10d %c\n",q->name,

       q->cputime,q->needtime,q->prio,q->state);

}

void prt()    /*输出函数*/

{

   PCB *p;

   prt1();  /*输出标题*/

   if(run!=NULL) /*如果运行指针不空*/

      prt2(run); /*输出当前正在运行的PCB*/

   p=ready;  /*输出就绪队列PCB*/

   while(p!=NULL)

   {

      prt2(p);

      p=p->next;

   }

   p=finish;  /*输出完成队列的PCB*/

   while(p!=NULL)

   {

      prt2(p);

      p=p->next;

   }

   getch();  /*按任意键继续*/

}

void insert(PCB *q)   /*优先数的插入算法*/

{

   PCB *p1,*s,*r;

   int b;

   s=q;  /*待插入的PCB指针*/

   p1=ready; /*就绪队列头指针*/

   r=p1; /*rp1的前驱指针*/

   b=1;

   while((p1!=NULL)&&b)  /*根据优先数确定插入位置*/

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

      {

         r=p1;

         p1=p1->next;

      }

      else

         b=0;

   if(r!=p1)  /*如果条件成立说明插入在rp1之间*/

   {

      r->next=s;

      s->next=p1;

   }

   else

   {

      s->next=p1;  /*否则插入在就绪队列的头*/

      ready=s;

   }

}

void create()    /*优先数创建初始PCB信息*/

{

   PCB *p;

   int i,time;

   char na[10];

   ready=NULL; /*就绪队列头指针*/

   finish=NULL;  /*完成队列头指针*/

   run=NULL; /*运行队列指针*/

   printf("Enter name and time of process\n"); /*输入进程标识和所需时间创建PCB*/

   for(i=1;i<=N;i++)

   {

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

      scanf("%s",na);

      scanf("%d",&time);

      strcpy(p->name,na);

      p->cputime=0;

      p->needtime=time;

      p->state='w';

      p->prio=50-time;

      if(ready!=NULL) /*就绪队列不空调用插入函数插入*/

         insert(p);

      else

      {

         p->next=ready; /*创建就绪队列的第一个PCB*/

         ready=p;

      }

   }

   system("cls");

   printf("          output of priority:\n");

   printf("************************************************\n");

   prt();  /*输出进程PCB信息*/

   run=ready; /*将就绪队列的第一个进程投入运行*/

   ready=ready->next;

   run->state='R';

}

void priority()   /*优先数调度算法*/

{

   while(run!=NULL)  /*当运行队列不空时,有进程正在运行*/

   {

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

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

      run->prio=run->prio-3; /*每运行一次优先数降低3个单位*/

      if(run->needtime==0)  /*如所需时间为0将其插入完成队列*/

      {

         run->next=finish;

         finish=run;

         run->state='F';  /*置状态为完成态*/

         run=NULL;  /*运行队列头指针为空*/

         if(ready!=NULL) /*如就绪队列不空*/

            firstin(); /*将就绪对列的第一个进程投入运行*/

      }

      else /*没有运行完同时优先数不是最大,则将其变为就绪态插入到就绪队列*/

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

         {

            run->state='W';

            insert(run);

            firstin(); /*将就绪队列的第一个进程投入运行*/

         }

      prt(); /*输出进程PCB信息*/

   }

}

/*主函数*/

void main()

{

   system("cls");/*清屏*/

   printf("*****************priority********************\n");

   printf("Enter process number:");

   scanf("%d",&N); /*输入进程数*/

   create(); /*优先数法*/

   priority();

}

五、程序运行结果及分析

 

第二篇:优先数和轮转法进程调度实验报告

实验二 进程调度报告

一、 基本信息

1、

2、

3、 实验题目:进程调度 完成人:**** 报告日期:###########

二、 实验内容简要描述

1、实验目标:进程调度是处理机管理的核心内容。本实验要求用C语言编写和调试一个简单的进程调度程序。通过本实验可以加深理解有关进程控制块、进程队列的概念,并体会和了解优先数和时间片轮转调度算法的具体实施办法。

2、 实验要求:

(1)设计进程进程控制块PCB表结构,分别适用于优先数调度算法和循环轮转调度算法。PCB结构通常包括以下信息:进程名,进程优先数(或轮转时间片),进程所占用的CPU时间,进程的状态,当前队列指针等。根据调度算法的不同,PCB结构的内容可以作适当的增删。

(2)建立进程就绪队列。对两种不同算法编制入链子程序。

(3)编制两种进程调度算法:1)优先数调度;2)循环轮转调度。

三、 报告主要内容

1、 设计思路:

(1)设计就绪、执行、完成三个队列;根据输入进程的时间,按

照需要的时间越多,优先级越低,(60减去所需时间)建立就绪队列。

(2)对优先数调度算法实现,首先从就绪队列中取出第一个进程。进程执行,优先数减3,CPU时间片数加1,进程还需要时间片数减1,在此设置计数器count,来判断进程是否执行完成。若进程完成,标志flag为0,并插入完成队列;否则插入就绪队列,等待下一次继续执行。重复上述操作,直到进程全部完成。

(3)对轮转法调度算法实现,从就绪队列取进程,在时间片数为2的时间内进程执行,计数器count加2,若进程完成,继续取下一个进程执行,否则,若时间片用完,计数器清零,将该进程排列到就绪队列的尾上。然后取下一个进程,由于计数器已经清零,故相当于又给了一个时间片。重复上述操作,直到进程全部完成。

2、 主要数据结构:

(1)PCB结构:

typedef struct node

{

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

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

int round; /*分配CPU的时间片*/

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

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

char state; /*进程的状态,W--就绪态,R--执行态,F--

完成态*/

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

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

}PCB;

(2)三个应用队列:

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

3、 主要代码结构:

(1)函数声明部分:

void GetFirst(); /*从就绪队列取得第一个节点*/ void Output(); /*输出队列信息*/

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

void InsertTime(PCB *in); /*时间片队列*/

void InsertFinish(PCB *in); /*时间片队列*/

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

void TimeCreate(); /*时间片输入函数*/

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

void RoundRun(); /*时间片轮转调度*/

(2)主函数:

int main()

{

char choise;

printf("请输入要创建的进程数目:\n"); scanf("%d",&num);

getchar();

printf("输入进程的调度方法:

scanf("%c",&choise);

switch(choise)

{

case 'P':

PrioCreate();

Priority();

break;

case 'R':

TimeCreate();

RoundRun();

break;

default:break;

}

Output();

}

(P/R)\n");

4、 主要代码段分析:

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

{

int flag = 1; //设定标志位,当flag==0时,该进程结束

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(); /*继续取就绪队列队头进程进入执行队列*/ }

}

void RoundRun() /*时间片轮转调度算法*/

{

int flag = 1;

GetFirst();

while(run != NULL)

{

Output();

while(flag)

{

run->count++;

run->cputime++;

run->needtime--;

if(run->needtime == 0) /*进程执行完毕*/

{

run ->state = 'F';

InsertFinish(run);

flag = 0;

}

else if(run->count == run->round)/*时间片用完*/ {

run->state = 'W';

run->count = 0; /*计数器清零,为下次做准备*/ InsertTime(run);

flag = 0;

}

}

flag = 1;

GetFirst();

}

}

四、 实验结果

1、 基本数据

(1) 源程序代码行数

源码共:273行

(2) 完成该实验投入的时间(小时数)

(3) 与其他同学讨论次数

2、 测试数据设计

优先数调度算法测试数据:

A1 2

A2 3

A3 4

A4 2

A5 4

时间片轮转调度算法测试数据: A1 3

A2 2

A3 4

A4 2

A5 1

3.测试结果分析

优先数和轮转法进程调度实验报告

优先数和轮转法进程调度实验报告

优先数和轮转法进程调度实验报告

优先数和轮转法进程调度实验报告

优先数和轮转法进程调度实验报告

五、 实验体会

1、 实验过程中遇到的问题及解决过程

(1)本次试验,思路设计不难,主要还是在利用指针处理时感觉很困难,实验中设计了结构指针用来指向PCB结构,PCB结构中又有链表指针。为此必须时时防止出现野指针,程序崩溃。

(2)在时间片轮转法调度中,老师要求:进程每执行1次,CPU时间片数加2,进程还需要的时间数减2.一开始我认为这不妥,计数器统计,每次增加1。比如测试数据中第5个A5 1 。这个进程所需时间片只有1,所以如果都是减2,我设计后程序结果显示混乱。然后我把 进程执行完成的条件:if(run->needtime <= 0) /*进程执行完毕*/更改后,程序显示正常。

(3)在建立优先数就绪队列时主要运用,链表插入模型。但是由于本题是从建立、到完成一个就绪对列,所以必须分多种情况讨论。 2、

3、 实验过程中产生的错误及原因分析 实验体会和收获

(1)本次试验后对优先数调度算法和时间片轮转调度算法实现的过程,有了很清楚的认识、理解。设计计数器来对进程执行状态的时间分析,使得进程调度这一抽象模型得到具体化。之后,便是对进程的插入(执行完,插入到完成队列,否则插入到就绪)和再次调度(当改进程再次满足条件时,从就绪队列调度到执行队列)重复过程。

(2)通过设计PCB结构,模拟进程调度,加深了对进程的理解。

(3)提高了C语言编程动手能力,在设计就绪队列时,通过优先数将新进程插入就绪队列中的适当位置。要做多重判断,但实际又是“链表插入”模型的运用,这感觉很爽,无论多复杂的问题,都可以分化成简单的问题在已有的模型上处理。

附件1:参考文献

附件2:源程序(提交电子版本即可)

相关推荐