动态优先权进程调度算法的模拟

河南师范大学计算机与信息工程学院计算机学院设计性实验报告专业:朱文焌年级/班级：20xx级网络工程2015—2016学年第一学期课程名称操作系统指导教师张倩倩本组成员学号姓名朱文焌实验地点计算机与信息工程学院216实验时间2015.11.20项目名称使用动态优先权的进程调度算法的模拟实验类型设计性一、实验目的通过动态优先权调度算法和时间片轮转调度算法的模拟加深进程概念和进程调度过程的理解。二、实验仪器或设备一台笔记本电脑或者是一台台式机三、总体设计（设计原理、设计方案及流程等）本实验的目的就是用在Linux下用C语言编程模拟N个进程采用高优先权优先（要求采用动态优先权）进程调度算法。已知时间片轮转算法，可以根据时间片轮转的思路加以修改就行了。时间轮转调度算法与动态优先权的区别就是时间片轮转是在FIFO进程调度的基础上，队列中的进程按照进入的顺序，每个进程每次都执行一个时间片；如果运行完就把该进程释放掉，如果在一个时间片内未结束就插到队列尾部。而动态优先权进程调度算法就是按照优先权的大小运行进程，如果一个时间片内未运行完，则将优先权数减3后再插入到队列中（不是队尾而是队列中的适当位置，该位置前面的节点的优先级数大于该节点的优先级数，后面的节点的count值小于该节点的count值）。四、实验要求：(1)在Linux下用C语言编程模拟N个进程采用高优先权优先（要求采用动态优先权）进程调度算法。为了清楚地观察每个进程的调度过程，程序应将每个时间片内的进程情况显示出来；(2)进程控制块是进程存在的唯一标志，因此，在模拟算法中每一个进程用一个进程控制块PCB来代表，PCB用一结构体表示。包括以下字段：进程标识数id，或者进程的名称name；进程优先数priority，并规定优先数越大的进程，其优先权越高；进程需要运行的CPU时间ntime；进程的运行时间rtime；进程状态state；队列指针next，用来将PCB排成队列。河南师范大学计算机与信息工程学院(3)进程在运行过程中其状态将在就绪、执行、阻塞（可选）、完成几种状态之间转换，同时进程可能处于不同的队列中，如就绪队列、阻塞队列（可选）。在两种调度算法中，考虑分别可以选择什么样的队列及如何实现进程的入队、出队操作；(4)为了便于处理，优先权调度每次也仅让进程执行一个时间片，若在一个时间片内未运行结束，调整进程优先级将其插入就绪队列，进行新一轮调度；(5)优先数改变原则：进程每运行若一个时间单位，优先数减3；进程在就绪队列中呆一个时间片，优先数增加1。（仅供参考，合理即可）(6)优先权调度中，对于遇到优先权一致的情况，可采用FCFS策略解决；(7)由于是模拟进程调度，所以，对被选中的进程并不实际启动运行，而是修改进程控制块的相关信息来模拟进程的一次运行；(8)为了清楚地观察诸进程的调度过程，程序应将每个时间片内的进程的情况显示出来，参照格式如下:idcputimeneedtimepriority(count)state00248ready(9)sort函数执行流程河南师范大学计算机与信息工程学院五、实验步骤（包括主要步骤、代码分析等）#includestdio.h#includestdlib.h#definegetpch(type)(type*)malloc(sizeof(type))structpcb{//定义进程控制块charname[10];//进程的名字charstate;//进程的状态intcount;//进程优先级intntime;//进程运行需要的CPU时间intrtime;//进程已运行的时间structpcb*link;//连接pcb的指针}*ready=NULL,*tail=NULL,*p;//就绪队列指针，队尾指针typedefstructpcbPCB;intslice=1;PCB*readyMaxProcess;intreadyQueNum=0;//就绪队列的进程数量sort()//将进程插入到就绪指针{PCB*q;if(ready==NULL)//队列为空，将p插入到队列中{ready=p;tail=p;}else//若就绪队列不为空，将p插入到队列{if(p-countready-count)//p指针所指节点的count值头的大于队列节点的count值，将p指针所指节点插入到对头{p-link=ready;ready=p;}else{boolm=false;q=ready;//q2=q1-link;while(m==false){if(tail-count=p-count)//若p的count值小于队尾指针所指节点的的count值的话，将p插到队尾{tail-link=p;河南师范大学计算机与信息工程学院tail=p;p-link=NULL;m=true;}else{if(q-count=p-count&&p-countq-link-count)//若p的count值大于队尾指针所指节点的的count值的话,将p所指节点插入到队列中指定位置//必须满足插入位置的前一个节点的count值大于p-count,并且满足插入位置的后一个节点的count值小于p-count{p-link=q-link;q-link=p;m=true;}else{q=q-link;//q2=q2-link;}}}}}}input(){inti,num;printf(\n请输入进程个数:);scanf(%d,&num);for(i=0;inum;i++){printf(\n进程号No.%d:\n,i);p=getpch(PCB);printf(\n请输入进程名:);scanf(%s,p-name);printf(\n请输入进程优先权数:);scanf(%d,&p-count);printf(\n请输入进程运行时间:);scanf(%d,&p-ntime);河南师范大学计算机与信息工程学院printf(\n);p-rtime=0;p-state='w';p-link=NULL;sort();//将进程p插入就绪队列ready中}printf(\n请输入时间片大小:);scanf(%d,&slice);}//获得就绪队列中进程的个数intspace(){PCB*pr=ready;while(pr!=NULL){readyQueNum++;pr=pr-link;}return(readyQueNum);}//显示进程disp(PCB*pr){printf(\nqname\tstate\tcount\tndtime\truntime\n);printf(|%s\t,pr-name);printf(|%c\t,pr-state);printf(|%d\t,pr-count);printf(|%d\t,pr-ntime);printf(|%d\t,pr-rtime);printf(\n);}//显示当前运行进程和就绪队列中进程的信息check(){PCB*pr;printf(\n****当前正在运行的进程是:%s,readyMaxProcess-name);disp(readyMaxProcess);pr=ready;printf(\n****当前就绪队列状态为:\n);while(pr!=NULL)河南师范大学计算机与信息工程学院{pr-count++;disp(pr);pr=pr-link;}}//撤销进程destroy(){printf(\n进程[%s]已完成.\n,readyMaxProcess-name);free(readyMaxProcess);//readyQueNum--;}//使当前进程运行一个时间片，若结束则撤销，否则插入就绪队列队尾running(){inttempt=0;tempt=readyMaxProcess-ntime-readyMaxProcess-rtime;if(temptslice)readyMaxProcess-rtime+=slice;elsereadyMaxProcess-rtime+=tempt;check();if(readyMaxProcess-rtime==readyMaxProcess-ntime)destroy();else{readyMaxProcess-count=readyMaxProcess-count-3;readyMaxProcess-state='w';p=readyMaxProcess;//再将队头节点readyMaxProcess插入到队列时，现将赋给另一个指针psort();}}main(){intlen,h=0;input();//输入进程并形成就绪队列len=space();//获得就绪队列中进程的个数while((len!=0)&&(ready!=NULL))//若就绪队列不为空河南师范大学计算机与信息工程学院{len=space();h++;printf(\nTheexecutenumber:%d\n,h);readyMaxProcess=ready;//将指向队优先级最大的节点的指针指向队头节点ready=ready-link;//改变对头指针readyMaxProcess-link=NULL;//将优先级最大的进程从队列中分裂出来readyMaxProcess-state='R';running();}printf(\n\n所有进程已经完成.\n);}进程名/进程属性运行所需时间ntime进程的优先权数进程a108进程b95进程c69六、实验结果河南师范大学计算机与信息工程学院河南师范大学计算机与信息工程学院七、结果分析与总结这个实验最主要就是理解动态优先权数调度算法的原理，利用c语言程序完成该过程的模拟。在编写该程序的时候采用了很多方法（如双向链表），但是都比较复杂，所以转向了在时间片轮转的基础上改进的方法。最主要的思想就是进程进队列，二次插入或者多次插入队列均采用按照优先权大小的顺序查找插入的适当位置。可以分为三种情况:1、直接插入到对头。2、插入到队尾。3、插入到队列中间。第一种必须满足进程的优先级大于队头结点的优先级；第二种是进程的优先级必须小于或者等于队尾结点的优先级数；第三种结点的值小于或者等于头结点的优先级数，并且大于队尾结点的优先级数。经过多次的调试程序，多次的失败，但是并未失去信心，知道得到正确的结果。付出可能会有收获，但不付出一定不会有收获。教师签名：年月日