实验一 进程调度——starof

一.实验题目: 

1、编写并调试一个模拟的进程调度程序，采用“最高优先数优先”调度算法对五个进程进行调度。

2、编写并调试一个模拟的进程调度程序，采用“轮转法”调度算法对五个进程进行调度。

二:实验目的

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

三.实验内容:      

  最高优先级优先调度算法

 1)优先级简介

动态优先数是指在进程创建时先确定一个初始优先数， 以后在进程运行中随着进程特性的改变不断修改优先数，这样，由于开始优先数很低而得不到CPU的进程，就能因为等待时间的增长而优先数变为最高而得到CPU运行。

例如：在进程获得一次CPU后就将其优先数减少1。或者，进程等待的时间超过某一时限时增加其优先数的值，等等。

   2)详细设计

优先权调度算法：

1、设定系统中有五个进程，每一个进程用一个进程控制块（ PCB）表示，进程队列采

用链表数据结构。

2、进程控制块包含如下信息：进程名、优先数、需要运行时间、已用CPU时间、进程状态等等。

3、 在每次运行设计的处理调度程序之前，由终端输入五个进程的“优先数”和“要求运行时间”。

4、进程的优先数及需要的运行时间人为地指定.进程的运行时间以时间片为单位进行计算。

5、采用优先权调度算法，将五个进程按给定的优先数从大到小连成就绪队列。用头指针指出队列首进程，队列采用链表结构。

6、处理机调度总是选队列首进程运行。采用动态优先数办法，进程每运行一次优先数减“1”，同时将已运行时间加“1”。

7、进程运行一次后，若要求运行时间不等于已运行时间，则再将它加入就绪队列；否则将其状态置为“结束”,且退出就绪队列。

8、“就绪”状态的进程队列不为空，则重复上面6，7步骤，直到所有进程都成为“结束”状态。

9、在设计的程序中有输入语句，输入5个进程的“优先数”和“要求运行时间”，也有显示或打印语句，能显示或打印每次被选中进程的进程名、运行一次后队列的变化，以及结束进程的进程名。

10、最后，为五个进程任意确定一组“优先数”和“要求运行时间”，运行并调试所设计的程序，显示或打印出逐次被选中进程的进程名及其进程控制块的动态变化过程。

 3)流程图:                                                                    

               图一.最高优先级优先调度算法流程图

4)源程序:

#include "stdio.h"

#include

#include

#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;

void 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;

    }

}

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

{

    int i;

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

    printf("\\n 请输入五个进程信息:\\n");

for(i=0; i<5; 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);

}

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

{

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

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

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

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

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

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

    printf("\\n");

}

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

{

    PCB* pr;

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

    disp(p);

    pr=ready;

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

    while(pr!=NULL)

    {

        disp(pr);

pr=pr->link;

    }

}

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

{

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

    free(p);

}

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

{

(p->rtime)++;

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

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

    else

    {

(p->super)--;

p->state='w';

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

    }

}

void youxian()      // 高优先级优先算法的程序入口

{

    int len,h=0;

    char ch;

    system("cls");

    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 按任一键继续......");

    }

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

    ch=getchar();

}

void sort2()

{

    PCB *q;

    q=ready;

    if(ready==NULL) ready=p;

    else

    {

while(q->link!=NULL)

        {

q=q->link;

        }

q->link=p;

    }

}

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

{

(p->rtime)++;

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

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

    else

    {

p->state='w';

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

    }

}

void lunzhuan()       //轮转法演示进程的程序入口

{

    int len,h=0;

    char ch;

    system("cls");

    input2();

    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();

        running2();

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

    }

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

    ch=getchar();

}

void menu()    //菜单

{

    int m;

    system("cls");

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

    printf("\\\\进程调度演示\\n");

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

    printf("\\n\\n\\n\\\1.演示最高优先数优先算法.");

    printf("\\n\\\2.演示轮转法算法.");

    printf("\\n\\\0.退出程序.");

    printf("\\n\\n\\\\选择进程调度方法:");

    scanf("%d",&m);

    switch(m)

    {

    case 1:

        youxian();         //高优先级优先算法的程序入口

        system("cls");

        menu();

        break;

//case 2:

        // lunzhuan();          //轮转法演示进程的程序入口

        //system("cls");

        // menu();

        // break;

    case 0:

        system("cls");

        break;

    default:

        system("cls");

        menu();

    }

}

int main() /*主函数*/

{

    menu();

    return 0;

}

五)调试结果（用C语言编写，在ColdBlocks 下编译运行的）

  1.一运行程序,则显示一如下界面:

