昆明理工大学信息工程与自动化学院学生实验报告（2010 —2011 学年第二学期）课程名称：操作系统开课实验室：年月日目录一、实验目的 (1)二、实验原理及基本技术路线图 (1)1. 进程的状态转换图 (2)2. 各原语的功能说明 (2)3.多级反馈队列调度算法的描述 (3)4. 程序功能结构图 (4)5. 流程图 (4)6. 数据结构定义 (5)7. 主要变量的说明 (6)8. 函数的说明 (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 <stdio.h># include <stdlib.h># include <math.h># include <string.h>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 <ReadyNum; 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 < num; 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<80;i++) printf("*");printf("\n");MultiDispatch();/*算法开始*/Output(); /*输出最终的调度序列*/return 0;}五、实验过程原始记录(数据、图表、计算等)六、实验结果、分析和结论（误差分析与数据处理、成果总结等。