昆明理工大学进程管理实验报告
昆明理工大学信息工程与自动化学院学生实验报告
( 2010 —2011 学年 第 二 学期 )
课程名称:操作系统 开课实验室: 年 月 日
目录
一、
二、
1.
2.
3.
4.
5.
6.
7.
8.
四、
五、
六、 实验目的 ................................................................................................................................................. 1 实验原理及基本技术路线图 ................................................................................................................. 1 进程的状态转换图 ................................................................................................................................. 2 各原语的功能说明 ................................................................................................................................. 2 多级反馈队列调度算法的描述 ......................................................................................................... 3 程序功能结构图 ..................................................................................................................................... 4 流程图..................................................................................................................................................... 4 数据结构定义 ......................................................................................................................................... 5 主要变量的说明 ..................................................................................................................................... 6 函数的说明 ............................................................................................................................................. 6 实验方法、步骤 ..................................................................................................................................... 6 实验过程原始记录 ............................................................................................................................... 18 实验结果、分析和结论 ....................................................................................................................... 21
一、 实验目的
通过编写进程管理的算法,要求学生掌握整个进程管理的各个环节,进程的数据结构描述,进程的各种状态之间的转换,以及进程的调度算法。以加深对进程的概念及进程调度算法的理解,并且提高链表的应用能力,达到提高编程能力的目的。
二、 实验原理及基本技术路线图(方框原理图)
用C语言或C++语言开发。需要定义PCB的数据结构,用链表的形式管理进程,采用
多级反馈队列调度的算法模拟进程的控制。要求有创建、撤销、调度、阻塞、唤醒进程等功能。
1. 进程的状态转换图:
2. 各原语的功能说明:
-进程创建原语:进程创建是调用创建原语来实现。创建原语扫描系统的PCB链表,在找到一定PCB 链表之后,填入调用者提供的有关参数(这些参数包括:进程名、进程优先级P0、进程正文段起始地址d0、资源清单R0等),最后形成代表进程的PCB结构。
-进程撤销(终止): 撤消原语首先检查PCB进程链或进程家族,寻找所要撤消的进程是否存在。 如果找到了所要撤消的进程的PCB结构,则撤消原语释放该进程所占有的资源之后,把 对应的PCB结构从进程链或进程家族中摘下并返回给PCB空队列。如果被撤消的进程有自己的子进程,则撤消原语先撤消其子进程的PCB结构并释放子进程所 占用的资源之后,再撤消当前进程的PCB结构和释放其资源。
-阻塞原语:当发生引起阻塞的事件时,该原语被该进程自己调用来阻塞自己。阻塞原语在阻塞一 个进程时,由于该进程正处于执行状态,故应先中断处理机和保存该进程的CPU现场。然后将被阻塞进程置“阻塞”状态后插入等待队列中,再转进程调度程序选择新的就绪进程投入运行。
-唤醒原语:当等待队列中的进程所等待的事件发生时,等待该事件的所有进程都将被唤醒。一个 处于阻塞状态的进程不可能自己唤醒自己。唤醒一个进程有两种方法:一种是由系统进程唤醒。另一种是由事件发生进程唤醒。当由系统进程唤醒等待进程时,系统进程统一控制事件的发生并将“事件发生”这一消息通知等待进程。从而使得该进程因等待事件已发生而进入就绪队列。等待进程也可由事件发生进唤醒。由事件发生进程唤醒时,事件发生进程和被唤醒进程之间是合作关系。因此,唤醒原语既可被系统进程调用,也可被事件发生进程调用。我们称调用唤醒原语的进程为唤醒进程。
3. 多级反馈队列调度算法的描述:
(1) 应设置多个就绪队列,并为各个队列赋予不同的优先级。 第一个队列的优先级最高,第二个队列次之,其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同,在优先权愈高的队列中,为每个进程所规定的执行时间片就愈小。例如,第二个队列的时间片要比第一个队列的时间片长一倍,„„,第i+1个队列的时间片要比第i个队列的时间片长一倍。 图 3-5 是多级反馈队列算法的示意。
(2) 当一个新进程进入内存后,首先将它放入第一队列的末尾,按FCFS原则排队等待调度。当轮到该进程执行时,如它能在该时间片内完成,便可准备撤离系统;如果它在一个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾,再同样地按FCFS原则等待调度执行;如果它在第二队列中运行一个时间片后仍未完成,再依次将它放入第三队列,„„,如此下去,当一个长作业(进程)从第一队列依次降到第n队列后,在第n队列中便采取按时间片轮转的方式运行。
(3) 仅当第一队列空闲时,调度程序才调度第二队列中的进程运行; 仅当第1~(i-1) 队列均空时,才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时,又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列),则此时新进程将抢占正在运行进程的处理机,即由调度程序把正在运行的进程放回到第i队列的末尾,把处理机分
配给新到的高优先权进程。
4. 程序功能结构图:
5. 流程图:
6. 数据结构定义:
char name[20]; /*进程的名字*/
int supernumber; /*进程的优先级*/
int round; /*分配CPU的时间片*/
int cputime; /*CPU执行时间*/
int needtime; /*进程执行所需要的时间*/
char state; /*进程的状态,W——就绪态,R——执行态,F——完成态*/ int count; /*记录执行的次数*/
struct node *next; /*链表指针
*/
7. 主要变量的说明:
PCB *run=NULL,*finish=NULL; /*定义三个队列,就绪队列,执行队列和完成队列*/ ReadyQueue *Head = NULL; /*定义第一个就绪队列*/
int num; /*进程个数*/
int ReadyNum; /*就绪队列个数*/
8. 函数的说明:
void Output(); /*进程信息输出函数*/
void InsertFinish(PCB *in); /*将进程插入到完成队列尾部*/
void Insertsupernumber(ReadyQueue *in); /*创建就绪队列,规定优先数越小,优先级越低*/
void supernumberCreate(); /*创建就绪队列输入函数*/
void GetFirst(ReadyQueue *queue); /*取得某一个就绪队列中的队头进程*/ void InsertLast(PCB *in,ReadyQueue *queue); /*将进程插入到就绪队列尾部*/ void ProcessCreate(); /*进程创建函数*/
void RoundRun(ReadyQueue *timechip); /*时间片轮转调度算法*/
void MultiDispatch(); /*多级调度算法,每次执行一个时间片*/
三、 三、所用仪器、材料(设备名称、型号、规格等)。
计算机一台
四、 实验方法、步骤
# include
# include
# include
# include
typedef struct node /*进程节点信息*/
{
char name[20]; /*进程的名字*/
int supernumber; /*进程的优先级*/
int round; /*分配CPU的时间片*/
int cputime; /*CPU执行时间*/
int needtime; /*进程执行所需要的时间*/
char state; /*进程的状态,W——就绪态,R——执行态,F——完成态*/ int count; /*记录执行的次数*/
struct node *next; /*链表指针*/
}PCB;
typedef struct Queue /*多级就绪队列节点信息*/
{
PCB *LinkPCB; /*就绪队列中的进程队列指针*/
int supernumber; /*本就绪队列的优先级*/
int round; /*本就绪队列所分配的时间片*/
struct Queue *next; /*指向下一个就绪队列的链表指针*/
}ReadyQueue;
PCB *run=NULL,*finish=NULL; /*定义三个队列,就绪队列,执行队列和完成队列*/ ReadyQueue *Head = NULL; /*定义第一个就绪队列*/
int num; /*进程个数*/
int ReadyNum; /*就绪队列个数*/
void Output(); /*进程信息输出函数*/
void InsertFinish(PCB *in); /*将进程插入到完成队列尾部*/
void Insertsupernumber(ReadyQueue *in); /*创建就绪队列,规定优先数越小,优先级越低*/
void supernumberCreate(); /*创建就绪队列输入函数*/
void GetFirst(ReadyQueue *queue); /*取得某一个就绪队列中的队头进程*/
void InsertLast(PCB *in,ReadyQueue *queue); /*将进程插入到就绪队列尾部*/ void ProcessCreate(); /*进程创建函数*/
void RoundRun(ReadyQueue *timechip); /*时间片轮转调度算法*/
void MultiDispatch(); /*多级调度算法,每次执行一个时间片*/
void Output() /*进程信息输出函数*/
{
ReadyQueue *print = Head;
PCB *p;
printf("进程名\t优先级\t轮数\tcpu时间\t需要时间\t进程状态\t计数器\n"); while(print)
{
if(print ->LinkPCB != NULL) { p=print ->LinkPCB; while(p) { printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->supernumber,p->round,p->cputime,p->needtime,p->state,p->count);
p = p->next; } } print = print->next;
}
p = finish;
while(p!=NULL)
{
printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->supernumber,p->round,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%d\t\t%c\t\t%d\n",p->name,p->supernumber,p->round,p->cputime,p->needtime,p->state,p->count);
p = p->next;
}
}
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 Insertsupernumber(ReadyQueue *in) /*创建就绪队列,规定优先数越小,优先级越低*/
{
ReadyQueue *fst,*nxt;
fst = nxt = Head;
if(Head == NULL) /*如果没有队列,则为第一个元素*/
{
in->next = Head; Head = in;
}
else /*查到合适的位置进行插入*/
{
队头*/
if(in ->supernumber >= fst ->supernumber) /*比第一个还要大,则插入到{ in->next = Head; Head = 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 supernumberCreate() /*创建就绪队列输入函数*/
{
ReadyQueue *tmp;
int i;
static int j=0;
printf("输入就绪队列的个数:\n");
scanf("%d",&ReadyNum);
printf("每个就绪队列的CPU时间片:(优先级和时间片成反比)\n");
for(i = 0;i
{
if((tmp = (ReadyQueue *)malloc(sizeof(ReadyQueue)))==NULL) { perror("malloc"); exit(1); } tmp->round=int(pow(2.0,(++j))); /*输入此就绪队列中给每个进程所分配的CPU时间片*/
printf("%d \n",tmp->round); tmp ->supernumber = 50 - tmp->round; /*设置其优先级,时间片越高,其优先级越低*/
tmp ->LinkPCB = NULL; /*初始化其连接的进程队列为空*/ tmp ->next = NULL; Insertsupernumber(tmp); /*按照优先级从高到低,建立多个就绪队列*/ }
}
void GetFirst(ReadyQueue *queue) /*取得某一个就绪队列中的队头进程*/ {
run = queue ->LinkPCB;
if(queue ->LinkPCB != NULL)
{
run ->state = 'R'; queue ->LinkPCB = queue ->LinkPCB ->next; run ->next = NULL;
}
}
void ProcessCreate() /*进程创建函数*/
{
PCB *tmp;
int i;
static int j=1;
printf("输入进程的个数:\n");
scanf("%d",&num);
for(i = 0;i
{
if((tmp = (PCB *)malloc(sizeof(PCB)))==NULL) { perror("malloc"); exit(1); } printf("输入%d进程名字:\n",j); scanf("%s",tmp->name); getchar(); printf("输入%d进程时间:\n",j++);/*吸收回车符号*/ scanf("%d",&(tmp->needtime)); tmp ->cputime = 0; tmp ->state ='W'; tmp ->supernumber = 50 - tmp->needtime; /*设置其优先级,需要的时间越
多,优先级越低*/
tmp ->round = Head ->round; tmp ->count = 0; InsertLast(tmp,Head); /*按照优先级从高到低,插入到就绪队列*/ }
system("cls");
}
void InsertLast(PCB *in,ReadyQueue *queue) /*
{
PCB *fst;
fst = queue->LinkPCB;
if( queue->LinkPCB == NULL)
{
in->next = queue->LinkPCB;
queue->LinkPCB = in;
}
else
{
while(fst->next != NULL)
{
fst = fst->next;
}
in ->next = fst ->next;
fst ->next = in;
}
}
将进程插入到就绪队列尾部*/
void RoundRun(ReadyQueue *timechip) /*时间片轮转调度算法*/
{
int flag = 1;
GetFirst(timechip);
while(run != NULL)
{
while(flag)
{
run->count++;
run->cputime++;
run->needtime--;
if(run->needtime == 0) /*进程执行完毕*/
{
run ->state = 'F';
InsertFinish(run);
flag = 0;
}
else if(run->count == timechip ->round)/*时间片用完*/ {
run->state = 'W';
run->count = 0; /*计数器清零,为下次做准备*/
InsertLast(run,timechip);
flag = 0;
}
}
flag = 1;
GetFirst(timechip);
}
}
void MultiDispatch() /*多级调度算法,每次执行一个时间片*/
{
int flag = 1;
int k = 0;
ReadyQueue *point;
point = Head;
GetFirst(point);
while(run != NULL)
{
Output();
if(Head ->LinkPCB!=NULL)
point = Head;
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; /*计数器清零,为下次做准备*/ if(point ->next!=NULL) { run ->round = point->next ->round;/*设置其时间片是下一个就绪队列的时间片*/
InsertLast(run,point->next); /*将进程插入到下一个就绪队列中*/
flag = 0; } else { RoundRun(point); /*如果为最后一个就绪队列就调用时间片轮转算法*/
break; } } } flag = 1; if(point ->LinkPCB == NULL)/*就绪队列指针下移*/ point =point->next; if(point ->next ==NULL) { RoundRun(point); break; } GetFirst(point);
}
}
int main( )
{
printf("\t\t\t\t进程管理\n");
supernumberCreate(); /*创建就绪队列*/ ProcessCreate();/*创建就绪进程队列*/ printf("\t\t\t\t进程调度\n");
for(int i=0;i
Output(); /*输出最终的调度序列*/
return 0;
}
五、 实验过程原始记录(数据、图表、计算等)
六、
实验结果、分析和结论(误差分析与数据处理、成果总结等。其中,绘制
曲线图时必须用计算纸)
很多进程调度方法都有一定的局限性,如短进程优先的调度法,仅照顾了短进程而忽略了长进程,而且如果并未指明进程的长度,则段进程优先和基于进程长度的抢占调度算法,都将无法使用,而多级反馈队列调度算法,则不必事先知道各种进程所需的时间,而且还可以满足各种类型进程的需要,因而它是目前被公认为的一种较好的进程调度算法。
同时通过编写进程管理的算法,我大体掌握整个进程管理的各个环节,基本描述进程的数据结构,进程的各种状态之间的转换,以及进程的调度算法。加深了对进程的概念及进程调度算法的理解,并且提高链表的应用能力,达到提高编程能力的目的
在制作这个程序时,对于链表知识的欠缺是一个十分大的阻碍,在参照数据结构的同时我完成了这个实验,对我而言这是一个突破。同时也加深我对程序编写的兴趣。