2. 选择1.进入最高优先数优先算法的演示,此时输入5个进程的名,优先级以及运行时间

4.此后,每按一次回车键,相当于队列首进程运行了一个cpu的时间,运行完毕后,如果要求运行时间不等于已运行时间，则再将它加入就绪队列；否则将其状态置为“结束”,且退出就绪队列。第一次运行程序时的正在运行的进程以及等待队列中的进程的各信息如下:

5.继续按回车键,则显示第二次时的运行情况:

6. 一直按回车键,直到进程运行完毕.

                 <二>简单轮转法调度算法

1)简单轮转法的基本思想：

所有就绪进程按 FCFS排成一个队列，总是把处理机分配给队首的进程，各进程占用CPU的时间片相同。即将CPU的处理时间划分成一个个相同的时间片，就绪队列的诸进程轮流运行一个时间片。当一个时间片结束时，如果运行进程用完它的时间片后还未完成，就强迫运行机制进程让出CPU，就把它送回到就绪队列的末尾，等待下一次调度。同时，进程调度又去选择就绪队列中的队首进程，分配给它一时间片，以投入运行。直至所有的进程运行完毕。

  2)详细设计:

1、设系统有5个进程，每个进程用一个进程控制块PCB来代表。

2、为每个进程任意确定一个要求运行时间。

3、按照进程输入的先后顺序排成一个队列。再设一个队首指针指向第一个到达进程的首址。

4、执行处理机调度时，开始选择队首的第一个进程运行。另外，再设一个当前运行进程的指针，指向当前正在运行的进程。

5.考虑到代码的可重用性, 轮转法调度程序和最高优先级优先调度是调用同一个模快进行输出

注:由于轮转法调度程序和最高优先级优先调度是调用同一个模快进行输出,所以在时间轮转法调度算法的进程中,依然显示了随即产生的优先级数.

6.进程运行一次后，以后的调度则将当前指针依此下移一个位置，指向下一个进程，即调整当前运行指针指向该进程的链接指针所指进程，以指示应运行进程。同时还应判断该进程的要求运行时间是否等于已运行时间。若不等，则等待下一轮的运行，否则将该进程的状态置为完成态C，并退出循环队列。

7.若就绪队列不空，则重复上述的（5）和（6）步骤直到所有的进程都运行完为止。

8.在所设计的调度程序中,包含显示或打印语句。显示或打印每次选中的进程的名称及运行一次后队列的变化情况。

3)流程图

                   图二. 简单轮转法调度算法流程图

4)主要程序

  轮转法调度算法与最高优先数优先算法代码大多数都是共享的.很大不同的只有他们每次运行一个cpu时间后,运行后的进程怎样插入到队列中的的sort()算法,还有就是运行算法running();下面我只列出几个算法的代码

void sort2()

{

    PCB *q;

    q=ready;

    if(ready==NULL) ready=p;

    else

    {

while(q->link!=NULL)

        {

q=q->link;

        }

q->link=p;

    }

}

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

{

(p->rtime)++;

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

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

    else

    {

p->state='w';

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

    }

}

void lunzhuan()       //轮转法演示进程的程序入口

{

    int len,h=0;

    char ch;

    system("cls");

    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();

        running2();

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

    }

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

    ch=getchar();

}

void menu()    //菜单

{

    int m;

    system("cls");

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

    printf("\\\\进程调度演示\\n");

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

    printf("\\n\\n\\n\\\1.演示最高优先数优先算法.");

    printf("\\n\\\2.演示轮转法算法.");

    printf("\\n\\\0.退出程序.");

    printf("\\n\\n\\\\选择进程调度方法:");

    scanf("%d",&m);

    switch(m)

    {

    case 1:

        youxian();         //高优先级优先算法的程序入口

        system("cls");

        menu();

        break;

    case 2:

        lunzhuan();          //轮转法演示进程的程序入口

        system("cls");

        menu();

        break;

    case 0:

        system("cls");

        break;

    default:

        system("cls");

        menu();

    }

}

5)调试结果:

 1.输入五个进程的初始状态如下:

2.此后,每按一次回车键,相当于队列首进程运行了一个cpu的时间,运行完毕后,如果要求运行时间不等于已运行时间，则再将它加入就绪队列；否则将其状态置为“结束”,且退出就绪队列。第一次运行程序时的正在运行的进程以及等待队列中的进程的各信息如下:

 3.继续按回车键,则显示第二次时的运行情况:

4.一直按回车键,直到进程运行完毕.

四.总结及心得体会