使用动态优先权和时间片轮转的进程调度算法的模拟

河南师范大学计算机与信息工程学院计算机与信息工程学院设计性实验报告专业：计算机科学与技术年级/班级：2103级2015—2016学年第一学期课程名称操作系统指导教师张倩倩学号姓名1308114088郅伟远实验地点网络实验室216实验时间2015/12/5项目名称使用动态优先权和时间片轮转的进程调度算法的模拟实验类型设计性一、实验目的通过动态优先权调度算法的模拟加深进程概念和进程调度过程的理解。二、实验仪器或设备虚拟机三、总体设计（设计原理、设计方案及流程等）实验内容(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)state00248ready10347ready20644ready30545ready40446ready简单时间片轮转调度模拟程序见roundrobin.c，优先权调度大家请参考时间片轮转自行实现，有自己想法的同学可以按照自己的思路独立完成实验，而不用参考roundrobin.c程序。四、实验步骤（包括主要步骤、代码分析等）#includestdio.h#includestdlib.h#definegetpch(type)(type*)malloc(sizeof(type))structpcb{charname[10];charstate;intcount;intntime;intrtime;intpriority;structpcb*link;}*ready=NULL,*tail=NULL,*p;typedefstructpcbPCB;intslice;河南师范大学计算机与信息工程学院sort(){PCB*first,*second;intinsert=0;if((ready==NULL)||((p-priority)(ready-priority))){p-link=ready;ready=p;}else{first=ready;second=first-link;while(second!=NULL){if((p-priority)(second-priority)){p-link=second;first-link=p;second=NULL;insert=1;}else{first=first-link;second=second-link;}}if(insert==0)first-link=p;}}input(){inti,num;printf(\npleaseenteranumberofprocesses:);scanf(%d,&num);for(i=0;inum;i++){printf(\nprocessnumberNo.%d:\n,i);p=getpch(PCB);printf(\npleaseentertheprocessname:);scanf(%s,p-name);printf(\npleaseentertheprocessrunningtime:);河南师范大学计算机与信息工程学院scanf(%d,&p-ntime);printf(\npleaseentertheprioritynumber:);scanf(%d,&p-priority);printf(\n);p-rtime=0;p-state='w';p-count=0;p-link=NULL;sort();}printf(\npleaseenterthetimeslicesize:);scanf(%d,&slice);}intspace(){intl=0;PCB*pr=ready;while(pr!=NULL){l++;pr=pr-link;}return(l);}disp(PCB*pr){printf(\nqname\tstate\tcount\tntime\trtime\tpriority\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(%d\t,pr-priority);printf(\n);}check(){PCB*pr;printf(\n****thecurrentrunningprocessis:%s,p-name);disp(p);pr=ready;printf(\n****thecurrentreadyqueuestate:\n);while(pr!=NULL)河南师范大学计算机与信息工程学院{disp(pr);pr=pr-link;}}destroy(){printf(\nprocess[%s]finish.\n,p-name);free(p);}running(){inttempt;tempt=p-ntime-p-rtime;if(temptslice)p-rtime+=slice;elsep-rtime+=tempt;p-count++;check();if(p-rtime==p-ntime)destroy();else{p-priority-=3;p-state='w';sort();}}main(){intlen,h=0;charch;input();len=space();while((len!=0)&&(ready!=NULL)){h++;printf(\nTheexecutenumber:%d\n,h);p=ready;ready=p-link;p-link=NULL;p-state='R';running();河南师范大学计算机与信息工程学院}printf(\n\nallprocesseshavebeencompleted.\n);}[root@localhost~]#gcccmc.c-ocmc[root@localhost~]#./cmcpleaseenteranumberofprocesses:3processnumberNo.0:pleaseentertheprocessname:3pleaseentertheprocessrunningtime:2pleaseentertheprioritynumber:5processnumberNo.1:pleaseentertheprocessname:45pleaseentertheprocessrunningtime:8pleaseentertheprioritynumber:4processnumberNo.2:pleaseentertheprocessname:6pleaseentertheprocessrunningtime:4pleaseentertheprioritynumber:1pleaseenterthetimeslicesize:5Theexecutenumber:1****thecurrentrunningprocessis:3qnamestatecountntimertimepriority河南师范大学计算机与信息工程学院3R1225****thecurrentreadyqueuestate:qnamestatecountntimertimepriority45w0804qnamestatecountntimertimepriority6w0401process[3]finish.Theexecutenumber:2****thecurrentrunningprocessis:45qnamestatecountntimertimepriority45R1854****thecurrentreadyqueuestate:qnamestatecountntimertimepriority6w0401Theexecutenumber:3****thecurrentrunningprocessis:6qnamestatecountntimertimepriority6R1441****thecurrentreadyqueuestate:qnamestatecountntimertimepriority45w1851process[6]finish.Theexecutenumber:4****thecurrentrunningprocessis:45qnamestatecountntimertimepriority45R2881****thecurrentreadyqueuestate:河南师范大学计算机与信息工程学院process[45]finish.allprocesseshavebeencompleted.Pressanykeytocontinue五、结果分析与总结这次实验让我对动态优先权调度算法的实现过程有了更深层次的认识和理解，本实验陌生的指令不少，但在老师与同学的帮助下都一一解决了，同时在本次实验中也显露出了很多缺陷与不足，有很多细节没有注意到，希望在以后的实验中能够加以改正。2015年12月6日