动态优先权进程调度算法的模拟说课讲解.pdf
动态优先权进程调度算法的模拟 精品文档 收集于网络，如有侵权请联系管理员删除 计算机学院设计性实验报告 专业:朱文焌 年级/班级：20 xx 级网络工程 20152016 学年第一学期 课程名称 操作系统 指导教师 张倩倩 本组成员 学号姓名 朱文焌 实验地点 计算机与信息工程学院 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)为了清楚地观察诸进程的调度过程，程序应将每个时间片内的进程的情况显示出来，参照格式如下:id cputime needtime priority(count)state 精品文档 收集于网络，如有侵权请联系管理员删除 0 0 2 48 ready(9)sort 函数执行流程 五、实验步骤（包括主要步骤、代码分析等）#include stdio.h#include#define getpch(type)(type*)malloc(sizeof(type)struct pcb /定义进程控制块 char name10;/进程的名字 char state;/进程的状态 int count;/进程优先级 int ntime;/进程运行需要的 CPU 时间 int rtime;/进程已运行的时间 struct pcb*link;/连接 pcb 的指针*ready=NULL,*tail=NULL,*p;/就绪队列指针，队尾指针 typedef struct pcb PCB;int slice=1;精品文档 收集于网络，如有侵权请联系管理员删除 PCB*readyMaxProcess;int readyQueNum=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 bool m=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()int i,num;printf(n 请输入进程个数:);scanf(%d,&num);for(i=0;iname);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);/获得就绪队列中进程的个数 int space()PCB*pr=ready;while(pr!=NULL)readyQueNum+;pr=pr-link;return(readyQueNum);/显示进程 disp(PCB*pr)printf(nqname tstate tcount tndtime truntime n);printf(|%st,pr-name);printf(|%ct,pr-state);printf(|%dt,pr-count);printf(|%dt,pr-ntime);printf(|%dt,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()int tempt=0;tempt=readyMaxProcess-ntime-readyMaxProcess-rtime;if(temptslice)readyMaxProcess-rtime+=slice;else readyMaxProcess-rtime+=tempt;check();if(readyMaxProcess-rtime=readyMaxProcess-ntime)destroy();else readyMaxProcess-count=readyMaxProcess-count-3;readyMaxProcess-state=w;精品文档 收集于网络，如有侵权请联系管理员删除 p=readyMaxProcess;/再将队头节点 readyMaxProcess 插入到队列时，现将赋给另一个指针 p sort();main()int len,h=0;input();/输入进程并形成就绪队列 len=space();/获得就绪队列中进程的个数 while(len!=0)&(ready!=NULL)/若就绪队列不为空 len=space();h+;printf(n The execute number:%d n,h);readyMaxProcess=ready;/将指向队优先级最大的节点的指针指向队头节点 ready=ready-link;/改变对头指针 readyMaxProcess-link=NULL;/将优先级最大的进程从队列中分裂出来 readyMaxProcess-state=R;running();printf(nn 所有进程已经完成.n);进程名/进程属性 运行所需时间ntime 进程的优先权数 进程 a 10 8 进程 b 9 5 进程 c 6 9 精品文档 收集于网络，如有侵权请联系管理员删除 六、实验结果 精品文档 收集于网络，如有侵权请联系管理员删除 七、结果分析与总结 这个实验最主要就是理解动态优先权数调度算法的原理，利用 c 语言程序完成该过程的模拟。在编写该程序的时候采用了很多方法（如双向链表），但是都比较复杂，所以转向了在时间片轮转的基础上改进的方法。最主要的思想就是进程进队列，二次插入或者多次插入队列均采用按照优先权大小的顺序查找插入的适当位置。可以分为三种情况:1、直接插入到对头。2、插入到队尾。3、插入到队列中间。第一种必须满足进程的优先级大于队头结点的优先级；第二种是进程的优先级必须小于或者等于队尾结点的优先级数；第三种结点的值小精品文档 收集于网络，如有侵权请联系管理员删除 于或者等于头结点的优先级数，并且大于队尾结点的优先级数。经过多次的调试程序，多次的失败，但是并未失去信心，知道得到正确的结果。付出可能会有收获，但不付出一定不会有收获。教师签名：年 月 日
