非抢占式动态优先算法进程调度实验.doc

实验： 进程调度算法

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

二、 实验要求：
用C++语言实验对N个进程采用非抢占式的动态优先权优先算法的进程调度

三、 实验内容：
（1） 设计一个有N个进程并发的进程调度程序。进程调度算法：采用非抢占式最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）算法。

（2） 每个进程有一个进程控制块（PCB）表示。PCB用结构来描述，包括以下字段：
l 进程标识ID、
l 优先数、
l 到达时间、
l 需要运行时间、
l 已用CPU时间
l 进程阻塞时间startblock（表示进程在运行startblock个时间片后，进程将进入阻塞状态），
l 进程被阻塞的时间blocktime（表示进程等待blocktime个时间片后，将转换成就绪状态），
l 进程状态state，就绪W（Wait）、运行R（Run）、或完成F（Finish）三种状态
l 队列指针next等等。

进程的PCB中的数据需要程序员初始化给定。
（3） 优先数改变的规则
进程在就绪对列中呆一个时间片，优先数增加1；
进程每运行一个时间片，优先数减1；
（4） 运行过程描述
首先按照初始化输入，按照各进程优先级高低排列就绪队列中进程的顺序，优先级最高的进程最先获得CPU控制权运行。如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，此时应将进程的优先数减1（即降低一级），如果到了进程阻塞的时间，阻塞进程，然后把它插入阻塞队列，等待经过blocktime后，再唤醒进程，把它按照优先级高低，插入就绪队列相应位置等待CPU。
每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的PCB，以便进行检查。
重复以上过程，直到所要进程都完成为止。

五、流程图

进程完成，撤消该进程
就绪队列首进程投入运行
时间片到，运行进程已占用CPU时间+1
运行进程已占用CPU时间已达到所需的运行时间
把运行进程插入到下一个队列的队尾
插入新的进程
开始
初始化PCB,输入进程信息
所有队列都为空
各进程按FCFS原则排队等待调度

退出程序

是

是

六、结果过程及截图
初始化队列

输入所有进程后的进程信息如下：

按Y键继续运行进程：

按Y键继续运行进程：

运行若干次后的状态：

添加新的进程：

七、所遇困难的解决以及心得体会
在这个多级反馈的实验中，我采取了用一条实际上的链表队列来模拟多个逻辑上的队列，通过维护几个链表的状态信息来找到每个进程运行完后应该插入的地方，还有一个标志位Fend用来表明新插入的队列的位置。虽然实验原理很简单，但是在编写代码的过程中遇到了不少的问题，在两个小时之内已经完成的大体代码的编写，但是之中存在不少的问题，导致了用了差不多四个小时的时间去调试才把它弄好，这主要归咎于在开始设计代码的不太合理，在后期使得代码结构有些混乱，使得调试更加的麻烦，以及对编程的不熟悉。通过这个实验不仅使我对进程的调度算法有了更深的认识，使得理论知识得到的实践，也使我的编程能力得到了进一步提高。
八、源代码

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

#define getpch(type) (type*)malloc(sizeof(type))
#define NULL 0
#define TIME 2//时间片长度

typedef struct pcb{//进程管理块
char name[10];//进程名字
char state; //进程状态
int queue; //进程所在的队列
int ntime; //进程需要运行的时间
int rtime; //进程已经运行的时间
int etime; //进程在本队列可运行的时间片
struct pcb *link;
}PCB;

PCB *ready = NULL, *pinsert = NULL, *pfend = NULL,*p =NULL; //就绪队列，进程插入位置的变量

int geti() //使用户仅能输入整数
{
char ch;
int i = 0;
fflush(stdin);
ch = getchar();
while(ch == '\n'){
printf("\tf输入不能为空..请重新输入\n");
fflush(stdin);
ch = getchar();
}
while(ch != '\n'){
if(ch > '9' || ch < '0'){
printf("\t输入有误!!输入只能为正整数，请重新输入...\n");
fflush(stdin);
i = 0;
ch = getchar();
}else{
i = i*10 + (ch - '0');
ch = getchar();
}
}
return i;
}

void findpos()//更新状态量
{
PCB *ps = pfend;
if(!ps || !ps -> link || (ps-> link->queue - ps->queue) > 1)
pinsert = ps;
else{
while (ps->link && ps ->link->queue != (pfend ->queue +2))
ps = ps->link;
pinsert = ps;

}
}

void insert()//插入进程
{
if(!ready ){

ready = p;
pfend = p;
pinsert = p;
}else if(ready ->queue == 1){//第一队列存在
p->link = pfend->link;
pfend->link = p;
pfend = p;
findpos();

}
else{
p->link = ready;
ready = p;
findpos();
}

}

void input()/*建立进程控制块函数*/
{
int i,num;

printf("\n请输入进程的个数?");
num = geti();
for(i=0; i < num; i++)
{
printf("\n进程号No.%d:\n",i+1);
p=getpch(PCB);
printf("\n输入进程名:");
scanf("%s",p->name);
printf("\n输入进程运行时间:");
p ->ntime = geti();
printf("\n");
p->rtime=0;
p->state='w';
p->queue =1;
p->etime = TIME;
p->link=NULL;
insert();/*调用insert函数*/
}
}

void disp(PCB *pr)/*建立进程现实函数，用于显示当前进程*/
{
printf("\nname\t state\t queue\t ntime\t rtime\t在队列可停留时间\t \n");
printf("|%s\t",pr->name);
printf(" |%c\t",pr->state);
printf(" |%d\t",pr->queue);
printf(" |%d\t",pr->ntime);
printf(" |%d\t",pr->rtime);
printf(" |%d\t",pr->etime);
printf("\n");
}

void check()/*建立进程查看函数*/
{
PCB *pr;
printf("\n ****当前正在运行的进程是:%s",ready->name);/*显示当前运行的进程*/
disp(ready);
pr= ready ->link;
printf("\n****当前就绪队列状态为:\n");/*显示就绪队列状态*/
while(pr!=NULL)
{
disp(pr);
pr=pr->link;
}
}

void sort()//调整进程队列

{
if(!ready->link ||ready->queue < ready->link->queue) return;

p = ready ->link;
ready ->link = pinsert ->link;
pinsert ->link = ready;
pinsert = ready;
ready = p;
if (ready && ready -> queue == pinsert ->queue){
findpos();
}

}

void addnew()//添加新的进程
{
if(ready ->queue != 1){
(ready -> queue)++;
ready->etime *= 2;
ready -> state='w';
sort();/*调用sort函数*/
input();
}
else{
input();

}

}
void destroy()/*建立进程撤销函数(进程运行结束，撤销进程)*/
{
printf("\n进程[%s]已完成.\n",ready->name);
p = ready;
ready = ready->link;
free(p);
if (ready && ready -> queue == pinsert ->queue)
findpos();
}

void running()/*建立进程就绪函数(进程运行时间到，置就绪状态)*/
{
(ready -> rtime)++;
ready ->etime --;
if(ready->rtime == ready->ntime){
destroy();
return;
}else if(ready ->etime == 0){
int time = 2;
(ready -> queue)++;
for(int i = 2; i != ready->queue; ++i)
time *= 2;
ready->etime = time;
ready -> state='w';
sort();/*调用sort函数*/
}
}

void main()
{
char ch;
input();
while(ready != NULL)
{
printf("\nThe execute name:%s\n",ready ->name);
ready ->state = 'R';
check();
running();
printf("\n按i键添加新进程....按其他任意键继续运行...");
fflush(stdin);
ch = getchar();
if (ch == 'i'|| ch=='I')
addnew();

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

}